Re: [PATCH] Reduce memory size of tsearch red-black tree.

[Mark Wielaard <mark at klomp dot org>]

On Mon, Aug 15, 2016 at 08:34:14PM +0200, Florian Weimer wrote:
> On 08/14/2016 11:15 PM, Mark Wielaard wrote:
> > +#ifdef CAN_USE_MALLOC_LOW_BIT
> > +  static_assert (alignof (max_align_t) > 1, "malloc must return aligned ptrs");
> > +#endif
> 
> You should add a runtime check, too, failing if malloc returns an odd
> pointer.  Not all interposed mallocs provide the fundamental alignment,
> unfortunately.

OK, I'll add a runtime check after the relevant malloc in the code.
Although I assume that if the static build time assert succeeds then
there might be other code (possibly even the compiler) will assume
malloc returned pointers are naturally aligned and might fail in
facinating ways if malloc doesn't obey it's contract.

> I think you can skip the conditional compilation if you include this change.
> glibc malloc will always provide this level of alignment, and the
> compile-time conditional will not help with interposed mallocs anyway.

I would like the keep the conditional (which really is a constant, there
is no real conditionality about it, the assumption is always truea.) Just
like the DEBUGGING code that does a (very slow) sanity check of the
black-red tree after every operation. The alternative code path is much
simpler and can be used to verify the algorithm without having to think
about the low-bit pointer manipulation.

Sorry for the following out of thread reply. I am currently travelling
without access to my normal internet and email setup. I am not subscribed
to the list and gmane seems down. But I saw this reply in the web archive:

Adhemerval Zanella wrote:

> Why not enforce alignment with memalign/posix_memalign/aligned_alloc and
> drop CAN_USE_MALLOC_LOW_BIT?

If we cannot depend on malloc returning naturally aligned memory then
neither can the above functions. That means they will have to allocate
larger blocks and return an aligned address inside the allocated memory
block. That means there is no memory saving at all, and maybe even an
even larger memory use than expected.

I will rename the define to USE_MALLOC_LOW_BIT to make clear it is
always possible to use this code as long as malloc returns naturally
aligned memory blocks.

Cheers,

Mark

Cheers,

Mark