Subversion Repositories HelenOS

Rev

Rev 2089 | Rev 3206 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
377 jermar 1
/*
2071 jermar 2
 * Copyright (c) 2005 Jakub Jermar
377 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
 
1757 jermar 29
/** @addtogroup genericmm
1702 cejka 30
 * @{
31
 */
32
 
1248 jermar 33
/**
1702 cejka 34
 * @file
1248 jermar 35
 * @brief   Buddy allocator framework.
36
 *
37
 * This file contains buddy system allocator framework.
38
 * Specialized functions are needed for this abstract framework
39
 * to be useful.
40
 */
41
 
377 jermar 42
#include <mm/buddy.h>
43
#include <mm/frame.h>
44
#include <arch/types.h>
45
#include <debug.h>
533 bondari 46
#include <print.h>
3057 decky 47
#include <macros.h>
377 jermar 48
 
814 palkovsky 49
/** Return size needed for the buddy configuration data */
50
size_t buddy_conf_size(int max_order)
51
{
52
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
53
}
54
 
55
 
377 jermar 56
/** Create buddy system
57
 *
58
 * Allocate memory for and initialize new buddy system.
59
 *
1229 jermar 60
 * @param b Preallocated buddy system control data.
377 jermar 61
 * @param max_order The biggest allocable size will be 2^max_order.
62
 * @param op Operations for new buddy system.
490 jermar 63
 * @param data Pointer to be used by implementation.
377 jermar 64
 *
65
 * @return New buddy system.
66
 */
814 palkovsky 67
void buddy_system_create(buddy_system_t *b,
1780 jermar 68
             uint8_t max_order,
814 palkovsky 69
             buddy_system_operations_t *op,
70
             void *data)
377 jermar 71
{
72
    int i;
73
 
378 jermar 74
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
75
 
377 jermar 76
    ASSERT(op->find_buddy);
77
    ASSERT(op->set_order);
78
    ASSERT(op->get_order);
79
    ASSERT(op->bisect);
80
    ASSERT(op->coalesce);
533 bondari 81
    ASSERT(op->mark_busy);
377 jermar 82
 
83
    /*
814 palkovsky 84
     * Use memory after our own structure
85
     */
86
    b->order = (link_t *) (&b[1]);
377 jermar 87
 
814 palkovsky 88
    for (i = 0; i <= max_order; i++)
89
        list_initialize(&b->order[i]);
90
 
91
    b->max_order = max_order;
92
    b->op = op;
93
    b->data = data;
377 jermar 94
}
95
 
533 bondari 96
/** Check if buddy system can allocate block
97
 *
98
 * @param b Buddy system pointer
99
 * @param i Size of the block (2^i)
100
 *
101
 * @return True if block can be allocated
102
 */
1780 jermar 103
bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i) {
104
    uint8_t k;
533 bondari 105
 
735 bondari 106
    /*
107
     * If requested block is greater then maximal block
108
     * we know immediatly that we cannot satisfy the request.
109
     */
110
    if (i > b->max_order) return false;
111
 
112
    /*
113
     * Check if any bigger or equal order has free elements
114
     */
115
    for (k=i; k <= b->max_order; k++) {
533 bondari 116
        if (!list_empty(&b->order[k])) {
117
            return true;
118
        }
119
    }
120
 
121
    return false;
122
 
123
}
124
 
814 palkovsky 125
/** Allocate PARTICULAR block from buddy system
126
 *
127
 * @ return Block of data or NULL if no such block was found
128
 */
129
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
130
{
131
    link_t *left,*right, *tmp;
1780 jermar 132
    uint8_t order;
814 palkovsky 133
 
134
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
135
    ASSERT(left);
136
    list_remove(left);
137
    while (1) {
138
        if (! b->op->get_order(b,left)) {
139
            b->op->mark_busy(b, left);
140
            return left;
141
        }
142
 
143
        order = b->op->get_order(b, left);
144
 
145
        right = b->op->bisect(b, left);
146
        b->op->set_order(b, left, order-1);
147
        b->op->set_order(b, right, order-1);
148
 
149
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
150
 
151
        if (tmp == right) {
152
            right = left;
153
            left = tmp;
822 palkovsky 154
        }
155
        ASSERT(tmp == left);
814 palkovsky 156
        b->op->mark_busy(b, left);
157
        buddy_system_free(b, right);
158
        b->op->mark_available(b, left);
159
    }
160
}
161
 
377 jermar 162
/** Allocate block from buddy system.
163
 *
164
 * @param b Buddy system pointer.
165
 * @param i Returned block will be 2^i big.
166
 *
167
 * @return Block of data represented by link_t.
168
 */
1780 jermar 169
link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
377 jermar 170
{
171
    link_t *res, *hlp;
172
 
735 bondari 173
    ASSERT(i <= b->max_order);
377 jermar 174
 
175
    /*
176
     * If the list of order i is not empty,
177
     * the request can be immediatelly satisfied.
178
     */
179
    if (!list_empty(&b->order[i])) {
180
        res = b->order[i].next;
181
        list_remove(res);
533 bondari 182
        b->op->mark_busy(b, res);
377 jermar 183
        return res;
184
    }
185
    /*
186
     * If order i is already the maximal order,
187
     * the request cannot be satisfied.
188
     */
735 bondari 189
    if (i == b->max_order)
377 jermar 190
        return NULL;
191
 
192
    /*
193
     * Try to recursively satisfy the request from higher order lists.
194
     */
195
    hlp = buddy_system_alloc(b, i + 1);
196
 
197
    /*
198
     * The request could not be satisfied
199
     * from higher order lists.
200
     */
201
    if (!hlp)
202
        return NULL;
203
 
204
    res = hlp;
205
 
206
    /*
207
     * Bisect the block and set order of both of its parts to i.
208
     */
489 jermar 209
    hlp = b->op->bisect(b, res);
210
    b->op->set_order(b, res, i);
211
    b->op->set_order(b, hlp, i);
377 jermar 212
 
213
    /*
814 palkovsky 214
     * Return the other half to buddy system. Mark the first part
815 jermar 215
     * full, so that it won't coalesce again.
377 jermar 216
     */
533 bondari 217
    b->op->mark_busy(b, res);
377 jermar 218
    buddy_system_free(b, hlp);
219
 
220
    return res;
221
 
222
}
223
 
224
/** Return block to buddy system.
225
 *
226
 * @param b Buddy system pointer.
227
 * @param block Block to return.
228
 */
229
void buddy_system_free(buddy_system_t *b, link_t *block)
230
{
231
    link_t *buddy, *hlp;
1780 jermar 232
    uint8_t i;
533 bondari 233
 
377 jermar 234
    /*
235
     * Determine block's order.
236
     */
489 jermar 237
    i = b->op->get_order(b, block);
377 jermar 238
 
735 bondari 239
    ASSERT(i <= b->max_order);
377 jermar 240
 
735 bondari 241
    if (i != b->max_order) {
377 jermar 242
        /*
379 jermar 243
         * See if there is any buddy in the list of order i.
377 jermar 244
         */
489 jermar 245
        buddy = b->op->find_buddy(b, block);
379 jermar 246
        if (buddy) {
247
 
489 jermar 248
            ASSERT(b->op->get_order(b, buddy) == i);
379 jermar 249
            /*
250
             * Remove buddy from the list of order i.
251
             */
252
            list_remove(buddy);
378 jermar 253
 
379 jermar 254
            /*
255
             * Invalidate order of both block and buddy.
256
             */
489 jermar 257
            b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
258
            b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
379 jermar 259
 
260
            /*
261
             * Coalesce block and buddy into one block.
262
             */
489 jermar 263
            hlp = b->op->coalesce(b, block, buddy);
377 jermar 264
 
379 jermar 265
            /*
266
             * Set order of the coalesced block to i + 1.
267
             */
489 jermar 268
            b->op->set_order(b, hlp, i + 1);
377 jermar 269
 
379 jermar 270
            /*
271
             * Recursively add the coalesced block to the list of order i + 1.
272
             */
273
            buddy_system_free(b, hlp);
274
            return;
275
        }
377 jermar 276
    }
277
 
379 jermar 278
    /*
279
     * Insert block into the list of order i.
280
     */
281
    list_append(block, &b->order[i]);
282
 
377 jermar 283
}
683 bondari 284
 
285
/** Prints out structure of buddy system
286
 *
287
 * @param b Pointer to buddy system
1708 jermar 288
 * @param elem_size Element size
683 bondari 289
 */
686 bondari 290
void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
683 bondari 291
    index_t i;
292
    count_t cnt, elem_count = 0, block_count = 0;
3057 decky 293
    link_t *cur;
683 bondari 294
 
295
 
686 bondari 296
    printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
297
    printf("-----\t------\t--------\t----------\t---------------\n");
683 bondari 298
 
3057 decky 299
    for (i = 0;i <= b->max_order; i++) {
683 bondari 300
        cnt = 0;
301
        if (!list_empty(&b->order[i])) {
701 jermar 302
            for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
303
                cnt++;
683 bondari 304
        }
305
 
3057 decky 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);
822 palkovsky 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
 
683 bondari 316
        block_count += cnt;
317
        elem_count += (1 << i) * cnt;
318
    }
686 bondari 319
    printf("-----\t------\t--------\t----------\t---------------\n");
3057 decky 320
    printf("Buddy system contains %" PRIc " free elements (%" PRIc " blocks)\n" , elem_count, block_count);
683 bondari 321
}
1702 cejka 322
 
1757 jermar 323
/** @}
1702 cejka 324
 */