mm/kmalloc.c

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

DEFINITIONS
