buddy.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2005 Jakub Jermar
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00042 #include <mm/buddy.h>
00043 #include <mm/frame.h>
00044 #include <arch/types.h>
00045 #include <typedefs.h>
00046 #include <adt/list.h>
00047 #include <debug.h>
00048 #include <print.h>
00049 
00051 size_t buddy_conf_size(int max_order)
00052 {
00053         return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
00054 }
00055 
00056 
00068 void buddy_system_create(buddy_system_t *b,
00069                          __u8 max_order, 
00070                          buddy_system_operations_t *op, 
00071                          void *data)
00072 {
00073         int i;
00074 
00075         ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
00076 
00077         ASSERT(op->find_buddy);
00078         ASSERT(op->set_order);
00079         ASSERT(op->get_order);
00080         ASSERT(op->bisect);
00081         ASSERT(op->coalesce);
00082         ASSERT(op->mark_busy);
00083 
00084         /*
00085          * Use memory after our own structure
00086          */
00087         b->order = (link_t *) (&b[1]);
00088         
00089         for (i = 0; i <= max_order; i++)
00090                 list_initialize(&b->order[i]);
00091 
00092         b->max_order = max_order;
00093         b->op = op;
00094         b->data = data;
00095 }
00096 
00104 bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {
00105         __u8 k;
00106         
00107         /*
00108          * If requested block is greater then maximal block
00109          * we know immediatly that we cannot satisfy the request.
00110          */
00111         if (i > b->max_order) return false;
00112 
00113         /*
00114          * Check if any bigger or equal order has free elements
00115          */
00116         for (k=i; k <= b->max_order; k++) {
00117                 if (!list_empty(&b->order[k])) {
00118                         return true;
00119                 }
00120         }
00121         
00122         return false;
00123         
00124 }
00125 
00130 link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
00131 {
00132         link_t *left,*right, *tmp;
00133         __u8 order;
00134 
00135         left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
00136         ASSERT(left);
00137         list_remove(left);
00138         while (1) {
00139                 if (! b->op->get_order(b,left)) {
00140                         b->op->mark_busy(b, left);
00141                         return left;
00142                 }
00143                 
00144                 order = b->op->get_order(b, left);
00145 
00146                 right = b->op->bisect(b, left);
00147                 b->op->set_order(b, left, order-1);
00148                 b->op->set_order(b, right, order-1);
00149 
00150                 tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
00151 
00152                 if (tmp == right) {
00153                         right = left;
00154                         left = tmp;
00155                 } 
00156                 ASSERT(tmp == left);
00157                 b->op->mark_busy(b, left);
00158                 buddy_system_free(b, right);
00159                 b->op->mark_available(b, left);
00160         }
00161 }
00162 
00170 link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
00171 {
00172         link_t *res, *hlp;
00173 
00174         ASSERT(i <= b->max_order);
00175 
00176         /*
00177          * If the list of order i is not empty,
00178          * the request can be immediatelly satisfied.
00179          */
00180         if (!list_empty(&b->order[i])) {
00181                 res = b->order[i].next;
00182                 list_remove(res);
00183                 b->op->mark_busy(b, res);
00184                 return res;
00185         }
00186         /*
00187          * If order i is already the maximal order,
00188          * the request cannot be satisfied.
00189          */
00190         if (i == b->max_order)
00191                 return NULL;
00192 
00193         /*
00194          * Try to recursively satisfy the request from higher order lists.
00195          */     
00196         hlp = buddy_system_alloc(b, i + 1);
00197         
00198         /*
00199          * The request could not be satisfied
00200          * from higher order lists.
00201          */
00202         if (!hlp)
00203                 return NULL;
00204                 
00205         res = hlp;
00206         
00207         /*
00208          * Bisect the block and set order of both of its parts to i.
00209          */
00210         hlp = b->op->bisect(b, res);
00211         b->op->set_order(b, res, i);
00212         b->op->set_order(b, hlp, i);
00213         
00214         /*
00215          * Return the other half to buddy system. Mark the first part
00216          * full, so that it won't coalesce again.
00217          */
00218         b->op->mark_busy(b, res);
00219         buddy_system_free(b, hlp);
00220         
00221         return res;
00222         
00223 }
00224 
00230 void buddy_system_free(buddy_system_t *b, link_t *block)
00231 {
00232         link_t *buddy, *hlp;
00233         __u8 i;
00234 
00235         /*
00236          * Determine block's order.
00237          */
00238         i = b->op->get_order(b, block);
00239 
00240         ASSERT(i <= b->max_order);
00241 
00242         if (i != b->max_order) {
00243                 /*
00244                  * See if there is any buddy in the list of order i.
00245                  */
00246                 buddy = b->op->find_buddy(b, block);
00247                 if (buddy) {
00248 
00249                         ASSERT(b->op->get_order(b, buddy) == i);
00250                         /*
00251                          * Remove buddy from the list of order i.
00252                          */
00253                         list_remove(buddy);
00254                 
00255                         /*
00256                          * Invalidate order of both block and buddy.
00257                          */
00258                         b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
00259                         b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
00260                 
00261                         /*
00262                          * Coalesce block and buddy into one block.
00263                          */
00264                         hlp = b->op->coalesce(b, block, buddy);
00265 
00266                         /*
00267                          * Set order of the coalesced block to i + 1.
00268                          */
00269                         b->op->set_order(b, hlp, i + 1);
00270 
00271                         /*
00272                          * Recursively add the coalesced block to the list of order i + 1.
00273                          */
00274                         buddy_system_free(b, hlp);
00275                         return;
00276                 }
00277         }
00278 
00279         /*
00280          * Insert block into the list of order i.
00281          */
00282         list_append(block, &b->order[i]);
00283 
00284 }
00285 
00291 void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
00292         index_t i;
00293         count_t cnt, elem_count = 0, block_count = 0;
00294         link_t * cur;
00295         
00296 
00297         printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
00298         printf("-----\t------\t--------\t----------\t---------------\n");
00299         
00300         for (i=0;i <= b->max_order; i++) {
00301                 cnt = 0;
00302                 if (!list_empty(&b->order[i])) {
00303                         for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
00304                                 cnt++;
00305                 }
00306         
00307                 printf("#%zd\t%5zd\t%7zdK\t%8zdK\t%6zd\t", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
00308                 if (!list_empty(&b->order[i])) {
00309                         for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
00310                                 b->op->print_id(b, cur);
00311                                 printf(" ");
00312                         }
00313                 }
00314                 printf("\n");
00315                         
00316                 block_count += cnt;
00317                 elem_count += (1 << i) * cnt;
00318         }
00319         printf("-----\t------\t--------\t----------\t---------------\n");
00320         printf("Buddy system contains %zd free elements (%zd blocks)\n" , elem_count, block_count);
00321 
00322 }
00323 

Generated on Sun Jun 18 16:26:58 2006 for HelenOS Kernel (amd64) by  doxygen 1.4.6