Context Navigation

-              rbed67f2
+              r947ab77e
  * 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.
  */
 …
 #include <synch/mutex.h>
 #include <synch/spinlock.h>
-#include <synch/rcu.h>
 #include <mm/frame.h>
 #include <mm/page.h>
 …
 #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>
 …
 /** 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;
 …
 } futex_ptr_t;
-static void destroy_task_cache(work_t *work);
 static void futex_initialize(futex_t *futex, uintptr_t paddr);
 static void futex_add_ref(futex_t *futex);
 …
 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);
 …
 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.
 …
 };
-/** 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)
 …
 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");
+}
 …
 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) {
+        spinlock_lock(&TASK->futex_list_lock);
+        list_foreach_safe(TASK->futex_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.
+                 * The function is free to free the futex.  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_unlock(&TASK->futex_list_lock);
+}
 …
 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;
+        /*
+         * 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, &paddr);
+        if (fut_link) {
+                free(futex);
+                futex = member_to_inst(fut_link, futex_t, ht_link);
+                futex_add_ref(futex);
+        } else {
+                futex_initialize(futex, paddr);
+                hash_table_insert(&futex_ht, &futex->ht_link);
+        }
+        spinlock_unlock(&futex_ht_lock);
+        return futex;
+}
 …
+}
-/** 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.
 …
+}
-/*
- * 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;
+}
 /** @}
  */

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 947ab77e in mainline for kernel/generic/src/synch/futex.c

Legend:

kernel/generic/src/synch/futex.c

Download in other formats: