URL https://opencores.org/ocsvn/or1k_old/or1k_old/trunk

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [rc203soc/] [sw/] [uClinux/] [mm/] [kmalloc.c] - Blame information for rev 1782

Details | Compare with Previous | View Log


/*
 *  linux/mm/kmalloc.c
 *
 *  Copyright (C) 1991, 1992  Linus Torvalds & Roger Wolff.
 *
 *  Written by R.E. Wolff Sept/Oct '93.
 *
 */
 
/*
 * Modified by Alex Bligh (alex@cconcepts.co.uk) 4 Apr 1994 to use multiple
 * pages. So for 'page' throughout, read 'area'.
 *
 * Largely rewritten.. Linus
 */
 
#include <linux/mm.h>
#include <linux/delay.h>
#include <linux/interrupt.h>
 
#include <asm/system.h>
#include <asm/dma.h>
 
/* Define this if you want slow routines that try to trip errors */
#undef SADISTIC_KMALLOC
 
/* 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
 * protected by cli(). (If that goes wrong. So what?)
 *
 * These routines restore the interrupt status to allow calling with ints
 * off.
 */
 
/*
 * A block header. This is in front of every malloc-block, whether free or not.
 */
struct block_header {
        unsigned long bh_flags;
        union {
                unsigned long ubh_length;
                struct block_header *fbh_next;
        } vp;
};
 
 
#define bh_length vp.ubh_length
#define bh_next   vp.fbh_next
#define BH(p) ((struct block_header *)(p))
 
 
/*
 * The page descriptor is at the front of every page that malloc has in use.
 */
struct page_descriptor {
        struct page_descriptor *next;
        struct block_header *firstfree;
        int order;
        int nfree;
};
 
 
#define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))
 
 
/*
 * A size descriptor describes a specific class of malloc sizes.
 * Each class of sizes has its own freelist.
 */
struct size_descriptor {
        struct page_descriptor *firstfree;
        struct page_descriptor *dmafree;        /* DMA-able memory */
        int nblocks;
 
        int nmallocs;
        int nfrees;
        int nbytesmalloced;
        int npages;
        unsigned long gfporder; /* number of pages in the area required */
};
 
/*
 * For now it is unsafe to allocate bucket sizes between n and
 * n-sizeof(page_descriptor) where n is PAGE_SIZE * any power of two
 *
 * The blocksize and sizes arrays _must_ match!
 */
#if PAGE_SIZE == 4096
static const unsigned int blocksize[] = {
        32,
        64,
        128,
        252,
        508,
        1020,
        2040,
        4096 - 16,
        8192 - 16,
        16384 - 16,
        32768 - 16,
        65536 - 16,
        131072 - 16,
 
};
 
static struct size_descriptor sizes[] =
{
        {NULL, NULL, 127, 0, 0, 0, 0, 0},
        {NULL, NULL, 63, 0, 0, 0, 0, 0},
        {NULL, NULL, 31, 0, 0, 0, 0, 0},
        {NULL, NULL, 16, 0, 0, 0, 0, 0},
        {NULL, NULL, 8, 0, 0, 0, 0, 0},
        {NULL, NULL, 4, 0, 0, 0, 0, 0},
        {NULL, NULL, 2, 0, 0, 0, 0, 0},
        {NULL, NULL, 1, 0, 0, 0, 0, 0},
        {NULL, NULL, 1, 0, 0, 0, 0, 1},
        {NULL, NULL, 1, 0, 0, 0, 0, 2},
        {NULL, NULL, 1, 0, 0, 0, 0, 3},
        {NULL, NULL, 1, 0, 0, 0, 0, 4},
        {NULL, NULL, 1, 0, 0, 0, 0, 5},
        {NULL, NULL, 0, 0, 0, 0, 0, 0}
};
#elif PAGE_SIZE == 8192
static const unsigned int blocksize[] = {
        64,
        128,
        248,
        504,
        1016,
        2040,
        4080,
        8192 - 32,
        16384 - 32,
        32768 - 32,
        65536 - 32,
        131072 - 32,
        262144 - 32,
 
};
 
struct size_descriptor sizes[] =
{
        {NULL, NULL, 127, 0, 0, 0, 0, 0},
        {NULL, NULL, 63, 0, 0, 0, 0, 0},
        {NULL, NULL, 31, 0, 0, 0, 0, 0},
        {NULL, NULL, 16, 0, 0, 0, 0, 0},
        {NULL, NULL, 8, 0, 0, 0, 0, 0},
        {NULL, NULL, 4, 0, 0, 0, 0, 0},
        {NULL, NULL, 2, 0, 0, 0, 0, 0},
        {NULL, NULL, 1, 0, 0, 0, 0, 0},
        {NULL, NULL, 1, 0, 0, 0, 0, 1},
        {NULL, NULL, 1, 0, 0, 0, 0, 2},
        {NULL, NULL, 1, 0, 0, 0, 0, 3},
        {NULL, NULL, 1, 0, 0, 0, 0, 4},
        {NULL, NULL, 1, 0, 0, 0, 0, 5},
        {NULL, NULL, 0, 0, 0, 0, 0, 0}
};
#else
#error you need to make a version for your pagesize
#endif
 
#define NBLOCKS(order)          (sizes[order].nblocks)
#define BLOCKSIZE(order)        (blocksize[order])
#define AREASIZE(order)         (PAGE_SIZE<<(sizes[order].gfporder))
 
/*
 * Create a small cache of page allocations: this helps a bit with
 * those pesky 8kB+ allocations for NFS when we're temporarily
 * out of memory..
 *
 * This is a _truly_ small cache, we just cache one single page
 * order (for orders 0, 1 and 2, that is  4, 8 and 16kB on x86).
 */
#define MAX_CACHE_ORDER 3
struct page_descriptor * kmalloc_cache[MAX_CACHE_ORDER];
 
static inline struct page_descriptor * get_kmalloc_pages(unsigned long priority,
        unsigned long order, int dma)
{
        return (struct page_descriptor *) __get_free_pages(priority, order, dma);
}
 
static inline void free_kmalloc_pages(struct page_descriptor * page,
        unsigned long order, int dma)
{
        if (!dma && order < MAX_CACHE_ORDER) {
                page = xchg(kmalloc_cache+order, page);
                if (!page)
                        return;
        }
        free_pages((unsigned long) page, order);
}
 
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;
}
 
 
/*
 * Ugh, this is ugly, but we want the default case to run
 * straight through, which is why we have the ugly goto's
 */
void *kmalloc(size_t size, int priority)
{
        unsigned long flags;
        unsigned long type;
        int order, dma;
        struct block_header *p;
        struct page_descriptor *page, **pg;
        struct size_descriptor *bucket = sizes;
 
        /* Get order */
        order = 0;
        {
                unsigned int realsize = size + sizeof(struct block_header);
                for (;;) {
                        int ordersize = BLOCKSIZE(order);
                        if (realsize <= ordersize)
                                break;
                        order++;
                        bucket++;
                        if (ordersize)
                                continue;
                        printk("kmalloc of too large a block (%d bytes).\n", (int) size);
                        return NULL;
                }
        }
 
        dma = 0;
        type = MF_USED;
        pg = &bucket->firstfree;
        if (priority & GFP_DMA) {
                dma = 1;
                type = MF_DMA;
                pg = &bucket->dmafree;
        }
 
        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));
                        priority = GFP_ATOMIC;
                }
        }
 
        save_flags(flags);
        cli();
        page = *pg;
        if (!page)
                goto no_bucket_page;
 
        p = page->firstfree;
        if (p->bh_flags != MF_FREE)
                goto not_free_on_freelist;
 
found_it:
        page->firstfree = p->bh_next;
        page->nfree--;
        if (!page->nfree)
                *pg = page->next;
        restore_flags(flags);
        bucket->nmallocs++;
        bucket->nbytesmalloced += size;
        p->bh_flags = type;     /* As of now this block is officially in use */
        p->bh_length = size;
#ifdef SADISTIC_KMALLOC
        memset(p+1, 0xf0, size);
#endif
        return p + 1;           /* Pointer arithmetic: increments past header */
 
 
no_bucket_page:
        /*
         * If we didn't find a page already allocated for this
         * bucket size, we need to get one..
         *
         * This can be done with ints on: it is private to this invocation
         */
        restore_flags(flags);
 
        {
                int i, sz;
 
                /* sz is the size of the blocks we're dealing with */
                sz = BLOCKSIZE(order);
 
                page = get_kmalloc_pages(priority, bucket->gfporder, dma);
                if (!page)
                        goto no_free_page;
found_cached_page:
 
                bucket->npages++;
 
                page->order = order;
                /* Loop for all but last block: */
                i = (page->nfree = bucket->nblocks) - 1;
                p = BH(page + 1);
                while (i > 0) {
                        i--;
                        p->bh_flags = MF_FREE;
                        p->bh_next = BH(((long) p) + sz);
                        p = p->bh_next;
                }
                /* Last block: */
                p->bh_flags = MF_FREE;
                p->bh_next = NULL;
 
                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;
        goto found_it;
 
 
no_free_page:
        /*
         * No free pages, check the kmalloc cache of
         * pages to see if maybe we have something available
         */
        if (!dma && order < MAX_CACHE_ORDER) {
                page = xchg(kmalloc_cache+order, page);
                if (page)
                        goto found_cached_page;
        }
        {
                static unsigned long last = 0;
                if (priority != GFP_BUFFER && priority != GFP_IO &&
                    (last + 10 * HZ < jiffies)) {
                        last = jiffies;
                        printk("Couldn't get a free page.....\n");
                }
                return NULL;
        }
 
not_free_on_freelist:
        restore_flags(flags);
        printk("Problem: block on freelist at %08lx isn't free.\n", (long) p);
        return NULL;
}
 
void kfree(void *__ptr)
{
        int dma;
        unsigned long flags;
        unsigned int order;
        struct page_descriptor *page, **pg;
        struct size_descriptor *bucket;
 
        if (!__ptr)
                goto null_kfree;
#define ptr ((struct block_header *) __ptr)
        page = PAGE_DESC(ptr);
        __ptr = ptr - 1;
        if (~PAGE_MASK & (unsigned long)page->next)
                goto bad_order;
        order = page->order;
        if (order >= sizeof(sizes) / sizeof(sizes[0]))
                goto bad_order;
        bucket = sizes + order;
        dma = 0;
        pg = &bucket->firstfree;
        if (ptr->bh_flags == MF_DMA) {
                dma = 1;
                ptr->bh_flags = MF_USED;
                pg = &bucket->dmafree;
        }
        if (ptr->bh_flags != MF_USED)
                goto bad_order;
        ptr->bh_flags = MF_FREE;        /* As of now this block is officially free */
#ifdef SADISTIC_KMALLOC
        memset(ptr+1, 0xe0, ptr->bh_length);
#endif
        save_flags(flags);
        cli();
 
        bucket->nfrees++;
        bucket->nbytesmalloced -= ptr->bh_length;
 
        ptr->bh_next = page->firstfree;
        page->firstfree = ptr;
        if (!page->nfree++) {
/* Page went from full to one free block: put it on the freelist. */
                if (bucket->nblocks == 1)
                        goto free_page;
                page->next = *pg;
                *pg = page;
        }
/* If page is completely free, free it */
        if (page->nfree == bucket->nblocks) {
                for (;;) {
                        struct page_descriptor *tmp = *pg;
                        if (!tmp)
                                goto not_on_freelist;
                        if (tmp == page)
                                break;
                        pg = &tmp->next;
                }
                *pg = page->next;
free_page:
                bucket->npages--;
                free_kmalloc_pages(page, bucket->gfporder, dma);
        }
        restore_flags(flags);
null_kfree:
        return;
 
bad_order:
        printk("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
               ptr+1, page->next, page->order);
        return;
 
not_on_freelist:
        restore_flags(flags);
        printk("Ooops. page %p doesn't show on freelist.\n", page);
}

Browse

Tools

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [rc203soc/] [sw/] [uClinux/] [mm/] [kmalloc.c] - Blame information for rev 1782

Line No.	Rev	Author	Line
1	1634	jcastillo	`/*`
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 <linux/interrupt.h>`
20
21			`#include <asm/system.h>`
22			`#include <asm/dma.h>`
23
24			`/* Define this if you want slow routines that try to trip errors */`
25			`#undef SADISTIC_KMALLOC`
26
27			`/* Private flags. */`
28
29			`#define MF_USED 0xffaa0055`
30			`#define MF_DMA 0xff00aa55`
31			`#define MF_FREE 0x0055ffaa`
32
33
34			`/*`
35			`* Much care has gone into making these routines in this file reentrant.`
36			`*`
37			`* The fancy bookkeeping of nbytesmalloced and the like are only used to`
38			`* report them to the user (oooohhhhh, aaaaahhhhh....) are not`
39			`* protected by cli(). (If that goes wrong. So what?)`
40			`*`
41			`* These routines restore the interrupt status to allow calling with ints`
42			`* off.`
43			`*/`
44
45			`/*`
46			`* A block header. This is in front of every malloc-block, whether free or not.`
47			`*/`
48			`struct block_header {`
49			`unsigned long bh_flags;`
50			`union {`
51			`unsigned long ubh_length;`
52			`struct block_header *fbh_next;`
53			`} vp;`
54			`};`
55
56
57			`#define bh_length vp.ubh_length`
58			`#define bh_next vp.fbh_next`
59			`#define BH(p) ((struct block_header *)(p))`
60
61
62			`/*`
63			`* The page descriptor is at the front of every page that malloc has in use.`
64			`*/`
65			`struct page_descriptor {`
66			`struct page_descriptor *next;`
67			`struct block_header *firstfree;`
68			`int order;`
69			`int nfree;`
70			`};`
71
72
73			`#define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))`
74
75
76			`/*`
77			`* A size descriptor describes a specific class of malloc sizes.`
78			`* Each class of sizes has its own freelist.`
79			`*/`
80			`struct size_descriptor {`
81			`struct page_descriptor *firstfree;`
82			`struct page_descriptor dmafree; / DMA-able memory */`
83			`int nblocks;`
84
85			`int nmallocs;`
86			`int nfrees;`
87			`int nbytesmalloced;`
88			`int npages;`
89			`unsigned long gfporder; /* number of pages in the area required */`
90			`};`
91
92			`/*`
93			`* For now it is unsafe to allocate bucket sizes between n and`
94			`* n-sizeof(page_descriptor) where n is PAGE_SIZE * any power of two`
95			`*`
96			`* The blocksize and sizes arrays _must_ match!`
97			`*/`
98			`#if PAGE_SIZE == 4096`
99			`static const unsigned int blocksize[] = {`
100			`32,`
101			`64,`
102			`128,`
103			`252,`
104			`508,`
105			`1020,`
106			`2040,`
107			`4096 - 16,`
108			`8192 - 16,`
109			`16384 - 16,`
110			`32768 - 16,`
111			`65536 - 16,`
112			`131072 - 16,`
113
114			`};`
115
116			`static struct size_descriptor sizes[] =`
117			`{`
118			`{NULL, NULL, 127, 0, 0, 0, 0, 0},`
119			`{NULL, NULL, 63, 0, 0, 0, 0, 0},`
120			`{NULL, NULL, 31, 0, 0, 0, 0, 0},`
121			`{NULL, NULL, 16, 0, 0, 0, 0, 0},`
122			`{NULL, NULL, 8, 0, 0, 0, 0, 0},`
123			`{NULL, NULL, 4, 0, 0, 0, 0, 0},`
124			`{NULL, NULL, 2, 0, 0, 0, 0, 0},`
125			`{NULL, NULL, 1, 0, 0, 0, 0, 0},`
126			`{NULL, NULL, 1, 0, 0, 0, 0, 1},`
127			`{NULL, NULL, 1, 0, 0, 0, 0, 2},`
128			`{NULL, NULL, 1, 0, 0, 0, 0, 3},`
129			`{NULL, NULL, 1, 0, 0, 0, 0, 4},`
130			`{NULL, NULL, 1, 0, 0, 0, 0, 5},`
131			`{NULL, NULL, 0, 0, 0, 0, 0, 0}`
132			`};`
133			`#elif PAGE_SIZE == 8192`
134			`static const unsigned int blocksize[] = {`
135			`64,`
136			`128,`
137			`248,`
138			`504,`
139			`1016,`
140			`2040,`
141			`4080,`
142			`8192 - 32,`
143			`16384 - 32,`
144			`32768 - 32,`
145			`65536 - 32,`
146			`131072 - 32,`
147			`262144 - 32,`
148
149			`};`
150
151			`struct size_descriptor sizes[] =`
152			`{`
153			`{NULL, NULL, 127, 0, 0, 0, 0, 0},`
154			`{NULL, NULL, 63, 0, 0, 0, 0, 0},`
155			`{NULL, NULL, 31, 0, 0, 0, 0, 0},`
156			`{NULL, NULL, 16, 0, 0, 0, 0, 0},`
157			`{NULL, NULL, 8, 0, 0, 0, 0, 0},`
158			`{NULL, NULL, 4, 0, 0, 0, 0, 0},`
159			`{NULL, NULL, 2, 0, 0, 0, 0, 0},`
160			`{NULL, NULL, 1, 0, 0, 0, 0, 0},`
161			`{NULL, NULL, 1, 0, 0, 0, 0, 1},`
162			`{NULL, NULL, 1, 0, 0, 0, 0, 2},`
163			`{NULL, NULL, 1, 0, 0, 0, 0, 3},`
164			`{NULL, NULL, 1, 0, 0, 0, 0, 4},`
165			`{NULL, NULL, 1, 0, 0, 0, 0, 5},`
166			`{NULL, NULL, 0, 0, 0, 0, 0, 0}`
167			`};`
168			`#else`
169			`#error you need to make a version for your pagesize`
170			`#endif`
171
172			`#define NBLOCKS(order) (sizes[order].nblocks)`
173			`#define BLOCKSIZE(order) (blocksize[order])`
174			`#define AREASIZE(order) (PAGE_SIZE<<(sizes[order].gfporder))`
175
176			`/*`
177			`* Create a small cache of page allocations: this helps a bit with`
178			`* those pesky 8kB+ allocations for NFS when we're temporarily`
179			`* out of memory..`
180			`*`
181			`* This is a _truly_ small cache, we just cache one single page`
182			`* order (for orders 0, 1 and 2, that is 4, 8 and 16kB on x86).`
183			`*/`
184			`#define MAX_CACHE_ORDER 3`
185			`struct page_descriptor * kmalloc_cache[MAX_CACHE_ORDER];`
186
187			`static inline struct page_descriptor * get_kmalloc_pages(unsigned long priority,`
188			`unsigned long order, int dma)`
189			`{`
190			`return (struct page_descriptor *) __get_free_pages(priority, order, dma);`
191			`}`
192
193			`static inline void free_kmalloc_pages(struct page_descriptor * page,`
194			`unsigned long order, int dma)`
195			`{`
196			`if (!dma && order < MAX_CACHE_ORDER) {`
197			`page = xchg(kmalloc_cache+order, page);`
198			`if (!page)`
199			`return;`
200			`}`
201			`free_pages((unsigned long) page, order);`
202			`}`
203
204			`long kmalloc_init(long start_mem, long end_mem)`
205			`{`
206			`int order;`
207
208			`/*`
209			`* Check the static info array. Things will blow up terribly if it's`
210			`* incorrect. This is a late "compile time" check.....`
211			`*/`
212			`for (order = 0; BLOCKSIZE(order); order++) {`
213			`if ((NBLOCKS(order) * BLOCKSIZE(order) + sizeof(struct page_descriptor)) >`
214			`AREASIZE(order)) {`
215			`printk("Cannot use %d bytes out of %d in order = %d block mallocs\n",`
216			`(int) (NBLOCKS(order) * BLOCKSIZE(order) +`
217			`sizeof(struct page_descriptor)),`
218			`(int) AREASIZE(order),`
219			`BLOCKSIZE(order));`
220			`panic("This only happens if someone messes with kmalloc");`
221			`}`
222			`}`
223			`return start_mem;`
224			`}`
225
226
227			`/*`
228			`* Ugh, this is ugly, but we want the default case to run`
229			`* straight through, which is why we have the ugly goto's`
230			`*/`
231			`void *kmalloc(size_t size, int priority)`
232			`{`
233			`unsigned long flags;`
234			`unsigned long type;`
235			`int order, dma;`
236			`struct block_header *p;`
237			`struct page_descriptor page, *pg;`
238			`struct size_descriptor *bucket = sizes;`
239
240			`/* Get order */`
241			`order = 0;`
242			`{`
243			`unsigned int realsize = size + sizeof(struct block_header);`
244			`for (;;) {`
245			`int ordersize = BLOCKSIZE(order);`
246			`if (realsize <= ordersize)`
247			`break;`
248			`order++;`
249			`bucket++;`
250			`if (ordersize)`
251			`continue;`
252			`printk("kmalloc of too large a block (%d bytes).\n", (int) size);`
253			`return NULL;`
254			`}`
255			`}`
256
257			`dma = 0;`
258			`type = MF_USED;`
259			`pg = &bucket->firstfree;`
260			`if (priority & GFP_DMA) {`
261			`dma = 1;`
262			`type = MF_DMA;`
263			`pg = &bucket->dmafree;`
264			`}`
265
266			`priority &= GFP_LEVEL_MASK;`
267
268			`/* Sanity check... */`
269			`if (intr_count && priority != GFP_ATOMIC) {`
270			`static int count = 0;`
271			`if (++count < 5) {`
272			`printk("kmalloc called nonatomically from interrupt %p\n",`
273			`__builtin_return_address(0));`
274			`priority = GFP_ATOMIC;`
275			`}`
276			`}`
277
278			`save_flags(flags);`
279			`cli();`
280			`page = *pg;`
281			`if (!page)`
282			`goto no_bucket_page;`
283
284			`p = page->firstfree;`
285			`if (p->bh_flags != MF_FREE)`
286			`goto not_free_on_freelist;`
287
288			`found_it:`
289			`page->firstfree = p->bh_next;`
290			`page->nfree--;`
291			`if (!page->nfree)`
292			`*pg = page->next;`
293			`restore_flags(flags);`
294			`bucket->nmallocs++;`
295			`bucket->nbytesmalloced += size;`
296			`p->bh_flags = type; /* As of now this block is officially in use */`
297			`p->bh_length = size;`
298			`#ifdef SADISTIC_KMALLOC`
299			`memset(p+1, 0xf0, size);`
300			`#endif`
301			`return p + 1; /* Pointer arithmetic: increments past header */`
302
303
304			`no_bucket_page:`
305			`/*`
306			`* If we didn't find a page already allocated for this`
307			`* bucket size, we need to get one..`
308			`*`
309			`* This can be done with ints on: it is private to this invocation`
310			`*/`
311			`restore_flags(flags);`
312
313			`{`
314			`int i, sz;`
315
316			`/* sz is the size of the blocks we're dealing with */`
317			`sz = BLOCKSIZE(order);`
318
319			`page = get_kmalloc_pages(priority, bucket->gfporder, dma);`
320			`if (!page)`
321			`goto no_free_page;`
322			`found_cached_page:`
323
324			`bucket->npages++;`
325
326			`page->order = order;`
327			`/* Loop for all but last block: */`
328			`i = (page->nfree = bucket->nblocks) - 1;`
329			`p = BH(page + 1);`
330			`while (i > 0) {`
331			`i--;`
332			`p->bh_flags = MF_FREE;`
333			`p->bh_next = BH(((long) p) + sz);`
334			`p = p->bh_next;`
335			`}`
336			`/* Last block: */`
337			`p->bh_flags = MF_FREE;`
338			`p->bh_next = NULL;`
339
340			`p = BH(page+1);`
341			`}`
342
343			`/*`
344			`* Now we're going to muck with the "global" freelist`
345			`* for this size: this should be uninterruptible`
346			`*/`
347			`cli();`
348			`page->next = *pg;`
349			`*pg = page;`
350			`goto found_it;`
351
352
353			`no_free_page:`
354			`/*`
355			`* No free pages, check the kmalloc cache of`
356			`* pages to see if maybe we have something available`
357			`*/`
358			`if (!dma && order < MAX_CACHE_ORDER) {`
359			`page = xchg(kmalloc_cache+order, page);`
360			`if (page)`
361			`goto found_cached_page;`
362			`}`
363			`{`
364			`static unsigned long last = 0;`
365			`if (priority != GFP_BUFFER && priority != GFP_IO &&`
366			`(last + 10 * HZ < jiffies)) {`
367			`last = jiffies;`
368			`printk("Couldn't get a free page.....\n");`
369			`}`
370			`return NULL;`
371			`}`
372
373			`not_free_on_freelist:`
374			`restore_flags(flags);`
375			`printk("Problem: block on freelist at %08lx isn't free.\n", (long) p);`
376			`return NULL;`
377			`}`
378
379			`void kfree(void *__ptr)`
380			`{`
381			`int dma;`
382			`unsigned long flags;`
383			`unsigned int order;`
384			`struct page_descriptor page, *pg;`
385			`struct size_descriptor *bucket;`
386
387			`if (!__ptr)`
388			`goto null_kfree;`
389			`#define ptr ((struct block_header *) __ptr)`
390			`page = PAGE_DESC(ptr);`
391			`__ptr = ptr - 1;`
392			`if (~PAGE_MASK & (unsigned long)page->next)`
393			`goto bad_order;`
394			`order = page->order;`
395			`if (order >= sizeof(sizes) / sizeof(sizes[0]))`
396			`goto bad_order;`
397			`bucket = sizes + order;`
398			`dma = 0;`
399			`pg = &bucket->firstfree;`
400			`if (ptr->bh_flags == MF_DMA) {`
401			`dma = 1;`
402			`ptr->bh_flags = MF_USED;`
403			`pg = &bucket->dmafree;`
404			`}`
405			`if (ptr->bh_flags != MF_USED)`
406			`goto bad_order;`
407			`ptr->bh_flags = MF_FREE; /* As of now this block is officially free */`
408			`#ifdef SADISTIC_KMALLOC`
409			`memset(ptr+1, 0xe0, ptr->bh_length);`
410			`#endif`
411			`save_flags(flags);`
412			`cli();`
413
414			`bucket->nfrees++;`
415			`bucket->nbytesmalloced -= ptr->bh_length;`
416
417			`ptr->bh_next = page->firstfree;`
418			`page->firstfree = ptr;`
419			`if (!page->nfree++) {`
420			`/* Page went from full to one free block: put it on the freelist. */`
421			`if (bucket->nblocks == 1)`
422			`goto free_page;`
423			`page->next = *pg;`
424			`*pg = page;`
425			`}`
426			`/* If page is completely free, free it */`
427			`if (page->nfree == bucket->nblocks) {`
428			`for (;;) {`
429			`struct page_descriptor tmp = pg;`
430			`if (!tmp)`
431			`goto not_on_freelist;`
432			`if (tmp == page)`
433			`break;`
434			`pg = &tmp->next;`
435			`}`
436			`*pg = page->next;`
437			`free_page:`
438			`bucket->npages--;`
439			`free_kmalloc_pages(page, bucket->gfporder, dma);`
440			`}`
441			`restore_flags(flags);`
442			`null_kfree:`
443			`return;`
444
445			`bad_order:`
446			`printk("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",`
447			`ptr+1, page->next, page->order);`
448			`return;`
449
450			`not_on_freelist:`
451			`restore_flags(flags);`
452			`printk("Ooops. page %p doesn't show on freelist.\n", page);`
453			`}`