Return to alloc.c CVS log

Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386

Annotation of coherent/b/STREAMS/coh.386/alloc.c, revision 1.1

1.1     ! root        1: /* $Header: /src386/STREAMS/coh.386/RCS/alloc.c,v 2.3 93/08/09 13:35:06 bin Exp Locker: bin $ */
        !             2: /* (lgl-
        !             3:  *     The information contained herein is a trade secret of Mark Williams
        !             4:  *     Company, and  is confidential information.  It is provided  under a
        !             5:  *     license agreement,  and may be  copied or disclosed  only under the
        !             6:  *     terms of  that agreement.  Any  reproduction or disclosure  of this
        !             7:  *     material without the express written authorization of Mark Williams
        !             8:  *     Company or persuant to the license agreement is unlawful.
        !             9:  *
        !            10:  *     COHERENT Version 2.3.37
        !            11:  *     Copyright (c) 1982, 1983, 1984.
        !            12:  *     An unpublished work by Mark Williams Company, Chicago.
        !            13:  *     All rights reserved.
        !            14:  -lgl) */
        !            15: /*
        !            16:  * Coherent.
        !            17:  * Storage allocator.
        !            18:  *
        !            19:  * $Log:       alloc.c,v $
        !            20:  * Revision 2.3  93/08/09  13:35:06  bin
        !            21:  * Kernel 82 changes
        !            22:  * 
        !            23:  * Revision 2.2  93/07/26  14:28:19  nigel
        !            24:  * Nigel's R80
        !            25:  * 
        !            26:  * Revision 1.4  93/04/14  10:06:13  root
        !            27:  * r75
        !            28:  * 
        !            29:  * Revision 1.2  92/01/06  11:58:31  hal
        !            30:  * Compile with cc.mwc.
        !            31:  * 
        !            32:  * Revision 1.1        88/03/24  16:13:25      src
        !            33:  * Initial revision
        !            34:  * 
        !            35:  */
        !            36: 
        !            37: #include <common/ccompat.h>
        !            38: #include <common/__parith.h>
        !            39: #include <common/_tricks.h>
        !            40: #include <kernel/param.h>
        !            41: #include <sys/debug.h>
        !            42: 
        !            43: #include <sys/coherent.h>
        !            44: #include <sys/errno.h>
        !            45: #include <sys/proc.h>
        !            46: 
        !            47: #include <kernel/alloc.h>
        !            48: 
        !            49: /*
        !            50:  * Alloc definitions. These used to be in <sys/machine.h> for some unknown
        !            51:  * and unknowable reason. They belong here, so now here they are. Since the
        !            52:  * person(s) who wrote this stuff neglected to mention what the alignment
        !            53:  * issues are, we'll stay with what they did.
        !            54:  *
        !            55:  * This stuff is aligned on double-byte boundaries and the pointer to the
        !            56:  * next block in a circular list is tagged with the status of the current
        !            57:  * block. Blocks are not coalesced when freed, that is done by the allocator
        !            58:  * when trying to locate a sufficiently large free block.
        !            59:  *
        !            60:  * As an extra twist, you might have wondered why alloc () tries to loop
        !            61:  * twice over the whole arena. It does that because it looks for an exact fit
        !            62:  * (after coalescing). The allocator has no memory because there is no actual
        !            63:  * overall arena structure, so every call to alloc () will try to coalesce the
        !            64:  * entire arena unless there is an exact-sized hole.
        !            65:  */
        !            66: 
        !            67: enum {
        !            68:        BLOCK_FREE      = 0,
        !            69:        BLOCK_USED
        !            70: };
        !            71: 
        !            72: #define        ALIGN_MASK      1
        !            73: #define        align(p)        ((ALL *) ((__ptr_arith_t) (p) & ~ ALIGN_MASK))
        !            74: #define        link(p)         align ((p)->a_link)
        !            75: #define        tstfree(p)      (((p)->a_link & BLOCK_USED) == BLOCK_FREE)
        !            76: 
        !            77: #define        MAKE_LINK(a,f)  ((__ptr_arith_t) a + (f))
        !            78: #define        MAKE_FREE(a)    ((a)->a_link &= ~ BLOCK_USED)
        !            79: #define        MAKE_USED(a)    ((a)->a_link |= BLOCK_USED)
        !            80: 
        !            81: 
        !            82: typedef union all_u {
        !            83:        __ptr_arith_t   a_link;
        !            84: } ALL;
        !            85: 
        !            86: 
        !            87: #define        NEXT_FIT        1
        !            88: 
        !            89: #if    NEXT_FIT
        !            90: 
        !            91: struct _heap {
        !            92:        ALL           * _next_block;
        !            93: };
        !            94: 
        !            95: #define        HEAP_CONTROL_SIZE       sizeof (heap_t)
        !            96: #define        START_BLOCK(heap)       ((heap)->_next_block)
        !            97: #define        SET_START_BLOCK(heap,newstart) \
        !            98:                                ((heap)->_next_block = (newstart))
        !            99: #else
        !           100: 
        !           101: #define        HEAP_CONTROL_SIZE       0
        !           102: #define        START_BLOCK(heap)       ((ALL *) (heap))
        !           103: #define        SET_START_BLOCK(heap,newstart)  ((void) 0)
        !           104: 
        !           105: #endif
        !           106: 
        !           107: #ifndef TEST   /* Do not test setarena() or alloc() or free().  */
        !           108: 
        !           109: /*
        !           110:  * Create an arena.
        !           111:  */
        !           112: 
        !           113: heap_t *
        !           114: setarena(cp, n)
        !           115: register char *cp;
        !           116: {
        !           117:        ALL           * first_block;
        !           118:        ALL           * last_block;
        !           119:        heap_t        * heap_control;
        !           120: 
        !           121:        /*
        !           122:         * Begin by aligning the memory passed in and rounding down the size.
        !           123:         */
        !           124: 
        !           125:        {
        !           126:                int             align = (__ptr_arith_t) cp & ALIGN_MASK;
        !           127: 
        !           128:                if (align) {
        !           129:                        align = ALIGN_MASK + 1 - align;
        !           130:                        cp += align;
        !           131:                        n -= align;
        !           132:                }
        !           133: 
        !           134:                n &= ~ sizeof (ALL *);
        !           135:        }
        !           136: 
        !           137:        /*
        !           138:         * Make room for a heap control area.
        !           139:         */
        !           140: 
        !           141:        heap_control = (heap_t *) cp;
        !           142: 
        !           143:        cp += HEAP_CONTROL_SIZE;
        !           144:        n -= HEAP_CONTROL_SIZE;
        !           145: 
        !           146:        first_block = (ALL *) cp;
        !           147:        if ((last_block = (ALL *) (cp + n) - 1) < first_block)
        !           148:                panic("Arena %x too small", (int) cp);
        !           149: 
        !           150:        /*
        !           151:         * The initial memory arena consists of a circular list of blocks,
        !           152:         * one large free block and one tiny used block at the end. In the
        !           153:         * original "design", there was no heap control block.
        !           154:         */
        !           155: 
        !           156:        first_block->a_link = MAKE_LINK (last_block, BLOCK_FREE);
        !           157:        last_block->a_link = MAKE_LINK (first_block, BLOCK_USED);
        !           158: 
        !           159:        SET_START_BLOCK (heap_control, first_block);
        !           160:        return heap_control;
        !           161: }
        !           162: 
        !           163: 
        !           164: #if    0
        !           165: /*
        !           166:  * NIGEL: This code intrigues me... let's keep statistics.
        !           167:  */
        !           168: 
        !           169: typedef        unsigned long   stat_t;
        !           170: 
        !           171: static stat_t          _allocations;
        !           172: static stat_t          _block_tests;
        !           173: static stat_t          _block_fits;
        !           174: static stat_t          _exact_fits;
        !           175: 
        !           176: #define        ADD_STAT(stat)  ((stat += 1) == 0 ? stat -- : 0)
        !           177: 
        !           178: void dumpstats () {
        !           179:        printf ("allocations = %d\ntotal tests = %d\n"
        !           180:                "total matches =  %d\nexact fits = %d\n",
        !           181:                _allocations, _block_tests, _block_fits, _exact_fits);
        !           182: }
        !           183: #else
        !           184: # define       ADD_STAT(stat)  ((void) 0)
        !           185: #endif
        !           186: 
        !           187: /*
        !           188:  * Allocate `l' bytes of memory.
        !           189:  */
        !           190: 
        !           191: __VOID__ *
        !           192: alloc (heap_control, size)
        !           193: heap_t       * heap_control;
        !           194: size_t         size;
        !           195: {
        !           196:        register ALL *scan_block;
        !           197:        register ALL *next_block;
        !           198:        register unsigned i;
        !           199:        register unsigned n;
        !           200:        register unsigned s;
        !           201: 
        !           202:        ADD_STAT (_allocations);
        !           203: 
        !           204:        n = 1 + __DIVIDE_ROUNDUP (size, sizeof (ALL));
        !           205: 
        !           206: #if    EXACT_FIT
        !           207:        for (i = 0 ; i < 2 ; i ++) {
        !           208: #endif
        !           209:                for (scan_block = START_BLOCK (heap_control) ;
        !           210:                     link (scan_block) != START_BLOCK (heap_control) ;
        !           211:                     scan_block = link (scan_block)) {
        !           212:                        ASSERT (vtop (scan_block) != NULL);
        !           213:                        ADD_STAT (_block_tests);
        !           214: 
        !           215:                        if (! tstfree (scan_block))
        !           216:                                continue;
        !           217: 
        !           218:                       for (next_block = link (scan_block) ;
        !           219:                            tstfree (next_block) ;
        !           220:                            next_block = link (next_block))
        !           221:                                if (next_block == START_BLOCK (heap_control))
        !           222:                                        break;
        !           223: 
        !           224:                        scan_block->a_link = MAKE_LINK (next_block,
        !           225:                                                        BLOCK_FREE);
        !           226:                        if ((s = next_block - scan_block) < n)
        !           227:                                continue;
        !           228: 
        !           229:                        ADD_STAT (_block_fits);
        !           230: 
        !           231:                        if (s > n) {
        !           232: #if    EXACT_FIT
        !           233:        /*
        !           234:         * This innocent-looking line of code is what makes this system prefer
        !           235:         * exact fits (which only happen about 10% of the time from the
        !           236:         * statistics which I have collected).
        !           237:         */
        !           238:                                if (i == 0)
        !           239:                                        continue;
        !           240: #endif
        !           241:                                (scan_block + n)->a_link =
        !           242:                                        MAKE_LINK (next_block, BLOCK_FREE);
        !           243:                                next_block = scan_block + n;
        !           244:                                scan_block->a_link = MAKE_LINK (next_block,
        !           245:                                                                BLOCK_FREE);
        !           246:                        }
        !           247:                        MAKE_USED (scan_block);
        !           248:                        SET_START_BLOCK (heap_control, next_block);
        !           249: #if    0
        !           250:                        memset (scan_block + 1, 0, size);
        !           251: #endif
        !           252: #if    EXACT_FIT
        !           253:                        if (i == 0)
        !           254:                                ADD_STAT (_exact_fits);
        !           255: #endif
        !           256:                        return (__VOID__ *) (scan_block + 1);
        !           257:                }
        !           258: #if    EXACT_FIT
        !           259:        }
        !           260: #endif
        !           261:        u.u_error = ENOSPC;
        !           262:        return NULL;
        !           263: }
        !           264: 
        !           265: /*
        !           266:  * Free memory.
        !           267:  */
        !           268: free(cp)
        !           269: char *cp;
        !           270: {
        !           271:        register ALL *ap;
        !           272:        extern char __end;
        !           273: 
        !           274: #if 0
        !           275:        ap = ((ALL *)cp) - 1;
        !           276:        if (ap<(ALL *)&__end || tstfree(ap))
        !           277:                panic("Bad free %x\n", (unsigned)cp);
        !           278: #else
        !           279:        ap = ((ALL *)cp) - 1;
        !           280:        if (ap<(ALL *)&__end) {
        !           281:                int *r = (int *)(&cp);  /* return address */
        !           282:                printf("cp=%x ap=%x &__end=%x\n", cp, ap, &__end);
        !           283:                panic("Bad free() from eip=%x\n", *(r-1));
        !           284:        }
        !           285:        if (tstfree(ap)) {
        !           286:                int *r = (int *)(&cp);  /* return address */
        !           287:                printf("cp=%x tstfree(%x)=%x\n", cp, ap, tstfree(ap));
        !           288:                panic("Bad free() from eip=%x\n", *(r-1));
        !           289:        }
        !           290: #endif
        !           291:        MAKE_FREE (ap);
        !           292: }
        !           293: 
        !           294: #endif /* TEST */
        !           295: 
        !           296: #ifdef _I386
        !           297: /*
        !           298:  * unsigned char *palloc(int size);
        !           299:  *
        !           300:  * Allocate 'size' bytes of kernel space, which does not cross a click
        !           301:  * boundary.  Returns a pointer to the space allocated on success,
        !           302:  * NULL on failure.
        !           303:  *
        !           304:  * Allocate twice as much memory as we need, and then return a chunk that
        !           305:  * does not cross a click boundary.  Immediately before the chunk that
        !           306:  * we return, we store the true address of the chunk that was kalloc()'d.
        !           307:  *
        !           308:  * Since this routine is for relatively small short-lived objects,
        !           309:  * which we expect to allocate frequently, speed is more important than
        !           310:  * space overhead.
        !           311:  *
        !           312:  * We assume that kalloc() returns word aligned addresses.
        !           313:  *
        !           314:  * There are two cases:
        !           315:  * There is enough room before the click boundary (or there is no click
        !           316:  *     boundary) for the pointer and the memory we need.
        !           317:  * Otherwise, return the chunk starting at the click boundary, storing
        !           318:  *     the pointer right before the click boundary.  This trick allows
        !           319:  *     us to allocate up to 1 full click.
        !           320:  *
        !           321:  * If kalloc() did NOT return word aligned chunks, then there would be
        !           322:  * a third case, where there might not be enough space for the pointer
        !           323:  * before the click boundary.
        !           324:  */
        !           325: 
        !           326: #define c_boundry(x)   ctob(btoc((x)+1)) /* Next click boundary above x.  */
        !           327: #define VOID   unsigned char
        !           328: 
        !           329: #ifdef TEST
        !           330: #undef kalloc
        !           331: #undef kfree
        !           332: VOID *kalloc();
        !           333: void kfree();
        !           334: #endif /* TEST */
        !           335: 
        !           336: VOID *
        !           337: palloc(size)
        !           338:        int size;       /* Size in bytes of area to allocate.  */
        !           339: {
        !           340:        VOID *local_arena;      /* Value returned by kalloc().  */
        !           341:        VOID *boundry;          /* Next click boundry above local_arena.  */
        !           342:        VOID *retval;           /* What we give back to our caller.  */
        !           343: 
        !           344:        if (size > NBPC)
        !           345:                panic("palloc(%x): can not palloc more than 1 click.", size);
        !           346: 
        !           347:        /* Fetch twice as much space as requested, plus a pointer.  */
        !           348:        if ((local_arena = (VOID *) kalloc (sizeof (VOID *) + (2 * size)))
        !           349:            == NULL)
        !           350:                return NULL;
        !           351:        
        !           352:        boundry = (VOID *) c_boundry (local_arena);
        !           353: 
        !           354:        T_PIGGY(0x2000, printf("b: %x ", boundry));
        !           355: 
        !           356:        /* First case:  enough space before the boundry.  */
        !           357:        if ( (boundry - local_arena) >= (size + sizeof(VOID *)) ) {
        !           358: 
        !           359:                T_PIGGY(0x2000, printf("c1 "));
        !           360: 
        !           361:                * (VOID **)local_arena = local_arena;
        !           362:                retval = local_arena + sizeof(VOID *);
        !           363:        } else if ((boundry - local_arena) < sizeof(VOID *)) {
        !           364:                /*
        !           365:                 * Second case: There is not enough space before the
        !           366:                 * boundry for the whole pointer.
        !           367:                 */
        !           368:                T_PIGGY(0x2000, printf("c2 "));
        !           369: 
        !           370:                * (VOID **)local_arena = local_arena;
        !           371:                retval = local_arena + sizeof(VOID *);
        !           372:        } else {
        !           373: 
        !           374:                T_PIGGY(0x2000, printf("c3: %x ", (boundry - local_arena)));
        !           375: 
        !           376:                * (VOID **)(boundry - sizeof(VOID *)) = local_arena;
        !           377:                retval = boundry;
        !           378:        }
        !           379: 
        !           380:        T_PIGGY( 0x2000,
        !           381:                printf("palloc(%x) = %x:%x (was %x:%x), ",
        !           382:                        size, retval, (retval+size)-1,
        !           383:                        local_arena, (local_arena+(2*size)+sizeof(VOID *))-1)
        !           384:        );
        !           385: 
        !           386: #if    0
        !           387:        /*
        !           388:         * NIGEL: Things in trace macros must now be expressions. These ones
        !           389:         * weren't worth cleaning up.
        !           390:         */
        !           391:        T_PIGGY( 0x2000,
        !           392:                if ((retval+size)-1 > (local_arena+(2*size)+sizeof(VOID *))-1) {
        !           393:                        printf("\npalloc() overrun\n");
        !           394:                }
        !           395:                if (retval < local_arena) {
        !           396:                        printf("\npalloc() underrun\n");
        !           397:                }
        !           398:        );
        !           399: #endif
        !           400: 
        !           401:        return (VOID *) retval;
        !           402: } /* palloc() */
        !           403: 
        !           404: /*
        !           405:  * void pfree(VOID *ptr);
        !           406:  * Free the chunk of memory 'ptr' allocated by palloc().
        !           407:  *
        !           408:  * Note that 'ptr' is really a VOID *, but we call it VOID **
        !           409:  * to simplify arithmetic.
        !           410:  *
        !           411:  * The address returned by kalloc() is stored immediately
        !           412:  * before the chunk returned by palloc().
        !           413:  */
        !           414: void
        !           415: pfree(ptr)
        !           416:        VOID *ptr[];
        !           417: {
        !           418:        T_PIGGY(0x2000, printf("pfree(%x):kfree(%x), ", ptr, *(ptr-1)));
        !           419:        kfree(*(ptr-1));
        !           420: } /* pfree() */
        !           421: 
        !           422: 
        !           423: #ifdef TEST
        !           424: 
        !           425: #include <sys/compat.h>
        !           426: #include <stdio.h>
        !           427: #include <stdarg.h>
        !           428: 
        !           429: #define FOURK  4096    /* How many bytes in 4K?  */
        !           430: #define NUM_TESTS 40   /* How many tests do we run?  */
        !           431: #define SMALL_NUMBER 6 /* A small number whose exact value we don't care about.  */
        !           432: #define HUGE   (100*FOURK)     /* Allocate from this pool.  */
        !           433: #define IGNORE(v)      (v==v)  /* Lint food.  */
        !           434: 
        !           435: unsigned t_piggy = 0x2000;     /* Turn on TRACER bits.  */
        !           436: 
        !           437: main()
        !           438: {
        !           439:        int i;
        !           440:        VOID *chunk;
        !           441: 
        !           442:        for (i = 0; i < NUM_TESTS; ++i) {
        !           443:                if (NULL == (chunk = palloc(SMALL_NUMBER))) {
        !           444:                        printf("No more fake memory to eat.\n");
        !           445:                        printf("This is probably a bug.\n");
        !           446:                        exit(1);
        !           447:                }
        !           448: 
        !           449:                printf("chunk: %x\n", chunk);
        !           450:        }
        !           451: } /* main() for TEST */
        !           452: 
        !           453: /*
        !           454:  * Print a message and die.
        !           455:  */
        !           456: 
        !           457: panic(format)
        !           458: char * format;
        !           459: {
        !           460:        va_list args;
        !           461:        va_start (args, format);
        !           462:        vprintf (format, args);
        !           463:        va_end (args);
        !           464:        exit(1);
        !           465: }
        !           466: 
        !           467: /*
        !           468:  * Fake kalloc() for use by palloc().
        !           469:  * Allocate a chunk of some non-existant memory space.
        !           470:  */
        !           471: VOID *
        !           472: kalloc(size)
        !           473:        int size;
        !           474: {
        !           475:        static VOID *base = NULL;
        !           476:        static VOID *top_free = NULL;
        !           477:        VOID *retval;
        !           478: 
        !           479: 
        !           480:        /*
        !           481:         * First time through, allocate a nice big chunk of memory
        !           482:         * to carve up.
        !           483:         */
        !           484:        if (NULL == base) {
        !           485:                if (NULL == (base = malloc(HUGE))) {
        !           486:                        printf("Can not malloc %d bytes.\n", HUGE);
        !           487:                        exit(1);
        !           488:                }
        !           489:                /* Make sure we start close to a click boundry.  */
        !           490:                top_free = c_boundry(base) + SMALL_NUMBER;
        !           491:        }
        !           492: 
        !           493:        retval = top_free;
        !           494:        /*
        !           495:         * We want to encourage test addresses to migrate accross
        !           496:         * click boundries.
        !           497:         */
        !           498:        if (size < (FOURK - 1)) {
        !           499:                top_free += (FOURK - 1);
        !           500:        } else {
        !           501:                top_free += size;
        !           502:        }
        !           503: 
        !           504:        return(retval);
        !           505: } /* kalloc() */
        !           506: 
        !           507: /*
        !           508:  * Fake kfree for pfree() to use.
        !           509:  */
        !           510: void
        !           511: kfree(addr)
        !           512:        VOID *addr;
        !           513: {
        !           514:        IGNORE(addr);
        !           515:        /* Do nothing!  */
        !           516: } /* kfree() */
        !           517: 
        !           518: #endif /* TEST */
        !           519: 
        !           520: #endif /* _I386 */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.