![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to nalloc2.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Atari MiNT] / MiNT / src|
Return to nalloc2.c CVS log | Up to [Atari MiNT] / MiNT / src |
1.1 root 1: /*
2:
1.1.1.2 ! root 3: * Copyright 1992,1993 Atari Corporation.
! 4:
! 5: * All rights reserved.
1.1 root 6:
7: */
8:
9:
10:
11: /*
12:
13: * General-purpose memory allocator, on the MWC arena model, with
14:
15: * this added feature:
16:
17: *
18:
19: * All blocks are coalesced when they're freed. If this results in
20:
21: * an arena with only one block, and that free, it's returned to the
22:
23: * OS.
24:
25: *
26:
27: * The functions here have the same names and bindings as the MWC
28:
29: * memory manager, which is the same as the UNIX names and bindings.
30:
31: *
32:
33: * MiNT version: used for kmalloc to manage kernel memory in small hunks,
34:
35: * rather than using a page at a time.
36:
37: */
38:
39:
40:
41: #include "mint.h"
42:
43:
44:
45: #if 0
46:
47: #define NALLOC_DEBUG(c) TRACE(("nalloc: %c",c));
48:
49: #else
50:
51: #define NALLOC_DEBUG(c) /* nothing */
52:
53: #endif
54:
55:
56:
57: #define NKMAGIC 0x19870425L
58:
59:
60:
61: /*
62:
63: * block header: every memory block has one.
64:
65: * A block is either allocated or on the free
66:
67: * list of the arena. There is no allocated list: it's not necessary.
68:
69: * The next pointer is only valid for free blocks: for allocated blocks
70:
71: * maybe it should hold a verification value..?
72:
73: *
74:
75: * Zero-length blocks are possible and free; they hold space which might
76:
77: * get coalesced usefully later on.
78:
79: */
80:
81:
82:
83: struct block {
84:
85: struct block *b_next; /* NULL for last guy; next alloc or next free */
86:
87: long b_size;
88:
89: };
90:
91:
92:
93: /*
94:
95: * arena header: every arena has one. Each arena is always completely
96:
97: * filled with blocks; the first starts right after this header.
98:
99: */
100:
101:
102:
103: struct arena {
104:
105: struct arena *a_next;
106:
107: struct block *a_ffirst;
108:
109: long a_size;
110:
111: };
112:
113:
114:
115: /*
116:
117: * Arena linked-list pointer, and block size.
118:
119: */
120:
121:
122:
123: static struct arena *a_first = (struct arena *)NULL;
124:
125:
126:
127: void
128:
129: nalloc_arena_add(start,len)
130:
131: void *start;
132:
133: long len;
134:
135: {
136:
1.1.1.2 ! root 137: struct arena *a;
1.1 root 138:
139: struct block *b;
140:
141:
142:
1.1.1.2 ! root 143: for (a = a_first; a && a->a_next; a = a->a_next)
1.1 root 144:
1.1.1.2 ! root 145: continue;
! 146:
! 147: if (a)
! 148:
! 149: a->a_next = (struct arena *)start;
! 150:
! 151: else
! 152:
! 153: a_first = (struct arena *)start;
! 154:
! 155: a = start;
! 156:
! 157: a->a_next = NULL;
1.1 root 158:
159: a->a_ffirst = b = (struct block *)(a+1);
160:
1.1.1.2 ! root 161: a->a_size = len - sizeof(*a);
1.1 root 162:
163: b->b_next = NULL;
164:
165: b->b_size = (len - sizeof(*a) - sizeof(*b));
166:
167: }
168:
169:
170:
171:
172:
173: void *
174:
175: nalloc(size)
176:
177: long size;
178:
179: {
180:
181: struct arena *a;
182:
183: struct block *b, *mb, **q;
184:
185: long temp;
186:
187:
188:
189: NALLOC_DEBUG('A');
190:
191:
192:
193: /* force even-sized alloc's */
194:
195: size = (size+1) & ~1;
196:
197:
198:
199: for (a = a_first; a; a = a->a_next) {
200:
201: for (b = *(q = &a->a_ffirst); b; b = *(q = &b->b_next)) {
202:
203: /* if big enough, use it */
204:
1.1.1.2 ! root 205: if (b->b_size >= (size + sizeof(struct block))) {
1.1 root 206:
207:
208:
209: /* got one */
210:
211: mb = b;
212:
213:
214:
215: /* cut the free block into an allocated part & a free part */
216:
217: temp = mb->b_size - size - sizeof(struct block);
218:
219: if (temp >= 0) {
220:
221: /* large enough to cut */
222:
223: NALLOC_DEBUG('c');
224:
225: b = (struct block *)(((char *)(b+1)) + size);
226:
227: b->b_size = temp;
228:
229: b->b_next = mb->b_next;
230:
231: *q = b;
232:
233: mb->b_size = size;
234:
235: mb->b_next = (struct block *)NKMAGIC;
236:
237: }
238:
239: else {
240:
241: /* not big enough to cut: unlink this from free list */
242:
243: NALLOC_DEBUG('w');
244:
245: *q = mb->b_next;
246:
247: }
248:
249: return (void *)(mb+1);
250:
251: }
252:
253: }
254:
255: }
256:
257:
258:
259: /* no block available: get a new arena */
260:
261:
262:
263: #if 1
264:
265: return NULL; /* MiNT: fail. */
266:
267: #else
268:
269: if (!minarena) {
270:
271: minarena = Malloc(-1L) / 20;
272:
273: if (minarena > MAXARENA) minarena = MAXARENA;
274:
275: }
276:
277:
278:
279: if (size < minarena) {
280:
281: NALLOC_DEBUG('m');
282:
283: temp = minarena;
284:
285: }
286:
287: else {
288:
289: NALLOC_DEBUG('s');
290:
291: temp = size;
292:
293: }
294:
295:
296:
297: a = (struct arena *)Malloc(temp +
298:
299: sizeof(struct arena) +
300:
301: sizeof(struct block));
302:
303:
304:
305: /* if Malloc failed return failure */
306:
307: if (a == 0) {
308:
309: NALLOC_DEBUG('x');
310:
311: return 0;
312:
313: }
314:
315:
316:
317: a->a_size = temp + sizeof(struct block);
318:
319: a->a_next = a_first;
320:
321: a_first = a;
322:
323: mb = (struct block *)(a+1);
324:
325: mb->b_next = NULL;
326:
327: mb->b_size = size;
328:
329:
330:
331: if (temp > (size + sizeof(struct block))) {
332:
333: NALLOC_DEBUG('c');
334:
335: b = a->a_ffirst = ((char *)(mb+1)) + size;
336:
337: b->b_next = NULL;
338:
339: b->b_size = temp - size - sizeof(struct block);
340:
341: }
342:
343: else {
344:
345: a->a_ffirst = NULL;
346:
347: }
348:
349: return (void *)(++mb);
350:
351: #endif
352:
353: }
354:
355:
356:
357: void
358:
359: nfree(start)
360:
361: void *start;
362:
363: {
364:
365: struct arena *a, **qa;
366:
367: struct block *b;
368:
369: struct block *pb;
370:
371: struct block *fb = (struct block *)start;
372:
373:
374:
375: NALLOC_DEBUG('F');
376:
377: if (fb->b_next != (struct block *)NKMAGIC) {
378:
379: FATAL("nfree: block %lx not allocated by nalloc!",fb);
380:
381: }
382:
383:
384:
385: /* set fb (and b) to header start */
386:
387: b = --fb;
388:
389:
390:
391: /* the arena this block lives in */
392:
393: for (a = *(qa = &a_first); a; a = *(qa = &a->a_next)) {
394:
395: if ((unsigned long)b > (unsigned long)a &&
396:
397: (unsigned long)b < (((unsigned long)a) + a->a_size)) goto found;
398:
399: }
400:
401: FATAL("nfree: block %lx not in any arena!",fb);
402:
403:
404:
405: found:
406:
407: /* Found it! */
408:
409: /* a is this block's arena */
410:
411:
412:
413: /* set pb to the previous free block in this arena, b to next */
414:
415: for (pb = NULL, b = a->a_ffirst;
416:
417: b && (b < fb);
418:
419: pb = b, b = b->b_next) ;
420:
421:
422:
423: fb->b_next = b;
424:
425:
426:
427: /* Coalesce backwards: if any prev ... */
428:
429: if (pb) {
430:
431: /* if it's adjacent ... */
432:
433: if ((((unsigned long)(pb+1)) + pb->b_size) == (unsigned long)fb) {
434:
435: NALLOC_DEBUG('b');
436:
437: pb->b_size += sizeof(struct block) + fb->b_size;
438:
439: fb = pb;
440:
441: }
442:
443: else {
444:
445: /* ... else not adjacent, but there is a prev free block */
446:
447: /* so set its next ptr to fb */
448:
449: pb->b_next = fb;
450:
451: }
452:
453: }
454:
455: else {
456:
457: /* ... else no prev free block: set arena's free list ptr to fb */
458:
459: a->a_ffirst = fb;
460:
461: }
462:
463:
464:
465: /* Coalesce forwards: b holds start of free block AFTER fb, if any */
466:
467: if (b && (((unsigned long)(fb+1)) + fb->b_size) == (unsigned long)b) {
468:
469: NALLOC_DEBUG('f');
470:
471: fb->b_size += sizeof(struct block) + b->b_size;
472:
473: fb->b_next = b->b_next;
474:
475: }
476:
477:
478:
479: /* if, after coalescing, this arena is entirely free, Mfree it! */
480:
1.1.1.2 ! root 481: if ((struct arena *)a->a_ffirst == a+1 &&
! 482:
! 483: (a->a_ffirst->b_size + sizeof(struct block))== a->a_size &&
1.1 root 484:
1.1.1.2 ! root 485: a != a_first) {
1.1 root 486:
487: NALLOC_DEBUG('!');
488:
489: *qa = a->a_next;
490:
1.1.1.2 ! root 491: #if 1
1.1 root 492:
1.1.1.2 ! root 493: kfree(a); /* MiNT -- give back so it can be used by users */
! 494:
! 495: #else
! 496:
! 497: (void)Mfree(a);
1.1 root 498:
499: #endif
500:
1.1.1.2 ! root 501: }
! 502:
1.1 root 503:
504:
505: return;
506:
507: }
508:
509:
510:
511: void
512:
513: NALLOC_DUMP()
514:
515: {
516:
517: struct arena *a;
518:
519: struct block *b;
520:
521:
522:
523: for (a = a_first; a; a = a->a_next) {
524:
525: FORCE("Arena at %lx size %lx: free list:",a,a->a_size);
526:
527: for (b = a->a_ffirst; b; b = b->b_next) {
528:
529: FORCE(" %8lx size %8lx",b,b->b_size);
530:
531: }
532:
533: }
534:
535: }
536:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.