* [9fans] lowest valid stack address @ 2009-09-01 15:08 erik quanstrom 2009-09-01 16:52 ` cinap_lenrek 0 siblings, 1 reply; 14+ messages in thread From: erik quanstrom @ 2009-09-01 15:08 UTC (permalink / raw) To: 9fans 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 15:08 [9fans] lowest valid stack address erik quanstrom @ 2009-09-01 16:52 ` cinap_lenrek 2009-09-01 16:55 ` erik quanstrom 0 siblings, 1 reply; 14+ messages in thread From: cinap_lenrek @ 2009-09-01 16:52 UTC (permalink / raw) To: 9fans [-- 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 16:52 ` cinap_lenrek @ 2009-09-01 16:55 ` erik quanstrom 2009-09-01 17:47 ` erik quanstrom 0 siblings, 1 reply; 14+ messages in thread From: erik quanstrom @ 2009-09-01 16:55 UTC (permalink / raw) To: 9fans 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 16:55 ` erik quanstrom @ 2009-09-01 17:47 ` erik quanstrom 2009-09-01 23:22 ` Russ Cox 0 siblings, 1 reply; 14+ messages in thread From: erik quanstrom @ 2009-09-01 17:47 UTC (permalink / raw) To: 9fans 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 17:47 ` erik quanstrom @ 2009-09-01 23:22 ` Russ Cox 2009-09-01 23:49 ` erik quanstrom 0 siblings, 1 reply; 14+ messages in thread From: Russ Cox @ 2009-09-01 23:22 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 23:22 ` Russ Cox @ 2009-09-01 23:49 ` erik quanstrom 2009-09-01 23:59 ` Russ Cox 2009-09-02 8:01 ` Andrés Domínguez 0 siblings, 2 replies; 14+ messages in thread From: erik quanstrom @ 2009-09-01 23:49 UTC (permalink / raw) To: 9fans 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(""); } ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 23:49 ` erik quanstrom @ 2009-09-01 23:59 ` Russ Cox 2009-09-02 0:18 ` Devon H. O'Dell 2009-09-02 8:01 ` Andrés Domínguez 1 sibling, 1 reply; 14+ messages in thread From: Russ Cox @ 2009-09-01 23:59 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs > 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 23:59 ` Russ Cox @ 2009-09-02 0:18 ` Devon H. O'Dell 0 siblings, 0 replies; 14+ messages in thread From: Devon H. O'Dell @ 2009-09-02 0:18 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 > > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-01 23:49 ` erik quanstrom 2009-09-01 23:59 ` Russ Cox @ 2009-09-02 8:01 ` Andrés Domínguez 2009-09-02 8:58 ` Gorka Guardiola 2009-09-02 13:28 ` Devon H. O'Dell 1 sibling, 2 replies; 14+ messages in thread From: Andrés Domínguez @ 2009-09-02 8:01 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-02 8:01 ` Andrés Domínguez @ 2009-09-02 8:58 ` Gorka Guardiola 2009-09-02 13:32 ` erik quanstrom 2009-09-02 13:28 ` Devon H. O'Dell 1 sibling, 1 reply; 14+ messages in thread From: Gorka Guardiola @ 2009-09-02 8:58 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-02 8:58 ` Gorka Guardiola @ 2009-09-02 13:32 ` erik quanstrom 0 siblings, 0 replies; 14+ messages in thread From: erik quanstrom @ 2009-09-02 13:32 UTC (permalink / raw) To: 9fans > > 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-02 8:01 ` Andrés Domínguez 2009-09-02 8:58 ` Gorka Guardiola @ 2009-09-02 13:28 ` Devon H. O'Dell 2009-09-02 13:35 ` erik quanstrom 1 sibling, 1 reply; 14+ messages in thread From: Devon H. O'Dell @ 2009-09-02 13:28 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 > > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-02 13:28 ` Devon H. O'Dell @ 2009-09-02 13:35 ` erik quanstrom 2009-09-02 14:17 ` Devon H. O'Dell 0 siblings, 1 reply; 14+ messages in thread From: erik quanstrom @ 2009-09-02 13:35 UTC (permalink / raw) To: 9fans > 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 ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [9fans] lowest valid stack address 2009-09-02 13:35 ` erik quanstrom @ 2009-09-02 14:17 ` Devon H. O'Dell 0 siblings, 0 replies; 14+ messages in thread From: Devon H. O'Dell @ 2009-09-02 14:17 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 > > ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2009-09-02 14:17 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-09-01 15:08 [9fans] lowest valid stack address erik quanstrom 2009-09-01 16:52 ` cinap_lenrek 2009-09-01 16:55 ` erik quanstrom 2009-09-01 17:47 ` erik quanstrom 2009-09-01 23:22 ` Russ Cox 2009-09-01 23:49 ` erik quanstrom 2009-09-01 23:59 ` Russ Cox 2009-09-02 0:18 ` Devon H. O'Dell 2009-09-02 8:01 ` Andrés Domínguez 2009-09-02 8:58 ` Gorka Guardiola 2009-09-02 13:32 ` erik quanstrom 2009-09-02 13:28 ` Devon H. O'Dell 2009-09-02 13:35 ` erik quanstrom 2009-09-02 14:17 ` Devon H. O'Dell
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).