From nobody Fri Dec 19 07:18:09 2025 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B3DD0212FAF for ; Sat, 8 Mar 2025 16:48:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=193.142.43.55 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741452524; cv=none; b=a5H7Jp+c60N03SgaTHDGMgx6dsfx8nlDLINZwoc9BgTq98wHLv4yTfS3PvtRnEYBaDLdhCFGx3YyPHxB2Jjjf7ZbZ4cFbZq5r72nw8Ql5zj0h17iP2mpiovY6rGdAzw2zSqkaEF4QV0PMSWPU0pf+uRK8GPAsXpzNJFhugpAt14= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741452524; c=relaxed/simple; bh=8UmxBRmF5nXHswTC8BicM5u5C0y9sC394+CC1Pxv8T0=; h=Message-ID:From:To:Cc:Subject:References:MIME-Version: Content-Type:Date; b=p5Rb1RfUdgSEBBb25O7btvr2r1OgxAErjc8c1Vg93DXV+a2ieLUvlCr0KZZeHiW+ILpPpTAhbqgx8Voi1PGnz/8RN6rvavPREBknXpaUSn/frYYc6/nFIC8TaKEQ6rXSV6hEJR0kVJMdVJGa1l+0kRLn1D1K0qr/rl4V7TDnP08= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de; spf=pass smtp.mailfrom=linutronix.de; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=1Yb8b9gA; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=lLfVAiI6; arc=none smtp.client-ip=193.142.43.55 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linutronix.de Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="1Yb8b9gA"; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="lLfVAiI6" Message-ID: <20250308155624.279080328@linutronix.de> DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1741452521; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: references:references; bh=qoabwlj1EGQBFXc6piAS9tlQQLf9azO7VG5Y2rcwn2E=; b=1Yb8b9gACJSVZytKQQAOpuF2ugs+XmbODu8KaRKmBjTMfOqNIcEB5EesHPeV0wr/RXeJqi pj43yoQLUmW+sywI0u+PHdKb/xC8JfP/HKtA+6gpKlVG/19mg44ynyyYW4edZZWXYh2rHr 1G5T513ETKtm+jpH9sE8vJ/B8nS7sd4mlelUePmw6XEImnUFZnSsW2O2A1zRCx/8zbpKWa xql/Tkb6iUF1UFGleZjSt8RCxOLyGxYTPx5xK6yijPGM+L6MisXnyfZQ+H75CUIlzp//oF /+8OvdYcpqAfXfFm2HLasprmhmhpYK8eDxEP1ZHyZ5bDUDD2/mr1M2x4ATCAHQ== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1741452521; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: references:references; bh=qoabwlj1EGQBFXc6piAS9tlQQLf9azO7VG5Y2rcwn2E=; b=lLfVAiI6sTj6n8l5qWxvhVHz61+Vcr96tVrbyQL7/nHSOwXVxmTYiJvbdJ0FAt35lrkQgk PPYzcc9HpWFTEABg== From: Thomas Gleixner To: LKML Cc: Anna-Maria Behnsen , Frederic Weisbecker , Benjamin Segall , Eric Dumazet , Andrey Vagin , Pavel Tikhomirov , Peter Zijlstra , Cyrill Gorcunov Subject: [patch V3 13/18] posix-timers: Switch to jhash32() References: <20250308155501.391430556@linutronix.de> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Date: Sat, 8 Mar 2025 17:48:40 +0100 (CET) Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The hash distribution of hash_32() is suboptimal. jhash32() provides a way better distribution, which evens out the length of the hash bucket lists, which in turn avoids large outliers in list walk times. Due to the sparse ID space (thanks CRIU) there is no guarantee that the timers will be fully evenly distributed over the hash buckets, but the behaviour is way better than with hash_32() even for randomly sparse ID spaces. For a pathological test case with 64 processes creating and accessing 20000 timers each, this results in a runtime reduction of ~10% and a significantly reduced runtime variation. Signed-off-by: Thomas Gleixner --- V2: New patch --- kernel/time/posix-timers.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) --- a/kernel/time/posix-timers.c +++ b/kernel/time/posix-timers.c @@ -11,8 +11,8 @@ */ #include #include -#include #include +#include #include #include #include @@ -47,11 +47,11 @@ struct timer_hash_bucket { =20 static struct { struct timer_hash_bucket *buckets; - unsigned long bits; + unsigned long mask; } __timer_data __ro_after_init __aligned(2*sizeof(long)); =20 #define timer_buckets (__timer_data.buckets) -#define timer_hashbits (__timer_data.bits) +#define timer_hashmask (__timer_data.mask) =20 static const struct k_clock * const posix_clocks[]; static const struct k_clock *clockid_to_kclock(const clockid_t id); @@ -87,7 +87,7 @@ DEFINE_CLASS_IS_COND_GUARD(lock_timer); =20 static struct timer_hash_bucket *hash_bucket(struct signal_struct *sig, un= signed int nr) { - return &timer_buckets[hash_32(hash32_ptr(sig) ^ nr, timer_hashbits)]; + return &timer_buckets[jhash2((u32 *)&sig, sizeof(sig) / sizeof(u32), nr) = & timer_hashmask]; } =20 static struct k_itimer *posix_timer_by_id(timer_t id) @@ -1514,7 +1514,7 @@ static int __init posixtimer_init(void) timer_buckets =3D alloc_large_system_hash("posixtimers", sizeof(*timer_bu= ckets), size, 0, 0, &shift, NULL, size, size); size =3D 1UL << shift; - timer_hashbits =3D ilog2(size); + timer_hashmask =3D size - 1; =20 for (i =3D 0; i < size; i++) { spin_lock_init(&timer_buckets[i].lock);