Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #14113 > unrolled thread

malloc

Back to article view | Back to comp.lang.c++

Contents

  malloc jgk@panix.com (Joe keane) - 2012-02-16 21:04 +0000
    Re: malloc Devil with the China Blue Dress <chine.bleu@yahoo.com> - 2012-02-16 13:21 -0800
      Re: malloc BGB <cr88192@hotmail.com> - 2012-02-16 16:16 -0700
        Re: malloc Paavo Helde <myfirstname@osa.pri.ee> - 2012-02-17 14:46 -0600
          Re: malloc Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-17 14:51 -0800
            Re: malloc BGB <cr88192@hotmail.com> - 2012-02-17 19:58 -0700
              Re: malloc Paavo Helde <myfirstname@osa.pri.ee> - 2012-02-18 02:18 -0600
                Re: malloc BGB <cr88192@hotmail.com> - 2012-02-18 01:58 -0700
                Re: malloc glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-02-18 15:30 +0000
              Re: malloc Kaz Kylheku <kaz@kylheku.com> - 2012-02-18 10:36 +0000
              Re: malloc William Ahern <william@wilbur.25thandClement.com> - 2012-02-18 16:43 -0800
                Re: malloc BGB <cr88192@hotmail.com> - 2012-02-18 20:03 -0700
                  Re: malloc Miles Bader <miles@gnu.org> - 2012-02-19 12:49 +0900
                    Re: malloc William Ahern <william@wilbur.25thandClement.com> - 2012-02-18 21:08 -0800
                    Re: malloc "io_x" <a@b.c.invalid> - 2012-02-19 18:23 +0100
                  Re: malloc William Ahern <william@wilbur.25thandClement.com> - 2012-02-18 21:06 -0800
                    Re: malloc BGB <cr88192@hotmail.com> - 2012-02-18 23:06 -0700
        Re: malloc "Asger Joergensen" <Junk@Asger-P.dk> - 2012-02-19 15:54 +0000
          Re: malloc BGB <cr88192@hotmail.com> - 2012-02-19 09:37 -0700
      Re: malloc Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-16 20:27 -0500
        Re: malloc Goran <goran.pusic@gmail.com> - 2012-02-16 23:40 -0800
          Re: malloc Keith Thompson <kst-u@mib.org> - 2012-02-17 02:26 -0800
            Re: malloc Goran <goran.pusic@gmail.com> - 2012-02-17 04:01 -0800
              Re: malloc Keith Thompson <kst-u@mib.org> - 2012-02-17 09:25 -0800
                Re: malloc 88888 Dihedral <dihedral88888@googlemail.com> - 2012-02-17 09:37 -0800
                Re: malloc Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-17 14:49 -0800
                  Re: malloc glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-02-18 01:43 +0000
                    Re: malloc Kaz Kylheku <kaz@kylheku.com> - 2012-02-18 02:04 +0000
                  Re: malloc scott@slp53.sl.home (Scott Lurndal) - 2012-02-18 03:04 +0000
                    Re: malloc Robert Wessel <robertwessel2@yahoo.com> - 2012-02-17 22:15 -0600
                    Re: malloc Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-17 23:48 -0800
                Re: malloc Kaz Kylheku <kaz@kylheku.com> - 2012-02-17 23:29 +0000
          Re: malloc Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-17 08:06 -0500
            Re: malloc Goran <goran.pusic@gmail.com> - 2012-02-18 07:57 -0800
              Re: malloc Keith Thompson <kst-u@mib.org> - 2012-02-18 10:57 -0800
              Re: malloc Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-19 08:51 -0500
        Re: malloc scott@slp53.sl.home (Scott Lurndal) - 2012-02-17 20:31 +0000
          Re: malloc Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-18 00:01 -0800
            Re: malloc scott@slp53.sl.home (Scott Lurndal) - 2012-02-18 17:07 +0000
              Re: malloc Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-18 18:14 -0800
                Re: malloc scott@slp53.sl.home (Scott Lurndal) - 2012-02-19 17:14 +0000
    Re: malloc Goran <goran.pusic@gmail.com> - 2012-02-16 23:43 -0800
    Re: malloc "io_x" <a@b.c.invalid> - 2012-02-19 16:44 +0100

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#14139

On Feb 17, 2:27 am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
>
> > In article<jhjr14$rj...@reader1.panix.com>, j...@panix.com (Joe keane) wrote:
>
> >> Bugs of memory allocation will make you mad.
>
> >> Bugs *in* memory allocation will put you in the cuckoo people place.
>
> > Which is why they are exceedingly rare. Nearly all allocation problems are due
> > to the program storing outside array bounds.
>
>      The only allocator bug I have personally encountered was with
> a malloc() implementation that never, never returned NULL.  When it
> ought to have returned NULL, it crashed the program instead ...

If you don't provide a way to verify that, it didn't happen ;-), and
there was a bug in your code.

Goran.

[toc] | [prev] | [next] | [standalone]

#14154

Goran <goran.pusic@gmail.com> writes:
> On Feb 17, 2:27 am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
>> On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
>>
>> > In article<jhjr14$rj...@reader1.panix.com>, j...@panix.com (Joe keane) wrote:
>>
>> >> Bugs of memory allocation will make you mad.
>>
>> >> Bugs *in* memory allocation will put you in the cuckoo people place.
>>
>> > Which is why they are exceedingly rare. Nearly all allocation problems are due
>> > to the program storing outside array bounds.
>>
>>      The only allocator bug I have personally encountered was with
>> a malloc() implementation that never, never returned NULL.  When it
>> ought to have returned NULL, it crashed the program instead ...
>
> If you don't provide a way to verify that, it didn't happen ;-), and
> there was a bug in your code.

I suspect he's referring to the malloc() implementation
on typical Linux systems, which overcommits memory by default.
It can allocate a large chunk of address space for which no actual
memory is available.  The memory isn't actually allocated until
the process attempts to access it.  If there isn't enough memory
available for the allocation, the "OOM killer" kills some process
(not necessarily the one that did the allocation).

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#14160

On Feb 17, 11:26 am, Keith Thompson <ks...@mib.org> wrote:
> Goran <goran.pu...@gmail.com> writes:
> > On Feb 17, 2:27 am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> >> On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
>
> >> > In article<jhjr14$rj...@reader1.panix.com>, j...@panix.com (Joe keane) wrote:
>
> >> >> Bugs of memory allocation will make you mad.
>
> >> >> Bugs *in* memory allocation will put you in the cuckoo people place.
>
> >> > Which is why they are exceedingly rare. Nearly all allocation problems are due
> >> > to the program storing outside array bounds.
>
> >>      The only allocator bug I have personally encountered was with
> >> a malloc() implementation that never, never returned NULL.  When it
> >> ought to have returned NULL, it crashed the program instead ...
>
> > If you don't provide a way to verify that, it didn't happen ;-), and
> > there was a bug in your code.
>
> I suspect he's referring to the malloc() implementation
> on typical Linux systems, which overcommits memory by default.
> It can allocate a large chunk of address space for which no actual
> memory is available.  The memory isn't actually allocated until
> the process attempts to access it.  If there isn't enough memory
> available for the allocation, the "OOM killer" kills some process
> (not necessarily the one that did the allocation).

That crossed my mind, but what he said doesn't correspond with what
happens: malloc does return something and __doesn't__ crash the
program. OOM killer kills the code upon an attempt to access that
memory.

But given the way he explained it, it's possible that he's affected by
OOM killer, and he forgot, or never knew, what really happened.

Goran.

[toc] | [prev] | [next] | [standalone]

#14182

Goran <goran.pusic@gmail.com> writes:
> On Feb 17, 11:26 am, Keith Thompson <ks...@mib.org> wrote:
[...]
>> I suspect he's referring to the malloc() implementation
>> on typical Linux systems, which overcommits memory by default.
>> It can allocate a large chunk of address space for which no actual
>> memory is available.  The memory isn't actually allocated until
>> the process attempts to access it.  If there isn't enough memory
>> available for the allocation, the "OOM killer" kills some process
>> (not necessarily the one that did the allocation).
>
> That crossed my mind, but what he said doesn't correspond with what
> happens: malloc does return something and __doesn't__ crash the
> program. OOM killer kills the code upon an attempt to access that
> memory.

If you call malloc() and it overcommits, it won't crash the
program until you access the allocated memory.  (The rationale for
overcommitting is that most programs don't actually use most of
the memory the memory the allocate.  I find that odd)

> But given the way he explained it, it's possible that he's affected by
> OOM killer, and he forgot, or never knew, what really happened.

Given the post you're responding to, I would find it more likely that
he knows exactly what happened and didn't mention it.  Reading his
more recent followup, apparently it was on VMS, not Linux, and was
likely a bug in DEC's C library.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#14184

Keith Thompson於 2012年2月18日星期六UTC+8上午1時25分19秒寫道：
> Goran <goran.pusic@gmail.com> writes:
> > On Feb 17, 11:26 am, Keith Thompson <ks...@mib.org> wrote:
> [...]
> >> I suspect he's referring to the malloc() implementation
> >> on typical Linux systems, which overcommits memory by default.
> >> It can allocate a large chunk of address space for which no actual
> >> memory is available.  The memory isn't actually allocated until
> >> the process attempts to access it.  If there isn't enough memory
> >> available for the allocation, the "OOM killer" kills some process
> >> (not necessarily the one that did the allocation).
> >
> > That crossed my mind, but what he said doesn't correspond with what
> > happens: malloc does return something and __doesn't__ crash the
> > program. OOM killer kills the code upon an attempt to access that
> > memory.
> 
> If you call malloc() and it overcommits, it won't crash the
> program until you access the allocated memory.  (The rationale for
> overcommitting is that most programs don't actually use most of
> the memory the memory the allocate.  I find that odd)
> 
> > But given the way he explained it, it's possible that he's affected by
> > OOM killer, and he forgot, or never knew, what really happened.
> 
> Given the post you're responding to, I would find it more likely that
> he knows exactly what happened and didn't mention it.  Reading his
> more recent followup, apparently it was on VMS, not Linux, and was
> likely a bug in DEC's C library.
> 
> -- 
> Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
>     Will write code for food.
> "We must do something.  This is something.  Therefore, we must do this."
>     -- Antony Jay and Jonathan Lynn, "Yes Minister"

Nowadays malloc is too primitive for managing objects.

I have to compress some rarely used objects from time to time. Now the question is shared references which
sould be stored including the data state and dynamical  access methods for switching between the native mode and the compressed mode in the heap space.

[toc] | [prev] | [next] | [standalone]

#14204

On Feb 17, 9:25 am, Keith Thompson <ks...@mib.org> wrote:
> If you call malloc() and it overcommits, it won't crash the
> program until you access the allocated memory.  (The rationale for
> overcommitting is that most programs don't actually use most of
> the memory the memory the allocate.  I find that odd)

Really? The explanation that I'm most familiar with is that most fork
calls are immediately followed by exec, and thus if you're low on
memory, then a large process cannot spawn a new process without
overcommit because the only process create primitive is fork, which
"copies" the memory space of the parent process.

I of course think this is a broken state of affairs for several
reasons. 1- Just introduce a new create process primitive that creates
a process from an executable file with a copy options for specifying
the env vars, the command line, the working dir, etc. Sure it lacks
the full "power" of fork + exec, but it's a lot easier to use, and for
most uses of fork, I expect this would suffice, and then we could
avoid this nasty overcommit problem. 2- I'm annoyed at the ease at
which resources can be leaked to child processes and the near
impossibility to do anything portably about it.

However, due to discussions on this board, I've come to learn that OOM
situations are very hard to program for, and OOM in a common desktop
just can't be handled gracefully.

[toc] | [prev] | [next] | [standalone]

#14215

In comp.lang.c++ Joshua Maurice <joshuamaurice@gmail.com> wrote:

(snip)

> Really? The explanation that I'm most familiar with is that most fork
> calls are immediately followed by exec, and thus if you're low on
> memory, then a large process cannot spawn a new process without
> overcommit because the only process create primitive is fork, which
> "copies" the memory space of the parent process.

That was fixed about 20 years ago. Among others, there is vfork()

  "vfork - spawn new process in a virtual memory efficient way"

A simple explanation is that vfork() tells the system that you 
expect to call exec() next, and it can optimize for that case.

> I of course think this is a broken state of affairs for several
> reasons. 1- Just introduce a new create process primitive that creates
> a process from an executable file with a copy options for specifying
> the env vars, the command line, the working dir, etc. 

(snip)

-- glen

[toc] | [prev] | [next] | [standalone]

#14216

On 2012-02-18, glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
> In comp.lang.c++ Joshua Maurice <joshuamaurice@gmail.com> wrote:
>
> (snip)
>
>> Really? The explanation that I'm most familiar with is that most fork
>> calls are immediately followed by exec, and thus if you're low on
>> memory, then a large process cannot spawn a new process without
>> overcommit because the only process create primitive is fork, which
>> "copies" the memory space of the parent process.
>
> That was fixed about 20 years ago. Among others, there is vfork()
>
>   "vfork - spawn new process in a virtual memory efficient way"
>
> A simple explanation is that vfork() tells the system that you 
> expect to call exec() next, and it can optimize for that case.

vfork is a dangerous hack which exposes the semantics of the optimization
of fork to the program.

A modern copy-on-write fork hides the semantics: the parent and child
spaces are shared, but appear duplicated.

A copy-on-write fork does have to account for the virtual space required
to duplicate the private mappings of the parent process, because those
will be copied physically if they are touched.

If you have a 500 megabyte process, of which 400 megabytes are private
mappings, and that process forks, the virtual layout of the system
increases by 400 megabytes. If overcommit is not allowed, that means
that the 400 megabytes has to be counted as physical memory.

Joshua is completely right here: forking is one of the use cases for
overcommit for this reason.

[toc] | [prev] | [next] | [standalone]

#14219

Joshua Maurice <joshuamaurice@gmail.com> writes:
>On Feb 17, 9:25=A0am, Keith Thompson <ks...@mib.org> wrote:
>> If you call malloc() and it overcommits, it won't crash the
>> program until you access the allocated memory. =A0(The rationale for
>> overcommitting is that most programs don't actually use most of
>> the memory the memory the allocate. =A0I find that odd)
>
>Really? The explanation that I'm most familiar with is that most fork
>calls are immediately followed by exec, and thus if you're low on
>memory, then a large process cannot spawn a new process without
>overcommit because the only process create primitive is fork, which
>"copies" the memory space of the parent process.

You're confusing overcommit with copy-on-write.  Fork uses COW[*] in
which the parent and child share the physical pages until the child
writes to one - at that point, they child gets a copy (and an allocation
occurs which may fail at that point if memory and swap are exhausted).

Overcommit was allowed to support sparse arrays which are common
with some workloads.

scott

(p.s.  see 'posix_spawn').

[*] COW came into general use in the SVR3.2/SVR4 timeframe.  Linux has always
    used COW on fork.   The only cost for the child is the page table
    (which actually can be quite a bit for a 1TB virtual address space using
     4k pages - IIRC about 2GB just for page tables to map that much VA; makes
     1G pages much more attractive (drops the page table size to 8k)).

[toc] | [prev] | [next] | [standalone]

#14220

On 18 Feb 2012 03:04:14 GMT, scott@slp53.sl.home (Scott Lurndal)
wrote:

>Joshua Maurice <joshuamaurice@gmail.com> writes:
>>On Feb 17, 9:25=A0am, Keith Thompson <ks...@mib.org> wrote:
>>> If you call malloc() and it overcommits, it won't crash the
>>> program until you access the allocated memory. =A0(The rationale for
>>> overcommitting is that most programs don't actually use most of
>>> the memory the memory the allocate. =A0I find that odd)
>>
>>Really? The explanation that I'm most familiar with is that most fork
>>calls are immediately followed by exec, and thus if you're low on
>>memory, then a large process cannot spawn a new process without
>>overcommit because the only process create primitive is fork, which
>>"copies" the memory space of the parent process.
>
>You're confusing overcommit with copy-on-write.  Fork uses COW[*] in
>which the parent and child share the physical pages until the child
>writes to one - at that point, they child gets a copy (and an allocation
>occurs which may fail at that point if memory and swap are exhausted).
>
>Overcommit was allowed to support sparse arrays which are common
>with some workloads.


I don't think there's much daylight between the two.  In both cases a
process has been implicitly allocated virtual pages, without
(necessarily) the presence of enough actual pages (real and/or disk)
to make good on that allocation, and the system can fail in the future
when the application does something apparently innocuous, like try to
write to a page it appears to have been allocated.

And while I'm not familiar with the implementation of all over-commit
schemes, at least a couple I've seen actually map all allocated pages
to a read-only pages full of zeros, and then use the COW mechanism to
allocate actual pages when they're written to.  This has the advantage
of not requiring a second mechanism, and possibly further delaying the
actual allocation (as an ordinary read does not trigger it).

[toc] | [prev] | [next] | [standalone]

#14224

On Feb 17, 7:04 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:
> Joshua Maurice <joshuamaur...@gmail.com> writes:
> >Really? The explanation that I'm most familiar with is that most fork
> >calls are immediately followed by exec, and thus if you're low on
> >memory, then a large process cannot spawn a new process without
> >overcommit because the only process create primitive is fork, which
> >"copies" the memory space of the parent process.
>
> You're confusing overcommit with copy-on-write.  Fork uses COW[*] in
> which the parent and child share the physical pages until the child
> writes to one - at that point, they child gets a copy (and an allocation
> occurs which may fail at that point if memory and swap are exhausted).
>
> Overcommit was allowed to support sparse arrays which are common
> with some workloads.
[...]
> [*] COW came into general use in the SVR3.2/SVR4 timeframe.  Linux has always
>     used COW on fork.   The only cost for the child is the page table
>     (which actually can be quite a bit for a 1TB virtual address space using
>      4k pages - IIRC about 2GB just for page tables to map that much VA; makes
>      1G pages much more attractive (drops the page table size to 8k)).

So, I thought that if I turned overcommit off in Linux that if I tried
to fork with a large process and low commit, then the fork would fail.
(We're getting a little off topic, but I do not care.)

> (p.s.  see 'posix_spawn').

posix_spawn solves the "COW" and fork memory problem, but posix_spawn
still has all of the same process w.r.t. leaking resources to child
processes because its defined semantics are "as if fork followed by
exec".

[toc] | [prev] | [next] | [standalone]

#14208

["Followup-To:" header set to comp.lang.c.]
On 2012-02-17, Keith Thompson <kst-u@mib.org> wrote:
> Goran <goran.pusic@gmail.com> writes:
>> On Feb 17, 11:26 am, Keith Thompson <ks...@mib.org> wrote:
> [...]
>>> I suspect he's referring to the malloc() implementation
>>> on typical Linux systems, which overcommits memory by default.
>>> It can allocate a large chunk of address space for which no actual
>>> memory is available.  The memory isn't actually allocated until
>>> the process attempts to access it.  If there isn't enough memory
>>> available for the allocation, the "OOM killer" kills some process
>>> (not necessarily the one that did the allocation).
>>
>> That crossed my mind, but what he said doesn't correspond with what
>> happens: malloc does return something and __doesn't__ crash the
>> program. OOM killer kills the code upon an attempt to access that
>> memory.
>
> If you call malloc() and it overcommits, it won't crash the
> program until you access the allocated memory.  (The rationale for
> overcommitting is that most programs don't actually use most of
> the memory the memory the allocate.  I find that odd)

Odd or not, it is borne out empirically. Applications are physically
smaller than their virtual footprints.

It may be the case that C programs that malloc something usually use
the whole block.

But overcommitting is not implemented at the level of malloc, but
at the level of a lower level allocator like mmap.

If the system maps a large block to give you a smaller one, that large
block will not be all used immediately.

Another example is thread stacks. If you give each thread a one megabyte
stack and make 100 threads, that's 100 megs of virtual space. But that one
megabyte is a worst case that few, if any, of the threads will hit.

Programs with lots of threads on GNU/Linux have inflated virtual footprints
due to the generous default stack size.

[toc] | [prev] | [next] | [standalone]

#14162

On 2/17/2012 2:40 AM, Goran wrote:
> On Feb 17, 2:27 am, Eric Sosman<esos...@ieee-dot-org.invalid>  wrote:
>> On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
>>
>>> In article<jhjr14$rj...@reader1.panix.com>, j...@panix.com (Joe keane) wrote:
>>
>>>> Bugs of memory allocation will make you mad.
>>
>>>> Bugs *in* memory allocation will put you in the cuckoo people place.
>>
>>> Which is why they are exceedingly rare. Nearly all allocation problems are due
>>> to the program storing outside array bounds.
>>
>>       The only allocator bug I have personally encountered was with
>> a malloc() implementation that never, never returned NULL.  When it
>> ought to have returned NULL, it crashed the program instead ...
>
> If you don't provide a way to verify that, it didn't happen ;-), and
> there was a bug in your code.

     Yeah, it was probably my code.  Awfully nice of DEC to fix it
for me by patching VMS' C library, don't you think?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#14236

On Feb 17, 2:06 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> > If you don't provide a way to verify that, it didn't happen ;-), and
> > there was a bug in your code.
>
>      Yeah, it was probably my code.  Awfully nice of DEC to fix it
> for me by patching VMS' C library, don't you think?

If you do have a legit library bug, you can just send a link to the
bug report.

I am not a mind reader, and in vast majority of cases, when people say
there's a library bug, there isn't.

Goran.

[toc] | [prev] | [next] | [standalone]

#14239

Goran <goran.pusic@gmail.com> writes:
> On Feb 17, 2:06 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
>> > If you don't provide a way to verify that, it didn't happen ;-), and
>> > there was a bug in your code.
>>
>>      Yeah, it was probably my code.  Awfully nice of DEC to fix it
>> for me by patching VMS' C library, don't you think?
>
> If you do have a legit library bug, you can just send a link to the
> bug report.
>
> I am not a mind reader, and in vast majority of cases, when people say
> there's a library bug, there isn't.

I don't believe Eric is obligated to convince you that it really happened.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#14278

On 2/18/2012 10:57 AM, Goran wrote:
> On Feb 17, 2:06 pm, Eric Sosman<esos...@ieee-dot-org.invalid>  wrote:
>>> If you don't provide a way to verify that, it didn't happen ;-), and
>>> there was a bug in your code.
>>
>>       Yeah, it was probably my code.  Awfully nice of DEC to fix it
>> for me by patching VMS' C library, don't you think?
>
> If you do have a legit library bug, you can just send a link to the
> bug report.

     The bug and fix dated from 1988, if memory serves, or possibly
1989.  VAX VMS (not OpenVMS), probably V5 but possibly V4, on a
MicroVAX II.  The compiler was VAXC (a pre-ANSI implementation;
sorry I cannot recall the version number), and I think the run-time
library was VAXC$LIB (that's where the bug lay and was patched).

     The company that issued the bug and then the patch went out
of business in 1998.

     The company that bought the remains of the company also went
out of business, in 2002.

     The company that bought the remains of the company that bought
the remains is still around, doing business under the name "Hewlett-
Packard Company."  If you are interested, I suggest you contact them
about the possibility of making available their archives of dead
acquisitions' long-dead fix lists.  (As I'm sure you're aware, putting
bug reports and fix lists on the Web was fairly unusual in 1988, since
Tim Berners-Lee's first Web browser was two years in the future.)

> I am not a mind reader, and in vast majority of cases, when people say
> there's a library bug, there isn't.

     Agreed, on both points.  For a number of reasons, libraries tend
to be less buggy than the calling code -- but "less buggy" does not
mean "bug-free."  And to the other point, I'm convinced not only of
your inability to read minds, but of your difficulty in comprehending
text.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#14190

Eric Sosman <esosman@ieee-dot-org.invalid> writes:
>On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
>> In article<jhjr14$rjk$1@reader1.panix.com>, jgk@panix.com (Joe keane) wrote:
>>
>>> Bugs of memory allocation will make you mad.
>>>
>>> Bugs *in* memory allocation will put you in the cuckoo people place.
>>
>> Which is why they are exceedingly rare. Nearly all allocation problems are due
>> to the program storing outside array bounds.
>
>     The only allocator bug I have personally encountered was with
>a malloc() implementation that never, never returned NULL.  When it
>ought to have returned NULL, it crashed the program instead ...

If it is the implementation I'm thinking of, it would have eventually
returned NULL if you'd had enough swap space available.

There were implementations in the 90's (solaris, AIX) in which, to support
very large sparse arrays, would use lazy allocation with malloc, such that
malloc would allocate virtual address space, not actual memory.  When each
page of the allocation was subsequently touched, it would be allocated from
the available memory pool or swap space.   If there was insufficient space
available, the access would result in a Segmentation Violation (SIGSEGV).

So, if you completely exhaust the virtual address space, malloc would return
NULL (or if there wasn't a large enough contiguous chunk of VA space), otherwise
you'd potentially get an error sometime later when accessing the allocated
address space.

There was a flag to mallopt(3) if I recall correctly that would affect this
behavior.

I remember long discussions about this behavior at one of the X/Open meetings
in the 90's.

scott

[toc] | [prev] | [next] | [standalone]

#14225

On Feb 17, 12:31 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:
> Eric Sosman <esos...@ieee-dot-org.invalid> writes:
> >On 2/16/2012 4:21 PM, Devil with the China Blue Dress wrote:
> >> In article<jhjr14$rj...@reader1.panix.com>, j...@panix.com (Joe keane) wrote:
>
> >>> Bugs of memory allocation will make you mad.
>
> >>> Bugs *in* memory allocation will put you in the cuckoo people place.
>
> >> Which is why they are exceedingly rare. Nearly all allocation problems are due
> >> to the program storing outside array bounds.
>
> >     The only allocator bug I have personally encountered was with
> >a malloc() implementation that never, never returned NULL.  When it
> >ought to have returned NULL, it crashed the program instead ...
>
> If it is the implementation I'm thinking of, it would have eventually
> returned NULL if you'd had enough swap space available.
>
> There were implementations in the 90's (solaris, AIX) in which, to support
> very large sparse arrays, would use lazy allocation with malloc, such that
> malloc would allocate virtual address space, not actual memory.  When each
> page of the allocation was subsequently touched, it would be allocated from
> the available memory pool or swap space.   If there was insufficient space
> available, the access would result in a Segmentation Violation (SIGSEGV).
>
> So, if you completely exhaust the virtual address space, malloc would return
> NULL (or if there wasn't a large enough contiguous chunk of VA space), otherwise
> you'd potentially get an error sometime later when accessing the allocated
> address space.
>
> There was a flag to mallopt(3) if I recall correctly that would affect this
> behavior.
>
> I remember long discussions about this behavior at one of the X/Open meetings
> in the 90's.

Can you give me some more rational into this perhaps please? Or point
me in a right direction? Coding and supporting overcommit for programs
that use sparse arrays just seems like .. a braindead idea. Kernel
support that will result in random programs dying for a question use
case when equivalent or better alternatives likely exist in userspace?

[toc] | [prev] | [next] | [standalone]

#14237

Joshua Maurice <joshuamaurice@gmail.com> writes:
>On Feb 17, 12:31=A0pm, sc...@slp53.sl.home (Scott Lurndal) wrote:

>> I remember long discussions about this behavior at one of the X/Open meet=
>ings
>> in the 90's.
>
>Can you give me some more rational into this perhaps please? Or point
>me in a right direction? Coding and supporting overcommit for programs
>that use sparse arrays just seems like .. a braindead idea. Kernel
>support that will result in random programs dying for a question use
>case when equivalent or better alternatives likely exist in userspace?

Be careful not to conflate the linux OOM killer with overcommit failures.

One operating system (only noted as XXX in my notes from 26 Feb 1993) also
provides a SIGDANGER signal that can be caught when system memory is
low.

 Here is portions of the Standard Interpretation Request sent to X/Open:
------------------------------------------------------------------------

 MALLOC XPG3 CONFORMANCE INTERPRETATION

 APPLICANTS POSITION
 -------------------

 Our position is that XXX3.2 and the malloc function included within
 it does indeed comply with the X/Open Portability Guide 3 based on the
 following facts:

     1. The XXX malloc() does return a pointer to a fully allocated,
        fully available block of virtual memory.  This is
        explained more in the early and late allocation section below.

     2. The XXX malloc() can and does return a null pointer under
        appropriate conditions, such as: ulimit size exceeded, segment
        size exceeded, corrupted memory, etc. Setting the rlimit down
        from the default 131Mb to 20Mb, for example, will cause the test
        mentioned in the XXXWorld article to receive a null pointer from
        malloc().

     3. While just an indicator of compliance, XXX has passed and
        continues to pass the appropriate portion of the VSX3, level
        205.

 We believe that the issues here are 1) the definition of "allocates",
 2) the system implementation schemes of "early" and "late" allocation,
 3) what the relevant standards have to say about the implementation of
 malloc() and 4) what the relevant standards say about the interaction of
 processes on a system.

 [[ .. Material elided .. ]]

 2. Early and Late Allocation
 ----------------------------

 At issue here is early versus late allocation.  XXX does return a
 pointer to a fully allocated, fully available block of virtual memory-
 just as specified, just as it must to meet the XPG3 specification and
 other standards, and just as every other system does.  What it does not
 do is allocate an equivalent amount of paging space.  Many UNIX
 implementations use early allocation, and show it when fork() or exec()
 are called and the action cannot complete due to lack of resource.
 Other implementations rely on late allocation of memory for performance
 reasons, Mach falling into that category. These implementations show
 problems when the backing store is full. Many fall in between,
 preferring to thrash or have the OS die when backing store runs out.

 XXX leans toward late allocation to assist in the efficient use of disk
 resources, and to support customers whose applications wish to take
 advantage of a "sparse allocation" algorithm for resource management.
 Often, programs will allocate large amounts of virtual memory and then
 use only a tiny fraction of it.  This is particularly true of technical
 applications which use sparse vectors or matrices as data structures.

 [[ .. Material elided .. ]]

 SUMMARY
 -------

 XXX malloc() behaves like other industry malloc()s when proper resource
 limits are set.  The only difference is in how XXX handles resource
 overcommitment in a multi-process environment. How resource
 overcommitment is handled is not covered in any relevant industry
 standard.  Paging space management is orthogonal to and separate from
 source code application programming interface specifications (as
 currently defined) such as malloc behavior.

 X/Open Initial Response

    In our view, late allocation schemes will become increasingly common,
    and we should ensure that our interpretation of "allocation" in XPG3
    and XPG4 encompasses this implementation behaviour.

    A permanent waiver is recommended on the basis of a grey area in XPG3.

======== Response from company YYY: ===============


        <name elided> and I discussed this issue at length before he left
   on vacation.  I'll list some of the key points below, but the bottom line
   is that we believe that X/Open should not grant this waiver because the
   implementation is not meeting XPG3 or XPG4 requirements.  The XPG3 and
   XPG4 malloc ERRORS sections say malloc() will fail if insufficient
   storage space is not available.  We believe that even though allocation
   may be an undefined term, sufficient storage space if defined well enough
   by common usage to outlaw the described behavior.

1.  What does XPG3 require?:
        Assuming we are calling malloc(x) with x != 0, malloc() is supposed
to return a pointer to the first byte of allocated space of at least x bytes
suitably aligned to store any type of object.  So far the lack of definition
of the term "allocated" works.  But the ERRORS section is more explicit.
There it (XPG3, Vol 2, P276) says:
                The malloc() function will fail if:
                [ENOMEM]        Insufficient storage space is available.
(Note that it says "will fail"; not "may fail".  If it said "may fail"
approval of the waiver would be on solid ground.)  Then the key point is
that it says it fails if "insufficent storage space" is available.  We
don't believe this is ambiguous.  The storage space has to include
address space, page table entries, backing store, and any other kind of
allocation needed to allow the process to use the area that malloc() says
it has allocated.  If the ENOMEM description had said "Unable to allocate
space." instead of the wording it does use, we could agree with the
unspecified meaning of the term "allocate".

2.  Are there similar allocation problems that result in termination of a
        process after successful execution of an XPG4 specified function()?

        If there were others, we could say: "Look at this other example
where XPG3 doesn't say that this can happen, but it does and portable
applications can't recover from them either."  We came up with two
marginally similar cases:
        A.  If a user is executing a program and the program file is changed
                while the user is running, the program may die when an
                updated page gets swapped in that doesn't fit in the old
                executable.  (We don't think this case applies because one
                user took physical action (copying a new file on top of an
                executing file) that caused the break.  This is different
                from the system saying "you're all set" and later coming back
                and saying "just kidding, you're dead".

        B.  In many (probably most since V7) implementations of the exec()
                family of functions, it is possible to get to a stage in
                the execution of exec where the invoking process image
                can't be returned to and yet the new process image can't
                be loaded.  This is reported to the parent of the execing
                process as death of child by SIGKILL.  At least in this
                case you haven't started processing a transaction that
                can't be completed because the system made promises it
                wouldn't keep later.

        There are other timing related issues that can give anomalous
results (like asking if a region of a file can be locked, getting an
affirmative response, and then finding out that there is a blocking
lock by the time you actually try to place a lock), but these are the
result of the system reporting current state that does change quickly
on today's processors.

        The next issue we discussed is how the described behavior would affect
application writers.  This is hinted at in 2B above.  Most applications
have learned to allocate the space they will need for a transaction before
starting the transaction and giving an error before starting something
that can't be completed if "sufficient storage space" isn't available.
There are obvious cases where a file system can fill up and make it
hard for an application to recover, but at least the application is
notified by write() failures that things aren't going well and is given
a chance to recover in a standard way.  (i.e.  ANSI C, SVID, XPG3, XPG4,
POSIX.1 describe how errno will be set and what values write(), fflush(),
fclose(), etc. will return in error cases.)  These same applications
running on a system as specified by this request will receive a signal
(presumably with default action of terminate the process) with no indication
that they were in trouble.  Such applications would end up with partially
processed transactions with no way for a portable application to clean it up.
        If someone wants to let applications use this faster, more dangerous
way of living, they should have the application call a system function
saying "I know about SIGDANGER; I want to run faster; use late allocation."
This would be analagous to the IEXTEN bit specified by POSIX for termios
behavior.  If IEXTEN isn't set, the implementation must do only the
things specified in the standard; if the application set IEXTEN, the
implementation can provide all sorts of wondrous extensions that may
affect users and applications in ways not specified by POSIX.

        We also note that the XPG4 ERRORS section uses the same wording
as XPG3, so this problem is not just related to XPG3 conformance; it also
affects XPG4 conformance.

==== Response from company ZZZ  ====

The effect of this implementation is that programs written portably can
die due to the system's failing in a way that requires implementation-
specific coding to recover from.  Even worse, the failures are unlikely
to be reproducible.  Although there is a great deal of existing (and
new!) code that simply assumes that all malloc()s will work, those that
do check then presume that the entire space is allocated and available.

The implementation-specific code mentioned in the letter also seems to
me to be less than useful!  A signal that says "a page that was
allocated for you cannot be instantiated when needed" at best provides
the process the ability to print a message before it dies.  Unlike an
immediate allocation failure from malloc(), the process (without some
pretty architecture-specific programming!) cannot know where it is in
its processing and what data structure it might have run short of.

In general, I completely agree that an approach that uses a "lazy"
scheme to allocation is a solid and appropriate approach.  However, the
behavior on "overcommitment" is inappropriate.  Independent of whether
such can be classified as a failure to meet the specifications (or, at
least, their intent) or is only a "quality of implementation" question,
the result is practically unusable if "overcommitment" is anything other
than a very unlikely occurrence.  [How can an application ever be safe
in this environment otherwise?  There's virtually no way to protect
from a "random" failure of any program that uses malloc() unless it
always modifies each page--read as "each byte" unless the program knows
pages and their alignments--immediately after a successful malloc()!
And this, of course, causes any benefits from the "lazy allocation"
scheme to be entirely lost.]

In my opinion, the XXX system should assure that there are sufficient
pages available in the equivalent of the "swap device" such that the
full allocation will not fail at some point in the indefinite future
due to "overcommitment" by the system.  This does not preclude delaying
the actual allocation and zero-filling of pages until they are needed,
just that the external storage necessary to back-up the allocation be
guaranteed at the time of allocation.  The proposed waiver seems ill-
advised to me.

===== My Response at the time ====

> Ladies & Gentlemen, please would you consider the attached waiver which
> is being sent out for interpretation and review.
> 
Up front, I don't think the waiver should be granted.

>  Our position is that XXX3.2 and the malloc function included within
>  it does indeed comply with the X/Open Portability Guide 3 based on the
>  following facts:
> 
>      1. The XXX malloc() does return a pointer to a fully allocated,
>         fully available block of virtual memory.  This is
>         explained more in the early and late allocation section below.

I base this upon ISO C (1990) 4.10.3 where it states
  "... and then used to access such an object or array of such objects in
       the space allocated (until the space is explicity freed or
       reallocated)."

If the process is killed due to the inability to fetch [allocate] backing store
on disk, then the pointer cannot be used to access such an object,
and this violates the intent of the ISO C language standard.

===== End Notes =====

Oddly, I can't find any email regarding the resolution of this interpretation
request (my written notes from the meeting are in a box in the attic) and
there is nothing in the rationale here that would shed any light on it:

http://pubs.opengroup.org/onlinepubs/9699919799/functions/malloc.html

scott

[toc] | [prev] | [next] | [standalone]

#14253

On Feb 18, 9:07 am, sc...@slp53.sl.home (Scott Lurndal) wrote:
> Joshua Maurice <joshuamaur...@gmail.com> writes:
> >On Feb 17, 12:31=A0pm, sc...@slp53.sl.home (Scott Lurndal) wrote:
> >> I remember long discussions about this behavior at one of the X/Open meet=
> >ings
> >> in the 90's.
>
> >Can you give me some more rational into this perhaps please? Or point
> >me in a right direction? Coding and supporting overcommit for programs
> >that use sparse arrays just seems like .. a braindead idea. Kernel
> >support that will result in random programs dying for a question use
> >case when equivalent or better alternatives likely exist in userspace?
>
> Be careful not to conflate the linux OOM killer with overcommit failures.
>
> One operating system (only noted as XXX in my notes from 26 Feb 1993) also
> provides a SIGDANGER signal that can be caught when system memory is
> low.
>
>  Here is portions of the Standard Interpretation Request sent to X/Open:
[notes]
> ===== End Notes =====
>
> Oddly, I can't find any email regarding the resolution of this interpretation
> request (my written notes from the meeting are in a box in the attic) and
> there is nothing in the rationale here that would shed any light on it:
>
> http://pubs.opengroup.org/onlinepubs/9699919799/functions/malloc.html
>
> scott

The justification given here is again sparse vectors or sparse
matrices. I'll repeat my earlier objection that just seems like an
entirely braindead thing to add to the kernel when there are easy
userspace workarounds. Hell, just increase swap by a large margin, and
with any sane modern virtual memory implementation, you'll get almost
the same result (except with a larger swap requirement, but not more
actual disk usage). So, the argument was that we want to allow this
buggy behavior to allow lazy userspace coders to run programs with
small swap? I was looking for specific case examples, something, that
goes into this use case besides another pithy one liner "it exists".
From google, the only references to virtual memory overcommit I can
seem to find are in relation to VMs, and the Linux feature. It's hard
for me to comment when I'm so relatively ignorant.

And yes, overcommit is separate from the Linux OOM killer. Still, your
options are rather limited as to what to do when a process writes to a
new page and you have no space left, and none of them are what I would
call "good".

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c++

csiph-web