Go: pointer bit stealing technique

[Vitaly Isaev]

In a well-known book "The Art of Multiprocessor Programming" by Herlihy, Shavit some of lock-free and wait-free algorithms utilize Java's template AtomicMarkableReference<T> type. It allows to perform single atomic CAS operation on the pair consisting of T reference and boolean mark.

There is no similar type in C/C++/Go stdlib, but at least in C++ it's possible to model it using bit stealing approach (see C++ example). On x86_64 arch only 48 bits of 64 bits are actually used, so one can store arbitrary data in the remaining 16 bits, and work with the whole pointer and the data atomically.

As far as I understand, there are two requirements to implement this approach:

1. Pointers must be aligned.
2. Pointer's low bits must be clear (if you want to store something like bool in this area, it must not be already occupied).

But some stackowerflow users have questioned whether these remaining bits are really free in Go. Perhaps Go runtime already uses these area for GC or some other background routines?

So is it possible to use pointer bit stealing technique in Go? Are there any working examples?

Thank you

[Robert Engels]

The Java implementation does not use bit stealing - it uses an atomic pointer to an immutable struct - the same can be done in Go. 

On May 6, 2021, at 6:16 AM, Vitaly Isaev <vitaly...@gmail.com> wrote:



--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b9e78da6-2a88-444b-9d83-64c2341bdc22n%40googlegroups.com.

[David Riley]

On May 6, 2021, at 7:16 AM, Vitaly Isaev <vitaly...@gmail.com> wrote:
>
> There is no similar type in C/C++/Go stdlib, but at least in C++ it's possible to model it using bit stealing approach (see C++ example). On x86_64 arch only 48 bits of 64 bits are actually used, so one can store arbitrary data in the remaining 16 bits, and work with the whole pointer and the data atomically.

I would strongly recommend that you not do this, because this has a nasty way of breaking a LOT of things in the future. The original Macintosh system software and ROMs used this "clever" technique almost exactly, because the 68000 only had a 24-bit address bus. When the 68020 came out and people wanted to use more than 16 MB of address space, it created BIG problems which took many years to resolve (and many things were not completely resolved until Apple moved to the PowerPC).

History is littered with examples of why you should not do naughty things with "unused" pointer bits (see also ARM's Thumb instruction set, which used the unused LSB of the instruction counter to signify Thumb mode, causing headaches for compiler, debugger and disassembler writers to this day).


- Dave

[Ian Lance Taylor]

The Go language spec does not in any way guarantee that this will
work. If it happens to work today, it may break in the future. So I
definitely recommend against it.

That said, I believe it will work today, and in fact the Go runtime
uses a somewhat similar technique internally (by the way, in the bit
stealing approach you need more than a boolean mark, or you will get
ABA problems). It's OK for the Go runtime to do this, because if we
break the required guarantees in the future we will fix the Go runtime
at the same time. The relevant code is

https://golang.org/src/runtime/lfstack.go
https://golang.org/src/runtime/lfstack_32bit.go
https://golang.org/src/runtime/lfstack_64bit.go

Again, outside of the runtime code like this is not supported and may
well break in the future.

Ian