ia64/xen-unstable

view xen/common/xmalloc_tlsf.c @ 18645:48fba1dbcfaf

xmalloc: use tlsf algorithm

This patch replaces the Xen xmalloc engine with tlsf, an allocation
engine that is both more space efficient and time-bounded, especially
for allocation sizes between PAGE_SIZE/2 and PAGE_SIZE.

The file xmalloc.c is deprecated but not yet deleted. A simple
changein common/Makefile will change back to the legacy xmalloc/xfree
if needed for testing.

Code adapted from Nitin Gupta's tlsf-kmod, rev 229, found here:
http://code.google.com/p/compcache/source/browse/trunk/sub-projects/allocat=
ors/tlsf-kmod
with description and performance details here:
http://code.google.com/p/compcache/wiki/TLSFAllocator
(new Xen code uses 4K=3DPAGE_SIZE for the region size)

For detailed info on tlsf, see:
http://rtportal.upv.es/rtmalloc/

Signed-off-by: Dan Magenheimer <dan.magenheimer@oracle.com>
Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Oct 16 11:09:50 2008 +0100 (2008-10-16)
parents
children bb1a67a7db26
line source
1 /*
2 * Two Levels Segregate Fit memory allocator (TLSF)
3 * Version 2.3.2
4 *
5 * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
6 *
7 * Thanks to Ismael Ripoll for his suggestions and reviews
8 *
9 * Copyright (C) 2007, 2006, 2005, 2004
10 *
11 * This code is released using a dual license strategy: GPL/LGPL
12 * You can choose the licence that better fits your requirements.
13 *
14 * Released under the terms of the GNU General Public License Version 2.0
15 * Released under the terms of the GNU Lesser General Public License
16 * Version 2.1
17 *
18 * This is kernel port of TLSF allocator.
19 * Original code can be found at: http://rtportal.upv.es/rtmalloc/
20 * Adapted for Linux by Nitin Gupta (nitingupta910@gmail.com)
21 * (http://code.google.com/p/compcache/source/browse/trunk/sub-projects
22 * /allocators/tlsf-kmod r229 dated Aug 27, 2008
23 * Adapted for Xen by Dan Magenheimer (dan.magenheimer@oracle.com)
24 */
26 #include <xen/config.h>
27 #include <xen/irq.h>
28 #include <xen/mm.h>
29 #include <asm/time.h>
31 #define MAX_POOL_NAME_LEN 16
33 typedef void *(get_memory)(size_t bytes);
34 typedef void (put_memory)(void *ptr);
36 /* Some IMPORTANT TLSF parameters */
37 #define MEM_ALIGN (sizeof(void *) * 2)
38 #define MEM_ALIGN_MASK (~(MEM_ALIGN - 1))
40 #define MAX_FLI (30)
41 #define MAX_LOG2_SLI (5)
42 #define MAX_SLI (1 << MAX_LOG2_SLI)
44 #define FLI_OFFSET (6)
45 /* tlsf structure just will manage blocks bigger than 128 bytes */
46 #define SMALL_BLOCK (128)
47 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
48 #define MIN_BLOCK_SIZE (sizeof(struct free_ptr))
49 #define BHDR_OVERHEAD (sizeof(struct bhdr) - MIN_BLOCK_SIZE)
51 #define PTR_MASK (sizeof(void *) - 1)
52 #define BLOCK_SIZE_MASK (0xFFFFFFFF - PTR_MASK)
54 #define GET_NEXT_BLOCK(addr, r) ((struct bhdr *) \
55 ((char *)(addr) + (r)))
56 #define ROUNDUP_SIZE(r) (((r) + MEM_ALIGN - 1) & MEM_ALIGN_MASK)
57 #define ROUNDDOWN_SIZE(r) ((r) & MEM_ALIGN_MASK)
58 #define ROUNDUP_PAGE(r) (((r) + PAGE_SIZE - 1) & PAGE_MASK)
60 #define BLOCK_STATE (0x1)
61 #define PREV_STATE (0x2)
63 /* bit 0 of the block size */
64 #define FREE_BLOCK (0x1)
65 #define USED_BLOCK (0x0)
67 /* bit 1 of the block size */
68 #define PREV_FREE (0x2)
69 #define PREV_USED (0x0)
71 static spinlock_t pool_list_lock;
72 static struct list_head pool_list_head;
74 struct free_ptr {
75 struct bhdr *prev;
76 struct bhdr *next;
77 };
79 struct bhdr {
80 /* All blocks in a region are linked in order of physical address */
81 struct bhdr *prev_hdr;
82 /*
83 * The size is stored in bytes
84 * bit 0: block is free, if set
85 * bit 1: previous block is free, if set
86 */
87 u32 size;
88 /* Free blocks in individual freelists are linked */
89 union {
90 struct free_ptr free_ptr;
91 u8 buffer[sizeof(struct free_ptr)];
92 } ptr;
93 };
95 struct pool {
96 /* First level bitmap (REAL_FLI bits) */
97 u32 fl_bitmap;
99 /* Second level bitmap */
100 u32 sl_bitmap[REAL_FLI];
102 /* Free lists */
103 struct bhdr *matrix[REAL_FLI][MAX_SLI];
105 spinlock_t lock;
107 size_t init_size;
108 size_t max_size;
109 size_t grow_size;
111 /* Basic stats */
112 size_t used_size;
113 size_t num_regions;
115 /* User provided functions for expanding/shrinking pool */
116 get_memory *get_mem;
117 put_memory *put_mem;
119 struct list_head list;
121 void *init_region;
122 char name[MAX_POOL_NAME_LEN];
123 };
125 /*
126 * Helping functions
127 */
129 /**
130 * Returns indexes (fl, sl) of the list used to serve request of size r
131 */
132 static inline void MAPPING_SEARCH(size_t *r, int *fl, int *sl)
133 {
134 int t;
136 if ( *r < SMALL_BLOCK )
137 {
138 *fl = 0;
139 *sl = *r / (SMALL_BLOCK / MAX_SLI);
140 }
141 else
142 {
143 t = (1 << (fls(*r) - 1 - MAX_LOG2_SLI)) - 1;
144 *r = *r + t;
145 *fl = fls(*r) - 1;
146 *sl = (*r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI;
147 *fl -= FLI_OFFSET;
148 /*if ((*fl -= FLI_OFFSET) < 0) // FL will be always >0!
149 *fl = *sl = 0;
150 */
151 *r &= ~t;
152 }
153 }
155 /**
156 * Returns indexes (fl, sl) which is used as starting point to search
157 * for a block of size r. It also rounds up requested size(r) to the
158 * next list.
159 */
160 static inline void MAPPING_INSERT(size_t r, int *fl, int *sl)
161 {
162 if ( r < SMALL_BLOCK )
163 {
164 *fl = 0;
165 *sl = r / (SMALL_BLOCK / MAX_SLI);
166 }
167 else
168 {
169 *fl = fls(r) - 1;
170 *sl = (r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI;
171 *fl -= FLI_OFFSET;
172 }
173 }
175 /**
176 * Returns first block from a list that hold blocks larger than or
177 * equal to the one pointed by the indexes (fl, sl)
178 */
179 static inline struct bhdr *FIND_SUITABLE_BLOCK(struct pool *p, int *fl,
180 int *sl)
181 {
182 u32 tmp = p->sl_bitmap[*fl] & (~0 << *sl);
183 struct bhdr *b = NULL;
185 if ( tmp )
186 {
187 *sl = ffs(tmp) - 1;
188 b = p->matrix[*fl][*sl];
189 }
190 else
191 {
192 *fl = ffs(p->fl_bitmap & (~0 << (*fl + 1))) - 1;
193 if ( likely(*fl > 0) )
194 {
195 *sl = ffs(p->sl_bitmap[*fl]) - 1;
196 b = p->matrix[*fl][*sl];
197 }
198 }
200 return b;
201 }
203 /**
204 * Remove first free block(b) from free list with indexes (fl, sl).
205 */
206 static inline void EXTRACT_BLOCK_HDR(struct bhdr *b, struct pool *p, int fl,
207 int sl)
208 {
209 p->matrix[fl][sl] = b->ptr.free_ptr.next;
210 if ( p->matrix[fl][sl] )
211 {
212 p->matrix[fl][sl]->ptr.free_ptr.prev = NULL;
213 }
214 else
215 {
216 clear_bit(sl, &p->sl_bitmap[fl]);
217 if ( !p->sl_bitmap[fl] )
218 clear_bit(fl, &p->fl_bitmap);
219 }
220 b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
221 }
223 /**
224 * Removes block(b) from free list with indexes (fl, sl)
225 */
226 static inline void EXTRACT_BLOCK(struct bhdr *b, struct pool *p, int fl,
227 int sl)
228 {
229 if ( b->ptr.free_ptr.next )
230 b->ptr.free_ptr.next->ptr.free_ptr.prev =
231 b->ptr.free_ptr.prev;
232 if ( b->ptr.free_ptr.prev )
233 b->ptr.free_ptr.prev->ptr.free_ptr.next =
234 b->ptr.free_ptr.next;
235 if ( p->matrix[fl][sl] == b )
236 {
237 p->matrix[fl][sl] = b->ptr.free_ptr.next;
238 if ( !p->matrix[fl][sl] )
239 {
240 clear_bit(sl, &p->sl_bitmap[fl]);
241 if ( !p->sl_bitmap[fl] )
242 clear_bit (fl, &p->fl_bitmap);
243 }
244 }
245 b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
246 }
248 /**
249 * Insert block(b) in free list with indexes (fl, sl)
250 */
251 static inline void INSERT_BLOCK(struct bhdr *b, struct pool *p, int fl, int sl)
252 {
253 b->ptr.free_ptr = (struct free_ptr) {NULL, p->matrix[fl][sl]};
254 if ( p->matrix[fl][sl] )
255 p->matrix[fl][sl]->ptr.free_ptr.prev = b;
256 p->matrix[fl][sl] = b;
257 set_bit(sl, &p->sl_bitmap[fl]);
258 set_bit(fl, &p->fl_bitmap);
259 }
261 /**
262 * Region is a virtually contiguous memory region and Pool is
263 * collection of such regions
264 */
265 static inline void ADD_REGION(void *region, size_t region_size,
266 struct pool *pool)
267 {
268 int fl, sl;
269 struct bhdr *b, *lb;
271 b = (struct bhdr *)(region);
272 b->prev_hdr = NULL;
273 b->size = ROUNDDOWN_SIZE(region_size - 2 * BHDR_OVERHEAD)
274 | FREE_BLOCK | PREV_USED;
275 MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl);
276 INSERT_BLOCK(b, pool, fl, sl);
277 /* The sentinel block: allows us to know when we're in the last block */
278 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
279 lb->prev_hdr = b;
280 lb->size = 0 | USED_BLOCK | PREV_FREE;
281 pool->used_size += BHDR_OVERHEAD; /* only sentinel block is "used" */
282 pool->num_regions++;
283 }
285 /*
286 * Allocator code start
287 */
289 /**
290 * tlsf_create_memory_pool - create dynamic memory pool
291 * @name: name of the pool
292 * @get_mem: callback function used to expand pool
293 * @put_mem: callback function used to shrink pool
294 * @init_size: inital pool size (in bytes)
295 * @max_size: maximum pool size (in bytes) - set this as 0 for no limit
296 * @grow_size: amount of memory (in bytes) added to pool whenever required
297 *
298 * All size values are rounded up to next page boundary.
299 */
300 static void *tlsf_create_memory_pool(const char *name,
301 get_memory get_mem,
302 put_memory put_mem,
303 size_t init_size,
304 size_t max_size,
305 size_t grow_size)
306 {
307 struct pool *pool;
308 void *region;
309 int pool_bytes, pool_order;
311 BUG_ON(max_size && (max_size < init_size));
313 pool_bytes = ROUNDUP_SIZE(sizeof(*pool));
314 pool_order = get_order_from_bytes(pool_bytes);
316 pool = (void *)alloc_xenheap_pages(pool_order);
317 if ( pool == NULL )
318 return NULL;
319 memset(pool, 0, pool_bytes);
321 /* Round to next page boundary */
322 init_size = ROUNDUP_PAGE(init_size);
323 max_size = ROUNDUP_PAGE(max_size);
324 grow_size = ROUNDUP_PAGE(grow_size);
326 /* pool global overhead not included in used size */
327 pool->used_size = 0;
329 pool->init_size = init_size;
330 pool->max_size = max_size;
331 pool->grow_size = grow_size;
332 pool->get_mem = get_mem;
333 pool->put_mem = put_mem;
334 pool->name[0] = '\0'; /* ignore name for now */
335 region = get_mem(init_size);
336 if ( region == NULL )
337 goto out_region;
338 ADD_REGION(region, init_size, pool);
339 pool->init_region = region;
341 spin_lock_init(&pool->lock);
343 spin_lock(&pool_list_lock);
344 list_add_tail(&pool->list, &pool_list_head);
345 spin_unlock(&pool_list_lock);
347 return pool;
349 out_region:
350 free_xenheap_pages(pool, pool_order);
351 return NULL;
352 }
354 #if 0
356 /**
357 * tlsf_get_used_size - get memory currently used by given pool
358 *
359 * Used memory includes stored data + metadata + internal fragmentation
360 */
361 static size_t tlsf_get_used_size(void *mem_pool)
362 {
363 struct pool *pool = (struct pool *)mem_pool;
364 return pool->used_size;
365 }
367 /**
368 * tlsf_get_total_size - get total memory currently allocated for given pool
369 *
370 * This is the total memory currently allocated for this pool which includes
371 * used size + free size.
372 *
373 * (Total - Used) is good indicator of memory efficiency of allocator.
374 */
375 static size_t tlsf_get_total_size(void *mem_pool)
376 {
377 size_t total;
378 struct pool *pool = (struct pool *)mem_pool;
379 total = ROUNDUP_SIZE(sizeof(*pool))
380 + pool->init_size
381 + (pool->num_regions - 1) * pool->grow_size;
382 return total;
383 }
385 /**
386 * tlsf_destroy_memory_pool - cleanup given pool
387 * @mem_pool: Pool to be destroyed
388 *
389 * Data structures associated with pool are freed.
390 * All memory allocated from pool must be freed before
391 * destorying it.
392 */
393 static void tlsf_destroy_memory_pool(void *mem_pool)
394 {
395 struct pool *pool;
397 if ( mem_pool == NULL )
398 return;
400 pool = (struct pool *)mem_pool;
402 /* User is destroying without ever allocating from this pool */
403 if ( tlsf_get_used_size(pool) == BHDR_OVERHEAD )
404 {
405 pool->put_mem(pool->init_region);
406 pool->used_size -= BHDR_OVERHEAD;
407 }
409 /* Check for memory leaks in this pool */
410 if ( tlsf_get_used_size(pool) )
411 printk("memory leak in pool: %s (%p). "
412 "%lu bytes still in use.\n",
413 pool->name, pool, (long)tlsf_get_used_size(pool));
415 spin_lock(&pool_list_lock);
416 list_del_init(&pool->list);
417 spin_unlock(&pool_list_lock);
418 pool->put_mem(pool);
419 }
421 #endif
423 /**
424 * tlsf_malloc - allocate memory from given pool
425 * @size: no. of bytes
426 * @mem_pool: pool to allocate from
427 */
428 static void *tlsf_malloc(size_t size, void *mem_pool)
429 {
430 struct pool *pool = (struct pool *)mem_pool;
431 struct bhdr *b, *b2, *next_b, *region;
432 int fl, sl;
433 size_t tmp_size;
435 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
436 /* Rounding up the requested size and calculating fl and sl */
438 spin_lock(&pool->lock);
439 retry_find:
440 MAPPING_SEARCH(&size, &fl, &sl);
442 /* Searching a free block */
443 if ( !(b = FIND_SUITABLE_BLOCK(pool, &fl, &sl)) )
444 {
445 /* Not found */
446 if ( size > (pool->grow_size - 2 * BHDR_OVERHEAD) )
447 goto out_locked;
448 if ( pool->max_size && (pool->init_size +
449 pool->num_regions * pool->grow_size
450 > pool->max_size) )
451 goto out_locked;
452 spin_unlock(&pool->lock);
453 if ( (region = pool->get_mem(pool->grow_size)) == NULL )
454 goto out;
455 spin_lock(&pool->lock);
456 ADD_REGION(region, pool->grow_size, pool);
457 goto retry_find;
458 }
459 EXTRACT_BLOCK_HDR(b, pool, fl, sl);
461 /*-- found: */
462 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
463 /* Should the block be split? */
464 tmp_size = (b->size & BLOCK_SIZE_MASK) - size;
465 if ( tmp_size >= sizeof(struct bhdr) )
466 {
467 tmp_size -= BHDR_OVERHEAD;
468 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
470 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
471 b2->prev_hdr = b;
473 next_b->prev_hdr = b2;
475 MAPPING_INSERT(tmp_size, &fl, &sl);
476 INSERT_BLOCK(b2, pool, fl, sl);
478 b->size = size | (b->size & PREV_STATE);
479 }
480 else
481 {
482 next_b->size &= (~PREV_FREE);
483 b->size &= (~FREE_BLOCK); /* Now it's used */
484 }
486 pool->used_size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
488 spin_unlock(&pool->lock);
489 return (void *)b->ptr.buffer;
491 /* Failed alloc */
492 out_locked:
493 spin_unlock(&pool->lock);
495 out:
496 return NULL;
497 }
499 /**
500 * tlsf_free - free memory from given pool
501 * @ptr: address of memory to be freed
502 * @mem_pool: pool to free from
503 */
504 static void tlsf_free(void *ptr, void *mem_pool)
505 {
506 struct pool *pool = (struct pool *)mem_pool;
507 struct bhdr *b, *tmp_b;
508 int fl = 0, sl = 0;
510 if ( unlikely(ptr == NULL) )
511 return;
513 b = (struct bhdr *)((char *) ptr - BHDR_OVERHEAD);
515 spin_lock(&pool->lock);
516 b->size |= FREE_BLOCK;
517 pool->used_size -= (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
518 b->ptr.free_ptr = (struct free_ptr) { NULL, NULL};
519 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
520 if ( tmp_b->size & FREE_BLOCK )
521 {
522 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl);
523 EXTRACT_BLOCK(tmp_b, pool, fl, sl);
524 b->size += (tmp_b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
525 }
526 if ( b->size & PREV_FREE )
527 {
528 tmp_b = b->prev_hdr;
529 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl);
530 EXTRACT_BLOCK(tmp_b, pool, fl, sl);
531 tmp_b->size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
532 b = tmp_b;
533 }
534 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
535 tmp_b->prev_hdr = b;
537 MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl);
539 if ( (b->prev_hdr == NULL) && ((tmp_b->size & BLOCK_SIZE_MASK) == 0) )
540 {
541 pool->put_mem(b);
542 pool->num_regions--;
543 pool->used_size -= BHDR_OVERHEAD; /* sentinel block header */
544 goto out;
545 }
547 INSERT_BLOCK(b, pool, fl, sl);
549 tmp_b->size |= PREV_FREE;
550 tmp_b->prev_hdr = b;
551 out:
552 spin_unlock(&pool->lock);
553 }
555 /*
556 * Glue for xmalloc().
557 */
559 static struct pool *xenpool;
561 static void *tlsf_get_xenheap_page(size_t size)
562 {
563 ASSERT(size == PAGE_SIZE);
564 return alloc_xenheap_pages(0);
565 }
567 static void tlsf_put_xenheap_page(void *p)
568 {
569 free_xenheap_pages(p,0);
570 }
572 static void *tlsf_xenheap_malloc_whole_pages(size_t size)
573 {
574 struct bhdr *b;
575 unsigned int pageorder = get_order_from_bytes(size + BHDR_OVERHEAD);
577 b = alloc_xenheap_pages(pageorder);
578 if ( b == NULL )
579 return NULL;
581 b->size = (1 << (pageorder + PAGE_SHIFT));
582 return (void *)b->ptr.buffer;
583 }
585 static void tlsf_xenheap_init(void)
586 {
587 INIT_LIST_HEAD(&pool_list_head);
588 spin_lock_init(&pool_list_lock);
589 xenpool = tlsf_create_memory_pool(
590 "", tlsf_get_xenheap_page,
591 tlsf_put_xenheap_page, PAGE_SIZE, 0, PAGE_SIZE);
592 BUG_ON(!xenpool);
593 }
595 /*
596 * xmalloc()
597 */
599 void *_xmalloc(size_t size, size_t align)
600 {
601 void *p;
602 u32 pad;
604 ASSERT(!in_irq());
606 ASSERT((align & (align - 1)) == 0);
607 if ( align < MEM_ALIGN )
608 align = MEM_ALIGN;
609 size += align - MEM_ALIGN;
611 if ( !xenpool )
612 tlsf_xenheap_init();
614 if ( size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) )
615 p = tlsf_xenheap_malloc_whole_pages(size);
616 else
617 p = tlsf_malloc(size, xenpool);
619 /* Add alignment padding. */
620 if ( (pad = -(long)p & (align - 1)) != 0 )
621 {
622 char *q = (char *)p + pad;
623 struct bhdr *b = (struct bhdr *)(q - BHDR_OVERHEAD);
624 ASSERT(q > (char *)p);
625 b->size = pad | 1;
626 p = q;
627 }
629 ASSERT(((unsigned long)p & (align - 1)) == 0);
630 return p;
631 }
633 void xfree(void *p)
634 {
635 struct bhdr *b;
637 ASSERT(!in_irq());
639 if ( p == NULL )
640 return;
642 /* Strip alignment padding. */
643 b = (struct bhdr *)((char *) p - BHDR_OVERHEAD);
644 if ( b->size & 1 )
645 {
646 p = (char *)p - (b->size & ~1u);
647 b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
648 ASSERT(!(b->size & 1));
649 }
651 if ( b->size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) )
652 free_xenheap_pages((void *)b, get_order_from_bytes(b->size));
653 else
654 tlsf_free(p, xenpool);
655 }