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
15 #include <linux/mm.h>
16 #include <asm/system.h>
17 #include <linux/delay.h>
18
19 #defineGFP_LEVEL_MASK 0xf
20
21 /* I want this low enough for a while to catch errors. 22 I want this number to be increased in the near future: 23 loadable device drivers should use this function to get memory */ 24
25 #define MAX_KMALLOC_K ((PAGE_SIZE<<(NUM_AREA_ORDERS-1))>>10)
26
27
28 /* This defines how many times we should try to allocate a free page before 29 giving up. Normally this shouldn't happen at all. */ 30 #defineMAX_GET_FREE_PAGE_TRIES 4
31
32
33 /* Private flags. */ 34
35 #defineMF_USED 0xffaa0055
36 #defineMF_FREE 0x0055ffaa
37
38
39 /* 40 * Much care has gone into making these routines in this file reentrant. 41 * 42 * The fancy bookkeeping of nbytesmalloced and the like are only used to 43 * report them to the user (oooohhhhh, aaaaahhhhh....) are not 44 * protected by cli(). (If that goes wrong. So what?) 45 * 46 * These routines restore the interrupt status to allow calling with ints 47 * off. 48 */ 49
50 /* 51 * A block header. This is in front of every malloc-block, whether free or not. 52 */ 53 structblock_header{ 54 unsignedlongbh_flags;
55 union{ 56 unsignedlongubh_length;
57 structblock_header *fbh_next;
58 }vp;
59 };
60
61
62 #definebh_lengthvp.ubh_length 63 #definebh_nextvp.fbh_next 64 #defineBH(p) ((structblock_header *)(p))
65
66
67 /* 68 * The page descriptor is at the front of every page that malloc has in use. 69 */ 70 structpage_descriptor{ 71 structpage_descriptor *next;
72 structblock_header *firstfree;
73 intorder;
74 intnfree;
75 };
76
77
78 #definePAGE_DESC(p) ((structpage_descriptor *)(((unsignedlong)(p)) & PAGE_MASK))
79
80
81 /* 82 * A size descriptor describes a specific class of malloc sizes. 83 * Each class of sizes has its own freelist. 84 */ 85 structsize_descriptor{ 86 structpage_descriptor *firstfree;
87 intsize;
88 intnblocks;
89
90 intnmallocs;
91 intnfrees;
92 intnbytesmalloced;
93 intnpages;
94 unsignedlonggfporder; /* number of pages in the area required */ 95 };
96
97 /* 98 * For now it is unsafe to allocate bucket sizes between n & n=16 where n is 99 * 4096 * any power of two 100 */ 101
102 structsize_descriptorsizes[] = { 103 {NULL, 32,127, 0,0,0,0, 0},
104 {NULL, 64, 63, 0,0,0,0, 0 },
105 {NULL, 128, 31, 0,0,0,0, 0 },
106 {NULL, 252, 16, 0,0,0,0, 0 },
107 {NULL, 508, 8, 0,0,0,0, 0 },
108 {NULL,1020, 4, 0,0,0,0, 0 },
109 {NULL,2040, 2, 0,0,0,0, 0 },
110 {NULL,4096-16, 1, 0,0,0,0, 0 },
111 {NULL,8192-16, 1, 0,0,0,0, 1 },
112 {NULL,16384-16, 1, 0,0,0,0, 2 },
113 {NULL,32768-16, 1, 0,0,0,0, 3 },
114 {NULL,65536-16, 1, 0,0,0,0, 4 },
115 {NULL,131072-16, 1, 0,0,0,0, 5 },
116 {NULL, 0, 0, 0,0,0,0, 0 } 117 };
118
119
120 #defineNBLOCKS(order) (sizes[order].nblocks)
121 #defineBLOCKSIZE(order) (sizes[order].size)
122 #defineAREASIZE(order) (PAGE_SIZE<<(sizes[order].gfporder))
123
124
125 longkmalloc_init (longstart_mem,longend_mem)
/* */ 126 { 127 intorder;
128
129 /* 130 * Check the static info array. Things will blow up terribly if it's 131 * incorrect. This is a late "compile time" check..... 132 */ 133 for (order = 0;BLOCKSIZE(order);order++)
134 { 135 if ((NBLOCKS (order)*BLOCKSIZE(order) + sizeof (structpage_descriptor)) >
136 AREASIZE(order))
137 { 138 printk ("Cannot use %d bytes out of %d in order = %d block mallocs\n",
139 NBLOCKS (order) * BLOCKSIZE(order) +
140 sizeof (structpage_descriptor),
141 (int) AREASIZE(order),
142 BLOCKSIZE (order));
143 panic ("This only happens if someone messes with kmalloc");
144 } 145 } 146 returnstart_mem;
147 } 148
149
150
151 intget_order (intsize)
/* */ 152 { 153 intorder;
154
155 /* Add the size of the header */ 156 size += sizeof (structblock_header);
157 for (order = 0;BLOCKSIZE(order);order++)
158 if (size <= BLOCKSIZE (order))
159 returnorder;
160 return -1;
161 } 162
163 void * kmalloc (size_tsize, intpriority)
/* */ 164 { 165 unsignedlongflags;
166 intorder,tries,i,sz;
167 structblock_header *p;
168 structpage_descriptor *page;
169
170 /* Sanity check... */ 171 if (intr_count && priority != GFP_ATOMIC) { 172 staticintcount = 0;
173 if (++count < 5) { 174 printk("kmalloc called nonatomically from interrupt %08lx\n",
175 ((unsignedlong *)&size)[-1]);
176 priority = GFP_ATOMIC;
177 } 178 } 179
180 order = get_order (size);
181 if (order < 0)
182 { 183 printk ("kmalloc of too large a block (%d bytes).\n",size);
184 return (NULL);
185 } 186
187 save_flags(flags);
188
189 /* It seems VERY unlikely to me that it would be possible that this 190 loop will get executed more than once. */ 191 tries = MAX_GET_FREE_PAGE_TRIES;
192 while (tries --)
193 { 194 /* Try to allocate a "recently" freed memory block */ 195 cli ();
196 if ((page = sizes[order].firstfree) &&
197 (p = page->firstfree))
198 { 199 if (p->bh_flags == MF_FREE)
200 { 201 page->firstfree = p->bh_next;
202 page->nfree--;
203 if (!page->nfree)
204 { 205 sizes[order].firstfree = page->next;
206 page->next = NULL;
207 } 208 restore_flags(flags);
209
210 sizes [order].nmallocs++;
211 sizes [order].nbytesmalloced += size;
212 p->bh_flags = MF_USED; /* As of now this block is officially in use */ 213 p->bh_length = size;
214 returnp+1; /* Pointer arithmetic: increments past header */ 215 } 216 printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
217 return (NULL);
218 } 219 restore_flags(flags);
220
221
222 /* Now we're in trouble: We need to get a new free page..... */ 223
224 sz = BLOCKSIZE(order); /* sz is the size of the blocks we're dealing with */ 225
226 /* This can be done with ints on: This is private to this invocation */ 227 page = (structpage_descriptor *) __get_free_pages (priority & GFP_LEVEL_MASK, sizes[order].gfporder);
228 if (!page) { 229 staticunsignedlonglast = 0;
230 if (last + 10*HZ < jiffies) { 231 last = jiffies;
232 printk ("Couldn't get a free page.....\n");
233 } 234 returnNULL;
235 } 236 #if 0
237 printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
238 #endif 239 sizes[order].npages++;
240
241 /* Loop for all but last block: */ 242 for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next)
243 { 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 page->firstfree = BH(page+1);
254 #if 0
255 printk ("%d blocks per page\n",page->nfree);
256 #endif 257 /* Now we're going to muck with the "global" freelist for this size: 258 this should be uniterruptible */ 259 cli ();
260 /* 261 * sizes[order].firstfree used to be NULL, otherwise we wouldn't be 262 * here, but you never know.... 263 */ 264 page->next = sizes[order].firstfree;
265 sizes[order].firstfree = page;
266 restore_flags(flags);
267 } 268
269 /* Pray that printk won't cause this to happen again :-) */ 270
271 printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
272 "new page for an object only %d bytes long, but some other process\n"
273 "beat me to actually allocating it. Also note that this 'error'\n"
274 "message is soooo very long to catch your attention. I'd appreciate\n"
275 "it if you'd be so kind as to report what conditions caused this to\n"
276 "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
277 "(Executive summary: This can't happen)\n",
278 MAX_GET_FREE_PAGE_TRIES,
279 size);
280 returnNULL;
281 } 282
283
284 voidkfree_s (void *ptr,intsize)
/* */ 285 { 286 unsignedlongflags;
287 intorder;
288 registerstructblock_header *p=((structblock_header *)ptr) -1;
289 structpage_descriptor *page,*pg2;
290
291 page = PAGE_DESC (p);
292 order = page->order;
293 if ((order < 0) ||
294 (order > sizeof (sizes)/sizeof (sizes[0])) ||
295 (((long)(page->next)) & ~PAGE_MASK) ||
296 (p->bh_flags != MF_USED))
297 { 298 printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
299 p, page->next, page->order);
300 return;
301 } 302 if (size &&
303 size != p->bh_length)
304 { 305 printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
306 p,size,p->bh_length);
307 return;
308 } 309 size = p->bh_length;
310 p->bh_flags = MF_FREE; /* As of now this block is officially free */ 311 save_flags(flags);
312 cli ();
313 p->bh_next = page->firstfree;
314 page->firstfree = p;
315 page->nfree ++;
316
317 if (page->nfree == 1)
318 {/* Page went from full to one free block: put it on the freelist */ 319 if (page->next)
320 { 321 printk ("Page %p already on freelist dazed and confused....\n", page);
322 } 323 else 324 { 325 page->next = sizes[order].firstfree;
326 sizes[order].firstfree = page;
327 } 328 } 329
330 /* If page is completely free, free it */ 331 if (page->nfree == NBLOCKS (page->order))
332 { 333 #if 0
334 printk ("Freeing page %08x.\n", (long)page);
335 #endif 336 if (sizes[order].firstfree == page)
337 { 338 sizes[order].firstfree = page->next;
339 } 340 else 341 { 342 for (pg2=sizes[order].firstfree;
343 (pg2 != NULL) && (pg2->next != page);
344 pg2=pg2->next)
345 /* Nothing */;
346 if (pg2 != NULL)
347 pg2->next = page->next;
348 else 349 printk ("Ooops. page %p doesn't show on freelist.\n", page);
350 } 351 /* FIXME: I'm sure we should do something with npages here (like npages--) */ 352 free_pages ((long)page, sizes[order].gfporder);
353 } 354 restore_flags(flags);
355
356 /* FIXME: ?? Are these increment & decrement operations guaranteed to be 357 * atomic? Could an IRQ not occur between the read & the write? 358 * Maybe yes on a x86 with GCC...?? 359 */ 360 sizes[order].nfrees++; /* Noncritical (monitoring) admin stuff */ 361 sizes[order].nbytesmalloced -= size;
362 }