Does process need to have a kernel-side stack all the time?

Does process need to have a kernel-side stack all the time?

[Denys Vlasenko]

Hi Ingo,

You are one of the experts in processes/threads and scheduling
in Linux kernel, I hope you can answer this question.

A lot of effort went into minimizing of stack usage.
If I understand it correctly, one of the reasons for this
was to be efficient and not have lots of pages
used for stacks when we have a lot of threads
(tens of thousands).

A random thought occurred to me: in a system with so many
threads most of them are not executing anyway, even on
that gigantic Altix machines. Do they all need to have
kernel stack, all the time? I mean: the process which
is running in user space is not using kernel stack at all.
Process which is not running on a CPU right now
is not using it either. But they do still consume
at least 4k (or 8k on 64bits) of RAM.

Process absolutely must have kernel stack only when
it is actively running in kernel code (not sleeping),
right?

Can we have per-CPU kernel stacks instead, so that process
gets a kernel stack only every time it enters the kernel;
and make it so that the process which is scheduled away
from a CPU does not need to have kernel stack?

Currently, when process sleeps, we save some
state in stack, and such a change may require
some substantial surgery.

Can you tell me whether this is possible at all,
and how difficult you estimate it to be?
--
vda

Re: Does process need to have a kernel-side stack all the time?

[Denis V. Lunev]

On Mon, 2008-04-14 at 15:47 +0200, Denys Vlasenko wrote:
> Hi Ingo,
> 
> You are one of the experts in processes/threads and scheduling
> in Linux kernel, I hope you can answer this question.
> 
> A lot of effort went into minimizing of stack usage.
> If I understand it correctly, one of the reasons for this
> was to be efficient and not have lots of pages
> used for stacks when we have a lot of threads
> (tens of thousands).
> 
> A random thought occurred to me: in a system with so many
> threads most of them are not executing anyway, even on
> that gigantic Altix machines. Do they all need to have
> kernel stack, all the time? I mean: the process which
> is running in user space is not using kernel stack at all.
> Process which is not running on a CPU right now
> is not using it either. But they do still consume
> at least 4k (or 8k on 64bits) of RAM.
> 
> Process absolutely must have kernel stack only when
> it is actively running in kernel code (not sleeping),
> right?
> 
> Can we have per-CPU kernel stacks instead, so that process
> gets a kernel stack only every time it enters the kernel;
> and make it so that the process which is scheduled away
> from a CPU does not need to have kernel stack?
> 
> Currently, when process sleeps, we save some
> state in stack, and such a change may require
> some substantial surgery.
> 
> Can you tell me whether this is possible at all,
> and how difficult you estimate it to be?

I do not think that this can help. Usually, the process (thread) invokes
some syscall like sleep and goes to the waiting state _from the kernel_,
i.e. the kernel stack is used at that moment and will be required during
wake up.

Regards,
	Den

Re: Does process need to have a kernel-side stack all the time?

[Denys Vlasenko]

On Monday 14 April 2008 16:17, Denis V. Lunev wrote:
> On Mon, 2008-04-14 at 15:47 +0200, Denys Vlasenko wrote:
> > Currently, when process sleeps, we save some
> > state in stack, and such a change may require
> > some substantial surgery.
> > 
> > Can you tell me whether this is possible at all,
> > and how difficult you estimate it to be?
> 
> I do not think that this can help. Usually, the process (thread) invokes
> some syscall like sleep and goes to the waiting state _from the kernel_,
> i.e. the kernel stack is used at that moment and will be required during
> wake up.

See my quote above. That's exactly what I said. This is how it currently
works.

But do you really need 4k to remember that "this thread went to sleep by
executing sleep(60)"? Theoretically, you may get away with much smaller
save area to remember that, and be able to wake up and return to userspace.
--
vda

Re: Does process need to have a kernel-side stack all the time?

[Ingo Molnar]

* Denys Vlasenko <vda.linux@googlemail.com> wrote:

> But do you really need 4k to remember that "this thread went to sleep 
> by executing sleep(60)"? Theoretically, you may get away with much 
> smaller save area to remember that, and be able to wake up and return 
> to userspace.

there are three major issues.

1) the kernel stack is not just about "this thread went to sleep", it 
also contains all the call frames up to the point that schedules. That 
might be quite complex, such as:

 [<c0127c56>] kmap+0x45/0x48
 [<c0178e53>] unmap_vmas+0x57e/0x5f2
 [<c017c41c>] exit_mmap+0x8d/0x112
 [<c0131b2e>] mmput+0x35/0x7d
 [<c01355eb>] exit_mm+0xf5/0xfa
 [<c0136389>] do_exit+0x1ee/0x7a0
 [<c01067f2>] die+0x1f9/0x201
 [<c124a5be>] do_trap+0x9a/0xb2
 [<c0106bc1>] do_invalid_op+0x97/0xa1
 [<c124a28c>] error_code+0x7c/0x84
 [<c0492d21>] plist_del+0x34/0x65
 [<c0155034>] task_blocks_on_rt_mutex+0x14e/0x1b7
 [<c12488c5>] rt_mutex_slowlock+0x13d/0x236
 [<c1248596>] rt_mutex_lock_interruptible+0x2a/0x2f
 [<c1248f20>] _mutex_lock_interruptible+0x37/0x55
 [<c0574325>] tty_write+0x88/0x1d3
 [<c018cb05>] vfs_write+0xb1/0x165
 [<c018d2fc>] sys_write+0x40/0x67
 [<c01050e0>] syscall_call+0x7/0xb

we cannot throw that away or save it differently - it would be way too 
expensive.

2) another issue is that 4K of memory per task isnt all that large. 
Tasks tend to have much larger footprint in other areas: inodes, 
dentries, kmalloc's, open files, sockets, etc. etc. Any task that does 
something interesting will have a lot more than just 4K memory of 
footprint.

3) for runnable tasks a kernel stack is needed in every moment, because 
whenever the CPU enters IRQ handling or fault/exception handling, it 
will switch to a privileged stack. In theory we could have per CPU 
privileged stacks (and even have it for certain types of kernel-only 
exceptions), but especially because faults and even irqs can trigger 
scheduling, it's quite convenient to use the kernel stack as the 
privileged stack too.

	Ingo

Re: Does process need to have a kernel-side stack all the time?

[Andi Kleen]

Denys Vlasenko <vda.linux@googlemail.com> writes:

> A lot of effort went into minimizing of stack usage.
> If I understand it correctly, one of the reasons for this
> was to be efficient and not have lots of pages
> used for stacks when we have a lot of threads
> (tens of thousands).

Actually the real reason the 4K stacks were introduced IIRC was that
the VM is not very good at allocation of order > 0 pages and that only
using order 0 and not order 1 in normal operation prevented some stalls.

This rationale also goes back to 2.4 (especially some of the early 2.4
VMs were not very good) and the 2.6 VM is generally better and on
x86-64 I don't see much evidence that these stalls are a big problem
(but then x86-64 also has more lowmem).

Note that your proposal doesn't change this at all.

I personally think 4K stacks are a bad idea because code 
is always getting more complex and having more stack is 
a very useful safety margin.

> A random thought occurred to me: in a system with so many
> threads most of them are not executing anyway, even on
> that gigantic Altix machines. Do they all need to have
> kernel stack, all the time? I mean: the process which
> is running in user space is not using kernel stack at all.
> Process which is not running on a CPU right now
> is not using it either.

Actually processes that sleep do use the stack.
Take a look at Sysrq-t output some time. Pretty much 
all sleepers have some context.

Only processes currently running in user land do not use
the kernel stack, but there are very little of them
(never more than you have CPUs) 

-Andi

Re: Does process need to have a kernel-side stack all the time?

[Denys Vlasenko]

On Monday 14 April 2008 19:44, Andi Kleen wrote:
> > A lot of effort went into minimizing of stack usage.
> > If I understand it correctly, one of the reasons for this
> > was to be efficient and not have lots of pages
> > used for stacks when we have a lot of threads
> > (tens of thousands).
> 
> Actually the real reason the 4K stacks were introduced IIRC was that
> the VM is not very good at allocation of order > 0 pages and that only
> using order 0 and not order 1 in normal operation prevented some stalls.
> 
> This rationale also goes back to 2.4 (especially some of the early 2.4
> VMs were not very good) and the 2.6 VM is generally better and on
> x86-64 I don't see much evidence that these stalls are a big problem
> (but then x86-64 also has more lowmem).
> 
> Note that your proposal doesn't change this at all.

Actually, it does, because if you have only N*no_of_CPUs stacks,
you can allocate them upfront, making fragmentation a non-issue.

However, the proposal doesn't look viable anyway.
--
vda

Re: Does process need to have a kernel-side stack all the time?

[Chris Snook]

Denys Vlasenko wrote:
> Hi Ingo,
> 
> You are one of the experts in processes/threads and scheduling
> in Linux kernel, I hope you can answer this question.
> 
> A lot of effort went into minimizing of stack usage.
> If I understand it correctly, one of the reasons for this
> was to be efficient and not have lots of pages
> used for stacks when we have a lot of threads
> (tens of thousands).

If your application is using tens of thousands of threads on hardware that can't 
spare tens of megabytes to ensure that a thread will always have a kernel stack 
when it needs one, your application is horribly misdesigned.

> A random thought occurred to me: in a system with so many
> threads most of them are not executing anyway, even on
> that gigantic Altix machines. Do they all need to have
> kernel stack, all the time? I mean: the process which
> is running in user space is not using kernel stack at all.
> Process which is not running on a CPU right now
> is not using it either. But they do still consume
> at least 4k (or 8k on 64bits) of RAM.

If they're sleeping, they need a kernel stack.  If they're simply scheduled out, 
then your system is massively overloaded, and you need more CPUs or fewer threads.

> Process absolutely must have kernel stack only when
> it is actively running in kernel code (not sleeping),
> right?

It absolutely needs a kernel stack when it's sleeping in the kernel.  It does 
not really need a stack if it's simply scheduled out, but sleeping should be the 
typical case, if the application is designed and configured to operate efficiently.

> Can we have per-CPU kernel stacks instead, so that process
> gets a kernel stack only every time it enters the kernel;
> and make it so that the process which is scheduled away
> from a CPU does not need to have kernel stack?

You're essentially asking us to optimize forkbombs at the expense of 
well-designed applications.  Unless the cost is nearly zero (and it's not) we 
shouldn't do something like this.

> Currently, when process sleeps, we save some
> state in stack, and such a change may require
> some substantial surgery.

Yes, and that surgery will absolutely kill performance on the page fault and I/O 
paths, while only saving a few kilobytes of RAM on well-configured systems.

> Can you tell me whether this is possible at all,
> and how difficult you estimate it to be?

It may be possible, but it's certainly not a good idea.  Applications that 
suffer a performance hit due to kernel stack usage while scheduled out are 
poorly designed and need to be fixed.  The fraction of a percent performance 
boost they'd get from this change is nothing compared to the thousand percent 
speedup they'd get from using threads intelligently.

-- Chris

Re: Does process need to have a kernel-side stack all the time?

[Ingo Molnar]

* Andi Kleen <andi@firstfloor.org> wrote:

> Denys Vlasenko <vda.linux@googlemail.com> writes:
> 
> > A lot of effort went into minimizing of stack usage.
> > If I understand it correctly, one of the reasons for this
> > was to be efficient and not have lots of pages
> > used for stacks when we have a lot of threads
> > (tens of thousands).
> 
> Actually the real reason the 4K stacks were introduced IIRC was that 
> the VM is not very good at allocation of order > 0 pages and that only 
> using order 0 and not order 1 in normal operation prevented some 
> stalls.

no, the primary motivation Arjan and me started working on 4K stacks and 
implemented it was what Denys mentioned: i had a testcase that ran 
50,000 threads before it ran out of memory - i wanted it to run 100,000 
threads. The improved order-0 behavior was just icing on the cake.

	Ingo

Re: Does process need to have a kernel-side stack all the time?

[Andi Kleen]

> no, the primary motivation Arjan and me started working on 4K stacks and 
> implemented it was what Denys mentioned: i had a testcase that ran 
> 50,000 threads before it ran out of memory - i wanted it to run 100,000 
> threads. The improved order-0 behavior was just icing on the cake.

I checked the original changelog and it mentions both with the
dumb reason covered in one sentence and the stall issue deserving
a full paragraph.

Well frankly that was a dumb reason then.  Ok I hadn't imagined you
both really spent time on something dumb :) The stall reason
at least made some sense, although I suspect it is obsolete by now.

My objection to the 100k threads would be less that they
shouldn't be needed (we all know that user space does dumb things), but
that when you have them either with 4k stacks (or 50k threads with 8k
stack) you're dangerously near lowmem exhaustion on 32bit and then
sooner or later the system will have trouble anyways from low lowmem.
It's fundamentally not a reliable setup.

-Andi

Re: Does process need to have a kernel-side stack all the time?

[Arjan van de Ven]

On Wed, 16 Apr 2008 14:47:28 +0200
Ingo Molnar <mingo@elte.hu> wrote:

> 
> * Andi Kleen <andi@firstfloor.org> wrote:
> 
> > Denys Vlasenko <vda.linux@googlemail.com> writes:
> > 
> > > A lot of effort went into minimizing of stack usage.
> > > If I understand it correctly, one of the reasons for this
> > > was to be efficient and not have lots of pages
> > > used for stacks when we have a lot of threads
> > > (tens of thousands).
> > 
> > Actually the real reason the 4K stacks were introduced IIRC was
> > that the VM is not very good at allocation of order > 0 pages and
> > that only using order 0 and not order 1 in normal operation
> > prevented some stalls.
> 
> no, the primary motivation Arjan and me started working on 4K stacks
> and implemented it was what Denys mentioned: i had a testcase that

well that and the fact that RH had customers who had major issues at fewer threads
with 8Kb versus fragmentation.
on 32 bit with a bunch of ram, there's just not enough lowmem around to not have it
fragmented to hell and back.


x86_64 is better off there, it doesn't really have lowmem, and also buddy works better
against fragmentation the bigger the zone it works with it seems
(or at least, the lower the ratio of long term pinned pages is)


-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Does process need to have a kernel-side stack all the time?

[Andi Kleen]

> well that and the fact that RH had customers who had major issues at fewer threads
> with 8Kb versus fragmentation.
> on 32 bit with a bunch of ram, there's just not enough lowmem around to not have it
> fragmented to hell and back.

2.6 VM has much more aggressive defrag heuristics than 2.4. That is what
I meant with likely obsolete.

-Andi

Re: Does process need to have a kernel-side stack all the time?

[Denys Vlasenko]

On Wednesday 16 April 2008 14:47, Ingo Molnar wrote:
> * Andi Kleen <andi@firstfloor.org> wrote:
> 
> > Denys Vlasenko <vda.linux@googlemail.com> writes:
> > 
> > > A lot of effort went into minimizing of stack usage.
> > > If I understand it correctly, one of the reasons for this
> > > was to be efficient and not have lots of pages
> > > used for stacks when we have a lot of threads
> > > (tens of thousands).
> > 
> > Actually the real reason the 4K stacks were introduced IIRC was that 
> > the VM is not very good at allocation of order > 0 pages and that only 
> > using order 0 and not order 1 in normal operation prevented some 
> > stalls.
> 
> no, the primary motivation Arjan and me started working on 4K stacks and 
> implemented it was what Denys mentioned: i had a testcase that ran 
> 50,000 threads before it ran out of memory - i wanted it to run 100,000 
> threads. The improved order-0 behavior was just icing on the cake.

And my "random thought" occurred along the lines "Ingo once ran
100000 threads and then ran out of space for stack... wait a minute!
Why every single one of those threads need to have a stack at the same time?
They sure as hell can't actively use more than NR_CPUS stacks at once!".

Pity it wouldn't work.
--
vda

Re: Does process need to have a kernel-side stack all the time?

[Arjan van de Ven]

On Wed, 16 Apr 2008 15:59:01 +0200
Andi Kleen <andi@firstfloor.org> wrote:

> 
> > well that and the fact that RH had customers who had major issues
> > at fewer threads with 8Kb versus fragmentation.
> > on 32 bit with a bunch of ram, there's just not enough lowmem
> > around to not have it fragmented to hell and back.
> 
> 2.6 VM has much more aggressive defrag heuristics than 2.4. That is
> what I meant with likely obsolete.

it's a question of very simple math though; both the space and the
amount of other pinnings mean you run into a wall.

2.6 is no doubt better, for sure it's better in freeing up memory etc.
It just can't be good enough.

(just to be clear, customers do run 30k threads workloads on 16Mb machines that
also have a sizable inode and dentry cache. you just cannot defragment that to the point
that you can use 8k stacks).




-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Does process need to have a kernel-side stack all the time?

[Arjan van de Ven]

On Wed, 16 Apr 2008 16:20:43 +0200
Denys Vlasenko <vda.linux@googlemail.com> wrote:

> 
> And my "random thought" occurred along the lines "Ingo once ran
> 100000 threads and then ran out of space for stack... wait a minute!
> Why every single one of those threads need to have a stack at the
> same time? They sure as hell can't actively use more than NR_CPUS
> stacks at once!".
> 
> Pity it wouldn't work.

you could make it work ... sort of.
That is, you can deal with the case with apps that sleep on select/poll/sleep
(which is the majority)
by starting out at a small stack (say 512 bytes), and then in the syscall code switch
to a 4Kb stack for all but these 3 "known to not go deep but normal sleepers" syscalls.

I doubt it's worth the complexity, but it very likely could be made to work.... it's just
going to get very messy (how to deal with "current" is just the start of the messyness)


-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org