source: mainline/kernel/generic/src/mm/frame.c@ 11d41be5

/*
 * Copyright (c) 2001-2005 Jakub Jermar
 * Copyright (c) 2005 Sergey Bondari
 * Copyright (c) 2009 Martin Decky
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup genericmm
 * @{
 */

/**
 * @file
 * @brief Physical frame allocator.
 *
 * This file contains the physical frame allocator and memory zone management.
 * The frame allocator is built on top of the two-level bitmap structure.
 *
 */

#include <typedefs.h>
#include <mm/frame.h>
#include <mm/reserve.h>
#include <mm/as.h>
#include <panic.h>
#include <debug.h>
#include <adt/list.h>
#include <synch/mutex.h>
#include <synch/condvar.h>
#include <arch/asm.h>
#include <arch.h>
#include <print.h>
#include <align.h>
#include <mm/slab.h>
#include <bitops.h>
#include <macros.h>
#include <config.h>
#include <str.h>

zones_t zones;

/*
 * Synchronization primitives used to sleep when there is no memory
 * available.
 */
static mutex_t mem_avail_mtx;
static condvar_t mem_avail_cv;
static size_t mem_avail_req = 0;  /**< Number of frames requested. */
static size_t mem_avail_gen = 0;  /**< Generation counter. */

/********************/
/* Helper functions */
/********************/

NO_TRACE static inline size_t frame_index(zone_t *zone, frame_t *frame)
{
        return (size_t) (frame - zone->frames);
}

NO_TRACE static inline size_t frame_index_abs(zone_t *zone, frame_t *frame)
{
        return (size_t) (frame - zone->frames) + zone->base;
}

NO_TRACE static inline bool frame_index_valid(zone_t *zone, size_t index)
{
        return (index < zone->count);
}

/** Initialize frame structure.
 *
 * @param frame Frame structure to be initialized.
 *
 */
NO_TRACE static void frame_initialize(frame_t *frame)
{
        frame->refcount = 0;
        frame->parent = NULL;
}

/*******************/
/* Zones functions */
/*******************/

/** Insert-sort zone into zones list.
 *
 * Assume interrupts are disabled and zones lock is
 * locked.
 *
 * @param base  Base frame of the newly inserted zone.
 * @param count Number of frames of the newly inserted zone.
 *
 * @return Zone number on success, -1 on error.
 *
 */
NO_TRACE static size_t zones_insert_zone(pfn_t base, size_t count,
    zone_flags_t flags)
{
        if (zones.count + 1 == ZONES_MAX) {
                printf("Maximum zone count %u exceeded!\n", ZONES_MAX);
                return (size_t) -1;
        }
        
        size_t i;
        for (i = 0; i < zones.count; i++) {
                /* Check for overlap */
                if (overlaps(zones.info[i].base, zones.info[i].count,
                    base, count)) {
                        
                        /*
                         * If the overlaping zones are of the same type
                         * and the new zone is completely within the previous
                         * one, then quietly ignore the new zone.
                         *
                         */
                        
                        if ((zones.info[i].flags != flags) ||
                            (!iswithin(zones.info[i].base, zones.info[i].count,
                            base, count))) {
                                printf("Zone (%p, %p) overlaps "
                                    "with previous zone (%p %p)!\n",
                                    (void *) PFN2ADDR(base), (void *) PFN2ADDR(count),
                                    (void *) PFN2ADDR(zones.info[i].base),
                                    (void *) PFN2ADDR(zones.info[i].count));
                        }
                        
                        return (size_t) -1;
                }
                if (base < zones.info[i].base)
                        break;
        }
        
        /* Move other zones up */
        for (size_t j = zones.count; j > i; j--)
                zones.info[j] = zones.info[j - 1];
        
        zones.count++;
        
        return i;
}

/** Get total available frames.
 *
 * Assume interrupts are disabled and zones lock is
 * locked.
 *
 * @return Total number of available frames.
 *
 */
NO_TRACE static size_t frame_total_free_get_internal(void)
{
        size_t total = 0;
        size_t i;

        for (i = 0; i < zones.count; i++)
                total += zones.info[i].free_count;
        
        return total;
}

NO_TRACE size_t frame_total_free_get(void)
{
        size_t total;

        irq_spinlock_lock(&zones.lock, true);
        total = frame_total_free_get_internal();
        irq_spinlock_unlock(&zones.lock, true);

        return total;
}


/** Find a zone with a given frames.
 *
 * Assume interrupts are disabled and zones lock is
 * locked.
 *
 * @param frame Frame number contained in zone.
 * @param count Number of frames to look for.
 * @param hint  Used as zone hint.
 *
 * @return Zone index or -1 if not found.
 *
 */
NO_TRACE size_t find_zone(pfn_t frame, size_t count, size_t hint)
{
        if (hint >= zones.count)
                hint = 0;
        
        size_t i = hint;
        do {
                if ((zones.info[i].base <= frame)
                    && (zones.info[i].base + zones.info[i].count >= frame + count))
                        return i;
                
                i++;
                if (i >= zones.count)
                        i = 0;
                
        } while (i != hint);
        
        return (size_t) -1;
}

/** @return True if zone can allocate specified number of frames */
NO_TRACE static bool zone_can_alloc(zone_t *zone, size_t count,
    pfn_t constraint)
{
        /*
         * The function bitmap_allocate_range() does not modify
         * the bitmap if the last argument is NULL.
         */
        
        return ((zone->flags & ZONE_AVAILABLE) &&
            bitmap_allocate_range(&zone->bitmap, count, zone->base,
            FRAME_LOWPRIO, constraint, NULL));
}

/** Find a zone that can allocate specified number of frames
 *
 * This function searches among all zones. Assume interrupts are
 * disabled and zones lock is locked.
 *
 * @param count      Number of free frames we are trying to find.
 * @param flags      Required flags of the zone.
 * @param constraint Indication of bits that cannot be set in the
 *                   physical frame number of the first allocated frame.
 * @param hint       Preferred zone.
 *
 * @return Zone that can allocate specified number of frames.
 * @return -1 if no zone can satisfy the request.
 *
 */
NO_TRACE static size_t find_free_zone_all(size_t count, zone_flags_t flags,
    pfn_t constraint, size_t hint)
{
        for (size_t pos = 0; pos < zones.count; pos++) {
                size_t i = (pos + hint) % zones.count;
                
                /* Check whether the zone meets the search criteria. */
                if (!ZONE_FLAGS_MATCH(zones.info[i].flags, flags))
                        continue;
                
                /* Check if the zone can satisfy the allocation request. */
                if (zone_can_alloc(&zones.info[i], count, constraint))
                        return i;
        }
        
        return (size_t) -1;
}

/** Check if frame range  priority memory
 *
 * @param pfn   Starting frame.
 * @param count Number of frames.
 *
 * @return True if the range contains only priority memory.
 *
 */
NO_TRACE static bool is_high_priority(pfn_t base, size_t count)
{
        return (base + count <= FRAME_LOWPRIO);
}

/** Find a zone that can allocate specified number of frames
 *
 * This function ignores zones that contain only high-priority
 * memory. Assume interrupts are disabled and zones lock is locked.
 *
 * @param count      Number of free frames we are trying to find.
 * @param flags      Required flags of the zone.
 * @param constraint Indication of bits that cannot be set in the
 *                   physical frame number of the first allocated frame.
 * @param hint       Preferred zone.
 *
 * @return Zone that can allocate specified number of frames.
 * @return -1 if no low-priority zone can satisfy the request.
 *
 */
NO_TRACE static size_t find_free_zone_lowprio(size_t count, zone_flags_t flags,
    pfn_t constraint, size_t hint)
{       
        for (size_t pos = 0; pos < zones.count; pos++) {
                size_t i = (pos + hint) % zones.count;
                
                /* Skip zones containing only high-priority memory. */
                if (is_high_priority(zones.info[i].base, zones.info[i].count))
                        continue;
                
                /* Check whether the zone meets the search criteria. */
                if (!ZONE_FLAGS_MATCH(zones.info[i].flags, flags))
                        continue;
                
                /* Check if the zone can satisfy the allocation request. */
                if (zone_can_alloc(&zones.info[i], count, constraint))
                        return i;
        }
        
        return (size_t) -1;
}

/** Find a zone that can allocate specified number of frames
 *
 * Assume interrupts are disabled and zones lock is
 * locked.
 *
 * @param count      Number of free frames we are trying to find.
 * @param flags      Required flags of the target zone.
 * @param constraint Indication of bits that cannot be set in the
 *                   physical frame number of the first allocated frame.
 * @param hint       Preferred zone.
 *
 * @return Zone that can allocate specified number of frames.
 * @return -1 if no zone can satisfy the request.
 *
 */
NO_TRACE static size_t find_free_zone(size_t count, zone_flags_t flags,
    pfn_t constraint, size_t hint)
{
        if (hint >= zones.count)
                hint = 0;
        
        /*
         * Prefer zones with low-priority memory over
         * zones with high-priority memory.
         */
        
        size_t znum = find_free_zone_lowprio(count, flags, constraint, hint);
        if (znum != (size_t) -1)
                return znum;
        
        /* Take all zones into account */
        return find_free_zone_all(count, flags, constraint, hint);
}

/******************/
/* Zone functions */
/******************/

/** Return frame from zone. */
NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t index)
{
        ASSERT(index < zone->count);
        
        return &zone->frames[index];
}

/** Allocate frame in particular zone.
 *
 * Assume zone is locked and is available for allocation.
 * Panics if allocation is impossible.
 *
 * @param zone       Zone to allocate from.
 * @param count      Number of frames to allocate
 * @param constraint Indication of bits that cannot be set in the
 *                   physical frame number of the first allocated frame.
 *
 * @return Frame index in zone.
 *
 */
NO_TRACE static size_t zone_frame_alloc(zone_t *zone, size_t count,
    pfn_t constraint)
{
        ASSERT(zone->flags & ZONE_AVAILABLE);
        
        /* Allocate frames from zone */
        size_t index;
        int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base,
            FRAME_LOWPRIO, constraint, &index);
        
        ASSERT(avail);
        
        /* Update frame reference count */
        for (size_t i = 0; i < count; i++) {
                frame_t *frame = zone_get_frame(zone, index + i);
                
                ASSERT(frame->refcount == 0);
                frame->refcount = 1;
        }
        
        /* Update zone information. */
        zone->free_count -= count;
        zone->busy_count += count;
        
        return index;
}

/** Free frame from zone.
 *
 * Assume zone is locked and is available for deallocation.
 *
 * @param zone  Pointer to zone from which the frame is to be freed.
 * @param index Frame index relative to zone.
 *
 * @return Number of freed frames.
 *
 */
NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t index)
{
        ASSERT(zone->flags & ZONE_AVAILABLE);
        
        frame_t *frame = zone_get_frame(zone, index);
        
        ASSERT(frame->refcount > 0);
        
        if (!--frame->refcount) {
                bitmap_set(&zone->bitmap, index, 0);
                
                /* Update zone information. */
                zone->free_count++;
                zone->busy_count--;
                
                return 1;
        }
        
        return 0;
}

/** Mark frame in zone unavailable to allocation. */
NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t index)
{
        ASSERT(zone->flags & ZONE_AVAILABLE);
        
        frame_t *frame = zone_get_frame(zone, index);
        if (frame->refcount > 0)
                return;
        
        frame->refcount = 1;
        bitmap_set_range(&zone->bitmap, index, 1);
        
        zone->free_count--;
        reserve_force_alloc(1);
}

/** Merge two zones.
 *
 * Assume z1 & z2 are locked and compatible and zones lock is
 * locked.
 *
 * @param z1       First zone to merge.
 * @param z2       Second zone to merge.
 * @param old_z1   Original data of the first zone.
 * @param confdata Merged zone configuration data.
 *
 */
NO_TRACE static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1,
    void *confdata)
{
        ASSERT(zones.info[z1].flags & ZONE_AVAILABLE);
        ASSERT(zones.info[z2].flags & ZONE_AVAILABLE);
        ASSERT(zones.info[z1].flags == zones.info[z2].flags);
        ASSERT(zones.info[z1].base < zones.info[z2].base);
        ASSERT(!overlaps(zones.info[z1].base, zones.info[z1].count,
            zones.info[z2].base, zones.info[z2].count));
        
        /* Difference between zone bases */
        pfn_t base_diff = zones.info[z2].base - zones.info[z1].base;
        
        zones.info[z1].count = base_diff + zones.info[z2].count;
        zones.info[z1].free_count += zones.info[z2].free_count;
        zones.info[z1].busy_count += zones.info[z2].busy_count;
        
        bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count,
            confdata + (sizeof(frame_t) * zones.info[z1].count));
        bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count);
        
        zones.info[z1].frames = (frame_t *) confdata;
        
        /*
         * Copy frames and bits from both zones to preserve parents, etc.
         */
        
        for (size_t i = 0; i < old_z1->count; i++) {
                bitmap_set(&zones.info[z1].bitmap, i,
                    bitmap_get(&old_z1->bitmap, i));
                zones.info[z1].frames[i] = old_z1->frames[i];
        }
        
        for (size_t i = 0; i < zones.info[z2].count; i++) {
                bitmap_set(&zones.info[z1].bitmap, base_diff + i,
                    bitmap_get(&zones.info[z2].bitmap, i));
                zones.info[z1].frames[base_diff + i] =
                    zones.info[z2].frames[i];
        }
}

/** Return old configuration frames into the zone.
 *
 * We have two cases:
 * - The configuration data is outside the zone
 *   -> do nothing (perhaps call frame_free?)
 * - The configuration data was created by zone_create
 *   or updated by reduce_region -> free every frame
 *
 * @param znum  The actual zone where freeing should occur.
 * @param pfn   Old zone configuration frame.
 * @param count Old zone frame count.
 *
 */
NO_TRACE static void return_config_frames(size_t znum, pfn_t pfn, size_t count)
{
        ASSERT(zones.info[znum].flags & ZONE_AVAILABLE);
        
        size_t cframes = SIZE2FRAMES(zone_conf_size(count));
        
        if ((pfn < zones.info[znum].base) ||
            (pfn >= zones.info[znum].base + zones.info[znum].count))
                return;
        
        for (size_t i = 0; i < cframes; i++)
                (void) zone_frame_free(&zones.info[znum],
                    pfn - zones.info[znum].base + i);
}

/** Merge zones z1 and z2.
 *
 * The merged zones must be 2 zones with no zone existing in between
 * (which means that z2 = z1 + 1). Both zones must be available zones
 * with the same flags.
 *
 * When you create a new zone, the frame allocator configuration does
 * not to be 2^order size. Once the allocator is running it is no longer
 * possible, merged configuration data occupies more space :-/
 *
 */
bool zone_merge(size_t z1, size_t z2)
{
        irq_spinlock_lock(&zones.lock, true);
        
        bool ret = true;
        
        /*
         * We can join only 2 zones with none existing inbetween,
         * the zones have to be available and with the same
         * set of flags
         */
        if ((z1 >= zones.count) || (z2 >= zones.count) || (z2 - z1 != 1) ||
            (zones.info[z1].flags != zones.info[z2].flags)) {
                ret = false;
                goto errout;
        }
        
        pfn_t cframes = SIZE2FRAMES(zone_conf_size(
            zones.info[z2].base - zones.info[z1].base
            + zones.info[z2].count));
        
        /* Allocate merged zone data inside one of the zones */
        pfn_t pfn;
        if (zone_can_alloc(&zones.info[z1], cframes, 0)) {
                pfn = zones.info[z1].base +
                    zone_frame_alloc(&zones.info[z1], cframes, 0);
        } else if (zone_can_alloc(&zones.info[z2], cframes, 0)) {
                pfn = zones.info[z2].base +
                    zone_frame_alloc(&zones.info[z2], cframes, 0);
        } else {
                ret = false;
                goto errout;
        }
        
        /* Preserve original data from z1 */
        zone_t old_z1 = zones.info[z1];
        
        /* Do zone merging */
        zone_merge_internal(z1, z2, &old_z1, (void *) PA2KA(PFN2ADDR(pfn)));
        
        /* Subtract zone information from busy frames */
        zones.info[z1].busy_count -= cframes;
        
        /* Free old zone information */
        return_config_frames(z1,
            ADDR2PFN(KA2PA((uintptr_t) old_z1.frames)), old_z1.count);
        return_config_frames(z1,
            ADDR2PFN(KA2PA((uintptr_t) zones.info[z2].frames)),
            zones.info[z2].count);
        
        /* Move zones down */
        for (size_t i = z2 + 1; i < zones.count; i++)
                zones.info[i - 1] = zones.info[i];
        
        zones.count--;
        
errout:
        irq_spinlock_unlock(&zones.lock, true);
        
        return ret;
}

/** Merge all mergeable zones into one big zone.
 *
 * It is reasonable to do this on systems where
 * BIOS reports parts in chunks, so that we could
 * have 1 zone (it's faster).
 *
 */
void zone_merge_all(void)
{
        size_t i = 1;
        
        while (i < zones.count) {
                if (!zone_merge(i - 1, i))
                        i++;
        }
}

/** Create new frame zone.
 *
 * @param zone     Zone to construct.
 * @param start    Physical address of the first frame within the zone.
 * @param count    Count of frames in zone.
 * @param flags    Zone flags.
 * @param confdata Configuration data of the zone.
 *
 * @return Initialized zone.
 *
 */
NO_TRACE static void zone_construct(zone_t *zone, pfn_t start, size_t count,
    zone_flags_t flags, void *confdata)
{
        zone->base = start;
        zone->count = count;
        zone->flags = flags;
        zone->free_count = count;
        zone->busy_count = 0;
        
        if (flags & ZONE_AVAILABLE) {
                /*
                 * Initialize frame bitmap (located after the array of
                 * frame_t structures in the configuration space).
                 */
                
                bitmap_initialize(&zone->bitmap, count, confdata +
                    (sizeof(frame_t) * count));
                bitmap_clear_range(&zone->bitmap, 0, count);
                
                /*
                 * Initialize the array of frame_t structures.
                 */
                
                zone->frames = (frame_t *) confdata;
                
                for (size_t i = 0; i < count; i++)
                        frame_initialize(&zone->frames[i]);
        } else {
                bitmap_initialize(&zone->bitmap, 0, NULL);
                zone->frames = NULL;
        }
}

/** Compute configuration data size for zone.
 *
 * @param count Size of zone in frames.
 *
 * @return Size of zone configuration info (in bytes).
 *
 */
size_t zone_conf_size(size_t count)
{
        return (count * sizeof(frame_t) + bitmap_size(count));
}

/** Allocate external configuration frames from low memory. */
pfn_t zone_external_conf_alloc(size_t count)
{
        size_t frames = SIZE2FRAMES(zone_conf_size(count));
        
        return ADDR2PFN((uintptr_t)
            frame_alloc(frames, FRAME_LOWMEM | FRAME_ATOMIC, 0));
}

/** Create and add zone to system.
 *
 * @param start     First frame number (absolute).
 * @param count     Size of zone in frames.
 * @param confframe Where configuration frames are supposed to be.
 *                  Automatically checks that we will not disturb the
 *                  kernel and possibly init. If confframe is given
 *                  _outside_ this zone, it is expected, that the area is
 *                  already marked BUSY and big enough to contain
 *                  zone_conf_size() amount of data. If the confframe is
 *                  inside the area, the zone free frame information is
 *                  modified not to include it.
 *
 * @return Zone number or -1 on error.
 *
 */
size_t zone_create(pfn_t start, size_t count, pfn_t confframe,
    zone_flags_t flags)
{
        irq_spinlock_lock(&zones.lock, true);
        
        if (flags & ZONE_AVAILABLE) {  /* Create available zone */
                /*
                 * Theoretically we could have NULL here, practically make sure
                 * nobody tries to do that. If some platform requires, remove
                 * the assert
                 */
                ASSERT(confframe != ADDR2PFN((uintptr_t ) NULL));
                
                /* Update the known end of physical memory. */
                config.physmem_end = max(config.physmem_end, PFN2ADDR(start + count));
                
                /*
                 * If confframe is supposed to be inside our zone, then make sure
                 * it does not span kernel & init
                 */
                size_t confcount = SIZE2FRAMES(zone_conf_size(count));
                
                if ((confframe >= start) && (confframe < start + count)) {
                        for (; confframe < start + count; confframe++) {
                                uintptr_t addr = PFN2ADDR(confframe);
                                if (overlaps(addr, PFN2ADDR(confcount),
                                    KA2PA(config.base), config.kernel_size))
                                        continue;
                                
                                if (overlaps(addr, PFN2ADDR(confcount),
                                    KA2PA(config.stack_base), config.stack_size))
                                        continue;
                                
                                bool overlap = false;
                                for (size_t i = 0; i < init.cnt; i++) {
                                        if (overlaps(addr, PFN2ADDR(confcount),
                                            init.tasks[i].paddr,
                                            init.tasks[i].size)) {
                                                overlap = true;
                                                break;
                                        }
                                }
                                
                                if (overlap)
                                        continue;
                                
                                break;
                        }
                        
                        if (confframe >= start + count)
                                panic("Cannot find configuration data for zone.");
                }
                
                size_t znum = zones_insert_zone(start, count, flags);
                if (znum == (size_t) -1) {
                        irq_spinlock_unlock(&zones.lock, true);
                        return (size_t) -1;
                }
                
                void *confdata = (void *) PA2KA(PFN2ADDR(confframe));
                zone_construct(&zones.info[znum], start, count, flags, confdata);
                
                /* If confdata in zone, mark as unavailable */
                if ((confframe >= start) && (confframe < start + count)) {
                        for (size_t i = confframe; i < confframe + confcount; i++)
                                zone_mark_unavailable(&zones.info[znum],
                                    i - zones.info[znum].base);
                }
                
                irq_spinlock_unlock(&zones.lock, true);
                
                return znum;
        }
        
        /* Non-available zone */
        size_t znum = zones_insert_zone(start, count, flags);
        if (znum == (size_t) -1) {
                irq_spinlock_unlock(&zones.lock, true);
                return (size_t) -1;
        }
        
        zone_construct(&zones.info[znum], start, count, flags, NULL);
        
        irq_spinlock_unlock(&zones.lock, true);
        
        return znum;
}

/*******************/
/* Frame functions */
/*******************/

/** Set parent of frame. */
void frame_set_parent(pfn_t pfn, void *data, size_t hint)
{
        irq_spinlock_lock(&zones.lock, true);
        
        size_t znum = find_zone(pfn, 1, hint);
        
        ASSERT(znum != (size_t) -1);
        
        zone_get_frame(&zones.info[znum],
            pfn - zones.info[znum].base)->parent = data;
        
        irq_spinlock_unlock(&zones.lock, true);
}

void *frame_get_parent(pfn_t pfn, size_t hint)
{
        irq_spinlock_lock(&zones.lock, true);
        
        size_t znum = find_zone(pfn, 1, hint);
        
        ASSERT(znum != (size_t) -1);
        
        void *res = zone_get_frame(&zones.info[znum],
            pfn - zones.info[znum].base)->parent;
        
        irq_spinlock_unlock(&zones.lock, true);
        
        return res;
}

/** Allocate frames of physical memory.
 *
 * @param count      Number of continuous frames to allocate.
 * @param flags      Flags for host zone selection and address processing.
 * @param constraint Indication of physical address bits that cannot be
 *                   set in the address of the first allocated frame.
 * @param pzone      Preferred zone.
 *
 * @return Physical address of the allocated frame.
 *
 */
uintptr_t frame_alloc_generic(size_t count, frame_flags_t flags,
    uintptr_t constraint, size_t *pzone)
{
        ASSERT(count > 0);
        
        size_t hint = pzone ? (*pzone) : 0;
        pfn_t frame_constraint = ADDR2PFN(constraint);
        
        /*
         * If not told otherwise, we must first reserve the memory.
         */
        if (!(flags & FRAME_NO_RESERVE))
                reserve_force_alloc(count);
        
loop:
        irq_spinlock_lock(&zones.lock, true);
        
        /*
         * First, find suitable frame zone.
         */
        size_t znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
            frame_constraint, hint);
        
        /*
         * If no memory, reclaim some slab memory,
         * if it does not help, reclaim all.
         */
        if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
                irq_spinlock_unlock(&zones.lock, true);
                size_t freed = slab_reclaim(0);
                irq_spinlock_lock(&zones.lock, true);
                
                if (freed > 0)
                        znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
                            frame_constraint, hint);
                
                if (znum == (size_t) -1) {
                        irq_spinlock_unlock(&zones.lock, true);
                        freed = slab_reclaim(SLAB_RECLAIM_ALL);
                        irq_spinlock_lock(&zones.lock, true);
                        
                        if (freed > 0)
                                znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
                                    frame_constraint, hint);
                }
        }
        
        if (znum == (size_t) -1) {
                if (flags & FRAME_ATOMIC) {
                        irq_spinlock_unlock(&zones.lock, true);
                        
                        if (!(flags & FRAME_NO_RESERVE))
                                reserve_free(count);
                        
                        return 0;
                }
                
#ifdef CONFIG_DEBUG
                size_t avail = frame_total_free_get_internal();
#endif
                
                irq_spinlock_unlock(&zones.lock, true);
                
                if (!THREAD)
                        panic("Cannot wait for %zu frames to become available "
                            "(%zu available).", count, avail);
                
                /*
                 * Sleep until some frames are available again.
                 */
                
#ifdef CONFIG_DEBUG
                printf("Thread %" PRIu64 " waiting for %zu frames "
                    "(%zu available).\n", THREAD->tid, count, avail);
#endif
                
                /*
                 * Since the mem_avail_mtx is an active mutex, we need to
                 * disable interrupts to prevent deadlock with TLB shootdown.
                 */
                ipl_t ipl = interrupts_disable();
                mutex_lock(&mem_avail_mtx);
                
                if (mem_avail_req > 0)
                        mem_avail_req = min(mem_avail_req, count);
                else
                        mem_avail_req = count;
                
                size_t gen = mem_avail_gen;
                
                while (gen == mem_avail_gen)
                        condvar_wait(&mem_avail_cv, &mem_avail_mtx);
                
                mutex_unlock(&mem_avail_mtx);
                interrupts_restore(ipl);
                
#ifdef CONFIG_DEBUG
                printf("Thread %" PRIu64 " woken up.\n", THREAD->tid);
#endif
                
                goto loop;
        }
        
        pfn_t pfn = zone_frame_alloc(&zones.info[znum], count,
            frame_constraint) + zones.info[znum].base;
        
        irq_spinlock_unlock(&zones.lock, true);
        
        if (pzone)
                *pzone = znum;
        
        return PFN2ADDR(pfn);
}

uintptr_t frame_alloc(size_t count, frame_flags_t flags, uintptr_t constraint)
{
        return frame_alloc_generic(count, flags, constraint, NULL);
}

/** Free frames of physical memory.
 *
 * Find respective frame structures for supplied physical frames.
 * Decrement each frame reference count. If it drops to zero, mark
 * the frames as available.
 *
 * @param start Physical Address of the first frame to be freed.
 * @param count Number of frames to free.
 * @param flags Flags to control memory reservation.
 *
 */
void frame_free_generic(uintptr_t start, size_t count, frame_flags_t flags)
{
        size_t freed = 0;
        
        irq_spinlock_lock(&zones.lock, true);
        
        for (size_t i = 0; i < count; i++) {
                /*
                 * First, find host frame zone for addr.
                 */
                pfn_t pfn = ADDR2PFN(start) + i;
                size_t znum = find_zone(pfn, 1, 0);
                
                ASSERT(znum != (size_t) -1);
                
                freed += zone_frame_free(&zones.info[znum],
                    pfn - zones.info[znum].base);
        }
        
        irq_spinlock_unlock(&zones.lock, true);
        
        /*
         * Signal that some memory has been freed.
         * Since the mem_avail_mtx is an active mutex,
         * we need to disable interruptsto prevent deadlock
         * with TLB shootdown.
         */
        
        ipl_t ipl = interrupts_disable();
        mutex_lock(&mem_avail_mtx);
        
        if (mem_avail_req > 0)
                mem_avail_req -= min(mem_avail_req, freed);
        
        if (mem_avail_req == 0) {
                mem_avail_gen++;
                condvar_broadcast(&mem_avail_cv);
        }
        
        mutex_unlock(&mem_avail_mtx);
        interrupts_restore(ipl);
        
        if (!(flags & FRAME_NO_RESERVE))
                reserve_free(freed);
}

void frame_free(uintptr_t frame, size_t count)
{
        frame_free_generic(frame, count, 0);
}

void frame_free_noreserve(uintptr_t frame, size_t count)
{
        frame_free_generic(frame, count, FRAME_NO_RESERVE);
}

/** Add reference to frame.
 *
 * Find respective frame structure for supplied PFN and
 * increment frame reference count.
 *
 * @param pfn Frame number of the frame to be freed.
 *
 */
NO_TRACE void frame_reference_add(pfn_t pfn)
{
        irq_spinlock_lock(&zones.lock, true);
        
        /*
         * First, find host frame zone for addr.
         */
        size_t znum = find_zone(pfn, 1, 0);
        
        ASSERT(znum != (size_t) -1);
        
        zones.info[znum].frames[pfn - zones.info[znum].base].refcount++;
        
        irq_spinlock_unlock(&zones.lock, true);
}

/** Mark given range unavailable in frame zones.
 *
 */
NO_TRACE void frame_mark_unavailable(pfn_t start, size_t count)
{
        irq_spinlock_lock(&zones.lock, true);
        
        for (size_t i = 0; i < count; i++) {
                size_t znum = find_zone(start + i, 1, 0);
                
                if (znum == (size_t) -1)  /* PFN not found */
                        continue;
                
                zone_mark_unavailable(&zones.info[znum],
                    start + i - zones.info[znum].base);
        }
        
        irq_spinlock_unlock(&zones.lock, true);
}

/** Initialize physical memory management.
 *
 */
void frame_init(void)
{
        if (config.cpu_active == 1) {
                zones.count = 0;
                irq_spinlock_initialize(&zones.lock, "frame.zones.lock");
                mutex_initialize(&mem_avail_mtx, MUTEX_ACTIVE);
                condvar_initialize(&mem_avail_cv);
        }
        
        /* Tell the architecture to create some memory */
        frame_low_arch_init();
        
        if (config.cpu_active == 1) {
                frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
                    SIZE2FRAMES(config.kernel_size));
                frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)),
                    SIZE2FRAMES(config.stack_size));
                
                for (size_t i = 0; i < init.cnt; i++)
                        frame_mark_unavailable(ADDR2PFN(init.tasks[i].paddr),
                            SIZE2FRAMES(init.tasks[i].size));
                
                if (ballocs.size)
                        frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)),
                            SIZE2FRAMES(ballocs.size));
                
                /*
                 * Blacklist first frame, as allocating NULL would
                 * fail in some places
                 */
                frame_mark_unavailable(0, 1);
        }
        
        frame_high_arch_init();
}

/** Adjust bounds of physical memory region according to low/high memory split.
 *
 * @param low[in]      If true, the adjustment is performed to make the region
 *                     fit in the low memory. Otherwise the adjustment is
 *                     performed to make the region fit in the high memory.
 * @param basep[inout] Pointer to a variable which contains the region's base
 *                     address and which may receive the adjusted base address.
 * @param sizep[inout] Pointer to a variable which contains the region's size
 *                     and which may receive the adjusted size.
 *
 * @return True if the region still exists even after the adjustment.
 * @return False otherwise.
 *
 */
bool frame_adjust_zone_bounds(bool low, uintptr_t *basep, size_t *sizep)
{
        uintptr_t limit = KA2PA(config.identity_base) + config.identity_size;
        
        if (low) {
                if (*basep > limit)
                        return false;
                
                if (*basep + *sizep > limit)
                        *sizep = limit - *basep;
        } else {
                if (*basep + *sizep <= limit)
                        return false;
                
                if (*basep <= limit) {
                        *sizep -= limit - *basep;
                        *basep = limit;
                }
        }
        
        return true;
}

/** Return total size of all zones.
 *
 */
uint64_t zones_total_size(void)
{
        irq_spinlock_lock(&zones.lock, true);
        
        uint64_t total = 0;
        
        for (size_t i = 0; i < zones.count; i++)
                total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
        
        irq_spinlock_unlock(&zones.lock, true);
        
        return total;
}

void zones_stats(uint64_t *total, uint64_t *unavail, uint64_t *busy,
    uint64_t *free)
{
        ASSERT(total != NULL);
        ASSERT(unavail != NULL);
        ASSERT(busy != NULL);
        ASSERT(free != NULL);
        
        irq_spinlock_lock(&zones.lock, true);
        
        *total = 0;
        *unavail = 0;
        *busy = 0;
        *free = 0;
        
        for (size_t i = 0; i < zones.count; i++) {
                *total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
                
                if (zones.info[i].flags & ZONE_AVAILABLE) {
                        *busy += (uint64_t) FRAMES2SIZE(zones.info[i].busy_count);
                        *free += (uint64_t) FRAMES2SIZE(zones.info[i].free_count);
                } else
                        *unavail += (uint64_t) FRAMES2SIZE(zones.info[i].count);
        }
        
        irq_spinlock_unlock(&zones.lock, true);
}

/** Prints list of zones.
 *
 */
void zones_print_list(void)
{
#ifdef __32_BITS__
        printf("[nr] [base addr] [frames    ] [flags ] [free frames ] [busy frames ]\n");
#endif

#ifdef __64_BITS__
        printf("[nr] [base address    ] [frames    ] [flags ] [free frames ] [busy frames ]\n");
#endif
        
        /*
         * Because printing may require allocation of memory, we may not hold
         * the frame allocator locks when printing zone statistics. Therefore,
         * we simply gather the statistics under the protection of the locks and
         * print the statistics when the locks have been released.
         *
         * When someone adds/removes zones while we are printing the statistics,
         * we may end up with inaccurate output (e.g. a zone being skipped from
         * the listing).
         */
        
        size_t free_lowmem = 0;
        size_t free_highmem = 0;
        size_t free_highprio = 0;
        
        for (size_t i = 0;; i++) {
                irq_spinlock_lock(&zones.lock, true);
                
                if (i >= zones.count) {
                        irq_spinlock_unlock(&zones.lock, true);
                        break;
                }
                
                pfn_t fbase = zones.info[i].base;
                uintptr_t base = PFN2ADDR(fbase);
                size_t count = zones.info[i].count;
                zone_flags_t flags = zones.info[i].flags;
                size_t free_count = zones.info[i].free_count;
                size_t busy_count = zones.info[i].busy_count;
                
                bool available = ((flags & ZONE_AVAILABLE) != 0);
                bool lowmem = ((flags & ZONE_LOWMEM) != 0);
                bool highmem = ((flags & ZONE_HIGHMEM) != 0);
                bool highprio = is_high_priority(fbase, count);
                
                if (available) {
                        if (lowmem)
                                free_lowmem += free_count;
                        
                        if (highmem)
                                free_highmem += free_count;
                        
                        if (highprio) {
                                free_highprio += free_count;
                        } else {
                                /*
                                 * Walk all frames of the zone and examine
                                 * all high priority memory to get accurate
                                 * statistics.
                                 */
                                
                                for (size_t index = 0; index < count; index++) {
                                        if (is_high_priority(fbase + index, 0)) {
                                                if (!bitmap_get(&zones.info[i].bitmap, index))
                                                        free_highprio++;
                                        } else
                                                break;
                                }
                        }
                }
                
                irq_spinlock_unlock(&zones.lock, true);
                
                printf("%-4zu", i);
                
#ifdef __32_BITS__
                printf("  %p", (void *) base);
#endif
                
#ifdef __64_BITS__
                printf(" %p", (void *) base);
#endif
                
                printf(" %12zu %c%c%c%c%c    ", count,
                    available ? 'A' : '-',
                    (flags & ZONE_RESERVED) ? 'R' : '-',
                    (flags & ZONE_FIRMWARE) ? 'F' : '-',
                    (flags & ZONE_LOWMEM) ? 'L' : '-',
                    (flags & ZONE_HIGHMEM) ? 'H' : '-');
                
                if (available)
                        printf("%14zu %14zu",
                            free_count, busy_count);
                
                printf("\n");
        }
        
        printf("\n");
        
        uint64_t size;
        const char *size_suffix;
        
        bin_order_suffix(FRAMES2SIZE(free_lowmem), &size, &size_suffix,
            false);
        printf("Available low memory:    %zu frames (%" PRIu64 " %s)\n",
            free_lowmem, size, size_suffix);
        
        bin_order_suffix(FRAMES2SIZE(free_highmem), &size, &size_suffix,
            false);
        printf("Available high memory:   %zu frames (%" PRIu64 " %s)\n",
            free_highmem, size, size_suffix);
        
        bin_order_suffix(FRAMES2SIZE(free_highprio), &size, &size_suffix,
            false);
        printf("Available high priority: %zu frames (%" PRIu64 " %s)\n",
            free_highprio, size, size_suffix);
}

/** Prints zone details.
 *
 * @param num Zone base address or zone number.
 *
 */
void zone_print_one(size_t num)
{
        irq_spinlock_lock(&zones.lock, true);
        size_t znum = (size_t) -1;
        
        for (size_t i = 0; i < zones.count; i++) {
                if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
                        znum = i;
                        break;
                }
        }
        
        if (znum == (size_t) -1) {
                irq_spinlock_unlock(&zones.lock, true);
                printf("Zone not found.\n");
                return;
        }
        
        size_t free_lowmem = 0;
        size_t free_highmem = 0;
        size_t free_highprio = 0;
        
        pfn_t fbase = zones.info[znum].base;
        uintptr_t base = PFN2ADDR(fbase);
        zone_flags_t flags = zones.info[znum].flags;
        size_t count = zones.info[znum].count;
        size_t free_count = zones.info[znum].free_count;
        size_t busy_count = zones.info[znum].busy_count;
        
        bool available = ((flags & ZONE_AVAILABLE) != 0);
        bool lowmem = ((flags & ZONE_LOWMEM) != 0);
        bool highmem = ((flags & ZONE_HIGHMEM) != 0);
        bool highprio = is_high_priority(fbase, count);
        
        if (available) {
                if (lowmem)
                        free_lowmem = free_count;
                
                if (highmem)
                        free_highmem = free_count;
                
                if (highprio) {
                        free_highprio = free_count;
                } else {
                        /*
                         * Walk all frames of the zone and examine
                         * all high priority memory to get accurate
                         * statistics.
                         */
                        
                        for (size_t index = 0; index < count; index++) {
                                if (is_high_priority(fbase + index, 0)) {
                                        if (!bitmap_get(&zones.info[znum].bitmap, index))
                                                free_highprio++;
                                } else
                                        break;
                        }
                }
        }
        
        irq_spinlock_unlock(&zones.lock, true);
        
        uint64_t size;
        const char *size_suffix;
        
        bin_order_suffix(FRAMES2SIZE(count), &size, &size_suffix, false);
        
        printf("Zone number:             %zu\n", znum);
        printf("Zone base address:       %p\n", (void *) base);
        printf("Zone size:               %zu frames (%" PRIu64 " %s)\n", count,
            size, size_suffix);
        printf("Zone flags:              %c%c%c%c%c\n",
            available ? 'A' : '-',
            (flags & ZONE_RESERVED) ? 'R' : '-',
            (flags & ZONE_FIRMWARE) ? 'F' : '-',
            (flags & ZONE_LOWMEM) ? 'L' : '-',
            (flags & ZONE_HIGHMEM) ? 'H' : '-');
        
        if (available) {
                bin_order_suffix(FRAMES2SIZE(busy_count), &size, &size_suffix,
                    false);
                printf("Allocated space:         %zu frames (%" PRIu64 " %s)\n",
                    busy_count, size, size_suffix);
                
                bin_order_suffix(FRAMES2SIZE(free_count), &size, &size_suffix,
                    false);
                printf("Available space:         %zu frames (%" PRIu64 " %s)\n",
                    free_count, size, size_suffix);
                
                bin_order_suffix(FRAMES2SIZE(free_lowmem), &size, &size_suffix,
                    false);
                printf("Available low memory:    %zu frames (%" PRIu64 " %s)\n",
                    free_lowmem, size, size_suffix);
                
                bin_order_suffix(FRAMES2SIZE(free_highmem), &size, &size_suffix,
                    false);
                printf("Available high memory:   %zu frames (%" PRIu64 " %s)\n",
                    free_highmem, size, size_suffix);
                
                bin_order_suffix(FRAMES2SIZE(free_highprio), &size, &size_suffix,
                    false);
                printf("Available high priority: %zu frames (%" PRIu64 " %s)\n",
                    free_highprio, size, size_suffix);
        }
}

/** @}
 */