Index: kernel/generic/src/cap/cap.c
===================================================================
--- kernel/generic/src/cap/cap.c	(revision 6636fb199c2da579a541a22014f1a1e5321c2a68)
+++ kernel/generic/src/cap/cap.c	(revision cccd60c3524a3bb23ce0db2ce5c33c181326931e)
@@ -79,17 +79,34 @@
 #include <adt/list.h>
 
+#include <stdint.h>
+
+#define MAX_CAPS	INT_MAX
+
 static kobject_t *cap_unpublish_locked(task_t *, cap_handle_t, kobject_type_t);
 
-/** Initialize capability and associate it with its handle
- *
- * @param cap     Address of the capability.
- * @param handle  Capability handle.
- */
-void cap_initialize(cap_t *cap, cap_handle_t handle)
-{
-	cap->state = CAP_STATE_FREE;
-	cap->handle = handle;
-	link_initialize(&cap->link);
-}
+static size_t caps_hash(const ht_link_t *item)
+{
+	cap_t *cap = hash_table_get_inst(item, cap_t, caps_link);
+	return hash_mix(cap->handle);
+}
+
+static size_t caps_key_hash(void *key)
+{
+	cap_handle_t *handle = (cap_handle_t *) key;
+	return hash_mix(*handle);
+}
+
+static bool caps_key_equal(void *key, const ht_link_t *item)
+{
+	cap_handle_t *handle = (cap_handle_t *) key;
+	cap_t *cap = hash_table_get_inst(item, cap_t, caps_link);
+	return *handle == cap->handle;
+}
+
+static hash_table_ops_t caps_ops = {
+	.hash = caps_hash,
+	.key_hash = caps_key_hash,
+	.key_equal = caps_key_equal
+};
 
 /** Allocate the capability info structure
@@ -100,5 +117,13 @@
 {
 	task->cap_info = (cap_info_t *) malloc(sizeof(cap_info_t), 0);
-	task->cap_info->caps = malloc(sizeof(cap_t) * MAX_CAPS, 0);
+	task->cap_info->handles = ra_arena_create();
+	// FIXME: allow caps_task_alloc() to fail 
+	assert(task->cap_info->handles);
+	bool success = ra_span_add(task->cap_info->handles, 0, MAX_CAPS);
+	// FIXME: allow caps_task_alloc() to fail 
+	assert(success);
+	success = hash_table_create(&task->cap_info->caps, 0, 0, &caps_ops);
+	// FIXME: allow caps_task_alloc() to fail 
+	assert(success);
 }
 
@@ -113,7 +138,4 @@
 	for (kobject_type_t t = 0; t < KOBJECT_TYPE_MAX; t++)
 		list_initialize(&task->cap_info->type_list[t]);
-
-	for (cap_handle_t h = 0; h < MAX_CAPS; h++)
-		cap_initialize(&task->cap_info->caps[h], h);
 }
 
@@ -124,5 +146,6 @@
 void caps_task_free(task_t *task)
 {
-	free(task->cap_info->caps);
+	hash_table_destroy(&task->cap_info->caps);
+	ra_arena_destroy(task->cap_info->handles);
 	free(task->cap_info);
 }
@@ -146,5 +169,5 @@
 	mutex_lock(&task->cap_info->lock);
 	list_foreach_safe(task->cap_info->type_list[type], cur, next) {
-		cap_t *cap = list_get_instance(cur, cap_t, link);
+		cap_t *cap = list_get_instance(cur, cap_t, type_link);
 		done = cb(cap, arg);
 		if (!done)
@@ -156,4 +179,18 @@
 }
 
+/** Initialize capability and associate it with its handle
+ *
+ * @param cap     Address of the capability.
+ * @param task    Backling to the owning task.
+ * @param handle  Capability handle.
+ */
+static void cap_initialize(cap_t *cap, task_t *task, cap_handle_t handle)
+{
+	cap->state = CAP_STATE_FREE;
+	cap->task = task;
+	cap->handle = handle;
+	link_initialize(&cap->type_link);
+}
+
 /** Get capability using capability handle
  *
@@ -171,7 +208,29 @@
 	if ((handle < 0) || (handle >= MAX_CAPS))
 		return NULL;
-	if (task->cap_info->caps[handle].state != state)
+	ht_link_t *link = hash_table_find(&task->cap_info->caps, &handle);
+	if (!link)
 		return NULL;
-	return &task->cap_info->caps[handle];
+	cap_t *cap = hash_table_get_inst(link, cap_t, caps_link);
+	if (cap->state != state)
+		return NULL;
+	return cap;
+}
+
+static bool cap_reclaimer(ht_link_t *link, void *arg)
+{
+	cap_t **result = (cap_t **) arg;
+	cap_t *cap = hash_table_get_inst(link, cap_t, caps_link);
+
+	if (cap->state == CAP_STATE_PUBLISHED && cap->kobject->ops->reclaim &&
+	    cap->kobject->ops->reclaim(cap->kobject)) {
+		kobject_t *kobj = cap_unpublish_locked(cap->task, cap->handle,
+		    cap->kobject->type);
+		kobject_put(kobj);
+		cap_initialize(cap, cap->task, cap->handle);
+		*result = cap;
+		return false;
+	}
+
+	return true;
 }
 
@@ -185,25 +244,39 @@
 cap_handle_t cap_alloc(task_t *task)
 {
-	mutex_lock(&task->cap_info->lock);
-	for (cap_handle_t handle = 0; handle < MAX_CAPS; handle++) {
-		cap_t *cap = &task->cap_info->caps[handle];
-		/* See if the capability should be garbage-collected */
-		if (cap->state == CAP_STATE_PUBLISHED &&
-		    cap->kobject->ops->reclaim &&
-		    cap->kobject->ops->reclaim(cap->kobject)) {
-			kobject_t *kobj = cap_unpublish_locked(task, handle,
-			    cap->kobject->type);
-			kobject_put(kobj);
-			cap_initialize(&task->cap_info->caps[handle], handle);
+	cap_t *cap = NULL;
+	cap_handle_t handle;
+
+	/*
+	 * First of all, see if we can reclaim a capability. Note that this
+	 * feature is only temporary and capability reclamaition will eventually
+	 * be phased out.
+	 */
+	mutex_lock(&task->cap_info->lock);
+	hash_table_apply(&task->cap_info->caps, cap_reclaimer, &cap);
+
+	/*
+	 * If we don't have a capability by now, try to allocate a new one.
+	 */
+	if (!cap) {
+		cap = malloc(sizeof(cap_t), 0);
+		if (!cap) {
+			mutex_unlock(&task->cap_info->lock);
+			return ENOMEM;
 		}
-		if (cap->state == CAP_STATE_FREE) {
-			cap->state = CAP_STATE_ALLOCATED;
+		uintptr_t hbase;
+		if (!ra_alloc(task->cap_info->handles, 1, 1, &hbase)) {
+			free(cap);
 			mutex_unlock(&task->cap_info->lock);
-			return handle;
+			return ENOMEM;
 		}
-	}
-	mutex_unlock(&task->cap_info->lock);
-
-	return ELIMIT;
+		cap_initialize(cap, task, (cap_handle_t) hbase);
+		hash_table_insert(&task->cap_info->caps, &cap->caps_link);
+	}
+
+	cap->state = CAP_STATE_ALLOCATED;
+	handle = cap->handle;
+	mutex_unlock(&task->cap_info->lock);
+
+	return handle;
 }
 
@@ -227,5 +300,5 @@
 	/* Hand over kobj's reference to cap */
 	cap->kobject = kobj;
-	list_append(&cap->link, &task->cap_info->type_list[kobj->type]);
+	list_append(&cap->type_link, &task->cap_info->type_list[kobj->type]);
 	mutex_unlock(&task->cap_info->lock);
 }
@@ -242,5 +315,5 @@
 			kobj = cap->kobject;
 			cap->kobject = NULL;
-			list_remove(&cap->link);
+			list_remove(&cap->type_link);
 			cap->state = CAP_STATE_ALLOCATED;
 		}
@@ -281,8 +354,13 @@
 	assert(handle >= 0);
 	assert(handle < MAX_CAPS);
-	assert(task->cap_info->caps[handle].state == CAP_STATE_ALLOCATED);
-
-	mutex_lock(&task->cap_info->lock);
-	cap_initialize(&task->cap_info->caps[handle], handle);
+
+	mutex_lock(&task->cap_info->lock);
+	cap_t *cap = cap_get(task, handle, CAP_STATE_ALLOCATED);
+
+	assert(cap);
+
+	hash_table_remove_item(&task->cap_info->caps, &cap->caps_link);
+	ra_free(task->cap_info->handles, handle, 1);
+	free(cap);
 	mutex_unlock(&task->cap_info->lock);
 }