Re: [9fans] lowest valid stack address
2009/9/2 erik quanstrom quans...@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
2009/9/2 Andrés Domínguez andres...@gmail.com: 2009/9/2 erik quanstrom quans...@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
2009/9/2 Andrés Domínguez andres...@gmail.com: 2009/9/2 erik quanstrom quans...@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
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
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
2009/9/2 erik quanstrom quans...@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
Re: [9fans] lowest valid stack address
read /proc/$pid/segment -- cinap ---BeginMessage--- 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---End Message---
Re: [9fans] lowest valid stack address
On Tue Sep 1 12:54:06 EDT 2009, cinap_len...@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
On Tue Sep 1 12:56:41 EDT 2009, quans...@quanstro.net wrote: On Tue Sep 1 12:54:06 EDT 2009, cinap_len...@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 50-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
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
On Tue Sep 1 19:24:33 EDT 2009, r...@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
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
2009/9/1 Russ Cox r...@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