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                    void *user_metadata) {
 144     struct buddy_mempool * mp = NULL;
 145     unsigned long flags = 0;
 146     int ret = 0;
 147
 148     if (pool_order > zone->max_order) {
 149         ERROR("Pool order size is larger than max allowable zone size (pool_order=%lu) (max_order=%lu)\n", pool_order, zone->max_order);
 150         return -1;
 151     } else if (pool_order < zone->min_order) {
 152         ERROR("Pool order is smaller than min allowable zone size (pool_order=%lu) (min_order=%lu)\n", pool_order, zone->min_order);
 153         return -1;
 154     }
 155
 156     mp = palacios_alloc_extended(sizeof(struct buddy_mempool), GFP_KERNEL, zone->node_id);
 157
 158     if (!mp) {
 159         ERROR("Could not allocate mempool\n");
 160         return -1;
 161     }
 162
 163     mp->base_addr  = base_addr;
 164     mp->pool_order = pool_order;
 165     mp->zone = zone;
 166     mp->num_free_blocks = 0;
 167
 168     mp->user_metadata = user_metadata;
 169
 170     /* Allocate a bitmap with 1 bit per minimum-sized block */
 171     mp->num_blocks = (1UL << pool_order) / (1UL << zone->min_order);
 172
 173     mp->tag_bits   = palacios_alloc_extended(
 174                                   BITS_TO_LONGS(mp->num_blocks) * sizeof(long), GFP_KERNEL, zone->node_id
 175                                   );
 176
 177     if (!(mp->tag_bits)) {
 178         ERROR("Could not allocate tag_bits\n");
 179         palacios_free(mp);
 180         return -1;
 181     }
 182
 183
 184     /* Initially mark all minimum-sized blocks as allocated */
 185     bitmap_zero(mp->tag_bits, mp->num_blocks);
 186
 187     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 188     ret = insert_mempool(zone, mp);
 189     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 190
 191     if (ret == -1) {
 192         ERROR("Error: Could not insert mempool into zone\n");
 193         palacios_free(mp->tag_bits);
 194         palacios_free(mp);
 195
 196         return -1;
 197     }
 198
 199     buddy_free(zone, base_addr, pool_order);
 200
 201     INFO("Added memory pool (addr=%p), order=%lu\n", (void *)base_addr, pool_order);
 202
 203     return 0;
 204 }
 205
 206
 207 /**
 208  * Removes a mempool from a zone,
 209  * assumes the zone lock is already held
 210  */
 211 static int __buddy_remove_mempool(struct buddy_memzone * zone,
 212                                   unsigned long base_addr,
 213                                   unsigned char force,
 214                                   void **user_metadata)
 215 {
 216
 217     struct buddy_mempool * pool = NULL;
 218     struct block * block = NULL;
 219
 220
 221     pool = find_mempool(zone, base_addr);
 222
 223     if (pool == NULL) {
 224         ERROR("Could not find mempool with base address (%p)\n", (void *)base_addr);
 225         return -1;
 226     }
 227
 228     block = (struct block *)__va(pool->base_addr);
 229
 230     INFO("Removing Mempool %p, base=%p\n",pool,block);
 231
 232     // The largest order block in the memory pool must be free
 233     if (!is_available(pool, block)) {
 234         if (!force) {
 235             ERROR("Trying to remove an in use memory pool\n");
 236             *user_metadata=0;
 237             return -1;
 238         } else {
 239             WARNING("Forcefully removing in use memory pool\n");
 240         }
 241     }
 242
 243     *user_metadata = pool->user_metadata;
 244
 245     if (is_available(pool,block)) {
 246         list_del(&(block->link));
 247     } else {
 248         // we may not be on the free list if we are being
 249         // forcibly removed before all allocations are freed
 250     }
 251
 252     rb_erase(&(pool->tree_node), &(zone->mempools));
 253
 254     palacios_free(pool->tag_bits);
 255     palacios_free(pool);
 256
 257     zone->num_pools--;
 258
 259     return 0;
 260 }
 261
 262 int buddy_remove_pool(struct buddy_memzone * zone,
 263                       unsigned long base_addr,
 264                       unsigned char force,
 265                       void          **user_metadata)
 266 {
 267     unsigned long flags = 0;
 268     int ret = 0;
 269
 270
 271     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 272     ret = __buddy_remove_mempool(zone, base_addr, force, user_metadata);
 273     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 274
 275     return ret;
 276 }
 277
 278
 279
 280
 281
 282 /**
 283  * Allocates a block of memory of the requested size (2^order bytes).
 284  *
 285  * Arguments:
 286  *       [IN] mp:    Buddy system memory allocator object.
 287  *       [IN] order: Block size to allocate (2^order bytes).
 288  *       [IN] constraints: bitmmask showing restrictions for scan. currently: 0=none, or LWK_BUDDY_CONSTRAINT_4GB
 289  * Returns:
 290  *       Success: Pointer to the start of the allocated memory block.
 291  *       Failure: NULL
 292  */
 293 uintptr_t
 294 buddy_alloc(struct buddy_memzone *zone, unsigned long order, int constraints)
 295 {
 296     unsigned long j;
 297     struct buddy_mempool * mp = NULL;
 298     struct list_head * list = NULL;
 299     struct list_head * cur = NULL;
 300     struct block * block = NULL;
 301     struct block * buddy_block = NULL;
 302     unsigned long flags = 0;
 303
 304     if (constraints && constraints!=LWK_BUDDY_CONSTRAINT_4GB) {
 305         ERROR("Do not know how to satisfy constraint mask 0x%x\n", constraints);
 306         return (uintptr_t) NULL;
 307     }
 308
 309     BUG_ON(zone == NULL);
 310     BUG_ON(order > zone->max_order);
 311
 312     /* Fixup requested order to be at least the minimum supported */
 313     if (order < zone->min_order) {
 314         order = zone->min_order;
 315     }
 316
 317     INFO("zone=%p, order=%lu\n", zone, order);
 318
 319     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 320
 321     for (j = order; j <= zone->max_order; j++) {
 322
 323         INFO("Order iter=%lu\n", j);
 324
 325         block=NULL;
 326
 327         list = &(zone->avail[j]);
 328
 329         if (list_empty(list)) {
 330             continue;
 331         }
 332
 333         list_for_each(cur, list) {
 334             block = list_entry(cur, struct block, link);
 335
 336             if (!constraints) {
 337                 // without a constraint, we just want the first one
 338                 break;
 339             }
 340
 341             if (constraints & LWK_BUDDY_CONSTRAINT_4GB) {
 342                 // under this constraint, we will only use if the entirity
 343                 // of the allocation within the block will be below 4 GB
 344                 void *block_pa = (void*)__pa(block);
 345                 if ((block_pa + (1ULL<<order)) <= (void*)(0x100000000ULL)) {
 346                     // this block will work
 347                     break;
 348                 } else {
 349                     // look for the next block
 350                     block=NULL;
 351                     continue;
 352                 }
 353             }
 354         }
 355
 356         if (!block) {
 357             // uh oh, no block, look to next order
 358             continue;
 359         }
 360
 361         // have appropriate block, will allocate
 362
 363         list_del(&(block->link));
 364
 365         mp = block->mp;
 366
 367         mark_allocated(mp, block);
 368
 369         INFO("pool=%p, block=%p, order=%lu, j=%lu\n", mp, block, order, j);
 370
 371         /* Trim if a higher order block than necessary was allocated */
 372         while (j > order) {
 373             --j;
 374             buddy_block = (struct block *)((unsigned long)block + (1UL << j));
 375             buddy_block->mp = mp;
 376             buddy_block->order = j;
 377             mark_available(mp, buddy_block);
 378             list_add(&(buddy_block->link), &(zone->avail[j]));
 379         }
 380
 381         mp->num_free_blocks -= (1UL << (order - zone->min_order));
 382
 383         palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 384
 385         return __pa(block);
 386     }
 387
 388     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 389
 390     return (uintptr_t)NULL;
 391 }
 392
 393
 394 /**
 395  * Returns a block of memory to the buddy system memory allocator.
 396  */
 397 int
 398 buddy_free(
 399         //!    Buddy system memory allocator object.
 400         struct buddy_memzone *  zone,
 401         //!  Address of memory block to free.
 402         uintptr_t addr,
 403         //! Size of the memory block (2^order bytes).
 404         unsigned long           order
 405 )
 406 {
 407     struct block * block  = NULL;
 408     struct buddy_mempool * pool = NULL;
 409     unsigned long flags = 0;
 410
 411     BUG_ON(zone == NULL);
 412     BUG_ON(order > zone->max_order);
 413
 414
 415     if ((addr & ((1UL << zone->min_order) - 1)) != 0) {
 416         ERROR("Attempting to free an invalid memory address (%p)\n", (void *)addr);
 417         BUG_ON(1);
 418     }
 419
 420
 421     /* Fixup requested order to be at least the minimum supported */
 422     if (order < zone->min_order) {
 423         order = zone->min_order;
 424     }
 425
 426
 427     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 428
 429     pool = find_mempool(zone, addr);
 430
 431     if ((pool == NULL) || (order > pool->pool_order)) {
 432         WARNING("Attempted to free an invalid page address (%p) - pool=%p order=%lu\n", (void *)addr,pool,order);
 433         palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 434         return -1;
 435     }
 436
 437
 438     /* Overlay block structure on the memory block being freed */
 439     block = (struct block *) __va(addr);
 440
 441     if (is_available(pool, block)) {
 442         ERROR("Error: Freeing an available block\n");
 443         palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 444         return -1;
 445     }
 446
 447     pool->num_free_blocks += (1UL << (order - zone->min_order));
 448
 449     /* Coalesce as much as possible with adjacent free buddy blocks */
 450     while (order < pool->pool_order) {
 451         /* Determine our buddy block's address */
 452         struct block * buddy = find_buddy(pool, block, order);
 453
 454         /* Make sure buddy is available and has the same size as us */
 455         if (!is_available(pool, buddy))
 456             break;
 457         if (is_available(pool, buddy) && (buddy->order != order))
 458             break;
 459
 460         /* OK, we're good to go... buddy merge! */
 461         list_del(&buddy->link);
 462         if (buddy < block)
 463             block = buddy;
 464         ++order;
 465         block->order = order;
 466     }
 467
 468     /* Add the (possibly coalesced) block to the appropriate free list */
 469     block->order = order;
 470     block->mp = pool;
 471     mark_available(pool, block);
 472     list_add(&(block->link), &(zone->avail[order]));
 473
 474     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 475
 476     return 0;
 477 }
 478
 479
 480
 481
 482 /**
 483  * Dumps the state of a buddy system memory allocator object to the console.
 484  */
 485 static int
 486 zone_mem_show(struct seq_file * s, void * v) {
 487     struct buddy_memzone * zone = s->private;
 488     unsigned long i;
 489     unsigned long num_blocks;
 490     struct list_head * entry = NULL;
 491     unsigned long flags = 0;
 492
 493
 494     if (!zone) {
 495         seq_printf(s, "Null Zone Pointer!!\n");
 496         return 0;
 497     }
 498
 499     seq_printf(s, "DUMP OF BUDDY MEMORY ZONE:\n");
 500     seq_printf(s, "  Zone Max Order=%lu, Min Order=%lu\n",
 501            zone->max_order, zone->min_order);
 502
 503     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 504
 505     for (i = zone->min_order; i <= zone->max_order; i++) {
 506
 507         /* Count the number of memory blocks in the list */
 508         num_blocks = 0;
 509         list_for_each(entry, &zone->avail[i]) {
 510             ++num_blocks;
 511         }
 512
 513         seq_printf(s, "  order %2lu: %lu free blocks\n", i, num_blocks);
 514     }
 515
 516
 517     seq_printf(s, " %lu memory pools\n", zone->num_pools);
 518     // list pools in zone
 519     {
 520         struct rb_node * node = rb_first(&(zone->mempools));
 521         struct buddy_mempool * pool = NULL;
 522
 523         while (node) {
 524             pool = rb_entry(node, struct buddy_mempool, tree_node);
 525
 526             seq_printf(s, "    Base Addr=%p, order=%lu, size=%lu, free=%lu\n",
 527                        (void *)pool->base_addr, pool->pool_order, (1UL << pool->pool_order),
 528                        pool->num_free_blocks << zone->min_order);
 529
 530
 531             node = rb_next(node);
 532         }
 533     }
 534
 535     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 536
 537     return 0;
 538 }
 539
 540
 541 static int zone_proc_open(struct inode * inode, struct file * filp) {
 542     struct proc_dir_entry * proc_entry = PDE(inode);
 543     INFO("proc_entry at %p, data at %p\n", proc_entry, proc_entry->data);
 544     return single_open(filp, zone_mem_show, proc_entry->data);
 545 }
 546
 547
 548 static struct file_operations zone_proc_ops = {
 549     .owner = THIS_MODULE,
 550     .open = zone_proc_open,
 551     .read = seq_read,
 552     .llseek = seq_lseek,
 553     .release = single_release,
 554 };
 555
 556
 557 void buddy_deinit(struct buddy_memzone * zone, int (*free_callback)(void *user_metadata)) {
 558     unsigned long flags;
 559     struct rb_node *node;
 560     struct buddy_mempool **pools;
 561     unsigned long long base_addr;
 562     void *meta;
 563     int i;
 564     unsigned long num_in_tree;
 565
 566     pools = (struct buddy_mempool **) palacios_alloc(sizeof(struct buddy_mempool *)*zone->num_pools);
 567     if (!pools) {
 568         ERROR("Cannot allocate space for doing deinit of memory zone\n");
 569         return ;
 570     }
 571
 572     // We will lock only to build up the memory pool list
 573     // when we free memory, we need to be able to support free callbacks
 574     // that could block.  This does leave a race with adds, allocs, and frees, however
 575     // In Palacios, we expect a deinit will only really happen on the module unload
 576     // so this should not present a problem
 577     palacios_spinlock_lock_irqsave(&(zone->lock), flags);
 578
 579     // because it does not appear possible to erase while iterating
 580     // over the rb tree, we do the following contorted mess
 581     // get the pools
 582     for (num_in_tree=0, node=rb_first(&(zone->mempools));
 583          node && num_in_tree<zone->num_pools;
 584          node=rb_next(node), num_in_tree++) {
 585
 586         pools[num_in_tree]=rb_entry(node,struct buddy_mempool, tree_node);
 587     }
 588
 589     palacios_spinlock_unlock_irqrestore(&(zone->lock), flags);
 590
 591     if (num_in_tree != zone->num_pools) {
 592         WARNING("Odd, the number of pools in the tree is %lu, but the zone reports %lu\n",
 593                 num_in_tree, zone->num_pools);
 594     }
 595
 596     // now we'll free the memory
 597     // note that buddy_remove_mempool also removes them
 598     // from the rb tree, and frees them
 599     for (i=0;i<num_in_tree;i++) {
 600         base_addr = pools[i]->base_addr;
 601
 602         if (buddy_remove_pool(zone, base_addr, 1, &meta)) {
 603             WARNING("Cannot remove memory pool at %p during zone deinit...\n",(void*)(base_addr));
 604             continue;
 605         }
 606
 607         // pool and node are now gone...
 608
 609         // invoke the callback to free the actual memory, if any
 610         if (free_callback) {
 611             free_callback(meta);
 612         }
 613     }
 614
 615
 616     // get rid of /proc entry
 617     {
 618         char proc_file_name[128];
 619
 620         memset(proc_file_name, 0, 128);
 621         snprintf(proc_file_name, 128, "v3-mem%d", zone->node_id);
 622
 623         remove_proc_entry(proc_file_name, palacios_get_procdir());
 624     }
 625
 626
 627     palacios_free(pools);
 628     palacios_free(zone->avail);
 629     palacios_free(zone);
 630
 631     return;
 632 }
 633
 634
 635
 636 /**
 637  * Initializes a buddy system memory allocator object.
 638  *
 639  * Arguments:
 640  *       [IN] base_addr:  Base address of the memory pool.
 641  *       [IN] pool_order: Size of the memory pool (2^pool_order bytes).
 642  *       [IN] min_order:  Minimum allocatable block size (2^min_order bytes).
 643  *
 644  * Returns:
 645  *       Success: Pointer to an initialized buddy system memory allocator.
 646  *       Failure: NULL
 647  *
 648  * NOTE: The min_order argument is provided as an optimization. Since one tag
 649  *       bit is required for each minimum-sized block, large memory pools that
 650  *       allow order 0 allocations will use large amounts of memory. Specifying
 651  *       a min_order of 5 (32 bytes), for example, reduces the number of tag
 652  *       bits by 32x.
 653  */
 654 struct buddy_memzone *
 655 buddy_init(
 656         unsigned long max_order,
 657         unsigned long min_order,
 658         unsigned int node_id
 659 )
 660 {
 661     struct buddy_memzone * zone = NULL;
 662     unsigned long i;
 663
 664     DEBUG("Initializing Memory zone with up to %lu bit blocks on Node %d\n", max_order, node_id);
 665
 666
 667     /* Smallest block size must be big enough to hold a block structure */
 668     if ((1UL << min_order) < sizeof(struct block))
 669         min_order = ilog2( roundup_pow_of_two(sizeof(struct block)) );
 670
 671     /* The minimum block order must be smaller than the pool order */
 672     if (min_order > max_order)
 673         return NULL;
 674
 675     zone = palacios_alloc_extended(sizeof(struct buddy_memzone), GFP_KERNEL, node_id);
 676
 677     INFO("Allocated zone at %p\n", zone);
 678
 679     if (!zone) {
 680         ERROR("Could not allocate memzone\n");
 681         return NULL;
 682     }
 683
 684     memset(zone, 0, sizeof(struct buddy_memzone));
 685
 686     zone->max_order = max_order;
 687     zone->min_order  = min_order;
 688     zone->node_id = node_id;
 689
 690     /* Allocate a list for every order up to the maximum allowed order */
 691     zone->avail = palacios_alloc_extended((max_order + 1) * sizeof(struct list_head), GFP_KERNEL, zone->node_id);
 692
 693     if (!(zone->avail)) {
 694         ERROR("Unable to allocate space for zone list\n");
 695         palacios_free(zone);
 696         return NULL;
 697     }
 698
 699     INFO("Allocated free lists at %p\n", zone->avail);
 700
 701     /* Initially all lists are empty */
 702     for (i = 0; i <= max_order; i++) {
 703         INIT_LIST_HEAD(&zone->avail[i]);
 704     }
 705
 706
 707     palacios_spinlock_init(&(zone->lock));
 708
 709     zone->mempools.rb_node = NULL;
 710
 711     INFO("Allocated zone at %p\n", zone);
 712
 713     {
 714         struct proc_dir_entry * zone_entry = NULL;
 715         char proc_file_name[128];
 716
 717         memset(proc_file_name, 0, 128);
 718         snprintf(proc_file_name, 128, "v3-mem%u", zone->node_id);
 719
 720         zone_entry = create_proc_entry(proc_file_name, 0444, palacios_get_procdir());
 721         if (zone_entry) {
 722             zone_entry->proc_fops = &zone_proc_ops;
 723             zone_entry->data = zone;
 724             INFO("Successfully created /proc/v3vee/v3-mem%d\n", zone->node_id);
 725         } else {
 726             ERROR("Cannot create /proc/v3vee/v3-mem%d\n", zone->node_id);
 727         }
 728
 729     }
 730
 731     return zone;
 732 }