On 2024-01-21, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> 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.

Welcome to C23! free_sized(malloc(42), 73) -> UB.

--
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 21/01/2024 21:49, Kaz Kylheku wrote:
> On 2024-01-21, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> 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.
>
> Welcome to C23! free_sized(malloc(42), 73) -> UB.
>

I've used such a sized free function in my own libraries for a long time.

Yes, you can pass the wrong size (although there are debugging options
where it will keep track of the sizes and double-check, if you suspect
such a bug).

But the real problems are the same as they are now in C:

free(p) when p has not been assigned a value from malloc
free(p); free(p); call twice
--- forget to call free
free(q); free the wrong pointer
free(p+1); pass an invalid pointer

Getting a p=malloc() correctly matched up with just one free(p) in a
different part of the program, at a different time, is the hard bit.

The easy bit is this:

p = malloc(sizeof(*p));
...
free_sized(p, sizeof(*p));

(Is it still malloc or is there a malloc_sized? Since part of the point
is not wasting time and memory managing that extra metadata.)

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

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

It's trivial to fix that problem: simply require implementations
to define a preprocessor symbol about how the implementation
works. Problem solved.

(There are other instances of implementation-defined behavior
that would benefit from analogous changes along these lines.)

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

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

I don't agree that they can't be distinguished in _any_ portable
way.

I suppose a case could be made that they can't be distinguished in
any _convenient_ portable way. But that's not the same as _any_
portable way.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> 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.
>
> It's trivial to fix that problem: simply require implementations
> to define a preprocessor symbol about how the implementation
> works. Problem solved.
>
> (There are other instances of implementation-defined behavior
> that would benefit from analogous changes along these lines.)

I tend to agree that such a preprocessor symbol would be an improvement.

I still think, as I wrote above, that removing the permission to return
a null pointer on a successful zero-sized allocation would be a greater
improvement.

A preprocessor symbol makes it easier for programmers to work around the
potential difference between implementations. The change I advocate
would make it completely unnecessary.

Except, of course, that most code would still have to allow for pre-C26
behavior, even if the change were adopted in C26. That's unavoidable in
the absence of time machines. On the gripping hand, since it seems that
most existing implementations (well, all of the few I've tried) return a
non-null pointer for malloc(0), it might be reasonable to ignore the few
pre-C26 implementations that return a null pointer.

--
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 22:09, bart wrote:
> On 21/01/2024 21:49, Kaz Kylheku wrote:
>> On 2024-01-21, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>>> 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.
>>
>> Welcome to C23! free_sized(malloc(42), 73) -> UB.
>>
>
> I've used such a sized free function in my own libraries for a long time.
>
> Yes, you can pass the wrong size (although there are debugging options
> where it will keep track of the sizes and double-check, if you suspect
> such a bug).
>
> But the real problems are the same as they are now in C:
>
>    free(p)           when p has not been assigned a value from malloc
>    free(p); free(p); call twice
>    ---               forget to call free
>    free(q);          free the wrong pointer
>    free(p+1);        pass an invalid pointer
>
> Getting a p=malloc() correctly matched up with just one free(p) in a
> different part of the program, at a different time, is the hard bit.
>
> The easy bit is this:
>
>     p = malloc(sizeof(*p));
>     ...
>     free_sized(p, sizeof(*p));
>
> (Is it still malloc or is there a malloc_sized? Since part of the point
> is not wasting time and memory managing that extra metadata.)
>
The thing is you have to be disciplined. I have a fairly strict rule
that either alloaction and free must be in the same function, or if a
function returns a structure that needs to be operated on, there is a
constructor which sets it up in a valid state and a matching destructor
(I always use the prefix kill, though a colleague who had been in the
military objected because it reminded him too much of the army).

One difficulty is when you pass up an allocatred pointer which is not to
a custom structure, eg from strdup(). So you have to break the rule and
treat the strdup call as though it were a call to malloc. Then rarely
you have graph like structures which add and subtract nodes. So you
isolate the code that adds or subtracts the node, and set up the whole
thing in a valid (but maybe empty) state in one call, and destroy the
whole thing in another. But you can't keep to the rule that each
addition of a node will be matched by a freeing of the node in the same
function.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

On 1/21/2024 12:34 PM, 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.
>

Why?

On 1/21/2024 12:54 PM, 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.  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.)
>

Think of a block of memory aligned on a very large boundary, and padded
up to a boundary size. So, we free take take its address, round down to
a boundary and get at a header...

On 1/21/2024 5:05 PM, Chris M. Thomasson wrote:
[...]
> Think of a block of memory aligned on a very large boundary, and padded
> up to a boundary size. So, we free take take its address, round down to
> a boundary and get at a header...

God damn typos!

free takes its address, rounds down to a boundary, and can get at a
header structure.

This works fine if we make sure if we take alignment and a large
boundary into account. Basically, we need each allocation to be at least
be as large as a word/pointer if you will. This pointer is used for a
linked list in the header, that sits on alignment boundaries.

On 1/21/2024 1:16 PM, Kaz Kylheku wrote:
> 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.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Right!

On 22/01/2024 01:04, Chris M. Thomasson wrote:
> On 1/21/2024 12:34 PM, 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.
>>
>
> Why?
It depends how malloc is implemented.
But the traditional way, using a contiguous pool and a linked list of
free blocks, each allocation is for a fixed number of units the same
size as the header, and you need to know how many units are in the block
to add it to the free list on deallocation, and also for
defragmentation. So the header is a pointer to the next free block plus
a size.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

On 1/21/2024 6:05 PM, Malcolm McLean wrote:
> On 22/01/2024 01:04, Chris M. Thomasson wrote:
>> On 1/21/2024 12:34 PM, 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.
>>>
>>
>> Why?
> It depends how malloc is implemented.
> But the traditional way, using a contiguous pool and a linked list of
> free blocks, each allocation is for a fixed number of units the same
> size as the header, and you need to know how many units are in the block
> to add it to the free list on deallocation, and also for
> defragmentation. So the header is a pointer to the next free block plus
> a size.

Think of free rounding a block down to a large boundary, where access to
a header is right there...

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> It's trivial to fix that problem: simply require implementations
>> to define a preprocessor symbol about how the implementation
>> works. Problem solved.
>>
>> (There are other instances of implementation-defined behavior
>> that would benefit from analogous changes along these lines.)
>
> I tend to agree that such a preprocessor symbol would be an improvement.
>
> I still think, as I wrote above, that removing the permission to
> return a null pointer on a successful zero-sized allocation would be a
> greater improvement.

Fully agreed. That permission has been grit in the gears for a very long
time, for much of which I had the misfortune of having to deal with it
in real life thanks to IBM’s bad decisions.

Fixing it would have been, what, a 2-line change to the impacted
implementations, but apparently it’s better for all the users to deal
with the consequences instead.

> A preprocessor symbol makes it easier for programmers to work around the
> potential difference between implementations. The change I advocate
> would make it completely unnecessary.
>
> Except, of course, that most code would still have to allow for pre-C26
> behavior, even if the change were adopted in C26. That's unavoidable in
> the absence of time machines. On the gripping hand, since it seems that
> most existing implementations (well, all of the few I've tried) return a
> non-null pointer for malloc(0), it might be reasonable to ignore the few
> pre-C26 implementations that return a null pointer.

“Reasonable” isn’t really relevant (at least in my working environment):
either my code has to run on such implementations or it doesn’t.

--
https://www.greenend.org.uk/rjk/

On 21/01/2024 22:20, Kaz Kylheku wrote:
> 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.
>

I hadn't noticed that addition in C23 - I'll look it up.

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

It would be a lot more efficient if the sized free was matched with an
appropriate malloc - if malloc() still has to track the size somewhere
in case the user calls free() instead of free_sized(), the gains are
much less.

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

On 21/01/2024 22:31, Keith Thompson wrote:
> 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.
>

Sure. But that's part of the fun of C :-)

Many calls to malloc are of the form :

p = malloc(sizeof(*p));

so freeing them with :

free_sized(p, sizeof(*p));

should not be a significant risk.

There are circumstances where you'd have to track the size as well, and
there is then plenty of scope for mistakes.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> 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 ... */

Of course that’s what the cautious programmer must do practice. But in
terms of the total cost (over all users, implementers, etc) fixing the
definitions of memcpy/memset/etc (as well as malloc) would have been the
better answer.

Standard C is trying to have its own cake and eat it here: 0-sized
allocations can be represented by null pointers when it’s malloc, but
not when it’s memcpy.

--
https://www.greenend.org.uk/rjk/

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. That will take up some space even when
> malloc(0) is called, if NULL is not being returned.

The alternative is making a rod for the back of every single caller
(i.e. all consumers must track allocation sizes). I think the design of
malloc got this one right.

--
https://www.greenend.org.uk/rjk/

On 22/01/2024 10:22, Richard Kettlewell wrote:
> 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. That will take up some space even when
>> malloc(0) is called, if NULL is not being returned.
>
> The alternative is making a rod for the back of every single caller
> (i.e. all consumers must track allocation sizes).

Not at all. Let's first emulate a pair of functions where the caller is
expected to remember the size:

void* malloc_s (size_t n) {return malloc(n);}
void free_s (void* p, size_t n) {free(p);}

Then a typical alloc/dealloc sequence might look like this:

typedef struct {int d,m,y;}Date;
Date* p;

p=malloc_s(sizeof(*p));
...
free_s(p, sizeof(*p));

Is that particularly onerous? If you have a fixed-size object like a
struct, then you will always know its size.

For variable-sized objects, then yes you need to keep a record of the
size, but the chances are you have to do that anyway. For example to be
able to iterate over that dynamic array.

But if you really wanted (for example when allocating variable length,
zero-terminated strings), you can write a couple of wrappers around
malloc_s and free_s to emulate what malloc and free provide in terms of
not needing to remember the allocation size:

typedef long long int i64;

void* malloc2(i64 n) {
void* p;

p=malloc_s(n+sizeof(i64));
if (p==NULL) return NULL;
*((i64*)p) = n;
return (char*)p+sizeof(i64);
}

void free2(void* p) {
i64* q = (i64*)((char*)p-sizeof(i64));
i64 size = *q;

free_s(q, *q);
}

Untested code, it's to demonstrate what's involved: you ask for an
allocation 8 bytes bigger, use the 8 bytes at the beginning to store the
size, and return a pointer to just after those 8 bytes. (I'm assuming
8-byte alignment will suffice.)

Now you can do this:

p=malloc2(sizeof(*p));
...
free2(p);

> I think the design of malloc got this one right.

I think it got it wrong. Now everyone is lumbered with an allocation
scheme that will ALWAYS have to store the size of that struct, perhaps
taking as much space as the struct itself.

Imagine allocating 100M of those structs, and also storing 100M copies
of sizeof(Date) or whatever metadata is needed.

Getting around that, by writing your own small-object allocator on top
of malloc, is a lot harder that adding your own size-tracking on top of
a malloc that does not store any extra data. As I've shown.

(This is also a scheme where, if a user needs to get the size of an
allocation block, it can do so:

i64 size_s(void* p) {
i64* q = (i64*)((char*)p-sizeof(i64));
return *q;
}

But this will be the requested size not the capacity of the allocated
block. That would depend on how malloc_s/free_s are implemented.)

On 22/01/2024 01:04, Chris M. Thomasson wrote:
> On 1/21/2024 12:34 PM, 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.
>>
>
> Why?

Try writing an allocator with zero memory overheads that doesn't spend
all its time on trying to deduce the extend of the block being allocated.

Apparently, 'malloc' on my machines doesn't know about such techniques,
because if I run this program:

enum {n=1024};
char* lastp = malloc(n);
char* p;

for(int i=0; i<10; ++i) {
p=malloc(n);
printf("%p %d\n", p, p-lastp);
lastp=p;
}

Then on Windows I might get:

0000026d06d15b30 18288
0000026d06d15f40 1040
0000026d06d16350 1040
0000026d06d16760 1040
0000026d06d16b70 1040
0000026d06d16f80 1040
0000026d06d17390 1040
0000026d06d177a0 1040
0000026d06d17bb0 1040
0000026d06d17fd0 1056

Some odd results, but generally it uses 16 bytes more than 1024. If I
run it under WSL, the same thing. Also on rextester.com.

You're saying it should be only 1024 bytes that are occupied? OK, tell
the authors of these various mallocs that.

BTW if I run this program (in my language which uses an allocator that
requires a size to free):

const n=1024
ref byte p:=pcm_alloc(n), lastp

to 10 do
p:=pcm_alloc(n)
println p, p-lastp
lastp:=p
od

I get these results:

02E2D440 1024
02E2D840 1024
02E2DC40 1024
02E2E040 1024
02E2E440 1024
02E2E840 1024
02E2EC40 1024
02E2F040 1024
02E2F440 1024
02E2F840 1024

Unless I use a bigger N, since then it switches to using malloc, and I
get similar results to above. But the overheads then are less significant.

On 22/01/2024 11:55, bart wrote:

>
> BTW if I run this program (in my language which uses an allocator that
> requires a size to free):
>
>     const n=1024
>     ref byte p:=pcm_alloc(n), lastp

(p and lastp are declared in the wrong order. The results shown are from
the fixed version.)

> I get these results:
>
> 02E2D440 1024
> 02E2D840 1024
....

(If I compile to an .obj file, which enables high-memory code, and link
using gcc, then it will show the bigger addresses like the C, but still
with 1024-byte allocations.)

On 21/01/2024 12:04, Tim Rentsch wrote:
> 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.
No, because it's natural to write

employees = malloc(Nemployees * sizeof(EMPLOYEE));
if (!employees)
goto out_of_memory;

You don't want to have to special case Nemployees == 0.

--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

Richard Kettlewell <invalid@invalid.invalid> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>> It's trivial to fix that problem: simply require implementations
>>> to define a preprocessor symbol about how the implementation
>>> works. Problem solved.
>>>
>>> (There are other instances of implementation-defined behavior
>>> that would benefit from analogous changes along these lines.)
>>
>> I tend to agree that such a preprocessor symbol would be an improvement.
>>
>> I still think, as I wrote above, that removing the permission to
>> return a null pointer on a successful zero-sized allocation would be a
>> greater improvement.
>
> Fully agreed. That permission has been grit in the gears for a very long
> time, for much of which I had the misfortune of having to deal with it
> in real life thanks to IBM’s bad decisions.

Can you expand on "IBM's bad decisions"?

[...]

--
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 */

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On 21/01/2024 12:04, Tim Rentsch wrote:
>> 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.
> No, because it's natural to write
>
> employees = malloc(Nemployees * sizeof(EMPLOYEE));
> if (!employees)
> goto out_of_memory;
>
> You don't want to have to special case Nemployees == 0.

There are three scenarios being considered.

1. malloc(0) always returns a null pointer.
2. All malloc(0) calls return the same non-null pointer, perhaps to a
single pre-allocated object.
3. malloc(0) acts like malloc(1), returning a null pointer only if
memory has been exhausted.

Implementations currently choose between 1 and 3; 2 would be
non-conforming. Kaz suggested allowing (or requiring?) 2. (I advocate
requiring 3, which is the current behavior of all the implementations
I've tried.)

Tim is talking about scenario 2, wh

--
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 */

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On 21/01/2024 12:04, Tim Rentsch wrote:
>> 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.
> No, because it's natural to write
>
> employees = malloc(Nemployees * sizeof(EMPLOYEE));
> if (!employees)
> goto out_of_memory;
>
> You don't want to have to special case Nemployees == 0.

[Ignore my previous followup. I accidentally posted it before I
finished writing it.]

There are three scenarios being considered.

1. malloc(0) always returns a null pointer.
2. All malloc(0) calls return the same non-null pointer, perhaps to a
single pre-allocated object.
3. malloc(0) acts like malloc(1), returning a null pointer only if
memory has been exhausted.

Implementations currently choose between 1 and 3; 2 would be
non-conforming. Kaz suggested allowing (or requiring?) 2. (I advocate
requiring 3, which is the current behavior of all the implementations
I've tried.)

Tim is talking about scenario 2. Your code sample would work correctly
in that scenario.

--
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 */

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>On 21/01/2024 12:04, Tim Rentsch wrote:
>> 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.
>No, because it's natural to write
>
>employees = malloc(Nemployees * sizeof(EMPLOYEE));
>if (!employees)
> goto out_of_memory;
>
>You don't want to have to special case Nemployees == 0.

I see no problem in special casing it.