Subversion Repositories HelenOS-historic

Rev

Rev 813 | Rev 815 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 813 Rev 814
Line 26... Line 26...
26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
 27 
 */
28 
 
 28 
 
29 
#include <mm/buddy.h>
 29 
#include <mm/buddy.h>
30 
#include <mm/frame.h>
 30 
#include <mm/frame.h>
31 
#include <mm/heap.h>
 - 
 
32 
#include <arch/types.h>
 31 
#include <arch/types.h>
33 
#include <typedefs.h>
 32 
#include <typedefs.h>
34 
#include <adt/list.h>
 33 
#include <adt/list.h>
35 
#include <debug.h>
 34 
#include <debug.h>
36 
#include <print.h>
 35 
#include <print.h>
37 
 
 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 
 
38 
/** Create buddy system
 44 
/** Create buddy system
39 
 *
 45 
 *
40 
 * Allocate memory for and initialize new buddy system.
 46 
 * Allocate memory for and initialize new buddy system.
41 
 *
 47 
 *
- 
 
 48 
 * @param b Preallocated buddy system control data
42 
 * @param max_order The biggest allocable size will be 2^max_order.
 49 
 * @param max_order The biggest allocable size will be 2^max_order.
43 
 * @param op Operations for new buddy system.
 50 
 * @param op Operations for new buddy system.
44 
 * @param data Pointer to be used by implementation.
 51 
 * @param data Pointer to be used by implementation.
45 
 *
 52 
 *
46 
 * @return New buddy system.
 53 
 * @return New buddy system.
47 
 */
 54 
 */
48 
buddy_system_t *buddy_system_create(__u8 max_order, buddy_system_operations_t *op, void *data)
 55 
void buddy_system_create(buddy_system_t *b,
- 
 
 56 
             __u8 max_order,
- 
 
 57 
             buddy_system_operations_t *op,
- 
 
 58 
             void *data)
49 
{
 59 
{
50 
    buddy_system_t *b;
 - 
 
51 
    int i;
 60 
    int i;
52 
 
 61 
 
53 
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
 62 
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
54 
 
 63 
 
55 
    ASSERT(op->find_buddy);
 64 
    ASSERT(op->find_buddy);
Line 58... Line 67...
58 
    ASSERT(op->bisect);
 67 
    ASSERT(op->bisect);
59 
    ASSERT(op->coalesce);
 68 
    ASSERT(op->coalesce);
60 
    ASSERT(op->mark_busy);
 69 
    ASSERT(op->mark_busy);
61 
 
 70 
 
62 
    /*
 71 
    /*
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.
 72 
     * Use memory after our own structure
70 
         */
 73 
     */
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;
 74 
    b->order = (link_t *) (&b[1]);
81 
        b->op = op;
 - 
 
82 
        b->data = data;
 - 
 
83 
    }
 - 
 
84 
   
 75 
   
- 
 
 76 
    for (i = 0; i <= max_order; i++)
- 
 
 77 
        list_initialize(&b->order[i]);
- 
 
 78 
 
- 
 
 79 
    b->max_order = max_order;
85 
    return b;
 80 
    b->op = op;
- 
 
 81 
    b->data = data;
86 
}
 82 
}
87 
 
 83 
 
88 
/** Check if buddy system can allocate block
 84 
/** Check if buddy system can allocate block
89 
 *
 85 
 *
90 
 * @param b Buddy system pointer
 86 
 * @param b Buddy system pointer
Line 112... Line 108...
112 
   
 108 
   
113 
    return false;
 109 
    return false;
114 
   
 110 
   
115 
}
 111 
}
116 
 
 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 
 
117 
/** Allocate block from buddy system.
 149 
/** Allocate block from buddy system.
118 
 *
 150 
 *
119 
 * @param b Buddy system pointer.
 151 
 * @param b Buddy system pointer.
120 
 * @param i Returned block will be 2^i big.
 152 
 * @param i Returned block will be 2^i big.
121 
 *
 153 
 *
Line 135... Line 167...
135 
        res = b->order[i].next;
 167 
        res = b->order[i].next;
136 
        list_remove(res);
 168 
        list_remove(res);
137 
        b->op->mark_busy(b, res);
 169 
        b->op->mark_busy(b, res);
138 
        return res;
 170 
        return res;
139 
    }
 171 
    }
140 
   
 - 
 
141 
    /*
 172 
    /*
142 
     * If order i is already the maximal order,
 173 
     * If order i is already the maximal order,
143 
     * the request cannot be satisfied.
 174 
     * the request cannot be satisfied.
144 
     */
 175 
     */
145 
    if (i == b->max_order)
 176 
    if (i == b->max_order)
Line 165... Line 196...
165 
    hlp = b->op->bisect(b, res);
 196 
    hlp = b->op->bisect(b, res);
166 
    b->op->set_order(b, res, i);
 197 
    b->op->set_order(b, res, i);
167 
    b->op->set_order(b, hlp, i);
 198 
    b->op->set_order(b, hlp, i);
168 
   
 199 
   
169 
    /*
 200 
    /*
170 
     * Return the other half to buddy system.
 201 
     * Return the other half to buddy system. Mark the first part
171 
     * PROBLEM!!!! WILL FIND OTHER PART AS BUDDY AND LINK TOGETHER
 202 
     * full, so that it won't coalsce again.
172 
     */
 203 
     */
173 
    b->op->mark_busy(b, res);
 204 
    b->op->mark_busy(b, res);
174 
    buddy_system_free(b, hlp);
 205 
    buddy_system_free(b, hlp);
175 
   
 206 
   
176 
    return res;
 207 
    return res;