Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 947ab77e in mainline


Ignore:
Timestamp:
2018-11-07T20:41:51Z (3 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master
Children:
aae365bc
Parents:
bed67f2
Message:

Stop using CHT in futexes

Location:
kernel/generic
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/proc/task.h

    rbed67f2 r947ab77e  
    130130        task_arch_t arch;
    131131
    132         struct futex_cache {
    133                 /** CHT mapping virtual addresses of futex variables to futex objects.*/
    134                 cht_t ht;
    135                 /** Serializes access to futex_list.*/
    136                 SPINLOCK_DECLARE(list_lock);
    137                 /** List of all futexes accesses by this task. */
    138                 list_t list;
    139                 work_t destroy_work;
    140         } *futexes;
     132        /** Serializes access to futex_list.*/
     133        SPINLOCK_DECLARE(futex_list_lock);
     134        /** List of all futexes accesses by this task. */
     135        list_t futex_list;
    141136
    142137        /** Accumulated accounting. */
  • kernel/generic/include/synch/futex.h

    rbed67f2 r947ab77e  
    5858extern void futex_task_cleanup(void);
    5959extern void futex_task_init(struct task *);
    60 extern void futex_task_deinit(struct task *);
    6160
    6261#endif
  • kernel/generic/src/proc/task.c

    rbed67f2 r947ab77e  
    285285
    286286        /*
    287          * Free up dynamically allocated state.
    288          */
    289         futex_task_deinit(task);
    290 
    291         /*
    292287         * Drop our reference to the address space.
    293288         */
  • kernel/generic/src/synch/futex.c

    rbed67f2 r947ab77e  
    5252 * of pointers (futex_ptr_t, task->futex_list) to the different futex
    5353 * 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.
    6154 */
    6255
     
    6558#include <synch/mutex.h>
    6659#include <synch/spinlock.h>
    67 #include <synch/rcu.h>
    6860#include <mm/frame.h>
    6961#include <mm/page.h>
     
    7365#include <genarch/mm/page_pt.h>
    7466#include <genarch/mm/page_ht.h>
    75 #include <adt/cht.h>
    7667#include <adt/hash.h>
    7768#include <adt/hash_table.h>
     
    8475/** Task specific pointer to a global kernel futex object. */
    8576typedef struct futex_ptr {
    86         /** CHT link. */
    87         cht_link_t cht_link;
    8877        /** List of all futex pointers used by the task. */
    8978        link_t all_link;
     
    9483} futex_ptr_t;
    9584
    96 static void destroy_task_cache(work_t *work);
    97 
    9885static void futex_initialize(futex_t *futex, uintptr_t paddr);
    9986static void futex_add_ref(futex_t *futex);
     
    10289
    10390static futex_t *get_futex(uintptr_t uaddr);
    104 static futex_t *find_cached_futex(uintptr_t uaddr);
    105 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr);
    10691static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
    10792
     
    11095static bool futex_ht_key_equal(void *key, const ht_link_t *item);
    11196static void futex_ht_remove_callback(ht_link_t *item);
    112 
    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);
    11797
    11898/** Mutex protecting the global futex hash table.
     
    136116};
    137117
    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 
    147118/** Initialize futex subsystem. */
    148119void futex_init(void)
     
    154125void futex_task_init(struct task *task)
    155126{
    156         task->futexes = nfmalloc(sizeof(struct futex_cache));
    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);
     127        list_initialize(&task->futex_list);
     128        spinlock_initialize(&task->futex_list_lock, "futex-list-lock");
    199129}
    200130
     
    202132void futex_task_cleanup(void)
    203133{
    204         struct futex_cache *futexes = TASK->futexes;
    205 
    206134        /* 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) {
     135        spinlock_lock(&TASK->futex_list_lock);
     136
     137        list_foreach_safe(TASK->futex_list, cur_link, next_link) {
    210138                futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);
    211139
    212140                /*
    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.
     141                 * The function is free to free the futex.  Moreover
     142                 * release_ref() only frees the futex if this is the last task
     143                 * referencing the futex. Therefore, only threads of this task
     144                 * may have referenced the futex if it is to be freed.
    219145                 */
    220146                futex_release_ref_locked(fut_ptr->futex);
    221147        }
    222148
    223         spinlock_unlock(&futexes->list_lock);
     149        spinlock_unlock(&TASK->futex_list_lock);
    224150}
    225151
     
    268194static futex_t *get_futex(uintptr_t uaddr)
    269195{
    270         futex_t *futex = find_cached_futex(uaddr);
    271 
    272         if (futex)
    273                 return futex;
    274 
    275196        uintptr_t paddr;
    276197
    277         if (!find_futex_paddr(uaddr, &paddr)) {
    278                 return 0;
    279         }
    280 
    281         return get_and_cache_futex(paddr, uaddr);
     198        if (!find_futex_paddr(uaddr, &paddr))
     199                return NULL;
     200
     201        futex_t *futex = malloc(sizeof(futex_t));
     202        if (!futex)
     203                return NULL;
     204
     205        /*
     206         * Find the futex object in the global futex table (or insert it
     207         * if it is not present).
     208         */
     209        spinlock_lock(&futex_ht_lock);
     210
     211        ht_link_t *fut_link = hash_table_find(&futex_ht, &paddr);
     212
     213        if (fut_link) {
     214                free(futex);
     215                futex = member_to_inst(fut_link, futex_t, ht_link);
     216                futex_add_ref(futex);
     217        } else {
     218                futex_initialize(futex, paddr);
     219                hash_table_insert(&futex_ht, &futex->ht_link);
     220        }
     221
     222        spinlock_unlock(&futex_ht_lock);
     223
     224        return futex;
    282225}
    283226
     
    306249}
    307250
    308 /** Returns the futex cached in this task with the virtual address uaddr. */
    309 static futex_t *find_cached_futex(uintptr_t uaddr)
    310 {
    311         cht_read_lock();
    312 
    313         futex_t *futex;
    314         cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);
    315 
    316         if (futex_ptr_link) {
    317                 futex_ptr_t *futex_ptr =
    318                     member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
    319 
    320                 futex = futex_ptr->futex;
    321         } else {
    322                 futex = NULL;
    323         }
    324 
    325         cht_read_unlock();
    326 
    327         return futex;
    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));
    337         if (!futex)
    338                 return NULL;
    339 
    340         /*
    341          * Find the futex object in the global futex table (or insert it
    342          * if it is not present).
    343          */
    344         spinlock_lock(&futex_ht_lock);
    345 
    346         ht_link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
    347 
    348         if (fut_link) {
    349                 free(futex);
    350                 futex = member_to_inst(fut_link, futex_t, ht_link);
    351                 futex_add_ref(futex);
    352         } else {
    353                 futex_initialize(futex, phys_addr);
    354                 hash_table_insert(&futex_ht, &futex->ht_link);
    355         }
    356 
    357         spinlock_unlock(&futex_ht_lock);
    358 
    359         /*
    360          * Cache the link to the futex object for this task.
    361          */
    362         futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t));
    363         if (!fut_ptr) {
    364                 spinlock_lock(&futex_ht_lock);
    365                 futex_release_ref(futex);
    366                 spinlock_unlock(&futex_ht_lock);
    367                 return NULL;
    368         }
    369         cht_link_t *dup_link;
    370 
    371         fut_ptr->futex = futex;
    372         fut_ptr->uaddr = uaddr;
    373 
    374         cht_read_lock();
    375 
    376         /* Cache the mapping from the virtual address to the futex for this task. */
    377         if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
    378                 spinlock_lock(&TASK->futexes->list_lock);
    379                 list_append(&fut_ptr->all_link, &TASK->futexes->list);
    380                 spinlock_unlock(&TASK->futexes->list_lock);
    381         } else {
    382                 /* Another thread of this task beat us to it. Use that mapping instead.*/
    383                 free(fut_ptr);
    384                 futex_release_ref_locked(futex);
    385 
    386                 futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
    387                 futex = dup->futex;
    388         }
    389 
    390         cht_read_unlock();
    391 
    392         return futex;
    393 }
    394 
    395251/** Sleep in futex wait queue with a timeout.
    396252 *  If the sleep times out or is interrupted, the next wakeup is ignored.
     
    477333}
    478334
    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;
    509 }
    510 
    511335/** @}
    512336 */
Note: See TracChangeset for help on using the changeset viewer.