ia64/xen-unstable
changeset 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>
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 | 98ff908a91b7 |
children | bb1a67a7db26 |
files | xen/common/Makefile xen/common/xmalloc_tlsf.c |
line diff
1.1 --- a/xen/common/Makefile Thu Oct 16 09:52:40 2008 +0100 1.2 +++ b/xen/common/Makefile Thu Oct 16 11:09:50 2008 +0100 1.3 @@ -25,7 +25,7 @@ obj-y += timer.o 1.4 obj-y += trace.o 1.5 obj-y += version.o 1.6 obj-y += vsprintf.o 1.7 -obj-y += xmalloc.o 1.8 +obj-y += xmalloc_tlsf.o 1.9 obj-y += rcupdate.o 1.10 1.11 obj-$(perfc) += perfc.o
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/xen/common/xmalloc_tlsf.c Thu Oct 16 11:09:50 2008 +0100 2.3 @@ -0,0 +1,655 @@ 2.4 +/* 2.5 + * Two Levels Segregate Fit memory allocator (TLSF) 2.6 + * Version 2.3.2 2.7 + * 2.8 + * Written by Miguel Masmano Tello <mimastel@doctor.upv.es> 2.9 + * 2.10 + * Thanks to Ismael Ripoll for his suggestions and reviews 2.11 + * 2.12 + * Copyright (C) 2007, 2006, 2005, 2004 2.13 + * 2.14 + * This code is released using a dual license strategy: GPL/LGPL 2.15 + * You can choose the licence that better fits your requirements. 2.16 + * 2.17 + * Released under the terms of the GNU General Public License Version 2.0 2.18 + * Released under the terms of the GNU Lesser General Public License 2.19 + * Version 2.1 2.20 + * 2.21 + * This is kernel port of TLSF allocator. 2.22 + * Original code can be found at: http://rtportal.upv.es/rtmalloc/ 2.23 + * Adapted for Linux by Nitin Gupta (nitingupta910@gmail.com) 2.24 + * (http://code.google.com/p/compcache/source/browse/trunk/sub-projects 2.25 + * /allocators/tlsf-kmod r229 dated Aug 27, 2008 2.26 + * Adapted for Xen by Dan Magenheimer (dan.magenheimer@oracle.com) 2.27 + */ 2.28 + 2.29 +#include <xen/config.h> 2.30 +#include <xen/irq.h> 2.31 +#include <xen/mm.h> 2.32 +#include <asm/time.h> 2.33 + 2.34 +#define MAX_POOL_NAME_LEN 16 2.35 + 2.36 +typedef void *(get_memory)(size_t bytes); 2.37 +typedef void (put_memory)(void *ptr); 2.38 + 2.39 +/* Some IMPORTANT TLSF parameters */ 2.40 +#define MEM_ALIGN (sizeof(void *) * 2) 2.41 +#define MEM_ALIGN_MASK (~(MEM_ALIGN - 1)) 2.42 + 2.43 +#define MAX_FLI (30) 2.44 +#define MAX_LOG2_SLI (5) 2.45 +#define MAX_SLI (1 << MAX_LOG2_SLI) 2.46 + 2.47 +#define FLI_OFFSET (6) 2.48 +/* tlsf structure just will manage blocks bigger than 128 bytes */ 2.49 +#define SMALL_BLOCK (128) 2.50 +#define REAL_FLI (MAX_FLI - FLI_OFFSET) 2.51 +#define MIN_BLOCK_SIZE (sizeof(struct free_ptr)) 2.52 +#define BHDR_OVERHEAD (sizeof(struct bhdr) - MIN_BLOCK_SIZE) 2.53 + 2.54 +#define PTR_MASK (sizeof(void *) - 1) 2.55 +#define BLOCK_SIZE_MASK (0xFFFFFFFF - PTR_MASK) 2.56 + 2.57 +#define GET_NEXT_BLOCK(addr, r) ((struct bhdr *) \ 2.58 + ((char *)(addr) + (r))) 2.59 +#define ROUNDUP_SIZE(r) (((r) + MEM_ALIGN - 1) & MEM_ALIGN_MASK) 2.60 +#define ROUNDDOWN_SIZE(r) ((r) & MEM_ALIGN_MASK) 2.61 +#define ROUNDUP_PAGE(r) (((r) + PAGE_SIZE - 1) & PAGE_MASK) 2.62 + 2.63 +#define BLOCK_STATE (0x1) 2.64 +#define PREV_STATE (0x2) 2.65 + 2.66 +/* bit 0 of the block size */ 2.67 +#define FREE_BLOCK (0x1) 2.68 +#define USED_BLOCK (0x0) 2.69 + 2.70 +/* bit 1 of the block size */ 2.71 +#define PREV_FREE (0x2) 2.72 +#define PREV_USED (0x0) 2.73 + 2.74 +static spinlock_t pool_list_lock; 2.75 +static struct list_head pool_list_head; 2.76 + 2.77 +struct free_ptr { 2.78 + struct bhdr *prev; 2.79 + struct bhdr *next; 2.80 +}; 2.81 + 2.82 +struct bhdr { 2.83 + /* All blocks in a region are linked in order of physical address */ 2.84 + struct bhdr *prev_hdr; 2.85 + /* 2.86 + * The size is stored in bytes 2.87 + * bit 0: block is free, if set 2.88 + * bit 1: previous block is free, if set 2.89 + */ 2.90 + u32 size; 2.91 + /* Free blocks in individual freelists are linked */ 2.92 + union { 2.93 + struct free_ptr free_ptr; 2.94 + u8 buffer[sizeof(struct free_ptr)]; 2.95 + } ptr; 2.96 +}; 2.97 + 2.98 +struct pool { 2.99 + /* First level bitmap (REAL_FLI bits) */ 2.100 + u32 fl_bitmap; 2.101 + 2.102 + /* Second level bitmap */ 2.103 + u32 sl_bitmap[REAL_FLI]; 2.104 + 2.105 + /* Free lists */ 2.106 + struct bhdr *matrix[REAL_FLI][MAX_SLI]; 2.107 + 2.108 + spinlock_t lock; 2.109 + 2.110 + size_t init_size; 2.111 + size_t max_size; 2.112 + size_t grow_size; 2.113 + 2.114 + /* Basic stats */ 2.115 + size_t used_size; 2.116 + size_t num_regions; 2.117 + 2.118 + /* User provided functions for expanding/shrinking pool */ 2.119 + get_memory *get_mem; 2.120 + put_memory *put_mem; 2.121 + 2.122 + struct list_head list; 2.123 + 2.124 + void *init_region; 2.125 + char name[MAX_POOL_NAME_LEN]; 2.126 +}; 2.127 + 2.128 +/* 2.129 + * Helping functions 2.130 + */ 2.131 + 2.132 +/** 2.133 + * Returns indexes (fl, sl) of the list used to serve request of size r 2.134 + */ 2.135 +static inline void MAPPING_SEARCH(size_t *r, int *fl, int *sl) 2.136 +{ 2.137 + int t; 2.138 + 2.139 + if ( *r < SMALL_BLOCK ) 2.140 + { 2.141 + *fl = 0; 2.142 + *sl = *r / (SMALL_BLOCK / MAX_SLI); 2.143 + } 2.144 + else 2.145 + { 2.146 + t = (1 << (fls(*r) - 1 - MAX_LOG2_SLI)) - 1; 2.147 + *r = *r + t; 2.148 + *fl = fls(*r) - 1; 2.149 + *sl = (*r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI; 2.150 + *fl -= FLI_OFFSET; 2.151 + /*if ((*fl -= FLI_OFFSET) < 0) // FL will be always >0! 2.152 + *fl = *sl = 0; 2.153 + */ 2.154 + *r &= ~t; 2.155 + } 2.156 +} 2.157 + 2.158 +/** 2.159 + * Returns indexes (fl, sl) which is used as starting point to search 2.160 + * for a block of size r. It also rounds up requested size(r) to the 2.161 + * next list. 2.162 + */ 2.163 +static inline void MAPPING_INSERT(size_t r, int *fl, int *sl) 2.164 +{ 2.165 + if ( r < SMALL_BLOCK ) 2.166 + { 2.167 + *fl = 0; 2.168 + *sl = r / (SMALL_BLOCK / MAX_SLI); 2.169 + } 2.170 + else 2.171 + { 2.172 + *fl = fls(r) - 1; 2.173 + *sl = (r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI; 2.174 + *fl -= FLI_OFFSET; 2.175 + } 2.176 +} 2.177 + 2.178 +/** 2.179 + * Returns first block from a list that hold blocks larger than or 2.180 + * equal to the one pointed by the indexes (fl, sl) 2.181 + */ 2.182 +static inline struct bhdr *FIND_SUITABLE_BLOCK(struct pool *p, int *fl, 2.183 + int *sl) 2.184 +{ 2.185 + u32 tmp = p->sl_bitmap[*fl] & (~0 << *sl); 2.186 + struct bhdr *b = NULL; 2.187 + 2.188 + if ( tmp ) 2.189 + { 2.190 + *sl = ffs(tmp) - 1; 2.191 + b = p->matrix[*fl][*sl]; 2.192 + } 2.193 + else 2.194 + { 2.195 + *fl = ffs(p->fl_bitmap & (~0 << (*fl + 1))) - 1; 2.196 + if ( likely(*fl > 0) ) 2.197 + { 2.198 + *sl = ffs(p->sl_bitmap[*fl]) - 1; 2.199 + b = p->matrix[*fl][*sl]; 2.200 + } 2.201 + } 2.202 + 2.203 + return b; 2.204 +} 2.205 + 2.206 +/** 2.207 + * Remove first free block(b) from free list with indexes (fl, sl). 2.208 + */ 2.209 +static inline void EXTRACT_BLOCK_HDR(struct bhdr *b, struct pool *p, int fl, 2.210 + int sl) 2.211 +{ 2.212 + p->matrix[fl][sl] = b->ptr.free_ptr.next; 2.213 + if ( p->matrix[fl][sl] ) 2.214 + { 2.215 + p->matrix[fl][sl]->ptr.free_ptr.prev = NULL; 2.216 + } 2.217 + else 2.218 + { 2.219 + clear_bit(sl, &p->sl_bitmap[fl]); 2.220 + if ( !p->sl_bitmap[fl] ) 2.221 + clear_bit(fl, &p->fl_bitmap); 2.222 + } 2.223 + b->ptr.free_ptr = (struct free_ptr) {NULL, NULL}; 2.224 +} 2.225 + 2.226 +/** 2.227 + * Removes block(b) from free list with indexes (fl, sl) 2.228 + */ 2.229 +static inline void EXTRACT_BLOCK(struct bhdr *b, struct pool *p, int fl, 2.230 + int sl) 2.231 +{ 2.232 + if ( b->ptr.free_ptr.next ) 2.233 + b->ptr.free_ptr.next->ptr.free_ptr.prev = 2.234 + b->ptr.free_ptr.prev; 2.235 + if ( b->ptr.free_ptr.prev ) 2.236 + b->ptr.free_ptr.prev->ptr.free_ptr.next = 2.237 + b->ptr.free_ptr.next; 2.238 + if ( p->matrix[fl][sl] == b ) 2.239 + { 2.240 + p->matrix[fl][sl] = b->ptr.free_ptr.next; 2.241 + if ( !p->matrix[fl][sl] ) 2.242 + { 2.243 + clear_bit(sl, &p->sl_bitmap[fl]); 2.244 + if ( !p->sl_bitmap[fl] ) 2.245 + clear_bit (fl, &p->fl_bitmap); 2.246 + } 2.247 + } 2.248 + b->ptr.free_ptr = (struct free_ptr) {NULL, NULL}; 2.249 +} 2.250 + 2.251 +/** 2.252 + * Insert block(b) in free list with indexes (fl, sl) 2.253 + */ 2.254 +static inline void INSERT_BLOCK(struct bhdr *b, struct pool *p, int fl, int sl) 2.255 +{ 2.256 + b->ptr.free_ptr = (struct free_ptr) {NULL, p->matrix[fl][sl]}; 2.257 + if ( p->matrix[fl][sl] ) 2.258 + p->matrix[fl][sl]->ptr.free_ptr.prev = b; 2.259 + p->matrix[fl][sl] = b; 2.260 + set_bit(sl, &p->sl_bitmap[fl]); 2.261 + set_bit(fl, &p->fl_bitmap); 2.262 +} 2.263 + 2.264 +/** 2.265 + * Region is a virtually contiguous memory region and Pool is 2.266 + * collection of such regions 2.267 + */ 2.268 +static inline void ADD_REGION(void *region, size_t region_size, 2.269 + struct pool *pool) 2.270 +{ 2.271 + int fl, sl; 2.272 + struct bhdr *b, *lb; 2.273 + 2.274 + b = (struct bhdr *)(region); 2.275 + b->prev_hdr = NULL; 2.276 + b->size = ROUNDDOWN_SIZE(region_size - 2 * BHDR_OVERHEAD) 2.277 + | FREE_BLOCK | PREV_USED; 2.278 + MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl); 2.279 + INSERT_BLOCK(b, pool, fl, sl); 2.280 + /* The sentinel block: allows us to know when we're in the last block */ 2.281 + lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK); 2.282 + lb->prev_hdr = b; 2.283 + lb->size = 0 | USED_BLOCK | PREV_FREE; 2.284 + pool->used_size += BHDR_OVERHEAD; /* only sentinel block is "used" */ 2.285 + pool->num_regions++; 2.286 +} 2.287 + 2.288 +/* 2.289 + * Allocator code start 2.290 + */ 2.291 + 2.292 +/** 2.293 + * tlsf_create_memory_pool - create dynamic memory pool 2.294 + * @name: name of the pool 2.295 + * @get_mem: callback function used to expand pool 2.296 + * @put_mem: callback function used to shrink pool 2.297 + * @init_size: inital pool size (in bytes) 2.298 + * @max_size: maximum pool size (in bytes) - set this as 0 for no limit 2.299 + * @grow_size: amount of memory (in bytes) added to pool whenever required 2.300 + * 2.301 + * All size values are rounded up to next page boundary. 2.302 + */ 2.303 +static void *tlsf_create_memory_pool(const char *name, 2.304 + get_memory get_mem, 2.305 + put_memory put_mem, 2.306 + size_t init_size, 2.307 + size_t max_size, 2.308 + size_t grow_size) 2.309 +{ 2.310 + struct pool *pool; 2.311 + void *region; 2.312 + int pool_bytes, pool_order; 2.313 + 2.314 + BUG_ON(max_size && (max_size < init_size)); 2.315 + 2.316 + pool_bytes = ROUNDUP_SIZE(sizeof(*pool)); 2.317 + pool_order = get_order_from_bytes(pool_bytes); 2.318 + 2.319 + pool = (void *)alloc_xenheap_pages(pool_order); 2.320 + if ( pool == NULL ) 2.321 + return NULL; 2.322 + memset(pool, 0, pool_bytes); 2.323 + 2.324 + /* Round to next page boundary */ 2.325 + init_size = ROUNDUP_PAGE(init_size); 2.326 + max_size = ROUNDUP_PAGE(max_size); 2.327 + grow_size = ROUNDUP_PAGE(grow_size); 2.328 + 2.329 + /* pool global overhead not included in used size */ 2.330 + pool->used_size = 0; 2.331 + 2.332 + pool->init_size = init_size; 2.333 + pool->max_size = max_size; 2.334 + pool->grow_size = grow_size; 2.335 + pool->get_mem = get_mem; 2.336 + pool->put_mem = put_mem; 2.337 + pool->name[0] = '\0'; /* ignore name for now */ 2.338 + region = get_mem(init_size); 2.339 + if ( region == NULL ) 2.340 + goto out_region; 2.341 + ADD_REGION(region, init_size, pool); 2.342 + pool->init_region = region; 2.343 + 2.344 + spin_lock_init(&pool->lock); 2.345 + 2.346 + spin_lock(&pool_list_lock); 2.347 + list_add_tail(&pool->list, &pool_list_head); 2.348 + spin_unlock(&pool_list_lock); 2.349 + 2.350 + return pool; 2.351 + 2.352 + out_region: 2.353 + free_xenheap_pages(pool, pool_order); 2.354 + return NULL; 2.355 +} 2.356 + 2.357 +#if 0 2.358 + 2.359 +/** 2.360 + * tlsf_get_used_size - get memory currently used by given pool 2.361 + * 2.362 + * Used memory includes stored data + metadata + internal fragmentation 2.363 + */ 2.364 +static size_t tlsf_get_used_size(void *mem_pool) 2.365 +{ 2.366 + struct pool *pool = (struct pool *)mem_pool; 2.367 + return pool->used_size; 2.368 +} 2.369 + 2.370 +/** 2.371 + * tlsf_get_total_size - get total memory currently allocated for given pool 2.372 + * 2.373 + * This is the total memory currently allocated for this pool which includes 2.374 + * used size + free size. 2.375 + * 2.376 + * (Total - Used) is good indicator of memory efficiency of allocator. 2.377 + */ 2.378 +static size_t tlsf_get_total_size(void *mem_pool) 2.379 +{ 2.380 + size_t total; 2.381 + struct pool *pool = (struct pool *)mem_pool; 2.382 + total = ROUNDUP_SIZE(sizeof(*pool)) 2.383 + + pool->init_size 2.384 + + (pool->num_regions - 1) * pool->grow_size; 2.385 + return total; 2.386 +} 2.387 + 2.388 +/** 2.389 + * tlsf_destroy_memory_pool - cleanup given pool 2.390 + * @mem_pool: Pool to be destroyed 2.391 + * 2.392 + * Data structures associated with pool are freed. 2.393 + * All memory allocated from pool must be freed before 2.394 + * destorying it. 2.395 + */ 2.396 +static void tlsf_destroy_memory_pool(void *mem_pool) 2.397 +{ 2.398 + struct pool *pool; 2.399 + 2.400 + if ( mem_pool == NULL ) 2.401 + return; 2.402 + 2.403 + pool = (struct pool *)mem_pool; 2.404 + 2.405 + /* User is destroying without ever allocating from this pool */ 2.406 + if ( tlsf_get_used_size(pool) == BHDR_OVERHEAD ) 2.407 + { 2.408 + pool->put_mem(pool->init_region); 2.409 + pool->used_size -= BHDR_OVERHEAD; 2.410 + } 2.411 + 2.412 + /* Check for memory leaks in this pool */ 2.413 + if ( tlsf_get_used_size(pool) ) 2.414 + printk("memory leak in pool: %s (%p). " 2.415 + "%lu bytes still in use.\n", 2.416 + pool->name, pool, (long)tlsf_get_used_size(pool)); 2.417 + 2.418 + spin_lock(&pool_list_lock); 2.419 + list_del_init(&pool->list); 2.420 + spin_unlock(&pool_list_lock); 2.421 + pool->put_mem(pool); 2.422 +} 2.423 + 2.424 +#endif 2.425 + 2.426 +/** 2.427 + * tlsf_malloc - allocate memory from given pool 2.428 + * @size: no. of bytes 2.429 + * @mem_pool: pool to allocate from 2.430 + */ 2.431 +static void *tlsf_malloc(size_t size, void *mem_pool) 2.432 +{ 2.433 + struct pool *pool = (struct pool *)mem_pool; 2.434 + struct bhdr *b, *b2, *next_b, *region; 2.435 + int fl, sl; 2.436 + size_t tmp_size; 2.437 + 2.438 + size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size); 2.439 + /* Rounding up the requested size and calculating fl and sl */ 2.440 + 2.441 + spin_lock(&pool->lock); 2.442 + retry_find: 2.443 + MAPPING_SEARCH(&size, &fl, &sl); 2.444 + 2.445 + /* Searching a free block */ 2.446 + if ( !(b = FIND_SUITABLE_BLOCK(pool, &fl, &sl)) ) 2.447 + { 2.448 + /* Not found */ 2.449 + if ( size > (pool->grow_size - 2 * BHDR_OVERHEAD) ) 2.450 + goto out_locked; 2.451 + if ( pool->max_size && (pool->init_size + 2.452 + pool->num_regions * pool->grow_size 2.453 + > pool->max_size) ) 2.454 + goto out_locked; 2.455 + spin_unlock(&pool->lock); 2.456 + if ( (region = pool->get_mem(pool->grow_size)) == NULL ) 2.457 + goto out; 2.458 + spin_lock(&pool->lock); 2.459 + ADD_REGION(region, pool->grow_size, pool); 2.460 + goto retry_find; 2.461 + } 2.462 + EXTRACT_BLOCK_HDR(b, pool, fl, sl); 2.463 + 2.464 + /*-- found: */ 2.465 + next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK); 2.466 + /* Should the block be split? */ 2.467 + tmp_size = (b->size & BLOCK_SIZE_MASK) - size; 2.468 + if ( tmp_size >= sizeof(struct bhdr) ) 2.469 + { 2.470 + tmp_size -= BHDR_OVERHEAD; 2.471 + b2 = GET_NEXT_BLOCK(b->ptr.buffer, size); 2.472 + 2.473 + b2->size = tmp_size | FREE_BLOCK | PREV_USED; 2.474 + b2->prev_hdr = b; 2.475 + 2.476 + next_b->prev_hdr = b2; 2.477 + 2.478 + MAPPING_INSERT(tmp_size, &fl, &sl); 2.479 + INSERT_BLOCK(b2, pool, fl, sl); 2.480 + 2.481 + b->size = size | (b->size & PREV_STATE); 2.482 + } 2.483 + else 2.484 + { 2.485 + next_b->size &= (~PREV_FREE); 2.486 + b->size &= (~FREE_BLOCK); /* Now it's used */ 2.487 + } 2.488 + 2.489 + pool->used_size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD; 2.490 + 2.491 + spin_unlock(&pool->lock); 2.492 + return (void *)b->ptr.buffer; 2.493 + 2.494 + /* Failed alloc */ 2.495 + out_locked: 2.496 + spin_unlock(&pool->lock); 2.497 + 2.498 + out: 2.499 + return NULL; 2.500 +} 2.501 + 2.502 +/** 2.503 + * tlsf_free - free memory from given pool 2.504 + * @ptr: address of memory to be freed 2.505 + * @mem_pool: pool to free from 2.506 + */ 2.507 +static void tlsf_free(void *ptr, void *mem_pool) 2.508 +{ 2.509 + struct pool *pool = (struct pool *)mem_pool; 2.510 + struct bhdr *b, *tmp_b; 2.511 + int fl = 0, sl = 0; 2.512 + 2.513 + if ( unlikely(ptr == NULL) ) 2.514 + return; 2.515 + 2.516 + b = (struct bhdr *)((char *) ptr - BHDR_OVERHEAD); 2.517 + 2.518 + spin_lock(&pool->lock); 2.519 + b->size |= FREE_BLOCK; 2.520 + pool->used_size -= (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD; 2.521 + b->ptr.free_ptr = (struct free_ptr) { NULL, NULL}; 2.522 + tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK); 2.523 + if ( tmp_b->size & FREE_BLOCK ) 2.524 + { 2.525 + MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl); 2.526 + EXTRACT_BLOCK(tmp_b, pool, fl, sl); 2.527 + b->size += (tmp_b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD; 2.528 + } 2.529 + if ( b->size & PREV_FREE ) 2.530 + { 2.531 + tmp_b = b->prev_hdr; 2.532 + MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl); 2.533 + EXTRACT_BLOCK(tmp_b, pool, fl, sl); 2.534 + tmp_b->size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD; 2.535 + b = tmp_b; 2.536 + } 2.537 + tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK); 2.538 + tmp_b->prev_hdr = b; 2.539 + 2.540 + MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl); 2.541 + 2.542 + if ( (b->prev_hdr == NULL) && ((tmp_b->size & BLOCK_SIZE_MASK) == 0) ) 2.543 + { 2.544 + pool->put_mem(b); 2.545 + pool->num_regions--; 2.546 + pool->used_size -= BHDR_OVERHEAD; /* sentinel block header */ 2.547 + goto out; 2.548 + } 2.549 + 2.550 + INSERT_BLOCK(b, pool, fl, sl); 2.551 + 2.552 + tmp_b->size |= PREV_FREE; 2.553 + tmp_b->prev_hdr = b; 2.554 + out: 2.555 + spin_unlock(&pool->lock); 2.556 +} 2.557 + 2.558 +/* 2.559 + * Glue for xmalloc(). 2.560 + */ 2.561 + 2.562 +static struct pool *xenpool; 2.563 + 2.564 +static void *tlsf_get_xenheap_page(size_t size) 2.565 +{ 2.566 + ASSERT(size == PAGE_SIZE); 2.567 + return alloc_xenheap_pages(0); 2.568 +} 2.569 + 2.570 +static void tlsf_put_xenheap_page(void *p) 2.571 +{ 2.572 + free_xenheap_pages(p,0); 2.573 +} 2.574 + 2.575 +static void *tlsf_xenheap_malloc_whole_pages(size_t size) 2.576 +{ 2.577 + struct bhdr *b; 2.578 + unsigned int pageorder = get_order_from_bytes(size + BHDR_OVERHEAD); 2.579 + 2.580 + b = alloc_xenheap_pages(pageorder); 2.581 + if ( b == NULL ) 2.582 + return NULL; 2.583 + 2.584 + b->size = (1 << (pageorder + PAGE_SHIFT)); 2.585 + return (void *)b->ptr.buffer; 2.586 +} 2.587 + 2.588 +static void tlsf_xenheap_init(void) 2.589 +{ 2.590 + INIT_LIST_HEAD(&pool_list_head); 2.591 + spin_lock_init(&pool_list_lock); 2.592 + xenpool = tlsf_create_memory_pool( 2.593 + "", tlsf_get_xenheap_page, 2.594 + tlsf_put_xenheap_page, PAGE_SIZE, 0, PAGE_SIZE); 2.595 + BUG_ON(!xenpool); 2.596 +} 2.597 + 2.598 +/* 2.599 + * xmalloc() 2.600 + */ 2.601 + 2.602 +void *_xmalloc(size_t size, size_t align) 2.603 +{ 2.604 + void *p; 2.605 + u32 pad; 2.606 + 2.607 + ASSERT(!in_irq()); 2.608 + 2.609 + ASSERT((align & (align - 1)) == 0); 2.610 + if ( align < MEM_ALIGN ) 2.611 + align = MEM_ALIGN; 2.612 + size += align - MEM_ALIGN; 2.613 + 2.614 + if ( !xenpool ) 2.615 + tlsf_xenheap_init(); 2.616 + 2.617 + if ( size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) ) 2.618 + p = tlsf_xenheap_malloc_whole_pages(size); 2.619 + else 2.620 + p = tlsf_malloc(size, xenpool); 2.621 + 2.622 + /* Add alignment padding. */ 2.623 + if ( (pad = -(long)p & (align - 1)) != 0 ) 2.624 + { 2.625 + char *q = (char *)p + pad; 2.626 + struct bhdr *b = (struct bhdr *)(q - BHDR_OVERHEAD); 2.627 + ASSERT(q > (char *)p); 2.628 + b->size = pad | 1; 2.629 + p = q; 2.630 + } 2.631 + 2.632 + ASSERT(((unsigned long)p & (align - 1)) == 0); 2.633 + return p; 2.634 +} 2.635 + 2.636 +void xfree(void *p) 2.637 +{ 2.638 + struct bhdr *b; 2.639 + 2.640 + ASSERT(!in_irq()); 2.641 + 2.642 + if ( p == NULL ) 2.643 + return; 2.644 + 2.645 + /* Strip alignment padding. */ 2.646 + b = (struct bhdr *)((char *) p - BHDR_OVERHEAD); 2.647 + if ( b->size & 1 ) 2.648 + { 2.649 + p = (char *)p - (b->size & ~1u); 2.650 + b = (struct bhdr *)((char *)p - BHDR_OVERHEAD); 2.651 + ASSERT(!(b->size & 1)); 2.652 + } 2.653 + 2.654 + if ( b->size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) ) 2.655 + free_xenheap_pages((void *)b, get_order_from_bytes(b->size)); 2.656 + else 2.657 + tlsf_free(p, xenpool); 2.658 +}