Subversion Repositories HelenOS

Rev

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

Rev 3424 Rev 3425
Line 33... Line 33...
33
/**
33
/**
34
 * @file
34
 * @file
35
 * @brief   Buddy allocator framework.
35
 * @brief   Buddy allocator framework.
36
 *
36
 *
37
 * This file contains buddy system allocator framework.
37
 * This file contains buddy system allocator framework.
38
 * Specialized functions are needed for this abstract framework
38
 * Specialized functions are needed for this abstract framework to be useful.
39
 * to be useful.
-
 
40
 */
39
 */
41
 
40
 
42
#include <mm/buddy.h>
41
#include <mm/buddy.h>
43
#include <mm/frame.h>
42
#include <mm/frame.h>
44
#include <arch/types.h>
43
#include <arch/types.h>
45
#include <debug.h>
44
#include <debug.h>
46
#include <print.h>
45
#include <print.h>
47
#include <macros.h>
46
#include <macros.h>
48
 
47
 
49
/** Return size needed for the buddy configuration data */
48
/** Return size needed for the buddy configuration data. */
50
size_t buddy_conf_size(int max_order)
49
size_t buddy_conf_size(int max_order)
51
{
50
{
52
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
51
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
53
}
52
}
54
 
53
 
55
 
54
 
56
/** Create buddy system
55
/** Create buddy system.
57
 *
56
 *
58
 * Allocate memory for and initialize new buddy system.
57
 * Allocate memory for and initialize new buddy system.
59
 *
58
 *
60
 * @param b Preallocated buddy system control data.
59
 * @param b     Preallocated buddy system control data.
61
 * @param max_order The biggest allocable size will be 2^max_order.
60
 * @param max_order The biggest allocable size will be 2^max_order.
62
 * @param op Operations for new buddy system.
61
 * @param op        Operations for new buddy system.
63
 * @param data Pointer to be used by implementation.
62
 * @param data      Pointer to be used by implementation.
64
 *
63
 *
65
 * @return New buddy system.
64
 * @return      New buddy system.
66
 */
65
 */
-
 
66
void
67
void buddy_system_create(buddy_system_t *b,
67
buddy_system_create(buddy_system_t *b, uint8_t max_order,
68
             uint8_t max_order,
-
 
69
             buddy_system_operations_t *op,
68
    buddy_system_operations_t *op, void *data)
70
             void *data)
-
 
71
{
69
{
72
    int i;
70
    int i;
73
 
71
 
74
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
72
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
75
 
73
 
Line 79... Line 77...
79
    ASSERT(op->bisect);
77
    ASSERT(op->bisect);
80
    ASSERT(op->coalesce);
78
    ASSERT(op->coalesce);
81
    ASSERT(op->mark_busy);
79
    ASSERT(op->mark_busy);
82
 
80
 
83
    /*
81
    /*
84
     * Use memory after our own structure
82
     * Use memory after our own structure.
85
     */
83
     */
86
    b->order = (link_t *) (&b[1]);
84
    b->order = (link_t *) (&b[1]);
87
   
85
   
88
    for (i = 0; i <= max_order; i++)
86
    for (i = 0; i <= max_order; i++)
89
        list_initialize(&b->order[i]);
87
        list_initialize(&b->order[i]);
Line 91... Line 89...
91
    b->max_order = max_order;
89
    b->max_order = max_order;
92
    b->op = op;
90
    b->op = op;
93
    b->data = data;
91
    b->data = data;
94
}
92
}
95
 
93
 
96
/** Check if buddy system can allocate block
94
/** Check if buddy system can allocate block.
97
 *
95
 *
98
 * @param b Buddy system pointer
96
 * @param b     Buddy system pointer.
99
 * @param i Size of the block (2^i)
97
 * @param i     Size of the block (2^i).
100
 *
98
 *
101
 * @return True if block can be allocated
99
 * @return      True if block can be allocated.
102
 */
100
 */
103
bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i) {
101
bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i)
-
 
102
{
104
    uint8_t k;
103
    uint8_t k;
105
   
104
   
106
    /*
105
    /*
107
     * If requested block is greater then maximal block
106
     * If requested block is greater then maximal block
108
     * we know immediatly that we cannot satisfy the request.
107
     * we know immediatly that we cannot satisfy the request.
109
     */
108
     */
110
    if (i > b->max_order) return false;
109
    if (i > b->max_order)
-
 
110
        return false;
111
 
111
 
112
    /*
112
    /*
113
     * Check if any bigger or equal order has free elements
113
     * Check if any bigger or equal order has free elements
114
     */
114
     */
115
    for (k=i; k <= b->max_order; k++) {
115
    for (k = i; k <= b->max_order; k++) {
116
        if (!list_empty(&b->order[k])) {
116
        if (!list_empty(&b->order[k])) {
117
            return true;
117
            return true;
118
        }
118
        }
119
    }
119
    }
120
   
120
   
121
    return false;
121
    return false;
122
   
-
 
123
}
122
}
124
 
123
 
125
/** Allocate PARTICULAR block from buddy system
124
/** Allocate PARTICULAR block from buddy system.
126
 *
125
 *
127
 * @ return Block of data or NULL if no such block was found
126
 * @return      Block of data or NULL if no such block was found.
128
 */
127
 */
129
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
128
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
130
{
129
{
131
    link_t *left,*right, *tmp;
130
    link_t *left,*right, *tmp;
132
    uint8_t order;
131
    uint8_t order;
133
 
132
 
134
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
133
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
135
    ASSERT(left);
134
    ASSERT(left);
136
    list_remove(left);
135
    list_remove(left);
137
    while (1) {
136
    while (1) {
138
        if (! b->op->get_order(b,left)) {
137
        if (!b->op->get_order(b, left)) {
139
            b->op->mark_busy(b, left);
138
            b->op->mark_busy(b, left);
140
            return left;
139
            return left;
141
        }
140
        }
142
       
141
       
143
        order = b->op->get_order(b, left);
142
        order = b->op->get_order(b, left);
144
 
143
 
145
        right = b->op->bisect(b, left);
144
        right = b->op->bisect(b, left);
146
        b->op->set_order(b, left, order-1);
145
        b->op->set_order(b, left, order - 1);
147
        b->op->set_order(b, right, order-1);
146
        b->op->set_order(b, right, order - 1);
148
 
147
 
149
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
148
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
150
 
149
 
151
        if (tmp == right) {
150
        if (tmp == right) {
152
            right = left;
151
            right = left;
Line 159... Line 158...
159
    }
158
    }
160
}
159
}
161
 
160
 
162
/** Allocate block from buddy system.
161
/** Allocate block from buddy system.
163
 *
162
 *
164
 * @param b Buddy system pointer.
163
 * @param b     Buddy system pointer.
165
 * @param i Returned block will be 2^i big.
164
 * @param i     Returned block will be 2^i big.
166
 *
165
 *
167
 * @return Block of data represented by link_t.
166
 * @return      Block of data represented by link_t.
168
 */
167
 */
169
link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
168
link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
170
{
169
{
171
    link_t *res, *hlp;
170
    link_t *res, *hlp;
172
 
171
 
Line 216... Line 215...
216
     */
215
     */
217
    b->op->mark_busy(b, res);
216
    b->op->mark_busy(b, res);
218
    buddy_system_free(b, hlp);
217
    buddy_system_free(b, hlp);
219
   
218
   
220
    return res;
219
    return res;
221
   
-
 
222
}
220
}
223
 
221
 
224
/** Return block to buddy system.
222
/** Return block to buddy system.
225
 *
223
 *
226
 * @param b Buddy system pointer.
224
 * @param b     Buddy system pointer.
227
 * @param block Block to return.
225
 * @param block     Block to return.
228
 */
226
 */
229
void buddy_system_free(buddy_system_t *b, link_t *block)
227
void buddy_system_free(buddy_system_t *b, link_t *block)
230
{
228
{
231
    link_t *buddy, *hlp;
229
    link_t *buddy, *hlp;
232
    uint8_t i;
230
    uint8_t i;
Line 266... Line 264...
266
             * Set order of the coalesced block to i + 1.
264
             * Set order of the coalesced block to i + 1.
267
             */
265
             */
268
            b->op->set_order(b, hlp, i + 1);
266
            b->op->set_order(b, hlp, i + 1);
269
 
267
 
270
            /*
268
            /*
271
             * Recursively add the coalesced block to the list of order i + 1.
269
             * Recursively add the coalesced block to the list of
-
 
270
             * order i + 1.
272
             */
271
             */
273
            buddy_system_free(b, hlp);
272
            buddy_system_free(b, hlp);
274
            return;
273
            return;
275
        }
274
        }
276
    }
275
    }
277
 
276
 
278
    /*
277
    /*
279
     * Insert block into the list of order i.
278
     * Insert block into the list of order i.
280
     */
279
     */
281
    list_append(block, &b->order[i]);
280
    list_append(block, &b->order[i]);
282
 
-
 
283
}
-
 
284
 
-
 
285
/** Prints out structure of buddy system
-
 
286
 *
-
 
287
 * @param b Pointer to buddy system
-
 
288
 * @param elem_size Element size
-
 
289
 */
-
 
290
void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
-
 
291
    index_t i;
-
 
292
    count_t cnt, elem_count = 0, block_count = 0;
-
 
293
    link_t *cur;
-
 
294
   
-
 
295
 
-
 
296
    printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
-
 
297
    printf("-----\t------\t--------\t----------\t---------------\n");
-
 
298
   
-
 
299
    for (i = 0;i <= b->max_order; i++) {
-
 
300
        cnt = 0;
-
 
301
        if (!list_empty(&b->order[i])) {
-
 
302
            for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
-
 
303
                cnt++;
-
 
304
        }
-
 
305
   
-
 
306
        printf("#%" PRIi "\t%5" PRIc "\t%7" PRIc "K\t%8" PRIi "K\t%6u\t",
-
 
307
            i, cnt, SIZE2KB(cnt * (1 << i) * elem_size), SIZE2KB((1 << i) * elem_size), 1 << i);
-
 
308
        if (!list_empty(&b->order[i])) {
-
 
309
            for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
-
 
310
                b->op->print_id(b, cur);
-
 
311
                printf(" ");
-
 
312
            }
-
 
313
        }
-
 
314
        printf("\n");
-
 
315
           
-
 
316
        block_count += cnt;
-
 
317
        elem_count += (1 << i) * cnt;
-
 
318
    }
-
 
319
    printf("-----\t------\t--------\t----------\t---------------\n");
-
 
320
    printf("Buddy system contains %" PRIc " free elements (%" PRIc " blocks)\n" , elem_count, block_count);
-
 
321
}
281
}
322
 
282
 
323
/** @}
283
/** @}
324
 */
284
 */