]>
Commit | Line | Data |
---|---|---|
10cef602 MM |
1 | /* |
2 | * SLOB Allocator: Simple List Of Blocks | |
3 | * | |
4 | * Matt Mackall <mpm@selenic.com> 12/30/03 | |
5 | * | |
6 | * How SLOB works: | |
7 | * | |
8 | * The core of SLOB is a traditional K&R style heap allocator, with | |
9 | * support for returning aligned objects. The granularity of this | |
10 | * allocator is 8 bytes on x86, though it's perhaps possible to reduce | |
11 | * this to 4 if it's deemed worth the effort. The slob heap is a | |
12 | * singly-linked list of pages from __get_free_page, grown on demand | |
13 | * and allocation from the heap is currently first-fit. | |
14 | * | |
15 | * Above this is an implementation of kmalloc/kfree. Blocks returned | |
16 | * from kmalloc are 8-byte aligned and prepended with a 8-byte header. | |
17 | * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls | |
18 | * __get_free_pages directly so that it can return page-aligned blocks | |
19 | * and keeps a linked list of such pages and their orders. These | |
20 | * objects are detected in kfree() by their page alignment. | |
21 | * | |
22 | * SLAB is emulated on top of SLOB by simply calling constructors and | |
23 | * destructors for every SLAB allocation. Objects are returned with | |
5af60839 | 24 | * the 8-byte alignment unless the SLAB_HWCACHE_ALIGN flag is |
10cef602 MM |
25 | * set, in which case the low-level allocator will fragment blocks to |
26 | * create the proper alignment. Again, objects of page-size or greater | |
27 | * are allocated by calling __get_free_pages. As SLAB objects know | |
28 | * their size, no separate size bookkeeping is necessary and there is | |
29 | * essentially no allocation space overhead. | |
30 | */ | |
31 | ||
10cef602 MM |
32 | #include <linux/slab.h> |
33 | #include <linux/mm.h> | |
34 | #include <linux/cache.h> | |
35 | #include <linux/init.h> | |
36 | #include <linux/module.h> | |
37 | #include <linux/timer.h> | |
38 | ||
39 | struct slob_block { | |
40 | int units; | |
41 | struct slob_block *next; | |
42 | }; | |
43 | typedef struct slob_block slob_t; | |
44 | ||
45 | #define SLOB_UNIT sizeof(slob_t) | |
46 | #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT) | |
47 | #define SLOB_ALIGN L1_CACHE_BYTES | |
48 | ||
49 | struct bigblock { | |
50 | int order; | |
51 | void *pages; | |
52 | struct bigblock *next; | |
53 | }; | |
54 | typedef struct bigblock bigblock_t; | |
55 | ||
56 | static slob_t arena = { .next = &arena, .units = 1 }; | |
57 | static slob_t *slobfree = &arena; | |
58 | static bigblock_t *bigblocks; | |
59 | static DEFINE_SPINLOCK(slob_lock); | |
60 | static DEFINE_SPINLOCK(block_lock); | |
61 | ||
62 | static void slob_free(void *b, int size); | |
bcb4ddb4 DG |
63 | static void slob_timer_cbk(void); |
64 | ||
10cef602 MM |
65 | |
66 | static void *slob_alloc(size_t size, gfp_t gfp, int align) | |
67 | { | |
68 | slob_t *prev, *cur, *aligned = 0; | |
69 | int delta = 0, units = SLOB_UNITS(size); | |
70 | unsigned long flags; | |
71 | ||
72 | spin_lock_irqsave(&slob_lock, flags); | |
73 | prev = slobfree; | |
74 | for (cur = prev->next; ; prev = cur, cur = cur->next) { | |
75 | if (align) { | |
76 | aligned = (slob_t *)ALIGN((unsigned long)cur, align); | |
77 | delta = aligned - cur; | |
78 | } | |
79 | if (cur->units >= units + delta) { /* room enough? */ | |
80 | if (delta) { /* need to fragment head to align? */ | |
81 | aligned->units = cur->units - delta; | |
82 | aligned->next = cur->next; | |
83 | cur->next = aligned; | |
84 | cur->units = delta; | |
85 | prev = cur; | |
86 | cur = aligned; | |
87 | } | |
88 | ||
89 | if (cur->units == units) /* exact fit? */ | |
90 | prev->next = cur->next; /* unlink */ | |
91 | else { /* fragment */ | |
92 | prev->next = cur + units; | |
93 | prev->next->units = cur->units - units; | |
94 | prev->next->next = cur->next; | |
95 | cur->units = units; | |
96 | } | |
97 | ||
98 | slobfree = prev; | |
99 | spin_unlock_irqrestore(&slob_lock, flags); | |
100 | return cur; | |
101 | } | |
102 | if (cur == slobfree) { | |
103 | spin_unlock_irqrestore(&slob_lock, flags); | |
104 | ||
105 | if (size == PAGE_SIZE) /* trying to shrink arena? */ | |
106 | return 0; | |
107 | ||
108 | cur = (slob_t *)__get_free_page(gfp); | |
109 | if (!cur) | |
110 | return 0; | |
111 | ||
112 | slob_free(cur, PAGE_SIZE); | |
113 | spin_lock_irqsave(&slob_lock, flags); | |
114 | cur = slobfree; | |
115 | } | |
116 | } | |
117 | } | |
118 | ||
119 | static void slob_free(void *block, int size) | |
120 | { | |
121 | slob_t *cur, *b = (slob_t *)block; | |
122 | unsigned long flags; | |
123 | ||
124 | if (!block) | |
125 | return; | |
126 | ||
127 | if (size) | |
128 | b->units = SLOB_UNITS(size); | |
129 | ||
130 | /* Find reinsertion point */ | |
131 | spin_lock_irqsave(&slob_lock, flags); | |
132 | for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next) | |
133 | if (cur >= cur->next && (b > cur || b < cur->next)) | |
134 | break; | |
135 | ||
136 | if (b + b->units == cur->next) { | |
137 | b->units += cur->next->units; | |
138 | b->next = cur->next->next; | |
139 | } else | |
140 | b->next = cur->next; | |
141 | ||
142 | if (cur + cur->units == b) { | |
143 | cur->units += b->units; | |
144 | cur->next = b->next; | |
145 | } else | |
146 | cur->next = b; | |
147 | ||
148 | slobfree = cur; | |
149 | ||
150 | spin_unlock_irqrestore(&slob_lock, flags); | |
151 | } | |
152 | ||
153 | static int FASTCALL(find_order(int size)); | |
154 | static int fastcall find_order(int size) | |
155 | { | |
156 | int order = 0; | |
157 | for ( ; size > 4096 ; size >>=1) | |
158 | order++; | |
159 | return order; | |
160 | } | |
161 | ||
2e892f43 | 162 | void *__kmalloc(size_t size, gfp_t gfp) |
10cef602 MM |
163 | { |
164 | slob_t *m; | |
165 | bigblock_t *bb; | |
166 | unsigned long flags; | |
167 | ||
168 | if (size < PAGE_SIZE - SLOB_UNIT) { | |
169 | m = slob_alloc(size + SLOB_UNIT, gfp, 0); | |
170 | return m ? (void *)(m + 1) : 0; | |
171 | } | |
172 | ||
173 | bb = slob_alloc(sizeof(bigblock_t), gfp, 0); | |
174 | if (!bb) | |
175 | return 0; | |
176 | ||
177 | bb->order = find_order(size); | |
178 | bb->pages = (void *)__get_free_pages(gfp, bb->order); | |
179 | ||
180 | if (bb->pages) { | |
181 | spin_lock_irqsave(&block_lock, flags); | |
182 | bb->next = bigblocks; | |
183 | bigblocks = bb; | |
184 | spin_unlock_irqrestore(&block_lock, flags); | |
185 | return bb->pages; | |
186 | } | |
187 | ||
188 | slob_free(bb, sizeof(bigblock_t)); | |
189 | return 0; | |
190 | } | |
2e892f43 | 191 | EXPORT_SYMBOL(__kmalloc); |
10cef602 | 192 | |
fd76bab2 PE |
193 | /** |
194 | * krealloc - reallocate memory. The contents will remain unchanged. | |
195 | * | |
196 | * @p: object to reallocate memory for. | |
197 | * @new_size: how many bytes of memory are required. | |
198 | * @flags: the type of memory to allocate. | |
199 | * | |
200 | * The contents of the object pointed to are preserved up to the | |
201 | * lesser of the new and old sizes. If @p is %NULL, krealloc() | |
202 | * behaves exactly like kmalloc(). If @size is 0 and @p is not a | |
203 | * %NULL pointer, the object pointed to is freed. | |
204 | */ | |
205 | void *krealloc(const void *p, size_t new_size, gfp_t flags) | |
206 | { | |
207 | void *ret; | |
208 | ||
209 | if (unlikely(!p)) | |
210 | return kmalloc_track_caller(new_size, flags); | |
211 | ||
212 | if (unlikely(!new_size)) { | |
213 | kfree(p); | |
214 | return NULL; | |
215 | } | |
216 | ||
217 | ret = kmalloc_track_caller(new_size, flags); | |
218 | if (ret) { | |
219 | memcpy(ret, p, min(new_size, ksize(p))); | |
220 | kfree(p); | |
221 | } | |
222 | return ret; | |
223 | } | |
224 | EXPORT_SYMBOL(krealloc); | |
225 | ||
10cef602 MM |
226 | void kfree(const void *block) |
227 | { | |
228 | bigblock_t *bb, **last = &bigblocks; | |
229 | unsigned long flags; | |
230 | ||
231 | if (!block) | |
232 | return; | |
233 | ||
234 | if (!((unsigned long)block & (PAGE_SIZE-1))) { | |
235 | /* might be on the big block list */ | |
236 | spin_lock_irqsave(&block_lock, flags); | |
237 | for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) { | |
238 | if (bb->pages == block) { | |
239 | *last = bb->next; | |
240 | spin_unlock_irqrestore(&block_lock, flags); | |
241 | free_pages((unsigned long)block, bb->order); | |
242 | slob_free(bb, sizeof(bigblock_t)); | |
243 | return; | |
244 | } | |
245 | } | |
246 | spin_unlock_irqrestore(&block_lock, flags); | |
247 | } | |
248 | ||
249 | slob_free((slob_t *)block - 1, 0); | |
250 | return; | |
251 | } | |
252 | ||
253 | EXPORT_SYMBOL(kfree); | |
254 | ||
fd76bab2 | 255 | size_t ksize(const void *block) |
10cef602 MM |
256 | { |
257 | bigblock_t *bb; | |
258 | unsigned long flags; | |
259 | ||
260 | if (!block) | |
261 | return 0; | |
262 | ||
263 | if (!((unsigned long)block & (PAGE_SIZE-1))) { | |
264 | spin_lock_irqsave(&block_lock, flags); | |
265 | for (bb = bigblocks; bb; bb = bb->next) | |
266 | if (bb->pages == block) { | |
267 | spin_unlock_irqrestore(&slob_lock, flags); | |
268 | return PAGE_SIZE << bb->order; | |
269 | } | |
270 | spin_unlock_irqrestore(&block_lock, flags); | |
271 | } | |
272 | ||
273 | return ((slob_t *)block - 1)->units * SLOB_UNIT; | |
274 | } | |
275 | ||
276 | struct kmem_cache { | |
277 | unsigned int size, align; | |
278 | const char *name; | |
279 | void (*ctor)(void *, struct kmem_cache *, unsigned long); | |
280 | void (*dtor)(void *, struct kmem_cache *, unsigned long); | |
281 | }; | |
282 | ||
283 | struct kmem_cache *kmem_cache_create(const char *name, size_t size, | |
284 | size_t align, unsigned long flags, | |
285 | void (*ctor)(void*, struct kmem_cache *, unsigned long), | |
286 | void (*dtor)(void*, struct kmem_cache *, unsigned long)) | |
287 | { | |
288 | struct kmem_cache *c; | |
289 | ||
290 | c = slob_alloc(sizeof(struct kmem_cache), flags, 0); | |
291 | ||
292 | if (c) { | |
293 | c->name = name; | |
294 | c->size = size; | |
295 | c->ctor = ctor; | |
296 | c->dtor = dtor; | |
297 | /* ignore alignment unless it's forced */ | |
5af60839 | 298 | c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0; |
10cef602 MM |
299 | if (c->align < align) |
300 | c->align = align; | |
bc0055ae AM |
301 | } else if (flags & SLAB_PANIC) |
302 | panic("Cannot create slab cache %s\n", name); | |
10cef602 MM |
303 | |
304 | return c; | |
305 | } | |
306 | EXPORT_SYMBOL(kmem_cache_create); | |
307 | ||
133d205a | 308 | void kmem_cache_destroy(struct kmem_cache *c) |
10cef602 MM |
309 | { |
310 | slob_free(c, sizeof(struct kmem_cache)); | |
10cef602 MM |
311 | } |
312 | EXPORT_SYMBOL(kmem_cache_destroy); | |
313 | ||
314 | void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags) | |
315 | { | |
316 | void *b; | |
317 | ||
318 | if (c->size < PAGE_SIZE) | |
319 | b = slob_alloc(c->size, flags, c->align); | |
320 | else | |
321 | b = (void *)__get_free_pages(flags, find_order(c->size)); | |
322 | ||
323 | if (c->ctor) | |
324 | c->ctor(b, c, SLAB_CTOR_CONSTRUCTOR); | |
325 | ||
326 | return b; | |
327 | } | |
328 | EXPORT_SYMBOL(kmem_cache_alloc); | |
329 | ||
a8c0f9a4 PE |
330 | void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags) |
331 | { | |
332 | void *ret = kmem_cache_alloc(c, flags); | |
333 | if (ret) | |
334 | memset(ret, 0, c->size); | |
335 | ||
336 | return ret; | |
337 | } | |
338 | EXPORT_SYMBOL(kmem_cache_zalloc); | |
339 | ||
10cef602 MM |
340 | void kmem_cache_free(struct kmem_cache *c, void *b) |
341 | { | |
342 | if (c->dtor) | |
343 | c->dtor(b, c, 0); | |
344 | ||
345 | if (c->size < PAGE_SIZE) | |
346 | slob_free(b, c->size); | |
347 | else | |
348 | free_pages((unsigned long)b, find_order(c->size)); | |
349 | } | |
350 | EXPORT_SYMBOL(kmem_cache_free); | |
351 | ||
352 | unsigned int kmem_cache_size(struct kmem_cache *c) | |
353 | { | |
354 | return c->size; | |
355 | } | |
356 | EXPORT_SYMBOL(kmem_cache_size); | |
357 | ||
358 | const char *kmem_cache_name(struct kmem_cache *c) | |
359 | { | |
360 | return c->name; | |
361 | } | |
362 | EXPORT_SYMBOL(kmem_cache_name); | |
363 | ||
364 | static struct timer_list slob_timer = TIMER_INITIALIZER( | |
bcb4ddb4 | 365 | (void (*)(unsigned long))slob_timer_cbk, 0, 0); |
10cef602 | 366 | |
2e892f43 CL |
367 | int kmem_cache_shrink(struct kmem_cache *d) |
368 | { | |
369 | return 0; | |
370 | } | |
371 | EXPORT_SYMBOL(kmem_cache_shrink); | |
372 | ||
55935a34 | 373 | int kmem_ptr_validate(struct kmem_cache *a, const void *b) |
2e892f43 CL |
374 | { |
375 | return 0; | |
376 | } | |
377 | ||
bcb4ddb4 DG |
378 | void __init kmem_cache_init(void) |
379 | { | |
380 | slob_timer_cbk(); | |
381 | } | |
382 | ||
383 | static void slob_timer_cbk(void) | |
10cef602 MM |
384 | { |
385 | void *p = slob_alloc(PAGE_SIZE, 0, PAGE_SIZE-1); | |
386 | ||
387 | if (p) | |
388 | free_page((unsigned long)p); | |
389 | ||
390 | mod_timer(&slob_timer, jiffies + HZ); | |
391 | } |