drivers/md/dm-vdo/wait-queue.h

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