Falcon at 05:06, 18 March 2011

2011-03-18T05:06:09Z

Tim Bird: /* Comments */ add Rob Landley comment

2011-02-10T23:26:23Z

‎Comments: add Rob Landley comment

Wmat: added in body of page Work on Tiny Linux Kernel

2011-02-01T20:20:27Z

added in body of page Work on Tiny Linux Kernel

New page

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 ==

* [1] System Size - http://elinux.org/System_Size#Kernel_size_reduction
* [2] Kernel Size Tuning Guide - http://elinux.org/Kernel_Size_Tuning_Guide
* [3] Linux Tiny Project - http://elinux.org/Linux_Tiny
* [4] Section garbage collection patchset -
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
* [8] Fast Kernel Decompression - http://elinux.org/Fast_Kernel_Decompression
* [9] XZ Embedded - http://tukaani.org/xz/embedded.html
* [10] Ultimate Packer for eXecutables - http://upx.sourceforge.net/
* [11] Linux-Tiny for MIPS/Loongson -
http://dev.lemote.com/cgit/linux-loongson-community.git/log/?h=tiny36
* [12] Brain Fuck Scheduler - http://en.wikipedia.org/wiki/Brain_Fuck_Scheduler
* [13] lwIP: A Lightweight TCP/IP stack -
http://savannah.nongnu.org/projects/lwip/
* [14] uIP - http://www.sics.se/~adam/uip/index.php/Main_Page
* [15] Add boot cache to kernel - http://elinux.org/Add_boot_cache_to_kernel

== Comments ==

[[Category:Project proposals 2011]]

← Older revision		Revision as of 23:26, 10 February 2011
Line 289:		Line 289:

	== Comments ==		== 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."
		+


	[[Category:Project proposals 2011]]		[[Category:Project proposals 2011]]

@@ Line 8: / Line 8: @@
 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
+time has increased the kernel image size bit by bit. The new features do expand
-applications a lot but their increased size also limit the application of Linux
+the applications a lot but their increased size also limit the application of
-in some specific places(e.g. Linux as bootloader, Damn Small Linux, small
+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
+storage devices using old 2.4 kernel). Is it possible to eliminate or at least
 lighten this limitation?
@@ Line 108: / Line 108: @@
    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
+   size, lzma or XZ embedded may be the best choice, but to consider
    decompression speed, lzo may be the choice, the other two are more or less
    in-between.
@@ Line 261: / Line 261: @@
 == Contractor Candidates ==
-I have already finished some of the above proposed work in [1], So I would be
+I have already finished some of the above proposed work in [11], So I would be
 interested in working on some of these items myself.

Work on Tiny Linux Kernel - Revision history

Falcon at 05:06, 18 March 2011

Tim Bird: /* Comments */ add Rob Landley comment

Wmat: added in body of page Work on Tiny Linux Kernel