This source file includes following definitions.
- kmalloc_init
- get_order
- kmalloc
- kfree_s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 #include <linux/mm.h>
16 #include <asm/system.h>
17 #include <linux/delay.h>
18
19 #define GFP_LEVEL_MASK 0xf
20
21
22
23
24
25 #define MAX_KMALLOC_K ((PAGE_SIZE<<(NUM_AREA_ORDERS-1))>>10)
26
27
28
29
30 #define MAX_GET_FREE_PAGE_TRIES 4
31
32
33
34
35 #define MF_USED 0xffaa0055
36 #define MF_FREE 0x0055ffaa
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 struct block_header {
54 unsigned long bh_flags;
55 union {
56 unsigned long ubh_length;
57 struct block_header *fbh_next;
58 } vp;
59 };
60
61
62 #define bh_length vp.ubh_length
63 #define bh_next vp.fbh_next
64 #define BH(p) ((struct block_header *)(p))
65
66
67
68
69
70 struct page_descriptor {
71 struct page_descriptor *next;
72 struct block_header *firstfree;
73 int order;
74 int nfree;
75 };
76
77
78 #define PAGE_DESC(p) ((struct page_descriptor *)(((unsigned long)(p)) & PAGE_MASK))
79
80
81
82
83
84
85 struct size_descriptor {
86 struct page_descriptor *firstfree;
87 struct page_descriptor *dmafree;
88 int size;
89 int nblocks;
90
91 int nmallocs;
92 int nfrees;
93 int nbytesmalloced;
94 int npages;
95 unsigned long gfporder;
96 };
97
98
99
100
101
102 #if PAGE_SIZE == 4096
103 struct size_descriptor sizes[] = {
104 { NULL, NULL, 32,127, 0,0,0,0, 0},
105 { NULL, NULL, 64, 63, 0,0,0,0, 0 },
106 { NULL, NULL, 128, 31, 0,0,0,0, 0 },
107 { NULL, NULL, 252, 16, 0,0,0,0, 0 },
108 { NULL, NULL, 508, 8, 0,0,0,0, 0 },
109 { NULL, NULL,1020, 4, 0,0,0,0, 0 },
110 { NULL, NULL,2040, 2, 0,0,0,0, 0 },
111 { NULL, NULL,4096-16, 1, 0,0,0,0, 0 },
112 { NULL, NULL,8192-16, 1, 0,0,0,0, 1 },
113 { NULL, NULL,16384-16, 1, 0,0,0,0, 2 },
114 { NULL, NULL,32768-16, 1, 0,0,0,0, 3 },
115 { NULL, NULL,65536-16, 1, 0,0,0,0, 4 },
116 { NULL, NULL,131072-16, 1, 0,0,0,0, 5 },
117 { NULL, NULL, 0, 0, 0,0,0,0, 0 }
118 };
119 #elif PAGE_SIZE == 8192
120 struct size_descriptor sizes[] = {
121 { NULL, NULL, 64,127, 0,0,0,0, 0},
122 { NULL, NULL, 128, 63, 0,0,0,0, 0 },
123 { NULL, NULL, 248, 31, 0,0,0,0, 0 },
124 { NULL, NULL, 504, 16, 0,0,0,0, 0 },
125 { NULL, NULL,1016, 8, 0,0,0,0, 0 },
126 { NULL, NULL,2040, 4, 0,0,0,0, 0 },
127 { NULL, NULL,4080, 2, 0,0,0,0, 0 },
128 { NULL, NULL,8192-32, 1, 0,0,0,0, 0 },
129 { NULL, NULL,16384-32, 1, 0,0,0,0, 1 },
130 { NULL, NULL,32768-32, 1, 0,0,0,0, 2 },
131 { NULL, NULL,65536-32, 1, 0,0,0,0, 3 },
132 { NULL, NULL,131072-32, 1, 0,0,0,0, 4 },
133 { NULL, NULL,262144-32, 1, 0,0,0,0, 5 },
134 { NULL, NULL, 0, 0, 0,0,0,0, 0 }
135 };
136 #else
137 #error you need to make a version for your pagesize
138 #endif
139
140 #define NBLOCKS(order) (sizes[order].nblocks)
141 #define BLOCKSIZE(order) (sizes[order].size)
142 #define AREASIZE(order) (PAGE_SIZE<<(sizes[order].gfporder))
143
144
145 long kmalloc_init (long start_mem,long end_mem)
146 {
147 int order;
148
149
150
151
152
153 for (order = 0;BLOCKSIZE(order);order++)
154 {
155 if ((NBLOCKS (order)*BLOCKSIZE(order) + sizeof (struct page_descriptor)) >
156 AREASIZE(order))
157 {
158 printk ("Cannot use %d bytes out of %d in order = %d block mallocs\n",
159 (int) (NBLOCKS (order) * BLOCKSIZE(order) +
160 sizeof (struct page_descriptor)),
161 (int) AREASIZE(order),
162 BLOCKSIZE (order));
163 panic ("This only happens if someone messes with kmalloc");
164 }
165 }
166 return start_mem;
167 }
168
169
170
171 int get_order (int size)
172 {
173 int order;
174
175
176 size += sizeof (struct block_header);
177 for (order = 0;BLOCKSIZE(order);order++)
178 if (size <= BLOCKSIZE (order))
179 return order;
180 return -1;
181 }
182
183 void * kmalloc (size_t size, int priority)
184 {
185 unsigned long flags;
186 int order,tries,i,sz;
187 int dma_flag;
188 struct block_header *p;
189 struct page_descriptor *page;
190
191 dma_flag = (priority & GFP_DMA);
192 priority &= GFP_LEVEL_MASK;
193
194
195 if (intr_count && priority != GFP_ATOMIC) {
196 static int count = 0;
197 if (++count < 5) {
198 printk("kmalloc called nonatomically from interrupt %p\n",
199 __builtin_return_address(0));
200 priority = GFP_ATOMIC;
201 }
202 }
203
204 order = get_order (size);
205 if (order < 0)
206 {
207 printk ("kmalloc of too large a block (%d bytes).\n",(int) size);
208 return (NULL);
209 }
210
211 save_flags(flags);
212
213
214
215 tries = MAX_GET_FREE_PAGE_TRIES;
216 while (tries --)
217 {
218
219 cli ();
220 if ((page = (dma_flag ? sizes[order].dmafree : sizes[order].firstfree)) &&
221 (p = page->firstfree))
222 {
223 if (p->bh_flags == MF_FREE)
224 {
225 page->firstfree = p->bh_next;
226 page->nfree--;
227 if (!page->nfree)
228 {
229 if(dma_flag)
230 sizes[order].dmafree = page->next;
231 else
232 sizes[order].firstfree = page->next;
233 page->next = NULL;
234 }
235 restore_flags(flags);
236
237 sizes [order].nmallocs++;
238 sizes [order].nbytesmalloced += size;
239 p->bh_flags = MF_USED;
240 p->bh_length = size;
241 return p+1;
242 }
243 printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
244 return (NULL);
245 }
246 restore_flags(flags);
247
248
249
250
251 sz = BLOCKSIZE(order);
252
253
254 if (dma_flag)
255 page = (struct page_descriptor *) __get_dma_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
256 else
257 page = (struct page_descriptor *) __get_free_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
258
259 if (!page) {
260 static unsigned long last = 0;
261 if (last + 10*HZ < jiffies) {
262 last = jiffies;
263 printk ("Couldn't get a free page.....\n");
264 }
265 return NULL;
266 }
267 #if 0
268 printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
269 #endif
270 sizes[order].npages++;
271
272
273 for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next)
274 {
275 p->bh_flags = MF_FREE;
276 p->bh_next = BH ( ((long)p)+sz);
277 }
278
279 p->bh_flags = MF_FREE;
280 p->bh_next = NULL;
281
282 page->order = order;
283 page->nfree = NBLOCKS(order);
284 page->firstfree = BH(page+1);
285 #if 0
286 printk ("%d blocks per page\n",page->nfree);
287 #endif
288
289
290 cli ();
291
292
293
294
295 if (dma_flag) {
296 page->next = sizes[order].dmafree;
297 sizes[order].dmafree = page;
298 } else {
299 page->next = sizes[order].firstfree;
300 sizes[order].firstfree = page;
301 }
302 restore_flags(flags);
303 }
304
305
306
307 printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
308 "new page for an object only %d bytes long, but some other process\n"
309 "beat me to actually allocating it. Also note that this 'error'\n"
310 "message is soooo very long to catch your attention. I'd appreciate\n"
311 "it if you'd be so kind as to report what conditions caused this to\n"
312 "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
313 "(Executive summary: This can't happen)\n",
314 MAX_GET_FREE_PAGE_TRIES,
315 (int) size);
316 return NULL;
317 }
318
319 void kfree_s (void *ptr,int size)
320 {
321 unsigned long flags;
322 int order;
323 register struct block_header *p=((struct block_header *)ptr) -1;
324 struct page_descriptor *page,*pg2;
325
326 page = PAGE_DESC (p);
327 order = page->order;
328 if ((order < 0) ||
329 (order > sizeof (sizes)/sizeof (sizes[0])) ||
330 (((long)(page->next)) & ~PAGE_MASK) ||
331 (p->bh_flags != MF_USED))
332 {
333 printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
334 p, page->next, page->order);
335 return;
336 }
337 if (size &&
338 size != p->bh_length)
339 {
340 printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
341 p,size,p->bh_length);
342 return;
343 }
344 size = p->bh_length;
345 p->bh_flags = MF_FREE;
346 save_flags(flags);
347 cli ();
348 p->bh_next = page->firstfree;
349 page->firstfree = p;
350 page->nfree ++;
351
352 if (page->nfree == 1)
353 {
354
355 if (page->next)
356 {
357 printk ("Page %p already on freelist dazed and confused....\n", page);
358 }
359 else
360 {
361 page->next = sizes[order].firstfree;
362 sizes[order].firstfree = page;
363 }
364 }
365
366
367 if (page->nfree == NBLOCKS (page->order))
368 {
369 #if 0
370 printk ("Freeing page %08x.\n", (long)page);
371 #endif
372 if (sizes[order].firstfree == page)
373 {
374 sizes[order].firstfree = page->next;
375 }
376 else if (sizes[order].dmafree == page)
377 {
378 sizes[order].dmafree = page->next;
379 }
380 else
381 {
382 for (pg2=sizes[order].firstfree;
383 (pg2 != NULL) && (pg2->next != page);
384 pg2=pg2->next)
385 ;
386 if (!pg2)
387 for (pg2=sizes[order].dmafree;
388 (pg2 != NULL) && (pg2->next != page);
389 pg2=pg2->next)
390 ;
391 if (pg2 != NULL)
392 pg2->next = page->next;
393 else
394 printk ("Ooops. page %p doesn't show on freelist.\n", page);
395 }
396
397 free_pages ((long)page, sizes[order].gfporder);
398 }
399 restore_flags(flags);
400
401
402
403
404
405 sizes[order].nfrees++;
406 sizes[order].nbytesmalloced -= size;
407 }