The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
From: Paul Ruizendaal <pnr@planet.nl>
To: The Eunuchs Hysterical Society <tuhs@tuhs.org>
Subject: [TUHS] Porting the SysIII kernel: first steps & memory management
Date: Fri, 30 Dec 2022 19:25:18 +0100	[thread overview]
Message-ID: <4A7EBAFB-CF48-45CF-9609-A9DF924AF299@planet.nl> (raw)


Porting the SysIII kernel to a D1 board (https://www.aliexpress.us/item/3256803408560538.html) began with a port of XV6, in order to test the tool chain and to get comfortable with this target. Michael Engel had already ported XV6 to the D1 chip a few months before (https://www.uni-bamberg.de/fileadmin/sysnap/slides/xv6-riscv.pdf), giving a ready base to work with.

The main new effort was to add code to initialise the DRAM controller and the SD Card interface, and to have a simple boot loader. Such code is available from the manufacturer board support package (BSP), although in this case the DRAM controller code was only available as assembler compiler output and had to be reverse engineered back into C. In general I was surprised to see how big and unwieldy the BSP code is; maybe the code just looks sloppy because it has to deal with all kinds of edge cases - but I can also imagine that it accumulates cruft as it is ported from SoC to SoC by the manufacturer.

The resulting XV6 source tree is here: https://gitlab.com/pnru/xv6-d1
This version automatically boots from the SD Card on the board.

With that out of the way, the ancient Unix port was relatively easy. It would seem to me that the SysIII code base has a lot of clean-up work in it that still pays off today. The code compiles to a 64-bit target with minimal updates, which I think is a compliment to the engineers that worked on it. Probably using a LLP64 compiler also helped. In order to bring something up quickly, I modified the kernel to load ELF binaries, so that I could use proven material from the XV6 port (such as a minimalistic init and shell).

Initially, I just replaced VAX memory management with page table code taken from XV6 (i.e. no VM or swapping). Working with Risc-V page tables gives much simpler code, but I have a deeper appreciation of the VAX paging design now: for the type of code that was run in 1980, the VAX design enables very small page tables with just a few dozen entries. In contrast, for the 3-level page tables of 64-bit Risc-V I end up with 7 pages of page table of 4KB each, or 28KB -- that is larger than the memory image of many SysIII programs. If I move the ‘trampoline' to just above the stack in virtual memory it could be 5 pages instead of 7, but the overall picture remains the same. The 68020 or ‘030 MMU could be configured to have various page sizes -- this looked byzantine to me when I first saw it, but it makes more sense now.

Next I replaced the VAX scatter paging / partial swapping code, keeping the same methodology. I noticed that there is still confusion over memory management in 32V and SysIII (and implicitly SVR1,R2). The original 32V as described in the London/Reiser paper used V7 style swapping. This code can be found as ‘slowsys’ in the surviving source (https://www.tuhs.org/cgi-bin/utree.pl?file=32V/usr/src/slowsys). It was quickly (Mar vs. Jan 1979) replaced by the scatter loading / partial swapping design already hinted at in the paper (source is in 32V/usr/src/sys). Unfortunately, the “32V uses V7 swapping” meme lives on.

In scatter paging, the pages are no longer allocated continuous in physical memory but new pages are taken from a free list and expansion swaps are not usually needed. Also, when a process is swapped out, it is not fully swapped out, but just enough pages to make room for the new process. When it is readied to run again, only the partial set needs to be reloaded. In the VAX context, scatter paging and partial swapping are quite effective and I think competitive with demand paging for the 25-100KB processes that were in use at the time. As I mentioned in the post on the toolchain, the Plan 9 C compiler can easily use 1MB of memory and in a 4MB of core context, this trashes the algorithm; it starts to behave much like traditional swapping. The reason for this is that the entire process must be in memory in order to be able to run and the algorithm cannot recognise that a much smaller working set is needed. The implicit assumption of small processes can also be seen in the choice to limit partial swaps to 4KB per iteration (8 VAX pages).

For handling processes with a large memory footprint but a small working set a true demand paged VM approach is needed. The simplest such approach appears to be Richard Miller’s work for SVR1 (see June 1984 Usenix conference proceedings, "A Demand Paging Virtual Memory Manager for System V"). This is a very light touch implementation of demand paging and it seems that enough bits and pieces survive to recreate it.

The journey through the memory code made it clear again that in SysIII and before, the memory code is scattered over several locations and not so easy to fathom at first glance. It would seem that in SysV/68 an attempt was made to organise the code into separate files and with a more defined API. It does not seem to have carried through. Maybe this was because the MMU’s of the 1980-1985 era were all too different to be efficiently abstracted into a single framework.

Beyond SysV/68, were there any other attempts in the early 80’s to organise and abstract the kernel memory management code (outside BSD)?




                 reply	other threads:[~2022-12-30 18:26 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=4A7EBAFB-CF48-45CF-9609-A9DF924AF299@planet.nl \
    --to=pnr@planet.nl \
    --cc=tuhs@tuhs.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).