Skip to contentSkip to conversation

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

DISCUSSION Denys Vlasenko 6 participants 14 messages Apr 14, 2008 – Apr 16, 2008

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 29 lines · 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?

Quoted 6 lines

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

#2 lore raw
Quoted 5 lines · Denis V. Lunev
Quoted 4 lines · Denys Vlasenko

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

Quoted 7 lines
Quoted 2 lines

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

#3 lore raw
Quoted 4 lines · Denys Vlasenko

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

#4 lore raw
In reply to Denys Vlasenko
Quoted 5 lines · Denys Vlasenko

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.

Quoted 7 lines

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

#5 lore raw
Quoted 10 lines · Andi Kleen
Quoted 5 lines

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.

Quoted 6 lines

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

#13 lore raw
In reply to Denys Vlasenko
Quoted 10 lines · 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).

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.

Quoted 8 lines

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.

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 2 lines

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

#6 lore raw
In reply to Andi Kleen
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Denys Vlasenko

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).

Quoted 4 lines

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

#7 lore raw
Quoted 5 lines

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

#8 lore raw
In reply to Ingo Molnar
Quoted 11 lines · On Wed, 16 Apr 2008 14:47:28 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Denys Vlasenko

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).

Quoted 7 lines
Quoted 4 lines

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)

Signature · 3 lines
If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#9 lore raw
Quoted 5 lines

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

#11 lore raw
In reply to Ingo Molnar
Quoted 15 lines · Ingo Molnar
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Denys Vlasenko

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).

Quoted 4 lines

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.

Quoted 4 lines

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

#10 lore raw
In reply to Andi Kleen
Quoted 8 lines · On Wed, 16 Apr 2008 15:59:01 +0200 Andi Kleen <[email protected]> wrote:
Quoted 5 lines

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).

Signature · 3 lines
If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#12 lore raw
In reply to Denys Vlasenko
Quoted 8 lines · On Wed, 16 Apr 2008 16:20:43 +0200 Denys Vlasenko <[email protected]>…

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)

Signature · 3 lines
If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org