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\n", 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\n", 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 } 274