linux_module/buddy.c

   1 /* Copyright (c) 2007, Sandia National Laboratories */
   2 /* Modified by Jack Lange, 2012 */
   3
   4 #include <linux/module.h>
   5 #include <linux/slab.h>
   6 #include <linux/log2.h>
   7 #include "buddy.h"
   8 #include "palacios.h"
   9
  10 #include <linux/proc_fs.h>
  11 #include <linux/seq_file.h>
  12
  13
  14 /**
  15  * Converts a block address to its block index in the specified buddy allocator.
  16  * A block's index is used to find the block's tag bit, mp->tag_bits[block_id].
  17  */
  18 static unsigned long
  19 block_to_id(struct buddy_mempool *mp, struct block *block)
  20 {
  21     unsigned long block_id =
  22         ((unsigned long)__pa(block) - mp->base_addr) >> mp->zone->min_order;
  23     BUG_ON(block_id >= mp->num_blocks);
  24     return block_id;
  25 }
  26
  27
  28 /**
  29  * Marks a block as free by setting its tag bit to one.
  30  */
  31 static void
  32 mark_available(struct buddy_mempool *mp, struct block *block)
  33 {
  34     __set_bit(block_to_id(mp, block), mp->tag_bits);
  35 }
  36
  37
  38 /**
  39  * Marks a block as allocated by setting its tag bit to zero.
  40  */
  41 static void
  42 mark_allocated(struct buddy_mempool *mp, struct block *block)
  43 {
  44     __clear_bit(block_to_id(mp, block), mp->tag_bits);
  45 }
  46
  47
  48 /**
  49  * Returns true if block is free, false if it is allocated.
  50  */
  51 static int
  52 is_available(struct buddy_mempool *mp, struct block *block)
  53 {
  54     return test_bit(block_to_id(mp, block), mp->tag_bits);
  55 }
  56
  57
  58 /**
  59  * Returns the address of the block's buddy block.
  60  */
  61 static void *
  62 find_buddy(struct buddy_mempool *mp, struct block *block, unsigned long order)
  63 {
  64     unsigned long _block;
  65     unsigned long _buddy;
  66
  67     BUG_ON((unsigned long)__pa(block) < mp->base_addr);
  68
  69     /* Fixup block address to be zero-relative */
  70     _block = (unsigned long)__pa(block) - mp->base_addr;
  71
  72     /* Calculate buddy in zero-relative space */
  73     _buddy = _block ^ (1UL << order);
  74
  75     /* Return the buddy's address */
  76     return (void *)(_buddy + __va(mp->base_addr));
  77 }
  78
  79
  80 static inline uintptr_t pool_end_addr(struct buddy_mempool * pool) {
  81     return pool->base_addr + (1UL << pool->pool_order);
  82 }
  83
  84
  85 static struct buddy_mempool *
  86 find_mempool(struct buddy_memzone * zone, uintptr_t addr) {
  87     struct rb_node * n = zone->mempools.rb_node;
  88     struct buddy_mempool * pool = NULL;
  89
  90     while (n) {
  91         pool = rb_entry(n, struct buddy_mempool, tree_node);
  92
  93         if (addr < pool->base_addr) {
  94             n = n->rb_left;
  95         } else if (addr >= pool_end_addr(pool)) {
  96             n = n->rb_right;
  97         } else {
  98             return pool;
  99         }
 100     }
 101
 102     return NULL;
 103 }
 104
 105
 106
 107 static int
 108 insert_mempool(struct buddy_memzone * zone,
 109                struct buddy_mempool * pool) {
 110     struct rb_node ** p = &(zone->mempools.rb_node);
 111     struct rb_node * parent = NULL;
 112     struct buddy_mempool * tmp_pool;
 113
 114     while (*p) {
 115         parent = *p;
 116         tmp_pool = rb_entry(parent, struct buddy_mempool, tree_node);
 117
 118         if (pool_end_addr(pool) <= tmp_pool->base_addr) {
 119             p = &(*p)->rb_left;
 120         } else if (pool->base_addr >= pool_end_addr(tmp_pool)) {
 121             p = &(*p)->rb_right;
 122         } else {
 123             return -1;
 124         }
 125     }
 126
 127     rb_link_node(&(pool->tree_node), parent, p);
 128     rb_insert_color(&(pool->tree_node), &(zone->mempools));
 129     zone->num_pools++;
 130
 131     return 0;
 132 }
 133
 134
 135
 136
 137 /* This adds a pool of a given size to a buddy allocated zone
 138  */
 139
 140 int buddy_add_pool(struct buddy_memzone * zone,
 141                    unsigned long base_addr,
 142                    unsigned long pool_order) {
 143     struct buddy_mempool * mp = NULL;
 144     unsigned long flags = 0;
 145     int ret = 0;
 146
 147     if (pool_order > zone->max_order) {
 148         ERROR("Pool order size is larger than max allowable zone size (pool_order=%lu) (max_order=%lu)\n", pool_order, zone->max_order);
 149         return -1;
 150     } else if (pool_order < zone->min_order) {
 151         ERROR("Pool order is smaller than min allowable zone size (pool_order=%lu) (min_order=%lu)\n", pool_order, zone->min_order);
 152         return -1;
 153     }
 154
 155     mp = kmalloc_node(sizeof(struct buddy_mempool), GFP_KERNEL, zone->node_id);
 156
 157     if (IS_ERR(mp)) {
 158         ERROR("Could not allocate mempool\n");
 159         return -1;
 160     }
 161
 162     mp->base_addr  = base_addr;
 163     mp->pool_order = pool_order;
 164     mp->zone = zone;
 165     mp->num_free_blocks = 0;
 166
 167     /* Allocate a bitmap with 1 bit per minimum-sized block */
 168     mp->num_blocks = (1UL << pool_order) / (1UL << zone->min_order);
 169
 170     mp->tag_bits   = kmalloc_node(
 171                                   BITS_TO_LONGS(mp->num_blocks) * sizeof(long), GFP_KERNEL, zone->node_id
 172                                   );
 173
 174     /* Initially mark all minimum-sized blocks as allocated */
 175     bitmap_zero(mp->tag_bits, mp->num_blocks);
 176
 177     spin_lock_irqsave(&(zone->lock), flags);
 178     ret = insert_mempool(zone, mp);
 179     spin_unlock_irqrestore(&(zone->lock), flags);
 180
 181     if (ret == -1) {
 182         ERROR("Error: Could not insert mempool into zone\n");
 183         kfree(mp->tag_bits);
 184         kfree(mp);
 185
 186         return -1;
 187     }
 188
 189     buddy_free(zone, base_addr, pool_order);
 190
 191     printk("Added memory pool (addr=%p), order=%lu\n", (void *)base_addr, pool_order);
 192
 193     return 0;
 194 }
 195
 196
 197 /**
 198  * Removes a mempool from a zone,
 199  * assumes the zone lock is already held
 200  */
 201 static int __buddy_remove_mempool(struct buddy_memzone * zone,
 202                                   unsigned long base_addr,
 203                                   unsigned char force) {
 204
 205     struct buddy_mempool * pool = NULL;
 206     struct block * block = NULL;
 207
 208     pool = find_mempool(zone, base_addr);
 209
 210     if (pool == NULL) {
 211         ERROR("Could not find mempool with base address (%p)\n", (void *)base_addr);
 212         return -1;
 213     }
 214
 215     if (!bitmap_empty(pool->tag_bits, pool->num_blocks)) {
 216         ERROR("Trying to remove an in use memory pool\n");
 217         return -1;
 218     }
 219
 220     block = (struct block *)__va(pool->base_addr);
 221
 222     list_del(&(block->link));
 223     rb_erase(&(pool->tree_node), &(zone->mempools));
 224
 225     kfree(pool->tag_bits);
 226     kfree(pool);
 227
 228     zone->num_pools--;
 229
 230     return 0;
 231 }
 232
 233 int buddy_remove_pool(struct buddy_memzone * zone,
 234                          unsigned long base_addr,
 235                          unsigned char force) {
 236     unsigned long flags = 0;
 237     int ret = 0;
 238
 239     spin_lock_irqsave(&(zone->lock), flags);
 240     ret = __buddy_remove_mempool(zone, base_addr, force);
 241     spin_unlock_irqrestore(&(zone->lock), flags);
 242
 243     return ret;
 244 }
 245
 246
 247
 248
 249 /**
 250  * Allocates a block of memory of the requested size (2^order bytes).
 251  *
 252  * Arguments:
 253  *       [IN] mp:    Buddy system memory allocator object.
 254  *       [IN] order: Block size to allocate (2^order bytes).
 255  *
 256  * Returns:
 257  *       Success: Pointer to the start of the allocated memory block.
 258  *       Failure: NULL
 259  */
 260 uintptr_t
 261 buddy_alloc(struct buddy_memzone *zone, unsigned long order)
 262 {
 263     unsigned long j;
 264     struct buddy_mempool * mp = NULL;
 265     struct list_head * list = NULL;
 266     struct block * block = NULL;
 267     struct block * buddy_block = NULL;
 268     unsigned long flags = 0;
 269
 270     BUG_ON(zone == NULL);
 271     BUG_ON(order > zone->max_order);
 272
 273     /* Fixup requested order to be at least the minimum supported */
 274     if (order < zone->min_order) {
 275         order = zone->min_order;
 276     }
 277
 278     printk("zone=%p, order=%lu\n", zone, order);
 279
 280     spin_lock_irqsave(&(zone->lock), flags);
 281
 282     for (j = order; j <= zone->max_order; j++) {
 283
 284         printk("Order iter=%lu\n", j);
 285
 286         /* Try to allocate the first block in the order j list */
 287         list = &zone->avail[j];
 288
 289         if (list_empty(list))
 290             continue;
 291
 292         block = list_entry(list->next, struct block, link);
 293         list_del(&(block->link));
 294
 295         mp = block->mp;
 296
 297         mark_allocated(mp, block);
 298
 299         printk("pool=%p, block=%p, order=%lu, j=%lu\n", mp, block, order, j);
 300
 301         /*
 302         spin_unlock_irqrestore(&(zone->lock), flags);
 303         return 0;
 304         */
 305
 306         /* Trim if a higher order block than necessary was allocated */
 307         while (j > order) {
 308             --j;
 309             buddy_block = (struct block *)((unsigned long)block + (1UL << j));
 310             buddy_block->mp = mp;
 311             buddy_block->order = j;
 312             mark_available(mp, buddy_block);
 313             list_add(&(buddy_block->link), &(zone->avail[j]));
 314         }
 315
 316         mp->num_free_blocks -= (1UL << (order - zone->min_order));
 317
 318         spin_unlock_irqrestore(&(zone->lock), flags);
 319
 320         return __pa(block);
 321     }
 322
 323     spin_unlock_irqrestore(&(zone->lock), flags);
 324
 325     return (uintptr_t)NULL;
 326 }
 327
 328
 329 /**
 330  * Returns a block of memory to the buddy system memory allocator.
 331  */
 332 void
 333 buddy_free(
 334         //!    Buddy system memory allocator object.
 335         struct buddy_memzone *  zone,
 336         //!  Address of memory block to free.
 337         uintptr_t addr,
 338         //! Size of the memory block (2^order bytes).
 339         unsigned long           order
 340 )
 341 {
 342     struct block * block  = NULL;
 343     struct buddy_mempool * pool = NULL;
 344     unsigned long flags = 0;
 345
 346     BUG_ON(zone == NULL);
 347     BUG_ON(order > zone->max_order);
 348
 349
 350     if ((addr & ((1UL << zone->min_order) - 1)) != 0) {
 351         ERROR("Attempting to free an invalid memory address (%p)\n", (void *)addr);
 352         BUG_ON(1);
 353     }
 354
 355
 356     /* Fixup requested order to be at least the minimum supported */
 357     if (order < zone->min_order) {
 358         order = zone->min_order;
 359     }
 360
 361
 362     spin_lock_irqsave(&(zone->lock), flags);
 363
 364     pool = find_mempool(zone, addr);
 365
 366     if ((pool == NULL) || (order > pool->pool_order)) {
 367         WARNING("Attempted to free an invalid page address (%p)\n", (void *)addr);
 368         spin_unlock_irqrestore(&(zone->lock), flags);
 369         return;
 370     }
 371
 372
 373     /* Overlay block structure on the memory block being freed */
 374     block = (struct block *) __va(addr);
 375
 376     if (is_available(pool, block)) {
 377         printk(KERN_ERR "Error: Freeing an available block\n");
 378         spin_unlock_irqrestore(&(zone->lock), flags);
 379         return;
 380     }
 381
 382     pool->num_free_blocks += (1UL << (order - zone->min_order));
 383
 384     /* Coalesce as much as possible with adjacent free buddy blocks */
 385     while (order < pool->pool_order) {
 386         /* Determine our buddy block's address */
 387         struct block * buddy = find_buddy(pool, block, order);
 388
 389         /* Make sure buddy is available and has the same size as us */
 390         if (!is_available(pool, buddy))
 391             break;
 392         if (is_available(pool, buddy) && (buddy->order != order))
 393             break;
 394
 395         /* OK, we're good to go... buddy merge! */
 396         list_del(&buddy->link);
 397         if (buddy < block)
 398             block = buddy;
 399         ++order;
 400         block->order = order;
 401     }
 402
 403     /* Add the (possibly coalesced) block to the appropriate free list */
 404     block->order = order;
 405     block->mp = pool;
 406     mark_available(pool, block);
 407     list_add(&(block->link), &(zone->avail[order]));
 408
 409     spin_unlock_irqrestore(&(zone->lock), flags);
 410 }
 411
 412
 413
 414
 415 /**
 416  * Dumps the state of a buddy system memory allocator object to the console.
 417  */
 418 static int
 419 zone_mem_show(struct seq_file * s, void * v) {
 420     struct buddy_memzone * zone = s->private;
 421     unsigned long i;
 422     unsigned long num_blocks;
 423     struct list_head * entry = NULL;
 424     unsigned long flags = 0;
 425
 426
 427     if (!zone) {
 428         seq_printf(s, "Null Zone Pointer!!\n");
 429         return 0;
 430     }
 431
 432     seq_printf(s, "DUMP OF BUDDY MEMORY ZONE:\n");
 433     seq_printf(s, "  Zone Max Order=%lu, Min Order=%lu\n",
 434            zone->max_order, zone->min_order);
 435
 436     spin_lock_irqsave(&(zone->lock), flags);
 437
 438     for (i = zone->min_order; i <= zone->max_order; i++) {
 439
 440         /* Count the number of memory blocks in the list */
 441         num_blocks = 0;
 442         list_for_each(entry, &zone->avail[i]) {
 443             ++num_blocks;
 444         }
 445
 446         seq_printf(s, "  order %2lu: %lu free blocks\n", i, num_blocks);
 447     }
 448
 449
 450     seq_printf(s, " %lu memory pools\n", zone->num_pools);
 451     // list pools in zone
 452     {
 453         struct rb_node * node = rb_first(&(zone->mempools));
 454         struct buddy_mempool * pool = NULL;
 455
 456         while (node) {
 457             pool = rb_entry(node, struct buddy_mempool, tree_node);
 458
 459             seq_printf(s, "    Base Addr=%p, order=%lu, size=%lu, free=%lu\n",
 460                        (void *)pool->base_addr, pool->pool_order, (1UL << pool->pool_order),
 461                        pool->num_free_blocks << zone->min_order);
 462
 463
 464             node = rb_next(node);
 465         }
 466     }
 467
 468     spin_unlock_irqrestore(&(zone->lock), flags);
 469
 470     return 0;
 471 }
 472
 473
 474 static int zone_proc_open(struct inode * inode, struct file * filp) {
 475     struct proc_dir_entry * proc_entry = PDE(inode);
 476     printk("proc_entry at %p, data at %p\n", proc_entry, proc_entry->data);
 477     return single_open(filp, zone_mem_show, proc_entry->data);
 478 }
 479
 480
 481 static struct file_operations zone_proc_ops = {
 482     .owner = THIS_MODULE,
 483     .open = zone_proc_open,
 484     .read = seq_read,
 485     .llseek = seq_lseek,
 486     .release = single_release,
 487 };
 488
 489
 490
 491 void buddy_deinit(struct buddy_memzone * zone) {
 492     unsigned long flags;
 493
 494     spin_lock_irqsave(&(zone->lock), flags);
 495
 496     // for each pool, free it
 497
 498     spin_unlock_irqrestore(&(zone->lock), flags);
 499
 500     {
 501         char proc_file_name[128];
 502
 503         memset(proc_file_name, 0, 128);
 504         snprintf(proc_file_name, 128, "v3-mem%d", zone->node_id);
 505
 506         remove_proc_entry(proc_file_name, palacios_proc_dir);
 507     }
 508
 509
 510     kfree(zone->avail);
 511     kfree(zone);
 512
 513     return;
 514 }
 515
 516
 517
 518 /**
 519  * Initializes a buddy system memory allocator object.
 520  *
 521  * Arguments:
 522  *       [IN] base_addr:  Base address of the memory pool.
 523  *       [IN] pool_order: Size of the memory pool (2^pool_order bytes).
 524  *       [IN] min_order:  Minimum allocatable block size (2^min_order bytes).
 525  *
 526  * Returns:
 527  *       Success: Pointer to an initialized buddy system memory allocator.
 528  *       Failure: NULL
 529  *
 530  * NOTE: The min_order argument is provided as an optimization. Since one tag
 531  *       bit is required for each minimum-sized block, large memory pools that
 532  *       allow order 0 allocations will use large amounts of memory. Specifying
 533  *       a min_order of 5 (32 bytes), for example, reduces the number of tag
 534  *       bits by 32x.
 535  */
 536 struct buddy_memzone *
 537 buddy_init(
 538         unsigned long max_order,
 539         unsigned long min_order,
 540         unsigned int node_id
 541 )
 542 {
 543     struct buddy_memzone * zone = NULL;
 544     unsigned long i;
 545
 546     DEBUG("Initializing Memory zone with up to %lu bit blocks on Node %d\n", max_order, node_id);
 547
 548
 549     /* Smallest block size must be big enough to hold a block structure */
 550     if ((1UL << min_order) < sizeof(struct block))
 551         min_order = ilog2( roundup_pow_of_two(sizeof(struct block)) );
 552
 553     /* The minimum block order must be smaller than the pool order */
 554     if (min_order > max_order)
 555         return NULL;
 556
 557     zone = kmalloc_node(sizeof(struct buddy_memzone), GFP_KERNEL, node_id);
 558
 559     printk("Allocated zone at %p\n", zone);
 560
 561     if (IS_ERR(zone)) {
 562         ERROR("Could not allocate memzone\n");
 563         return NULL;
 564     }
 565
 566     memset(zone, 0, sizeof(struct buddy_memzone));
 567
 568     zone->max_order = max_order;
 569     zone->min_order  = min_order;
 570     zone->node_id = node_id;
 571
 572     /* Allocate a list for every order up to the maximum allowed order */
 573     zone->avail = kmalloc_node((max_order + 1) * sizeof(struct list_head), GFP_KERNEL, zone->node_id);
 574
 575     printk("Allocated free lists at %p\n", zone->avail);
 576
 577     /* Initially all lists are empty */
 578     for (i = 0; i <= max_order; i++) {
 579         INIT_LIST_HEAD(&zone->avail[i]);
 580     }
 581
 582
 583     spin_lock_init(&(zone->lock));
 584
 585     zone->mempools.rb_node = NULL;
 586
 587     printk("Allocated zone at %p\n", zone);
 588
 589     {
 590         struct proc_dir_entry * zone_entry = NULL;
 591         char proc_file_name[128];
 592
 593         memset(proc_file_name, 0, 128);
 594         snprintf(proc_file_name, 128, "v3-mem%d", zone->node_id);
 595
 596         zone_entry = create_proc_entry(proc_file_name, 0444, palacios_proc_dir);
 597         if (zone_entry) {
 598             zone_entry->proc_fops = &zone_proc_ops;
 599             zone_entry->data = zone;
 600         } else {
 601             printk(KERN_ERR "Error creating memory zone proc file\n");
 602         }
 603
 604     }
 605
 606     return zone;
 607 }