Index: kernel/generic/src/mm/as.c
===================================================================
--- kernel/generic/src/mm/as.c	(revision ca21f1e2563262ce9dfca34baebb191c134e3037)
+++ kernel/generic/src/mm/as.c	(revision d83663074f80313df3a9070a823f80355dfebb7e)
@@ -89,8 +89,9 @@
 as_operations_t *as_operations = NULL;
 
-/** Slab for as_t objects.
- *
- */
+/** Cache for as_t objects */
 static slab_cache_t *as_cache;
+
+/** Cache for as_page_mapping_t objects */
+static slab_cache_t *as_page_mapping_cache;
 
 /** ASID subsystem lock.
@@ -138,4 +139,7 @@
 	as_cache = slab_cache_create("as_t", sizeof(as_t), 0,
 	    as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED);
+
+	as_page_mapping_cache = slab_cache_create("as_page_mapping_t",
+	    sizeof(as_page_mapping_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
 
 	AS_KERNEL = as_create(FLAG_AS_KERNEL);
@@ -524,4 +528,144 @@
 }
 
+/** Get key function for pagemap ordered dictionary.
+ *
+ * The key is the virtual address of the page (as_page_mapping_t.vaddr)
+ *
+ * @param odlink Link to as_pagemap_t.map ordered dictionary
+ * @return Pointer to virtual address cast as @c void *
+ */
+static void *as_pagemap_getkey(odlink_t *odlink)
+{
+	as_page_mapping_t *mapping;
+
+	mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);
+	return (void *) &mapping->vaddr;
+}
+
+/** Comparison function for pagemap ordered dictionary.
+ *
+ * @param a Pointer to virtual address cast as @c void *
+ * @param b Pointer to virtual address cast as @c void *
+ * @return <0, =0, >0 if virtual address a is less than, equal to, or
+ *         greater-than b, respectively.
+ */
+static int as_pagemap_cmp(void *a, void *b)
+{
+	uintptr_t va = *(uintptr_t *)a;
+	uintptr_t vb = *(uintptr_t *)b;
+
+	return va - vb;
+}
+
+/** Initialize pagemap.
+ *
+ * @param pagemap Pagemap
+ */
+NO_TRACE void as_pagemap_initialize(as_pagemap_t *pagemap)
+{
+	odict_initialize(&pagemap->map, as_pagemap_getkey, as_pagemap_cmp);
+}
+
+/** Finalize pagemap.
+ *
+ * Destroy any entries in the pagemap.
+ *
+ * @param pagemap Pagemap
+ */
+NO_TRACE void as_pagemap_finalize(as_pagemap_t *pagemap)
+{
+	as_page_mapping_t *mapping = as_pagemap_first(pagemap);
+	while (mapping != NULL) {
+		as_pagemap_remove(mapping);
+		mapping = as_pagemap_first(pagemap);
+	}
+	odict_finalize(&pagemap->map);
+}
+
+/** Get first page mapping.
+ *
+ * @param pagemap Pagemap
+ * @return First mapping or @c NULL if there is none
+ */
+NO_TRACE as_page_mapping_t *as_pagemap_first(as_pagemap_t *pagemap)
+{
+	odlink_t *odlink;
+
+	odlink = odict_first(&pagemap->map);
+	if (odlink == NULL)
+		return NULL;
+
+	return odict_get_instance(odlink, as_page_mapping_t, lpagemap);
+}
+
+/** Get next page mapping.
+ *
+ * @param cur Current mapping
+ * @return Next mapping or @c NULL if @a cur is the last one
+ */
+NO_TRACE as_page_mapping_t *as_pagemap_next(as_page_mapping_t *cur)
+{
+	odlink_t *odlink;
+
+	odlink = odict_next(&cur->lpagemap, &cur->pagemap->map);
+	if (odlink == NULL)
+		return NULL;
+
+	return odict_get_instance(odlink, as_page_mapping_t, lpagemap);
+}
+
+/** Find frame by virtual address.
+ *
+ * @param pagemap Pagemap
+ * @param vaddr Virtual address of page
+ * @param rframe Place to store physical frame address
+ * @return EOK on succcess or ENOENT if no mapping found
+ */
+NO_TRACE errno_t as_pagemap_find(as_pagemap_t *pagemap, uintptr_t vaddr,
+    uintptr_t *rframe)
+{
+	odlink_t *odlink;
+	as_page_mapping_t *mapping;
+
+	odlink = odict_find_eq(&pagemap->map, &vaddr, NULL);
+	if (odlink == NULL)
+		return ENOENT;
+
+	mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);
+	*rframe = mapping->frame;
+	return EOK;
+}
+
+/** Insert new page mapping.
+ *
+ * This function can block to allocate kernel memory.
+ *
+ * @param pagemap Pagemap
+ * @param vaddr Virtual page address
+ * @param frame Physical frame address
+ */
+NO_TRACE void as_pagemap_insert(as_pagemap_t *pagemap, uintptr_t vaddr,
+    uintptr_t frame)
+{
+	as_page_mapping_t *mapping;
+
+	mapping = slab_alloc(as_page_mapping_cache, 0);
+	mapping->pagemap = pagemap;
+	odlink_initialize(&mapping->lpagemap);
+	mapping->vaddr = vaddr;
+	mapping->frame = frame;
+	odict_insert(&mapping->lpagemap, &pagemap->map, NULL);
+}
+
+/** Remove page mapping.
+ *
+ * @param mapping Mapping
+ */
+NO_TRACE void as_pagemap_remove(as_page_mapping_t *mapping)
+{
+	odict_remove(&mapping->lpagemap);
+	slab_free(as_page_mapping_cache, mapping);
+}
+
 /** Remove reference to address space area share info.
  *
@@ -545,10 +689,8 @@
 		 * reference from all frames found there.
 		 */
-		list_foreach(sh_info->pagemap.leaf_list, leaf_link,
-		    btree_node_t, node) {
-			btree_key_t i;
-
-			for (i = 0; i < node->keys; i++)
-				frame_free((uintptr_t) node->value[i], 1);
+		as_page_mapping_t *mapping = as_pagemap_first(&sh_info->pagemap);
+		while (mapping != NULL) {
+			frame_free(mapping->frame, 1);
+			mapping = as_pagemap_next(mapping);
 		}
 
@@ -561,5 +703,5 @@
 			    sh_info->backend_shared_data);
 		}
-		btree_destroy(&sh_info->pagemap);
+		as_pagemap_finalize(&sh_info->pagemap);
 		free(sh_info);
 	}
@@ -665,5 +807,5 @@
 		si->backend_shared_data = NULL;
 		si->backend = backend;
-		btree_create(&si->pagemap);
+		as_pagemap_initialize(&si->pagemap);
 
 		area->sh_info = si;
Index: kernel/generic/src/mm/backend_anon.c
===================================================================
--- kernel/generic/src/mm/backend_anon.c	(revision ca21f1e2563262ce9dfca34baebb191c134e3037)
+++ kernel/generic/src/mm/backend_anon.c	(revision d83663074f80313df3a9070a823f80355dfebb7e)
@@ -144,7 +144,7 @@
 				assert(PTE_PRESENT(&pte));
 
-				btree_insert(&area->sh_info->pagemap,
+				as_pagemap_insert(&area->sh_info->pagemap,
 				    (base + P2SZ(j)) - area->base,
-				    (void *) PTE_GET_FRAME(&pte), NULL);
+				    PTE_GET_FRAME(&pte));
 				page_table_unlock(area->as, false);
 
@@ -201,6 +201,4 @@
 	mutex_lock(&area->sh_info->lock);
 	if (area->sh_info->shared) {
-		btree_node_t *leaf;
-
 		/*
 		 * The area is shared, chances are that the mapping can be found
@@ -210,33 +208,19 @@
 		 * mapping, a new frame is allocated and the mapping is created.
 		 */
-		frame = (uintptr_t) btree_search(&area->sh_info->pagemap,
-		    upage - area->base, &leaf);
-		if (!frame) {
-			bool allocate = true;
-			unsigned int i;
+		errno_t rc = as_pagemap_find(&area->sh_info->pagemap,
+		    upage - area->base, &frame);
+		if (rc != EOK) {
+			/* Need to allocate the frame */
+			kpage = km_temporary_page_get(&frame,
+			    FRAME_NO_RESERVE);
+			memsetb((void *) kpage, PAGE_SIZE, 0);
+			km_temporary_page_put(kpage);
 
 			/*
-			 * Zero can be returned as a valid frame address.
-			 * Just a small workaround.
+			 * Insert the address of the newly allocated
+			 * frame to the pagemap.
 			 */
-			for (i = 0; i < leaf->keys; i++) {
-				if (leaf->key[i] == upage - area->base) {
-					allocate = false;
-					break;
-				}
-			}
-			if (allocate) {
-				kpage = km_temporary_page_get(&frame,
-				    FRAME_NO_RESERVE);
-				memsetb((void *) kpage, PAGE_SIZE, 0);
-				km_temporary_page_put(kpage);
-
-				/*
-				 * Insert the address of the newly allocated
-				 * frame to the pagemap.
-				 */
-				btree_insert(&area->sh_info->pagemap,
-				    upage - area->base, (void *) frame, leaf);
-			}
+			as_pagemap_insert(&area->sh_info->pagemap,
+			    upage - area->base, frame);
 		}
 		frame_reference_add(ADDR2PFN(frame));
Index: kernel/generic/src/mm/backend_elf.c
===================================================================
--- kernel/generic/src/mm/backend_elf.c	(revision ca21f1e2563262ce9dfca34baebb191c134e3037)
+++ kernel/generic/src/mm/backend_elf.c	(revision d83663074f80313df3a9070a823f80355dfebb7e)
@@ -219,7 +219,7 @@
 				assert(PTE_PRESENT(&pte));
 
-				btree_insert(&area->sh_info->pagemap,
+				as_pagemap_insert(&area->sh_info->pagemap,
 				    (base + P2SZ(j)) - area->base,
-				    (void *) PTE_GET_FRAME(&pte), NULL);
+				    PTE_GET_FRAME(&pte));
 				page_table_unlock(area->as, false);
 
@@ -267,5 +267,4 @@
 	elf_header_t *elf = area->backend_data.elf;
 	elf_segment_header_t *entry = area->backend_data.segment;
-	btree_node_t *leaf;
 	uintptr_t base;
 	uintptr_t frame;
@@ -301,27 +300,11 @@
 	mutex_lock(&area->sh_info->lock);
 	if (area->sh_info->shared) {
-		bool found = false;
-
 		/*
 		 * The address space area is shared.
 		 */
 
-		frame = (uintptr_t) btree_search(&area->sh_info->pagemap,
-		    upage - area->base, &leaf);
-		if (!frame) {
-			unsigned int i;
-
-			/*
-			 * Workaround for valid NULL address.
-			 */
-
-			for (i = 0; i < leaf->keys; i++) {
-				if (leaf->key[i] == upage - area->base) {
-					found = true;
-					break;
-				}
-			}
-		}
-		if (frame || found) {
+		errno_t rc = as_pagemap_find(&area->sh_info->pagemap,
+		    upage - area->base, &frame);
+		if (rc == EOK) {
 			frame_reference_add(ADDR2PFN(frame));
 			page_mapping_insert(AS, upage, frame,
@@ -415,6 +398,6 @@
 	if (dirty && area->sh_info->shared) {
 		frame_reference_add(ADDR2PFN(frame));
-		btree_insert(&area->sh_info->pagemap, upage - area->base,
-		    (void *) frame, leaf);
+		as_pagemap_insert(&area->sh_info->pagemap, upage - area->base,
+		    frame);
 	}