Subversion Repositories HelenOS

/*

 * 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 buddy allocator.

 *

 * @see buddy.c

 */

#include <arch/types.h>

#include <mm/frame.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>

zones_t zones;

/*

 * Synchronization primitives used to sleep when there is no memory

 * available.

 */

mutex_t mem_avail_mtx;

condvar_t mem_avail_cv;

count_t mem_avail_req = 0;  /**< Number of frames requested. */

count_t mem_avail_gen = 0;  /**< Generation counter. */

/********************/

/* Helper functions */

/********************/

static inline index_t frame_index(zone_t *zone, frame_t *frame)

{

	return (index_t) (frame - zone->frames);

}

static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)

{

	return (index_t) (frame - zone->frames) + zone->base;

}

static inline bool frame_index_valid(zone_t *zone, index_t index)

{

	return (index < zone->count);

}

static inline index_t make_frame_index(zone_t *zone, frame_t *frame)

{

	return (frame - zone->frames);

}

/** Initialize frame structure.

 *

 * @param frame Frame structure to be initialized.

 *

 */

static void frame_initialize(frame_t *frame)

{

	frame->refcount = 1;

	frame->buddy_order = 0;

}

/*******************/

/* 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.

 *

 */

static count_t zones_insert_zone(pfn_t base, count_t count)

{

	if (zones.count + 1 == ZONES_MAX) {

		printf("Maximum zone count %u exceeded!\n", ZONES_MAX);

		return (count_t) -1;

	}

	count_t i;

	for (i = 0; i < zones.count; i++) {

		/* Check for overlap */

		if (overlaps(base, count,

		    zones.info[i].base, zones.info[i].count)) {

			printf("Zones overlap!\n");

			return (count_t) -1;

		}

		if (base < zones.info[i].base)

			break;

	}

	/* Move other zones up */

	count_t j;

	for (j = zones.count; j > i; j--) {

		zones.info[j] = zones.info[j - 1];

		zones.info[j].buddy_system->data =

		    (void *) &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.

 *

 */

#ifdef CONFIG_DEBUG

static count_t total_frames_free(void)

{

	count_t total = 0;

	count_t i;

	for (i = 0; i < zones.count; i++)

		total += zones.info[i].free_count;

	return total;

}

#endif

/** 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.

 *

 */

count_t find_zone(pfn_t frame, count_t count, count_t hint)

{

	if (hint >= zones.count)

		hint = 0;

	count_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 (count_t) -1;

}

/** @return True if zone can allocate specified order */

static bool zone_can_alloc(zone_t *zone, uint8_t order)

{

	return (zone_flags_available(zone->flags)

	    && buddy_system_can_alloc(zone->buddy_system, order));

}

/** Find a zone that can allocate order frames.

 *

 * Assume interrupts are disabled and zones lock is

 * locked.

 *

 * @param order Size (2^order) of free space we are trying to find.

 * @param flags Required flags of the target zone.

 * @param hind  Preferred zone.

 *

 */

static count_t find_free_zone(uint8_t order, zone_flags_t flags, count_t hint)

{

	if (hint >= zones.count)

		hint = 0;

	count_t i = hint;

	do {

		/*

		 * Check whether the zone meets the search criteria.

		 */

		if ((zones.info[i].flags & flags) == flags) {

			/*

			 * Check if the zone has 2^order frames area available.

			 */

			if (zone_can_alloc(&zones.info[i], order))

				return i;

		}

		i++;

		if (i >= zones.count)

			i = 0;

	} while (i != hint);

	return (count_t) -1;

}

/**************************/

/* Buddy system functions */

/**************************/

/** Buddy system find_block implementation.

 *

 * Find block that is parent of current list.

 * That means go to lower addresses, until such block is found

 *

 * @param order Order of parent must be different then this

 *              parameter!!

 *

 */

static link_t *zone_buddy_find_block(buddy_system_t *buddy, link_t *child,

    uint8_t order)

{

	frame_t *frame = list_get_instance(child, frame_t, buddy_link);

	zone_t *zone = (zone_t *) buddy->data;

	index_t index = frame_index(zone, frame);

	do {

		if (zone->frames[index].buddy_order != order)

			return &zone->frames[index].buddy_link;

	} while (index-- > 0);

	return NULL;

}

/** Buddy system find_buddy implementation.

 *

 * @param buddy Buddy system.

 * @param block Block for which buddy should be found.

 *

 * @return Buddy for given block if found.

 *

 */

static link_t *zone_buddy_find_buddy(buddy_system_t *buddy, link_t *block) 

{

	frame_t *frame = list_get_instance(block, frame_t, buddy_link);

	zone_t *zone = (zone_t *) buddy->data;

	ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),

	    frame->buddy_order));

	bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);

	index_t index;

	if (is_left) {

		index = (frame_index(zone, frame)) +

		    (1 << frame->buddy_order);

	} else {	/* is_right */

		index = (frame_index(zone, frame)) -

		    (1 << frame->buddy_order);

	}

	if (frame_index_valid(zone, index)) {

		if ((zone->frames[index].buddy_order == frame->buddy_order) &&

		    (zone->frames[index].refcount == 0)) {

			return &zone->frames[index].buddy_link;

		}

	}

	return NULL;

}

/** Buddy system bisect implementation.

 *

 * @param buddy Buddy system.

 * @param block Block to bisect.

 *

 * @return Right block.

 *

 */

static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)

{

	frame_t *frame_l = list_get_instance(block, frame_t, buddy_link);

	frame_t *frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));

	return &frame_r->buddy_link;

}

/** Buddy system coalesce implementation.

 *

 * @param buddy   Buddy system.

 * @param block_1 First block.

 * @param block_2 First block's buddy.

 *

 * @return Coalesced block (actually block that represents lower

 *         address).

 *

 */

static link_t *zone_buddy_coalesce(buddy_system_t *buddy, link_t *block_1,

    link_t *block_2)

{

	frame_t *frame1 = list_get_instance(block_1, frame_t, buddy_link);

	frame_t *frame2 = list_get_instance(block_2, frame_t, buddy_link);

	return ((frame1 < frame2) ? block_1 : block_2);

}

/** Buddy system set_order implementation.

 *

 * @param buddy Buddy system.

 * @param block Buddy system block.

 * @param order Order to set.

 *

 */

static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,

    uint8_t order)

{

	list_get_instance(block, frame_t, buddy_link)->buddy_order = order;

}

/** Buddy system get_order implementation.

 *

 * @param buddy Buddy system.

 * @param block Buddy system block.

 *

 * @return Order of block.

 *

 */

static uint8_t zone_buddy_get_order(buddy_system_t *buddy, link_t *block)

{

	return list_get_instance(block, frame_t, buddy_link)->buddy_order;

}

/** Buddy system mark_busy implementation.

 *

 * @param buddy Buddy system.

 * @param block Buddy system block.

 *

 */

static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t * block)

{

	list_get_instance(block, frame_t, buddy_link)->refcount = 1;

}

/** Buddy system mark_available implementation.

 *

 * @param buddy Buddy system.

 * @param block Buddy system block.

 */

static void zone_buddy_mark_available(buddy_system_t *buddy, link_t *block)

{

	list_get_instance(block, frame_t, buddy_link)->refcount = 0;

}

static buddy_system_operations_t zone_buddy_system_operations = {

	.find_buddy = zone_buddy_find_buddy,

	.bisect = zone_buddy_bisect,

	.coalesce = zone_buddy_coalesce,

	.set_order = zone_buddy_set_order,

	.get_order = zone_buddy_get_order,

	.mark_busy = zone_buddy_mark_busy,

	.mark_available = zone_buddy_mark_available,

	.find_block = zone_buddy_find_block

};

/******************/

/* Zone functions */

/******************/

/** 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 order Allocate exactly 2^order frames.

 *

 * @return Frame index in zone.

 *

 */

static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)

{

	ASSERT(zone_flags_available(zone->flags));

	/* Allocate frames from zone buddy system */

	link_t *link = buddy_system_alloc(zone->buddy_system, order);

	ASSERT(link);

	/* Update zone information. */

	zone->free_count -= (1 << order);

	zone->busy_count += (1 << order);

	/* Frame will be actually a first frame of the block. */

	frame_t *frame = list_get_instance(link, frame_t, buddy_link);

	/* Get frame address */

	return make_frame_index(zone, frame);

}

/** 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 frame_idx Frame index relative to zone.

 *

 */

static void zone_frame_free(zone_t *zone, index_t frame_idx)

{

	ASSERT(zone_flags_available(zone->flags));

	frame_t *frame = &zone->frames[frame_idx];

	/* Remember frame order */

	uint8_t order = frame->buddy_order;

	ASSERT(frame->refcount);

	if (!--frame->refcount) {

		buddy_system_free(zone->buddy_system, &frame->buddy_link);

		/* Update zone information. */

		zone->free_count += (1 << order);

		zone->busy_count -= (1 << order);

	}

}

/** Return frame from zone. */

static frame_t *zone_get_frame(zone_t *zone, index_t frame_idx)

{

	ASSERT(frame_idx < zone->count);

	return &zone->frames[frame_idx];

}

/** Mark frame in zone unavailable to allocation. */

static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)

{

	ASSERT(zone_flags_available(zone->flags));

	frame_t *frame = zone_get_frame(zone, frame_idx);

	if (frame->refcount)

		return;

	link_t *link __attribute__ ((unused));

	link = buddy_system_alloc_block(zone->buddy_system,

	    &frame->buddy_link);

	ASSERT(link);

	zone->free_count--;

}

/** Merge two zones.

 *

 * Expect buddy to point to space at least zone_conf_size large.

 * 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 date of the first zone.

 * @param buddy  Merged zone buddy.

 *

 */

static void zone_merge_internal(count_t z1, count_t z2, zone_t *old_z1, buddy_system_t *buddy)

{

	ASSERT(zone_flags_available(zones.info[z1].flags));

	ASSERT(zone_flags_available(zones.info[z2].flags));

	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;

	zones.info[z1].buddy_system = buddy;

	uint8_t order = fnzb(zones.info[z1].count);

	buddy_system_create(zones.info[z1].buddy_system, order,

	    &zone_buddy_system_operations, (void *) &zones.info[z1]);

	zones.info[z1].frames =

	    (frame_t *) ((uint8_t *) zones.info[z1].buddy_system

	    + buddy_conf_size(order));

	/* This marks all frames busy */

	count_t i;

	for (i = 0; i < zones.info[z1].count; i++)

		frame_initialize(&zones.info[z1].frames[i]);

	/* Copy frames from both zones to preserve full frame orders,

	 * parents etc. Set all free frames with refcount = 0 to 1, because

	 * we add all free frames to buddy allocator later again, clearing

	 * order to 0. Don't set busy frames with refcount = 0, as they

	 * will not be reallocated during merge and it would make later

	 * problems with allocation/free.

	 */

	for (i = 0; i < old_z1->count; i++)

		zones.info[z1].frames[i] = old_z1->frames[i];

	for (i = 0; i < zones.info[z2].count; i++)

		zones.info[z1].frames[base_diff + i]

		    = zones.info[z2].frames[i];

	i = 0;

	while (i < zones.info[z1].count) {

		if (zones.info[z1].frames[i].refcount) {

			/* Skip busy frames */

			i += 1 << zones.info[z1].frames[i].buddy_order;

		} else {

			/* Free frames, set refcount = 1

			 * (all free frames have refcount == 0, we need not

			 * to check the order)

			 */

			zones.info[z1].frames[i].refcount = 1;

			zones.info[z1].frames[i].buddy_order = 0;

			i++;

		}

	}

	/* Add free blocks from the original zone z1 */

	while (zone_can_alloc(old_z1, 0)) {

		/* Allocate from the original zone */

		pfn_t frame_idx = zone_frame_alloc(old_z1, 0);

		/* Free the frame from the merged zone */

		frame_t *frame = &zones.info[z1].frames[frame_idx];

		frame->refcount = 0;

		buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);

	}

	/* Add free blocks from the original zone z2 */

	while (zone_can_alloc(&zones.info[z2], 0)) {

		/* Allocate from the original zone */

		pfn_t frame_idx = zone_frame_alloc(&zones.info[z2], 0);

		/* Free the frame from the merged zone */

		frame_t *frame = &zones.info[z1].frames[base_diff + frame_idx];

		frame->refcount = 0;

		buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);

	}

}

/** 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.

 *

 */

static void return_config_frames(count_t znum, pfn_t pfn, count_t count)

{

	ASSERT(zone_flags_available(zones.info[znum].flags));

	count_t cframes = SIZE2FRAMES(zone_conf_size(count));

	if ((pfn < zones.info[znum].base)

	    || (pfn >= zones.info[znum].base + zones.info[znum].count))

		return;

	frame_t *frame __attribute__ ((unused));

	frame = &zones.info[znum].frames[pfn - zones.info[znum].base];

	ASSERT(!frame->buddy_order);

	count_t i;

	for (i = 0; i < cframes; i++) {

		zones.info[znum].busy_count++;

		zone_frame_free(&zones.info[znum],

		    pfn - zones.info[znum].base + i);

	}

}

/** Reduce allocated block to count of order 0 frames.

 *

 * The allocated block needs 2^order frames. Reduce all frames

 * in the block to order 0 and free the unneeded frames. This means that

 * when freeing the previously allocated block starting with frame_idx,

 * you have to free every frame.

 *

 * @param znum      Zone.

 * @param frame_idx Index the first frame of the block.

 * @param count     Allocated frames in block.

 *

 */

static void zone_reduce_region(count_t znum, pfn_t frame_idx, count_t count)

{

	ASSERT(zone_flags_available(zones.info[znum].flags));

	ASSERT(frame_idx + count < zones.info[znum].count);

	uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;

	ASSERT((count_t) (1 << order) >= count);

	/* Reduce all blocks to order 0 */

	count_t i;

	for (i = 0; i < (count_t) (1 << order); i++) {

		frame_t *frame = &zones.info[znum].frames[i + frame_idx];

		frame->buddy_order = 0;

		if (!frame->refcount)

			frame->refcount = 1;

		ASSERT(frame->refcount == 1);

	}

	/* Free unneeded frames */

	for (i = count; i < (count_t) (1 << order); i++)

		zone_frame_free(&zones.info[znum], i + frame_idx);

}

/** 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 :-/

 *

 * The function uses

 *

 */

bool zone_merge(count_t z1, count_t z2)

{

	ipl_t ipl = interrupts_disable();

	spinlock_lock(&zones.lock);

	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)

	    || (!zone_flags_available(zones.info[z1].flags))

	    || (!zone_flags_available(zones.info[z2].flags))

	    || (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));

	uint8_t order;

	if (cframes == 1)

		order = 0;

	else

		order = fnzb(cframes - 1) + 1;

	/* Allocate merged zone data inside one of the zones */

	pfn_t pfn;

	if (zone_can_alloc(&zones.info[z1], order)) {

		pfn = zones.info[z1].base + zone_frame_alloc(&zones.info[z1], order);

	} else if (zone_can_alloc(&zones.info[z2], order)) {

		pfn = zones.info[z2].base + zone_frame_alloc(&zones.info[z2], order);

	} else {

		ret = false;

		goto errout;

	}

	/* Preserve original data from z1 */

	zone_t old_z1 = zones.info[z1];

	old_z1.buddy_system->data = (void *) &old_z1;

	/* Do zone merging */

	buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(pfn));

	zone_merge_internal(z1, z2, &old_z1, buddy);

	/* Free unneeded config frames */

	zone_reduce_region(z1, pfn - zones.info[z1].base, cframes);

	/* 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 */

	count_t i;

	for (i = z2 + 1; i < zones.count; i++) {

		zones.info[i - 1] = zones.info[i];

		zones.info[i - 1].buddy_system->data =

		    (void *) &zones.info[i - 1];

	}

	zones.count--;

errout:

	spinlock_unlock(&zones.lock);

	interrupts_restore(ipl);

	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)

{

	count_t i = 0;

	while (i < zones.count) {

		if (!zone_merge(i, i + 1))

			i++;

	}

}

/** Create new frame zone.

 *

 * @param zone  Zone to construct.

 * @param buddy Address of buddy system configuration information.

 * @param start Physical address of the first frame within the zone.

 * @param count Count of frames in zone.

 * @param flags Zone flags.

 *

 * @return Initialized zone.

 *

 */

static void zone_construct(zone_t *zone, buddy_system_t *buddy, pfn_t start, count_t count, zone_flags_t flags)

{

	zone->base = start;

	zone->count = count;

	zone->flags = flags;

	zone->free_count = count;

	zone->busy_count = 0;

	zone->buddy_system = buddy;

	if (zone_flags_available(flags)) {

		/*

		 * Compute order for buddy system and initialize

		 */

		uint8_t order = fnzb(count);

		buddy_system_create(zone->buddy_system, order,

		    &zone_buddy_system_operations, (void *) zone);

		/* Allocate frames _after_ the confframe */

		/* Check sizes */

		zone->frames = (frame_t *) ((uint8_t *) zone->buddy_system +

		    buddy_conf_size(order));

		count_t i;

		for (i = 0; i < count; i++)

			frame_initialize(&zone->frames[i]);

		/* Stuffing frames */

		for (i = 0; i < count; i++) {

			zone->frames[i].refcount = 0;

			buddy_system_free(zone->buddy_system, &zone->frames[i].buddy_link);

		}

	} else

		zone->frames = NULL;

}

/** Compute configuration data size for zone.

 *

 * @param count Size of zone in frames.

 *

 * @return Size of zone configuration info (in bytes).

 *

 */

uintptr_t zone_conf_size(count_t count)

{

	return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count)));

}

/** 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.

 *

 */

count_t zone_create(pfn_t start, count_t count, pfn_t confframe, zone_flags_t flags)

{

	ipl_t ipl = interrupts_disable();

	spinlock_lock(&zones.lock);

	if (zone_flags_available(flags)) {  /* 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 != NULL);

		/* If confframe is supposed to be inside our zone, then make sure

		 * it does not span kernel & init

		 */

		count_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;

				count_t i;

				for (i = 0; i < init.cnt; i++)

					if (overlaps(addr, PFN2ADDR(confcount),

					    KA2PA(init.tasks[i].addr),

					    init.tasks[i].size)) {

						overlap = true;

						break;

					}

				if (overlap)

					continue;

				break;

			}

			if (confframe >= start + count)

				panic("Cannot find configuration data for zone.");

		}

		count_t znum = zones_insert_zone(start, count);

		if (znum == (count_t) -1) {

			spinlock_unlock(&zones.lock);

			interrupts_restore(ipl);

			return (count_t) -1;

		}

		buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(confframe));

		zone_construct(&zones.info[znum], buddy, start, count, flags);

		/* If confdata in zone, mark as unavailable */

		if ((confframe >= start) && (confframe < start + count)) {

			count_t i;

			for (i = confframe; i < confframe + confcount; i++)

				zone_mark_unavailable(&zones.info[znum],

				    i - zones.info[znum].base);

		}

		spinlock_unlock(&zones.lock);

		interrupts_restore(ipl);

		return znum;

	}

	/* Non-available zone */

	count_t znum = zones_insert_zone(start, count);

	if (znum == (count_t) -1) {

		spinlock_unlock(&zones.lock);

		interrupts_restore(ipl);

		return (count_t) -1;

	}

	zone_construct(&zones.info[znum], NULL, start, count, flags);

	spinlock_unlock(&zones.lock);

	interrupts_restore(ipl);

	return znum;

}

/*******************/

/* Frame functions */

/*******************/

/** Set parent of frame. */

void frame_set_parent(pfn_t pfn, void *data, count_t hint)

{

	ipl_t ipl = interrupts_disable();

	spinlock_lock(&zones.lock);

	count_t znum = find_zone(pfn, 1, hint);

	ASSERT(znum != (count_t) -1);

	zone_get_frame(&zones.info[znum],

	    pfn - zones.info[znum].base)->parent = data;

	spinlock_unlock(&zones.lock);

	interrupts_restore(ipl);

}

void *frame_get_parent(pfn_t pfn, count_t hint)

{

	ipl_t ipl = interrupts_disable();

	spinlock_lock(&zones.lock);

	count_t znum = find_zone(pfn, 1, hint);

	ASSERT(znum != (count_t) -1);

	void *res = zone_get_frame(&zones.info[znum],

	    pfn - zones.info[znum].base)->parent;

	spinlock_unlock(&zones.lock);

	interrupts_restore(ipl);

	return res;

}

/** Allocate power-of-two frames of physical memory.

 *

 * @param order Allocate exactly 2^order frames.

 * @param flags Flags for host zone selection and address processing.

 * @param pzone Preferred zone.

 *

 * @return Physical address of the allocated frame.

 *

 */

void *frame_alloc_generic(uint8_t order, frame_flags_t flags, count_t *pzone)

{

	count_t size = ((count_t) 1) << order;

	ipl_t ipl;

	count_t hint = pzone ? (*pzone) : 0;

loop:

	ipl = interrupts_disable();

	spinlock_lock(&zones.lock);

	/*

	 * First, find suitable frame zone.

	 */

	count_t znum = find_free_zone(order,

	    FRAME_TO_ZONE_FLAGS(flags), hint);

	/* If no memory, reclaim some slab memory,

	   if it does not help, reclaim all */

	if ((znum == (count_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {

		count_t freed = slab_reclaim(0);

		if (freed > 0)

			znum = find_free_zone(order,

			    FRAME_TO_ZONE_FLAGS(flags), hint);

		if (znum == (count_t) -1) {

			freed = slab_reclaim(SLAB_RECLAIM_ALL);

			if (freed > 0)

				znum = find_free_zone(order,

				    FRAME_TO_ZONE_FLAGS(flags), hint);

		}

	}

	if (znum == (count_t) -1) {

		if (flags & FRAME_ATOMIC) {

			spinlock_unlock(&zones.lock);

			interrupts_restore(ipl);

			return NULL;

		}

#ifdef CONFIG_DEBUG

		count_t avail = total_frames_free();

#endif

		spinlock_unlock(&zones.lock);

		interrupts_restore(ipl);

		/*

		 * Sleep until some frames are available again.

		 */

#ifdef CONFIG_DEBUG

		printf("Thread %" PRIu64 " waiting for %" PRIc " frames, "

		    "%" PRIc " available.\n", THREAD->tid, size, avail);

#endif

		mutex_lock(&mem_avail_mtx);

		if (mem_avail_req > 0)

			mem_avail_req = min(mem_avail_req, size);

		else

			mem_avail_req = size;

		count_t gen = mem_avail_gen;

		while (gen == mem_avail_gen)

			condvar_wait(&mem_avail_cv, &mem_avail_mtx);

		mutex_unlock(&mem_avail_mtx);

#ifdef CONFIG_DEBUG

		printf("Thread %" PRIu64 " woken up.\n", THREAD->tid);

#endif

		goto loop;

	}

	pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)

	    + zones.info[znum].base;

	spinlock_unlock(&zones.lock);