Subversion Repositories HelenOS

Rev

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