Subversion Repositories HelenOS

Rev

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