From Newsgroup: comp.arch

According to Tim Rentsch <tr.17687@z991.linuxsc.com>:

Once there is a way to get additional memory from whatever underlying >environment is there, malloc() and free() can be implemented (and I
believe most often are implemented) without needing to compare
pointers. Note: pointers can be tested for equality without having
to compare them relationally, and testing pointers for equality is >well-defined between any two pointers (which may need to be converted
to 'void *' to avoid a type mismatch).

I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the
pointers.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

According to Tim Rentsch <tr.17687@z991.linuxsc.com>:

Once there is a way to get additional memory from whatever underlying >>environment is there, malloc() and free() can be implemented (and I
believe most often are implemented) without needing to compare
pointers. Note: pointers can be tested for equality without having
to compare them relationally, and testing pointers for equality is >>well-defined between any two pointers (which may need to be converted
to 'void *' to avoid a type mismatch).

I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the
pointers.

Assuming the malloc implementation associates metadata with the
allocation (e.g. in bytes either before the returned pointer or
after the allocation), the comparision for consolidation should
always be standard supported equality comparisons.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.arch

According to Scott Lurndal <slp53@pacbell.net>:

I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the
pointers.

Assuming the malloc implementation associates metadata with the
allocation (e.g. in bytes either before the returned pointer or
after the allocation), the comparision for consolidation should
always be standard supported equality comparisons.

I've seen allocators that sort the free list. And then there's
other approches like buddy allocators that futz directly with
the address bits.

You probably could write a malloc/free that worked without doing
anything other than equality comparisons but I doubt it would be a
very good ones. The real ones I've seen also have tons of defensive
compares to try to check for pointer smashing.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

According to Scott Lurndal <slp53@pacbell.net>:

I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the >>>pointers.

Assuming the malloc implementation associates metadata with the
allocation (e.g. in bytes either before the returned pointer or
after the allocation), the comparision for consolidation should
always be standard supported equality comparisons.

I've seen allocators that sort the free list. And then there's
other approches like buddy allocators that futz directly with
the address bits.

You probably could write a malloc/free that worked without doing
anything other than equality comparisons but I doubt it would be a
very good ones. The real ones I've seen also have tons of defensive
compares to try to check for pointer smashing.

It's really an academic question. Very few useful C programs have ever
been written in pure standard C. 'cat' perhaps? checks Unixware's
cat.c; not portable - it uses 'fstat', 'read' and 'write'.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

According to Tim Rentsch <tr.17687@z991.linuxsc.com>:

Once there is a way to get additional memory from whatever underlying
environment is there, malloc() and free() can be implemented (and I
believe most often are implemented) without needing to compare
pointers. Note: pointers can be tested for equality without having
to compare them relationally, and testing pointers for equality is
well-defined between any two pointers (which may need to be converted
to 'void *' to avoid a type mismatch).

I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the
pointers.

It might seem that way, but it isn't so. There is a fairly
straightforward scheme -- using a single address-sized cell
before each memory block -- that consolidates adjacent free
chunks and maintains free lists, without needing to compare
pointers (and in fact doesn't use pointers at all except for the
free lists). Doing a malloc() needs to search an appropriate
free list for an adequately large free block, and is constant
time thereafter; doing a free() uses constant time, including
consolidation of adjacent free chunks. For an implementation
with 8-byte addresses, this can be done with a grain size of 16
bytes and a minimum of 32-byte blocks (of which 24 bytes can be
used by the client). Coincidentally (or not) that matches the
sizes I see in tests done on an Ubuntu Linux system (any size
less than 25 uses 32 bytes, any size less than 41 uses 48 bytes,
etc).

The key insight is to use the preceding memory word to hold the
size of this block plus two bits: bit A is one if this block is
not free, and bit B is one if the previous block is not free. If
bit B is zero (so the previous block is free) then the last word
of the previous block holds the size of that block. Free lists
are maintained using the first two words in each free block (of
course plus the list headers, which is a small fixed overhead).
This information is enough to combine adjacent free blocks when a
free() is done.
--- Synchronet 3.20a-Linux NewsLink 1.114