xref: /linux/drivers/md/dm-vdo/priority-table.c (revision 79790b6818e96c58fe2bffee1b418c16e64e7b80)
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  */
vdo_make_priority_table(unsigned int max_priority,struct priority_table ** table_ptr)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  */
vdo_free_priority_table(struct priority_table * table)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  */
vdo_reset_priority_table(struct priority_table * table)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  */
vdo_priority_table_enqueue(struct priority_table * table,unsigned int priority,struct list_head * entry)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 
mark_bucket_empty(struct priority_table * table,struct bucket * bucket)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  */
vdo_priority_table_dequeue(struct priority_table * table)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  */
vdo_priority_table_remove(struct priority_table * table,struct list_head * entry)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  */
vdo_is_priority_table_empty(struct priority_table * table)221 bool vdo_is_priority_table_empty(struct priority_table *table)
222 {
223 	return (table->search_vector == 0);
224 }
225