![[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.3 ! root 3: * Copyright 1992,1993,1994 Atari Corporation.
1.1.1.2 root 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:
1.1.1.3 ! root 235: } else {
1.1 root 236:
237: /* not big enough to cut: unlink this from free list */
238:
239: NALLOC_DEBUG('w');
240:
241: *q = mb->b_next;
242:
243: }
244:
1.1.1.3 ! root 245: mb->b_next = (struct block *)NKMAGIC;
! 246:
1.1 root 247: return (void *)(mb+1);
248:
249: }
250:
251: }
252:
253: }
254:
255:
256:
257: /* no block available: get a new arena */
258:
259:
260:
261: #if 1
262:
263: return NULL; /* MiNT: fail. */
264:
265: #else
266:
267: if (!minarena) {
268:
269: minarena = Malloc(-1L) / 20;
270:
271: if (minarena > MAXARENA) minarena = MAXARENA;
272:
273: }
274:
275:
276:
277: if (size < minarena) {
278:
279: NALLOC_DEBUG('m');
280:
281: temp = minarena;
282:
283: }
284:
285: else {
286:
287: NALLOC_DEBUG('s');
288:
289: temp = size;
290:
291: }
292:
293:
294:
295: a = (struct arena *)Malloc(temp +
296:
297: sizeof(struct arena) +
298:
299: sizeof(struct block));
300:
301:
302:
303: /* if Malloc failed return failure */
304:
305: if (a == 0) {
306:
307: NALLOC_DEBUG('x');
308:
309: return 0;
310:
311: }
312:
313:
314:
315: a->a_size = temp + sizeof(struct block);
316:
317: a->a_next = a_first;
318:
319: a_first = a;
320:
321: mb = (struct block *)(a+1);
322:
323: mb->b_next = NULL;
324:
325: mb->b_size = size;
326:
327:
328:
329: if (temp > (size + sizeof(struct block))) {
330:
331: NALLOC_DEBUG('c');
332:
333: b = a->a_ffirst = ((char *)(mb+1)) + size;
334:
335: b->b_next = NULL;
336:
337: b->b_size = temp - size - sizeof(struct block);
338:
339: }
340:
341: else {
342:
343: a->a_ffirst = NULL;
344:
345: }
346:
347: return (void *)(++mb);
348:
349: #endif
350:
351: }
352:
353:
354:
355: void
356:
357: nfree(start)
358:
359: void *start;
360:
361: {
362:
363: struct arena *a, **qa;
364:
365: struct block *b;
366:
367: struct block *pb;
368:
369: struct block *fb = (struct block *)start;
370:
371:
372:
373: NALLOC_DEBUG('F');
374:
375:
376:
1.1.1.3 ! root 377: /* set fb (and b) to header start */
1.1 root 378:
1.1.1.3 ! root 379: b = --fb;
1.1 root 380:
381:
382:
1.1.1.3 ! root 383: if (fb->b_next != (struct block *)NKMAGIC) {
! 384:
! 385: FATAL("nfree: block %lx not allocated by nalloc!",fb);
! 386:
! 387: }
1.1 root 388:
389:
390:
391: /* the arena this block lives in */
392:
393: for (a = *(qa = &a_first); a; a = *(qa = &a->a_next)) {
394:
1.1.1.3 ! root 395: if ((unsigned long)b >= (unsigned long)(a+1) &&
1.1 root 396:
1.1.1.3 ! root 397: (unsigned long)b < (((unsigned long)(a+1)) + a->a_size)) goto found;
1.1 root 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.