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