Subversion Repositories HelenOS-historic

Rev

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

Rev 532 Rev 533
1
/*
1
/*
2
 * Copyright (C) 2001-2004 Jakub Jermar
2
 * Copyright (C) 2001-2004 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 <typedefs.h>
29
#include <typedefs.h>
30
#include <arch/types.h>
30
#include <arch/types.h>
31
#include <mm/heap.h>
31
#include <mm/heap.h>
32
#include <mm/frame.h>
32
#include <mm/frame.h>
33
#include <mm/vm.h>
33
#include <mm/vm.h>
34
#include <panic.h>
34
#include <panic.h>
35
#include <debug.h>
35
#include <debug.h>
36
#include <list.h>
36
#include <list.h>
37
#include <synch/spinlock.h>
37
#include <synch/spinlock.h>
38
#include <arch/asm.h>
38
#include <arch/asm.h>
39
#include <arch.h>
39
#include <arch.h>
-
 
40
#include <print.h>
40
 
41
 
41
spinlock_t zone_head_lock;       /**< this lock protects zone_head list */
42
spinlock_t zone_head_lock;       /**< this lock protects zone_head list */
42
link_t zone_head;                /**< list of all zones in the system */
43
link_t zone_head;                /**< list of all zones in the system */
43
 
44
 
-
 
45
region_t zone_blacklist[ZONE_BLACKLIST_SIZE];
-
 
46
count_t zone_blacklist_count = 0;
-
 
47
 
44
static struct buddy_system_operations  zone_buddy_system_operations = {
48
static struct buddy_system_operations  zone_buddy_system_operations = {
45
    .find_buddy = zone_buddy_find_buddy,
49
    .find_buddy = zone_buddy_find_buddy,
46
    .bisect = zone_buddy_bisect,
50
    .bisect = zone_buddy_bisect,
47
    .coalesce = zone_buddy_coalesce,
51
    .coalesce = zone_buddy_coalesce,
48
    .set_order = zone_buddy_set_order,
52
    .set_order = zone_buddy_set_order,
49
    .get_order = zone_buddy_get_order,
53
    .get_order = zone_buddy_get_order,
-
 
54
    .mark_busy = zone_buddy_mark_busy,
50
};
55
};
51
 
56
 
52
/** Initialize physical memory management
57
/** Initialize physical memory management
53
 *
58
 *
54
 * Initialize physical memory managemnt.
59
 * Initialize physical memory managemnt.
55
 */
60
 */
56
void frame_init(void)
61
void frame_init(void)
57
{
62
{
58
    if (config.cpu_active == 1) {
63
    if (config.cpu_active == 1) {
59
        zone_init();
64
        zone_init();
-
 
65
        frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
60
    }
66
    }
61
 
67
 
62
    frame_arch_init();
68
    frame_arch_init();
63
   
-
 
64
    if (config.cpu_active == 1) {
-
 
65
                frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
-
 
66
        }  
-
 
67
}
69
}
68
 
70
 
69
/** Allocate a frame
71
/** Allocate a frame
70
 *
72
 *
71
 * Allocate a frame of physical memory.
73
 * Allocate a frame of physical memory.
72
 *
74
 *
73
 * @param flags Flags for host zone selection and address processing.
75
 * @param flags Flags for host zone selection and address processing.
74
 *
76
 *
75
 * @return Allocated frame.
77
 * @return Allocated frame.
76
 */
78
 */
77
__address frame_alloc(int flags)
79
__address frame_alloc(int flags, __u8 order)
78
{
80
{
79
    ipl_t ipl;
81
    ipl_t ipl;
80
    link_t *cur, *tmp;
82
    link_t *cur, *tmp;
81
    zone_t *z;
83
    zone_t *z;
82
    zone_t *zone = NULL;
84
    zone_t *zone = NULL;
83
    frame_t *frame = NULL;
85
    frame_t *frame = NULL;
84
    __address v;
86
    __address v;
85
   
87
   
86
loop:
88
loop:
87
    ipl = interrupts_disable();
89
    ipl = interrupts_disable();
88
    spinlock_lock(&zone_head_lock);
90
    spinlock_lock(&zone_head_lock);
89
   
91
 
90
    /*
92
    /*
91
     * First, find suitable frame zone.
93
     * First, find suitable frame zone.
92
     */
94
     */
93
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
95
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
94
        z = list_get_instance(cur, zone_t, link);
96
        z = list_get_instance(cur, zone_t, link);
95
       
97
       
96
        spinlock_lock(&z->lock);
98
        spinlock_lock(&z->lock);
97
        /*
99
 
98
         * Check if the zone has any free frames.
100
        /* Check if the zone has 2^order frames area available  */
99
         */
-
 
100
        if (z->free_count) {
101
        if (buddy_system_can_alloc(z->buddy_system, order)) {
101
            zone = z;
102
            zone = z;
102
            break;
103
            break;
103
        }
104
        }
-
 
105
       
104
        spinlock_unlock(&z->lock);
106
        spinlock_unlock(&z->lock);
105
    }
107
    }
106
   
108
   
107
    if (!zone) {
109
    if (!zone) {
108
        if (flags & FRAME_PANIC)
110
        if (flags & FRAME_PANIC)
109
            panic("Can't allocate frame.\n");
111
            panic("Can't allocate frame.\n");
110
       
112
       
111
        /*
113
        /*
112
         * TODO: Sleep until frames are available again.
114
         * TODO: Sleep until frames are available again.
113
         */
115
         */
114
        spinlock_unlock(&zone_head_lock);
116
        spinlock_unlock(&zone_head_lock);
115
        interrupts_restore(ipl);
117
        interrupts_restore(ipl);
116
 
118
 
117
        panic("Sleep not implemented.\n");
119
        panic("Sleep not implemented.\n");
118
        goto loop;
120
        goto loop;
119
    }
121
    }
120
       
122
       
121
    tmp = zone->free_head.next;
-
 
122
    frame = list_get_instance(tmp, frame_t, link);
-
 
123
 
123
 
124
    frame->refcount++;
-
 
125
    list_remove(tmp);           /* remove frame from free_head */
124
    /* Allocate frames from zone buddy system */
126
    zone->free_count--;
-
 
127
    zone->busy_count++;
125
    cur = buddy_system_alloc(zone->buddy_system, order);
128
   
126
   
129
    //v = zone->base + (frame - zone->frames) * FRAME_SIZE;
127
    /* frame will be actually a first frame of the block */
130
    v = FRAME2ADDR(zone, frame);
128
    frame = list_get_instance(cur, frame_t, buddy_link);
131
   
129
   
-
 
130
    /* get frame address */
-
 
131
    v = FRAME2ADDR(zone, frame);
-
 
132
 
132
    if (flags & FRAME_KA)
133
    if (flags & FRAME_KA)
133
        v = PA2KA(v);
134
        v = PA2KA(v);
134
   
135
   
135
    spinlock_unlock(&zone->lock);
136
    spinlock_unlock(&zone->lock);
136
   
-
 
137
    spinlock_unlock(&zone_head_lock);
137
    spinlock_unlock(&zone_head_lock);
138
    interrupts_restore(ipl);
138
    interrupts_restore(ipl);
139
   
-
 
140
    return v;
139
    return v;
-
 
140
 
141
}
141
}
142
 
142
 
143
/** Free a frame.
143
/** Free a frame.
144
 *
144
 *
145
 * Find respective frame structrue for supplied addr.
145
 * Find respective frame structrue for supplied addr.
146
 * Decrement frame reference count.
146
 * Decrement frame reference count.
147
 * If it drops to zero, move the frame structure to free list.
147
 * If it drops to zero, move the frame structure to free list.
148
 *
148
 *
149
 * @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
149
 * @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
150
 */
150
 */
151
void frame_free(__address addr)
151
void frame_free(__address addr)
152
{
152
{
153
    ipl_t ipl;
153
    ipl_t ipl;
154
    link_t *cur;
154
    link_t *cur;
155
    zone_t *z;
155
    zone_t *z;
156
    zone_t *zone = NULL;
156
    zone_t *zone = NULL;
157
    frame_t *frame;
157
    frame_t *frame;
158
   
-
 
159
    ASSERT(addr % FRAME_SIZE == 0);
158
    ASSERT(addr % FRAME_SIZE == 0);
160
   
159
   
161
    ipl = interrupts_disable();
160
    ipl = interrupts_disable();
162
    spinlock_lock(&zone_head_lock);
161
    spinlock_lock(&zone_head_lock);
163
   
162
   
164
    /*
163
    /*
165
     * First, find host frame zone for addr.
164
     * First, find host frame zone for addr.
166
     */
165
     */
167
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
166
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
168
        z = list_get_instance(cur, zone_t, link);
167
        z = list_get_instance(cur, zone_t, link);
169
       
168
       
170
        spinlock_lock(&z->lock);
169
        spinlock_lock(&z->lock);
171
       
170
       
172
        if (IS_KA(addr))
171
        if (IS_KA(addr))
173
            addr = KA2PA(addr);
172
            addr = KA2PA(addr);
174
       
173
       
175
        /*
174
        /*
176
         * Check if addr belongs to z.
175
         * Check if addr belongs to z.
177
         */
176
         */
178
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
177
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
179
            zone = z;
178
            zone = z;
180
            break;
179
            break;
181
        }
180
        }
182
        spinlock_unlock(&z->lock);
181
        spinlock_unlock(&z->lock);
183
    }
182
    }
184
   
183
   
185
    ASSERT(zone != NULL);
184
    ASSERT(zone != NULL);
186
   
185
   
187
    frame = ADDR2FRAME(zone, addr);
186
    frame = ADDR2FRAME(zone, addr);
188
    // frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
-
 
-
 
187
 
189
    ASSERT(frame->refcount);
188
    ASSERT(frame->refcount);
190
 
189
 
191
    if (!--frame->refcount) {
190
    if (!--frame->refcount) {
192
        list_append(&frame->link, &zone->free_head);    /* append frame to free_head */
-
 
193
        zone->free_count++;
-
 
194
        zone->busy_count--;
-
 
195
    }
-
 
196
   
-
 
197
    spinlock_unlock(&zone->lock);  
-
 
198
   
-
 
199
    spinlock_unlock(&zone_head_lock);
-
 
200
    interrupts_restore(ipl);
-
 
201
}
-
 
202
 
-
 
203
/** Mark frame not free.
-
 
204
 *
-
 
205
 * Find respective frame structrue for supplied addr.
-
 
206
 * Increment frame reference count and remove the frame structure from free list.
-
 
207
 *
-
 
208
 * @param addr Address of the frame to be marked. It must be a multiple of FRAME_SIZE.
-
 
209
 */
-
 
210
void frame_not_free(__address addr)
-
 
211
{
-
 
212
    ipl_t ipl;
-
 
213
    link_t *cur;
-
 
214
    zone_t *z;
-
 
215
    zone_t *zone = NULL;
-
 
216
    frame_t *frame;
-
 
217
   
-
 
218
    ASSERT(addr % FRAME_SIZE == 0);
-
 
219
   
-
 
220
    ipl = interrupts_disable();
-
 
221
    spinlock_lock(&zone_head_lock);
-
 
222
   
-
 
223
    /*
-
 
224
     * First, find host frame zone for addr.
-
 
225
     */
-
 
226
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
-
 
227
        z = list_get_instance(cur, zone_t, link);
-
 
228
       
-
 
229
        spinlock_lock(&z->lock);
-
 
230
       
-
 
231
        if (IS_KA(addr))
-
 
232
            addr = KA2PA(addr);
-
 
233
       
-
 
234
        /*
-
 
235
         * Check if addr belongs to z.
-
 
236
         */
-
 
237
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
-
 
238
            zone = z;
-
 
239
            break;
-
 
240
        }
-
 
241
        spinlock_unlock(&z->lock);
-
 
242
    }
-
 
243
   
-
 
244
    ASSERT(zone != NULL);
-
 
245
   
-
 
246
    //frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
-
 
247
    frame = ADDR2FRAME(zone, addr);
-
 
248
 
-
 
249
    if (!frame->refcount) {
-
 
250
        frame->refcount++;
-
 
251
 
-
 
252
        list_remove(&frame->link);          /* remove frame from free_head */
191
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
253
        zone->free_count--;
-
 
254
        zone->busy_count++;
-
 
255
    }
192
    }
256
   
193
   
257
    spinlock_unlock(&zone->lock);  
194
    spinlock_unlock(&zone->lock);  
258
   
195
   
259
    spinlock_unlock(&zone_head_lock);
196
    spinlock_unlock(&zone_head_lock);
260
    interrupts_restore(ipl);
197
    interrupts_restore(ipl);
261
}
198
}
262
 
199
 
263
/** Mark frame region not free.
200
/** Mark frame region not free.
264
 *
201
 *
265
 * Mark frame region not free.
202
 * Mark frame region not free.
266
 *
203
 *
267
 * @param start First address.
204
 * @param start First address.
268
 * @param stop Last address.
205
 * @param stop Last address.
269
 */
206
 */
270
void frame_region_not_free(__address start, __address stop)
207
void frame_region_not_free(__address base, size_t size)
271
{
208
{
272
        __address a;
209
    count_t index;
-
 
210
    index = zone_blacklist_count++;
-
 
211
    ASSERT(base % FRAME_SIZE == 0);
273
 
212
   
274
        start /= FRAME_SIZE;
213
    if (size % FRAME_SIZE != 0) {
-
 
214
        size = size + (FRAME_SIZE - size % FRAME_SIZE);
-
 
215
    }
275
        stop /= FRAME_SIZE;
216
    ASSERT(size % FRAME_SIZE == 0);
-
 
217
    ASSERT(zone_blacklist_count <= ZONE_BLACKLIST_SIZE);
276
        for (a = start; a <= stop; a++)
218
    zone_blacklist[index].base = base;
277
                frame_not_free(a * FRAME_SIZE);
219
    zone_blacklist[index].size = size;
278
}
220
}
279
 
221
 
280
 
222
 
281
/** Initialize zonekeeping
223
/** Initialize zonekeeping
282
 *
224
 *
283
 * Initialize zonekeeping.
225
 * Initialize zonekeeping.
284
 */
226
 */
285
void zone_init(void)
227
void zone_init(void)
286
{
228
{
287
    spinlock_initialize(&zone_head_lock);
229
    spinlock_initialize(&zone_head_lock);
288
    list_initialize(&zone_head);
230
    list_initialize(&zone_head);
289
}
231
}
290
 
232
 
-
 
233
 
-
 
234
void zone_create_in_region(__address base, size_t size) {
-
 
235
    int i;
-
 
236
    zone_t * z;
-
 
237
    __address s; size_t sz;
-
 
238
   
-
 
239
    ASSERT(base % FRAME_SIZE == 0);
-
 
240
    ASSERT(size % FRAME_SIZE == 0);
-
 
241
   
-
 
242
    if (!size) return;
-
 
243
   
-
 
244
    for (i = 0; i < zone_blacklist_count; i++) {
-
 
245
        if (zone_blacklist[i].base >= base && zone_blacklist[i].base < base + size) {
-
 
246
            s = base; sz = zone_blacklist[i].base - base;
-
 
247
            ASSERT(base != s || sz != size);
-
 
248
            zone_create_in_region(s, sz);
-
 
249
           
-
 
250
            s = zone_blacklist[i].base + zone_blacklist[i].size;
-
 
251
            sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);
-
 
252
            ASSERT(base != s || sz != size);
-
 
253
            zone_create_in_region(s, sz);
-
 
254
            return;
-
 
255
       
-
 
256
        }
-
 
257
    }
-
 
258
   
-
 
259
    z = zone_create(base, size, 0);
-
 
260
 
-
 
261
    if (!z) {
-
 
262
        panic("Cannot allocate zone (%dB).\n", size);
-
 
263
    }
-
 
264
   
-
 
265
    zone_attach(z);
-
 
266
}
-
 
267
 
-
 
268
 
-
 
269
 
291
/** Create frame zone
270
/** Create frame zone
292
 *
271
 *
293
 * Create new frame zone.
272
 * Create new frame zone.
294
 *
273
 *
295
 * @param start Physical address of the first frame within the zone.
274
 * @param start Physical address of the first frame within the zone.
296
 * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
275
 * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
297
 * @param flags Zone flags.
276
 * @param flags Zone flags.
298
 *
277
 *
299
 * @return Initialized zone.
278
 * @return Initialized zone.
300
 */
279
 */
301
zone_t *zone_create(__address start, size_t size, int flags)
280
zone_t * zone_create(__address start, size_t size, int flags)
302
{
281
{
303
    zone_t *z;
282
    zone_t *z;
304
    count_t cnt;
283
    count_t cnt;
305
    int i;
284
    int i;
306
    __u8 max_order;
285
    __u8 max_order;
-
 
286
 
-
 
287
    /* hack for bug #10 */
-
 
288
    // if (start == 0x100000) size -= (FRAME_SIZE * 256);
307
   
289
 
-
 
290
    // printf("ZONE_CREATE()   %X - %X (%d kbytes)          \n", start, start+size, size/1024); 
308
    ASSERT(start % FRAME_SIZE == 0);
291
    ASSERT(start % FRAME_SIZE == 0);
309
    ASSERT(size % FRAME_SIZE == 0);
292
    ASSERT(size % FRAME_SIZE == 0);
310
   
293
   
311
    cnt = size / FRAME_SIZE;
294
    cnt = size / FRAME_SIZE;
312
   
295
   
313
    z = (zone_t *) early_malloc(sizeof(zone_t));
296
    z = (zone_t *) early_malloc(sizeof(zone_t));
314
    if (z) {
297
    if (z) {
315
        link_initialize(&z->link);
298
        link_initialize(&z->link);
316
        spinlock_initialize(&z->lock);
299
        spinlock_initialize(&z->lock);
317
   
300
   
318
        z->base = start;
301
        z->base = start;
319
        z->flags = flags;
302
        z->flags = flags;
320
 
303
 
321
        z->free_count = cnt;
304
        z->free_count = cnt;
322
        list_initialize(&z->free_head);
305
        list_initialize(&z->free_head);
323
 
306
 
324
        z->busy_count = 0;
307
        z->busy_count = 0;
325
       
308
       
326
        z->frames = (frame_t *) early_malloc(cnt * sizeof(frame_t));
309
        z->frames = (frame_t *) early_malloc(cnt * sizeof(frame_t));
327
        if (!z->frames) {
310
        if (!z->frames) {
328
            early_free(z);
311
            early_free(z);
329
            return NULL;
312
            return NULL;
330
        }
313
        }
331
       
314
       
332
        for (i = 0; i<cnt; i++) {
315
        for (i = 0; i<cnt; i++) {
333
            frame_initialize(&z->frames[i], z);
316
            frame_initialize(&z->frames[i], z);
334
            list_append(&z->frames[i].link, &z->free_head);
317
            list_append(&z->frames[i].link, &z->free_head);
335
        }
318
        }
336
       
319
       
337
        /*
320
        /*
338
         * Create buddy system for the zone
321
         * Create buddy system for the zone
339
         */
322
         */
340
        for (max_order = 0; cnt >> max_order; max_order++);
323
        for (max_order = 0; cnt >> max_order; max_order++);
341
        z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
324
        z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
-
 
325
       
-
 
326
        /* Stuffing frames */
-
 
327
        for (i = 0; i<cnt; i++) {
-
 
328
            z->frames[i].refcount = 0;
-
 
329
            buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);  
-
 
330
        }
342
    }
331
    }
343
   
-
 
344
    return z;
332
    return z;
345
}
333
}
346
 
334
 
347
/** Attach frame zone
335
/** Attach frame zone
348
 *
336
 *
349
 * Attach frame zone to zone list.
337
 * Attach frame zone to zone list.
350
 *
338
 *
351
 * @param zone Zone to be attached.
339
 * @param zone Zone to be attached.
352
 */
340
 */
353
void zone_attach(zone_t *zone)
341
void zone_attach(zone_t *zone)
354
{
342
{
355
    ipl_t ipl;
343
    ipl_t ipl;
356
   
344
   
357
    ipl = interrupts_disable();
345
    ipl = interrupts_disable();
358
    spinlock_lock(&zone_head_lock);
346
    spinlock_lock(&zone_head_lock);
359
   
347
   
360
    list_append(&zone->link, &zone_head);
348
    list_append(&zone->link, &zone_head);
361
   
349
   
362
    spinlock_unlock(&zone_head_lock);
350
    spinlock_unlock(&zone_head_lock);
363
    interrupts_restore(ipl);
351
    interrupts_restore(ipl);
364
}
352
}
365
 
353
 
366
/** Initialize frame structure
354
/** Initialize frame structure
367
 *
355
 *
368
 * Initialize frame structure.
356
 * Initialize frame structure.
369
 *
357
 *
370
 * @param frame Frame structure to be initialized.
358
 * @param frame Frame structure to be initialized.
371
 * @param zone Host frame zone.
359
 * @param zone Host frame zone.
372
 */
360
 */
373
void frame_initialize(frame_t *frame, zone_t *zone)
361
void frame_initialize(frame_t *frame, zone_t *zone)
374
{
362
{
375
    frame->refcount = 0;
363
    frame->refcount = 1;
-
 
364
    frame->buddy_order = 0;
376
    link_initialize(&frame->link);
365
    link_initialize(&frame->link);
377
}
366
}
378
 
367
 
379
 
368
 
380
 
-
 
381
/*
-
 
382
 * buddy system functions (under construction)
-
 
383
 *
-
 
384
 */
-
 
385
 
-
 
386
 
-
 
387
/** Allocate 2^order frames
-
 
388
 *
-
 
389
 */
-
 
390
__address zone_buddy_frame_alloc(int flags, __u8 order) {
-
 
391
    ipl_t ipl;
-
 
392
    link_t *cur, *tmp;
-
 
393
    zone_t *z;
-
 
394
    zone_t *zone = NULL;
-
 
395
    frame_t *frame = NULL;
-
 
396
    __address v;
-
 
397
   
-
 
398
loop:
-
 
399
    ipl = interrupts_disable();
-
 
400
    spinlock_lock(&zone_head_lock);
-
 
401
   
-
 
402
    /*
-
 
403
     * First, find suitable frame zone.
-
 
404
     */
-
 
405
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
-
 
406
        z = list_get_instance(cur, zone_t, link);
-
 
407
       
-
 
408
        spinlock_lock(&z->lock);
-
 
409
        /*
-
 
410
         * Check if the zone has 2^order frames area available
-
 
411
         * TODO: Must check if buddy system has at least block in order >= given order
-
 
412
         */
-
 
413
        if (z->free_count == (1 >> order)) {
-
 
414
            zone = z;
-
 
415
            break;
-
 
416
        }
-
 
417
       
-
 
418
        spinlock_unlock(&z->lock);
-
 
419
    }
-
 
420
   
-
 
421
    if (!zone) {
-
 
422
        if (flags & FRAME_PANIC)
-
 
423
            panic("Can't allocate frame.\n");
-
 
424
       
-
 
425
        /*
-
 
426
         * TODO: Sleep until frames are available again.
-
 
427
         */
-
 
428
        spinlock_unlock(&zone_head_lock);
-
 
429
        interrupts_restore(ipl);
-
 
430
 
-
 
431
        panic("Sleep not implemented.\n");
-
 
432
        goto loop;
-
 
433
    }
-
 
434
       
-
 
435
 
-
 
436
    /* Allocate frames from zone buddy system */
-
 
437
    cur = buddy_system_alloc(zone->buddy_system, order);
-
 
438
   
-
 
439
    /* frame will be actually a first frame of the block */
-
 
440
    frame = list_get_instance(cur, frame_t, buddy_link);
-
 
441
   
-
 
442
    /* get frame address */
-
 
443
    v = FRAME2ADDR(zone, frame);
-
 
444
   
-
 
445
    if (flags & FRAME_KA)
-
 
446
        v = PA2KA(v);
-
 
447
   
-
 
448
    spinlock_unlock(&zone->lock);
-
 
449
    spinlock_unlock(&zone_head_lock);
-
 
450
    interrupts_restore(ipl);
-
 
451
   
-
 
452
    return v;
-
 
453
}
-
 
454
 
-
 
455
 
-
 
456
/** Free frame(s)
-
 
457
 *
-
 
458
 * @param addr Address of the frame(s) to be freed. It must be a multiple of FRAME_SIZE.
-
 
459
 */
-
 
460
void zone_buddy_frame_free(__address addr)
-
 
461
{
-
 
462
    ipl_t ipl;
-
 
463
    link_t *cur;
-
 
464
    zone_t *z;
-
 
465
    zone_t *zone = NULL;
-
 
466
    frame_t *frame;
-
 
467
   
-
 
468
    ASSERT(addr % FRAME_SIZE == 0);
-
 
469
   
-
 
470
    ipl = interrupts_disable();
-
 
471
    spinlock_lock(&zone_head_lock);
-
 
472
   
-
 
473
    /*
-
 
474
     * First, find host frame zone for addr.
-
 
475
     */
-
 
476
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
-
 
477
        z = list_get_instance(cur, zone_t, link);
-
 
478
       
-
 
479
        spinlock_lock(&z->lock);
-
 
480
       
-
 
481
        if (IS_KA(addr))
-
 
482
            addr = KA2PA(addr);
-
 
483
       
-
 
484
        /*
-
 
485
         * Check if addr belongs to z.
-
 
486
         */
-
 
487
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
-
 
488
            zone = z;
-
 
489
            break;
-
 
490
        }
-
 
491
        spinlock_unlock(&z->lock);
-
 
492
    }
-
 
493
   
-
 
494
    ASSERT(zone != NULL);
-
 
495
   
-
 
496
    frame = ADDR2FRAME(zone, addr);
-
 
497
 
-
 
498
    ASSERT(frame->refcount);
-
 
499
 
-
 
500
    if (!--frame->refcount) {
-
 
501
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
-
 
502
    }
-
 
503
   
-
 
504
    spinlock_unlock(&zone->lock);  
-
 
505
   
-
 
506
    spinlock_unlock(&zone_head_lock);
-
 
507
    interrupts_restore(ipl);
-
 
508
}
-
 
509
 
-
 
510
/** Guess zone by frame instance address
-
 
511
 *
-
 
512
 * @param frame Frame
-
 
513
 *
-
 
514
 * @return Zone of given frame
-
 
515
 */
-
 
516
zone_t * get_zone_by_frame(frame_t * frame) {
-
 
517
    link_t * cur;
-
 
518
    zone_t * zone, *z;
-
 
519
 
-
 
520
    ASSERT(frame);
-
 
521
    /*
-
 
522
     * First, find host frame zone for addr.
-
 
523
     */
-
 
524
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
-
 
525
        z = list_get_instance(cur, zone_t, link);
-
 
526
       
-
 
527
        spinlock_lock(&z->lock);
-
 
528
       
-
 
529
        /*
-
 
530
         * Check if frame address belongs to z.
-
 
531
         */
-
 
532
        if ((frame >= z->frames) && (frame <= z->frames + (z->free_count + z->busy_count))) {
-
 
533
            zone = z;
-
 
534
            break;
-
 
535
        }
-
 
536
        spinlock_unlock(&z->lock);
-
 
537
    }
-
 
538
    ASSERT(zone);
-
 
539
   
-
 
540
    return zone;
-
 
541
 
-
 
542
 
-
 
543
}
-
 
544
 
-
 
545
/** Buddy system find_buddy implementation
369
/** Buddy system find_buddy implementation
546
 *
370
 *
547
 * @param b Buddy system.
371
 * @param b Buddy system.
548
 * @param block Block for which buddy should be found
372
 * @param block Block for which buddy should be found
549
 *
373
 *
550
 * @return Buddy for given block if found
374
 * @return Buddy for given block if found
551
 */
375
 */
552
link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
376
link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
553
    frame_t * frame, * f;
377
    frame_t * frame, * f;
554
    zone_t * zone;
378
    zone_t * zone;
555
    link_t * cur;
379
    link_t * cur;
-
 
380
    count_t index;
556
    bool is_left, is_right;
381
    bool is_left, is_right;
557
 
382
 
558
    frame = list_get_instance(block, frame_t, buddy_link);
383
    frame = list_get_instance(block, frame_t, buddy_link);
559
    zone = get_zone_by_frame(frame);
384
    zone = (zone_t *) b->data;
560
   
-
 
561
   
385
   
562
    /*
386
    /*
563
     * (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY
387
     * (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY
564
     * (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
388
     * (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
565
     */
389
     */
566
     
390
 
567
    is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
391
    is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
568
    is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
392
    is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
569
   
393
   
570
    ASSERT((is_left || is_right) && (!is_left || !is_right));
394
    ASSERT((is_left || is_right) && (!is_left || !is_right));
571
   
395
   
572
    for (cur = &zone->buddy_system->order[frame->buddy_order]; cur; cur = cur->next) {
-
 
573
        f = list_get_instance(cur, frame_t, buddy_link);
-
 
574
       
396
    /*
575
        ASSERT(f->buddy_order == frame->buddy_order);
397
     * test left buddy
576
       
398
     */
577
        /*
399
    if (is_left) {
578
         * if found frame is coherent with our frame from the left
400
        index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
579
         */
401
    } else if (is_right) {
580
        if ((FRAME_INDEX(zone, f) + 1 >> frame->buddy_order == FRAME_INDEX(zone, frame)) && is_right) {
402
        index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
581
            return cur;
-
 
582
        }
403
    }
583
       
404
   
584
        /*
405
    if (FRAME_INDEX_VALID(zone, index)) {
585
         * if found frame is coherent with our frame from the right
406
        if (    zone->frames[index].buddy_order == frame->buddy_order &&
586
         */
-
 
587
        if ((FRAME_INDEX(zone,f) - 1 >> frame->buddy_order == FRAME_INDEX(zone, frame)) && is_left) {
407
            zone->frames[index].refcount == 0) {
588
            return cur;
408
            return &zone->frames[index].buddy_link;
589
        }
409
        }
590
       
-
 
591
    }
410
    }
592
   
411
   
593
    return NULL;
412
    return NULL;
594
   
413
   
595
   
-
 
596
}
414
}
597
 
415
 
598
/** Buddy system bisect implementation
416
/** Buddy system bisect implementation
599
 *
417
 *
600
 * @param b Buddy system.
418
 * @param b Buddy system.
601
 * @param block Block to bisect
419
 * @param block Block to bisect
602
 *
420
 *
603
 * @return right block
421
 * @return right block
604
 */
422
 */
605
link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
423
link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
606
    frame_t * frame_l, * frame_r;
424
    frame_t * frame_l, * frame_r;
607
   
-
 
608
    frame_l = list_get_instance(block, frame_t, buddy_link);
425
    frame_l = list_get_instance(block, frame_t, buddy_link);
609
 
-
 
610
    frame_r = (frame_t *) (&frame_l + (1>>frame_l->buddy_order-1));
426
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
611
 
-
 
612
    return &frame_r->buddy_link;
427
    return &frame_r->buddy_link;
613
   
-
 
614
}
428
}
615
 
429
 
616
/** Buddy system coalesce implementation
430
/** Buddy system coalesce implementation
617
 *
431
 *
618
 * @param b Buddy system.
432
 * @param b Buddy system.
619
 * @param block_1 First block
433
 * @param block_1 First block
620
 * @param block_2 First block's buddy
434
 * @param block_2 First block's buddy
621
 *
435
 *
622
 * @return Coalesced block (actually block that represents lower address)
436
 * @return Coalesced block (actually block that represents lower address)
623
 */
437
 */
624
link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1, link_t * block_2) {
438
link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1, link_t * block_2) {
625
    frame_t * frame1, * frame2;
439
    frame_t * frame1, * frame2;
626
   
-
 
627
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
440
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
628
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
441
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
629
   
-
 
630
    return &frame1 < &frame2 ? block_1 : block_2;
442
    return frame1 < frame2 ? block_1 : block_2;
631
}
443
}
632
 
444
 
633
/** Buddy system set_order implementation
445
/** Buddy system set_order implementation
634
 *
446
 *
635
 * @param b Buddy system.
447
 * @param b Buddy system.
636
 * @param block Buddy system block
448
 * @param block Buddy system block
637
 * @param order Order to set
449
 * @param order Order to set
638
 */
450
 */
639
void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
451
void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
640
    frame_t * frame;
452
    frame_t * frame;
641
    frame = list_get_instance(block, frame_t, buddy_link);
453
    frame = list_get_instance(block, frame_t, buddy_link);
642
    frame->buddy_order = order;
454
    frame->buddy_order = order;
643
}
455
}
644
 
456
 
645
/** Buddy system get_order implementation
457
/** Buddy system get_order implementation
646
 *
458
 *
647
 * @param b Buddy system.
459
 * @param b Buddy system.
648
 * @param block Buddy system block
460
 * @param block Buddy system block
649
 *
461
 *
650
 * @return Order of block
462
 * @return Order of block
651
 */
463
 */
652
__u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
464
__u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
653
    frame_t * frame;
465
    frame_t * frame;
654
    frame = list_get_instance(block, frame_t, buddy_link);
466
    frame = list_get_instance(block, frame_t, buddy_link);
655
    return frame->buddy_order;
467
    return frame->buddy_order;
656
}
468
}
-
 
469
 
-
 
470
/** Buddy system mark_busy implementation
-
 
471
 *
-
 
472
 * @param b Buddy system
-
 
473
 * @param block Buddy system block
-
 
474
 *
-
 
475
 */
-
 
476
void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
-
 
477
    frame_t * frame;
-
 
478
    frame = list_get_instance(block, frame_t, buddy_link);
-
 
479
    frame->refcount = 1;
-
 
480
}
657
 
481