trinque

2020/01/20

A Republican OS - Part 3

Filed under: Uncategorized — trinque @ 10:58 p.m.

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.

  1. Note that GPT partitioning does not require use of UEFI. This was a point of confusion on my part, and perhaps yours! []
  2. This is mapped to the memory address 0xFFFFFFF0 on x86. []
  3. Yes, your computer is made of computers, which are made of... aw hell. []
  4. If anyone knows what hysterical raisins came up with this address, let me know. []
  5. Go on, take a look at your own. dd if=/dev/sda of=mbr.bin bs=512 count=1; hexdump mbr.bin []
  6. 512 bytes due to historic hard drive sector size. These days sector sizes of 4k are common. []
  7. 0x000-0x1b7 []
  8. 0x1b8-0x1bb []
  9. 0x1bc-0x1bd []
  10. 0x1be-0x1fd []
  11. Note that your hex editor will display this the other direction on a little-endian architecture. []
  12. !!!!!!!!!!! []
  13. Not to mention, a full-featured shell that will happily pretend to be bash for you, if you like. []
  14. Surely this can be accomplished with a simple shell loop and `kill`? []
  15. Aside which you probably intend to install a syslog daemon, so why have two? []
  16. A USB drive or peripheral, perhaps. []

7 Comments »

  1. 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.

  2. I love the detail you went into here on the boot process, I'd never read it broken down as such.

    If anyone knows what hysterical raisins came up with this address, let me know.

    Allegedly it was Dr. David Bradley of IBM.

    If there's a compelling case why Busybox is an insufficient base system, I'd love to know why.

    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 *.c yields 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..

    Until next time.

    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.

  3. 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.

  4. 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.

  5. > 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.

  6. busybox-1.31.1 cloc .
    3726 text files.
    3114 unique files.
    1727 files ignored.

    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.

    In a few cases, the GNU utilities' default behavior is incompatible
    with the POSIX standard. To suppress these incompatibilities, define
    the `POSIXLY_CORRECT' environment variable. Unless you are checking
    for POSIX conformance, you probably do not need to define
    `POSIXLY_CORRECT'.

    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.

    10 chown fails when the username contains a ’.’ in it.

    That was a problem with now quite old versions of fileutils that are unlikely to be in use anymore. Newer versions fix the problem. This entry is retained only to prevent ’makeinfo’ from renumbering the following entries.

    Comedic relief also available.

    It is extremely unlikely that you will be able to recover a file from the filesystem after you have removed it. It depends upon your operating system and the filesystem used with it. The disk blocks storing the file would have been freed and very likely reused by other files. This is especially true on an active file system. However, having said that disclaimer, it is frequently possible to recover deleted files.

    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 ?

    If anyone knows what hysterical raisins came up with this address

    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.

    Surely this can be accomplished with a simple shell loop and `kill`?

    Ahhahaha yeeeeeah, okay :D

    Comment by Mircea Popescu — 2020/01/27 @ 8:36 a.m.

  7. 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?

    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.

    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.

    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.

RSS feed for comments on this post. TrackBack URL

Leave a comment

+