plist.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * lib/plist.c
  4 *
  5 * Descending-priority-sorted double-linked list
  6 *
  7 * (C) 2002-2003 Intel Corp
  8 * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
  9 *
 10 * 2001-2005 (c) MontaVista Software, Inc.
 11 * Daniel Walker <dwalker@mvista.com>
 12 *
 13 * (C) 2005 Linutronix GmbH, Thomas Gleixner <tglx@kernel.org>
 14 *
 15 * Simplifications of the original code by
 16 * Oleg Nesterov <oleg@tv-sign.ru>
 17 *
 18 * Based on simple lists (include/linux/list.h).
 19 *
 20 * This file contains the add / del functions which are considered to
 21 * be too large to inline. See include/linux/plist.h for further
 22 * information.
 23 */
 24
 25#include <linux/bug.h>
 26#include <linux/plist.h>
 27
 28#ifdef CONFIG_DEBUG_PLIST
 29
 30static struct plist_head test_head;
 31
 32static void plist_check_prev_next(struct list_head *t, struct list_head *p,
 33				  struct list_head *n)
 34{
 35	WARN(n->prev != p || p->next != n,
 36			"top: %p, n: %p, p: %p\n"
 37			"prev: %p, n: %p, p: %p\n"
 38			"next: %p, n: %p, p: %p\n",
 39			 t, t->next, t->prev,
 40			p, p->next, p->prev,
 41			n, n->next, n->prev);
 42}
 43
 44static void plist_check_list(struct list_head *top)
 45{
 46	struct list_head *prev = top, *next = top->next;
 47
 48	plist_check_prev_next(top, prev, next);
 49	while (next != top) {
 50		prev = next;
 51		next = prev->next;
 52		plist_check_prev_next(top, prev, next);
 53	}
 54}
 55
 56static void plist_check_head(struct plist_head *head)
 57{
 58	if (!plist_head_empty(head))
 59		plist_check_list(&plist_first(head)->prio_list);
 60	plist_check_list(&head->node_list);
 61}
 62
 63#else
 64# define plist_check_head(h)	do { } while (0)
 65#endif
 66
 67/**
 68 * plist_add - add @node to @head
 69 *
 70 * @node:	&struct plist_node pointer
 71 * @head:	&struct plist_head pointer
 72 */
 73void plist_add(struct plist_node *node, struct plist_head *head)
 74{
 75	struct plist_node *first, *iter, *prev = NULL, *last, *reverse_iter;
 76	struct list_head *node_next = &head->node_list;
 77
 78	plist_check_head(head);
 79	WARN_ON(!plist_node_empty(node));
 80	WARN_ON(!list_empty(&node->prio_list));
 81
 82	if (plist_head_empty(head))
 83		goto ins_node;
 84
 85	first = iter = plist_first(head);
 86	last = reverse_iter = list_entry(first->prio_list.prev, struct plist_node, prio_list);
 87
 88	do {
 89		if (node->prio < iter->prio) {
 90			node_next = &iter->node_list;
 91			break;
 92		} else if (node->prio >= reverse_iter->prio) {
 93			prev = reverse_iter;
 94			iter = list_entry(reverse_iter->prio_list.next,
 95				struct plist_node, prio_list);
 96			if (likely(reverse_iter != last))
 97				node_next = &iter->node_list;
 98			break;
 99		}
100
101		prev = iter;
102		iter = list_entry(iter->prio_list.next,
103				struct plist_node, prio_list);
104		reverse_iter = list_entry(reverse_iter->prio_list.prev,
105				struct plist_node, prio_list);
106	} while (iter != first);
107
108	if (!prev || prev->prio != node->prio)
109		list_add_tail(&node->prio_list, &iter->prio_list);
110ins_node:
111	list_add_tail(&node->node_list, node_next);
112
113	plist_check_head(head);
114}
115
116/**
117 * plist_del - Remove a @node from plist.
118 *
119 * @node:	&struct plist_node pointer - entry to be removed
120 * @head:	&struct plist_head pointer - list head
121 */
122void plist_del(struct plist_node *node, struct plist_head *head)
123{
124	plist_check_head(head);
125
126	if (!list_empty(&node->prio_list)) {
127		if (node->node_list.next != &head->node_list) {
128			struct plist_node *next;
129
130			next = list_entry(node->node_list.next,
131					struct plist_node, node_list);
132
133			/* add the next plist_node into prio_list */
134			if (list_empty(&next->prio_list))
135				list_add(&next->prio_list, &node->prio_list);
136		}
137		list_del_init(&node->prio_list);
138	}
139
140	list_del_init(&node->node_list);
141
142	plist_check_head(head);
143}
144
145/**
146 * plist_requeue - Requeue @node at end of same-prio entries.
147 *
148 * This is essentially an optimized plist_del() followed by
149 * plist_add().  It moves an entry already in the plist to
150 * after any other same-priority entries.
151 *
152 * @node:	&struct plist_node pointer - entry to be moved
153 * @head:	&struct plist_head pointer - list head
154 */
155void plist_requeue(struct plist_node *node, struct plist_head *head)
156{
157	struct plist_node *iter;
158	struct list_head *node_next = &head->node_list;
159
160	plist_check_head(head);
161	BUG_ON(plist_head_empty(head));
162	BUG_ON(plist_node_empty(node));
163
164	if (node == plist_last(head))
165		return;
166
167	iter = plist_next(node);
168
169	if (node->prio != iter->prio)
170		return;
171
172	plist_del(node, head);
173
174	/*
175	 * After plist_del(), iter is the replacement of the node.  If the node
176	 * was on prio_list, take shortcut to find node_next instead of looping.
177	 */
178	if (!list_empty(&iter->prio_list)) {
179		iter = list_entry(iter->prio_list.next, struct plist_node,
180				  prio_list);
181		node_next = &iter->node_list;
182		goto queue;
183	}
184
185	plist_for_each_continue(iter, head) {
186		if (node->prio != iter->prio) {
187			node_next = &iter->node_list;
188			break;
189		}
190	}
191queue:
192	list_add_tail(&node->node_list, node_next);
193
194	plist_check_head(head);
195}
196
197#ifdef CONFIG_DEBUG_PLIST
198#include <linux/sched.h>
199#include <linux/sched/clock.h>
200#include <linux/module.h>
201#include <linux/init.h>
202
203static struct plist_node __initdata test_node[241];
204
205static void __init plist_test_check(int nr_expect)
206{
207	struct plist_node *first, *prio_pos, *node_pos;
208
209	if (plist_head_empty(&test_head)) {
210		BUG_ON(nr_expect != 0);
211		return;
212	}
213
214	prio_pos = first = plist_first(&test_head);
215	plist_for_each(node_pos, &test_head) {
216		if (nr_expect-- < 0)
217			break;
218		if (node_pos == first)
219			continue;
220		if (node_pos->prio == prio_pos->prio) {
221			BUG_ON(!list_empty(&node_pos->prio_list));
222			continue;
223		}
224
225		BUG_ON(prio_pos->prio > node_pos->prio);
226		BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
227		prio_pos = node_pos;
228	}
229
230	BUG_ON(nr_expect != 0);
231	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
232}
233
234static void __init plist_test_requeue(struct plist_node *node)
235{
236	plist_requeue(node, &test_head);
237
238	if (node != plist_last(&test_head))
239		BUG_ON(node->prio == plist_next(node)->prio);
240}
241
242static int  __init plist_test(void)
243{
244	int nr_expect = 0, i, loop;
245	unsigned int r = local_clock();
246
247	printk(KERN_DEBUG "start plist test\n");
248	plist_head_init(&test_head);
249	for (i = 0; i < ARRAY_SIZE(test_node); i++)
250		plist_node_init(test_node + i, 0);
251
252	for (loop = 0; loop < 1000; loop++) {
253		r = r * 193939 % 47629;
254		i = r % ARRAY_SIZE(test_node);
255		if (plist_node_empty(test_node + i)) {
256			r = r * 193939 % 47629;
257			test_node[i].prio = r % 99;
258			plist_add(test_node + i, &test_head);
259			nr_expect++;
260		} else {
261			plist_del(test_node + i, &test_head);
262			nr_expect--;
263		}
264		plist_test_check(nr_expect);
265		if (!plist_node_empty(test_node + i)) {
266			plist_test_requeue(test_node + i);
267			plist_test_check(nr_expect);
268		}
269	}
270
271	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
272		if (plist_node_empty(test_node + i))
273			continue;
274		plist_del(test_node + i, &test_head);
275		nr_expect--;
276		plist_test_check(nr_expect);
277	}
278
279	printk(KERN_DEBUG "end plist test\n");
280
281	/* Worst case test for plist_add() */
282	unsigned int test_data[241];
283
284	for (i = 0; i < ARRAY_SIZE(test_data); i++)
285		test_data[i] = i;
286
287	ktime_t start, end, time_elapsed = 0;
288
289	plist_head_init(&test_head);
290
291	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
292		plist_node_init(test_node + i, 0);
293		test_node[i].prio = test_data[i];
294	}
295
296	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
297		if (plist_node_empty(test_node + i)) {
298			start = ktime_get();
299			plist_add(test_node + i, &test_head);
300			end = ktime_get();
301			time_elapsed += (end - start);
302		}
303	}
304
305	pr_debug("plist_add worst case test time elapsed %lld\n", time_elapsed);
306	return 0;
307}
308
309module_init(plist_test);
310
311#endif