1 // Copyright 2016 The Fuchsia Authors
2 //
3 // Use of this source code is governed by a MIT-style
4 // license that can be found in the LICENSE file or at
5 // https://opensource.org/licenses/MIT
6 
7 #pragma once
8 
9 #include <kernel/lockdep.h>
10 #include <kernel/thread.h>
11 #include <kernel/wait.h>
12 #include <list.h>
13 #include <zircon/types.h>
14 #include <fbl/intrusive_hash_table.h>
15 #include <fbl/mutex.h>
16 
17 // Node for linked list of threads blocked on a futex
18 // Intended to be embedded within a ThreadDispatcher Instance
19 class FutexNode : public fbl::SinglyLinkedListable<FutexNode*> {
20 public:
21     using HashTable = fbl::HashTable<uintptr_t, FutexNode*>;
22 
23     FutexNode();
24     ~FutexNode();
25 
26     FutexNode(const FutexNode &) = delete;
27     FutexNode& operator=(const FutexNode &) = delete;
28 
29     bool IsInQueue() const;
30     void SetAsSingletonList();
31 
32     // adds a list of nodes to our tail
33     void AppendList(FutexNode* head);
34 
35     static FutexNode* RemoveNodeFromList(FutexNode* list_head, FutexNode* node);
36 
37     static FutexNode* WakeThreads(FutexNode* node, uint32_t count,
38                                   uintptr_t old_hash_key);
39 
40     static FutexNode* RemoveFromHead(FutexNode* list_head,
41                                      uint32_t count,
42                                      uintptr_t old_hash_key,
43                                      uintptr_t new_hash_key);
44 
45     // This must be called with a guard held in the calling scope. Releases the
46     // guard and does not reacquire it.
47     zx_status_t BlockThread(Guard<fbl::Mutex>&& adopt_guard, zx_time_t deadline, TimerSlack slack);
48 
set_hash_key(uintptr_t key)49     void set_hash_key(uintptr_t key) {
50         hash_key_ = key;
51     }
52 
53     // Trait implementation for fbl::HashTable
GetKey()54     uintptr_t GetKey() const { return hash_key_; }
GetHash(uintptr_t key)55     static size_t GetHash(uintptr_t key) { return (key >> 3); }
56 
57 private:
58     static void RelinkAsAdjacent(FutexNode* node1, FutexNode* node2);
59     static void SpliceNodes(FutexNode* node1, FutexNode* node2);
60 
61     void WakeThread();
62 
63     void MarkAsNotInQueue();
64 
65     // hash_key_ contains the futex address.  This field has two roles:
66     //  * It is used by FutexWait() to determine which queue to remove the
67     //    thread from when a wait operation times out.
68     //  * Additionally, when this FutexNode is the head of a futex wait
69     //    queue, this field is used by the HashTable (because it uses
70     //    intrusive SinglyLinkedLists).
71     uintptr_t hash_key_;
72 
73     // Used for waking the thread corresponding to the FutexNode.
74     WaitQueue wait_queue_;
75 
76     // queue_prev_ and queue_next_ are used for maintaining a circular
77     // doubly-linked list of threads that are waiting on one futex address.
78     //  * When the list contains only this node, queue_prev_ and
79     //    queue_next_ both point back to this node.
80     //  * When the thread is not waiting on a futex, queue_next_ is null.
81     FutexNode* queue_prev_ = nullptr;
82     FutexNode* queue_next_ = nullptr;
83 };
84