Changes in kernel/generic/src/synch/futex.c [e88eb48:ef4218f] 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
- * user space virtual addresses from all tasks that map to the
- * physical address of the futex variable. A futex object is freed
+ * tasks that reference the futex variable. A futex object is freed
  * when the last task having accessed the futex exits.
  *
@@ -52 +51 @@
  * 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.
  */
 
@@ -65 +57 @@
 #include <synch/mutex.h>
 #include <synch/spinlock.h>
-#include <synch/rcu.h>
 #include <mm/frame.h>
 #include <mm/page.h>
@@ -73 +64 @@
 #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>
@@ -84 +74 @@
 /** Task specific pointer to a global kernel futex object. */
 typedef struct futex_ptr {
-        /** CHT link. */
-        cht_link_t cht_link;
-        /** List of all futex pointers used by the task. */
-        link_t all_link;
+        /** Link for the list of all futex pointers used by a task. */
+        link_t task_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);
@@ -102 +86 @@
 
 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);
 
@@ -110 +92 @@
 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.
@@ -136 +113 @@
 };
 
-/** 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)
@@ -154 +122 @@
 void futex_task_init(struct task *task)
 {
-        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);
+        list_initialize(&task->futex_list);
+        spinlock_initialize(&task->futex_list_lock, "futex-list-lock");
 }
 
@@ -202 +129 @@
 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(&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);
+        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);
 }
 
@@ -240 +159 @@
 {
         assert(spinlock_locked(&futex_ht_lock));
-        assert(0 < futex->refcount);
+        assert(futex->refcount > 0);
         ++futex->refcount;
 }
@@ -248 +167 @@
 {
         assert(spinlock_locked(&futex_ht_lock));
-        assert(0 < futex->refcount);
+        assert(futex->refcount > 0);
 
         --futex->refcount;
 
-        if (0 == futex->refcount) {
+        if (futex->refcount == 0)
                 hash_table_remove(&futex_ht, &futex->paddr);
-        }
 }
 
@@ -268 +186 @@
 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 0;
-        }
-
-        return get_and_cache_futex(paddr, uaddr);
+        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;
 }
 
@@ -306 +274 @@
 }
 
-/** 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.
@@ -477 +359 @@
 }
 
-/*
- * 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;
-}
-
 /** @}
  */