kitten/mm/buddy.c

   1 /* Copyright (c) 2007, Sandia National Laboratories */
   2
   3 #include <lwk/kernel.h>
   4 #include <lwk/log2.h>
   5 #include <lwk/buddy.h>
   6 #include <lwk/bootmem.h>
   7
   8
   9 /**
  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.
  13  */
  14 struct block {
  15         struct list_head link;
  16         unsigned long    order;
  17 };
  18
  19
  20 /**
  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].
  23  */
  24 static unsigned long
  25 block_to_id(struct buddy_mempool *mp, struct block *block)
  26 {
  27         unsigned long block_id =
  28                 ((unsigned long)block - mp->base_addr) >> mp->min_order;
  29         BUG_ON(block_id >= mp->num_blocks);
  30         return block_id;
  31 }
  32
  33
  34 /**
  35  * Marks a block as free by setting its tag bit to one.
  36  */
  37 static void
  38 mark_available(struct buddy_mempool *mp, struct block *block)
  39 {
  40         __set_bit(block_to_id(mp, block), mp->tag_bits);
  41 }
  42
  43
  44 /**
  45  * Marks a block as allocated by setting its tag bit to zero.
  46  */
  47 static void
  48 mark_allocated(struct buddy_mempool *mp, struct block *block)
  49 {
  50         __clear_bit(block_to_id(mp, block), mp->tag_bits);
  51 }
  52
  53
  54 /**
  55  * Returns true if block is free, false if it is allocated.
  56  */
  57 static int
  58 is_available(struct buddy_mempool *mp, struct block *block)
  59 {
  60         return test_bit(block_to_id(mp, block), mp->tag_bits);
  61 }
  62
  63
  64 /**
  65  * Returns the address of the block's buddy block.
  66  */
  67 static void *
  68 find_buddy(struct buddy_mempool *mp, struct block *block, unsigned long order)
  69 {
  70         unsigned long _block;
  71         unsigned long _buddy;
  72
  73         BUG_ON((unsigned long)block < mp->base_addr);
  74
  75         /* Fixup block address to be zero-relative */
  76         _block = (unsigned long)block - mp->base_addr;
  77
  78         /* Calculate buddy in zero-relative space */
  79         _buddy = _block ^ (1UL << order);
  80
  81         /* Return the buddy's address */
  82         return (void *)(_buddy + mp->base_addr);
  83 }
  84
  85
  86 /**
  87  * Initializes a buddy system memory allocator object.
  88  *
  89  * Arguments:
  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).
  93  *
  94  * Returns:
  95  *       Success: Pointer to an initialized buddy system memory allocator.
  96  *       Failure: NULL
  97  *
  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
 102  *       bits by 32x.
 103  */
 104 struct buddy_mempool *
 105 buddy_init(
 106         unsigned long base_addr,
 107         unsigned long pool_order,
 108         unsigned long min_order
 109 )
 110 {
 111         struct buddy_mempool *mp;
 112         unsigned long i;
 113
 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)) );
 117
 118         /* The minimum block order must be smaller than the pool order */
 119         if (min_order > pool_order)
 120                 return NULL;
 121
 122         mp = alloc_bootmem(sizeof(struct buddy_mempool));
 123
 124         mp->base_addr  = base_addr;
 125         mp->pool_order = pool_order;
 126         mp->min_order  = min_order;
 127
 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));
 130
 131         /* Initially all lists are empty */
 132         for (i = 0; i <= pool_order; i++)
 133                 INIT_LIST_HEAD(&mp->avail[i]);
 134
 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)
 139                          );
 140
 141         /* Initially mark all minimum-sized blocks as allocated */
 142         bitmap_zero(mp->tag_bits, mp->num_blocks);
 143
 144         return mp;
 145 }
 146
 147
 148 /**
 149  * Allocates a block of memory of the requested size (2^order bytes).
 150  *
 151  * Arguments:
 152  *       [IN] mp:    Buddy system memory allocator object.
 153  *       [IN] order: Block size to allocate (2^order bytes).
 154  *
 155  * Returns:
 156  *       Success: Pointer to the start of the allocated memory block.
 157  *       Failure: NULL
 158  */
 159 void *
 160 buddy_alloc(struct buddy_mempool *mp, unsigned long order)
 161 {
 162         unsigned long j;
 163         struct list_head *list;
 164         struct block *block;
 165         struct block *buddy_block;
 166
 167         BUG_ON(mp == NULL);
 168         BUG_ON(order > mp->pool_order);
 169
 170         /* Fixup requested order to be at least the minimum supported */
 171         if (order < mp->min_order)
 172                 order = mp->min_order;
 173
 174         for (j = order; j <= mp->pool_order; j++) {
 175
 176                 /* Try to allocate the first block in the order j list */
 177                 list = &mp->avail[j];
 178                 if (list_empty(list))
 179                         continue;
 180                 block = list_entry(list->next, struct block, link);
 181                 list_del(&block->link);
 182                 mark_allocated(mp, block);
 183
 184                 /* Trim if a higher order block than necessary was allocated */
 185                 while (j > order) {
 186                         --j;
 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]);
 191                 }
 192
 193                 return block;
 194         }
 195
 196         return NULL;
 197 }
 198
 199
 200 /**
 201  * Returns a block of memory to the buddy system memory allocator.
 202  *
 203  * Arguments:
 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).
 207  */
 208 void
 209 buddy_free(struct buddy_mempool *mp, void *addr, unsigned long order)
 210 {
 211         struct block *block;
 212         struct block *buddy;
 213
 214         BUG_ON(mp == NULL);
 215         BUG_ON(order > mp->pool_order);
 216
 217         /* Fixup requested order to be at least the minimum supported */
 218         if (order < mp->min_order)
 219                 order = mp->min_order;
 220
 221         /* Overlay block structure on the memory block being freed */
 222         block = addr;
 223         BUG_ON(is_available(mp, block));
 224
 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);
 229
 230                 /* Make sure buddy is available and has the same size as us */
 231                 if (!is_available(mp, buddy))
 232                         break;
 233                 if (is_available(mp, buddy) && (buddy->order != order))
 234                         break;
 235
 236                 /* OK, we're good to go... buddy merge! */
 237                 list_del(&buddy->link);
 238                 if (buddy < block)
 239                         block = buddy;
 240                 ++order;
 241                 block->order = order;
 242         }
 243
 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]);
 248 }
 249
 250
 251 /**
 252  * Dumps the state of a buddy system memory allocator object to the console.
 253  */
 254 void
 255 buddy_dump_mempool(struct buddy_mempool *mp)
 256 {
 257         unsigned long i;
 258         unsigned long num_blocks;
 259         struct list_head *entry;
 260
 261         printk(KERN_DEBUG "DUMP OF BUDDY MEMORY POOL:\n");
 262
 263         for (i = mp->min_order; i <= mp->pool_order; i++) {
 264
 265                 /* Count the number of memory blocks in the list */
 266                 num_blocks = 0;
 267                 list_for_each(entry, &mp->avail[i])
 268                         ++num_blocks;
 269
 270                 printk(KERN_DEBUG "  order %2lu: %lu free blocks\n", i, num_blocks);
 271         }
 272 }
 273
 274