The Kernel Boot Process

The previous post explained how computers boot up right up to the point where the boot loader, after stuffing the kernel image into memory, is about to jump into the kernel entry point. This last post about booting takes a look at the guts of the kernel to see how an operating system starts life. Since I have an empirical bent I’ll link heavily to the sources for Linux kernel 2.6.25.6 at the Linux Cross Reference. The sources are very readable if you are familiar with C-like syntax; even if you miss some details you can get the gist of what’s happening. The main obstacle is the lack of context around some of the code, such as when or why it runs or the underlying features of the machine. I hope to provide a bit of that context. Due to brevity (hah!) a lot of fun stuff - like interrupts and memory - gets only a nod for now. The post ends with the highlights for the Windows boot.

At this point in the Intel x86 boot story the processor is running in real-mode, is able to address 1 MB of memory, and RAM looks like this for a modern Linux system:

RAM contents after boot loader runs
RAM contents after boot loader is done

The kernel image has been loaded to memory by the boot loader using the BIOS disk I/O services. This image is an exact copy of the file in your hard drive that contains the kernel, e.g. /boot/vmlinuz-2.6.22-14-server. The image is split into two pieces: a small part containing the real-mode kernel code is loaded below the 640K barrier; the bulk of the kernel, which runs in protected mode, is loaded after the first megabyte of memory.

The action starts in the real-mode kernel header pictured above. This region of memory is used to implement the Linux boot protocol between the boot loader and the kernel. Some of the values there are read by the boot loader while doing its work. These include amenities such as a human-readable string containing the kernel version, but also crucial information like the size of the real-mode kernel piece. The boot loader also writes values to this region, such as the memory address for the command-line parameters given by the user in the boot menu. Once the boot loader is finished it has filled in all of the parameters required by the kernel header. It’s then time to jump into the kernel entry point. The diagram below shows the code sequence for the kernel initialization, along with source directories, files, and line numbers:

Architecture-specific Linux Kernel Initialization
Architecture-specific Linux Kernel Initialization

The early kernel start-up for the Intel architecture is in file arch/x86/boot/header.S. It’s in assembly language, which is rare for the kernel at large but common for boot code. The start of this file actually contains boot sector code, a left over from the days when Linux could work without a boot loader. Nowadays this boot sector, if executed, only prints a “bugger_off_msg” to the user and reboots. Modern boot loaders ignore this legacy code. After the boot sector code we have the first 15 bytes of the real-mode kernel header; these two pieces together add up to 512 bytes, the size of a typical disk sector on Intel hardware.

After these 512 bytes, at offset 0×200, we find the very first instruction that runs as part of the Linux kernel: the real-mode entry point. It’s in header.S:110 and it is a 2-byte jump written directly in machine code as 0×3aeb. You can verify this by running hexdump on your kernel image and seeing the bytes at that offset - just a sanity check to make sure it’s not all a dream. The boot loader jumps into this location when it is finished, which in turn jumps to header.S:229 where we have a regular assembly routine called start_of_setup. This short routine sets up a stack, zeroes the bss segment (the area that contains static variables, so they start with zero values) for the real-mode kernel and then jumps to good old C code at arch/x86/boot/main.c:122.

main() does some house keeping like detecting memory layout, setting a video mode, etc. It then calls go_to_protected_mode(). Before the CPU can be set to protected mode, however, a few tasks must be done. There are two main issues: interrupts and memory. In real-mode the interrupt vector table for the processor is always at memory address 0, whereas in protected mode the location of the interrupt vector table is stored in a CPU register called IDTR. Meanwhile, the translation of logical memory addresses (the ones programs manipulate) to linear memory addresses (a raw number from 0 to the top of the memory) is different between real-mode and protected mode. Protected mode requires a register called GDTR to be loaded with the address of a Global Descriptor Table for memory. So go_to_protected_mode() calls setup_idt() and setup_gdt() to install a temporary interrupt descriptor table and global descriptor table.

We’re now ready for the plunge into protected mode, which is done by protected_mode_jump, another assembly routine. This routine enables protected mode by setting the PE bit in the CR0 CPU register. At this point we’re running with paging disabled; paging is an optional feature of the processor, even in protected mode, and there’s no need for it yet. What’s important is that we’re no longer confined to the 640K barrier and can now address up to 4GB of RAM. The routine then calls the 32-bit kernel entry point, which is startup_32 for compressed kernels. This routine does some basic register initializations and calls decompress_kernel(), a C function to do the actual decompression.

decompress_kernel() prints the familiar “Decompressing Linux…” message. Decompression happens in-place and once it’s finished the uncompressed kernel image has overwritten the compressed one pictured in the first diagram. Hence the uncompressed contents also start at 1MB. decompress_kernel() then prints “done.” and the comforting “Booting the kernel.” By “Booting” it means a jump to the final entry point in this whole story, given to Linus by God himself atop Mountain Halti, which is the protected-mode kernel entry point at the start of the second megabyte of RAM (0×100000). That sacred location contains a routine called, uh, startup_32. But this one is in a different directory, you see.

The second incarnation of startup_32 is also an assembly routine, but it contains 32-bit mode initializations. It clears the bss segment for the protected-mode kernel (which is the true kernel that will now run until the machine reboots or shuts down), sets up the final global descriptor table for memory, builds page tables so that paging can be turned on, enables paging, initializes a stack, creates the final interrupt descriptor table, and finally jumps to to the architecture-independent kernel start-up, start_kernel(). The diagram below shows the code flow for the last leg of the boot:

Architecture-independent Linux Kernel Initialization
Architecture-independent Linux Kernel Initialization

start_kernel() looks more like typical kernel code, which is nearly all C and machine independent. The function is a long list of calls to initializations of the various kernel subsystems and data structures. These include the scheduler, memory zones, time keeping, and so on. start_kernel() then calls rest_init(), at which point things are almost all working. rest_init() creates a kernel thread passing another function, kernel_init(), as the entry point. rest_init() then calls schedule() to kickstart task scheduling and goes to sleep by calling cpu_idle(), which is the idle thread for the Linux kernel. cpu_idle() runs forever and so does process zero, which hosts it. Whenever there is work to do - a runnable process - process zero gets booted out of the CPU, only to return when no runnable processes are available.

But here’s the kicker for us. This idle loop is the end of the long thread we followed since boot, it’s the final descendent of the very first jump executed by the processor after power up. All of this mess, from reset vector to BIOS to MBR to boot loader to real-mode kernel to protected-mode kernel, all of it leads right here, jump by jump by jump it ends in the idle loop for the boot processor, cpu_idle(). Which is really kind of cool. However, this can’t be the whole story otherwise the computer would do no work.

At this point, the kernel thread started previously is ready to kick in, displacing process 0 and its idle thread. And so it does, at which point kernel_init() starts running since it was given as the thread entry point. kernel_init() is responsible for initializing the remaining CPUs in the system, which have been halted since boot. All of the code we’ve seen so far has been executed in a single CPU, called the boot processor. As the other CPUs, called application processors, are started they come up in real-mode and must run through several initializations as well. Many of the code paths are common, as you can see in the code for startup_32, but there are slight forks taken by the late-coming application processors. Finally, kernel_init() calls init_post(), which tries to execute a user-mode process in the following order: /sbin/init, /etc/init, /bin/init, and /bin/sh. If all fail, the kernel will panic. Luckily init is usually there, and starts running as PID 1. It checks its configuration file to figure out which processes to launch, which might include X11 Windows, programs for logging in on the console, network daemons, and so on. Thus ends the boot process as yet another Linux box starts running somewhere. May your uptime be long and untroubled.

The process for Windows is similar in many ways, given the common architecture. Many of the same problems are faced and similar initializations must be done. When it comes to boot one of the biggest differences is that Windows packs all of the real-mode kernel code, and some of the initial protected mode code, into the boot loader itself (C:\NTLDR). So instead of having two regions in the same kernel image, Windows uses different binary images. Plus Linux completely separates boot loader and kernel; in a way this automatically falls out of the open source process. The diagram below shows the main bits for the Windows kernel:

Windows Kernel Initialization
Windows Kernel Initialization

The Windows user-mode start-up is naturally very different. There’s no /sbin/init, but rather Csrss.exe and Winlogon.exe. Winlogon spawns Services.exe, which starts all of the Windows Services, and Lsass.exe, the local security authentication subsystem. The classic Windows login dialog runs in the context of Winlogon.

This is the end of this boot series. Thanks everyone for reading and for feedback. I’m sorry some things got superficial treatment; I’ve gotta start somewhere and only so much fits into blog-sized bites. But nothing like a day after the next; my plan is to do regular “Software Illustrated” posts like this series along with other topics. Meanwhile, here are some resources:

[Update: Thanks to Marius Barbu for catching a mistake where I wrote "CR3" instead of GDTR]

June 23, 2008 | Filed Under Internals, Linux, Software Illustrated

39 Comments 

Why Brazil Loves Linux

[Disclosure: I am a dual American/Brazilian citizen. I've used Linux since 1996 and Microsoft products since 1990. I like both platforms.]

Brazil often makes Linux-related headlines, the latest being the adoption of KDE in Brazilian public schools. It’s clear that Brazil is enamored with Linux, but why? This is an important question for Microsoft since emerging markets are key to sales growth. Microsoft’s Annual Report 2007 reported that “impressive growth included India, China, and Brazil which all delivered revenue growth that topped 40 percent”, which is much faster than growth in developed countries. These markets are also friendly towards Linux and pose significant challenges for Microsoft. This post is my take on the reasons for Brazil’s fondness of Linux. I speak for Brazil since I was born and raised there, but I think much of this applies to the other BRIC countries and emerging markets in general.

The first and obvious argument is economic: free as in beer is a big deal in Brazil’s economy. The table below contrasts the economics of license costs in the US and in Brazil:

US Brazil
Gross National Income (GNI) per capita $44,710 $4,710
Cost of Windows Vista Business $186 $364
Cost of MS Office 2007 Standard $289 $587
Cost of Business Licenses as % of GNI per capita 1.06% 20.1%
Cost of Windows Vista Home Basic $116 $252
Cost of Office Home/Student $109 $117
Cost of Home Licenses as % of GNI per capita 0.5% 7.8%
All figures in US dollars. An exchange rate of USD$1 = R$1.70 was used to compute the cost of licenses in Brazil.

You might be surprised to learn that Microsoft licenses are nearly twice as expensive in Brazil in absolute terms. I imagine Microsoft charges about the same and Brazil’s brutal tax burden makes up the rest (the taxes are built into the price). But the interesting result is the relative price of licenses in each society, captured as % of GNI per capita. As a proportion of national incomes, business licenses are nineteen times more expensive to Brazilian society and home licenses are fifteen times more expensive. While GNI per capita is not a perfect figure, it reflects the incomes people make, how much they spend to live, and how much they pay in taxes. It is a crucial number when it comes to public policy; it’s not hard to understand why rational policies must dodge licensing costs when possible. If there’s any hope of widespread computer access, then surely we can’t expect people to spend 7.8% of their annual income on Microsoft software licenses alone. The burden on small businesses is also prohibitive. This order-of-magnitude difference is a fundamental problem that can’t be solved by piecemeal license giveaways. Suppose Microsoft gave out Windows and Office wholesale to all schools. Then what happens if those kids need a computer at home or in their parents’ business? License costs are simply out of whack with respect to most of society. Using Linux in public schools, rarely attended by richer kids, seems inescapable.

Notice that I didn’t use Windows Vista Starter Edition in the figures. This is because I find the limitation of three simultaneous programs absurd. It’s hard to believe Microsoft put in such an abominable restriction; it’s one thing to quietly omit features, it’s quite another to slap people on the face with “Sorry, no, only 3 programs! Click OK to continue.” Even the limited hardware supported by Vista Starter can easily run multiple programs, so that’s no excuse. I imagine a kid trying to learn programming in such a machine, trying to run a few tools plus a test application, and being told to bugger off. How is this bridging the digital divide? Besides, there are limitations on buying Vista Starter - a family receiving a donated computer, for example, cannot buy a retail version of it. And to cap it off, if they went ahead and bought OEM, the dollar figure for Vista Starter + Office Home comes to 5% of GNI per capita, still an order of magnitude above the US figure.

Looking at these numbers, you might wonder how Microsoft sales could grow 40% in Brazil last year - I mean, do they even have computers there? It turns out that Brazil has both the 10th largest economy in the world and the 11th worst distribution of income. There are wealthy households, businesses, and government departments to whom license prices matter far less. For example, after the dollar plunge the cost in dollars of a programmer in Brazil is close to that of one in the US, provided the employer is paying all taxes (the norm for mid-size and large businesses). These wealthier pockets comprise a sizable market whose landscape is more similar to the US: labor costs dwarf license costs, MS Office is a near-monopoly, and inertia is in Microsoft’s favor. Since this market is in Brazil’s economy the licensing costs still consume relatively more purchasing power, but Microsoft can definitely compete in these niches. Except there’s more to the story than economics.

Many cultural issues work against Microsoft to mobilize Brazilians in favor of the Penguin. I’ll hit up the three I deem biggest: 1) utter disregard for copyright, 2) strong anti-Microsoft feelings, and 3) Linux alpha geek monopoly. A thorny reality aggravates the first two issues: anti-American sentiment. It’s worth looking at this sentiment for context. The Pew Research Center runs the Pew Global Attitudes Project to track global public opinion on a variety of issues. Their latest report shows continued decline in US image, which has plummeted around the globe in the past 5 years. Here’s the data:

Anti-US sentiment in the world

I was shocked to see these results at first. Things might not be as bleak as the numbers suggest though. Some of the backlash is not structural, but rather directed at the current US Administration. It may well subdue come January 2009. Yet it’s important for American companies to factor this in when thinking about markets abroad. Nothing new there, except for how bad things got. Anti-American sentiment is particularly strong in 3 of the BRIC: Brazil, Russia, and China. (In Brazil this is only a political/ideological thing, one-on-one people are still as friendly as ever towards Americans and everyone else.) Keep these numbers in mind when thinking about the factors below, starting with disregard for copyright.

When I was growing up in Brazil, paying for software licenses was about as natural as a third arm growing out of your back. Whenever you needed software, you’d dial up a friendly pirate and buy a “collection” for, uh, $30. That included, my friends, instant home delivery: the guy would drive to your house and deliver the collection. If you were programming at night, he might even bring you a pizza. The best pirates had good access to the warez scene and could find anything in case you had a custom request. In the collection you’d find cracked versions of several major pieces of software from various manufacturers. How convenient. Borland Delphi? Check. Visual Studio? Check. Windows NT 4.0 Server, Workstation? Check. Linux? Check (saves you the download). It was like MSDN for the whole computer industry! The piracy happened regardless of income levels - people “buying” the software were by no means poor (otherwise they wouldn’t have a computer in the first place, at that point in time). Many could easily afford licenses, yet felt absolutely no qualms about piracy. The whole culture disregarded copyrights deeply. To most people, the pirate was doing honest work: downloading all this stuff, burning it, delivering it. An honorable job.

Things have changed since then, but not much. Copyright enforcement is more serious; piracy within mid-size or large businesses is rare. There is more copyright awareness (or indoctrination, depending on whom you ask). Home users still pirate anything they can though. This is not restricted to software either: visit any campus in Brazil and you’ll see rampant photocopying of text books. Street vendors sell DVDs filled with MP3s, movies, you name it. I’m sure Hollywood execs have nightmares where they’re roaming the streets of Brazil. The culture still expects free distribution and the environment is very hostile to proprietary software licenses.

Before Windows Genuine Advantage, Microsoft’s strategy was to ignore the pirates: sell to the corporations, let everyone else copy it. Now regular people are growing third arms and paying for Windows licenses. Fair enough: middle-class fat cats should not be ripping off your software. The trouble is that nowadays not all cats are fat: years of sound macroeconomic policy have allowed lower-middle-class people to buy computers. This is a change from when I was there. There are now many folks who, though not poor, definitely have a very hard time paying for licenses. They either go to Linux or go unpatched. The need to buy software would effectively keep these families out of computing: they do back flips just to get the hardware itself, in the hopes of giving their children a better shot. And richer people resent paying for software, however messed up that is. Every customer cut off by Windows Genuine Advantage is a possible conversion to Linux or at the very least a little more pressure towards migration. If people had to pay for Office too, there’d be gnashing of teeth. I’m not suggesting Microsoft is responsible for fixing severe income inequality or supporting middle-class free loaders; that’s just the nut they need to crack with a creative revenue model because Linux fits like a glove. On to the next issue.

Vista Starter Limits You to Three Programs
Vista Starter caps you at 3 programs. This is not how you win friends and influence people.

Brazil imported the anti-Microsoft stance common in American geeks, but on top of the usual arguments Microsoft is foreign. This adds fuel to the flame. To the Brazilian Microsoft hater, not only there is an “evil monopoly”, but its profits are repatriated and its jobs are elsewhere. Practices like the 3-program limitation on Vista Starter further erode good will (Brazilians call it the “castrated Windows” among other colorful names). Add a dash of anti-American sentiment and you’ve got some serious resistance. This fiery mood has a strong influence, from the teenager hanging out in #hackers on Brasnet to IT departments to the federal government. Even in a rational self-interest analysis, one might rightly point out that if free/open source software (FOSS) were to wipe out Windows, negative effects on Brazil’s economy are likely minimal. The wealth, jobs, and opportunity created by Microsoft aren’t in Brazil (productivity gains might be, but that’s a whole different argument). The trade offs of a potential Linux/Google take over are different when there’s no national off-the-shelf software industry, plus Google’s revenue model works beautifully in a developing country. This mix of ideological and rational arguments torpedoes Microsoft’s support.

The third cultural issue working for Linux is more subtle. In the US people talk about Microsoft losing the alpha geeks, but in Brazil FOSS has already reached a near-monopoly on them. Again, the standard reasons apply but are augmented by the local realities. Before FOSS, interesting software work was very rare in Brazil and the chance to shape widely used products practically did not exist. Imagine a place where 80% of programmers build boring, low-powered line-of-business applications working in conditions exactly opposite of Peopleware. That’s the US. Make it 99% and you have Brazil. In the US we have a wildly dynamic economy full of start-ups and interesting companies soaking up talent fast, but not so in Brazil. David Solomon, co-author of Windows Internals, was working for DEC at 16. But what if there is no one building a kernel in a 3,000-mile radius? Emigration was the most realistic possibility for interesting work. A 16-year-old would have been out of luck.

The FOSS revolution plus the Internet changed all this. Now people in Brazil can actually develop interesting and widely used programs. We’ve got kernel hackers like Marcelo Tosatti, who maintained the 2.4 Linux kernel series, and Arnaldo Carvalho de Melo, who co-founded the Conectiva distribution. There are RedHat employees, Debian contributors, committers on various projects, and so on. Lua, the programming language, comes from Brazil. There’s a practical advantage in being able to, say, tune a distribution for a particular purpose (e.g., the distribution being delivered to public schools). But beyond that it’s inspiring to finally be able to work with talented people in cool projects and have a chance to participate, rather than be handed down a proprietary product built abroad over which you have zero control. People are excited about and grateful for this. By the time you mix up these elements nearly all talented CS students and alpha geeks are well into the Linux camp. Unlike the US, the dynamic economy isn’t there to add some fragmentation. When these people go on to make technology choices in government or industry, guess what they’ll pick?

So that’s it. I think these are the main factors in Brazil’s love affair with Linux: economics, disregard for copyright, anti-Microsoft sentiment, and massive alpha geek support. These factors feed off each other, all pushing towards Linux. Millions of kids using KDE would impact the work force eventually. If Microsoft is overzealous in their anti-piracy efforts, it might precipitate faster changes in this delicate market. Meanwhile, Google Docs and Open Office are catching on. There are tactical moves Microsoft could make to counter Linux momentum, like a more sustainable licensing model for homes and small businesses (maybe their announced annuity licensing?), better native branding, and perhaps some native development. But Google has done all three already and is very well-liked in Brazil despite the anti-US feelings. My Brazilian friends, even a pragmatic IT manager who plays poker with Microsoft Brazil employees, seem to operate on the assumption that an eventual Linux take over (with some combination of Google/Google Docs/Open Office) is just a matter of time. What holds it back is that all the factors discussed here can spark things up, but until desktop Linux is ready to catch on fire you get much hype and little change. The wood does seem drier and drier, so we’ll see. What do you think?

May 1, 2008 | Filed Under Linux

50 Comments