LZO kernel compression

As Michael stated in his review of the interesting features in Linux 2.6.30, new compression options have been recently added to the kernel. We therefore decided to have a look at those compression methods, from a compression ratio and decompression speed point of view.

This comparison will be based on “self-extractible kernels”, that is, kernel images containing bootstrap code allowing them to extract a compressed image. As underlined in the previous article, this approach is not used on all architectures. Blackfin, notably, chose a different path and compresses the whole kernel image, without including bootstrap code. While this has the clear advantage of making compression much simpler with respect to kernel code, it forces decompression out to the bootloader code.

Each of those methods has its advantages. Indeed, the Blackfin approach relies on the bootloader to provide the necessary functions, so that may be a problem to do things like bypassing u-boot to reduce the boot time. On the other hand, implementing it only once in the bootloader (as architecture-independent code) makes it unnecessary to write the low-level bootstrap code for each architecture in the kernel, which is surely interesting on virtually all architectures, the notable exceptions being x86 and ARM.

Gzip (also known as Zlib or inflate) has been the traditional (and, as a matter of fact, only) method used to compress kernels. Consequently, we’ll use it as the reference in the following tests. Our test environment is as follows:

ARM9 AT91SAM9263 CPU, 200MHz, using the mainline arch/arm/configs/usb-a9263.config.

This comparison includes figures for LZO, a new kernel image compression method that I have contributed to the Linux sources, and which hopefully will make its way into the mainline kernel. LZO support in the kernel is only new for kernel decompression, as it is already used by JFFS2 and UBIFS. LZO is a stream-oriented algorithm, and although its compression ratio is lower than that of gzip, decompression is lightning-fast, as we will soon find out.

So, here are the figures, average on 20 boots with each compression method:

Uncompressed 3.24Mo 200%
LZO 1.76Mo 0.552s 70% 109%
Gzip 1.62Mo 0.775s 100% 100%
LZMA 1.22Mo 5.011s 646% 75%

Bzip2 has not been tested here: the low-level bootstrap file, head.S, only allocates 64Kb for use by malloc() on ARM. Some quick tests showed that the kernel would not extract with less than 3.5Mib of malloc() space. That would require to modify head.S so that malloc can use more memory, which we will not do here. However, given that enough memory is usable on the system, one could well use bzip2. All the other algorithms performed the extraction using the standard 64Kib malloc space.

From the results, we can clearly see that LZMA is nearly unsuitable for our system, and should be considered only if the space constraints for storing the kernel are so tight that we can’t afford to use more space that was is strictly necessary.

LZO looks like a good candidate when it comes to speeding up the boot process, at the expense of some (almost neglectable) extra space. Gzip is close to LZO when it comes to size, although extraction is not as fast. That means that unless you’re hitting corner cases, like only having enough space for a Gzip compressed image but not for one made with LZO, choosing the latter is probably a safe bet.

Besides, the LZO-compressed kernel size is about 54% the size of the uncompressed kernel. As the kernel load time varies linearly with its size, load time for an uncompressed kernel doubles. While 0.55s are won because there’s no need to run a decompression algorithm, you spend twice as much time loading the kernel. This time is not negligible at all compared to the decompression time. Indeed, loading the uncompressed image takes roughly 0.8s. That means that at the cost of slowing down the boot process by 0.15s (compared to an uncompressed kernel), one gets a kernel image which is roughly twice as small. Rather nice, isn’t it?

Crosstool-NG 1.5.0 released, with new features!

Crosstool-NG, the successor of Crosstool, is a tool that automates the complicated process of building a cross-compilation toolchain. It provides a nice menuconfig interface to fine tune the configuration of the toolchain, before creating the toolchain automatically by retrieving, extracting, patching, configuring, compiling and installing the different components in the right order, with the right arguments and configuration.

Yann E. Morin, the maintainer of Crosstool-NG has just announced the release of Crosstool-NG 1.5.0, with the following new features:

  • Support for gcc 4.4
  • Experimental support for canadian-cross toolchains. Canadian-cross toolchains are toolchains that are built on machine A, to run on machine B and generate code for machine C, while usual cross-compilation toolchain are built on machine A, to run on machine A and generate code for machine B
  • Experimental support for AVR32, with support for operation as MMU-less, thanks to the newlib C library

In addition to these important features, bugs have been fixed and improvements have been made. Yann also switched the development of Crosstool-NG from Subversion to Mercurial, in order to ease community participation in the improvement of Crosstool-NG.

By the way, if you are interested in Crosstool-NG, don’t miss Yann E. Morin’s talk at the Embedded Linux Conference Europe 2009. See the program for details.

CALAO boards supported in mainline U-Boot

CALAO SystemsI’m happy to announce that a couple days ago, support for the CALAO SBC35-A9G20, TNY-A9260 and TNY-A9G20 boards made its way into the U-Boot git repository. Sadly, it’s not possible to boot from an MMC/SD card with the SBC35 yet, but it’s something I’m currently working on.

Support for all these cards will be available in the next U-Boot release, due in November.

Faster boot: starting Linux directly from AT91bootstrap

Reducing start-up time looks like one of the most discussed topics nowadays, for both embedded and desktop systems. Typically, the boot process consists of three steps: AT91SAM9263 CPU

  • First-stage bootloader
  • Second-stage bootloader
  • Linux kernel

The first-stage bootloader is often a tiny piece of code whose sole purpose is to bring the hardware in a state where it is able to execute more elaborate programs. On our testing board (CALAO TNY-A9260), it’s a piece of code the CPU stores in internal SRAM and its size is limited to 4Kib, which is a very small amount of space indeed. The second-stage bootloader often provides more advanced features, like downloading the kernel from the network, looking at the contents of the memory, and so on. On our board, this second-stage bootloader is the famous U-Boot.

One way of achieving a faster boot is to simply bypass the second-stage bootloader, and directly boot Linux from the first-stage bootloader. This first-stage bootloader here is AT91bootstrap, which is an open-source bootloader developed by Atmel for their AT91 ARM-based SoCs. While this approach is somewhat static, it’s suitable for production use when the needs are simple (like simply loading a kernel from NAND flash and booting it), and allows to effectively reduce the boot time by not loading U-Boot at all. On our testing board, that saves about 2s.

As we have the source, it’s rather easy to modify AT91bootstrap to suit our needs. To make things easier, we’ll boot using an existing U-Boot uImage. The only requirement is that it should be an uncompressed uImage, like the one automatically generated by make uImage when building the kernel (there’s not much point using such compressed uImage files on ARM anyway, as it is possible to build self-extractible compressed kernels on this platform).

Looking at the (shortened) main.c, the code that actually boots the kernel looks like this:

int main(void)
{
/* ================== 1st step: Hardware Initialization ================= */
/* Performs the hardware initialization */
hw_init();

/* Load from Nandflash in RAM */
load_nandflash(IMG_ADDRESS, IMG_SIZE, JUMP_ADDR);

/* Jump to the Image Address */
return JUMP_ADDR;
}

In the original source code, load_nandflash actually loads the second-stage bootloader, and then jumps directly to JUMP_ADDR (this value can be found in U-Boot as TEXT_BASE, in the board-specific file config.mk. This is the base address from which the program will be executed). Now, if we want to load the kernel directly instead of a second-level bootloader, we need to know a handful of values:

  • the kernel image address (we will reuse IMG_ADDRESS here, but one could
    imagine reading the actual image address from a fixed location in NAND)
  • the kernel size
  • the kernel load address
  • the kernel entry point

The last three values can be extracted from the uImage header. We will not hard-code the kernel size as it was previously the case (using IMG_SIZE), as this would lead to set a maximum size for the image and would force us to copy more data than necessary. All those values are stored as 32 bits bigendian in the header. Looking at the struct image_header declaration from image.h in the uboot-mkimage sources, we can see that the header structure is like this:

typedef struct image_header {
uint32_t    ih_magic;    /* Image Header Magic Number    */
uint32_t    ih_hcrc;    /* Image Header CRC Checksum    */
uint32_t    ih_time;    /* Image Creation Timestamp    */
uint32_t    ih_size;    /* Image Data Size        */
uint32_t    ih_load;    /* Data     Load  Address        */
uint32_t    ih_ep;        /* Entry Point Address        */
uint32_t    ih_dcrc;    /* Image Data CRC Checksum    */
uint8_t        ih_os;        /* Operating System        */
uint8_t        ih_arch;    /* CPU architecture        */
uint8_t        ih_type;    /* Image Type            */
uint8_t        ih_comp;    /* Compression Type        */
uint8_t        ih_name[IH_NMLEN];    /* Image Name        */
} image_header_t;

It’s quite easy to determine where the values we’re looking for actually are in the uImage header.

  • ih_size is the fourth member, hence we can find it at offset 12
  • ih_load and ih_ep are right after ih_size, and therefore can be found at offset 16 and 20.

A first call to load_nandflash is necessary to get those values. As the data we need are contained within the first 32 bytes, that’s all we need to load at first. However, some space is required in memory to actually store the data. The first-stage bootloader is running in internal SRAM, so we can pick any location we want in SDRAM. For the sake of simplicity, we’ll choose PHYS_SDRAM_BASEhere, which we define to the base address of the on-board SDRAM in the CPU address space. Then, a second call will be necessary to load the entire kernel image at the right load address.

Then all we need to do is:

#define be32_to_cpu(a) ((a)[0] << 24 | (a)[1] << 16 | (a)[2] << 8 | (a)[3])
#define PHYS_SDRAM_BASE 0x20000000

int main(void)
{
unsigned char *tmp;
unsigned long jump_addr;
unsigned long load_addr;
unsigned long size;

hw_init();

load_nandflash(IMG_ADDRESS, 0x20, PHYS_SDRAM_BASE);

/* Setup tmp so that we can read the kernel size */
tmp = PHYS_SDRAM_BASE + 12;
size = be32_to_cpu(tmp);

/* Now, load address */
tmp += 4;
load_addr = be32_to_cpu(tmp);

/* And finally, entry point */
tmp += 4;
jump_addr = be32_to_cpu(tmp);

/* Load the actual kernel */
load_nandflash(IMG_ADDRESS, size, load_addr - 0x40);

return jump_addr;
}

Note that the second call to load_nandflash could in theory be replaced by:

load_nandflash(IMG_ADDRESS + 0x40, size + 0x40, load_addr);

However, this will not work. What happens is that load_nandflash starts reading at an address aligned on a page boundary, so even when passing IMG_ADDRESS+0x40 as a first argument, reading will start at IMG_ADDRESS, leading to a failure (writes have to aligned on a page boundary, so it is safe to assume that IMG_ADDRESS is actually correctly aligned).

The above piece of code will silently fail if anything goes wrong, and does no checking at all – indeed, the binary size is very limited and we can’t afford to put more code than what is strictly necessary to boot the kernel.

First Buildroot Developer Day after ELCE, on October 17th in Grenoble, France

Buildroot logoThe first Buildroot Developer Day will take place on Saturday, October 17th in Grenoble, France, just the day after Embedded Linux Conference Europe. This Developer Day aims at allowing Buildroot developers to meet and exchange ideas on the project and its future.

As the number of places is limited, interested candidates are invited to send an e-mail to Peter Korsgaard (jacmet at uclibc dot org) and Thomas Petazzoni (thomas dot petazzoni at free-electrons dot com).

Peter Korsgaard and I are organizing this Developer Day thanks to the sponsorship of Calao Systems (offering the location for the meeting) and Free Electrons (offering free lunch to the participants).

See also the announcement of the mailing list and on Buildroot website.

Embedded Linux Conference Europe 2009 program

GrenobleAs we announced a few months ago, Embedded Linux Conference 2009 will take place in Grenoble, France on October 15th and 16th. The list of sessions has just been published online, and as usual, it is a very exciting list of in-depth technical talks.

Because of my involvement in Buildroot, I’m particularly interested in the numerous talks about embedded Linux build systems: Florian Fainelli will talk about OpenWRT (which is not only dedicated to Wifi routers, but is a generic embedded Linux build system, built as a fork of Buildroot), Gordon Hecker on e2factory (a build system I’ve never heard of until now, but conferences are great to discover new tools and projects), Cedric Hombourger on OpenEmbedded (I will be particularly happy to meet Cedric again since I had the chance to work with him six years ago), Marcin Jusziewicz on OpenEmbedded again, Robert Schwebel on PTXdist and finally Alex de Vries on what seems to be a more generic talk about build systems.

Of course, besides build systems, a lot of other topics will be covered. I’ve noted things such as the talk on Canola by Gustavo Barbieri, the boot time presentation by Grégory Clément, the device tree talks by Wolfram Sang and Vitaly Wool, the talk by Alessandro Rubini in order to meet one of the author of Linux Device Drivers, the power management and clock management talks also.

Free Electrons will obviously be present during this conference :

  • Michael Opdenacker, my colleague, will give a talk entitled Update on boot time reduction techniques
  • Michael, again, will be the chair of a Small Business BOF, which should allow small companies offering services around embedded Linux to meet and exchange their ideas and experience
  • Finally, I will be the co-chair with Peter Korsgaard of a BOF on Buildroot
  • We will share a booth with our partner Calao Systems during the Minalogic Embedded Systems Exhibition. This will be another opportunity to meet.

I hope to see you in October at ELCE !

Add an introduction sequence to a Theora video

FilmTo produce new HD videos from the Embedded Linux Conference, we needed a new script to add an introduction sequence to the videos we processed.

To make all this automatic, and to suppress the need to go through interactive tools (such as kdenlive) to produce a title with a fade-in / fade-out effect, I created a new theora-intro script. The process got much more complex than I expected, but fortunately, I got a lot of valuable advise and help from the Theora mailing list, and could hide all this complexity inside the script. That’s what scripts are for!

A nice feature. compared to the interactive video editors, is that no extra video processing pass is needed. Thanks to this, even a big video file can be processed within a few minutes. Another useful feature is that the script preserves the Ogg metadata (artist, title, location, copyright…).

So, if you wish to add an introduction sequence to your own videos, whatever their initial format, first convert them to Theora using ffmpeg2theora. Then, create a title image for your video, and then run theora-intro on it.

You can find all useful details on our theora-intro page.

ELC 2009 videos

My Colleague Thomas and I had the privilege to participate to the 2009 edition of the Embedded Linux Conference, which took place in San Francisco, on April 6-8. In spite of the weak economy, this event was once again a success. It attracted major developers from the embedded Linux community, as well as participants from all over the word.

Following the tradition, we are proud to release new videos about this event. These videos were shot by Satoru Ueda and Tim Bird (Sony), and by Thomas Petazzoni and Michael Opdenacker (Free Electrons). For the first time, we used an HD camcorder to shoot some of the videos. A higher resolution allows to read the slides projected on the screen. As usual, the videos are released with a Creative Commons Attribution – ShareAlike 3.0 license.

Thomas and I found the following talks particularly interesting:

  • Ubiquitous Linux, by Dirk Hohndel
  • Embedded Linux and Mainline Kernel, by David Woodhouse
  • What are Interrupt Threads and How Do They Work?, by Reece Pollack
  • Visualizing Process Memory, by Matt Mackall
  • KProbes and Systemtap Status, by Tim Bird
  • Deploying LTTng on Exotic Embedded Architectures, by Mathieu Desnoyers
  • Embedded Linux on FPGAs for fun and profit, by Dr John Williams (Petalogix)
  • Linux on Embedded PowerPC porting guide, by Grant Likely
  • Understanding and writing an LLVM Compiler Backend, by Bruno Cardoso Lopes

You may be interested in watching the presentations we made and the BOFs we led:

  • Building Embedded Linux Systems with Buildroot, by Thomas Petazzoni. In these last months, Thomas has made big contributions to this build system.
  • Build tools BOF, by Thomas Petazzoni
  • Update on filesystems for flash storage, by Michael Opdenacker
  • System Size BOF, by Michael Opdenacker

Of course, lots of other talks were very interesting. See the whole list by yourself:

theora-intro

Add an introduction sequence to a Theora video

Introduction

For the needs of producing conference videos, we developed a Python script to add an introduction sequence to a given Ogg/Theora video:

Usage: theora-intro [options] input-video title-image output-video

Adds an introduction to a source Ogg/Theora video, using the given title image

Options:
  --version             show program's version number and exit
  -h, --help            show this help message and exit
  -v, --verbose         Verbose mode
  --artist=ARTIST       Overrides the ARTIST Ogg metadata
  --title=TITLE         Overrides the TITLE Ogg metadata
  --date=DATE           Overrides the DATE Ogg metadata
  --location=LOCATION   Overrides the LOCATION Ogg metadata
  --organization=ORGANIZATION
                        Overrides the ORGANIZATION Ogg metadata
  --copyright=COPYRIGHT
                        Overrides the COPYRIGHT Ogg metadata
  --license=LICENSE     Overrides the LICENSE Ogg metadata
  --contact=CONTACT     Overrides the CONTACT Ogg metadata

Why was this script created?

This script was created especially for people who need to produce multiple videos, typically from the same event. So far, the only way to add an introduction video with fade-in and fade-out was through interactive video editors, such as kdenlive, and this required to encode the video again. Another reason to create a script is that the sequence of commands to run and the amount of data to extract and generate is rather complex. Having a script rather than just a howto thus reduces the risk of errors and mistakes.

Downloads

All the releases of theora-intro can be found here.

How it works

To create an introduction sequence and concatenate it to the input video, theora-intro first needs to collect information from the input video. In particular, it reads the video width, height, the number of frames per seconds, as well as the audio bitrate and sample frequency, which need to be the same in the introduction sequence.

The introduction sequence shows the input title image (scaled), which fades in from a black picture, and eventually fades out to black again. The script actually generates a series of PNG images (using ImageMagick‘s convert utility), and converts this series into a video using ffmpeg2theora. Any input image format should work (JPG, GIF, PNG…), as ImageMagick supports most existing formats.

To be complete, the introduction sequence also needs an audio track. If it didn’t, the output video wouldn’t have any. Therefore, theora-intro generates a silent sample in WAV format, and converts it to Ogg/Vorbis.

The audio and video for the introduction sequence are then merged and concatenated. For some reasons still a bit unclear, the audio tracks of the introduction and input videos need to be resampled, but at last, there is no need to encode the video again. This makes theora-intro much faster than the time it takes to encode the video (just a few minutes even for big video files encoded in several hours).

You can find out more details by reading the code! It shoudn’t be difficult to understand it.

Ogg Metadata

It is useful to produce Ogg/Theora videos with appropriate metadata (artist, title, location, copyright…). If the input video contains such metadata, these metadata are also replicated to the generated video. Note that theora-intro has options to override these metadata when needed, or when there are no such metadata in the input video.

Requirements

This script relies on several software packages and libraries:

In Ubuntu and Debian, you can get the first four packages as follows:

sudo apt-get install vorbis-tools imagemagick ffmpeg2theora oggz-tools

Anyway, if any of the above packages is missing, theora-intro will let you know.

Use in real life

theora-intro was used to produce videos from the 2009 edition of the Embedded Linux Conference.

Known issues

At the moment, videos generated with the latest release still show a few warnings with the ogginfo command:

$ ogginfo elc2009-bird-closing.ogv 
Processing file "elc2009-bird-closing.ogv"...

New logical stream (#1, serial: 376a8b22): type theora
New logical stream (#2, serial: 06fd37a7): type vorbis
Theora headers parsed for stream 1, information follows...
Version: 3.2.1
Vendor: Xiph.Org libTheora I 20081020 3 2 1
Width: 1280
Height: 720
Total image: 1280 by 720, crop offset (0, 0)
Framerate 25/1 (25.00 fps)
Aspect ratio undefined
Colourspace: Rec. ITU-R BT.470-6 Systems B and G (PAL)
Pixel format 4:2:0
Target bitrate: 0 kbps
Nominal quality setting (0-63): 63
User comments section follows...
	TITLE=Tim Bird (Sony)- ELC Closing
	DATE=May 2009
	LOCATION=San Francisco
	ORGANIZATION=Free Electrons
	COPYRIGHT=Free Electrons
	LICENSE=Creative Commons BY-SA 3.0
	CONTACT=feedback@...
	ENCODER=ffmpeg2theora-0.23
Vorbis headers parsed for stream 2, information follows...
Version: 0
Vendor: Xiph.Org libVorbis I 20070622 (1.2.0)
Channels: 2
Rate: 48000

Nominal bitrate: 48.000000 kb/s
Upper bitrate not set
Lower bitrate not set
User comments section follows...
	ENCODER=oggVideoTools 0.8
Warning: Expected frame 5265, got 5266
Warning: Expected frame 5270, got 5269
Warning: Expected frame 12663, got 12664
Warning: Expected frame 12667, got 12666
Warning: Expected frame 13657, got 13658
Warning: Expected frame 13660, got 13659
Warning: Expected frame 14213, got 14214
Warning: Expected frame 14218, got 14217
Warning: Expected frame 14875, got 14876
Warning: Expected frame 14879, got 14878
Warning: Expected frame 17635, got 17636
Warning: Expected frame 17638, got 17637
Vorbis stream 2:
	Total data length: 4322809 bytes
	Playback length: 11m:57.264s
	Average bitrate: 48.214426 kb/s
Logical stream 2 ended
Theora stream 1:
	Total data length: 49233283 bytes
	Playback length: 11m:57.320s
	Average bitrate: 549.080277 kb/s
Logical stream 1 ended

These warnings don’t seem to create any issue in Ogg/Theora players. They are probably caused by an issue in the Ogg Video Tools, and we have reported this to their maintainer.

On the road to Buildroot 2009.08

Buildroot logoAs I posted back in March, the Buildroot project has begun a new life since January. One of the aspects this new life is the fact that stable releases are delivered every three months. So we had one in February (2009.02), one in May (2009.05) and therefore we’re going to have one release soon in August (2009.08).

Peter Korsgaard, Buildroot’s maintainer, has just released 2009.08-rc1, a good opportunity to look at what’s new in Buildroot since the last release. To highlight Free Electrons’ participation in the free software community, it is worth noting that in number of patches, I’m the second most important contributor to Buildroot, right after Peter, the maintainer. It’s really nice that I’ve been able to find enough time to contribute at such a level to Buildroot, and hope to be able to dedicate more time in the future to Buildroot, since we have lots of ideas to improve the project.

Back to the 2009.08 release specifically, in the notable features or improvements, we have :

  • Improvement of external toolchain support. I’ve already posted about this specific feature, that I find very important. Several reports from people using this feature have been received since then, which means that it is a useful feature for some of the Buildroot users. So, we have now support for glibc toolchains, the configuration provided to Buildroot is verified against the real toolchain configuration, the copy of the toolchain libraries to the target has been improved (including the C++ standard library) and other minor improvements have been. I’ve been the major contributor of these improvements, together with the reports provided by Buildroot users
  • Integration of the QT-based configurator. Buildroot uses the kconfig system from the kernel to allow its users to configure the different elements of the system to be built. Until now, only the ncurses interface (make menuconfig) was supported. In the 2009.08, the QT interface (make xconfig) will also be supported, adding a little more userfriendliness to Buildroot. This feature was contributed by Alper Yildirim, and I helped in polishing the remaining issues.
  • Support for the Xtensa architecture has been contribued by Maxim Grigoriev, from Tensilica, the company designing the Xtensa architecture.
  • Cleanup of X.org support. the configuration options were clarified, and mandatory dependencies on useless libraries such as libXt or libXaw were removed, some components were upgraded to fix build issues. It’s also a task I contributed to.
  • Of course, toolchain components have been upgraded (GCC 4.4.1, 2.6.30 kernel headers), new packages have been added (bmon, ctorrent, dosfstools, enchant, gst-plugins-bad, iw, libmms, libnl, netstat-nat, ntfsprogs, sdl_gfx, spawn-fcgi), and many more packages have been upgraded (bind, busybox, coreutils, sqlite, directfb, expat, gamin, gnuconfig, haserl, ipsec-tools, classpath, libcurl, libglib2, liblockfile, libpng, libsoup, libxml2, lighttpd, ltp-testsuite, lvm2, matchbox, memstat, gst-plugins-good, gstreamer, libogg, libvorbis, mplayer, neon, openssl, pciutils, php, qt, ruby, sawman, webkit, wpa-supplicant, xdriver_xf86-input-synaptics, xdriver_xf86-video-intel, xlib_libXfont, xlib_libXft, xlib_libXt, xproto_xproto, xserver-xorg, xutil_makedepend, xutil_util-macros)
  • We’re also paying a lot more attention to the bugs reported in our bugtracker than we used to do in the past. Since 2009.05, 43 reported issues have been fixed, and I except that we will fix some more before the 2009.08 release

Shortly after the 2009.08, we will set the goals for the next 2009.11 release, and I’d like to do a lot of cleanup to make Buildroot easier to use and to understand. We’ll see how things go.

In the mean time, if you’re interested in testing and improving Buildroot, don’t hesitate to grab 2009.08-rc1, try it in your conditions with your package set, and report your issues!