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
 38struct vdo_waiter;
 39
 40struct 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 */
 51typedef 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 */
 58typedef bool (*vdo_waiter_match_fn)(struct vdo_waiter *waiter, void *context);
 59
 60/* The structure for entries in a vdo_wait_queue. */
 61struct 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 */
 78static 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 */
 87static 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 */
101static inline bool __must_check vdo_waitq_has_waiters(const struct vdo_wait_queue *waitq)
102{
103	return (waitq->last_waiter != NULL);
104}
105
106void vdo_waitq_enqueue_waiter(struct vdo_wait_queue *waitq,
107			      struct vdo_waiter *waiter);
108
109struct vdo_waiter *vdo_waitq_dequeue_waiter(struct vdo_wait_queue *waitq);
110
111void vdo_waitq_notify_all_waiters(struct vdo_wait_queue *waitq,
112				  vdo_waiter_callback_fn callback, void *context);
113
114bool vdo_waitq_notify_next_waiter(struct vdo_wait_queue *waitq,
115				  vdo_waiter_callback_fn callback, void *context);
116
117void vdo_waitq_transfer_all_waiters(struct vdo_wait_queue *from_waitq,
118				    struct vdo_wait_queue *to_waitq);
119
120struct vdo_waiter *vdo_waitq_get_first_waiter(const struct vdo_wait_queue *waitq);
121
122void 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 */
133static 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 */