linux-kernel - Re: [PATCH RFC ticketlock] Auto-queued ticketlock

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: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1370900106.3252.11.camel@edumazet-glaptop>
Date:	Mon, 10 Jun 2013 14:35:06 -0700
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	paulmck@...ux.vnet.ibm.com
Cc:	linux-kernel@...r.kernel.org, mingo@...e.hu, laijs@...fujitsu.com,
	dipankar@...ibm.com, akpm@...ux-foundation.org,
	mathieu.desnoyers@...icios.com, josh@...htriplett.org,
	niv@...ibm.com, tglx@...utronix.de, peterz@...radead.org,
	rostedt@...dmis.org, Valdis.Kletnieks@...edu, dhowells@...hat.com,
	edumazet@...gle.com, darren@...art.com, fweisbec@...il.com,
	sbw@....edu, torvalds@...ux-foundation.org
Subject: Re: [PATCH RFC ticketlock] Auto-queued ticketlock

On Sun, 2013-06-09 at 12:36 -0700, Paul E. McKenney wrote:
> Breaking up locks is better than implementing high-contention locks, but
> if we must have high-contention locks, why not make them automatically
> switch between light-weight ticket locks at low contention and queued
> locks at high contention?
> 
> This commit therefore allows ticket locks to automatically switch between
> pure ticketlock and queued-lock operation as needed.  If too many CPUs
> are spinning on a given ticket lock, a queue structure will be allocated
> and the lock will switch to queued-lock operation.  When the lock becomes
> free, it will switch back into ticketlock operation.  The low-order bit
> of the head counter is used to indicate that the lock is in queued mode,
> which forces an unconditional mismatch between the head and tail counters.
> This approach means that the common-case code path under conditions of
> low contention is very nearly that of a plain ticket lock.
> 
> A fixed number of queueing structures is statically allocated in an
> array.  The ticket-lock address is used to hash into an initial element,
> but if that element is already in use, it moves to the next element.  If
> the entire array is already in use, continue to spin in ticket mode.
> 
> This has been only lightly tested in the kernel, though a userspace
> implementation has survived substantial testing.
> 
> Signed-off-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>
> 

This looks a great idea ;)

> +
> +static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
> +{
> +	__ticket_t head = 2;
> +
> +	head = xadd(&lock->tickets.head, 2);

	head = xadd(&lock->tickets.head, head);

> +	if (head & 0x1)
> +		tkt_q_do_wake(lock);
> +}
> +#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */

> + */
> +void tkt_q_do_wake(arch_spinlock_t *asp)
> +{
> +	struct tkt_q_head *tqhp;
> +	struct tkt_q *tqp;
> +
> +	/* If the queue is still being set up, wait for it. */
> +	while ((tqhp = tkt_q_find_head(asp)) == NULL)
> +		cpu_relax();
> +
> +	for (;;) {
> +
> +		/* Find the first queue element. */
> +		tqp = ACCESS_ONCE(tqhp->spin);
> +		if (tqp != NULL)
> +			break;  /* Element exists, hand off lock. */
> +		if (tkt_q_try_unqueue(asp, tqhp))
> +			return; /* No element, successfully removed queue. */
> +		cpu_relax();
> +	}
> +	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
> +		ACCESS_ONCE(tqhp->head_tkt) = -1;
> +	smp_mb(); /* Order pointer fetch and assignment against handoff. */
> +	ACCESS_ONCE(tqp->cpu) = -1;
> +}

EXPORT_SYMBOL(tkt_q_do_wake) ?

Hmm, unfortunately I lack time this week to fully read the patch !



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/