WebSVN – HelenOS – Blame – /trunk/kernel/generic/src/mm/frame.c

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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/frame.c – Rev 3972