Index: kernel/generic/include/adt/odict.h
===================================================================
--- kernel/generic/include/adt/odict.h	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/include/adt/odict.h	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -45,4 +45,5 @@
 
 extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t);
+extern void odict_finalize(odict_t *);
 extern void odlink_initialize(odlink_t *);
 extern void odict_insert(odlink_t *, odict_t *, odlink_t *);
Index: kernel/generic/include/mm/as.h
===================================================================
--- kernel/generic/include/mm/as.h	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/include/mm/as.h	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -46,4 +46,5 @@
 #include <adt/list.h>
 #include <adt/btree.h>
+#include <adt/odict.h>
 #include <lib/elf.h>
 #include <arch.h>
@@ -115,6 +116,9 @@
 	mutex_t lock;
 
-	/** B+tree of address space areas. */
-	btree_t as_area_btree;
+	/** Address space areas in this address space by base address.
+	 *
+	 * Members are of type as_area_t.
+	 */
+	odict_t as_areas;
 
 	/** Non-generic content. */
@@ -204,4 +208,7 @@
 	as_t *as;
 
+	/** Link to @c as->as_areas */
+	odlink_t las_areas;
+
 	/** Memory flags. */
 	unsigned int flags;
@@ -273,4 +280,6 @@
     uintptr_t *, uintptr_t);
 extern errno_t as_area_change_flags(as_t *, unsigned int, uintptr_t);
+extern as_area_t *as_area_first(as_t *);
+extern as_area_t *as_area_next(as_area_t *);
 
 extern unsigned int as_area_get_flags(as_area_t *);
Index: kernel/generic/src/adt/odict.c
===================================================================
--- kernel/generic/src/adt/odict.c	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/src/adt/odict.c	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -204,4 +204,13 @@
 	odict->getkey = getkey;
 	odict->cmp = cmp;
+}
+
+/** Finalize ordered dictionary.
+ *
+ * @param odict Ordered dictionary (must be empty)
+ */
+void odict_finalize(odict_t *odict)
+{
+	assert(odict->root == NULL);
 }
 
Index: kernel/generic/src/mm/as.c
===================================================================
--- kernel/generic/src/mm/as.c	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/src/mm/as.c	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -1,4 +1,5 @@
 /*
  * Copyright (c) 2010 Jakub Jermar
+ * Copyright (c) 2018 Jiri Svoboda
  * All rights reserved.
  *
@@ -111,4 +112,7 @@
 as_t *AS_KERNEL = NULL;
 
+static void *as_areas_getkey(odlink_t *);
+static int as_areas_cmp(void *, void *);
+
 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags)
 {
@@ -150,5 +154,5 @@
 	(void) as_create_arch(as, 0);
 
-	btree_create(&as->as_area_btree);
+	odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp);
 
 	if (flags & FLAG_AS_KERNEL)
@@ -224,20 +228,18 @@
 	/*
 	 * Destroy address space areas of the address space.
-	 * The B+tree must be walked carefully because it is
-	 * also being destroyed.
-	 */
-	bool cond = true;
-	while (cond) {
-		assert(!list_empty(&as->as_area_btree.leaf_list));
-
-		btree_node_t *node =
-		    list_get_instance(list_first(&as->as_area_btree.leaf_list),
-		    btree_node_t, leaf_link);
-
-		if ((cond = node->keys))
-			as_area_destroy(as, node->key[0]);
-	}
-
-	btree_destroy(&as->as_area_btree);
+	 * Need to start from the beginning each time since we are destroying
+	 * the areas.
+	 */
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		/*
+		 * XXX We already have as_area_t, but as_area_destroy will
+		 * have to search for it. This could be made faster.
+		 */
+		as_area_destroy(as, area->base);
+		area = as_area_first(as);
+	}
+
+	odict_finalize(&as->as_areas);
 
 #ifdef AS_PAGE_TABLE
@@ -277,4 +279,72 @@
 }
 
+/** Return first address space area.
+ *
+ * @param as Address space
+ * @return First area in @a as (i.e. area with the lowest base address)
+ *         or @c NULL if there is none
+ */
+as_area_t *as_area_first(as_t *as)
+{
+	odlink_t *odlink = odict_first(&as->as_areas);
+	if (odlink == NULL)
+		return NULL;
+
+	return odict_get_instance(odlink, as_area_t, las_areas);
+}
+
+/** Return next address space area.
+ *
+ * @param cur Current area
+ * @return Next area in the same address space or @c NULL if @a cur is the
+ *         last area.
+ */
+as_area_t *as_area_next(as_area_t *cur)
+{
+	odlink_t *odlink = odict_next(&cur->las_areas, &cur->as->as_areas);
+	if (odlink == NULL)
+		return NULL;
+
+	return odict_get_instance(odlink, as_area_t, las_areas);
+}
+
+/** Determine if area with specified parameters would conflict with
+ * a specific existing address space area.
+ *
+ * @param addr    Starting virtual address of the area being tested.
+ * @param count   Number of pages in the area being tested.
+ * @param guarded True if the area being tested is protected by guard pages.
+ * @param area    Area against which we are testing.
+ *
+ * @return True if the two areas conflict, false otherwise.
+ */
+NO_TRACE static bool area_is_conflicting(uintptr_t addr,
+    size_t count, bool guarded, as_area_t *area)
+{
+	assert((addr % PAGE_SIZE) == 0);
+
+	size_t gsize = P2SZ(count);
+	size_t agsize = P2SZ(area->pages);
+
+	/*
+	 * A guarded area has one guard page before, one page after.
+	 * What we do here is: if either area is guarded, we add
+	 * PAGE_SIZE to the size of both areas. That guarantees
+	 * they will be spaced at least one page apart.
+	 */
+	if (guarded || (area->flags & AS_AREA_GUARD) != 0) {
+		/* Add guard page size unless area is at the end of VA domain */
+		if (!overflows(addr, P2SZ(count)))
+			gsize += PAGE_SIZE;
+
+		/* Add guard page size unless area is at the end of VA domain */
+		if (!overflows(area->base, P2SZ(area->pages)))
+			agsize += PAGE_SIZE;
+	}
+
+	return overlaps(addr, gsize, area->base, agsize);
+
+}
+
 /** Check area conflicts with other areas.
  *
@@ -283,5 +353,6 @@
  * @param count   Number of pages in the area being tested.
  * @param guarded True if the area being tested is protected by guard pages.
- * @param avoid   Do not touch this area.
+ * @param avoid   Do not touch this area. I.e. this area is not considered
+ *                as presenting a conflict.
  *
  * @return True if there is no conflict, false otherwise.
@@ -308,44 +379,18 @@
 
 	/*
-	 * The leaf node is found in O(log n), where n is proportional to
-	 * the number of address space areas belonging to as.
-	 * The check for conflicts is then attempted on the rightmost
-	 * record in the left neighbour, the leftmost record in the right
-	 * neighbour and all records in the leaf node itself.
-	 */
-	btree_node_t *leaf;
-	as_area_t *area =
-	    (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf);
-	if (area) {
-		if (area != avoid)
-			return false;
-	}
-
-	/* First, check the two border cases. */
-	btree_node_t *node =
-	    btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
-	if (node) {
-		area = (as_area_t *) node->value[node->keys - 1];
+	 * To determine if we overlap with another area, we just need
+	 * to look at overlap with the last area with base address <=
+	 * to ours and on the first area with base address > than ours.
+	 *
+	 * First find last area with <= base address.
+	 */
+	odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL);
+	if (odlink != NULL) {
+		as_area_t *area = odict_get_instance(odlink, as_area_t,
+		    las_areas);
 
 		if (area != avoid) {
 			mutex_lock(&area->lock);
-
-			/*
-			 * If at least one of the two areas are protected
-			 * by the AS_AREA_GUARD flag then we must be sure
-			 * that they are separated by at least one unmapped
-			 * page.
-			 */
-			int const gp = (guarded ||
-			    (area->flags & AS_AREA_GUARD)) ? 1 : 0;
-
-			/*
-			 * The area comes from the left neighbour node, which
-			 * means that there already are some areas in the leaf
-			 * node, which in turn means that adding gp is safe and
-			 * will not cause an integer overflow.
-			 */
-			if (overlaps(addr, P2SZ(count), area->base,
-			    P2SZ(area->pages + gp))) {
+			if (area_is_conflicting(addr, count, guarded, area)) {
 				mutex_unlock(&area->lock);
 				return false;
@@ -354,28 +399,23 @@
 			mutex_unlock(&area->lock);
 		}
-	}
-
-	node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
-	if (node) {
-		area = (as_area_t *) node->value[0];
+
+		/* Next area */
+		odlink = odict_next(odlink, &as->as_areas);
+	}
+
+	/*
+	 * Next area, if any, is the first with base > than our base address.
+	 * If there was no area with <= base, we need to look at the first area.
+	 */
+	if (odlink == NULL)
+		odlink = odict_first(&as->as_areas);
+
+	if (odlink != NULL) {
+		as_area_t *area = odict_get_instance(odlink, as_area_t,
+		    las_areas);
 
 		if (area != avoid) {
-			int gp;
-
 			mutex_lock(&area->lock);
-
-			gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
-			if (gp && overflows(addr, P2SZ(count))) {
-				/*
-				 * Guard page not needed if the supposed area
-				 * is adjacent to the end of the address space.
-				 * We already know that the following test is
-				 * going to fail...
-				 */
-				gp--;
-			}
-
-			if (overlaps(addr, P2SZ(count + gp), area->base,
-			    P2SZ(area->pages))) {
+			if (area_is_conflicting(addr, count, guarded, area)) {
 				mutex_unlock(&area->lock);
 				return false;
@@ -384,36 +424,4 @@
 			mutex_unlock(&area->lock);
 		}
-	}
-
-	/* Second, check the leaf node. */
-	btree_key_t i;
-	for (i = 0; i < leaf->keys; i++) {
-		area = (as_area_t *) leaf->value[i];
-		int agp;
-		int gp;
-
-		if (area == avoid)
-			continue;
-
-		mutex_lock(&area->lock);
-
-		gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
-		agp = gp;
-
-		/*
-		 * Sanitize the two possible unsigned integer overflows.
-		 */
-		if (gp && overflows(addr, P2SZ(count)))
-			gp--;
-		if (agp && overflows(area->base, P2SZ(area->pages)))
-			agp--;
-
-		if (overlaps(addr, P2SZ(count + gp), area->base,
-		    P2SZ(area->pages + agp))) {
-			mutex_unlock(&area->lock);
-			return false;
-		}
-
-		mutex_unlock(&area->lock);
 	}
 
@@ -482,31 +490,28 @@
 
 	/* Eventually check the addresses behind each area */
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) {
-
-		for (btree_key_t i = 0; i < node->keys; i++) {
-			as_area_t *area = (as_area_t *) node->value[i];
-
-			mutex_lock(&area->lock);
-
-			addr =
-			    ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE);
-
-			if (guarded || area->flags & AS_AREA_GUARD) {
-				/*
-				 * We must leave an unmapped page
-				 * between the two areas.
-				 */
-				addr += P2SZ(1);
-			}
-
-			bool avail =
-			    ((addr >= bound) && (addr >= area->base) &&
-			    (check_area_conflicts(as, addr, pages, guarded, area)));
-
-			mutex_unlock(&area->lock);
-
-			if (avail)
-				return addr;
-		}
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		mutex_lock(&area->lock);
+
+		addr = area->base + P2SZ(area->pages);
+
+		if (guarded || area->flags & AS_AREA_GUARD) {
+			/*
+			 * We must leave an unmapped page
+			 * between the two areas.
+			 */
+			addr += P2SZ(1);
+		}
+
+		bool avail =
+		    ((addr >= bound) && (addr >= area->base) &&
+		    (check_area_conflicts(as, addr, pages, guarded, area)));
+
+		mutex_unlock(&area->lock);
+
+		if (avail)
+			return addr;
+
+		area = as_area_next(area);
 	}
 
@@ -623,4 +628,5 @@
 
 	area->as = as;
+	odlink_initialize(&area->las_areas);
 	area->flags = flags;
 	area->attributes = attrs;
@@ -680,6 +686,5 @@
 
 	btree_create(&area->used_space);
-	btree_insert(&as->as_area_btree, *base, (void *) area,
-	    NULL);
+	odict_insert(&area->las_areas, &as->as_areas, NULL);
 
 	mutex_unlock(&as->lock);
@@ -701,51 +706,17 @@
 	assert(mutex_locked(&as->lock));
 
-	btree_node_t *leaf;
-	as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va,
-	    &leaf);
-	if (area) {
-		/* va is the base address of an address space area */
-		mutex_lock(&area->lock);
+	odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL);
+	if (odlink == NULL)
+		return NULL;
+
+	as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
+	mutex_lock(&area->lock);
+
+	assert(area->base <= va);
+
+	if (va <= area->base + (P2SZ(area->pages) - 1))
 		return area;
-	}
-
-	/*
-	 * Search the leaf node and the rightmost record of its left neighbour
-	 * to find out whether this is a miss or va belongs to an address
-	 * space area found there.
-	 */
-
-	/* First, search the leaf node itself. */
-	btree_key_t i;
-
-	for (i = 0; i < leaf->keys; i++) {
-		area = (as_area_t *) leaf->value[i];
-
-		mutex_lock(&area->lock);
-
-		if ((area->base <= va) &&
-		    (va <= area->base + (P2SZ(area->pages) - 1)))
-			return area;
-
-		mutex_unlock(&area->lock);
-	}
-
-	/*
-	 * Second, locate the left neighbour and test its last record.
-	 * Because of its position in the B+tree, it must have base < va.
-	 */
-	btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree,
-	    leaf);
-	if (lnode) {
-		area = (as_area_t *) lnode->value[lnode->keys - 1];
-
-		mutex_lock(&area->lock);
-
-		if (va <= area->base + (P2SZ(area->pages) - 1))
-			return area;
-
-		mutex_unlock(&area->lock);
-	}
-
+
+	mutex_unlock(&area->lock);
 	return NULL;
 }
@@ -985,6 +956,4 @@
 		area->backend->destroy(area);
 
-	uintptr_t base = area->base;
-
 	page_table_lock(as, false);
 
@@ -1053,5 +1022,5 @@
 	 * Remove the empty area from address space.
 	 */
-	btree_remove(&as->as_area_btree, base, NULL);
+	odict_remove(&area->las_areas);
 
 	free(area);
@@ -1608,4 +1577,34 @@
 
 	return area_flags_to_page_flags(area->flags);
+}
+
+/** Get key function for the @c as_t.as_areas ordered dictionary.
+ *
+ * @param odlink Link
+ * @return Pointer to task ID cast as 'void *'
+ */
+static void *as_areas_getkey(odlink_t *odlink)
+{
+	as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
+	return (void *) &area->base;
+}
+
+/** Key comparison function for the @c as_t.as_areas ordered dictionary.
+ *
+ * @param a Pointer to area A base
+ * @param b Pointer to area B base
+ * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B
+ */
+static int as_areas_cmp(void *a, void *b)
+{
+	uintptr_t base_a = *(uintptr_t *)a;
+	uintptr_t base_b = *(uintptr_t *)b;
+
+	if (base_a < base_b)
+		return -1;
+	else if (base_a == base_b)
+		return 0;
+	else
+		return +1;
 }
 
@@ -2242,37 +2241,26 @@
 	mutex_lock(&as->lock);
 
-	/* First pass, count number of areas. */
-
-	size_t area_cnt = 0;
-
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
-	    node) {
-		area_cnt += node->keys;
-	}
+	/* Count number of areas. */
+	size_t area_cnt = odict_count(&as->as_areas);
 
 	size_t isize = area_cnt * sizeof(as_area_info_t);
 	as_area_info_t *info = nfmalloc(isize);
 
-	/* Second pass, record data. */
+	/* Record area data. */
 
 	size_t area_idx = 0;
 
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
-	    node) {
-		btree_key_t i;
-
-		for (i = 0; i < node->keys; i++) {
-			as_area_t *area = node->value[i];
-
-			assert(area_idx < area_cnt);
-			mutex_lock(&area->lock);
-
-			info[area_idx].start_addr = area->base;
-			info[area_idx].size = P2SZ(area->pages);
-			info[area_idx].flags = area->flags;
-			++area_idx;
-
-			mutex_unlock(&area->lock);
-		}
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		assert(area_idx < area_cnt);
+		mutex_lock(&area->lock);
+
+		info[area_idx].start_addr = area->base;
+		info[area_idx].size = P2SZ(area->pages);
+		info[area_idx].flags = area->flags;
+		++area_idx;
+
+		mutex_unlock(&area->lock);
+		area = as_area_next(area);
 	}
 
@@ -2293,18 +2281,14 @@
 
 	/* Print out info about address space areas */
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
-	    node) {
-		btree_key_t i;
-
-		for (i = 0; i < node->keys; i++) {
-			as_area_t *area = node->value[i];
-
-			mutex_lock(&area->lock);
-			printf("as_area: %p, base=%p, pages=%zu"
-			    " (%p - %p)\n", area, (void *) area->base,
-			    area->pages, (void *) area->base,
-			    (void *) (area->base + P2SZ(area->pages)));
-			mutex_unlock(&area->lock);
-		}
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		mutex_lock(&area->lock);
+		printf("as_area: %p, base=%p, pages=%zu"
+		    " (%p - %p)\n", area, (void *) area->base,
+		    area->pages, (void *) area->base,
+		    (void *) (area->base + P2SZ(area->pages)));
+		mutex_unlock(&area->lock);
+
+		area = as_area_next(area);
 	}
 
Index: kernel/generic/src/proc/task.c
===================================================================
--- kernel/generic/src/proc/task.c	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/src/proc/task.c	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -64,5 +64,7 @@
 IRQ_SPINLOCK_INITIALIZE(tasks_lock);
 
-/** Ordered dictionary of active tasks.
+/** Ordered dictionary of active tasks by task ID.
+ *
+ * Members are task_t structures.
  *
  * The task is guaranteed to exist after it was found in the @c tasks
Index: kernel/generic/src/sysinfo/stats.c
===================================================================
--- kernel/generic/src/sysinfo/stats.c	(revision ac9e79d3a90877ce1c23d880e260120e23f9deaf)
+++ kernel/generic/src/sysinfo/stats.c	(revision b2941268bdf4d8343f1272eb1abf67d33643e63e)
@@ -145,17 +145,13 @@
 	size_t pages = 0;
 
-	/* Walk the B+ tree and count pages */
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
-	    node) {
-		unsigned int i;
-		for (i = 0; i < node->keys; i++) {
-			as_area_t *area = node->value[i];
-
-			if (mutex_trylock(&area->lock) != EOK)
-				continue;
-
-			pages += area->pages;
-			mutex_unlock(&area->lock);
-		}
+	/* Walk areas in the address space and count pages */
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		if (mutex_trylock(&area->lock) != EOK)
+			continue;
+
+		pages += area->pages;
+		mutex_unlock(&area->lock);
+		area = as_area_next(area);
 	}
 
@@ -186,16 +182,13 @@
 	size_t pages = 0;
 
-	/* Walk the B+ tree and count pages */
-	list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) {
-		unsigned int i;
-		for (i = 0; i < node->keys; i++) {
-			as_area_t *area = node->value[i];
-
-			if (mutex_trylock(&area->lock) != EOK)
-				continue;
-
-			pages += area->resident;
-			mutex_unlock(&area->lock);
-		}
+	/* Walk areas in the address space and count pages */
+	as_area_t *area = as_area_first(as);
+	while (area != NULL) {
+		if (mutex_trylock(&area->lock) != EOK)
+			continue;
+
+		pages += area->resident;
+		mutex_unlock(&area->lock);
+		area = as_area_next(area);
 	}
 
