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