1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright 2023 Red Hat 4 */ 5 6 #include "wait-queue.h" 7 8 #include <linux/device-mapper.h> 9 10 #include "permassert.h" 11 12 #include "status-codes.h" 13 14 /** 15 * vdo_waitq_enqueue_waiter() - Add a waiter to the tail end of a waitq. 16 * @waitq: The vdo_wait_queue to which to add the waiter. 17 * @waiter: The waiter to add to the waitq. 18 * 19 * The waiter must not already be waiting in a waitq. 20 */ 21 void vdo_waitq_enqueue_waiter(struct vdo_wait_queue *waitq, struct vdo_waiter *waiter) 22 { 23 BUG_ON(waiter->next_waiter != NULL); 24 25 if (waitq->last_waiter == NULL) { 26 /* 27 * The waitq is empty, so form the initial circular list by self-linking the 28 * initial waiter. 29 */ 30 waiter->next_waiter = waiter; 31 } else { 32 /* Splice the new waiter in at the end of the waitq. */ 33 waiter->next_waiter = waitq->last_waiter->next_waiter; 34 waitq->last_waiter->next_waiter = waiter; 35 } 36 37 /* In both cases, the waiter we added to the ring becomes the last waiter. */ 38 waitq->last_waiter = waiter; 39 waitq->length += 1; 40 } 41 42 /** 43 * vdo_waitq_transfer_all_waiters() - Transfer all waiters from one waitq to 44 * a second waitq, emptying the first waitq. 45 * @from_waitq: The waitq containing the waiters to move. 46 * @to_waitq: The waitq that will receive the waiters from the first waitq. 47 */ 48 void vdo_waitq_transfer_all_waiters(struct vdo_wait_queue *from_waitq, 49 struct vdo_wait_queue *to_waitq) 50 { 51 /* If the source waitq is empty, there's nothing to do. */ 52 if (!vdo_waitq_has_waiters(from_waitq)) 53 return; 54 55 if (vdo_waitq_has_waiters(to_waitq)) { 56 /* 57 * Both are non-empty. Splice the two circular lists together 58 * by swapping the next (head) pointers in the list tails. 59 */ 60 struct vdo_waiter *from_head = from_waitq->last_waiter->next_waiter; 61 struct vdo_waiter *to_head = to_waitq->last_waiter->next_waiter; 62 63 to_waitq->last_waiter->next_waiter = from_head; 64 from_waitq->last_waiter->next_waiter = to_head; 65 } 66 67 to_waitq->last_waiter = from_waitq->last_waiter; 68 to_waitq->length += from_waitq->length; 69 vdo_waitq_init(from_waitq); 70 } 71 72 /** 73 * vdo_waitq_notify_all_waiters() - Notify all the entries waiting in a waitq. 74 * @waitq: The vdo_wait_queue containing the waiters to notify. 75 * @callback: The function to call to notify each waiter, or NULL to invoke the callback field 76 * registered in each waiter. 77 * @context: The context to pass to the callback function. 78 * 79 * Notifies all the entries waiting in a waitq to continue execution by invoking a callback 80 * function on each of them in turn. The waitq is copied and emptied before invoking any callbacks, 81 * and only the waiters that were in the waitq at the start of the call will be notified. 82 */ 83 void vdo_waitq_notify_all_waiters(struct vdo_wait_queue *waitq, 84 vdo_waiter_callback_fn callback, void *context) 85 { 86 /* 87 * Copy and empty the waitq first, avoiding the possibility of an infinite 88 * loop if entries are returned to the waitq by the callback function. 89 */ 90 struct vdo_wait_queue waiters; 91 92 vdo_waitq_init(&waiters); 93 vdo_waitq_transfer_all_waiters(waitq, &waiters); 94 95 /* Drain the copied waitq, invoking the callback on every entry. */ 96 while (vdo_waitq_has_waiters(&waiters)) 97 vdo_waitq_notify_next_waiter(&waiters, callback, context); 98 } 99 100 /** 101 * vdo_waitq_get_first_waiter() - Return the waiter that is at the head end of a waitq. 102 * @waitq: The vdo_wait_queue from which to get the first waiter. 103 * 104 * Return: The first (oldest) waiter in the waitq, or NULL if the waitq is empty. 105 */ 106 struct vdo_waiter *vdo_waitq_get_first_waiter(const struct vdo_wait_queue *waitq) 107 { 108 struct vdo_waiter *last_waiter = waitq->last_waiter; 109 110 if (last_waiter == NULL) { 111 /* There are no waiters, so we're done. */ 112 return NULL; 113 } 114 115 /* The waitq is circular, so the last entry links to the head of the waitq. */ 116 return last_waiter->next_waiter; 117 } 118 119 /** 120 * vdo_waitq_dequeue_matching_waiters() - Remove all waiters that match based on the specified 121 * matching method and append them to a vdo_wait_queue. 122 * @waitq: The vdo_wait_queue to process. 123 * @waiter_match: The method to determine matching. 124 * @match_context: Contextual info for the match method. 125 * @matched_waitq: A wait_waitq to store matches. 126 */ 127 void vdo_waitq_dequeue_matching_waiters(struct vdo_wait_queue *waitq, 128 vdo_waiter_match_fn waiter_match, 129 void *match_context, 130 struct vdo_wait_queue *matched_waitq) 131 { 132 struct vdo_wait_queue iteration_waitq; 133 134 vdo_waitq_init(&iteration_waitq); 135 vdo_waitq_transfer_all_waiters(waitq, &iteration_waitq); 136 137 while (vdo_waitq_has_waiters(&iteration_waitq)) { 138 struct vdo_waiter *waiter = vdo_waitq_dequeue_waiter(&iteration_waitq); 139 140 vdo_waitq_enqueue_waiter((waiter_match(waiter, match_context) ? 141 matched_waitq : waitq), waiter); 142 } 143 } 144 145 /** 146 * vdo_waitq_dequeue_waiter() - Remove the first (oldest) waiter from a waitq. 147 * @waitq: The vdo_wait_queue from which to remove the first entry. 148 * 149 * The caller will be responsible for waking the waiter by continuing its 150 * execution appropriately. 151 * 152 * Return: The first (oldest) waiter in the waitq, or NULL if the waitq is empty. 153 */ 154 struct vdo_waiter *vdo_waitq_dequeue_waiter(struct vdo_wait_queue *waitq) 155 { 156 struct vdo_waiter *first_waiter = vdo_waitq_get_first_waiter(waitq); 157 struct vdo_waiter *last_waiter = waitq->last_waiter; 158 159 if (first_waiter == NULL) 160 return NULL; 161 162 if (first_waiter == last_waiter) { 163 /* The waitq has a single entry, so empty it by nulling the tail. */ 164 waitq->last_waiter = NULL; 165 } else { 166 /* 167 * The waitq has multiple waiters, so splice the first waiter out 168 * of the circular waitq. 169 */ 170 last_waiter->next_waiter = first_waiter->next_waiter; 171 } 172 173 /* The waiter is no longer in a waitq. */ 174 first_waiter->next_waiter = NULL; 175 waitq->length -= 1; 176 177 return first_waiter; 178 } 179 180 /** 181 * vdo_waitq_notify_next_waiter() - Notify the next entry waiting in a waitq. 182 * @waitq: The vdo_wait_queue containing the waiter to notify. 183 * @callback: The function to call to notify the waiter, or NULL to invoke the callback field 184 * registered in the waiter. 185 * @context: The context to pass to the callback function. 186 * 187 * Notifies the next entry waiting in a waitq to continue execution by invoking a callback function 188 * on it after removing it from the waitq. 189 * 190 * Return: true if there was a waiter in the waitq. 191 */ 192 bool vdo_waitq_notify_next_waiter(struct vdo_wait_queue *waitq, 193 vdo_waiter_callback_fn callback, void *context) 194 { 195 struct vdo_waiter *waiter = vdo_waitq_dequeue_waiter(waitq); 196 197 if (waiter == NULL) 198 return false; 199 200 if (callback == NULL) 201 callback = waiter->callback; 202 callback(waiter, context); 203 204 return true; 205 } 206