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 = 0xDeadBabe, 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 static void 46 ixprt() 47 { 48 xsummary(); 49 ixsummary(); 50 } 51 52 void 53 xinit(void) 54 { 55 Hole *h, *eh; 56 57 eh = &xlists.hole[Nhole-1]; 58 for(h = xlists.hole; h < eh; h++) 59 h->link = h+1; 60 61 xlists.flist = xlists.hole; 62 63 if(conf.npage1) 64 xhole(conf.base1, conf.npage1*BY2PG); 65 conf.npage1 = conf.base1+(conf.npage1*BY2PG); 66 67 if(conf.npage0) 68 xhole(conf.base0, conf.npage0*BY2PG); 69 conf.npage0 = conf.base0+(conf.npage0*BY2PG); 70 71 /* Save the bounds of kernel alloc memory for kernel mmu mapping */ 72 conf.base0 = (ulong)KADDR(conf.base0); 73 conf.base1 = (ulong)KADDR(conf.base1); 74 conf.npage0 = (ulong)KADDR(conf.npage0); 75 conf.npage1 = (ulong)KADDR(conf.npage1); 76 77 debugkey('x', "xalloc/ialloc", ixprt, 0); 78 } 79 80 void* 81 xspanalloc(ulong size, int align, ulong span) 82 { 83 ulong a, v, t; 84 85 a = (ulong)xalloc(size+align+span); 86 if(a == 0) 87 panic("xspanalloc: %lud %d %lux\n", size, align, span); 88 89 if(span > 2) { 90 v = (a + span) & ~(span-1); 91 t = v - a; 92 if(t > 0) 93 xhole(PADDR(a), t); 94 t = a + span - v; 95 if(t > 0) 96 xhole(PADDR(v+size+align), t); 97 } 98 else 99 v = a; 100 101 if(align > 1) 102 v = (v + align) & ~(align-1); 103 104 return (void*)v; 105 } 106 107 void* 108 xallocz(ulong size, int zero) 109 { 110 Xhdr *p; 111 Hole *h, **l; 112 113 size += BY2V + sizeof(Xhdr); 114 size &= ~(BY2V-1); 115 116 ilock(&xlists); 117 l = &xlists.table; 118 for(h = *l; h; h = h->link) { 119 if(h->size >= size) { 120 p = (Xhdr*)h->addr; 121 h->addr += size; 122 h->size -= size; 123 if(h->size == 0) { 124 *l = h->link; 125 h->link = xlists.flist; 126 xlists.flist = h; 127 } 128 iunlock(&xlists); 129 p = KADDR(p); 130 p->magix = Magichole; 131 p->size = size; 132 if(zero) 133 memset(p->data, 0, size); 134 return p->data; 135 } 136 l = &h->link; 137 } 138 iunlock(&xlists); 139 return nil; 140 } 141 142 void* 143 xalloc(ulong size) 144 { 145 return xallocz(size, 1); 146 } 147 148 void 149 xfree(void *p) 150 { 151 Xhdr *x; 152 153 x = (Xhdr*)((ulong)p - datoff); 154 if(x->magix != Magichole) { 155 xsummary(); 156 panic("xfree(0x%lux) 0x%lux!=0x%lux", p, (ulong)Magichole, x->magix); 157 } 158 xhole(PADDR(x), x->size); 159 } 160 161 int 162 xmerge(void *vp, void *vq) 163 { 164 Xhdr *p, *q; 165 166 p = (Xhdr*)(((ulong)vp - offsetof(Xhdr, data[0]))); 167 q = (Xhdr*)(((ulong)vq - offsetof(Xhdr, data[0]))); 168 if(p->magix != Magichole || q->magix != Magichole) { 169 xsummary(); 170 panic("xmerge(%#p, %#p) bad magic %#lux, %#lux\n", 171 vp, vq, p->magix, q->magix); 172 } 173 if((uchar*)p+p->size == (uchar*)q) { 174 p->size += q->size; 175 return 1; 176 } 177 return 0; 178 } 179 180 void 181 xhole(ulong addr, ulong size) 182 { 183 ulong top; 184 Hole *h, *c, **l; 185 186 if(size == 0) 187 return; 188 189 top = addr + size; 190 ilock(&xlists); 191 l = &xlists.table; 192 for(h = *l; h; h = h->link) { 193 if(h->top == addr) { 194 h->size += size; 195 h->top = h->addr+h->size; 196 c = h->link; 197 if(c && h->top == c->addr) { 198 h->top += c->size; 199 h->size += c->size; 200 h->link = c->link; 201 c->link = xlists.flist; 202 xlists.flist = c; 203 } 204 iunlock(&xlists); 205 return; 206 } 207 if(h->addr > addr) 208 break; 209 l = &h->link; 210 } 211 if(h && top == h->addr) { 212 h->addr -= size; 213 h->size += size; 214 iunlock(&xlists); 215 return; 216 } 217 218 if(xlists.flist == nil) { 219 iunlock(&xlists); 220 print("xfree: no free holes, leaked %lud bytes\n", size); 221 return; 222 } 223 224 h = xlists.flist; 225 xlists.flist = h->link; 226 h->addr = addr; 227 h->top = top; 228 h->size = size; 229 h->link = *l; 230 *l = h; 231 iunlock(&xlists); 232 } 233 234 void 235 xsummary(void) 236 { 237 int i; 238 Hole *h; 239 240 i = 0; 241 for(h = xlists.flist; h; h = h->link) 242 i++; 243 244 print("%d holes free\n", i); 245 i = 0; 246 for(h = xlists.table; h; h = h->link) { 247 print("%.8lux %.8lux %lud\n", h->addr, h->top, h->size); 248 i += h->size; 249 } 250 print("%d bytes free\n", i); 251 } 252