Return to nalloc2.c CVS log

Up to [Atari MiNT] / MiNT / src

Annotation of MiNT/src/nalloc2.c, revision 1.1

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.