rb tree: remove strict aliasing violations

[rlibby]

Summary

Rework internal RB macros to avoid assignments via type punned pointers.
RB uses low order pointer bits to encode information (whether children
are red), and was manipulating those values via (*(__uintptr_t *)&elm),
which leads to strict aliasing warnings.

In the kernel we use -fno-strict-aliasing, but this isn't necessarily
the case in user space. This quiets thousands of -Wstrict-aliasing
warnings in the user space build.

Reported by: GCC -Wstrict-aliasing

Test Plan

env CROSS_TOOLCHAIN=amd64-gcc13 make buildkernel
env CROSS_TOOLCHAIN=amd64-gcc13 make buildworld
kyua test

[rlibby]

There are other options for how to spell the internal macros. I'm open to something else that might be more clear. Something in particular I considered is just providing

#define _RB_OP_RVAL(elm, op, dir)	((__typeof(elm))		\
					((__uintptr_t)(elm) op (dir)))
#define	_RB_OP(elm, op, dir)	((elm) = _RB_OP_RVAL((elm), op, (dir)))
#define	_RB_OPUP(elm, field, op, dir)	_RB_OP(_RB_UP((elm), field), op, (dir))

and not _RB_{OR,XOR,ORUP,XORUP} and then having the rb code look like e.g.

			_RB_OPUP(parent, field, ^, elmdir);

instead of _RB_XORUP(parent, field, elmdir).

[kib]

In D52939#1209577, @rlibby wrote:

There are other options for how to spell the internal macros. I'm open to something else that might be more clear. Something in particular I considered is just providing

#define _RB_OP_RVAL(elm, op, dir)	((__typeof(elm))		\
					((__uintptr_t)(elm) op (dir)))
#define	_RB_OP(elm, op, dir)	((elm) = _RB_OP_RVAL((elm), op, (dir)))
#define	_RB_OPUP(elm, field, op, dir)	_RB_OP(_RB_UP((elm), field), op, (dir))

and not _RB_{OR,XOR,ORUP,XORUP} and then having the rb code look like e.g.

			_RB_OPUP(parent, field, ^, elmdir);

instead of _RB_XORUP(parent, field, elmdir).

For me, your current choice is easier to read. I would only suggest to add some additional verb to the macro name to emphasize that it modifies the argument. E.g. _SET instead of UP or something similar.

[rlibby]

kib feedback: macro names could be more clear about modifying the
argument. I went with "MOD" instead of "SET".

[rlibby]

whitespace fixup

[dougm]

I'd make style changes, but they're not important enough to block this, or to have a protracted discussion about it.

sys/sys/tree.h

343

The names _RB_XOR and _RB_OR don't suggest that the macros have side effects. I suggest either _RB_FLIP/_RB_SET or _RB_XOR_EQ/_RB_OR_EQ. to make the side effects more obvious.

(I wrote this before the 'MOD' parts got added.)

345

I'm not sure that these two macros improve the clarity of the code.

_RB_MOD_XOR(_RB_UP(parent, field), elmdir)

is pretty clear.

[rlibby]

dougm feedback: _UPMOD_ macros don't improve clarity

[rlibby]

sys/sys/tree.h

345

Updated the patch to remove the UPMOD macros. A slight downside is that this spelling is a little longer, which results in several lines now needing to be continued.