Subversion Repositories HelenOS

Rev

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

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