Replace ABA primitives with LL/SC emulation?

[nwf]

CHERI builds primarily on RISC platforms, specifically MIPS and RISC V, which have native LL/SC support. AFAICT, MIPS R4K promises relatively strong LL/SC operation (permitting loads and stores from the core having done the LL); RISC V promises little but presumably real implementations will also be relatively strong. Anyway, on these platforms, I think ds/aba.h is more of a hindrance than a help; the sole user, ds/mpmcstack.h is forced to phrase its operations in terms of CAS and so will always require ABA protection. While the existing non-X86 paths in ds/aba.h optimistically fall back to just a pointer-sized CAS, this fails to deliver effective ABA protection

I am unsure what the correct answer is, but I think, at least broadly, that mpmcstack should be rewritten in terms of a LL/SC primitive that can be provided by some platform-specific code. I haven't come up with a better answer than something like this, tho', which isn't great, so other thoughts are more than welcome. Notably, this approach, I think, relies very, very heavily on the compiler's ability to inline to produce good code.

  template<typename T, Construction c = RequiresInit>
  class LLSC
  {
    /* Cmp defined as in existing ds/aba */
  private:
   Cmp value;

  public:
    inline bool llsc(std::function<bool, T*> f, bool* out)
    {
      T t;
      // Load link t from this, or load t and the generation counter
      *out = f(&t);
      if (*out)
      {
        // Store conditional or CAS2 with incremented generation counter
      }
      else
      {
        return true; // will cause exit from calling loop, which can look at *out
      }
    }
  }

[mjp41]

We really require the only way to make a Cmp is Cmp read(), then I think the current interface may be fine for LL/SC. I.e. the

using Cmp = T*;

Is not good enough. But the idea is that you can only compare exchange with a previously read value. The previously read value would be LL, and then the compare exchange would be a SC.

I am unsure on the semantics of LL/SC around multiple LL operations, i.e. what would happen if a thread has multiple ABA operations in progress, then I am not sure this API would protect enough.

[nwf]

Most implementations permit only a single LL/SC in flight at once, which is a bit of a travesty, but is what we have. That said, I have been hacking up a LL/SC implementation of ds/aba.h following your suggestion that load() is LL and will let you know how it goes.

[mjp41]

Great thanks.

We probably want the Debug version to store the address read from in the Cmp. So that we can check the exchange is on the right location.

In fact, it might be interesting to change the API a little

    struct Cmp
    {
      T* ptr;
      uintptr_t aba;  // For X86
      T** addr;  // ABA protected location read from

      bool compare_exchange(T* t) { ... }
    };

Then compare_exchange is guaranteed to be on the same location.

So effectively would do something like

    ABA a = ...;
    Cmp c = a.read();
    do
    {
       ....
    } while (c.exchange(new_v));

in the mpmcstack.

[mjp41]

@nwf Did you ever get any further on this? I realised the ARM implementation does not actually do the load-link/store-conditional, so is broken. I am about to work on this, but if you have thoughts please let me know.

[nwf]

No, I think whatever I did down this path I long-since abandoned. The work for Cornucopia used some rather hackish inline assembler, as found in bb81acc from https://github.com/CTSRD-CHERI/snmalloc .

[mjp41]

@nwf, Thanks Wes, I think the new API I have implemented is roughly what we agreed here, so hopefully will match LL/SC semantics for ARM/MIPS/RISC V. I have a back up implementation using a lock, so any platform should work, and then we can make it non-blocking with custom implementations later.

[mjp41]

Done in #161