Removing sbrk and brk

Removing sbrk and brk

[Rich Felker]

Based on a discussion on IRC, we're thinking about removing support
for the legacy sbrk and brk functions. These functions are
fundamentally broken and unfixable: For an application to use them
correctly, it must depend on the malloc subsystem never being used,
but this is impossible to guarantee since malloc may be used
internally by libc functions without documenting this to the
application. The interference is two-way: unexpected malloc would
interfere with an application's management of the heap via sbrk, and
unexpected sbrk interferes with malloc. Other implementations of
malloc (e.g. in glibc) handle this "gracefully", just splitting the
heap and leaving an unfreeable block where the application made a mess
by calling sbrk. musl's malloc does not even check for this (it would
be a mess working it in with musl's page-at-a-time brk adjustment
logic since the application's sbrk adjustments might not be
page-aligned) and therefore horribly crashes if the application has
used sbrk/brk itself.

As far as I can tell, the only remotely legitimate use for sbrk/brk is
for applications to provide their own malloc implementation using it.
This (redefining malloc) is not supported by musl (per ISO C and
POSIX, it results in undefined behavior) so there's really no
legitimate way musl-linked programs can be using sbrk/brk.

What we have encountered is certain programs and libraries (most
notably Boehm GC, but also programs that try to redefine malloc by
default, such as some versions of bash) causing horrible memory
corruption and runtime crashes that are hard to track down, due to
their use of sbrk.

Based on today's discussion, I think the cleanest solution is just to
eliminate sbrk/brk. This could be done in one of several ways:

- making them always-fail
- making the headers break use of them
- completely removing the symbols

The latter options are in some ways preferable, since the failure
would be caught at build-time and the program could be patched (or
different configure options passed) to fix the incorrect sbrk usage.

Unfortunately, this might break otherwise-correct programs that just
use sbrk(0) as a stupid way to "measure heap usage" or similar. I'm
not sure if that's an acceptable cost.

Another option would be providing dummy sbrk of some sort:

- sbrk(positive) == malloc(positive), sbrk(negative) == fail. This of
  course leads to memory leaks, but any usage of sbrk is
  potentially-leaky anyway since you can't always undo it safely.

- First call to sbrk or brk creates a large PROT_NONE mapping to
  provide a fake heap, and subsequent calls adjust an emulated brk
  pointer in this region and use mprotect to 'allocate'/'free'.

- Something else?

Finally, another alternative might be leaving sbrk/brk alone and
modifying malloc not to use the brk at all. This has been proposed
several times (well, supporting non-brk allocation has been proposed
anyway) to avoid spurious malloc failures when the brk cannot be
extended, and if we support that we might as well just drop brk
support in malloc (otherwise there's code with duplicate functionality
and thus more bloat). So this might actually be the best long-term
option. Switching malloc from using brk to PROT_NONE/mprotect (see the
above idea for brk emulation) would also make the malloc
implementation more portable to systems with no concept of brk.
However this option would definitely be a post-1.0 development
direction, and not something we could do right away (of course I'd
probably hold off until after 1.0 for any of these changes since
they're fairly invasive, except possibly the idea of making sbrk
always-fail).

Rich

Re: Removing sbrk and brk

[Luca Barbato]

On 22/12/13 00:40, Rich Felker wrote:
> Finally, another alternative might be leaving sbrk/brk alone and
> modifying malloc not to use the brk at all. This has been proposed
> several times (well, supporting non-brk allocation has been proposed
> anyway) to avoid spurious malloc failures when the brk cannot be
> extended, and if we support that we might as well just drop brk
> support in malloc (otherwise there's code with duplicate functionality
> and thus more bloat). So this might actually be the best long-term
> option. Switching malloc from using brk to PROT_NONE/mprotect (see the
> above idea for brk emulation) would also make the malloc
> implementation more portable to systems with no concept of brk.
> However this option would definitely be a post-1.0 development
> direction, and not something we could do right away (of course I'd
> probably hold off until after 1.0 for any of these changes since
> they're fairly invasive, except possibly the idea of making sbrk
> always-fail).

I'd add compile time and runtime warnings and plan for post-1.0

lu

Re: Removing sbrk and brk

[Richard Pennington]

On 12/21/2013 08:15 PM, Luca Barbato wrote:
> On 22/12/13 00:40, Rich Felker wrote:
>> Finally, another alternative might be leaving sbrk/brk alone and
>> modifying malloc not to use the brk at all. This has been proposed
>> several times (well, supporting non-brk allocation has been proposed
>> anyway) to avoid spurious malloc failures when the brk cannot be
>> extended, and if we support that we might as well just drop brk
>> support in malloc (otherwise there's code with duplicate functionality
>> and thus more bloat). So this might actually be the best long-term
>> option. Switching malloc from using brk to PROT_NONE/mprotect (see the
>> above idea for brk emulation) would also make the malloc
>> implementation more portable to systems with no concept of brk.
>> However this option would definitely be a post-1.0 development
>> direction, and not something we could do right away (of course I'd
>> probably hold off until after 1.0 for any of these changes since
>> they're fairly invasive, except possibly the idea of making sbrk
>> always-fail).
> I'd add compile time and runtime warnings and plan for post-1.0
>
> lu
The latest OS X Mavericks has sbrk() marked as deprecated and clang 
issues a warning for using it.

-Rich

Re: Removing sbrk and brk

[Luca Barbato]

On 22/12/13 18:58, Richard Pennington wrote:
> On 12/21/2013 08:15 PM, Luca Barbato wrote:
>> On 22/12/13 00:40, Rich Felker wrote:
>>> Finally, another alternative might be leaving sbrk/brk alone and
>>> modifying malloc not to use the brk at all. This has been proposed
>>> several times (well, supporting non-brk allocation has been proposed
>>> anyway) to avoid spurious malloc failures when the brk cannot be
>>> extended, and if we support that we might as well just drop brk
>>> support in malloc (otherwise there's code with duplicate functionality
>>> and thus more bloat). So this might actually be the best long-term
>>> option. Switching malloc from using brk to PROT_NONE/mprotect (see the
>>> above idea for brk emulation) would also make the malloc
>>> implementation more portable to systems with no concept of brk.
>>> However this option would definitely be a post-1.0 development
>>> direction, and not something we could do right away (of course I'd
>>> probably hold off until after 1.0 for any of these changes since
>>> they're fairly invasive, except possibly the idea of making sbrk
>>> always-fail).
>> I'd add compile time and runtime warnings and plan for post-1.0
>>
>> lu
> The latest OS X Mavericks has sbrk() marked as deprecated and clang
> issues a warning for using it.
> 

Sounds like a plan =)

Re: Removing sbrk and brk

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2013-12-21 18:40:41 -0500]:
> As far as I can tell, the only remotely legitimate use for sbrk/brk is
> for applications to provide their own malloc implementation using it.

single-threaded static linked binaries may want to avoid pulling in
the entire malloc implementation with locks etc and use sbrk instead
(i know some plan9 tools did this), i guess that should work if only
async-signal-safe libc calls are used (those cannot use malloc or brk
internally), but i don't think this is common

sbrk(0) is a valid usage and i think that's common (eventhough it is
mostly useless)

> - making them always-fail
> - making the headers break use of them
> - completely removing the symbols
> 
> The latter options are in some ways preferable, since the failure
> would be caught at build-time and the program could be patched (or
> different configure options passed) to fix the incorrect sbrk usage.

i think there is a general problem of dangerous/broken/legacy interfaces

i would prefer a separate tool that can catch these at compile-/run-time
rather than fixing them in the libc (sbrk/brk are special because they
are almost always wrong while the other broken interfaces are possible
to use without invoking ub)

another solution is to split libc into libgood and libbad
(or mark the broken apis in some way to catch their usage easily)

...
> However this option would definitely be a post-1.0 development
> direction, and not something we could do right away (of course I'd
> probably hold off until after 1.0 for any of these changes since
> they're fairly invasive, except possibly the idea of making sbrk
> always-fail).

so the options in increasing effort are

1) leave it as is
2) completely remove sbrk/brk
3) always fail (except for sbrk(0))
4) emulate with mmap+mprotect
5) malloc without brk

i like 1) or 3) for 1.0 and 5) for post-1.0

Re: Removing sbrk and brk

[Christian Neukirchen]

Szabolcs Nagy <nsz@port70.net> writes:

> so the options in increasing effort are
>
> 1) leave it as is
> 2) completely remove sbrk/brk
> 3) always fail (except for sbrk(0))
> 4) emulate with mmap+mprotect
> 5) malloc without brk
>
> i like 1) or 3) for 1.0 and 5) for post-1.0

FWIW, this would be my prefered way as well.

-- 
Christian Neukirchen  <chneukirchen@gmail.com>  http://chneukirchen.org

Re: Removing sbrk and brk

[Rich Felker]

On Sun, Dec 22, 2013 at 07:48:55PM +0100, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2013-12-21 18:40:41 -0500]:
> > As far as I can tell, the only remotely legitimate use for sbrk/brk is
> > for applications to provide their own malloc implementation using it.
> 
> single-threaded static linked binaries may want to avoid pulling in
> the entire malloc implementation with locks etc and use sbrk instead
> (i know some plan9 tools did this), i guess that should work if only
> async-signal-safe libc calls are used (those cannot use malloc or brk
> internally), but i don't think this is common

In principle, there's no rule that AS-safe interfaces can't use
malloc. As one special case, if signal/sigaction has never been
called, you can't be in an AS context, so malloc could be used freely.
Other means of detection may also be possible. Unless sbrk were
_specified_ (in the documentation of this legacy/nonstandard function)
as safe to use as long as you stick to only AS-safe functions, I don't
see how applications could use it safely even then.

FYI the dynamic linker also uses malloc but I don't see a way this
could be dangerous to such apps unless you're using dlopen too.

> sbrk(0) is a valid usage and i think that's common (eventhough it is
> mostly useless)

Mostly useless I agree, but I worry that some things might
gratuitously break if it doesn't work...

> > - making them always-fail
> > - making the headers break use of them
> > - completely removing the symbols
> > 
> > The latter options are in some ways preferable, since the failure
> > would be caught at build-time and the program could be patched (or
> > different configure options passed) to fix the incorrect sbrk usage.
> 
> i think there is a general problem of dangerous/broken/legacy interfaces
> 
> i would prefer a separate tool that can catch these at compile-/run-time
> rather than fixing them in the libc (sbrk/brk are special because they
> are almost always wrong while the other broken interfaces are possible
> to use without invoking ub)

As far as I'm aware, sbrk/brk are the only ones that can _never_ be
used safely. Even gets _can_ be used safely, e.g. if stdin is a pipe
from a related process and you know the max line length you will
encounter.

> another solution is to split libc into libgood and libbad
> (or mark the broken apis in some way to catch their usage easily)

There are various GCC-specific ways in the headers such as the
deprecated attribute and poison pragma. These could be utilized with
-include or a special -I path and #include_next.

> ....
> > However this option would definitely be a post-1.0 development
> > direction, and not something we could do right away (of course I'd
> > probably hold off until after 1.0 for any of these changes since
> > they're fairly invasive, except possibly the idea of making sbrk
> > always-fail).
> 
> so the options in increasing effort are
> 
> 1) leave it as is
> 2) completely remove sbrk/brk
> 3) always fail (except for sbrk(0))
> 4) emulate with mmap+mprotect
> 5) malloc without brk
> 
> i like 1) or 3) for 1.0 and 5) for post-1.0

I agree mostly. Option 5 would be ideal, but it depends on determining
whether there would be detrimental affects on performance. Even if
there are, however, it may be acceptable since I eventually want to
drop the madvise-based approach to returning memory to the kernel,
which doesn't relinquish any commit charge, and replace it with
PROT_NONE...

For now though it seems we're trying to decide between options 1 and
3. If we go for option 1, we should fix the integer overflow/wrapping
issue in sbrk you reported on irc..

Rich

Re: Removing sbrk and brk

[Rich Felker]

On Sun, Dec 22, 2013 at 11:46:09PM -0500, Rich Felker wrote:
> > so the options in increasing effort are
> > 
> > 1) leave it as is
> > 2) completely remove sbrk/brk
> > 3) always fail (except for sbrk(0))
> > 4) emulate with mmap+mprotect
> > 5) malloc without brk
> > 
> > i like 1) or 3) for 1.0 and 5) for post-1.0
> 
> I agree mostly. Option 5 would be ideal, but it depends on determining
> whether there would be detrimental affects on performance. Even if
> there are, however, it may be acceptable since I eventually want to
> drop the madvise-based approach to returning memory to the kernel,
> which doesn't relinquish any commit charge, and replace it with
> PROT_NONE...
> 
> For now though it seems we're trying to decide between options 1 and
> 3. If we go for option 1, we should fix the integer overflow/wrapping
> issue in sbrk you reported on irc..

OK, I'm modifying sbrk so sbrk(0) returns the current brk and
sbrk(nonzero) returns (void*)-1 with errno set to ENOMEM (option 3
above). This should help us catch any programs attempting to use sbrk
for memory management and get them fixed rather than dealing with
hideous memory-corruption errors that are hard to track down, and
we'll have some time to track them down between now and 1.0.

sbrk may be re-added sometime after 1.0 if malloc is changed to no
longer use the brk (option 5 above).

Rich

Re: Removing sbrk and brk

[Thorsten Glaser]

Rich Felker <dalias <at> aerifal.cx> writes:

> sbrk may be re-added sometime after 1.0 if malloc is changed to no
> longer use the brk (option 5 above).

You may want to import omalloc (based on mmap malloc, written from
scratch by Otto Moerbeek) with lots of security features:

http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c
http://www.openbsd.org/cgi-bin/man.cgi?query=malloc

It does assume that mmap() is randomised and NULs the result.

bye,
//mirabilos

Re: Re: Removing sbrk and brk

[Daniel Cegiełka]

2014/1/3 Thorsten Glaser <t.glaser@tarent.de>:
> Rich Felker <dalias <at> aerifal.cx> writes:
>
>> sbrk may be re-added sometime after 1.0 if malloc is changed to no
>> longer use the brk (option 5 above).
>
> You may want to import omalloc (based on mmap malloc, written from
> scratch by Otto Moerbeek) with lots of security features:
>
> http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c
> http://www.openbsd.org/cgi-bin/man.cgi?query=malloc
>
> It does assume that mmap() is randomised and NULs the result.
>
> bye,
> //mirabilos

Yes, I also wanted to suggest malloc from OpenBSD. This may be the
right solution for musl.

Daniel

Re: Re: Removing sbrk and brk

[Rich Felker]

On Fri, Jan 03, 2014 at 11:51:32AM +0000, Thorsten Glaser wrote:
> Rich Felker <dalias <at> aerifal.cx> writes:
> 
> > sbrk may be re-added sometime after 1.0 if malloc is changed to no
> > longer use the brk (option 5 above).
> 
> You may want to import omalloc (based on mmap malloc, written from
> scratch by Otto Moerbeek) with lots of security features:

This discussion is about improving one aspect of malloc, not replacing
it with a third-party implementation. The reason musl is significantly
smaller and more maintainable than glibc and uclibc is that it's not a
hodge-podge of copy-and-paste from various legacy code. I suspect
omalloc is considerably higher quality than a lot of the things those
two implementations copied, but from casual inspection, it doesn't
look anywhere near as small or high-performance as musl's.

The actual motivation for moving to mmap in malloc is twofold:
preventing allocation failure when expansion of the brk is blocked by
an inconveniently-placed mapping, and unifying an idea I have in mind
for actually returning unneeded commit charge (right now, musl returns
unneeded physical memory but not commit charge).

> http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c
> http://www.openbsd.org/cgi-bin/man.cgi?query=malloc
> 
> It does assume that mmap() is randomised and NULs the result.

If so, this is a rather odd (incorrect) assumption and results in
highly suboptimal behavior (O(n) malloc in place of O(1), where n is
the size of the allocation).

Rich

Re: Re: Removing sbrk and brk

[Rich Felker]

On Fri, Jan 03, 2014 at 12:33:01PM -0500, Rich Felker wrote:
> hodge-podge of copy-and-paste from various legacy code. I suspect
> omalloc is considerably higher quality than a lot of the things those
> two implementations copied, but from casual inspection, it doesn't
> look anywhere near as small or high-performance as musl's.
> 
> > http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c

Quick summary of omalloc:

- Uses mmap directly for allocations of at least PAGE_SIZE (vs musl
  which only uses mmap directly past 128k/256k limit).

- Rounds all allocation sizes up to a power of 2 (vs musl which has
  exact sizes for all mod-16-aligned sizes up to 512 bytes, or
  mod-32-aligned up to 1024 bytes on 64-bit, and above that every 1/4
  unit between successive powers of 2).

- Global lock (vs musl which uses local, per-bin locks, allowing
  allocations of different sizes not to touch the same locks).

- Allocations smaller than PAGE_SIZE are made by allocating a whole
  page of same-size objects that cannot be merged or resized in-place
  (vs musl which splits and combines free ranges as needed from a
  large, growable heap).

Overall my assessment is that omalloc is _simple_ (in some ways
simpler than musl's), but looks to have much worse fragmentation
properties, much worse performance properties (both syscall overhead
and locking come to mind), and no other clear advantages.

Rich

Re: Re: Removing sbrk and brk

[Rich Felker]

On Fri, Jan 03, 2014 at 01:19:06PM -0500, Rich Felker wrote:
> On Fri, Jan 03, 2014 at 12:33:01PM -0500, Rich Felker wrote:
> > hodge-podge of copy-and-paste from various legacy code. I suspect
> > omalloc is considerably higher quality than a lot of the things those
> > two implementations copied, but from casual inspection, it doesn't
> > look anywhere near as small or high-performance as musl's.
> > 
> > > http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c
> 
> Quick summary of omalloc:
> 
> - Uses mmap directly for allocations of at least PAGE_SIZE (vs musl
>   which only uses mmap directly past 128k/256k limit).
> 
> - Rounds all allocation sizes up to a power of 2 (vs musl which has
>   exact sizes for all mod-16-aligned sizes up to 512 bytes, or
>   mod-32-aligned up to 1024 bytes on 64-bit, and above that every 1/4
>   unit between successive powers of 2).
> 
> - Global lock (vs musl which uses local, per-bin locks, allowing
>   allocations of different sizes not to touch the same locks).
> 
> - Allocations smaller than PAGE_SIZE are made by allocating a whole
>   page of same-size objects that cannot be merged or resized in-place
>   (vs musl which splits and combines free ranges as needed from a
>   large, growable heap).
> 
> Overall my assessment is that omalloc is _simple_ (in some ways
> simpler than musl's), but looks to have much worse fragmentation
> properties, much worse performance properties (both syscall overhead
> and locking come to mind), and no other clear advantages.

And one more big one:

- Allocations don't have headers locally, so free is not O(1), but has
  to perform a hash table lookup based on the address passed to it (vs
  musl which has O(1) free, modulo retry-on-contention issues).

I'm not sure how bad the cost from the hash table is; in some ways,
it's an interesting alternate solution that avoids overhead and allows
tight packing of small allocations. It also provides greater
protection against corruption of the internal malloc structures, in
the sense of allowing the program to keep going after overflows, but
less ability to catch overflows and less protection from corrupting
other application data, unless you add back overhead just for that
purpose.

Rich

Re: Removing sbrk and brk

[Thorsten Glaser]

Rich Felker <dalias <at> aerifal.cx> writes:

> > Overall my assessment is that omalloc is _simple_ (in some ways
> > simpler than musl's), but looks to have much worse fragmentation
> > properties, much worse performance properties (both syscall overhead
> > and locking come to mind), and no other clear advantages.

I think the idea behind simplicity was ease of auditing, and the
fragmentation properties are accepted because omalloc inserts
unmapped guard pages between allocations and randomises them
(via mmap) for proactive security reasons.

> tight packing of small allocations. It also provides greater
> protection against corruption of the internal malloc structures, in

Indeed.

> the sense of allowing the program to keep going after overflows, but
> less ability to catch overflows and less protection from corrupting
> other application data, unless you add back overhead just for that
> purpose.

Such as the guard pages, yes.

But I guess it depends on whether you want to optimise for speed.
On the other hand, just the suggestion of reverting (in my eyes)
to the musl behaviour of having a heap that’s grown/shrunk dynamically
for smaller objects smells weird to me (with the BSD developer hat on).

But I’m just a downstream of omalloc. I really suggest to talk to
Otto Moerbeek, who, in contrast to most OpenBSD developers, is
pleasant to talk with and approachable.

bye,
//mirabilos

Re: Re: Removing sbrk and brk

[Rich Felker]

On Mon, Jan 06, 2014 at 02:51:11PM +0000, Thorsten Glaser wrote:
> Rich Felker <dalias <at> aerifal.cx> writes:
> 
> > > Overall my assessment is that omalloc is _simple_ (in some ways
> > > simpler than musl's), but looks to have much worse fragmentation
> > > properties, much worse performance properties (both syscall overhead
> > > and locking come to mind), and no other clear advantages.
> 
> I think the idea behind simplicity was ease of auditing, and the

Indeed, this makes sense.

> fragmentation properties are accepted because omalloc inserts
> unmapped guard pages between allocations and randomises them
> (via mmap) for proactive security reasons.

This seems to be optional behavior; using guard pages with all
allocations would blow up memory usage several thousand times and
limit the number of allocations possible on 32-bit systems to well
under one million -- yielding an unusable system.

> But I guess it depends on whether you want to optimise for speed.
> On the other hand, just the suggestion of reverting (in my eyes)
> to the musl behaviour of having a heap that’s grown/shrunk dynamically
> for smaller objects smells weird to me (with the BSD developer hat on).

In what way? The basic dlmalloc design musl uses is basically known
(albeit without any proof I'm aware of) to be the only efficient way
to do malloc. Pretty much all "improvements" to it actually sacrifice
O(1) operations or low fragmentation to buy performance improvements
in certain cases deemed likely (and of course making the worst-case
worse).

> But I’m just a downstream of omalloc. I really suggest to talk to
> Otto Moerbeek, who, in contrast to most OpenBSD developers, is
> pleasant to talk with and approachable.

Might be interesting, but pretty off-topic. Using the OpenBSD malloc
in musl is not something that's really on the table.

Rich

Re: Removing sbrk and brk

[Thorsten Glaser]

Rich Felker <dalias <at> aerifal.cx> writes:

> This seems to be optional behavior; using guard pages with all
> allocations would blow up memory usage several thousand times and

No, they aren’t accessible, so the kernel (should) never maps them
to any real RAM.

> limit the number of allocations possible on 32-bit systems to well
> under one million -- yielding an unusable system.

FSVO unusable. The default datasize ulimit on OpenBSD/i386 2.x/3.x
was 128 MiB, with the maximum having been 1 GiB (now 1.5 GiB, I
believ), anyway, so there is enough space for that. (In general,
they heavily use this – randomisation and guard pages.)

But this is getting even more OT.

> > But I’m just a downstream of omalloc. I really suggest to talk to
> > Otto Moerbeek, who, in contrast to most OpenBSD developers, is
> > pleasant to talk with and approachable.
> 
> Might be interesting

Mmhm. I must admit I had hoped to be able to pick some fruit from
that since you do bring up things I’d not have thought of. But np.

> but pretty off-topic. Using the OpenBSD malloc
> in musl is not something that's really on the table.

OK. I was just suggesting this in case it would have been something
you could have / wanted to use, and had not thought of already.

That’s it from me on the malloc thread.

bye,
//mirabilos

Re: Re: Removing sbrk and brk

[Rich Felker]

On Tue, Jan 07, 2014 at 09:43:26AM +0000, Thorsten Glaser wrote:
> Rich Felker <dalias <at> aerifal.cx> writes:
> 
> > This seems to be optional behavior; using guard pages with all
> > allocations would blow up memory usage several thousand times and
> 
> No, they aren’t accessible, so the kernel (should) never maps them
> to any real RAM.

The point is that even a 1-byte allocation (in fairness, that would be
rounded up to at least 16 bytes) ends up consuming a whole page and
thus 4k of storage, plus another 4k of virtual address space for the
guard page. On MIPS it may be even worse (16k pages are required on
some hardwasre).

> > limit the number of allocations possible on 32-bit systems to well
> > under one million -- yielding an unusable system.
> 
> FSVO unusable. The default datasize ulimit on OpenBSD/i386 2.x/3.x
> was 128 MiB, with the maximum having been 1 GiB (now 1.5 GiB, I

If the datasize ulimit was 128M, that translates (via the above waste
of a whole page per allocation) into an actual allocation limit that
may be at low as 512k (if all allocations are small). That's getting
out of the "FSVO" range and into the "plain unusable" range. For more
typical allocation sizes, the available total might be more like
5-20M.

Rich

Re: Re: Removing sbrk and brk

[Rich Felker]

It seems like I've made some incorrect statements in this thread which
the OpenBSD folks weren't too happy about, so now that I'm more clear
on the details I'd like to correct those mistakes for the record...

On Tue, Jan 07, 2014 at 11:06:27AM -0500, Rich Felker wrote:
> On Tue, Jan 07, 2014 at 09:43:26AM +0000, Thorsten Glaser wrote:
> > Rich Felker <dalias <at> aerifal.cx> writes:
> > 
> > > This seems to be optional behavior; using guard pages with all
> > > allocations would blow up memory usage several thousand times and
> > 
> > No, they aren’t accessible, so the kernel (should) never maps them
> > to any real RAM.
> 
> The point is that even a 1-byte allocation (in fairness, that would be
> rounded up to at least 16 bytes) ends up consuming a whole page and
> thus 4k of storage, plus another 4k of virtual address space for the
> guard page. On MIPS it may be even worse (16k pages are required on
> some hardwasre).

This is both incorrect and misleading. I was under the impression that
omalloc had a (non-default) option to use guard pages for all
allocations, even sub-page-size ones. This is not the case, and my
only excuse is that I wrote the above a day or two after last reading
the source and seeing that it had configurable options, but without
taking the time to confirm their nature.

So in reality, guard pages are only used for allocations that take up
at least a whole page, and so from what I can tell now, the maximum
overhead is something like 100% (not 25600%) committed memory and 200%
virtual address space and occurs for allocations just larger than one
page (where you end up needing one extra page for the rest of the
storage, and one guard page).

This is comparable to the overhead for small allocations (less than a
page), which are rounded up to a power-of-two size and thus have a
worst-case overhead of near-100%.

So there's no pathologically huge over-allocation going on, just
moderate overhead, which the OpenBSD folks have claimed (and I believe
them on this) has caught serious bugs in lots of major software.

Hope this clears things up.

Rich

Re: Re: Removing sbrk and brk

[Daniel Cegiełka]

And what do we do with failures when sbrk is used?

# grep -r sbrk /usr/bin/
Binary file /usr/bin/readelf matches
Binary file /usr/bin/as matches
Binary file /usr/bin/addr2line matches
Binary file /usr/bin/c++filt matches
Binary file /usr/bin/ld matches
Binary file /usr/bin/objdump matches
Binary file /usr/bin/size matches
Binary file /usr/bin/ar matches
Binary file /usr/bin/objcopy matches
Binary file /usr/bin/elfedit matches
Binary file /usr/bin/strings matches
Binary file /usr/bin/ld.bfd matches
Binary file /usr/bin/strip matches
Binary file /usr/bin/gdb matches
Binary file /usr/bin/nm matches
Binary file /usr/bin/ranlib matches


eg ex/vi doesn't work with new musl (git) - sbrk is used internally:

http://ex-vi.cvs.sourceforge.net/viewvc/ex-vi/ex-vi/ex_subr.c?revision=1.8&view=markup

481int
482morelines(void)
483{
484#ifdef _SC_PAGESIZE
485 static long pg;
486
487 if (pg == 0) {
488 pg = sysconf(_SC_PAGESIZE);
489 if (pg <= 0 || pg >= 65536)
490 pg = 4096;
491 pg /= sizeof (line);
492 }
493 if ((char *)sbrk(pg * sizeof (line)) == (char *)-1)
494 return (-1);
495 endcore += pg;
496 return (0);
497#else /* !_SC_PAGESIZE */
498 if (sbrk(1024 * sizeof (line)) == (char *)-1)
499 return (-1);
500 endcore += 1024;
501 return (0);
502#endif /* !_SC_PAGESIZE */
503}

and

http://ex-vi.cvs.sourceforge.net/viewvc/ex-vi/ex-vi/ex.c?revision=1.4&view=markup

532 fendcore = (line *) sbrk(0);
533 endcore = fendcore - 2;

and errors (vi) didn't indicate what failing.

Best regards,
Daniel

Re: Re: Removing sbrk and brk

[Szabolcs Nagy]

* Daniel Cegie?ka <daniel.cegielka@gmail.com> [2014-02-21 17:03:36 +0100]:
> And what do we do with failures when sbrk is used?
> 

most of these only call sbrk(0) which is supported

> # grep -r sbrk /usr/bin/
> Binary file /usr/bin/readelf matches
> Binary file /usr/bin/as matches
> Binary file /usr/bin/addr2line matches
> Binary file /usr/bin/c++filt matches
> Binary file /usr/bin/ld matches
> Binary file /usr/bin/objdump matches
> Binary file /usr/bin/size matches
> Binary file /usr/bin/ar matches
> Binary file /usr/bin/objcopy matches
> Binary file /usr/bin/elfedit matches
> Binary file /usr/bin/strings matches
> Binary file /usr/bin/ld.bfd matches
> Binary file /usr/bin/strip matches
> Binary file /usr/bin/gdb matches
> Binary file /usr/bin/nm matches
> Binary file /usr/bin/ranlib matches
> 

> eg ex/vi doesn't work with new musl (git) - sbrk is used internally:
> 
> http://ex-vi.cvs.sourceforge.net/viewvc/ex-vi/ex-vi/ex_subr.c?revision=1.8&view=markup
> 

the "old musl" did not support sbrk either (the cited code uses it
with malloc), the "new musl" just helps you find the bug more easily

Re: Re: Removing sbrk and brk

[Daniel Cegiełka]

2014-02-21 17:36 GMT+01:00 Szabolcs Nagy <nsz@port70.net>:
> * Daniel Cegie?ka <daniel.cegielka@gmail.com> [2014-02-21 17:03:36 +0100]:
>> And what do we do with failures when sbrk is used?
>>
>
> most of these only call sbrk(0) which is supported

ok, thank you for the information.


>> http://ex-vi.cvs.sourceforge.net/viewvc/ex-vi/ex-vi/ex_subr.c?revision=1.8&view=markup
>>
>
> the "old musl" did not support sbrk either (the cited code uses it
> with malloc), the "new musl" just helps you find the bug more easily

ex/vi doesn't work with the new musl. Too bad, because it is the
traditional unix ex/vi. Maybe Gunnar Ritter still fixes bugs.

best regards,
Daniel

Re: Re: Removing sbrk and brk

[Rich Felker]

On Fri, Feb 21, 2014 at 05:47:05PM +0100, Daniel Cegiełka wrote:
> 2014-02-21 17:36 GMT+01:00 Szabolcs Nagy <nsz@port70.net>:
> > * Daniel Cegie?ka <daniel.cegielka@gmail.com> [2014-02-21 17:03:36 +0100]:
> >> And what do we do with failures when sbrk is used?
> >>
> >
> > most of these only call sbrk(0) which is supported
> 
> ok, thank you for the information.
> 
> 
> >> http://ex-vi.cvs.sourceforge.net/viewvc/ex-vi/ex-vi/ex_subr.c?revision=1.8&view=markup
> >>
> >
> > the "old musl" did not support sbrk either (the cited code uses it
> > with malloc), the "new musl" just helps you find the bug more easily
> 
> ex/vi doesn't work with the new musl. Too bad, because it is the
> traditional unix ex/vi. Maybe Gunnar Ritter still fixes bugs.

Then it didn't work before either; it was silently corrupting memory.
The only difference now is that you know that it's not working.

The lazy way around this would be writing a fake sbrk that just mmaps
a huge PROT_NONE region the first time it's called then mprotects more
of it to PROT_READ|PROT_WRITE every time sbrk is called to make more
available. This is a *portable* fake sbrk that should work on any
system.

Rich

Re: Re: Removing sbrk and brk

[Daniel Cegiełka]

2014-02-21 18:09 GMT+01:00 Rich Felker <dalias@aerifal.cx>:

> Then it didn't work before either; it was silently corrupting memory.
> The only difference now is that you know that it's not working.

Thank you for your response and I understand the reasons.
In my free time I will try to fix ex/vi - it will require more work.

best regards,
Daniel