Subversion Repositories HelenOS

Rev

Rev 788 | Rev 814 | 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 <adt/list.h>
  35. #include <debug.h>
  36. #include <print.h>
  37.  
  38. /** Create buddy system
  39.  *
  40.  * Allocate memory for and initialize new buddy system.
  41.  *
  42.  * @param max_order The biggest allocable size will be 2^max_order.
  43.  * @param op Operations for new buddy system.
  44.  * @param data Pointer to be used by implementation.
  45.  *
  46.  * @return New buddy system.
  47.  */
  48. buddy_system_t *buddy_system_create(__u8 max_order, buddy_system_operations_t *op, void *data)
  49. {
  50.     buddy_system_t *b;
  51.     int i;
  52.  
  53.     ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
  54.  
  55.     ASSERT(op->find_buddy);
  56.     ASSERT(op->set_order);
  57.     ASSERT(op->get_order);
  58.     ASSERT(op->bisect);
  59.     ASSERT(op->coalesce);
  60.     ASSERT(op->mark_busy);
  61.  
  62.     /*
  63.      * Allocate memory for structure describing the whole buddy system.
  64.      */
  65.     b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
  66.    
  67.     if (b) {
  68.         /*
  69.          * Allocate memory for all orders this buddy system will work with.
  70.          */
  71.         b->order = (link_t *) early_malloc((max_order + 1) * sizeof(link_t));
  72.         if (!b->order) {
  73.             early_free(b);
  74.             return NULL;
  75.         }
  76.    
  77.         for (i = 0; i <= max_order; i++)
  78.             list_initialize(&b->order[i]);
  79.    
  80.         b->max_order = max_order;
  81.         b->op = op;
  82.         b->data = data;
  83.     }
  84.    
  85.     return b;
  86. }
  87.  
  88. /** Check if buddy system can allocate block
  89.  *
  90.  * @param b Buddy system pointer
  91.  * @param i Size of the block (2^i)
  92.  *
  93.  * @return True if block can be allocated
  94.  */
  95. bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {
  96.     __u8 k;
  97.    
  98.     /*
  99.      * If requested block is greater then maximal block
  100.      * we know immediatly that we cannot satisfy the request.
  101.      */
  102.     if (i > b->max_order) return false;
  103.  
  104.     /*
  105.      * Check if any bigger or equal order has free elements
  106.      */
  107.     for (k=i; k <= b->max_order; k++) {
  108.         if (!list_empty(&b->order[k])) {
  109.             return true;
  110.         }
  111.     }
  112.    
  113.     return false;
  114.    
  115. }
  116.  
  117. /** Allocate block from buddy system.
  118.  *
  119.  * @param b Buddy system pointer.
  120.  * @param i Returned block will be 2^i big.
  121.  *
  122.  * @return Block of data represented by link_t.
  123.  */
  124. link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
  125. {
  126.     link_t *res, *hlp;
  127.  
  128.     ASSERT(i <= b->max_order);
  129.  
  130.     /*
  131.      * If the list of order i is not empty,
  132.      * the request can be immediatelly satisfied.
  133.      */
  134.     if (!list_empty(&b->order[i])) {
  135.         res = b->order[i].next;
  136.         list_remove(res);
  137.         b->op->mark_busy(b, res);
  138.         return res;
  139.     }
  140.    
  141.     /*
  142.      * If order i is already the maximal order,
  143.      * the request cannot be satisfied.
  144.      */
  145.     if (i == b->max_order)
  146.         return NULL;
  147.  
  148.     /*
  149.      * Try to recursively satisfy the request from higher order lists.
  150.      */
  151.     hlp = buddy_system_alloc(b, i + 1);
  152.    
  153.     /*
  154.      * The request could not be satisfied
  155.      * from higher order lists.
  156.      */
  157.     if (!hlp)
  158.         return NULL;
  159.        
  160.     res = hlp;
  161.    
  162.     /*
  163.      * Bisect the block and set order of both of its parts to i.
  164.      */
  165.     hlp = b->op->bisect(b, res);
  166.     b->op->set_order(b, res, i);
  167.     b->op->set_order(b, hlp, i);
  168.    
  169.     /*
  170.      * Return the other half to buddy system.
  171.      * PROBLEM!!!! WILL FIND OTHER PART AS BUDDY AND LINK TOGETHER
  172.      */
  173.     b->op->mark_busy(b, res);
  174.     buddy_system_free(b, hlp);
  175.    
  176.     return res;
  177.    
  178. }
  179.  
  180. /** Return block to buddy system.
  181.  *
  182.  * @param b Buddy system pointer.
  183.  * @param block Block to return.
  184.  */
  185. void buddy_system_free(buddy_system_t *b, link_t *block)
  186. {
  187.     link_t *buddy, *hlp;
  188.     __u8 i;
  189.  
  190.     /*
  191.      * Determine block's order.
  192.      */
  193.     i = b->op->get_order(b, block);
  194.  
  195.     ASSERT(i <= b->max_order);
  196.  
  197.     if (i != b->max_order) {
  198.         /*
  199.          * See if there is any buddy in the list of order i.
  200.          */
  201.         buddy = b->op->find_buddy(b, block);
  202.         if (buddy) {
  203.  
  204.             ASSERT(b->op->get_order(b, buddy) == i);
  205.             /*
  206.              * Remove buddy from the list of order i.
  207.              */
  208.             list_remove(buddy);
  209.        
  210.             /*
  211.              * Invalidate order of both block and buddy.
  212.              */
  213.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  214.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  215.        
  216.             /*
  217.              * Coalesce block and buddy into one block.
  218.              */
  219.             hlp = b->op->coalesce(b, block, buddy);
  220.  
  221.             /*
  222.              * Set order of the coalesced block to i + 1.
  223.              */
  224.             b->op->set_order(b, hlp, i + 1);
  225.  
  226.             /*
  227.              * Recursively add the coalesced block to the list of order i + 1.
  228.              */
  229.             buddy_system_free(b, hlp);
  230.             return;
  231.         }
  232.     }
  233.  
  234.     /*
  235.      * Insert block into the list of order i.
  236.      */
  237.     list_append(block, &b->order[i]);
  238.  
  239. }
  240.  
  241. /** Prints out structure of buddy system
  242.  *
  243.  * @param b Pointer to buddy system
  244.  * @param es Element size
  245.  */
  246. void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
  247.     index_t i;
  248.     count_t cnt, elem_count = 0, block_count = 0;
  249.     link_t * cur;
  250.    
  251.  
  252.     printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
  253.     printf("-----\t------\t--------\t----------\t---------------\n");
  254.    
  255.     for (i=0;i <= b->max_order; i++) {
  256.         cnt = 0;
  257.         if (!list_empty(&b->order[i])) {
  258.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
  259.                 cnt++;
  260.         }
  261.    
  262.         printf("#%d\t%d\t%dK\t\t%dK\t\t%d\n", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
  263.        
  264.         block_count += cnt;
  265.         elem_count += (1 << i) * cnt;
  266.     }
  267.     printf("-----\t------\t--------\t----------\t---------------\n");
  268.     printf("Buddy system contains %d free elements (%d blocks)\n" , elem_count, block_count);
  269.  
  270. }
  271.