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(max_priority + 1, buckets, __func__, &table); 64 if (result != VDO_SUCCESS) 65 return result; 66 67 for (priority = 0; priority <= max_priority; priority++) { 68 struct bucket *bucket = &table->buckets[priority]; 69 70 bucket->priority = priority; 71 INIT_LIST_HEAD(&bucket->queue); 72 } 73 74 table->max_priority = max_priority; 75 table->search_vector = 0; 76 77 *table_ptr = table; 78 return VDO_SUCCESS; 79 } 80 81 /** 82 * vdo_free_priority_table() - Free a priority_table. 83 * @table: The table to free. 84 * 85 * The table does not own the entries stored in it and they are not freed by this call. 86 */ 87 void vdo_free_priority_table(struct priority_table *table) 88 { 89 if (table == NULL) 90 return; 91 92 /* 93 * Unlink the buckets from any entries still in the table so the entries won't be left with 94 * dangling pointers to freed memory. 95 */ 96 vdo_reset_priority_table(table); 97 98 vdo_free(table); 99 } 100 101 /** 102 * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when 103 * newly constructed. 104 * @table: The table to reset. 105 * 106 * The table does not own the entries stored in it and they are not freed (or even unlinked from 107 * each other) by this call. 108 */ 109 void vdo_reset_priority_table(struct priority_table *table) 110 { 111 unsigned int priority; 112 113 table->search_vector = 0; 114 for (priority = 0; priority <= table->max_priority; priority++) 115 list_del_init(&table->buckets[priority].queue); 116 } 117 118 /** 119 * vdo_priority_table_enqueue() - Add a new entry to the priority table, appending it to the queue 120 * for entries with the specified priority. 121 * @table: The table in which to store the entry. 122 * @priority: The priority of the entry. 123 * @entry: The list_head embedded in the entry to store in the table (the caller must have 124 * initialized it). 125 */ 126 void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority, 127 struct list_head *entry) 128 { 129 VDO_ASSERT_LOG_ONLY((priority <= table->max_priority), 130 "entry priority must be valid for the table"); 131 132 /* Append the entry to the queue in the specified bucket. */ 133 list_move_tail(entry, &table->buckets[priority].queue); 134 135 /* Flag the bucket in the search vector since it must be non-empty. */ 136 table->search_vector |= (1ULL << priority); 137 } 138 139 static inline void mark_bucket_empty(struct priority_table *table, struct bucket *bucket) 140 { 141 table->search_vector &= ~(1ULL << bucket->priority); 142 } 143 144 /** 145 * vdo_priority_table_dequeue() - Find the highest-priority entry in the table, remove it from the 146 * table, and return it. 147 * @table: The priority table from which to remove an entry. 148 * 149 * If there are multiple entries with the same priority, the one that has been in the table with 150 * that priority the longest will be returned. 151 * 152 * Return: The dequeued entry, or NULL if the table is currently empty. 153 */ 154 struct list_head *vdo_priority_table_dequeue(struct priority_table *table) 155 { 156 struct bucket *bucket; 157 struct list_head *entry; 158 int top_priority; 159 160 if (table->search_vector == 0) { 161 /* All buckets are empty. */ 162 return NULL; 163 } 164 165 /* 166 * Find the highest priority non-empty bucket by finding the highest-order non-zero bit in 167 * the search vector. 168 */ 169 top_priority = ilog2(table->search_vector); 170 171 /* Dequeue the first entry in the bucket. */ 172 bucket = &table->buckets[top_priority]; 173 entry = bucket->queue.next; 174 list_del_init(entry); 175 176 /* Clear the bit in the search vector if the bucket has been emptied. */ 177 if (list_empty(&bucket->queue)) 178 mark_bucket_empty(table, bucket); 179 180 return entry; 181 } 182 183 /** 184 * vdo_priority_table_remove() - Remove a specified entry from its priority table. 185 * @table: The table from which to remove the entry. 186 * @entry: The entry to remove from the table. 187 */ 188 void vdo_priority_table_remove(struct priority_table *table, struct list_head *entry) 189 { 190 struct list_head *next_entry; 191 192 /* 193 * We can't guard against calls where the entry is on a list for a different table, but 194 * it's easy to deal with an entry not in any table or list. 195 */ 196 if (list_empty(entry)) 197 return; 198 199 /* 200 * Remove the entry from the bucket list, remembering a pointer to another entry in the 201 * list. 202 */ 203 next_entry = entry->next; 204 list_del_init(entry); 205 206 /* 207 * If the rest of the list is now empty, the next node must be the list head in the bucket 208 * and we can use it to update the search vector. 209 */ 210 if (list_empty(next_entry)) 211 mark_bucket_empty(table, list_entry(next_entry, struct bucket, queue)); 212 } 213 214 /** 215 * vdo_is_priority_table_empty() - Return whether the priority table is empty. 216 * @table: The table to check. 217 * 218 * Return: true if the table is empty. 219 */ 220 bool vdo_is_priority_table_empty(struct priority_table *table) 221 { 222 return (table->search_vector == 0); 223 } 224