Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!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 18:19:26 +0000
Organization: A little, after lunch
Lines: 78
Message-ID: <viac7e$l1oi$8@dont-email.me>
References: <vhigot$1uakf$1@dont-email.me> <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>
 <vi9ce3$fjo6$7@dont-email.me> <vi9u5l$iego$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 28 Nov 2024 19:19:27 +0100 (CET)
Injection-Info: dont-email.me; posting-host="324bccc9bb11dd88d68685d631659c8b";
	logging-data="689938"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ZWx3LsdPcZgjj3qKJCdlvcWvFLR7G2B8="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:gabRSth7vvWPX5TtpbB6/dD/jzI=
Content-Language: en-GB
In-Reply-To: <vi9u5l$iego$1@dont-email.me>
Bytes: 5384

On 28/11/2024 14:19, Rich wrote:
> The Natural Philosopher <tnp@invalid.invalid> wrote:
>> 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 performance reasons you'd want to maintain some index data
> structure that can be searched faster than O(N), which becomes
> additional overhead for the malloc's and for free.  As well, as Richard
> K.  also says in his posts, just that is not enough to track and ignore
> all double free operations.  Which adds on even more overhead.
> 
Its not hard to do a binary search on an ordered linked list, and its a 
piece if piss to insert to make it ordered


-- 
“it should be clear by now to everyone that activist environmentalism 
(or environmental activism) is becoming a general ideology about humans, 
about their freedom, about the relationship between the individual and 
the state, and about the manipulation of people under the guise of a 
'noble' idea. It is not an honest pursuit of 'sustainable development,' 
a matter of elementary environmental protection, or a search for 
rational mechanisms designed to achieve a healthy environment. Yet 
things do occur that make you shake your head and remind yourself that 
you live neither in Joseph Stalin’s Communist era, nor in the Orwellian 
utopia of 1984.”

Vaclav Klaus