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 extern unsigned long intr_count;
155
156
157 if (intr_count && priority != GFP_ATOMIC) {
158 printk("kmalloc called nonatomically from interrupt %08lx\n",
159 ((unsigned long *)&size)[-1]);
160 priority = GFP_ATOMIC;
161 }
162 if (size > MAX_KMALLOC_K * 1024)
163 {
164 printk ("kmalloc: I refuse to allocate %d bytes (for now max = %d).\n",
165 size,MAX_KMALLOC_K*1024);
166 return (NULL);
167 }
168
169 order = get_order (size);
170 if (order < 0)
171 {
172 printk ("kmalloc of too large a block (%d bytes).\n",size);
173 return (NULL);
174 }
175
176 save_flags(flags);
177
178
179
180 tries = MAX_GET_FREE_PAGE_TRIES;
181 while (tries --)
182 {
183
184 cli ();
185 if ((page = sizes[order].firstfree) &&
186 (p = page->firstfree))
187 {
188 if (p->bh_flags == MF_FREE)
189 {
190 page->firstfree = p->bh_next;
191 page->nfree--;
192 if (!page->nfree)
193 {
194 sizes[order].firstfree = page->next;
195 page->next = NULL;
196 }
197 restore_flags(flags);
198
199 sizes [order].nmallocs++;
200 sizes [order].nbytesmalloced += size;
201 p->bh_flags = MF_USED;
202 p->bh_length = size;
203 return p+1;
204 }
205 printk ("Problem: block on freelist at %08lx isn't free.\n",(long)p);
206 return (NULL);
207 }
208 restore_flags(flags);
209
210
211
212
213 sz = BLOCKSIZE(order);
214
215
216 page = (struct page_descriptor *) __get_free_page (priority & GFP_LEVEL_MASK);
217 if (!page)
218 {
219 printk ("Couldn't get a free page.....\n");
220 return NULL;
221 }
222 #if 0
223 printk ("Got page %08x to use for %d byte mallocs....",(long)page,sz);
224 #endif
225 sizes[order].npages++;
226
227
228 for (i=NBLOCKS(order),p=BH (page+1);i > 1;i--,p=p->bh_next)
229 {
230 p->bh_flags = MF_FREE;
231 p->bh_next = BH ( ((long)p)+sz);
232 }
233
234 p->bh_flags = MF_FREE;
235 p->bh_next = NULL;
236
237 page->order = order;
238 page->nfree = NBLOCKS(order);
239 page->firstfree = BH(page+1);
240 #if 0
241 printk ("%d blocks per page\n",page->nfree);
242 #endif
243
244
245 cli ();
246
247
248
249
250 page->next = sizes[order].firstfree;
251 sizes[order].firstfree = page;
252 restore_flags(flags);
253 }
254
255
256
257 printk ("Hey. This is very funny. I tried %d times to allocate a whole\n"
258 "new page for an object only %d bytes long, but some other process\n"
259 "beat me to actually allocating it. Also note that this 'error'\n"
260 "message is soooo very long to catch your attention. I'd appreciate\n"
261 "it if you'd be so kind as to report what conditions caused this to\n"
262 "the author of this kmalloc: wolff@dutecai.et.tudelft.nl.\n"
263 "(Executive summary: This can't happen)\n",
264 MAX_GET_FREE_PAGE_TRIES,
265 size);
266 return NULL;
267 }
268
269
270 void kfree_s (void *ptr,int size)
271 {
272 unsigned long flags;
273 int order;
274 register struct block_header *p=((struct block_header *)ptr) -1;
275 struct page_descriptor *page,*pg2;
276
277 page = PAGE_DESC (p);
278 order = page->order;
279 if ((order < 0) ||
280 (order > sizeof (sizes)/sizeof (sizes[0])) ||
281 (((long)(page->next)) & ~PAGE_MASK) ||
282 (p->bh_flags != MF_USED))
283 {
284 printk ("kfree of non-kmalloced memory: %p, next= %p, order=%d\n",
285 p, page->next, page->order);
286 return;
287 }
288 if (size &&
289 size != p->bh_length)
290 {
291 printk ("Trying to free pointer at %p with wrong size: %d instead of %lu.\n",
292 p,size,p->bh_length);
293 return;
294 }
295 size = p->bh_length;
296 p->bh_flags = MF_FREE;
297
298 save_flags(flags);
299 cli ();
300 p->bh_next = page->firstfree;
301 page->firstfree = p;
302 page->nfree ++;
303
304 if (page->nfree == 1)
305 {
306 if (page->next)
307 {
308 printk ("Page %p already on freelist dazed and confused....\n", page);
309 }
310 else
311 {
312 page->next = sizes[order].firstfree;
313 sizes[order].firstfree = page;
314 }
315 }
316
317
318 if (page->nfree == NBLOCKS (page->order))
319 {
320 #if 0
321 printk ("Freeing page %08x.\n", (long)page);
322 #endif
323 if (sizes[order].firstfree == page)
324 {
325 sizes[order].firstfree = page->next;
326 }
327 else
328 {
329 for (pg2=sizes[order].firstfree;
330 (pg2 != NULL) && (pg2->next != page);
331 pg2=pg2->next)
332 ;
333 if (pg2 != NULL)
334 pg2->next = page->next;
335 else
336 printk ("Ooops. page %p doesn't show on freelist.\n", page);
337 }
338 free_page ((long)page);
339 }
340 restore_flags(flags);
341
342 sizes[order].nfrees++;
343 sizes[order].nbytesmalloced -= size;
344 }