Subversion Repositories HelenOS

Rev

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