Return to malloc.c CVS log

Up to [Early Linux] / linux / kernel

Annotation of linux/kernel/malloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * malloc.c --- a general purpose kernel memory allocator for Linux.
        !             3:  * 
        !             4:  * Written by Theodore Ts'o ([email protected]), 11/29/91
        !             5:  *
        !             6:  * This routine is written to be as fast as possible, so that it
        !             7:  * can be called from the interrupt level.
        !             8:  *
        !             9:  * Limitations: maximum size of memory we can allocate using this routine
        !            10:  *     is 4k, the size of a page in Linux.
        !            11:  *
        !            12:  * The general game plan is that each page (called a bucket) will only hold
        !            13:  * objects of a given size.  When all of the object on a page are released,
        !            14:  * the page can be returned to the general free pool.  When malloc() is
        !            15:  * called, it looks for the smallest bucket size which will fulfill its
        !            16:  * request, and allocate a piece of memory from that bucket pool.
        !            17:  *
        !            18:  * Each bucket has as its control block a bucket descriptor which keeps 
        !            19:  * track of how many objects are in use on that page, and the free list
        !            20:  * for that page.  Like the buckets themselves, bucket descriptors are
        !            21:  * stored on pages requested from get_free_page().  However, unlike buckets,
        !            22:  * pages devoted to bucket descriptor pages are never released back to the
        !            23:  * system.  Fortunately, a system should probably only need 1 or 2 bucket
        !            24:  * descriptor pages, since a page can hold 256 bucket descriptors (which
        !            25:  * corresponds to 1 megabyte worth of bucket pages.)  If the kernel is using 
        !            26:  * that much allocated memory, it's probably doing something wrong.  :-)
        !            27:  *
        !            28:  * Note: malloc() and free() both call get_free_page() and free_page()
        !            29:  *     in sections of code where interrupts are turned off, to allow
        !            30:  *     malloc() and free() to be safely called from an interrupt routine.
        !            31:  *     (We will probably need this functionality when networking code,
        !            32:  *     particularily things like NFS, is added to Linux.)  However, this
        !            33:  *     presumes that get_free_page() and free_page() are interrupt-level
        !            34:  *     safe, which they may not be once paging is added.  If this is the
        !            35:  *     case, we will need to modify malloc() to keep a few unused pages
        !            36:  *     "pre-allocated" so that it can safely draw upon those pages if
        !            37:  *     it is called from an interrupt routine.
        !            38:  *
        !            39:  *     Another concern is that get_free_page() should not sleep; if it 
        !            40:  *     does, the code is carefully ordered so as to avoid any race 
        !            41:  *     conditions.  The catch is that if malloc() is called re-entrantly, 
        !            42:  *     there is a chance that unecessary pages will be grabbed from the 
        !            43:  *     system.  Except for the pages for the bucket descriptor page, the 
        !            44:  *     extra pages will eventually get released back to the system, though,
        !            45:  *     so it isn't all that bad.
        !            46:  */
        !            47: 
        !            48: #include <linux/kernel.h>
        !            49: #include <linux/mm.h>
        !            50: #include <asm/system.h>
        !            51: 
        !            52: struct bucket_desc {   /* 16 bytes */
        !            53:        void                    *page;
        !            54:        struct bucket_desc      *next;
        !            55:        void                    *freeptr;
        !            56:        unsigned short          refcnt;
        !            57:        unsigned short          bucket_size;
        !            58: };
        !            59: 
        !            60: struct _bucket_dir {   /* 8 bytes */
        !            61:        int                     size;
        !            62:        struct bucket_desc      *chain;
        !            63: };
        !            64: 
        !            65: /*
        !            66:  * The following is the where we store a pointer to the first bucket
        !            67:  * descriptor for a given size.  
        !            68:  *
        !            69:  * If it turns out that the Linux kernel allocates a lot of objects of a
        !            70:  * specific size, then we may want to add that specific size to this list,
        !            71:  * since that will allow the memory to be allocated more efficiently.
        !            72:  * However, since an entire page must be dedicated to each specific size
        !            73:  * on this list, some amount of temperance must be exercised here.
        !            74:  *
        !            75:  * Note that this list *must* be kept in order.
        !            76:  */
        !            77: struct _bucket_dir bucket_dir[] = {
        !            78:        { 16,   (struct bucket_desc *) 0},
        !            79:        { 32,   (struct bucket_desc *) 0},
        !            80:        { 64,   (struct bucket_desc *) 0},
        !            81:        { 128,  (struct bucket_desc *) 0},
        !            82:        { 256,  (struct bucket_desc *) 0},
        !            83:        { 512,  (struct bucket_desc *) 0},
        !            84:        { 1024, (struct bucket_desc *) 0},
        !            85:        { 2048, (struct bucket_desc *) 0},
        !            86:        { 4096, (struct bucket_desc *) 0},
        !            87:        { 0,    (struct bucket_desc *) 0}};   /* End of list marker */
        !            88: 
        !            89: /*
        !            90:  * This contains a linked list of free bucket descriptor blocks
        !            91:  */
        !            92: struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
        !            93: 
        !            94: /*
        !            95:  * This routine initializes a bucket description page.
        !            96:  */
        !            97: static inline void init_bucket_desc()
        !            98: {
        !            99:        struct bucket_desc *bdesc, *first;
        !           100:        int     i;
        !           101:        
        !           102:        first = bdesc = (struct bucket_desc *) get_free_page();
        !           103:        if (!bdesc)
        !           104:                panic("Out of memory in init_bucket_desc()");
        !           105:        for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
        !           106:                bdesc->next = bdesc+1;
        !           107:                bdesc++;
        !           108:        }
        !           109:        /*
        !           110:         * This is done last, to avoid race conditions in case 
        !           111:         * get_free_page() sleeps and this routine gets called again....
        !           112:         */
        !           113:        bdesc->next = free_bucket_desc;
        !           114:        free_bucket_desc = first;
        !           115: }
        !           116: 
        !           117: void *malloc(unsigned int len)
        !           118: {
        !           119:        struct _bucket_dir      *bdir;
        !           120:        struct bucket_desc      *bdesc;
        !           121:        void                    *retval;
        !           122: 
        !           123:        /*
        !           124:         * First we search the bucket_dir to find the right bucket change
        !           125:         * for this request.
        !           126:         */
        !           127:        for (bdir = bucket_dir; bdir->size; bdir++)
        !           128:                if (bdir->size >= len)
        !           129:                        break;
        !           130:        if (!bdir->size) {
        !           131:                printk("malloc called with impossibly large argument (%d)\n",
        !           132:                        len);
        !           133:                panic("malloc: bad arg");
        !           134:        }
        !           135:        /*
        !           136:         * Now we search for a bucket descriptor which has free space
        !           137:         */
        !           138:        cli();  /* Avoid race conditions */
        !           139:        for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) 
        !           140:                if (bdesc->freeptr)
        !           141:                        break;
        !           142:        /*
        !           143:         * If we didn't find a bucket with free space, then we'll 
        !           144:         * allocate a new one.
        !           145:         */
        !           146:        if (!bdesc) {
        !           147:                char            *cp;
        !           148:                int             i;
        !           149: 
        !           150:                if (!free_bucket_desc)  
        !           151:                        init_bucket_desc();
        !           152:                bdesc = free_bucket_desc;
        !           153:                free_bucket_desc = bdesc->next;
        !           154:                bdesc->refcnt = 0;
        !           155:                bdesc->bucket_size = bdir->size;
        !           156:                bdesc->page = bdesc->freeptr = (void *) cp = get_free_page();
        !           157:                if (!cp)
        !           158:                        panic("Out of memory in kernel malloc()");
        !           159:                /* Set up the chain of free objects */
        !           160:                for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
        !           161:                        *((char **) cp) = cp + bdir->size;
        !           162:                        cp += bdir->size;
        !           163:                }
        !           164:                *((char **) cp) = 0;
        !           165:                bdesc->next = bdir->chain; /* OK, link it in! */
        !           166:                bdir->chain = bdesc;
        !           167:        }
        !           168:        retval = (void *) bdesc->freeptr;
        !           169:        bdesc->freeptr = *((void **) retval);
        !           170:        bdesc->refcnt++;
        !           171:        sti();  /* OK, we're safe again */
        !           172:        return(retval);
        !           173: }
        !           174: 
        !           175: /*
        !           176:  * Here is the free routine.  If you know the size of the object that you
        !           177:  * are freeing, then free_s() will use that information to speed up the
        !           178:  * search for the bucket descriptor.
        !           179:  * 
        !           180:  * We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
        !           181:  */
        !           182: void free_s(void *obj, int size)
        !           183: {
        !           184:        void            *page;
        !           185:        struct _bucket_dir      *bdir;
        !           186:        struct bucket_desc      *bdesc, *prev;
        !           187: 
        !           188:        /* Calculate what page this object lives in */
        !           189:        page = (void *)  ((unsigned long) obj & 0xfffff000);
        !           190:        /* Now search the buckets looking for that page */
        !           191:        for (bdir = bucket_dir; bdir->size; bdir++) {
        !           192:                prev = 0;
        !           193:                /* If size is zero then this conditional is always false */
        !           194:                if (bdir->size < size)
        !           195:                        continue;
        !           196:                for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
        !           197:                        if (bdesc->page == page) 
        !           198:                                goto found;
        !           199:                        prev = bdesc;
        !           200:                }
        !           201:        }
        !           202:        panic("Bad address passed to kernel free_s()");
        !           203: found:
        !           204:        cli(); /* To avoid race conditions */
        !           205:        *((void **)obj) = bdesc->freeptr;
        !           206:        bdesc->freeptr = obj;
        !           207:        bdesc->refcnt--;
        !           208:        if (bdesc->refcnt == 0) {
        !           209:                /*
        !           210:                 * We need to make sure that prev is still accurate.  It
        !           211:                 * may not be, if someone rudely interrupted us....
        !           212:                 */
        !           213:                if ((prev && (prev->next != bdesc)) ||
        !           214:                    (!prev && (bdir->chain != bdesc)))
        !           215:                        for (prev = bdir->chain; prev; prev = prev->next)
        !           216:                                if (prev->next == bdesc)
        !           217:                                        break;
        !           218:                if (prev)
        !           219:                        prev->next = bdesc->next;
        !           220:                else {
        !           221:                        if (bdir->chain != bdesc)
        !           222:                                panic("malloc bucket chains corrupted");
        !           223:                        bdir->chain = bdesc->next;
        !           224:                }
        !           225:                free_page((unsigned long) bdesc->page);
        !           226:                bdesc->next = free_bucket_desc;
        !           227:                free_bucket_desc = bdesc;
        !           228:        }
        !           229:        sti();
        !           230:        return;
        !           231: }
        !           232: 

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