Subversion Repositories HelenOS

Rev

Rev 3149 | 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 to be useful.
  39.  */
  40.  
  41. #include <mm/buddy.h>
  42. #include <mm/frame.h>
  43. #include <arch/types.h>
  44. #include <debug.h>
  45. #include <print.h>
  46. #include <macros.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
  67. buddy_system_create(buddy_system_t *b, uint8_t max_order,
  68.     buddy_system_operations_t *op, void *data)
  69. {
  70.     int i;
  71.  
  72.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  73.  
  74.     ASSERT(op->find_buddy);
  75.     ASSERT(op->set_order);
  76.     ASSERT(op->get_order);
  77.     ASSERT(op->bisect);
  78.     ASSERT(op->coalesce);
  79.     ASSERT(op->mark_busy);
  80.  
  81.     /*
  82.      * Use memory after our own structure.
  83.      */
  84.     b->order = (link_t *) (&b[1]);
  85.    
  86.     for (i = 0; i <= max_order; i++)
  87.         list_initialize(&b->order[i]);
  88.  
  89.     b->max_order = max_order;
  90.     b->op = op;
  91.     b->data = data;
  92. }
  93.  
  94. /** Check if buddy system can allocate block.
  95.  *
  96.  * @param b     Buddy system pointer.
  97.  * @param i     Size of the block (2^i).
  98.  *
  99.  * @return      True if block can be allocated.
  100.  */
  101. bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i)
  102. {
  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)
  110.         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. /** 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. /** Return block to buddy system.
  223.  *
  224.  * @param b     Buddy system pointer.
  225.  * @param block     Block to return.
  226.  */
  227. void buddy_system_free(buddy_system_t *b, link_t *block)
  228. {
  229.     link_t *buddy, *hlp;
  230.     uint8_t i;
  231.  
  232.     /*
  233.      * Determine block's order.
  234.      */
  235.     i = b->op->get_order(b, block);
  236.  
  237.     ASSERT(i <= b->max_order);
  238.  
  239.     if (i != b->max_order) {
  240.         /*
  241.          * See if there is any buddy in the list of order i.
  242.          */
  243.         buddy = b->op->find_buddy(b, block);
  244.         if (buddy) {
  245.  
  246.             ASSERT(b->op->get_order(b, buddy) == i);
  247.             /*
  248.              * Remove buddy from the list of order i.
  249.              */
  250.             list_remove(buddy);
  251.        
  252.             /*
  253.              * Invalidate order of both block and buddy.
  254.              */
  255.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  256.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  257.        
  258.             /*
  259.              * Coalesce block and buddy into one block.
  260.              */
  261.             hlp = b->op->coalesce(b, block, buddy);
  262.  
  263.             /*
  264.              * Set order of the coalesced block to i + 1.
  265.              */
  266.             b->op->set_order(b, hlp, i + 1);
  267.  
  268.             /*
  269.              * Recursively add the coalesced block to the list of
  270.              * 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.  */
  285.