Subversion Repositories HelenOS

Rev

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

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