Work on Tiny Linux Kernel

From eLinux.org
Revision as of 23:26, 10 February 2011 by Tim Bird (Talk | contribs) (Comments: add Rob Landley comment)

Jump to: navigation, search

Work on Tiny Linux Kernel

Summary
Work on Tiny Linux Kernel
Proposer
Wu Zhangjin

Description

Linux has gained more and more new features in recent years but at the same time increased the kernel image size bit by bit. The new features do expand the applications a lot but their increased size also limit the application of Linux in some specific places(e.g. Linux as bootloader, Damn Small Linux, small storage devices using old 2.4 kernel). Is it possible to elimiate or at least lighten this limitation?

The answer is 'Yes' but also 'No'. 'Yes' means there were lots of works on reducing the kernel size, 'No' means more effort need to be taken to achieve the goal.

Some of the existing works have been collected and documented at [1], here lists them and introduces their status:

  • Configuration Options
 [2] documentes about measuring kernel size and configuring the kernel for
 smallest size.
 But more features are not configurable currently, such as kernel and module
 parameters support, random number generator, ptrace system call, they may be
 not necessary for "Linux as bootloader with kexec". So, more efforts should
 be taken to define what is a minimal kernel(e.g. only as bootloader or be
 able to start X, the definition can be application-guided-classified) and
 investigate which features are really necessary for the defined minimal
 kernel. At last a smallest but application-objected-functional features(e.g
 system calls, components) should be documented and provided for each specific
 definition of the minimal kernel and therefore the others should be
 configurable with more patches.
 The size measuring methods introduced in [1] are cool but a full-featured
 size mearsuing and reporting tool(or tools collection) is still missing. Such
 a tool (or tools collection) should be able to generate a detailed size
 report for compiled kernel image, run-time kernel and eventually reduce the
 kernel size automatically or at least provide the 'hotspot' for size
 reducing.
 The report can be divided into several different types and corresponding
 grains. Basic types include component/feature, object, function and data.
 component/feature include init, time, irq, scheduler, mm, fs, drivers...,
 objects are linked with lots of smaller objects, function consists of
 branches (e.g.  switch...case, if...else...), inline functions, data includes
 array, structure If those details can be defined, measured and reported
 carefully, the eventual automatic or manual size reducing may be very cleared
 and easier.
  • The Linux-tiny patchset
 "The Linux Tiny patch set is a collection of patches which can be used to
 make the Linux kernel consume less space. The long-term goal of the
 Linux-tiny project is to mainline these patches. Several patches have been
 mainlined over the last few years, and work continues in this area."
 Although lots of patches have been mainlined, but some of them are still only
 available for 2.6.23. So, more work is needed to forward-port them to the
 latest new kernel version and git repository may be needed to simplify the
 maintaining, testing and eventually speedup the upstream.
  • Compiler options for reducing kernel size
 -Os is already available with CONFIG_CC_OPTIMIZE_FOR_SIZE=y, but the "Section
 garbage collection patchset" is not completely mainlined for a linker
 bug(only affects parisc).  Those patches can shrink kernel size by ~10% by
 improving dead code/data elimination at link time. So, it is really important
 to upstream it completely and more works are needed to make the other kernel
 features survive even with this patchset(e.g. Ftrace and Gcov have been
 broken by this patchset).
  • Runtime size of kernel
 The above methods only focus on the size of the statically compiled image for
 the kernel. However, the kernel also allocates memory dynamically when it
 runs. If the memory size is limited, the runtime size of kernel should be
 concerned(e.g. the corresponding malloc/free should be measured).

And here collects more methods which are missing above:

  • Strip kernel image
 The basic idea here is everything which is useless for the kernel running can
 be removed (if don't consider potential debugging).
 The compiler-generated local symbols can be stripped with "strip -X"
 (CONFIG_STRIP_ASM_SYMS=y), more symbols can be stripped with --discard-all
 and --strip-all, and even more bytes(section table) can be removed by the
 sstrip tool provided by elfkickers [5](or the one from openwrt [6]).
 Specific sections can be removed with "strip -S", If your bootloader support
 binary format of the kernel image, vmlinux.bin can be used instead of vmlinux
 for more sections have been removed by objcopy.
 If the above tools are not enough, a manual stripping method can be
 referenced in "A Whirlwind Tutorial on Creating Really Teensy ELF Executables
 for Linux" [7].
  • Compress kernel image
 To reduce the kernel image size itself is really important, but with
 compression, smaller kernel image size can be gained and the effect is very
 obvious, the current available kernel compression support include gzip,
 bzip2, lzma, lzo and lately XZ embedded becomes available. To get smallest
 size, lzma or XZ embdded may be the best choice, but to consider
 decompression speed, lzo may be the choice, the other two are more or less
 in-between.
 Besides, UPX [10] is another competitive project, which includes those
 features: excellent compression ratio, very fast decompression, no memory
 overhead, safe, universal, portable, extendable and free(Lincensed under GPL
 v2+), another important feature is the compressed packages are
 self-decompressed. But UPX still only work for some architectures, more work
 should be taken to port it for more architectures and their variants.

Ok, then, There are multiple work items here that could be of interest:

  • Define a long-term goal of kernel size reducing
 Define a minimal kernel with the application-guided method(e.g. Use Linux as
 a bootloader or as a kernel for rescue system...), analyze the necessary
 features it needs and make the left features configurable.
 Using linux as a bootloader with kexec may be a candidate of the definition
 of "a minimal kernel". then, the investigation becomes what is necessary for
 a basic scalable bootloader.
  • Make a size measure, report and automatically reducing utility
 Collect all exisiting measuring methods and tools, write new tools and
 eventually build a size-utils tool package. Of course, related documentation
 should be added.
  • Make kernel more configurable
 ** ptrace system call
 ** alram, getitimer, setitimer system call
 ** kernel and module parameters support
 ** remove sysfs support of specific drivers for !CONFIG_SYSFS
 ** random number generators: /dev/{random, urandom}
 ** NR_IRQS, COMMAND_LINE_SIZE, MAX_NR_CON_DRIVER, MAX_NR_CONSOLES ...
 ** convert big static array to configurable variable: e.g. modedb,
    ata_device_blacklist
 ** make "kexec on crash" configurable
 ** make duplicated features configurable: e.g. emulated software FPU and
    hardware FPU support
  • Forward-port Linux-tiny patchset to new kernel version
  • Enhance 'Section garbage collection patchset'
 ** Ensure the other features(e.g. Ftrace, Gcov, Perf...) survive with it
 ** Enhance it for specific architectures (e.g. add -ffunction-sections and
   -fdata-sections for specific arch; move the functions and data in assembly
   to their own sections...)
  • Add sstrip to scripts/
 Can apply the one from openwrt [6] directly.
  • Add or enhance compressed kernel image support
** If the arch doesn't support compressed kernel image support, add it
** Add(or port) more algorithm support: e.g. uImage(compress kernel image
   for U-boot), XZ embedded, UPX.
  • Use/Add light-weight implementation instead of exisiting implementation
** Use BFS instead of CFS
** Port lwip or uip support
  • Convert dynamic probing to static definition
 Mark the variables for probing, run the kernel once, dump out the probed
 value and convert them to macros(e.g. cpu-feature-override support of MIPS).
 The probing include PCI probing, CPU-feature probing ....
 With the method from [15], this converting may be possible to be autmated
 with some enhancement of the gcc or ld.
  • Launch an open project(git repository) to develop/maintain all of

the above work

** Collect and maintain patches, tools and documentations
** Release snapshots for testing
** Upsteam one by one when they are acceptable by mainline

Scope

This should be a long-term project, can not estimate an accurate time for the whole project. but for some specific contents, they are estimated below:

  • Linux-Tiny patchset forward-porting
 Most of them have been ported to 2.6.36 in [1], This porting (for 2.6.39?)
 probably be finished in 1-2 weeks.
  • Add sstrip to scripts/
 This probably can be finished in several hours.
  • Enhance 'Section garbage collection patchset'
 To ensure the other kernel features work with it may need several weeks for
 enough testing. Enhance it for specific architectures may need several weeks
 too, different arch may need different effort, the work for MIPS has been
 finished in [1].
  • Make kernel more configurable
 Basic development for the above proposed part have been finished in [1], but
 only for experimentation in current stage and more effort need for specific
 archs and testing. and some of them may not be acceptable for mainline. so,
 the whole time needed is hard to be estimated, at least several weeks.
  • Add or enhance compressed kernel image support
 Add compressed kernel image support for a new arch may need several weeks,
 add/port uImage, XZ embedded support may be easier in several hours, but
 adding UPX support for specific vmlinux, vmlinuz may need several weeks too.
  • Use/Add light-weight implementation instead of exisiting implementation
 Using BFS instead of CFS is easy if the BFS patch is there, but porting lwIP
 or uIP may be hard, probably several weeks and for specific drivers, more
 time.
  • Convert dynamic probing to static definition
 If only for cpu-feature probing, basic work(only for MIPS currently) has been
 finished in [11] to generate the macros automatcially, porting it to the
 other arch may need several weeks. If consider the other probing and even for
 automatic converting with the method proposed in [15], more work are needed.
  • Define a long-term goal of kernel size reducing
 To define 'a minimal kernel' and the necessary kernel feature may be hard,
 but if only consider the kernel as bootloader with kexec, probably, several
 weeks.
  • Make a size measure, report and automatically reducing utility
 Collect the exisiting tools is easy, but to get a full-featured tool
 collection, probably several weeks are needed.
  • Launch an open project(git repository) to develop/maintain all of

the above work

 To launch a basic project, create the corresponding git repo is easy, may be
 finished in several hours but development and maintaining are long-term.

As the estimation above, this is a long-term project, the basic work may be finished in one year, but the whole kernel size reducing project is long term.

Contractor Candidates

I have already finished some of the above proposed work in [1], So I would be interested in working on some of these items myself.

Related work

https://patchwork.kernel.org/project/linux-parisc/list/?submitter=Denys+Vlasenko

  • [5] sstrip in 'elfkickers: Kickers of ELF' -

http://muppetlabs.com/~breadbox/software/elfkickers.html

  • [6] sstrip from openwrt -

https://dev.openwrt.org/browser/trunk/tools/sstrip/src/sstrip.c

  • [7] A Whirlwind Tutorial on Creating Really Teensy ELF Executables

for Linux - http://muppetlabs.com/~breadbox/software/tiny/teensy.html

http://dev.lemote.com/cgit/linux-loongson-community.git/log/?h=tiny36

http://savannah.nongnu.org/projects/lwip/

Comments

Rob Landley writes:

I note my old rant about a "hello world" kernel: http://www.mentby.com/rob-landley/what-happened-to-linux-tiny.html

Stripping down the Linux kernel by removing stuff is a red queen's race, running to stay in place. You need to be able start with a configuration that does essentially nothing, and then _add_ only what you need. (And that includes things like "do I really need the process scheduler, if I just have a blob of realtime code that fits in a kernel module and I want the system to do nothing but run that blob, monitor two serial ports, and talk to the outside world via netconsole.")

I am reminded of the 2.2 kernel trick where people would bring up interfaces, set up routing and ipchains rules, and then intentionally panic the system (make init exit) so the process scheduler stopped... but the system was still responding to interrupts and thus routing packets. The general idea was "ok, the router's been lototomized and even I can't change the config without a reboot. Just TRY to break into it, I dare you."