Changes in kernel/generic/src/synch/futex.c [96b02eb9:98000fb] in mainline

File:

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

kernel/generic/src/synch/futex.c

@@ -37 +37 @@
 
 #include <synch/futex.h>
-#include <synch/mutex.h>
+#include <synch/rwlock.h>
 #include <synch/spinlock.h>
 #include <synch/synch.h>
@@ -60 +60 @@
 
 static futex_t *futex_find(uintptr_t paddr);
-static size_t futex_ht_hash(sysarg_t *key);
-static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
+static size_t futex_ht_hash(unative_t *key);
+static bool futex_ht_compare(unative_t *key, size_t keys, link_t *item);
 static void futex_ht_remove_callback(link_t *item);
 
 /**
- * Mutex protecting global futex hash table.
+ * Read-write lock 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;
+static rwlock_t futex_ht_lock;
 
 /** Futex hash table. */
@@ -84 +84 @@
 void futex_init(void)
 {
-        mutex_initialize(&futex_ht_lock, MUTEX_PASSIVE);
+        rwlock_initialize(&futex_ht_lock);
         hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
 }
@@ -90 +90 @@
 /** Initialize kernel futex structure.
  *
- * @param futex         Kernel futex structure.
+ * @param futex Kernel futex structure.
  */
 void futex_initialize(futex_t *futex)
@@ -102 +102 @@
 /** Sleep in futex wait queue.
  *
- * @param uaddr         Userspace address of the futex counter.
- *
- * @return              If there is no physical mapping for uaddr ENOENT is
- *                      returned. Otherwise returns a wait result as defined in
- *                      synch.h.
- */
-sysarg_t sys_futex_sleep(uintptr_t uaddr)
+ * @param uaddr Userspace address of the futex counter.
+ * @param usec If non-zero, number of microseconds this thread is willing to
+ *     sleep.
+ * @param flags Select mode of operation.
+ *
+ * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See
+ *     synch.h. If there is no physical mapping for uaddr ENOENT is returned.
+ */
+unative_t sys_futex_sleep_timeout(uintptr_t uaddr, uint32_t usec, int flags)
 {
         futex_t *futex;
         uintptr_t paddr;
         pte_t *t;
+        ipl_t ipl;
         int rc;
         
+        ipl = interrupts_disable();
+
         /*
          * Find physical address of futex counter.
@@ -122 +127 @@
         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
                 page_table_unlock(AS, true);
-                return (sysarg_t) ENOENT;
+                interrupts_restore(ipl);
+                return (unative_t) ENOENT;
         }
         paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
         page_table_unlock(AS, true);
         
+        interrupts_restore(ipl);        
+
         futex = futex_find(paddr);
 
@@ -132 +140 @@
         udebug_stoppable_begin();
 #endif
-        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE); 
+        rc = waitq_sleep_timeout(&futex->wq, usec, flags |
+            SYNCH_FLAGS_INTERRUPTIBLE);
+
 #ifdef CONFIG_UDEBUG
         udebug_stoppable_end();
 #endif
-        return (sysarg_t) rc;
+        return (unative_t) rc;
 }
 
 /** Wakeup one thread waiting in futex wait queue.
  *
- * @param uaddr         Userspace address of the futex counter.
- *
- * @return              ENOENT if there is no physical mapping for uaddr.
- */
-sysarg_t sys_futex_wakeup(uintptr_t uaddr)
+ * @param uaddr Userspace address of the futex counter.
+ *
+ * @return ENOENT if there is no physical mapping for uaddr.
+ */
+unative_t sys_futex_wakeup(uintptr_t uaddr)
 {
         futex_t *futex;
         uintptr_t paddr;
         pte_t *t;
+        ipl_t ipl;
+        
+        ipl = interrupts_disable();
         
         /*
@@ -158 +171 @@
         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
                 page_table_unlock(AS, true);
-                return (sysarg_t) ENOENT;
+                interrupts_restore(ipl);
+                return (unative_t) ENOENT;
         }
         paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
         page_table_unlock(AS, true);
         
+        interrupts_restore(ipl);
+
         futex = futex_find(paddr);
                 
@@ -174 +190 @@
  * 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.
+ * @param paddr Physical address of the userspace futex counter.
+ *
+ * @return Address of the kernel futex structure.
  */
 futex_t *futex_find(uintptr_t paddr)
@@ -188 +204 @@
          * or allocate new one if it does not exist already.
          */
-        mutex_lock(&futex_ht_lock);
+        rwlock_read_lock(&futex_ht_lock);
         item = hash_table_find(&futex_ht, &paddr);
         if (item) {
@@ -200 +216 @@
                         /*
                          * 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.
+                         * However, we only have read access.
+                         * Gain write access and try again.
                          */
-                        futex->refcount++;
-                        btree_insert(&TASK->futexes, paddr, futex, leaf);
+                        mutex_unlock(&TASK->futexes_lock);
+                        goto gain_write_access;
                 }
                 mutex_unlock(&TASK->futexes_lock);
+
+                rwlock_read_unlock(&futex_ht_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);
+gain_write_access:
+                /*
+                 * Upgrade to writer is not currently supported,
+                 * therefore, it is necessary to release the read lock
+                 * and reacquire it as a writer.
+                 */
+                rwlock_read_unlock(&futex_ht_lock);
+
+                rwlock_write_lock(&futex_ht_lock);
+                /*
+                 * Avoid possible race condition by searching
+                 * the hash table once again with write access.
+                 */
+                item = hash_table_find(&futex_ht, &paddr);
+                if (item) {
+                        futex = hash_table_get_instance(item, futex_t, 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);
-                
+                        /*
+                         * See if this futex is known to the current task.
+                         */
+                        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);
+        
+                        rwlock_write_unlock(&futex_ht_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);
+                        
+                        rwlock_write_unlock(&futex_ht_lock);
+                }
         }
-        mutex_unlock(&futex_ht_lock);
         
         return futex;
@@ -230 +284 @@
 /** Compute hash index into futex hash table.
  *
- * @param key           Address where the key (i.e. physical address of futex
- *                      counter) is stored.
- *
- * @return              Index into futex hash table.
- */
-size_t futex_ht_hash(sysarg_t *key)
+ * @param key Address where the key (i.e. physical address of futex counter) is
+ *     stored.
+ *
+ * @return Index into futex hash table.
+ */
+size_t futex_ht_hash(unative_t *key)
 {
         return (*key & (FUTEX_HT_SIZE - 1));
@@ -242 +296 @@
 /** Compare futex hash table item with a key.
  *
- * @param key           Address where the key (i.e. physical address of futex
- *                      counter) is stored.
- *
- * @return              True if the item matches the key. False otherwise.
- */
-bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item)
+ * @param key Address where the key (i.e. physical address of futex counter) is
+ *     stored.
+ *
+ * @return True if the item matches the key. False otherwise.
+ */
+bool futex_ht_compare(unative_t *key, size_t keys, link_t *item)
 {
         futex_t *futex;
@@ -259 +313 @@
 /** Callback for removal items from futex hash table.
  *
- * @param item          Item removed from the hash table.
+ * @param item Item removed from the hash table.
  */
 void futex_ht_remove_callback(link_t *item)
@@ -274 +328 @@
         link_t *cur;
         
-        mutex_lock(&futex_ht_lock);
+        rwlock_write_lock(&futex_ht_lock);
         mutex_lock(&TASK->futexes_lock);
 
@@ -294 +348 @@
         
         mutex_unlock(&TASK->futexes_lock);
-        mutex_unlock(&futex_ht_lock);
+        rwlock_write_unlock(&futex_ht_lock);
 }