Subversion Repositories HelenOS

Rev

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

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