ref: 556618eb07d1ac6e2c629a60acd53c45d53261be
dir: /sys/src/9/port/memmap.c/
#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); }