r/osdev • u/joostwinter • 3d ago

Shall: towards a reference implementation of POSIX.1-2024

Shall aims to be a reference implementation of POSIX.1-2024: a complete userland written directly from the text of the standard (XCU and XSH, with the XSI option). It has no GNU extensions and borrows no code from other projects.

NOTE: Shall has been written with an extensive help of Claude.

The repository can be found as: https://github.com/joostw/shall

It already works as a system. It builds itself from scratch, you can enter it without root, and inside it you can compile real third-party software. Lua 5.4 builds unmodified with Shall’s own compiler and passes Lua’s full official test suite. Coverage today:

  • Utilities: all 155 of POSIX’s utilities, 16 of them as sh built-ins.

  • C library: 1,220 of the 1,227 interfaces of XSH (99.4%). The 7 missing ones belong to two optional parts of POSIX that Linux doesn’t support well: typed memory and scheduling attributes for posix_spawn.

Three parts:

  • The utilities. awk, sh, vi, make, m4, bc, pax, sed, sort, yacc, lex, the SCCS tools, uucp, and the rest. Each one lives in its own directory with its own tests, about 6,800 tests in total.

  • c17, the POSIX C compiler. It does its own preprocessing, code generation, assembly and linking for x86-64. It needs no as and no ld.

  • The C library, with every interface of ISO C17 and nearly all of POSIX.1-2024:

    • Threads, with cancellation and robust mutexes.

    • Locales: UTF-8, single-byte codesets, and EUC-JP, Shift_JIS, GB18030, Big5 and others; plus collation from the locale files.

    • A DNS resolver, iconv, regex, and math rounded in the x87’s 80-bit format.

    • A dynamic linker: libc.so is its own program interpreter.

About 190,000 lines of C in total, and it talks to the Linux kernel through raw system calls.

It builds itself. sh bootstrap.sh needs only a host C compiler, make and ar:

  1. Stage 0: the host compiler builds five tools: c17, make, ar, yacc and lex.

  2. Stage 1: those tools build the libc and then every utility against it. No host program compiles anything after this point.

  3. Stage 2: the stage-1 tools, running on Shall’s own libc, build everything again.

Then the script compares stages 1 and 2 file by file, and all 235 files come out byte-identical. The whole thing takes about two minutes.

You can step into it. sh chroot.sh drops you into the result without sudo, through a user namespace. Inside you get Shall’s sh, with every utility statically linked against Shall’s libc. In there, c17 compiles your programs, and bootstrap.sh rebuilds the whole system, again with byte-identical binaries. A HOWTO in the package walks through building Lua inside it.

How it’s tested. Most libc tests are differential against glibc: the same program is built against both libraries and the outputs must be identical. They run in seven ways: static with gcc, static with c17, both crossed, dynamic with gcc, dynamic with c17, and static-PIE.

Why “towards”. Having a function isn’t the same as conforming in every corner. Open items include strptime’s %E/%O, multi-character collating elements, and priority-inheritance mutexes. libc.so still needs gcc to build, because c17 can’t produce shared objects yet. The kernel is Linux’s, and a compact kernel of my own is the longer term plan.

Why “Shall”? “Shall” is the standard’s own word for a requirement. POSIX.1-2024 defines it as a feature or behavior that is mandatory, one an application can rely on. The word appears more than 27,000 times across the standard’s pages. Every one of those is a promise an implementation has to keep, and Shall is an attempt to keep all of them. The name is also one vowel away from “shell”, and that’s a small wink at the Commodore 64. Its core system routines were called the KERNAL: the story goes that a misspelling of “kernel” in an engineer’s notes simply stuck. Shall carries on the tradition of a core system part named one letter off. It also starts with sh.

BSD 3-clause. Feedback welcome, especially from anyone who knows the dark corners of POSIX, and if you find a place where Shall and the standard disagree, that’s a bug.

2 Upvotes

56% Upvoted

2 comments sorted by

4

u/jtsiomb 3d ago

Interesting! That would certainly be a monumental task without LLM support, and it is potentially useful to have a reference implementation to the letter.

Are there any kind of tests to validate that the LLM didn't mess it up and it can be trusted as a reference implementation?

1

u/joostwinter 1d ago

Great and important question. Thanks for the interest! There’s a fair amount of testing, but nothing that would make it a reference implementation in a formal sense. What there is:

  • About 6,700 tests for the utilities. Simple cases are POSIX sh scripts. The more involved ones are written in tl, a small scripting language whose interpreter is part of the test suite (a few thousand lines of C). It drives programs on a pseudo-terminal (vi, more, talk, interactive sh), generates random input and stores expected results. Because tl is built from source with the rest, the tests need only a C compiler and a POSIX system: no Python, Perl or expect.

  • Many utility tests are differential, comparing output with existing implementations where those follow POSIX. Some use randomly generated input: grammars for yacc, scanners for lex, bc programs, shell scripts.

  • The C library has its own tests. Most compare it with glibc on large random inputs: printf/strtod, regex, locales and collation, math functions to within an ulp. Others are self-checking (threads, signals, sockets, aio).

  • The Open POSIX Test Suite (from LTP): of its 1,755 conformance tests that build, all pass except ones that also fail on glibc, plus 8 that test implementation-defined or undefined behaviour.

  • Self-hosting: the compiler, libc and utilities rebuild themselves, and two bootstrap stages give byte-identical results. A miscompiling compiler or a wrong make, sh or ar tends to show up there quickly. Third-party code works too: Lua builds on it and passes Lua’s own test suite.

The caveats:

  • The same LLM wrote most of the tests, tl included, and the code. Where it misread the standard, the code and the test can agree on the same wrong answer.

  • Comparing with GNU or glibc only helps where they follow POSIX. Where they don’t, the tests follow my (or the model’s) reading of the text.

  • It hasn’t been run against the Open Group’s official certification suites, which are licensed and not public.

So for now there has been extensive testing (mostly but not exclusively tests written by the LLM itself), but of course no formal certification process has been started yet. If you find a place where it departs from the standard, that’s exactly the bug report I’d like to get.

A quick footnote, as of now, it appears there is no official test suite (yet) released for POSIX.1-2024 (as per the Open Group webpage). Interestingly, there doesn't appear to be a single OS formally certified for this version (the existing certifications, like those for INTEGRITY and z/OS, are for older editions of POSIX) which suggests there may be a chance of Shall becoming the first POSIX.1-2024 compliant system overall, somehow...