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