From: eLinux.org

Kernel Small Stacks

Here is some random information about small kernel stack sizes.

The default stack size for a process running in kernel space is 8K (as
of 2011).

There used to be an option on x86 to reduce the stack size to 4K. And
indeed there were efforts in 2006 to make this the default stack size.
However, using a small stack opens up the dangerous possibility that the
stack will overflow, causing a kernel hang.

Besides wasting memory, if the stack space is not really needed, 8K
stacks also have an effect on, and are affected by, general kernel
memory allocation. To create an 8K stack requires an order-1 allocation,
meaning that 2 contiguous physical pages must be allocated together in
order to create a new process stack. If memory has become fragmented, it
may be impossible to fulfill an order-1 allocation, even though
individual pages of physical memory may be free. Thus 4K stack
allocations (order-0 allocations) are more likely to succeed. This is
important for systems operating under extreme memory pressure.

There were years of debate on the kernel mailing list about whether 4K
stacks should be the default, and lots of bug reports that ended up
being caused stack overflows with 4K stacks enabled. The option to
support 4k stacks on x86 was removed in 2010, from kernel version 2.6.37
with this commit: dcfa726280116dd31adad37da940f542663567d0

Contents

Historical information on 4K Stacks

Here are some articles and links to information about 4K stacks:

Stack layout

The kernel stack is laid out with the stack pointer at the top of each
stack (at the highest stack address), growing downward for each function
call and stack allocation. The thread_info structure for a process is
at the bottom of the stack. There is no physical mechanism to detect, at
allocation time, if the stack pointer wanders into the thread_info area
of the stack. Hence, if the stack overflows (the stack pointer goes into
the thread_info area), the behavior of the system is undefined.

Stack structure:

  1. top     +----------------+
  2.         | return vals    |
  3.         |   & local vars |
  4.         | ...            |
  5.         |                |
  6.         |                |
  7.         | 0's            |
  8.         | thread_info    |
  9. bottom  +----------------+

Stack measuring/monitoring mechanisms

Because of previous efforts to conserve stack space, there are actually
a few different mechanisms for monitoring the kernel stack usage. Some
tools report on the static size of stack usage by kernel functions (a
check which is done by either the compiler or a separate tool operating
on the kernel binary), and some mechanisms can report on actual stack
utilization at runtime.

CONFIG_FRAME_WARN

This kernel configuration option passes an option to the compiler to
cause it to emit a warning when a static stack size for a routine is
detected that is larger than the specified threshold. It requires gcc
version 4.4 or later in order to work.

The gcc option used is “-Wframe-larger-than=xxx”.

By default, CONFIG_FRAME_WARN has the value of 1024, but you can set
it to any value from 0 to 8192.

Here is a sample of build output with this option configured to 256:

  1.   ...
  2.   CC      ipc/msg.o
  3.   CC      ipc/sem.o
  4.  .../linux-3.0.y/ipc/sem.c: In function 'semctl_main.clone.7':
  5.  .../linux-3.0.y/ipc/sem.c:1021:1: warning: the frame size of 520 bytes is larger than 256 bytes
  6.  .../linux-3.0.y/ipc/sem.c: In function 'sys_semtimedop':
  7.  .../linux-3.0.y/ipc/sem.c:1514:1: warning: the frame size of 472 bytes is larger than 256 bytes
  8.   CC      ipc/shm.o
  9.   CC      ipc/ipcns_notifier.o

checkstack.pl

The kernel source includes a script to perform static stack analysis
called scripts/checkstack.pl.

Usage is as follows:

  1. $(CROSS_COMPILE)objdump -d vmlinux | scripts/checkstack.pl [arch]

Replace [arch] with the architecture of the kernel being analyzed.
Several architectures are supported, including arm, mips and x86. You
should use a cross-objdump that matches the architecture you compiled
the kernel for. For example, if you used: arm-gnueabi-linux-gcc as your
compiler, you would use arm-gnueabi-linux-objdump as your object dump
program. This should have been included in your cross-compiler toolchain
package.

Below is some sample output from using checkstack.pl. Note that the file
is first dumped to an assembly file (.S), and then piped to
checkstack.pl. You can examine the assembly file to see in detail the
instructions used to reserve space on the stack, for routines of
interest found by checkstack.pl.

An item in brackets is a module name, in case of a loadable module. The
number at end is stack depth detected for function. The Leading value is
the address of the stack reservation code.

  1. $ arm-eabi-objdummp -d vmlinux -o vmlinux-arm.S
  2. $ cat vmlinux-arm.S | scripts/checkstack.pl arm
  3. 0x0012c858 nlmclnt_reclaim [vmlinux-arm.o]:             720
  4. 0x0025748c do_tcp_getsockopt.clone.11 [vmlinux-arm.o]:  552
  5. 0x00258d04 do_tcp_setsockopt.clone.14 [vmlinux-arm.o]:  544
  6. 0x000b2db4 do_sys_poll [vmlinux-arm.o]:                 532
  7. 0x00138744 semctl_main.clone.7 [vmlinux-arm.o]:         532
  8. 0x00138ec4 sys_semtimedop [vmlinux-arm.o]:              484
  9. 0x000c5618 default_file_splice_read [vmlinux-arm.o]:    436
  10. 0x00251de4 do_ip_setsockopt.clone.22 [vmlinux-arm.o]:   416
  11. 0x00191fd4 extract_buf [vmlinux-arm.o]:                 408
  12. 0x0019bc24 loop_get_status_old [vmlinux-arm.o]:         396
  13. 0x000e6f88 do_task_stat [vmlinux-arm.o]:                380
  14. 0x0019b8f0 loop_set_status_old [vmlinux-arm.o]:         380
  15. 0x002078f0 snd_ctl_elem_add_user [vmlinux-arm.o]:       376
  16. 0x0026267c tcp_make_synack [vmlinux-arm.o]:             372
  17. 0x00127be4 nfs_dns_parse [vmlinux-arm.o]:               368
  18. 0x000b2240 do_select [vmlinux-arm.o]:                   340
  19. 0x001f6f10 mmc_blk_issue_rw_rq [vmlinux-arm.o]:         340
  20. 0x001726a0 fb_set_var [vmlinux-arm.o]:                  336
  21. 0x000c58d0 __generic_file_splice_read [vmlinux-arm.o]:  316
  22. 0x0022a074 dev_seq_printf_stats [vmlinux-arm.o]:        316
  23. 0x0006383c tracing_splice_read_pipe [vmlinux-arm.o]:    308
  24. 0x000c53c8 vmsplice_to_pipe [vmlinux-arm.o]:            308
  25. 0x002512b4 do_ip_getsockopt [vmlinux-arm.o]:            304
  26. 0x00225f68 skb_splice_bits [vmlinux-arm.o]:             300

stack_size

Below are some results for static analysis of function stack depth in
the Linux kernel, using ‘stack_size’. (stack_size is a custom tool
written by Tim Bird, before he found out about checkstack.pl.)

See this kernel message for a patch containing ‘stack_size’:
https://lkml.org/lkml/2011/10/18/479

ARM results

The following results include the reduction in size for ‘struct
poll_wqueue’:

  1. $ ./stack_size vmlinux-arm
  2. ============ RESULTS ===============
  3. number of functions     = 14371
  4. max function stack depth= 736
  5. function with max depth = nlmclnt_reclaim
  7. Function Name                    Stack Depth
  8. =====================            ===========
  9. __generic_file_splice_read        352
  10. do_select                         376
  11. loop_set_status_old               392
  12. snd_ctl_elem_add_user             408
  13. extract_buf                       432
  14. default_file_splice_read          472
  15. sys_semtimedop                    520
  16. semctl_main.clone.7               560
  17. do_sys_poll                       568
  18. nlmclnt_reclaim                   736

x86_64 results

  1. $ ./show_stacks_x86_64.py vmlinux-x86_64.o
  2. ============ RESULTS ===============
  3. number of functions     = 29587
  4. max function stack depth= 1208
  5. function with max depth = security_load_policy
  7. Function Name                    Stack Depth
  8. =====================            ===========
  9. x86_schedule_events               632
  10. drm_crtc_helper_set_mode          632
  11. sys_semtimedop                    664
  12. do_task_stat                      712
  13. node_read_meminfo                 760
  14. default_file_splice_read          792
  15. do_select                         920
  16. nlmclnt_reclaim                   936
  17. do_sys_poll                      1048
  18. security_load_policy             1208

CONFIG_DEBUG_STACK_USAGE

There is kernel feature to output the stack usage of each process, as
well as the process that uses the most stack in the system. This is
controlled by the kernel configuration option
CONFIG_DEBUG_STACK_USAGE.

This option modifies the process creation path so that the stack is
initialized with all zeros. At any time, a request can be made to
measure the stack depth of all running processes. This is calculated by
measuring the amount of zeros from the end of thread_info to the first
non-zero item on each stack.

In more detail, it does the following:

  • at process creation time, fills the stack with zeros (kernel/fork.c)
  • on sysrq ‘t’, show free space, from call to stack_not_used()
    (kernel/sched.c)
    • it shows as 0 otherwise ??
  • define check_stack_usage(), which emits printks on each low-water
    hit
    • low-water appears to be global over all stacks
    • check_stack_usage() is only called on process exit, so you
      might not know about a problem process until very late
  • stack_not_used() is defined in include/linux/sched.h. It counts
    the number of zero bytes following the end of thread_info going up.

As the systems runs, any time the stack low-water mark is exceeded, then
the kernel prints a report (logs it to the kernel message log). This can
be viewed with the dmesg command:

Here is example output, greping the kernel message log for “greatest”:

  1. # dmesg | grep greatest
  2. kworker/u:0 used greatest stack depth: 10564 bytes left
  3. busybox used greatest stack depth: 9512 bytes left
  4. busybox used greatest stack depth: 9504 bytes left
  5. grep used greatest stack depth: 9372 bytes left
  6. init used greatest stack depth: 9028 bytes left

To get a report on the stack usage of currently running processes, you
use ‘t’ with sysrq. For example:

  1. $ echo t >/proc/sysrq-trigger

A stack dump for each process is shown, along with stack usage
information.

Here is some sample output:

  1. $ echo t >/proc/sysrq-trigger
  2. $ dmesg | grep -v [[]
  3.   task                PC stack   pid father
  4. init            S 802af8b0   932     1      0 0x00000000
  5. kthreadd        S 802af8b0  2496     2      0 0x00000000
  6. ksoftirqd/0     S 802af8b0  2840     3      2 0x00000000
  7. kworker/0:0     S 802af8b0  2776     4      2 0x00000000
  8. kworker/u:0     S 802af8b0  2548     5      2 0x00000000
  9. migration/0     S 802af8b0  2704     6      2 0x00000000
  10. migration/1     S 802af8b0  2704     7      2 0x00000000
  11. kworker/1:0     S 802af8b0  2560     8      2 0x00000000
  12. ksoftirqd/1     S 802af8b0  3024     9      2 0x00000000
  13. khelper         S 802af8b0  2824    10      2 0x00000000
  14. sync_supers     S 802af8b0  2872    11      2 0x00000000
  15. bdi-default     S 802af8b0  2584    12      2 0x00000000
  16. kblockd         S 802af8b0  2824    13      2 0x00000000
  17. khubd           S 802af8b0  2744    14      2 0x00000000
  18. rpciod          S 802af8b0  3024    15      2 0x00000000
  19. kworker/0:1     S 802af8b0  1240    16      2 0x00000000
  20. kswapd0         S 802af8b0  2848    17      2 0x00000000
  21. fsnotify_mark   S 802af8b0  2632    18      2 0x00000000
  22. nfsiod          S 802af8b0  3024    19      2 0x00000000
  23. kworker/u:1     S 802af8b0  2840    20      2 0x00000000
  24. hoge            S 802af8b0  3024    23      2 0x00000000
  25. kworker/1:1     S 802af8b0  1716    24      2 0x00000000
  26. flush-0:13      S 802af8b0  2528    28      2 0x00000000
  27. telnetd         S 802af8b0  1848    48      1 0x00000000
  28. ash             R running   1264    56      1 0x00000000

Stack tracer in ftrace

For detailed instructions, see:
Ftrace#Find_deepest_kernel_stack

Rough notes:

  • Turn on CONFIG_STACK_TRACER in kernel config
  • pass ‘stacktrace’ on kernel command line, or at runtime do:
  • echo 1 >/proc/sys/kernel/stack_tracer_enabled
  • mount -t debugfs none /sys/kernel/debug
  • \
  • cat /sys/kernel/debug/tracing/stack_trace

See http://lwn.net/Articles/295955/

Stack limit patches

Sony has a series of patches which implement a stack guard page, and use
that to show a backtrace if the process uses more than a specified
amount in its kernel stack. In essence, this creates a hard failure for
a controlled stack overflow event.

These patches do the following: Add the config options:

  • CONFIG_SNSC_DEBUG_STACK_LIMIT - perform stack layout changes
  • CONFIG_SNSC_SUPPORT_4KB_MAPPING - re-map kernel memory for 4K
    TLB mappings
  • CONFIG_SNSC_DEBUG_STACK_LIMIT_MANUAL - allow a user-specified
    starting stack size

the patches do several things:

  • change the stack layout to place thread_info at the top of the
    stack rather than at the bottom
  • change the stack size to 16KB (order 2)
  • allow configuring the default starting position of the stack, to
    simulate an arbitrary stack size (default is right below
    thread_info)
  • remap the kernel memory so that 4KB mappings are used
    • this allows unmapping the bottom page of the stack, so that a
      fault occurs when the page is accessed (on a stack overflow for
      a manually configured small stack)
    • this is only turned on if you specify ‘use_4kb_mapping’ on the
  • unmap the bottom page of the stack (the guard page)
    • this is only turned on if you specify ‘unmap_stack’

[ FIXTHIS - need to add more to this section]

ARM 4K Stacks

In October of 2011, Tim Bird submitted patches to add 4K stack support
for the ARM architecture to the Linux kernel. The patches he submitted
are here:

After some discussion, these patches were not accepted into mainline.

The following points were problems that needed to be addressed for this
patch set:

  1. * Should make this depend on CONFIG_EXPERT (to warn developers who attempt to use this)
  2. * Should add interrupt stacks to ARM to take pressure off of 4K stacks
  3. * Should determine if 4K stacks use case will cause ripple effect and lots of ifdefs and hard maintenance issues throughout the kernel.  In particular, need to look at:
  4.   * %pV recursion in printk.  This is used by several file systems
  5.     * question: for operation or just reporting??

Dave Chinner (here) wrote:

  1. There's a good reason 4k stacks went away: it's
  2. simply not enough space for the deep 60+ function call stacks we see
  3. with even trivial storage stack configurations.
  5. The stack usage on 32 bit ARM and x86 is going to be similar, so
  6. you're going to be fighting a losing battle - there is no stack
  7. space that can be trimmed from most paths. To make matter worse,
  8. there's been stuff done to the storage stack that significantly
  9. increases stack usage since 4k stacks went away (e.g. the on-stack
  10. block plugging changes).
  12. And FWIW, XFS is widely used on ARM based NAS devices, so this isn't
  13. a theoretical problem I'm making up here...

This is a pretty good example of people denying a use case with a red
herring.

Possible mixed stack size feature

One option for realizing most of the benefits of 4K stacks, while
preserving more robustness, would be to utilize mixed stack sizes in the
kernel.

Processes known to exercise only certain, stack-conservative, code paths
in the kernel could utilize 4K stacks, and other processes could utilize
8K (or larger) stacks for safety purposes.

There would have to be a mechanism to support selecting the stack size
at process creation time. One simple mechanism would be to introduce a
child_stack_size parameter in thread_info, settable via /proc, and
use this on the clone system call.

A system to support different-sized stacks by changing the stack size of
already running processes would likely be too complicated to be
practical.

Currently, the method of accessing the thread_info structure for a task
in the kernel relies on the stack size of all processes being consistent
among all processes (and being a power of two). A pointer to
thread_info is obtained by masking the current stack pointer with a
value dependent on the (global) size of the stack. With mixed stack
sizes, a different mechanism would be needed to convert from stack
pointer to thread_info. One method which might work would be to
pre-allocate a stack pool for non-standard-sized stacks, and use pointer
comparison to see if SP fell within the pool. If the pool was exhausted,
the default stack size would be used.

This would work best in the case of a system with an identifiable number
of processes which would use special-sized stacks.

Problems

This area has random notes for stack depth management issues:

Problem routines

do_select, do_sys_poll

The structure ‘struct poll_wqueue’ is a large data structure used for
the select() and poll() system calls to manage a sub-set of the file
descriptors being polled. This structure includes an array of wait
queues which can be used immediately (without requiring or waiting for a
memory allocation) for polling file I/O.

The number of entries in the array of wait queues can be controlled via
macros in include/linux/poll.h

nlm_clnt_reclaim

network lock manager for network filesystems. Not applicable to most
embedded products (except possibly during development).

security_load_policy

An selinux routine, not applicable to embedded.