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