linux-kernel - Re: [PATCH 1/2] MN10300: Move asm-arm/cnt32_to

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] [day] [month] [year] [list]

Date:	Mon, 06 Oct 2008 11:06:53 -0400 (EDT)
From:	Nicolas Pitre <nico@....org>
To:	David Howells <dhowells@...hat.com>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>, torvalds@...l.org,
	akpm@...ux-foundation.org, linux-am33-list@...hat.com,
	lkml <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 1/2] MN10300: Move asm-arm/cnt32_to_63.h to include/linux/

On Mon, 6 Oct 2008, David Howells wrote:

> Nicolas Pitre <nico@....org> wrote:
> 
> > If so then you're using this interface in an inappropriate way.
> > 
> > The _absolute_ minimum frequency with which this should be fully 
> > executed is once per half period of the base counter.  I hope that in 
> > practice it happens far more often than that.
> 
> I think you're misunderstanding my contention.
> 
> If preemption is enabled, cnt32_to_63() can be called with greater than
> minimum frequency and yet reversions can still happen.
> 
> The problem is that a process that's half way through executing cnt32_to_63()
> can be preempted for a period of time sufficient that when it is rescheduled
> and writes __m_cnt_hi, it corrupts it with an out of date value.

I think you're misunderstanding my objection.

if a process that's half way through executing cnt32_to_63()
is preempted for a period of time in the same ball park as the 
half period of the base counter then my point is that you have 
a much bigger problem.

For __m_cnt_hi to be written with an out-of-date value, you'd need 
this sequence of events:

(1)	__x.hi = __m_cnt_hi;
(2)	__x.lo = (cnt_lo);
(3)	if (unlikely((s32)(__x.hi ^ __x.lo) < 0))
(4)		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31);

cnt_lo		cnt_hi		instance A	instance B
---------------------------------------------------------------------
0x7fffffff	0x00000000	...
0x80000000	0x00000000	...
[the code isn't called for a _long_ time during which __m_cnt_hi
 is not in synch with the low part]
0xff000000	0x00000000	(1) __x.hi = 0
0xff000001	0x00000000	(2) __x.lo = 0xff000001
0xff000002	0x00000000	(3) condition is true
0xff000003	0x00000000	*** preemption ***
0xff000004	0x00000000			...
[a little while later]
0xffff0000	0x00000000			(1) __x.hi = 0
0xffff0001	0x00000000			(2) __x.lo = 0xffff0001
0xffff0002	0x00000000			(3) condition is true
0xffff0003	0x00000000			(4) update __m_cnt_hi
0xffff0004	0x80000000			...
[a little while later]
0xffffffff	0x80000000			...
0x00000000	0x80000000			...
0x00000001	0x80000000			(1) __x.hi = 0x80000000
0x00000002	0x80000000			(2) __x.lo = 0x00000002
0x00000003	0x80000000			(3) condition is true
0x00000004	0x80000000			(4) update __m_cnt_hi
0x00000005	0x00000001			...
0x00000006	0x00000001			*** preemption ***
0x00000007	0x00000001	(4) update update __m_cnt_hi
0x00000008	0x80000000	...

At this point, it is true that __m_cnt_hi is not up to date while it was 
a moment before.  But that has no consequence because it was reverted 
to the same state before the update at 0x00000004, meaning that the 
update will be redone as soon as the code is executed again.

Sure this could be defeated if 1) the execution in instance B didn't 
come soon enough to notice the initial lack of synchronization before 
the second half period passed, or 2) the duration of the preemption of 
instance A was long enough so not to leave enough time for __m_cnt_hi to 
be corrected back with the current half-period.  But those are extreme 
cases this algorithm is _not_ made for because in practice they should 
_not_ happen.

If the complete code sequence is always executed _at_ _least_ once per 
half-period then you're OK.  That's the theoretical requirement.  In 
practice you should expect it to be called many many times per 
half-period to keep __m_cnt_hi warm.  In my case this is a couple 
hundred times per half period so I'm not worried.

So, if you have a system where 1) this code might not get called for a 
long time _and_ 2) if called it can be preempted away for a long time, 
then you certainly risk having __m_cnt_hi miss a transition.  But in 
that case fixing those issue is way more important than worrying about a 
glitch in the __m_cnt_hi value.

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