confused with DDK docs

Maxim_S_Shatskih · January 4, 2007, 3:01pm

> (therefore continuous) it is always possible for logic to go wrong if two

devices happen to assert an event at the same time in an asynchronous
system*.

The bus grant logic on both PCI and frontside buses prevent this. Some CPU will
win, another will lose.

–
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com

Tim_Roberts · January 4, 2007, 3:35pm

Maxim S. Shatskih wrote:

> I want to know how this spinning mechanism is implemented on machines.
>

Something like this:

loop:
lock bts [spinlock]
jnz loop

Right. Here is a case where the kernel debugger’s ability to treat a PE
executable as a crash dump comes in very handy – we can go straight to
the source and disassemble it. This is from a multiprocessor system:

C:\tmp\x>*i386kd.exe -z \WINDOWS\system32\ntoskrnl.exe*

Loading Dump File [C:\WINDOWS\system32\ntoskrnl.exe]
Symbol search path is:
srv*c:\ddk\symbols*http://msdl.microsoft.com/download/symbols
Executable search path is:
ModLoad: 00400000 00626000 C:\WINDOWS\system32\ntoskrnl.exe
eax=00000000 ebx=00000000 ecx=00000000 edx=00000000 esi=00000000
edi=00000000
eip=005e890b esp=00000000 ebp=00000000 iopl=0 nv up di pl nz na
pe nc
cs=0000 ss=0000 ds=0000 es=0000 fs=0000 gs=0000
efl=00000000
ntoskrnl!KiSystemStartup:
005e890b 55 push ebp
0:000> *u KiAcquireSpinLock*
ntoskrnl!KiAcquireSpinLock:
0040b458 f00fba2900 lock bts dword ptr [ecx],0x0
0040b45d 7201 jb ntoskrnl!KiAcquireSpinLock+0x8 (0040b460)
0040b45f c3 ret
0040b460 f70101000000 test dword ptr [ecx],0x1
0040b466 74f0 jz ntoskrnl!KiAcquireSpinLock (0040b458)
0040b468 f390 pause
0040b46a ebf4 jmp ntoskrnl!KiAcquireSpinLock+0x8 (0040b460)

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

Mike_Kemp · January 5, 2007, 10:20am

Hi Tim

Yes, I did say in my first post that synchronous systems were safe. Just
seems to me that as soon as you let an asynchronous signal in you cannot be
certain, as these are indeed analogue signals firing at random! (Anyone who
thinks logic signal are always 0 or 1 has never looked at a 'scope).

Luckily, with enough gates and clock delays you can get the probably of
success very close to unity so that it is as safe as you want to design it.

Glad to hear that all multi CPU systems are synchronous - if they weren’t
there are an awful lot of chances to trip over that 1 in a
1,000,000,000,000,000,…

Best regards

Mike

----- Original Message -----
From: Tim Roberts
To: Windows System Software Devs Interest List
Sent: Thursday, January 04, 2007 6:12 PM
Subject: Re: [ntdev] confused with DDK docs

Mike Kemp wrote:

Yes I am sure that in practice it is a very low probability, low
enough to be irrelevant maybe. Just shaking off the holiday spirit by
trying to be thought provoking and hope no-one thinks the probability
is zero!

I know I can find a time between the simultaneous case you mention
when processor A is guaranteed to win, and the picosecond before when
processor B will win, in which it will fail…

This is utter nonsense. These are not arbitrary analog signals firing
at random. These are fully synchronous systems, controlled by clocks.
It doesn’t matter whether there are picoseconds of difference in the
signal timing. The processor specification requires that those signals
be stable well before the next clock edge, and the memory controller
(which arbitrates the LOCK# signal) will not check them until it sees
the clock edge. It is possible for multiple processors to assert LOCK#
during a single clock cycle; the memory controller will see them as
simultaneous, and will have some kind of priority scheme to allow one of
them to win, while the other one gets wait states.

You are saying that the probability of failure in a normally operating
system is not zero. Nonsense. Barring a physical failure, like a
broken wire, the probability IS zero.

I’m happy to concede that the average OS will run for years without
error.

That has not been my experience, but the failures are not due to a race
in the LOCK# signal.

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

OSR_Community_User · January 5, 2007, 11:18am

Well, in ten years [the first 10 of my career] of designing, testing, and debugging hardware I’ve looked at plenty of 'scopes, and this is simply not true. Yes, there is a period where the signal is switching and is specified as “indeterminate” because it is between the switching thresholds of its receivers, and yes, any designer who isn’t a total idiot understands rise times, fall times, threshold levels, fan-in, fan-out, even wire delays, transmission line effects, noise suppression and all the rest of the wonderful world of practical electronic design.

But it is simple arithmetic to add up all those delays along each path and guarantee a signal is where it needs to be before the minimum setup time for the receiving latch wrt the clock- and that the signal also meets minimum hold times, and that the clock pulse width is within specifications. If even that is a challenge, then there are simulation and design checking / analysis programs to pick up your slack [and more].

The probability of the lock instruction failing is not 0, but not because of this issue- it’s not 0 because hardware fails- parts can go out of spec or even fail catastrophically as they age. It’s also not 0 because even fresh parts may be out-of-spec (test processes are not 100%, ever). It’s even not 0 because this stuff is made by human beings, which are notoriously fallible. But all of those probabilities are about as low as they can be made. Systems can run reliably for years because of this [and additional work done on fault tolerant design].

But the circuit designs simply do not have this flaw. If they do, then they are bad designs. I’ve had to deal with such designs, some of them my own, of course. But to say you can’t properly design a synchronous state machine to deal with asynchronous events is just not true.

Finally, you keep calling the lock signal asynchronous. It can’t be- it has to come out of the same synchronous state machine that eventually decides it’s been granted the lock.

Mike_Kemp · January 6, 2007, 9:53am

Hi Bob

Thanks for coming back on this. I’d intended this as a “food for thought”
item, raising what I thought was a well known (though mostly theoretical)
issue with asynchronous events.

I’d not intended to waste too much time on this, so to all those of us who
are snowed under with development work, please excuse this post, and stop
reading now.

I agree with you that in all practical senses, good design can place any
theoretical error beyond the scope of practical worries. We all hope for
good design but of course many of use here spend a lot of time programming
around problems that slipped through the net into production :-)!

I also agree that with fully synchronous multiple CPUs, the lock signal is
synchronous (btw I never said it was asynchronous in this case, sorry if I
misled you somewhere).

The original thread however was stressing some timing issues that made me
suspect that it may relate to a situation where the CPUs were asynchronous,
as otherwise I, like you, cannot see any issue to talk about. Of course with
synchronous CPUs, simultanoeus events are common and easy to cope with.

The only place I draw a line is with the assertion that asynchronous signals
can be handled with 100% foolproof design, full stop, end of discussion.

I have to say, I’d like to believe it, but simply asserting it is not going
to persuade me, or hopefully, anyone else.

I ran the following short argument (intended to prove my claim that
asynchronous events exist that will break any logic system) passed my
hardware designer, and it raised an question I’ll mention below. First, here
is the argument:

Given we have a synchronous logic system with an asynchronous input, and a
asynchronous event occurs. The logic system is required to enter one of two
states A or B depending on whether the event occurs before or after the
system clock in question.

Assume that relative to a specific system clock, there is a latest time Ta
at which the asynchronous event will be recognised and outcome A results.
Assume there is also an earliest later time Tb at which the event is not
recognised, and outcome B results.

Clearly Ta != Tb as both results cannot occur.

Therefore there exists a time Tx such that Ta < Tx < Tb at which neither
outcome would result, otherwise this would invalidate our assumption that Ta
was already the latest time for outcome A and Tb was already the earliest
time for outcome B.

You then have a system that has broken, as the asynchronous event has caused
an outcome that is neither A nor B.

My hardware designer said that all that would happen is that in the
intervening period, event A or B would occur at random because of noise. (We
can eliminate component tolerance as this is a “specific” system).

However, does this mean that the only reason we can make a system 100%
reliable is because of the existence of random noise? A perfect system
without noise is surely proved to be at risk by the argument above.

Also, even in the presence of noise, the above argument applies, as all it
does it create a whole bunch of Ta and Tb pairs. All we have to do is
examine the first such pair, apply the above argument, and sure enough there
exists a time when the logic system fails to make the decision.

Someone has suggested this is just a glitch situation, add a clock delay and
latch it again. However all this does it make a new logic system, slightly
different to the preceeding one. The argument above applies to ALL logic
systems, however many double checks are made. I fear this also includes
adding a software workaround, as this is also just fiddling within the black
box.

I’d truly like to understand where the argument above falls down, if it
does. Regrettably my old university lecturers are mostly gone now so I can’t
go back to them. If anyone knows of a web forum for this I’d like to dip in
as time allows.

Anyway, please take this as intended, food for thought, not a criticism of
designers and hopefully not the ramblings of an incompetent!

Best regards

Mike

----- Original Message -----
From: Bob Kjelgaard
To: Windows System Software Devs Interest List
Sent: Friday, January 05, 2007 4:17 PM
Subject: RE: [ntdev] confused with DDK docs

Well, in ten years [the first 10 of my career] of designing, testing, and
debugging hardware I’ve looked at plenty of 'scopes, and this is simply not
true. Yes, there is a period where the signal is switching and is specified
as “indeterminate” because it is between the switching thresholds of its
receivers, and yes, any designer who isn’t a total idiot understands rise
times, fall times, threshold levels, fan-in, fan-out, even wire delays,
transmission line effects, noise suppression and all the rest of the
wonderful world of practical electronic design.

But it is simple arithmetic to add up all those delays along each path and
guarantee a signal is where it needs to be before the minimum setup time for
the receiving latch wrt the clock- and that the signal also meets minimum
hold times, and that the clock pulse width is within specifications. If
even that is a challenge, then there are simulation and design checking /
analysis programs to pick up your slack [and more].

The probability of the lock instruction failing is not 0, but not because of
this issue- it’s not 0 because hardware fails- parts can go out of spec or
even fail catastrophically as they age. It’s also not 0 because even fresh
parts may be out-of-spec (test processes are not 100%, ever). It’s even not
0 because this stuff is made by human beings, which are notoriously
fallible. But all of those probabilities are about as low as they can be
made. Systems can run reliably for years because of this [and additional
work done on fault tolerant design].

But the circuit designs simply do not have this flaw. If they do, then they
are bad designs. I’ve had to deal with such designs, some of them my own,
of course. But to say you can’t properly design a synchronous state machine
to deal with asynchronous events is just not true.

Finally, you keep calling the lock signal asynchronous. It can’t be- it has
to come out of the same synchronous state machine that eventually decides
it’s been granted the lock.

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

Christiaan_Ghijselinck · January 6, 2007, 11:12am

Hardware developers are aware of such situations. One method is to postpone the
read out of the signal ( thus , not ACKing ) of the event during the transition time of the “system clock” .
As per result , outcome B will be the result since the event will we handled when the system clock
transistion has ended. I agree that this is already a kind of asynchoneous hardware handshaking
mechanism. The other approch is fully synchroneous : the hardware that “events” the other
hardware has to “pulse” the event for a specific long duration , always mentioned in specifications ! That
duration must be bigger than the “system clock” handling to assure that the event will be detected.
Within your particular example , outcome B will be once more the result.

Btw . , hardware developers have to use more brain cells to develop their hardware than software
people have to develop their software [joking]

Christiaan

----- Original Message -----
From: “Mike Kemp”
To: “Windows System Software Devs Interest List”
Sent: Saturday, January 06, 2007 3:52 PM
Subject: Re: [ntdev] confused with DDK docs

> Hi Bob
>
> Thanks for coming back on this. I’d intended this as a “food for thought”
> item, raising what I thought was a well known (though mostly theoretical)
> issue with asynchronous events.
>
> I’d not intended to waste too much time on this, so to all those of us who
> are snowed under with development work, please excuse this post, and stop
> reading now.
>
> I agree with you that in all practical senses, good design can place any
> theoretical error beyond the scope of practical worries. We all hope for
> good design but of course many of use here spend a lot of time programming
> around problems that slipped through the net into production :-)!
>
> I also agree that with fully synchronous multiple CPUs, the lock signal is
> synchronous (btw I never said it was asynchronous in this case, sorry if I
> misled you somewhere).
>
> The original thread however was stressing some timing issues that made me
> suspect that it may relate to a situation where the CPUs were asynchronous,
> as otherwise I, like you, cannot see any issue to talk about. Of course with
> synchronous CPUs, simultanoeus events are common and easy to cope with.
>
> The only place I draw a line is with the assertion that asynchronous signals
> can be handled with 100% foolproof design, full stop, end of discussion.
>
> I have to say, I’d like to believe it, but simply asserting it is not going
> to persuade me, or hopefully, anyone else.
>
> I ran the following short argument (intended to prove my claim that
> asynchronous events exist that will break any logic system) passed my
> hardware designer, and it raised an question I’ll mention below. First, here
> is the argument:
>
> -------------------
>
> Given we have a synchronous logic system with an asynchronous input, and a
> asynchronous event occurs. The logic system is required to enter one of two
> states A or B depending on whether the event occurs before or after the
> system clock in question.
>
> Assume that relative to a specific system clock, there is a latest time Ta
> at which the asynchronous event will be recognised and outcome A results.
> Assume there is also an earliest later time Tb at which the event is not
> recognised, and outcome B results.
>
> Clearly Ta != Tb as both results cannot occur.
>
> Therefore there exists a time Tx such that Ta < Tx < Tb at which neither
> outcome would result, otherwise this would invalidate our assumption that Ta
> was already the latest time for outcome A and Tb was already the earliest
> time for outcome B.
>
> You then have a system that has broken, as the asynchronous event has caused
> an outcome that is neither A nor B.
>
> -------------------
>
> My hardware designer said that all that would happen is that in the
> intervening period, event A or B would occur at random because of noise. (We
> can eliminate component tolerance as this is a “specific” system).
>
> However, does this mean that the only reason we can make a system 100%
> reliable is because of the existence of random noise? A perfect system
> without noise is surely proved to be at risk by the argument above.
>
> Also, even in the presence of noise, the above argument applies, as all it
> does it create a whole bunch of Ta and Tb pairs. All we have to do is
> examine the first such pair, apply the above argument, and sure enough there
> exists a time when the logic system fails to make the decision.
>
> Someone has suggested this is just a glitch situation, add a clock delay and
> latch it again. However all this does it make a new logic system, slightly
> different to the preceeding one. The argument above applies to ALL logic
> systems, however many double checks are made. I fear this also includes
> adding a software workaround, as this is also just fiddling within the black
> box.
>
> I’d truly like to understand where the argument above falls down, if it
> does. Regrettably my old university lecturers are mostly gone now so I can’t
> go back to them. If anyone knows of a web forum for this I’d like to dip in
> as time allows.
>
> Anyway, please take this as intended, food for thought, not a criticism of
> designers and hopefully not the ramblings of an incompetent!
>
> Best regards
>
> Mike
>
> ----- Original Message -----
> From: Bob Kjelgaard
> To: Windows System Software Devs Interest List
> Sent: Friday, January 05, 2007 4:17 PM
> Subject: RE: [ntdev] confused with DDK docs
>
>
> Well, in ten years [the first 10 of my career] of designing, testing, and
> debugging hardware I’ve looked at plenty of 'scopes, and this is simply not
> true. Yes, there is a period where the signal is switching and is specified
> as “indeterminate” because it is between the switching thresholds of its
> receivers, and yes, any designer who isn’t a total idiot understands rise
> times, fall times, threshold levels, fan-in, fan-out, even wire delays,
> transmission line effects, noise suppression and all the rest of the
> wonderful world of practical electronic design.
>
> But it is simple arithmetic to add up all those delays along each path and
> guarantee a signal is where it needs to be before the minimum setup time for
> the receiving latch wrt the clock- and that the signal also meets minimum
> hold times, and that the clock pulse width is within specifications. If
> even that is a challenge, then there are simulation and design checking /
> analysis programs to pick up your slack [and more].
>
> The probability of the lock instruction failing is not 0, but not because of
> this issue- it’s not 0 because hardware fails- parts can go out of spec or
> even fail catastrophically as they age. It’s also not 0 because even fresh
> parts may be out-of-spec (test processes are not 100%, ever). It’s even not
> 0 because this stuff is made by human beings, which are notoriously
> fallible. But all of those probabilities are about as low as they can be
> made. Systems can run reliably for years because of this [and additional
> work done on fault tolerant design].
>
> But the circuit designs simply do not have this flaw. If they do, then they
> are bad designs. I’ve had to deal with such designs, some of them my own,
> of course. But to say you can’t properly design a synchronous state machine
> to deal with asynchronous events is just not true.
>
> Finally, you keep calling the lock signal asynchronous. It can’t be- it has
> to come out of the same synchronous state machine that eventually decides
> it’s been granted the lock.
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.osronline.com/article.cfm?id=256
>
> To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

OSR_Community_User · January 6, 2007, 1:01pm

It might interest you to know that the ARM 9 processor (or some variant of it) is an entirely asynchronous design. I don’t know what point it is at, release-wise, but it’s more than a whiteboard idea. I think their main design goal is very low power consumption when idle, but it also has some interesting properties, like a more diffuse EM signature.

http://www.eetimes.com/news/latest/showArticle.jhtml?articleID=179101800

Also, I don’t buy your argument about Ta, Tb, etc. There aren’t two distinct, and therefore probably unequal, time intervals. There’s one, and the analog state of a particular synchronous bit converges to known value by the time the clock rises/falls. When the input changes near that time, the result is basically arbitrary, but that doesn’t matter – it’s going to be one value or the other.

A lot of hardware wouldn’t work, at all, if this weren’t true.

From: xxxxx@lists.osr.com [xxxxx@lists.osr.com] On Behalf Of Mike Kemp [xxxxx@sintefex.com]
Sent: Saturday, January 06, 2007 6:52 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] confused with DDK docs