// Copyright 2016 The Fuchsia Authors
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT

#include <object/futex_context.h>

#include <assert.h>
#include <lib/user_copy/user_ptr.h>
#include <fbl/auto_lock.h>
#include <object/thread_dispatcher.h>
#include <trace.h>
#include <zircon/types.h>

using fbl::AutoLock;

#define LOCAL_TRACE 0

FutexContext::FutexContext() {
    LTRACE_ENTRY;
}

FutexContext::~FutexContext() {
    LTRACE_ENTRY;

    // All of the threads should have removed themselves from wait queues
    // by the time the process has exited.
    DEBUG_ASSERT(futex_table_.is_empty());
}

zx_status_t FutexContext::FutexWait(user_in_ptr<const int> value_ptr, int current_value, zx_time_t deadline) {
    LTRACE_ENTRY;

    uintptr_t futex_key = reinterpret_cast<uintptr_t>(value_ptr.get());
    if (futex_key % sizeof(int))
        return ZX_ERR_INVALID_ARGS;

    FutexNode* node;

    // FutexWait() checks that the address value_ptr still contains
    // current_value, and if so it sleeps awaiting a FutexWake() on value_ptr.
    // Those two steps must together be atomic with respect to FutexWake().
    // If a FutexWake() operation could occur between them, a userland mutex
    // operation built on top of futexes would have a race condition that
    // could miss wakeups.
    lock_.Acquire();

    int value;
    zx_status_t result = value_ptr.copy_from_user(&value);
    if (result != ZX_OK) {
        lock_.Release();
        return result;
    }
    if (value != current_value) {
        lock_.Release();
        return ZX_ERR_BAD_STATE;
    }

    ThreadDispatcher* thread = ThreadDispatcher::GetCurrent();
    node = thread->futex_node();
    node->set_hash_key(futex_key);
    node->SetAsSingletonList();

    QueueNodesLocked(node);

    // Block current thread.  This releases lock_ and does not reacquire it.
    result = node->BlockThread(&lock_, deadline);
    if (result == ZX_OK) {
        DEBUG_ASSERT(!node->IsInQueue());
        // All the work necessary for removing us from the hash table was done by FutexWake()
        return ZX_OK;
    }

    // The following happens if we hit the deadline (ZX_ERR_TIMED_OUT) or if
    // the thread was killed (ZX_ERR_INTERNAL_INTR_KILLED) or suspended
    // (ZX_ERR_INTERNAL_INTR_RETRY).
    //
    // We need to ensure that the thread's node is removed from the wait
    // queue, because FutexWake() probably didn't do that.
    AutoLock lock(&lock_);
    if (UnqueueNodeLocked(node)) {
        return result;
    }
    // The current thread was not found on the wait queue.  This means
    // that, although we hit the deadline (or were suspended/killed), we
    // were *also* woken by FutexWake() (which removed the thread from the
    // wait queue) -- the two raced together.
    //
    // In this case, we want to return a success status.  This preserves
    // the property that if FutexWake() is called with wake_count=1 and
    // there are waiting threads, then at least one FutexWait() call
    // returns success.
    //
    // If that property is broken, it can lead to missed wakeups in
    // concurrency constructs that are built on top of futexes.  For
    // example, suppose a FutexWake() call from pthread_mutex_unlock()
    // races with a FutexWait() deadline from pthread_mutex_timedlock(). A
    // typical implementation of pthread_mutex_timedlock() will return
    // immediately without trying again to claim the mutex if this
    // FutexWait() call returns a timeout status.  If that happens, and if
    // another thread is waiting on the mutex, then that thread won't get
    // woken -- the wakeup from the FutexWake() call would have got lost.
    return ZX_OK;
}

zx_status_t FutexContext::FutexWake(user_in_ptr<const int> value_ptr,
                                    uint32_t count) {
    LTRACE_ENTRY;

    if (count == 0) return ZX_OK;

    uintptr_t futex_key = reinterpret_cast<uintptr_t>(value_ptr.get());
    if (futex_key % sizeof(int))
        return ZX_ERR_INVALID_ARGS;

    AutoLock lock(&lock_);

    FutexNode* node = futex_table_.erase(futex_key);
    if (!node) {
        // nothing blocked on this futex if we can't find it
        return ZX_OK;
    }
    DEBUG_ASSERT(node->GetKey() == futex_key);

    bool any_woken = false;
    FutexNode* remaining_waiters =
        FutexNode::WakeThreads(node, count, futex_key, &any_woken);

    if (remaining_waiters) {
        DEBUG_ASSERT(remaining_waiters->GetKey() == futex_key);
        futex_table_.insert(remaining_waiters);
    }

    if (any_woken) {
        lock.release();
        thread_reschedule();
    }

    return ZX_OK;
}

zx_status_t FutexContext::FutexRequeue(user_in_ptr<const int> wake_ptr, uint32_t wake_count, int current_value,
                                       user_in_ptr<const int> requeue_ptr, uint32_t requeue_count) {
    LTRACE_ENTRY;

    if ((requeue_ptr.get() == nullptr) && requeue_count)
        return ZX_ERR_INVALID_ARGS;

    AutoLock lock(&lock_);

    int value;
    zx_status_t result = wake_ptr.copy_from_user(&value);
    if (result != ZX_OK) return result;
    if (value != current_value) return ZX_ERR_BAD_STATE;

    uintptr_t wake_key = reinterpret_cast<uintptr_t>(wake_ptr.get());
    uintptr_t requeue_key = reinterpret_cast<uintptr_t>(requeue_ptr.get());
    if (wake_key == requeue_key) return ZX_ERR_INVALID_ARGS;
    if (wake_key % sizeof(int) || requeue_key % sizeof(int))
        return ZX_ERR_INVALID_ARGS;

    // This must happen before RemoveFromHead() calls set_hash_key() on
    // nodes below, because operations on futex_table_ look at the GetKey
    // field of the list head nodes for wake_key and requeue_key.
    FutexNode* node = futex_table_.erase(wake_key);
    if (!node) {
        // nothing blocked on this futex if we can't find it
        return ZX_OK;
    }

    bool any_woken = false;
    if (wake_count > 0) {
        node = FutexNode::WakeThreads(node, wake_count, wake_key, &any_woken);
    }

    // node is now the head of wake_ptr futex after possibly removing some threads to wake
    if (node != nullptr) {
        if (requeue_count > 0) {
            // head and tail of list of nodes to requeue
            FutexNode* requeue_head = node;
            node = FutexNode::RemoveFromHead(node, requeue_count,
                                             wake_key, requeue_key);

            // now requeue our nodes to requeue_ptr mutex
            DEBUG_ASSERT(requeue_head->GetKey() == requeue_key);
            QueueNodesLocked(requeue_head);
        }
    }

    // add any remaining nodes back to wake_key futex
    if (node != nullptr) {
        DEBUG_ASSERT(node->GetKey() == wake_key);
        futex_table_.insert(node);
    }

    if (any_woken) {
        lock.release();
        thread_reschedule();
    }

    return ZX_OK;
}

void FutexContext::QueueNodesLocked(FutexNode* head) {
    DEBUG_ASSERT(lock_.IsHeld());

    FutexNode::HashTable::iterator iter;

    // Attempt to insert this FutexNode into the hash table.  If the insert
    // succeeds, then the current thread is first to block on this futex and we
    // are finished.  If the insert fails, then there is already a thread
    // waiting on this futex.  Add ourselves to that thread's list.
    if (!futex_table_.insert_or_find(head, &iter))
        iter->AppendList(head);
}

// This attempts to unqueue a thread (which may or may not be waiting on a
// futex), given its FutexNode.  This returns whether the FutexNode was
// found and removed from a futex wait queue.
bool FutexContext::UnqueueNodeLocked(FutexNode* node) {
    DEBUG_ASSERT(lock_.IsHeld());

    if (!node->IsInQueue())
        return false;

    // Note: When UnqueueNode() is called from FutexWait(), it might be
    // tempting to reuse the futex key that was passed to FutexWait().
    // However, that could be out of date if the thread was requeued by
    // FutexRequeue(), so we need to re-get the hash table key here.
    uintptr_t futex_key = node->GetKey();

    FutexNode* old_head = futex_table_.erase(futex_key);
    DEBUG_ASSERT(old_head);
    FutexNode* new_head = FutexNode::RemoveNodeFromList(old_head, node);
    if (new_head)
        futex_table_.insert(new_head);
    return true;
}