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         struct page_descriptor *dmafree; /* DMA-able memory */
  88         int size;
  89         int nblocks;
  90 
  91         int nmallocs;
  92         int nfrees;
  93         int nbytesmalloced;
  94         int npages;
  95         unsigned long gfporder; /* number of pages in the area required */
  96 };
  97 
  98 /*
  99  * For now it is unsafe to allocate bucket sizes between n & n=16 where n is
 100  * 4096 * any power of two
 101  */
 102 #if PAGE_SIZE == 4096
 103 struct size_descriptor sizes[] = { 
 104         { NULL, NULL,  32,127, 0,0,0,0, 0},
 105         { NULL, NULL,  64, 63, 0,0,0,0, 0 },
 106         { NULL, NULL, 128, 31, 0,0,0,0, 0 },
 107         { NULL, NULL, 252, 16, 0,0,0,0, 0 },
 108         { NULL, NULL, 508,  8, 0,0,0,0, 0 },
 109         { NULL, NULL,1020,  4, 0,0,0,0, 0 },
 110         { NULL, NULL,2040,  2, 0,0,0,0, 0 },
 111         { NULL, NULL,4096-16,  1, 0,0,0,0, 0 },
 112         { NULL, NULL,8192-16,  1, 0,0,0,0, 1 },
 113         { NULL, NULL,16384-16,  1, 0,0,0,0, 2 },
 114         { NULL, NULL,32768-16,  1, 0,0,0,0, 3 },
 115         { NULL, NULL,65536-16,  1, 0,0,0,0, 4 },
 116         { NULL, NULL,131072-16,  1, 0,0,0,0, 5 },
 117         { NULL, NULL,   0,  0, 0,0,0,0, 0 }
 118 };
 119 #elif PAGE_SIZE == 8192
 120 struct size_descriptor sizes[] = { 
 121         { NULL, NULL,  64,127, 0,0,0,0, 0},
 122         { NULL, NULL, 128, 63, 0,0,0,0, 0 },
 123         { NULL, NULL, 248, 31, 0,0,0,0, 0 },
 124         { NULL, NULL, 504, 16, 0,0,0,0, 0 },
 125         { NULL, NULL,1016,  8, 0,0,0,0, 0 },
 126         { NULL, NULL,2040,  4, 0,0,0,0, 0 },
 127         { NULL, NULL,4080,  2, 0,0,0,0, 0 },
 128         { NULL, NULL,8192-32,  1, 0,0,0,0, 0 },
 129         { NULL, NULL,16384-32,  1, 0,0,0,0, 1 },
 130         { NULL, NULL,32768-32,  1, 0,0,0,0, 2 },
 131         { NULL, NULL,65536-32,  1, 0,0,0,0, 3 },
 132         { NULL, NULL,131072-32,  1, 0,0,0,0, 4 },
 133         { NULL, NULL,262144-32,  1, 0,0,0,0, 5 },
 134         { NULL, NULL,   0,  0, 0,0,0,0, 0 }
 135 };
 136 #else
 137 #error you need to make a version for your pagesize
 138 #endif
 139 
 140 #define NBLOCKS(order)          (sizes[order].nblocks)
 141 #define BLOCKSIZE(order)        (sizes[order].size)
 142 #define AREASIZE(order)         (PAGE_SIZE<<(sizes[order].gfporder))
 143 
 144 
 145 long kmalloc_init (long start_mem,long end_mem)
     /* [previous][next][first][last][top][bottom][index][help] */
 146 {
 147         int order;
 148 
 149 /* 
 150  * Check the static info array. Things will blow up terribly if it's
 151  * incorrect. This is a late "compile time" check.....
 152  */
 153 for (order = 0;BLOCKSIZE(order);order++)
 154     {
 155     if ((NBLOCKS (order)*BLOCKSIZE(order) + sizeof (struct page_descriptor)) >
 156         AREASIZE(order)) 
 157         {
 158         printk ("Cannot use %d bytes out of %d in order = %d block mallocs\n",
 159                 (int) (NBLOCKS (order) * BLOCKSIZE(order) + 
 160                         sizeof (struct page_descriptor)),
 161                 (int) AREASIZE(order),
 162                 BLOCKSIZE (order));
 163         panic ("This only happens if someone messes with kmalloc");
 164         }
 165     }
 166 return start_mem;
 167 }
 168 
 169 
 170 
 171 int get_order (int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 172 {
 173         int order;
 174 
 175         /* Add the size of the header */
 176         size += sizeof (struct block_header);
 177         for (order = 0;BLOCKSIZE(order);order++)
 178                 if (size <= BLOCKSIZE (order))
 179                         return order; 
 180         return -1;
 181 }
 182 
 183 void * kmalloc (size_t size, int priority)
     /* [previous][next][first][last][top][bottom][index][help] */
 184 {
 185         unsigned long flags;
 186         int order,tries,i,sz;
 187         int dma_flag;
 188         struct block_header *p;
 189         struct page_descriptor *page;
 190 
 191         dma_flag = (priority & GFP_DMA);
 192         priority &= GFP_LEVEL_MASK;
 193           
 194 /* Sanity check... */
 195         if (intr_count && priority != GFP_ATOMIC) {
 196                 static int count = 0;
 197                 if (++count < 5) {
 198                         printk("kmalloc called nonatomically from interrupt %p\n",
 199                                 __builtin_return_address(0));
 200                         priority = GFP_ATOMIC;
 201                 }
 202         }
 203 
 204 order = get_order (size);
 205 if (order < 0)
 206     {
 207     printk ("kmalloc of too large a block (%d bytes).\n",(int) size);
 208     return (NULL);
 209     }
 210 
 211 save_flags(flags);
 212 
 213 /* It seems VERY unlikely to me that it would be possible that this 
 214    loop will get executed more than once. */
 215 tries = MAX_GET_FREE_PAGE_TRIES; 
 216 while (tries --)
 217     {
 218     /* Try to allocate a "recently" freed memory block */
 219     cli ();
 220     if ((page = (dma_flag ? sizes[order].dmafree : sizes[order].firstfree)) &&
 221         (p    =  page->firstfree))
 222         {
 223         if (p->bh_flags == MF_FREE)
 224             {
 225             page->firstfree = p->bh_next;
 226             page->nfree--;
 227             if (!page->nfree)
 228                 {
 229                   if(dma_flag)
 230                     sizes[order].dmafree = page->next;
 231                   else
 232                     sizes[order].firstfree = page->next;
 233                   page->next = NULL;
 234                 }
 235             restore_flags(flags);
 236 
 237             sizes [order].nmallocs++;
 238             sizes [order].nbytesmalloced += size;
 239             p->bh_flags =  MF_USED; /* As of now this block is officially in use */
 240             p->bh_length = size;
 241             return p+1; /* Pointer arithmetic: increments past header */
 242             }
 243         printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
 244         return (NULL);
 245         }
 246     restore_flags(flags);
 247 
 248 
 249     /* Now we're in trouble: We need to get a new free page..... */
 250 
 251     sz = BLOCKSIZE(order); /* sz is the size of the blocks we're dealing with */
 252 
 253     /* This can be done with ints on: This is private to this invocation */
 254     if (dma_flag)
 255       page = (struct page_descriptor *) __get_dma_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
 256     else
 257       page = (struct page_descriptor *) __get_free_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
 258 
 259     if (!page) {
 260         static unsigned long last = 0;
 261         if (last + 10*HZ < jiffies) {
 262                 last = jiffies;
 263                 printk ("Couldn't get a free page.....\n");
 264         }
 265         return NULL;
 266     }
 267 #if 0
 268     printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
 269 #endif
 270     sizes[order].npages++;
 271 
 272     /* Loop for all but last block: */
 273     for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next) 
 274         {
 275         p->bh_flags = MF_FREE;
 276         p->bh_next = BH ( ((long)p)+sz);
 277         }
 278     /* Last block: */
 279     p->bh_flags = MF_FREE;
 280     p->bh_next = NULL;
 281 
 282     page->order = order;
 283     page->nfree = NBLOCKS(order); 
 284     page->firstfree = BH(page+1);
 285 #if 0
 286     printk ("%d blocks per page\n",page->nfree);
 287 #endif
 288     /* Now we're going to muck with the "global" freelist for this size:
 289        this should be uninterruptible */
 290     cli ();
 291     /* 
 292      * sizes[order].firstfree used to be NULL, otherwise we wouldn't be
 293      * here, but you never know.... 
 294      */
 295     if (dma_flag) {
 296       page->next = sizes[order].dmafree;
 297       sizes[order].dmafree = page;
 298     } else {
 299       page->next = sizes[order].firstfree;
 300       sizes[order].firstfree = page;
 301     }
 302     restore_flags(flags);
 303     }
 304 
 305 /* Pray that printk won't cause this to happen again :-) */
 306 
 307 printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
 308         "new page for an object only %d bytes long, but some other process\n"
 309         "beat me to actually allocating it. Also note that this 'error'\n"
 310         "message is soooo very long to catch your attention. I'd appreciate\n"
 311         "it if you'd be so kind as to report what conditions caused this to\n"
 312         "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
 313         "(Executive summary: This can't happen)\n", 
 314                 MAX_GET_FREE_PAGE_TRIES,
 315                 (int) size);
 316 return NULL;
 317 }
 318 
 319 void kfree_s (void *ptr,int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 320 {
 321 unsigned long flags;
 322 int order;
 323 register struct block_header *p=((struct block_header *)ptr) -1;
 324 struct page_descriptor *page,*pg2;
 325 
 326 page = PAGE_DESC (p);
 327 order = page->order;
 328 if ((order < 0) || 
 329     (order > sizeof (sizes)/sizeof (sizes[0])) ||
 330     (((long)(page->next)) & ~PAGE_MASK) ||
 331     (p->bh_flags != MF_USED))
 332     {
 333     printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
 334                 p, page->next, page->order);
 335     return;
 336     }
 337 if (size &&
 338     size != p->bh_length)
 339     {
 340     printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
 341         p,size,p->bh_length);
 342     return;
 343     }
 344 size = p->bh_length;
 345 p->bh_flags = MF_FREE; /* As of now this block is officially free */
 346 save_flags(flags);
 347 cli ();
 348 p->bh_next = page->firstfree;
 349 page->firstfree = p;
 350 page->nfree ++;
 351 
 352 if (page->nfree == 1)
 353    { /* Page went from full to one free block: put it on the freelist.  Do not bother
 354       trying to put it on the DMA list. */
 355    if (page->next)
 356         {
 357         printk ("Page %p already on freelist dazed and confused....\n", page);
 358         }
 359    else
 360         {
 361         page->next = sizes[order].firstfree;
 362         sizes[order].firstfree = page;
 363         }
 364    }
 365 
 366 /* If page is completely free, free it */
 367 if (page->nfree == NBLOCKS (page->order))
 368     {
 369 #if 0
 370     printk ("Freeing page %08x.\n", (long)page);
 371 #endif
 372     if (sizes[order].firstfree == page)
 373         {
 374         sizes[order].firstfree = page->next;
 375         }
 376     else if (sizes[order].dmafree == page)
 377         {
 378         sizes[order].dmafree = page->next;
 379         }
 380     else
 381         {
 382         for (pg2=sizes[order].firstfree;
 383                 (pg2 != NULL) && (pg2->next != page);
 384                         pg2=pg2->next)
 385             /* Nothing */;
 386         if (!pg2)
 387           for (pg2=sizes[order].dmafree;
 388                (pg2 != NULL) && (pg2->next != page);
 389                pg2=pg2->next)
 390             /* Nothing */;
 391         if (pg2 != NULL)
 392             pg2->next = page->next;
 393         else
 394             printk ("Ooops. page %p doesn't show on freelist.\n", page);
 395         }
 396 /* FIXME: I'm sure we should do something with npages here (like npages--) */
 397     free_pages ((long)page, sizes[order].gfporder);
 398     }
 399 restore_flags(flags);
 400 
 401 /* FIXME: ?? Are these increment & decrement operations guaranteed to be
 402  *           atomic? Could an IRQ not occur between the read & the write?
 403  *           Maybe yes on a x86 with GCC...??
 404  */
 405 sizes[order].nfrees++;      /* Noncritical (monitoring) admin stuff */
 406 sizes[order].nbytesmalloced -= size;
 407 }

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