linux-kernel - Re: [PATCH RFC ticketlock] v3 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 for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20130702055638.GY3773@linux.vnet.ibm.com>
Date:	Mon, 1 Jul 2013 22:56:38 -0700
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Raghavendra KT <raghavendra.kt.linux@...il.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, walken@...gle.com,
	waiman.long@...com, davidlohr.bueso@...com,
	Raghavendra KT <raghavendra.kt@...ux.vnet.ibm.com>
Subject: Re: [PATCH RFC ticketlock] v3 Auto-queued ticketlock

On Mon, Jul 01, 2013 at 02:49:34PM +0530, Raghavendra KT wrote:
> On Sun, Jun 23, 2013 at 11:23 PM, Raghavendra KT
> <raghavendra.kt.linux@...il.com> wrote:
> >
> >
> > On Wed, Jun 12, 2013 at 9:10 PM, Paul E. McKenney
> > <paulmck@...ux.vnet.ibm.com> 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?  After all, this would remove the need for
> >> the developer to predict which locks will be highly contended.
> >>
> >> This commit 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.
> >>
> >> Signed-off-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>
> >> [ paulmck: Eliminate duplicate code and update comments (Steven Rostedt).
> >> ]
> >> [ paulmck: Address Eric Dumazet review feedback. ]
> >> [ paulmck: Use Lai Jiangshan idea to eliminate smp_mb(). ]
> >> [ paulmck: Expand ->head_tkt from s32 to s64 (Waiman Long). ]
> >> [ paulmck: Move cpu_relax() to main spin loop (Steven Rostedt). ]
> >> [ paulmck: Reduce queue-switch contention (Waiman Long). ]
> >> [ paulmck: __TKT_SPIN_INC for __ticket_spin_trylock() (Steffen Persvold).
> >> ]
> >> [ paulmck: Type safety fixes (Steven Rostedt). ]
> >> [ paulmck: Pre-check cmpxchg() value (Waiman Long). ]
> >> [ paulmck: smp_mb() downgrade to smp_wmb() (Lai Jiangshan). ]
> >>
> > [...]
> >
> > I did test this on 32 core machine with 32 vcpu guests.
> >
> > This version gave me around 20% improvement fro sysbench and 36% improvement
> > for ebizzy, for 1x commit though other overcommited results showed
> > degradation. I have not tested Lai Jiangshan's patches on top of this yet.
> > Will report any findings.
> 
> Sorry for late report.

Not a problem, thank you for running these numbers!

> With Lai's patch I see few percentage of improvement in ebizzy 1x and
> reduction in degradation in dbench 1x.

OK, good!  But my guess is that even pushing the lock-acquisition
slowpath out of line, we still would not reach parity for the less-good
results.  Still seems like I should add Lai Jiangshan's patches
and post them somewhere in case they are helpful in some other context.

						Thanx, Paul

> But over-commit degradation seem to still persist. seeing this,  I
> feel it is more of qmode overhead itself for large guests,
> 
> +---+-----------+-----------+-----------+------------+-----------+
>                               ebizzy (rec/sec higher is better)
> +---+---+-----------+-----------+-----------+------------+-----------+
>     base      stdev         patched       stdev     %improvement
> +---+-----------+-----------+-----------+------------+-----------+
> 1x  5574.9000   237.4997          7851.9000   148.6737    40.84378
> 2x  2741.5000   561.3090          1620.9000   410.8299   -40.87543
> 3x  2146.2500   216.7718          1751.8333    96.5023   -18.37702
> +---+-----------+-----------+-----------+------------+-----------+
> +---+-----------+-----------+-----------+------------+-----------+
>                               dbench (throughput higher is better)
> +---+-----------+-----------+-----------+------------+-----------+
>     base      stdev         patched       stdev     %improvement
> +---+-----------+-----------+-----------+------------+-----------+
> 1x 14111.5600   754.4525         13826.5700  1458.0744    -2.01955
> 2x  2481.6270    71.2665          1549.3740   245.3777   -37.56620
> 3x  1510.2483    31.8634          1116.0158    26.4882   -26.10382
> +---+-----------+-----------+-----------+------------+-----------+
> 

--
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/