![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Plan 9 NeXT] / lucent / sys / src / 9 / port|
Return to alloc.c CVS log | Up to [Plan 9 NeXT] / lucent / sys / src / 9 / port |
1.1 root 1: #include "u.h"
2: #include "../port/lib.h"
3: #include "mem.h"
4: #include "dat.h"
5: #include "fns.h"
6: #include "error.h"
7:
8:
9: /*
10: * Plan 9 has two kernel allocators, the x... routines provide a first
11: * fit hole allocator which should be used for permanent or large structures.
12: * Routines are provided to allocate aligned memory which does not cross
13: * arbitrary 2^n boundaries. A second allocator malloc, smalloc, free is
14: * a 2n bucket allocator which steals from the x routines. This should
15: * be used for small frequently used structures.
16: */
17:
18: #define nil ((void*)0)
19: #define datoff ((ulong)((Xhdr*)0)->data)
20: #define bdatoff ((ulong)((Bucket*)0)->data)
21:
22: enum
23: {
24: Maxpow = 18,
25: CUTOFF = 12,
26: Nhole = 128,
27: Magichole = 0xDeadBabe,
28: Magic2n = 0xFeedBeef,
29: Spanlist = 64,
30:
31: NTRACE = 20,
32: };
33:
34: typedef struct Hole Hole;
35: typedef struct Xalloc Xalloc;
36: typedef struct Xhdr Xhdr;
37: typedef struct Bucket Bucket;
38: typedef struct Arena Arena;
39:
40: struct Hole
41: {
42: ulong addr;
43: ulong size;
44: ulong top;
45: Hole *link;
46: };
47:
48: struct Xhdr
49: {
50: ulong size;
51: ulong magix;
52: char data[1];
53: };
54:
55: struct Xalloc
56: {
57: Lock;
58: Hole hole[Nhole];
59: Hole *flist;
60: Hole *table;
61: };
62:
63: struct Bucket
64: {
65: int size;
66: int magic;
67: Bucket *next;
68: ulong pc;
69: char data[1];
70: };
71:
72: struct Arena
73: {
74: Lock;
75: Bucket *btab[Maxpow];
76: int nbuck[Maxpow];
77: struct{
78: ulong pc;
79: ulong alloc;
80: ulong free;
81: } trace[NTRACE];
82: QLock rq;
83: Rendez r;
84: };
85:
86: static Arena arena;
87: static Xalloc xlists;
88:
89: void
90: xinit(void)
91: {
92: Hole *h, *eh;
93: int up, np0, np1;
94:
95: eh = &xlists.hole[Nhole-1];
96: for(h = xlists.hole; h < eh; h++)
97: h->link = h+1;
98:
99: xlists.flist = xlists.hole;
100:
101: up = conf.upages;
102: np1 = up;
103: if(np1 > conf.npage1)
104: np1 = conf.npage1;
105:
106: palloc.p1 = conf.base1 + (conf.npage1 - np1)*BY2PG;
107: conf.npage1 -= np1;
108: xhole(conf.base1, conf.npage1*BY2PG);
109: conf.npage1 = conf.base1+(conf.npage1*BY2PG);
110: up -= np1;
111:
112: np0 = up;
113: if(np0 > conf.npage0)
114: np0 = conf.npage0;
115:
116: palloc.p0 = conf.base0 + (conf.npage0 - np0)*BY2PG;
117: conf.npage0 -= np0;
118: xhole(conf.base0, conf.npage0*BY2PG);
119: conf.npage0 = conf.base0+(conf.npage0*BY2PG);
120:
121: palloc.np0 = np0;
122: palloc.np1 = np1;
123: /* Save the bounds of kernel alloc memory for kernel mmu mapping */
124: conf.base0 = (ulong)KADDR(conf.base0);
125: conf.base1 = (ulong)KADDR(conf.base1);
126: conf.npage0 = (ulong)KADDR(conf.npage0);
127: conf.npage1 = (ulong)KADDR(conf.npage1);
128: }
129:
130: /*
131: * NB. spanalloc memory will cause a panic if free'd
132: */
133: void*
134: xspanalloc(ulong size, int align, ulong span)
135: {
136: int i, j;
137: ulong a, p, sinc;
138: ulong ptr[Spanlist];
139:
140: sinc = size/8;
141: span = ~(span-1);
142: for(i = 0; i < Spanlist; i++) {
143: p = (ulong)xalloc(size+align);
144: if(p == 0)
145: break;
146:
147: a = p+align;
148: a &= ~(align-1);
149: if((a&span) == ((a+size)&span)) {
150: for(j = 0; j < i; j++)
151: if(ptr[j])
152: xfree((void*)ptr[j]);
153:
154: return (void*)a;
155: }
156: xfree((void*)p);
157: ptr[i] = (ulong)xalloc(sinc);
158: }
159: USED(sinc);
160: xsummary();
161: panic("xspanalloc: %d %d %lux\n", size, align, span);
162: return 0;
163: }
164:
165: void*
166: xalloc(ulong size)
167: {
168: Xhdr *p;
169: Hole *h, **l;
170:
171: size += BY2WD + sizeof(Xhdr);
172: size &= ~(BY2WD-1);
173:
174: lock(&xlists);
175: l = &xlists.table;
176: for(h = *l; h; h = h->link) {
177: if(h->size >= size) {
178: p = (Xhdr*)h->addr;
179: h->addr += size;
180: h->size -= size;
181: if(h->size == 0) {
182: *l = h->link;
183: h->link = xlists.flist;
184: xlists.flist = h;
185: }
186: unlock(&xlists);
187: p = KADDR(p);
188: memset(p, 0, size);
189: p->magix = Magichole;
190: p->size = size;
191: return p->data;
192: }
193: l = &h->link;
194: }
195: unlock(&xlists);
196: return nil;
197: }
198:
199: void
200: xfree(void *p)
201: {
202: Xhdr *x;
203:
204: x = (Xhdr*)((ulong)p - datoff);
205: if(x->magix != Magichole)
206: panic("xfree");
207:
208: xhole(PADDR(x), x->size);
209: }
210:
211: void
212: xhole(ulong addr, ulong size)
213: {
214: ulong top;
215: Hole *h, *c, **l;
216:
217: if(size == 0)
218: return;
219:
220: top = addr + size;
221: lock(&xlists);
222: l = &xlists.table;
223: for(h = *l; h; h = h->link) {
224: if(h->top == addr) {
225: h->size += size;
226: h->top = h->addr+h->size;
227: c = h->link;
228: if(c && h->top == c->addr) {
229: h->top += c->size;
230: h->size += c->size;
231: h->link = c->link;
232: c->link = xlists.flist;
233: xlists.flist = c;
234: }
235: unlock(&xlists);
236: return;
237: }
238: if(h->addr > addr)
239: break;
240: l = &h->link;
241: }
242: if(h && top == h->addr) {
243: h->addr -= size;
244: h->size += size;
245: unlock(&xlists);
246: return;
247: }
248:
249: if(xlists.flist == nil) {
250: unlock(&xlists);
251: print("xfree: no free holes, leaked %d bytes\n", size);
252: return;
253: }
254:
255: h = xlists.flist;
256: xlists.flist = h->link;
257: h->addr = addr;
258: h->top = top;
259: h->size = size;
260: h->link = *l;
261: *l = h;
262: unlock(&xlists);
263: }
264:
265: void
266: alloctrace(void *p, ulong pc)
267: {
268: Bucket *bp;
269: int i;
270:
271: bp = (Bucket*)((ulong)p - bdatoff);
272: if(bp->size != 13)
273: return;
274: bp->pc = pc;
275: lock(&arena);
276: for(i = 0; i < NTRACE; i++){
277: if(arena.trace[i].pc == 0)
278: arena.trace[i].pc = pc;
279: if(arena.trace[i].pc == pc){
280: arena.trace[i].alloc++;
281: break;
282: }
283: }
284: unlock(&arena);
285: }
286:
287: void*
288: malloc(ulong size)
289: {
290: ulong next;
291: int pow, n;
292: Bucket *bp, *nbp;
293:
294: for(pow = 3; pow < Maxpow; pow++)
295: if(size <= (1<<pow))
296: goto good;
297:
298: return nil;
299: good:
300: /* Allocate off this list */
301: lock(&arena);
302: bp = arena.btab[pow];
303: if(bp) {
304: arena.btab[pow] = bp->next;
305: if(bp->magic != 0 || bp->size != pow){
306: unlock(&arena);
307: panic("malloc bp %lux magic %lux size %d next %lux pow %d", bp,
308: bp->magic, bp->size, bp->next, pow);
309: }
310: bp->magic = Magic2n;
311: unlock(&arena);
312:
313: memset(bp->data, 0, size);
314: bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
315: return bp->data;
316: }
317: unlock(&arena);
318:
319: size = sizeof(Bucket)+(1<<pow);
320: size += 3;
321: size &= ~3;
322:
323: if(pow < CUTOFF) {
324: n = (CUTOFF-pow)+2;
325: bp = xalloc(size*n);
326: if(bp == nil)
327: return nil;
328:
329: nbp = bp;
330: lock(&arena);
331: arena.nbuck[pow] += n;
332: while(--n) {
333: next = (ulong)nbp+size;
334: nbp = (Bucket*)next;
335: nbp->size = pow;
336: nbp->next = arena.btab[pow];
337: arena.btab[pow] = nbp;
338: }
339: unlock(&arena);
340: }
341: else {
342: bp = xalloc(size);
343: if(bp == nil)
344: return nil;
345:
346: arena.nbuck[pow]++;
347: }
348:
349: bp->size = pow;
350: bp->magic = Magic2n;
351: bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
352: return bp->data;
353: }
354:
355: void*
356: smalloc(ulong size)
357: {
358: char *s;
359: void *p;
360: int attempt;
361: Bucket *bp;
362:
363: for(attempt = 0; attempt < 1000; attempt++) {
364: p = malloc(size);
365: if(p != nil) {
366: bp = (Bucket*)((ulong)p - bdatoff);
367: bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
368: return p;
369: }
370: s = u->p->psstate;
371: u->p->psstate = "Malloc";
372: qlock(&arena.rq);
373: while(waserror())
374: ;
375: sleep(&arena.r, return0, nil);
376: poperror();
377: qunlock(&arena.rq);
378: u->p->psstate = s;
379: }
380: print("%s:%d: out of memory in smalloc %d\n", u->p->text, u->p->pid, size);
381: u->p->state = Broken;
382: u->p->psstate = "NoMem";
383: for(;;)
384: sched();
385: return 0;
386: }
387:
388: int
389: msize(void *ptr)
390: {
391: Bucket *bp;
392:
393: bp = (Bucket*)((ulong)ptr - bdatoff);
394: if(bp->magic != Magic2n)
395: panic("msize");
396: return 1<<bp->size;
397: }
398:
399: void
400: free(void *ptr)
401: {
402: ulong pc, n;
403: Bucket *bp, **l;
404:
405: bp = (Bucket*)((ulong)ptr - bdatoff);
406: l = &arena.btab[bp->size];
407:
408: lock(&arena);
409: if(bp->magic != Magic2n)
410: panic("free");
411: bp->magic = 0;
412: bp->next = *l;
413: *l = bp;
414: if(bp->size == 13) {
415: pc = bp->pc;
416: for(n = 0; n < NTRACE; n++){
417: if(arena.trace[n].pc == pc){
418: arena.trace[n].free++;
419: break;
420: }
421: }
422: }
423: unlock(&arena);
424: if(arena.r.p)
425: wakeup(&arena.r);
426: }
427:
428: void
429: xsummary(void)
430: {
431: Hole *h;
432: Bucket *k;
433: int i, nfree, nused;
434:
435: i = 0;
436: for(h = xlists.flist; h; h = h->link)
437: i++;
438:
439: print("%d holes free\n", i);
440: i = 0;
441: for(h = xlists.table; h; h = h->link) {
442: print("%.8lux %.8lux %d\n", h->addr, h->top, h->size);
443: i += h->size;
444: }
445: print("%d bytes free\n", i);
446: nused = 0;
447: for(i = 3; i < Maxpow; i++) {
448: if(arena.btab[i] == 0 && arena.nbuck[i] == 0)
449: continue;
450: nused += arena.nbuck[i]*(1<<i);
451: nfree = 0;
452: for(k = arena.btab[i]; k; k = k->next)
453: nfree++;
454: print("%8d %4d %4d\n", 1<<i, arena.nbuck[i], nfree);
455: }
456: for(i = 0; i < NTRACE && arena.trace[i].pc; i++)
457: print("%lux %d %d\n", arena.trace[i].pc, arena.trace[i].alloc, arena.trace[i].free);
458: print("%d bytes in pool\n", nused);
459: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.