ia64/xen-unstable

view xen/common/xmalloc_tlsf.c @ 19835:edfdeb150f27

Fix buildsystem to detect udev > version 124

udev removed the udevinfo symlink from versions higher than 123 and
xen's build-system could not detect if udev is in place and has the
required version.

Signed-off-by: Marc-A. Dahlhaus <mad@wol.de>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Jun 25 13:02:37 2009 +0100 (2009-06-25)
parents f210a633571c
children
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 /* Some IMPORTANT TLSF parameters */
34 #define MEM_ALIGN (sizeof(void *) * 2)
35 #define MEM_ALIGN_MASK (~(MEM_ALIGN - 1))
37 #define MAX_FLI (30)
38 #define MAX_LOG2_SLI (5)
39 #define MAX_SLI (1 << MAX_LOG2_SLI)
41 #define FLI_OFFSET (6)
42 /* tlsf structure just will manage blocks bigger than 128 bytes */
43 #define SMALL_BLOCK (128)
44 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
45 #define MIN_BLOCK_SIZE (sizeof(struct free_ptr))
46 #define BHDR_OVERHEAD (sizeof(struct bhdr) - MIN_BLOCK_SIZE)
48 #define PTR_MASK (sizeof(void *) - 1)
49 #define BLOCK_SIZE_MASK (0xFFFFFFFF - PTR_MASK)
51 #define GET_NEXT_BLOCK(addr, r) ((struct bhdr *) \
52 ((char *)(addr) + (r)))
53 #define ROUNDUP_SIZE(r) (((r) + MEM_ALIGN - 1) & MEM_ALIGN_MASK)
54 #define ROUNDDOWN_SIZE(r) ((r) & MEM_ALIGN_MASK)
55 #define ROUNDUP_PAGE(r) (((r) + PAGE_SIZE - 1) & PAGE_MASK)
57 #define BLOCK_STATE (0x1)
58 #define PREV_STATE (0x2)
60 /* bit 0 of the block size */
61 #define FREE_BLOCK (0x1)
62 #define USED_BLOCK (0x0)
64 /* bit 1 of the block size */
65 #define PREV_FREE (0x2)
66 #define PREV_USED (0x0)
68 static spinlock_t pool_list_lock;
69 static struct list_head pool_list_head;
71 struct free_ptr {
72 struct bhdr *prev;
73 struct bhdr *next;
74 };
76 struct bhdr {
77 /* All blocks in a region are linked in order of physical address */
78 struct bhdr *prev_hdr;
79 /*
80 * The size is stored in bytes
81 * bit 0: block is free, if set
82 * bit 1: previous block is free, if set
83 */
84 u32 size;
85 /* Free blocks in individual freelists are linked */
86 union {
87 struct free_ptr free_ptr;
88 u8 buffer[sizeof(struct free_ptr)];
89 } ptr;
90 };
92 struct xmem_pool {
93 /* First level bitmap (REAL_FLI bits) */
94 u32 fl_bitmap;
96 /* Second level bitmap */
97 u32 sl_bitmap[REAL_FLI];
99 /* Free lists */
100 struct bhdr *matrix[REAL_FLI][MAX_SLI];
102 spinlock_t lock;
104 unsigned long init_size;
105 unsigned long max_size;
106 unsigned long grow_size;
108 /* Basic stats */
109 unsigned long used_size;
110 unsigned long num_regions;
112 /* User provided functions for expanding/shrinking pool */
113 xmem_pool_get_memory *get_mem;
114 xmem_pool_put_memory *put_mem;
116 struct list_head list;
118 void *init_region;
119 char name[MAX_POOL_NAME_LEN];
120 };
122 /*
123 * Helping functions
124 */
126 /**
127 * Returns indexes (fl, sl) of the list used to serve request of size r
128 */
129 static inline void MAPPING_SEARCH(unsigned long *r, int *fl, int *sl)
130 {
131 int t;
133 if ( *r < SMALL_BLOCK )
134 {
135 *fl = 0;
136 *sl = *r / (SMALL_BLOCK / MAX_SLI);
137 }
138 else
139 {
140 t = (1 << (fls(*r) - 1 - MAX_LOG2_SLI)) - 1;
141 *r = *r + t;
142 *fl = fls(*r) - 1;
143 *sl = (*r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI;
144 *fl -= FLI_OFFSET;
145 /*if ((*fl -= FLI_OFFSET) < 0) // FL will be always >0!
146 *fl = *sl = 0;
147 */
148 *r &= ~t;
149 }
150 }
152 /**
153 * Returns indexes (fl, sl) which is used as starting point to search
154 * for a block of size r. It also rounds up requested size(r) to the
155 * next list.
156 */
157 static inline void MAPPING_INSERT(unsigned long r, int *fl, int *sl)
158 {
159 if ( r < SMALL_BLOCK )
160 {
161 *fl = 0;
162 *sl = r / (SMALL_BLOCK / MAX_SLI);
163 }
164 else
165 {
166 *fl = fls(r) - 1;
167 *sl = (r >> (*fl - MAX_LOG2_SLI)) - MAX_SLI;
168 *fl -= FLI_OFFSET;
169 }
170 }
172 /**
173 * Returns first block from a list that hold blocks larger than or
174 * equal to the one pointed by the indexes (fl, sl)
175 */
176 static inline struct bhdr *FIND_SUITABLE_BLOCK(struct xmem_pool *p, int *fl,
177 int *sl)
178 {
179 u32 tmp = p->sl_bitmap[*fl] & (~0 << *sl);
180 struct bhdr *b = NULL;
182 if ( tmp )
183 {
184 *sl = ffs(tmp) - 1;
185 b = p->matrix[*fl][*sl];
186 }
187 else
188 {
189 *fl = ffs(p->fl_bitmap & (~0 << (*fl + 1))) - 1;
190 if ( likely(*fl > 0) )
191 {
192 *sl = ffs(p->sl_bitmap[*fl]) - 1;
193 b = p->matrix[*fl][*sl];
194 }
195 }
197 return b;
198 }
200 /**
201 * Remove first free block(b) from free list with indexes (fl, sl).
202 */
203 static inline void EXTRACT_BLOCK_HDR(struct bhdr *b, struct xmem_pool *p, int fl,
204 int sl)
205 {
206 p->matrix[fl][sl] = b->ptr.free_ptr.next;
207 if ( p->matrix[fl][sl] )
208 {
209 p->matrix[fl][sl]->ptr.free_ptr.prev = NULL;
210 }
211 else
212 {
213 clear_bit(sl, &p->sl_bitmap[fl]);
214 if ( !p->sl_bitmap[fl] )
215 clear_bit(fl, &p->fl_bitmap);
216 }
217 b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
218 }
220 /**
221 * Removes block(b) from free list with indexes (fl, sl)
222 */
223 static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
224 int sl)
225 {
226 if ( b->ptr.free_ptr.next )
227 b->ptr.free_ptr.next->ptr.free_ptr.prev =
228 b->ptr.free_ptr.prev;
229 if ( b->ptr.free_ptr.prev )
230 b->ptr.free_ptr.prev->ptr.free_ptr.next =
231 b->ptr.free_ptr.next;
232 if ( p->matrix[fl][sl] == b )
233 {
234 p->matrix[fl][sl] = b->ptr.free_ptr.next;
235 if ( !p->matrix[fl][sl] )
236 {
237 clear_bit(sl, &p->sl_bitmap[fl]);
238 if ( !p->sl_bitmap[fl] )
239 clear_bit (fl, &p->fl_bitmap);
240 }
241 }
242 b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
243 }
245 /**
246 * Insert block(b) in free list with indexes (fl, sl)
247 */
248 static inline void INSERT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl, int sl)
249 {
250 b->ptr.free_ptr = (struct free_ptr) {NULL, p->matrix[fl][sl]};
251 if ( p->matrix[fl][sl] )
252 p->matrix[fl][sl]->ptr.free_ptr.prev = b;
253 p->matrix[fl][sl] = b;
254 set_bit(sl, &p->sl_bitmap[fl]);
255 set_bit(fl, &p->fl_bitmap);
256 }
258 /**
259 * Region is a virtually contiguous memory region and Pool is
260 * collection of such regions
261 */
262 static inline void ADD_REGION(void *region, unsigned long region_size,
263 struct xmem_pool *pool)
264 {
265 int fl, sl;
266 struct bhdr *b, *lb;
268 b = (struct bhdr *)(region);
269 b->prev_hdr = NULL;
270 b->size = ROUNDDOWN_SIZE(region_size - 2 * BHDR_OVERHEAD)
271 | FREE_BLOCK | PREV_USED;
272 MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl);
273 INSERT_BLOCK(b, pool, fl, sl);
274 /* The sentinel block: allows us to know when we're in the last block */
275 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
276 lb->prev_hdr = b;
277 lb->size = 0 | USED_BLOCK | PREV_FREE;
278 pool->used_size += BHDR_OVERHEAD; /* only sentinel block is "used" */
279 pool->num_regions++;
280 }
282 /*
283 * TLSF pool-based allocator start.
284 */
286 struct xmem_pool *xmem_pool_create(
287 const char *name,
288 xmem_pool_get_memory get_mem,
289 xmem_pool_put_memory put_mem,
290 unsigned long init_size,
291 unsigned long max_size,
292 unsigned long grow_size)
293 {
294 struct xmem_pool *pool;
295 int pool_bytes, pool_order;
297 BUG_ON(max_size && (max_size < init_size));
299 pool_bytes = ROUNDUP_SIZE(sizeof(*pool));
300 pool_order = get_order_from_bytes(pool_bytes);
302 pool = (void *)alloc_xenheap_pages(pool_order, 0);
303 if ( pool == NULL )
304 return NULL;
305 memset(pool, 0, pool_bytes);
307 /* Round to next page boundary */
308 init_size = ROUNDUP_PAGE(init_size);
309 max_size = ROUNDUP_PAGE(max_size);
310 grow_size = ROUNDUP_PAGE(grow_size);
312 /* pool global overhead not included in used size */
313 pool->used_size = 0;
315 pool->init_size = init_size;
316 pool->max_size = max_size;
317 pool->grow_size = grow_size;
318 pool->get_mem = get_mem;
319 pool->put_mem = put_mem;
320 strlcpy(pool->name, name, sizeof(pool->name));
322 /* always obtain init_region lazily now to ensure it is get_mem'd
323 * in the same "context" as all other regions */
325 spin_lock_init(&pool->lock);
327 spin_lock(&pool_list_lock);
328 list_add_tail(&pool->list, &pool_list_head);
329 spin_unlock(&pool_list_lock);
331 return pool;
332 }
334 unsigned long xmem_pool_get_used_size(struct xmem_pool *pool)
335 {
336 return pool->used_size;
337 }
339 unsigned long xmem_pool_get_total_size(struct xmem_pool *pool)
340 {
341 unsigned long total;
342 total = ROUNDUP_SIZE(sizeof(*pool))
343 + pool->init_size
344 + (pool->num_regions - 1) * pool->grow_size;
345 return total;
346 }
348 void xmem_pool_destroy(struct xmem_pool *pool)
349 {
350 int pool_bytes, pool_order;
352 if ( pool == NULL )
353 return;
355 /* User is destroying without ever allocating from this pool */
356 if ( xmem_pool_get_used_size(pool) == BHDR_OVERHEAD )
357 {
358 ASSERT(!pool->init_region);
359 pool->used_size -= BHDR_OVERHEAD;
360 }
362 /* Check for memory leaks in this pool */
363 if ( xmem_pool_get_used_size(pool) )
364 printk("memory leak in pool: %s (%p). "
365 "%lu bytes still in use.\n",
366 pool->name, pool, xmem_pool_get_used_size(pool));
368 spin_lock(&pool_list_lock);
369 list_del_init(&pool->list);
370 spin_unlock(&pool_list_lock);
372 pool_bytes = ROUNDUP_SIZE(sizeof(*pool));
373 pool_order = get_order_from_bytes(pool_bytes);
374 free_xenheap_pages(pool,pool_order);
375 }
377 void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool)
378 {
379 struct bhdr *b, *b2, *next_b, *region;
380 int fl, sl;
381 unsigned long tmp_size;
383 if ( pool->init_region == NULL )
384 {
385 if ( (region = pool->get_mem(pool->init_size)) == NULL )
386 goto out;
387 ADD_REGION(region, pool->init_size, pool);
388 pool->init_region = region;
389 }
391 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
392 /* Rounding up the requested size and calculating fl and sl */
394 spin_lock(&pool->lock);
395 retry_find:
396 MAPPING_SEARCH(&size, &fl, &sl);
398 /* Searching a free block */
399 if ( !(b = FIND_SUITABLE_BLOCK(pool, &fl, &sl)) )
400 {
401 /* Not found */
402 if ( size > (pool->grow_size - 2 * BHDR_OVERHEAD) )
403 goto out_locked;
404 if ( pool->max_size && (pool->init_size +
405 pool->num_regions * pool->grow_size
406 > pool->max_size) )
407 goto out_locked;
408 spin_unlock(&pool->lock);
409 if ( (region = pool->get_mem(pool->grow_size)) == NULL )
410 goto out;
411 spin_lock(&pool->lock);
412 ADD_REGION(region, pool->grow_size, pool);
413 goto retry_find;
414 }
415 EXTRACT_BLOCK_HDR(b, pool, fl, sl);
417 /*-- found: */
418 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
419 /* Should the block be split? */
420 tmp_size = (b->size & BLOCK_SIZE_MASK) - size;
421 if ( tmp_size >= sizeof(struct bhdr) )
422 {
423 tmp_size -= BHDR_OVERHEAD;
424 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
426 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
427 b2->prev_hdr = b;
429 next_b->prev_hdr = b2;
431 MAPPING_INSERT(tmp_size, &fl, &sl);
432 INSERT_BLOCK(b2, pool, fl, sl);
434 b->size = size | (b->size & PREV_STATE);
435 }
436 else
437 {
438 next_b->size &= (~PREV_FREE);
439 b->size &= (~FREE_BLOCK); /* Now it's used */
440 }
442 pool->used_size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
444 spin_unlock(&pool->lock);
445 return (void *)b->ptr.buffer;
447 /* Failed alloc */
448 out_locked:
449 spin_unlock(&pool->lock);
451 out:
452 return NULL;
453 }
455 void xmem_pool_free(void *ptr, struct xmem_pool *pool)
456 {
457 struct bhdr *b, *tmp_b;
458 int fl = 0, sl = 0;
460 if ( unlikely(ptr == NULL) )
461 return;
463 b = (struct bhdr *)((char *) ptr - BHDR_OVERHEAD);
465 spin_lock(&pool->lock);
466 b->size |= FREE_BLOCK;
467 pool->used_size -= (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
468 b->ptr.free_ptr = (struct free_ptr) { NULL, NULL};
469 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
470 if ( tmp_b->size & FREE_BLOCK )
471 {
472 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl);
473 EXTRACT_BLOCK(tmp_b, pool, fl, sl);
474 b->size += (tmp_b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
475 }
476 if ( b->size & PREV_FREE )
477 {
478 tmp_b = b->prev_hdr;
479 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE_MASK, &fl, &sl);
480 EXTRACT_BLOCK(tmp_b, pool, fl, sl);
481 tmp_b->size += (b->size & BLOCK_SIZE_MASK) + BHDR_OVERHEAD;
482 b = tmp_b;
483 }
484 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE_MASK);
485 tmp_b->prev_hdr = b;
487 MAPPING_INSERT(b->size & BLOCK_SIZE_MASK, &fl, &sl);
489 if ( (b->prev_hdr == NULL) && ((tmp_b->size & BLOCK_SIZE_MASK) == 0) )
490 {
491 pool->put_mem(b);
492 pool->num_regions--;
493 pool->used_size -= BHDR_OVERHEAD; /* sentinel block header */
494 goto out;
495 }
497 INSERT_BLOCK(b, pool, fl, sl);
499 tmp_b->size |= PREV_FREE;
500 tmp_b->prev_hdr = b;
501 out:
502 spin_unlock(&pool->lock);
503 }
505 int xmem_pool_maxalloc(struct xmem_pool *pool)
506 {
507 return pool->grow_size - (2 * BHDR_OVERHEAD);
508 }
510 /*
511 * Glue for xmalloc().
512 */
514 static struct xmem_pool *xenpool;
516 static void *xmalloc_pool_get(unsigned long size)
517 {
518 ASSERT(size == PAGE_SIZE);
519 return alloc_xenheap_page();
520 }
522 static void xmalloc_pool_put(void *p)
523 {
524 free_xenheap_page(p);
525 }
527 static void *xmalloc_whole_pages(unsigned long size)
528 {
529 struct bhdr *b;
530 unsigned int pageorder = get_order_from_bytes(size + BHDR_OVERHEAD);
532 b = alloc_xenheap_pages(pageorder, 0);
533 if ( b == NULL )
534 return NULL;
536 b->size = (1 << (pageorder + PAGE_SHIFT));
537 return (void *)b->ptr.buffer;
538 }
540 static void tlsf_init(void)
541 {
542 INIT_LIST_HEAD(&pool_list_head);
543 spin_lock_init(&pool_list_lock);
544 xenpool = xmem_pool_create(
545 "xmalloc", xmalloc_pool_get, xmalloc_pool_put,
546 PAGE_SIZE, 0, PAGE_SIZE);
547 BUG_ON(!xenpool);
548 }
550 /*
551 * xmalloc()
552 */
554 void *_xmalloc(unsigned long size, unsigned long align)
555 {
556 void *p;
557 u32 pad;
559 ASSERT(!in_irq());
561 ASSERT((align & (align - 1)) == 0);
562 if ( align < MEM_ALIGN )
563 align = MEM_ALIGN;
564 size += align - MEM_ALIGN;
566 if ( !xenpool )
567 tlsf_init();
569 if ( size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) )
570 p = xmalloc_whole_pages(size);
571 else
572 p = xmem_pool_alloc(size, xenpool);
574 /* Add alignment padding. */
575 if ( (pad = -(long)p & (align - 1)) != 0 )
576 {
577 char *q = (char *)p + pad;
578 struct bhdr *b = (struct bhdr *)(q - BHDR_OVERHEAD);
579 ASSERT(q > (char *)p);
580 b->size = pad | 1;
581 p = q;
582 }
584 ASSERT(((unsigned long)p & (align - 1)) == 0);
585 return p;
586 }
588 void xfree(void *p)
589 {
590 struct bhdr *b;
592 ASSERT(!in_irq());
594 if ( p == NULL )
595 return;
597 /* Strip alignment padding. */
598 b = (struct bhdr *)((char *) p - BHDR_OVERHEAD);
599 if ( b->size & 1 )
600 {
601 p = (char *)p - (b->size & ~1u);
602 b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
603 ASSERT(!(b->size & 1));
604 }
606 if ( b->size >= (PAGE_SIZE - (2*BHDR_OVERHEAD)) )
607 free_xenheap_pages((void *)b, get_order_from_bytes(b->size));
608 else
609 xmem_pool_free(p, xenpool);
610 }