Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r759ea0d rfeeac0d  
    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 found = false;
    294         pte_t *t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), true);
    295        
    296         if (t && PTE_VALID(t) && PTE_PRESENT(t)) {
    297                 found = true;
    298                 *paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
    299         }
    300        
    301         spinlock_unlock(&futex_ht_lock);
    302         page_table_unlock(AS, false);
    303        
    304         return found;
    305 }
    306 
    307 /** Returns the futex cached in this task with the virtual address uaddr. */
    308 static futex_t *find_cached_futex(uintptr_t uaddr)
    309 {
    310         cht_read_lock();
    311        
    312         futex_t *futex;
    313         cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);
    314 
    315         if (futex_ptr_link) {
    316                 futex_ptr_t *futex_ptr
    317                         = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
    318                
    319                 futex = futex_ptr->futex;
    320         } else {
    321                 futex = NULL;
    322         }
    323        
    324         cht_read_unlock();
    325        
    326         return futex;
    327 }
    328 
    329 
    330 /**
    331  * Returns a kernel futex for the physical address @a phys_addr and caches
    332  * it in this task under the virtual address @a uaddr (if not already cached).
    333  */
    334 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr)
    335 {
    336         futex_t *futex = malloc(sizeof(futex_t), 0);
    337        
    338         /*
    339          * Find the futex object in the global futex table (or insert it
    340          * if it is not present).
    341          */
    342         spinlock_lock(&futex_ht_lock);
    343        
    344         link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
    345        
    346         if (fut_link) {
    347                 free(futex);
    348                 futex = member_to_inst(fut_link, futex_t, ht_link);
    349                 futex_add_ref(futex);
    350         } else {
    351                 futex_initialize(futex, phys_addr);
    352                 hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
    353         }
    354        
    355         spinlock_unlock(&futex_ht_lock);
    356        
    357         /*
    358          * Cache the link to the futex object for this task.
    359          */
    360         futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0);
    361         cht_link_t *dup_link;
    362        
    363         fut_ptr->futex = futex;
    364         fut_ptr->uaddr = uaddr;
    365        
    366         cht_read_lock();
    367        
    368         /* Cache the mapping from the virtual address to the futex for this task. */
    369         if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
    370                 spinlock_lock(&TASK->futexes->list_lock);
    371                 list_append(&fut_ptr->all_link, &TASK->futexes->list);
    372                 spinlock_unlock(&TASK->futexes->list_lock);
    373         } else {
    374                 /* Another thread of this task beat us to it. Use that mapping instead.*/
    375                 free(fut_ptr);
    376                 futex_release_ref_locked(futex);
    377                
    378                 futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
    379                 futex = dup->futex;             
    380         }
    381 
    382         cht_read_unlock();
    383        
    384         return futex;
    38599}
    386100
    … …  
    395109sysarg_t sys_futex_sleep(uintptr_t uaddr)
    396110{
    397         futex_t *futex = get_futex(uaddr);
    398        
    399         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);
    400123                return (sysarg_t) ENOENT;
    401 
    402         int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    403 
     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);
     129
     130#ifdef CONFIG_UDEBUG
     131        udebug_stoppable_begin();
     132#endif
     133        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
     134#ifdef CONFIG_UDEBUG
     135        udebug_stoppable_end();
     136#endif
    404137        return (sysarg_t) rc;
    405138}
    … …  
    413146sysarg_t sys_futex_wakeup(uintptr_t uaddr)
    414147{
    415         futex_t *futex = get_futex(uaddr);
    416        
    417         if (futex) {
    418                 waitq_wakeup(&futex->wq, WAKEUP_FIRST);
    419                 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);
    420208        } else {
    421                 return (sysarg_t) ENOENT;
    422         }
    423 }
    424 
     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}
    425228
    426229/** Compute hash index into futex hash table.
    … …  
    465268}
    466269
    467 /*
    468  * Operations of a task's CHT that caches mappings of futex user space
    469  * virtual addresses to kernel futex objects.
    470  */
    471 
    472 static size_t task_fut_ht_hash(const cht_link_t *link)
    473 {
    474         const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link);
    475         return fut_ptr->uaddr;
    476 }
    477 
    478 static size_t task_fut_ht_key_hash(void *key)
    479 {
    480         return *(uintptr_t*)key;
    481 }
    482 
    483 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2)
    484 {
    485         const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link);
    486         const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link);
    487        
    488         return fut_ptr1->uaddr == fut_ptr2->uaddr;
    489 }
    490 
    491 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item)
    492 {
    493         const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link);
    494         uintptr_t uaddr = *(uintptr_t*)key;
    495        
    496         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, leaf_link, btree_node_t, node) {
     277                unsigned int i;
     278               
     279                for (i = 0; i < node->keys; i++) {
     280                        futex_t *ftx;
     281                        uintptr_t paddr = node->key[i];
     282                       
     283                        ftx = (futex_t *) node->value[i];
     284                        if (--ftx->refcount == 0)
     285                                hash_table_remove(&futex_ht, &paddr, 1);
     286                }
     287        }
     288       
     289        mutex_unlock(&TASK->futexes_lock);
     290        mutex_unlock(&futex_ht_lock);
    497291}
    498292
Note: See TracChangeset for help on using the changeset viewer.