Subversion Repositories HelenOS

Rev

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