source: mainline/kernel/generic/src/synch/futex.c@ 38dc82d

/*
 * Copyright (c) 2006 Jakub Jermar
 * Copyright (c) 2012 Adam Hraska
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup sync
 * @{
 */

/**
 * @file
 * @brief       Kernel backend for futexes.
 * 
 * Kernel futex objects are stored in a global hash table futex_ht 
 * where the physical address of the futex variable (futex_t.paddr)
 * is used as the lookup key. As a result multiple address spaces 
 * may share the same futex variable. 
 * 
 * A kernel futex object is created the first time a task accesses
 * the futex (having a futex variable at a physical address not 
 * encountered before). Futex object's lifetime is governed by
 * a reference count that represents the number of all the different
 * user space virtual addresses from all tasks that map to the
 * physical address of the futex variable. A futex object is freed
 * when the last task having accessed the futex exits.
 * 
 * Each task keeps track of the futex objects it accessed in a list
 * of pointers (futex_ptr_t, task->futex_list) to the different futex 
 * objects.
 * 
 * To speed up translation of futex variables' virtual addresses
 * to their physical addresses, futex pointers accessed by the
 * task are furthermore stored in a concurrent hash table (CHT,
 * task->futexes->ht). A single lookup without locks or accesses
 * to the page table translates a futex variable's virtual address 
 * into its futex kernel object. 
 */

#include <synch/futex.h>
#include <synch/mutex.h>
#include <synch/spinlock.h>
#include <synch/rcu.h>
#include <mm/frame.h>
#include <mm/page.h>
#include <mm/slab.h>
#include <proc/thread.h>
#include <proc/task.h>
#include <genarch/mm/page_pt.h>
#include <genarch/mm/page_ht.h>
#include <adt/cht.h>
#include <adt/hash_table.h>
#include <adt/list.h>
#include <arch.h>
#include <align.h>
#include <panic.h>
#include <errno.h>

#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */

/** Task specific pointer to a global kernel futex object. */
typedef struct futex_ptr {
        /** CHT link. */
        cht_link_t cht_link;
        /** List of all futex pointers used by the task. */
        link_t all_link;
        /** Kernel futex object. */
        futex_t *futex;
        /** User space virtual address of the futex variable in the task. */
        uintptr_t uaddr;
} futex_ptr_t;


static void destroy_task_cache(work_t *work);

static void futex_initialize(futex_t *futex, uintptr_t paddr);
static void futex_add_ref(futex_t *futex);
static void futex_release_ref(futex_t *futex);
static void futex_release_ref_locked(futex_t *futex);

static futex_t *get_futex(uintptr_t uaddr);
static futex_t *find_cached_futex(uintptr_t uaddr);
static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr);
static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);

static size_t futex_ht_hash(sysarg_t *key);
static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
static void futex_ht_remove_callback(link_t *item);

static size_t task_fut_ht_hash(const cht_link_t *link);
static size_t task_fut_ht_key_hash(void *key);
static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2);
static bool task_fut_ht_key_equal(void *key, const cht_link_t *item);


/** Mutex protecting the global futex hash table.
 * 
 * Acquire task specific TASK->futex_list_lock before this mutex.
 */
SPINLOCK_STATIC_INITIALIZE_NAME(futex_ht_lock, "futex-ht-lock");

/** Global kernel futex hash table. Lock futex_ht_lock before accessing.
 * 
 * Physical address of the futex variable is the lookup key.
 */
static hash_table_t futex_ht;

/** Global kernel futex hash table operations. */
static hash_table_operations_t futex_ht_ops = {
        .hash = futex_ht_hash,
        .compare = futex_ht_compare,
        .remove_callback = futex_ht_remove_callback
};

/** Task futex cache CHT operations. */
static cht_ops_t task_futex_ht_ops = {
        .hash = task_fut_ht_hash,
        .key_hash = task_fut_ht_key_hash,
        .equal = task_fut_ht_equal,
        .key_equal = task_fut_ht_key_equal,
        .remove_callback = NULL
};

/** Initialize futex subsystem. */
void futex_init(void)
{
        hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
}

/** Initializes the futex structures for the new task. */
void futex_task_init(struct task *task)
{
        task->futexes = malloc(sizeof(struct futex_cache), 0);
        
        cht_create(&task->futexes->ht, 0, 0, 0, true, &task_futex_ht_ops);
        
        list_initialize(&task->futexes->list);
        spinlock_initialize(&task->futexes->list_lock, "futex-list-lock");
}

/** Destroys the futex structures for the dying task. */
void futex_task_deinit(task_t *task)
{
        /* Interrupts are disabled so we must not block (cannot run cht_destroy). */
        if (interrupts_disabled()) {
                /* Invoke the blocking cht_destroy in the background. */
                workq_global_enqueue_noblock(&task->futexes->destroy_work, 
                        destroy_task_cache);
        } else {
                /* We can block. Invoke cht_destroy in this thread. */
                destroy_task_cache(&task->futexes->destroy_work);
        }
}

/** Deallocates a task's CHT futex cache (must already be empty). */
static void destroy_task_cache(work_t *work)
{
        struct futex_cache *cache = 
                member_to_inst(work, struct futex_cache, destroy_work);
        
        /* 
         * Destroy the cache before manually freeing items of the cache in case
         * table resize is in progress.
         */
        cht_destroy_unsafe(&cache->ht);
        
        /* Manually free futex_ptr cache items. */
        list_foreach_safe(cache->list, cur_link, next_link) {
                futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);

                list_remove(cur_link);
                free(fut_ptr);
        }
        
        free(cache);
}

/** Remove references from futexes known to the current task. */
void futex_task_cleanup(void)
{
        struct futex_cache *futexes = TASK->futexes;
        
        /* All threads of this task have terminated. This is the last thread. */
        spinlock_lock(&futexes->list_lock);
        
        list_foreach_safe(futexes->list, cur_link, next_link) {
                futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link);

                /*
                 * The function is free to free the futex. All other threads of this
                 * task have already terminated, so they have also definitely
                 * exited their CHT futex cache protecting rcu reader sections.
                 * Moreover release_ref() only frees the futex if this is the 
                 * last task referencing the futex. Therefore, only threads
                 * of this task may have referenced the futex if it is to be freed.
                 */
                futex_release_ref_locked(fut_ptr->futex);
        }
        
        spinlock_unlock(&futexes->list_lock);
}


/** Initialize the kernel futex structure.
 *
 * @param futex Kernel futex structure.
 * @param paddr Physical address of the futex variable.
 */
static void futex_initialize(futex_t *futex, uintptr_t paddr)
{
        waitq_initialize(&futex->wq);
        link_initialize(&futex->ht_link);
        futex->paddr = paddr;
        futex->refcount = 1;
}

/** Increments the counter of tasks referencing the futex. */
static void futex_add_ref(futex_t *futex)
{
        ASSERT(spinlock_locked(&futex_ht_lock));
        ASSERT(0 < futex->refcount);
        ++futex->refcount;
}

/** Decrements the counter of tasks referencing the futex. May free the futex.*/
static void futex_release_ref(futex_t *futex)
{
        ASSERT(spinlock_locked(&futex_ht_lock));
        ASSERT(0 < futex->refcount);
        
        --futex->refcount;
        
        if (0 == futex->refcount) {
                hash_table_remove(&futex_ht, &futex->paddr, 1);
        }
}

/** Decrements the counter of tasks referencing the futex. May free the futex.*/
static void futex_release_ref_locked(futex_t *futex)
{
        spinlock_lock(&futex_ht_lock);
        futex_release_ref(futex);
        spinlock_unlock(&futex_ht_lock);
}

/** Returns a futex for the virtual address @a uaddr (or creates one). */
static futex_t *get_futex(uintptr_t uaddr)
{
        futex_t *futex = find_cached_futex(uaddr);
        
        if (futex) 
                return futex;

        uintptr_t paddr;

        if (!find_futex_paddr(uaddr, &paddr)) {
                return 0;
        }

        return get_and_cache_futex(paddr, uaddr);
}


/** Finds the physical address of the futex variable. */
static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *paddr)
{
        page_table_lock(AS, false);
        spinlock_lock(&futex_ht_lock);

        bool success = false;

        pte_t t;
        bool found;

        found = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), true, &t);
        if (found && PTE_VALID(&t) && PTE_PRESENT(&t)) {
                success = true;
                *paddr = PTE_GET_FRAME(&t) +
                    (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));
        }
        
        spinlock_unlock(&futex_ht_lock);
        page_table_unlock(AS, false);
        
        return success;
}

/** Returns the futex cached in this task with the virtual address uaddr. */
static futex_t *find_cached_futex(uintptr_t uaddr)
{
        cht_read_lock();
        
        futex_t *futex;
        cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr);

        if (futex_ptr_link) {
                futex_ptr_t *futex_ptr 
                        = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link);
                
                futex = futex_ptr->futex;
        } else {
                futex = NULL;
        }
        
        cht_read_unlock();
        
        return futex;
}


/** 
 * Returns a kernel futex for the physical address @a phys_addr and caches 
 * it in this task under the virtual address @a uaddr (if not already cached).
 */
static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr)
{
        futex_t *futex = malloc(sizeof(futex_t), 0);
        
        /* 
         * Find the futex object in the global futex table (or insert it 
         * if it is not present).
         */
        spinlock_lock(&futex_ht_lock);
        
        link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
        
        if (fut_link) {
                free(futex);
                futex = member_to_inst(fut_link, futex_t, ht_link);
                futex_add_ref(futex);
        } else {
                futex_initialize(futex, phys_addr);
                hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
        }
        
        spinlock_unlock(&futex_ht_lock);
        
        /* 
         * Cache the link to the futex object for this task. 
         */
        futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0);
        cht_link_t *dup_link;
        
        fut_ptr->futex = futex;
        fut_ptr->uaddr = uaddr;
        
        cht_read_lock();
        
        /* Cache the mapping from the virtual address to the futex for this task. */
        if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) {
                spinlock_lock(&TASK->futexes->list_lock);
                list_append(&fut_ptr->all_link, &TASK->futexes->list);
                spinlock_unlock(&TASK->futexes->list_lock);
        } else {
                /* Another thread of this task beat us to it. Use that mapping instead.*/
                free(fut_ptr);
                futex_release_ref_locked(futex);
                
                futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link);
                futex = dup->futex;             
        }

        cht_read_unlock();
        
        return futex;
}

/** Sleep in futex wait queue.
 *
 * @param uaddr         Userspace address of the futex counter.
 *
 * @return              If there is no physical mapping for uaddr ENOENT is
 *                      returned. Otherwise returns a wait result as defined in
 *                      synch.h.
 */
sysarg_t sys_futex_sleep(uintptr_t uaddr)
{
        futex_t *futex = get_futex(uaddr);
        
        if (!futex) 
                return (sysarg_t) ENOENT;

#ifdef CONFIG_UDEBUG
        udebug_stoppable_begin();
#endif

        int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE); 

#ifdef CONFIG_UDEBUG
        udebug_stoppable_end();
#endif

        return (sysarg_t) rc;
}

/** Wakeup one thread waiting in futex wait queue.
 *
 * @param uaddr         Userspace address of the futex counter.
 *
 * @return              ENOENT if there is no physical mapping for uaddr.
 */
sysarg_t sys_futex_wakeup(uintptr_t uaddr)
{
        futex_t *futex = get_futex(uaddr);
        
        if (futex) {
                waitq_wakeup(&futex->wq, WAKEUP_FIRST);
                return 0;
        } else {
                return (sysarg_t) ENOENT;
        }
}


/** Compute hash index into futex hash table.
 *
 * @param key           Address where the key (i.e. physical address of futex
 *                      counter) is stored.
 *
 * @return              Index into futex hash table.
 */
size_t futex_ht_hash(sysarg_t *key)
{
        return (*key & (FUTEX_HT_SIZE - 1));
}

/** Compare futex hash table item with a key.
 *
 * @param key           Address where the key (i.e. physical address of futex
 *                      counter) is stored.
 *
 * @return              True if the item matches the key. False otherwise.
 */
bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item)
{
        futex_t *futex;

        ASSERT(keys == 1);

        futex = hash_table_get_instance(item, futex_t, ht_link);
        return *key == futex->paddr;
}

/** Callback for removal items from futex hash table.
 *
 * @param item          Item removed from the hash table.
 */
void futex_ht_remove_callback(link_t *item)
{
        futex_t *futex;

        futex = hash_table_get_instance(item, futex_t, ht_link);
        free(futex);
}

/*
 * Operations of a task's CHT that caches mappings of futex user space 
 * virtual addresses to kernel futex objects.
 */

static size_t task_fut_ht_hash(const cht_link_t *link)
{
        const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link);
        return fut_ptr->uaddr;
}

static size_t task_fut_ht_key_hash(void *key)
{
        return *(uintptr_t*)key;
}

static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2)
{
        const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link);
        const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link);
        
        return fut_ptr1->uaddr == fut_ptr2->uaddr;
}

static bool task_fut_ht_key_equal(void *key, const cht_link_t *item)
{
        const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link);
        uintptr_t uaddr = *(uintptr_t*)key;
        
        return fut_ptr->uaddr == uaddr;
}

/** @}
 */