lib/malloc.c

/* */
This source file includes following definitions.
init_bucket_desc
malloc
free_s
   1 /*
   2  * malloc.c --- a general purpose kernel memory allocator for Linux.
   3  * 
   4  * Written by Theodore Ts'o (tytso@mit.edu), 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(GFP_KERNEL);
 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(GFP_KERNEL);
 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
/* */
root/lib/malloc.c

DEFINITIONS
