Re: aligned_alloc c11 function

[Niclas Rosenvik <nros%NetBSD.org@localhost>]

On Sun, 1 Nov 2015 11:34:44 -0800
"Terry Moore" <tmm%mcci.com@localhost> wrote:

> > > > (On all real platforms, MIN_ALIGNMENT == sizeof(void *)  
> > >
> > > Only for strange values of "real".  Platforms where sizeof(void
> > > *) is not a power of two predate C (and are part of the reason
> > > why C has that latitude built into it).
> > >
> > > Perhaps all, what was the phrase, "industrially relevant"
> > > platforms....
> > >  
> > Looking at the cpu architectures that NetBSD supports[1] I would I
> > draw the conclusion that on all of them sizeof(void*) is either 4
> > or 8. Or am I wrong? So I think that using Terry's suggestion is
> > fine. If anyone is against this please speak up.  
> 
> Hi Niclas,
> 
> One of the things I really like about the NetBSD lists is that the
> people are extremely serious about portability. I hadn't considered
> that sizeof(void*) might not be power of 2; but Mouse was correct to
> point it out. (And it was amusing to work out the solution using
> NetBSD notation, as it were.)  I actually do know of machines in
> which sizeof(void*) is not a power of two. They are moderately insane
> architectures, but sometimes one has to deal with them.
> 
> There's no runtime efficiency cost for using <sys/bitops.h> and
> computing the appropriate lg2 size ahead of time. We can argue about
> testing it, there's also an argument for explicitly writing out the
> abstract property we need. But the argument about testing is an
> argument *against* portability -- if you try to code for
> universality, including machines that don't exist yet, you can never
> prove that you have it right. But the counter-argument is that if you
> understand what the portability constraints & assumptions are, you
> understand much more about what you're trying to compute, and
> therefore are much less likely to make careless blunders. In my
> experience, the counter-argument is persuasive.
> 
> If nothing else, NetBSD provides worked examples to the rest of the
> world that portability doesn't have to be expensive at run time
> (though it certainly requires a lot more thought while coding).
> 
> In any case: you can just have a trio of #defines:
> 
> #define LOWER_SIZEVOID  (1 << ilog2(sizeof(void *)))
> #define UPPER_SIZEVOID  (LOWER_SIZEVOID << 1)
> #define MIN_ALIGN 	(sizeof(void *) == LOWER_SIZEVOID \
> 					? LOWER_SIZEVOID \
> 					: UPPER_SIZEVOID)
> 
> Then change the while() to "if (alignment < MIN_ALIGN) alignment =
> MIN_ALIGN;" 
> 
> (All the above intended to be adjusted to your preferred style /
> names / line wrapping / etc. Obviously anything in a macro can be
> written out.)
> 
> But you're writing the code, so ultimately you get to decide!
> 
> Best regards,
> --Terry
> 

Then talking about portability here I guess you mean machine
portability? I worry about another portability as well, compiler
portability. My problem with ilog2 in bitops.h is that it uses
__builtin_constant_p which is a GNU extension and thus not compiler
portable. From a performance perspective there is also a problem if
the compiler don't think it's a built in constant it will use fls32
in the if every time aligned_alloc runs. This is a higher
performance penalty than the while loop that Robert suggested.
(also see roberts mail)
There is a predefined macro on most gnu-like compilers
named __SIZEOF_POINTER__ that holds sizeof(void *).
By using this and _ilog2_const from bitops.h everything
can be done in the preprocessor and thereby guarantee that
fls32(fls64) is never used.

#if defined(__SIZEOF_POINTER__)
#include <sys/bitops.h>
#define LOWER_SIZEVOID  (1 << _ilog2_const(__SIZEOF_POINTER__))
#define UPPER_SIZEVOID  (LOWER_SIZEVOID << 1)
#define MIN_ALIGN 	(__SIZEOF_POINTER__ == LOWER_SIZEVOID \
					? LOWER_SIZEVOID \
					: UPPER_SIZEVOID)
#endif

In order for the code to run on compilers that don't define
__SIZEOF_POINTER__ #if will have to be used in the code so it will
be more complicated. Plus I wonder if _ilog2_const is supposed to be
used like this or if it just a helper function to ilog2 whose name 
can change at any time breaking the above code?
The whole code is in ilog2_aligned_alloc.c .

The while loop will at most be run 10 times on a system with a 
1024 bit address bus. This is very little. And it will only happen
if alignment is lower than sizeof(void *) as Robert points out.
The while loop caused one bug that I just found out. 
In the case that alignment and size are both zero the first
if check will be passed and the while loop will be infinite.
That is fixed in versions attached.

Due to the above considerations I think I will commit aligned_alloc.c
with the while (without the preprocessor code).

Regards,
Niclas Rosenvik

/* $NetBSD$ */

/*-
 * Copyright (C) 2015 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Niclas Rosenvik.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice(s), this list of conditions and the following disclaimer as
 *    the first lines of this file unmodified other than the possible
 *    addition of one or more copyright notices.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice(s), this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <errno.h>
#include <stdint.h>
#include <stdlib.h>

#if defined(__SIZEOF_POINTER__)
#include <sys/bitops.h>
#define LOWER_SIZEVOID  (1 << _ilog2_const(__SIZEOF_POINTER__))
#define UPPER_SIZEVOID  (LOWER_SIZEVOID << 1)
#define MIN_ALIGN 	(__SIZEOF_POINTER__ == LOWER_SIZEVOID \
					? LOWER_SIZEVOID \
					: UPPER_SIZEVOID)
#endif


void *
aligned_alloc(size_t alignment, size_t size)
{
        void *memptr;
        int err;
#if defined(__SIZEOF_POINTER__)
        static const minalign = MIN_ALIGN;
#endif

        /*
         * Check that alignment is a power of 2
         * and that size is an integer multiple of alignment.
         */
        if (alignment == 0 ||
	    ((alignment - 1) & alignment) != 0 ||
            (size & (alignment-1)) != 0) {
                errno = EINVAL;
                return NULL;
        }

        /*
         * Adjust alignment to satisfy posix_memalign,
         * larger alignments satisfy smaller alignments.
         */
#if defined(__SIZEOF_POINTER__)
        if (alignment < sizeof(void*))
                alignment = minalign; 
#else
        while (alignment < sizeof(void*))
                alignment <<=1;
#endif
        err = posix_memalign(&memptr, alignment, size);

        if (err) {
                errno = err;
                return NULL;
        }

        return memptr;
}

/* $NetBSD$ */

/*-
 * Copyright (C) 2015 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Niclas Rosenvik.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice(s), this list of conditions and the following disclaimer as
 *    the first lines of this file unmodified other than the possible
 *    addition of one or more copyright notices.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice(s), this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <errno.h>
#include <stdlib.h>

void *
aligned_alloc(size_t alignment, size_t size)
{
        void *memptr;
        int err;
	
        /*
         * Check that alignment is a power of 2
         * and that size is an integer multiple of alignment.
         */
        if (alignment == 0 || ((alignment - 1) & alignment) != 0 ||
            (size & (alignment-1)) != 0) {
                errno = EINVAL;
                return NULL;
        }
	
        /*
         * Adjust alignment to satisfy posix_memalign,
         * larger alignments satisfy smaller alignments.
         */
        while (alignment < sizeof(void *)) {
                alignment <<= 1;
        }
	
        err = posix_memalign(&memptr, alignment, size);
	
        if (err) {
                errno = err;
                return NULL;
        }
	
        return memptr;
}