Rev 780 | Rev 782 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
759 | palkovsky | 1 | /* |
2 | * Copyright (C) 2006 Ondrej Palkovsky |
||
3 | * All rights reserved. |
||
4 | * |
||
5 | * Redistribution and use in source and binary forms, with or without |
||
6 | * modification, are permitted provided that the following conditions |
||
7 | * are met: |
||
8 | * |
||
9 | * - Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * - Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * - The name of the author may not be used to endorse or promote products |
||
15 | * derived from this software without specific prior written permission. |
||
16 | * |
||
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
||
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
||
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
||
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
||
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
||
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
||
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
||
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
||
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
27 | */ |
||
28 | |||
769 | palkovsky | 29 | /* |
30 | * The SLAB allocator is closely modelled after Opensolaris SLAB allocator |
||
31 | * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/ |
||
32 | * |
||
33 | * with the following exceptions: |
||
34 | * - empty SLABS are deallocated immediately |
||
35 | * (in Linux they are kept in linked list, in Solaris ???) |
||
36 | * - empty magazines are deallocated when not needed |
||
37 | * (in Solaris they are held in linked list in slab cache) |
||
38 | * |
||
39 | * Following features are not currently supported but would be easy to do: |
||
40 | * - cache coloring |
||
41 | * - dynamic magazine growing (different magazine sizes are already |
||
42 | * supported, but we would need to adjust allocating strategy) |
||
43 | * |
||
44 | * The SLAB allocator supports per-CPU caches ('magazines') to facilitate |
||
45 | * good SMP scaling. |
||
46 | * |
||
47 | * When a new object is being allocated, it is first checked, if it is |
||
48 | * available in CPU-bound magazine. If it is not found there, it is |
||
49 | * allocated from CPU-shared SLAB - if partial full is found, it is used, |
||
50 | * otherwise a new one is allocated. |
||
51 | * |
||
52 | * When an object is being deallocated, it is put to CPU-bound magazine. |
||
53 | * If there is no such magazine, new one is allocated (if it fails, |
||
54 | * the object is deallocated into SLAB). If the magazine is full, it is |
||
55 | * put into cpu-shared list of magazines and new one is allocated. |
||
56 | * |
||
57 | * The CPU-bound magazine is actually a pair of magazine to avoid |
||
58 | * thrashing when somebody is allocating/deallocating 1 item at the magazine |
||
59 | * size boundary. LIFO order is enforced, which should avoid fragmentation |
||
60 | * as much as possible. |
||
61 | * |
||
62 | * Every cache contains list of full slabs and list of partialy full slabs. |
||
63 | * Empty SLABS are immediately freed (thrashing will be avoided because |
||
64 | * of magazines). |
||
65 | * |
||
66 | * The SLAB information structure is kept inside the data area, if possible. |
||
67 | * The cache can be marked that it should not use magazines. This is used |
||
68 | * only for SLAB related caches to avoid deadlocks and infinite recursion |
||
69 | * (the SLAB allocator uses itself for allocating all it's control structures). |
||
70 | * |
||
71 | * The SLAB allocator allocates lot of space and does not free it. When |
||
72 | * frame allocator fails to allocate the frame, it calls slab_reclaim(). |
||
73 | * It tries 'light reclaim' first, then brutal reclaim. The light reclaim |
||
74 | * releases slabs from cpu-shared magazine-list, until at least 1 slab |
||
75 | * is deallocated in each cache (this algorithm should probably change). |
||
76 | * The brutal reclaim removes all cached objects, even from CPU-bound |
||
77 | * magazines. |
||
78 | * |
||
775 | palkovsky | 79 | * TODO: For better CPU-scaling the magazine allocation strategy should |
80 | * be extended. Currently, if the cache does not have magazine, it asks |
||
81 | * for non-cpu cached magazine cache to provide one. It might be feasible |
||
82 | * to add cpu-cached magazine cache (which would allocate it's magazines |
||
83 | * from non-cpu-cached mag. cache). This would provide a nice per-cpu |
||
84 | * buffer. The other possibility is to use the per-cache |
||
85 | * 'empty-magazine-list', which decreases competing for 1 per-system |
||
86 | * magazine cache. |
||
87 | * |
||
776 | palkovsky | 88 | * - it might be good to add granularity of locks even to slab level, |
89 | * we could then try_spinlock over all partial slabs and thus improve |
||
90 | * scalability even on slab level |
||
769 | palkovsky | 91 | */ |
92 | |||
93 | |||
759 | palkovsky | 94 | #include <synch/spinlock.h> |
95 | #include <mm/slab.h> |
||
96 | #include <list.h> |
||
97 | #include <memstr.h> |
||
98 | #include <align.h> |
||
99 | #include <mm/heap.h> |
||
762 | palkovsky | 100 | #include <mm/frame.h> |
759 | palkovsky | 101 | #include <config.h> |
102 | #include <print.h> |
||
103 | #include <arch.h> |
||
104 | #include <panic.h> |
||
762 | palkovsky | 105 | #include <debug.h> |
771 | palkovsky | 106 | #include <bitops.h> |
759 | palkovsky | 107 | |
108 | SPINLOCK_INITIALIZE(slab_cache_lock); |
||
769 | palkovsky | 109 | static LIST_INITIALIZE(slab_cache_list); |
759 | palkovsky | 110 | |
769 | palkovsky | 111 | /** Magazine cache */ |
112 | static slab_cache_t mag_cache; |
||
113 | /** Cache for cache descriptors */ |
||
114 | static slab_cache_t slab_cache_cache; |
||
759 | palkovsky | 115 | |
769 | palkovsky | 116 | /** Cache for external slab descriptors |
117 | * This time we want per-cpu cache, so do not make it static |
||
118 | * - using SLAB for internal SLAB structures will not deadlock, |
||
119 | * as all slab structures are 'small' - control structures of |
||
120 | * their caches do not require further allocation |
||
121 | */ |
||
122 | static slab_cache_t *slab_extern_cache; |
||
771 | palkovsky | 123 | /** Caches for malloc */ |
124 | static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1]; |
||
125 | char *malloc_names[] = { |
||
126 | "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128", |
||
127 | "malloc-256","malloc-512","malloc-1K","malloc-2K", |
||
128 | "malloc-4K","malloc-8K","malloc-16K","malloc-32K", |
||
129 | "malloc-64K","malloc-128K" |
||
130 | }; |
||
762 | palkovsky | 131 | |
769 | palkovsky | 132 | /** Slab descriptor */ |
762 | palkovsky | 133 | typedef struct { |
134 | slab_cache_t *cache; /**< Pointer to parent cache */ |
||
135 | link_t link; /* List of full/partial slabs */ |
||
136 | void *start; /**< Start address of first available item */ |
||
137 | count_t available; /**< Count of available items in this slab */ |
||
138 | index_t nextavail; /**< The index of next available item */ |
||
139 | }slab_t; |
||
140 | |||
759 | palkovsky | 141 | /**************************************/ |
762 | palkovsky | 142 | /* SLAB allocation functions */ |
759 | palkovsky | 143 | |
762 | palkovsky | 144 | /** |
145 | * Allocate frames for slab space and initialize |
||
146 | * |
||
147 | */ |
||
148 | static slab_t * slab_space_alloc(slab_cache_t *cache, int flags) |
||
149 | { |
||
150 | void *data; |
||
151 | slab_t *slab; |
||
152 | size_t fsize; |
||
153 | int i; |
||
154 | zone_t *zone = NULL; |
||
155 | int status; |
||
764 | palkovsky | 156 | frame_t *frame; |
759 | palkovsky | 157 | |
762 | palkovsky | 158 | data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone); |
764 | palkovsky | 159 | if (status != FRAME_OK) { |
762 | palkovsky | 160 | return NULL; |
764 | palkovsky | 161 | } |
768 | palkovsky | 162 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
769 | palkovsky | 163 | slab = slab_alloc(slab_extern_cache, flags); |
762 | palkovsky | 164 | if (!slab) { |
165 | frame_free((__address)data); |
||
166 | return NULL; |
||
167 | } |
||
168 | } else { |
||
169 | fsize = (PAGE_SIZE << cache->order); |
||
170 | slab = data + fsize - sizeof(*slab); |
||
171 | } |
||
764 | palkovsky | 172 | |
762 | palkovsky | 173 | /* Fill in slab structures */ |
763 | jermar | 174 | /* TODO: some better way of accessing the frame */ |
766 | palkovsky | 175 | for (i=0; i < (1 << cache->order); i++) { |
764 | palkovsky | 176 | frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE))); |
177 | frame->parent = slab; |
||
762 | palkovsky | 178 | } |
179 | |||
180 | slab->start = data; |
||
181 | slab->available = cache->objects; |
||
182 | slab->nextavail = 0; |
||
767 | palkovsky | 183 | slab->cache = cache; |
762 | palkovsky | 184 | |
185 | for (i=0; i<cache->objects;i++) |
||
186 | *((int *) (slab->start + i*cache->size)) = i+1; |
||
764 | palkovsky | 187 | |
188 | atomic_inc(&cache->allocated_slabs); |
||
762 | palkovsky | 189 | return slab; |
190 | } |
||
191 | |||
759 | palkovsky | 192 | /** |
766 | palkovsky | 193 | * Deallocate space associated with SLAB |
762 | palkovsky | 194 | * |
195 | * @return number of freed frames |
||
196 | */ |
||
197 | static count_t slab_space_free(slab_cache_t *cache, slab_t *slab) |
||
198 | { |
||
199 | frame_free((__address)slab->start); |
||
768 | palkovsky | 200 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
769 | palkovsky | 201 | slab_free(slab_extern_cache, slab); |
764 | palkovsky | 202 | |
203 | atomic_dec(&cache->allocated_slabs); |
||
204 | |||
762 | palkovsky | 205 | return 1 << cache->order; |
206 | } |
||
207 | |||
208 | /** Map object to slab structure */ |
||
209 | static slab_t * obj2slab(void *obj) |
||
210 | { |
||
211 | frame_t *frame; |
||
212 | |||
213 | frame = frame_addr2frame((__address)obj); |
||
214 | return (slab_t *)frame->parent; |
||
215 | } |
||
216 | |||
217 | /**************************************/ |
||
218 | /* SLAB functions */ |
||
219 | |||
220 | |||
221 | /** |
||
759 | palkovsky | 222 | * Return object to slab and call a destructor |
223 | * |
||
762 | palkovsky | 224 | * @param slab If the caller knows directly slab of the object, otherwise NULL |
225 | * |
||
759 | palkovsky | 226 | * @return Number of freed pages |
227 | */ |
||
762 | palkovsky | 228 | static count_t slab_obj_destroy(slab_cache_t *cache, void *obj, |
229 | slab_t *slab) |
||
759 | palkovsky | 230 | { |
762 | palkovsky | 231 | count_t frames = 0; |
232 | |||
233 | if (!slab) |
||
234 | slab = obj2slab(obj); |
||
235 | |||
767 | palkovsky | 236 | ASSERT(slab->cache == cache); |
780 | palkovsky | 237 | ASSERT(slab->available < cache->objects); |
767 | palkovsky | 238 | |
776 | palkovsky | 239 | spinlock_lock(&cache->slablock); |
240 | |||
762 | palkovsky | 241 | *((int *)obj) = slab->nextavail; |
242 | slab->nextavail = (obj - slab->start)/cache->size; |
||
243 | slab->available++; |
||
244 | |||
245 | /* Move it to correct list */ |
||
246 | if (slab->available == cache->objects) { |
||
247 | /* Free associated memory */ |
||
248 | list_remove(&slab->link); |
||
776 | palkovsky | 249 | /* This should not produce deadlock, as |
250 | * magazine is always allocated with NO reclaim, |
||
251 | * keep all locks */ |
||
762 | palkovsky | 252 | frames = slab_space_free(cache, slab); |
780 | palkovsky | 253 | } else if (slab->available == 1) { |
254 | /* It was in full, move to partial */ |
||
255 | list_remove(&slab->link); |
||
256 | list_prepend(&slab->link, &cache->partial_slabs); |
||
762 | palkovsky | 257 | } |
258 | |||
776 | palkovsky | 259 | spinlock_unlock(&cache->slablock); |
260 | |||
762 | palkovsky | 261 | return frames; |
759 | palkovsky | 262 | } |
263 | |||
264 | /** |
||
265 | * Take new object from slab or create new if needed |
||
266 | * |
||
267 | * @return Object address or null |
||
268 | */ |
||
269 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
||
270 | { |
||
762 | palkovsky | 271 | slab_t *slab; |
272 | void *obj; |
||
273 | |||
776 | palkovsky | 274 | spinlock_lock(&cache->slablock); |
275 | |||
762 | palkovsky | 276 | if (list_empty(&cache->partial_slabs)) { |
277 | /* Allow recursion and reclaiming |
||
278 | * - this should work, as the SLAB control structures |
||
279 | * are small and do not need to allocte with anything |
||
280 | * other ten frame_alloc when they are allocating, |
||
281 | * that's why we should get recursion at most 1-level deep |
||
282 | */ |
||
776 | palkovsky | 283 | spinlock_unlock(&cache->slablock); |
762 | palkovsky | 284 | slab = slab_space_alloc(cache, flags); |
780 | palkovsky | 285 | if (!slab) |
286 | return NULL; |
||
776 | palkovsky | 287 | spinlock_lock(&cache->slablock); |
762 | palkovsky | 288 | } else { |
289 | slab = list_get_instance(cache->partial_slabs.next, |
||
290 | slab_t, |
||
291 | link); |
||
292 | list_remove(&slab->link); |
||
293 | } |
||
294 | obj = slab->start + slab->nextavail * cache->size; |
||
295 | slab->nextavail = *((int *)obj); |
||
296 | slab->available--; |
||
297 | if (! slab->available) |
||
764 | palkovsky | 298 | list_prepend(&slab->link, &cache->full_slabs); |
762 | palkovsky | 299 | else |
764 | palkovsky | 300 | list_prepend(&slab->link, &cache->partial_slabs); |
776 | palkovsky | 301 | |
302 | spinlock_unlock(&cache->slablock); |
||
762 | palkovsky | 303 | return obj; |
759 | palkovsky | 304 | } |
305 | |||
306 | /**************************************/ |
||
307 | /* CPU-Cache slab functions */ |
||
308 | |||
309 | /** |
||
781 | palkovsky | 310 | * Finds a full magazine in cache, takes it from list |
311 | * and returns it |
||
312 | * |
||
313 | * @param first If true, return first, else last mag |
||
314 | */ |
||
315 | static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache, |
||
316 | int first) |
||
317 | { |
||
318 | slab_magazine_t *mag = NULL; |
||
319 | link_t *cur; |
||
320 | |||
321 | spinlock_lock(&cache->maglock); |
||
322 | if (!list_empty(&cache->magazines)) { |
||
323 | if (first) |
||
324 | cur = cache->magazines.next; |
||
325 | else |
||
326 | cur = cache->magazines.prev; |
||
327 | mag = list_get_instance(cur, slab_magazine_t, link); |
||
328 | list_remove(&mag->link); |
||
329 | atomic_dec(&cache->magazine_counter); |
||
330 | } |
||
331 | spinlock_unlock(&cache->maglock); |
||
332 | return mag; |
||
333 | } |
||
334 | |||
335 | /** Prepend magazine to magazine list in cache */ |
||
336 | static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag) |
||
337 | { |
||
338 | spinlock_lock(&cache->maglock); |
||
339 | |||
340 | list_prepend(&mag->link, &cache->magazines); |
||
341 | atomic_inc(&cache->magazine_counter); |
||
342 | |||
343 | spinlock_unlock(&cache->maglock); |
||
344 | } |
||
345 | |||
346 | /** |
||
759 | palkovsky | 347 | * Free all objects in magazine and free memory associated with magazine |
348 | * |
||
349 | * @return Number of freed pages |
||
350 | */ |
||
351 | static count_t magazine_destroy(slab_cache_t *cache, |
||
352 | slab_magazine_t *mag) |
||
353 | { |
||
354 | int i; |
||
355 | count_t frames = 0; |
||
356 | |||
767 | palkovsky | 357 | for (i=0;i < mag->busy; i++) { |
762 | palkovsky | 358 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
767 | palkovsky | 359 | atomic_dec(&cache->cached_objs); |
360 | } |
||
759 | palkovsky | 361 | |
362 | slab_free(&mag_cache, mag); |
||
363 | |||
364 | return frames; |
||
365 | } |
||
366 | |||
367 | /** |
||
769 | palkovsky | 368 | * Find full magazine, set it as current and return it |
369 | * |
||
370 | * Assume cpu_magazine lock is held |
||
371 | */ |
||
372 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
||
373 | { |
||
374 | slab_magazine_t *cmag, *lastmag, *newmag; |
||
375 | |||
376 | cmag = cache->mag_cache[CPU->id].current; |
||
377 | lastmag = cache->mag_cache[CPU->id].last; |
||
378 | if (cmag) { /* First try local CPU magazines */ |
||
379 | if (cmag->busy) |
||
380 | return cmag; |
||
381 | |||
382 | if (lastmag && lastmag->busy) { |
||
383 | cache->mag_cache[CPU->id].current = lastmag; |
||
384 | cache->mag_cache[CPU->id].last = cmag; |
||
385 | return lastmag; |
||
386 | } |
||
387 | } |
||
388 | /* Local magazines are empty, import one from magazine list */ |
||
781 | palkovsky | 389 | newmag = get_mag_from_cache(cache, 1); |
390 | if (!newmag) |
||
769 | palkovsky | 391 | return NULL; |
392 | |||
393 | if (lastmag) |
||
781 | palkovsky | 394 | magazine_destroy(cache, lastmag); |
395 | |||
769 | palkovsky | 396 | cache->mag_cache[CPU->id].last = cmag; |
397 | cache->mag_cache[CPU->id].current = newmag; |
||
398 | return newmag; |
||
399 | } |
||
400 | |||
401 | /** |
||
759 | palkovsky | 402 | * Try to find object in CPU-cache magazines |
403 | * |
||
404 | * @return Pointer to object or NULL if not available |
||
405 | */ |
||
406 | static void * magazine_obj_get(slab_cache_t *cache) |
||
407 | { |
||
408 | slab_magazine_t *mag; |
||
767 | palkovsky | 409 | void *obj; |
759 | palkovsky | 410 | |
772 | palkovsky | 411 | if (!CPU) |
412 | return NULL; |
||
413 | |||
759 | palkovsky | 414 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
415 | |||
769 | palkovsky | 416 | mag = get_full_current_mag(cache); |
417 | if (!mag) { |
||
418 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
419 | return NULL; |
||
759 | palkovsky | 420 | } |
767 | palkovsky | 421 | obj = mag->objs[--mag->busy]; |
759 | palkovsky | 422 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
767 | palkovsky | 423 | atomic_dec(&cache->cached_objs); |
424 | |||
425 | return obj; |
||
759 | palkovsky | 426 | } |
427 | |||
428 | /** |
||
768 | palkovsky | 429 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
769 | palkovsky | 430 | * no empty magazine is available and cannot be allocated |
759 | palkovsky | 431 | * |
773 | palkovsky | 432 | * Assume mag_cache[CPU->id].lock is held |
433 | * |
||
759 | palkovsky | 434 | * We have 2 magazines bound to processor. |
435 | * First try the current. |
||
436 | * If full, try the last. |
||
437 | * If full, put to magazines list. |
||
438 | * allocate new, exchange last & current |
||
439 | * |
||
768 | palkovsky | 440 | */ |
441 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
||
442 | { |
||
443 | slab_magazine_t *cmag,*lastmag,*newmag; |
||
444 | |||
445 | cmag = cache->mag_cache[CPU->id].current; |
||
446 | lastmag = cache->mag_cache[CPU->id].last; |
||
447 | |||
448 | if (cmag) { |
||
449 | if (cmag->busy < cmag->size) |
||
450 | return cmag; |
||
451 | if (lastmag && lastmag->busy < lastmag->size) { |
||
452 | cache->mag_cache[CPU->id].last = cmag; |
||
453 | cache->mag_cache[CPU->id].current = lastmag; |
||
454 | return lastmag; |
||
455 | } |
||
456 | } |
||
457 | /* current | last are full | nonexistent, allocate new */ |
||
458 | /* We do not want to sleep just because of caching */ |
||
459 | /* Especially we do not want reclaiming to start, as |
||
460 | * this would deadlock */ |
||
461 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
||
462 | if (!newmag) |
||
463 | return NULL; |
||
464 | newmag->size = SLAB_MAG_SIZE; |
||
465 | newmag->busy = 0; |
||
466 | |||
467 | /* Flush last to magazine list */ |
||
781 | palkovsky | 468 | if (lastmag) |
469 | put_mag_to_cache(cache, lastmag); |
||
470 | |||
768 | palkovsky | 471 | /* Move current as last, save new as current */ |
472 | cache->mag_cache[CPU->id].last = cmag; |
||
473 | cache->mag_cache[CPU->id].current = newmag; |
||
474 | |||
475 | return newmag; |
||
476 | } |
||
477 | |||
478 | /** |
||
479 | * Put object into CPU-cache magazine |
||
480 | * |
||
759 | palkovsky | 481 | * @return 0 - success, -1 - could not get memory |
482 | */ |
||
483 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
||
484 | { |
||
485 | slab_magazine_t *mag; |
||
486 | |||
772 | palkovsky | 487 | if (!CPU) |
488 | return -1; |
||
489 | |||
759 | palkovsky | 490 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
768 | palkovsky | 491 | |
492 | mag = make_empty_current_mag(cache); |
||
769 | palkovsky | 493 | if (!mag) { |
494 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
495 | return -1; |
||
496 | } |
||
759 | palkovsky | 497 | |
498 | mag->objs[mag->busy++] = obj; |
||
499 | |||
500 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
767 | palkovsky | 501 | atomic_inc(&cache->cached_objs); |
759 | palkovsky | 502 | return 0; |
503 | } |
||
504 | |||
505 | |||
506 | /**************************************/ |
||
762 | palkovsky | 507 | /* SLAB CACHE functions */ |
759 | palkovsky | 508 | |
762 | palkovsky | 509 | /** Return number of objects that fit in certain cache size */ |
510 | static int comp_objects(slab_cache_t *cache) |
||
511 | { |
||
512 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
||
513 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
||
514 | else |
||
515 | return (PAGE_SIZE << cache->order) / cache->size; |
||
516 | } |
||
517 | |||
518 | /** Return wasted space in slab */ |
||
519 | static int badness(slab_cache_t *cache) |
||
520 | { |
||
521 | int objects; |
||
522 | int ssize; |
||
523 | |||
524 | objects = comp_objects(cache); |
||
525 | ssize = PAGE_SIZE << cache->order; |
||
526 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
||
527 | ssize -= sizeof(slab_t); |
||
528 | return ssize - objects*cache->size; |
||
529 | } |
||
530 | |||
759 | palkovsky | 531 | /** Initialize allocated memory as a slab cache */ |
532 | static void |
||
533 | _slab_cache_create(slab_cache_t *cache, |
||
534 | char *name, |
||
535 | size_t size, |
||
536 | size_t align, |
||
537 | int (*constructor)(void *obj, int kmflag), |
||
538 | void (*destructor)(void *obj), |
||
539 | int flags) |
||
540 | { |
||
541 | int i; |
||
771 | palkovsky | 542 | int pages; |
759 | palkovsky | 543 | |
544 | memsetb((__address)cache, sizeof(*cache), 0); |
||
545 | cache->name = name; |
||
546 | |||
766 | palkovsky | 547 | if (align < sizeof(__native)) |
548 | align = sizeof(__native); |
||
549 | size = ALIGN_UP(size, align); |
||
550 | |||
762 | palkovsky | 551 | cache->size = size; |
759 | palkovsky | 552 | |
553 | cache->constructor = constructor; |
||
554 | cache->destructor = destructor; |
||
555 | cache->flags = flags; |
||
556 | |||
557 | list_initialize(&cache->full_slabs); |
||
558 | list_initialize(&cache->partial_slabs); |
||
559 | list_initialize(&cache->magazines); |
||
776 | palkovsky | 560 | spinlock_initialize(&cache->slablock, "slab_lock"); |
561 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
||
768 | palkovsky | 562 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
773 | palkovsky | 563 | for (i=0; i < config.cpu_count; i++) { |
772 | palkovsky | 564 | memsetb((__address)&cache->mag_cache[i], |
565 | sizeof(cache->mag_cache[i]), 0); |
||
759 | palkovsky | 566 | spinlock_initialize(&cache->mag_cache[i].lock, |
776 | palkovsky | 567 | "slab_maglock_cpu"); |
772 | palkovsky | 568 | } |
759 | palkovsky | 569 | } |
570 | |||
571 | /* Compute slab sizes, object counts in slabs etc. */ |
||
572 | if (cache->size < SLAB_INSIDE_SIZE) |
||
573 | cache->flags |= SLAB_CACHE_SLINSIDE; |
||
574 | |||
762 | palkovsky | 575 | /* Minimum slab order */ |
771 | palkovsky | 576 | pages = ((cache->size-1) >> PAGE_WIDTH) + 1; |
577 | cache->order = fnzb(pages); |
||
766 | palkovsky | 578 | |
762 | palkovsky | 579 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
580 | cache->order += 1; |
||
581 | } |
||
582 | cache->objects = comp_objects(cache); |
||
766 | palkovsky | 583 | /* If info fits in, put it inside */ |
584 | if (badness(cache) > sizeof(slab_t)) |
||
585 | cache->flags |= SLAB_CACHE_SLINSIDE; |
||
762 | palkovsky | 586 | |
759 | palkovsky | 587 | spinlock_lock(&slab_cache_lock); |
588 | |||
589 | list_append(&cache->link, &slab_cache_list); |
||
590 | |||
591 | spinlock_unlock(&slab_cache_lock); |
||
592 | } |
||
593 | |||
594 | /** Create slab cache */ |
||
595 | slab_cache_t * slab_cache_create(char *name, |
||
596 | size_t size, |
||
597 | size_t align, |
||
598 | int (*constructor)(void *obj, int kmflag), |
||
599 | void (*destructor)(void *obj), |
||
600 | int flags) |
||
601 | { |
||
602 | slab_cache_t *cache; |
||
603 | |||
769 | palkovsky | 604 | cache = slab_alloc(&slab_cache_cache, 0); |
759 | palkovsky | 605 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
606 | flags); |
||
607 | return cache; |
||
608 | } |
||
609 | |||
610 | /** |
||
611 | * Reclaim space occupied by objects that are already free |
||
612 | * |
||
613 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
||
614 | * @return Number of freed pages |
||
615 | */ |
||
616 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
||
617 | { |
||
618 | int i; |
||
619 | slab_magazine_t *mag; |
||
620 | count_t frames = 0; |
||
781 | palkovsky | 621 | int magcount; |
759 | palkovsky | 622 | |
623 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
||
624 | return 0; /* Nothing to do */ |
||
781 | palkovsky | 625 | |
626 | /* We count up to original magazine count to avoid |
||
627 | * endless loop |
||
628 | */ |
||
629 | magcount = atomic_get(&cache->magazine_counter); |
||
630 | while (magcount-- && (mag=get_mag_from_cache(cache,0))) { |
||
631 | frames += magazine_destroy(cache,mag); |
||
632 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
||
633 | break; |
||
769 | palkovsky | 634 | } |
759 | palkovsky | 635 | |
636 | if (flags & SLAB_RECLAIM_ALL) { |
||
781 | palkovsky | 637 | /* Free cpu-bound magazines */ |
759 | palkovsky | 638 | /* Destroy CPU magazines */ |
639 | for (i=0; i<config.cpu_count; i++) { |
||
781 | palkovsky | 640 | spinlock_lock(&cache->mag_cache[i].lock); |
641 | |||
759 | palkovsky | 642 | mag = cache->mag_cache[i].current; |
643 | if (mag) |
||
644 | frames += magazine_destroy(cache, mag); |
||
645 | cache->mag_cache[i].current = NULL; |
||
646 | |||
647 | mag = cache->mag_cache[i].last; |
||
648 | if (mag) |
||
649 | frames += magazine_destroy(cache, mag); |
||
650 | cache->mag_cache[i].last = NULL; |
||
781 | palkovsky | 651 | |
652 | spinlock_unlock(&cache->mag_cache[i].lock); |
||
759 | palkovsky | 653 | } |
654 | } |
||
767 | palkovsky | 655 | |
759 | palkovsky | 656 | return frames; |
657 | } |
||
658 | |||
659 | /** Check that there are no slabs and remove cache from system */ |
||
660 | void slab_cache_destroy(slab_cache_t *cache) |
||
661 | { |
||
781 | palkovsky | 662 | ipl_t ipl; |
663 | |||
664 | /* First remove cache from link, so that we don't need |
||
665 | * to disable interrupts later |
||
666 | */ |
||
667 | |||
668 | ipl = interrupts_disable(); |
||
669 | spinlock_lock(&slab_cache_lock); |
||
670 | |||
671 | list_remove(&cache->link); |
||
672 | |||
673 | spinlock_unlock(&slab_cache_lock); |
||
674 | interrupts_restore(ipl); |
||
675 | |||
759 | palkovsky | 676 | /* Do not lock anything, we assume the software is correct and |
677 | * does not touch the cache when it decides to destroy it */ |
||
678 | |||
679 | /* Destroy all magazines */ |
||
680 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
||
681 | |||
682 | /* All slabs must be empty */ |
||
683 | if (!list_empty(&cache->full_slabs) \ |
||
684 | || !list_empty(&cache->partial_slabs)) |
||
685 | panic("Destroying cache that is not empty."); |
||
686 | |||
769 | palkovsky | 687 | slab_free(&slab_cache_cache, cache); |
759 | palkovsky | 688 | } |
689 | |||
690 | /** Allocate new object from cache - if no flags given, always returns |
||
691 | memory */ |
||
692 | void * slab_alloc(slab_cache_t *cache, int flags) |
||
693 | { |
||
694 | ipl_t ipl; |
||
695 | void *result = NULL; |
||
773 | palkovsky | 696 | |
759 | palkovsky | 697 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
698 | ipl = interrupts_disable(); |
||
771 | palkovsky | 699 | |
772 | palkovsky | 700 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
759 | palkovsky | 701 | result = magazine_obj_get(cache); |
776 | palkovsky | 702 | if (!result) |
759 | palkovsky | 703 | result = slab_obj_create(cache, flags); |
704 | |||
769 | palkovsky | 705 | interrupts_restore(ipl); |
706 | |||
764 | palkovsky | 707 | if (result) |
708 | atomic_inc(&cache->allocated_objs); |
||
709 | |||
759 | palkovsky | 710 | return result; |
711 | } |
||
712 | |||
771 | palkovsky | 713 | /** Return object to cache, use slab if known */ |
714 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
||
759 | palkovsky | 715 | { |
716 | ipl_t ipl; |
||
717 | |||
718 | ipl = interrupts_disable(); |
||
719 | |||
762 | palkovsky | 720 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
721 | || magazine_obj_put(cache, obj)) { |
||
776 | palkovsky | 722 | |
771 | palkovsky | 723 | slab_obj_destroy(cache, obj, slab); |
776 | palkovsky | 724 | |
759 | palkovsky | 725 | } |
769 | palkovsky | 726 | interrupts_restore(ipl); |
764 | palkovsky | 727 | atomic_dec(&cache->allocated_objs); |
759 | palkovsky | 728 | } |
729 | |||
771 | palkovsky | 730 | /** Return slab object to cache */ |
731 | void slab_free(slab_cache_t *cache, void *obj) |
||
732 | { |
||
733 | _slab_free(cache,obj,NULL); |
||
734 | } |
||
735 | |||
759 | palkovsky | 736 | /* Go through all caches and reclaim what is possible */ |
737 | count_t slab_reclaim(int flags) |
||
738 | { |
||
739 | slab_cache_t *cache; |
||
740 | link_t *cur; |
||
741 | count_t frames = 0; |
||
742 | |||
743 | spinlock_lock(&slab_cache_lock); |
||
744 | |||
776 | palkovsky | 745 | /* TODO: Add assert, that interrupts are disabled, otherwise |
746 | * memory allocation from interrupts can deadlock. |
||
781 | palkovsky | 747 | * - cache_destroy can call this with interrupts enabled :-/ |
776 | palkovsky | 748 | */ |
749 | |||
759 | palkovsky | 750 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
751 | cache = list_get_instance(cur, slab_cache_t, link); |
||
752 | frames += _slab_reclaim(cache, flags); |
||
753 | } |
||
754 | |||
755 | spinlock_unlock(&slab_cache_lock); |
||
756 | |||
757 | return frames; |
||
758 | } |
||
759 | |||
760 | |||
761 | /* Print list of slabs */ |
||
762 | void slab_print_list(void) |
||
763 | { |
||
764 | slab_cache_t *cache; |
||
765 | link_t *cur; |
||
766 | |||
767 | spinlock_lock(&slab_cache_lock); |
||
767 | palkovsky | 768 | printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n"); |
759 | palkovsky | 769 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
770 | cache = list_get_instance(cur, slab_cache_t, link); |
||
767 | palkovsky | 771 | printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size, |
766 | palkovsky | 772 | (1 << cache->order), cache->objects, |
767 | palkovsky | 773 | atomic_get(&cache->allocated_slabs), |
774 | atomic_get(&cache->cached_objs), |
||
766 | palkovsky | 775 | atomic_get(&cache->allocated_objs), |
776 | cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out"); |
||
759 | palkovsky | 777 | } |
778 | spinlock_unlock(&slab_cache_lock); |
||
779 | } |
||
780 | |||
778 | palkovsky | 781 | #ifdef CONFIG_DEBUG |
782 | static int _slab_initialized = 0; |
||
783 | #endif |
||
784 | |||
759 | palkovsky | 785 | void slab_cache_init(void) |
786 | { |
||
771 | palkovsky | 787 | int i, size; |
788 | |||
759 | palkovsky | 789 | /* Initialize magazine cache */ |
790 | _slab_cache_create(&mag_cache, |
||
791 | "slab_magazine", |
||
792 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
||
793 | sizeof(__address), |
||
794 | NULL, NULL, |
||
769 | palkovsky | 795 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
796 | /* Initialize slab_cache cache */ |
||
797 | _slab_cache_create(&slab_cache_cache, |
||
798 | "slab_cache", |
||
799 | sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]), |
||
800 | sizeof(__address), |
||
801 | NULL, NULL, |
||
802 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
||
803 | /* Initialize external slab cache */ |
||
804 | slab_extern_cache = slab_cache_create("slab_extern", |
||
805 | sizeof(slab_t), |
||
806 | 0, NULL, NULL, |
||
807 | SLAB_CACHE_SLINSIDE); |
||
759 | palkovsky | 808 | |
809 | /* Initialize structures for malloc */ |
||
771 | palkovsky | 810 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
811 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
||
812 | i++, size <<= 1) { |
||
813 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
||
814 | size, 0, |
||
815 | NULL,NULL,0); |
||
816 | } |
||
778 | palkovsky | 817 | #ifdef CONFIG_DEBUG |
818 | _slab_initialized = 1; |
||
819 | #endif |
||
759 | palkovsky | 820 | } |
771 | palkovsky | 821 | |
822 | /**************************************/ |
||
823 | /* kalloc/kfree functions */ |
||
824 | void * kalloc(unsigned int size, int flags) |
||
825 | { |
||
826 | int idx; |
||
778 | palkovsky | 827 | |
828 | ASSERT(_slab_initialized); |
||
771 | palkovsky | 829 | ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W)); |
830 | |||
831 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
||
832 | size = (1 << SLAB_MIN_MALLOC_W); |
||
833 | |||
834 | idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1; |
||
835 | |||
836 | return slab_alloc(malloc_caches[idx], flags); |
||
837 | } |
||
838 | |||
839 | |||
840 | void kfree(void *obj) |
||
841 | { |
||
781 | palkovsky | 842 | slab_t *slab; |
843 | |||
844 | if (!obj) return; |
||
845 | |||
846 | slab = obj2slab(obj); |
||
771 | palkovsky | 847 | _slab_free(slab->cache, obj, slab); |
848 | } |