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