Subversion Repositories HelenOS

Rev

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

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