1 /* Copyright (c) 2007, Sandia National Laboratories */
3 #include <lwk/kernel.h>
6 #include <lwk/bootmem.h>
10 * Each free block has one of these structures at its head. The link member
11 * provides linkage for the mp->avail[order] free list, where order is the
12 * size of the free block.
15 struct list_head link;
21 * Converts a block address to its block index in the specified buddy allocator.
22 * A block's index is used to find the block's tag bit, mp->tag_bits[block_id].
25 block_to_id(struct buddy_mempool *mp, struct block *block)
27 unsigned long block_id =
28 ((unsigned long)block - mp->base_addr) >> mp->min_order;
29 BUG_ON(block_id >= mp->num_blocks);
35 * Marks a block as free by setting its tag bit to one.
38 mark_available(struct buddy_mempool *mp, struct block *block)
40 __set_bit(block_to_id(mp, block), mp->tag_bits);
45 * Marks a block as allocated by setting its tag bit to zero.
48 mark_allocated(struct buddy_mempool *mp, struct block *block)
50 __clear_bit(block_to_id(mp, block), mp->tag_bits);
55 * Returns true if block is free, false if it is allocated.
58 is_available(struct buddy_mempool *mp, struct block *block)
60 return test_bit(block_to_id(mp, block), mp->tag_bits);
65 * Returns the address of the block's buddy block.
68 find_buddy(struct buddy_mempool *mp, struct block *block, unsigned long order)
73 BUG_ON((unsigned long)block < mp->base_addr);
75 /* Fixup block address to be zero-relative */
76 _block = (unsigned long)block - mp->base_addr;
78 /* Calculate buddy in zero-relative space */
79 _buddy = _block ^ (1UL << order);
81 /* Return the buddy's address */
82 return (void *)(_buddy + mp->base_addr);
87 * Initializes a buddy system memory allocator object.
90 * [IN] base_addr: Base address of the memory pool.
91 * [IN] pool_order: Size of the memory pool (2^pool_order bytes).
92 * [IN] min_order: Minimum allocatable block size (2^min_order bytes).
95 * Success: Pointer to an initialized buddy system memory allocator.
98 * NOTE: The min_order argument is provided as an optimization. Since one tag
99 * bit is required for each minimum-sized block, large memory pools that
100 * allow order 0 allocations will use large amounts of memory. Specifying
101 * a min_order of 5 (32 bytes), for example, reduces the number of tag
104 struct buddy_mempool *
106 unsigned long base_addr,
107 unsigned long pool_order,
108 unsigned long min_order
111 struct buddy_mempool *mp;
114 /* Smallest block size must be big enough to hold a block structure */
115 if ((1UL << min_order) < sizeof(struct block))
116 min_order = ilog2( roundup_pow_of_two(sizeof(struct block)) );
118 /* The minimum block order must be smaller than the pool order */
119 if (min_order > pool_order)
122 mp = alloc_bootmem(sizeof(struct buddy_mempool));
124 mp->base_addr = base_addr;
125 mp->pool_order = pool_order;
126 mp->min_order = min_order;
128 /* Allocate a list for every order up to the maximum allowed order */
129 mp->avail = alloc_bootmem((pool_order + 1) * sizeof(struct list_head));
131 /* Initially all lists are empty */
132 for (i = 0; i <= pool_order; i++)
133 INIT_LIST_HEAD(&mp->avail[i]);
135 /* Allocate a bitmap with 1 bit per minimum-sized block */
136 mp->num_blocks = (1UL << pool_order) / (1UL << min_order);
137 mp->tag_bits = alloc_bootmem(
138 BITS_TO_LONGS(mp->num_blocks) * sizeof(long)
141 /* Initially mark all minimum-sized blocks as allocated */
142 bitmap_zero(mp->tag_bits, mp->num_blocks);
149 * Allocates a block of memory of the requested size (2^order bytes).
152 * [IN] mp: Buddy system memory allocator object.
153 * [IN] order: Block size to allocate (2^order bytes).
156 * Success: Pointer to the start of the allocated memory block.
160 buddy_alloc(struct buddy_mempool *mp, unsigned long order)
163 struct list_head *list;
165 struct block *buddy_block;
168 BUG_ON(order > mp->pool_order);
170 /* Fixup requested order to be at least the minimum supported */
171 if (order < mp->min_order)
172 order = mp->min_order;
174 for (j = order; j <= mp->pool_order; j++) {
176 /* Try to allocate the first block in the order j list */
177 list = &mp->avail[j];
178 if (list_empty(list))
180 block = list_entry(list->next, struct block, link);
181 list_del(&block->link);
182 mark_allocated(mp, block);
184 /* Trim if a higher order block than necessary was allocated */
187 buddy_block = (struct block *)((unsigned long)block + (1UL << j));
188 buddy_block->order = j;
189 mark_available(mp, buddy_block);
190 list_add(&buddy_block->link, &mp->avail[j]);
201 * Returns a block of memory to the buddy system memory allocator.
204 * [IN] mp: Buddy system memory allocator object.
205 * [IN] addr: Address of memory block to free.
206 * [IN] order: Size of the memory block (2^order bytes).
209 buddy_free(struct buddy_mempool *mp, void *addr, unsigned long order)
215 BUG_ON(order > mp->pool_order);
217 /* Fixup requested order to be at least the minimum supported */
218 if (order < mp->min_order)
219 order = mp->min_order;
221 /* Overlay block structure on the memory block being freed */
223 BUG_ON(is_available(mp, block));
225 /* Coalesce as much as possible with adjacent free buddy blocks */
226 while (order < mp->pool_order) {
227 /* Determine our buddy block's address */
228 buddy = find_buddy(mp, block, order);
230 /* Make sure buddy is available and has the same size as us */
231 if (!is_available(mp, buddy))
233 if (is_available(mp, buddy) && (buddy->order != order))
236 /* OK, we're good to go... buddy merge! */
237 list_del(&buddy->link);
241 block->order = order;
244 /* Add the (possibly coalesced) block to the appropriate free list */
245 block->order = order;
246 mark_available(mp, block);
247 list_add(&block->link, &mp->avail[order]);
252 * Dumps the state of a buddy system memory allocator object to the console.
255 buddy_dump_mempool(struct buddy_mempool *mp)
258 unsigned long num_blocks;
259 struct list_head *entry;
261 printk(KERN_DEBUG "DUMP OF BUDDY MEMORY POOL:\n");
263 for (i = mp->min_order; i <= mp->pool_order; i++) {
265 /* Count the number of memory blocks in the list */
267 list_for_each(entry, &mp->avail[i])
270 printk(KERN_DEBUG " order %2lu: %lu free blocks\n", i, num_blocks);