Subversion Repositories HelenOS

Rev

Rev 1780 | Rev 2071 | 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. /** @addtogroup genericmm
  30.  * @{
  31.  */
  32.  
  33. /**
  34.  * @file
  35.  * @brief   Buddy allocator framework.
  36.  *
  37.  * This file contains buddy system allocator framework.
  38.  * Specialized functions are needed for this abstract framework
  39.  * to be useful.
  40.  */
  41.  
  42. #include <mm/buddy.h>
  43. #include <mm/frame.h>
  44. #include <arch/types.h>
  45. #include <typedefs.h>
  46. #include <adt/list.h>
  47. #include <debug.h>
  48. #include <print.h>
  49.  
  50. /** Return size needed for the buddy configuration data */
  51. size_t buddy_conf_size(int max_order)
  52. {
  53.     return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
  54. }
  55.  
  56.  
  57. /** Create buddy system
  58.  *
  59.  * Allocate memory for and initialize new buddy system.
  60.  *
  61.  * @param b Preallocated buddy system control data.
  62.  * @param max_order The biggest allocable size will be 2^max_order.
  63.  * @param op Operations for new buddy system.
  64.  * @param data Pointer to be used by implementation.
  65.  *
  66.  * @return New buddy system.
  67.  */
  68. void buddy_system_create(buddy_system_t *b,
  69.              uint8_t max_order,
  70.              buddy_system_operations_t *op,
  71.              void *data)
  72. {
  73.     int i;
  74.  
  75.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  76.  
  77.     ASSERT(op->find_buddy);
  78.     ASSERT(op->set_order);
  79.     ASSERT(op->get_order);
  80.     ASSERT(op->bisect);
  81.     ASSERT(op->coalesce);
  82.     ASSERT(op->mark_busy);
  83.  
  84.     /*
  85.      * Use memory after our own structure
  86.      */
  87.     b->order = (link_t *) (&b[1]);
  88.    
  89.     for (i = 0; i <= max_order; i++)
  90.         list_initialize(&b->order[i]);
  91.  
  92.     b->max_order = max_order;
  93.     b->op = op;
  94.     b->data = data;
  95. }
  96.  
  97. /** Check if buddy system can allocate block
  98.  *
  99.  * @param b Buddy system pointer
  100.  * @param i Size of the block (2^i)
  101.  *
  102.  * @return True if block can be allocated
  103.  */
  104. bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i) {
  105.     uint8_t k;
  106.    
  107.     /*
  108.      * If requested block is greater then maximal block
  109.      * we know immediatly that we cannot satisfy the request.
  110.      */
  111.     if (i > b->max_order) return false;
  112.  
  113.     /*
  114.      * Check if any bigger or equal order has free elements
  115.      */
  116.     for (k=i; k <= b->max_order; k++) {
  117.         if (!list_empty(&b->order[k])) {
  118.             return true;
  119.         }
  120.     }
  121.    
  122.     return false;
  123.    
  124. }
  125.  
  126. /** Allocate PARTICULAR block from buddy system
  127.  *
  128.  * @ return Block of data or NULL if no such block was found
  129.  */
  130. link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
  131. {
  132.     link_t *left,*right, *tmp;
  133.     uint8_t order;
  134.  
  135.     left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  136.     ASSERT(left);
  137.     list_remove(left);
  138.     while (1) {
  139.         if (! b->op->get_order(b,left)) {
  140.             b->op->mark_busy(b, left);
  141.             return left;
  142.         }
  143.        
  144.         order = b->op->get_order(b, left);
  145.  
  146.         right = b->op->bisect(b, left);
  147.         b->op->set_order(b, left, order-1);
  148.         b->op->set_order(b, right, order-1);
  149.  
  150.         tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  151.  
  152.         if (tmp == right) {
  153.             right = left;
  154.             left = tmp;
  155.         }
  156.         ASSERT(tmp == left);
  157.         b->op->mark_busy(b, left);
  158.         buddy_system_free(b, right);
  159.         b->op->mark_available(b, left);
  160.     }
  161. }
  162.  
  163. /** Allocate block from buddy system.
  164.  *
  165.  * @param b Buddy system pointer.
  166.  * @param i Returned block will be 2^i big.
  167.  *
  168.  * @return Block of data represented by link_t.
  169.  */
  170. link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
  171. {
  172.     link_t *res, *hlp;
  173.  
  174.     ASSERT(i <= b->max_order);
  175.  
  176.     /*
  177.      * If the list of order i is not empty,
  178.      * the request can be immediatelly satisfied.
  179.      */
  180.     if (!list_empty(&b->order[i])) {
  181.         res = b->order[i].next;
  182.         list_remove(res);
  183.         b->op->mark_busy(b, res);
  184.         return res;
  185.     }
  186.     /*
  187.      * If order i is already the maximal order,
  188.      * the request cannot be satisfied.
  189.      */
  190.     if (i == b->max_order)
  191.         return NULL;
  192.  
  193.     /*
  194.      * Try to recursively satisfy the request from higher order lists.
  195.      */
  196.     hlp = buddy_system_alloc(b, i + 1);
  197.    
  198.     /*
  199.      * The request could not be satisfied
  200.      * from higher order lists.
  201.      */
  202.     if (!hlp)
  203.         return NULL;
  204.        
  205.     res = hlp;
  206.    
  207.     /*
  208.      * Bisect the block and set order of both of its parts to i.
  209.      */
  210.     hlp = b->op->bisect(b, res);
  211.     b->op->set_order(b, res, i);
  212.     b->op->set_order(b, hlp, i);
  213.    
  214.     /*
  215.      * Return the other half to buddy system. Mark the first part
  216.      * full, so that it won't coalesce again.
  217.      */
  218.     b->op->mark_busy(b, res);
  219.     buddy_system_free(b, hlp);
  220.    
  221.     return res;
  222.    
  223. }
  224.  
  225. /** Return block to buddy system.
  226.  *
  227.  * @param b Buddy system pointer.
  228.  * @param block Block to return.
  229.  */
  230. void buddy_system_free(buddy_system_t *b, link_t *block)
  231. {
  232.     link_t *buddy, *hlp;
  233.     uint8_t i;
  234.  
  235.     /*
  236.      * Determine block's order.
  237.      */
  238.     i = b->op->get_order(b, block);
  239.  
  240.     ASSERT(i <= b->max_order);
  241.  
  242.     if (i != b->max_order) {
  243.         /*
  244.          * See if there is any buddy in the list of order i.
  245.          */
  246.         buddy = b->op->find_buddy(b, block);
  247.         if (buddy) {
  248.  
  249.             ASSERT(b->op->get_order(b, buddy) == i);
  250.             /*
  251.              * Remove buddy from the list of order i.
  252.              */
  253.             list_remove(buddy);
  254.        
  255.             /*
  256.              * Invalidate order of both block and buddy.
  257.              */
  258.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  259.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  260.        
  261.             /*
  262.              * Coalesce block and buddy into one block.
  263.              */
  264.             hlp = b->op->coalesce(b, block, buddy);
  265.  
  266.             /*
  267.              * Set order of the coalesced block to i + 1.
  268.              */
  269.             b->op->set_order(b, hlp, i + 1);
  270.  
  271.             /*
  272.              * Recursively add the coalesced block to the list of order i + 1.
  273.              */
  274.             buddy_system_free(b, hlp);
  275.             return;
  276.         }
  277.     }
  278.  
  279.     /*
  280.      * Insert block into the list of order i.
  281.      */
  282.     list_append(block, &b->order[i]);
  283.  
  284. }
  285.  
  286. /** Prints out structure of buddy system
  287.  *
  288.  * @param b Pointer to buddy system
  289.  * @param elem_size Element size
  290.  */
  291. void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
  292.     index_t i;
  293.     count_t cnt, elem_count = 0, block_count = 0;
  294.     link_t * cur;
  295.    
  296.  
  297.     printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
  298.     printf("-----\t------\t--------\t----------\t---------------\n");
  299.    
  300.     for (i=0;i <= b->max_order; i++) {
  301.         cnt = 0;
  302.         if (!list_empty(&b->order[i])) {
  303.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
  304.                 cnt++;
  305.         }
  306.    
  307.         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);
  308.         if (!list_empty(&b->order[i])) {
  309.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
  310.                 b->op->print_id(b, cur);
  311.                 printf(" ");
  312.             }
  313.         }
  314.         printf("\n");
  315.            
  316.         block_count += cnt;
  317.         elem_count += (1 << i) * cnt;
  318.     }
  319.     printf("-----\t------\t--------\t----------\t---------------\n");
  320.     printf("Buddy system contains %zd free elements (%zd blocks)\n" , elem_count, block_count);
  321.  
  322. }
  323.  
  324. /** @}
  325.  */
  326.