[linux.git] / lib / plist.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * lib/plist.c
 *
 * Descending-priority-sorted double-linked list
 *
 * (C) 2002-2003 Intel Corp
 * Inaky Perez-Gonzalez <[email protected]>.
 *
 * 2001-2005 (c) MontaVista Software, Inc.
 * Daniel Walker <[email protected]>
 *
 * (C) 2005 Thomas Gleixner <[email protected]>
 *
 * Simplifications of the original code by
 * Oleg Nesterov <[email protected]>
 *
 * Based on simple lists (include/linux/list.h).
 *
 * This file contains the add / del functions which are considered to
 * be too large to inline. See include/linux/plist.h for further
 * information.
 */

#include <linux/bug.h>
#include <linux/plist.h>

#ifdef CONFIG_DEBUG_PLIST

static struct plist_head test_head;

static void plist_check_prev_next(struct list_head *t, struct list_head *p,
				  struct list_head *n)
{
	WARN(n->prev != p || p->next != n,
			"top: %p, n: %p, p: %p\n"
			"prev: %p, n: %p, p: %p\n"
			"next: %p, n: %p, p: %p\n",
			 t, t->next, t->prev,
			p, p->next, p->prev,
			n, n->next, n->prev);
}

static void plist_check_list(struct list_head *top)
{
	struct list_head *prev = top, *next = top->next;

	plist_check_prev_next(top, prev, next);
	while (next != top) {
		WRITE_ONCE(prev, next);
		WRITE_ONCE(next, prev->next);
		plist_check_prev_next(top, prev, next);
	}
}

static void plist_check_head(struct plist_head *head)
{
	if (!plist_head_empty(head))
		plist_check_list(&plist_first(head)->prio_list);
	plist_check_list(&head->node_list);
}

#else
# define plist_check_head(h)	do { } while (0)
#endif

/**
 * plist_add - add @node to @head
 *
 * @node:	&struct plist_node pointer
 * @head:	&struct plist_head pointer
 */
void plist_add(struct plist_node *node, struct plist_head *head)
{
	struct plist_node *first, *iter, *prev = NULL, *last, *reverse_iter;
	struct list_head *node_next = &head->node_list;

	plist_check_head(head);
	WARN_ON(!plist_node_empty(node));
	WARN_ON(!list_empty(&node->prio_list));

	if (plist_head_empty(head))
		goto ins_node;

	first = iter = plist_first(head);
	last = reverse_iter = list_entry(first->prio_list.prev, struct plist_node, prio_list);

	do {
		if (node->prio < iter->prio) {
			node_next = &iter->node_list;
			break;
		} else if (node->prio >= reverse_iter->prio) {
			prev = reverse_iter;
			iter = list_entry(reverse_iter->prio_list.next,
				struct plist_node, prio_list);
			if (likely(reverse_iter != last))
				node_next = &iter->node_list;
			break;
		}

		prev = iter;
		iter = list_entry(iter->prio_list.next,
				struct plist_node, prio_list);
		reverse_iter = list_entry(reverse_iter->prio_list.prev,
				struct plist_node, prio_list);
	} while (iter != first);

	if (!prev || prev->prio != node->prio)
		list_add_tail(&node->prio_list, &iter->prio_list);
ins_node:
	list_add_tail(&node->node_list, node_next);

	plist_check_head(head);
}

/**
 * plist_del - Remove a @node from plist.
 *
 * @node:	&struct plist_node pointer - entry to be removed
 * @head:	&struct plist_head pointer - list head
 */
void plist_del(struct plist_node *node, struct plist_head *head)
{
	plist_check_head(head);

	if (!list_empty(&node->prio_list)) {
		if (node->node_list.next != &head->node_list) {
			struct plist_node *next;

			next = list_entry(node->node_list.next,
					struct plist_node, node_list);

			/* add the next plist_node into prio_list */
			if (list_empty(&next->prio_list))
				list_add(&next->prio_list, &node->prio_list);
		}
		list_del_init(&node->prio_list);
	}

	list_del_init(&node->node_list);

	plist_check_head(head);
}

/**
 * plist_requeue - Requeue @node at end of same-prio entries.
 *
 * This is essentially an optimized plist_del() followed by
 * plist_add().  It moves an entry already in the plist to
 * after any other same-priority entries.
 *
 * @node:	&struct plist_node pointer - entry to be moved
 * @head:	&struct plist_head pointer - list head
 */
void plist_requeue(struct plist_node *node, struct plist_head *head)
{
	struct plist_node *iter;
	struct list_head *node_next = &head->node_list;

	plist_check_head(head);
	BUG_ON(plist_head_empty(head));
	BUG_ON(plist_node_empty(node));

	if (node == plist_last(head))
		return;

	iter = plist_next(node);

	if (node->prio != iter->prio)
		return;

	plist_del(node, head);

	plist_for_each_continue(iter, head) {
		if (node->prio != iter->prio) {
			node_next = &iter->node_list;
			break;
		}
	}
	list_add_tail(&node->node_list, node_next);

	plist_check_head(head);
}

#ifdef CONFIG_DEBUG_PLIST
#include <linux/sched.h>
#include <linux/sched/clock.h>
#include <linux/module.h>
#include <linux/init.h>

static struct plist_node __initdata test_node[241];

static void __init plist_test_check(int nr_expect)
{
	struct plist_node *first, *prio_pos, *node_pos;

	if (plist_head_empty(&test_head)) {
		BUG_ON(nr_expect != 0);
		return;
	}

	prio_pos = first = plist_first(&test_head);
	plist_for_each(node_pos, &test_head) {
		if (nr_expect-- < 0)
			break;
		if (node_pos == first)
			continue;
		if (node_pos->prio == prio_pos->prio) {
			BUG_ON(!list_empty(&node_pos->prio_list));
			continue;
		}

		BUG_ON(prio_pos->prio > node_pos->prio);
		BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
		prio_pos = node_pos;
	}

	BUG_ON(nr_expect != 0);
	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
}

static void __init plist_test_requeue(struct plist_node *node)
{
	plist_requeue(node, &test_head);

	if (node != plist_last(&test_head))
		BUG_ON(node->prio == plist_next(node)->prio);
}

static int  __init plist_test(void)
{
	int nr_expect = 0, i, loop;
	unsigned int r = local_clock();

	printk(KERN_DEBUG "start plist test\n");
	plist_head_init(&test_head);
	for (i = 0; i < ARRAY_SIZE(test_node); i++)
		plist_node_init(test_node + i, 0);

	for (loop = 0; loop < 1000; loop++) {
		r = r * 193939 % 47629;
		i = r % ARRAY_SIZE(test_node);
		if (plist_node_empty(test_node + i)) {
			r = r * 193939 % 47629;
			test_node[i].prio = r % 99;
			plist_add(test_node + i, &test_head);
			nr_expect++;
		} else {
			plist_del(test_node + i, &test_head);
			nr_expect--;
		}
		plist_test_check(nr_expect);
		if (!plist_node_empty(test_node + i)) {
			plist_test_requeue(test_node + i);
			plist_test_check(nr_expect);
		}
	}

	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
		if (plist_node_empty(test_node + i))
			continue;
		plist_del(test_node + i, &test_head);
		nr_expect--;
		plist_test_check(nr_expect);
	}

	printk(KERN_DEBUG "end plist test\n");

	/* Worst case test for plist_add() */
	unsigned int test_data[241];

	for (i = 0; i < ARRAY_SIZE(test_data); i++)
		test_data[i] = i;

	ktime_t start, end, time_elapsed = 0;

	plist_head_init(&test_head);

	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
		plist_node_init(test_node + i, 0);
		test_node[i].prio = test_data[i];
	}

	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
		if (plist_node_empty(test_node + i)) {
			start = ktime_get();
			plist_add(test_node + i, &test_head);
			end = ktime_get();
			time_elapsed += (end - start);
		}
	}

	pr_debug("plist_add worst case test time elapsed %lld\n", time_elapsed);
	return 0;
}

module_init(plist_test);

#endif
Commit	Line	Data
aded9cb8	1	// SPDX-License-Identifier: GPL-2.0-or-later
77ba89c5 IM	2	/*
	3	* lib/plist.c
	4	*
	5	* Descending-priority-sorted double-linked list
	6	*
	7	* (C) 2002-2003 Intel Corp
	8	* Inaky Perez-Gonzalez <[email protected]>.
	9	*
	10	* 2001-2005 (c) MontaVista Software, Inc.
	11	* Daniel Walker <[email protected]>
	12	*
	13	* (C) 2005 Thomas Gleixner <[email protected]>
	14	*
	15	* Simplifications of the original code by
	16	* Oleg Nesterov <[email protected]>
	17	*
77ba89c5 IM	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
50af5ead	25	#include <linux/bug.h>
77ba89c5	26	#include <linux/plist.h>
77ba89c5	27
8e18faea	28	#ifdef CONFIG_DEBUG_PLIST
77ba89c5	29
6d55da53 LJ	30	static struct plist_head test_head;
6d55da53 LJ	31
77ba89c5 IM	32	static void plist_check_prev_next(struct list_head t, struct list_head p,
	33	struct list_head *n)
	34	{
5cd2b459 AV	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);
77ba89c5 IM	42	}
	43
	44	static 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) {
7abcb84f HC	50	WRITE_ONCE(prev, next);
7abcb84f HC	51	WRITE_ONCE(next, prev->next);
77ba89c5 IM	52	plist_check_prev_next(top, prev, next);
	53	}
	54	}
	55
	56	static void plist_check_head(struct plist_head *head)
	57	{
bf6a9b83 LJ	58	if (!plist_head_empty(head))
bf6a9b83 LJ	59	plist_check_list(&plist_first(head)->prio_list);
77ba89c5 IM	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	*/
	73	void plist_add(struct plist_node node, struct plist_head head)
	74	{
c8dab79f	75	struct plist_node first, iter, prev = NULL, last, *reverse_iter;
bf6a9b83	76	struct list_head *node_next = &head->node_list;
77ba89c5 IM	77
	78	plist_check_head(head);
	79	WARN_ON(!plist_node_empty(node));
bf6a9b83	80	WARN_ON(!list_empty(&node->prio_list));
77ba89c5	81
bf6a9b83 LJ	82	if (plist_head_empty(head))
	83	goto ins_node;
	84
	85	first = iter = plist_first(head);
c8dab79f	86	last = reverse_iter = list_entry(first->prio_list.prev, struct plist_node, prio_list);
bf6a9b83 LJ	87
	88	do {
	89	if (node->prio < iter->prio) {
	90	node_next = &iter->node_list;
	91	break;
c8dab79f HC	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;
77ba89c5	99	}
77ba89c5	100
bf6a9b83 LJ	101	prev = iter;
	102	iter = list_entry(iter->prio_list.next,
	103	struct plist_node, prio_list);
c8dab79f HC	104	reverse_iter = list_entry(reverse_iter->prio_list.prev,
c8dab79f HC	105	struct plist_node, prio_list);
bf6a9b83 LJ	106	} while (iter != first);
	107
	108	if (!prev \|\| prev->prio != node->prio)
	109	list_add_tail(&node->prio_list, &iter->prio_list);
	110	ins_node:
	111	list_add_tail(&node->node_list, node_next);
77ba89c5 IM	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	*/
	122	void plist_del(struct plist_node node, struct plist_head head)
	123	{
	124	plist_check_head(head);
	125
bf6a9b83 LJ	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);
77ba89c5	132
bf6a9b83 LJ	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);
77ba89c5 IM	138	}
77ba89c5 IM	139
bf6a9b83	140	list_del_init(&node->node_list);
77ba89c5 IM	141
	142	plist_check_head(head);
	143	}
6d55da53	144
a75f232c DS	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	*/
	155	void 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	plist_for_each_continue(iter, head) {
	175	if (node->prio != iter->prio) {
	176	node_next = &iter->node_list;
	177	break;
	178	}
	179	}
	180	list_add_tail(&node->node_list, node_next);
	181
	182	plist_check_head(head);
	183	}
	184
8e18faea	185	#ifdef CONFIG_DEBUG_PLIST
6d55da53	186	#include <linux/sched.h>
e6017571	187	#include <linux/sched/clock.h>
6d55da53 LJ	188	#include <linux/module.h>
	189	#include <linux/init.h>
	190
	191	static struct plist_node __initdata test_node[241];
	192
	193	static void __init plist_test_check(int nr_expect)
	194	{
	195	struct plist_node first, prio_pos, *node_pos;
	196
	197	if (plist_head_empty(&test_head)) {
	198	BUG_ON(nr_expect != 0);
	199	return;
	200	}
	201
	202	prio_pos = first = plist_first(&test_head);
	203	plist_for_each(node_pos, &test_head) {
	204	if (nr_expect-- < 0)
	205	break;
	206	if (node_pos == first)
	207	continue;
	208	if (node_pos->prio == prio_pos->prio) {
	209	BUG_ON(!list_empty(&node_pos->prio_list));
	210	continue;
	211	}
	212
	213	BUG_ON(prio_pos->prio > node_pos->prio);
	214	BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
	215	prio_pos = node_pos;
	216	}
	217
	218	BUG_ON(nr_expect != 0);
	219	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
	220	}
	221
a75f232c DS	222	static void __init plist_test_requeue(struct plist_node *node)
	223	{
	224	plist_requeue(node, &test_head);
	225
	226	if (node != plist_last(&test_head))
	227	BUG_ON(node->prio == plist_next(node)->prio);
	228	}
	229
6d55da53 LJ	230	static int __init plist_test(void)
	231	{
	232	int nr_expect = 0, i, loop;
	233	unsigned int r = local_clock();
	234
18120627	235	printk(KERN_DEBUG "start plist test\n");
732375c6	236	plist_head_init(&test_head);
6d55da53 LJ	237	for (i = 0; i < ARRAY_SIZE(test_node); i++)
	238	plist_node_init(test_node + i, 0);
	239
	240	for (loop = 0; loop < 1000; loop++) {
	241	r = r * 193939 % 47629;
	242	i = r % ARRAY_SIZE(test_node);
	243	if (plist_node_empty(test_node + i)) {
	244	r = r * 193939 % 47629;
	245	test_node[i].prio = r % 99;
	246	plist_add(test_node + i, &test_head);
	247	nr_expect++;
	248	} else {
	249	plist_del(test_node + i, &test_head);
	250	nr_expect--;
	251	}
	252	plist_test_check(nr_expect);
a75f232c DS	253	if (!plist_node_empty(test_node + i)) {
	254	plist_test_requeue(test_node + i);
	255	plist_test_check(nr_expect);
	256	}
6d55da53 LJ	257	}
	258
	259	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
	260	if (plist_node_empty(test_node + i))
	261	continue;
	262	plist_del(test_node + i, &test_head);
	263	nr_expect--;
	264	plist_test_check(nr_expect);
	265	}
	266
18120627	267	printk(KERN_DEBUG "end plist test\n");
c8dab79f HC	268
	269	/* Worst case test for plist_add() */
	270	unsigned int test_data[241];
	271
	272	for (i = 0; i < ARRAY_SIZE(test_data); i++)
	273	test_data[i] = i;
	274
	275	ktime_t start, end, time_elapsed = 0;
	276
	277	plist_head_init(&test_head);
	278
	279	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
	280	plist_node_init(test_node + i, 0);
	281	test_node[i].prio = test_data[i];
	282	}
	283
	284	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
	285	if (plist_node_empty(test_node + i)) {
	286	start = ktime_get();
	287	plist_add(test_node + i, &test_head);
	288	end = ktime_get();
	289	time_elapsed += (end - start);
	290	}
	291	}
	292
	293	pr_debug("plist_add worst case test time elapsed %lld\n", time_elapsed);
6d55da53 LJ	294	return 0;
	295	}
	296
	297	module_init(plist_test);
	298
	299	#endif