Subversion Repositories HelenOS-historic

Rev

Rev 1583 | Rev 1702 | 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. /**
  30.  * @file    futex.c
  31.  * @brief   Kernel backend for futexes.
  32.  */
  33.  
  34. #include <synch/futex.h>
  35. #include <synch/rwlock.h>
  36. #include <synch/spinlock.h>
  37. #include <synch/synch.h>
  38. #include <mm/frame.h>
  39. #include <mm/page.h>
  40. #include <mm/slab.h>
  41. #include <proc/thread.h>
  42. #include <proc/task.h>
  43. #include <genarch/mm/page_pt.h>
  44. #include <genarch/mm/page_ht.h>
  45. #include <adt/hash_table.h>
  46. #include <adt/list.h>
  47. #include <arch.h>
  48. #include <align.h>
  49. #include <panic.h>
  50. #include <errno.h>
  51. #include <print.h>
  52.  
  53. #define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
  54.  
  55. static void futex_initialize(futex_t *futex);
  56.  
  57. static futex_t *futex_find(__address paddr);
  58. static index_t futex_ht_hash(__native *key);
  59. static bool futex_ht_compare(__native *key, count_t keys, link_t *item);
  60. static void futex_ht_remove_callback(link_t *item);
  61.  
  62. /**
  63.  * Read-write lock protecting global futex hash table.
  64.  * It is also used to serialize access to all futex_t structures.
  65.  * Must be acquired before the task futex B+tree lock.
  66.  */
  67. static rwlock_t futex_ht_lock;
  68.  
  69. /** Futex hash table. */
  70. static hash_table_t futex_ht;
  71.  
  72. /** Futex hash table operations. */
  73. static hash_table_operations_t futex_ht_ops = {
  74.     .hash = futex_ht_hash,
  75.     .compare = futex_ht_compare,
  76.     .remove_callback = futex_ht_remove_callback
  77. };
  78.  
  79. /** Initialize futex subsystem. */
  80. void futex_init(void)
  81. {
  82.     rwlock_initialize(&futex_ht_lock);
  83.     hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
  84. }
  85.  
  86. /** Initialize kernel futex structure.
  87.  *
  88.  * @param futex Kernel futex structure.
  89.  */
  90. void futex_initialize(futex_t *futex)
  91. {
  92.     waitq_initialize(&futex->wq);
  93.     link_initialize(&futex->ht_link);
  94.     futex->paddr = 0;
  95.     futex->refcount = 1;
  96. }
  97.  
  98. /** Sleep in futex wait queue.
  99.  *
  100.  * @param uaddr Userspace address of the futex counter.
  101.  * @param usec If non-zero, number of microseconds this thread is willing to sleep.
  102.  * @param flags Select mode of operation.
  103.  *
  104.  * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See synch.h.
  105.  *     If there is no physical mapping for uaddr ENOENT is returned.
  106.  */
  107. __native sys_futex_sleep_timeout(__address uaddr, __u32 usec, int flags)
  108. {
  109.     futex_t *futex;
  110.     __address paddr;
  111.     pte_t *t;
  112.     ipl_t ipl;
  113.    
  114.     ipl = interrupts_disable();
  115.  
  116.     /*
  117.      * Find physical address of futex counter.
  118.      */
  119.     page_table_lock(AS, true);
  120.     t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
  121.     if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
  122.         page_table_unlock(AS, true);
  123.         interrupts_restore(ipl);
  124.         return (__native) ENOENT;
  125.     }
  126.     paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
  127.     page_table_unlock(AS, true);
  128.    
  129.     interrupts_restore(ipl);   
  130.  
  131.     futex = futex_find(paddr);
  132.    
  133.     return (__native) waitq_sleep_timeout(&futex->wq, usec, flags | SYNCH_FLAGS_INTERRUPTIBLE);
  134. }
  135.  
  136. /** Wakeup one thread waiting in futex wait queue.
  137.  *
  138.  * @param uaddr Userspace address of the futex counter.
  139.  *
  140.  * @return ENOENT if there is no physical mapping for uaddr.
  141.  */
  142. __native sys_futex_wakeup(__address uaddr)
  143. {
  144.     futex_t *futex;
  145.     __address paddr;
  146.     pte_t *t;
  147.     ipl_t ipl;
  148.    
  149.     ipl = interrupts_disable();
  150.    
  151.     /*
  152.      * Find physical address of futex counter.
  153.      */
  154.     page_table_lock(AS, true);
  155.     t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE));
  156.     if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
  157.         page_table_unlock(AS, true);
  158.         interrupts_restore(ipl);
  159.         return (__native) ENOENT;
  160.     }
  161.     paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
  162.     page_table_unlock(AS, true);
  163.    
  164.     interrupts_restore(ipl);
  165.  
  166.     futex = futex_find(paddr);
  167.        
  168.     waitq_wakeup(&futex->wq, WAKEUP_FIRST);
  169.    
  170.     return 0;
  171. }
  172.  
  173. /** Find kernel address of the futex structure corresponding to paddr.
  174.  *
  175.  * If the structure does not exist already, a new one is created.
  176.  *
  177.  * @param paddr Physical address of the userspace futex counter.
  178.  *
  179.  * @return Address of the kernel futex structure.
  180.  */
  181. futex_t *futex_find(__address paddr)
  182. {
  183.     link_t *item;
  184.     futex_t *futex;
  185.     btree_node_t *leaf;
  186.    
  187.     /*
  188.      * Find the respective futex structure
  189.      * or allocate new one if it does not exist already.
  190.      */
  191.     rwlock_read_lock(&futex_ht_lock);
  192.     item = hash_table_find(&futex_ht, &paddr);
  193.     if (item) {
  194.         futex = hash_table_get_instance(item, futex_t, ht_link);
  195.  
  196.         /*
  197.          * See if the current task knows this futex.
  198.          */
  199.         mutex_lock(&TASK->futexes_lock);
  200.         if (!btree_search(&TASK->futexes, paddr, &leaf)) {
  201.             /*
  202.              * The futex is new to the current task.
  203.              * However, we only have read access.
  204.              * Gain write access and try again.
  205.              */
  206.             mutex_unlock(&TASK->futexes_lock);
  207.             goto gain_write_access;
  208.         }
  209.         mutex_unlock(&TASK->futexes_lock);
  210.  
  211.         rwlock_read_unlock(&futex_ht_lock);
  212.     } else {
  213. gain_write_access:
  214.         /*
  215.          * Upgrade to writer is not currently supported,
  216.          * therefore, it is necessary to release the read lock
  217.          * and reacquire it as a writer.
  218.          */
  219.         rwlock_read_unlock(&futex_ht_lock);
  220.  
  221.         rwlock_write_lock(&futex_ht_lock);
  222.         /*
  223.          * Avoid possible race condition by searching
  224.          * the hash table once again with write access.
  225.          */
  226.         item = hash_table_find(&futex_ht, &paddr);
  227.         if (item) {
  228.             futex = hash_table_get_instance(item, futex_t, ht_link);
  229.            
  230.             /*
  231.              * See if this futex is known to the current task.
  232.              */
  233.             mutex_lock(&TASK->futexes_lock);
  234.             if (!btree_search(&TASK->futexes, paddr, &leaf)) {
  235.                 /*
  236.                  * The futex is new to the current task.
  237.                  * Upgrade its reference count and put it to the
  238.                  * current task's B+tree of known futexes.
  239.                  */
  240.                 futex->refcount++;
  241.                 btree_insert(&TASK->futexes, paddr, futex, leaf);
  242.             }
  243.             mutex_unlock(&TASK->futexes_lock);
  244.    
  245.             rwlock_write_unlock(&futex_ht_lock);
  246.         } else {
  247.             futex = (futex_t *) malloc(sizeof(futex_t), 0);
  248.             futex_initialize(futex);
  249.             futex->paddr = paddr;
  250.             hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
  251.            
  252.             /*
  253.              * This is the first task referencing the futex.
  254.              * It can be directly inserted into its
  255.              * B+tree of known futexes.
  256.              */
  257.             mutex_lock(&TASK->futexes_lock);
  258.             btree_insert(&TASK->futexes, paddr, futex, NULL);
  259.             mutex_unlock(&TASK->futexes_lock);
  260.            
  261.             rwlock_write_unlock(&futex_ht_lock);
  262.         }
  263.     }
  264.    
  265.     return futex;
  266. }
  267.  
  268. /** Compute hash index into futex hash table.
  269.  *
  270.  * @param key Address where the key (i.e. physical address of futex counter) is stored.
  271.  *
  272.  * @return Index into futex hash table.
  273.  */
  274. index_t futex_ht_hash(__native *key)
  275. {
  276.     return *key & (FUTEX_HT_SIZE-1);
  277. }
  278.  
  279. /** Compare futex hash table item with a key.
  280.  *
  281.  * @param key Address where the key (i.e. physical address of futex counter) is stored.
  282.  *
  283.  * @return True if the item matches the key. False otherwise.
  284.  */
  285. bool futex_ht_compare(__native *key, count_t keys, link_t *item)
  286. {
  287.     futex_t *futex;
  288.  
  289.     ASSERT(keys == 1);
  290.  
  291.     futex = hash_table_get_instance(item, futex_t, ht_link);
  292.     return *key == futex->paddr;
  293. }
  294.  
  295. /** Callback for removal items from futex hash table.
  296.  *
  297.  * @param item Item removed from the hash table.
  298.  */
  299. void futex_ht_remove_callback(link_t *item)
  300. {
  301.     futex_t *futex;
  302.  
  303.     futex = hash_table_get_instance(item, futex_t, ht_link);
  304.     free(futex);
  305. }
  306.  
  307. /** Remove references from futexes known to the current task. */
  308. void futex_cleanup(void)
  309. {
  310.     link_t *cur;
  311.    
  312.     rwlock_write_lock(&futex_ht_lock);
  313.     mutex_lock(&TASK->futexes_lock);
  314.  
  315.     for (cur = TASK->futexes.leaf_head.next; cur != &TASK->futexes.leaf_head; cur = cur->next) {
  316.         btree_node_t *node;
  317.         int i;
  318.        
  319.         node = list_get_instance(cur, btree_node_t, leaf_link);
  320.         for (i = 0; i < node->keys; i++) {
  321.             futex_t *ftx;
  322.             __address paddr = node->key[i];
  323.            
  324.             ftx = (futex_t *) node->value[i];
  325.             if (--ftx->refcount == 0)
  326.                 hash_table_remove(&futex_ht, &paddr, 1);
  327.         }
  328.     }
  329.    
  330.     mutex_unlock(&TASK->futexes_lock);
  331.     rwlock_write_unlock(&futex_ht_lock);
  332. }
  333.