![[first]](../icons/first.png){kind=icon}
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
1 /*
2 * malloc.c --- a general purpose kernel memory allocator for Linux.
3 *
4 * Written by Theodore Ts'o (tytso@mit.edu), 11/29/91
5 *
6 * This routine is written to be as fast as possible, so that it
7 * can be called from the interrupt level.
8 *
9 * Limitations: maximum size of memory we can allocate using this routine
10 * is 4k, the size of a page in Linux.
11 *
12 * The general game plan is that each page (called a bucket) will only hold
13 * objects of a given size. When all of the object on a page are released,
14 * the page can be returned to the general free pool. When kmalloc() is
15 * called, it looks for the smallest bucket size which will fulfill its
16 * request, and allocate a piece of memory from that bucket pool.
17 *
18 * Each bucket has as its control block a bucket descriptor which keeps
19 * track of how many objects are in use on that page, and the free list
20 * for that page. Like the buckets themselves, bucket descriptors are
21 * stored on pages requested from get_free_page(). However, unlike buckets,
22 * pages devoted to bucket descriptor pages are never released back to the
23 * system. Fortunately, a system should probably only need 1 or 2 bucket
24 * descriptor pages, since a page can hold 256 bucket descriptors (which
25 * corresponds to 1 megabyte worth of bucket pages.) If the kernel is using
26 * that much allocated memory, it's probably doing something wrong. :-)
27 *
28 * Note: kmalloc() and kfree() both call get_free_page() and free_page()
29 * in sections of code where interrupts are turned off, to allow
30 * kmalloc() and kfree() to be safely called from an interrupt routine.
31 * (We will probably need this functionality when networking code,
32 * particularily things like NFS, is added to Linux.) However, this
33 * presumes that get_free_page() and free_page() are interrupt-level
34 * safe, which they may not be once paging is added. If this is the
35 * case, we will need to modify kmalloc() to keep a few unused pages
36 * "pre-allocated" so that it can safely draw upon those pages if
37 * it is called from an interrupt routine.
38 *
39 * Another concern is that get_free_page() should not sleep; if it
40 * does, the code is carefully ordered so as to avoid any race
41 * conditions. The catch is that if kmalloc() is called re-entrantly,
42 * there is a chance that unecessary pages will be grabbed from the
43 * system. Except for the pages for the bucket descriptor page, the
44 * extra pages will eventually get released back to the system, though,
45 * so it isn't all that bad.
46 */
47
48 /* I'm going to modify it to keep some free pages around. Get free page
49 can sleep, and tcp/ip needs to call kmalloc at interrupt time (Or keep
50 big buffers around for itself.) I guess I'll have return from
51 syscall fill up the free page descriptors. -RAB */
52
53 /* since the advent of GFP_ATOMIC, I've changed the kmalloc code to
54 use it and return NULL if it can't get a page. -RAB */
55 /* (mostly just undid the previous changes -RAB) */
56
57 /* I've added the priority argument to kmalloc so routines can
58 sleep on memory if they want. - RAB */
59
60 /* I've also got to make sure that kmalloc is reentrant now. */
61
62 /* Debugging support: add file/line info, add beginning+end markers. -M.U- */
63
64 #include <linux/kernel.h>
65 #include <linux/mm.h>
66 #include <linux/string.h>
67
68 #include <asm/system.h>
69
70 struct bucket_desc { /* 16 bytes */
71 void *page;
72 struct bucket_desc *next;
73 void *freeptr;
74 unsigned short refcnt;
75 unsigned short bucket_size;
76 };
77
78 struct _bucket_dir { /* 8 bytes */
79 unsigned int size;
80 struct bucket_desc *chain;
81 };
82
83 #ifdef CONFIG_DEBUG_MALLOC
84
85 struct hdr_start {
86 const char *file;
87 const char *ok_file;
88 unsigned short line;
89 unsigned short ok_line;
90 unsigned short size;
91 int magic;
92 };
93 struct hdr_end {
94 int magic;
95 };
96
97 #define DEB_MAGIC_FREE 0x13579BDF /* free block */
98 #define DEB_MAGIC_ALLOC 0x2468ACE0 /* allocated block */
99 #define DEB_MAGIC_USED 0x147AD036 /* allocated but bad */
100 #define DEB_MAGIC_FREED 0x258BE169 /* free but abused */
101
102 #define DEB_MAGIC_END 0x369CF258 /* end marker */
103
104 #endif
105 /*
106 * The following is the where we store a pointer to the first bucket
107 * descriptor for a given size.
108 *
109 * If it turns out that the Linux kernel allocates a lot of objects of a
110 * specific size, then we may want to add that specific size to this list,
111 * since that will allow the memory to be allocated more efficiently.
112 * However, since an entire page must be dedicated to each specific size
113 * on this list, some amount of temperance must be exercised here.
114 *
115 * Note that this list *must* be kept in order.
116 */
117 struct _bucket_dir bucket_dir[] = {
118 #ifndef CONFIG_DEBUG_MALLOC /* Debug headers have too much overhead */
119 { 16, (struct bucket_desc *) 0},
120 #endif
121 { 32, (struct bucket_desc *) 0},
122 { 64, (struct bucket_desc *) 0},
123 { 128, (struct bucket_desc *) 0},
124 { 256, (struct bucket_desc *) 0},
125 { 512, (struct bucket_desc *) 0},
126 { 1024, (struct bucket_desc *) 0},
127 { 2048, (struct bucket_desc *) 0},
128 { 4096, (struct bucket_desc *) 0},
129 { 0, (struct bucket_desc *) 0}}; /* End of list marker */
130
131 /*
132 * This contains a linked list of free bucket descriptor blocks
133 */
134 static struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
135
136 /*
137 * This routine initializes a bucket description page.
138 */
139
140 /* It assumes it is called with interrupts on. and will
141 return that way. It also can sleep if priority != GFP_ATOMIC. */
142
143 static inline void init_bucket_desc(unsigned long page)
/* ![[next]](../icons/right.png)
![[first]](../icons/n_first.png)
![[top]](../icons/top.png)
*/
144 {
145 struct bucket_desc *bdesc;
146 int i;
147
148 bdesc = (struct bucket_desc *) page;
149 for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
150 bdesc->next = bdesc+1;
151 bdesc++;
152 }
153 /*
154 * This is done last, to avoid race conditions in case
155 * get_free_page() sleeps and this routine gets called again....
156 */
157 cli();
158 bdesc->next = free_bucket_desc;
159 free_bucket_desc = (struct bucket_desc *) page;
160 }
161
162 /*
163 * Re-organized some code to give cleaner assembly output for easier
164 * verification.. LBT
165 */
166 #ifdef CONFIG_DEBUG_MALLOC
167 void *
168 deb_kmalloc(const char *deb_file, unsigned short deb_line,
/* ![[previous]](../icons/left.png)
*/
169 unsigned int len, int priority)
170 #else
171 void *
172 kmalloc(unsigned int len, int priority)
173 #endif
174 {
175 int i;
176 unsigned long flags;
177 unsigned long page;
178 struct _bucket_dir *bdir;
179 struct bucket_desc *bdesc;
180 void *retval;
181
182 #ifdef CONFIG_DEBUG_MALLOC
183 len += sizeof(struct hdr_start)+sizeof(struct hdr_end);
184 #endif
185 /*
186 * First we search the bucket_dir to find the right bucket change
187 * for this request.
188 */
189
190 /* The sizes are static so there is no reentry problem here. */
191 bdir = bucket_dir;
192 for (bdir = bucket_dir ; bdir->size < len ; bdir++) {
193 if (!bdir->size)
194 goto too_large;
195 }
196
197 /*
198 * Now we search for a bucket descriptor which has free space
199 */
200 save_flags(flags);
201 cli(); /* Avoid race conditions */
202 for (bdesc = bdir->chain; bdesc != NULL; bdesc = bdesc->next)
203 if (bdesc->freeptr)
204 goto found_bdesc;
205 /*
206 * If we didn't find a bucket with free space, then we'll
207 * allocate a new one.
208 */
209
210 /*
211 * Note that init_bucket_descriptor() does its
212 * own cli() before returning, and guarantees that
213 * there is a bucket desc in the page.
214 */
215 if (!free_bucket_desc) {
216 restore_flags(flags);
217 page = get_free_page(priority);
218 if (!page)
219 return NULL;
220 init_bucket_desc(page);
221 }
222
223 bdesc = free_bucket_desc;
224 free_bucket_desc = bdesc->next;
225 restore_flags(flags);
226
227 page = get_free_page(priority);
228
229 /*
230 * Out of memory? Put the bucket descriptor back on the free list
231 */
232 if (!page) {
233 cli();
234 bdesc->next = free_bucket_desc;
235 free_bucket_desc = bdesc;
236 restore_flags(flags);
237 return NULL;
238 }
239
240 bdesc->refcnt = 0;
241 bdesc->bucket_size = bdir->size;
242 bdesc->page = bdesc->freeptr = (void *) page;
243
244 /* Set up the chain of free objects */
245 for (i=PAGE_SIZE/bdir->size; i > 0 ; i--) {
246 #ifdef CONFIG_DEBUG_MALLOC
247 struct hdr_start *hd;
248 struct hdr_end *he;
249 hd = (struct hdr_start *) page;
250 he = (struct hdr_end *)(page+(bdir->size-sizeof(struct hdr_end)));
251 hd->magic = DEB_MAGIC_FREE;
252 hd->file = hd->ok_file = "(expand)";
253 hd->line = hd->ok_line = 0;
254 hd->size = bdir->size-sizeof(struct hdr_start)-sizeof(struct hdr_end);
255 he->magic = DEB_MAGIC_END;
256
257 memset(hd+1,0xF8,hd->size);
258
259 *((void **) (hd+1)) = (i==1) ? NULL : (void *)(page + bdir->size);
260 #else
261 *((void **) page) = (i==1) ? NULL : (void *)(page + bdir->size);
262 #endif
263 page += bdir->size;
264 }
265
266 /* turn interrupts back off for putting the
267 thing onto the chain. */
268 cli();
269 /* remember bdir is not changed. */
270 bdesc->next = bdir->chain; /* OK, link it in! */
271 bdir->chain = bdesc;
272
273 found_bdesc:
274 retval = (void *) bdesc->freeptr;
275 #ifdef CONFIG_DEBUG_MALLOC
276 bdesc->freeptr = *((void **) (((char *)retval)+sizeof(struct hdr_start)));
277 #else
278 bdesc->freeptr = *((void **) retval);
279 #endif
280 bdesc->refcnt++;
281 restore_flags(flags); /* OK, we're safe again */
282 #ifdef CONFIG_DEBUG_MALLOC
283 {
284 struct hdr_start *hd;
285 struct hdr_end *he;
286
287 hd = (struct hdr_start *) retval;
288 retval = hd+1;
289 len -= sizeof(struct hdr_start)+sizeof(struct hdr_end);
290 if(hd->magic != DEB_MAGIC_FREE && hd->magic != DEB_MAGIC_FREED) {
291 printk("DEB_MALLOC allocating %s block 0x%x (head 0x%x) from %s:%d, magic %x\n",
292 (hd->magic == DEB_MAGIC_ALLOC) ? "nonfree" : "trashed",
293 retval,hd,deb_file,deb_line,hd->magic);
294 return NULL;
295 }
296 if(len > hd->size || len > bdir->size-sizeof(struct hdr_start)-sizeof(struct hdr_end)) {
297 printk("DEB_MALLOC got %x:%x-byte block, wanted %x, from %s:%d, last %s:%d\n",
298 hd->size,bdir->size,len,hd->file,hd->line,deb_file,deb_line);
299 return NULL;
300 }
301 {
302 unsigned char *x = (unsigned char *) retval;
303 unsigned short pos = 4;
304 x += pos;
305 while(pos < hd->size) {
306 if(*x++ != 0xF8) {
307 printk("DEB_MALLOC used 0x%x:%x(%x) while free, from %s:%d\n",
308 retval,pos,hd->size,hd->file,hd->line);
309 return NULL;
310 }
311 pos++;
312 }
313 }
314 he = (struct hdr_end *)(((char *)retval)+hd->size);
315 if(he->magic != DEB_MAGIC_END) {
316 printk("DEB_MALLOC overran 0x%x:%d while free, from %s:%d\n",retval,hd->size,hd->file,hd->line);
317 }
318 memset(retval, 0xf0, len);
319 he = (struct hdr_end *)(((char *)retval)+len);
320 hd->file = hd->ok_file = deb_file;
321 hd->line = hd->ok_line = deb_line;
322 hd->size = len;
323 hd->magic = DEB_MAGIC_ALLOC;
324 he->magic = DEB_MAGIC_END;
325 }
326 #endif
327 return retval;
328
329 too_large:
330 /* This should be changed for sizes > 1 page. */
331 printk("kmalloc called with impossibly large argument (%d)\n", len);
332 return NULL;
333 }
334
335 #ifdef CONFIG_DEBUG_MALLOC
336 void deb_kcheck_s(const char *deb_file, unsigned short deb_line,
/* */
337 void *obj, int size)
338 {
339 struct hdr_start *hd;
340 struct hdr_end *he;
341
342 if (!obj)
343 return;
344 hd = (struct hdr_start *) obj;
345 hd--;
346
347 if(hd->magic != DEB_MAGIC_ALLOC) {
348 if(hd->magic != DEB_MAGIC_USED && hd->magic != DEB_MAGIC_FREED)
349 printk("DEB_MALLOC Using %s block of 0x%x from %s:%d, by %s:%d, last %s:%d\n",
350 (hd->magic == DEB_MAGIC_FREE)?"free":"bad",obj,deb_file,deb_line,hd->file,hd->line,hd->ok_file,hd->ok_line);
351 if(hd->magic == DEB_MAGIC_FREE)
352 hd->magic = DEB_MAGIC_FREED;
353 return;
354 }
355 if(hd->size != size) {
356 if(size != 0) {
357 printk("DEB_MALLOC size for 0x%x given as %d, stored %d, from %s:%d, last %s:%d\n",
358 obj,size,hd->size,deb_file,deb_line,hd->ok_file,hd->ok_line);
359 }
360 size = hd->size;
361 }
362 he = (struct hdr_end *)(((char *)obj)+size);
363 if(he->magic != DEB_MAGIC_END) {
364 printk("DEB_MALLOC overran block 0x%x:%d, free at %s:%d\n",obj,hd->size,deb_file,deb_line);
365 hd->magic = DEB_MAGIC_USED;
366 return;
367 }
368 hd->ok_file = deb_file;
369 hd->ok_line = deb_line;
370 }
371 #endif
372
373 /*
374 * Here is the kfree routine. If you know the size of the object that you
375 * are freeing, then kfree_s() will use that information to speed up the
376 * search for the bucket descriptor.
377 *
378 * We will #define a macro so that "kfree(x)" is becomes "kfree_s(x, 0)"
379 */
380 #ifdef CONFIG_DEBUG_MALLOC
381 void deb_kfree_s(const char *deb_file, unsigned short deb_line,
/* */
382 void *obj, int size)
383 #else
384 void kfree_s(void *obj, int size)
385 #endif
386 {
387 unsigned long flags;
388 void *page;
389 struct _bucket_dir *bdir;
390 struct bucket_desc *bdesc, *prev;
391
392 if (!obj)
393 return;
394 #ifdef CONFIG_DEBUG_MALLOC
395 {
396 struct hdr_start *hd;
397 struct hdr_end *he;
398 hd = (struct hdr_start *) obj;
399 hd--;
400
401 if(hd->magic != DEB_MAGIC_ALLOC && hd->magic != DEB_MAGIC_USED) {
402 if(hd->magic != DEB_MAGIC_FREED)
403 printk("DEB_MALLOC %s free of 0x%x from %s:%d by %s:%d, last %s:%d\n",
404 (hd->magic == DEB_MAGIC_FREE)?"dup":"bad",
405 obj,deb_file,deb_line,hd->file,hd->line,hd->ok_file,hd->ok_line);
406 return;
407 }
408 if(hd->size != size) {
409 if(size != 0) {
410 if(hd->magic != DEB_MAGIC_USED)
411 printk("DEB_MALLOC size for 0x%x given as %d, stored %d, from %s:%d, last %s:%d\n",
412 obj,size,hd->size,deb_file,deb_line,hd->ok_file,hd->ok_line);
413 }
414 size = hd->size;
415 }
416 he = (struct hdr_end *)(((char *)obj)+size);
417 if(he->magic != DEB_MAGIC_END) {
418 if(hd->magic != DEB_MAGIC_USED)
419 printk("DEB_MALLOC overran block 0x%x:%d, free at %s:%d, last %s:%d\n",
420 obj,hd->size,deb_file,deb_line,hd->ok_file,hd->ok_line);
421 return;
422 }
423 size += sizeof(struct hdr_start)+sizeof(struct hdr_end);
424 }
425 #endif
426 save_flags(flags);
427 /* Calculate what page this object lives in */
428 page = (void *) ((unsigned long) obj & 0xfffff000);
429
430 /* Now search the buckets looking for that page */
431 for (bdir = bucket_dir; bdir->size; bdir++) {
432 prev = 0;
433 /* If size is zero then this conditional is always true */
434 if (bdir->size >= size) {
435 /* We have to turn off interrupts here because
436 we are descending the chain. If something
437 changes it in the middle we could suddenly
438 find ourselves descending the free list.
439 I think this would only cause a memory
440 leak, but better safe than sorry. */
441 cli(); /* To avoid race conditions */
442 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
443 if (bdesc->page == page)
444 goto found;
445 prev = bdesc;
446 }
447 }
448 }
449
450 restore_flags(flags);
451 printk("Bad address passed to kernel kfree_s(%X, %d)\n",obj, size);
452 #ifdef CONFIG_DEBUG_MALLOC
453 printk("Offending code: %s:%d\n",deb_file,deb_line);
454 #else
455 printk("Offending eip: %08x\n",((unsigned long *) &obj)[-1]);
456 #endif
457 return;
458
459 found:
460 /* interrupts are off here. */
461 #ifdef CONFIG_DEBUG_MALLOC
462
463 {
464 struct hdr_start *hd;
465 struct hdr_end *he;
466 hd = (struct hdr_start *) obj;
467 hd--;
468
469 hd->file = deb_file;
470 hd->line = deb_line;
471 hd->magic = DEB_MAGIC_FREE;
472 hd->size = bdir->size-sizeof(struct hdr_start)-sizeof(struct hdr_end);
473 he = (struct hdr_end *)(((char *)obj)+hd->size);
474 memset(obj, 0xf8, hd->size);
475 he->magic = DEB_MAGIC_END;
476 *((void **)obj) = bdesc->freeptr;
477 obj = hd;
478 }
479 #else
480 *((void **)obj) = bdesc->freeptr;
481 #endif
482
483 bdesc->freeptr = obj;
484 bdesc->refcnt--;
485 if (bdesc->refcnt == 0) {
486 /*
487 * We need to make sure that prev is still accurate. It
488 * may not be, if someone rudely interrupted us....
489 */
490 if ((prev && (prev->next != bdesc)) ||
491 (!prev && (bdir->chain != bdesc)))
492 for (prev = bdir->chain; prev; prev = prev->next)
493 if (prev->next == bdesc)
494 break;
495 if (prev)
496 prev->next = bdesc->next;
497 else {
498 if (bdir->chain != bdesc)
499 panic("kmalloc bucket chains corrupted");
500 bdir->chain = bdesc->next;
501 }
502 bdesc->next = free_bucket_desc;
503 free_bucket_desc = bdesc;
504 free_page((unsigned long) bdesc->page);
505 }
506 restore_flags(flags);
507 return;
508 }
509
510 #ifdef CONFIG_DEBUG_MALLOC
511 int get_malloc(char *buffer)
/* ![[last]](../icons/n_last.png)
*/
512 {
513 int len = 0;
514 int i;
515 unsigned long flags;
516 void *page;
517 struct _bucket_dir *bdir;
518 struct bucket_desc *bdesc;
519
520 save_flags(flags);
521 cli(); /* To avoid race conditions */
522 for (bdir = bucket_dir; bdir->size; bdir++) {
523 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
524 page = bdesc->page;
525 for (i=PAGE_SIZE/bdir->size; i > 0 ; i--) {
526 struct hdr_start *hd;
527 hd = (struct hdr_start *)page;
528 if(hd->magic == DEB_MAGIC_ALLOC) {
529 if(len > PAGE_SIZE-80) {
530 restore_flags(flags);
531 len += sprintf(buffer+len,"+++\n");
532 return len;
533 }
534 len += sprintf(buffer+len,"%08x:%03x %s:%d %s:%d\n",
535 (long)(page+sizeof(struct hdr_start)),hd->size,hd->file,hd->line,hd->ok_file,hd->ok_line);
536 }
537 page += bdir->size;
538 }
539 }
540 }
541
542 restore_flags(flags);
543 return len;
544 }
545 #endif
![[bottom]](../icons/n_bottom.png){kind=icon}
*/