root/mm/kmalloc.c

/* */

DEFINITIONS

1. kmalloc_init
2. get_order
3. kmalloc
4. kfree

   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  * Largely rewritten.. Linus
  15  */
  16 
  17 #include <linux/mm.h>
  18 #include <linux/delay.h>
  19 #include <asm/system.h>
  20 #include <asm/dma.h>
  21 
  22 
  23 /* Private flags. */
  24 
  25 #define MF_USED 0xffaa0055
  26 #define MF_DMA  0xff00aa55
  27 #define MF_FREE 0x0055ffaa
  28 
  29 
  30 /*
  31  * Much care has gone into making these routines in this file reentrant.
  32  *
  33  * The fancy bookkeeping of nbytesmalloced and the like are only used to
  34  * report them to the user (oooohhhhh, aaaaahhhhh....) are not
  35  * protected by cli(). (If that goes wrong. So what?)
  36  *
  37  * These routines restore the interrupt status to allow calling with ints
  38  * off.
  39  */
  40 
  41 /*
  42  * A block header. This is in front of every malloc-block, whether free or not.
  43  */
  44 struct block_header {
  45         unsigned long bh_flags;
  46         union {
  47                 unsigned long ubh_length;
  48                 struct block_header *fbh_next;
  49         } vp;
  50 };
  51 
  52 
  53 #define bh_length vp.ubh_length
  54 #define bh_next   vp.fbh_next
  55 #define BH(p) ((struct block_header *)(p))
  56 
  57 
  58 /*
  59  * The page descriptor is at the front of every page that malloc has in use.
  60  */
  61 struct page_descriptor {
  62         struct page_descriptor *next;
  63         struct block_header *firstfree;
  64         int order;
  65         int nfree;
  66 };
  67 
  68 
  69 #define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))
  70 
  71 
  72 /*
  73  * A size descriptor describes a specific class of malloc sizes.
  74  * Each class of sizes has its own freelist.
  75  */
  76 struct size_descriptor {
  77         struct page_descriptor *firstfree;
  78         struct page_descriptor *dmafree;        /* DMA-able memory */
  79         int size;
  80         int nblocks;
  81 
  82         int nmallocs;
  83         int nfrees;
  84         int nbytesmalloced;
  85         int npages;
  86         unsigned long gfporder; /* number of pages in the area required */
  87 };
  88 
  89 /*
  90  * For now it is unsafe to allocate bucket sizes between n and n-16 where n is
  91  * 4096 * any power of two
  92  */
  93 #if PAGE_SIZE == 4096
  94 struct size_descriptor sizes[] =
  95 {
  96         {NULL, NULL, 32, 127, 0, 0, 0, 0, 0},
  97         {NULL, NULL, 64, 63, 0, 0, 0, 0, 0},
  98         {NULL, NULL, 128, 31, 0, 0, 0, 0, 0},
  99         {NULL, NULL, 252, 16, 0, 0, 0, 0, 0},
 100         {NULL, NULL, 508, 8, 0, 0, 0, 0, 0},
 101         {NULL, NULL, 1020, 4, 0, 0, 0, 0, 0},
 102         {NULL, NULL, 2040, 2, 0, 0, 0, 0, 0},
 103         {NULL, NULL, 4096 - 16, 1, 0, 0, 0, 0, 0},
 104         {NULL, NULL, 8192 - 16, 1, 0, 0, 0, 0, 1},
 105         {NULL, NULL, 16384 - 16, 1, 0, 0, 0, 0, 2},
 106         {NULL, NULL, 32768 - 16, 1, 0, 0, 0, 0, 3},
 107         {NULL, NULL, 65536 - 16, 1, 0, 0, 0, 0, 4},
 108         {NULL, NULL, 131072 - 16, 1, 0, 0, 0, 0, 5},
 109         {NULL, NULL, 0, 0, 0, 0, 0, 0, 0}
 110 };
 111 #elif PAGE_SIZE == 8192
 112 struct size_descriptor sizes[] =
 113 {
 114         {NULL, NULL, 64, 127, 0, 0, 0, 0, 0},
 115         {NULL, NULL, 128, 63, 0, 0, 0, 0, 0},
 116         {NULL, NULL, 248, 31, 0, 0, 0, 0, 0},
 117         {NULL, NULL, 504, 16, 0, 0, 0, 0, 0},
 118         {NULL, NULL, 1016, 8, 0, 0, 0, 0, 0},
 119         {NULL, NULL, 2040, 4, 0, 0, 0, 0, 0},
 120         {NULL, NULL, 4080, 2, 0, 0, 0, 0, 0},
 121         {NULL, NULL, 8192 - 32, 1, 0, 0, 0, 0, 0},
 122         {NULL, NULL, 16384 - 32, 1, 0, 0, 0, 0, 1},
 123         {NULL, NULL, 32768 - 32, 1, 0, 0, 0, 0, 2},
 124         {NULL, NULL, 65536 - 32, 1, 0, 0, 0, 0, 3},
 125         {NULL, NULL, 131072 - 32, 1, 0, 0, 0, 0, 4},
 126         {NULL, NULL, 262144 - 32, 1, 0, 0, 0, 0, 5},
 127         {NULL, NULL, 0, 0, 0, 0, 0, 0, 0}
 128 };
 129 #else
 130 #error you need to make a version for your pagesize
 131 #endif
 132 
 133 #define NBLOCKS(order)          (sizes[order].nblocks)
 134 #define BLOCKSIZE(order)        (sizes[order].size)
 135 #define AREASIZE(order)         (PAGE_SIZE<<(sizes[order].gfporder))
 136 
 137 
 138 long kmalloc_init(long start_mem, long end_mem)
     /*  */
 139 {
 140         int order;
 141 
 142 /*
 143  * Check the static info array. Things will blow up terribly if it's
 144  * incorrect. This is a late "compile time" check.....
 145  */
 146         for (order = 0; BLOCKSIZE(order); order++) {
 147                 if ((NBLOCKS(order) * BLOCKSIZE(order) + sizeof(struct page_descriptor)) >
 148                     AREASIZE(order)) {
 149                         printk("Cannot use %d bytes out of %d in order = %d block mallocs\n",
 150                                (int) (NBLOCKS(order) * BLOCKSIZE(order) +
 151                                       sizeof(struct page_descriptor)),
 152                                 (int) AREASIZE(order),
 153                                BLOCKSIZE(order));
 154                         panic("This only happens if someone messes with kmalloc");
 155                 }
 156         }
 157         return start_mem;
 158 }
 159 
 160 
 161 
 162 int get_order(int size)
     /*  */
 163 {
 164         int order;
 165 
 166         /* Add the size of the header */
 167         size += sizeof(struct block_header);
 168         for (order = 0; BLOCKSIZE(order); order++)
 169                 if (size <= BLOCKSIZE(order))
 170                         return order;
 171         return -1;
 172 }
 173 
 174 void *kmalloc(size_t size, int priority)
     /*  */
 175 {
 176         unsigned long flags;
 177         unsigned long max_addr, type;
 178         int order, i, sz;
 179         struct block_header *p;
 180         struct page_descriptor *page, **pg;
 181 
 182         order = get_order(size);
 183         if (order < 0) {
 184                 printk("kmalloc of too large a block (%d bytes).\n", (int) size);
 185                 return (NULL);
 186         }
 187 
 188         max_addr = ~0UL;
 189         type = MF_USED;
 190         pg = &sizes[order].firstfree;
 191         if (priority & GFP_DMA) {
 192                 max_addr = MAX_DMA_ADDRESS;
 193                 type = MF_DMA;
 194                 pg = &sizes[order].dmafree;
 195         }
 196 
 197         priority &= GFP_LEVEL_MASK;
 198 
 199 /* Sanity check... */
 200         if (intr_count && priority != GFP_ATOMIC) {
 201                 static int count = 0;
 202                 if (++count < 5) {
 203                         printk("kmalloc called nonatomically from interrupt %p\n",
 204                                __builtin_return_address(0));
 205                         priority = GFP_ATOMIC;
 206                 }
 207         }
 208 
 209         save_flags(flags);
 210         cli();
 211         page = *pg;
 212         if (page) {
 213                 p = page->firstfree;
 214                 if (p->bh_flags != MF_FREE) {
 215                         restore_flags(flags);
 216                         printk("Problem: block on freelist at %08lx isn't free.\n", (long) p);
 217                         return NULL;
 218                 }
 219                 goto found_it;
 220         }
 221 
 222         /* We need to get a new free page..... */
 223         /* This can be done with ints on: This is private to this invocation */
 224         restore_flags(flags);
 225 
 226         /* sz is the size of the blocks we're dealing with */
 227         sz = BLOCKSIZE(order);
 228 
 229         page = (struct page_descriptor *) __get_free_pages(priority,
 230                         sizes[order].gfporder, max_addr);
 231 
 232         if (!page) {
 233                 static unsigned long last = 0;
 234                 if (priority != GFP_BUFFER && (last + 10 * HZ < jiffies)) {
 235                         last = jiffies;
 236                         printk("Couldn't get a free page.....\n");
 237                 }
 238                 return NULL;
 239         }
 240         sizes[order].npages++;
 241 
 242         /* Loop for all but last block: */
 243         for (i = NBLOCKS(order), p = BH(page + 1); i > 1; i--, p = p->bh_next) {
 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         p = BH(page+1);
 254 
 255         /*
 256          * Now we're going to muck with the "global" freelist
 257          * for this size: this should be uninterruptible
 258          */
 259         cli();
 260         page->next = *pg;
 261         *pg = page;
 262 
 263 found_it:
 264         page->firstfree = p->bh_next;
 265         page->nfree--;
 266         if (!page->nfree)
 267                 *pg = page->next;
 268         restore_flags(flags);
 269         sizes[order].nmallocs++;
 270         sizes[order].nbytesmalloced += size;
 271         p->bh_flags = type;     /* As of now this block is officially in use */
 272         p->bh_length = size;
 273         return p + 1;           /* Pointer arithmetic: increments past header */
 274 }
 275 
 276 void kfree(void *ptr)
     /*  */
 277 {
 278         int size;
 279         unsigned long flags;
 280         int order;
 281         register struct block_header *p;
 282         struct page_descriptor *page, **pg;
 283 
 284         if (!ptr)
 285                 return;
 286         p = ((struct block_header *) ptr) - 1;
 287         page = PAGE_DESC(p);
 288         order = page->order;
 289         pg = &sizes[order].firstfree;
 290         if (p->bh_flags == MF_DMA) {
 291                 p->bh_flags = MF_USED;
 292                 pg = &sizes[order].dmafree;
 293         }
 294 
 295         if ((order < 0) ||
 296             (order >= sizeof(sizes) / sizeof(sizes[0])) ||
 297             (((long) (page->next)) & ~PAGE_MASK) ||
 298             (p->bh_flags != MF_USED)) {
 299                 printk("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
 300                        p, page->next, page->order);
 301                 return;
 302         }
 303         size = p->bh_length;
 304         p->bh_flags = MF_FREE;  /* As of now this block is officially free */
 305         save_flags(flags);
 306         cli();
 307         p->bh_next = page->firstfree;
 308         page->firstfree = p;
 309         page->nfree++;
 310 
 311         if (page->nfree == 1) {
 312 /* Page went from full to one free block: put it on the freelist. */
 313                 page->next = *pg;
 314                 *pg = page;
 315         }
 316 /* If page is completely free, free it */
 317         if (page->nfree == NBLOCKS(order)) {
 318                 for (;;) {
 319                         struct page_descriptor *tmp = *pg;
 320                         if (!tmp) {
 321                                 printk("Ooops. page %p doesn't show on freelist.\n", page);
 322                                 break;
 323                         }
 324                         if (tmp == page) {
 325                                 *pg = page->next;
 326                                 break;
 327                         }
 328                         pg = &tmp->next;
 329                 }
 330                 sizes[order].npages--;
 331                 free_pages((long) page, sizes[order].gfporder);
 332         }
 333         sizes[order].nfrees++;
 334         sizes[order].nbytesmalloced -= size;
 335         restore_flags(flags);
 336 }

/* */