Subversion Repositories HelenOS

Rev

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