linux-kernel - Re: [PATCH] Document Linux's circular buffering capabilities

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]

Date:	Fri, 12 Mar 2010 23:41:08 +0000
From:	David Howells <dhowells@...hat.com>
To:	Stefan Richter <stefanr@...6.in-berlin.de>
Cc:	dhowells@...hat.com, torvalds@...l.org, akpm@...ux-foundation.org,
	sgruszka@...hat.com, davem@...emloft.net,
	linux-kernel@...r.kernel.org,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Randy Dunlap <rdunlap@...otime.net>
Subject: Re: [PATCH] Document Linux's circular buffering capabilities

Stefan Richter <stefanr@...6.in-berlin.de> wrote:

> "...do this" could be misunderstood as "use a modulus instruction",
> although the heading says that this section is about 2^n sized buffers.
> How about reversing the leading paragraph?
> 
>     Calculating the occupied or free space of a circular buffer involves
>     a somewhat slow modulus operation.  But if the buffer size is an
>     exact power of 2, a quick bitwise AND can be used instead.
> 
>     There is a set of macros which do the latter, that can be made use
>     of by [...]

How about:

	Calculation of the occupancy or the remaining capacity of an
	arbitrarily sized circular buffer would normally be a slow operation,
	requiring the use of a modulus (divide) instruction.  However, if the
	buffer is of a power-of-2 size, then a much quicker bitwise-AND
	instruction can be used instead.

	Linux provides a set of macros for handling power-of-2 circular
	buffers.  These can be made use of by:
	...

> > +Note the use of ACCESS_ONCE() in both algorithms to read the opposition index.
> > +This prevents the compiler from discarding and reloading its cached value -
> > +which some compilers will do, even after an implied compiler barrier.
> 
> I don't understand why ACCESS_ONCE is needed here.  The CIRC_SPACE and
> CIRC_CNT macros do not look at head and tail more than once.

In this example they don't, but say someone wants to read several elements
from the buffer, they might end up accessing their copy of head several times.

If you only access it once anyway, ACCESS_ONCE() shouldn't hurt.

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