Subversion Repositories HelenOS

Rev

Rev 489 | Rev 501 | 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. #include <mm/buddy.h>
  30. #include <mm/frame.h>
  31. #include <mm/heap.h>
  32. #include <arch/types.h>
  33. #include <typedefs.h>
  34. #include <list.h>
  35. #include <debug.h>
  36.  
  37. /** Create buddy system
  38.  *
  39.  * Allocate memory for and initialize new buddy system.
  40.  *
  41.  * @param max_order The biggest allocable size will be 2^max_order.
  42.  * @param op Operations for new buddy system.
  43.  * @param data Pointer to be used by implementation.
  44.  *
  45.  * @return New buddy system.
  46.  */
  47. buddy_system_t *buddy_system_create(__u8 max_order, buddy_system_operations_t *op, void *data)
  48. {
  49.     buddy_system_t *b;
  50.     int i;
  51.  
  52.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  53.  
  54.     ASSERT(op->find_buddy);
  55.     ASSERT(op->set_order);
  56.     ASSERT(op->get_order);
  57.     ASSERT(op->bisect);
  58.     ASSERT(op->coalesce);
  59.  
  60.     /*
  61.      * Allocate memory for structure describing the whole buddy system.
  62.      */
  63.     b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
  64.    
  65.     if (b) {
  66.         /*
  67.          * Allocate memory for all orders this buddy system will work with.
  68.          */
  69.         b->order = (link_t *) early_malloc(max_order * sizeof(link_t));
  70.         if (!b->order) {
  71.             early_free(b);
  72.             return NULL;
  73.         }
  74.    
  75.         for (i = 0; i < max_order; i++)
  76.             list_initialize(&b->order[i]);
  77.    
  78.         b->max_order = max_order;
  79.         b->op = op;
  80.         b->data = data;
  81.     }
  82.    
  83.     return b;
  84. }
  85.  
  86. /** Allocate block from buddy system.
  87.  *
  88.  * @param b Buddy system pointer.
  89.  * @param i Returned block will be 2^i big.
  90.  *
  91.  * @return Block of data represented by link_t.
  92.  */
  93. link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
  94. {
  95.     link_t *res, *hlp;
  96.  
  97.     ASSERT(i < b->max_order);
  98.  
  99.     /*
  100.      * If the list of order i is not empty,
  101.      * the request can be immediatelly satisfied.
  102.      */
  103.     if (!list_empty(&b->order[i])) {
  104.         res = b->order[i].next;
  105.         list_remove(res);
  106.         return res;
  107.     }
  108.    
  109.     /*
  110.      * If order i is already the maximal order,
  111.      * the request cannot be satisfied.
  112.      */
  113.     if (i == b->max_order - 1)
  114.         return NULL;
  115.  
  116.     /*
  117.      * Try to recursively satisfy the request from higher order lists.
  118.      */
  119.     hlp = buddy_system_alloc(b, i + 1);
  120.    
  121.     /*
  122.      * The request could not be satisfied
  123.      * from higher order lists.
  124.      */
  125.     if (!hlp)
  126.         return NULL;
  127.        
  128.     res = hlp;
  129.    
  130.     /*
  131.      * Bisect the block and set order of both of its parts to i.
  132.      */
  133.     hlp = b->op->bisect(b, res);
  134.     b->op->set_order(b, res, i);
  135.     b->op->set_order(b, hlp, i);
  136.    
  137.     /*
  138.      * Return the other half to buddy system.
  139.      */
  140.     buddy_system_free(b, hlp);
  141.    
  142.     return res;
  143.    
  144. }
  145.  
  146. /** Return block to buddy system.
  147.  *
  148.  * @param b Buddy system pointer.
  149.  * @param block Block to return.
  150.  */
  151. void buddy_system_free(buddy_system_t *b, link_t *block)
  152. {
  153.     link_t *buddy, *hlp;
  154.     __u8 i;
  155.    
  156.     /*
  157.      * Determine block's order.
  158.      */
  159.     i = b->op->get_order(b, block);
  160.  
  161.     ASSERT(i < b->max_order);
  162.  
  163.     if (i != b->max_order - 1) {
  164.         /*
  165.          * See if there is any buddy in the list of order i.
  166.          */
  167.         buddy = b->op->find_buddy(b, block);
  168.         if (buddy) {
  169.  
  170.             ASSERT(b->op->get_order(b, buddy) == i);
  171.        
  172.             /*
  173.              * Remove buddy from the list of order i.
  174.              */
  175.             list_remove(buddy);
  176.        
  177.             /*
  178.              * Invalidate order of both block and buddy.
  179.              */
  180.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  181.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  182.        
  183.             /*
  184.              * Coalesce block and buddy into one block.
  185.              */
  186.             hlp = b->op->coalesce(b, block, buddy);
  187.  
  188.             /*
  189.              * Set order of the coalesced block to i + 1.
  190.              */
  191.             b->op->set_order(b, hlp, i + 1);
  192.  
  193.             /*
  194.              * Recursively add the coalesced block to the list of order i + 1.
  195.              */
  196.             buddy_system_free(b, hlp);
  197.             return;
  198.         }
  199.     }
  200.  
  201.     /*
  202.      * Insert block into the list of order i.
  203.      */
  204.     list_append(block, &b->order[i]);
  205.  
  206. }
  207.