Subversion Repositories HelenOS

Rev

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