A minimal operating system (2K LOC) on QEMU and a RISC-V board | Hacker News Reader

A minimal operating system (2K LOC) on QEMU and a RISC-V board

github.com

87 pointslioeters19 comments

Oberon is not as minimal as this, but it had the same goal: a complete OS, including language, compiler, IDE, etc. that a single student could study and understand in a single university semester.

http://www.projectoberon.net/

It is alive and still being used, worked on and updated.

Documentation:

https://en.wikibooks.org/wiki/Oberon

For comparison FreeRTOS[0] is, at minimum, about 9000 LOC[1] at least according to the article (I don't know when it was written), so 2000 lines is indeed pretty small.

[0]: https://www.freertos.org/ [1]: https://aosabook.org/en/v2/freertos.html

The famous UNIXv6 is also around 9k.

It sounds small, but unfortunately is vague on what exactly it's capable of --- e.g. "file system", if https://github.com/yhzhang0128/egos-2000/blob/main/library/f... is the file that contains it, is more than the 339 lines that were advertised, and appears to be missing the code to process paths. (I was expecting FAT32 or similar, which is definitely doable in that size.)

Also, 2kloc is what I expect to be in a few files at most, not a dozen spread out over (nested!) subdirectories --- that makes it feel much bigger than it really is.

Very nice! Personally would have called the layers earth, grass, and bugs, but that might be misunderstood. Thanks for sharing!

MINIX v3 is an actual OS. Of course, no RISC-V and, definitely, not 2K LOC.

Very useful learning project. It's written in C mostly. Would be cool to do something similar in Rust.

QNX could fit into 2KB of cache I believe. So there's still some room for improvement.

I think you may be mis-remembering something. I am not sure what.

QNX was and is very small, but not small enough to run inside a CPU's cache when it was current and in the news, no. Today, yes, but not in 2kB! 2MB, more like.

The product I can recall that ran inside a CPU's cache was Symbolics OpenGenera.

Genera is an OS written in Lisp for Symbolics Lisp machines. I.e. a CPU that ran a Lisp-like bytecode.

https://en.wikipedia.org/wiki/Genera_(operating_system)

To make OpenGenera, a version for non-Lisp hardware, Symbolics wrote a tiny Lisp interpreter for the DEC Alpha which fit inside the Alpha CPU's cache.

It was described in their paper at the time (circa 1994):

http://pt.withy.org/publications/VLM.html

Later, a version of this was built to run on x86-64 Linux:

https://archives.loomcom.com/genera/genera-install.html

Thanks for the info. I did misremember, it took 45 KB to fit the QNX kernel, as another user linked, so not quite L1 cache sized at the time.

There have been subsequent updates to the Linux runtime:

https://jaoswald.blogspot.com/2020/05/open-genera-vlm-on-lin...

That gets it running on Ubuntu 18.04.

I would love to see this packaged as a Snap or something for more recent Ubuntu versions.

No, there was a demo that fit on a 1.44 MB floppy from the late 90s (and thus only needing to support functionality of the time) [1]. As stated on the page, the kernel itself occupied 45 KB at the time. A current version would need additional lines to support features ubiquitous in modern chips such as having multiple cores.

To put a 2 KB OS into context, the average x86 instruction is going to be around 3-4 bytes, so that OS would need to be around 500 assembly instructions in total.

[1] http://web.archive.org/web/20011106140711/http://www.qnx.com...

Thanks for the links but 45 KB is likely closer to 2 KB then 2K LOC. So I think the point about room for improvements still stands.

A minimal OS that supports the features included in modern ISAs such as ARMv8 or x64 would be way more then 2k LOC, probably more then 20k LOC.

Actually, 45 KB is pretty close to what you might expect from 2 KLOC of C code. Your average line of C will compile down to around 3-5 instructions in ARMv8 and x86-64 at around 3-5 bytes per instruction that is ~10-20 bytes per line.

Also, I was pointing out that 2 KB of executable code you originally suggested for QNX is a suspicious number and should set off warning bells and how to do the back of the envelope calculation to build the intuition for why it is suspicious.

I actually built it. It's a whooooole lot bigger than 45 KB. It's bigger than a 1.44 MB floppy.

    bruce@rip:~/riscv/egos/egos-2000/build/release$ size -t *
       text    data     bss     dec     hex filename
       1552       8    3076    4636    121c cat.elf
       2232       8    3076    5316    14c4 cd.elf
       1440    1076    2048    4564    11d4 clock.elf
       3692    2120    2104    7916    1eec crash1.elf
        424       8    2048    2480     9b0 crash2.elf
    4294256    2496    3400 4300152  419d78 earth.elf
        224       8    2048    2280     8e8 echo.elf
       7144      12    2380    9536    2540 grass.elf
       1136       8    3076    4220    107c ls.elf
        156       8    2048    2212     8a4 pwd.elf
       2928    1076    3076    7080    1ba8 sys_dir.elf
       7972    2120    2132   12224    2fc0 sys_file.elf
       4340      24    3088    7452    1d1c sys_proc.elf
       1736       8    2048    3792     ed0 sys_shell.elf
        188       8    2048    2244     8c4 ult.elf
    4329420    8988   37696 4376104  42c628 (TOTALS)

I'm not sure how the heck earth.elf text section is 4 MB. Sure, it's got a ton of libgcc stuff (e.g. mul/dev emulation) and libc stuff (e.g. big printf stuff). But it gzips to 100k and objdump shows 23676 instructions, which is 94704 bytes. Hex dumping the file, earth.elf is full of 0s from 0x1a9d0 to 0x4ab000 which is 4785712 bytes.

Changing the ISA in the makefile from RV32I to RV32IMAC reduces all the text sizes except earth.elf by 20% to 30%, as expected.

       text    data     bss     dec     hex filename
       1224       8    3076    4308    10d4 cat.elf
       1694       8    3076    4778    12aa cd.elf
        868    1076    2048    3992     f98 clock.elf
       2712    2120    2104    6936    1b18 crash1.elf
        324       8    2048    2380     94c crash2.elf
    4264910    2496    3400 4270806  412ad6 earth.elf
        164       8    2048    2220     8ac echo.elf
       5346      12    2380    7738    1e3a grass.elf
        928       8    3076    4012     fac ls.elf
        110       8    2048    2166     876 pwd.elf
       2066    1076    3076    6218    184a sys_dir.elf
       6074    2120    2132   10326    2856 sys_file.elf
       3474      24    3088    6586    19ba sys_proc.elf
       1350       8    2048    3406     d4e sys_shell.elf
        146       8    2048    2202     89a ult.elf
    4291390    8988   37696 4338074  42319a (TOTALS)

earth.elf might be a spurious file?

Huh, I didn't realize the average line of C code worked out to 3-5 instructions.

It depends on the line! Many lines of C will translate to a single instruction.

Arithmetic expressions generally need one instruction per C operator. Each array access might need one or two extra instructions. A function call will need one instruction to move each argument into place (unless the argument is the result of arithmetic or array/pointer dereference in which case that part is for free), plus one or two instructions to jump to the function being called.

LOC is not instruction. I see it is basically C, so a single LOC (think about an "if" or any loop instruction) would require more than a bunch of MC instructions.

Reply on news.ycombinator.com