Subversion Repositories HelenOS-historic

Rev

Rev 683 | Rev 735 | 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. #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 * 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.     ASSERT(i < b->max_order);
  99.    
  100.     for (k=i; k < b->max_order; k++) {
  101.         if (!list_empty(&b->order[k])) {
  102.             return true;
  103.         }
  104.     }
  105.    
  106.     return false;
  107.    
  108. }
  109.  
  110. /** Allocate block from buddy system.
  111.  *
  112.  * @param b Buddy system pointer.
  113.  * @param i Returned block will be 2^i big.
  114.  *
  115.  * @return Block of data represented by link_t.
  116.  */
  117. link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
  118. {
  119.     link_t *res, *hlp;
  120.  
  121.     ASSERT(i < b->max_order);
  122.  
  123.     /*
  124.      * If the list of order i is not empty,
  125.      * the request can be immediatelly satisfied.
  126.      */
  127.     if (!list_empty(&b->order[i])) {
  128.         res = b->order[i].next;
  129.         list_remove(res);
  130.         b->op->mark_busy(b, res);
  131.         return res;
  132.     }
  133.    
  134.     /*
  135.      * If order i is already the maximal order,
  136.      * the request cannot be satisfied.
  137.      */
  138.     if (i == b->max_order - 1)
  139.         return NULL;
  140.  
  141.     /*
  142.      * Try to recursively satisfy the request from higher order lists.
  143.      */
  144.     hlp = buddy_system_alloc(b, i + 1);
  145.    
  146.     /*
  147.      * The request could not be satisfied
  148.      * from higher order lists.
  149.      */
  150.     if (!hlp)
  151.         return NULL;
  152.        
  153.     res = hlp;
  154.    
  155.     /*
  156.      * Bisect the block and set order of both of its parts to i.
  157.      */
  158.     hlp = b->op->bisect(b, res);
  159.     b->op->set_order(b, res, i);
  160.     b->op->set_order(b, hlp, i);
  161.    
  162.     /*
  163.      * Return the other half to buddy system.
  164.      * PROBLEM!!!! FILL FIND OTHER PART AS BUDDY AND LINK TOGETHER
  165.      */
  166.     b->op->mark_busy(b, res);
  167.     buddy_system_free(b, hlp);
  168.    
  169.     return res;
  170.    
  171. }
  172.  
  173. /** Return block to buddy system.
  174.  *
  175.  * @param b Buddy system pointer.
  176.  * @param block Block to return.
  177.  */
  178. void buddy_system_free(buddy_system_t *b, link_t *block)
  179. {
  180.     link_t *buddy, *hlp;
  181.     __u8 i;
  182.  
  183.     /*
  184.      * Determine block's order.
  185.      */
  186.     i = b->op->get_order(b, block);
  187.  
  188.     ASSERT(i < b->max_order);
  189.  
  190.     if (i != b->max_order - 1) {
  191.         /*
  192.          * See if there is any buddy in the list of order i.
  193.          */
  194.         buddy = b->op->find_buddy(b, block);
  195.         if (buddy) {
  196.  
  197.             ASSERT(b->op->get_order(b, buddy) == i);
  198.             /*
  199.              * Remove buddy from the list of order i.
  200.              */
  201.             list_remove(buddy);
  202.        
  203.             /*
  204.              * Invalidate order of both block and buddy.
  205.              */
  206.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  207.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  208.        
  209.             /*
  210.              * Coalesce block and buddy into one block.
  211.              */
  212.             hlp = b->op->coalesce(b, block, buddy);
  213.  
  214.             /*
  215.              * Set order of the coalesced block to i + 1.
  216.              */
  217.             b->op->set_order(b, hlp, i + 1);
  218.  
  219.             /*
  220.              * Recursively add the coalesced block to the list of order i + 1.
  221.              */
  222.             buddy_system_free(b, hlp);
  223.             return;
  224.         }
  225.     }
  226.  
  227.     /*
  228.      * Insert block into the list of order i.
  229.      */
  230.     list_append(block, &b->order[i]);
  231.  
  232. }
  233.  
  234.  
  235.  
  236. /** Prints out structure of buddy system
  237.  *
  238.  * @param b Pointer to buddy system
  239.  * @param es Element size
  240.  */
  241. void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
  242.     index_t i;
  243.     count_t cnt, elem_count = 0, block_count = 0;
  244.     link_t * cur;
  245.    
  246.  
  247.     printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
  248.     printf("-----\t------\t--------\t----------\t---------------\n");
  249.    
  250.     for (i=0;i < b->max_order; i++) {
  251.         cnt = 0;
  252.         if (!list_empty(&b->order[i])) {
  253.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) cnt++;
  254.         }
  255.    
  256.         printf("#%d\t%d\t%d kb\t\t%d kb\t\t%d\n", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
  257.        
  258.         block_count += cnt;
  259.         elem_count += (1 << i) * cnt;
  260.     }
  261.     printf("-----\t------\t--------\t----------\t---------------\n");
  262.     printf("Buddy system contains %d elements (%d blocks)\n" , elem_count, block_count);
  263.  
  264. }
  265.