lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20250119062408.77638-1-richard120310@gmail.com>
Date: Sun, 19 Jan 2025 14:24:08 +0800
From: I Hsin Cheng <richard120310@...il.com>
To: akpm@...ux-foundation.org
Cc: jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	I Hsin Cheng <richard120310@...il.com>
Subject: [PATCH] lib/plist.c: Add shortcut for plist_requeue()

In the operation of plist_requeue(), "node" is deleted from the list
before queueing it back to the list again, which involves looping to
find the tail of same-prio entries.

If "node" is the head of same-prio entries which means its prio_list is
on the priority list, then "node_next" can be retrieve immediately by
the next entry of prio_list, instead of looping nodes on node_list.

The shortcut implementation can benefit plist_requeue() regarding to the
following test[1], and the test result is shown in the following table.

One can observe from the test result that when the number of nodes of
same-prio entries is smaller, then the probability of hitting the
shortcut can be bigger, thus the benefit can be more significant.

While it tends to behave almost the same for long same-prio entries,
since the probability of taking the shortcut is much smaller.

 -----------------------------------------------------------------------
| Test size          |    200 |     400 |     600 |     800 |     1000 |
 -----------------------------------------------------------------------
| new_plist_requeue  |  271521|  1007913|  2148033|  4346792|  12200940|
 -----------------------------------------------------------------------
| old_plist_requeue  |  301395|  1105544|  2488301|  4632980|  12217275|
 -----------------------------------------------------------------------

Signed-off-by: I Hsin Cheng <richard120310@...il.com>
---
[1]:
The test is done on x86_64 architecture with v6.9 kernel and 
Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz.

Test script( executed in kernel module mode ):

int init_module(void)
{
	unsigned int test_data[test_size];

	/* Split the list into 10 different priority
	 * , when test_size is larger, the number of
	 * nodes within each priority is larger.
	 */
	for (i = 0; i < ARRAY_SIZE(test_data); i++) {
		test_data[i] = i % 10;
	}

	ktime_t start, end, time_elapsed = 0;
	plist_head_init(&test_head_local);

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


	for (i = 0; i < ARRAY_SIZE(test_node_local); i++) {
		if (plist_node_empty(test_node_local + i)) {
			plist_add(test_node_local + i, &test_head_local);
		}
	}

	for (i = 0; i < ARRAY_SIZE(test_node_local); i += 1) {
		start = ktime_get();
		plist_requeue(test_node_local + i, &test_head_local);
		end = ktime_get();
		time_elapsed += (end - start);
	}

	pr_info("plist_requeue() elapsed time : %lld, size %d\n", time_elapsed, test_size);
	return 0;
}


 lib/plist.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/lib/plist.c b/lib/plist.c
index c6bce1226..5071b1eb2 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -171,12 +171,23 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
 
 	plist_del(node, head);
 
+	/* After plist_del(), iter is the replacement of node
+	 * , if node was on prio_list, then take shortcut to
+	 * find node_next instead of looping.
+	 */
+	if (!list_empty(&iter->prio_list)) {
+		iter = list_entry(iter->prio_list.next, struct plist_node, prio_list);
+		node_next = &iter->node_list;
+		goto queue;
+	}
+
 	plist_for_each_continue(iter, head) {
 		if (node->prio != iter->prio) {
 			node_next = &iter->node_list;
 			break;
 		}
 	}
+queue:
 	list_add_tail(&node->node_list, node_next);
 
 	plist_check_head(head);
-- 
2.43.0


Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ