Subversion Repositories HelenOS

Rev

Rev 1787 | Rev 2745 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2006 Jakub Jermar
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup sync
  30.  * @{
  31.  */
  32.  
  33. /**
  34.  * @file
  35.  * @brief   Kernel backend for futexes.
  36.  */
  37.  
  38. #include <synch/futex.h>
  39. #include <synch/rwlock.h>
  40. #include <synch/spinlock.h>
  41. #include <synch/synch.h>
  42. #include <mm/frame.h>
  43. #include <mm/page.h>
  44. #include <mm/slab.h>
  45. #include <proc/thread.h>
  46. #include <proc/task.h>
  47. #include <genarch/mm/page_pt.h>
  48. #include <genarch/mm/page_ht.h>
  49. #include <adt/hash_table.h>
  50. #include <adt/list.h>
  51. #include <arch.h>
  52. #include <align.h>
  53. #include <panic.h>
  54. #include <errno.h>
  55. #include <print.h>
  56.  
  57. #define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
  58.  
  59. static void futex_initialize(futex_t *futex);
  60.  
  61. static futex_t *futex_find(uintptr_t paddr);
  62. static index_t futex_ht_hash(unative_t *key);
  63. static bool futex_ht_compare(unative_t *key, count_t keys, link_t *item);
  64. static void futex_ht_remove_callback(link_t *item);
  65.  
  66. /**
  67.  * Read-write lock protecting global futex hash table.
  68.  * It is also used to serialize access to all futex_t structures.
  69.  * Must be acquired before the task futex B+tree lock.
  70.  */
  71. static rwlock_t futex_ht_lock;
  72.  
  73. /** Futex hash table. */
  74. static hash_table_t futex_ht;
  75.  
  76. /** Futex hash table operations. */
  77. static hash_table_operations_t futex_ht_ops = {
  78.     .hash = futex_ht_hash,
  79.     .compare = futex_ht_compare,
  80.     .remove_callback = futex_ht_remove_callback
  81. };
  82.  
  83. /** Initialize futex subsystem. */
  84. void futex_init(void)
  85. {
  86.     rwlock_initialize(&futex_ht_lock);
  87.     hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
  88. }
  89.  
  90. /** Initialize kernel futex structure.
  91.  *
  92.  * @param futex Kernel futex structure.
  93.  */
  94. void futex_initialize(futex_t *futex)
  95. {
  96.     waitq_initialize(&futex->wq);
  97.     link_initialize(&futex->ht_link);
  98.     futex->paddr = 0;
  99.     futex->refcount = 1;
  100. }
  101.  
  102. /** Sleep in futex wait queue.
  103.  *
  104.  * @param uaddr Userspace address of the futex counter.
  105.  * @param usec If non-zero, number of microseconds this thread is willing to sleep.
  106.  * @param flags Select mode of operation.
  107.  *
  108.  * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
  109.  *     If there is no physical mapping for uaddr ENOENT is returned.
  110.  */
  111. unative_t sys_futex_sleep_timeout(uintptr_t uaddr, uint32_t usec, int flags)
  112. {
  113.     futex_t *futex;
  114.     uintptr_t paddr;
  115.     pte_t *t;
  116.     ipl_t ipl;
  117.    
  118.     ipl = interrupts_disable();
  119.  
  120.     /*
  121.      * Find physical address of futex counter.
  122.      */
  123.     page_table_lock(AS, true);
  124.     t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
  125.     if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
  126.         page_table_unlock(AS, true);
  127.         interrupts_restore(ipl);
  128.         return (unative_t) ENOENT;
  129.     }
  130.     paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
  131.     page_table_unlock(AS, true);
  132.    
  133.     interrupts_restore(ipl);   
  134.  
  135.     futex = futex_find(paddr);
  136.    
  137.     return (unative_t) waitq_sleep_timeout(&futex->wq, usec, flags | SYNCH_FLAGS_INTERRUPTIBLE);
  138. }
  139.  
  140. /** Wakeup one thread waiting in futex wait queue.
  141.  *
  142.  * @param uaddr Userspace address of the futex counter.
  143.  *
  144.  * @return ENOENT if there is no physical mapping for uaddr.
  145.  */
  146. unative_t sys_futex_wakeup(uintptr_t uaddr)
  147. {
  148.     futex_t *futex;
  149.     uintptr_t paddr;
  150.     pte_t *t;
  151.     ipl_t ipl;
  152.    
  153.     ipl = interrupts_disable();
  154.    
  155.     /*
  156.      * Find physical address of futex counter.
  157.      */
  158.     page_table_lock(AS, true);
  159.     t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
  160.     if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
  161.         page_table_unlock(AS, true);
  162.         interrupts_restore(ipl);
  163.         return (unative_t) ENOENT;
  164.     }
  165.     paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
  166.     page_table_unlock(AS, true);
  167.    
  168.     interrupts_restore(ipl);
  169.  
  170.     futex = futex_find(paddr);
  171.        
  172.     waitq_wakeup(&futex->wq, WAKEUP_FIRST);
  173.    
  174.     return 0;
  175. }
  176.  
  177. /** Find kernel address of the futex structure corresponding to paddr.
  178.  *
  179.  * If the structure does not exist already, a new one is created.
  180.  *
  181.  * @param paddr Physical address of the userspace futex counter.
  182.  *
  183.  * @return Address of the kernel futex structure.
  184.  */
  185. futex_t *futex_find(uintptr_t paddr)
  186. {
  187.     link_t *item;
  188.     futex_t *futex;
  189.     btree_node_t *leaf;
  190.    
  191.     /*
  192.      * Find the respective futex structure
  193.      * or allocate new one if it does not exist already.
  194.      */
  195.     rwlock_read_lock(&futex_ht_lock);
  196.     item = hash_table_find(&futex_ht, &paddr);
  197.     if (item) {
  198.         futex = hash_table_get_instance(item, futex_t, ht_link);
  199.  
  200.         /*
  201.          * See if the current task knows this futex.
  202.          */
  203.         mutex_lock(&TASK->futexes_lock);
  204.         if (!btree_search(&TASK->futexes, paddr, &leaf)) {
  205.             /*
  206.              * The futex is new to the current task.
  207.              * However, we only have read access.
  208.              * Gain write access and try again.
  209.              */
  210.             mutex_unlock(&TASK->futexes_lock);
  211.             goto gain_write_access;
  212.         }
  213.         mutex_unlock(&TASK->futexes_lock);
  214.  
  215.         rwlock_read_unlock(&futex_ht_lock);
  216.     } else {
  217. gain_write_access:
  218.         /*
  219.          * Upgrade to writer is not currently supported,
  220.          * therefore, it is necessary to release the read lock
  221.          * and reacquire it as a writer.
  222.          */
  223.         rwlock_read_unlock(&futex_ht_lock);
  224.  
  225.         rwlock_write_lock(&futex_ht_lock);
  226.         /*
  227.          * Avoid possible race condition by searching
  228.          * the hash table once again with write access.
  229.          */
  230.         item = hash_table_find(&futex_ht, &paddr);
  231.         if (item) {
  232.             futex = hash_table_get_instance(item, futex_t, ht_link);
  233.            
  234.             /*
  235.              * See if this futex is known to the current task.
  236.              */
  237.             mutex_lock(&TASK->futexes_lock);
  238.             if (!btree_search(&TASK->futexes, paddr, &leaf)) {
  239.                 /*
  240.                  * The futex is new to the current task.
  241.                  * Upgrade its reference count and put it to the
  242.                  * current task's B+tree of known futexes.
  243.                  */
  244.                 futex->refcount++;
  245.                 btree_insert(&TASK->futexes, paddr, futex, leaf);
  246.             }
  247.             mutex_unlock(&TASK->futexes_lock);
  248.    
  249.             rwlock_write_unlock(&futex_ht_lock);
  250.         } else {
  251.             futex = (futex_t *) malloc(sizeof(futex_t), 0);
  252.             futex_initialize(futex);
  253.             futex->paddr = paddr;
  254.             hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
  255.            
  256.             /*
  257.              * This is the first task referencing the futex.
  258.              * It can be directly inserted into its
  259.              * B+tree of known futexes.
  260.              */
  261.             mutex_lock(&TASK->futexes_lock);
  262.             btree_insert(&TASK->futexes, paddr, futex, NULL);
  263.             mutex_unlock(&TASK->futexes_lock);
  264.            
  265.             rwlock_write_unlock(&futex_ht_lock);
  266.         }
  267.     }
  268.    
  269.     return futex;
  270. }
  271.  
  272. /** Compute hash index into futex hash table.
  273.  *
  274.  * @param key Address where the key (i.e. physical address of futex counter) is stored.
  275.  *
  276.  * @return Index into futex hash table.
  277.  */
  278. index_t futex_ht_hash(unative_t *key)
  279. {
  280.     return *key & (FUTEX_HT_SIZE-1);
  281. }
  282.  
  283. /** Compare futex hash table item with a key.
  284.  *
  285.  * @param key Address where the key (i.e. physical address of futex counter) is stored.
  286.  *
  287.  * @return True if the item matches the key. False otherwise.
  288.  */
  289. bool futex_ht_compare(unative_t *key, count_t keys, link_t *item)
  290. {
  291.     futex_t *futex;
  292.  
  293.     ASSERT(keys == 1);
  294.  
  295.     futex = hash_table_get_instance(item, futex_t, ht_link);
  296.     return *key == futex->paddr;
  297. }
  298.  
  299. /** Callback for removal items from futex hash table.
  300.  *
  301.  * @param item Item removed from the hash table.
  302.  */
  303. void futex_ht_remove_callback(link_t *item)
  304. {
  305.     futex_t *futex;
  306.  
  307.     futex = hash_table_get_instance(item, futex_t, ht_link);
  308.     free(futex);
  309. }
  310.  
  311. /** Remove references from futexes known to the current task. */
  312. void futex_cleanup(void)
  313. {
  314.     link_t *cur;
  315.    
  316.     rwlock_write_lock(&futex_ht_lock);
  317.     mutex_lock(&TASK->futexes_lock);
  318.  
  319.     for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {
  320.         btree_node_t *node;
  321.         int i;
  322.        
  323.         node = list_get_instance(cur, btree_node_t, leaf_link);
  324.         for (i = 0; i < node->keys; i++) {
  325.             futex_t *ftx;
  326.             uintptr_t paddr = node->key[i];
  327.            
  328.             ftx = (futex_t *) node->value[i];
  329.             if (--ftx->refcount == 0)
  330.                 hash_table_remove(&futex_ht, &paddr, 1);
  331.         }
  332.     }
  333.    
  334.     mutex_unlock(&TASK->futexes_lock);
  335.     rwlock_write_unlock(&futex_ht_lock);
  336. }
  337.  
  338. /** @}
  339.  */
  340.