Subversion Repositories HelenOS

Rev

Rev 4263 | 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
4153 mejdrech 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
4153 mejdrech 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>
3187 jermar 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
 
4153 mejdrech 62
zones_t zones;
367 jermar 63
 
814 palkovsky 64
/*
3187 jermar 65
 * Synchronization primitives used to sleep when there is no memory
66
 * available.
67
 */
3188 jermar 68
mutex_t mem_avail_mtx;
69
condvar_t mem_avail_cv;
4581 mejdrech 70
size_t mem_avail_req = 0;  /**< Number of frames requested. */
71
size_t mem_avail_gen = 0;  /**< Generation counter. */
2121 decky 72
 
2725 decky 73
/********************/
814 palkovsky 74
/* Helper functions */
2725 decky 75
/********************/
76
 
4581 mejdrech 77
static inline size_t frame_index(zone_t *zone, frame_t *frame)
762 palkovsky 78
{
4581 mejdrech 79
    return (size_t) (frame - zone->frames);
762 palkovsky 80
}
2725 decky 81
 
4581 mejdrech 82
static inline size_t frame_index_abs(zone_t *zone, frame_t *frame)
1 jermar 83
{
4581 mejdrech 84
    return (size_t) (frame - zone->frames) + zone->base;
1 jermar 85
}
2725 decky 86
 
4581 mejdrech 87
static inline bool frame_index_valid(zone_t *zone, size_t index)
814 palkovsky 88
{
2745 decky 89
    return (index < zone->count);
814 palkovsky 90
}
1 jermar 91
 
4581 mejdrech 92
static inline size_t make_frame_index(zone_t *zone, frame_t *frame)
762 palkovsky 93
{
2725 decky 94
    return (frame - zone->frames);
762 palkovsky 95
}
96
 
3185 jermar 97
/** Initialize frame structure.
762 palkovsky 98
 *
4153 mejdrech 99
 * @param frame Frame structure to be initialized.
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
 
4153 mejdrech 108
/*******************/
109
/* Zones functions */
110
/*******************/
762 palkovsky 111
 
3185 jermar 112
/** Insert-sort zone into zones list.
822 palkovsky 113
 *
4153 mejdrech 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
 */
4581 mejdrech 123
static size_t zones_insert_zone(pfn_t base, size_t count)
1 jermar 124
{
2725 decky 125
    if (zones.count + 1 == ZONES_MAX) {
126
        printf("Maximum zone count %u exceeded!\n", ZONES_MAX);
4581 mejdrech 127
        return (size_t) -1;
2725 decky 128
    }
129
 
4581 mejdrech 130
    size_t i;
1037 decky 131
    for (i = 0; i < zones.count; i++) {
4153 mejdrech 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");
4581 mejdrech 136
            return (size_t) -1;
814 palkovsky 137
        }
4153 mejdrech 138
        if (base < zones.info[i].base)
822 palkovsky 139
            break;
368 jermar 140
    }
2725 decky 141
 
822 palkovsky 142
    /* Move other zones up */
4581 mejdrech 143
    size_t j;
4153 mejdrech 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
 
4153 mejdrech 155
/** Get total available frames.
2725 decky 156
 *
4153 mejdrech 157
 * Assume interrupts are disabled and zones lock is
158
 * locked.
2725 decky 159
 *
4153 mejdrech 160
 * @return Total number of available frames.
161
 *
368 jermar 162
 */
4153 mejdrech 163
#ifdef CONFIG_DEBUG
4581 mejdrech 164
static size_t total_frames_free(void)
1 jermar 165
{
4581 mejdrech 166
    size_t total = 0;
167
    size_t i;
4153 mejdrech 168
    for (i = 0; i < zones.count; i++)
169
        total += zones.info[i].free_count;
533 bondari 170
 
4153 mejdrech 171
    return total;
172
}
173
#endif
814 palkovsky 174
 
4153 mejdrech 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
 */
4581 mejdrech 187
size_t find_zone(pfn_t frame, size_t count, size_t hint)
4153 mejdrech 188
{
2745 decky 189
    if (hint >= zones.count)
814 palkovsky 190
        hint = 0;
533 bondari 191
 
4581 mejdrech 192
    size_t i = hint;
814 palkovsky 193
    do {
4153 mejdrech 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;
3207 jermar 201
    } while (i != hint);
4153 mejdrech 202
 
4581 mejdrech 203
    return (size_t) -1;
533 bondari 204
}
205
 
822 palkovsky 206
/** @return True if zone can allocate specified order */
4153 mejdrech 207
static bool zone_can_alloc(zone_t *zone, uint8_t order)
822 palkovsky 208
{
4153 mejdrech 209
    return (zone_flags_available(zone->flags)
210
        && buddy_system_can_alloc(zone->buddy_system, order));
822 palkovsky 211
}
212
 
4153 mejdrech 213
/** Find a zone that can allocate order frames.
367 jermar 214
 *
4153 mejdrech 215
 * Assume interrupts are disabled and zones lock is
216
 * locked.
367 jermar 217
 *
4153 mejdrech 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
 */
4581 mejdrech 223
static size_t find_free_zone(uint8_t order, zone_flags_t flags, size_t hint)
367 jermar 224
{
814 palkovsky 225
    if (hint >= zones.count)
226
        hint = 0;
4153 mejdrech 227
 
4581 mejdrech 228
    size_t i = hint;
814 palkovsky 229
    do {
3207 jermar 230
        /*
231
         * Check whether the zone meets the search criteria.
232
         */
4153 mejdrech 233
        if ((zones.info[i].flags & flags) == flags) {
3207 jermar 234
            /*
235
             * Check if the zone has 2^order frames area available.
236
             */
4153 mejdrech 237
            if (zone_can_alloc(&zones.info[i], order))
238
                return i;
367 jermar 239
        }
4153 mejdrech 240
 
241
        i++;
242
        if (i >= zones.count)
814 palkovsky 243
            i = 0;
3207 jermar 244
    } while (i != hint);
4153 mejdrech 245
 
4581 mejdrech 246
    return (size_t) -1;
367 jermar 247
}
248
 
2059 jermar 249
/**************************/
814 palkovsky 250
/* Buddy system functions */
2059 jermar 251
/**************************/
814 palkovsky 252
 
3185 jermar 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
 *
4153 mejdrech 258
 * @param order Order of parent must be different then this
259
 *              parameter!!
260
 *
367 jermar 261
 */
4153 mejdrech 262
static link_t *zone_buddy_find_block(buddy_system_t *buddy, link_t *child,
2133 jermar 263
    uint8_t order)
367 jermar 264
{
4153 mejdrech 265
    frame_t *frame = list_get_instance(child, frame_t, buddy_link);
266
    zone_t *zone = (zone_t *) buddy->data;
367 jermar 267
 
4581 mejdrech 268
    size_t index = frame_index(zone, frame);
814 palkovsky 269
    do {
4153 mejdrech 270
        if (zone->frames[index].buddy_order != order)
814 palkovsky 271
            return &zone->frames[index].buddy_link;
4153 mejdrech 272
    } while (index-- > 0);
273
 
814 palkovsky 274
    return NULL;
367 jermar 275
}
479 bondari 276
 
3185 jermar 277
/** Buddy system find_buddy implementation.
489 jermar 278
 *
4153 mejdrech 279
 * @param buddy Buddy system.
280
 * @param block Block for which buddy should be found.
479 bondari 281
 *
4153 mejdrech 282
 * @return Buddy for given block if found.
283
 *
479 bondari 284
 */
4153 mejdrech 285
static link_t *zone_buddy_find_buddy(buddy_system_t *buddy, link_t *block)
814 palkovsky 286
{
4153 mejdrech 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
 
4153 mejdrech 292
    bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
293
 
4581 mejdrech 294
    size_t index;
533 bondari 295
    if (is_left) {
3185 jermar 296
        index = (frame_index(zone, frame)) +
297
            (1 << frame->buddy_order);
4153 mejdrech 298
    } else {    /* is_right */
3185 jermar 299
        index = (frame_index(zone, frame)) -
300
            (1 << frame->buddy_order);
533 bondari 301
    }
302
 
814 palkovsky 303
    if (frame_index_valid(zone, index)) {
4153 mejdrech 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
    }
4153 mejdrech 309
 
310
    return NULL;
479 bondari 311
}
312
 
3185 jermar 313
/** Buddy system bisect implementation.
479 bondari 314
 *
4153 mejdrech 315
 * @param buddy Buddy system.
316
 * @param block Block to bisect.
480 bondari 317
 *
4153 mejdrech 318
 * @return Right block.
319
 *
479 bondari 320
 */
4153 mejdrech 321
static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)
3185 jermar 322
{
4153 mejdrech 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
 
3185 jermar 329
/** Buddy system coalesce implementation.
479 bondari 330
 *
4153 mejdrech 331
 * @param buddy   Buddy system.
332
 * @param block_1 First block.
333
 * @param block_2 First block's buddy.
480 bondari 334
 *
4153 mejdrech 335
 * @return Coalesced block (actually block that represents lower
336
 *         address).
337
 *
479 bondari 338
 */
4153 mejdrech 339
static link_t *zone_buddy_coalesce(buddy_system_t *buddy, link_t *block_1,
340
    link_t *block_2)
822 palkovsky 341
{
4153 mejdrech 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
 
4153 mejdrech 345
    return ((frame1 < frame2) ? block_1 : block_2);
479 bondari 346
}
347
 
3185 jermar 348
/** Buddy system set_order implementation.
489 jermar 349
 *
4153 mejdrech 350
 * @param buddy Buddy system.
351
 * @param block Buddy system block.
352
 * @param order Order to set.
353
 *
479 bondari 354
 */
4153 mejdrech 355
static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,
3185 jermar 356
    uint8_t order)
357
{
4153 mejdrech 358
    list_get_instance(block, frame_t, buddy_link)->buddy_order = order;
479 bondari 359
}
360
 
3185 jermar 361
/** Buddy system get_order implementation.
489 jermar 362
 *
4153 mejdrech 363
 * @param buddy Buddy system.
364
 * @param block Buddy system block.
479 bondari 365
 *
4153 mejdrech 366
 * @return Order of block.
367
 *
479 bondari 368
 */
4153 mejdrech 369
static uint8_t zone_buddy_get_order(buddy_system_t *buddy, link_t *block)
3185 jermar 370
{
4153 mejdrech 371
    return list_get_instance(block, frame_t, buddy_link)->buddy_order;
479 bondari 372
}
533 bondari 373
 
3185 jermar 374
/** Buddy system mark_busy implementation.
533 bondari 375
 *
4153 mejdrech 376
 * @param buddy Buddy system.
377
 * @param block Buddy system block.
378
 *
533 bondari 379
 */
4153 mejdrech 380
static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t * block)
3185 jermar 381
{
4153 mejdrech 382
    list_get_instance(block, frame_t, buddy_link)->refcount = 1;
533 bondari 383
}
676 bondari 384
 
3185 jermar 385
/** Buddy system mark_available implementation.
814 palkovsky 386
 *
4153 mejdrech 387
 * @param buddy Buddy system.
388
 * @param block Buddy system block.
814 palkovsky 389
 */
4153 mejdrech 390
static void zone_buddy_mark_available(buddy_system_t *buddy, link_t *block)
3185 jermar 391
{
4153 mejdrech 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,
3206 jermar 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
 
3185 jermar 410
/** Allocate frame in particular zone.
814 palkovsky 411
 *
4153 mejdrech 412
 * Assume zone is locked and is available for allocation.
1269 decky 413
 * Panics if allocation is impossible.
814 palkovsky 414
 *
4153 mejdrech 415
 * @param zone  Zone to allocate from.
416
 * @param order Allocate exactly 2^order frames.
1269 decky 417
 *
4153 mejdrech 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
{
4153 mejdrech 423
    ASSERT(zone_flags_available(zone->flags));
424
 
814 palkovsky 425
    /* Allocate frames from zone buddy system */
4153 mejdrech 426
    link_t *link = buddy_system_alloc(zone->buddy_system, order);
814 palkovsky 427
 
4153 mejdrech 428
    ASSERT(link);
814 palkovsky 429
 
430
    /* Update zone information. */
431
    zone->free_count -= (1 << order);
432
    zone->busy_count += (1 << order);
4153 mejdrech 433
 
814 palkovsky 434
    /* Frame will be actually a first frame of the block. */
4153 mejdrech 435
    frame_t *frame = list_get_instance(link, frame_t, buddy_link);
814 palkovsky 436
 
4153 mejdrech 437
    /* Get frame address */
438
    return make_frame_index(zone, frame);
814 palkovsky 439
}
440
 
3185 jermar 441
/** Free frame from zone.
814 palkovsky 442
 *
4153 mejdrech 443
 * Assume zone is locked and is available for deallocation.
1568 palkovsky 444
 *
4153 mejdrech 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
 */
4581 mejdrech 449
static void zone_frame_free(zone_t *zone, size_t frame_idx)
814 palkovsky 450
{
4153 mejdrech 451
    ASSERT(zone_flags_available(zone->flags));
814 palkovsky 452
 
4153 mejdrech 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);
4153 mejdrech 459
 
814 palkovsky 460
    if (!--frame->refcount) {
461
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
4153 mejdrech 462
 
946 jermar 463
        /* Update zone information. */
464
        zone->free_count += (1 << order);
465
        zone->busy_count -= (1 << order);
814 palkovsky 466
    }
467
}
468
 
3185 jermar 469
/** Return frame from zone. */
4581 mejdrech 470
static frame_t *zone_get_frame(zone_t *zone, size_t frame_idx)
814 palkovsky 471
{
472
    ASSERT(frame_idx < zone->count);
473
    return &zone->frames[frame_idx];
474
}
475
 
3185 jermar 476
/** Mark frame in zone unavailable to allocation. */
4581 mejdrech 477
static void zone_mark_unavailable(zone_t *zone, size_t frame_idx)
814 palkovsky 478
{
4153 mejdrech 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;
4153 mejdrech 484
 
485
    link_t *link __attribute__ ((unused));
486
 
2133 jermar 487
    link = buddy_system_alloc_block(zone->buddy_system,
488
        &frame->buddy_link);
4153 mejdrech 489
 
814 palkovsky 490
    ASSERT(link);
491
    zone->free_count--;
492
}
493
 
4153 mejdrech 494
/** Merge two zones.
822 palkovsky 495
 *
4153 mejdrech 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
 *
4153 mejdrech 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
 */
4581 mejdrech 506
static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1, buddy_system_t *buddy)
822 palkovsky 507
{
4153 mejdrech 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
 
4153 mejdrech 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 */
4581 mejdrech 532
    size_t i;
4153 mejdrech 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,
4153 mejdrech 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
     */
4153 mejdrech 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;
4153 mejdrech 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
    }
4153 mejdrech 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;
4153 mejdrech 574
        buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
822 palkovsky 575
    }
4153 mejdrech 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;
4153 mejdrech 585
        buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
822 palkovsky 586
    }
587
}
588
 
3185 jermar 589
/** Return old configuration frames into the zone.
822 palkovsky 590
 *
4153 mejdrech 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
 *
4153 mejdrech 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
 */
4581 mejdrech 602
static void return_config_frames(size_t znum, pfn_t pfn, size_t count)
822 palkovsky 603
{
4153 mejdrech 604
    ASSERT(zone_flags_available(zones.info[znum].flags));
822 palkovsky 605
 
4581 mejdrech 606
    size_t cframes = SIZE2FRAMES(zone_conf_size(count));
4153 mejdrech 607
 
608
    if ((pfn < zones.info[znum].base)
609
        || (pfn >= zones.info[znum].base + zones.info[znum].count))
822 palkovsky 610
        return;
4153 mejdrech 611
 
612
    frame_t *frame __attribute__ ((unused));
822 palkovsky 613
 
4153 mejdrech 614
    frame = &zones.info[znum].frames[pfn - zones.info[znum].base];
824 palkovsky 615
    ASSERT(!frame->buddy_order);
4153 mejdrech 616
 
4581 mejdrech 617
    size_t i;
2122 decky 618
    for (i = 0; i < cframes; i++) {
4153 mejdrech 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
 
3185 jermar 625
/** Reduce allocated block to count of order 0 frames.
824 palkovsky 626
 *
4153 mejdrech 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
 *
4153 mejdrech 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
 */
4581 mejdrech 637
static void zone_reduce_region(size_t znum, pfn_t frame_idx, size_t count)
824 palkovsky 638
{
4153 mejdrech 639
    ASSERT(zone_flags_available(zones.info[znum].flags));
640
    ASSERT(frame_idx + count < zones.info[znum].count);
824 palkovsky 641
 
4153 mejdrech 642
    uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;
4581 mejdrech 643
    ASSERT((size_t) (1 << order) >= count);
4153 mejdrech 644
 
824 palkovsky 645
    /* Reduce all blocks to order 0 */
4581 mejdrech 646
    size_t i;
647
    for (i = 0; i < (size_t) (1 << order); i++) {
4153 mejdrech 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
    }
4153 mejdrech 654
 
824 palkovsky 655
    /* Free unneeded frames */
4581 mejdrech 656
    for (i = count; i < (size_t) (1 << order); i++)
4153 mejdrech 657
        zone_frame_free(&zones.info[znum], i + frame_idx);
824 palkovsky 658
}
659
 
3185 jermar 660
/** Merge zones z1 and z2.
822 palkovsky 661
 *
4153 mejdrech 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
 *
4153 mejdrech 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
 */
4581 mejdrech 673
bool zone_merge(size_t z1, size_t z2)
822 palkovsky 674
{
4153 mejdrech 675
    ipl_t ipl = interrupts_disable();
822 palkovsky 676
    spinlock_lock(&zones.lock);
4153 mejdrech 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;
4153 mejdrech 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;
4153 mejdrech 700
    else
1700 palkovsky 701
        order = fnzb(cframes - 1) + 1;
4153 mejdrech 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 */
4153 mejdrech 723
    zone_reduce_region(z1, pfn - zones.info[z1].base, cframes);
724
 
822 palkovsky 725
    /* Subtract zone information from busy frames */
4153 mejdrech 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 */
4581 mejdrech 736
    size_t i;
4153 mejdrech 737
    for (i = z2 + 1; i < zones.count; i++) {
1037 decky 738
        zones.info[i - 1] = zones.info[i];
4153 mejdrech 739
        zones.info[i - 1].buddy_system->data =
740
            (void *) &zones.info[i - 1];
741
    }
742
 
822 palkovsky 743
    zones.count--;
4153 mejdrech 744
 
822 palkovsky 745
errout:
746
    spinlock_unlock(&zones.lock);
747
    interrupts_restore(ipl);
4153 mejdrech 748
 
749
    return ret;
822 palkovsky 750
}
751
 
4153 mejdrech 752
/** Merge all mergeable zones into one big zone.
822 palkovsky 753
 *
4153 mejdrech 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
{
4581 mejdrech 761
    size_t i = 0;
4153 mejdrech 762
    while (i < zones.count) {
763
        if (!zone_merge(i, i + 1))
764
            i++;
822 palkovsky 765
    }
766
}
767
 
3185 jermar 768
/** Create new frame zone.
814 palkovsky 769
 *
4153 mejdrech 770
 * @param zone  Zone to construct.
771
 * @param buddy Address of buddy system configuration information.
772
 * @param start Physical address of the first frame within the zone.
773
 * @param count Count of frames in zone.
774
 * @param flags Zone flags.
814 palkovsky 775
 *
4153 mejdrech 776
 * @return Initialized zone.
777
 *
814 palkovsky 778
 */
4581 mejdrech 779
static void zone_construct(zone_t *zone, buddy_system_t *buddy, pfn_t start, size_t count, zone_flags_t flags)
814 palkovsky 780
{
4153 mejdrech 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
 
4153 mejdrech 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
 
4581 mejdrech 802
        size_t i;
4153 mejdrech 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
 
3185 jermar 815
/** Compute configuration data size for zone.
1568 palkovsky 816
 *
4153 mejdrech 817
 * @param count Size of zone in frames.
818
 *
819
 * @return Size of zone configuration info (in bytes).
820
 *
1568 palkovsky 821
 */
4581 mejdrech 822
uintptr_t zone_conf_size(size_t count)
814 palkovsky 823
{
4153 mejdrech 824
    return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count)));
814 palkovsky 825
}
826
 
3185 jermar 827
/** Create and add zone to system.
814 palkovsky 828
 *
4153 mejdrech 829
 * @param start     First frame number (absolute).
830
 * @param count     Size of zone in frames.
831
 * @param confframe Where configuration frames are supposed to be.
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
 *
4153 mejdrech 840
 * @return Zone number or -1 on error.
841
 *
814 palkovsky 842
 */
4581 mejdrech 843
size_t zone_create(pfn_t start, size_t count, pfn_t confframe, zone_flags_t flags)
814 palkovsky 844
{
4153 mejdrech 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
         */
4581 mejdrech 858
        size_t confcount = SIZE2FRAMES(zone_conf_size(count));
4153 mejdrech 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),
4153 mejdrech 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;
4581 mejdrech 871
                size_t i;
4153 mejdrech 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
 
4153 mejdrech 885
            if (confframe >= start + count)
886
                panic("Cannot find configuration data for zone.");
814 palkovsky 887
        }
4153 mejdrech 888
 
4581 mejdrech 889
        size_t znum = zones_insert_zone(start, count);
890
        if (znum == (size_t) -1) {
4153 mejdrech 891
            spinlock_unlock(&zones.lock);
892
            interrupts_restore(ipl);
4581 mejdrech 893
            return (size_t) -1;
4153 mejdrech 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)) {
4581 mejdrech 901
            size_t i;
4153 mejdrech 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
    }
3188 jermar 912
 
4153 mejdrech 913
    /* Non-available zone */
4581 mejdrech 914
    size_t znum = zones_insert_zone(start, count);
915
    if (znum == (size_t) -1) {
4153 mejdrech 916
        spinlock_unlock(&zones.lock);
917
        interrupts_restore(ipl);
4581 mejdrech 918
        return (size_t) -1;
4153 mejdrech 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
 
4153 mejdrech 928
/*******************/
814 palkovsky 929
/* Frame functions */
4153 mejdrech 930
/*******************/
814 palkovsky 931
 
3185 jermar 932
/** Set parent of frame. */
4581 mejdrech 933
void frame_set_parent(pfn_t pfn, void *data, size_t hint)
814 palkovsky 934
{
4153 mejdrech 935
    ipl_t ipl = interrupts_disable();
936
    spinlock_lock(&zones.lock);
937
 
4581 mejdrech 938
    size_t znum = find_zone(pfn, 1, hint);
4153 mejdrech 939
 
4581 mejdrech 940
    ASSERT(znum != (size_t) -1);
4153 mejdrech 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
 
4581 mejdrech 949
void *frame_get_parent(pfn_t pfn, size_t hint)
814 palkovsky 950
{
4153 mejdrech 951
    ipl_t ipl = interrupts_disable();
952
    spinlock_lock(&zones.lock);
814 palkovsky 953
 
4581 mejdrech 954
    size_t znum = find_zone(pfn, 1, hint);
4153 mejdrech 955
 
4581 mejdrech 956
    ASSERT(znum != (size_t) -1);
4153 mejdrech 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
 *
4153 mejdrech 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
 *
4153 mejdrech 973
 * @return Physical address of the allocated frame.
1269 decky 974
 *
814 palkovsky 975
 */
4581 mejdrech 976
void *frame_alloc_generic(uint8_t order, frame_flags_t flags, size_t *pzone)
814 palkovsky 977
{
4581 mejdrech 978
    size_t size = ((size_t) 1) << order;
814 palkovsky 979
    ipl_t ipl;
4581 mejdrech 980
    size_t hint = pzone ? (*pzone) : 0;
814 palkovsky 981
 
982
loop:
983
    ipl = interrupts_disable();
4153 mejdrech 984
    spinlock_lock(&zones.lock);
1269 decky 985
 
814 palkovsky 986
    /*
987
     * First, find suitable frame zone.
988
     */
4581 mejdrech 989
    size_t znum = find_free_zone(order,
4153 mejdrech 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 */
4581 mejdrech 994
    if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
4263 mejdrech 995
        spinlock_unlock(&zones.lock);
996
        interrupts_restore(ipl);
997
 
4581 mejdrech 998
        size_t freed = slab_reclaim(0);
4153 mejdrech 999
 
4263 mejdrech 1000
        ipl = interrupts_disable();
1001
        spinlock_lock(&zones.lock);
1002
 
4153 mejdrech 1003
        if (freed > 0)
1004
            znum = find_free_zone(order,
1005
                FRAME_TO_ZONE_FLAGS(flags), hint);
1006
 
4581 mejdrech 1007
        if (znum == (size_t) -1) {
4263 mejdrech 1008
            spinlock_unlock(&zones.lock);
1009
            interrupts_restore(ipl);
1010
 
814 palkovsky 1011
            freed = slab_reclaim(SLAB_RECLAIM_ALL);
4263 mejdrech 1012
 
1013
            ipl = interrupts_disable();
1014
            spinlock_lock(&zones.lock);
1015
 
4153 mejdrech 1016
            if (freed > 0)
1017
                znum = find_free_zone(order,
1018
                    FRAME_TO_ZONE_FLAGS(flags), hint);
814 palkovsky 1019
        }
1020
    }
4153 mejdrech 1021
 
4581 mejdrech 1022
    if (znum == (size_t) -1) {
3187 jermar 1023
        if (flags & FRAME_ATOMIC) {
4153 mejdrech 1024
            spinlock_unlock(&zones.lock);
3187 jermar 1025
            interrupts_restore(ipl);
4153 mejdrech 1026
            return NULL;
3187 jermar 1027
        }
814 palkovsky 1028
 
3187 jermar 1029
#ifdef CONFIG_DEBUG
4581 mejdrech 1030
        size_t avail = total_frames_free();
3187 jermar 1031
#endif
4153 mejdrech 1032
 
1033
        spinlock_unlock(&zones.lock);
1034
        interrupts_restore(ipl);
1035
 
1036
        /*
1037
         * Sleep until some frames are available again.
1038
         */
1039
 
1040
#ifdef CONFIG_DEBUG
4581 mejdrech 1041
        printf("Thread %" PRIu64 " waiting for %" PRIs " frames, "
1042
            "%" PRIs " available.\n", THREAD->tid, size, avail);
4153 mejdrech 1043
#endif
1044
 
3188 jermar 1045
        mutex_lock(&mem_avail_mtx);
4153 mejdrech 1046
 
1047
        if (mem_avail_req > 0)
1048
            mem_avail_req = min(mem_avail_req, size);
1049
        else
1050
            mem_avail_req = size;
4581 mejdrech 1051
        size_t gen = mem_avail_gen;
4153 mejdrech 1052
 
1053
        while (gen == mem_avail_gen)
3188 jermar 1054
            condvar_wait(&mem_avail_cv, &mem_avail_mtx);
4153 mejdrech 1055
 
3188 jermar 1056
        mutex_unlock(&mem_avail_mtx);
4153 mejdrech 1057
 
3187 jermar 1058
#ifdef CONFIG_DEBUG
4153 mejdrech 1059
        printf("Thread %" PRIu64 " woken up.\n", THREAD->tid);
3187 jermar 1060
#endif
4153 mejdrech 1061
 
814 palkovsky 1062
        goto loop;
1063
    }
1269 decky 1064
 
4153 mejdrech 1065
    pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)
1066
        + zones.info[znum].base;
3188 jermar 1067
 
4153 mejdrech 1068
    spinlock_unlock(&zones.lock);
814 palkovsky 1069
    interrupts_restore(ipl);
4153 mejdrech 1070
 
1071
    if (pzone)
1072
        *pzone = znum;
1073
 
1760 palkovsky 1074
    if (flags & FRAME_KA)
4153 mejdrech 1075
        return (void *) PA2KA(PFN2ADDR(pfn));
1076
 
1077
    return (void *) PFN2ADDR(pfn);
814 palkovsky 1078
}
1079
 
1080
/** Free a frame.
1081
 *
1854 jermar 1082
 * Find respective frame structure for supplied physical frame address.
4153 mejdrech 1083
 * Decrement frame reference count. If it drops to zero, move the frame
1084
 * structure to free list.
814 palkovsky 1085
 *
4153 mejdrech 1086
 * @param frame Physical Address of of the frame to be freed.
1087
 *
814 palkovsky 1088
 */
1780 jermar 1089
void frame_free(uintptr_t frame)
814 palkovsky 1090
{
4153 mejdrech 1091
    ipl_t ipl = interrupts_disable();
1092
    spinlock_lock(&zones.lock);
1093
 
814 palkovsky 1094
    /*
1095
     * First, find host frame zone for addr.
1096
     */
4153 mejdrech 1097
    pfn_t pfn = ADDR2PFN(frame);
4581 mejdrech 1098
    size_t znum = find_zone(pfn, 1, NULL);
814 palkovsky 1099
 
4581 mejdrech 1100
    ASSERT(znum != (size_t) -1);
814 palkovsky 1101
 
4153 mejdrech 1102
    zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base);
3187 jermar 1103
 
4153 mejdrech 1104
    spinlock_unlock(&zones.lock);
1105
    interrupts_restore(ipl);
1106
 
3187 jermar 1107
    /*
1108
     * Signal that some memory has been freed.
1109
     */
3188 jermar 1110
    mutex_lock(&mem_avail_mtx);
4153 mejdrech 1111
    if (mem_avail_req > 0)
1112
        mem_avail_req--;
1113
 
1114
    if (mem_avail_req == 0) {
1115
        mem_avail_gen++;
1116
        condvar_broadcast(&mem_avail_cv);
1117
    }
3188 jermar 1118
    mutex_unlock(&mem_avail_mtx);
814 palkovsky 1119
}
1120
 
1236 jermar 1121
/** Add reference to frame.
1122
 *
1123
 * Find respective frame structure for supplied PFN and
1124
 * increment frame reference count.
1125
 *
4153 mejdrech 1126
 * @param pfn Frame number of the frame to be freed.
1127
 *
1236 jermar 1128
 */
1129
void frame_reference_add(pfn_t pfn)
1130
{
4153 mejdrech 1131
    ipl_t ipl = interrupts_disable();
1132
    spinlock_lock(&zones.lock);
1236 jermar 1133
 
1134
    /*
1135
     * First, find host frame zone for addr.
1136
     */
4581 mejdrech 1137
    size_t znum = find_zone(pfn, 1, NULL);
1236 jermar 1138
 
4581 mejdrech 1139
    ASSERT(znum != (size_t) -1);
1236 jermar 1140
 
4153 mejdrech 1141
    zones.info[znum].frames[pfn - zones.info[znum].base].refcount++;
1142
 
1143
    spinlock_unlock(&zones.lock);
1236 jermar 1144
    interrupts_restore(ipl);
1145
}
814 palkovsky 1146
 
3185 jermar 1147
/** Mark given range unavailable in frame zones. */
4581 mejdrech 1148
void frame_mark_unavailable(pfn_t start, size_t count)
814 palkovsky 1149
{
4153 mejdrech 1150
    ipl_t ipl = interrupts_disable();
1151
    spinlock_lock(&zones.lock);
852 palkovsky 1152
 
4581 mejdrech 1153
    size_t i;
2122 decky 1154
    for (i = 0; i < count; i++) {
4581 mejdrech 1155
        size_t znum = find_zone(start + i, 1, 0);
1156
        if (znum == (size_t) -1)  /* PFN not found */
814 palkovsky 1157
            continue;
4153 mejdrech 1158
 
1159
        zone_mark_unavailable(&zones.info[znum],
1160
            start + i - zones.info[znum].base);
814 palkovsky 1161
    }
4153 mejdrech 1162
 
1163
    spinlock_unlock(&zones.lock);
1164
    interrupts_restore(ipl);
814 palkovsky 1165
}
1166
 
3185 jermar 1167
/** Initialize physical memory management. */
814 palkovsky 1168
void frame_init(void)
1169
{
1170
    if (config.cpu_active == 1) {
1171
        zones.count = 0;
1981 jermar 1172
        spinlock_initialize(&zones.lock, "zones.lock");
3188 jermar 1173
        mutex_initialize(&mem_avail_mtx, MUTEX_ACTIVE);
1174
        condvar_initialize(&mem_avail_cv);
814 palkovsky 1175
    }
4153 mejdrech 1176
 
814 palkovsky 1177
    /* Tell the architecture to create some memory */
1178
    frame_arch_init();
1179
    if (config.cpu_active == 1) {
2133 jermar 1180
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
1181
            SIZE2FRAMES(config.kernel_size));
1182
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)),
1183
            SIZE2FRAMES(config.stack_size));
1037 decky 1184
 
4581 mejdrech 1185
        size_t i;
2133 jermar 1186
        for (i = 0; i < init.cnt; i++) {
1187
            pfn_t pfn = ADDR2PFN(KA2PA(init.tasks[i].addr));
1188
            frame_mark_unavailable(pfn,
1189
                SIZE2FRAMES(init.tasks[i].size));
1190
        }
4153 mejdrech 1191
 
1894 jermar 1192
        if (ballocs.size)
2133 jermar 1193
            frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)),
1194
                SIZE2FRAMES(ballocs.size));
4153 mejdrech 1195
 
1599 palkovsky 1196
        /* Black list first frame, as allocating NULL would
4153 mejdrech 1197
         * fail in some places
1198
         */
1599 palkovsky 1199
        frame_mark_unavailable(0, 1);
814 palkovsky 1200
    }
1201
}
1202
 
3185 jermar 1203
/** Return total size of all zones. */
1204
uint64_t zone_total_size(void)
1205
{
4153 mejdrech 1206
    ipl_t ipl = interrupts_disable();
2725 decky 1207
    spinlock_lock(&zones.lock);
1208
 
4153 mejdrech 1209
    uint64_t total = 0;
4581 mejdrech 1210
    size_t i;
4153 mejdrech 1211
    for (i = 0; i < zones.count; i++)
1212
        total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
2725 decky 1213
 
1214
    spinlock_unlock(&zones.lock);
1215
    interrupts_restore(ipl);
1216
 
1217
    return total;
1218
}
1219
 
3185 jermar 1220
/** Prints list of zones. */
1221
void zone_print_list(void)
1222
{
4153 mejdrech 1223
#ifdef __32_BITS__
1224
    printf("#  base address frames       flags    free frames  busy frames\n");
1225
    printf("-- ------------ ------------ -------- ------------ ------------\n");
3057 decky 1226
#endif
1227
 
1228
#ifdef __64_BITS__
4153 mejdrech 1229
    printf("#  base address          frames      flags    free frames  busy frames\n");
1230
    printf("-- -------------------- ------------ -------- ------------ ------------\n");
3057 decky 1231
#endif
2712 decky 1232
 
3205 jermar 1233
    /*
1234
     * Because printing may require allocation of memory, we may not hold
1235
     * the frame allocator locks when printing zone statistics.  Therefore,
1236
     * we simply gather the statistics under the protection of the locks and
1237
     * print the statistics when the locks have been released.
1238
     *
1239
     * When someone adds/removes zones while we are printing the statistics,
1240
     * we may end up with inaccurate output (e.g. a zone being skipped from
1241
     * the listing).
1242
     */
4153 mejdrech 1243
 
4581 mejdrech 1244
    size_t i;
4153 mejdrech 1245
    for (i = 0;; i++) {
1246
        ipl_t ipl = interrupts_disable();
3205 jermar 1247
        spinlock_lock(&zones.lock);
1248
 
1249
        if (i >= zones.count) {
1250
            spinlock_unlock(&zones.lock);
1251
            interrupts_restore(ipl);
1252
            break;
1253
        }
1254
 
4153 mejdrech 1255
        uintptr_t base = PFN2ADDR(zones.info[i].base);
4581 mejdrech 1256
        size_t count = zones.info[i].count;
4153 mejdrech 1257
        zone_flags_t flags = zones.info[i].flags;
4581 mejdrech 1258
        size_t free_count = zones.info[i].free_count;
1259
        size_t busy_count = zones.info[i].busy_count;
4153 mejdrech 1260
 
3205 jermar 1261
        spinlock_unlock(&zones.lock);
1262
        interrupts_restore(ipl);
4153 mejdrech 1263
 
1264
        bool available = zone_flags_available(flags);
1265
 
4581 mejdrech 1266
        printf("%-2" PRIs, i);
4153 mejdrech 1267
 
3057 decky 1268
#ifdef __32_BITS__
4153 mejdrech 1269
        printf("   %10p", base);
3057 decky 1270
#endif
4153 mejdrech 1271
 
3057 decky 1272
#ifdef __64_BITS__
4153 mejdrech 1273
        printf("   %18p", base);
3057 decky 1274
#endif
2712 decky 1275
 
4581 mejdrech 1276
        printf(" %12" PRIs " %c%c%c      ", count,
4153 mejdrech 1277
            available ? 'A' : ' ',
1278
            (flags & ZONE_RESERVED) ? 'R' : ' ',
1279
            (flags & ZONE_FIRMWARE) ? 'F' : ' ');
1280
 
1281
        if (available)
4581 mejdrech 1282
            printf("%12" PRIs " %12" PRIs,
4153 mejdrech 1283
                free_count, busy_count);
1284
 
1285
        printf("\n");
676 bondari 1286
    }
1287
}
1288
 
1708 jermar 1289
/** Prints zone details.
677 bondari 1290
 *
4153 mejdrech 1291
 * @param num Zone base address or zone number.
1292
 *
677 bondari 1293
 */
4581 mejdrech 1294
void zone_print_one(size_t num)
3185 jermar 1295
{
4153 mejdrech 1296
    ipl_t ipl = interrupts_disable();
814 palkovsky 1297
    spinlock_lock(&zones.lock);
4581 mejdrech 1298
    size_t znum = (size_t) -1;
4153 mejdrech 1299
 
4581 mejdrech 1300
    size_t i;
1037 decky 1301
    for (i = 0; i < zones.count; i++) {
4153 mejdrech 1302
        if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
1303
            znum = i;
822 palkovsky 1304
            break;
1305
        }
676 bondari 1306
    }
4153 mejdrech 1307
 
4581 mejdrech 1308
    if (znum == (size_t) -1) {
3206 jermar 1309
        spinlock_unlock(&zones.lock);
1310
        interrupts_restore(ipl);
822 palkovsky 1311
        printf("Zone not found.\n");
3206 jermar 1312
        return;
822 palkovsky 1313
    }
676 bondari 1314
 
4153 mejdrech 1315
    uintptr_t base = PFN2ADDR(zones.info[i].base);
1316
    zone_flags_t flags = zones.info[i].flags;
4581 mejdrech 1317
    size_t count = zones.info[i].count;
1318
    size_t free_count = zones.info[i].free_count;
1319
    size_t busy_count = zones.info[i].busy_count;
4153 mejdrech 1320
 
814 palkovsky 1321
    spinlock_unlock(&zones.lock);
701 jermar 1322
    interrupts_restore(ipl);
4153 mejdrech 1323
 
1324
    bool available = zone_flags_available(flags);
1325
 
4581 mejdrech 1326
    printf("Zone number:       %" PRIs "\n", znum);
3206 jermar 1327
    printf("Zone base address: %p\n", base);
4581 mejdrech 1328
    printf("Zone size:         %" PRIs " frames (%" PRIs " KiB)\n", count,
3206 jermar 1329
        SIZE2KB(FRAMES2SIZE(count)));
4153 mejdrech 1330
    printf("Zone flags:        %c%c%c\n",
1331
        available ? 'A' : ' ',
1332
        (flags & ZONE_RESERVED) ? 'R' : ' ',
1333
        (flags & ZONE_FIRMWARE) ? 'F' : ' ');
1334
 
1335
    if (available) {
4581 mejdrech 1336
        printf("Allocated space:   %" PRIs " frames (%" PRIs " KiB)\n",
4153 mejdrech 1337
            busy_count, SIZE2KB(FRAMES2SIZE(busy_count)));
4581 mejdrech 1338
        printf("Available space:   %" PRIs " frames (%" PRIs " KiB)\n",
4153 mejdrech 1339
            free_count, SIZE2KB(FRAMES2SIZE(free_count)));
1340
    }
676 bondari 1341
}
1342
 
1757 jermar 1343
/** @}
1702 cejka 1344
 */