Subversion Repositories HelenOS

Rev

Rev 815 | Rev 1196 | 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.         ASSERT(tmp == left);
  144.         b->op->mark_busy(b, left);
  145.         buddy_system_free(b, right);
  146.         b->op->mark_available(b, left);
  147.     }
  148. }
  149.  
  150. /** Allocate block from buddy system.
  151.  *
  152.  * @param b Buddy system pointer.
  153.  * @param i Returned block will be 2^i big.
  154.  *
  155.  * @return Block of data represented by link_t.
  156.  */
  157. link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
  158. {
  159.     link_t *res, *hlp;
  160.  
  161.     ASSERT(i <= b->max_order);
  162.  
  163.     /*
  164.      * If the list of order i is not empty,
  165.      * the request can be immediatelly satisfied.
  166.      */
  167.     if (!list_empty(&b->order[i])) {
  168.         res = b->order[i].next;
  169.         list_remove(res);
  170.         b->op->mark_busy(b, res);
  171.         return res;
  172.     }
  173.     /*
  174.      * If order i is already the maximal order,
  175.      * the request cannot be satisfied.
  176.      */
  177.     if (i == b->max_order)
  178.         return NULL;
  179.  
  180.     /*
  181.      * Try to recursively satisfy the request from higher order lists.
  182.      */
  183.     hlp = buddy_system_alloc(b, i + 1);
  184.    
  185.     /*
  186.      * The request could not be satisfied
  187.      * from higher order lists.
  188.      */
  189.     if (!hlp)
  190.         return NULL;
  191.        
  192.     res = hlp;
  193.    
  194.     /*
  195.      * Bisect the block and set order of both of its parts to i.
  196.      */
  197.     hlp = b->op->bisect(b, res);
  198.     b->op->set_order(b, res, i);
  199.     b->op->set_order(b, hlp, i);
  200.    
  201.     /*
  202.      * Return the other half to buddy system. Mark the first part
  203.      * full, so that it won't coalesce again.
  204.      */
  205.     b->op->mark_busy(b, res);
  206.     buddy_system_free(b, hlp);
  207.    
  208.     return res;
  209.    
  210. }
  211.  
  212. /** Return block to buddy system.
  213.  *
  214.  * @param b Buddy system pointer.
  215.  * @param block Block to return.
  216.  */
  217. void buddy_system_free(buddy_system_t *b, link_t *block)
  218. {
  219.     link_t *buddy, *hlp;
  220.     __u8 i;
  221.  
  222.     /*
  223.      * Determine block's order.
  224.      */
  225.     i = b->op->get_order(b, block);
  226.  
  227.     ASSERT(i <= b->max_order);
  228.  
  229.     if (i != b->max_order) {
  230.         /*
  231.          * See if there is any buddy in the list of order i.
  232.          */
  233.         buddy = b->op->find_buddy(b, block);
  234.         if (buddy) {
  235.  
  236.             ASSERT(b->op->get_order(b, buddy) == i);
  237.             /*
  238.              * Remove buddy from the list of order i.
  239.              */
  240.             list_remove(buddy);
  241.        
  242.             /*
  243.              * Invalidate order of both block and buddy.
  244.              */
  245.             b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
  246.             b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  247.        
  248.             /*
  249.              * Coalesce block and buddy into one block.
  250.              */
  251.             hlp = b->op->coalesce(b, block, buddy);
  252.  
  253.             /*
  254.              * Set order of the coalesced block to i + 1.
  255.              */
  256.             b->op->set_order(b, hlp, i + 1);
  257.  
  258.             /*
  259.              * Recursively add the coalesced block to the list of order i + 1.
  260.              */
  261.             buddy_system_free(b, hlp);
  262.             return;
  263.         }
  264.     }
  265.  
  266.     /*
  267.      * Insert block into the list of order i.
  268.      */
  269.     list_append(block, &b->order[i]);
  270.  
  271. }
  272.  
  273. /** Prints out structure of buddy system
  274.  *
  275.  * @param b Pointer to buddy system
  276.  * @param es Element size
  277.  */
  278. void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
  279.     index_t i;
  280.     count_t cnt, elem_count = 0, block_count = 0;
  281.     link_t * cur;
  282.    
  283.  
  284.     printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
  285.     printf("-----\t------\t--------\t----------\t---------------\n");
  286.    
  287.     for (i=0;i <= b->max_order; i++) {
  288.         cnt = 0;
  289.         if (!list_empty(&b->order[i])) {
  290.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
  291.                 cnt++;
  292.         }
  293.    
  294.         printf("#%d\t%d\t%dK\t\t%dK\t\t%d\t", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
  295.         if (!list_empty(&b->order[i])) {
  296.             for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
  297.                 b->op->print_id(b, cur);
  298.                 printf(" ");
  299.             }
  300.         }
  301.         printf("\n");
  302.            
  303.         block_count += cnt;
  304.         elem_count += (1 << i) * cnt;
  305.     }
  306.     printf("-----\t------\t--------\t----------\t---------------\n");
  307.     printf("Buddy system contains %d free elements (%d blocks)\n" , elem_count, block_count);
  308.  
  309. }
  310.