Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r38dc82d 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.
    122  */
    123 SPINLOCK_STATIC_INITIALIZE_NAME(futex_ht_lock, "futex-ht-lock");
    124 
    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  */
     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.
     69 */
     70static mutex_t futex_ht_lock;
     71
     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)
    14984{
     85        mutex_initialize(&futex_ht_lock, MUTEX_PASSIVE);
    15086        hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
    15187}
    15288
    153 /** Initializes the futex structures for the new task. */
    154 void futex_task_init(struct task *task)
    155 {
    156         task->futexes = malloc(sizeof(struct futex_cache), 0);
    157        
    158         cht_create(&task->futexes->ht, 0, 0, 0, true, &task_futex_ht_ops);
    159        
    160         list_initialize(&task->futexes->list);
    161         spinlock_initialize(&task->futexes->list_lock, "futex-list-lock");
    162 }
    163 
    164 /** Destroys the futex structures for the dying task. */
    165 void futex_task_deinit(task_t *task)
    166 {
    167         /* Interrupts are disabled so we must not block (cannot run cht_destroy). */
    168         if (interrupts_disabled()) {
    169                 /* Invoke the blocking cht_destroy in the background. */
    170                 workq_global_enqueue_noblock(&task->futexes->destroy_work,
    171                         destroy_task_cache);
    172         } else {
    173                 /* We can block. Invoke cht_destroy in this thread. */
    174                 destroy_task_cache(&task->futexes->destroy_work);
    175         }
    176 }
    177 
    178 /** Deallocates a task's CHT futex cache (must already be empty). */
    179 static void destroy_task_cache(work_t *work)
    180 {
    181         struct futex_cache *cache =
    182                 member_to_inst(work, struct futex_cache, destroy_work);
    183        
    184         /*
    185          * Destroy the cache before manually freeing items of the cache in case
    186          * table resize is in progress.
    187          */
    188         cht_destroy_unsafe(&cache->ht);
    189        
    190         /* Manually free futex_ptr cache items. */
    191         list_foreach_safe(cache->list, cur_link, next_link) {
    192                 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
    193 
    194                 list_remove(cur_link);
    195                 free(fut_ptr);
    196         }
    197        
    198         free(cache);
    199 }
    200 
    201 /** Remove references from futexes known to the current task. */
    202 void futex_task_cleanup(void)
    203 {
    204         struct futex_cache *futexes = TASK->futexes;
    205        
    206         /* All threads of this task have terminated. This is the last thread. */
    207         spinlock_lock(&futexes->list_lock);
    208        
    209         list_foreach_safe(futexes->list, cur_link, next_link) {
    210                 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
    211 
    212                 /*
    213                  * The function is free to free the futex. All other threads of this
    214                  * task have already terminated, so they have also definitely
    215                  * exited their CHT futex cache protecting rcu reader sections.
    216                  * Moreover release_ref() only frees the futex if this is the
    217                  * last task referencing the futex. Therefore, only threads
    218                  * of this task may have referenced the futex if it is to be freed.
    219                  */
    220                 futex_release_ref_locked(fut_ptr->futex);
    221         }
    222        
    223         spinlock_unlock(&futexes->list_lock);
    224 }
    225 
    226 
    227 /** Initialize the kernel futex structure.
    228  *
    229  * @param futex Kernel futex structure.
    230  * @param paddr Physical address of the futex variable.
    231  */
    232 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)
    23394{
    23495        waitq_initialize(&futex->wq);
    23596        link_initialize(&futex->ht_link);
    236         futex->paddr = paddr;
     97        futex->paddr = 0;
    23798        futex->refcount = 1;
    238 }
    239 
    240 /** Increments the counter of tasks referencing the futex. */
    241 static void futex_add_ref(futex_t *futex)
    242 {
    243         ASSERT(spinlock_locked(&futex_ht_lock));
    244         ASSERT(0 < futex->refcount);
    245         ++futex->refcount;
    246 }
    247 
    248 /** Decrements the counter of tasks referencing the futex. May free the futex.*/
    249 static void futex_release_ref(futex_t *futex)
    250 {
    251         ASSERT(spinlock_locked(&futex_ht_lock));
    252         ASSERT(0 < futex->refcount);
    253        
    254         --futex->refcount;
    255        
    256         if (0 == futex->refcount) {
    257                 hash_table_remove(&futex_ht, &futex->paddr, 1);
    258         }
    259 }
    260 
    261 /** Decrements the counter of tasks referencing the futex. May free the futex.*/
    262 static void futex_release_ref_locked(futex_t *futex)
    263 {
    264         spinlock_lock(&futex_ht_lock);
    265         futex_release_ref(futex);
    266         spinlock_unlock(&futex_ht_lock);
    267 }
    268 
    269 /** Returns a futex for the virtual address @a uaddr (or creates one). */
    270 static futex_t *get_futex(uintptr_t uaddr)
    271 {
    272         futex_t *futex = find_cached_futex(uaddr);
    273        
    274         if (futex)
    275                 return futex;
    276 
    277         uintptr_t paddr;
    278 
    279         if (!find_futex_paddr(uaddr, &paddr)) {
    280                 return 0;
    281         }
    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, false);
    291         spinlock_lock(&futex_ht_lock);
    292 
    293         bool success = false;
    294 
    295         pte_t t;
    296         bool found;
    297 
    298         found = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), true, &t);
    299         if (found && PTE_VALID(&t) && PTE_PRESENT(&t)) {
    300                 success = true;
    301                 *paddr = PTE_GET_FRAME(&t) +
    302                     (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    303         }
    304        
    305         spinlock_unlock(&futex_ht_lock);
    306         page_table_unlock(AS, false);
    307        
    308         return success;
    309 }
    310 
    311 /** Returns the futex cached in this task with the virtual address uaddr. */
    312 static futex_t *find_cached_futex(uintptr_t uaddr)
    313 {
    314         cht_read_lock();
    315        
    316         futex_t *futex;
    317         cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);
    318 
    319         if (futex_ptr_link) {
    320                 futex_ptr_t *futex_ptr
    321                         = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
    322                
    323                 futex = futex_ptr->futex;
    324         } else {
    325                 futex = NULL;
    326         }
    327        
    328         cht_read_unlock();
    329        
    330         return futex;
    331 }
    332 
    333 
    334 /**
    335  * Returns a kernel futex for the physical address @a phys_addr and caches
    336  * it in this task under the virtual address @a uaddr (if not already cached).
    337  */
    338 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr)
    339 {
    340         futex_t *futex = malloc(sizeof(futex_t), 0);
    341        
    342         /*
    343          * Find the futex object in the global futex table (or insert it
    344          * if it is not present).
    345          */
    346         spinlock_lock(&futex_ht_lock);
    347        
    348         link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
    349        
    350         if (fut_link) {
    351                 free(futex);
    352                 futex = member_to_inst(fut_link, futex_t, ht_link);
    353                 futex_add_ref(futex);
    354         } else {
    355                 futex_initialize(futex, phys_addr);
    356                 hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
    357         }
    358        
    359         spinlock_unlock(&futex_ht_lock);
    360        
    361         /*
    362          * Cache the link to the futex object for this task.
    363          */
    364         futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0);
    365         cht_link_t *dup_link;
    366        
    367         fut_ptr->futex = futex;
    368         fut_ptr->uaddr = uaddr;
    369        
    370         cht_read_lock();
    371        
    372         /* Cache the mapping from the virtual address to the futex for this task. */
    373         if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
    374                 spinlock_lock(&TASK->futexes->list_lock);
    375                 list_append(&fut_ptr->all_link, &TASK->futexes->list);
    376                 spinlock_unlock(&TASK->futexes->list_lock);
    377         } else {
    378                 /* Another thread of this task beat us to it. Use that mapping instead.*/
    379                 free(fut_ptr);
    380                 futex_release_ref_locked(futex);
    381                
    382                 futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
    383                 futex = dup->futex;             
    384         }
    385 
    386         cht_read_unlock();
    387        
    388         return futex;
    38999}
    390100
    … …  
    399109sysarg_t sys_futex_sleep(uintptr_t uaddr)
    400110{
    401         futex_t *futex = get_futex(uaddr);
    402        
    403         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);
    404123                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);
    405129
    406130#ifdef CONFIG_UDEBUG
    407131        udebug_stoppable_begin();
    408132#endif
    409 
    410         int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    411 
     133        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    412134#ifdef CONFIG_UDEBUG
    413135        udebug_stoppable_end();
    414136#endif
    415 
    416137        return (sysarg_t) rc;
    417138}
    … …  
    425146sysarg_t sys_futex_wakeup(uintptr_t uaddr)
    426147{
    427         futex_t *futex = get_futex(uaddr);
    428        
    429         if (futex) {
    430                 waitq_wakeup(&futex->wq, WAKEUP_FIRST);
    431                 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);
    432208        } else {
    433                 return (sysarg_t) ENOENT;
    434         }
    435 }
    436 
     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}
    437228
    438229/** Compute hash index into futex hash table.
    … …  
    477268}
    478269
    479 /*
    480  * Operations of a task's CHT that caches mappings of futex user space
    481  * virtual addresses to kernel futex objects.
    482  */
    483 
    484 static size_t task_fut_ht_hash(const cht_link_t *link)
    485 {
    486         const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link);
    487         return fut_ptr->uaddr;
    488 }
    489 
    490 static size_t task_fut_ht_key_hash(void *key)
    491 {
    492         return *(uintptr_t*)key;
    493 }
    494 
    495 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2)
    496 {
    497         const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link);
    498         const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link);
    499        
    500         return fut_ptr1->uaddr == fut_ptr2->uaddr;
    501 }
    502 
    503 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item)
    504 {
    505         const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link);
    506         uintptr_t uaddr = *(uintptr_t*)key;
    507        
    508         return fut_ptr->uaddr == uaddr;
     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);
    509293}
    510294
Note: See TracChangeset for help on using the changeset viewer.