Why did InterlockedIncrement/Decrement only return result’s sign? (2004) | Hacker News Reader

Why did InterlockedIncrement/Decrement only return result’s sign? (2004)

devblogs.microsoft.com

62 pointsuserbinator43 comments

I never would have guessed that what I take for granted to be a multi-threaded intrinsic actually existed long before x86 multi-threading was widespread. A quick search shows potential dual 386 boards, I assume these instructions were to support those?

These instructions exist to support preemptive multitasking, not multi-processing. Your process can get suspended in the middle of non-atomic additions. Then you have a race condition.

that makes sense

On x86, inc/dec cannot be interrupted. The main use-case for these atomic inc/dec functions (and the associated LOCK prefix, which has been there since the 8086) is indeed for multiprocessing. x86 was designed to support multiprocessing from the beginning, although it was rarely used, mostly in systems outside the PC architecture.

INC/DEC don’t give you a copy of the value to examine (the Windows 98 behavior described in the article). If you want that, you need a second instruction and you need to worry about being interrupted.

The parent is correct. You don't need to worry about being interrupted. If you did no program would be correct in the presence of interrupts. The entire state of the processor can be saved and restored during an interrupt as if nothing has happened. LOCK is for multi-processing.

EDIT: That said you do have to worry about being interrupted mid-sequence of instructions and data races but that's what critical sections are for. So INC or DEC (which increment/decrement and set flags) are perfectly safe under interrupts. If you have more a more complex sequence then you need a critical section. However they are not safe (without the LOCK) under multi-processing.

EDIT2: also to clarify you're not interrupted mid-instruction. I.e. you can't observe the undelying read/modify/write through interrupts, only through a second core/processor.

It’s clear from the article and the chain of parent comments that we’re talking about threads with preemptive multitasking and access to a shared integer in memory. I didn’t say INC/DEC are unsafe; I said they don’t satisfy the contract of the function in the article, the whole point of which is about the return value. If you (e.g.) combine an INC/DEC with a MOV to fetch the return value, that’s unsafe. You can make it safe with a critical section, but that may be unnecessarily inefficient. The XADD instruction referenced in the article, when it’s available (486+), can be used to satisfy the contract without this overhead.

But the concern with a shared integer is correctness under inc/dec. If you have a multi-processor and you don't LOCK then the value can be anything because it's racy. With multiple threads there is still correctness when multiple threads access the atomic and the flags returned are correct without the need to "lock the bus". The article just explains why the return value uses the flags - for correctness. If you have a sequence of instructions then (potentially) you don't have correctness either with multiple threads on the same core or across cores.

EDIT: if your point was that you can't return the value using either LOCK INC or INC and either on a single core or multiple cores then your point is correct. I sort of read it as INC itself (the x86 instruction) is racy under multi-threading.

The context in which this discussion takes place is “Return Values: The function returns the resulting incremented value” and “Since Windows 98 was a uniprocessor operating system, it didn’t have to worry about a second processor changing the memory at the same time”. The concern with a shared integer in this context is that you get interrupted between INC and MOV.

As the comment you reply to states: “INC/DEC don’t give you a copy of the value to examine. (…) If you want that, you need a second instruction.”

Here’s what you might be missing: Even on a single processor machine, if you have multiple threads and a preemptive (!) multitasking OS like Windows 95, any locking protocol can be interrupted mid-sequence. A second OS thread (yes, they existed) may be scheduled and observe an inconsistent state. Or it may perform an update on its own and leave the first state in an inconsistent state when it resumes.

And yes, this kind of stuff actually happened.

I wrote that sort of code on those sorts of platforms ;) The bigger problem was code that assumed INC/DEC was atomic and broke when the first multi core CPUs came out. Everyone knows/knew that a sequence of instructions can be interrupted with multiple OS threads and preemption. So I don't think I'm missing that. INC/DEC give you flags but they don't give you a copy of the value. But you still need to LOCK INC or LOCK DEC for your code to be multi-core safe. And if you're sharing values you need something like "test and set" or a kernel synchronization object.

EDIT: I was basically saying the comment above that was correct because the comment I was replying to seemed to suggest it wasn't. But I guess both of them are correct and we're all in agreement ;)

EDIT2: So really I agree that InterlockedIncrement/Decerement were designed for multi-processing use case since they basically offer no advantage for a single core over just inc/dec (++/--) this is what the comment above the one I was replying to (gp?) was implying and the person responding to that seemed to think otherwise ;) but I think we still found out we all agree.

Were these ALU primitives or were they like "load, increment, store"?The latter could easily be non-atomic.

INC/DEC are internally decomposed into separate read-modify-write operations, but are still atomic with regards to interrupts; for multiprocessing you need the LOCK prefix, which in the past brute-force locked the memory bus, but these days make sure that the operations are scheduled in such a way that the core is guaranteed not to lose ownership of the cacheline.

Right, many of the early (~1975) era microcomputers were bus backplane machines, where the CPU boards were just one of the "bus masters" and designed to cooperatively share the mostly passive backplane. (ex: ss-50, s-100).

It was fairly common to attach z80's and the like as secondary co-processors, as well as allowing peripheral boards direct access to RAM/etc via DMA. So, while I'm not aware of anyone building a machine using multiple 8086's its was pretty common to put 8086's and z80's together in the same machine, nevermind the 8087 was effectively a second processor as well until it was integrated in the 80486 DX.

Although looking at a few of the schematics on http://www.s100computers.com/index.html I don't see anyone actually using the 8086 #LOCK pin even if they are running the processor in max mode to gain the extra control lines for the S-100. Probably because few people were thinking about full _symetric_ Multi Processing, vs heterogeneous machines, which were fairly common. Z80 boards existed for a lot of machines (I had one for my apple II+), as did various other combinations.

Probably DMA accesses

Original comments on the article:

https://web.archive.org/web/20190201150607/http://blogs.msdn...

Alternatively,

http://bytepointer.com/resources/old_new_thing/20040506_174_...

Weird digression: Where is he getting the term "interlocked"? That's not the industry term ("atomic"), nor is it something from Intel (who talk about the LOCK prefix, and a "bus lock" in older hardware manuals, the word "interlock" appears in the SDM in just a few places where it's talking about pipeline stall behavior).

Chen seems to be using it confidently, and it's clearly there in the names of the API entry points. Is this just something Microsoft made up? It's the first I've noticed it.

I think it’s as simple as the industry not having reached consensus on “atomic” at the time Microsoft was naming these things. The terminology around concurrent programming was absolutely in flux in the late ‘80s & early ‘90: Windows programmers were more familiar with “critical sections” as an abstraction than mutexes.

> Windows programmers were more familiar with “critical sections” as an abstraction than mutexes.

I disagree on that front. Mutex kernel objects have existed just as long as critical sections. Critical section objects are cheaper because they don’t switch into the kernel when not contended.

A Win32 critical section enters the kernel when blocked. (Edit: nevermind, you're not disputing this)

A pthread mutex on Linux won't enter the kernel when uncontended (thanks to futex -- this wasn't true ~20 years ago).

I would say the terms are pretty synonymous, and implementation choices differ; sometimes implementation choices are implied by the name but I don't think everybody agrees on how those choices map to names.

That’s only an implementation/optimization difference, I think it’s also relevant to understand why that’s the case. At the API level, the important distinction is that a Mutex an be shared between processes. This is great when you need it, but having the capability makes Mutexes have a somewhat expensive implementation. CriticalSections stay inside the process, so can be optimized for that (more common) use case.

Precisely.

> A safety device that prevents activation in unsafe conditions.

-- https://en.wiktionary.org/wiki/interlock#Noun

Which seems weirdly fitting considering the Win98 behavior on 80386 CPUs ;)

Further googling leads me to believe that MS indeed made the term up for referring to atomic operations back then, but they kept it ever since.

I suspect it's just a Microsoft-ism that came from the LOCK prefix.

I don't think Microsoft invented it:

> On the CDC CYBER, an interlock register is available ... Operation of this interlock register is similar to TEST AND SET

Concurrency in Operating Systems, October 1976 https://www.computer.org/csdl/magazine/co/1976/10/01647182/1...

To add to this, an interlock (which unfortunately is a dated term) is the part of the hardware checking for atomicity when required.

Perhaps it worked during development but at release Windows 98 required a 486 processor:

https://web.archive.org/web/19990420193302/http://microsoft....

I remember writing user code that the documentation said it would return the new ref count... But then not actually because that couldn't be guaranteed, and the return value was only useful for debugging. I just treated it as void and was surprised any number leaked out was useful. On the other side of the wall the return value was probably required.

> Okay, you also get some obscure information like whether there were an even or odd number of 1 bits in the bottom 8 bits of result, but that’s hardly useful nowadays.

I'm honestly curious, was it ever useful, or is it just an expression?

Parity is cheap to calculate in hardware but much more expensive to do purely in software. See https://stackoverflow.com/questions/25707130/what-is-the-pur...

The parity flag goes all the way back to the Intel 8080 and Z80 (gosh, even the Intel 4004 it seems [2]) and AFAIK was used for error detection when reading data from IO devices [1].

[1] https://en.wikipedia.org/wiki/Parity_bit

[2] https://12ft.io/proxy?q=https%3A%2F%2Fwww.hackster.io%2FMayu...

I love how this shows some of the problems with unnecessary dependencies even back in 1995.

Let’s say you really only cared about the sign of the result — freeing a resource when a refcount reaches 0 is a plausible use-case for that. But instead of using a single CPU instruction, you decide to link in a Windows function, because it’s easy, and why not pay for the overhead of a dynamically linked function call when CPUs are so fast?

And the joke is, when users upgraded to Windows 98, your program became a lot slower, because without asking you, the API was augmented to emulate a CPU feature you don’t need.

If this isn’t essentially 1995’s left-pad, I don’t know what would qualify.

Writing assembly isn't portable. Windows NT 3.1-4 ran on MIPS, PowerPC, and more. Intel was coming out with new instruction sets all the time.

Not sure why you mention Intel extending their instruction set, the addition of stuff like SIMD never changed the behavior of anything that existed before.

Very few programs ran on non-x86 back then anyway. Some people used to argue that writing assembly is more portable than using OS functions. I’m not saying I fully agree with that view, but it’s a discussion one can reasonably have.

Intel was constantly adding new instructions which could be more performant. Inline assembly can never take advantages of that; compilers or OS functions can

To be clear I understand you correctly, you think there was a chance that Intel would add a CPU instruction that is "more performant" than ADD? In fact, significantly so, to the extent that this would justify the overhead of a dynamically linked function call? Do I understand you correctly?

(BTW, this is exactly the kind of argument people made in defense of left-pad, which in my view completely validates my analogy.)

Hopefully on Windows NT the function would be inlined into a single instruction, though I don't exactly have faith in pre-2000 compilers. I assume this would be less than practical on Windows 98 with its fallback path.

The function is dynamically linked from kernel32.dll, compiler inlining is irrelevant here.

Wow, that comment must have hit a nerve.

This takes me back. Richter’s book made me really respect the NT kernel team.

Best it returned nothing.

It could be that was the original intention for just that? But some large 'it must run' program depended on that behavior?

I ended up in something similar with a prog I was working on. I had used some pre-release APIs. By the time they shipped win95 those APIs no longer existed, docs removed and the items purged from the headers. I did not have the luxury of calling someone in MS and saying 'fix that'.

The win16 way was to dig and bend it, mangle, until it worked. The win32 way was a bit lest flexible.

Reply on news.ycombinator.com