tagged_ptr assumes zero leading bits

[nyh@…]

I've noticed that boost::lockfree::queue does not work on the OSv operating system, crashing when used.

After some investigation, I discovered the problem: lockfree::queue uses tagged_ptr, and that, when compiled on x86_64, uses tagged_ptr_ptrcompression which assumes that pointers always start with 16 zero bits.

The thing is - the x86_64 standard does *not* guarantee that pointers must start with all zero bits. It just guarantees that pointers are so-called "canonical", meaning that the first 16 (usually) bits are either all 0, or all 1. But they *can* be all 1-s, and indeed in OSv, malloc()ed memory has addresses starting with all 1s. By the way, in Linux, kernel-space memory (as opposed to user-space memory) also has such addresses.

But tagged_ptr::extract_ptr() assumes that the leading bits of pointers are always zero - which happens to be true on Linux's user-space memory but is not generally guaranteed by x86_64 (and isn't true on OSv).

I'm not sure what to suggest as a fix. One not-really-safe-but-will-probably-work-in-practice option is to choose to fill the pointer with 0 or 1 bits depending on the 47th bit. Another not-quite-foolproof option is to assume that in one program all pointers will start with the same prefix (all 0 or all 1), so calculate this prefix once at runtime and then use it every time.

[nyh@…]

Another more-reliable fix is to keep one of the tag bits unchanged - i.e., zero only 15 bits, not 16 bits, and then the original pointer can be restored by extending bit 48. But this will mean that now only 15 bits are available for a tag, not 16. I don't know whether this is acceptable or not.

[timblechmann]

as a workaround, you can try to configure the queue to use array indices instead of pointers ...

for OSv one could either provide a separate version of tagged_ptr_ptrcompression or to use tagged_ptr instead of tagged_ptr_ptrcompression. this will require a cmpxchg16b instruction, though.

i don't have access to OSv, but i'd happily accept a patch!

[anonymous]

By the way, this month, Intel announced - ​https://software.intel.com/sites/default/files/managed/2b/80/5-level_paging_white_paper.pdf - that it will be releasing processors which support 57 bits of addresses, which will leave only 7 bits unused in pointers (6 bits, if you consider the need to remember if it's all zeros or all ones). It may be time to reconsider the validity of the tagged_ptr implementation?