Subversion Repositories HelenOS

Rev

Rev 532 | Rev 534 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1 jermar 1
/*
2
 * Copyright (C) 2001-2004 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
 
368 jermar 29
#include <typedefs.h>
1 jermar 30
#include <arch/types.h>
31
#include <mm/heap.h>
32
#include <mm/frame.h>
33
#include <mm/vm.h>
34
#include <panic.h>
367 jermar 35
#include <debug.h>
368 jermar 36
#include <list.h>
1 jermar 37
#include <synch/spinlock.h>
115 jermar 38
#include <arch/asm.h>
195 vana 39
#include <arch.h>
533 bondari 40
#include <print.h>
115 jermar 41
 
367 jermar 42
spinlock_t zone_head_lock;       /**< this lock protects zone_head list */
43
link_t zone_head;                /**< list of all zones in the system */
44
 
533 bondari 45
region_t zone_blacklist[ZONE_BLACKLIST_SIZE];
46
count_t zone_blacklist_count = 0;
47
 
479 bondari 48
static struct buddy_system_operations  zone_buddy_system_operations = {
49
    .find_buddy = zone_buddy_find_buddy,
50
    .bisect = zone_buddy_bisect,
51
    .coalesce = zone_buddy_coalesce,
52
    .set_order = zone_buddy_set_order,
53
    .get_order = zone_buddy_get_order,
533 bondari 54
    .mark_busy = zone_buddy_mark_busy,
479 bondari 55
};
56
 
368 jermar 57
/** Initialize physical memory management
58
 *
59
 * Initialize physical memory managemnt.
60
 */
1 jermar 61
void frame_init(void)
62
{
125 jermar 63
    if (config.cpu_active == 1) {
367 jermar 64
        zone_init();
533 bondari 65
        frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
1 jermar 66
    }
67
 
68
    frame_arch_init();
69
}
70
 
368 jermar 71
/** Allocate a frame
72
 *
73
 * Allocate a frame of physical memory.
74
 *
75
 * @param flags Flags for host zone selection and address processing.
76
 *
77
 * @return Allocated frame.
1 jermar 78
 */
533 bondari 79
__address frame_alloc(int flags, __u8 order)
1 jermar 80
{
413 jermar 81
    ipl_t ipl;
368 jermar 82
    link_t *cur, *tmp;
83
    zone_t *z;
84
    zone_t *zone = NULL;
85
    frame_t *frame = NULL;
86
    __address v;
1 jermar 87
 
88
loop:
413 jermar 89
    ipl = interrupts_disable();
368 jermar 90
    spinlock_lock(&zone_head_lock);
533 bondari 91
 
368 jermar 92
    /*
93
     * First, find suitable frame zone.
94
     */
95
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
96
        z = list_get_instance(cur, zone_t, link);
1 jermar 97
 
368 jermar 98
        spinlock_lock(&z->lock);
533 bondari 99
 
100
        /* Check if the zone has 2^order frames area available  */
101
        if (buddy_system_can_alloc(z->buddy_system, order)) {
368 jermar 102
            zone = z;
103
            break;
1 jermar 104
        }
533 bondari 105
 
368 jermar 106
        spinlock_unlock(&z->lock);
1 jermar 107
    }
368 jermar 108
 
109
    if (!zone) {
110
        if (flags & FRAME_PANIC)
111
            panic("Can't allocate frame.\n");
112
 
113
        /*
114
         * TODO: Sleep until frames are available again.
115
         */
116
        spinlock_unlock(&zone_head_lock);
413 jermar 117
        interrupts_restore(ipl);
1 jermar 118
 
368 jermar 119
        panic("Sleep not implemented.\n");
120
        goto loop;
121
    }
1 jermar 122
 
368 jermar 123
 
533 bondari 124
    /* Allocate frames from zone buddy system */
125
    cur = buddy_system_alloc(zone->buddy_system, order);
1 jermar 126
 
533 bondari 127
    /* frame will be actually a first frame of the block */
128
    frame = list_get_instance(cur, frame_t, buddy_link);
129
 
130
    /* get frame address */
479 bondari 131
    v = FRAME2ADDR(zone, frame);
533 bondari 132
 
368 jermar 133
    if (flags & FRAME_KA)
134
        v = PA2KA(v);
135
 
136
    spinlock_unlock(&zone->lock);
137
    spinlock_unlock(&zone_head_lock);
413 jermar 138
    interrupts_restore(ipl);
368 jermar 139
    return v;
533 bondari 140
 
1 jermar 141
}
142
 
368 jermar 143
/** Free a frame.
144
 *
145
 * Find respective frame structrue for supplied addr.
146
 * Decrement frame reference count.
147
 * If it drops to zero, move the frame structure to free list.
148
 *
149
 * @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
1 jermar 150
 */
151
void frame_free(__address addr)
152
{
413 jermar 153
    ipl_t ipl;
368 jermar 154
    link_t *cur;
155
    zone_t *z;
156
    zone_t *zone = NULL;
157
    frame_t *frame;
158
    ASSERT(addr % FRAME_SIZE == 0);
1 jermar 159
 
413 jermar 160
    ipl = interrupts_disable();
368 jermar 161
    spinlock_lock(&zone_head_lock);
1 jermar 162
 
368 jermar 163
    /*
164
     * First, find host frame zone for addr.
165
     */
166
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
167
        z = list_get_instance(cur, zone_t, link);
168
 
169
        spinlock_lock(&z->lock);
170
 
171
        if (IS_KA(addr))
172
            addr = KA2PA(addr);
173
 
174
        /*
175
         * Check if addr belongs to z.
176
         */
177
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
178
            zone = z;
179
            break;
1 jermar 180
        }
368 jermar 181
        spinlock_unlock(&z->lock);
1 jermar 182
    }
183
 
368 jermar 184
    ASSERT(zone != NULL);
185
 
479 bondari 186
    frame = ADDR2FRAME(zone, addr);
533 bondari 187
 
368 jermar 188
    ASSERT(frame->refcount);
189
 
190
    if (!--frame->refcount) {
533 bondari 191
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
368 jermar 192
    }
193
 
194
    spinlock_unlock(&zone->lock);  
195
 
196
    spinlock_unlock(&zone_head_lock);
413 jermar 197
    interrupts_restore(ipl);
1 jermar 198
}
199
 
368 jermar 200
/** Mark frame region not free.
201
 *
202
 * Mark frame region not free.
203
 *
204
 * @param start First address.
205
 * @param stop Last address.
206
 */
533 bondari 207
void frame_region_not_free(__address base, size_t size)
1 jermar 208
{
533 bondari 209
    count_t index;
210
    index = zone_blacklist_count++;
211
    ASSERT(base % FRAME_SIZE == 0);
212
 
213
    if (size % FRAME_SIZE != 0) {
214
        size = size + (FRAME_SIZE - size % FRAME_SIZE);
215
    }
216
    ASSERT(size % FRAME_SIZE == 0);
217
    ASSERT(zone_blacklist_count <= ZONE_BLACKLIST_SIZE);
218
    zone_blacklist[index].base = base;
219
    zone_blacklist[index].size = size;
1 jermar 220
}
367 jermar 221
 
368 jermar 222
 
367 jermar 223
/** Initialize zonekeeping
224
 *
225
 * Initialize zonekeeping.
226
 */
227
void zone_init(void)
228
{
229
    spinlock_initialize(&zone_head_lock);
230
    list_initialize(&zone_head);
231
}
232
 
533 bondari 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
 
367 jermar 270
/** Create frame zone
271
 *
272
 * Create new frame zone.
273
 *
274
 * @param start Physical address of the first frame within the zone.
275
 * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
276
 * @param flags Zone flags.
277
 *
278
 * @return Initialized zone.
279
 */
533 bondari 280
zone_t * zone_create(__address start, size_t size, int flags)
367 jermar 281
{
282
    zone_t *z;
283
    count_t cnt;
284
    int i;
479 bondari 285
    __u8 max_order;
533 bondari 286
 
287
    /* hack for bug #10 */
288
    // if (start == 0x100000) size -= (FRAME_SIZE * 256);
289
 
290
    // printf("ZONE_CREATE()   %X - %X (%d kbytes)          \n", start, start+size, size/1024); 
367 jermar 291
    ASSERT(start % FRAME_SIZE == 0);
292
    ASSERT(size % FRAME_SIZE == 0);
293
 
294
    cnt = size / FRAME_SIZE;
295
 
374 jermar 296
    z = (zone_t *) early_malloc(sizeof(zone_t));
367 jermar 297
    if (z) {
298
        link_initialize(&z->link);
299
        spinlock_initialize(&z->lock);
300
 
301
        z->base = start;
302
        z->flags = flags;
303
 
304
        z->free_count = cnt;
305
        list_initialize(&z->free_head);
306
 
307
        z->busy_count = 0;
308
 
374 jermar 309
        z->frames = (frame_t *) early_malloc(cnt * sizeof(frame_t));
367 jermar 310
        if (!z->frames) {
375 jermar 311
            early_free(z);
367 jermar 312
            return NULL;
313
        }
314
 
315
        for (i = 0; i<cnt; i++) {
316
            frame_initialize(&z->frames[i], z);
317
            list_append(&z->frames[i].link, &z->free_head);
318
        }
319
 
479 bondari 320
        /*
321
         * Create buddy system for the zone
322
         */
323
        for (max_order = 0; cnt >> max_order; max_order++);
489 jermar 324
        z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
533 bondari 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
        }
367 jermar 331
    }
332
    return z;
333
}
334
 
335
/** Attach frame zone
336
 *
337
 * Attach frame zone to zone list.
338
 *
339
 * @param zone Zone to be attached.
340
 */
341
void zone_attach(zone_t *zone)
342
{
413 jermar 343
    ipl_t ipl;
367 jermar 344
 
413 jermar 345
    ipl = interrupts_disable();
367 jermar 346
    spinlock_lock(&zone_head_lock);
347
 
348
    list_append(&zone->link, &zone_head);
349
 
350
    spinlock_unlock(&zone_head_lock);
413 jermar 351
    interrupts_restore(ipl);
367 jermar 352
}
353
 
354
/** Initialize frame structure
355
 *
356
 * Initialize frame structure.
357
 *
358
 * @param frame Frame structure to be initialized.
359
 * @param zone Host frame zone.
360
 */
361
void frame_initialize(frame_t *frame, zone_t *zone)
362
{
533 bondari 363
    frame->refcount = 1;
364
    frame->buddy_order = 0;
367 jermar 365
    link_initialize(&frame->link);
366
}
479 bondari 367
 
368
 
369
/** Buddy system find_buddy implementation
489 jermar 370
 *
371
 * @param b Buddy system.
480 bondari 372
 * @param block Block for which buddy should be found
479 bondari 373
 *
480 bondari 374
 * @return Buddy for given block if found
479 bondari 375
 */
489 jermar 376
link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
480 bondari 377
    frame_t * frame, * f;
378
    zone_t * zone;
379
    link_t * cur;
533 bondari 380
    count_t index;
480 bondari 381
    bool is_left, is_right;
479 bondari 382
 
480 bondari 383
    frame = list_get_instance(block, frame_t, buddy_link);
533 bondari 384
    zone = (zone_t *) b->data;
480 bondari 385
 
386
    /*
387
     * (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY
388
     * (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
389
     */
533 bondari 390
 
480 bondari 391
    is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
392
    is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
393
 
394
    ASSERT((is_left || is_right) && (!is_left || !is_right));
395
 
533 bondari 396
    /*
397
     * test left buddy
398
     */
399
    if (is_left) {
400
        index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
401
    } else if (is_right) {
402
        index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
403
    }
404
 
405
    if (FRAME_INDEX_VALID(zone, index)) {
406
        if (    zone->frames[index].buddy_order == frame->buddy_order &&
407
            zone->frames[index].refcount == 0) {
408
            return &zone->frames[index].buddy_link;
480 bondari 409
        }
410
    }
411
 
412
    return NULL;
413
 
479 bondari 414
}
415
 
416
/** Buddy system bisect implementation
417
 *
489 jermar 418
 * @param b Buddy system.
480 bondari 419
 * @param block Block to bisect
420
 *
421
 * @return right block
479 bondari 422
 */
489 jermar 423
link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
480 bondari 424
    frame_t * frame_l, * frame_r;
425
    frame_l = list_get_instance(block, frame_t, buddy_link);
533 bondari 426
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
480 bondari 427
    return &frame_r->buddy_link;
479 bondari 428
}
429
 
430
/** Buddy system coalesce implementation
431
 *
489 jermar 432
 * @param b Buddy system.
480 bondari 433
 * @param block_1 First block
434
 * @param block_2 First block's buddy
435
 *
436
 * @return Coalesced block (actually block that represents lower address)
479 bondari 437
 */
489 jermar 438
link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1, link_t * block_2) {
480 bondari 439
    frame_t * frame1, * frame2;
440
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
441
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
533 bondari 442
    return frame1 < frame2 ? block_1 : block_2;
479 bondari 443
}
444
 
445
/** Buddy system set_order implementation
489 jermar 446
 *
447
 * @param b Buddy system.
480 bondari 448
 * @param block Buddy system block
449
 * @param order Order to set
479 bondari 450
 */
489 jermar 451
void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
480 bondari 452
    frame_t * frame;
453
    frame = list_get_instance(block, frame_t, buddy_link);
454
    frame->buddy_order = order;
479 bondari 455
}
456
 
457
/** Buddy system get_order implementation
489 jermar 458
 *
459
 * @param b Buddy system.
480 bondari 460
 * @param block Buddy system block
479 bondari 461
 *
480 bondari 462
 * @return Order of block
479 bondari 463
 */
489 jermar 464
__u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
480 bondari 465
    frame_t * frame;
466
    frame = list_get_instance(block, frame_t, buddy_link);
467
    return frame->buddy_order;
479 bondari 468
}
533 bondari 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
}