Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Competing criteria

Reply
Thread Tools

Competing criteria

 
 
Ark
Guest
Posts: n/a
 
      10-23-2011


On 10/22/2011 6:20 PM, Richard Damon wrote:
> On 10/22/11 5:33 PM, Ark wrote:
>>
>>
>> On 10/22/2011 4:47 PM, Richard Damon wrote:

>
>>>
>>> As I mentioned last night, that isn't totally true. It can be generally
>>> considered safe to do heap allocation during initial startup (for
>>> buffers that will then live forever, perhaps handed out and collected
>>> with allocation functions.
>>>
>>> While in principle, it would normally be possible to rewrite all the
>>> code that uses the heap to use statically allocated buffers, this often
>>> forces details of implementation to leak out, especially of objects that
>>> need internal buffers that can't be fixed in size over all uses.
>>>
>>> It can also be acceptable to heap allocations for non-critical
>>> operations that are allowed to fail or be postponed for arbitrary
>>> periods of time. These allocations should be for a limited period of
>>> time, and it is desirable for there to be occasional times when most of
>>> these are all released at the same time to let the heap defragment.

>>
>> IOW, malloc() can be (made) more or less benign but free() is totally
>> unacceptable.
>> Which is not totally true either.
>> If memory serves me right, there are allocation algorithms that
>> guarantee to succeed if the contiguous memory pool is "only" twice as
>> large as the max you need at any given time. Of course if you already
>> know what this max is, you can probably do better w.r.t. memory
>> resources.
>> OTOH, for any allocation algorithm there is a pattern of
>> allocations/deallocations which would fatally fragment the pool (aka
>> heap), in the sense that enough total memory is available but it is not
>> contiguous
>> - Ark

>
> The rule I always use is a task is not allowed to fail, then it can't
> call on anything that might fail. malloc, in general, has the
> possibility to fail so needs to be avoided in tasks that can not fail.
>
> free() is actually always safe, as free can never fail, and can never
> cause another malloc to fail. What can get you in trouble is to free a
> resource that you will need in the future, as after you free a memory
> block, you can't be sure you can get it back until every block allocated
> after it is freed too (based on normal heap rules).
>
> While, as you say, there are patterns of allocations and deallocations
> that fragment the heap, the rule that allocations (after the startup
> code) are be of short/finite duration is designed it prevent those bad
> patterns. Also, the goal to have periods of time when you free most of
> the short term usage also minimizes how bad fragmentation gets.


I don't think we disagree on anything.
By "free() is evil" I mean that a pattern of pre-allocating on start-up
is fine (but doesn't buy you anything if you don't care about keeping
the types opaque); anything else is risky.
<OT>
I believe the idea of malloc was driven by use cases of non-interactive
programs that run and end, whether succeeding or failing. I mean, like
grep. For a program that starts and never ends, be it an embedded
freestanding program or hosted service/daemon, malloc /interface/ is
suited exceptionally poorly. An intermediate group is indeterminately
long interactive programs, like office applications - but they, as we
know, *are* allowed to fail
</OT>
- Ark
 
Reply With Quote
 
 
 
 
Joachim Schmitz
Guest
Posts: n/a
 
      10-23-2011
io_x wrote:
> "Richard Damon" <(E-Mail Removed)> ha scritto nel
> messaggio news:j7vfkc$goj$(E-Mail Removed)...
>> On 10/22/11 5:33 PM, Ark wrote:
>> The rule I always use is a task is not allowed to fail, then it
>> can't call on anything that might fail. malloc, in general, has the
>> possibility to fail so needs to be avoided in tasks that can not
>> fail. free() is actually always safe, as free can never fail, and can
>> never cause another malloc to fail.

>
> i think some free() function can fail in the wrost way


Indeed free() can fail if cou give something not NULL which hasn't come from
malloc(), calloc() or realloc() or had been free()'d already, in which case
undefined behavoir occurs (and free() doesn't have means to report an error)

From a Linux man-page:
free() frees the memory space pointed to by ptr, which must have been
returned by a previous call to malloc(), calloc() or realloc(). Otherwise,
or if free(ptr) has already been called before, undefined behaviour occurs.
If ptr is NULL, no operation is performed.



Bye, Jojo

 
Reply With Quote
 
 
 
 
Willem
Guest
Posts: n/a
 
      10-23-2011
Joachim Schmitz wrote:
) io_x wrote:
)> "Richard Damon" <(E-Mail Removed)> ha scritto nel
)> messaggio news:j7vfkc$goj$(E-Mail Removed)...
)>> On 10/22/11 5:33 PM, Ark wrote:
)>> The rule I always use is a task is not allowed to fail, then it
)>> can't call on anything that might fail. malloc, in general, has the
)>> possibility to fail so needs to be avoided in tasks that can not
)>> fail. free() is actually always safe, as free can never fail, and can
)>> never cause another malloc to fail.
)>
)> i think some free() function can fail in the wrost way
)
) Indeed free() can fail if cou give something not NULL which hasn't come from
) malloc(), calloc() or realloc() or had been free()'d already, in which case
) undefined behavoir occurs (and free() doesn't have means to report an error)

IOW: free() can only fail if there is a programming error.
OTOH: malloc() can fail because of external circumstances.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      10-23-2011
On Oct 23, 10:06*am, "Joachim Schmitz" <nospam.j...@schmitz-
digital.de> wrote:
> io_x wrote:
> > "Richard Damon" <(E-Mail Removed)> ha scritto nel
> > messaggionews:j7vfkc$goj$(E-Mail Removed)...
> >> On 10/22/11 5:33 PM, Ark wrote:
> >> The rule I always use is a task is not allowed to fail, then it
> >> can't call on anything that might fail. malloc, in general, has the
> >> possibility to fail so needs to be avoided in tasks that can not
> >> fail. free() is actually always safe, as free can never fail, and can
> >> never cause another malloc to fail.

>
> > i think some free() function can fail in the wrost way

>
> Indeed free() can fail if cou give something not NULL which hasn't come from
> malloc(), calloc() or realloc() or had been free()'d already, in which case
> undefined behavoir occurs (and free() doesn't have means to report an error)
>
> From a Linux man-page:
> free() frees the memory space pointed to by ptr, which must have been
> returned by a previous call to malloc(), calloc() or realloc(). Otherwise,
> or if free(ptr) has already been called before, undefined behaviour occurs.
> If ptr is NULL, no operation is performed.


I wouldn't call this a failure on free()'s part. Essentially free()'s
pre-condition has been violated. The caller is the failure.
 
Reply With Quote
 
Richard Damon
Guest
Posts: n/a
 
      10-23-2011
On 10/23/11 8:29 AM, Eric Sosman wrote:
> On 10/22/2011 6:20 PM, Richard Damon wrote:
>> [...]
>> The rule I always use is a task is not allowed to fail, then it can't
>> call on anything that might fail. malloc, in general, has the
>> possibility to fail so needs to be avoided in tasks that can not fail.

>
> You may be using "fail" too broadly. Yes, malloc() can "fail" in
> the sense that it reserves no memory. But malloc() does not then abort
> the program or something equally drastic; it returns NULL to inform the
> caller of the outcome and allow the caller to take action as appropriate
> in the context. If the caller (and the caller's callers) cannot proceed
> without the reserved memory, perhaps the program will then "fail" -- but
> this is not an inevitable outcome when malloc() "fails."
>
> If getenv("FAILURE_OPTION") returns NULL, is that a "failure?"
>
> If strchr(string, '?') returns NULL, is that a "failure?"
>
> If fopen("nonsuch.txt", "r") returns NULL, is that a "failure?"
>
> Depending on the structure and needs of the program, the answers
> could be any combination of "Yes," "No," and "It's complicated." The
> same goes for malloc().
>


The simple answer is use the same definition of fail in the two places.
If the task isn't allowed to fail by aborting, but can say "can't do
it", then it can't call things that abort but can call things like
malloc which may return a "can't do it" response (as long as you check
for them and don't assume it gave you the memory). More commonly failure
is an inability to do the task requested. As you examples show,
sometimes what that really means is dependent on context.

As most guideline rules, it is stated in the simple, easy to remember
format, not with all the appended legalese about unusual conditions and
exemptions. As an example, a task that must complete, might be able to
call malloc for a buffer, if the task has a suitable alternative that it
can fall back on if the malloc returns no buffer, for example, maybe it
has a buffer kept in reserve, that it can use in emergencies, but when
it falls back on that, it sends out a notice that it may not be able to
handle any more traffic (allowing future requests to fail).


 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      10-23-2011
On Oct 23, 3:15*pm, Richard Damon <(E-Mail Removed)>
wrote:
>
> if the task has a suitable alternative that it
> can fall back on if the malloc returns no buffer,
>

People discuss this quite a bit. Technically it's often possible to
use a less memory-hungry algorithm if malloc() fails. However it's
almost never done in real code, because it means programs become much
more difficult to write and to test.
--
Basic algorithms. JPEG compressor/decompressor.
http://www.malcolmmclean.site11.com/www

 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      10-24-2011
On 2011-10-22, Roberto Waltman <(E-Mail Removed)> wrote:
> Seebs wrote:
>> the canonical
>>solution to "not heap allocation" is to define a reasonable maximum count
>>of simultaneous objects, statically allocate them, and then basically
>>write your own mini-allocator that keeps track of which ones you're using.
>>This, you will note, is probably stupid.


> Far from being stupid, that is the only way you can guarantee that
> memory allocation will not fail due to memory fragmentation, in
> systems with limited resources, no virtual memory and that must run
> 24/7.


True, but it doesn't prevent memory allocation from failing due to a lack
of resources. So you still have to deal with memory allocation failures.

And given a choice between rare failures due to fragmentation, and frequent
failures due to poor choice of static limits...

-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
Markus Wichmann
Guest
Posts: n/a
 
      10-24-2011
On 23.10.2011 15:24, Malcolm McLean wrote:
> On Oct 23, 3:15 pm, Richard Damon <(E-Mail Removed)>
> wrote:
>>
>> if the task has a suitable alternative that it
>> can fall back on if the malloc returns no buffer,
>>

> People discuss this quite a bit. Technically it's often possible to
> use a less memory-hungry algorithm if malloc() fails. However it's
> almost never done in real code, because it means programs become much
> more difficult to write and to test.


It also means to write more code, some of which is almost never going to
get used... I mean, it would be like writing a program so that it runs
both on systems with an FPU and without: You basically have to write it
twice. It is almost always simpler to just say "Buy an FPU!" or "Buy
more RAM or enlarge the swap file!"

> --


The correct separator would be dash-dash-space-newline, you are missing
the space.

HTH,
Markus
 
Reply With Quote
 
Richard Damon
Guest
Posts: n/a
 
      10-24-2011
On 10/24/11 4:10 PM, Seebs wrote:
> On 2011-10-22, Roberto Waltman<(E-Mail Removed)> wrote:
>> Seebs wrote:
>>> the canonical
>>> solution to "not heap allocation" is to define a reasonable maximum count
>>> of simultaneous objects, statically allocate them, and then basically
>>> write your own mini-allocator that keeps track of which ones you're using.
>>> This, you will note, is probably stupid.

>
>> Far from being stupid, that is the only way you can guarantee that
>> memory allocation will not fail due to memory fragmentation, in
>> systems with limited resources, no virtual memory and that must run
>> 24/7.

>
> True, but it doesn't prevent memory allocation from failing due to a lack
> of resources. So you still have to deal with memory allocation failures.
>
> And given a choice between rare failures due to fragmentation, and frequent
> failures due to poor choice of static limits...
>
> -s


If you have frequent failures, you didn't set your static limits
correctly. To do the static preallocations, you need to do analysis. You
need to define what is allowed to be active at any given time, an make
sure you have sufficient resources statically allocated to meet that
demand. if you can't do the analysis, you can't make the performance
guarantee. If you can't preallocate sufficient buffers to meet that
demand, you need to do one of the following:

1) Find a way to do some of the jobs with less memory.
2) Add more memory to the system.
3) Reduce the required guaranteed performance

If you switch to a dynamic allocation system, it is virtually impossible
to really guarantee a performance level, and it can look really bad for
you to have a device whose performance deteriorates over time and
requires periodic reboots to keep it working up to spec.

To have a allocation failure, because you are operating beyond your
spec, is NOT a system failure, it should be allowable for you to refuse
to process that request.

If you have some memory left over, you might want to switch to making a
heap request when your preallocated buffers are exhausted, in this case
since you are now allowed to fail, you are ok. When done, you should
know that THIS buffer should be returned to the heap and not one of the
other preallocated buffer to avoid heap fragmentation (and depending on
how you did it, the preallocated buffers may not have come from the heap).

Note, that it might be possible that you know that the system goes into
different "modes" where the types of buffers needed are different. This
can make preallocation a bit harder, but judicious use of unions can
often solve this. To the degree that you can't preallocate as
efficiently as you think you might be able to use the heap, consider
that the cost for getting the guarantee. To really be sure the heap will
work would add a LOT of stress testing and analysis, and even then there
will be some doubt. One way to think about it, which car would you buy,
the one guaranteed to be able to get up to 70 mph, and if conditions are
good a bit beyond that, or the car that if conditions are right will
surpass 100 mph, but they can't be sure if there might be cases, even
somewhat rare (like maybe driving for a few hours), where it will only
hit 45 mph. If I plan to be driving on the highway, I don't think I
would want that second car. It may even "on average" go faster, but when
I want the performance, I want it. In the same way, if I buy a system
with a spec, I want it to meet the spec, not occasionally come up short
needing a reboot to clear up its memory fragmentation.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      10-25-2011
Markus Wichmann <(E-Mail Removed)> writes:
> On 23.10.2011 15:24, Malcolm McLean wrote:

[...]
>> --

>
> The correct separator would be dash-dash-space-newline, you are missing
> the space.


You can thank Google Groups for that.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
competing applications and subapplications BriC ASP .Net 0 12-22-2006 05:05 AM
Microsoft Has Stopped Competing with Linux Au79 Computer Support 2 03-23-2006 02:35 PM
Overview of competing Python modules? Thorsten Kampe Python 2 09-16-2004 09:20 PM
SVG: competing dynamic graphic generating modalities BMM XML 0 05-05-2004 09:34 PM
CSS background competing selectors question Derek Clarkson HTML 3 11-07-2003 12:08 AM



Advertisments