Introduce memswap(3) API

[rwatson]

Sundry sort-related utility functions end up implementing their own memory-swapping implementations that typically fail to preserve tags (qsort(), etc). This might be improved in the future by providing a memswap(3) API to C that provides a suitable implementation of swapping the contents of two memory locations -- e.g., memswap(void *dst, void *src, size_t len) that would preserve tags on suitably aligned and suitably sized chunks of memory. This would then ideally be used with uintptr_t when working with data structures that may contain pointers.

[davidchisnall]

A few other issues that need to be considered:

The C++ std::swap template exists for this purpose, but is specialised by type and inlined, so can generate efficient code. Most of the places where you'd need this in C are hot paths doing little work per swap, so the cost of the function call is likely to dominate. As such, this would have to either be a macro, or be something with compiler support.

Swapping can be a lot more efficient if we have a guarantee that dst and src don't alias. Should the API require this, or should we have different variants with different guarantees?

[rwatson]

Agreed on all points -- I'd imagined that memswap(3) (or whatever it ends up being) would be part of C rather than a library API per se, allowing the compiler to optimise it in much the same manner it currently does with memcpy(3), converting calls into more efficient inlined code, or vice versa.

On aliasing: If we think the primary consumer is sorting, then it probably makes sense to guarantee non-overlap. I wonder how much memmove(3) is used in practice...

[davidchisnall]

I wonder how much memmove(3) is used in practice...

LLVM recognises both memmove and memcpy and translates them to intrinsics, (this allows other optimisers to trivially change one form to the other if alias analysis can prove that two don't alias, so you may end up with a memmove call transformed to memcpy in the compiler). A number of coding guidelines recommend using memmove rather than memcpy, because it's easier than thinking and common memmove implementations are not slower than memcpy. Most implicit memcpys are trivially non-aliasing and so memcpy is used.

The distinction is more important for the inlined versions, because they can batch more sequential reads (given enough registers) and interact better with modern pipelines and caches, particularly when the size is known at compile time.

After further thought, I'm not sure how important the aliasing information will be for swap, because you intrinsically need to load both.

[brooksdavis]

Closing in favor of CTSRD-CHERI/llvm-project#395