Orange Pi5 kernel

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