How we found that the Linux nios2 memset() implementation had a bug!

NIOS II processorNiosII is a 32-bit RISC embedded processor architecture designed by Altera, for its family of FPGAs: Cyclone III, Cyclone IV, etc. Being a soft-core architecture, by using Altera’s Quartus Prime design software, you can adjust the CPU configuration to your needs and instantiate it into the FPGA. You can customize various parameters like the instruction or the data cache size, enable/disable the MMU, enable/disable an FPU, and so on. And for us embedded Linux engineers, a very interesting aspect is that both the Linux kernel and the U-Boot bootloader, in their official versions, support the NIOS II architecture.

Recently, one of our customers designed a custom NIOS II platform, and we are working on porting the mainline U-Boot bootloader and the mainline Linux kernel to this platform. The U-Boot porting went fine, and quickly allowed us to load and start a Linux kernel. However, the Linux kernel was crashing very early with:

[    0.000000] Linux version 4.5.0-00007-g1717be9-dirty (rperier@archy) (gcc version 4.9.2 (Altera 15.1 Build 185) ) #74 PREEMPT Fri Apr 22 17:43:22 CEST 2016
[    0.000000] bootconsole [early0] enabled
[    0.000000] early_console initialized at 0xe3080000
[    0.000000] BUG: failure at mm/bootmem.c:307/__free()!
[    0.000000] Kernel panic - not syncing: BUG!

This BUG() comes from the __free() function in mm/bootmem.c. The bootmem allocator is a simple page-based allocator used very early in the Linux kernel initialization for the very first allocations, even before the regular buddy page allocator and other allocators such as kmalloc are available. We were slightly surprised to hit a BUG in a generic part of the kernel, and immediately suspected some platform-specific issue, like an invalid load address for our kernel, or invalid link address, or other ideas like this. But we quickly came to the conclusion that everything was looking good on that side, and so we went on to actually understand what this BUG was all about.

The NIOS II memory initialization code in arch/nios2/kernel/setup.c does the following:

bootmap_size = init_bootmem_node(NODE_DATA(0),
                                 min_low_pfn, PFN_DOWN(PHYS_OFFSET),
                                 max_low_pfn);
[...]
free_bootmem(memory_start, memory_end - memory_start);

The first call init_bootmem_node() initializes the bootmem allocator, which primarily consists in allocating a bitmap, with one bit per page. The entire bootmem bitmap is set to 0xff via a memset() during this initialization:

static unsigned long __init init_bootmem_core(bootmem_data_t *bdata,
        unsigned long mapstart, unsigned long start, unsigned long end)
{
        [...]
        mapsize = bootmap_bytes(end - start);
        memset(bdata->node_bootmem_map, 0xff, mapsize);
        [...]
}

After doing the bootmem initialization, the NIOS II architecture code calls free_bootmem() to mark all the memory pages as available, except the ones that contain the kernel itself. To achieve this, the __free() function (which is the one triggering the BUG) clears the bits corresponding to the page to be marked as free. When clearing those bits, the function checks that the bit was previously set, and if it’s not the case, fires the BUG:

static void __init __free(bootmem_data_t *bdata,
                        unsigned long sidx, unsigned long eidx)
{
        [...]
        for (idx = sidx; idx < eidx; idx++)
                if (!test_and_clear_bit(idx, bdata->node_bootmem_map))
                        BUG();
}

So to summarize, we were in a situation where a bitmap is memset to 0xff, but almost immediately afterwards, a function that clears some bits finds that some of the bits are already cleared. Sounds odd, doesn’t it?

We started by double checking that the address of the bitmap was the same between the initialization function and the __free function, verifying that the code was not overwriting the bitmap, and other obvious issues. But everything looked alright. So we simply dumped the bitmap after it was initialized by memset to 0xff, and to our great surprise, we found that the bitmap was in fact initialized with the pattern 0xff00ff00 and not 0xffffffff. This obviously explained why we were hitting this BUG(): simply because the buffer was not properly initialized. At first, we really couldn’t believe this: how it is possible that something as essential as memset() in Linux was not doing its job properly?

On the NIOS II platform, memset() has an architecture-specific implementation, available in arch/nios2/lib/memset.c. For buffers smaller than 8 bytes, this memset implementation uses a simple naive loop, iterating byte by byte. For larger buffers, it uses a more optimized implementation, using inline assembly. This implementation copies data per blocks of 4-bytes rather than 1 byte to speed-up the memset.

We quickly tested a workaround that consisted in using the naive implementation for all buffer sizes, and it solved the problem: we had a booting kernel, all the way to the point where it mounts a root filesystem! So clearly, it’s the optimized implementation in assembly that had a bug.

After some investigation, we found out that the bug was in the very first instructions of the assembly code. The following piece of assembly is supposed to create a 4-byte value that repeats 4 times the 1-byte pattern passed as an argument to memset:

/* fill8 %3, %5 (c & 0xff) */
"       slli    %4, %5, 8\n"
"       or      %4, %4, %5\n"
"       slli    %3, %4, 16\n"
"       or      %3, %3, %4\n"

This code takes as input in %5 the one-byte pattern, and is supposed to return in %3 the 4-byte pattern. It goes through the following logic:

  • Stores in %4 the initial pattern shifted left by 8 bits. Provided an initial pattern of 0xff, %4 should now contain 0xff00
  • Does a logical or between %4 and %5, which leads to %4 containing 0xffff
  • Stores in %3 the 2-byte pattern shifted left by 16 bits. %3 should now contain 0xffff0000.
  • Does a logical or between code>%3 and %4, i.e between 0xffff0000 and 0xffff, which gives the expected 4-byte pattern 0xffffffff

When you look at the source code, it looks perfectly fine, so our source code review didn’t spot the problem. However, when looking at the actual compiled code disassembled, we got:

34:	280a923a 	slli	r5,r5,8
38:	294ab03a 	or	r5,r5,r5
3c:	2808943a 	slli	r4,r5,16
40:	2148b03a 	or	r4,r4,r5

Here r5 gets used for both %4 and %5. Due to this, the final pattern stored in r4 is 0xff00ff00 instead of the expected 0xffffffff.

Now, if we take a look at the output operands, %4 is defined with the "=r" constraint, i.e an output operand. How to prevent the compiler from re-using the corresponding register for another operand? As explained in this document, "=r" does not prevent gcc from using the same register for an output operand (%4) and input operand (%5). By adding the constrainst & (in addition to "=r"), we tell the compiler that the register associated with the given operand is an output-only register, and so, cannot be used with an input operand.

With this change, we get the following assembly output:

34:	2810923a 	slli	r8,r5,8
38:	4150b03a 	or	r8,r8,r5
3c:	400e943a 	slli	r7,r8,16
40:	3a0eb03a 	or	r7,r7,r8

Which is much better, and correctly produces the 0xffffffff pattern when 0xff is provided as the initial 1-byte pattern to memset.

In the end, the final patch only adds one character to adjust the inline assembly constraint and gets the proper behavior from gcc:

diff --git a/arch/nios2/lib/memset.c b/arch/nios2/lib/memset.c
index c2cfcb1..2fcefe7 100644
--- a/arch/nios2/lib/memset.c
+++ b/arch/nios2/lib/memset.c
@@ -68,7 +68,7 @@ void *memset(void *s, int c, size_t count)
 		  "=r" (charcnt),	/* %1  Output */
 		  "=r" (dwordcnt),	/* %2  Output */
 		  "=r" (fill8reg),	/* %3  Output */
-		  "=r" (wrkrega)	/* %4  Output */
+		  "=&r" (wrkrega)	/* %4  Output only */
 		: "r" (c),		/* %5  Input */
 		  "0" (s),		/* %0  Input/Output */
 		  "1" (count)		/* %1  Input/Output */

This patch was sent upstream to the NIOS II kernel maintainers:
[PATCH v2] nios2: memset: use the right constraint modifier for the %4 output operand, and has already been applied by the NIOS II maintainer.

We were quite surprised to find a bug in some common code for the NIOS II architecture: we were assuming it would have already been tested on enough platforms and with enough compilers/situations to not have such issues. But all in all, it was a fun debugging experience!

It is worth mentioning that in addition to this bug, we found another bug affecting NIOS II platforms, in the asm-generic implementation of the futex_atomic_cmpxchg_inatomic() function, which was causing some preemption imbalance warnings during the futex subsystem initialization. We also sent a patch for this problem, which has also been applied already.

Posted in Technical | Tagged , , | 6 Comments

Article on the CHIP in French Linux magazine

Free Electrons engineer and Allwinner platform maintainer Maxime Ripard has written a long article presenting the Nextthing C.H.I.P platform in issue #18 of French magazine OpenSilicium, dedicated to open source in embedded systems. The C.H.I.P has even been used for the front cover of the magazine!

OpenSilicium #18

In this article, Maxime presents the C.H.I.P platform, its history and the choice of the Allwinner SoC. He then details how to set up a developer-friendly environment to use the board, building and flashing from scratch U-Boot, the kernel and a Debian-based root filesystem. Finally, he describes how to use Device Tree overlays to describe additional peripherals connected to the board, with the traditional example of the LED.

OpenSilicium #18 CHIP article

In the same issue, OpenSilicium also covers numerous other topics:

  • A feedback on the FOSDEM 2016 conference
  • Uploading code to STM32 microcontrollers: the case of STM32-F401RE
  • Kernel and userspace debugging with ftrace
  • IoT prototyping with Buildroot
  • RIOT, the free operating system for the IoT world
  • Interview of Cedric Bail, working on the Enligthenment Foundation Libraries for Samsung
  • Setup of Xenomai on the Zynq Zedboard
  • Decompression of 3R data stream using a VHDL-described circuit
  • Write a userspace device driver for a FPGA using UIO
Posted in Technical | Tagged , | Leave a comment

Slides from the Embedded Linux Conference

Two weeks ago, the entire Free Electrons engineering team (9 persons) attended the Embedded Linux Conference in San Diego. We had some really good time there, with lots of interesting talks and useful meetings and discussions.

Tim Bird opening the conferenceDiscussion between Linus Torvalds and Dirk Hohndel

In addition to attending the event, we also participated by giving 5 different talks on various topics, for which we are publishing the slides:

Boris Brezillon, the new NAND Linux subsystem maintainer, presented on Modernizing the NAND framework: The big picture.

Boris Brezillon's talk on the NAND subsystem

Antoine Ténart presented on Using DT overlays to support the C.H.I.P’s capes.

Antoine Tenart's talk on using DT overlays for the CHIP

Maxime Ripard, maintainer of the Allwinner platform support in Linux, presented on Bringing display and 3D to the C.H.I.P computer.

Maxime Ripard's talk on display and 3D for the CHIP

Alexandre Belloni and Thomas Petazzoni presented Buildroot vs. OpenEmbedded/Yocto Project: a four hands discussion.

Belloni and Petazzoni's talk on OpenEmbedded vs. Buildroot

Thomas Petazzoni presented GNU Autotools: a tutorial.

Petazzoni's tutorial on the autotools

All the other slides from the conference are available from the event page as well as from eLinux.org Wiki. All conferences have been recorded, and the videos will hopefully be posted soon by the Linux Foundation.

Posted in Conference | Tagged , | Leave a comment

Free Electrons engineer Boris Brezillon becomes Linux NAND subsystem maintainer

Free Electrons engineer Boris Brezillon has been involved in the support for NAND flashes in the Linux kernel for quite some time. He is the author of the NAND driver for the Allwinner ARM processors, did several improvements to the NAND GPMI controller driver, has initiated a significant rework of the NAND subsystem, and is working on supporting MLC NANDs. Boris is also very active on the linux-mtd mailing list by reviewing patches from others, and making suggestions.

Hynix NAND flash

For those reasons, Boris was recently appointed by the MTD maintainer Brian Norris as a new maintainer of the NAND subsystem. NAND is considered a sub-subsystem of the MTD subsystem, and as such, Boris will be sending pull requests to Brian, who in turn is sending pull requests to Linus Torvalds. See this commit for the addition of Boris as a NAND maintainer in the MAINTAINERS file. Boris will therefore be in charge of reviewing and merging all the patches touching drivers/mtd/nand/, which consist mainly of NAND drivers. Boris has created a nand/next on Github, where he has already merged a number of patches that will be pushed to Brian Norris during the 4.7 merge window.

We are happy to see one of our engineers taking another position as a maintainer in the kernel community. Maxime Ripard was already a co-maintainer of the Allwinner ARM platform support, Alexandre Belloni a co-maintainer of the RTC subsystem and Atmel ARM platform support, Grégory Clement a co-maintainer of the Marvell EBU platform support, and Antoine Ténart a co-maintainer of the Annapurna Labs platform support.

Posted in Technical | Tagged , , , , | Leave a comment

Slides from Collaboration Summit talk on Linux kernel upstreaming

As we announced in a previous blog post, Free Electrons CTO Thomas Petazzoni gave a talk at the Collaboration Summit 2016 covering the topic of “Upstreaming hardware support in the Linux kernel: why and how?“.

The slides of the talk are now available in PDF format.

Upstreaming hardware support in the Linux kernel: why and how?

Upstreaming hardware support in the Linux kernel: why and how?

Upstreaming hardware support in the Linux kernel: why and how?

Through this talk, we identified a number of major reasons that should encourage hardware vendors to contribute the support for their hardware to the upstream Linux kernel, and some hints on how to achieve that. Of course, within a 25 minutes time slot, it was not possible to get into the details, but hopefully the general hints we have shared, based on our significant Linux kernel upstreaming experience, have been useful for the audience.

Unfortunately, none of the talks at the Collaboration Summit were recorded, so no video will be available for this talk.

Posted in Conference | Tagged , , | 1 Comment

Free Electrons contributions to Linux 4.5

Adelie PenguinLinus Torvalds just released Linux 4.5, for which the major new features have been described by LWN.net in three articles: part 1, part 2 and part 3. On a total of 12080 commits, Free Electrons contributed 121 patches, almost exactly 1% of the total. Due to its large number of contribution by patch number, Free Electrons engineer Boris Brezillon appears in the statistics of top-contributors for the 4.5 kernel in the LWN.net statistics article.

This time around, our important contributions were:

  • Addition of a driver for the Microcrystal rv1805 RTC, by Alexandre Belloni.
  • A huge number of patches touching all NAND controller drivers and the MTD subsystem, from Boris Brezillon. They are the first step of a more general rework of how NAND controllers and NAND chips are handled in the Linux kernel. As Boris explains in the cover letter, his series aims at clarifying the relationship between the mtd and nand_chip structures and hiding NAND framework internals to NAND. […]. This allows removal of some of the boilerplate code done in all NAND controller drivers, but most importantly, it unifies a bit the way NAND chip structures are instantiated.
  • On the support for the Marvell ARM processors:
    • In the mvneta networking driver (used on Armada 370, XP, 38x and soon on Armada 3700): addition of naive RSS support with per-CPU queues, configure XPS support, numerous fixes for potential race conditions.
    • Fix in the Marvell CESA driver
    • Misc improvements to the mv_xor driver for the Marvell XOR engines.
    • After four years of development the 32-bits Marvell EBU platform support is now pretty mature and the majority of patches for this platform now are improvements of existing drivers or bug fixes rather than new hardware support. Of course, the support for the 64-bits Marvell EBU platform has just started, and will require a significant number of patches and contributions to be fully supported upstream, which is an on-going effort.
  • On the support for the Atmel ARM processors:
    • Addition of the support for the L+G VInCo platform.
    • Improvement to the macb network driver to reset the PHY using a GPIO.
    • Fix Ethernet PHY issues on Atmel SAMA5D4
  • On the support for Allwinner ARM processors:
    • Implement audio capture in the sun4i audio driver.
    • Add the support for a special pin controller available on Allwinner A80.

The complete list of our contributions:

Posted in Technical | Tagged , , , , | Leave a comment

Free Electrons contributing Linux kernel initial support for Annapurna Labs ARM64 Platform-on-Chip

Annapurna Labs LogoWe are happy to announce that on February 8th 2016 we submitted to the mainline Linux kernel the initial support for Annapurna Labs Alpine v2 Platform-on-Chip based on the 64-bit ARMv8 architecture.

See our patch series:

Annapurna Labs was founded in 2011 in Israel. Annapurna Labs provides 32-bit and 64-bit ARM products including chips and subsystems under the Alpine brand for the home NAS, Gateway and WiFi router equipment, see this page for details. The 32-bit version already has support in the official Linux kernel (see alpine.dtsi), and we have started to add support for the quad core 64-bit version, called Alpine v2, which brings significant performance for the home.

This is our initial contribution and we plan to follow it with additional Alpine v2 functionality in the near future.

Posted in Technical | Tagged , , , | Leave a comment

“Porting Linux on ARM” seminar road show in France

CaptronicIn December 2015, Free Electrons engineer Alexandre Belloni gave a half-day seminar “Porting Linux on ARM” in Toulouse (France) in partnership with french organization Captronic. We published the materials used for the seminar shortly after the event.

We are happy to announce that this seminar will be given in four different cities in France over the next few months:

  • In Montpellier, on April 14th from 2 PM to 6 PM. See this page for details.
  • In Clermont-Ferrand, on April 27th from 2 PM to 6 PM. See this page for details.
  • In Brive, on April 28th from 9 AM to 1 PM. See this page for details.
  • Near Chambéry, on May 25th from 9:30 AM to 5/30 PM. See this page for details.
  • Near Bordeaux, on June 2nd from 2 PM to 6 PM. See this page for details.
  • Near Nancy, on June 16th from 2 PM to 6 PM. See this page for details.

The seminar is delivered in French, and the event is free after registration. The speaker, Alexandre Belloni, has worked on porting botloaders and the Linux kernel on a number of ARM platforms (Atmel, Freescale, Texas Instruments and more) and is the Linux kernel co-maintainer for the RTC subsystem and the support of the Atmel ARM processors.

Posted in Conference, Technical | Tagged , , , , | 2 Comments

Free Electrons at the Embedded Linux Conference 2016

Like every year for about 10 years, the entire Free Electrons engineering team will participate to the next Embedded Linux Conference, taking place on April 4-6 in San Diego, California. For us, participating to such conferences is very important, as it allows to remain up to date with the latest developments in the embedded Linux world, create contacts with other members of the embedded Linux community, and meet the community members we already know and work with on a daily basis via the mailing lists or IRC.

Embedded Linux Conference 2016

Over the years, our engineering team has grown, and with the arrival of two more engineers on March 14, our engineering team now gathers 9 persons, all of whom are going to participate to the Embedded Linux Conference.

As usual, in addition to attending, we also proposed a number of talks, and some of them have been accepted and are visible in the conference schedule:

As usual, our talks are centered around our areas of expertise: hardware support in the Linux kernel, especially for ARM platforms, and build system related topics (Buildroot, Yocto, autotools).

We are looking forward to attending this event, and see many other talks from various speakers: the proposed schedule contains a wide range of topics, many of which look really interesting!

Posted in Conference | Tagged , , , | Leave a comment

Free Electrons speaking at the Linux Collaboration Summit

Free Electrons engineers are regular speakers at the Embedded Linux Conference and Embedded Linux Conference Europe events from the Linux Foundation, to which our entire engineering team participates each year.

In 2016, for the first time, we will also be speaking at the Collaboration Summit, an invitation-only event where, as the Linux Foundation presents it, “the world’s thought leaders in open source software and collaborative development convene to share best practices and learn how to manage the largest shared technology investments of our time”.

Collaboration Summit 2016

This event will take place on March 29-31 in Lake Tahoe, California, and the event schedule has been published recently. Free Electrons CTO Thomas Petazzoni will be giving a talk Upstreaming hardware support in the Linux kernel: why and how?, during which we will share our experience working with HW manufacturers to bring the support for their hardware to the upstream Linux kernel, discuss the benefits of upstreaming, and best practices to work with upstream.

With a small team of engineers, Free Electrons has merged over the last few years thousands of patches in the official Linux kernel, and has several of its engineers having maintainer positions in the Linux kernel community. We are happy to take the opportunity of the Collaboration Summit to share some of our experience, and hopefully encourage and help other companies to participate upstream.

Posted in Conference | Tagged , , , , , | Leave a comment