root/mm/kmalloc.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. kmalloc_init
  2. get_order
  3. kmalloc
  4. kfree_s

   1 /*
   2  *  linux/mm/kmalloc.c
   3  *
   4  *  Copyright (C) 1991, 1992  Linus Torvalds & Roger Wolff.
   5  *
   6  *  Written by R.E. Wolff Sept/Oct '93.
   7  *
   8  */
   9 
  10 /*
  11  * Modified by Alex Bligh (alex@cconcepts.co.uk) 4 Apr 1994 to use multiple
  12  * pages. So for 'page' throughout, read 'area'.
  13  */
  14 
  15 #include <linux/mm.h>
  16 #include <asm/system.h>
  17 #include <linux/delay.h>
  18 
  19 #define GFP_LEVEL_MASK 0xf
  20 
  21 /* I want this low enough for a while to catch errors.
  22    I want this number to be increased in the near future:
  23         loadable device drivers should use this function to get memory */
  24 
  25 #define MAX_KMALLOC_K ((PAGE_SIZE<<(NUM_AREA_ORDERS-1))>>10)
  26 
  27 
  28 /* This defines how many times we should try to allocate a free page before
  29    giving up. Normally this shouldn't happen at all. */
  30 #define MAX_GET_FREE_PAGE_TRIES 4
  31 
  32 
  33 /* Private flags. */
  34 
  35 #define MF_USED 0xffaa0055
  36 #define MF_FREE 0x0055ffaa
  37 
  38 
  39 /* 
  40  * Much care has gone into making these routines in this file reentrant.
  41  *
  42  * The fancy bookkeeping of nbytesmalloced and the like are only used to
  43  * report them to the user (oooohhhhh, aaaaahhhhh....) are not 
  44  * protected by cli(). (If that goes wrong. So what?)
  45  *
  46  * These routines restore the interrupt status to allow calling with ints
  47  * off. 
  48  */
  49 
  50 /* 
  51  * A block header. This is in front of every malloc-block, whether free or not.
  52  */
  53 struct block_header {
  54         unsigned long bh_flags;
  55         union {
  56                 unsigned long ubh_length;
  57                 struct block_header *fbh_next;
  58         } vp;
  59 };
  60 
  61 
  62 #define bh_length vp.ubh_length
  63 #define bh_next   vp.fbh_next
  64 #define BH(p) ((struct block_header *)(p))
  65 
  66 
  67 /* 
  68  * The page descriptor is at the front of every page that malloc has in use. 
  69  */
  70 struct page_descriptor {
  71         struct page_descriptor *next;
  72         struct block_header *firstfree;
  73         int order;
  74         int nfree;
  75 };
  76 
  77 
  78 #define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))
  79 
  80 
  81 /*
  82  * A size descriptor describes a specific class of malloc sizes.
  83  * Each class of sizes has its own freelist.
  84  */
  85 struct size_descriptor {
  86         struct page_descriptor *firstfree;
  87         int size;
  88         int nblocks;
  89 
  90         int nmallocs;
  91         int nfrees;
  92         int nbytesmalloced;
  93         int npages;
  94         unsigned long gfporder; /* number of pages in the area required */
  95 };
  96 
  97 /*
  98  * For now it is unsafe to allocate bucket sizes between n & n=16 where n is
  99  * 4096 * any power of two
 100  */
 101 
 102 struct size_descriptor sizes[] = { 
 103         { NULL,  32,127, 0,0,0,0, 0},
 104         { NULL,  64, 63, 0,0,0,0, 0 },
 105         { NULL, 128, 31, 0,0,0,0, 0 },
 106         { NULL, 252, 16, 0,0,0,0, 0 },
 107         { NULL, 508,  8, 0,0,0,0, 0 },
 108         { NULL,1020,  4, 0,0,0,0, 0 },
 109         { NULL,2040,  2, 0,0,0,0, 0 },
 110         { NULL,4096-16,  1, 0,0,0,0, 0 },
 111         { NULL,8192-16,  1, 0,0,0,0, 1 },
 112         { NULL,16384-16,  1, 0,0,0,0, 2 },
 113         { NULL,32768-16,  1, 0,0,0,0, 3 },
 114         { NULL,65536-16,  1, 0,0,0,0, 4 },
 115         { NULL,131072-16,  1, 0,0,0,0, 5 },
 116         { NULL,   0,  0, 0,0,0,0, 0 }
 117 };
 118 
 119 
 120 #define NBLOCKS(order)          (sizes[order].nblocks)
 121 #define BLOCKSIZE(order)        (sizes[order].size)
 122 #define AREASIZE(order)         (PAGE_SIZE<<(sizes[order].gfporder))
 123 
 124 
 125 long kmalloc_init (long start_mem,long end_mem)
     /* [previous][next][first][last][top][bottom][index][help] */
 126 {
 127         int order;
 128 
 129 /* 
 130  * Check the static info array. Things will blow up terribly if it's
 131  * incorrect. This is a late "compile time" check.....
 132  */
 133 for (order = 0;BLOCKSIZE(order);order++)
 134     {
 135     if ((NBLOCKS (order)*BLOCKSIZE(order) + sizeof (struct page_descriptor)) >
 136         AREASIZE(order)) 
 137         {
 138         printk ("Cannot use %d bytes out of %d in order = %d block mallocs\n",
 139                 NBLOCKS (order) * BLOCKSIZE(order) + 
 140                         sizeof (struct page_descriptor),
 141                 (int) AREASIZE(order),
 142                 BLOCKSIZE (order));
 143         panic ("This only happens if someone messes with kmalloc");
 144         }
 145     }
 146 return start_mem;
 147 }
 148 
 149 
 150 
 151 int get_order (int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 152 {
 153         int order;
 154 
 155         /* Add the size of the header */
 156         size += sizeof (struct block_header); 
 157         for (order = 0;BLOCKSIZE(order);order++)
 158                 if (size <= BLOCKSIZE (order))
 159                         return order; 
 160         return -1;
 161 }
 162 
 163 void * kmalloc (size_t size, int priority)
     /* [previous][next][first][last][top][bottom][index][help] */
 164 {
 165         unsigned long flags;
 166         int order,tries,i,sz;
 167         struct block_header *p;
 168         struct page_descriptor *page;
 169 
 170 /* Sanity check... */
 171         if (intr_count && priority != GFP_ATOMIC) {
 172                 static int count = 0;
 173                 if (++count < 5) {
 174                         printk("kmalloc called nonatomically from interrupt %08lx\n",
 175                                 ((unsigned long *)&size)[-1]);
 176                         priority = GFP_ATOMIC;
 177                 }
 178         }
 179 
 180 order = get_order (size);
 181 if (order < 0)
 182     {
 183     printk ("kmalloc of too large a block (%d bytes).\n",size);
 184     return (NULL);
 185     }
 186 
 187 save_flags(flags);
 188 
 189 /* It seems VERY unlikely to me that it would be possible that this 
 190    loop will get executed more than once. */
 191 tries = MAX_GET_FREE_PAGE_TRIES; 
 192 while (tries --)
 193     {
 194     /* Try to allocate a "recently" freed memory block */
 195     cli ();
 196     if ((page = sizes[order].firstfree) &&
 197         (p    =  page->firstfree))
 198         {
 199         if (p->bh_flags == MF_FREE)
 200             {
 201             page->firstfree = p->bh_next;
 202             page->nfree--;
 203             if (!page->nfree)
 204                 {
 205                 sizes[order].firstfree = page->next;
 206                 page->next = NULL;
 207                 }
 208             restore_flags(flags);
 209 
 210             sizes [order].nmallocs++;
 211             sizes [order].nbytesmalloced += size;
 212             p->bh_flags =  MF_USED; /* As of now this block is officially in use */
 213             p->bh_length = size;
 214             return p+1; /* Pointer arithmetic: increments past header */
 215             }
 216         printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
 217         return (NULL);
 218         }
 219     restore_flags(flags);
 220 
 221 
 222     /* Now we're in trouble: We need to get a new free page..... */
 223 
 224     sz = BLOCKSIZE(order); /* sz is the size of the blocks we're dealing with */
 225 
 226     /* This can be done with ints on: This is private to this invocation */
 227     page = (struct page_descriptor *) __get_free_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
 228     if (!page) {
 229         static unsigned long last = 0;
 230         if (last + 10*HZ < jiffies) {
 231                 last = jiffies;
 232                 printk ("Couldn't get a free page.....\n");
 233         }
 234         return NULL;
 235     }
 236 #if 0
 237     printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
 238 #endif
 239     sizes[order].npages++;
 240 
 241     /* Loop for all but last block: */
 242     for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next) 
 243         {
 244         p->bh_flags = MF_FREE;
 245         p->bh_next = BH ( ((long)p)+sz);
 246         }
 247     /* Last block: */
 248     p->bh_flags = MF_FREE;
 249     p->bh_next = NULL;
 250 
 251     page->order = order;
 252     page->nfree = NBLOCKS(order); 
 253     page->firstfree = BH(page+1);
 254 #if 0
 255     printk ("%d blocks per page\n",page->nfree);
 256 #endif
 257     /* Now we're going to muck with the "global" freelist for this size:
 258        this should be uniterruptible */
 259     cli ();
 260     /* 
 261      * sizes[order].firstfree used to be NULL, otherwise we wouldn't be
 262      * here, but you never know.... 
 263      */
 264     page->next = sizes[order].firstfree;
 265     sizes[order].firstfree = page;
 266     restore_flags(flags);
 267     }
 268 
 269 /* Pray that printk won't cause this to happen again :-) */
 270 
 271 printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
 272         "new page for an object only %d bytes long, but some other process\n"
 273         "beat me to actually allocating it. Also note that this 'error'\n"
 274         "message is soooo very long to catch your attention. I'd appreciate\n"
 275         "it if you'd be so kind as to report what conditions caused this to\n"
 276         "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
 277         "(Executive summary: This can't happen)\n", 
 278                 MAX_GET_FREE_PAGE_TRIES,
 279                 size);
 280 return NULL;
 281 }
 282 
 283 
 284 void kfree_s (void *ptr,int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 285 {
 286 unsigned long flags;
 287 int order;
 288 register struct block_header *p=((struct block_header *)ptr) -1;
 289 struct page_descriptor *page,*pg2;
 290 
 291 page = PAGE_DESC (p);
 292 order = page->order;
 293 if ((order < 0) || 
 294     (order > sizeof (sizes)/sizeof (sizes[0])) ||
 295     (((long)(page->next)) & ~PAGE_MASK) ||
 296     (p->bh_flags != MF_USED))
 297     {
 298     printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
 299                 p, page->next, page->order);
 300     return;
 301     }
 302 if (size &&
 303     size != p->bh_length)
 304     {
 305     printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
 306         p,size,p->bh_length);
 307     return;
 308     }
 309 size = p->bh_length;
 310 p->bh_flags = MF_FREE; /* As of now this block is officially free */
 311 save_flags(flags);
 312 cli ();
 313 p->bh_next = page->firstfree;
 314 page->firstfree = p;
 315 page->nfree ++;
 316 
 317 if (page->nfree == 1)
 318    { /* Page went from full to one free block: put it on the freelist */
 319    if (page->next)
 320         {
 321         printk ("Page %p already on freelist dazed and confused....\n", page);
 322         }
 323    else
 324         {
 325         page->next = sizes[order].firstfree;
 326         sizes[order].firstfree = page;
 327         }
 328    }
 329 
 330 /* If page is completely free, free it */
 331 if (page->nfree == NBLOCKS (page->order))
 332     {
 333 #if 0
 334     printk ("Freeing page %08x.\n", (long)page);
 335 #endif
 336     if (sizes[order].firstfree == page)
 337         {
 338         sizes[order].firstfree = page->next;
 339         }
 340     else
 341         {
 342         for (pg2=sizes[order].firstfree;
 343                 (pg2 != NULL) && (pg2->next != page);
 344                         pg2=pg2->next)
 345             /* Nothing */;
 346         if (pg2 != NULL)
 347             pg2->next = page->next;
 348         else
 349             printk ("Ooops. page %p doesn't show on freelist.\n", page);
 350         }
 351 /* FIXME: I'm sure we should do something with npages here (like npages--) */
 352     free_pages ((long)page, sizes[order].gfporder);
 353     }
 354 restore_flags(flags);
 355 
 356 /* FIXME: ?? Are these increment & decrement operations guaranteed to be
 357  *           atomic? Could an IRQ not occur between the read & the write?
 358  *           Maybe yes on a x86 with GCC...??
 359  */
 360 sizes[order].nfrees++;      /* Noncritical (monitoring) admin stuff */
 361 sizes[order].nbytesmalloced -= size;
 362 }

/* [previous][next][first][last][top][bottom][index][help] */