Subversion Repositories HelenOS

Rev

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

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