Subversion Repositories HelenOS-historic

Rev

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