Re: Joy of this, Joy of that

Rich <rich@example.invalid> writes:

The Natural Philosopher <tnp@invalid.invalid> wrote:

Look I don't know how memory allocation and de allocation is done
but my instinct would be to hold a long list of pointers to allocated
blocks.  Possibly in order of the allocated addresses, which would make
allocating a new block a case of finding the first gap in the list that
is [required blocksize] and inserting a new list element, and de
allocation a question of searching the list for a matching allocation,
and deleting it from the list.
 
It would be trivial to get to the end of the list and discover that that
was the end, and, with no match found simply ignore the free call

>
Yes, but now you burden /every/ free(ptr) call with an O(N) linear
search of all allocated blocks to determine if "ptr" has been
previously freed.

Obviously a real implementation would use a faster data structure. But
see my other post for why this idea isn’t enough to solve the
problem. You need either full pointer provenance tracking
(e.g. valgrind, rather slowly), or in-band pointer tagging (e.g. CHERI,
if I understand correctly) or a different allocation model which
eliminates the problem at source (e.g. any number of languages with
automated memory management).

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