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

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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/frame.c @ 3370 – Rev 1981