#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"

enum {
       Allocated       = 1UL<<31,
};

typedef struct Mapent Mapent;
struct Mapent
{
       ulong   type;
       uvlong  addr;
       uvlong  size;
};

static struct {
       Lock;
       int     n;
       int     m;
       Mapent  a[256];
} mapalloc;

static void
dump1(Mapent *e)
{
       print("%.16llux-%.16llux %lux\n", e->addr, e->addr + e->size, e->type);
}

static int
insert(uvlong addr, uvlong size, ulong type)
{
       Mapent *e;

       if(size == 0 || addr == -1 || addr + size-1 < addr)
               return 0;

       if(mapalloc.n+mapalloc.m >= nelem(mapalloc.a))
               return 0;

       e = &mapalloc.a[mapalloc.n + mapalloc.m++];
       e->type = type;
       e->addr = addr;
       e->size = size;

       return 1;
}

static Mapent*
lookup(uvlong addr)
{
       Mapent *i, *e;

       if(addr == -1)
               return nil;
       for(i = mapalloc.a, e = i + mapalloc.n; i < e; i++){
               if(i->addr > addr)
                       break;
               if(addr - i->addr < i->size)
                       return i;
       }
       return nil;
}

static int
compare(void *a, void *b)
{
       Mapent *ma = a, *mb = b;

       if(ma->addr < mb->addr)
               return -1;
       if(ma->addr > mb->addr)
               return 1;

       if(ma->type < mb->type)
               return -1;
       if(ma->type > mb->type)
               return 1;

       return 0;
}

static void
sort(void)
{
       Mapent *d, *i, *j, *e;

Again:
       if(mapalloc.m == 0)
               return;
       mapalloc.n += mapalloc.m;
       mapalloc.m = 0;

       qsort(mapalloc.a, mapalloc.n, sizeof(*e), compare);

       d = i = mapalloc.a;
       e = i + mapalloc.n;
       while(i < e){
               if(i->size == 0)
                       goto Skip;
               for(j = i+1; j < e; j++){
                       if(j->size == 0)
                               continue;
                       if(j->addr - i->addr >= i->size)
                               break;
                       if(j->type <= i->type){
                               if(j->addr - i->addr + j->size <= i->size)
                                       j->size = 0;
                               else {
                                       j->size -= i->addr + i->size - j->addr;
                                       j->addr = i->addr + i->size;
                               }
                               continue;
                       }
                       if(j->addr - i->addr + j->size < i->size)
                               if(!insert(j->addr + j->size, i->size - (j->addr + j->size - i->addr), i->type))
                                       continue;
                       i->size = j->addr - i->addr;
                       if(i->size == 0)
                               goto Skip;
               }
               if(d > mapalloc.a){
                       j = d-1;
                       if(i->addr - j->addr == j->size && i->type == j->type){
                               j->size += i->size;
                               i->size = 0;
                               goto Skip;
                       }
               }
               memmove(d, i, sizeof(*i));
               d++;
       Skip:
               i++;
       }
       if(mapalloc.m > 0)
               memmove(d, e, mapalloc.m*sizeof(*e));
       mapalloc.n = d - mapalloc.a;
       goto Again;
}

void
memmapdump(void)
{
       int i;

       lock(&mapalloc);
       sort();
       for(i = 0; i < mapalloc.n; i++)
               dump1(&mapalloc.a[i]);
       unlock(&mapalloc);
}

uvlong
memmapnext(uvlong addr, ulong type)
{
       Mapent *i, *e;

       lock(&mapalloc);
       sort();
       for(i = mapalloc.a, e = i+mapalloc.n; i < e; i++){
               if(((i->type ^ type) & ~Allocated) == 0
               && (addr == -1 || i->addr > addr)){
                       addr = i->addr;
                       unlock(&mapalloc);
                       return addr;
               }
       }
       unlock(&mapalloc);
       return -1;
}

uvlong
memmapsize(uvlong addr, uvlong align)
{
       Mapent *i;
       uvlong size;

       size = 0;
       lock(&mapalloc);
       sort();
       if((i = lookup(addr)) != nil){
               if(align){
                       addr += align-1;
                       addr &= ~(align-1);
               }
               if(addr - i->addr < i->size)
                       size = i->size - (addr - i->addr);
       }
       unlock(&mapalloc);
       return size;
}

void
memmapadd(uvlong addr, uvlong size, ulong type)
{
       type &= ~Allocated;
       lock(&mapalloc);
       if(insert(addr, size, type))
               if(mapalloc.n+mapalloc.m >= nelem(mapalloc.a)-1)
                       sort();
       unlock(&mapalloc);
}

uvlong
memmapalloc(uvlong addr, uvlong size, uvlong align, ulong type)
{
       Mapent *i, *e;

       type &= ~Allocated;
       lock(&mapalloc);
       sort();
       if(addr != -1){
               i = lookup(addr);
               if(i == nil || i->type != type)
                       goto Fail;
               if(align){
                       addr += align-1;
                       addr &= ~(align-1);
                       if(addr - i->addr >= i->size)
                               goto Fail;
               }
               if(addr - i->addr + size > i->size)
                       goto Fail;
Alloc:
               if(size > 0 && !insert(addr, size, type|Allocated))
                       goto Fail;
               unlock(&mapalloc);
               return addr;
       }
       e = mapalloc.a + mapalloc.n;
       for(i = mapalloc.a; i < e; i++){
               if(i->type != type)
                       continue;
               addr = i->addr;
               if(align){
                       addr += align-1;
                       addr &= ~(align-1);
                       if(addr - i->addr >= i->size)
                               continue;
               }
               if(addr - i->addr + size <= i->size)
                       goto Alloc;
       }
Fail:
       unlock(&mapalloc);
       return -1;
}

void
memmapfree(uvlong addr, uvlong size, ulong type)
{
       Mapent *i;

       lock(&mapalloc);
       sort();
       i = lookup(addr);
       if(i == nil
       || i->type != (type|Allocated)
       || addr - i->addr + size > i->size){
               unlock(&mapalloc);
               return;
       }
       if(i->addr < addr)
               insert(i->addr, addr - i->addr, i->type);
       if(addr - i->addr + size < i->size)
               insert(addr+size, addr - i->addr + i->size - size, i->type);
       i->type &= ~Allocated;
       unlock(&mapalloc);
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.