[9fans] lowest valid stack address

[9fans] lowest valid stack address

[erik quanstrom]

assuming no thread library, is there a way of
determining the lowest valid stack address
from userspace?  the purpose is to create a
test onstack() so that it can be asserted that
a given pointer is !onstack.  thread library
knows.

is it fair to assume that the stack can be up
to 256mb?  how does this generalize to 64 bits?

how bogus is this code, and why?

void
initbos(int x)
{
	uint m;
	uintptr p;

	p = (uintptr)&x;
	m = 1 << sizeof p*8 - 4;
	m -= 1;
	p &= ~m;
	print("%p\n", p);
}

uintptr	bos;

#define onstack(x)	((uintptr)(x) >= bos)
#define threadonstack(x)	/* thread library knows */

- erik

Re: [9fans] lowest valid stack address

[cinap_lenrek]

[-- Attachment #1: Type: text/plain, Size: 38 bytes --]

read /proc/$pid/segment

--
cinap

[-- Attachment #2: Type: message/rfc822, Size: 2501 bytes --]

From: erik quanstrom <quanstro@quanstro.net>
To: 9fans@9fans.net
Subject: [9fans] lowest valid stack address
Date: Tue, 1 Sep 2009 11:08:06 -0400
Message-ID: <0662c118779db0f0ac85f3ce711dcbb9@quanstro.net>

assuming no thread library, is there a way of
determining the lowest valid stack address
from userspace?  the purpose is to create a
test onstack() so that it can be asserted that
a given pointer is !onstack.  thread library
knows.

is it fair to assume that the stack can be up
to 256mb?  how does this generalize to 64 bits?

how bogus is this code, and why?

void
initbos(int x)
{
	uint m;
	uintptr p;

	p = (uintptr)&x;
	m = 1 << sizeof p*8 - 4;
	m -= 1;
	p &= ~m;
	print("%p\n", p);
}

uintptr	bos;

#define onstack(x)	((uintptr)(x) >= bos)
#define threadonstack(x)	/* thread library knows */

- erik

Re: [9fans] lowest valid stack address

[erik quanstrom]

On Tue Sep  1 12:54:06 EDT 2009, cinap_lenrek@gmx.de wrote:

> read /proc/$pid/segment
>

how do i know how low the stack segment can go?

- erik

Re: [9fans] lowest valid stack address

[erik quanstrom]

On Tue Sep  1 12:56:41 EDT 2009, quanstro@quanstro.net wrote:
> On Tue Sep  1 12:54:06 EDT 2009, cinap_lenrek@gmx.de wrote:
>
> > read /proc/$pid/segment
>
> how do i know how low the stack segment can go?

i should have been more explicit.  it's not that useful to know
what the current stack allocation is.  it's more useful to know
what the lowest possible stack address could be.
knowing the exact minimum address of my process
doesn't tell me anything about other process' stacks
with which i share memory space.  the address in
question might be on another proc's stack.

i'm also worried that it would not be cheep enough to do
a system call ~50x per mailbox message to check the
sbrk or look at /proc/$pid/segment.  this would mean
500000-1m extra system calls just to open a mailbox.

i suppose that a function like malloctopaddr() would
do that without locking returns the last sbrk.

but i'd settle for the lowest stack address.

- erik

Re: [9fans] lowest valid stack address

[Russ Cox]

I believe that the Stack line in /proc/$pid/segment
tells you the lowest possible stack address, not
the amount in use right now.  I looked in the kernel
source and tried it in 9vx and it confirms my belief.
I don't have a Plan 9 kernel to try it on right now,
so maybe I'm wrong.

Do you have two different /proc/$pid/segment
with different lowest stack addresses on the Stack line?

Russ

Re: [9fans] lowest valid stack address

[erik quanstrom]

On Tue Sep  1 19:24:33 EDT 2009, rsc@swtch.com wrote:
> I believe that the Stack line in /proc/$pid/segment
> tells you the lowest possible stack address, not
> the amount in use right now.  I looked in the kernel
> source and tried it in 9vx and it confirms my belief.
> I don't have a Plan 9 kernel to try it on right now,
> so maybe I'm wrong.
>
> Do you have two different /proc/$pid/segment
> with different lowest stack addresses on the Stack line?

evidently i misread /proc/$pid/segment.
and i guess this should have been obvious.
segments don't grow on demand.  but inside
a segment, you can have demand zero fill.

aside: from the overcommit vm discussion.
in http://9fans.net/archive/2000/06/634 rob
says that plan 9 doesn't overcommit vm.
what's the history here?

- erik

---
#include <u.h>
#include <libc.h>

enum {
	Stack	= 15*1024*1024,
};

char *runargv[] = {"/bin/sed", "1q", 0, 0};

void
run(char **argv)
{
	switch(fork()){
	case -1:
		sysfatal("fork: %r");
	case 0:
		exec(*argv, argv);
		sysfatal("exec: %r");
	default:
		waitpid();
	}
}

void
bigstack(void)
{
	char big[Stack];

	memset(big, 0, sizeof big);
	run(runargv);
}

void
main(void)
{
	char buf[64];

	snprint(buf, sizeof buf, "/proc/%ud/segment", getpid());
	runargv[2] = buf;

	run(runargv);
	bigstack();
	exits("");
}

Re: [9fans] lowest valid stack address

[Russ Cox]

> aside: from the overcommit vm discussion.
> in http://9fans.net/archive/2000/06/634 rob
> says that plan 9 doesn't overcommit vm.
> what's the history here?

i think plan 9 does overcommit vm and did then too.

russ

Re: [9fans] lowest valid stack address

[Devon H. O'Dell]

2009/9/1 Russ Cox <rsc@swtch.com>:
>> aside: from the overcommit vm discussion.
>> in http://9fans.net/archive/2000/06/634 rob
>> says that plan 9 doesn't overcommit vm.
>> what's the history here?
>
> i think plan 9 does overcommit vm and did then too.

It very much so does.

--dho

> russ
>
>

Re: [9fans] lowest valid stack address

[Andrés Domínguez]

2009/9/2 erik quanstrom <quanstro@quanstro.net>:
>
> aside: from the overcommit vm discussion.
> in http://9fans.net/archive/2000/06/634 rob
> says that plan 9 doesn't overcommit vm.
> what's the history here?

Exactly two years ago you started a thread about
memory overcommit. If I remember correctly, plan9
overcommits vm. Few weeks later the Go program
from gorka crashed while allocating the stack, maybe
an overcommiting check was added, probably gorka
knows.

Andrés

Re: [9fans] lowest valid stack address

[Gorka Guardiola]

2009/9/2 Andrés Domínguez <andresdju@gmail.com>:
> 2009/9/2 erik quanstrom <quanstro@quanstro.net>:
>>
>> aside: from the overcommit vm discussion.
>> in http://9fans.net/archive/2000/06/634 rob
>> says that plan 9 doesn't overcommit vm.
>> what's the history here?
>
> Exactly two years ago you started a thread about
> memory overcommit. If I remember correctly, plan9
> overcommits vm. Few weeks later the Go program
> from gorka crashed while allocating the stack, maybe
> an overcommiting check was added, probably gorka
> knows.
>

I don´t think there was an extra check added for this,
that was probably coincidence.
I think that was some other effect.

The vm space may (and normally is) bigger than the physical memory
(that is what vm is about). but not the quantity really backed up by
physical memory because
there is no swap (there is but noone uses it).

If you don´t touch the memory,
it never gets mapped in, so you may reserve a big chunk, but it has to fit
in your vm in the space between the stack and the bss. In my go program
I was reserving something unreasonable like 1Gb
(I was doing some funny things with it) of stack using
the thread library and I probably ran out of vm space for the proc and the
kernel does check this.
-- 
- curiosity sKilled the cat

Re: [9fans] lowest valid stack address

[erik quanstrom]

> > Exactly two years ago you started a thread about
> > memory overcommit. If I remember correctly, plan9
> > overcommits vm. Few weeks later the Go program

i thought this was common knowledge, and so i ommitted
recounting the discussion.  since it's not common knowledge
i'll recount.

plan 9 overcommits vm.  a large amount of this overcommit
is due to the stack, since the kernel gives each process a 16mb
segment.  overcommit means you can malloc n bytes or even
use a few extra bytes on the stack but will fault when
accessing it.  needless to say, overcommit is not much fun.
executables are paged out even with no swap.

the reason for the crash of the Go program is that the
stack segment is 16mb.  while plan 9 will demand load
and zero fill within the stack segment, it's just a fault
to try to access memory outside of any segment.  therefore,
we know the Go program had a stack >=16mb.
(by careful arrangement, the page below the stack is
generally invalid — it's not in any segment.)

the bss, stack and shared segments are zero-filled on
demand.  it doesn't appear they can be paged out.

> If you don´t touch the memory,
> it never gets mapped in, so you may reserve a big chunk, but it has to fit
> in your vm in the space between the stack and the bss. In my go program
> I was reserving something unreasonable like 1Gb

the maximum segment allowed by the pc kernel is 1984mb.
(SEGMAPSIZE*PTEPERTAB*BY2PG), see segment.c:/^by2pg

- erik

Re: [9fans] lowest valid stack address

[Devon H. O'Dell]

2009/9/2 Andrés Domínguez <andresdju@gmail.com>:
> 2009/9/2 erik quanstrom <quanstro@quanstro.net>:
>>
>> aside: from the overcommit vm discussion.
>> in http://9fans.net/archive/2000/06/634 rob
>> says that plan 9 doesn't overcommit vm.
>> what's the history here?
>
> Exactly two years ago you started a thread about
> memory overcommit. If I remember correctly, plan9
> overcommits vm. Few weeks later the Go program
> from gorka crashed while allocating the stack, maybe
> an overcommiting check was added, probably gorka
> knows.

No checks have been added. I started a rather active thread about this
a few months ago in attempt to figure out a way to `protect' from this
behavior starving the kernel of memory and thus panicking. I'll leave
it up to Elly to find some way to actually exploit this :). The
problem ended up being that I'd have to rework a lot of the slab
allocator, or do checks on every memory allocation, and I didn't want
to do that. More detailed info for those who care:

Lemma: In order to avoid overcommitting, we must impose limits on how
much memory may, in fact, be allocated. To make the implementation
provable, you must be able to assert that memory always comes from the
same spot, and you thus have a single path to follow into allocation.

Memory limits must be enforced based on real hardware in the system.
The issue here is that some slabs will always fill up
disproportionately to others. Thus, whichever limit you impose, slabs
must be growable. Thus:
 - Systemic limits require you to be able to migrate pages between zones.
 - Per-zone memory limits are silly because you have to be able to
migrate pages between zones,
 - Per-process and per-user memory limits are silly, though easier to
implement, because they add too much overhead to allocations and
frees.

Basically, it boils down to: If you want to implement this
effectively, the slab allocator needs to be reworked so that memory
zones can `steal' pages from other zones. If this is a real issue, I'm
happy to go take another stab at it: I stopped working on it last time
because it seemed most people found it a non-issue.

--dho

> Andrés
>
>

Re: [9fans] lowest valid stack address

[erik quanstrom]

> problem ended up being that I'd have to rework a lot of the slab
> allocator, or do checks on every memory allocation, and I didn't want
> to do that. More detailed info for those who care:

could you use plan 9 terminology?

>
> Lemma: In order to avoid overcommitting, we must impose limits on how
> much memory may, in fact, be allocated. To make the implementation
> provable, you must be able to assert that memory always comes from the
> same spot, and you thus have a single path to follow into allocation.

"from the same spot" could mean from the same point in the code or
from the same physical address.  either way, i don't buy this assertion.
counter example: ssd drive remapping algorithms.

- erik

Re: [9fans] lowest valid stack address

[Devon H. O'Dell]

2009/9/2 erik quanstrom <quanstro@quanstro.net>:
>> problem ended up being that I'd have to rework a lot of the slab
>> allocator, or do checks on every memory allocation, and I didn't want
>> to do that. More detailed info for those who care:
>
> could you use plan 9 terminology?

Probably not. Plan 9 uses a slab allocator to allocate memory in both
kernel and userland. The only fault I see in my previous email is
saying `zone' instead of `pool', but they're synonymous enough. If you
cite a specific ambiguity, I'm more than happy to clarify.

>>
>> Lemma: In order to avoid overcommitting, we must impose limits on how
>> much memory may, in fact, be allocated. To make the implementation
>> provable, you must be able to assert that memory always comes from the
>> same spot, and you thus have a single path to follow into allocation.
>
> "from the same spot" could mean from the same point in the code or
> from the same physical address.  either way, i don't buy this assertion.
> counter example: ssd drive remapping algorithms.

That was a rather poor choice of words. Restatement: To prove the
safety of the implementation, you must be able to assert that any
memory allocation triggers a check on the availability of the
requested memory. This revised statement doesn't require that a single
code path be followed into allocation, but since malloc() obtains
memory from the slab allocator, it makes sense to build the protection
into the slab allocator: it's centralized, and all allocations are
guaranteed to go through there anyway. The safety of such an
implementation is much easier to prove.

I hope that clarifies what I meant.

Example for what I did not mean: the FreeBSD jail system `virtualizes'
kernel resources by partitioning them to certain jail IDs. This
requires any resources wishing to be shared to be jail-aware, with the
side-effect that proving a jail only has access to what it needs is
much more difficult, because you have to prove that every resource is
`protected' anywhere that it is potentially used in the kernel. The
analogue to this sort of thing for our discussion would be introducing
an additional API to be used in conjunction with malloc(), requiring
it to be used every time. Clearly, it is more difficult to prove that
all mallocs() are safe with such an API, and it is *impossible* to
prove that future calls will be protected, as it is impossible to
prove that future additions to the kernel are properly handled with
respect to jails.

It's a somewhat silly comparison (as no one in their right mind would
implement this as an API to be used alongside malloc), but it
illustrates my point well. And it was easier to come up with that than
coming up with some other theoretical non-centralized (from a code
point of view) solution to this problem.

--dho

> - erik
>
>