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