225 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright 2023 Red Hat4 */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 6318 19/*20 * All the entries with the same priority are queued in a circular list in a bucket for that21 * priority. The table is essentially an array of buckets.22 */23struct bucket {24 /*25 * The head of a queue of table entries, all having the same priority26 */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 end34 * of the queue in the appropriate bucket. The dequeue operation finds the highest-priority35 * non-empty bucket by searching a bit vector represented as a single 8-byte word, which is very36 * fast with compiler and CPU support.37 */38struct 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 */54int 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 */88void 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 with95 * 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 when104 * 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 from108 * each other) by this call.109 */110void 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 queue121 * 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 have125 * initialized it).126 */127void 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 140static 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 the147 * 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 with151 * that priority the longest will be returned.152 *153 * Return: The dequeued entry, or NULL if the table is currently empty.154 */155struct 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 in168 * 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 */189void 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, but195 * 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 the202 * 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 bucket209 * 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 */221bool vdo_is_priority_table_empty(struct priority_table *table)222{223 return (table->search_vector == 0);224}225