Subversion Repositories HelenOS

Rev

Rev 377 | Rev 379 | 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>
34
#include <list.h>
35
#include <debug.h>
36
 
37
/** Create buddy system
38
 *
39
 * Allocate memory for and initialize new buddy system.
40
 *
41
 * @param max_order The biggest allocable size will be 2^max_order.
42
 * @param op Operations for new buddy system.
43
 *
44
 * @return New buddy system.
45
 */
46
buddy_system_t *buddy_system_create(__u8 max_order, buddy_operations_t *op)
47
{
48
    buddy_system_t *b;
49
    int i;
50
 
378 jermar 51
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
52
 
377 jermar 53
    ASSERT(op->find_buddy);
54
    ASSERT(op->set_order);
55
    ASSERT(op->get_order);
56
    ASSERT(op->bisect);
57
    ASSERT(op->coalesce);
58
 
59
    /*
60
     * Allocate memory for structure describing the whole buddy system.
61
     */
62
    b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
63
 
64
    if (b) {
65
        /*
66
         * Allocate memory for all orders this buddy system will work with.
67
         */
68
        b->order = (link_t *) early_malloc(max_order * sizeof(link_t));
69
        if (!b->order) {
70
            early_free(b);
71
            return NULL;
72
        }
73
 
74
        for (i = 0; i < max_order; i++)
75
            list_initialize(&b->order[i]);
76
 
77
        b->max_order = max_order;
78
        b->op = op;
79
    }
80
 
81
    return b;
82
}
83
 
84
/** Allocate block from buddy system.
85
 *
86
 * Allocate block from buddy system.
87
 *
88
 * @param b Buddy system pointer.
89
 * @param i Returned block will be 2^i big.
90
 *
91
 * @return Block of data represented by link_t.
92
 */
93
link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
94
{
95
    link_t *res, *hlp;
96
 
97
    ASSERT(i < b->max_order);
98
 
99
    /*
100
     * If the list of order i is not empty,
101
     * the request can be immediatelly satisfied.
102
     */
103
    if (!list_empty(&b->order[i])) {
104
        res = b->order[i].next;
105
        list_remove(res);
106
        return res;
107
    }
108
 
109
    /*
110
     * If order i is already the maximal order,
111
     * the request cannot be satisfied.
112
     */
113
    if (i == b->max_order - 1)
114
        return NULL;
115
 
116
    /*
117
     * Try to recursively satisfy the request from higher order lists.
118
     */
119
    hlp = buddy_system_alloc(b, i + 1);
120
 
121
    /*
122
     * The request could not be satisfied
123
     * from higher order lists.
124
     */
125
    if (!hlp)
126
        return NULL;
127
 
128
    res = hlp;
129
 
130
    /*
131
     * Bisect the block and set order of both of its parts to i.
132
     */
133
    hlp = b->op->bisect(res);
134
    b->op->set_order(res, i);
135
    b->op->set_order(hlp, i);
136
 
137
    /*
138
     * Return the other half to buddy system.
139
     */
140
    buddy_system_free(b, hlp);
141
 
142
    return res;
143
 
144
}
145
 
146
/** Return block to buddy system.
147
 *
148
 * Return block to buddy system.
149
 *
150
 * @param b Buddy system pointer.
151
 * @param block Block to return.
152
 */
153
void buddy_system_free(buddy_system_t *b, link_t *block)
154
{
155
    link_t *buddy, *hlp;
156
    __u8 i;
157
 
158
    /*
159
     * Determine block's order.
160
     */
161
    i = b->op->get_order(block);
162
 
163
    ASSERT(i < b->max_order);
164
 
165
    /*
166
     * See if there is any buddy in the list of order i.
167
     */
168
    buddy = b->op->find_buddy(block);
169
 
170
    if (buddy && i != b->max_order - 1) {
378 jermar 171
 
172
        ASSERT(b->op->get_order(buddy) == i);
173
 
377 jermar 174
        /*
175
         * Remove buddy from the list of order i.
176
         */
177
        list_remove(buddy);
178
 
179
        /*
378 jermar 180
         * Invalidate order of both block and buddy.
181
         */
182
        b->op->set_order(block, BUDDY_SYSTEM_INNER_BLOCK);
183
        b->op->set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK);
184
 
185
        /*
377 jermar 186
         * Coalesce block and buddy into one block.
187
         */
188
        hlp = b->op->coalesce(block, buddy);
189
 
190
        /*
191
         * Set order of the coalesced block to i + 1.
192
         */
193
        b->op->set_order(hlp, i + 1);
194
 
195
        /*
196
         * Recursively add the coalesced block to the list of order i + 1.
197
         */
198
        buddy_system_free(b, hlp);
199
    }
200
    else {
201
        /*
202
         * Insert block into the list of order i.
203
         */
204
        list_append(block, &b->order[i]);
205
    }
206
 
207
}