malloc() and alignment (was Re: AVL tree insertion - programming exercise)

From	cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups	comp.lang.c
Subject	malloc() and alignment (was Re: AVL tree insertion - programming exercise)
Date	2026-10-22 00:43 +0000
Organization	PANIX Public Access Internet and UNIX, NYC
Message-ID	<11bbm71$1tc$1@reader2.panix.com> (permalink)
References	<86ece2kppv.fsf@linuxsc.com> <11al4mu$fqtl$1@kst.eternal-september.org> <11ali2e$pi$1@reader2.panix.com> <20261021162805.270@kylheku.com>

Show all headers | View raw

You're a bit late to the thread here, Kaz.  :-)

In article <20261021162805.270@kylheku.com>,
Kaz Kylheku  <046-301-5902@kylheku.com> wrote:
>On 2026-10-13, Dan Cross <cross@spitfire.i.gajendra.net> wrote:
>> In article <11al4mu$fqtl$1@kst.eternal-september.org>,
>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>>David Brown <david.brown@hesbynett.no> writes:
>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>>> Tim Rentsch wrote:
>>>>>> sons[2] array.  These links are basically pointers, but held
>>>>>> as uintptr_t so they can take one of the bits to mean "tall",
>>>>>> which means taller than the other subtree of the node.  The
>>>>>> tree structure should maintain an invariant that at most one
>>>>> Memory is cheap. 
>>>>
>>>> Not any more!
>>>>
>>>>> Do not encode tags into low bits of an address unless you really
>>>>> know what your doing.
>>>>
>>>> Agreed, as a principle.
>>>>
>>>>> As a precaution check the return address of malloc
>>>>>      p = malloc(m);
>>>>>      if ((uintptr_t)p)&1!=0) abort();
>>>>
>>>> malloc always returns an address with suitable alignment for any
>>>> fundamental alignment on the target.
>>
>> I don't think this is true anymore, as of C23.  Here's the
>> relevant text from n3220, sec 7.24.3, describing the return
>> value from `malloc` et al:
>>
>>|The pointer returned if the allocation succeeds is suitably
>>|aligned so that it may be assigned to a pointer to any type of
>>|object with a fundamental alignment requirement and size less
>>|than or equal to the size requested.
>>
>> This sentence is somewhat ambiguous because it's unclear whether
>> the "less than or equal to the size requested" criteria applies
>> to both the pointer type's size _and_ fundamental alignment
>> requirement, or _just_ the size, but I believe that it is the
>> former (that is, the "and" applies the size requirement to both
>> alignment and returned size).  Thus, a conforming implementation
>> of `malloc(1)` could return a pointer that is `alignof(char)`,
>> but not `alignof(int)`.
>
>Certainly a grammatic parse is possible such that the "less than or
>equal" only applies to the size. But then it is saying "pointer any type
>of object with a fundamental alignment requirement". That doesn't make
>sense. We can regard all objects types as having an alignment
>requirement (which may be relaxed: byte alignment).  The mention of
>alignment in this manner is redundant under this view.  Or we can regard
>those which have stricter than byte alignment as having a fundamental
>alignment requirement. The above parse then doesn't make sense;
>malloced pointers can be assigned to pointer types with byte alignment.

Yes, they can.  You can always take a pointer that is aligned to
a stricter boundary and assign it to some type with a weaker
alignment policy; a pointer that is page aligned is also byte
aligned.

The term, "fundamental alignment requirement" is a term of art
defined in the C standard.  All types have alignment
requirements; an alignment requirement is "fundamental" if it is
less than or equal to `alignof(max_align_t)`; any time with such
an alignment requirement has a fundamental alignment
requirement.

But not all alignment requirements are fundamental.  The
introduction of `alignas(...)` introduced types with alignment
requirements greater than `alignof(max_align_t)`; the standard
introduces another term of art, "extended alignment requirement"
to describe the alignment requirements of that category of
types.

>Either way it doesn't make a difference because ... ta daa ...
>alignment is constrained by size. No type has an alignment requirement
>exceeding its size: size being M, but required to be allocated on
>an address divisible by N, where N > M.
>
>So that is to say, if we state a requirement that the pointer
>successfully returned out of an allocator for a request of size S
>may be used as a pointer to any type whose size is <= S,
>we need no additional wording about alignment! All such types
>have an alignment necessarily <= S.  
>
>Then if we add wording that the pointer may be used to access
>such an object, then that implies the alignment is good also;
>we need not mention alignment.
>
>If a pointer is good for accessing any type of object whose size is <=
>S, then that pointer must be suitably aligned for any such type.

Yes, that describes the behavior of pointers with respect to the
types of things they can point to, but not necessary the
behavior of `malloc` (and calloc and realloc).  In particular,
`malloc` may return a pointer that is _over aligned_ for a given
size.  The language in C17 read to me, and many others, as
though it _required_ that.

However, it did not read that way to all implementers, and not
all implementations did that.  It was therefore unsafe to rely
on that behavior in portable code, even across sytems where
`alignof(max_align_t)` is greater than 1.  Hence, C23 relaxing
the behavior.

>> I argue that examining the text from C17 and how it has changed
>> further supports this interpretation.  From C17, sec 7.22.3:
>>
>>|The pointer returned if the allocation succeeds is suitably
>>|aligned so that it may be assigned to a pointer to any type of
>>|object with a fundamental alignment requirement and then used
>>|to access such an object or an array of such objects in the
>>|space allocated (until the space is explicitly deallocated).
>>
>> Here, no mention of the requested size is made at all, and this
>> clearly requires the return value from a successful allocation
>> by `malloc(1)` to be aligned so that one could assign it to a
>> pointer referring to any object of any type with a "fundamental
>> alignment requirement."
>
>"fundamental alignment requirement" is a normative term;
>it refers to alignment <= _Alignof(max_align_t).
>
>(An alignment that is larger would be something that the program
>declares, not reflecting anything coming form the host machine.)
>
>The requirement is saying that all successful mallocs (including
>zero sized ones, if not returning null?) must be aligned for
>a max_align_t, and may be accessed as such "in the space provided".
>
>So malloc(7) can be converted to a pointer to something that has
>8 byte alignment, but only the first 7 bytes of that can be
>accessed.

I think most readers believe that C17 said that `malloc(7)` must
return addressed aligned to whatever `alignof(max_align_t)` is,
full stop.

C23 relaxes this.  All types have an alignment requirement;
the "weakest" such requirement is whatever `alignof(char)` is;
usually just 1.  The primitive types all have a _fundamental
alignment requirement_; that is, an alignment requirement that
is _fundamental_, which is defined to be <= `align(max_align_t)`
(I suspect this is called "fundamental" because of something
about the basic types being the "fundamental types" or something
like that).

The proposal for change, and the text adopted in C23, is clear
in its intent: it is meant to say that, if a type has a
fundamental alignment requirement and that is <= the size of the
allocation requested in a successful call to `malloc`, then the
address returned from malloc is suitable for assignment to a
pointer to that type.  However, if the alignment of a type is
greater than than the size, but still fundamental, then the
address returned _does not need_ to be suitably aligned for
assignment to a pointer of that type.  (As you correctly point
out, it can't really be used anyway.)

>For instance  struct s { char x[7]; long long y; } could
>be such a type on some platform. If long long has 8 byte alignment,
>the structure type will have that alignment (and padding after x).
>
>The result of malloc(7) may be converted to "struct s *",
>and the pointer can be used to access p->x[0] through p->x[6].
>p->x[7] may be trampling on internal malloc bits.
>
>The allocator could allocate 7 byte (or smaller) objects in 8 byte
>chunks with some flags packed in there.

No, I don't think that's required under the C23 rules.  The
result of `malloc(7)` must be an address aligned to 4, but need
not be aligned to 8 (assuming both are fundamental alignments).

>> Playing games with pointer values can be useful for implementing
>> things like, e.g, Harris's lock-free linked list.
>
>But suppose you need two bits in a pointer, thus four byte alignment. It
>would not make sense to rely on malloc(1) giving you pointers with two
>bits to spare, yet what's what C17 was saying.

I agree!  But people do weird things.

>Of course, you're going to malloc at least four bytes, if you
>want four byte alignment.
>
>The allocator should be allowed to satisfy malloc(1) requests
>out of a byte array (with a separately stored free bitmask
>or radix tree for keeping track of free vs allocated bytes).
>
>It doesn't make sense to require malloc(1) to provide max_align_t
>alignment.

Yes.  The C17 "strong alignment" reading made very little sense
to me.

	- Dan C.

Thread

AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
  Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
      Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
        Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
          Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
      Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
        Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
          Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
              Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
                Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
            Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
              Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
                Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
                Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
                Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
                Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
                Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
                Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 18:26 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-12 21:17 +0200
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
                Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
                Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
  Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
  Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
    Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
    Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
  Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 01:38 -0700
    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 11:42 +0200
      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 10:55 +0000
      Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 04:29 -0700
        Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 14:01 +0200
          Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 05:09 -0700
          Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-13 19:01 +0000
        Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 15:17 +0000
          Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 17:39 +0200
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 09:01 -0700
            Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:17 +0000
              Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 18:01 -0700
              Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 21:13 -0700
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-14 09:43 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 20:11 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:25 -0700
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-15 09:28 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:13 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-14 18:03 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 18:21 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:42 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-15 14:25 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 15:54 -0700
                Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-15 23:51 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 18:14 -0700
                Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-16 20:26 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 15:27 -0700
                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 08:42 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-18 13:11 +0200
                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 15:12 +0000
                Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-18 19:54 +0000
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 03:09 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 21:34 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 11:27 +0000
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 11:27 -0700
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-17 08:21 -0700
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-17 10:48 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-17 18:10 +0000
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-21 02:34 -0700
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 10:39 -0700
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-21 02:41 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-21 11:22 +0000
          Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-13 17:15 +0000
            Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:30 +0000
          Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-21 23:55 +0000
            malloc() and alignment (was Re: AVL tree insertion - programming exercise) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-22 00:43 +0000
      Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 08:19 -0700
      Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-13 13:16 -0700
        Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-13 23:28 +0300
    Re: AVL tree insertion - programming exercise James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-10-13 06:20 -0400
      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 14:34 +0000
        Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 20:45 -0700
          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:25 +0000
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 20:54 -0700
            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 22:47 -0700
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-15 04:42 -0700
              Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-15 14:07 -0700
                Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-17 20:28 -0700
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

csiph-web