1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /*
3 * Copyright 2023 Red Hat
4 */
5
6 #ifndef VDO_WAIT_QUEUE_H
7 #define VDO_WAIT_QUEUE_H
8
9 #include <linux/compiler.h>
10 #include <linux/types.h>
11
12 /**
13 * A vdo_wait_queue is a circular singly linked list of entries waiting to be notified
14 * of a change in a condition. Keeping a circular list allows the vdo_wait_queue
15 * structure to simply be a pointer to the tail (newest) entry, supporting
16 * constant-time enqueue and dequeue operations. A null pointer is an empty waitq.
17 *
18 * An empty waitq:
19 * waitq0.last_waiter -> NULL
20 *
21 * A singleton waitq:
22 * waitq1.last_waiter -> entry1 -> entry1 -> [...]
23 *
24 * A three-element waitq:
25 * waitq2.last_waiter -> entry3 -> entry1 -> entry2 -> entry3 -> [...]
26 *
27 * linux/wait.h's wait_queue_head is _not_ used because vdo_wait_queue's
28 * interface is much less complex (doesn't need locking, priorities or timers).
29 * Made possible by vdo's thread-based resource allocation and locking; and
30 * the polling nature of vdo_wait_queue consumers.
31 *
32 * FIXME: could be made to use a linux/list.h's list_head but its extra barriers
33 * really aren't needed. Nor is a doubly linked list, but vdo_wait_queue could
34 * make use of __list_del_clearprev() -- but that would compromise the ability
35 * to make full use of linux's list interface.
36 */
37
38 struct vdo_waiter;
39
40 struct vdo_wait_queue {
41 /* The tail of the queue, the last (most recently added) entry */
42 struct vdo_waiter *last_waiter;
43 /* The number of waiters currently in the queue */
44 size_t length;
45 };
46
47 /**
48 * vdo_waiter_callback_fn - Callback type that will be called to resume processing
49 * of a waiter after it has been removed from its wait queue.
50 */
51 typedef void (*vdo_waiter_callback_fn)(struct vdo_waiter *waiter, void *context);
52
53 /**
54 * vdo_waiter_match_fn - Method type for waiter matching methods.
55 *
56 * Returns false if the waiter does not match.
57 */
58 typedef bool (*vdo_waiter_match_fn)(struct vdo_waiter *waiter, void *context);
59
60 /* The structure for entries in a vdo_wait_queue. */
61 struct vdo_waiter {
62 /*
63 * The next waiter in the waitq. If this entry is the last waiter, then this
64 * is actually a pointer back to the head of the waitq.
65 */
66 struct vdo_waiter *next_waiter;
67
68 /* Optional waiter-specific callback to invoke when dequeuing this waiter. */
69 vdo_waiter_callback_fn callback;
70 };
71
72 /**
73 * vdo_waiter_is_waiting() - Check whether a waiter is waiting.
74 * @waiter: The waiter to check.
75 *
76 * Return: true if the waiter is on some vdo_wait_queue.
77 */
vdo_waiter_is_waiting(struct vdo_waiter * waiter)78 static inline bool vdo_waiter_is_waiting(struct vdo_waiter *waiter)
79 {
80 return (waiter->next_waiter != NULL);
81 }
82
83 /**
84 * vdo_waitq_init() - Initialize a vdo_wait_queue.
85 * @waitq: The vdo_wait_queue to initialize.
86 */
vdo_waitq_init(struct vdo_wait_queue * waitq)87 static inline void vdo_waitq_init(struct vdo_wait_queue *waitq)
88 {
89 *waitq = (struct vdo_wait_queue) {
90 .last_waiter = NULL,
91 .length = 0,
92 };
93 }
94
95 /**
96 * vdo_waitq_has_waiters() - Check whether a vdo_wait_queue has any entries waiting.
97 * @waitq: The vdo_wait_queue to query.
98 *
99 * Return: true if there are any waiters in the waitq.
100 */
vdo_waitq_has_waiters(const struct vdo_wait_queue * waitq)101 static inline bool __must_check vdo_waitq_has_waiters(const struct vdo_wait_queue *waitq)
102 {
103 return (waitq->last_waiter != NULL);
104 }
105
106 void vdo_waitq_enqueue_waiter(struct vdo_wait_queue *waitq,
107 struct vdo_waiter *waiter);
108
109 struct vdo_waiter *vdo_waitq_dequeue_waiter(struct vdo_wait_queue *waitq);
110
111 void vdo_waitq_notify_all_waiters(struct vdo_wait_queue *waitq,
112 vdo_waiter_callback_fn callback, void *context);
113
114 bool vdo_waitq_notify_next_waiter(struct vdo_wait_queue *waitq,
115 vdo_waiter_callback_fn callback, void *context);
116
117 void vdo_waitq_transfer_all_waiters(struct vdo_wait_queue *from_waitq,
118 struct vdo_wait_queue *to_waitq);
119
120 struct vdo_waiter *vdo_waitq_get_first_waiter(const struct vdo_wait_queue *waitq);
121
122 void vdo_waitq_dequeue_matching_waiters(struct vdo_wait_queue *waitq,
123 vdo_waiter_match_fn waiter_match,
124 void *match_context,
125 struct vdo_wait_queue *matched_waitq);
126
127 /**
128 * vdo_waitq_num_waiters() - Return the number of waiters in a vdo_wait_queue.
129 * @waitq: The vdo_wait_queue to query.
130 *
131 * Return: The number of waiters in the waitq.
132 */
vdo_waitq_num_waiters(const struct vdo_wait_queue * waitq)133 static inline size_t __must_check vdo_waitq_num_waiters(const struct vdo_wait_queue *waitq)
134 {
135 return waitq->length;
136 }
137
138 #endif /* VDO_WAIT_QUEUE_H */
139