Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/synch/futex.c

    r3ac5086 r9d58539  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
    3  * Copyright (c) 2012 Adam Hraska
    43 * All rights reserved.
    54 *
    … …  
    3534 * @file
    3635 * @brief       Kernel backend for futexes.
    37  *
    38  * Kernel futex objects are stored in a global hash table futex_ht
    39  * where the physical address of the futex variable (futex_t.paddr)
    40  * is used as the lookup key. As a result multiple address spaces
    41  * may share the same futex variable.
    42  *
    43  * A kernel futex object is created the first time a task accesses
    44  * the futex (having a futex variable at a physical address not
    45  * encountered before). Futex object's lifetime is governed by
    46  * a reference count that represents the number of all the different
    47  * user space virtual addresses from all tasks that map to the
    48  * physical address of the futex variable. A futex object is freed
    49  * when the last task having accessed the futex exits.
    50  *
    51  * Each task keeps track of the futex objects it accessed in a list
    52  * of pointers (futex_ptr_t, task->futex_list) to the different futex
    53  * objects.
    54  *
    55  * To speed up translation of futex variables' virtual addresses
    56  * to their physical addresses, futex pointers accessed by the
    57  * task are furthermore stored in a concurrent hash table (CHT,
    58  * task->futexes->ht). A single lookup without locks or accesses
    59  * to the page table translates a futex variable's virtual address
    60  * into its futex kernel object.
    6136 */
    6237
    … …  
    6439#include <synch/mutex.h>
    6540#include <synch/spinlock.h>
    66 #include <synch/rcu.h>
    6741#include <mm/frame.h>
    6842#include <mm/page.h>
    … …  
    7246#include <genarch/mm/page_pt.h>
    7347#include <genarch/mm/page_ht.h>
    74 #include <adt/cht.h>
    7548#include <adt/hash_table.h>
    7649#include <adt/list.h>
    … …  
    7952#include <panic.h>
    8053#include <errno.h>
     54#include <print.h>
    8155
    8256#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
    8357
    84 /** Task specific pointer to a global kernel futex object. */
    85 typedef struct futex_ptr {
    86         /** CHT link. */
    87         cht_link_t cht_link;
    88         /** List of all futex pointers used by the task. */
    89         link_t all_link;
    90         /** Kernel futex object. */
    91         futex_t *futex;
    92         /** User space virtual address of the futex variable in the task. */
    93         uintptr_t uaddr;
    94 } futex_ptr_t;
    95 
    96 
    97 static void destroy_task_cache(work_t *work);
    98 
    99 static void futex_initialize(futex_t *futex, uintptr_t paddr);
    100 static void futex_add_ref(futex_t *futex);
    101 static void futex_release_ref(futex_t *futex);
    102 static void futex_release_ref_locked(futex_t *futex);
    103 
    104 static futex_t *get_futex(uintptr_t uaddr);
    105 static futex_t *find_cached_futex(uintptr_t uaddr);
    106 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr);
    107 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
    108 
     58static void futex_initialize(futex_t *futex);
     59
     60static futex_t *futex_find(uintptr_t paddr);
    10961static size_t futex_ht_hash(sysarg_t *key);
    11062static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
    11163static void futex_ht_remove_callback(link_t *item);
    11264
    113 static size_t task_fut_ht_hash(const cht_link_t *link);
    114 static size_t task_fut_ht_key_hash(void *key);
    115 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2);
    116 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item);
    117 
    118 
    119 /** Mutex protecting the global futex hash table.
    120  *
    121  * Acquire task specific TASK->futex_list_lock before this mutex.
     65/**
     66 * Mutex protecting global futex hash table.
     67 * It is also used to serialize access to all futex_t structures.
     68 * Must be acquired before the task futex B+tree lock.
    12269 */
    12370static mutex_t futex_ht_lock;
    12471
    125 /** Global kernel futex hash table. Lock futex_ht_lock before accessing.
    126  *
    127  * Physical address of the futex variable is the lookup key.
    128  */
     72/** Futex hash table. */
    12973static hash_table_t futex_ht;
    13074
    131 /** Global kernel futex hash table operations. */
     75/** Futex hash table operations. */
    13276static hash_table_operations_t futex_ht_ops = {
    13377        .hash = futex_ht_hash,
    … …  
    13680};
    13781
    138 /** Task futex cache CHT operations. */
    139 static cht_ops_t task_futex_ht_ops = {
    140         .hash = task_fut_ht_hash,
    141         .key_hash = task_fut_ht_key_hash,
    142         .equal = task_fut_ht_equal,
    143         .key_equal = task_fut_ht_key_equal,
    144         .remove_callback = NULL
    145 };
    146 
    14782/** Initialize futex subsystem. */
    14883void futex_init(void)
    … …  
    15287}
    15388
    154 /** Initializes the futex structures for the new task. */
    155 void futex_task_init(struct task *task)
    156 {
    157         task->futexes = malloc(sizeof(struct futex_cache), 0);
    158        
    159         cht_create(&task->futexes->ht, 0, 0, 0, true, &task_futex_ht_ops);
    160        
    161         list_initialize(&task->futexes->list);
    162         mutex_initialize(&task->futexes->list_lock, MUTEX_PASSIVE);
    163 }
    164 
    165 /** Destroys the futex structures for the dying task. */
    166 void futex_task_deinit(task_t *task)
    167 {
    168         /* Interrupts are disabled so we must not block (cannot run cht_destroy). */
    169         if (interrupts_disabled()) {
    170                 /* Invoke the blocking cht_destroy in the background. */
    171                 workq_global_enqueue_noblock(&task->futexes->destroy_work,
    172                         destroy_task_cache);
    173         } else {
    174                 /* We can block. Invoke cht_destroy in this thread. */
    175                 destroy_task_cache(&task->futexes->destroy_work);
    176         }
    177 }
    178 
    179 /** Deallocates a task's CHT futex cache (must already be empty). */
    180 static void destroy_task_cache(work_t *work)
    181 {
    182         struct futex_cache *cache =
    183                 member_to_inst(work, struct futex_cache, destroy_work);
    184        
    185         /*
    186          * Destroy the cache before manually freeing items of the cache in case
    187          * table resize is in progress.
    188          */
    189         cht_destroy_unsafe(&cache->ht);
    190        
    191         /* Manually free futex_ptr cache items. */
    192         list_foreach_safe(cache->list, cur_link, next_link) {
    193                 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
    194 
    195                 list_remove(cur_link);
    196                 free(fut_ptr);
    197         }
    198        
    199         free(cache);
    200 }
    201 
    202 /** Remove references from futexes known to the current task. */
    203 void futex_task_cleanup(void)
    204 {
    205         struct futex_cache *futexes = TASK->futexes;
    206        
    207         /* All threads of this task have terminated. This is the last thread. */
    208         mutex_lock(&futexes->list_lock);
    209        
    210         list_foreach_safe(futexes->list, cur_link, next_link) {
    211                 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
    212 
    213                 /*
    214                  * The function is free to free the futex. All other threads of this
    215                  * task have already terminated, so they have also definitely
    216                  * exited their CHT futex cache protecting rcu reader sections.
    217                  * Moreover release_ref() only frees the futex if this is the
    218                  * last task referencing the futex. Therefore, only threads
    219                  * of this task may have referenced the futex if it is to be freed.
    220                  */
    221                 futex_release_ref_locked(fut_ptr->futex);
    222         }
    223        
    224         mutex_unlock(&futexes->list_lock);
    225 }
    226 
    227 
    228 /** Initialize the kernel futex structure.
    229  *
    230  * @param futex Kernel futex structure.
    231  * @param paddr Physical address of the futex variable.
    232  */
    233 static void futex_initialize(futex_t *futex, uintptr_t paddr)
     89/** Initialize kernel futex structure.
     90 *
     91 * @param futex         Kernel futex structure.
     92 */
     93void futex_initialize(futex_t *futex)
    23494{
    23595        waitq_initialize(&futex->wq);
    23696        link_initialize(&futex->ht_link);
    237         futex->paddr = paddr;
     97        futex->paddr = 0;
    23898        futex->refcount = 1;
    239 }
    240 
    241 /** Increments the counter of tasks referencing the futex. */
    242 static void futex_add_ref(futex_t *futex)
    243 {
    244         ASSERT(mutex_locked(&futex_ht_lock));
    245         ASSERT(0 < futex->refcount);
    246         ++futex->refcount;
    247 }
    248 
    249 /** Decrements the counter of tasks referencing the futex. May free the futex.*/
    250 static void futex_release_ref(futex_t *futex)
    251 {
    252         ASSERT(mutex_locked(&futex_ht_lock));
    253         ASSERT(0 < futex->refcount);
    254        
    255         --futex->refcount;
    256        
    257         if (0 == futex->refcount) {
    258                 hash_table_remove(&futex_ht, &futex->paddr, 1);
    259         }
    260 }
    261 
    262 /** Decrements the counter of tasks referencing the futex. May free the futex.*/
    263 static void futex_release_ref_locked(futex_t *futex)
    264 {
    265         mutex_lock(&futex_ht_lock);
    266         futex_release_ref(futex);
    267         mutex_unlock(&futex_ht_lock);
    268 }
    269 
    270 /** Returns a futex for the virtual address @a uaddr (or creates one). */
    271 static futex_t *get_futex(uintptr_t uaddr)
    272 {
    273         futex_t *futex = find_cached_futex(uaddr);
    274        
    275         if (futex)
    276                 return futex;
    277 
    278         uintptr_t paddr;
    279 
    280         if (!find_futex_paddr(uaddr, &paddr))
    281                 return 0;
    282 
    283         return get_and_cache_futex(paddr, uaddr);
    284 }
    285 
    286 
    287 /** Finds the physical address of the futex variable. */
    288 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *paddr)
    289 {
    290         page_table_lock(AS, true);
    291 
    292         bool found = false;
    293         pte_t *t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false);
    294        
    295         if (t && PTE_VALID(t) && PTE_PRESENT(t)) {
    296                 found = true;
    297                 *paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    298         }
    299        
    300         page_table_unlock(AS, true);
    301        
    302         return found;
    303 }
    304 
    305 /** Returns the futex cached in this task with the virtual address uaddr. */
    306 static futex_t *find_cached_futex(uintptr_t uaddr)
    307 {
    308         cht_read_lock();
    309        
    310         futex_t *futex;
    311         cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);
    312 
    313         if (futex_ptr_link) {
    314                 futex_ptr_t *futex_ptr
    315                         = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
    316                
    317                 futex = futex_ptr->futex;
    318         } else {
    319                 futex = NULL;
    320         }
    321        
    322         cht_read_unlock();
    323        
    324         return futex;
    325 }
    326 
    327 
    328 /**
    329  * Returns a kernel futex for the physical address @a phys_addr and caches
    330  * it in this task under the virtual address @a uaddr (if not already cached).
    331  */
    332 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr)
    333 {
    334         futex_t *futex = malloc(sizeof(futex_t), 0);
    335        
    336         /*
    337          * Find the futex object in the global futex table (or insert it
    338          * if it is not present).
    339          */
    340         mutex_lock(&futex_ht_lock);
    341        
    342         link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
    343        
    344         if (fut_link) {
    345                 free(futex);
    346                 futex = member_to_inst(fut_link, futex_t, ht_link);
    347                 futex_add_ref(futex);
    348         } else {
    349                 futex_initialize(futex, phys_addr);
    350                 hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
    351         }
    352        
    353         mutex_unlock(&futex_ht_lock);
    354        
    355         /*
    356          * Cache the link to the futex object for this task.
    357          */
    358         futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0);
    359         cht_link_t *dup_link;
    360        
    361         fut_ptr->futex = futex;
    362         fut_ptr->uaddr = uaddr;
    363        
    364         cht_read_lock();
    365        
    366         /* Cache the mapping from the virtual address to the futex for this task. */
    367         if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
    368                 mutex_lock(&TASK->futexes->list_lock);
    369                 list_append(&fut_ptr->all_link, &TASK->futexes->list);
    370                 mutex_unlock(&TASK->futexes->list_lock);
    371         } else {
    372                 /* Another thread of this task beat us to it. Use that mapping instead.*/
    373                 free(fut_ptr);
    374                 futex_release_ref_locked(futex);
    375                
    376                 futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
    377                 futex = dup->futex;             
    378         }
    379 
    380         cht_read_unlock();
    381        
    382         return futex;
    38399}
    384100
    … …  
    393109sysarg_t sys_futex_sleep(uintptr_t uaddr)
    394110{
    395         futex_t *futex = get_futex(uaddr);
    396        
    397         if (!futex)
     111        futex_t *futex;
     112        uintptr_t paddr;
     113        pte_t *t;
     114        int rc;
     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), false);
     121        if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
     122                page_table_unlock(AS, true);
    398123                return (sysarg_t) ENOENT;
     124        }
     125        paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
     126        page_table_unlock(AS, true);
     127       
     128        futex = futex_find(paddr);
    399129
    400130#ifdef CONFIG_UDEBUG
    401131        udebug_stoppable_begin();
    402132#endif
    403         int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
     133        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    404134#ifdef CONFIG_UDEBUG
    405135        udebug_stoppable_end();
    … …  
    416146sysarg_t sys_futex_wakeup(uintptr_t uaddr)
    417147{
    418         futex_t *futex = get_futex(uaddr);
    419        
    420         if (futex) {
    421                 waitq_wakeup(&futex->wq, WAKEUP_FIRST);
    422                 return 0;
     148        futex_t *futex;
     149        uintptr_t paddr;
     150        pte_t *t;
     151       
     152        /*
     153         * Find physical address of futex counter.
     154         */
     155        page_table_lock(AS, true);
     156        t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false);
     157        if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
     158                page_table_unlock(AS, true);
     159                return (sysarg_t) ENOENT;
     160        }
     161        paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
     162        page_table_unlock(AS, true);
     163       
     164        futex = futex_find(paddr);
     165               
     166        waitq_wakeup(&futex->wq, WAKEUP_FIRST);
     167       
     168        return 0;
     169}
     170
     171/** Find kernel address of the futex structure corresponding to paddr.
     172 *
     173 * If the structure does not exist already, a new one is created.
     174 *
     175 * @param paddr         Physical address of the userspace futex counter.
     176 *
     177 * @return              Address of the kernel futex structure.
     178 */
     179futex_t *futex_find(uintptr_t paddr)
     180{
     181        link_t *item;
     182        futex_t *futex;
     183        btree_node_t *leaf;
     184       
     185        /*
     186         * Find the respective futex structure
     187         * or allocate new one if it does not exist already.
     188         */
     189        mutex_lock(&futex_ht_lock);
     190        item = hash_table_find(&futex_ht, &paddr);
     191        if (item) {
     192                futex = hash_table_get_instance(item, futex_t, ht_link);
     193
     194                /*
     195                 * See if the current task knows this futex.
     196                 */
     197                mutex_lock(&TASK->futexes_lock);
     198                if (!btree_search(&TASK->futexes, paddr, &leaf)) {
     199                        /*
     200                         * The futex is new to the current task.
     201                         * Upgrade its reference count and put it to the
     202                         * current task's B+tree of known futexes.
     203                         */
     204                        futex->refcount++;
     205                        btree_insert(&TASK->futexes, paddr, futex, leaf);
     206                }
     207                mutex_unlock(&TASK->futexes_lock);
    423208        } else {
    424                 return (sysarg_t) ENOENT;
    425         }
    426 }
    427 
     209                futex = (futex_t *) malloc(sizeof(futex_t), 0);
     210                futex_initialize(futex);
     211                futex->paddr = paddr;
     212                hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
     213                       
     214                /*
     215                 * This is the first task referencing the futex.
     216                 * It can be directly inserted into its
     217                 * B+tree of known futexes.
     218                 */
     219                mutex_lock(&TASK->futexes_lock);
     220                btree_insert(&TASK->futexes, paddr, futex, NULL);
     221                mutex_unlock(&TASK->futexes_lock);
     222               
     223        }
     224        mutex_unlock(&futex_ht_lock);
     225       
     226        return futex;
     227}
    428228
    429229/** Compute hash index into futex hash table.
    … …  
    468268}
    469269
    470 /*
    471  * Operations of a task's CHT that caches mappings of futex user space
    472  * virtual addresses to kernel futex objects.
    473  */
    474 
    475 static size_t task_fut_ht_hash(const cht_link_t *link)
    476 {
    477         const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link);
    478         return fut_ptr->uaddr;
    479 }
    480 
    481 static size_t task_fut_ht_key_hash(void *key)
    482 {
    483         return *(uintptr_t*)key;
    484 }
    485 
    486 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2)
    487 {
    488         const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link);
    489         const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link);
    490        
    491         return fut_ptr1->uaddr == fut_ptr2->uaddr;
    492 }
    493 
    494 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item)
    495 {
    496         const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link);
    497         uintptr_t uaddr = *(uintptr_t*)key;
    498        
    499         return fut_ptr->uaddr == uaddr;
    500 }
    501 
     270/** Remove references from futexes known to the current task. */
     271void futex_cleanup(void)
     272{
     273        mutex_lock(&futex_ht_lock);
     274        mutex_lock(&TASK->futexes_lock);
     275
     276        list_foreach(TASK->futexes.leaf_list, cur) {
     277                btree_node_t *node;
     278                unsigned int i;
     279               
     280                node = list_get_instance(cur, btree_node_t, leaf_link);
     281                for (i = 0; i < node->keys; i++) {
     282                        futex_t *ftx;
     283                        uintptr_t paddr = node->key[i];
     284                       
     285                        ftx = (futex_t *) node->value[i];
     286                        if (--ftx->refcount == 0)
     287                                hash_table_remove(&futex_ht, &paddr, 1);
     288                }
     289        }
     290       
     291        mutex_unlock(&TASK->futexes_lock);
     292        mutex_unlock(&futex_ht_lock);
     293}
    502294
    503295/** @}
Note: See TracChangeset for help on using the changeset viewer.