Index: uspace/srv/fs/fat/fat.h
===================================================================
--- uspace/srv/fs/fat/fat.h	(revision f5209056e979fbdfe341077cedd598173ff0370c)
+++ uspace/srv/fs/fat/fat.h	(revision 5a32409902b93bb03691e68b1253223ac54eb670)
@@ -215,5 +215,5 @@
 extern void fat_lookup(ipc_callid_t, ipc_call_t *);
 
-extern fat_idx_t *fat_idx_map(fat_cluster_t, unsigned);
+extern fat_idx_t *fat_idx_map(dev_handle_t, fat_cluster_t, unsigned);
 
 #endif
Index: uspace/srv/fs/fat/fat_idx.c
===================================================================
--- uspace/srv/fs/fat/fat_idx.c	(revision f5209056e979fbdfe341077cedd598173ff0370c)
+++ uspace/srv/fs/fat/fat_idx.c	(revision 5a32409902b93bb03691e68b1253223ac54eb670)
@@ -37,4 +37,5 @@
 
 #include "fat.h"
+#include "../../vfs/vfs.h"
 #include <errno.h>
 #include <string.h>
@@ -44,5 +45,165 @@
 #include <futex.h>
 
-fat_idx_t *fat_idx_map(fat_cluster_t pfc, unsigned pdi)
+/** Each instance of this type describes one interval of freed VFS indices. */
+typedef struct {
+	link_t		link;
+	fs_index_t	first;
+	fs_index_t	last;
+} freed_t;
+
+/**
+ * Each instance of this type describes state of all VFS indices that
+ * are currently unused.
+ */
+typedef struct {
+	link_t		link;
+	dev_handle_t	dev_handle;
+
+	/** Next unassigned index. */
+	fs_index_t	next;
+	/** Number of remaining unassigned indices. */
+	uint64_t	remaining;
+
+	/** Sorted list of intervals of freed indices. */
+	link_t		freed_head;
+} unused_t;
+
+static LIST_INITIALIZE(unused_head);
+
+/** Allocate a VFS index which is not currently in use. */
+static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
+{
+	link_t *l;
+	unused_t *u;
+	
+	assert(index);
+	for (l = unused_head.next; l != &unused_head; l = l->next) {
+		u = list_get_instance(l, unused_t, link);
+		if (u->dev_handle == dev_handle) 
+			goto hit;
+	}
+
+	/* dev_handle not found */
+	return false;	
+
+hit:
+	if (list_empty(&u->freed_head)) {
+		if (u->remaining) { 
+			/*
+			 * There are no freed indices, allocate one directly
+			 * from the counter.
+			 */
+			*index = u->next++;
+			--u->remaining;
+			return true;
+		}
+	} else {
+		/* There are some freed indices which we can reuse. */
+		freed_t *f = list_get_instance(u->freed_head.next, freed_t,
+		    link);
+		*index = f->first;
+		if (f->first++ == f->last) {
+			/* Destroy the interval. */
+			list_remove(&f->link);
+			free(f);
+		}
+		return true;
+	}
+	/*
+	 * We ran out of indices, which is extremely unlikely with FAT16, but
+	 * theoretically still possible (e.g. too many open unlinked nodes or
+	 * too many zero-sized nodes).
+	 */
+	return false;
+}
+
+/** If possible, merge two intervals of freed indices. */
+static void try_merge_intervals(link_t *l, link_t *r, link_t *cur)
+{
+	freed_t *fl = list_get_instance(l, freed_t, link);
+	freed_t *fr = list_get_instance(r, freed_t, link);
+
+	if (fl->last + 1 == fr->first) {
+		if (cur == l) {
+			fl->last = fr->last;
+			list_remove(r);
+			free(r);
+		} else {
+			fr->first = fl->first;
+			list_remove(l);
+			free(l);
+		}
+	}
+}
+
+/** Free a VFS index, which is no longer in use. */
+static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
+{
+	link_t *l;
+	unused_t *u;
+
+	for (l = unused_head.next; l != &unused_head; l = l->next) {
+		u = list_get_instance(l, unused_t, link);
+		if (u->dev_handle == dev_handle)
+			goto hit;
+	}
+
+	/* should not happen */
+	assert(0);
+
+hit:
+	if (u->next == index + 1) {
+		/* The index can be returned directly to the counter. */
+		u->next--;
+		u->remaining++;
+		return;
+	} else {
+		/*
+		 * The index must be returned either to an existing freed
+		 * interval or a new interval must be created.
+		 */
+		link_t *lnk;
+		freed_t *n;
+		for (lnk = u->freed_head.next; lnk != &u->freed_head;
+		    lnk = lnk->next) {
+			freed_t *f = list_get_instance(lnk, freed_t, link);
+			if (f->first == index + 1) {
+				f->first--;
+				if (lnk->prev != &u->freed_head)
+					try_merge_intervals(lnk->prev, lnk,
+					    lnk);
+				return;
+			}
+			if (f->last == index - 1) {
+				f->last++;
+				if (lnk->next != &u->freed_head)
+					try_merge_intervals(lnk, lnk->next,
+					    lnk);
+				return;
+			}
+			if (index > f->first) {
+				n = malloc(sizeof(freed_t));
+				/* TODO: sleep until allocation succeeds */
+				assert(n);
+				link_initialize(&n->link);
+				n->first = index;
+				n->last = index;
+				list_insert_before(&n->link, lnk);
+				return;
+			}
+
+		}
+		/* The index will form the last interval. */
+		n = malloc(sizeof(freed_t));
+		/* TODO: sleep until allocation succeeds */
+		assert(n);
+		link_initialize(&n->link);
+		n->first = index;
+		n->last = index;
+		list_append(&n->link, &u->freed_head);
+	}
+}
+
+fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
 {
 	return NULL;	/* TODO */
Index: uspace/srv/fs/fat/fat_ops.c
===================================================================
--- uspace/srv/fs/fat/fat_ops.c	(revision f5209056e979fbdfe341077cedd598173ff0370c)
+++ uspace/srv/fs/fat/fat_ops.c	(revision 5a32409902b93bb03691e68b1253223ac54eb670)
@@ -309,5 +309,6 @@
 			if (strcmp(name, component) == 0) {
 				/* hit */
-				fat_idx_t *idx = fat_idx_map(parentp->firstc,
+				fat_idx_t *idx = fat_idx_map(
+				    parentp->idx->dev_handle, parentp->firstc,
 				    i * dps + j);
 				void *node = fat_node_get(idx->dev_handle,
