Subversion Repositories HelenOS

Rev

Rev 1965 | Details | Compare with Previous | Last modification | View Log | RSS feed

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