patch-1.3.22 linux/mm/kmalloc.c
Next file: linux/mm/memory.c
Previous file: linux/mm/filemap.c
Back to the patch index
Back to the overall index
- Lines: 557
- Date:
Fri Sep 1 16:13:19 1995
- Orig file:
v1.3.21/linux/mm/kmalloc.c
- Orig date:
Thu Jun 29 19:02:55 1995
diff -u --recursive --new-file v1.3.21/linux/mm/kmalloc.c linux/mm/kmalloc.c
@@ -32,21 +32,22 @@
/* Private flags. */
#define MF_USED 0xffaa0055
+#define MF_DMA 0xff00aa55
#define MF_FREE 0x0055ffaa
-/*
+/*
* Much care has gone into making these routines in this file reentrant.
*
* The fancy bookkeeping of nbytesmalloced and the like are only used to
- * report them to the user (oooohhhhh, aaaaahhhhh....) are not
+ * report them to the user (oooohhhhh, aaaaahhhhh....) are not
* protected by cli(). (If that goes wrong. So what?)
*
* These routines restore the interrupt status to allow calling with ints
- * off.
+ * off.
*/
-/*
+/*
* A block header. This is in front of every malloc-block, whether free or not.
*/
struct block_header {
@@ -63,8 +64,8 @@
#define BH(p) ((struct block_header *)(p))
-/*
- * The page descriptor is at the front of every page that malloc has in use.
+/*
+ * The page descriptor is at the front of every page that malloc has in use.
*/
struct page_descriptor {
struct page_descriptor *next;
@@ -83,7 +84,7 @@
*/
struct size_descriptor {
struct page_descriptor *firstfree;
- struct page_descriptor *dmafree; /* DMA-able memory */
+ struct page_descriptor *dmafree; /* DMA-able memory */
int size;
int nblocks;
@@ -91,7 +92,7 @@
int nfrees;
int nbytesmalloced;
int npages;
- unsigned long gfporder; /* number of pages in the area required */
+ unsigned long gfporder; /* number of pages in the area required */
};
/*
@@ -99,38 +100,40 @@
* 4096 * any power of two
*/
#if PAGE_SIZE == 4096
-struct size_descriptor sizes[] = {
- { NULL, NULL, 32,127, 0,0,0,0, 0},
- { NULL, NULL, 64, 63, 0,0,0,0, 0 },
- { NULL, NULL, 128, 31, 0,0,0,0, 0 },
- { NULL, NULL, 252, 16, 0,0,0,0, 0 },
- { NULL, NULL, 508, 8, 0,0,0,0, 0 },
- { NULL, NULL,1020, 4, 0,0,0,0, 0 },
- { NULL, NULL,2040, 2, 0,0,0,0, 0 },
- { NULL, NULL,4096-16, 1, 0,0,0,0, 0 },
- { NULL, NULL,8192-16, 1, 0,0,0,0, 1 },
- { NULL, NULL,16384-16, 1, 0,0,0,0, 2 },
- { NULL, NULL,32768-16, 1, 0,0,0,0, 3 },
- { NULL, NULL,65536-16, 1, 0,0,0,0, 4 },
- { NULL, NULL,131072-16, 1, 0,0,0,0, 5 },
- { NULL, NULL, 0, 0, 0,0,0,0, 0 }
+struct size_descriptor sizes[] =
+{
+ {NULL, NULL, 32, 127, 0, 0, 0, 0, 0},
+ {NULL, NULL, 64, 63, 0, 0, 0, 0, 0},
+ {NULL, NULL, 128, 31, 0, 0, 0, 0, 0},
+ {NULL, NULL, 252, 16, 0, 0, 0, 0, 0},
+ {NULL, NULL, 508, 8, 0, 0, 0, 0, 0},
+ {NULL, NULL, 1020, 4, 0, 0, 0, 0, 0},
+ {NULL, NULL, 2040, 2, 0, 0, 0, 0, 0},
+ {NULL, NULL, 4096 - 16, 1, 0, 0, 0, 0, 0},
+ {NULL, NULL, 8192 - 16, 1, 0, 0, 0, 0, 1},
+ {NULL, NULL, 16384 - 16, 1, 0, 0, 0, 0, 2},
+ {NULL, NULL, 32768 - 16, 1, 0, 0, 0, 0, 3},
+ {NULL, NULL, 65536 - 16, 1, 0, 0, 0, 0, 4},
+ {NULL, NULL, 131072 - 16, 1, 0, 0, 0, 0, 5},
+ {NULL, NULL, 0, 0, 0, 0, 0, 0, 0}
};
#elif PAGE_SIZE == 8192
-struct size_descriptor sizes[] = {
- { NULL, NULL, 64,127, 0,0,0,0, 0},
- { NULL, NULL, 128, 63, 0,0,0,0, 0 },
- { NULL, NULL, 248, 31, 0,0,0,0, 0 },
- { NULL, NULL, 504, 16, 0,0,0,0, 0 },
- { NULL, NULL,1016, 8, 0,0,0,0, 0 },
- { NULL, NULL,2040, 4, 0,0,0,0, 0 },
- { NULL, NULL,4080, 2, 0,0,0,0, 0 },
- { NULL, NULL,8192-32, 1, 0,0,0,0, 0 },
- { NULL, NULL,16384-32, 1, 0,0,0,0, 1 },
- { NULL, NULL,32768-32, 1, 0,0,0,0, 2 },
- { NULL, NULL,65536-32, 1, 0,0,0,0, 3 },
- { NULL, NULL,131072-32, 1, 0,0,0,0, 4 },
- { NULL, NULL,262144-32, 1, 0,0,0,0, 5 },
- { NULL, NULL, 0, 0, 0,0,0,0, 0 }
+struct size_descriptor sizes[] =
+{
+ {NULL, NULL, 64, 127, 0, 0, 0, 0, 0},
+ {NULL, NULL, 128, 63, 0, 0, 0, 0, 0},
+ {NULL, NULL, 248, 31, 0, 0, 0, 0, 0},
+ {NULL, NULL, 504, 16, 0, 0, 0, 0, 0},
+ {NULL, NULL, 1016, 8, 0, 0, 0, 0, 0},
+ {NULL, NULL, 2040, 4, 0, 0, 0, 0, 0},
+ {NULL, NULL, 4080, 2, 0, 0, 0, 0, 0},
+ {NULL, NULL, 8192 - 32, 1, 0, 0, 0, 0, 0},
+ {NULL, NULL, 16384 - 32, 1, 0, 0, 0, 0, 1},
+ {NULL, NULL, 32768 - 32, 1, 0, 0, 0, 0, 2},
+ {NULL, NULL, 65536 - 32, 1, 0, 0, 0, 0, 3},
+ {NULL, NULL, 131072 - 32, 1, 0, 0, 0, 0, 4},
+ {NULL, NULL, 262144 - 32, 1, 0, 0, 0, 0, 5},
+ {NULL, NULL, 0, 0, 0, 0, 0, 0, 0}
};
#else
#error you need to make a version for your pagesize
@@ -141,269 +144,201 @@
#define AREASIZE(order) (PAGE_SIZE<<(sizes[order].gfporder))
-long kmalloc_init (long start_mem,long end_mem)
+long kmalloc_init(long start_mem, long end_mem)
{
int order;
-/*
+/*
* Check the static info array. Things will blow up terribly if it's
* incorrect. This is a late "compile time" check.....
*/
-for (order = 0;BLOCKSIZE(order);order++)
- {
- if ((NBLOCKS (order)*BLOCKSIZE(order) + sizeof (struct page_descriptor)) >
- AREASIZE(order))
- {
- printk ("Cannot use %d bytes out of %d in order = %d block mallocs\n",
- (int) (NBLOCKS (order) * BLOCKSIZE(order) +
- sizeof (struct page_descriptor)),
- (int) AREASIZE(order),
- BLOCKSIZE (order));
- panic ("This only happens if someone messes with kmalloc");
- }
- }
-return start_mem;
+ for (order = 0; BLOCKSIZE(order); order++) {
+ if ((NBLOCKS(order) * BLOCKSIZE(order) + sizeof(struct page_descriptor)) >
+ AREASIZE(order)) {
+ printk("Cannot use %d bytes out of %d in order = %d block mallocs\n",
+ (int) (NBLOCKS(order) * BLOCKSIZE(order) +
+ sizeof(struct page_descriptor)),
+ (int) AREASIZE(order),
+ BLOCKSIZE(order));
+ panic("This only happens if someone messes with kmalloc");
+ }
+ }
+ return start_mem;
}
-int get_order (int size)
+int get_order(int size)
{
int order;
/* Add the size of the header */
- size += sizeof (struct block_header);
- for (order = 0;BLOCKSIZE(order);order++)
- if (size <= BLOCKSIZE (order))
- return order;
+ size += sizeof(struct block_header);
+ for (order = 0; BLOCKSIZE(order); order++)
+ if (size <= BLOCKSIZE(order))
+ return order;
return -1;
}
-void * kmalloc (size_t size, int priority)
+void *kmalloc(size_t size, int priority)
{
unsigned long flags;
- int order,tries,i,sz;
- int dma_flag;
+ unsigned long max_addr, type;
+ int order, i, sz;
struct block_header *p;
- struct page_descriptor *page;
+ struct page_descriptor *page, **pg;
+
+ order = get_order(size);
+ if (order < 0) {
+ printk("kmalloc of too large a block (%d bytes).\n", (int) size);
+ return (NULL);
+ }
+
+ max_addr = ~0UL;
+ type = MF_USED;
+ pg = &sizes[order].firstfree;
+ if (priority & GFP_DMA) {
+ max_addr = MAX_DMA_ADDRESS;
+ type = MF_DMA;
+ pg = &sizes[order].dmafree;
+ }
- dma_flag = (priority & GFP_DMA);
priority &= GFP_LEVEL_MASK;
-
+
/* Sanity check... */
if (intr_count && priority != GFP_ATOMIC) {
static int count = 0;
if (++count < 5) {
printk("kmalloc called nonatomically from interrupt %p\n",
- __builtin_return_address(0));
+ __builtin_return_address(0));
priority = GFP_ATOMIC;
}
}
-order = get_order (size);
-if (order < 0)
- {
- printk ("kmalloc of too large a block (%d bytes).\n",(int) size);
- return (NULL);
- }
-
-save_flags(flags);
-
-/* It seems VERY unlikely to me that it would be possible that this
- loop will get executed more than once. */
-tries = MAX_GET_FREE_PAGE_TRIES;
-while (tries --)
- {
- /* Try to allocate a "recently" freed memory block */
- cli ();
- if ((page = (dma_flag ? sizes[order].dmafree : sizes[order].firstfree)) &&
- (p = page->firstfree))
- {
- if (p->bh_flags == MF_FREE)
- {
- page->firstfree = p->bh_next;
- page->nfree--;
- if (!page->nfree)
- {
- if(dma_flag)
- sizes[order].dmafree = page->next;
- else
- sizes[order].firstfree = page->next;
- page->next = NULL;
- }
- restore_flags(flags);
-
- sizes [order].nmallocs++;
- sizes [order].nbytesmalloced += size;
- p->bh_flags = MF_USED; /* As of now this block is officially in use */
- p->bh_length = size;
- return p+1; /* Pointer arithmetic: increments past header */
- }
- printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
- return (NULL);
- }
- restore_flags(flags);
-
-
- /* Now we're in trouble: We need to get a new free page..... */
-
- sz = BLOCKSIZE(order); /* sz is the size of the blocks we're dealing with */
-
- /* This can be done with ints on: This is private to this invocation */
- {
- unsigned long max_addr = ~0UL;
- if (dma_flag)
- max_addr = MAX_DMA_ADDRESS;
- page = (struct page_descriptor *) __get_free_pages (priority & GFP_LEVEL_MASK,
- sizes[order].gfporder, max_addr);
- }
-
- if (!page) {
- static unsigned long last = 0;
- if (last + 10*HZ < jiffies) {
- last = jiffies;
- printk ("Couldn't get a free page.....\n");
- }
- return NULL;
- }
-#if 0
- printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
-#endif
- sizes[order].npages++;
+ save_flags(flags);
+ cli();
+ page = *pg;
+ if (page) {
+ p = page->firstfree;
+ if (p->bh_flags != MF_FREE) {
+ restore_flags(flags);
+ printk("Problem: block on freelist at %08lx isn't free.\n", (long) p);
+ return NULL;
+ }
+ goto found_it;
+ }
- /* Loop for all but last block: */
- for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next)
- {
- p->bh_flags = MF_FREE;
- p->bh_next = BH ( ((long)p)+sz);
- }
- /* Last block: */
- p->bh_flags = MF_FREE;
- p->bh_next = NULL;
-
- page->order = order;
- page->nfree = NBLOCKS(order);
- page->firstfree = BH(page+1);
-#if 0
- printk ("%d blocks per page\n",page->nfree);
-#endif
- /* Now we're going to muck with the "global" freelist for this size:
- this should be uninterruptible */
- cli ();
- /*
- * sizes[order].firstfree used to be NULL, otherwise we wouldn't be
- * here, but you never know....
- */
- if (dma_flag) {
- page->next = sizes[order].dmafree;
- sizes[order].dmafree = page;
- } else {
- page->next = sizes[order].firstfree;
- sizes[order].firstfree = page;
- }
- restore_flags(flags);
- }
-
-/* Pray that printk won't cause this to happen again :-) */
-
-printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
- "new page for an object only %d bytes long, but some other process\n"
- "beat me to actually allocating it. Also note that this 'error'\n"
- "message is soooo very long to catch your attention. I'd appreciate\n"
- "it if you'd be so kind as to report what conditions caused this to\n"
- "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
- "(Executive summary: This can't happen)\n",
- MAX_GET_FREE_PAGE_TRIES,
- (int) size);
-return NULL;
+ /* We need to get a new free page..... */
+
+ /* sz is the size of the blocks we're dealing with */
+ sz = BLOCKSIZE(order);
+
+ /* This can be done with ints on: This is private to this invocation */
+ page = (struct page_descriptor *) __get_free_pages(priority & GFP_LEVEL_MASK,
+ sizes[order].gfporder, max_addr);
+
+ if (!page) {
+ static unsigned long last = 0;
+ if (last + 10 * HZ < jiffies) {
+ last = jiffies;
+ printk("Couldn't get a free page.....\n");
+ }
+ return NULL;
+ }
+ sizes[order].npages++;
+
+ /* Loop for all but last block: */
+ for (i = NBLOCKS(order), p = BH(page + 1); i > 1; i--, p = p->bh_next) {
+ p->bh_flags = MF_FREE;
+ p->bh_next = BH(((long) p) + sz);
+ }
+ /* Last block: */
+ p->bh_flags = MF_FREE;
+ p->bh_next = NULL;
+
+ page->order = order;
+ page->nfree = NBLOCKS(order);
+ p = BH(page+1);
+
+ /*
+ * Now we're going to muck with the "global" freelist
+ * for this size: this should be uninterruptible
+ */
+ cli();
+ page->next = *pg;
+ *pg = page;
+
+found_it:
+ page->firstfree = p->bh_next;
+ page->nfree--;
+ if (!page->nfree)
+ *pg = page->next;
+ restore_flags(flags);
+ sizes[order].nmallocs++;
+ sizes[order].nbytesmalloced += size;
+ p->bh_flags = type; /* As of now this block is officially in use */
+ p->bh_length = size;
+ return p + 1; /* Pointer arithmetic: increments past header */
}
-void kfree_s (void *ptr,int size)
+void kfree(void *ptr)
{
-unsigned long flags;
-int order;
-register struct block_header *p=((struct block_header *)ptr) -1;
-struct page_descriptor *page,*pg2;
-
-page = PAGE_DESC (p);
-order = page->order;
-if ((order < 0) ||
- (order > sizeof (sizes)/sizeof (sizes[0])) ||
- (((long)(page->next)) & ~PAGE_MASK) ||
- (p->bh_flags != MF_USED))
- {
- printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
- p, page->next, page->order);
- return;
- }
-if (size &&
- size != p->bh_length)
- {
- printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
- p,size,p->bh_length);
- return;
- }
-size = p->bh_length;
-p->bh_flags = MF_FREE; /* As of now this block is officially free */
-save_flags(flags);
-cli ();
-p->bh_next = page->firstfree;
-page->firstfree = p;
-page->nfree ++;
-
-if (page->nfree == 1)
- { /* Page went from full to one free block: put it on the freelist. Do not bother
- trying to put it on the DMA list. */
- if (page->next)
- {
- printk ("Page %p already on freelist dazed and confused....\n", page);
- }
- else
- {
- page->next = sizes[order].firstfree;
- sizes[order].firstfree = page;
- }
- }
+ int size;
+ unsigned long flags;
+ int order;
+ register struct block_header *p;
+ struct page_descriptor *page, **pg;
+ if (!ptr)
+ return;
+ p = ((struct block_header *) ptr) - 1;
+ page = PAGE_DESC(p);
+ order = page->order;
+ pg = &sizes[order].firstfree;
+ if (p->bh_flags == MF_DMA) {
+ p->bh_flags = MF_USED;
+ pg = &sizes[order].dmafree;
+ }
+
+ if ((order < 0) ||
+ (order > sizeof(sizes) / sizeof(sizes[0])) ||
+ (((long) (page->next)) & ~PAGE_MASK) ||
+ (p->bh_flags != MF_USED)) {
+ printk("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
+ p, page->next, page->order);
+ return;
+ }
+ size = p->bh_length;
+ p->bh_flags = MF_FREE; /* As of now this block is officially free */
+ save_flags(flags);
+ cli();
+ p->bh_next = page->firstfree;
+ page->firstfree = p;
+ page->nfree++;
+
+ if (page->nfree == 1) {
+/* Page went from full to one free block: put it on the freelist. */
+ page->next = *pg;
+ *pg = page;
+ }
/* If page is completely free, free it */
-if (page->nfree == NBLOCKS (page->order))
- {
-#if 0
- printk ("Freeing page %08x.\n", (long)page);
-#endif
- if (sizes[order].firstfree == page)
- {
- sizes[order].firstfree = page->next;
- }
- else if (sizes[order].dmafree == page)
- {
- sizes[order].dmafree = page->next;
- }
- else
- {
- for (pg2=sizes[order].firstfree;
- (pg2 != NULL) && (pg2->next != page);
- pg2=pg2->next)
- /* Nothing */;
- if (!pg2)
- for (pg2=sizes[order].dmafree;
- (pg2 != NULL) && (pg2->next != page);
- pg2=pg2->next)
- /* Nothing */;
- if (pg2 != NULL)
- pg2->next = page->next;
- else
- printk ("Ooops. page %p doesn't show on freelist.\n", page);
- }
-/* FIXME: I'm sure we should do something with npages here (like npages--) */
- free_pages ((long)page, sizes[order].gfporder);
- }
-restore_flags(flags);
-
-/* FIXME: ?? Are these increment & decrement operations guaranteed to be
- * atomic? Could an IRQ not occur between the read & the write?
- * Maybe yes on a x86 with GCC...??
- */
-sizes[order].nfrees++; /* Noncritical (monitoring) admin stuff */
-sizes[order].nbytesmalloced -= size;
+ if (page->nfree == NBLOCKS(order)) {
+ for (;;) {
+ struct page_descriptor *tmp = *pg;
+ if (!tmp) {
+ printk("Ooops. page %p doesn't show on freelist.\n", page);
+ break;
+ }
+ if (tmp == page) {
+ *pg = page->next;
+ break;
+ }
+ pg = &tmp->next;
+ }
+ sizes[order].npages--;
+ free_pages((long) page, sizes[order].gfporder);
+ }
+ sizes[order].nfrees++;
+ sizes[order].nbytesmalloced -= size;
+ restore_flags(flags);
}
FUNET's LINUX-ADM group, linux-adm@nic.funet.fi
TCL-scripts by Sam Shen, slshen@lbl.gov
with Sam's (original) version of this