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 */
23struct 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 */
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 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 */
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 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 */
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 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 */
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 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 */
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, 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 */
221bool vdo_is_priority_table_empty(struct priority_table *table)
222{
223	return (table->search_vector == 0);
224}
225