Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Back to article view | Back to comp.lang.c

Contents

  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 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-14 10:39 -0700
            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 "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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6  Next page →

#403204

In article <11arlj9$2q39c$1@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>> In article <11ap0fo$1t8gq$2@kst.eternal-september.org>,
>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>> >[snip]
>> Somewhat informally, the C17 wording could be read as requiring
>> that the pointer returned from `malloc` must be suitable for
>> assignment to any pointer to a type with `alignof(max_align_t)`
>> regardless of the requested size, which might be smaller.  N2293
>> calls this the, '"strong-alignment" reading.'
>
>The C17 wording is:
>
>    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).
>
>I don't see any other way to interpret that.

Nor do I, but N2293 says that some implementers did.  Here's how
David Goldblatt explains it:

|The current wording
|
|C17, 7.22.3 states: "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".
|
|The two clauses of interest here are "it may be assigned to a
|pointer to any type of object with a fundamental alignment
|requirement" and "and then used to access such an object or an
|array of such objects in the space allocated". Strong-alignment
|readers tend to see both clauses as independent, whereas
|weak-alignment readers tend to see the second as an adverbial
|clause modifying the first.  Neither reading is completely
|satisfactory.  The strong-alignment view implies an independent
|clause with a tense mismatch or a missing verb; the
|weak-alignment view uses "and then" when "then" would suffice,
|which could imply a sequencing at odds with the interpretation.

I don't see it, myself, and I'm a "strong-alignment reader", but
he goes on:

|In the author's view, attempting to declare one of these two
|parsings correct is a waste of time.  Many different
|implementers, fluent in English and acting in good faith, have
|parsed the sentence both ways.  The question is how to
|reconcile the divergence.

Indeed.

>It requires that
>a pointer returned by a successful malloc() must *always* be
>suitably aligned.  A pointer returned by malloc(1) must be aligned
>so that it can point to a long long, for example.
>
>It overlooks the fact that it can't point to a long long, because
>there isn't room for it.  And there's no portable way to tell if an
>implementation violates this requirement.  If an implementation's
>malloc(1) returns an "odd" pointer, it violates the standard's
>requirement, but that violation likely has no real effect.

Agreed.

>For C23, it was recognized that requiring strict alignment for
>tiny allocations is neither useful nor necessarily meaningful.
>malloc(1) might as well be allowed to return an "odd" pointer.

Yes.

>>>[snip]
>>>If you allow an object type to have an alignment greater than its
>>>size, then the ambiguity can result in an actual difference in the
>>>requirements.  But then arrays don't work.
>>
>> That's ok; this is only about the properties vis alignment of
>> the pointer returned from malloc.  Consider x86_64 with the
>> System V ABI again or ARM64 with the AAPCS; suppose that
>> `char *p = malloc(char[3]);` assigns a non-NULL ponter to `p`.
>
>Alas, that's a syntax error.  The argument to malloc is an expression,
>not a type.  (I'm certain you knew that.)

Indeed; I meant to write, `malloc(sizeof(char[3]))` but as you
correctly surmised, I mistyped.

>You can write
>`malloc(sizeof (char[3])`, but that's just malloc(3); no type
>information is passed.
>
>And the alignment of char[3] is 1.  An array of two char[3] objects has
>a size of 6; there are no alignment gaps between the elements.

Right.  The only reason I wanted to write it that way was to
drive that point home; in the "strong-alignment" reading, for
small allocations, the alignment of the address the pointer
returned from `malloc` refers to is totally decoupled from the
requested size: `sizeof(char[3])` is three, which reflects the
fundamental alignment requirement of `char[3]` being 1; because
`malloc` doesn't know whether the resulting allocation will be
used to store something with a fundamental alignment criteria of
two or not (assuming such a type exists in the implementation),
it must return a pointer to an address that is at least aligned
to an even boundary.  In any event, whether `malloc` must return
something with stronger alignment, or merely can at its own
convenience, is the interesting high order bit here.

But, you know, I can't type so flubbed the example. :-D

>> The question is only whether or not the address `p` refers to is
>> required to be aligned on a 16-byte boundary; under the
>> '"strong-alignment" reading' in N2293, it is, even though the
>> allocated size is only 3.  Under the '"weak-alignment" reading',
>> the return address can aligned on an even boundary, and C23
>> codified the weak-alignment reading.  Note that neither reading
>> says anything  about the size of elements or their alignment in
>> an allocation that is treated like an array; it only affects
>> the alignment of the starting address.
>
>Under C17, the result of malloc(3) must be strongly aligned (8
>bytes, for example).  Under C23, it has to be at least 2 if there
>are any types with 2-byte alignment.

Yes, that's my interpretation.

>> N2293 mentions this, but it probably bears repeating here: the
>> utility of forcing `malloc` to align small allocations to e.g.,
>> `alignof(max_align_t)` seems mostly restricted to having some
>> hope of overloading the low bits of the returned address for
>> some program-specific purpose, which is how this came up in the
>> first place in this thread.
>
>It hadn't occurred to me that that might be the reason.  I assumed
>it was just because strong alignment for small allocations is not
>useful and should not be required.  Allocating single bytes for
>malloc(1) calls could have real advantages for some programs, and
>the standard shouldn't prohibit that.

N2293 says that existing implementations differed; Goldblatt
gives a fairly concise list of major implementations and which
does what.

David Goldblatt is one of the maintainers of `jemalloc`, and
probably cares about the space efficiency of small allocations;
I suspect that motivated researching the differing
interpretations and became the real motivation.

It came up in this thread specifically because of discussions
around stealing the low bits from the integer representation of
a pointer.

>As I recall, there was a discussion about reusing low-order bits of
>pointers, and the fact that malloc(1) no longer has to be strongly
>aligned became relevant to that.  It doesn't imply that that was
>the reason.

See above.  I suspect Goldblatt wanted to reconcile the
different interpretations so that the `jemalloc` behavior could
be considering conformant with the standard.

>There might be an ambiguity in the English grammar of the C23
>statement about the alignment of malloc()ed pointers, but I don't
>*think* we've seen a case where the two (or more?) different
>interpretations actually lead to different semantics.

I suppose it depends on which semantics you mean.  There are
definitely implementations that the "weak-alignment" reading
and others that take the "strong-alignment" reading.  **On those
latter implementations**, assuming `malloc` of some small size
is successful, you can almost certainly cast the resulting
pointer to `uintptr_t` and use the low bits of the result for
stuff, whereas on the former implementations, you can't, unless
you know that the fundamental alignment requirement for the
size you request is sufficiently large so that the low bits will
be clear; for `malloc(1)` it basically won't be.

>>                              As has already been mentioned, the
>> standard makes no guarnatee about the integer representation of
>> addresses, so this is already somewhat fraught, but on many
>> platforms we may assume that as a practical matter, for a
>> pointer to a suitably aligned address, those bits will be clear
>> as a practical matter; I suppose if one wants that for a small
>> allocation, use `aligned_alloc`.  Caveat emptor.
>
>Yes, if you need aligned pointers, aligned_alloc() is the way to
>get them.  aligned_alloc(8, 1) gives you an 8-byte aligned pointer
>to a 1-byte object; if that's useful, it's because you're doing
>something weird.  And if you need to fiddle with the low-order
>bits of aligned pointers, you could run into the problems we've
>already discussed.

Yup.  Agreed on all counts.  There _are_ some valid uses for
stealing low bits, but they're pretty esoteric; for instance,
this: https://dl.acm.org/doi/10.1145/3731569.3764807

But if someone is dabbling in those dark magicks, they'd better
know just exactly what they're doing.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403205

cross@spitfire.i.gajendra.net (Dan Cross) writes:
[Snip stuff I agree with]

> Right.  The only reason I wanted to write it that way was to
> drive that point home; in the "strong-alignment" reading, for
> small allocations, the alignment of the address the pointer
> returned from `malloc` refers to is totally decoupled from the
> requested size: `sizeof(char[3])` is three, which reflects the
> fundamental alignment requirement of `char[3]` being 1; because
> `malloc` doesn't know whether the resulting allocation will be
> used to store something with a fundamental alignment criteria of
> two or not (assuming such a type exists in the implementation),
> it must return a pointer to an address that is at least aligned
> to an even boundary.  In any event, whether `malloc` must return
> something with stronger alignment, or merely can at its own
> convenience, is the interesting high order bit here.

Just to avoid any misunderstanding, you refer to "the fundamental
alignment requirement of `char[3]` being 1".

The phrase "fundamental alignment requirement" might be misleading.
It could imply to someone unfamiliar with the terminology that
char[3] could have a fundamental alignment requirement and a
differing non-fundamental alignment requirement.  (I had thought
the term "fundamental alignment" was new in C23, but it was added
in C11.)

It's possible that I'm the only one who thought this might be
confusing.  If so, ignore this.

To over-explain: Each object type has an alignment, which is an integer
value.

    A *fundamental alignment* is a valid alignment less than or equal to
    alignof(max_align_t).

    An *extended alignment* is represented by an alignment greater than
    alignof(max_align_t).

As far as the language is concerned `char[3]` has an alignment of
1, and that alignment happens to be a fundamental alignment.  (A
compiler might allocate standalone `char[3]` objects at a stricter
alignment, but the standard doesn't address that; compilers can
over-align anything they like.)

Which might be part of the confusion about the malloc() wording in C23.

    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.

I read the phrase "with a fundamental alignment requirement" as a
predicate.  A type has a fundamental alignment requirement or it
doesn't.

The alternative reading is "with a fundamental alignment requirement
(and size) less than or equal to the size requested", which says that
the alignment requirement (a) is fundamental *and* (b) is less than or
equal to the size requested.  I think that's a rather strained
interpretation -- and I can't think of any cases where the distinction
between the two readings of the C23 wording could be significant, given
that an object type can't have an alignment bigger than its size.

[Snip more stuff I agree with]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403211

In article <11as9gl$2vtou$1@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>[Snip stuff I agree with]
>
>> Right.  The only reason I wanted to write it that way was to
>> drive that point home; in the "strong-alignment" reading, for
>> small allocations, the alignment of the address the pointer
>> returned from `malloc` refers to is totally decoupled from the
>> requested size: `sizeof(char[3])` is three, which reflects the
>> fundamental alignment requirement of `char[3]` being 1; because
>> `malloc` doesn't know whether the resulting allocation will be
>> used to store something with a fundamental alignment criteria of
>> two or not (assuming such a type exists in the implementation),
>> it must return a pointer to an address that is at least aligned
>> to an even boundary.  In any event, whether `malloc` must return
>> something with stronger alignment, or merely can at its own
>> convenience, is the interesting high order bit here.
>
>Just to avoid any misunderstanding, you refer to "the fundamental
>alignment requirement of `char[3]` being 1".

What I'm trying to say (that I think you said better), is that
the alignment requirement of `char` is fundamental, and that the
aggregate type (the array, `char[3]`) has the same alignment
requirement.  In this case, the that is `1`.

>The phrase "fundamental alignment requirement" might be misleading.
>It could imply to someone unfamiliar with the terminology that
>char[3] could have a fundamental alignment requirement and a
>differing non-fundamental alignment requirement.  (I had thought
>the term "fundamental alignment" was new in C23, but it was added
>in C11.)
>
>It's possible that I'm the only one who thought this might be
>confusing.  If so, ignore this.

Hmm, I don't know that anyone else thought that, but I cannot
say that they did not, and it was useful to make the point.

>To over-explain: Each object type has an alignment, which is an integer
>value.
>
>    A *fundamental alignment* is a valid alignment less than or equal to
>    alignof(max_align_t).
>
>    An *extended alignment* is represented by an alignment greater than
>    alignof(max_align_t).
>
>As far as the language is concerned `char[3]` has an alignment of
>1, and that alignment happens to be a fundamental alignment.  (A
>compiler might allocate standalone `char[3]` objects at a stricter
>alignment, but the standard doesn't address that; compilers can
>over-align anything they like.)

Yes, and succinctly put.

A couple of minor quibbles: it bears mentioning that valid
alignments are positive powers of two.  Also, a point you had
aluded to earlier: for e.g., `malloc(sizeof(char[3]))`, by the
time the size argument gets to `malloc` the type information
(including the alignment requirement) has been lost; malloc just
sees `3`.  For an implementation where there exists types with
an alignment requirement of two and `sizeof(max_align_t)>=2`,
such an alignment requirement is also fundamental.  `malloc`
cannot know that its return value won't be used to hold an
object of such type, so it must return a pointer to an address
that is aligned on an even boundary.

>Which might be part of the confusion about the malloc() wording in C23.
>
>    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.
>
>I read the phrase "with a fundamental alignment requirement" as a
>predicate.  A type has a fundamental alignment requirement or it
>doesn't.
>
>The alternative reading is "with a fundamental alignment requirement
>(and size) less than or equal to the size requested", which says that
>the alignment requirement (a) is fundamental *and* (b) is less than or
>equal to the size requested.  I think that's a rather strained
>interpretation -- and I can't think of any cases where the distinction
>between the two readings of the C23 wording could be significant, given
>that an object type can't have an alignment bigger than its size.

Yes, and I do see what you mean: it's a distinction without a
difference due to other constraints imposed on types generally.

Specifically (and speaking somewhat loosely), if a type has an
alignment requirement that is fundamental, then it is <= the
type's size; no such type may have alignment>size.  Therefore,
whether or not the "size" condition is to applied to the
"fundamental alignment requirement" phrase in the C23 sentence,
the result is the same.

This is in contrast to the C17 phrasing, which was read by many
good judges as requiring alignment to `>=alignof(max_align_t)`
regardless of size.

>[Snip more stuff I agree with]

I think we're all agreed about the following: a conforming
implementation may choose for a successful call to `malloc` et
al to always return an "over-aligned" pointer to an address
aligned to a boundary that is >= `alignof(max_align_t)`, but
is not required to do so.

If you want to steal the low bits of an address for something,
be careful: there be dragons.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403216

cross@spitfire.i.gajendra.net (Dan Cross) writes:
[...]
> A couple of minor quibbles: it bears mentioning that valid
> alignments are positive powers of two.

And that wasn't explicitly stated until C11.  C99 talks about
alignment, but is a bit vagee about it.  A hypothetical conforming
C99 implementation might have had addresses organized in powers of
3, for example.  I doubt that any such implementation ever existed.

Even in C23, the definition of "alignment" is vague:

    alignment

    requirement that objects of a particular type be located on
    storage boundaries with addresses that are particular multiples
    of a byte (3.7) address

The meaning is obvious given a typical memory model, but I don't
know how you'd define "multiples of a byte address" in standardese.
I'm not even sure it's correctly stated.

In practice, I don't think this vagueness has been a problem;
everybody knows what it's *supposed* to mean.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403237

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <11ap0fo$1t8gq$2@kst.eternal-september.org>,
>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>
>>>> In article <11amvh2$14pou$3@kst.eternal-september.org>,
>>>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>>>
>>>>> [snip]
>>>>> So "a fundamental alignment requirement" and "size less than or
>>>>> equal to the size requested" are parallel requirements, both
>>>>> applying to the type of the pointed-to object.
>>>>
>>>> That is one of the two reasonable interpretations.  The other is
>>>> that the requirements placed on size and fundamental alignment
>>>> of the pointer type are cumulative and dependent on the size of
>>>> the allocation.  If so, then nothing in the C standard prevents
>>>> an implementation from from returning a pointer aligned to
>>>> `alignof(char)` for `malloc(1)`.
>>>
>>> I do see the parsing ambiguity now.
>>>
>>> I believe that's consistent with the way I parsed it.  A successful
>>> malloc(1) returns a value that can be assigned to a pointer of type
>>> char*, which points to the object type "char", which does have (a
>>> fundamental alignment requirement) and (a size less than or equal
>>> to the size requested).
>>
>> Right, but I think it's a bit deeper than that.
>>
>> Somewhat informally, the C17 wording could be read as requiring
>> that the pointer returned from `malloc` must be suitable for
>> assignment to any pointer to a type with `alignof(max_align_t)`
>> regardless of the requested size, which might be smaller.  N2293
>> calls this the, '"strong-alignment" reading.'
>
> The C17 wording is:
>
>     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).
>
> I don't see any other way to interpret that.  It requires that
> a pointer returned by a successful malloc() must *always* be
> suitably aligned.  A pointer returned by malloc(1) must be aligned
> so that it can point to a long long, for example.
>
> It overlooks the fact that it can't point to a long long, because
> there isn't room for it.  [...]

Let's see if we can get this discussion back on the rails.

Put yourself back in 1999.  Forget about anything from 2000 onwards.
There is just one relevant sentence in the C99 standard:

   The pointer returned if the allocation succeeds is suitably
   aligned so that it may be assigned to a pointer to any type of
   object and then used to access such an object in the space
   allocated (until the space is explicitly deallocated).

The original C standard says the same thing except it says "... is
explicitly freed or reallocated" rather than deallocated.

The intended meaning here is straightforward.  A pointer returned from
malloc() may be assigned to any pointer no matter what type it points
to.  Non-null pointers may be used to access a suitably sized array.
If the size requested is smaller than the pointed-to type, using the
pointer follows the rule for zero-length flexible array members:  it
acts like an array of size 1 except that trying to access the element
or advance to the next element is undefined behavior.  In other words
it's okay to use the pointer as a pointer but it can't be incremented
or dereferenced.

Now go forward to 2011.  We want the same behavior for malloc() as in
C99, only now we have to consider types with overly large alignments.
For obvious reasons we don't want to force malloc() to make worst-case
assumptions about what the alignment needs will be.  A new function
aligned_alloc() is added, with an extra parameter to specify what
alignment is needed, to take care of types with overly large alignment
needs.  The general rule for what pointer types are covered is changed
to admit the same kinds as when there were no overly large alignments;
that change is put in place by adding the clause "with a fundamental
alignment requirement" to the general description of memory management
functions.  The description of aligned_alloc() says specifically that
it allocates an object having the given alignment value (and so the
returned pointer value presumably may be used as such).  What happens
with requests whose size is smaller than what the assigned-to pointer
type implies is the same as before, following the FAM rule;  that rule
applies to aligned_alloc() the same as is does for malloc().

Note by the way that aligned_alloc() may be used to ask for a space
whose alignment is smaller than normal as well as any overly large
alignment.  So malloc() should be used for generic alignments, and
aligned_alloc() should be used any too-small or too-large alignment.

I don't have a copy of the C17 standard handy, but I expect it says
the same thing about malloc() and friends as the C11 standard does.

Regarding the discussion in N2293, I'm sorry to say that either the
author is not too bright or he just didn't have his Wheaties that
morning.  He reads the words but he doesn't understand the meaning.  
A fair guess is that he made two common mistakes:  one, he didn't
consider the historical context, and two, he looked at passages in
isolation without taking into account a broader context.  The Standard
is not meant to be read like a legal document.  All the parts are
expected to fit together, and in deciding what a particular passage
means one needs to consider other surrounding and related passages and
how they might interact.  As for the arguments about how various
implementations behave, the reasoning is backwards.  It's the tail
wagging the dog.  We don't judge what the C standard means based on
what implementations do;  rather we decide what the C standard is
meant to say and then assess whether a proposed implementation is
conforming.  The possibility of potential performance benefits does
not excuse changing the behavior required under previous C standards.
If someone thinks that's important they should use aligned_alloc();
otherwise they should just use malloc() and know that it will behave
the way it always has.

Bottom line:  the discussion in N2293 is misguided.  A technical
corrigendum should be issued, putting back the language used in C11
and C17, and adding a footnote explaining that aligned_alloc() can be
used for any allocation whose alignment is other than the default
alignment provided by malloc().

[toc] | [prev] | [next] | [standalone]

#403243

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>> In article <11ap0fo$1t8gq$2@kst.eternal-september.org>,
>>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>>> In article <11amvh2$14pou$3@kst.eternal-september.org>,
>>>>> Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>>>>
>>>>>> [snip]
>>>>>> So "a fundamental alignment requirement" and "size less than or
>>>>>> equal to the size requested" are parallel requirements, both
>>>>>> applying to the type of the pointed-to object.
>>>>>
>>>>> That is one of the two reasonable interpretations.  The other is
>>>>> that the requirements placed on size and fundamental alignment
>>>>> of the pointer type are cumulative and dependent on the size of
>>>>> the allocation.  If so, then nothing in the C standard prevents
>>>>> an implementation from from returning a pointer aligned to
>>>>> `alignof(char)` for `malloc(1)`.
>>>>
>>>> I do see the parsing ambiguity now.
>>>>
>>>> I believe that's consistent with the way I parsed it.  A successful
>>>> malloc(1) returns a value that can be assigned to a pointer of type
>>>> char*, which points to the object type "char", which does have (a
>>>> fundamental alignment requirement) and (a size less than or equal
>>>> to the size requested).
>>>
>>> Right, but I think it's a bit deeper than that.
>>>
>>> Somewhat informally, the C17 wording could be read as requiring
>>> that the pointer returned from `malloc` must be suitable for
>>> assignment to any pointer to a type with `alignof(max_align_t)`
>>> regardless of the requested size, which might be smaller.  N2293
>>> calls this the, '"strong-alignment" reading.'
>>
>> The C17 wording is:
>>
>>     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).
>>
>> I don't see any other way to interpret that.  It requires that
>> a pointer returned by a successful malloc() must *always* be
>> suitably aligned.  A pointer returned by malloc(1) must be aligned
>> so that it can point to a long long, for example.
>>
>> It overlooks the fact that it can't point to a long long, because
>> there isn't room for it.  [...]
>
> Let's see if we can get this discussion back on the rails.
>
> Put yourself back in 1999.  Forget about anything from 2000 onwards.
> There is just one relevant sentence in the C99 standard:
>
>    The pointer returned if the allocation succeeds is suitably
>    aligned so that it may be assigned to a pointer to any type of
>    object and then used to access such an object in the space
>    allocated (until the space is explicitly deallocated).
>
> The original C standard says the same thing except it says "... is
> explicitly freed or reallocated" rather than deallocated.

Yes.  That wording is flawed.  It implies that the pointer returned
by a successful malloc(1) may be "used to access" a long double
object in the space allocated.

If we set aside the "used to access" clause, it's still clear that the
returned pointer is suitably aligned for any object.  So malloc(1) must
return, for example, a 16-byte aligned pointer, even though no 16-byte
object can be stored in the allocated space.

> The intended meaning here is straightforward.  A pointer returned from
> malloc() may be assigned to any pointer no matter what type it points
> to.  Non-null pointers may be used to access a suitably sized array.
> If the size requested is smaller than the pointed-to type, using the
> pointer follows the rule for zero-length flexible array members:  it
> acts like an array of size 1 except that trying to access the element
> or advance to the next element is undefined behavior.  In other words
> it's okay to use the pointer as a pointer but it can't be incremented
> or dereferenced.

I agree that the intended meaning is straightforward, but the
words do not correctly express that intent.  To understand the
intent, you have to set aside the incorrect assertion that a pointer
returned by malloc() can be used to access an object bigger than
the requested allocation.

On the other hand, here's the C17 wording:

    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).

I suppose that could be read so it applies only if such an object *can*
exist in the space allocated.  But I still find it ambiguous at best.

> Now go forward to 2011.  We want the same behavior for malloc() as in
> C99, only now we have to consider types with overly large alignments.
> For obvious reasons we don't want to force malloc() to make worst-case
> assumptions about what the alignment needs will be.  A new function
> aligned_alloc() is added, with an extra parameter to specify what
> alignment is needed, to take care of types with overly large alignment
> needs.  The general rule for what pointer types are covered is changed
> to admit the same kinds as when there were no overly large alignments;
> that change is put in place by adding the clause "with a fundamental
> alignment requirement" to the general description of memory management
> functions.  The description of aligned_alloc() says specifically that
> it allocates an object having the given alignment value (and so the
> returned pointer value presumably may be used as such).  What happens
> with requests whose size is smaller than what the assigned-to pointer
> type implies is the same as before, following the FAM rule;  that rule
> applies to aligned_alloc() the same as is does for malloc().

"FAM"?

> Note by the way that aligned_alloc() may be used to ask for a space
> whose alignment is smaller than normal as well as any overly large
> alignment.  So malloc() should be used for generic alignments, and
> aligned_alloc() should be used any too-small or too-large alignment.

Suppose alignof (max_align_t) == 16.  aligned_malloc(1, 1024) must still
return a 16-byte aligned pointer.  This is stated explicitly in a
footnote in C23 (N3220).

> I don't have a copy of the C17 standard handy, but I expect it says
> the same thing about malloc() and friends as the C11 standard does.
>
> Regarding the discussion in N2293, I'm sorry to say that either the
> author is not too bright or he just didn't have his Wheaties that
> morning.  He reads the words but he doesn't understand the meaning.  

He reads the words and recognizes the flaw.

I personally don't think the "weak-alignment" reading described in
N2293 is valid, but if some implementers have actually interpreted
it that way, it's worth fixing the wording to clear it up.

> A fair guess is that he made two common mistakes:  one, he didn't
> consider the historical context, and two, he looked at passages in
> isolation without taking into account a broader context.  The Standard
> is not meant to be read like a legal document.  All the parts are
> expected to fit together, and in deciding what a particular passage
> means one needs to consider other surrounding and related passages and
> how they might interact.

If some wording in the standard requires historical context to
understand it, that wording is flawed.

>                           As for the arguments about how various
> implementations behave, the reasoning is backwards.  It's the tail
> wagging the dog.  We don't judge what the C standard means based on
> what implementations do;  rather we decide what the C standard is
> meant to say and then assess whether a proposed implementation is
> conforming.  The possibility of potential performance benefits does
> not excuse changing the behavior required under previous C standards.
> If someone thinks that's important they should use aligned_alloc();
> otherwise they should just use malloc() and know that it will behave
> the way it always has.
>
> Bottom line:  the discussion in N2293 is misguided.  A technical
> corrigendum should be issued, putting back the language used in C11
> and C17, and adding a footnote explaining that aligned_alloc() can be
> used for any allocation whose alignment is other than the default
> alignment provided by malloc().

I don't want to restore the flawed wording from C17 and earlier.

Are you saying that malloc(1) *should* be required to return a fully
aligned pointer?  Since C17 and earlier did require that, perhaps there
should have been more discussion about relaxing it by allowing malloc(1)
to return an "odd" pointer.  I don't think that was a bad change, but
it could in principle break some existing code.

I see two separate issues.

1. The wording in C17 and earlier can be read to require the ability to
   access a large object in a small allocated space.  That's a wording
   issue.

2. C17 and earlier require small allocations to be strongly aligned.
   C23 drops that requirement.

If there's a good reason to continue to require the result of
malloc(1) to be strongly aligned, I wouldn't object to it - but
C23 already dropped that requirement, so imposing it again in C2y
could be problematic.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403247

In article <86h5ikpd2n.fsf@linuxsc.com>,
Tim Rentsch  <tr.17687@z991.linuxsc.com> wrote:
>[snip]
>Regarding the discussion in N2293, I'm sorry to say that either the
>author is not too bright or he just didn't have his Wheaties that
>morning.  He reads the words but he doesn't understand the meaning.  
>A fair guess is that he made two common mistakes:  one, he didn't
>consider the historical context, and two, he looked at passages in
>isolation without taking into account a broader context.  The Standard
>is not meant to be read like a legal document.  All the parts are
>expected to fit together, and in deciding what a particular passage
>means one needs to consider other surrounding and related passages and
>how they might interact.  As for the arguments about how various
>implementations behave, the reasoning is backwards.  It's the tail
>wagging the dog.  We don't judge what the C standard means based on
>what implementations do;  rather we decide what the C standard is
>meant to say and then assess whether a proposed implementation is
>conforming.  The possibility of potential performance benefits does
>not excuse changing the behavior required under previous C standards.
>If someone thinks that's important they should use aligned_alloc();
>otherwise they should just use malloc() and know that it will behave
>the way it always has.

Did you actually _read_ N2293?

>Bottom line:  the discussion in N2293 is misguided.  A technical
>corrigendum should be issued, putting back the language used in C11
>and C17, and adding a footnote explaining that aligned_alloc() can be
>used for any allocation whose alignment is other than the default
>alignment provided by malloc().

No.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403158

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <86v775h9o2.fsf@linuxsc.com>,
>> Tim Rentsch  <tr.17687@z991.linuxsc.com> wrote:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
> [...]
>
>>>> 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, [...]
>>>
>>> It's poorly constructed but in English it has only one
>>> grammatical parse.
>>
>> Nope.  Not even close.
>
> I think Tim is right about there being only one grammatical parse.
> [...]

Thanks Keith!  I owe you one. :)

[toc] | [prev] | [next] | [standalone]

#403114

cross@spitfire.i.gajendra.net (Dan Cross) writes:
>In article <11al4mu$fqtl$1@kst.eternal-september.org>,
>Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:

>
>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."

Note that the processor ABI documents for x86_64 and
arm64 also require the return value always be aligned
congruent to zero module 16.

[toc] | [prev] | [next] | [standalone]

#403127

In article <fHtzS.249963$iAH2.193623@fx14.iad>,
Scott Lurndal <slp53@pacbell.net> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>In article <11al4mu$fqtl$1@kst.eternal-september.org>,
>>Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>>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."
>
>Note that the processor ABI documents for x86_64 and
>arm64 also require the return value always be aligned
>congruent to zero module 16.

Is that true?  Looking at the psABI for x86_64, I don't see that
mentioned anywhere; it does say that `_Alignof(max_align_t)` is
16, but it doesn't mention `malloc` at all.  POSIX is closer,
and uses language close to that in C17.  Arm64 refers to the
AAPCS64, which doesn't go into the return type of `malloc`,
either.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403107

David Brown wrote:
> 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!

I started on 65K.
>
>> 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.  Typically that means at least
> 64-bit alignment (and thus the three LSB's are always zero), but it is
> implementation dependent.
>


-- 
Siri Seal of Disavowal #777-000. Disavowed. Denied.  @
NO KINGS    For I desire mercy not sacrifice.       /|\
The Church of the Holey Apple .signature 5.5        / \
of Discordian Mysteries. This post insults Islam. Mohamed

[toc] | [prev] | [next] | [standalone]

#403121

On 10/13/2026 2:42 AM, David Brown wrote:
> 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.  Typically that means at least 64- 
> bit alignment (and thus the three LSB's are always zero), but it is 
> implementation dependent.
> 

Right, and sometimes that can be wasteful on certain memory constrained 
environments. Fwiw, I wrote a region allocator a while back that tends 
to pack thing on their alignment, but never needs a max a alignment for 
all.

Oh shit! I cannot get into google groups, I get a god damn: 429 Too Many 
Requests

Well, here is a mutated version of it that uses C++. I had the C only 
version in some of my saved google groups links. Sigh. Anyway:


My code:
____________________________________________



#if ! defined (RALLOC_H)
#  define RALLOC_H
#  if defined (__cplusplus)
extern "C" {
#  endif
     /**************************************************************/




#include <cstddef>
#include <cassert>




#if defined (_MSC_VER)
/* warning C4116: unnamed type definition in parentheses */
#  pragma warning (disable : 4116)
#endif




#if ! defined (NDEBUG)
#  include <cstdio>
#  define RALLOC_DBG_PRINTF(mp_exp) std::printf mp_exp
#else
#  define RALLOC_DBG_PRINTF(mp_exp) ((void)0)
#endif




#if ! defined (RALLOC_UINTPTR_TYPE)
#  define RALLOC_UINTPTR_TYPE size_t
#endif




     typedef RALLOC_UINTPTR_TYPE ralloc_uintptr_type;


     typedef char ralloc_static_assert[
         sizeof(ralloc_uintptr_type) == sizeof(void*) ? 1 : -1
     ];


#define RALLOC_ALIGN_OF(mp_type) alignof(mp_type)
#define RALLOC_ALIGN_MAX alignof(std::max_align_t)


#define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
   ((void*)( \
     (((ralloc_uintptr_type)(mp_ptr)) + ((mp_align) - 1)) \
     & ~(((mp_align) - 1)) \
   ))


#define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) \
   (((void*)(mp_ptr)) == RALLOC_ALIGN_UP(mp_ptr, mp_align))




     struct region {
         unsigned char* buffer;
         size_t size;
         size_t offset;
     };


     static void
     rinit(
         struct region* const self,
         void* buffer,
         size_t size
     ) {
         self->buffer = (unsigned char*)buffer;
         self->size = size;
         self->offset = 0;

         RALLOC_DBG_PRINTF((
             "rinit(%p) {\n"
             "  buffer          = %p\n"
             "  size            = %lu\n"
             "}\n\n\n",
             (void*)self,
             buffer,
             (unsigned long int)size
             ));
     }


     static void*
     rallocex(
         struct region* const self,
         size_t size,
         size_t align
     ) {
         unsigned char* align_buffer;
         size_t offset = self->offset;
         unsigned char* raw_buffer = self->buffer + offset;

         if (! size) {
             size = 1;
         }

         if (! align) {
             align = RALLOC_ALIGN_MAX;
         }

         assert(align == 1 || RALLOC_ALIGN_ASSERT(align, 2));

         align_buffer = (unsigned char*)RALLOC_ALIGN_UP(raw_buffer, align);

         assert(RALLOC_ALIGN_ASSERT(align_buffer, align));

         size += align_buffer - raw_buffer;

         if (offset + size > self->size) {
             return NULL;
         }

         self->offset = offset + size;

         RALLOC_DBG_PRINTF((
             "rallocex(%p) {\n"
             "  size            = %llu\n"
             "  alignment       = %llu\n"
             "  origin offset   = %llu\n"
             "  final offset    = %llu\n"
             "  raw_buffer      = %p\n"
             "  align_buffer    = %p\n"
             "  size adjustment = %llu\n"
             "  final size      = %llu\n"
             "}\n\n\n",
             (void*)self,
             (unsigned long long int)size - (align_buffer - raw_buffer),
             (unsigned long long int)align,
             (unsigned long long int)offset,
             (unsigned long long int)self->offset,
             (void*)raw_buffer,
             (void*)align_buffer,
             (unsigned long long int)(align_buffer - raw_buffer),
             (unsigned long long int)size
             ));

         return align_buffer;
     }


#define ralloc(mp_self, mp_size) \
   rallocex((mp_self), (mp_size), RALLOC_ALIGN_MAX)

#define ralloct(mp_self, mp_count, mp_type) \
   rallocex( \
     (mp_self), \
     sizeof(mp_type) * (mp_count),\
     RALLOC_ALIGN_OF(mp_type) \
   )


     static void
     rflush(
         struct region* const self
     ) {
         self->offset = 0;

         RALLOC_DBG_PRINTF((
             "rflush(%p) {}\n\n\n",
             (void*)self
             ));
     }




#undef RALLOC_DBG_PRINTF
#undef RALLOC_UINTPTR_TYPE




     /**************************************************************/
#  if defined (__cplusplus)
}
#  endif
#endif

[toc] | [prev] | [next] | [standalone]

#403122

On Tue, 13 Oct 2026 13:16:44 -0700
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote:
> 
> Oh shit! I cannot get into google groups, I get a god damn: 429 Too
> Many Requests

You can get into google groups but you would have to do it manually,
step by step starting from top
https://groups.google.com

Shortcuts, even the simplest ones like
https://groups.google.com/g/comp.lang.c 
nowadays work very rarely.

So it goes.

[toc] | [prev] | [next] | [standalone]

#403089

On 13/10/2026 10:38, chine.bleu wrote:
...> As a precaution check the return
> address of malloc
> 
>      p = malloc(m);
>      if ((uintptr_t)p)&1!=0) abort();
Just to be pedantic, the standard doesn't guarantee that the expression
you use will test what you want to test. Since there is a guarantee that
malloc() returns a universally aligned memory, I think it's actually
more likely that the test will fail than that malloc() will fail, though
both probabilities are quite negligible, so it's hard to be sure.

[toc] | [prev] | [next] | [standalone]

#403103

In article <11al0l0$eefv$1@dont-email.me>,
James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>On 13/10/2026 10:38, chine.bleu wrote:
>...> As a precaution check the return
>> address of malloc
>> 
>>      p = malloc(m);
>>      if ((uintptr_t)p)&1!=0) abort();
>
>Just to be pedantic, the standard doesn't guarantee that the expression
>you use will test what you want to test. Since there is a guarantee that
>malloc() returns a universally aligned memory, I think it's actually
>more likely that the test will fail than that malloc() will fail, though
>both probabilities are quite negligible, so it's hard to be sure.

The syntax and precedence errors aside, the test is clearly
meant to ensure that the low bit in the return from `malloc` is
clear, so that it can be repurposed for other things.  It should
likely be:

	p = malloc(m);
	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403140

cross@spitfire.i.gajendra.net (Dan Cross) writes:
> In article <11al0l0$eefv$1@dont-email.me>,
> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>On 13/10/2026 10:38, chine.bleu wrote:
>>...> As a precaution check the return
>>> address of malloc
>>> 
>>>  p = malloc(m);
>>>  if ((uintptr_t)p)&1!=0) abort();
>>
>>Just to be pedantic, the standard doesn't guarantee that the expression
>>you use will test what you want to test. Since there is a guarantee that
>>malloc() returns a universally aligned memory, I think it's actually
>>more likely that the test will fail than that malloc() will fail, though
>>both probabilities are quite negligible, so it's hard to be sure.
>
> The syntax and precedence errors aside, the test is clearly
> meant to ensure that the low bit in the return from `malloc` is
> clear, so that it can be repurposed for other things.  It should
> likely be:
>
> 	p = malloc(m);
> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();

I'm not sure the NULL test adds anything useful.  The low-order bits of
a null pointer are very likely to be 0 on any real-world system.

Also, the test only looks at the low-order bits of the result of
the current malloc() call.  If you have an exotic system where
an aligned pointer can have a low-order bit set to 1, it might
*sometimes* be set to 0.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403153

In article <11amttk$14pou$2@kst.eternal-september.org>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>On 13/10/2026 10:38, chine.bleu wrote:
>>>...> As a precaution check the return
>>>> address of malloc
>>>> 
>>>>  p = malloc(m);
>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>
>>>Just to be pedantic, the standard doesn't guarantee that the expression
>>>you use will test what you want to test. Since there is a guarantee that
>>>malloc() returns a universally aligned memory, I think it's actually
>>>more likely that the test will fail than that malloc() will fail, though
>>>both probabilities are quite negligible, so it's hard to be sure.
>>
>> The syntax and precedence errors aside, the test is clearly
>> meant to ensure that the low bit in the return from `malloc` is
>> clear, so that it can be repurposed for other things.  It should
>> likely be:
>>
>> 	p = malloc(m);
>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>
>I'm not sure the NULL test adds anything useful.  The low-order bits of
>a null pointer are very likely to be 0 on any real-world system.

It was just meant to `abort` if `malloc` could not allocate for
whatever reason, and was unrelated to this business of stealing
low bits to cache other data.  The assertion is that, if the
program survives these tests, then `p` is suitable for use.

Sorry, I should have been clear about that.

>Also, the test only looks at the low-order bits of the result of
>the current malloc() call.  If you have an exotic system where
>an aligned pointer can have a low-order bit set to 1, it might
>*sometimes* be set to 0.

I think the point is that if one wants to repurpose the low bits
of the integer representation of `p` for some purpose, then one
ought to verify the base assumption that those bits are
available.  One need not do that on every malloc call, however.

In the face of weird implementations and esoteric hardware, I
don't know that one can have a more general test suitable for
e.g. a `static_assert()`.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#403174

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>
>>> On 13/10/2026 10:38, chine.bleu wrote:
>>> ...> As a precaution check the return
>>>
>>>> address of malloc
>>>>
>>>>  p = malloc(m);
>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>
>>> Just to be pedantic, the standard doesn't guarantee that the
>>> expression you use will test what you want to test.  Since there
>>> is a guarantee that malloc() returns a universally aligned memory,
>>> I think it's actually more likely that the test will fail than
>>> that malloc() will fail, though both probabilities are quite
>>> negligible, so it's hard to be sure.
>>
>> The syntax and precedence errors aside, the test is clearly
>> meant to ensure that the low bit in the return from `malloc` is
>> clear, so that it can be repurposed for other things.  It should
>> likely be:
>>
>> 	p = malloc(m);
>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>
> I'm not sure the NULL test adds anything useful.  The low-order bits
> of a null pointer are very likely to be 0 on any real-world system.

Surely we would like to protect against a null pointer being used
to access a non-existent object.

> Also, the test only looks at the low-order bits of the result of
> the current malloc() call.  If you have an exotic system where
> an aligned pointer can have a low-order bit set to 1, it might
> *sometimes* be set to 0.

As long as the bit in question /is/ zero it doesn't matter if it
might have been one.  The bit will always be cleared before using
the pointer as a pointer, so the pointer value in use will match
the pointer value originally returned.

Thus we might write a safe allocation function as follows:

   void *
   safe_new( size_t n ){
      void *p = 0;

      while(  !p || (uintptr_t)p %2 != 0  )  free( p ),  p = malloc( n++ );

      return  p;
   }

Of course it might not succeed in some cases, but it will be
quite obvious if it doesn't.  :)

[toc] | [prev] | [next] | [standalone]

#403176

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>> In article <11al0l0$eefv$1@dont-email.me>,
>>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>> ...> As a precaution check the return
>>>>
>>>>> address of malloc
>>>>>
>>>>>  p = malloc(m);
>>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>>
>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>> expression you use will test what you want to test.  Since there
>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>> I think it's actually more likely that the test will fail than
>>>> that malloc() will fail, though both probabilities are quite
>>>> negligible, so it's hard to be sure.
>>>
>>> The syntax and precedence errors aside, the test is clearly
>>> meant to ensure that the low bit in the return from `malloc` is
>>> clear, so that it can be repurposed for other things.  It should
>>> likely be:
>>>
>>> 	p = malloc(m);
>>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>
>> I'm not sure the NULL test adds anything useful.  The low-order bits
>> of a null pointer are very likely to be 0 on any real-world system.
>
> Surely we would like to protect against a null pointer being used
> to access a non-existent object.
>
>> Also, the test only looks at the low-order bits of the result of
>> the current malloc() call.  If you have an exotic system where
>> an aligned pointer can have a low-order bit set to 1, it might
>> *sometimes* be set to 0.
>
> As long as the bit in question /is/ zero it doesn't matter if it
> might have been one.  The bit will always be cleared before using
> the pointer as a pointer, so the pointer value in use will match
> the pointer value originally returned.
>
> Thus we might write a safe allocation function as follows:
>
>    void *
>    safe_new( size_t n ){
>       void *p = 0;
>
>       while(  !p || (uintptr_t)p %2 != 0  )  free( p ),  p = malloc( n++ );
>
>       return  p;
>    }
>
> Of course it might not succeed in some cases, but it will be
> quite obvious if it doesn't.  :)

I might be missing the point of "chine.bleu"'s suggestion.  I was
assuming that the point was to check whether it's possible *in
general* to play with the low-order bits of malloc'ed pointers.

On most systems, you can probably make that assumption based on
what you know about the system's memory model.  But it can't be
checked reliably at run time.

If I wanted my program to play with low-order bits of pointers, and
refuse to run if the system doesn't support that, I might write a
program that does a *lot* of malloc() calls and invoke it during
configuration, refusing to proceed with the build if it reports that
malloc() can return an "odd" pointer.  Aborting during execution
feels sloppy.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#403185

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> wrote:
>>>>
>>>>> On 13/10/2026 10:38, chine.bleu wrote:
>>>>> ...> As a precaution check the return
>>>>>
>>>>>> address of malloc
>>>>>>
>>>>>>  p = malloc(m);
>>>>>>  if ((uintptr_t)p)&1!=0) abort();
>>>>>
>>>>> Just to be pedantic, the standard doesn't guarantee that the
>>>>> expression you use will test what you want to test.  Since there
>>>>> is a guarantee that malloc() returns a universally aligned memory,
>>>>> I think it's actually more likely that the test will fail than
>>>>> that malloc() will fail, though both probabilities are quite
>>>>> negligible, so it's hard to be sure.
>>>>
>>>> The syntax and precedence errors aside, the test is clearly
>>>> meant to ensure that the low bit in the return from `malloc` is
>>>> clear, so that it can be repurposed for other things.  It should
>>>> likely be:
>>>>
>>>> 	p = malloc(m);
>>>> 	if (p == NULL || ((uintptr_t)p & 1) != 0) abort();
>>>
>>> I'm not sure the NULL test adds anything useful.  The low-order bits
>>> of a null pointer are very likely to be 0 on any real-world system.
>>
>> Surely we would like to protect against a null pointer being used
>> to access a non-existent object.
>>
>>> Also, the test only looks at the low-order bits of the result of
>>> the current malloc() call.  If you have an exotic system where
>>> an aligned pointer can have a low-order bit set to 1, it might
>>> *sometimes* be set to 0.
>>
>> As long as the bit in question /is/ zero it doesn't matter if it
>> might have been one.  The bit will always be cleared before using
>> the pointer as a pointer, so the pointer value in use will match
>> the pointer value originally returned.
>>
>> Thus we might write a safe allocation function as follows:
>>
>>    void *
>>    safe_new( size_t n ){
>>       void *p = 0;
>>
>>       while(  !p || (uintptr_t)p %2 != 0  ){
>>          free( p ),  p = malloc( n++ );
>>       }
>>
>>       return  p;
>>    }
>>
>> Of course it might not succeed in some cases, but it will be
>> quite obvious if it doesn't.  :)
>
> I might be missing the point of "chine.bleu"'s suggestion.  I was
> assuming that the point was to check whether it's possible *in
> general* to play with the low-order bits of malloc'ed pointers.

I took the tests with the abort() calls to be simply protection
against an unsuitable pointer being returned.  Nothing more
complicated than that.

The point I was making is different.  It doesn't matter if the
bit in question is always zero as long as it is zero a fair
amount of the time.  Also it doesn't have to be a low order bit,
or any pre-chosen bit, as long as some particular bit is zero
often enough.  We can imagine doing a lot of malloc() calls at
program startup and tallying how often a zero appears at each bit
position, and using one of the bit positions with a high count.
Simply do enough malloc() calls until the value returned has a
zero bit at the selected bit position.  The code above looks at a
fixed low order bit, but it could just as well look at a bit
whose position was chosen at run time during program startup.

> On most systems, you can probably make that assumption based on
> what you know about the system's memory model.  But it can't be
> checked reliably at run time.
>
> If I wanted my program to play with low-order bits of pointers, and
> refuse to run if the system doesn't support that, I might write a
> program that does a *lot* of malloc() calls and invoke it during
> configuration, refusing to proceed with the build if it reports that
> malloc() can return an "odd" pointer.  Aborting during execution
> feels sloppy.

I understand what you're saying.  It's mostly orthogonal to what
I was saying.

[toc] | [prev] | [next] | [standalone]

Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web