Subversion Repositories HelenOS

Rev

Rev 381 | Rev 489 | 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.  *
  44.  * @return New buddy system.
  45.  */
  46. buddy_system_t *buddy_system_create(__u8 max_order, buddy_system_operations_t *op)
  47. {
  48.     buddy_system_t *b;
  49.     int i;
  50.  
  51.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  52.  
  53.     ASSERT(op->find_buddy);
  54.     ASSERT(op->set_order);
  55.     ASSERT(op->get_order);
  56.     ASSERT(op->bisect);
  57.     ASSERT(op->coalesce);
  58.  
  59.     /*
  60.      * Allocate memory for structure describing the whole buddy system.
  61.      */
  62.     b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
  63.    
  64.     if (b) {
  65.         /*
  66.          * Allocate memory for all orders this buddy system will work with.
  67.          */
  68.         b->order = (link_t *) early_malloc(max_order * sizeof(link_t));
  69.         if (!b->order) {
  70.             early_free(b);
  71.             return NULL;
  72.         }
  73.    
  74.         for (i = 0; i < max_order; i++)
  75.             list_initialize(&b->order[i]);
  76.    
  77.         b->max_order = max_order;
  78.         b->op = op;
  79.     }
  80.    
  81.     return b;
  82. }
  83.  
  84. /** Allocate block from buddy system.
  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(res);
  134.     b->op->set_order(res, i);
  135.     b->op->set_order(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.  * Return block to buddy system.
  149.  *
  150.  * @param b Buddy system pointer.
  151.  * @param block Block to return.
  152.  */
  153. void buddy_system_free(buddy_system_t *b, link_t *block)
  154. {
  155.     link_t *buddy, *hlp;
  156.     __u8 i;
  157.    
  158.     /*
  159.      * Determine block's order.
  160.      */
  161.     i = b->op->get_order(block);
  162.  
  163.     ASSERT(i < b->max_order);
  164.  
  165.     if (i != b->max_order - 1) {
  166.         /*
  167.          * See if there is any buddy in the list of order i.
  168.          */
  169.         buddy = b->op->find_buddy(block);
  170.         if (buddy) {
  171.  
  172.             ASSERT(b->op->get_order(buddy) == i);
  173.        
  174.             /*
  175.              * Remove buddy from the list of order i.
  176.              */
  177.             list_remove(buddy);
  178.        
  179.             /*
  180.              * Invalidate order of both block and buddy.
  181.              */
  182.             b->op->set_order(block, BUDDY_SYSTEM_INNER_BLOCK);
  183.             b->op->set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK);
  184.        
  185.             /*
  186.              * Coalesce block and buddy into one block.
  187.              */
  188.             hlp = b->op->coalesce(block, buddy);
  189.  
  190.             /*
  191.              * Set order of the coalesced block to i + 1.
  192.              */
  193.             b->op->set_order(hlp, i + 1);
  194.  
  195.             /*
  196.              * Recursively add the coalesced block to the list of order i + 1.
  197.              */
  198.             buddy_system_free(b, hlp);
  199.             return;
  200.         }
  201.     }
  202.  
  203.     /*
  204.      * Insert block into the list of order i.
  205.      */
  206.     list_append(block, &b->order[i]);
  207.  
  208. }
  209.