WebSVN – HelenOS – Blame – /trunk/uspace/srv/fs/fat/fat_idx.c

Rev	Author	Line No.	Line
2876	jermar	1	/*
		2	* Copyright (c) 2008 Jakub Jermar
		3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	/** @addtogroup fs
		30	* @{
		31	*/
		32
		33	/**
		34	* @file fat_idx.c
		35	* @brief Layer for translating FAT entities to VFS node indices.
		36	*/
		37
		38	#include "fat.h"
2881	jermar	39	#include "../../vfs/vfs.h"
2876	jermar	40	#include <errno.h>
		41	#include <string.h>
		42	#include <libadt/hash_table.h>
		43	#include <libadt/list.h>
		44	#include <assert.h>
		45	#include <futex.h>
		46
2881	jermar	47	/** Each instance of this type describes one interval of freed VFS indices. */
		48	typedef struct {
		49	link_t link;
		50	fs_index_t first;
		51	fs_index_t last;
		52	} freed_t;
		53
		54	/**
		55	* Each instance of this type describes state of all VFS indices that
		56	* are currently unused.
		57	*/
		58	typedef struct {
		59	link_t link;
		60	dev_handle_t dev_handle;
		61
		62	/** Next unassigned index. */
		63	fs_index_t next;
		64	/** Number of remaining unassigned indices. */
		65	uint64_t remaining;
		66
		67	/** Sorted list of intervals of freed indices. */
		68	link_t freed_head;
		69	} unused_t;
		70
		71	static LIST_INITIALIZE(unused_head);
		72
		73	/** Allocate a VFS index which is not currently in use. */
		74	static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
2876	jermar	75	{
2881	jermar	76	link_t *l;
		77	unused_t *u;
		78
		79	assert(index);
		80	for (l = unused_head.next; l != &unused_head; l = l->next) {
		81	u = list_get_instance(l, unused_t, link);
		82	if (u->dev_handle == dev_handle)
		83	goto hit;
		84	}
		85
		86	/* dev_handle not found */
		87	return false;
		88
		89	hit:
		90	if (list_empty(&u->freed_head)) {
		91	if (u->remaining) {
		92	/*
		93	* There are no freed indices, allocate one directly
		94	* from the counter.
		95	*/
		96	*index = u->next++;
		97	--u->remaining;
		98	return true;
		99	}
		100	} else {
		101	/* There are some freed indices which we can reuse. */
		102	freed_t *f = list_get_instance(u->freed_head.next, freed_t,
		103	link);
		104	*index = f->first;
		105	if (f->first++ == f->last) {
		106	/* Destroy the interval. */
		107	list_remove(&f->link);
		108	free(f);
		109	}
		110	return true;
		111	}
		112	/*
		113	* We ran out of indices, which is extremely unlikely with FAT16, but
		114	* theoretically still possible (e.g. too many open unlinked nodes or
		115	* too many zero-sized nodes).
		116	*/
		117	return false;
		118	}
		119
		120	/** If possible, merge two intervals of freed indices. */
		121	static void try_merge_intervals(link_t l, link_t r, link_t *cur)
		122	{
		123	freed_t *fl = list_get_instance(l, freed_t, link);
		124	freed_t *fr = list_get_instance(r, freed_t, link);
		125
		126	if (fl->last + 1 == fr->first) {
		127	if (cur == l) {
		128	fl->last = fr->last;
		129	list_remove(r);
		130	free(r);
		131	} else {
		132	fr->first = fl->first;
		133	list_remove(l);
		134	free(l);
		135	}
		136	}
		137	}
		138
		139	/** Free a VFS index, which is no longer in use. */
		140	static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
		141	{
		142	link_t *l;
		143	unused_t *u;
		144
		145	for (l = unused_head.next; l != &unused_head; l = l->next) {
		146	u = list_get_instance(l, unused_t, link);
		147	if (u->dev_handle == dev_handle)
		148	goto hit;
		149	}
		150
		151	/* should not happen */
		152	assert(0);
		153
		154	hit:
		155	if (u->next == index + 1) {
		156	/* The index can be returned directly to the counter. */
		157	u->next--;
		158	u->remaining++;
		159	return;
		160	} else {
		161	/*
		162	* The index must be returned either to an existing freed
		163	* interval or a new interval must be created.
		164	*/
		165	link_t *lnk;
		166	freed_t *n;
		167	for (lnk = u->freed_head.next; lnk != &u->freed_head;
		168	lnk = lnk->next) {
		169	freed_t *f = list_get_instance(lnk, freed_t, link);
		170	if (f->first == index + 1) {
		171	f->first--;
		172	if (lnk->prev != &u->freed_head)
		173	try_merge_intervals(lnk->prev, lnk,
		174	lnk);
		175	return;
		176	}
		177	if (f->last == index - 1) {
		178	f->last++;
		179	if (lnk->next != &u->freed_head)
		180	try_merge_intervals(lnk, lnk->next,
		181	lnk);
		182	return;
		183	}
		184	if (index > f->first) {
		185	n = malloc(sizeof(freed_t));
		186	/* TODO: sleep until allocation succeeds */
		187	assert(n);
		188	link_initialize(&n->link);
		189	n->first = index;
		190	n->last = index;
		191	list_insert_before(&n->link, lnk);
		192	return;
		193	}
		194
		195	}
		196	/* The index will form the last interval. */
		197	n = malloc(sizeof(freed_t));
		198	/* TODO: sleep until allocation succeeds */
		199	assert(n);
		200	link_initialize(&n->link);
		201	n->first = index;
		202	n->last = index;
		203	list_append(&n->link, &u->freed_head);
		204	}
		205	}
		206
		207	fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
		208	{
2876	jermar	209	return NULL; /* TODO */
		210	}

Subversion Repositories HelenOS

(root)/trunk/uspace/srv/fs/fat/fat_idx.c @ 4753 – Rev 2881