On 2024-01-19, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>> On Thu, 18 Jan 2024 16:13:48 -0800, Keith Thompson wrote:
>>> But with this proposed change, code could rely on realloc(ptr,
>>> 0) returning a non-null pointer *unless* available memory is critically
>>> low -- pretty much the same as in C11,
>>> except that a null pointer would be an indication that something is
>>> seriously wrong.
>>
>> So having to allocate something, when it didn’t actually need to allocate
>> anything, could lead to program failures in situations where things might
>> otherwise work fine.
>>
>> Unless, of course, there was a special non-null preallocated address value
>> that was returned for every zero-length allocation.
>
> That wouldn't meet the current requirements. If malloc(0) returns a
> non-null result, then two calls to malloc(0) must yield distinct results
> (if free() isn't called in between), just as two calls to malloc(1) must
> do.

But if malloc(0) returns null, then two such calls don't yield distinct
results.

We already don't know today whether malloc(0) == malloc(0).

> to write robust code. If malloc(0) and realloc(ptr, 0) return a
> non-null pointer on success, then a null result *always* indicates an
> allocation failure.

Not requiring the non-null return from malloc(0) to be distinct
from previous malloc(0) return values (whether they were freed or not),
could help to "sell" the idea of taking away the null return value.

Some implementors might grumble that null return allowed malloc(0) to be
efficient by not allocating anything. If they were allowed to return
(void *) -1 or something, that would placate that concern.

Say you have a large, sparse vector of dynamic vectors. Sparse in the
sense that most of the dynamic vectors in the sparse vector are empty;
only a few are nonempty. If those empty vectors come from malloc(0) in
an efficient way (nothing is allocated on the heap), that's nice.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku <433-929-6894@kylheku.com> writes:
[...]
> Not requiring the non-null return from malloc(0) to be distinct
> from previous malloc(0) return values (whether they were freed or not),
> could help to "sell" the idea of taking away the null return value.

But it would still be an additional special case -- and someone might
use malloc(0) specifically as a way to obtain a unique non-null pointer
while allocating minimal memory. (Of course the could use malloc(1) to
do the same thing.)

> Some implementors might grumble that null return allowed malloc(0) to be
> efficient by not allocating anything. If they were allowed to return
> (void *) -1 or something, that would placate that concern.
>
> Say you have a large, sparse vector of dynamic vectors. Sparse in the
> sense that most of the dynamic vectors in the sparse vector are empty;
> only a few are nonempty. If those empty vectors come from malloc(0) in
> an efficient way (nothing is allocated on the heap), that's nice.

What's being suggested is basically a second kind of null pointer, i.e.,
a second unique pointer value that can't be dereferenced. And if two
malloc(0) calls were allowed to return the same non-null value, that
would require additional wording in the standard. I don't strongly
object to the idea, but I don't think it's necessary.

And if, say, C26 permitted or required two non-null malloc(0) results to
be equal, code could not rely on that behavior unless it's guaranteed to
be compiled with a C26 or later compiler. It would be effectively
implementation-defined, but across editions of the standard rather than
implementations. (There's probably not much existing code that relies
on this.)

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

scott@slp53.sl.home (Scott Lurndal) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> scott@slp53.sl.home (Scott Lurndal) writes:
>>
>>> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>>>
>>>> I'm looking at the C99 and N3096 (April 2023) definitions of realloc
>>>> side by side.
>>>>
>>>> N3096 says
>>>>
>>>> "Otherwise, if ptr does not match a pointer earlier returned by a memory
>>>> management function, or if the space has been deallocated by a call to
>>>> the free or realloc function, or if the size is zero, the behavior is
>>>> undefined."
>>>>
>>>> Yikes! In C99 there is nothing about the size being zero:
>>>>
>>>> "Otherwise, if ptr does not match a pointer earlier returned by the
>>>> calloc, malloc, or realloc function, or if the space has been
>>>> deallocated by a call to the free or realloc function, the behavior is
>>>> undefined."
>>>>
>>>> Nothing about "or if the size is zero".
>>>>
>>>> Yikes; when did this criminal stupidity get perpetrated?
>>>
>>> I'm not sure what stupidity you are referring to, but IIRC, there was
>>> some recent standardization activity relating to realloc
>>> when size == 0 because there were differences in the behavior
>>> between different implementations. Making the behavior
>>> undefined was the only rational choice.
>>
>> Is that last sentence your own assessment, or are you simply
>> repeating someone else's assessment?
>
> My assessment. I've never found realloc useful, regardless of
> the value of the size parameter. YMMV.

So you aren't really in a position to say whether this decision was
the only rational choice. Generally I hope people who would make
such a statement would first make an effort to learn and understand
other people's thoughts on the matter.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> scott@slp53.sl.home (Scott Lurndal) writes:
>>>
>>>> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>>>>
>>>>> I'm looking at the C99 and N3096 (April 2023) definitions of realloc
>>>>> side by side.
>>>>>
>>>>> N3096 says
>>>>>
>>>>> "Otherwise, if ptr does not match a pointer earlier returned by a memory
>>>>> management function, or if the space has been deallocated by a call to
>>>>> the free or realloc function, or if the size is zero, the behavior is
>>>>> undefined."
>>>>>
>>>>> Yikes! In C99 there is nothing about the size being zero:
>>>>>
>>>>> "Otherwise, if ptr does not match a pointer earlier returned by the
>>>>> calloc, malloc, or realloc function, or if the space has been
>>>>> deallocated by a call to the free or realloc function, the behavior is
>>>>> undefined."
>>>>>
>>>>> Nothing about "or if the size is zero".
>>>>>
>>>>> Yikes; when did this criminal stupidity get perpetrated?
>>>>
>>>> I'm not sure what stupidity you are referring to, but IIRC, there was
>>>> some recent standardization activity relating to realloc
>>>> when size == 0 because there were differences in the behavior
>>>> between different implementations. Making the behavior
>>>> undefined was the only rational choice.
>>>
>>> Is that last sentence your own assessment, or are you simply
>>> repeating someone else's assessment?
>>
>> My assessment. I've never found realloc useful, regardless of
>> the value of the size parameter. YMMV.
>
>So you aren't really in a position to say whether this decision was
>the only rational choice. Generally I hope people who would make
>such a statement would first make an effort to learn and understand
>other people's thoughts on the matter.

The fact that I didn't find it useful, doesn't imply in any way
that I don't understand other's thoughts on the matter. I did
spend several years on various standards committees, compromise
was often the best way to make forward progress and 'undefined
behavior' was a rational compromise in that context.

I also believe that the fears over the impact of that decision
are overblown.

scott@slp53.sl.home (Scott Lurndal) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> scott@slp53.sl.home (Scott Lurndal) writes:
>>
>>> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>>>
>>>> On 2024-01-17, Scott Lurndal <scott@slp53.sl.home> wrote:
>>>>
>>>>> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>>>>>
>>>>>> Yikes; when did this criminal stupidity get perpetrated?
>>>>>
>>>>> I'm not sure what stupidity you are referring to, but IIRC, there was
>>>>> some recent standardization activity relating to realloc
>>>>> when size == 0 because there were differences in the behavior
>>>>> between different implementations. Making the behavior
>>>>> undefined was the only rational choice.
>>>>
>>>> No, the rational choice is letting those implementations be
>>>> nonconforming, until they fix their shit.
>>>>
>>>> You cannot claw back decades-old defined behaviors in a major
>>>
>>> Nobody is clawing anything back. [...]
>>
>> This statement seems directly contradicted by the proposed
>> modification to the C standard, which changes previously
>> defined behavior to undefined behavior.
>
> Clawing back implies that existing programs that rely
> on either behavior will stop working.
>
> That's not the case in the real world.

There is no question that the proposed change (which is possibly
ratified by now) would claw back some defined behavior in favor of
undefined behavior. What you're saying is that there will be no
consequences of that clawing back.

First, there certainly will be _some_ consequences, because some
people will modify their code even if they think there will be no
changes in the compilers and libraries they use.

Second, even if many compilers and many C libraries make no
changes (at least in the near future), the chances are high that
at least some will, especially in the presence of library software
updates and new platforms coming on line (low-end consumer
hardware such as switches and wifi routters), and consequently
some applications will get bitten by this.

Third, even if there are no changes in the near term, if we look
out ten years or more it is highly likely that these things will
change in many implementations, especially when taking into
account cross-compiling. The idea that there will be no changes
"in the real world" over a long time frame is incredibly naive.
The Linux null-pointer-use bug illustrates the problem.

> From the application portability point of view, there is little
> difference between implementation defined and undefined behavior.

This statement is nonsense. Essentially all C programs depend on
implementation-defined behavior to some degree. If all of that ID
behavior were changed to be undefined behavior, programming in C
would be impossible for all practical purposes, whether or not
portability is a consideration.

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>> On 2024-01-18, James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>> It's OK to rely upon the requirements imposed by an implementation when
>>> the C standard doesn't impose any - but when you do so, you need to make
>>> sure you actually know what those requirements are.
>>
>> Exactly, and in this specific case, it's not worth the effort compared
>> to writing a realloc wrapper that avoids the undefined behavior, while
>> itself providing a C99 conforming one.
>>
>> I'm not going to use realloc(ptr, 0) and check everyone's documentation.
>>
>> And then what if I don't find it defined? The what? Back to the
>> wrapper I could have just written in the first place.
> [...]
>
> I think I would have *liked* to see C23 drop the special permission
> to return a null pointer for a requested size of zero. C11 says (and
> this applies to malloc, realloc, and all other allocation functions):
>
> If the space cannot be allocated, a null pointer is returned. If
> the size of the space requested is zero, the behavior is
> implementation-defined: either a null pointer is returned, or
> the behavior is as if the size were some nonzero value, except
> that the returned pointer shall not be used to access an object.
>
> This could have been changed to:
>
> If the space cannot be allocated, a null pointer is returned. If
> the size of the space requested is zero, the behavior is as
> if the size were some nonzero value, except that the returned
> pointer shall not be used to access an object.
>
> Any existing implementations that always return a null pointer
> for malloc(0) would have to be updated. That shouldn't be a
> great burden.
>
> Note that malloc(0) or realloc(ptr, 0) can still fail and return
> a null pointer if no space can be allocated, so all allocations
> should still be checked. But with this proposed change, code
> could rely on realloc(ptr, 0) returning a non-null pointer *unless*
> available memory is critically low -- pretty much the same as in C11,
> except that a null pointer would be an indication that something
> is seriously wrong.
>
> (I remember seeing a discussion about making the behavior of
> realloc(ptr, 0) undefined. I'm making inquiries, and I'll follow
> up if I learn anything relevant.)

I got a response from JeanHeyd Meneide.

If realloc(ptr, 0) returns a null pointer there's no way to tell whether
allocation failed (and ptr has not been freed), or the implementation
returns a null pointer for zero-sized allocations (and ptr has been
freed). Some implementations set errno, but C doesn't require it.

C17 added this in 7.31.11, Future library directions:

Invoking realloc with a size argument equal to zero is an
obsolescent feature.

More references:

DR 400 <https://www.open-std.org/jtc1/sc22/wg14/www/docs/summary.htm#dr_400>
"realloc with size zero problems"

N2438 <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2438.htm>
"Clarification Request", "Realloc with size 0 ambiguity"

N2464 <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf>
This is the paper that proposed making realloc(?, 0) undefined behavior,
whether the first argument is null or not. Part of the rationale was to
allow POSIX to define it however they please.

N2665 <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2665.pdf>
Not directly relevant; it just removes the statement that zero-sized
reallocations are obsolescent, since it's no longer necessary.

Personally, I still think it would have been cleaner to remove the
permission for any allocation functions to return a null pointer, even
with a requested size of 0, unless there isn't enough memory for the
allocation to succeed.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

On Sat, 20 Jan 2024 19:50:31 -0800, Keith Thompson wrote:

> If realloc(ptr, 0) returns a null pointer there's no way to tell whether
> allocation failed (and ptr has not been freed) ...

Actually, that doesn’t seem like a reasonable interpretation, because it
leads to memory leaks.

On 2024-01-21, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:
> On Sat, 20 Jan 2024 19:50:31 -0800, Keith Thompson wrote:
>
>> If realloc(ptr, 0) returns a null pointer there's no way to tell whether
>> allocation failed (and ptr has not been freed) ...
>
> Actually, that doesn’t seem like a reasonable interpretation, because it
> leads to memory leaks.

That's not an "interpretation"; that's just a fact.

A null return from realloc has two documented meanings; situations exist
in which it cannot be distinguished which one, in any portable way.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku <433-929-6894@kylheku.com> writes:

[.. considering the behavior of malloc(0) ..]

> [If] implentations could have a single dedicated object for
> representing empty allocations (which can be passed to free any
> number of times), that would also be a nice requirement.

That defeats the whole purpose of having malloc(0) return
a non-null value. Don't you understand anything?

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

> What's being suggested is basically a second kind of null pointer, i.e.,
> a second unique pointer value that can't be dereferenced. And if two
> malloc(0) calls were allowed to return the same non-null value, that
> would require additional wording in the standard. I don't strongly
> object to the idea, but I don't think it's necessary.

It's a counterproductive idea. The whole point of malloc(0) being
able to return a non-null pointer is to get distinct "objects" for
different zero-sized allocations. The "objects" can't be used in
any way but comparing the pointers allows the "objects" from two
different allocations to be distinguished.

Kaz Kylheku <433-929-6894@kylheku.com> writes:

> On 2024-01-19, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>
>> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>>
>>> On 2024-01-18, James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>
>>>> It's OK to rely upon the requirements imposed by an implementation when
>>>> the C standard doesn't impose any - but when you do so, you need to make
>>>> sure you actually know what those requirements are.
>>>
>>> Exactly, and in this specific case, it's not worth the effort compared
>>> to writing a realloc wrapper that avoids the undefined behavior, while
>>> itself providing a C99 conforming one.
>>>
>>> I'm not going to use realloc(ptr, 0) and check everyone's documentation.
>>>
>>> And then what if I don't find it defined? The what? Back to the
>>> wrapper I could have just written in the first place.
>>
>> [...]
>>
>> I think I would have *liked* to see C23 drop the special permission
>> to return a null pointer for a requested size of zero.
>
> Yes. That would be the best thing.
>
> It also works well when the memory is subject to memcpy or memset,
> which have undefined behavior on null pointers.

That's a half-assed argument. There are other ways a pointer might
have a null value than just being the result of a call to malloc().
If code might call memset() et al with a zero size and a null
pointer, it's better to address all possible cases at once rather
than just some of them:

static inline void *
safer_memset( void *s, int c, size_t n ){
return n ? memset( s, c, n ) : s;
}

static inline void *
safer_memcpy( void *d, const void *s, size_t n ){
return n ? memcpy( d, s, n ) : d;
}

/* ... etc ... */

On 19/01/2024 21:50, Kaz Kylheku wrote:
> On 2024-01-19, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>> On Thu, 18 Jan 2024 16:13:48 -0800, Keith Thompson wrote:
>>>> But with this proposed change, code could rely on realloc(ptr,
>>>> 0) returning a non-null pointer *unless* available memory is critically
>>>> low -- pretty much the same as in C11,
>>>> except that a null pointer would be an indication that something is
>>>> seriously wrong.
>>>
>>> So having to allocate something, when it didn’t actually need to allocate
>>> anything, could lead to program failures in situations where things might
>>> otherwise work fine.
>>>
>>> Unless, of course, there was a special non-null preallocated address value
>>> that was returned for every zero-length allocation.
>>
>> That wouldn't meet the current requirements. If malloc(0) returns a
>> non-null result, then two calls to malloc(0) must yield distinct results
>> (if free() isn't called in between), just as two calls to malloc(1) must
>> do.
>
> But if malloc(0) returns null, then two such calls don't yield distinct
> results.
>
> We already don't know today whether malloc(0) == malloc(0).
>
>> to write robust code. If malloc(0) and realloc(ptr, 0) return a
>> non-null pointer on success, then a null result *always* indicates an
>> allocation failure.
>
> Not requiring the non-null return from malloc(0) to be distinct
> from previous malloc(0) return values (whether they were freed or not),
> could help to "sell" the idea of taking away the null return value.
>
> Some implementors might grumble that null return allowed malloc(0) to be
> efficient by not allocating anything. If they were allowed to return
> (void *) -1 or something, that would placate that concern.
>
> Say you have a large, sparse vector of dynamic vectors. Sparse in the
> sense that most of the dynamic vectors in the sparse vector are empty;
> only a few are nonempty. If those empty vectors come from malloc(0) in
> an efficient way (nothing is allocated on the heap), that's nice.

malloc has sort of created a rod for its own back by needing to store
the size of the allocation. That will take up some space even when
malloc(0) is called, if NULL is not being returned.

I've looked at my own allocator for small objects, which does not store
the size. There, successive calls to my_alloc(0) return the same pointer
value to a zero-sized memory block (but not if there are intervening
calls to my_alloc(100).)

A call to free a zero-sized block will be my_free(p,0) so it knows no
action is needed.

malloc(0) can be made efficient by it detecting the zero-size and
returning a pointer to the same special memory block, even if there are
intervening non-zero calls.

A call to free(p) where p refers to that zero-sized block can also be
detected.

So it will save on memory if allocating millions of zero-sized blocks,
but it means extra checks on each call.

Other replies however suggested that such malloc(0) calls need to return
unique values. But you can't have both have unique values and save
memory (at best you will need 1 byte per malloc(0), and some hairy means
of detecting whether the p in free(p) refers to one of those bytes, so a
bigger runtime overhead).

Kaz Kylheku <433-929-6894@kylheku.com> writes:

[...]

> Not requiring the non-null return from malloc(0) to be distinct
> from previous malloc(0) return values (whether they were freed or not),
> could help to "sell" the idea of taking away the null return value.
>
> Some implementors might grumble that null return allowed malloc(0) to be
> efficient by not allocating anything. If they were allowed to return
> (void *) -1 or something, that would placate that concern. [...]

You have the tail wagging the dog here. If the results of
different malloc(0) calls don't need to be distinguishable,
they might just as well all be null.

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

[...]

> Note that malloc(0) or realloc(ptr, 0) can still fail and return
> a null pointer if no space can be allocated, so all allocations
> should still be checked. [...]

Note that it isn't hard to write code for realloc() that
guarantees a realloc( p, 0 ) call will never fail (that
is, if 'p' is non-null, there will never be a case where
a null value indicating an allocation failure has to be
returned). To do that, all the implementation needs to
do is see if the malloc(0) allocation would fail, and
if it would then simply return 'p', without freeing it.

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

[.. considering the definition of malloc(0) ..]

> I dislike the fact that the behavior is currently
> implementation-defined. I think requiring malloc(0) to return a
> null pointer would be an improvement over the current (C11)
> specification, though it would be an odd special case; a null
> pointer would mean either that the allocation failed (and the
> system is likely in a bad state) or that the requested size was 0.
> Note that an application might call malloc() with a variable
> argument whose value can just happen to be zero. [...]

First I think it is worth going back and re-reading the Rationale
where it talks about malloc() and friends.

I'm sympathetic to the reaction about malloc() and friends having
different behavior in different implemenations. On the other
hand let's look at it from the point of view of implementations:

(A) For malloc(0) returning non-null: that can be a convenience
for some applications, and can be supplied in a way that client
code cannot provide.

(B) For malloc(0) returning null: most programs don't allocate
zero-sized objects, except perhaps inadvertently; in most uses
code will work without needing to distinguish, and in those cases
where the distinction is important it isn't hard to write code
that works for both allowed behaviors; being able to return null
for zero-size requests both simplifies the code and uses less
resource than choice (A). In small systems the added resource
demands may very well be the deciding factor between choosing (A)
and choosing (B).

For most aspects, client code can ignore the distinction between
behavior (A) and behavior (B). The big exception to that is how
to detect errors. If we think the C standard should continue to
allow both possibilities (and personally I think it should), a
way around the problem is to provide a testable macro symbol, as
for example

#if __MALLOC_0_GIVES_NULL
...
#elif __MALLOC_0_GIVES_NONNULL
...
#else
... deal with uncertainty in some way
... (not hard although it may involve a run-time cost)
#endif

If some such macros were provided it isn't hard to define a macro
that does error checking in both kinds of environments, so there
could be code like this:

Foo *p = malloc( n * sizeof *p );
if( MALLOC_FAILED( p, n ) ) ...

where the MALLOC_FAILED() macro would either simply test '!p' or
would test '!p && n > 0', depending on whether the code is
running in an (A) regime or a (B) regime.

Personally I would like to see the memory allocation functions
augmented to be explicit about which behavior is wanted:

void *malloc0( size_t ); /* returns NULL for size of 0 */
void *malloc1( size_t ); /* returns NULL only on failure */

along with analogous changes for calloc(), realloc(), etc.

On 2024-01-21, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>
> [.. considering the behavior of malloc(0) ..]
>
>> [If] implentations could have a single dedicated object for
>> representing empty allocations (which can be passed to free any
>> number of times), that would also be a nice requirement.
>
> That defeats the whole purpose of having malloc(0) return
> a non-null value. Don't you understand anything?

I undertand very clearly from past disccussions that you're attached to
a particular use case whereby malloc(0) returns unique objects.

However, I don't see that as the purpose, let alone the "whole purpose".

The standard currently does not endorse malloc(0) as a factory
for unique pointers.

Currently, it cannot be relied on due to the possibility of
the null return. If you want that behavior portably, you currently have
to use malloc(1) instead, or some other nonzero value.
Even if your program detects that malloc(0) returns a non-null
pointer one time, there is no requirement that all subsequent such
allocations will return non-null.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

bart <bc@freeuk.com> writes:

> malloc has sort of created a rod for its own back by needing to
> store the size of the allocation.

malloc does not need to store the size of the space requested.

It does need to save enough information to be able to compute
how much memory needs to be reclaimed, based on the pointer
to the memory area to be free()'d. That might not be as much
memory as a whole size word, although typically the overhead
is as many bytes as a pointer, or a size_t, per block (including
both allocated blocks and free blocks).

> That will take up some space even when malloc(0) is called, if
> NULL is not being returned. [...]
>
> Other replies however
> suggested that such malloc(0) calls need to return unique values.
> But you can't have both have unique values and save memory (at
> best you will need 1 byte per malloc(0), and some hairy means of
> detecting whether the p in free(p) refers to one of those bytes,
> so a bigger runtime overhead).

In a conventional architecture, eg x64, it isn't too difficult to
devise a method for malloc() and free() of zero-sized objects that
(a) has a fast check to see if an argument value refers to a
zero-size object, and (b) takes 1.5 bits or less per zero-size
object allocated.

On 1/21/2024 3:55 AM, bart wrote:
> On 19/01/2024 21:50, Kaz Kylheku wrote:
>> On 2024-01-19, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>>> On Thu, 18 Jan 2024 16:13:48 -0800, Keith Thompson wrote:
>>>>> But with this proposed change, code could rely on realloc(ptr,
>>>>> 0) returning a non-null pointer *unless* available memory is
>>>>> critically
>>>>> low -- pretty much the same as in C11,
>>>>> except that a null pointer would be an indication that something is
>>>>> seriously wrong.
>>>>
>>>> So having to allocate something, when it didn’t actually need to
>>>> allocate
>>>> anything, could lead to program failures in situations where things
>>>> might
>>>> otherwise work fine.
>>>>
>>>> Unless, of course, there was a special non-null preallocated address
>>>> value
>>>> that was returned for every zero-length allocation.
>>>
>>> That wouldn't meet the current requirements.  If malloc(0) returns a
>>> non-null result, then two calls to malloc(0) must yield distinct results
>>> (if free() isn't called in between), just as two calls to malloc(1) must
>>> do.
>>
>> But if malloc(0) returns null, then two such calls don't yield distinct
>> results.
>>
>> We already don't know today whether malloc(0) == malloc(0).
>>
>>> to write robust code.  If malloc(0) and realloc(ptr, 0) return a
>>> non-null pointer on success, then a null result *always* indicates an
>>> allocation failure.
>>
>> Not requiring the non-null return from malloc(0) to be distinct
>> from previous malloc(0) return values (whether they were freed or not),
>> could help to "sell" the idea of taking away the null return value.
>>
>> Some implementors might grumble that null return allowed malloc(0) to be
>> efficient by not allocating anything. If they were allowed to return
>> (void *) -1 or something, that would placate that concern.
>>
>> Say you have a large, sparse vector of dynamic vectors. Sparse in the
>> sense that most of the dynamic vectors in the sparse vector are empty;
>> only a few are nonempty. If those empty vectors come from malloc(0) in
>> an efficient way (nothing is allocated on the heap), that's nice.
>
> malloc has sort of created a rod for its own back by needing to store
> the size of the allocation. That will take up some space even when
> malloc(0) is called, if NULL is not being returned.
[...]

Why would malloc need to store the size of its allocations?

On 21/01/2024 20:22, Chris M. Thomasson wrote:
> On 1/21/2024 3:55 AM, bart wrote:

>> malloc has sort of created a rod for its own back by needing to store
>> the size of the allocation. That will take up some space even when
>> malloc(0) is called, if NULL is not being returned.
> [...]
>
> Why would malloc need to store the size of its allocations?
>

If you do this:

p = malloc(N);
...
free(p);

'free' will need to know what N was used to allocate p in order to
deallocate right size of memory.

On Sun, 21 Jan 2024 12:22:05 -0800, Chris M. Thomasson wrote:

> On 1/21/2024 3:55 AM, bart wrote:
>> On 19/01/2024 21:50, Kaz Kylheku wrote:
>>> On 2024-01-19, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>>>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>>>> On Thu, 18 Jan 2024 16:13:48 -0800, Keith Thompson wrote:
>>>>>> But with this proposed change, code could rely on realloc(ptr,
>>>>>> 0) returning a non-null pointer *unless* available memory is
>>>>>> critically
>>>>>> low -- pretty much the same as in C11,
>>>>>> except that a null pointer would be an indication that something is
>>>>>> seriously wrong.
>>>>>
>>>>> So having to allocate something, when it didn’t actually need to
>>>>> allocate
>>>>> anything, could lead to program failures in situations where things
>>>>> might
>>>>> otherwise work fine.
>>>>>
>>>>> Unless, of course, there was a special non-null preallocated address
>>>>> value
>>>>> that was returned for every zero-length allocation.
>>>>
>>>> That wouldn't meet the current requirements.  If malloc(0) returns a
>>>> non-null result, then two calls to malloc(0) must yield distinct results
>>>> (if free() isn't called in between), just as two calls to malloc(1) must
>>>> do.
>>>
>>> But if malloc(0) returns null, then two such calls don't yield distinct
>>> results.
>>>
>>> We already don't know today whether malloc(0) == malloc(0).
>>>
>>>> to write robust code.  If malloc(0) and realloc(ptr, 0) return a
>>>> non-null pointer on success, then a null result *always* indicates an
>>>> allocation failure.
>>>
>>> Not requiring the non-null return from malloc(0) to be distinct
>>> from previous malloc(0) return values (whether they were freed or not),
>>> could help to "sell" the idea of taking away the null return value.
>>>
>>> Some implementors might grumble that null return allowed malloc(0) to be
>>> efficient by not allocating anything. If they were allowed to return
>>> (void *) -1 or something, that would placate that concern.
>>>
>>> Say you have a large, sparse vector of dynamic vectors. Sparse in the
>>> sense that most of the dynamic vectors in the sparse vector are empty;
>>> only a few are nonempty. If those empty vectors come from malloc(0) in
>>> an efficient way (nothing is allocated on the heap), that's nice.
>>
>> malloc has sort of created a rod for its own back by needing to store
>> the size of the allocation. That will take up some space even when
>> malloc(0) is called, if NULL is not being returned.
> [...]
>
> Why would malloc need to store the size of its allocations?

So that, in a naive implementation, free() knows how much memory to
return to the freelist. See K&R Chapter 8, secion 8.7 "Example - A
Storage Allocator" for an example.

--
Lew Pitcher
"In Skills We Trust"

On 21/01/2024 21:34, bart wrote:
> On 21/01/2024 20:22, Chris M. Thomasson wrote:
>> On 1/21/2024 3:55 AM, bart wrote:
>
>>> malloc has sort of created a rod for its own back by needing to store
>>> the size of the allocation. That will take up some space even when
>>> malloc(0) is called, if NULL is not being returned.
>> [...]
>>
>> Why would malloc need to store the size of its allocations?
>>
>
> If you do this:
>
>     p = malloc(N);
>     ...
>     free(p);
>
> 'free' will need to know what N was used to allocate p in order to
> deallocate right size of memory.
>

It does not need to store the size of the allocation. It merely has to
store sufficient information to be able to figure out how to deallocate
properly. And any storage it needs can be in a different place from the
allocation.

Some malloc/free systems track the information separately from the
allocation data. One possibility is to use pools for different memory
sizes. When the user asks for X bytes, this is rounded up to the
nearest pool size - call it Y - and the allocation is made from the Y
pool, which can be viewed as an array of Y-size lumps. Only need one
single bit to track each allocation, to say which indexes in the array
are used. There are many other ways to do it.

Personally, I think it would be often more efficient in modern C if the
allocation system didn't track sizes at all, and "free" passed the
original size as a parameter. But that ship sailed long ago for
standard C. (C++ supports a sized deallocation system, and of course
there's nothing to stop you making your own allocator system for C.)

On 2024-01-21, bart <bc@freeuk.com> wrote:
> On 21/01/2024 20:22, Chris M. Thomasson wrote:
>> On 1/21/2024 3:55 AM, bart wrote:
>
>>> malloc has sort of created a rod for its own back by needing to store
>>> the size of the allocation. That will take up some space even when
>>> malloc(0) is called, if NULL is not being returned.
>> [...]
>>
>> Why would malloc need to store the size of its allocations?
>>
>
> If you do this:
>
> p = malloc(N);
> ...
> free(p);
>
> 'free' will need to know what N was used to allocate p in order to
> deallocate right size of memory.

While that is true in the abstract, it is not necesarily the case
that it needs to pull N out of the p object.

For instance, suppose N is a 64 byte allocation, and the allocator
has special heaps for small allocations.

It can figure out that p points into a heap that has 64 byte objects
and then do some pointer arithmetic to figure out which one,
and add that to a free list or bitmap or whatever.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2024-01-21, David Brown <david.brown@hesbynett.no> wrote:
> Personally, I think it would be often more efficient in modern C if the
> allocation system didn't track sizes at all, and "free" passed the
> original size as a parameter. But that ship sailed long ago for
> standard C.

That ship newly sailed in 2023.

The N3096 draft describes a function free_sized that takes a size. If
the size is wrong, the behavior is undefined.

So now C has two ways to free an object: an efficient one where
the program helps by giving the size, and the old free, which
may have to do more work.

I think going forward, it may start to become wise to detect the
implementation's support for free_sized (e.g. in a configure script)
and use that as much as possible, using free only when it's
inconvenient: for instance a function resembling POSIX strdup
might not be able to to safely assume that it can do
free_sized(str, strlen(str)+1), because the underlying buffer
might be larger.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

David Brown <david.brown@hesbynett.no> writes:
[...]
> Personally, I think it would be often more efficient in modern C if
> the allocation system didn't track sizes at all, and "free" passed the
> original size as a parameter. But that ship sailed long ago for
> standard C. (C++ supports a sized deallocation system, and of course
> there's nothing to stop you making your own allocator system for C.)

I suspect that calling malloc() with one size and free() with a
different one would have been a rich source of subtle bugs.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

On 21/01/2024 20:54, David Brown wrote:
> On 21/01/2024 21:34, bart wrote:
>> On 21/01/2024 20:22, Chris M. Thomasson wrote:
>>> On 1/21/2024 3:55 AM, bart wrote:
>>
>>>> malloc has sort of created a rod for its own back by needing to
>>>> store the size of the allocation. That will take up some space even
>>>> when malloc(0) is called, if NULL is not being returned.
>>> [...]
>>>
>>> Why would malloc need to store the size of its allocations?
>>>
>>
>> If you do this:
>>
>>      p = malloc(N);
>>      ...
>>      free(p);
>>
>> 'free' will need to know what N was used to allocate p in order to
>> deallocate right size of memory.
>>
>
> It does not need to store the size of the allocation.

So it doesn't specifically need to store N for free to do its job ...

> It merely has to
> store sufficient information to be able to figure out how to deallocate
> properly.  And any storage it needs can be in a different place from the
> allocation.
>
> Some malloc/free systems track the information separately from the
> allocation data.  One possibility is to use pools for different memory
> sizes.  When the user asks for X bytes, this is rounded up to the
> nearest pool size - call it Y - and the allocation is made from the Y
> pool, which can be viewed as an array of Y-size lumps.  Only need one
> single bit to track each allocation, to say which indexes in the array
> are used.  There are many other ways to do it.
>
> Personally, I think it would be often more efficient in modern C if the
> allocation system didn't track sizes at all, and "free" passed the
> original size as a parameter.

.... but here you're specifically passing N for free to do its job.
Suggesting this value is a good way to determine the necessary info.