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

DEFINITIONS
