sys/src/9/port/xalloc.c

   1 #include "u.h"
   2 #include "../port/lib.h"
   3 #include "mem.h"
   4 #include "dat.h"
   5 #include "fns.h"
   6
   7 enum
   8 {
   9         Nhole           = 128,
  10         Magichole       = 0x484F4C45,                   /* HOLE */
  11 };
  12
  13 typedef struct Hole Hole;
  14 typedef struct Xalloc Xalloc;
  15 typedef struct Xhdr Xhdr;
  16
  17 struct Hole
  18 {
  19         ulong   addr;
  20         ulong   size;
  21         ulong   top;
  22         Hole*   link;
  23 };
  24
  25 struct Xhdr
  26 {
  27         ulong   size;
  28         ulong   magix;
  29         char    data[];
  30 };
  31
  32 struct Xalloc
  33 {
  34         Lock;
  35         Hole    hole[Nhole];
  36         Hole*   flist;
  37         Hole*   table;
  38 };
  39
  40 static Xalloc   xlists;
  41
  42 void
  43 xinit(void)
  44 {
  45         int i, n, upages, kpages;
  46         ulong maxpages;
  47         Confmem *m;
  48         Pallocmem *pm;
  49         Hole *h, *eh;
  50
  51         eh = &xlists.hole[Nhole-1];
  52         for(h = xlists.hole; h < eh; h++)
  53                 h->link = h+1;
  54
  55         xlists.flist = xlists.hole;
  56
  57         upages = conf.upages;
  58         kpages = conf.npage - upages;
  59         pm = palloc.mem;
  60         for(i=0; i<nelem(conf.mem); i++){
  61                 m = &conf.mem[i];
  62                 n = m->npage;
  63                 if(n > kpages)
  64                         n = kpages;
  65                 /* don't try to use non-KADDR-able memory for kernel */
  66                 maxpages = cankaddr(m->base)/BY2PG;
  67                 if(n > maxpages)
  68                         n = maxpages;
  69                 /* first give to kernel */
  70                 if(n > 0){
  71                         m->kbase = (ulong)KADDR(m->base);
  72                         m->klimit = (ulong)KADDR(m->base+n*BY2PG);
  73                         xhole(m->base, n*BY2PG);
  74                         kpages -= n;
  75                 }
  76                 /* if anything left over, give to user */
  77                 if(n < m->npage){
  78                         if(pm >= palloc.mem+nelem(palloc.mem)){
  79                                 print("xinit: losing %lud pages\n", m->npage-n);
  80                                 continue;
  81                         }
  82                         pm->base = m->base+n*BY2PG;
  83                         pm->npage = m->npage - n;
  84                         pm++;
  85                 }
  86         }
  87         xsummary();
  88 }
  89
  90 void*
  91 xspanalloc(ulong size, int align, ulong span)
  92 {
  93         ulong a, v, t;
  94         a = (ulong)xalloc(size+align+span);
  95         if(a == 0)
  96                 panic("xspanalloc: %lud %d %lux", size, align, span);
  97
  98         if(span > 2) {
  99                 v = (a + span) & ~(span-1);
 100                 t = v - a;
 101                 if(t > 0)
 102                         xhole(PADDR(a), t);
 103                 t = a + span - v;
 104                 if(t > 0)
 105                         xhole(PADDR(v+size+align), t);
 106         }
 107         else
 108                 v = a;
 109
 110         if(align > 1)
 111                 v = (v + align) & ~(align-1);
 112
 113         return (void*)v;
 114 }
 115
 116 void*
 117 xallocz(ulong size, int zero)
 118 {
 119         Xhdr *p;
 120         Hole *h, **l;
 121
 122         /* add room for magix & size overhead, round up to nearest vlong */
 123         size += BY2V + offsetof(Xhdr, data[0]);
 124         size &= ~(BY2V-1);
 125
 126         ilock(&xlists);
 127         l = &xlists.table;
 128         for(h = *l; h; h = h->link) {
 129                 if(h->size >= size) {
 130                         p = (Xhdr*)KADDR(h->addr);
 131                         h->addr += size;
 132                         h->size -= size;
 133                         if(h->size == 0) {
 134                                 *l = h->link;
 135                                 h->link = xlists.flist;
 136                                 xlists.flist = h;
 137                         }
 138                         iunlock(&xlists);
 139                         if(zero)
 140                                 memset(p, 0, size);
 141                         p->magix = Magichole;
 142                         p->size = size;
 143                         return p->data;
 144                 }
 145                 l = &h->link;
 146         }
 147         iunlock(&xlists);
 148         return nil;
 149 }
 150
 151 void*
 152 xalloc(ulong size)
 153 {
 154         return xallocz(size, 1);
 155 }
 156
 157 void
 158 xfree(void *p)
 159 {
 160         Xhdr *x;
 161
 162         x = (Xhdr*)((ulong)p - offsetof(Xhdr, data[0]));
 163         if(x->magix != Magichole) {
 164                 xsummary();
 165                 panic("xfree(%#p) %#ux != %#lux", p, Magichole, x->magix);
 166         }
 167         xhole(PADDR((uintptr)x), x->size);
 168 }
 169
 170 int
 171 xmerge(void *vp, void *vq)
 172 {
 173         Xhdr *p, *q;
 174
 175         p = (Xhdr*)(((ulong)vp - offsetof(Xhdr, data[0])));
 176         q = (Xhdr*)(((ulong)vq - offsetof(Xhdr, data[0])));
 177         if(p->magix != Magichole || q->magix != Magichole) {
 178                 int i;
 179                 ulong *wd;
 180                 void *badp;
 181
 182                 xsummary();
 183                 badp = (p->magix != Magichole? p: q);
 184                 wd = (ulong *)badp - 12;
 185                 for (i = 24; i-- > 0; ) {
 186                         print("%#p: %lux", wd, *wd);
 187                         if (wd == badp)
 188                                 print(" <-");
 189                         print("\n");
 190                         wd++;
 191                 }
 192                 panic("xmerge(%#p, %#p) bad magic %#lux, %#lux",
 193                         vp, vq, p->magix, q->magix);
 194         }
 195         if((uchar*)p+p->size == (uchar*)q) {
 196                 p->size += q->size;
 197                 return 1;
 198         }
 199         return 0;
 200 }
 201
 202 void
 203 xhole(ulong addr, ulong size)
 204 {
 205         ulong top;
 206         Hole *h, *c, **l;
 207
 208         if(size == 0)
 209                 return;
 210
 211         top = addr + size;
 212         ilock(&xlists);
 213         l = &xlists.table;
 214         for(h = *l; h; h = h->link) {
 215                 if(h->top == addr) {
 216                         h->size += size;
 217                         h->top = h->addr+h->size;
 218                         c = h->link;
 219                         if(c && h->top == c->addr) {
 220                                 h->top += c->size;
 221                                 h->size += c->size;
 222                                 h->link = c->link;
 223                                 c->link = xlists.flist;
 224                                 xlists.flist = c;
 225                         }
 226                         iunlock(&xlists);
 227                         return;
 228                 }
 229                 if(h->addr > addr)
 230                         break;
 231                 l = &h->link;
 232         }
 233         if(h && top == h->addr) {
 234                 h->addr -= size;
 235                 h->size += size;
 236                 iunlock(&xlists);
 237                 return;
 238         }
 239
 240         if(xlists.flist == nil) {
 241                 iunlock(&xlists);
 242                 print("xfree: no free holes, leaked %lud bytes\n", size);
 243                 return;
 244         }
 245
 246         h = xlists.flist;
 247         xlists.flist = h->link;
 248         h->addr = addr;
 249         h->top = top;
 250         h->size = size;
 251         h->link = *l;
 252         *l = h;
 253         iunlock(&xlists);
 254 }
 255
 256 void
 257 xsummary(void)
 258 {
 259         int i;
 260         Hole *h;
 261
 262         i = 0;
 263         for(h = xlists.flist; h; h = h->link)
 264                 i++;
 265
 266         print("%d holes free\n", i);
 267         i = 0;
 268         for(h = xlists.table; h; h = h->link) {
 269                 print("%.8lux %.8lux %lud\n", h->addr, h->top, h->size);
 270                 i += h->size;
 271         }
 272         print("%d bytes free\n", i);
 273 }