Changeset 05913fe7 in mainline

Timestamp:

2017-10-09T22:18:09Z (5 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial

Children:

2bdf92a5

Parents:

e02bfb4

Message:

Allow virtually unlimited number of capabilities per task

Location:

kernel/generic

Files:

• include/cap/cap.h (modified) (4 diffs)
• src/cap/cap.c (modified) (11 diffs)

kernel/generic/include/cap/cap.h

@@ -38 +38 @@
 #include <typedefs.h>
 #include <adt/list.h>
+#include <adt/hash.h>
+#include <adt/hash_table.h>
+#include <lib/ra.h>
 #include <synch/mutex.h>
 #include <atomic.h>
-
-#define MAX_CAPS  64
 
 typedef int cap_handle_t;
@@ -89 +90 @@
         cap_state_t state;
 
+        struct task *task;
         cap_handle_t handle;
 
         /* Link to the task's capabilities of the same kobject type. */
-        link_t link;
+        link_t type_link;
+
+        ht_link_t caps_link;
 
         /* The underlying kernel object. */
@@ -103 +107 @@
         list_t type_list[KOBJECT_TYPE_MAX];
 
-        cap_t *caps;
+        hash_table_t caps;
+        ra_arena_t *handles;
 } cap_info_t;
 
@@ -112 +117 @@
     bool (*)(cap_t *, void *), void *);
 
-extern void cap_initialize(cap_t *, cap_handle_t);
 extern cap_handle_t cap_alloc(struct task *);
 extern void cap_publish(struct task *, cap_handle_t, kobject_t *);

kernel/generic/src/cap/cap.c

@@ -79 +79 @@
 #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 +117 @@
 {
         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 +138 @@
         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 +146 @@
 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 +169 @@
         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 +179 @@
 }
 
+/** 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 +208 @@
         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 +244 @@
 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 +300 @@
         /* 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 +315 @@
                         kobj = cap->kobject;
                         cap->kobject = NULL;
-                        list_remove(&cap->link);
+                        list_remove(&cap->type_link);
                         cap->state = CAP_STATE_ALLOCATED;
                 }
@@ -281 +354 @@
         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);
 }