drivers/md/dm-vdo/priority-table.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #include "priority-table.h"
   7
   8 #include <linux/log2.h>
   9
  10 #include "errors.h"
  11 #include "memory-alloc.h"
  12 #include "permassert.h"
  13
  14 #include "status-codes.h"
  15
  16 /* We use a single 64-bit search vector, so the maximum priority is 63 */
  17 #define MAX_PRIORITY 63
  18
  19 /*
  20  * All the entries with the same priority are queued in a circular list in a bucket for that
  21  * priority. The table is essentially an array of buckets.
  22  */
  23 struct bucket {
  24         /*
  25          * The head of a queue of table entries, all having the same priority
  26          */
  27         struct list_head queue;
  28         /* The priority of all the entries in this bucket */
  29         unsigned int priority;
  30 };
  31
  32 /*
  33  * A priority table is an array of buckets, indexed by priority. New entries are added to the end
  34  * of the queue in the appropriate bucket. The dequeue operation finds the highest-priority
  35  * non-empty bucket by searching a bit vector represented as a single 8-byte word, which is very
  36  * fast with compiler and CPU support.
  37  */
  38 struct priority_table {
  39         /* The maximum priority of entries that may be stored in this table */
  40         unsigned int max_priority;
  41         /* A bit vector flagging all buckets that are currently non-empty */
  42         u64 search_vector;
  43         /* The array of all buckets, indexed by priority */
  44         struct bucket buckets[];
  45 };
  46
  47 /**
  48  * vdo_make_priority_table() - Allocate and initialize a new priority_table.
  49  * @max_priority: The maximum priority value for table entries.
  50  * @table_ptr: A pointer to hold the new table.
  51  *
  52  * Return: VDO_SUCCESS or an error code.
  53  */
  54 int vdo_make_priority_table(unsigned int max_priority, struct priority_table **table_ptr)
  55 {
  56         struct priority_table *table;
  57         int result;
  58         unsigned int priority;
  59
  60         if (max_priority > MAX_PRIORITY)
  61                 return UDS_INVALID_ARGUMENT;
  62
  63         result = vdo_allocate_extended(struct priority_table, max_priority + 1,
  64                                        struct bucket, __func__, &table);
  65         if (result != VDO_SUCCESS)
  66                 return result;
  67
  68         for (priority = 0; priority <= max_priority; priority++) {
  69                 struct bucket *bucket = &table->buckets[priority];
  70
  71                 bucket->priority = priority;
  72                 INIT_LIST_HEAD(&bucket->queue);
  73         }
  74
  75         table->max_priority = max_priority;
  76         table->search_vector = 0;
  77
  78         *table_ptr = table;
  79         return VDO_SUCCESS;
  80 }
  81
  82 /**
  83  * vdo_free_priority_table() - Free a priority_table.
  84  * @table: The table to free.
  85  *
  86  * The table does not own the entries stored in it and they are not freed by this call.
  87  */
  88 void vdo_free_priority_table(struct priority_table *table)
  89 {
  90         if (table == NULL)
  91                 return;
  92
  93         /*
  94          * Unlink the buckets from any entries still in the table so the entries won't be left with
  95          * dangling pointers to freed memory.
  96          */
  97         vdo_reset_priority_table(table);
  98
  99         vdo_free(table);
 100 }
 101
 102 /**
 103  * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when
 104  *                          newly constructed.
 105  * @table: The table to reset.
 106  *
 107  * The table does not own the entries stored in it and they are not freed (or even unlinked from
 108  * each other) by this call.
 109  */
 110 void vdo_reset_priority_table(struct priority_table *table)
 111 {
 112         unsigned int priority;
 113
 114         table->search_vector = 0;
 115         for (priority = 0; priority <= table->max_priority; priority++)
 116                 list_del_init(&table->buckets[priority].queue);
 117 }
 118
 119 /**
 120  * vdo_priority_table_enqueue() - Add a new entry to the priority table, appending it to the queue
 121  *                                for entries with the specified priority.
 122  * @table: The table in which to store the entry.
 123  * @priority: The priority of the entry.
 124  * @entry: The list_head embedded in the entry to store in the table (the caller must have
 125  *         initialized it).
 126  */
 127 void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority,
 128                                 struct list_head *entry)
 129 {
 130         VDO_ASSERT_LOG_ONLY((priority <= table->max_priority),
 131                             "entry priority must be valid for the table");
 132
 133         /* Append the entry to the queue in the specified bucket. */
 134         list_move_tail(entry, &table->buckets[priority].queue);
 135
 136         /* Flag the bucket in the search vector since it must be non-empty. */
 137         table->search_vector |= (1ULL << priority);
 138 }
 139
 140 static inline void mark_bucket_empty(struct priority_table *table, struct bucket *bucket)
 141 {
 142         table->search_vector &= ~(1ULL << bucket->priority);
 143 }
 144
 145 /**
 146  * vdo_priority_table_dequeue() - Find the highest-priority entry in the table, remove it from the
 147  *                                table, and return it.
 148  * @table: The priority table from which to remove an entry.
 149  *
 150  * If there are multiple entries with the same priority, the one that has been in the table with
 151  * that priority the longest will be returned.
 152  *
 153  * Return: The dequeued entry, or NULL if the table is currently empty.
 154  */
 155 struct list_head *vdo_priority_table_dequeue(struct priority_table *table)
 156 {
 157         struct bucket *bucket;
 158         struct list_head *entry;
 159         int top_priority;
 160
 161         if (table->search_vector == 0) {
 162                 /* All buckets are empty. */
 163                 return NULL;
 164         }
 165
 166         /*
 167          * Find the highest priority non-empty bucket by finding the highest-order non-zero bit in
 168          * the search vector.
 169          */
 170         top_priority = ilog2(table->search_vector);
 171
 172         /* Dequeue the first entry in the bucket. */
 173         bucket = &table->buckets[top_priority];
 174         entry = bucket->queue.next;
 175         list_del_init(entry);
 176
 177         /* Clear the bit in the search vector if the bucket has been emptied. */
 178         if (list_empty(&bucket->queue))
 179                 mark_bucket_empty(table, bucket);
 180
 181         return entry;
 182 }
 183
 184 /**
 185  * vdo_priority_table_remove() - Remove a specified entry from its priority table.
 186  * @table: The table from which to remove the entry.
 187  * @entry: The entry to remove from the table.
 188  */
 189 void vdo_priority_table_remove(struct priority_table *table, struct list_head *entry)
 190 {
 191         struct list_head *next_entry;
 192
 193         /*
 194          * We can't guard against calls where the entry is on a list for a different table, but
 195          * it's easy to deal with an entry not in any table or list.
 196          */
 197         if (list_empty(entry))
 198                 return;
 199
 200         /*
 201          * Remove the entry from the bucket list, remembering a pointer to another entry in the
 202          * ring.
 203          */
 204         next_entry = entry->next;
 205         list_del_init(entry);
 206
 207         /*
 208          * If the rest of the list is now empty, the next node must be the list head in the bucket
 209          * and we can use it to update the search vector.
 210          */
 211         if (list_empty(next_entry))
 212                 mark_bucket_empty(table, list_entry(next_entry, struct bucket, queue));
 213 }
 214
 215 /**
 216  * vdo_is_priority_table_empty() - Return whether the priority table is empty.
 217  * @table: The table to check.
 218  *
 219  * Return: true if the table is empty.
 220  */
 221 bool vdo_is_priority_table_empty(struct priority_table *table)
 222 {
 223         return (table->search_vector == 0);
 224 }