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 = vp; 167 if((uchar*)vp+p->size == (uchar*)vq) { 168 q = vq; 169 p->size += q->size; 170 return 1; 171 } 172 return 0; 173 } 174 175 void 176 xhole(ulong addr, ulong size) 177 { 178 ulong top; 179 Hole *h, *c, **l; 180 181 if(size == 0) 182 return; 183 184 top = addr + size; 185 ilock(&xlists); 186 l = &xlists.table; 187 for(h = *l; h; h = h->link) { 188 if(h->top == addr) { 189 h->size += size; 190 h->top = h->addr+h->size; 191 c = h->link; 192 if(c && h->top == c->addr) { 193 h->top += c->size; 194 h->size += c->size; 195 h->link = c->link; 196 c->link = xlists.flist; 197 xlists.flist = c; 198 } 199 iunlock(&xlists); 200 return; 201 } 202 if(h->addr > addr) 203 break; 204 l = &h->link; 205 } 206 if(h && top == h->addr) { 207 h->addr -= size; 208 h->size += size; 209 iunlock(&xlists); 210 return; 211 } 212 213 if(xlists.flist == nil) { 214 iunlock(&xlists); 215 print("xfree: no free holes, leaked %lud bytes\n", size); 216 return; 217 } 218 219 h = xlists.flist; 220 xlists.flist = h->link; 221 h->addr = addr; 222 h->top = top; 223 h->size = size; 224 h->link = *l; 225 *l = h; 226 iunlock(&xlists); 227 } 228 229 void 230 xsummary(void) 231 { 232 int i; 233 Hole *h; 234 235 i = 0; 236 for(h = xlists.flist; h; h = h->link) 237 i++; 238 239 print("%d holes free\n", i); 240 i = 0; 241 for(h = xlists.table; h; h = h->link) { 242 print("%.8lux %.8lux %lud\n", h->addr, h->top, h->size); 243 i += h->size; 244 } 245 print("%d bytes free\n", i); 246 } 247