The autopkgtest to check Rumur could generate a compilable model contains logic
to decide whether linking against libatomic is needed, but this logic did not
correspond to the actual verifier code closely enough. The __sync built-in it
tests can be lowered to a single instruction on ≥ armv8.1-a, but the __atomic
built-ins used in the actual verifier cannot.

Changes to the verifier itself should now allow it to be lock-free on ≥
armv8.1-a. This change updates the logic used to check libatomic requirements to
something that approximates the new verifier.

Debian: fixes https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1018205


Reported-by: Tobias Frost <tobi@debian.org>
Thanks: Caroline Xu

remove 'final' from AST, Indexer 

Doxygen apparently understands this as an alternative to `\p` and it allows
writing with less ambiguity.

External users sometimes want to extend the AST with their own nodes or a node
that is “this existing node with a slight tweak.” Having methods marked `final`
forces them into forking Rumur just to remove these annotations. Recent analysis
has also suggested there is no significant performance benefit from `final`.¹

¹ https://16bpp.net/blog/post/the-performance-impact-of-cpp-final-keyword/

avoid linking libatomic if possible on ARM64

Double-word atomics are used to implement lock-free reference-counted pointers.¹
Compiler built-ins (the GCC __sync and __atomic built-ins) are used to access
this functionality. It is up to the compiler how to lower these built-ins, and
it chooses between emitting inline instructions or calling into the libatomic
runtime support library.² The implementations in libatomic are typically not
lock-free – they work by using per-variable-instance mutexes – which negates the
performance benefits of the lock-free algorithm we are trying to implement. In
tight code like our scenario, the function call overhead into libatomic is also
a noticeable factor.

It was observed that on ARM64 GCC lowers these __atomic built-ins into libatomic
calls. ARM64 has Load-Linked/Store-Conditional (LL/SC) instructions that can be
used to implement these inline, but GCC has traditionally avoided using these to
back the atomics.³ While compiler developers were debating the utility of these
instructions, ARM introduced “Large System Extensions,” adding a new CASP family
of instructions that more efficiently implements compare-and-swap.

So our aim is to use the CASP instructions where possible. We have the following
matrix:

  ┌──────┬───────────────────────┬───────────────────────┐
  │      │       Clang           │         GCC           │
  ├──────┼───────────────────────┼───────────────────────┤
  │ load │     __atomic          │       __sync          │
  │      │ <armv8.1-a: LL/SC     │ <armv8.1-a: libatomic │
  │      │ ≥armv8.1-a: CASP      │ ≥armv8.1-a: CASP      │
  ├──────┼───────────────────────┼───────────────────────┤
  │ store│     __atomic          │       __sync          │
  │      │ <armv8.1-a: LL/SC     │ <armv8.1-a: libatomic │
  │      │ ≥armv8.1-a: CASP      │ ≥armv8.1-a: CASP      │
  ├──────┼───────────────────────┼───────────────────────┤
  │ CAS  │     __atomic          │       __sync          │
  │      │ <armv8.1-a: libatomic │ <armv8.1-a: libatomic │
  │      │ ≥armv8.1-a: CASP      │ ≥armv8.1-a: CASP      │
  └──────┴───────────────────────┴───────────────────────┘

This seems to result in a near-optimal situation on ≥armv8.1-a. For <armv8.1-a,
the only way to avoid linking against libatomic seems to be resorting to inline
assembly which is not worthwhile.

Reported-by: e69d5a347277e5e7cb23518d93266bdac89a4bad

¹ Specifically “Hazard Pointers” as described in Maged Michael’s “Hazard
  Pointers: Safe Memory Reclamation for Lock-Free Objects” in TPDS 15(8) 2004.
² GCC 10.1 introduced a third option that does a runtime check, similar to GNU
  indirect functions (IFUNCs),
  https://community.arm.com/arm-community-blogs/b/tools-software-ides-blog/posts/making-the-most-of-the-arm-architecture-in-gcc-10.
  However, this is not relevant to us.
³ See https://gcc.gnu.org/pipermail/gcc-help/2017-June.txt for a lengthy debate
  on this and https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878 for the
  underlying rationale for avoiding both LL/SC and cmpxchg for backing these
  atomics. As one participant in the first linked discussion accurately
  summarises, “I think what’s happened makes perfect sense at each step of the
  way but has led to an outcome which is crazy.”

This is preparation for leveraging this to avoid linking against libatomic on
aarch64.

As discussed in the prior commit, this can avoid the need for linking against
libatomic.

The value of `-march=…` can be a factor in deciding whether linking against
libatomic is required. In particular, on aarch64 libatomic is required for <
armv8.1-a.

Upcoming changes make this branch apply on aarch64 too. Unfortunately as-is it
triggers a GCC bug. This rephrasing manages to side step the issue.

GCC: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114310

Python modernisation

This is more intuitive to C programmers and more in line with contemporary
formatter choices like Black.

The last fragments of Travis CI testing were removed in
bfefe96b.

It is unclear why we were not using this already.
b3288d12 backported this script to Python 3.4,
but `shutil.which` is already available there.

fix: avoid mixing '__sync_*' and '__atomic_*' built-ins on ref-counted pointers

When operating on reference counted pointers that take up a double-word,
`refcounted_ptr_peek` was using a single-word read as an optimisation because it
only needs the first word of the data. Meanwhile the other operations on
reference counted pointers were using double-word compare-and-swap. On x86-64
with `-mcx16`, this results in near-optimal code: `CMPXCHG16B` for the
double-word operations and `MOV` for the single-word read.¹ Similar for x86.

Unfortunately on other platforms, this design can result in non-atomic
operations. To understand why, note that the compiler has a number of options
for lowering both the `__sync_*` built-ins and the `__atomic_*` built-ins. Two
of these options are (1) an inline instruction sequence and (2) a call to a
libatomic function. A constraint is that its choices must interoperate
correctly. For example, lowering a 16-bit `__atomic_load` to a `MOV` and a
16-bit `__atomic_store` to a libatomic call (which is typically implemented with
a per-instance mutex) would be incorrect. The following interleaving could
occur, assuming X begins with the value 0x0:

  1. Thread A calls `__atomic_store` on X
  2. Thread A’s libatomic call takes a lock on X
  3. Thread A writes 0xad into the first byte of X
  4. Thread B loads both bytes of X in a single instruction
  5. Thread A writes 0xde into the second byte of X
  6. Thread A releases the lock on X

It would have been valid for thread B to read either 0x0 (seeing the value
before A’s store) or 0xdead (seeing the value after A’s store), but it instead
saw a torn read of 0x00ad. Because the load and store do not agree on the
protocol for synchronisation, atomicity can be violated.

Crucially the compiler is only required to maintain this compatibility between
the _same_ built-ins on the _same_ data type. The `__sync_*` built-ins and the
`__atomic_*` built-ins are not required to use compatible protocols (and indeed
they do not on x86-64 with `-mcx16`). And operations on a double-word type are
not required to use a compatible protocol with operations on a single-word type
(and indeed they do not on x86-64 _without_ `-mcx16`).

The code in `refcounted_ptr_peek` was violating _both_ of these assumptions. On
x86-64 without `-mcx16` it resulted in racy code, as it also did on ARM64. We
could try to detect the narrow scenario wherein it is safe to mix built-ins
because we know exactly which single instructions they will be lowered to (the
ideal case on x86-64 described in the first paragraph), but this change
conservatively switches to a double-word read which we know meets the compiler’s
assumptions.

¹ `MOV` is atomic on naturally aligned 8-/16-/32-/64-bit data on x86-64.

various tweaks

As encoded in a static assertion, the verifier assumes

  sizeof(refcounted_ptr_t) >= sizeof(struct refcounted_ptr)

However, some locations were implicitly assuming something stronger, that these
two were equally sized. This stronger property is true on most platforms – the
double word used for `refcounted_ptr_t` is exactly the same size as the
reference-counted pointer struct – but on esoteric platforms it may not be. If a
pointer is e.g. 2 bytes, the struct may end up being 4 bytes while
`refcounted_ptr_t` is 8 bytes.

To remedy this we need to:

  1. Always use `sizeof(struct refcounted_ptr)` in `memcpy` sizes in preference
     to `sizeof(refcounted_ptr_t)` to avoid over-reading/-writing; and

  2. Zero-initialise `refcounted_ptr_t` variables into which we are about to
     perform a (possibly short) `memcpy`.

This has never run in this repository and is currently disabled because there
was a ≥ 60 day window without commits. It has not been valuable in other C/C++
projects in which I have used it, so lets just remove it.

CI: add an aarch64 job

print configuration variables when running the test suite

CI: upgrade FreeBSD

This was EOLed on 2023-12-31.¹

¹ https://www.freebsd.org/security/unsupported/

Suggested-by: Lintian

Suggested-by: Tobias Frost <tobi@debian.org>

Debian: fixes https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1018202


Reported-by: Tobias Frost <tobi@debian.org>
Suggested-by: Tobias Frost <tobi@debian.org>