Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/src/synch/futex.c

    r9d58539 r3ac5086  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
    34 * All rights reserved.
    45 *
     
    3435 * @file
    3536 * @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.
    3661 */
    3762
     
    3964#include <synch/mutex.h>
    4065#include <synch/spinlock.h>
     66#include <synch/rcu.h>
    4167#include <mm/frame.h>
    4268#include <mm/page.h>
     
    4672#include <genarch/mm/page_pt.h>
    4773#include <genarch/mm/page_ht.h>
     74#include <adt/cht.h>
    4875#include <adt/hash_table.h>
    4976#include <adt/list.h>
     
    5279#include <panic.h>
    5380#include <errno.h>
    54 #include <print.h>
    5581
    5682#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
    5783
    58 static void futex_initialize(futex_t *futex);
    59 
    60 static futex_t *futex_find(uintptr_t paddr);
     84/** Task specific pointer to a global kernel futex object. */
     85typedef 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
     97static void destroy_task_cache(work_t *work);
     98
     99static void futex_initialize(futex_t *futex, uintptr_t paddr);
     100static void futex_add_ref(futex_t *futex);
     101static void futex_release_ref(futex_t *futex);
     102static void futex_release_ref_locked(futex_t *futex);
     103
     104static futex_t *get_futex(uintptr_t uaddr);
     105static futex_t *find_cached_futex(uintptr_t uaddr);
     106static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr);
     107static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
     108
    61109static size_t futex_ht_hash(sysarg_t *key);
    62110static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
    63111static void futex_ht_remove_callback(link_t *item);
    64112
    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.
     113static size_t task_fut_ht_hash(const cht_link_t *link);
     114static size_t task_fut_ht_key_hash(void *key);
     115static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2);
     116static 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.
    69122 */
    70123static mutex_t futex_ht_lock;
    71124
    72 /** Futex hash table. */
     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 */
    73129static hash_table_t futex_ht;
    74130
    75 /** Futex hash table operations. */
     131/** Global kernel futex hash table operations. */
    76132static hash_table_operations_t futex_ht_ops = {
    77133        .hash = futex_ht_hash,
     
    80136};
    81137
     138/** Task futex cache CHT operations. */
     139static 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
    82147/** Initialize futex subsystem. */
    83148void futex_init(void)
     
    87152}
    88153
    89 /** Initialize kernel futex structure.
    90  *
    91  * @param futex         Kernel futex structure.
    92  */
    93 void futex_initialize(futex_t *futex)
     154/** Initializes the futex structures for the new task. */
     155void 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. */
     166void 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). */
     180static 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. */
     203void 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 */
     233static void futex_initialize(futex_t *futex, uintptr_t paddr)
    94234{
    95235        waitq_initialize(&futex->wq);
    96236        link_initialize(&futex->ht_link);
    97         futex->paddr = 0;
     237        futex->paddr = paddr;
    98238        futex->refcount = 1;
     239}
     240
     241/** Increments the counter of tasks referencing the futex. */
     242static 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.*/
     250static 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.*/
     263static 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). */
     271static 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. */
     288static 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. */
     306static 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 */
     332static 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;
    99383}
    100384
     
    109393sysarg_t sys_futex_sleep(uintptr_t uaddr)
    110394{
    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);
     395        futex_t *futex = get_futex(uaddr);
     396       
     397        if (!futex)
    123398                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);
    129399
    130400#ifdef CONFIG_UDEBUG
    131401        udebug_stoppable_begin();
    132402#endif
    133         rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
     403        int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    134404#ifdef CONFIG_UDEBUG
    135405        udebug_stoppable_end();
     
    146416sysarg_t sys_futex_wakeup(uintptr_t uaddr)
    147417{
    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);
     418        futex_t *futex = get_futex(uaddr);
     419       
     420        if (futex) {
     421                waitq_wakeup(&futex->wq, WAKEUP_FIRST);
     422                return 0;
     423        } else {
    159424                return (sysarg_t) ENOENT;
    160425        }
    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  */
    179 futex_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);
    208         } else {
    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 }
     426}
     427
    228428
    229429/** Compute hash index into futex hash table.
     
    268468}
    269469
    270 /** Remove references from futexes known to the current task. */
    271 void 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 }
     470/*
     471 * Operations of a task's CHT that caches mappings of futex user space
     472 * virtual addresses to kernel futex objects.
     473 */
     474
     475static 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
     481static size_t task_fut_ht_key_hash(void *key)
     482{
     483        return *(uintptr_t*)key;
     484}
     485
     486static 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
     494static 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
    294502
    295503/** @}
Note: See TracChangeset for help on using the changeset viewer.