Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: The Natural Philosopher <tnp@invalid.invalid>
Newsgroups: comp.os.linux.misc
Subject: Re: Joy of this, Joy of that
Date: Thu, 28 Nov 2024 09:16:51 +0000
Organization: A little, after lunch
Lines: 58
Message-ID: <vi9ce3$fjo6$7@dont-email.me>
References: <vhigot$1uakf$1@dont-email.me>
 <wwvjzcu1chd.fsf@LkoBDZeT.terraraq.uk> <vhtide$1s5d5$8@dont-email.me>
 <wwvmshodcjt.fsf@LkoBDZeT.terraraq.uk> <vi01qi$2cic3$1@dont-email.me>
 <wwvmshnlmhm.fsf@LkoBDZeT.terraraq.uk> <vi2rat$318ah$4@dont-email.me>
 <wwviksav1i7.fsf@LkoBDZeT.terraraq.uk> <vi5e6t$3k9sn$1@dont-email.me>
 <O5u1P.72795$OVd1.12914@fx10.iad> <vi5tpb$3medq$3@dont-email.me>
 <vi71te$3vogk$11@dont-email.me> <vi7hl6$2snk$1@dont-email.me>
 <vi7kdc$3793$7@dont-email.me> <vi7q5f$4jlo$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 28 Nov 2024 10:16:52 +0100 (CET)
Injection-Info: dont-email.me; posting-host="324bccc9bb11dd88d68685d631659c8b";
	logging-data="511750"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/uAL7XOGSulBE0ps3dbNvBcnGu+cR3sIo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:YUJA7p/oBP5eP9tJuRTlv32fdpE=
Content-Language: en-GB
In-Reply-To: <vi7q5f$4jlo$1@dont-email.me>
Bytes: 4051

On 27/11/2024 18:58, Rich wrote:
> The Natural Philosopher <tnp@invalid.invalid> wrote:
>> On 27/11/2024 16:33, Rich wrote:
>>> The Natural Philosopher <tnp@invalid.invalid> wrote:
>>>> On 27/11/2024 01:48, Rich wrote:
>>>>> The only two guarantees given in that paragraph are:
>>>>>
>>>>> 1) if ptr was returned by one of the malloc's, the space referenced by
>>>>>       ptr is deallocated (albeit only for the first call of free(ptr), per
>>>>>       the second sentence);
>>>>> and
>>>>> 2) if ptr is NULL, nothing occurs.
>>>>
>>>> Exactly.  The result of anything else is implementation dependent on the
>>>> library.
>>>>
>>>> One might write a free that says 'look at our list of allocated blocks,
>>>> compare with the pointer and if no match do nothing'
>>>>
>>>> Or one that says  'look at our list of allocated block compare with the
>>>> pointer and if no match, segfault'
>>>>
>>>> I am not au fait with the internal of 'free()' so I cannot comment as to
>>>> why the first is not always the case.
>>>
>>> I can hazzard a guess.  The time taken to perform the search, or the
>>> effort needed to maintain an "index structure" to perform an optimized
>>> search, plus the time for the optimized search, was felt to be
>>> excessive and wasteful when the "spec" says "don't ever do this".
>>>
>>
>> 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.  With today's CPU's one could be excused in thinking
> "not such a big deal".  In the days of a PDP-11 or VAX-11/780 CPU
> performance levels, doing an O(N) linear search, on every call to free,
> to catch something the programmer was never supposed to do in the first
> place, was likely viewed as too much overhead.
> 
How else would you do it?

-- 
For every complex problem there is an answer that is clear, simple, and 
wrong.

H.L.Mencken