Index: uspace/srv/fs/fat/fat.h
===================================================================
--- uspace/srv/fs/fat/fat.h	(revision 78a1b7b61fd9804bd27c95cb57dd954ccd3becff)
+++ uspace/srv/fs/fat/fat.h	(revision add5835771e75bf78f021398e9c2da7a0311ca54)
@@ -181,4 +181,5 @@
 	link_t		uih_link;
 
+	futex_t		lock;
 	dev_handle_t	dev_handle;
 	fs_index_t	index;
@@ -198,4 +199,5 @@
 /** FAT in-core node. */
 typedef struct fat_node {
+	futex_t			lock;
 	fat_node_type_t		type;
 	fat_idx_t		*idx;
Index: uspace/srv/fs/fat/fat_idx.c
===================================================================
--- uspace/srv/fs/fat/fat_idx.c	(revision 78a1b7b61fd9804bd27c95cb57dd954ccd3becff)
+++ uspace/srv/fs/fat/fat_idx.c	(revision add5835771e75bf78f021398e9c2da7a0311ca54)
@@ -75,13 +75,5 @@
 static LIST_INITIALIZE(unused_head);
 
-/** Futex protecting the up_hash and ui_hash.
- *
- * The locking strategy assumes that there will be at most one fibril for each
- * dev_handle.  Therefore it will be sufficient to hold the futex for shorter
- * times (i.e. only during hash table operations as opposed to holding it the
- * whole time between an unsuccessful find and the following insert). Should the
- * assumption break, the locking strategy for this futex will have to be
- * reconsidered.
- */
+/** Futex protecting the up_hash and ui_hash. */
 static futex_t used_futex = FUTEX_INITIALIZER; 
 
@@ -353,5 +345,4 @@
 	futex_down(&used_futex);
 	l = hash_table_find(&up_hash, pkey);
-	futex_up(&used_futex);
 	if (l) {
 		fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
@@ -359,8 +350,10 @@
 		fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
 		if (!fidx) {
+			futex_up(&used_futex);
 			return NULL;
 		}
 		if (!fat_idx_alloc(dev_handle, &fidx->index)) {
 			free(fidx);
+			futex_up(&used_futex);
 			return NULL;
 		}
@@ -373,4 +366,5 @@
 		link_initialize(&fidx->uph_link);
 		link_initialize(&fidx->uih_link);
+		futex_initialize(&fidx->lock, 1);
 		fidx->dev_handle = dev_handle;
 		fidx->pfc = pfc;
@@ -378,9 +372,9 @@
 		fidx->nodep = NULL;
 
-		futex_down(&used_futex);
 		hash_table_insert(&up_hash, pkey, &fidx->uph_link);
 		hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
-		futex_up(&used_futex);
-	}
+	}
+	futex_down(&fidx->lock);
+	futex_up(&used_futex);
 
 	return fidx;
@@ -399,8 +393,9 @@
 	futex_down(&used_futex);
 	l = hash_table_find(&ui_hash, ikey);
-	futex_up(&used_futex);
 	if (l) {
 		fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
-	}
+		futex_down(&fidx->lock);
+	}
+	futex_up(&used_futex);
 
 	return fidx;
Index: uspace/srv/fs/fat/fat_ops.c
===================================================================
--- uspace/srv/fs/fat/fat_ops.c	(revision 78a1b7b61fd9804bd27c95cb57dd954ccd3becff)
+++ uspace/srv/fs/fat/fat_ops.c	(revision add5835771e75bf78f021398e9c2da7a0311ca54)
@@ -51,6 +51,9 @@
 #define BS_BLOCK		0
 
-/** List of free FAT nodes that still contain valid data. */
-LIST_INITIALIZE(ffn_head);
+/** Futex protecting the list of cached free FAT nodes. */
+static futex_t ffn_futex = FUTEX_INITIALIZER;
+
+/** List of cached free FAT nodes. */
+static LIST_INITIALIZE(ffn_head);
 
 #define FAT_NAME_LEN		8
@@ -180,4 +183,5 @@
 static void fat_node_initialize(fat_node_t *node)
 {
+	futex_initialize(&node->lock, 1);
 	node->idx = NULL;
 	node->type = 0;
@@ -237,8 +241,10 @@
 }
 
-/** Instantiate a FAT in-core node. */
-static void *fat_node_get(dev_handle_t dev_handle, fs_index_t index)
-{
-	fat_idx_t *idx;
+/** Internal version of fat_node_get().
+ *
+ * @param idxp		Locked index structure.
+ */
+static void *fat_node_get_core(fat_idx_t *idxp)
+{
 	block_t *b;
 	fat_dentry_t *d;
@@ -247,16 +253,14 @@
 	unsigned dps;
 
-	idx = fat_idx_get_by_index(dev_handle, index);
-	if (!idx)
-		return NULL;
-
-	if (idx->nodep) {
+	if (idxp->nodep) {
 		/*
 		 * We are lucky.
 		 * The node is already instantiated in memory.
 		 */
-		if (!idx->nodep->refcnt++)
+		futex_down(&idxp->nodep->lock);
+		if (!idxp->nodep->refcnt++)
 			list_remove(&nodep->ffn_link);
-		return idx->nodep;
+		futex_up(&idxp->nodep->lock);
+		return idxp->nodep;
 	}
 
@@ -265,15 +269,29 @@
 	 */
 	
-	assert(idx->pfc);
-
+	assert(idxp->pfc);
+
+	futex_down(&ffn_futex);
 	if (!list_empty(&ffn_head)) {
-		/* Try to use a cached unused node structure. */
+		/* Try to use a cached free node structure. */
+		fat_idx_t *idxp_tmp;
 		nodep = list_get_instance(ffn_head.next, fat_node_t, ffn_link);
+		if (futex_trydown(&nodep->lock) == ESYNCH_WOULD_BLOCK)
+			goto skip_cache;
+		idxp_tmp = nodep->idx;
+		if (futex_trydown(&idxp_tmp->lock) == ESYNCH_WOULD_BLOCK) {
+			futex_up(&nodep->lock);
+			goto skip_cache;
+		}
+		list_remove(&nodep->ffn_link);
+		futex_up(&ffn_futex);
 		if (nodep->dirty)
 			fat_node_sync(nodep);
-		list_remove(&nodep->ffn_link);
-		nodep->idx->nodep = NULL;
+		idxp_tmp->nodep = NULL;
+		futex_up(&nodep->lock);
+		futex_up(&idxp_tmp->lock);
 	} else {
+skip_cache:
 		/* Try to allocate a new node structure. */
+		futex_up(&ffn_futex);
 		nodep = (fat_node_t *)malloc(sizeof(fat_node_t));
 		if (!nodep)
@@ -282,13 +300,13 @@
 	fat_node_initialize(nodep);
 
-	bps = fat_bps_get(dev_handle);
+	bps = fat_bps_get(idxp->dev_handle);
 	dps = bps / sizeof(fat_dentry_t);
 
 	/* Read the block that contains the dentry of interest. */
-	b = _fat_block_get(dev_handle, idx->pfc,
-	    (idx->pdi * sizeof(fat_dentry_t)) / bps);
+	b = _fat_block_get(idxp->dev_handle, idxp->pfc,
+	    (idxp->pdi * sizeof(fat_dentry_t)) / bps);
 	assert(b);
 
-	d = ((fat_dentry_t *)b->data) + (idx->pdi % dps);
+	d = ((fat_dentry_t *)b->data) + (idxp->pdi % dps);
 	if (d->attr & FAT_ATTR_SUBDIR) {
 		/* 
@@ -309,17 +327,36 @@
 
 	/* Link the idx structure with the node structure. */
-	nodep->idx = idx;
-	idx->nodep = nodep;
+	nodep->idx = idxp;
+	idxp->nodep = nodep;
 
 	return nodep;
 }
 
+/** Instantiate a FAT in-core node. */
+static void *fat_node_get(dev_handle_t dev_handle, fs_index_t index)
+{
+	void *node;
+	fat_idx_t *idxp;
+
+	idxp = fat_idx_get_by_index(dev_handle, index);
+	if (!idxp)
+		return NULL;
+	/* idxp->lock held */
+	node = fat_node_get_core(idxp);
+	futex_up(&idxp->lock);
+	return node;
+}
+
 static void fat_node_put(void *node)
 {
 	fat_node_t *nodep = (fat_node_t *)node;
 
+	futex_down(&nodep->lock);
 	if (!--nodep->refcnt) {
+		futex_down(&ffn_futex);
 		list_append(&nodep->ffn_link, &ffn_head);
-	}
+		futex_up(&ffn_futex);
+	}
+	futex_up(&nodep->lock);
 }
 
@@ -380,4 +417,5 @@
 			if (strcmp(name, component) == 0) {
 				/* hit */
+				void *node;
 				fat_idx_t *idx = fat_idx_get_by_pos(
 				    parentp->idx->dev_handle, parentp->firstc,
@@ -391,6 +429,6 @@
 					return NULL;
 				}
-				void *node = fat_node_get(idx->dev_handle,
-				    idx->index);
+				node = fat_node_get_core(idx);
+				futex_up(&idx->lock);
 				block_put(b);
 				return node;
@@ -433,4 +471,5 @@
 		return false;
 
+	futex_down(&nodep->idx->lock);
 	bps = fat_bps_get(nodep->idx->dev_handle);
 	dps = bps / sizeof(fat_dentry_t);
@@ -453,11 +492,14 @@
 			case FAT_DENTRY_LAST:
 				block_put(b);
+				futex_up(&nodep->idx->lock);
 				return false;
 			default:
 			case FAT_DENTRY_VALID:
 				block_put(b);
+				futex_up(&nodep->idx->lock);
 				return true;
 			}
 			block_put(b);
+			futex_up(&nodep->idx->lock);
 			return true;
 		}
@@ -465,4 +507,5 @@
 	}
 
+	futex_up(&nodep->idx->lock);
 	return false;
 }