(Inspired by a sub-thread in one or another of the usual, interminable
navel-gazing threads for which CLC is justly famous...)

(On my system) "man realloc" says that:

If size was equal to 0, either NULL or a pointer suitable to be passed
to free() is returned.

which is odd, since, although the standard says either one is legal, the
implementation ought to know. Experimentation indicates that the answer is
the former (NULL).

But what I find interesting is the wording of the second alternative.
Earlier on, it says that the above call (realloc(p,0)) is equivalent to
free(p). So, that means that once the call is made, the pointer is no
longer valid. The text quoted above indicates that whatever is returned by
the call (if not NULL) is valid to be passed to free(). But wouldn't that
(doing so) lead to a dreaded "double free" ?

Note: I may have left some T's uncrossed and/or some I's undotted, but I am
running out of time, so I must cut this short. Rest assured that I have
considered all the possibilities, even if I have not delineated them all
here.

--
"Remember when teachers, public employees, Planned Parenthood, NPR and PBS
crashed the stock market, wiped out half of our 401Ks, took trillions in
TARP money, spilled oil in the Gulf of Mexico, gave themselves billions in
bonuses, and paid no taxes? Yeah, me neither."

On 7/30/23 12:36 PM, Kenny McCormack wrote:
> (Inspired by a sub-thread in one or another of the usual, interminable
> navel-gazing threads for which CLC is justly famous...)
>
> (On my system) "man realloc" says that:
>
> If size was equal to 0, either NULL or a pointer suitable to be passed
> to free() is returned.
>
> which is odd, since, although the standard says either one is legal, the
> implementation ought to know. Experimentation indicates that the answer is
> the former (NULL).
>
> But what I find interesting is the wording of the second alternative.
> Earlier on, it says that the above call (realloc(p,0)) is equivalent to
> free(p). So, that means that once the call is made, the pointer is no
> longer valid. The text quoted above indicates that whatever is returned by
> the call (if not NULL) is valid to be passed to free(). But wouldn't that
> (doing so) lead to a dreaded "double free" ?
>
> Note: I may have left some T's uncrossed and/or some I's undotted, but I am
> running out of time, so I must cut this short. Rest assured that I have
> considered all the possibilities, even if I have not delineated them all
> here.
>

My understanding is that, in effect, the call to realloc(p,0), if it is
using the second option of returning a suitable pointer, is effectively
do a free(p), and then allocating a "0 byte" block of memory and
returning the address of that. this pointer might have the same value as
the input pointer, or it might not. Calling free on the returned pointer
is allowed, and in fact needed to avoid a memory leak (of 0 bytes +
overhead) but calling free on the input pointer (unless the return
happens to match it) would be undefined behavior, as it was freed.

This is just like ANY use of the input pointer after the call, as it
might no longer be valid, unless of course, the return pointer happened
to match the input pointer as it was able to do the operation "in place".

As to why the document both behaviors, it may be that they support
multiple implementation libraries, and don't want to restrict them more
than the Standard does. It is NOT "Impleentation Defined Behavor" as to
which it does, it is just Unspecified, so the implementation can do
either, and could in fact do both at different times.

This just goes back to the Standards Committee not wanting to take sides
in a philosophical debate about 0-byte objects back when this came up,
and then not wanting to break code that depends on either behavior, such
code just needs to use implementations that promise the behavior they
depend on.

On 7/30/2023 9:36 AM, Kenny McCormack wrote:
> (Inspired by a sub-thread in one or another of the usual, interminable
> navel-gazing threads for which CLC is justly famous...)
>
> (On my system) "man realloc" says that:
>
> If size was equal to 0, either NULL or a pointer suitable to be passed
> to free() is returned.
>
> which is odd, since, although the standard says either one is legal, the
> implementation ought to know. Experimentation indicates that the answer is
> the former (NULL).
>
> But what I find interesting is the wording of the second alternative.
> Earlier on, it says that the above call (realloc(p,0)) is equivalent to
> free(p). So, that means that once the call is made, the pointer is no
> longer valid. The text quoted above indicates that whatever is returned by
> the call (if not NULL) is valid to be passed to free(). But wouldn't that
> (doing so) lead to a dreaded "double free" ?
>
> Note: I may have left some T's uncrossed and/or some I's undotted, but I am
> running out of time, so I must cut this short. Rest assured that I have
> considered all the possibilities, even if I have not delineated them all
> here.
>

void* p = realloc(p,0);
free(p);

Is fine. free(NULL) is fine.

Even if p is not NULL, it still can be passed to free. Keep in mind that
if p is not NULL it should never be used because its pointing to no
memory at all. What am I missing here?

Thanks.

On Sunday, 30 July 2023 at 20:12:58 UTC+1, Chris M. Thomasson wrote:
> On 7/30/2023 9:36 AM, Kenny McCormack wrote:
> > (Inspired by a sub-thread in one or another of the usual, interminable
> > navel-gazing threads for which CLC is justly famous...)
> >
> > (On my system) "man realloc" says that:
> >
> > If size was equal to 0, either NULL or a pointer suitable to be passed
> > to free() is returned.
> >
> > which is odd, since, although the standard says either one is legal, the
> > implementation ought to know. Experimentation indicates that the answer is
> > the former (NULL).
> >
> > But what I find interesting is the wording of the second alternative.
> > Earlier on, it says that the above call (realloc(p,0)) is equivalent to
> > free(p). So, that means that once the call is made, the pointer is no
> > longer valid. The text quoted above indicates that whatever is returned by
> > the call (if not NULL) is valid to be passed to free(). But wouldn't that
> > (doing so) lead to a dreaded "double free" ?
> >
> > Note: I may have left some T's uncrossed and/or some I's undotted, but I am
> > running out of time, so I must cut this short. Rest assured that I have
> > considered all the possibilities, even if I have not delineated them all
> > here.
> >
> void* p = realloc(p,0);
> free(p);
>
> Is fine. free(NULL) is fine.
>
> Even if p is not NULL, it still can be passed to free. Keep in mind that
> if p is not NULL it should never be used because its pointing to no
> memory at all. What am I missing here?
>
p is a valid pointer, but to a buffer of zero bytes. So it can be passed to any
function expecting a buffer, as long as that function is written to handle the
N ==0 case properly.
If we have this code.
unsigned char randomjunk[sizeof(void*)];
mempcy(&p, randomjunk, sizeof(void *));
functionexpectingabuffer(p, 0);

Then it's UB because the system can pick up that we're loading random junk
into an address register and trigger some sort of memory protection.

However is p is returned from realloc(ptr, 0) then it's OK.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Sunday, 30 July 2023 at 20:12:58 UTC+1, Chris M. Thomasson wrote:

>> void* p = realloc(p,0);

Danger Will Robinson! This is UB: p is indeterminate when passed to
realloc.

>> free(p);
>>
>> Is fine. free(NULL) is fine.
>>
>> Even if p is not NULL, it still can be passed to free. Keep in mind that
>> if p is not NULL it should never be used because its pointing to no
>> memory at all. What am I missing here?

Yes. If p in either NULL or a valid pointer from a prior allocation,
then

p = realloc(p, 0);
free(p);

is fine which was the point you wanted to make. It's unfortunate that
your example had an unrelated problem.

> p is a valid pointer, but to a buffer of zero bytes. So it can be
> passed to any function expecting a buffer, as long as that function is
> written to handle the N ==0 case properly.
> If we have this code.
> unsigned char randomjunk[sizeof(void*)];
> mempcy(&p, randomjunk, sizeof(void *));
> functionexpectingabuffer(p, 0);
>
> Then it's UB because the system can pick up that we're loading random junk
> into an address register and trigger some sort of memory protection.

I see you have decided to join Bart in misusing the term UB. That code
is UB regardless of what the system can or can't do. It's UB because
the language standard says you can't expect any defined behaviour from
that code.

Also, your supposed "reason" could lead readers astray. There is no UB
in this:

unsigned char randomjunk[sizeof (void*)];
mempcy(&p, randomjunk, sizeof p);

The undefined behaviour comes from /any/ access to the value in p after
this, even if that access does not involve it being treated as an
address. The confusion comes from the fact "loading random junk into an
address register" might be taken to refer to these lines, not the
passing of p to a function. After all, there no reason to think that
the code you show will result in a junk value getting into an address
register.

--
Ben.

On 7/31/2023 8:26 AM, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On Sunday, 30 July 2023 at 20:12:58 UTC+1, Chris M. Thomasson wrote:
>
>>> void* p = realloc(p,0);
>
> Danger Will Robinson! This is UB: p is indeterminate when passed to
> realloc.

AHHH SHIT!!!

void* b = realloc(a, 0);

God damn it! Sorry!

>
>>> free(p);
>>>
>>> Is fine. free(NULL) is fine.
>>>
>>> Even if p is not NULL, it still can be passed to free. Keep in mind that
>>> if p is not NULL it should never be used because its pointing to no
>>> memory at all. What am I missing here?
>
> Yes. If p in either NULL or a valid pointer from a prior allocation,
> then
>
> p = realloc(p, 0);
> free(p);
>
> is fine which was the point you wanted to make. It's unfortunate that
> your example had an unrelated problem.

Yeah. Shit happens. Thanks for the heads up, Ben. God Damn it.

>
>> p is a valid pointer, but to a buffer of zero bytes. So it can be
>> passed to any function expecting a buffer, as long as that function is
>> written to handle the N ==0 case properly.
>> If we have this code.
>> unsigned char randomjunk[sizeof(void*)];
>> mempcy(&p, randomjunk, sizeof(void *));
>> functionexpectingabuffer(p, 0);
>>
>> Then it's UB because the system can pick up that we're loading random junk
>> into an address register and trigger some sort of memory protection.
>
> I see you have decided to join Bart in misusing the term UB. That code
> is UB regardless of what the system can or can't do. It's UB because
> the language standard says you can't expect any defined behaviour from
> that code.
>
> Also, your supposed "reason" could lead readers astray. There is no UB
> in this:
>
> unsigned char randomjunk[sizeof (void*)];
> mempcy(&p, randomjunk, sizeof p);
>
> The undefined behaviour comes from /any/ access to the value in p after
> this, even if that access does not involve it being treated as an
> address. The confusion comes from the fact "loading random junk into an
> address register" might be taken to refer to these lines, not the
> passing of p to a function. After all, there no reason to think that
> the code you show will result in a junk value getting into an address
> register.
>

On 7/31/2023 2:35 PM, Chris M. Thomasson wrote:
> On 7/31/2023 8:26 AM, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On Sunday, 30 July 2023 at 20:12:58 UTC+1, Chris M. Thomasson wrote:
>>
>>>> void* p = realloc(p,0);
>>
>> Danger Will Robinson!  This is UB: p is indeterminate when passed to
>> realloc.

Face palm! How about danger Roger Wilco from SpaceQuest! ;^o

ARGGHHH!

>
> AHHH SHIT!!!
>
> void* b = realloc(a, 0);
>
> God damn it! Sorry!
[...]

gazelle@shell.xmission.com (Kenny McCormack) writes:

> (On my system) "man realloc" says that:
>
> If size was equal to 0, either NULL or a pointer suitable to
> be passed to free() is returned.
>
> which is odd, since, although the standard says either one is
> legal, the implementation ought to know. [...]

Probably the man page was written to express both possibilities,
so it could be used without change in different distributions.
Normally man pages are separate from whatever C implementation
is present; indeed there may be more than one, with different
choices made in the different implementations.

> But what I find interesting is the wording of the second
> alternative. Earlier on, it says that the above call
> (realloc(p,0)) is equivalent to free(p). [...]

The man page is either wrong or poorly written. I expect most
people have seen plenty of cases where what a man page says does
not exactly match what the C standard mandates.

Richard Damon <Richard@Damon-Family.org> writes:

> On 7/30/23 12:36 PM, Kenny McCormack wrote:
>
>> (On my system) "man realloc" says that:
>>
>> If size was equal to 0, either NULL or a pointer suitable to
>> be passed to free() is returned.
>>
>> which is odd, since, although the standard says either one is
>> legal, the implementation ought to know.

[...]

> As to why the document both behaviors, it may be that they support
> multiple implementation libraries, and don't want to restrict them
> more than the Standard does. It is NOT "Impleentation Defined
> Behavor" as to which it does, it is just Unspecified, so the
> implementation can do either, and could in fact do both at
> different times.

The choice for whether an allocation (or reallocation) of size 0
returns a null pointer or a "unique pointer" has been implementation
defined since C90: section 7.10.3 paragraph 1 in C90, 7.20.3 p1 in
n1256 for C99, and 7.22.3 p1 in n1570 for C11.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>gazelle@shell.xmission.com (Kenny McCormack) writes:
>
>> (On my system) "man realloc" says that:
>>
>> If size was equal to 0, either NULL or a pointer suitable to
>> be passed to free() is returned.
>>
>> which is odd, since, although the standard says either one is
>> legal, the implementation ought to know. [...]
>
>Probably the man page was written to express both possibilities,
>so it could be used without change in different distributions.
>Normally man pages are separate from whatever C implementation
>is present; indeed there may be more than one, with different
>choices made in the different implementations.

Some linux distributions simply provide the POSIX/SuS pages
rather than developing their own set of manual pages. Thus
the page will have generic elements not necessarily specific to
the implementation.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>Richard Damon <Richard@Damon-Family.org> writes:
>
>> On 7/30/23 12:36 PM, Kenny McCormack wrote:
>>
>>> (On my system) "man realloc" says that:
>>>
>>> If size was equal to 0, either NULL or a pointer suitable to
>>> be passed to free() is returned.
>>>
>>> which is odd, since, although the standard says either one is
>>> legal, the implementation ought to know.
>
>[...]
>
>> As to why the document both behaviors, it may be that they support
>> multiple implementation libraries, and don't want to restrict them
>> more than the Standard does. It is NOT "Impleentation Defined
>> Behavor" as to which it does, it is just Unspecified, so the
>> implementation can do either, and could in fact do both at
>> different times.
>
>The choice for whether an allocation (or reallocation) of size 0
>returns a null pointer or a "unique pointer" has been implementation
>defined since C90: section 7.10.3 paragraph 1 in C90, 7.20.3 p1 in
>n1256 for C99, and 7.22.3 p1 in n1570 for C11.

Even earlier, the System V Interface Definition (SVID3), first published
in 1983, says:

"If the size of the space requested is zero, the bahavior is
implementation defined; the value returned will either be a NULL
pointer or an unique pointer."

The Future Directions section indicates that the interface defintions
will use size_t instead of unsigned for the size parameter and the
older versions were moved to level 2 on 1989-09-30.

Richard Damon wrote:
> My understanding is that, in effect, the call to realloc(p,0), if it is
> using the second option of returning a suitable pointer, is effectively
> do a free(p), and then allocating a "0 byte" block of memory and
> returning the address of that.

Or it just returns p, as it might do whenever the requested new size is smaller
than the already-allocated size. No reason for 0 to be a special case.

Robert Latest <boblatest@yahoo.com> writes:

> Richard Damon wrote:
>
>> My understanding is that, in effect, the call to realloc(p,0), if
>> it is using the second option of returning a suitable pointer, is
>> effectively do a free(p), and then allocating a "0 byte" block of
>> memory and returning the address of that.
>
> Or it just returns p, as it might do whenever the requested new size
> is smaller than the already-allocated size. No reason for 0 to be a
> special case.

There are reasons for realloc() to zize 0 to be a special case.
Specifically, because the pointer value returned doesn't have to
be dereferencable, it can point to parts of the address space
that are otherwise unusable. The overhead for such "zero-byte
blocks" is very low, just a smidge over one bit. The usuable
memory previously allocated can be reclaimed and used in its
entirely for subsequent allocations. If running in a 64-bit
address space, vast amounts of otherwise unusable areas can
be used for these "special objects", having very little impact
on memory usable for actual objects.

On 31/08/2023 06:33, Tim Rentsch wrote:
> There are reasons for realloc() to zize 0 to be a special case.
> Specifically, because the pointer value returned doesn't have to
> be dereferencable, it can point to parts of the address space
> that are otherwise unusable. The overhead for such "zero-byte
> blocks" is very low, just a smidge over one bit. The usuable
> memory previously allocated can be reclaimed and used in its
> entirely for subsequent allocations. If running in a 64-bit
> address space, vast amounts of otherwise unusable areas can
> be used for these "special objects", having very little impact
> on memory usable for actual objects.

Tim, I'm confused by a little bit of that:

"just a smidge over one bit"

I can see how you might point them all to a single place that can't be
read or written, and have safety in case anyone tries to use them.

I can see that you might have a section of memory with a series of
bytes, each one reserved for these empty allocations. It might be
inaccessible, but will still use address space.

But how do you get anything smaller than a byte, but non-zero? I've only
ever used one CPU with addressing smaller than a byte.

Andy

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 31/08/2023 06:33, Tim Rentsch wrote:
>
>> There are reasons for realloc() to zize 0 to be a special case.
>> Specifically, because the pointer value returned doesn't have to
>> be dereferencable, it can point to parts of the address space
>> that are otherwise unusable. The overhead for such "zero-byte
>> blocks" is very low, just a smidge over one bit. The usuable
>> memory previously allocated can be reclaimed and used in its
>> entirely for subsequent allocations. If running in a 64-bit
>> address space, vast amounts of otherwise unusable areas can
>> be used for these "special objects", having very little impact
>> on memory usable for actual objects.
>
> Tim, I'm confused by a little bit of that:
>
> "just a smidge over one bit"
>
> I can see how you might point them all to a single place that can't be
> read or written, and have safety in case anyone tries to use them.
>
> I can see that you might have a section of memory with a series of
> bytes, each one reserved for these empty allocations. It might be
> inaccessible, but will still use address space.
>
> But how do you get anything smaller than a byte, but non-zero? I've
> only ever used one CPU with addressing smaller than a byte.

I was tempted to make a joke here, but I couldn't see how to turn
out something funny.

What I meant was just over one bit /per zero-byte block/. So if
there were 20,000 zero-byte blocks, they could be managed with
just a little more than 2500 bytes of allocated memory. Sorry
for the confusion.

On 01/09/2023 08:14, Tim Rentsch wrote:
> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
>> On 31/08/2023 06:33, Tim Rentsch wrote:
>>
>>> There are reasons for realloc() to zize 0 to be a special case.
>>> Specifically, because the pointer value returned doesn't have to
>>> be dereferencable, it can point to parts of the address space
>>> that are otherwise unusable. The overhead for such "zero-byte
>>> blocks" is very low, just a smidge over one bit. The usuable
>>> memory previously allocated can be reclaimed and used in its
>>> entirely for subsequent allocations. If running in a 64-bit
>>> address space, vast amounts of otherwise unusable areas can
>>> be used for these "special objects", having very little impact
>>> on memory usable for actual objects.
>>
>> Tim, I'm confused by a little bit of that:
>>
>> "just a smidge over one bit"
>>
>> I can see how you might point them all to a single place that can't be
>> read or written, and have safety in case anyone tries to use them.
>>
>> I can see that you might have a section of memory with a series of
>> bytes, each one reserved for these empty allocations. It might be
>> inaccessible, but will still use address space.
>>
>> But how do you get anything smaller than a byte, but non-zero? I've
>> only ever used one CPU with addressing smaller than a byte.
>
> I was tempted to make a joke here, but I couldn't see how to turn
> out something funny.
>
> What I meant was just over one bit /per zero-byte block/. So if
> there were 20,000 zero-byte blocks, they could be managed with
> just a little more than 2500 bytes of allocated memory. Sorry
> for the confusion.

I still don't follow you.

If I realloc to size 0 I get an address back. That can be a unique
address, in which case each one uses an address, and therefore a byte.

It can be a shared address, in which case the overhead per allocation is 0.

When I call free it would look at the shared address, and do nothing; if
it's a non-shared address it moves it to a free pool.

What does your bit do?

Andy

On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> What I meant was just over one bit /per zero-byte block/. So if
> there were 20,000 zero-byte blocks, they could be managed with
> just a little more than 2500 bytes of allocated memory. Sorry
> for the confusion.

The following is a much better requirement for malloc and realloc:

In the zero size case, return a non-null pointer to a single
program-wide object (always the same one), which can be passed
to the free function any number of times.

Since a zero sized object doesn't store any information, there
is no need to have more than one.

We satisfy these requirements:

- realloc(x, 0) is effectively free(x), except that it also
returns that object.

- the non-null object can be passed to library functions whose
behavior is not defined for null pointers, provided the
functions are not instructed to dereference it, or perform
pointer arithmetic.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On 2023-09-01, Vir Campestris <vir.campestris@invalid.invalid> wrote:
> It can be a shared address, in which case the overhead per allocation is 0.
>
> When I call free it would look at the shared address, and do nothing; if
> it's a non-shared address it moves it to a free pool.
>
> What does your bit do?

The address returned has to be a unique byte, but it doesn't have to
point to valid virtual or physical memory. On, say, 64 bit systems,
there is a lot of pointer space to play with that will never be used
for storage.

But you have to track, "did we allocate that pointer or not",
which is a Boolean property. That can be packed into a bit array
somewhere, whose elements correspond to a consecutive range of
some pointers. Just like a free sector map in MS-DOS FAT or whatever.

It's a decent implementation of the (possible) protocol that we have in
the standard of allocating unique objects for zero-sized requests.

The protocol itself is a silly idea, though.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:

> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>> What I meant was just over one bit /per zero-byte block/. So if there
>> were 20,000 zero-byte blocks, they could be managed with just a little
>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>
> The following is a much better requirement for malloc and realloc:
>
> In the zero size case, return a non-null pointer to a single
> program-wide object (always the same one), which can be passed to the
> free function any number of times.
>
> Since a zero sized object doesn't store any information, there is no
> need to have more than one.
>
> We satisfy these requirements:
>
> - realloc(x, 0) is effectively free(x), except that it also
> returns that object.
>
> - the non-null object can be passed to library functions whose
> behavior is not defined for null pointers, provided the functions are
> not instructed to dereference it, or perform pointer arithmetic.

This last point implies that there must be some way for code to
distinguish this non-null object (that cannot be dereferenced)
from other non-null objects that /can/ be dereferenced.

Given that you specify that the non-null pointer returned from
realloc(x,0)
would be "a single program-wide object" and "always the same one",
would you consider providing a unique name (like we do for the
null pointer constant NULL) for such an object? If so, what name
would you suggest, and what would the definition look like?

Just curious,
--
Lew Pitcher
"In Skills We Trust"

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 01/09/2023 08:14, Tim Rentsch wrote:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>> On 31/08/2023 06:33, Tim Rentsch wrote:
>>>
>>>> There are reasons for realloc() to zize 0 to be a special case.
>>>> Specifically, because the pointer value returned doesn't have to
>>>> be dereferencable, it can point to parts of the address space
>>>> that are otherwise unusable. The overhead for such "zero-byte
>>>> blocks" is very low, just a smidge over one bit. The usuable
>>>> memory previously allocated can be reclaimed and used in its
>>>> entirely for subsequent allocations. If running in a 64-bit
>>>> address space, vast amounts of otherwise unusable areas can
>>>> be used for these "special objects", having very little impact
>>>> on memory usable for actual objects.
>>>
>>> Tim, I'm confused by a little bit of that:
>>>
>>> "just a smidge over one bit"
>>>
>>> I can see how you might point them all to a single place that can't be
>>> read or written, and have safety in case anyone tries to use them.
>>>
>>> I can see that you might have a section of memory with a series of
>>> bytes, each one reserved for these empty allocations. It might be
>>> inaccessible, but will still use address space.
>>>
>>> But how do you get anything smaller than a byte, but non-zero? I've
>>> only ever used one CPU with addressing smaller than a byte.
>>
>> I was tempted to make a joke here, but I couldn't see how to turn
>> out something funny.
>>
>> What I meant was just over one bit /per zero-byte block/. So if
>> there were 20,000 zero-byte blocks, they could be managed with
>> just a little more than 2500 bytes of allocated memory. Sorry
>> for the confusion.
>
> I still don't follow you.
>
> If I realloc to size 0 I get an address back. That can be a unique
> address, in which case each one uses an address, and therefore a byte.
> [...]

In fact it must be a unique address, distinct from any other
address that has been allocated but not yet freed.

The key point is that, when the size is zero, the allocation
routine allocates /address space/ but does not allocate /memory/.
The address is not mapped to any memory, either physical or
virtual.

In a 64-bit address space, there are a lot more addresses than
there are bytes of memory, even virtual bytes of memory. All but
a very small fraction of 64-bit addresses cannot map to actual
memory, because there is no room on the address bus (figuratively
speaking).

For example, suppose our zero byte block reside at addresses
in the range

0x800000000000 to
0x802000000000

and "objects" are aligned to 32-byte boundaries. That means
there are 4294967296 zero-byte "objects" available. For each of
those objects, we need to know if it has been allocated by not
yet freed, that is, one bit per object. Add in a few extra
pointers and counts to manage the space to hold the bitmap
(so we don't have to use much more space for the bitmap than
is necessary), and we get a little over one bit /of actual
memory/ that is used to manage the zero-byte objects, which
take no actual memory.

Does that make more sense now?

On 2023-09-01, Lew Pitcher <lew.pitcher@digitalfreehold.ca> wrote:
> On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:
>
>> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>> What I meant was just over one bit /per zero-byte block/. So if there
>>> were 20,000 zero-byte blocks, they could be managed with just a little
>>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>>
>> The following is a much better requirement for malloc and realloc:
>>
>> In the zero size case, return a non-null pointer to a single
>> program-wide object (always the same one), which can be passed to the
>> free function any number of times.
>>
>> Since a zero sized object doesn't store any information, there is no
>> need to have more than one.
>>
>> We satisfy these requirements:
>>
>> - realloc(x, 0) is effectively free(x), except that it also
>> returns that object.
>>
>> - the non-null object can be passed to library functions whose
>> behavior is not defined for null pointers, provided the functions are
>> not instructed to dereference it, or perform pointer arithmetic.
>
> This last point implies that there must be some way for code to
> distinguish this non-null object (that cannot be dereferenced)
> from other non-null objects that /can/ be dereferenced.

No, it doesn't.

Say we make this pointer:

char x[4], *p = x + 4;

f(p);

p effectively points to the base of a zero length array: one
byte past its last element.

Does f need "some what to distinguish this p value from one that
can bedereferenced"?
>
> Given that you specify that the non-null pointer returned from
> realloc(x,0)
> would be "a single program-wide object" and "always the same one",
> would you consider providing a unique name (like we do for the
> null pointer constant NULL) for such an object?

Tentatively yes. POSIX systems could use the same value as MAP_FAILED
which is typically

#define MAP_FAILED ((void *) -1)

It is sometimes useful to have an additional pointer value that is
not the same as any object, and invalid.

One example is in this source file:

https://www.kylheku.com/cgit/txr/tree/regex.c

Look for casts like coerce(cset_L2_t *, -1). I didn't define
a constant for this.

This code implements a multi-level radix tree structure for
representing Unicode character sets.

A null pointer at any level in the tree indicates that that
section of the space is all zero bits: those code points
under that tree are not in the set. We don't have to allocate
the underying directories and pages just to fill them wit zeros.

I also wanted an efficient way to say that an entire subtree
contains nothing but 1 bits. For that, I used a -1 converted
to the pointer type.

> If so, what name
> would you suggest, and what would the definition look like?

The definition cannot be dictated at the ISO C level;
only its properties can be described.

In some implementation ((void *) -1) might be indistinguishable
from the null pointer; you know the deal.

I'm not conviced that the constant would have to be published just for
the purpose of its connection with malloc(0); it would have to be
considered separately useful.

And even then, it would ahve to be decided whether that constant should
actually be that malloc(0) value, or should that still use its own
value.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> What I meant was just over one bit /per zero-byte block/. So if
>> there were 20,000 zero-byte blocks, they could be managed with
>> just a little more than 2500 bytes of allocated memory. Sorry
>> for the confusion.
>
> The following is a much better requirement for malloc and realloc:
>
> In the zero size case, return a non-null pointer to a single
> program-wide object (always the same one), which can be passed
> to the free function any number of times. [...]

This idea is worse in one important respect: it doesn't satisfy
the specification in the C standard.

Incidentally, it also doesn't satisfy the requirements of the
people who proposed the idea to begin with.

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:
>
>> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> What I meant was just over one bit /per zero-byte block/. So if there
>>> were 20,000 zero-byte blocks, they could be managed with just a little
>>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>>
>> The following is a much better requirement for malloc and realloc:
>>
>> In the zero size case, return a non-null pointer to a single
>> program-wide object (always the same one), which can be passed to the
>> free function any number of times.
>>
>> Since a zero sized object doesn't store any information, there is no
>> need to have more than one.
>>
>> We satisfy these requirements:
>>
>> - realloc(x, 0) is effectively free(x), except that it also
>> returns that object.
>>
>> - the non-null object can be passed to library functions whose
>> behavior is not defined for null pointers, provided the functions are
>> not instructed to dereference it, or perform pointer arithmetic.
>
> This last point implies that there must be some way for code to
> distinguish this non-null object (that cannot be dereferenced)
> from other non-null objects that /can/ be dereferenced.

The idea that zero-byte objects can all be the same doesn't
satisfy the specifications in the C standard.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>Vir Campestris <vir.campestris@invalid.invalid> writes:
>
>
>In a 64-bit address space, there are a lot more addresses than
>there are bytes of memory, even virtual bytes of memory. All but
>a very small fraction of 64-bit addresses cannot map to actual
>memory, because there is no room on the address bus (figuratively
>speaking).

Current processors support between 44 and 52 bits of physical
address, and for the most part, the same on the virtual address
space as well. ARMv8 allows the VA space to be anywhere
from 16 bits to 52 bits on a per-translation-context) basis;
where smaller VA sizes can significantly decrease translation
table walk cost (i.e. by skipping levels).

With DDR5 and HBM we're seeing terabytes of DRAM on the bus.

With CXL (and Intel's PUMA chip) the physical address bus
will be fully utilized (all 64 bits) in the not so distant
future, if perhaps sparsely by using higher order bits to
identify nodes on the fabric.

On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> The idea that zero-byte objects can all be the same doesn't
> satisfy the specifications in the C standard.

yes; we all know are talking about an alternative requiremnt
that is not one of the current two implementation-defined choices.

However, anyone can implement the idea (or others) in an allocator
wrapper.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca