Subversion Repositories HelenOS

Rev

Rev 1229 | Rev 1702 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2005 Jakub Jermar
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /**
  30.  * @file    buddy.c
  31.  * @brief   Buddy allocator framework.
  32.  *
  33.  * This file contains buddy system allocator framework.
  34.  * Specialized functions are needed for this abstract framework
  35.  * to be useful.
  36.  */
  37.  
  38. #include <mm/buddy.h>
  39. #include <mm/frame.h>
  40. #include <arch/types.h>
  41. #include <typedefs.h>
  42. #include <adt/list.h>
  43. #include <debug.h>
  44. #include <print.h>
  45.  
  46. /** Return size needed for the buddy configuration data */
  47. size_t buddy_conf_size(int max_order)
  48. {
  49.     return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
  50. }
  51.  
  52.  
  53. /** Create buddy system
  54.  *
  55.  * Allocate memory for and initialize new buddy system.
  56.  *
  57.  * @param b Preallocated buddy system control data.
  58.  * @param max_order The biggest allocable size will be 2^max_order.
  59.  * @param op Operations for new buddy system.
  60.  * @param data Pointer to be used by implementation.
  61.  *
  62.  * @return New buddy system.
  63.  */
  64. void buddy_system_create(buddy_system_t *b,
  65.              __u8 max_order,
  66.              buddy_system_operations_t *op,
  67.              void *data)
  68. {
  69.     int i;
  70.  
  71.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  72.  
  73.     ASSERT(op->find_buddy);
  74.     ASSERT(op->set_order);
  75.     ASSERT(op->get_order);
  76.     ASSERT(op->bisect);
  77.     ASSERT(op->coalesce);
  78.     ASSERT(op->mark_busy);
  79.  
  80.     /*
  81.      * Use memory after our own structure
  82.      */
  83.     b->order = (link_t *) (&b[1]);
  84.    
  85.     for (i = 0; i <= max_order; i++)
  86.         list_initialize(&b->order[i]);
  87.  
  88.     b->max_order = max_order;
  89.     b->op = op;
  90.     b->data = data;
  91. }
  92.  
  93. /** Check if buddy system can allocate block
  94.  *
  95.  * @param b Buddy system pointer
  96.  * @param i Size of the block (2^i)
  97.  *
  98.  * @return True if block can be allocated
  99.  */
  100. bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {
  101.     __u8 k;
  102.    
  103.     /*
  104.      * If requested block is greater then maximal block
  105.      * we know immediatly that we cannot satisfy the request.
  106.      */
  107.     if (i > b->max_order) return false;
  108.  
  109.     /*
  110.      * Check if any bigger or equal order has free elements
  111.      */
  112.     for (k=i; k <= b->max_order; k++) {
  113.         if (!list_empty(&b->order[k])) {
  114.             return true;
  115.         }
  116.     }
  117.    
  118.     return false;
  119.    
  120. }
  121.  
  122. /** Allocate PARTICULAR block from buddy system
  123.  *
  124.  * @ return Block of data or NULL if no such block was found
  125.  */
  126. link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
  127. {
  128.     link_t *left,*right, *tmp;
  129.     __u8 order;
  130.  
  131.     left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  132.     ASSERT(left);
  133.     list_remove(left);
  134.     while (1) {
  135.         if (! b->op->get_order(b,left)) {
  136.             b->op->mark_busy(b, left);
  137.             return left;
  138.         }
  139.        
  140.         order = b->op->get_order(b, left);
  141.  
  142.         right = b->op->bisect(b, left);
  143.         b->op->set_order(b, left, order-1);
  144.         b->op->set_order(b, right, order-1);
  145.  
  146.         tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  147.  
  148.         if (tmp == right) {
  149.             right = left;
  150.             left = tmp;
  151.         }
  152.         ASSERT(tmp == left);
  153.         b->op->mark_busy(b, left);
  154.         buddy_system_free(b, right);
  155.         b->op->mark_available(b, left);
  156.     }
  157. }
  158.  
  159. /** Allocate block from buddy system.
  160.  *
  161.  * @param b Buddy system pointer.
  162.  * @param i Returned block will be 2^i big.
  163.  *
  164.  * @return Block of data represented by link_t.
  165.  */
  166. link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
  167. {
  168.     link_t *res, *hlp;
  169.  
  170.     ASSERT(i <= b->max_order);
  171.  
  172.     /*
  173.      * If the list of order i is not empty,
  174.      * the request can be immediatelly satisfied.
  175.      */
  176.     if (!list_empty(&b->order[i])) {
  177.         res = b->order[i].next;
  178.         list_remove(res);
  179.         b->op->mark_busy(b, res);
  180.         return res;
  181.     }
  182.     /*
  183.      * If order i is already the maximal order,
  184.      * the request cannot be satisfied.
  185.      */
  186.     if (i == b->max_order)
  187.         return NULL;
  188.  
  189.     /*
  190.      * Try to recursively satisfy the request from higher order lists.
  191.      */
  192.     hlp = buddy_system_alloc(b, i + 1);
  193.    
  194.     /*
  195.      * The request could not be satisfied
  196.      * from higher order lists.
  197.      */
  198.     if (!hlp)
  199.         return NULL;
  200.        
  201.     res = hlp;
  202.    
  203.     /*
  204.      * Bisect the block and set order of both of its parts to i.
  205.      */
  206.     hlp = b->op->bisect(b, res);
  207.     b->op->set_order(b, res, i);
  208.     b->op->set_order(b, hlp, i);
  209.    
  210.     /*
  211.      * Return the other half to buddy system. Mark the first part
  212.      * full, so that it won't coalesce again.
  213.      */
  214.     b->op->mark_busy(b, res);
  215.     buddy_system_free(b, hlp);
  216.    
  217.     return res;
  218.    
  219. }
  220.  
  221. /** Return block to buddy system.
  222.  *
  223.  * @param b Buddy system pointer.
  224.  * @param block Block to return.
  225.  */
  226. void buddy_system_free(buddy_system_t *b, link_t *block)
  227. {
  228.     link_t *buddy, *hlp;
  229.     __u8 i;
  230.  
  231.     /*
  232.      * Determine block's order.
  233.      */
  234.     i = b->op->get_order(b, block);
  235.  
  236.     ASSERT(i <= b->max_order);
  237.  
  238.     if (i != b->max_order) {
  239.         /*
  240.          * See if there is any buddy in the list of order i.
  241.          */
  242.         buddy = b->op->find_buddy(b, block);
  243.         if (buddy) {
  244.  
  245.             ASSERT(b->op->get_order(b, buddy) == i);
  246.             /*
  247.              * Remove buddy from the list of order i.
  248.              */
  249.             list_remove(buddy);
  250.        
  251.             /*
  252.              * Invalidate order of both block and buddy.
  253.              */
  254.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  255.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  256.        
  257.             /*
  258.              * Coalesce block and buddy into one block.
  259.              */
  260.             hlp = b->op->coalesce(b, block, buddy);
  261.  
  262.             /*
  263.              * Set order of the coalesced block to i + 1.
  264.              */
  265.             b->op->set_order(b, hlp, i + 1);
  266.  
  267.             /*
  268.              * Recursively add the coalesced block to the list of order i + 1.
  269.              */
  270.             buddy_system_free(b, hlp);
  271.             return;
  272.         }
  273.     }
  274.  
  275.     /*
  276.      * Insert block into the list of order i.
  277.      */
  278.     list_append(block, &b->order[i]);
  279.  
  280. }
  281.  
  282. /** Prints out structure of buddy system
  283.  *
  284.  * @param b Pointer to buddy system
  285.  * @param es Element size
  286.  */
  287. void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
  288.     index_t i;
  289.     count_t cnt, elem_count = 0, block_count = 0;
  290.     link_t * cur;
  291.    
  292.  
  293.     printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
  294.     printf("-----\t------\t--------\t----------\t---------------\n");
  295.    
  296.     for (i=0;i <= b->max_order; i++) {
  297.         cnt = 0;
  298.         if (!list_empty(&b->order[i])) {
  299.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
  300.                 cnt++;
  301.         }
  302.    
  303.         printf("#%zd\t%5zd\t%7zdK\t%8zdK\t%6zd\t", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
  304.         if (!list_empty(&b->order[i])) {
  305.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
  306.                 b->op->print_id(b, cur);
  307.                 printf(" ");
  308.             }
  309.         }
  310.         printf("\n");
  311.            
  312.         block_count += cnt;
  313.         elem_count += (1 << i) * cnt;
  314.     }
  315.     printf("-----\t------\t--------\t----------\t---------------\n");
  316.     printf("Buddy system contains %zd free elements (%zd blocks)\n" , elem_count, block_count);
  317.  
  318. }
  319.