malloc

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

BGB <cr88192@hotmail.com> wrote in news:jhk2rh$19o$1@news.albasani.net:

> On 2/16/2012 2: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.
>>
>
> which are annoyingly difficult to track down sometimes...
>
>
> it would be nice if compilers would offer an option (as a debugging
> feature) to optionally put in bounds checking for many operations

Yes it is, and they are doing that. Use e.g. MSVC with iterator checking
switched on (this is the default) and accessing e.g. a std::vector out of
bounds will generate a runtime error. With gcc one can use MALLOC_CHECK_
or -lmcheck, these also should catch some out-of-bounds access errors.

For raw pointers it is more difficult, you can use something like
ElectricFence or Valgrind on Linux, but it makes your program to run many
times slower and consume lots of more memory so this is just for
debugging.


hth
Paavo

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.

On Feb 17, 12:46*pm, Paavo Helde <myfirstn...@osa.pri.ee> wrote:
> BGB <cr88...@hotmail.com> wrote innews:jhk2rh$19o$1@news.albasani.net:
>
>
>
>
>
>
>
>
>
> > On 2/16/2012 2: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.
>
> > which are annoyingly difficult to track down sometimes...
>
> > it would be nice if compilers would offer an option (as a debugging
> > feature) to optionally put in bounds checking for many operations
>
> Yes it is, and they are doing that. Use e.g. MSVC with iterator checking
> switched on (this is the default) and accessing e.g. a std::vector out of
> bounds will generate a runtime error. With gcc one can use MALLOC_CHECK_
> or -lmcheck, these also should catch some out-of-bounds access errors.
>
> For raw pointers it is more difficult, you can use something like
> ElectricFence or Valgrind on Linux, but it makes your program to run many
> times slower and consume lots of more memory so this is just for
> debugging.

MSVC also has some debug options that try to catch writes past the
ends of allocated regions as well. IIRC, they overallocate, and put
special bit patterns at the start and end on allocation, and when
freed they check to see if those bit patterns are intact, raising a
fatal error or something if it finds a problem.

["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.

In comp.lang.c Kaz Kylheku <kaz@kylheku.com> wrote:
> ["Followup-To:" header set to comp.lang.c.]
> On 2012-02-17, Keith Thompson <kst-u@mib.org> wrote:
<snip>
> > 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.

Supposedly, and years ago when application developers where chummy with
the kernel folks.

> 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.

No, but it's not like allocators are mmap'ing large fractions of available
memory. The trend is toward more and smaller mmap'd backing blocks to, e.g.,
improve address randomization.

> 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.

Fortunately GCC already supports segmented stacks. Such support would have
been there sooner were it not for overcommit reducing the apparent demand
for such a feature. Although, glibc doesn't seem to be too eager to jump
aboard. Perhaps they feel that a 5% performance hit is too high a cost to
get rid of applications randomly crashing under high loads.

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

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.

On 2/17/2012 3:51 PM, Joshua Maurice wrote:
> On Feb 17, 12:46 pm, Paavo Helde<myfirstn...@osa.pri.ee> wrote:
>> BGB<cr88...@hotmail.com> wrote innews:jhk2rh$19o$1@news.albasani.net:
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>> On 2/16/2012 2: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.
>>
>>> which are annoyingly difficult to track down sometimes...
>>
>>> it would be nice if compilers would offer an option (as a debugging
>>> feature) to optionally put in bounds checking for many operations
>>
>> Yes it is, and they are doing that. Use e.g. MSVC with iterator checking
>> switched on (this is the default) and accessing e.g. a std::vector out of
>> bounds will generate a runtime error. With gcc one can use MALLOC_CHECK_
>> or -lmcheck, these also should catch some out-of-bounds access errors.
>>
>> For raw pointers it is more difficult, you can use something like
>> ElectricFence or Valgrind on Linux, but it makes your program to run many
>> times slower and consume lots of more memory so this is just for
>> debugging.
>

I was mildly aware of ElectricFence and Valgrind, and was also thinking
mostly of malloc'ed raw pointers and C-style arrays (when passed as
pointers). the idea would be if something like Valgrind were directly
integrated into the compiler/runtime as a debug option. this is mostly
what I was writing about.

as for bounds-checked collection types, yes, I have a few of those as
well, and also mostly use a custom memory manager (mostly for GC and
dynamic type-checking), which could (sadly) create issues (likely not
detect bounds violations) if this feature were available.


> MSVC also has some debug options that try to catch writes past the
> ends of allocated regions as well. IIRC, they overallocate, and put
> special bit patterns at the start and end on allocation, and when
> freed they check to see if those bit patterns are intact, raising a
> fatal error or something if it finds a problem.

this is partly what my memory allocators do, but may also under certain
cases scan the heap, detect corruption, and attempt to diagnose it.

a nifty tool I have used in some places is object-origin tracking, where
every time the allocator is accessed, it records where it was called
from, and will use this information (combined with some data-forensics)
to try to make an educated guess as to "who done it" (or, IOW, around
where the offending code might be).

although, sadly, there is no good way to implement a HW write barrier
for this (sadly, neither Windows nor Linux give enough control over the
CPU to really make something like this all that workable, even then it
would still likely be page-fault driven slowness).

I have some stuff for "software write barriers" (mostly needed for other
reasons), but not a lot of code uses them (unless forced into it),
partly due to the added awkwardness and performance overheads.

one option that could sort of work for larger arrays would be to put
unused pages between memory objects, such that going out of bounds is
more likely to trigger a page fault.


or such...

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)).

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).

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".

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 problemsare 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?

BGB <cr88192@hotmail.com> wrote in news:jhn46t$dlp$1@news.albasani.net:

>
> a nifty tool I have used in some places is object-origin tracking,
> where every time the allocator is accessed, it records where it was
> called from, and will use this information (combined with some
> data-forensics) to try to make an educated guess as to "who done it"
> (or, IOW, around where the offending code might be).
>
> although, sadly, there is no good way to implement a HW write barrier
> for this (sadly, neither Windows nor Linux give enough control over
> the CPU to really make something like this all that workable, even
> then it would still likely be page-fault driven slowness).

This has been done in hardware as well.
http://en.wikipedia.org/wiki/Bounds_checking mentions VAX, B6500 and
Burroughs. By some reason this approach has not really catched on.

>
> one option that could sort of work for larger arrays would be to put
> unused pages between memory objects, such that going out of bounds is
> more likely to trigger a page fault.

This is exactly what Electric Fence does. It is also slow as hell, I
guess the most slowdown comes from where the array ends in a middle of a
virtual memory page and efence has to decide after a page fault if the
access was legal or not. For small allocations it also produces severe
memory fragmentation.

If you are only interested in arrays, then some compiler support would be
indeed helpful. Electric Fence intercepts all malloc calls and does not
know if these are meant for arrays or not (I guess), so it has to protect
all of them.

However, I would say that the best advice for avoiding out-of-bounds
access errors with raw pointers in C++ is to not use raw pointers.

Cheers
Paavo

On 2/18/2012 1:18 AM, Paavo Helde wrote:
> BGB<cr88192@hotmail.com> wrote in news:jhn46t$dlp$1@news.albasani.net:
>
>>
>> a nifty tool I have used in some places is object-origin tracking,
>> where every time the allocator is accessed, it records where it was
>> called from, and will use this information (combined with some
>> data-forensics) to try to make an educated guess as to "who done it"
>> (or, IOW, around where the offending code might be).
>>
>> although, sadly, there is no good way to implement a HW write barrier
>> for this (sadly, neither Windows nor Linux give enough control over
>> the CPU to really make something like this all that workable, even
>> then it would still likely be page-fault driven slowness).
>
> This has been done in hardware as well.
> http://en.wikipedia.org/wiki/Bounds_checking mentions VAX, B6500 and
> Burroughs. By some reason this approach has not really catched on.
>

not nearly so helpful on the PC though, where one is limited to options
both available for x86 and also that will work directly on OS's like
Windows and Linux.

>>
>> one option that could sort of work for larger arrays would be to put
>> unused pages between memory objects, such that going out of bounds is
>> more likely to trigger a page fault.
>
> This is exactly what Electric Fence does. It is also slow as hell, I
> guess the most slowdown comes from where the array ends in a middle of a
> virtual memory page and efence has to decide after a page fault if the
> access was legal or not. For small allocations it also produces severe
> memory fragmentation.
>

yeah. there are ways it could be done a little faster, say if one had
access to ring-2 or similar. if one is stuck with ring-3, then one has
to jerk off with the page access every time one wants to change
something (that or use double-mapping). the general problem though is
that this sort of thing isn't really fast, which is sort of why it would
be nicer if the compiler could handle it in software (internally
generating calls to write-barrier functions or similar).


> If you are only interested in arrays, then some compiler support would be
> indeed helpful. Electric Fence intercepts all malloc calls and does not
> know if these are meant for arrays or not (I guess), so it has to protect
> all of them.
>

I had assumed the possibility of checking near all assignments via
pointers within a given compilation unit if a certain flag were used.

> However, I would say that the best advice for avoiding out-of-bounds
> access errors with raw pointers in C++ is to not use raw pointers.
>

I use both C++ and a lot of plain C as well (in a project currently with
parts written in 5 different languages, though C is the majority leader).

hence, in many cases raw pointers are often "the normal way of doing
things" (except when using dynamic types, or dedicated array objects).


or such...