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 } 225