Changes in kernel/generic/src/synch/futex.c [ef4218f:e88eb48] in mainline

File:

• kernel/generic/src/synch/futex.c (modified) (15 diffs)

kernel/generic/src/synch/futex.c

@@ -45 +45 @@
  * encountered before). Futex object's lifetime is governed by
  * a reference count that represents the number of all the different
- * tasks that reference the futex variable. A futex object is freed
+ * user space virtual addresses from all tasks that map to the
+ * physical address of the futex variable. A futex object is freed
  * when the last task having accessed the futex exits.
  *
@@ -51 +52 @@
  * of pointers (futex_ptr_t, task->futex_list) to the different futex
  * objects.
+ *
+ * To speed up translation of futex variables' virtual addresses
+ * to their physical addresses, futex pointers accessed by the
+ * task are furthermore stored in a concurrent hash table (CHT,
+ * task->futexes->ht). A single lookup without locks or accesses
+ * to the page table translates a futex variable's virtual address
+ * into its futex kernel object.
  */
 
@@ -57 +65 @@
 #include <synch/mutex.h>
 #include <synch/spinlock.h>
+#include <synch/rcu.h>
 #include <mm/frame.h>
 #include <mm/page.h>
@@ -64 +73 @@
 #include <genarch/mm/page_pt.h>
 #include <genarch/mm/page_ht.h>
+#include <adt/cht.h>
 #include <adt/hash.h>
 #include <adt/hash_table.h>
@@ -74 +84 @@
 /** Task specific pointer to a global kernel futex object. */
 typedef struct futex_ptr {
-        /** Link for the list of all futex pointers used by a task. */
-        link_t task_link;
+        /** CHT link. */
+        cht_link_t cht_link;
+        /** List of all futex pointers used by the task. */
+        link_t all_link;
         /** Kernel futex object. */
         futex_t *futex;
+        /** User space virtual address of the futex variable in the task. */
+        uintptr_t uaddr;
 } futex_ptr_t;
+
+static void destroy_task_cache(work_t *work);
 
 static void futex_initialize(futex_t *futex, uintptr_t paddr);
@@ -86 +102 @@
 
 static futex_t *get_futex(uintptr_t uaddr);
+static futex_t *find_cached_futex(uintptr_t uaddr);
+static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr);
 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
 
@@ -92 +110 @@
 static bool futex_ht_key_equal(void *key, const ht_link_t *item);
 static void futex_ht_remove_callback(ht_link_t *item);
+
+static size_t task_fut_ht_hash(const cht_link_t *link);
+static size_t task_fut_ht_key_hash(void *key);
+static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2);
+static bool task_fut_ht_key_equal(void *key, const cht_link_t *item);
 
 /** Mutex protecting the global futex hash table.
@@ -113 +136 @@
 };
 
+/** Task futex cache CHT operations. */
+static cht_ops_t task_futex_ht_ops = {
+        .hash = task_fut_ht_hash,
+        .key_hash = task_fut_ht_key_hash,
+        .equal = task_fut_ht_equal,
+        .key_equal = task_fut_ht_key_equal,
+        .remove_callback = NULL
+};
+
 /** Initialize futex subsystem. */
 void futex_init(void)
@@ -122 +154 @@
 void futex_task_init(struct task *task)
 {
-        list_initialize(&task->futex_list);
-        spinlock_initialize(&task->futex_list_lock, "futex-list-lock");
+        task->futexes = nfmalloc(sizeof(struct futex_cache));
+
+        cht_create(&task->futexes->ht, 0, 0, 0, true, &task_futex_ht_ops);
+
+        list_initialize(&task->futexes->list);
+        spinlock_initialize(&task->futexes->list_lock, "futex-list-lock");
+}
+
+/** Destroys the futex structures for the dying task. */
+void futex_task_deinit(task_t *task)
+{
+        /* Interrupts are disabled so we must not block (cannot run cht_destroy). */
+        if (interrupts_disabled()) {
+                /* Invoke the blocking cht_destroy in the background. */
+                workq_global_enqueue_noblock(&task->futexes->destroy_work,
+                    destroy_task_cache);
+        } else {
+                /* We can block. Invoke cht_destroy in this thread. */
+                destroy_task_cache(&task->futexes->destroy_work);
+        }
+}
+
+/** Deallocates a task's CHT futex cache (must already be empty). */
+static void destroy_task_cache(work_t *work)
+{
+        struct futex_cache *cache =
+            member_to_inst(work, struct futex_cache, destroy_work);
+
+        /*
+         * Destroy the cache before manually freeing items of the cache in case
+         * table resize is in progress.
+         */
+        cht_destroy_unsafe(&cache->ht);
+
+        /* Manually free futex_ptr cache items. */
+        list_foreach_safe(cache->list, cur_link, next_link) {
+                futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
+
+                list_remove(cur_link);
+                free(fut_ptr);
+        }
+
+        free(cache);
 }
 
@@ -129 +202 @@
 void futex_task_cleanup(void)
 {
+        struct futex_cache *futexes = TASK->futexes;
+
         /* All threads of this task have terminated. This is the last thread. */
-        spinlock_lock(&TASK->futex_list_lock);
-
-        list_foreach_safe(TASK->futex_list, cur_link, next_link) {
-                futex_ptr_t *futex_ptr = member_to_inst(cur_link, futex_ptr_t,
-                    task_link);
-
-                futex_release_ref_locked(futex_ptr->futex);
-                free(futex_ptr);
-        }
-
-        spinlock_unlock(&TASK->futex_list_lock);
+        spinlock_lock(&futexes->list_lock);
+
+        list_foreach_safe(futexes->list, cur_link, next_link) {
+                futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
+
+                /*
+                 * The function is free to free the futex. All other threads of this
+                 * task have already terminated, so they have also definitely
+                 * exited their CHT futex cache protecting rcu reader sections.
+                 * Moreover release_ref() only frees the futex if this is the
+                 * last task referencing the futex. Therefore, only threads
+                 * of this task may have referenced the futex if it is to be freed.
+                 */
+                futex_release_ref_locked(fut_ptr->futex);
+        }
+
+        spinlock_unlock(&futexes->list_lock);
 }
 
@@ -159 +240 @@
 {
         assert(spinlock_locked(&futex_ht_lock));
-        assert(futex->refcount > 0);
+        assert(0 < futex->refcount);
         ++futex->refcount;
 }
@@ -167 +248 @@
 {
         assert(spinlock_locked(&futex_ht_lock));
-        assert(futex->refcount > 0);
+        assert(0 < futex->refcount);
 
         --futex->refcount;
 
-        if (futex->refcount == 0)
+        if (0 == futex->refcount) {
                 hash_table_remove(&futex_ht, &futex->paddr);
+        }
 }
 
@@ -186 +268 @@
 static futex_t *get_futex(uintptr_t uaddr)
 {
+        futex_t *futex = find_cached_futex(uaddr);
+
+        if (futex)
+                return futex;
+
         uintptr_t paddr;
 
-        if (!find_futex_paddr(uaddr, &paddr))
-                return NULL;
-
-        futex_t *futex = malloc(sizeof(futex_t));
-        if (!futex)
-                return NULL;
-
-        futex_ptr_t *futex_ptr = malloc(sizeof(futex_ptr_t));
-        if (!futex_ptr) {
-                free(futex);
-                return NULL;
-        }
-
-        /*
-         * Find the futex object in the global futex table (or insert it
-         * if it is not present).
-         */
-        spinlock_lock(&TASK->futex_list_lock);
-        spinlock_lock(&futex_ht_lock);
-
-        ht_link_t *fut_link = hash_table_find(&futex_ht, &paddr);
-
-        if (fut_link) {
-                free(futex);
-                futex = member_to_inst(fut_link, futex_t, ht_link);
-
-                /*
-                 * See if the futex is already known to the TASK
-                 */
-                bool found = false;
-                list_foreach(TASK->futex_list, task_link, futex_ptr_t, fp) {
-                        if (fp->futex->paddr == paddr) {
-                                found = true;
-                                break;
-                        }
-                }
-                /*
-                 * If not, put it on the TASK->futex_list and bump its reference
-                 * count
-                 */
-                if (!found) {
-                        list_append(&futex_ptr->task_link, &TASK->futex_list);
-                        futex_add_ref(futex);
-                } else
-                        free(futex_ptr);
-        } else {
-                futex_initialize(futex, paddr);
-                hash_table_insert(&futex_ht, &futex->ht_link);
-
-                /*
-                 * This is a new futex, so it is not on the TASK->futex_list yet
-                 */
-                futex_ptr->futex = futex;
-                list_append(&futex_ptr->task_link, &TASK->futex_list);
-        }
-
-        spinlock_unlock(&futex_ht_lock);
-        spinlock_unlock(&TASK->futex_list_lock);
-
-        return futex;
+        if (!find_futex_paddr(uaddr, &paddr)) {
+                return 0;
+        }
+
+        return get_and_cache_futex(paddr, uaddr);
 }
 
@@ -274 +306 @@
 }
 
+/** Returns the futex cached in this task with the virtual address uaddr. */
+static futex_t *find_cached_futex(uintptr_t uaddr)
+{
+        cht_read_lock();
+
+        futex_t *futex;
+        cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);
+
+        if (futex_ptr_link) {
+                futex_ptr_t *futex_ptr =
+                    member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
+
+                futex = futex_ptr->futex;
+        } else {
+                futex = NULL;
+        }
+
+        cht_read_unlock();
+
+        return futex;
+}
+
+/**
+ * Returns a kernel futex for the physical address @a phys_addr and caches
+ * it in this task under the virtual address @a uaddr (if not already cached).
+ */
+static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr)
+{
+        futex_t *futex = malloc(sizeof(futex_t));
+        if (!futex)
+                return NULL;
+
+        /*
+         * Find the futex object in the global futex table (or insert it
+         * if it is not present).
+         */
+        spinlock_lock(&futex_ht_lock);
+
+        ht_link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
+
+        if (fut_link) {
+                free(futex);
+                futex = member_to_inst(fut_link, futex_t, ht_link);
+                futex_add_ref(futex);
+        } else {
+                futex_initialize(futex, phys_addr);
+                hash_table_insert(&futex_ht, &futex->ht_link);
+        }
+
+        spinlock_unlock(&futex_ht_lock);
+
+        /*
+         * Cache the link to the futex object for this task.
+         */
+        futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t));
+        if (!fut_ptr) {
+                spinlock_lock(&futex_ht_lock);
+                futex_release_ref(futex);
+                spinlock_unlock(&futex_ht_lock);
+                return NULL;
+        }
+        cht_link_t *dup_link;
+
+        fut_ptr->futex = futex;
+        fut_ptr->uaddr = uaddr;
+
+        cht_read_lock();
+
+        /* Cache the mapping from the virtual address to the futex for this task. */
+        if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
+                spinlock_lock(&TASK->futexes->list_lock);
+                list_append(&fut_ptr->all_link, &TASK->futexes->list);
+                spinlock_unlock(&TASK->futexes->list_lock);
+        } else {
+                /* Another thread of this task beat us to it. Use that mapping instead.*/
+                free(fut_ptr);
+                futex_release_ref_locked(futex);
+
+                futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
+                futex = dup->futex;
+        }
+
+        cht_read_unlock();
+
+        return futex;
+}
+
 /** Sleep in futex wait queue with a timeout.
- *
  *  If the sleep times out or is interrupted, the next wakeup is ignored.
  *  The userspace portion of the call must handle this condition.
@@ -359 +477 @@
 }
 
+/*
+ * Operations of a task's CHT that caches mappings of futex user space
+ * virtual addresses to kernel futex objects.
+ */
+
+static size_t task_fut_ht_hash(const cht_link_t *link)
+{
+        const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link);
+        return fut_ptr->uaddr;
+}
+
+static size_t task_fut_ht_key_hash(void *key)
+{
+        return *(uintptr_t *)key;
+}
+
+static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2)
+{
+        const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link);
+        const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link);
+
+        return fut_ptr1->uaddr == fut_ptr2->uaddr;
+}
+
+static bool task_fut_ht_key_equal(void *key, const cht_link_t *item)
+{
+        const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link);
+        uintptr_t uaddr = *(uintptr_t *)key;
+
+        return fut_ptr->uaddr == uaddr;
+}
+
 /** @}
  */