futex.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Jakub Jermar
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00038 #include <synch/futex.h>
00039 #include <synch/rwlock.h>
00040 #include <synch/spinlock.h>
00041 #include <synch/synch.h>
00042 #include <mm/frame.h>
00043 #include <mm/page.h>
00044 #include <mm/slab.h>
00045 #include <proc/thread.h>
00046 #include <proc/task.h>
00047 #include <genarch/mm/page_pt.h>
00048 #include <genarch/mm/page_ht.h>
00049 #include <adt/hash_table.h>
00050 #include <adt/list.h>
00051 #include <arch.h>
00052 #include <align.h>
00053 #include <panic.h>
00054 #include <errno.h>
00055 #include <print.h>
00056 
00057 #define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
00058 
00059 static void futex_initialize(futex_t *futex);
00060 
00061 static futex_t *futex_find(__address paddr);
00062 static index_t futex_ht_hash(__native *key);
00063 static bool futex_ht_compare(__native *key, count_t keys, link_t *item);
00064 static void futex_ht_remove_callback(link_t *item);
00065 
00071 static rwlock_t futex_ht_lock;
00072 
00074 static hash_table_t futex_ht;
00075 
00077 static hash_table_operations_t futex_ht_ops = {
00078         .hash = futex_ht_hash,
00079         .compare = futex_ht_compare,
00080         .remove_callback = futex_ht_remove_callback
00081 };
00082 
00084 void futex_init(void)
00085 {
00086         rwlock_initialize(&futex_ht_lock);
00087         hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
00088 }
00089 
00094 void futex_initialize(futex_t *futex)
00095 {
00096         waitq_initialize(&futex->wq);
00097         link_initialize(&futex->ht_link);
00098         futex->paddr = 0;
00099         futex->refcount = 1;
00100 }
00101 
00111 __native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int flags)
00112 {
00113         futex_t *futex;
00114         __address paddr;
00115         pte_t *t;
00116         ipl_t ipl;
00117         
00118         ipl = interrupts_disable();
00119 
00120         /*
00121          * Find physical address of futex counter.
00122          */
00123         page_table_lock(AS, true);
00124         t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
00125         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
00126                 page_table_unlock(AS, true);
00127                 interrupts_restore(ipl);
00128                 return (__native) ENOENT;
00129         }
00130         paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
00131         page_table_unlock(AS, true);
00132         
00133         interrupts_restore(ipl);        
00134 
00135         futex = futex_find(paddr);
00136         
00137         return (__native) waitq_sleep_timeout(&futex->wq, usec, flags | SYNCH_FLAGS_INTERRUPTIBLE);
00138 }
00139 
00146 __native sys_futex_wakeup(__address uaddr)
00147 {
00148         futex_t *futex;
00149         __address paddr;
00150         pte_t *t;
00151         ipl_t ipl;
00152         
00153         ipl = interrupts_disable();
00154         
00155         /*
00156          * Find physical address of futex counter.
00157          */
00158         page_table_lock(AS, true);
00159         t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
00160         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
00161                 page_table_unlock(AS, true);
00162                 interrupts_restore(ipl);
00163                 return (__native) ENOENT;
00164         }
00165         paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
00166         page_table_unlock(AS, true);
00167         
00168         interrupts_restore(ipl);
00169 
00170         futex = futex_find(paddr);
00171                 
00172         waitq_wakeup(&futex->wq, WAKEUP_FIRST);
00173         
00174         return 0;
00175 }
00176 
00185 futex_t *futex_find(__address paddr)
00186 {
00187         link_t *item;
00188         futex_t *futex;
00189         btree_node_t *leaf;
00190         
00191         /*
00192          * Find the respective futex structure
00193          * or allocate new one if it does not exist already.
00194          */
00195         rwlock_read_lock(&futex_ht_lock);
00196         item = hash_table_find(&futex_ht, &paddr);
00197         if (item) {
00198                 futex = hash_table_get_instance(item, futex_t, ht_link);
00199 
00200                 /*
00201                  * See if the current task knows this futex.
00202                  */
00203                 mutex_lock(&TASK->futexes_lock);
00204                 if (!btree_search(&TASK->futexes, paddr, &leaf)) {
00205                         /*
00206                          * The futex is new to the current task.
00207                          * However, we only have read access.
00208                          * Gain write access and try again.
00209                          */
00210                         mutex_unlock(&TASK->futexes_lock);
00211                         goto gain_write_access;
00212                 }
00213                 mutex_unlock(&TASK->futexes_lock);
00214 
00215                 rwlock_read_unlock(&futex_ht_lock);
00216         } else {
00217 gain_write_access:
00218                 /*
00219                  * Upgrade to writer is not currently supported,
00220                  * therefore, it is necessary to release the read lock
00221                  * and reacquire it as a writer.
00222                  */
00223                 rwlock_read_unlock(&futex_ht_lock);
00224 
00225                 rwlock_write_lock(&futex_ht_lock);
00226                 /*
00227                  * Avoid possible race condition by searching
00228                  * the hash table once again with write access.
00229                  */
00230                 item = hash_table_find(&futex_ht, &paddr);
00231                 if (item) {
00232                         futex = hash_table_get_instance(item, futex_t, ht_link);
00233                         
00234                         /*
00235                          * See if this futex is known to the current task.
00236                          */
00237                         mutex_lock(&TASK->futexes_lock);
00238                         if (!btree_search(&TASK->futexes, paddr, &leaf)) {
00239                                 /*
00240                                  * The futex is new to the current task.
00241                                  * Upgrade its reference count and put it to the
00242                                  * current task's B+tree of known futexes.
00243                                  */
00244                                 futex->refcount++;
00245                                 btree_insert(&TASK->futexes, paddr, futex, leaf);
00246                         }
00247                         mutex_unlock(&TASK->futexes_lock);
00248         
00249                         rwlock_write_unlock(&futex_ht_lock);
00250                 } else {
00251                         futex = (futex_t *) malloc(sizeof(futex_t), 0);
00252                         futex_initialize(futex);
00253                         futex->paddr = paddr;
00254                         hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
00255                         
00256                         /*
00257                          * This is the first task referencing the futex.
00258                          * It can be directly inserted into its
00259                          * B+tree of known futexes.
00260                          */
00261                         mutex_lock(&TASK->futexes_lock);
00262                         btree_insert(&TASK->futexes, paddr, futex, NULL);
00263                         mutex_unlock(&TASK->futexes_lock);
00264                         
00265                         rwlock_write_unlock(&futex_ht_lock);
00266                 }
00267         }
00268         
00269         return futex;
00270 }
00271 
00278 index_t futex_ht_hash(__native *key)
00279 {
00280         return *key & (FUTEX_HT_SIZE-1);
00281 }
00282 
00289 bool futex_ht_compare(__native *key, count_t keys, link_t *item)
00290 {
00291         futex_t *futex;
00292 
00293         ASSERT(keys == 1);
00294 
00295         futex = hash_table_get_instance(item, futex_t, ht_link);
00296         return *key == futex->paddr;
00297 }
00298 
00303 void futex_ht_remove_callback(link_t *item)
00304 {
00305         futex_t *futex;
00306 
00307         futex = hash_table_get_instance(item, futex_t, ht_link);
00308         free(futex);
00309 }
00310 
00312 void futex_cleanup(void)
00313 {
00314         link_t *cur;
00315         
00316         rwlock_write_lock(&futex_ht_lock);
00317         mutex_lock(&TASK->futexes_lock);
00318 
00319         for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {
00320                 btree_node_t *node;
00321                 int i;
00322                 
00323                 node = list_get_instance(cur, btree_node_t, leaf_link);
00324                 for (i = 0; i < node->keys; i++) {
00325                         futex_t *ftx;
00326                         __address paddr = node->key[i];
00327                         
00328                         ftx = (futex_t *) node->value[i];
00329                         if (--ftx->refcount == 0)
00330                                 hash_table_remove(&futex_ht, &paddr, 1);
00331                 }
00332         }
00333         
00334         mutex_unlock(&TASK->futexes_lock);
00335         rwlock_write_unlock(&futex_ht_lock);
00336 }
00337 

Generated on Sun Jun 18 17:17:05 2006 for HelenOS Kernel (ppc32) by  doxygen 1.4.6