Subversion Repositories HelenOS

Rev

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

Rev Author Line No. Line
1 jermar 1
/*
564 jermar 2
 * Copyright (C) 2001-2005 Jakub Jermar
3
 * Copyright (C) 2005 Sergey Bondari
1 jermar 4
 * All rights reserved.
5
 *
6
 * Redistribution and use in source and binary forms, with or without
7
 * modification, are permitted provided that the following conditions
8
 * are met:
9
 *
10
 * - Redistributions of source code must retain the above copyright
11
 *   notice, this list of conditions and the following disclaimer.
12
 * - Redistributions in binary form must reproduce the above copyright
13
 *   notice, this list of conditions and the following disclaimer in the
14
 *   documentation and/or other materials provided with the distribution.
15
 * - The name of the author may not be used to endorse or promote products
16
 *   derived from this software without specific prior written permission.
17
 *
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
 */
29
 
814 palkovsky 30
/*
31
 * Locking order
32
 *
33
 * In order to access particular zone, the process must first lock
34
 * the zones.lock, then lock the zone and then unlock the zones.lock.
35
 * This insures, that we can fiddle with the zones in runtime without
36
 * affecting the processes.
37
 *
38
 */
39
 
368 jermar 40
#include <typedefs.h>
1 jermar 41
#include <arch/types.h>
42
#include <mm/frame.h>
703 jermar 43
#include <mm/as.h>
1 jermar 44
#include <panic.h>
367 jermar 45
#include <debug.h>
788 jermar 46
#include <adt/list.h>
1 jermar 47
#include <synch/spinlock.h>
115 jermar 48
#include <arch/asm.h>
195 vana 49
#include <arch.h>
533 bondari 50
#include <print.h>
536 bondari 51
#include <align.h>
814 palkovsky 52
#include <mm/slab.h>
822 palkovsky 53
#include <bitops.h>
115 jermar 54
 
814 palkovsky 55
typedef struct {
56
    count_t refcount;   /**< tracking of shared frames  */
57
    __u8 buddy_order;   /**< buddy system block order */
58
    link_t buddy_link;  /**< link to the next free block inside one order */
59
    void *parent;           /**< If allocated by slab, this points there */
60
}frame_t;
367 jermar 61
 
814 palkovsky 62
typedef struct {
63
    SPINLOCK_DECLARE(lock); /**< this lock protects everything below */
64
    pfn_t base; /**< frame_no of the first frame in the frames array */
820 jermar 65
    count_t count;          /**< Size of zone */
533 bondari 66
 
814 palkovsky 67
    frame_t *frames;    /**< array of frame_t structures in this zone */
68
    count_t free_count; /**< number of free frame_t structures */
69
    count_t busy_count; /**< number of busy frame_t structures */
70
 
71
    buddy_system_t * buddy_system; /**< buddy system for the zone */
72
    int flags;
73
}zone_t;
479 bondari 74
 
814 palkovsky 75
/*
76
 * The zoneinfo.lock must be locked when accessing zoneinfo structure.
77
 * Some of the attributes in zone_t structures are 'read-only'
368 jermar 78
 */
1 jermar 79
 
814 palkovsky 80
struct {
81
    SPINLOCK_DECLARE(lock);
82
    int count;
83
    zone_t *info[ZONES_MAX];
84
}zones;
1 jermar 85
 
814 palkovsky 86
 
87
/*********************************/
88
/* Helper functions */
89
static inline index_t frame_index(zone_t *zone, frame_t *frame)
762 palkovsky 90
{
814 palkovsky 91
    return (index_t)(frame - zone->frames);
762 palkovsky 92
}
814 palkovsky 93
static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
1 jermar 94
{
814 palkovsky 95
    return (index_t)(frame - zone->frames) + zone->base;
1 jermar 96
}
814 palkovsky 97
static inline int frame_index_valid(zone_t *zone, index_t index)
98
{
99
    return index >= 0 && index < zone->count;
100
}
1 jermar 101
 
814 palkovsky 102
/** Compute pfn_t from frame_t pointer & zone pointer */
820 jermar 103
static index_t make_frame_index(zone_t *zone, frame_t *frame)
762 palkovsky 104
{
814 palkovsky 105
    return frame - zone->frames;
762 palkovsky 106
}
107
 
814 palkovsky 108
/** Initialize frame structure
762 palkovsky 109
 *
814 palkovsky 110
 * Initialize frame structure.
111
 *
112
 * @param frame Frame structure to be initialized.
762 palkovsky 113
 */
814 palkovsky 114
static void frame_initialize(frame_t *frame)
762 palkovsky 115
{
814 palkovsky 116
    frame->refcount = 1;
117
    frame->buddy_order = 0;
762 palkovsky 118
}
119
 
814 palkovsky 120
/*************************************/
121
/* Zoneinfo functions */
762 palkovsky 122
 
814 palkovsky 123
/**
124
 * Insert-sort zone into zones list
822 palkovsky 125
 *
126
 * @return zone number on success, -1 on error
1 jermar 127
 */
822 palkovsky 128
static int zones_add_zone(zone_t *newzone)
1 jermar 129
{
822 palkovsky 130
    int i,j;
131
    ipl_t ipl;
132
    zone_t *z;
762 palkovsky 133
 
822 palkovsky 134
    ipl = interrupts_disable();
814 palkovsky 135
    spinlock_lock(&zones.lock);
136
    /* Try to merge */
822 palkovsky 137
    if (zones.count+1 == ZONES_MAX)
138
        panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
533 bondari 139
 
822 palkovsky 140
    for (i=0; i < zones.count; i++) {
141
        /* Check for overflow */
142
        z = zones.info[zones.count];
143
        if (overlaps(newzone->base,newzone->count,
144
                 z->base, z->count)) {
145
            printf("Zones overlap!\n");
146
            return -1;
814 palkovsky 147
        }
822 palkovsky 148
        if (z->base < newzone->base)
149
            break;
368 jermar 150
    }
822 palkovsky 151
    /* Move other zones up */
152
    for (j=i;j < zones.count;j++)
153
        zones.info[j+1] = zones.info[j];
154
 
155
    zones.info[i] = newzone;
156
    zones.count++;
157
 
814 palkovsky 158
    spinlock_unlock(&zones.lock);
822 palkovsky 159
    interrupts_restore(ipl);
160
 
161
    return i;
1 jermar 162
}
163
 
814 palkovsky 164
/**
165
 * Try to find a zone where can we find the frame
368 jermar 166
 *
814 palkovsky 167
 * @param hint Start searching in zone 'hint'
168
 * @param lock Lock zone if true
368 jermar 169
 *
814 palkovsky 170
 * Assume interrupts disable
368 jermar 171
 */
814 palkovsky 172
static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
1 jermar 173
{
533 bondari 174
    int i;
814 palkovsky 175
    int hint = pzone ? *pzone : 0;
176
    zone_t *z;
533 bondari 177
 
814 palkovsky 178
    spinlock_lock(&zones.lock);
179
 
180
    if (hint >= zones.count || hint < 0)
181
        hint = 0;
533 bondari 182
 
814 palkovsky 183
    i = hint;
184
    do {
185
        z = zones.info[i];
186
        spinlock_lock(&z->lock);
187
        if (z->base <= frame && z->base + z->count > frame) {
188
            spinlock_unlock(&zones.lock); /* Unlock the global lock */
189
            if (pzone)
190
                *pzone = i;
191
            return z;
533 bondari 192
        }
814 palkovsky 193
        spinlock_unlock(&z->lock);
533 bondari 194
 
814 palkovsky 195
        i++;
196
        if (i >= zones.count)
197
            i = 0;
198
    } while(i != hint);
199
 
200
    spinlock_unlock(&zones.lock);
201
    return NULL;
533 bondari 202
}
203
 
822 palkovsky 204
/** @return True if zone can allocate specified order */
205
static int zone_can_alloc(zone_t *z, __u8 order)
206
{
207
    return buddy_system_can_alloc(z->buddy_system, order);
208
}
209
 
814 palkovsky 210
/**
211
 * Find AND LOCK zone that can allocate order frames
367 jermar 212
 *
814 palkovsky 213
 * Assume interrupts are disabled!!
367 jermar 214
 *
814 palkovsky 215
 * @param pzone Pointer to preferred zone or NULL, on return contains zone number
367 jermar 216
 */
814 palkovsky 217
static zone_t * find_free_zone_lock(__u8 order, int *pzone)
367 jermar 218
{
814 palkovsky 219
    int i;
367 jermar 220
    zone_t *z;
814 palkovsky 221
    int hint = pzone ? *pzone : 0;
367 jermar 222
 
814 palkovsky 223
    spinlock_lock(&zones.lock);
224
    if (hint >= zones.count)
225
        hint = 0;
226
    i = hint;
227
    do {
228
        z = zones.info[i];
724 palkovsky 229
 
814 palkovsky 230
        spinlock_lock(&z->lock);
367 jermar 231
 
814 palkovsky 232
        /* Check if the zone has 2^order frames area available  */
822 palkovsky 233
        if (zone_can_alloc(z, order)) {
814 palkovsky 234
            spinlock_unlock(&zones.lock);
235
            if (pzone)
236
                *pzone = i;
237
            return z;
367 jermar 238
        }
814 palkovsky 239
        spinlock_unlock(&z->lock);
240
        if (++i >= zones.count)
241
            i = 0;
242
    } while(i != hint);
243
    spinlock_unlock(&zones.lock);
244
    return NULL;
367 jermar 245
}
246
 
814 palkovsky 247
/********************************************/
248
/* Buddy system functions */
249
 
250
/** Buddy system find_block implementation
367 jermar 251
 *
814 palkovsky 252
 * Find block that is parent of current list.
253
 * That means go to lower addresses, until such block is found
367 jermar 254
 *
814 palkovsky 255
 * @param order - Order of parent must be different then this parameter!!
367 jermar 256
 */
814 palkovsky 257
static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
258
                     __u8 order)
367 jermar 259
{
814 palkovsky 260
    frame_t * frame;
261
    zone_t * zone;
262
    index_t index;
367 jermar 263
 
814 palkovsky 264
    frame = list_get_instance(child, frame_t, buddy_link);
265
    zone = (zone_t *) b->data;
367 jermar 266
 
814 palkovsky 267
    index = frame_index(zone, frame);
268
    do {
269
        if (zone->frames[index].buddy_order != order) {
270
            return &zone->frames[index].buddy_link;
271
        }
272
    } while(index-- > 0);
273
    return NULL;
367 jermar 274
}
479 bondari 275
 
822 palkovsky 276
static void zone_buddy_print_id(buddy_system_t *b, link_t *block)
277
{
278
    frame_t * frame;
279
    zone_t * zone;
280
    index_t index;
479 bondari 281
 
822 palkovsky 282
    frame = list_get_instance(block, frame_t, buddy_link);
283
    zone = (zone_t *) b->data;
284
    index = frame_index(zone, frame);
285
    printf("%d", index);
286
}                    
287
 
479 bondari 288
/** Buddy system find_buddy implementation
489 jermar 289
 *
290
 * @param b Buddy system.
480 bondari 291
 * @param block Block for which buddy should be found
479 bondari 292
 *
480 bondari 293
 * @return Buddy for given block if found
479 bondari 294
 */
814 palkovsky 295
static link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block)
296
{
539 jermar 297
    frame_t * frame;
480 bondari 298
    zone_t * zone;
564 jermar 299
    index_t index;
480 bondari 300
    bool is_left, is_right;
479 bondari 301
 
480 bondari 302
    frame = list_get_instance(block, frame_t, buddy_link);
533 bondari 303
    zone = (zone_t *) b->data;
814 palkovsky 304
    ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
480 bondari 305
 
724 palkovsky 306
    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
307
    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
814 palkovsky 308
 
564 jermar 309
    ASSERT(is_left ^ is_right);
533 bondari 310
    if (is_left) {
814 palkovsky 311
        index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
615 palkovsky 312
    } else { // if (is_right)
814 palkovsky 313
        index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
533 bondari 314
    }
315
 
814 palkovsky 316
 
317
    if (frame_index_valid(zone, index)) {
318
        if (zone->frames[index].buddy_order == frame->buddy_order &&
319
            zone->frames[index].refcount == 0) {
533 bondari 320
            return &zone->frames[index].buddy_link;
480 bondari 321
        }
322
    }
814 palkovsky 323
 
539 jermar 324
    return NULL;   
479 bondari 325
}
326
 
327
/** Buddy system bisect implementation
328
 *
489 jermar 329
 * @param b Buddy system.
480 bondari 330
 * @param block Block to bisect
331
 *
332
 * @return right block
479 bondari 333
 */
814 palkovsky 334
static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
480 bondari 335
    frame_t * frame_l, * frame_r;
564 jermar 336
 
480 bondari 337
    frame_l = list_get_instance(block, frame_t, buddy_link);
533 bondari 338
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
564 jermar 339
 
480 bondari 340
    return &frame_r->buddy_link;
479 bondari 341
}
342
 
343
/** Buddy system coalesce implementation
344
 *
489 jermar 345
 * @param b Buddy system.
480 bondari 346
 * @param block_1 First block
347
 * @param block_2 First block's buddy
348
 *
349
 * @return Coalesced block (actually block that represents lower address)
479 bondari 350
 */
814 palkovsky 351
static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
822 palkovsky 352
                    link_t * block_2)
353
{
814 palkovsky 354
    frame_t *frame1, *frame2;
564 jermar 355
 
480 bondari 356
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
357
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
564 jermar 358
 
533 bondari 359
    return frame1 < frame2 ? block_1 : block_2;
479 bondari 360
}
361
 
362
/** Buddy system set_order implementation
489 jermar 363
 *
364
 * @param b Buddy system.
480 bondari 365
 * @param block Buddy system block
366
 * @param order Order to set
479 bondari 367
 */
814 palkovsky 368
static void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
480 bondari 369
    frame_t * frame;
370
    frame = list_get_instance(block, frame_t, buddy_link);
371
    frame->buddy_order = order;
479 bondari 372
}
373
 
374
/** Buddy system get_order implementation
489 jermar 375
 *
376
 * @param b Buddy system.
480 bondari 377
 * @param block Buddy system block
479 bondari 378
 *
480 bondari 379
 * @return Order of block
479 bondari 380
 */
814 palkovsky 381
static __u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
480 bondari 382
    frame_t * frame;
383
    frame = list_get_instance(block, frame_t, buddy_link);
384
    return frame->buddy_order;
479 bondari 385
}
533 bondari 386
 
387
/** Buddy system mark_busy implementation
388
 *
389
 * @param b Buddy system
390
 * @param block Buddy system block
391
 *
392
 */
814 palkovsky 393
static void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
533 bondari 394
    frame_t * frame;
822 palkovsky 395
 
533 bondari 396
    frame = list_get_instance(block, frame_t, buddy_link);
397
    frame->refcount = 1;
398
}
676 bondari 399
 
814 palkovsky 400
/** Buddy system mark_available implementation
401
 *
402
 * @param b Buddy system
403
 * @param block Buddy system block
404
 *
405
 */
406
static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
407
    frame_t * frame;
408
    frame = list_get_instance(block, frame_t, buddy_link);
409
    frame->refcount = 0;
410
}
411
 
412
static struct buddy_system_operations  zone_buddy_system_operations = {
413
    .find_buddy = zone_buddy_find_buddy,
414
    .bisect = zone_buddy_bisect,
415
    .coalesce = zone_buddy_coalesce,
416
    .set_order = zone_buddy_set_order,
417
    .get_order = zone_buddy_get_order,
418
    .mark_busy = zone_buddy_mark_busy,
419
    .mark_available = zone_buddy_mark_available,
822 palkovsky 420
    .find_block = zone_buddy_find_block,
421
    .print_id = zone_buddy_print_id
814 palkovsky 422
};
423
 
424
/*************************************/
425
/* Zone functions */
426
 
427
/** Allocate frame in particular zone
428
 *
429
 * Assume zone is locked
822 palkovsky 430
 * Panics, if allocation is impossible.
814 palkovsky 431
 *
432
 * @return Frame index in zone
433
 */
822 palkovsky 434
static pfn_t zone_frame_alloc(zone_t *zone,__u8 order)
814 palkovsky 435
{
436
    pfn_t v;
437
    link_t *tmp;
438
    frame_t *frame;
439
 
440
    /* Allocate frames from zone buddy system */
441
    tmp = buddy_system_alloc(zone->buddy_system, order);
442
 
443
    ASSERT(tmp);
444
 
445
    /* Update zone information. */
446
    zone->free_count -= (1 << order);
447
    zone->busy_count += (1 << order);
448
 
449
    /* Frame will be actually a first frame of the block. */
450
    frame = list_get_instance(tmp, frame_t, buddy_link);
451
 
452
    /* get frame address */
453
    v = make_frame_index(zone, frame);
454
    return v;
455
}
456
 
457
/** Free frame from zone
458
 *
459
 * Assume zone is locked
460
 */
820 jermar 461
static void zone_frame_free(zone_t *zone, index_t frame_idx)
814 palkovsky 462
{
463
    frame_t *frame;
464
    __u8 order;
465
 
466
    frame = &zone->frames[frame_idx];
467
 
468
    /* remember frame order */
469
    order = frame->buddy_order;
470
 
471
    ASSERT(frame->refcount);
472
 
473
    if (!--frame->refcount) {
474
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
475
    }
476
 
477
    /* Update zone information. */
478
    zone->free_count += (1 << order);
479
    zone->busy_count -= (1 << order);
480
}
481
 
482
/** Return frame from zone */
820 jermar 483
static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
814 palkovsky 484
{
485
    ASSERT(frame_idx < zone->count);
486
    return &zone->frames[frame_idx];
487
}
488
 
489
/** Mark frame in zone unavailable to allocation */
820 jermar 490
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
814 palkovsky 491
{
492
    frame_t *frame;
493
    link_t *link;
494
 
495
    frame = zone_get_frame(zone, frame_idx);
822 palkovsky 496
    if (frame->refcount)
497
        return;
814 palkovsky 498
    link = buddy_system_alloc_block(zone->buddy_system,
499
                    &frame->buddy_link);
500
    ASSERT(link);
501
    zone->free_count--;
502
}
503
 
822 palkovsky 504
/**
505
 * Join 2 zones
506
 *
507
 * Expect zone_t *z to point to space at least zone_conf_size large
508
 *
509
 * Assume z1 & z2 are locked
510
 */
511
 
512
static void _zone_merge(zone_t *z, zone_t *z1, zone_t *z2)
513
{
514
    __u8 max_order;
515
    int i, z2idx;
516
    pfn_t frame_idx;
517
    frame_t *frame;
518
 
519
    ASSERT(!overlaps(z1->base,z1->count,z2->base,z2->count));
520
    ASSERT(z1->base < z2->base);
521
 
522
    spinlock_initialize(&z->lock, "zone_lock");
523
    z->base = z1->base;
524
    z->count = z2->base+z2->count - z1->base;
525
    z->flags = z1->flags & z2->flags;
526
 
527
    z->free_count = z1->free_count + z2->free_count;
528
    z->busy_count = z1->busy_count + z2->busy_count;
529
 
530
    max_order = fnzb(z->count);
531
 
532
    z->buddy_system = (buddy_system_t *)&z[1];
533
    buddy_system_create(z->buddy_system, max_order,
534
                &zone_buddy_system_operations,
535
                (void *) z);
536
 
537
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
538
    for (i = 0; i < z->count; i++) {
539
        /* This marks all frames busy */
540
        frame_initialize(&z->frames[i]);
541
    }
542
    /* Copy frames from both zones to preserve full frame orders,
543
     * parents etc. Set all frames with refcount=0 to 1, because
544
     * we add all free frames to buddy allocator later again, clear
545
     * order to 0.
546
     */
547
    for (i=0; i<z1->count; i++)
548
        z->frames[i] = z1->frames[i];
549
    for (i=0; i < z2->count; i++) {
550
        z2idx = i + (z2->base - z1->base);
551
        z->frames[z2idx] = z2->frames[i];
552
    }
553
    for (i=0; i < z->count; i++) {
554
        if (!z->frames[i].refcount) {
555
            z->frames[i].refcount = 1;
556
            z->frames[i].buddy_order = 0;
557
        }
558
    }
559
    /* Add free blocks from the 2 original zones */
560
    while (zone_can_alloc(z1, 0)) {
561
        frame_idx = zone_frame_alloc(z1, 0);
562
        frame = &z->frames[frame_idx];
563
        frame->refcount = 0;
564
        buddy_system_free(z->buddy_system, &frame->buddy_link);
565
    }
566
    while (zone_can_alloc(z2, 0)) {
567
        frame_idx = zone_frame_alloc(z2, 0);
568
        frame = &z->frames[frame_idx + (z2->base-z1->base)];
569
        frame->refcount = 0;
570
        buddy_system_free(z->buddy_system, &frame->buddy_link);
571
    }
572
}
573
 
574
/** Return old configuration frames into the zone
575
 *
576
 * We have several cases
577
 * - the conf. data is outside of zone -> exit, shall we call frame_free??
578
 * - the conf. data was created by zone_create -> free every frame
579
 * - the conf. data was created by merge in frame_alloc -> free first frame
580
 *   (the difference is in order)
581
 */
582
static void return_config_frames(zone_t *newzone, zone_t *oldzone)
583
{
584
    pfn_t pfn;
585
    frame_t *frame;
586
    count_t cframes;
587
    int i;
588
 
589
    pfn = ADDR2PFN((__address)KA2PA(oldzone));
590
    cframes = SIZE2FRAMES(zone_conf_size(oldzone->count));
591
 
592
    if (pfn < newzone->base || pfn >= newzone->base + newzone->count)
593
        return;
594
 
595
    frame = &newzone->frames[pfn - newzone->base];
596
    if (frame->buddy_order) {
597
        /* Normally zone config data is hidden, show it again */
598
        newzone->busy_count += (1 << frame->buddy_order);
599
        zone_frame_free(newzone, pfn - newzone->base);
600
        return;
601
    }
602
 
603
    for (i=0; i < cframes; i++) {
604
        newzone->busy_count++;
605
        zone_frame_free(newzone, pfn+i-newzone->base);
606
    }
607
}
608
 
609
/** Merge zones z1 and z2
610
 *
611
 * - the zones must be 2 zones with no zone existing in between,
612
 *   which means that z2 = z1+1
613
 *
614
 * - When you create a new zone, the frame allocator configuration does
615
 *   not to be 2^order size. Once the allocator is running it is no longer
616
 *   possible, merged configuration data occupies more space :-/
617
 */
618
void zone_merge(int z1, int z2)
619
{
620
    ipl_t ipl;
621
    zone_t *zone1, *zone2, *newzone;
622
    int cframes;
623
    __u8 order;
624
    int i;
625
    pfn_t pfn;
626
 
627
    ipl = interrupts_disable();
628
    spinlock_lock(&zones.lock);
629
 
630
    if (z1 < 0 || z1 >= zones.count || z2 < 0 || z2 >= zones.count)
631
        goto errout;
632
    /* We can join only 2 zones with none existing inbetween */
633
    if (z2-z1 != 1)
634
        goto errout;
635
 
636
    zone1 = zones.info[z1];
637
    zone2 = zones.info[z2];
638
    spinlock_lock(&zone1->lock);
639
    spinlock_lock(&zone2->lock);
640
 
641
    cframes = SIZE2FRAMES(zone_conf_size(zone2->base+zone2->count-zone1->base));
642
    order = fnzb(cframes) + 1;
643
 
644
    /* Allocate zonedata inside one of the zones */
645
    if (zone_can_alloc(zone1, order))
646
        pfn = zone1->base + zone_frame_alloc(zone1, order);
647
    else if (zone_can_alloc(zone2, order))
648
        pfn = zone2->base + zone_frame_alloc(zone2, order);
649
    else
650
        goto errout2;
651
 
652
    newzone = (zone_t *)PA2KA(PFN2ADDR(pfn));
653
 
654
    _zone_merge(newzone, zone1, zone2);
655
 
656
    /* Subtract zone information from busy frames */
657
    newzone->busy_count -= (1 << order);
658
 
659
    zones.info[z1] = newzone;
660
    for (i=z2+1;i < zones.count;i++)
661
        zones.info[i-1] = zones.info[i];
662
    zones.count--;
663
 
664
    /* Free old zone information */
665
    return_config_frames(newzone, zone1);
666
    return_config_frames(newzone, zone2);
667
errout2:
668
    /* Nobody is allowed to enter to zone, so we are safe
669
     * to touch the spinlocks last time */
670
    spinlock_unlock(&zone1->lock);
671
    spinlock_unlock(&zone2->lock);
672
errout:
673
    spinlock_unlock(&zones.lock);
674
    interrupts_restore(ipl);
675
}
676
 
677
 
678
/**
679
 * Merge all zones into one big zone
680
 *
681
 * It is reasonable to do this on systems whose bios reports parts in chunks,
682
 * so that we could have 1 zone (it's faster).
683
 */
684
void zone_merge_all(void)
685
{
686
    int count = zones.count;
687
 
688
    while (zones.count > 1 && --count) {
689
        zone_merge(0,1);
690
        break;
691
    }
692
}
693
 
814 palkovsky 694
/** Create frame zone
695
 *
696
 * Create new frame zone.
697
 *
698
 * @param start Physical address of the first frame within the zone.
699
 * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
700
 * @param conffram Address of configuration frame
701
 * @param flags Zone flags.
702
 *
703
 * @return Initialized zone.
704
 */
822 palkovsky 705
static void zone_construct(pfn_t start, count_t count, zone_t *z, int flags)
814 palkovsky 706
{
707
    int i;
708
    __u8 max_order;
709
 
710
    spinlock_initialize(&z->lock, "zone_lock");
711
    z->base = start;
712
    z->count = count;
713
    z->flags = flags;
714
    z->free_count = count;
715
    z->busy_count = 0;
716
 
717
    /*
718
     * Compute order for buddy system, initialize
719
     */
822 palkovsky 720
    max_order = fnzb(count);
814 palkovsky 721
    z->buddy_system = (buddy_system_t *)&z[1];
722
 
723
    buddy_system_create(z->buddy_system, max_order,
724
                &zone_buddy_system_operations,
725
                (void *) z);
726
 
727
    /* Allocate frames _after_ the conframe */
728
    /* Check sizes */
729
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
730
    for (i = 0; i<count; i++) {
731
        frame_initialize(&z->frames[i]);
732
    }
822 palkovsky 733
 
814 palkovsky 734
    /* Stuffing frames */
735
    for (i = 0; i < count; i++) {
736
        z->frames[i].refcount = 0;
737
        buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
738
    }
739
}
740
 
741
 
742
/** Compute configuration data size for zone */
822 palkovsky 743
__address zone_conf_size(count_t count)
814 palkovsky 744
{
745
    int size = sizeof(zone_t) + count*sizeof(frame_t);
746
    int max_order;
747
 
822 palkovsky 748
    max_order = fnzb(count);
814 palkovsky 749
    size += buddy_conf_size(max_order);
750
    return size;
751
}
752
 
822 palkovsky 753
 
814 palkovsky 754
/** Create and add zone to system
755
 *
756
 * @param confframe Where configuration frame is supposed to be.
820 jermar 757
 *                  Always check, that we will not disturb the kernel and possibly init.
814 palkovsky 758
 *                  If confframe is given _outside_ this zone, it is expected,
759
 *                  that the area is already marked BUSY and big enough
760
 *                  to contain zone_conf_size() amount of data
822 palkovsky 761
 *
762
 * @return Zone number or -1 on error
814 palkovsky 763
 */
822 palkovsky 764
int zone_create(pfn_t start, count_t count, pfn_t confframe, int flags)
814 palkovsky 765
{
766
    zone_t *z;
822 palkovsky 767
    __address addr;
820 jermar 768
    count_t confcount;
814 palkovsky 769
    int i;
822 palkovsky 770
    int znum;
814 palkovsky 771
 
772
    /* Theoretically we could have here 0, practically make sure
773
     * nobody tries to do that. If some platform requires, remove
774
     * the assert
775
     */
776
    ASSERT(confframe);
777
    /* If conframe is supposed to be inside our zone, then make sure
778
     * it does not span kernel & init
779
     */
822 palkovsky 780
    confcount = SIZE2FRAMES(zone_conf_size(count));
814 palkovsky 781
    if (confframe >= start && confframe < start+count) {
782
        for (;confframe < start+count;confframe++) {
783
            addr = PFN2ADDR(confframe);
822 palkovsky 784
            if (overlaps(addr, PFN2ADDR(confcount),
785
                     KA2PA(config.base),config.kernel_size))
814 palkovsky 786
                continue;
787
            if (config.init_addr)
822 palkovsky 788
                if (overlaps(addr,PFN2ADDR(confcount),
814 palkovsky 789
                         KA2PA(config.init_addr),
822 palkovsky 790
                         config.init_size))
814 palkovsky 791
                    continue;
792
            break;
793
        }
794
        if (confframe >= start+count)
795
            panic("Cannot find configuration data for zone.");
796
    }
797
 
822 palkovsky 798
    z = (zone_t *)PA2KA(PFN2ADDR(confframe));
799
    zone_construct(start, count, z, flags);
800
    znum = zones_add_zone(z);
801
    if (znum == -1)
802
        return -1;
803
 
814 palkovsky 804
    /* If confdata in zone, mark as unavailable */
805
    if (confframe >= start && confframe < start+count)
806
        for (i=confframe; i<confframe+confcount; i++) {
807
            zone_mark_unavailable(z, i - z->base);
808
        }
822 palkovsky 809
 
810
    return znum;
814 palkovsky 811
}
812
 
813
/***************************************/
814
/* Frame functions */
815
 
816
/** Set parent of frame */
817
void frame_set_parent(pfn_t pfn, void *data, int hint)
818
{
819
    zone_t *zone = find_zone_and_lock(pfn, &hint);
820
 
821
    ASSERT(zone);
822
 
823
    zone_get_frame(zone, pfn-zone->base)->parent = data;
824
    spinlock_unlock(&zone->lock);
825
}
826
 
827
void * frame_get_parent(pfn_t pfn, int hint)
828
{
829
    zone_t *zone = find_zone_and_lock(pfn, &hint);
830
    void *res;
831
 
832
    ASSERT(zone);
833
    res = zone_get_frame(zone, pfn - zone->base)->parent;
834
 
835
    spinlock_unlock(&zone->lock);
836
    return res;
837
}
838
 
839
/** Allocate power-of-two frames of physical memory.
840
 *
841
 * @param flags Flags for host zone selection and address processing.
842
 * @param order Allocate exactly 2^order frames.
843
 * @param pzone Preferred zone
844
 *
845
 * @return Allocated frame.
846
 */
847
pfn_t frame_alloc_generic(__u8 order, int flags, int * status, int *pzone)
848
{
849
    ipl_t ipl;
850
    int freed;
851
    pfn_t v;
852
    zone_t *zone;
853
 
854
loop:
855
    ipl = interrupts_disable();
856
    /*
857
     * First, find suitable frame zone.
858
     */
859
    zone = find_free_zone_lock(order,pzone);
860
    /* If no memory, reclaim some slab memory,
861
       if it does not help, reclaim all */
862
    if (!zone && !(flags & FRAME_NO_RECLAIM)) {
863
        freed = slab_reclaim(0);
864
        if (freed)
865
            zone = find_free_zone_lock(order,pzone);
866
        if (!zone) {
867
            freed = slab_reclaim(SLAB_RECLAIM_ALL);
868
            if (freed)
869
                zone = find_free_zone_lock(order,pzone);
870
        }
871
    }
872
    if (!zone) {
873
        if (flags & FRAME_PANIC)
874
            panic("Can't allocate frame.\n");
875
 
876
        /*
877
         * TODO: Sleep until frames are available again.
878
         */
879
        interrupts_restore(ipl);
880
 
881
        if (flags & FRAME_ATOMIC) {
882
            ASSERT(status != NULL);
883
            if (status)
884
                *status = FRAME_NO_MEMORY;
885
            return NULL;
886
        }
887
 
888
        panic("Sleep not implemented.\n");
889
        goto loop;
890
    }
822 palkovsky 891
    v = zone_frame_alloc(zone,order);
814 palkovsky 892
    v += zone->base;
893
 
894
    spinlock_unlock(&zone->lock);
895
    interrupts_restore(ipl);
896
 
897
    if (status)
898
        *status = FRAME_OK;
899
    return v;
900
}
901
 
902
/** Free a frame.
903
 *
822 palkovsky 904
 * Find respective frame structure for supplied addr.
814 palkovsky 905
 * Decrement frame reference count.
906
 * If it drops to zero, move the frame structure to free list.
907
 *
908
 * @param frame Frame no to be freed.
909
 */
910
void frame_free(pfn_t pfn)
911
{
912
    ipl_t ipl;
913
    zone_t *zone;
914
 
915
    ipl = interrupts_disable();
916
 
917
    /*
918
     * First, find host frame zone for addr.
919
     */
920
    zone = find_zone_and_lock(pfn,NULL);
921
    ASSERT(zone);
922
 
923
    zone_frame_free(zone, pfn-zone->base);
924
 
925
    spinlock_unlock(&zone->lock);
926
    interrupts_restore(ipl);
927
}
928
 
929
 
930
 
931
/** Mark given range unavailable in frame zones */
820 jermar 932
void frame_mark_unavailable(pfn_t start, count_t count)
814 palkovsky 933
{
934
    int i;
935
    zone_t *zone;
936
    int prefzone = 0;
937
 
822 palkovsky 938
    for (i=0; i < count; i++) {
814 palkovsky 939
        zone = find_zone_and_lock(start+i,&prefzone);
940
        if (!zone) /* PFN not found */
941
            continue;
942
        zone_mark_unavailable(zone, start+i-zone->base);
943
 
944
        spinlock_unlock(&zone->lock);
945
    }
946
}
947
 
948
/** Initialize physical memory management
949
 *
950
 * Initialize physical memory managemnt.
951
 */
952
void frame_init(void)
953
{
954
    if (config.cpu_active == 1) {
955
        zones.count = 0;
956
        spinlock_initialize(&zones.lock,"zones_glob_lock");
957
    }
958
    /* Tell the architecture to create some memory */
959
    frame_arch_init();
960
    if (config.cpu_active == 1) {
961
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
820 jermar 962
                       SIZE2FRAMES(config.kernel_size));
814 palkovsky 963
        if (config.init_size > 0)
964
            frame_mark_unavailable(ADDR2PFN(KA2PA(config.init_addr)),
820 jermar 965
                           SIZE2FRAMES(config.init_size));
814 palkovsky 966
    }
967
}
968
 
969
 
970
 
677 bondari 971
/** Prints list of zones
972
 *
973
 */
676 bondari 974
void zone_print_list(void) {
975
    zone_t *zone = NULL;
814 palkovsky 976
    int i;
701 jermar 977
    ipl_t ipl;
978
 
979
    ipl = interrupts_disable();
814 palkovsky 980
    spinlock_lock(&zones.lock);
822 palkovsky 981
    printf("#  Base address\tFree Frames\tBusy Frames\n");
982
    printf("   ------------\t-----------\t-----------\n");
814 palkovsky 983
    for (i=0;i<zones.count;i++) {
984
        zone = zones.info[i];
683 bondari 985
        spinlock_lock(&zone->lock);
822 palkovsky 986
        printf("%d  %L\t%d\t\t%d\n",i,PFN2ADDR(zone->base),
814 palkovsky 987
               zone->free_count, zone->busy_count);
701 jermar 988
        spinlock_unlock(&zone->lock);
676 bondari 989
    }
814 palkovsky 990
    spinlock_unlock(&zones.lock);
701 jermar 991
    interrupts_restore(ipl);
676 bondari 992
}
993
 
677 bondari 994
/** Prints zone details
995
 *
822 palkovsky 996
 * @param base Zone base address OR zone number
677 bondari 997
 */
822 palkovsky 998
void zone_print_one(int num) {
814 palkovsky 999
    zone_t *zone = NULL;
701 jermar 1000
    ipl_t ipl;
822 palkovsky 1001
    int i;
701 jermar 1002
 
1003
    ipl = interrupts_disable();
814 palkovsky 1004
    spinlock_lock(&zones.lock);
822 palkovsky 1005
 
1006
    for (i=0;i < zones.count; i++) {
1007
        if (i == num || zones.info[i]->base == ADDR2PFN(num)) {
1008
            zone = zones.info[i];
1009
            break;
1010
        }
676 bondari 1011
    }
822 palkovsky 1012
    if (!zone) {
1013
        printf("Zone not found.\n");
1014
        goto out;
1015
    }
676 bondari 1016
 
683 bondari 1017
    spinlock_lock(&zone->lock);
822 palkovsky 1018
    printf("Memory zone information\n");
814 palkovsky 1019
    printf("Zone base address: %P\n", PFN2ADDR(zone->base));
1020
    printf("Zone size: %d frames (%dK)\n", zone->count, ((zone->count) * FRAME_SIZE) >> 10);
701 jermar 1021
    printf("Allocated space: %d frames (%dK)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
1022
    printf("Available space: %d (%dK)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
686 bondari 1023
    buddy_system_structure_print(zone->buddy_system, FRAME_SIZE);
683 bondari 1024
 
1025
    spinlock_unlock(&zone->lock);
822 palkovsky 1026
out:
814 palkovsky 1027
    spinlock_unlock(&zones.lock);
701 jermar 1028
    interrupts_restore(ipl);
676 bondari 1029
}
1030