Before we continue our enumeration of components, let's discuss how a Linux system boots on an ATX-compatible computer. We'll focus on BIOS/MBR for now.1
First, the power button is pressed, which causes the PSU to turn on. Meanwhile, the motherboard begins sending "reset" to the CPU. The PSU, having established voltages within acceptable ranges, sets voltage high on the "PWR_OK" pin. This causes the motherboard's chipset to release the CPU from reset. The CPU then executes the BIOS from system ROM.2 The BIOS performs a power-on self test, and barring any terminal errors continues the boot process. This may involve executing the BIOS of video cards, hard drives, etc.3 After several lifetimes of initialization, which we'll elide for now, the computer is on and it's time to load an operating system from an attached hard drive.
The BIOS initiates this process via interrupt 0x19h, the handler of which makes successive attempts to load a master boot record at memory address 0x7C00 and execute.4 The first sector of a bootable hard drive5 contains contains the MBR6. This contains executable machine code,7 a unique-ish drive identifier,8 two null bytes,9 the partition table which reserves 16 bytes per partition,10 and the terminating two-byte "signature" of 0xAA55.11 Having identified a valid MBR, execution jumps to its memory address. Given the significant storage space restrictions in the MBR, the so-called 1st-stage boot-loader does little else than to locate, load, and execute a larger 2nd-stage boot-loader located somewhere else on the drive. The second-stage boot-loader in turn loads and executes an operating system kernel, in this case the Linux kernel.
The initialization process of the Linux kernel will require a series of articles all its own. For now, we'll move on. When kernel initialization is complete, the final stage of the boot process involves handing control over to a user-space program called init. This program controls the rest of the boot process, and is also responsible for graceful shutdown and reboot. There are customary features and behaviors for an init program, but all that's strictly necessary is that it never exit, for an exit from init will result in a kernel panic. Here we'll need to make another decision, so here we'll resume our analysis of options.
Busybox
This software is a damned treat. It was written with embedded systems and initramfs in mind, providing a thorough and useful set of user-land software. The size constraints of embedded systems have kept it from ballooning uncontrollably as Linux utilities more commonly used on desktop systems have. For not much more than the cost of bash12 you get an init, device node management, networking utilities, archivers, text editors... indeed, all the shell commands you might expect.13 If there's a compelling case why Busybox is an insufficient base system, I'd love to know why.
busybox-1.31.1 cloc .
3726 text files.
3114 unique files.
1727 files ignored.
github.com/AlDanial/cloc v 1.70 T=13.75 s (145.6 files/s, 24038.0 lines/s)
--------------------------------------------------------------------------------
Language files blank comment code
--------------------------------------------------------------------------------
C 675 27959 60252 180543
C/C++ Header 1115 1415 2721 31012
Bourne Shell 179 1556 1468 8658
HTML 10 1853 32 7324
C++ 1 166 62 1197
make 6 307 451 911
yacc 1 93 20 570
Perl 3 100 185 337
lex 1 40 12 303
NAnt script 1 84 0 260
Bourne Again Shell 5 51 94 234
Python 1 12 13 110
Qt Project 1 0 0 33
awk 1 2 8 30
bc 1 10 0 25
diff 1 1 8 15
--------------------------------------------------------------------------------
SUM: 2002 33649 65326 231562
--------------------------------------------------------------------------------
Not-busybox
Assuming we reject busybox, we'll still need to assemble much of what it provides. We'll make some conservative selections going forward, and see where we end up.
sysvinit
Here's a simple standalone init program. Aside init, several other redundant programs are provided, including one for killing everything but init,14 and another which provides a rudimentary logger.15
sysvinit-2.95 cloc .
71 text files.
66 unique files.
38 files ignored.
github.com/AlDanial/cloc v 1.70 T=0.30 s (108.8 files/s, 40593.4 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 21 1262 2218 8004
C/C++ Header 9 51 205 258
make 2 55 25 202
Bourne Shell 1 3 3 28
-------------------------------------------------------------------------------
SUM: 33 1371 2451 8492
-------------------------------------------------------------------------------
coreutils
This is the GNU incarnation of the standard UNIX utilities. It's heavier than all of busybox, and doesn't even give you the shell to run the 76k lines of shell script.
coreutils-8.31 cloc .
2878 text files.
2858 unique files.
484 files ignored.
github.com/AlDanial/cloc v 1.70 T=11.84 s (202.2 files/s, 40526.9 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 870 29351 36181 151337
Bourne Shell 637 24014 20200 75874
C/C++ Header 373 7551 12925 40036
m4 423 2459 2498 36820
make 16 3502 3068 7920
Perl 70 1819 2409 7671
TeX 1 811 3695 7163
yacc 1 279 309 1840
Python 1 12 9 48
sed 2 0 0 16
-------------------------------------------------------------------------------
SUM: 2394 69798 81294 328725
-------------------------------------------------------------------------------
bash
So here's the shell then, too. We're up to 536k lines by now, and we're still missing quite a lot.
bash-5.0 cloc .
1251 text files.
1219 unique files.
755 files ignored.
github.com/AlDanial/cloc v 1.70 T=5.80 s (85.6 files/s, 46369.2 lines/s)
---------------------------------------------------------------------------------------
Language files blank comment code
---------------------------------------------------------------------------------------
C 258 20944 20498 107295
HTML 3 3854 38 26338
Bourne Shell 36 3333 3388 20114
Windows Module Definition 44 2581 11 15096
C/C++ Header 111 2821 3506 7617
TeX 1 821 3462 6762
yacc 2 824 968 5398
m4 4 478 439 4742
Perl 2 535 834 4229
Bourne Again Shell 27 235 346 994
make 3 48 36 110
Assembly 2 11 20 48
awk 1 8 15 24
sed 2 0 0 16
---------------------------------------------------------------------------------------
SUM: 496 36493 33561 198783
---------------------------------------------------------------------------------------
net-tools
We'll need these to manipulate our network interfaces if we pass on busybox. 549,362 and counting.
net-tools-1.60 cloc .
152 text files.
131 unique files.
69 files ignored.
github.com/AlDanial/cloc v 1.70 T=0.26 s (314.7 files/s, 65320.9 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 67 1767 1571 12322
C/C++ Header 11 133 116 680
make 4 87 122 257
Bourne Shell 1 14 56 103
-------------------------------------------------------------------------------
SUM: 83 2001 1865 13362
-------------------------------------------------------------------------------
gzip
Busybox comes with its own implementation of several archive formats implemented in about 14k lines. Meanwhile, just a standalone GNU gzip is about four times fatter. 609,918 lines of code to know, own, and understand and we don't even have a text editor yet.
gzip-1.3.14 cloc .
362 text files.
352 unique files.
70 files ignored.
github.com/AlDanial/cloc v 1.70 T=0.70 s (419.6 files/s, 123880.3 lines/s)
---------------------------------------------------------------------------------------
Language files blank comment code
---------------------------------------------------------------------------------------
Bourne Shell 19 4519 3206 21230
C 86 2697 4765 15743
m4 106 666 742 10168
C/C++ Header 69 1530 2666 5905
TeX 1 731 2941 5619
make 6 628 493 1677
Assembly 1 21 38 179
DOS Batch 1 0 0 18
Perl 1 1 2 12
Windows Module Definition 2 0 0 5
---------------------------------------------------------------------------------------
SUM: 292 10793 14853 60556
eudev
Our machine needs to make new device nodes for when new hardware is connected.16 Let's select one of the cheaper device management daemons from Gentoo. 638,677 lines.
eudev cloc .
205 text files.
203 unique files.
60 files ignored.
github.com/AlDanial/cloc v 1.70 T=0.39 s (371.4 files/s, 101693.6 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 71 4844 3961 22185
C/C++ Header 43 690 853 2124
Perl 2 108 36 1753
XML 4 120 16 1542
make 16 121 8 490
m4 2 74 10 380
Python 2 38 46 225
Bourne Shell 3 10 6 25
Markdown 1 8 0 21
YAML 1 0 0 14
-------------------------------------------------------------------------------
SUM: 145 6013 4936 28759
-------------------------------------------------------------------------------
We're not nearly done selecting the components that would fill the rest of the gaps in our non-busybox system, and we're already at nearly three times the line count. If there are not significant gains to be had from the additional features found in the heftier implementations of these utilities, it would be difficult to justify their presence in a system which much be understood by its maintainers, instead of merely excreted by them. As we proceed, we must remain cognizant of how much complexity we've chosen to accumulate beneath us. Until next time.
- Note that GPT partitioning does not require use of UEFI. This was a point of confusion on my part, and perhaps yours! [↩]
- This is mapped to the memory address 0xFFFFFFF0 on x86. [↩]
- Yes, your computer is made of computers, which are made of... aw hell. [↩]
- If anyone knows what hysterical raisins came up with this address, let me know. [↩]
- Go on, take a look at your own. dd if=/dev/sda of=mbr.bin bs=512 count=1; hexdump mbr.bin [↩]
- 512 bytes due to historic hard drive sector size. These days sector sizes of 4k are common. [↩]
- 0x000-0x1b7 [↩]
- 0x1b8-0x1bb [↩]
- 0x1bc-0x1bd [↩]
- 0x1be-0x1fd [↩]
- Note that your hex editor will display this the other direction on a little-endian architecture. [↩]
- !!!!!!!!!!! [↩]
- Not to mention, a full-featured shell that will happily pretend to be bash for you, if you like. [↩]
- Surely this can be accomplished with a simple shell loop and `kill`? [↩]
- Aside which you probably intend to install a syslog daemon, so why have two? [↩]
- A USB drive or peripheral, perhaps. [↩]
I believe the unique ID in the MBR is a Microsoft invention, not strictly required, though LILO picked it up, to make sure it's booting from the intended disk or something.
One thing I noticed about Busybox is it has a lot of code grabbed from other sources, of mixed quality/readability. Still a much better starting point than the GNU stuff I'd say.
As to the shell - have you used the BB ash much in practice, or looked into the code? The problems I encountered with it were: 1) insufficiently POSIX and/or bash-compatible, some scripts break (sadly I don't seem to have noted which/why); 2) on initial inspection, the code had substantial async signal safety issues (or I was too thick to see how what it was doing could be safe, and it certainly wasn't explained); 3) the input editing was a bit basic for my bash-accustomed fingers. I ended up porting OpenBSD's pdksh fork back to Linux and doing a number of cleanups; it ended up around 20k lines. Probably not the smartest use of an intensive month, in hindsight, and the result still has quite a bit of ugliness, but perhaps it can be of use.
Comment by Jacob Welsh — 2020/01/21 @ 7:39 p.m.
I love the detail you went into here on the boot process, I'd never read it broken down as such.
Allegedly it was Dr. David Bradley of IBM.
I don't have one and haven't felt too many pain points using it via Gales Linux.
re init and logger, Jacob wrote a custom, 47 total line proggy and Gales uses DJB's multilog which is part of daemontools.
re shell, Jacob hasn't written an article about it yet, but given Gales uses shell scripts to build and install programs, he took pdksh and did some serious terraforming on it.
I tried installing
cloc on a gentoo I'm running, but paused for now because it wants me to change my perl.. Nevertheless, from the pressed gksh src directory,wc -l *.h *.cyields a total of 22`080.re device nodes, I wasn't aware busybox could do that. Gales uses MAKEDEV, is that overkill in your opinion ?
I'm going to email the busybox maintainer, Denys Vlasenko, let him know how highly regarded he is and invite him to join the convo. According to his resmue his resume, he's been employed by RedHat since 2008..
Any foreshadowing of topics to come in this series ? Back in December, you expected a 4/5 part series. Has that changed given what you've learned through the process ? If so, no problem, plans change, but am curious to know. Cheers !
Comment by Robinson Dorion — 2020/01/22 @ 12:48 p.m.
Jacob, the unique ID is useful when dealing with LILO installed to external disks. You can't guarantee that Linux will always enumerate block devices in the same order, and I want USB sticks that boot no matter what.
Your description of your experience hacking on pdksh doesn't exactly inspire confidence, meaning no offense. "I spent some time doing a thing and gee I hope it was time well spent." I have indeed used busybox's ash extensively, but I'd rather not trade vague anecdotes here. What scripts broke, are you sure it wasn't their own fault, or otherwise why wasn't it a better use of time to alter the shell built into busybox? Did you try enabling the bash-compatibility flag?
There need to be hard, substantiated reasons to introduce dependencies.
Comment by trinque — 2020/01/26 @ 4:19 p.m.
Robinson, glad you enjoyed it. Regarding the logger, there's a syslog and init in busybox! Why aren't you using those?! Regarding mdev, the same question applies. You have one, and grabbed another. What justified the other?
Four or five parts to this series is probably still accurate. From here I've got a foundation upon which to discuss how V enters the picture. After that, I'm going to produce a summary of all the foregoing and a specification.
Comment by trinque — 2020/01/26 @ 4:24 p.m.
> You can't guarantee that Linux will always enumerate block devices in the same order, and I want USB sticks that boot no matter what.
That's reason enough as far as I can see. Though I naively hope we don't also end up with "renaming eth0 to p3p7zxqw" or the like.
> What scripts broke, are you sure it wasn't their own fault, or otherwise why wasn't it a better use of time to alter the shell built into busybox?
I do sorely miss not having better documented the decision process. I could try to reproduce the failures by following an older version of my build docs once I free up some time.
> Did you try enabling the bash-compatibility flag?
If you mean the compile-time CONFIG_ASH_BASH_COMPAT then yes. Or is there some other I've missed?
> Regarding the logger, there's a syslog and init in busybox!
If I might address this one: I recall you've spoken favorably of "runit". Do you think that kind of process supervision & logging isn't useful? Daemontools was its predecessor (I'm not sure why it needed improving either but that's perhaps another topic). Then if I'm already using that, I'd rather not also have a non-minimal init to deal with.
Comment by Jacob Welsh — 2020/01/26 @ 6:26 p.m.
Da fuck were those ?! Busybox fulla pronz gifs, Sabrina's tits, what.
It just blows one's mind that coreutils threatens the half-milion line mark by now.
Their self-authored narratives are replete with this sort of absolutely intolerable smarm, too, readily explaining "what the fuck happened". The time seemingly not so long ago fileutils & textutils got merged with "sh-utils" to produce the sprawling vomit still stands in my mind as the moment when one threw hands in despair at trying to fucking read all this code. I'm pretty sure it was a degree of magnitude less, though.
Comedic relief also available.
Oh ye, trips down memory lane... why aren't you ever pleasant anymore!
Incidentally, how did 328725 and 198783 add up to yield either 536k or 549,362 ? I'm confused, what gives ?
It comes from ye antique z-80 days, back when memory was 32kb (7FFF) and the interrupts had to be installed somewhere, but memory contiguity was prized, so this pair of 512 sectors (one for code, one for saving the results) were placed at the end. 7FFF - 400 + 1 = 7C00.
Ahhahaha yeeeeeah, okay :D
Comment by Mircea Popescu — 2020/01/27 @ 8:36 a.m.
The short answer is I deferred to Jacob's judgment and underlying mutual manaloning from the shadows. I know he weighed various inits prior to writing his, not sure if busybox's was part of the weighing. Multilog is part of daemontools, which he's using for other purposes. As he acknowledged, he wasn't aware of busybox mdev and MAKEDEV was pulled in via Gentoo the old fashion way.
How V enters the picture and a specification sound like the money, looking forward to both!
Comment by Robinson Dorion — 2020/02/01 @ 7:05 p.m.