Changeset 947ab77e in mainline

Timestamp:

2018-11-07T20:41:51Z (6 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

aae365bc

Parents:

bed67f2

Message:

Stop using CHT in futexes

Location:

kernel/generic

Files:

• include/proc/task.h (modified) (1 diff)
• include/synch/futex.h (modified) (1 diff)
• src/proc/task.c (modified) (1 diff)
• src/synch/futex.c (modified) (13 diffs)

kernel/generic/include/proc/task.h

@@ -130 +130 @@
         task_arch_t arch;
 
-        struct futex_cache {
-                /** CHT mapping virtual addresses of futex variables to futex objects.*/
-                cht_t ht;
-                /** Serializes access to futex_list.*/
-                SPINLOCK_DECLARE(list_lock);
-                /** List of all futexes accesses by this task. */
-                list_t list;
-                work_t destroy_work;
-        } *futexes;
+        /** Serializes access to futex_list.*/
+        SPINLOCK_DECLARE(futex_list_lock);
+        /** List of all futexes accesses by this task. */
+        list_t futex_list;
 
         /** Accumulated accounting. */

kernel/generic/include/synch/futex.h

@@ -58 +58 @@
 extern void futex_task_cleanup(void);
 extern void futex_task_init(struct task *);
-extern void futex_task_deinit(struct task *);
 
 #endif

kernel/generic/src/proc/task.c

@@ -285 +285 @@
 
         /*
-         * Free up dynamically allocated state.
-         */
-        futex_task_deinit(task);
-
-        /*
          * Drop our reference to the address space.
          */

kernel/generic/src/synch/futex.c

@@ -52 +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.
  */
 
@@ -65 +58 @@
 #include <synch/mutex.h>
 #include <synch/spinlock.h>
-#include <synch/rcu.h>
 #include <mm/frame.h>
 #include <mm/page.h>
@@ -73 +65 @@
 #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 +75 @@
 /** 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;
@@ -94 +83 @@
 } 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);
@@ -102 +89 @@
 
 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 +95 @@
 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 +116 @@
 };
 
-/** 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 +125 @@
 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 +132 @@
 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);
 }
 
@@ -268 +194 @@
 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;
 }
 
@@ -306 +249 @@
 }
 
-/** 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.
@@ -477 +333 @@
 }
 
-/*
- * 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;
-}
-
 /** @}
  */