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

Changeset 1a5fe4f in mainline for kernel/generic/src/synch/futex.c


Ignore:
Timestamp:
2018-11-09T18:09:55Z (3 years ago)
Author:
GitHub <noreply@…>
Branches:
lfn, master
Children:
1892d2c
Parents:
3875f106 (diff), ef4218f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
git-author:
Jakub Jermář <jakub@…> (2018-11-09 18:09:55)
git-committer:
GitHub <noreply@…> (2018-11-09 18:09:55)
Message:

Merge pull request #54 from jermar/rcuremoval

Remove RCU and related features

File:
1 edited

Legend:

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

    r3875f106 r1a5fe4f  
    4545 * encountered before). Futex object's lifetime is governed by
    4646 * 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
     47 * tasks that reference the futex variable. A futex object is freed
    4948 * when the last task having accessed the futex exits.
    5049 *
     
    5251 * of pointers (futex_ptr_t, task->futex_list) to the different futex
    5352 * 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.
    6153 */
    6254
     
    6557#include <synch/mutex.h>
    6658#include <synch/spinlock.h>
    67 #include <synch/rcu.h>
    6859#include <mm/frame.h>
    6960#include <mm/page.h>
     
    7364#include <genarch/mm/page_pt.h>
    7465#include <genarch/mm/page_ht.h>
    75 #include <adt/cht.h>
    7666#include <adt/hash.h>
    7767#include <adt/hash_table.h>
     
    8474/** Task specific pointer to a global kernel futex object. */
    8575typedef 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;
     76        /** Link for the list of all futex pointers used by a task. */
     77        link_t task_link;
    9078        /** Kernel futex object. */
    9179        futex_t *futex;
    92         /** User space virtual address of the futex variable in the task. */
    93         uintptr_t uaddr;
    9480} futex_ptr_t;
    95 
    96 static void destroy_task_cache(work_t *work);
    9781
    9882static void futex_initialize(futex_t *futex, uintptr_t paddr);
     
    10286
    10387static 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);
    10688static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
    10789
     
    11092static bool futex_ht_key_equal(void *key, const ht_link_t *item);
    11193static 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);
    11794
    11895/** Mutex protecting the global futex hash table.
     
    136113};
    137114
    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 
    147115/** Initialize futex subsystem. */
    148116void futex_init(void)
     
    154122void futex_task_init(struct task *task)
    155123{
    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);
     124        list_initialize(&task->futex_list);
     125        spinlock_initialize(&task->futex_list_lock, "futex-list-lock");
    199126}
    200127
     
    202129void futex_task_cleanup(void)
    203130{
    204         struct futex_cache *futexes = TASK->futexes;
    205 
    206131        /* 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);
     132        spinlock_lock(&TASK->futex_list_lock);
     133
     134        list_foreach_safe(TASK->futex_list, cur_link, next_link) {
     135                futex_ptr_t *futex_ptr = member_to_inst(cur_link, futex_ptr_t,
     136                    task_link);
     137
     138                futex_release_ref_locked(futex_ptr->futex);
     139                free(futex_ptr);
     140        }
     141
     142        spinlock_unlock(&TASK->futex_list_lock);
    224143}
    225144
     
    240159{
    241160        assert(spinlock_locked(&futex_ht_lock));
    242         assert(0 < futex->refcount);
     161        assert(futex->refcount > 0);
    243162        ++futex->refcount;
    244163}
     
    248167{
    249168        assert(spinlock_locked(&futex_ht_lock));
    250         assert(0 < futex->refcount);
     169        assert(futex->refcount > 0);
    251170
    252171        --futex->refcount;
    253172
    254         if (0 == futex->refcount) {
     173        if (futex->refcount == 0)
    255174                hash_table_remove(&futex_ht, &futex->paddr);
    256         }
    257175}
    258176
     
    268186static futex_t *get_futex(uintptr_t uaddr)
    269187{
    270         futex_t *futex = find_cached_futex(uaddr);
    271 
    272         if (futex)
    273                 return futex;
    274 
    275188        uintptr_t paddr;
    276189
    277         if (!find_futex_paddr(uaddr, &paddr)) {
    278                 return 0;
    279         }
    280 
    281         return get_and_cache_futex(paddr, uaddr);
     190        if (!find_futex_paddr(uaddr, &paddr))
     191                return NULL;
     192
     193        futex_t *futex = malloc(sizeof(futex_t));
     194        if (!futex)
     195                return NULL;
     196
     197        futex_ptr_t *futex_ptr = malloc(sizeof(futex_ptr_t));
     198        if (!futex_ptr) {
     199                free(futex);
     200                return NULL;
     201        }
     202
     203        /*
     204         * Find the futex object in the global futex table (or insert it
     205         * if it is not present).
     206         */
     207        spinlock_lock(&TASK->futex_list_lock);
     208        spinlock_lock(&futex_ht_lock);
     209
     210        ht_link_t *fut_link = hash_table_find(&futex_ht, &paddr);
     211
     212        if (fut_link) {
     213                free(futex);
     214                futex = member_to_inst(fut_link, futex_t, ht_link);
     215
     216                /*
     217                 * See if the futex is already known to the TASK
     218                 */
     219                bool found = false;
     220                list_foreach(TASK->futex_list, task_link, futex_ptr_t, fp) {
     221                        if (fp->futex->paddr == paddr) {
     222                                found = true;
     223                                break;
     224                        }
     225                }
     226                /*
     227                 * If not, put it on the TASK->futex_list and bump its reference
     228                 * count
     229                 */
     230                if (!found) {
     231                        list_append(&futex_ptr->task_link, &TASK->futex_list);
     232                        futex_add_ref(futex);
     233                } else
     234                        free(futex_ptr);
     235        } else {
     236                futex_initialize(futex, paddr);
     237                hash_table_insert(&futex_ht, &futex->ht_link);
     238
     239                /*
     240                 * This is a new futex, so it is not on the TASK->futex_list yet
     241                 */
     242                futex_ptr->futex = futex;
     243                list_append(&futex_ptr->task_link, &TASK->futex_list);
     244        }
     245
     246        spinlock_unlock(&futex_ht_lock);
     247        spinlock_unlock(&TASK->futex_list_lock);
     248
     249        return futex;
    282250}
    283251
     
    306274}
    307275
    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 
    395276/** Sleep in futex wait queue with a timeout.
     277 *
    396278 *  If the sleep times out or is interrupted, the next wakeup is ignored.
    397279 *  The userspace portion of the call must handle this condition.
     
    477359}
    478360
    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 
    511361/** @}
    512362 */
Note: See TracChangeset for help on using the changeset viewer.