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 +}