Subversion Repositories HelenOS

Rev

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