Changeset 235d31d in mainline for kernel/generic/src/synch/futex.c

Timestamp:

2014-12-22T17:47:40Z (9 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

8c7d5ad

Parents:

eae91e0 (diff), 759ea0d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge the CHT pre-integration branch

This branch contains:

• the merge of lp:~adam-hraska+lp/helenos/rcu, which brings:

• a new preemptible kernel RCU variant called A-RCU,
• a preemptible variant of Podzimek's non-preemptible kernel RCU and
• a new variant of usersace RCU,
• a new concurrent hash table (CHT) implementation based on RCU,
• a deployment of CHT in kernel futex handling,
• a deployment of the userspace RCU in the implementation of upgradable futexes,

all described in Adam Hraska's master thesis named Read-Copy-Update
for HelenOS, defended in 2013 at MFF UK; furthemore, the branch
fixes two synchronization bugs in condvars and waitq, respectively:

• revid:adam.hraska+hos@gmail.com-20121116144921-3to9u1tn1sg07rg7
• revid:adam.hraska+hos@gmail.com-20121116173623-km7gwtqixwudpe66

• build fixes required to pass make check
• overhaul of ia64 and sparc64 trap handling, to allow exc_dispatch() to be used now when the kernel is more picky about CPU state accounting
• an important fix of the sparc64/sun4v preemptible trap handler
• various other fixes of issues discovered on non-x86 architectures

File:

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

kernel/generic/src/synch/futex.c

@@ -1 +1 @@
 /*
  * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
  * All rights reserved.
  *
@@ -34 +35 @@
  * @file
  * @brief       Kernel backend for futexes.
+ * 
+ * Kernel futex objects are stored in a global hash table futex_ht 
+ * where the physical address of the futex variable (futex_t.paddr)
+ * is used as the lookup key. As a result multiple address spaces 
+ * may share the same futex variable. 
+ * 
+ * A kernel futex object is created the first time a task accesses
+ * the futex (having a futex variable at a physical address not 
+ * 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
+ * when the last task having accessed the futex exits.
+ * 
+ * Each task keeps track of the futex objects it accessed in a list
+ * 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. 
  */
 
@@ -39 +64 @@
 #include <synch/mutex.h>
 #include <synch/spinlock.h>
+#include <synch/rcu.h>
 #include <mm/frame.h>
 #include <mm/page.h>
@@ -46 +72 @@
 #include <genarch/mm/page_pt.h>
 #include <genarch/mm/page_ht.h>
+#include <adt/cht.h>
 #include <adt/hash_table.h>
 #include <adt/list.h>
@@ -52 +79 @@
 #include <panic.h>
 #include <errno.h>
-#include <print.h>
 
 #define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
 
-static void futex_initialize(futex_t *futex);
-
-static futex_t *futex_find(uintptr_t paddr);
+/** 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;
+        /** 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);
+static void futex_add_ref(futex_t *futex);
+static void futex_release_ref(futex_t *futex);
+static void futex_release_ref_locked(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 size_t futex_ht_hash(sysarg_t *key);
 static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
 static void futex_ht_remove_callback(link_t *item);
 
-/**
- * Mutex protecting global futex hash table.
- * It is also used to serialize access to all futex_t structures.
- * Must be acquired before the task futex B+tree lock.
- */
-static mutex_t futex_ht_lock;
-
-/** Futex hash table. */
+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.
+ * 
+ * Acquire task specific TASK->futex_list_lock before this mutex.
+ */
+SPINLOCK_STATIC_INITIALIZE_NAME(futex_ht_lock, "futex-ht-lock");
+
+/** Global kernel futex hash table. Lock futex_ht_lock before accessing.
+ * 
+ * Physical address of the futex variable is the lookup key.
+ */
 static hash_table_t futex_ht;
 
-/** Futex hash table operations. */
+/** Global kernel futex hash table operations. */
 static hash_table_operations_t futex_ht_ops = {
         .hash = futex_ht_hash,
@@ -80 +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)
 {
-        mutex_initialize(&futex_ht_lock, MUTEX_PASSIVE);
         hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
 }
 
-/** Initialize kernel futex structure.
- *
- * @param futex         Kernel futex structure.
- */
-void futex_initialize(futex_t *futex)
+/** Initializes the futex structures for the new task. */
+void futex_task_init(struct task *task)
+{
+        task->futexes = malloc(sizeof(struct futex_cache), 0);
+        
+        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);
+}
+
+/** Remove references from futexes known to the current task. */
+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);
+}
+
+
+/** Initialize the kernel futex structure.
+ *
+ * @param futex Kernel futex structure.
+ * @param paddr Physical address of the futex variable.
+ */
+static void futex_initialize(futex_t *futex, uintptr_t paddr)
 {
         waitq_initialize(&futex->wq);
         link_initialize(&futex->ht_link);
-        futex->paddr = 0;
+        futex->paddr = paddr;
         futex->refcount = 1;
+}
+
+/** Increments the counter of tasks referencing the futex. */
+static void futex_add_ref(futex_t *futex)
+{
+        ASSERT(spinlock_locked(&futex_ht_lock));
+        ASSERT(0 < futex->refcount);
+        ++futex->refcount;
+}
+
+/** Decrements the counter of tasks referencing the futex. May free the futex.*/
+static void futex_release_ref(futex_t *futex)
+{
+        ASSERT(spinlock_locked(&futex_ht_lock));
+        ASSERT(0 < futex->refcount);
+        
+        --futex->refcount;
+        
+        if (0 == futex->refcount) {
+                hash_table_remove(&futex_ht, &futex->paddr, 1);
+        }
+}
+
+/** Decrements the counter of tasks referencing the futex. May free the futex.*/
+static void futex_release_ref_locked(futex_t *futex)
+{
+        spinlock_lock(&futex_ht_lock);
+        futex_release_ref(futex);
+        spinlock_unlock(&futex_ht_lock);
+}
+
+/** Returns a futex for the virtual address @a uaddr (or creates one). */
+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);
+}
+
+
+/** Finds the physical address of the futex variable. */
+static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *paddr)
+{
+        page_table_lock(AS, false);
+        spinlock_lock(&futex_ht_lock);
+
+        bool found = false;
+        pte_t *t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), true);
+        
+        if (t && PTE_VALID(t) && PTE_PRESENT(t)) {
+                found = true;
+                *paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
+        }
+        
+        spinlock_unlock(&futex_ht_lock);
+        page_table_unlock(AS, false);
+        
+        return found;
+}
+
+/** 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), 0);
+        
+        /* 
+         * Find the futex object in the global futex table (or insert it 
+         * if it is not present).
+         */
+        spinlock_lock(&futex_ht_lock);
+        
+        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, &phys_addr, &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), 0);
+        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;
 }
 
@@ -109 +395 @@
 sysarg_t sys_futex_sleep(uintptr_t uaddr)
 {
-        futex_t *futex;
-        uintptr_t paddr;
-        pte_t *t;
-        int rc;
-        
-        /*
-         * Find physical address of futex counter.
-         */
-        page_table_lock(AS, true);
-        t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false);
-        if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
-                page_table_unlock(AS, true);
+        futex_t *futex = get_futex(uaddr);
+        
+        if (!futex) 
                 return (sysarg_t) ENOENT;
-        }
-        paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
-        page_table_unlock(AS, true);
-        
-        futex = futex_find(paddr);
-
-#ifdef CONFIG_UDEBUG
-        udebug_stoppable_begin();
-#endif
-        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE); 
-#ifdef CONFIG_UDEBUG
-        udebug_stoppable_end();
-#endif
+
+        int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE); 
+
         return (sysarg_t) rc;
 }
@@ -146 +413 @@
 sysarg_t sys_futex_wakeup(uintptr_t uaddr)
 {
-        futex_t *futex;
-        uintptr_t paddr;
-        pte_t *t;
-        
-        /*
-         * Find physical address of futex counter.
-         */
-        page_table_lock(AS, true);
-        t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false);
-        if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
-                page_table_unlock(AS, true);
+        futex_t *futex = get_futex(uaddr);
+        
+        if (futex) {
+                waitq_wakeup(&futex->wq, WAKEUP_FIRST);
+                return 0;
+        } else {
                 return (sysarg_t) ENOENT;
         }
-        paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
-        page_table_unlock(AS, true);
-        
-        futex = futex_find(paddr);
-                
-        waitq_wakeup(&futex->wq, WAKEUP_FIRST);
-        
-        return 0;
-}
-
-/** Find kernel address of the futex structure corresponding to paddr.
- *
- * If the structure does not exist already, a new one is created.
- *
- * @param paddr         Physical address of the userspace futex counter.
- *
- * @return              Address of the kernel futex structure.
- */
-futex_t *futex_find(uintptr_t paddr)
-{
-        link_t *item;
-        futex_t *futex;
-        btree_node_t *leaf;
-        
-        /*
-         * Find the respective futex structure
-         * or allocate new one if it does not exist already.
-         */
-        mutex_lock(&futex_ht_lock);
-        item = hash_table_find(&futex_ht, &paddr);
-        if (item) {
-                futex = hash_table_get_instance(item, futex_t, ht_link);
-
-                /*
-                 * See if the current task knows this futex.
-                 */
-                mutex_lock(&TASK->futexes_lock);
-                if (!btree_search(&TASK->futexes, paddr, &leaf)) {
-                        /*
-                         * The futex is new to the current task.
-                         * Upgrade its reference count and put it to the
-                         * current task's B+tree of known futexes.
-                         */
-                        futex->refcount++;
-                        btree_insert(&TASK->futexes, paddr, futex, leaf);
-                }
-                mutex_unlock(&TASK->futexes_lock);
-        } else {
-                futex = (futex_t *) malloc(sizeof(futex_t), 0);
-                futex_initialize(futex);
-                futex->paddr = paddr;
-                hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
-                        
-                /*
-                 * This is the first task referencing the futex.
-                 * It can be directly inserted into its
-                 * B+tree of known futexes.
-                 */
-                mutex_lock(&TASK->futexes_lock);
-                btree_insert(&TASK->futexes, paddr, futex, NULL);
-                mutex_unlock(&TASK->futexes_lock);
-                
-        }
-        mutex_unlock(&futex_ht_lock);
-        
-        return futex;
-}
+}
+
 
 /** Compute hash index into futex hash table.
@@ -268 +465 @@
 }
 
-/** Remove references from futexes known to the current task. */
-void futex_cleanup(void)
-{
-        mutex_lock(&futex_ht_lock);
-        mutex_lock(&TASK->futexes_lock);
-
-        list_foreach(TASK->futexes.leaf_list, leaf_link, btree_node_t, node) {
-                unsigned int i;
-                
-                for (i = 0; i < node->keys; i++) {
-                        futex_t *ftx;
-                        uintptr_t paddr = node->key[i];
-                        
-                        ftx = (futex_t *) node->value[i];
-                        if (--ftx->refcount == 0)
-                                hash_table_remove(&futex_ht, &paddr, 1);
-                }
-        }
-        
-        mutex_unlock(&TASK->futexes_lock);
-        mutex_unlock(&futex_ht_lock);
+/*
+ * 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;
 }