Subversion Repositories HelenOS

Rev

Rev 3386 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 3386 Rev 4153
1
/*
1
/*
2
 * Copyright (c) 2005 Jakub Jermar
2
 * Copyright (c) 2005 Jakub Jermar
3
 * All rights reserved.
3
 * All rights reserved.
4
 *
4
 *
5
 * Redistribution and use in source and binary forms, with or without
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
6
 * modification, are permitted provided that the following conditions
7
 * are met:
7
 * are met:
8
 *
8
 *
9
 * - Redistributions of source code must retain the above copyright
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
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
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.
15
 *   derived from this software without specific prior written permission.
16
 *
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
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
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
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
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
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
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.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/** @addtogroup genericmm
29
/** @addtogroup genericmm
30
 * @{
30
 * @{
31
 */
31
 */
32
 
32
 
33
/**
33
/**
34
 * @file
34
 * @file
35
 * @brief   Buddy allocator framework.
35
 * @brief   Buddy allocator framework.
36
 *
36
 *
37
 * This file contains buddy system allocator framework.
37
 * This file contains buddy system allocator framework.
38
 * Specialized functions are needed for this abstract framework to be useful.
38
 * Specialized functions are needed for this abstract framework to be useful.
39
 */
39
 */
40
 
40
 
41
#include <mm/buddy.h>
41
#include <mm/buddy.h>
42
#include <mm/frame.h>
42
#include <mm/frame.h>
43
#include <arch/types.h>
43
#include <arch/types.h>
44
#include <debug.h>
44
#include <debug.h>
45
#include <print.h>
45
#include <print.h>
46
#include <macros.h>
46
#include <macros.h>
47
 
47
 
48
/** Return size needed for the buddy configuration data. */
48
/** Return size needed for the buddy configuration data. */
49
size_t buddy_conf_size(int max_order)
49
size_t buddy_conf_size(size_t max_order)
50
{
50
{
51
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
51
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
52
}
52
}
53
 
53
 
54
 
54
 
55
/** Create buddy system.
55
/** Create buddy system.
56
 *
56
 *
57
 * Allocate memory for and initialize new buddy system.
57
 * Allocate memory for and initialize new buddy system.
58
 *
58
 *
59
 * @param b     Preallocated buddy system control data.
59
 * @param b     Preallocated buddy system control data.
60
 * @param max_order The biggest allocable size will be 2^max_order.
60
 * @param max_order The biggest allocable size will be 2^max_order.
61
 * @param op        Operations for new buddy system.
61
 * @param op        Operations for new buddy system.
62
 * @param data      Pointer to be used by implementation.
62
 * @param data      Pointer to be used by implementation.
63
 *
63
 *
64
 * @return      New buddy system.
64
 * @return      New buddy system.
65
 */
65
 */
66
void
66
void
67
buddy_system_create(buddy_system_t *b, uint8_t max_order,
67
buddy_system_create(buddy_system_t *b, uint8_t max_order,
68
    buddy_system_operations_t *op, void *data)
68
    buddy_system_operations_t *op, void *data)
69
{
69
{
70
    int i;
70
    int i;
71
 
71
 
72
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
72
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
73
 
73
 
74
    ASSERT(op->find_buddy);
74
    ASSERT(op->find_buddy);
75
    ASSERT(op->set_order);
75
    ASSERT(op->set_order);
76
    ASSERT(op->get_order);
76
    ASSERT(op->get_order);
77
    ASSERT(op->bisect);
77
    ASSERT(op->bisect);
78
    ASSERT(op->coalesce);
78
    ASSERT(op->coalesce);
79
    ASSERT(op->mark_busy);
79
    ASSERT(op->mark_busy);
80
 
80
 
81
    /*
81
    /*
82
     * Use memory after our own structure.
82
     * Use memory after our own structure.
83
     */
83
     */
84
    b->order = (link_t *) (&b[1]);
84
    b->order = (link_t *) (&b[1]);
85
   
85
   
86
    for (i = 0; i <= max_order; i++)
86
    for (i = 0; i <= max_order; i++)
87
        list_initialize(&b->order[i]);
87
        list_initialize(&b->order[i]);
88
 
88
 
89
    b->max_order = max_order;
89
    b->max_order = max_order;
90
    b->op = op;
90
    b->op = op;
91
    b->data = data;
91
    b->data = data;
92
}
92
}
93
 
93
 
94
/** Check if buddy system can allocate block.
94
/** Check if buddy system can allocate block.
95
 *
95
 *
96
 * @param b     Buddy system pointer.
96
 * @param b     Buddy system pointer.
97
 * @param i     Size of the block (2^i).
97
 * @param i     Size of the block (2^i).
98
 *
98
 *
99
 * @return      True if block can be allocated.
99
 * @return      True if block can be allocated.
100
 */
100
 */
101
bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i)
101
bool buddy_system_can_alloc(buddy_system_t *b, uint8_t i)
102
{
102
{
103
    uint8_t k;
103
    uint8_t k;
104
   
104
   
105
    /*
105
    /*
106
     * If requested block is greater then maximal block
106
     * If requested block is greater then maximal block
107
     * we know immediatly that we cannot satisfy the request.
107
     * we know immediatly that we cannot satisfy the request.
108
     */
108
     */
109
    if (i > b->max_order)
109
    if (i > b->max_order)
110
        return false;
110
        return false;
111
 
111
 
112
    /*
112
    /*
113
     * Check if any bigger or equal order has free elements
113
     * Check if any bigger or equal order has free elements
114
     */
114
     */
115
    for (k = i; k <= b->max_order; k++) {
115
    for (k = i; k <= b->max_order; k++) {
116
        if (!list_empty(&b->order[k])) {
116
        if (!list_empty(&b->order[k])) {
117
            return true;
117
            return true;
118
        }
118
        }
119
    }
119
    }
120
   
120
   
121
    return false;
121
    return false;
122
}
122
}
123
 
123
 
124
/** Allocate PARTICULAR block from buddy system.
124
/** Allocate PARTICULAR block from buddy system.
125
 *
125
 *
126
 * @return      Block of data or NULL if no such block was found.
126
 * @return      Block of data or NULL if no such block was found.
127
 */
127
 */
128
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
128
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
129
{
129
{
130
    link_t *left,*right, *tmp;
130
    link_t *left,*right, *tmp;
131
    uint8_t order;
131
    uint8_t order;
132
 
132
 
133
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
133
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
134
    ASSERT(left);
134
    ASSERT(left);
135
    list_remove(left);
135
    list_remove(left);
136
    while (1) {
136
    while (1) {
137
        if (!b->op->get_order(b, left)) {
137
        if (!b->op->get_order(b, left)) {
138
            b->op->mark_busy(b, left);
138
            b->op->mark_busy(b, left);
139
            return left;
139
            return left;
140
        }
140
        }
141
       
141
       
142
        order = b->op->get_order(b, left);
142
        order = b->op->get_order(b, left);
143
 
143
 
144
        right = b->op->bisect(b, left);
144
        right = b->op->bisect(b, left);
145
        b->op->set_order(b, left, order - 1);
145
        b->op->set_order(b, left, order - 1);
146
        b->op->set_order(b, right, order - 1);
146
        b->op->set_order(b, right, order - 1);
147
 
147
 
148
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
148
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
149
 
149
 
150
        if (tmp == right) {
150
        if (tmp == right) {
151
            right = left;
151
            right = left;
152
            left = tmp;
152
            left = tmp;
153
        }
153
        }
154
        ASSERT(tmp == left);
154
        ASSERT(tmp == left);
155
        b->op->mark_busy(b, left);
155
        b->op->mark_busy(b, left);
156
        buddy_system_free(b, right);
156
        buddy_system_free(b, right);
157
        b->op->mark_available(b, left);
157
        b->op->mark_available(b, left);
158
    }
158
    }
159
}
159
}
160
 
160
 
161
/** Allocate block from buddy system.
161
/** Allocate block from buddy system.
162
 *
162
 *
163
 * @param b     Buddy system pointer.
163
 * @param b     Buddy system pointer.
164
 * @param i     Returned block will be 2^i big.
164
 * @param i     Returned block will be 2^i big.
165
 *
165
 *
166
 * @return      Block of data represented by link_t.
166
 * @return      Block of data represented by link_t.
167
 */
167
 */
168
link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
168
link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i)
169
{
169
{
170
    link_t *res, *hlp;
170
    link_t *res, *hlp;
171
 
171
 
172
    ASSERT(i <= b->max_order);
172
    ASSERT(i <= b->max_order);
173
 
173
 
174
    /*
174
    /*
175
     * If the list of order i is not empty,
175
     * If the list of order i is not empty,
176
     * the request can be immediatelly satisfied.
176
     * the request can be immediatelly satisfied.
177
     */
177
     */
178
    if (!list_empty(&b->order[i])) {
178
    if (!list_empty(&b->order[i])) {
179
        res = b->order[i].next;
179
        res = b->order[i].next;
180
        list_remove(res);
180
        list_remove(res);
181
        b->op->mark_busy(b, res);
181
        b->op->mark_busy(b, res);
182
        return res;
182
        return res;
183
    }
183
    }
184
    /*
184
    /*
185
     * If order i is already the maximal order,
185
     * If order i is already the maximal order,
186
     * the request cannot be satisfied.
186
     * the request cannot be satisfied.
187
     */
187
     */
188
    if (i == b->max_order)
188
    if (i == b->max_order)
189
        return NULL;
189
        return NULL;
190
 
190
 
191
    /*
191
    /*
192
     * Try to recursively satisfy the request from higher order lists.
192
     * Try to recursively satisfy the request from higher order lists.
193
     */
193
     */
194
    hlp = buddy_system_alloc(b, i + 1);
194
    hlp = buddy_system_alloc(b, i + 1);
195
   
195
   
196
    /*
196
    /*
197
     * The request could not be satisfied
197
     * The request could not be satisfied
198
     * from higher order lists.
198
     * from higher order lists.
199
     */
199
     */
200
    if (!hlp)
200
    if (!hlp)
201
        return NULL;
201
        return NULL;
202
       
202
       
203
    res = hlp;
203
    res = hlp;
204
   
204
   
205
    /*
205
    /*
206
     * Bisect the block and set order of both of its parts to i.
206
     * Bisect the block and set order of both of its parts to i.
207
     */
207
     */
208
    hlp = b->op->bisect(b, res);
208
    hlp = b->op->bisect(b, res);
209
    b->op->set_order(b, res, i);
209
    b->op->set_order(b, res, i);
210
    b->op->set_order(b, hlp, i);
210
    b->op->set_order(b, hlp, i);
211
   
211
   
212
    /*
212
    /*
213
     * Return the other half to buddy system. Mark the first part
213
     * Return the other half to buddy system. Mark the first part
214
     * full, so that it won't coalesce again.
214
     * full, so that it won't coalesce again.
215
     */
215
     */
216
    b->op->mark_busy(b, res);
216
    b->op->mark_busy(b, res);
217
    buddy_system_free(b, hlp);
217
    buddy_system_free(b, hlp);
218
   
218
   
219
    return res;
219
    return res;
220
}
220
}
221
 
221
 
222
/** Return block to buddy system.
222
/** Return block to buddy system.
223
 *
223
 *
224
 * @param b     Buddy system pointer.
224
 * @param b     Buddy system pointer.
225
 * @param block     Block to return.
225
 * @param block     Block to return.
226
 */
226
 */
227
void buddy_system_free(buddy_system_t *b, link_t *block)
227
void buddy_system_free(buddy_system_t *b, link_t *block)
228
{
228
{
229
    link_t *buddy, *hlp;
229
    link_t *buddy, *hlp;
230
    uint8_t i;
230
    uint8_t i;
231
 
231
 
232
    /*
232
    /*
233
     * Determine block's order.
233
     * Determine block's order.
234
     */
234
     */
235
    i = b->op->get_order(b, block);
235
    i = b->op->get_order(b, block);
236
 
236
 
237
    ASSERT(i <= b->max_order);
237
    ASSERT(i <= b->max_order);
238
 
238
 
239
    if (i != b->max_order) {
239
    if (i != b->max_order) {
240
        /*
240
        /*
241
         * See if there is any buddy in the list of order i.
241
         * See if there is any buddy in the list of order i.
242
         */
242
         */
243
        buddy = b->op->find_buddy(b, block);
243
        buddy = b->op->find_buddy(b, block);
244
        if (buddy) {
244
        if (buddy) {
245
 
245
 
246
            ASSERT(b->op->get_order(b, buddy) == i);
246
            ASSERT(b->op->get_order(b, buddy) == i);
247
            /*
247
            /*
248
             * Remove buddy from the list of order i.
248
             * Remove buddy from the list of order i.
249
             */
249
             */
250
            list_remove(buddy);
250
            list_remove(buddy);
251
       
251
       
252
            /*
252
            /*
253
             * Invalidate order of both block and buddy.
253
             * Invalidate order of both block and buddy.
254
             */
254
             */
255
            b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
255
            b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
256
            b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
256
            b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
257
       
257
       
258
            /*
258
            /*
259
             * Coalesce block and buddy into one block.
259
             * Coalesce block and buddy into one block.
260
             */
260
             */
261
            hlp = b->op->coalesce(b, block, buddy);
261
            hlp = b->op->coalesce(b, block, buddy);
262
 
262
 
263
            /*
263
            /*
264
             * Set order of the coalesced block to i + 1.
264
             * Set order of the coalesced block to i + 1.
265
             */
265
             */
266
            b->op->set_order(b, hlp, i + 1);
266
            b->op->set_order(b, hlp, i + 1);
267
 
267
 
268
            /*
268
            /*
269
             * Recursively add the coalesced block to the list of
269
             * Recursively add the coalesced block to the list of
270
             * order i + 1.
270
             * order i + 1.
271
             */
271
             */
272
            buddy_system_free(b, hlp);
272
            buddy_system_free(b, hlp);
273
            return;
273
            return;
274
        }
274
        }
275
    }
275
    }
276
 
276
 
277
    /*
277
    /*
278
     * Insert block into the list of order i.
278
     * Insert block into the list of order i.
279
     */
279
     */
280
    list_append(block, &b->order[i]);
280
    list_append(block, &b->order[i]);
281
}
281
}
282
 
282
 
283
/** @}
283
/** @}
284
 */
284
 */
285
 
285