kernel/object/include/object/futex_node.h

// 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

#pragma once

#include <kernel/thread.h>
#include <kernel/wait.h>
#include <list.h>
#include <zircon/types.h>
#include <fbl/intrusive_hash_table.h>
#include <fbl/mutex.h>

// Node for linked list of threads blocked on a futex
// Intended to be embedded within a ThreadDispatcher Instance
class FutexNode : public fbl::SinglyLinkedListable<FutexNode*> {
public:
    using HashTable = fbl::HashTable<uintptr_t, FutexNode*>;

    FutexNode();
    ~FutexNode();

    FutexNode(const FutexNode &) = delete;
    FutexNode& operator=(const FutexNode &) = delete;

    bool IsInQueue() const;
    void SetAsSingletonList();

    // adds a list of nodes to our tail
    void AppendList(FutexNode* head);

    static FutexNode* RemoveNodeFromList(FutexNode* list_head, FutexNode* node);

    static FutexNode* WakeThreads(FutexNode* node, uint32_t count,
                                  uintptr_t old_hash_key);

    static FutexNode* RemoveFromHead(FutexNode* list_head,
                                     uint32_t count,
                                     uintptr_t old_hash_key,
                                     uintptr_t new_hash_key);

    // This must be called with |mutex| held and returns without |mutex| held.
    zx_status_t BlockThread(fbl::Mutex* mutex, zx_time_t deadline) TA_REL(mutex);

    void set_hash_key(uintptr_t key) {
        hash_key_ = key;
    }

    // Trait implementation for fbl::HashTable
    uintptr_t GetKey() const { return hash_key_; }
    static size_t GetHash(uintptr_t key) { return (key >> 3); }

private:
    static void RelinkAsAdjacent(FutexNode* node1, FutexNode* node2);
    static void SpliceNodes(FutexNode* node1, FutexNode* node2);

    void WakeThread();

    void MarkAsNotInQueue();

    // hash_key_ contains the futex address.  This field has two roles:
    //  * It is used by FutexWait() to determine which queue to remove the
    //    thread from when a wait operation times out.
    //  * Additionally, when this FutexNode is the head of a futex wait
    //    queue, this field is used by the HashTable (because it uses
    //    intrusive SinglyLinkedLists).
    uintptr_t hash_key_;

    // Used for waking the thread corresponding to the FutexNode.
    WaitQueue wait_queue_;

    // queue_prev_ and queue_next_ are used for maintaining a circular
    // doubly-linked list of threads that are waiting on one futex address.
    //  * When the list contains only this node, queue_prev_ and
    //    queue_next_ both point back to this node.
    //  * When the thread is not waiting on a futex, queue_next_ is null.
    FutexNode* queue_prev_ = nullptr;
    FutexNode* queue_next_ = nullptr;
};