Subversion Repositories HelenOS-historic

Rev

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