Saturday, 22 April 2017

Code reorganisation, debug monitor, IDE, MinixFS

I have restructured the source code tree for MAXI09OS. Source files are now grouped in directories, with a directory for drivers, another one for the core of the OS, etc. The assembly source files are no longer stuck in a single directory. The makefiles are, by necessity, a little more complex as a result. After toying with using make in a recursive (PDF) fashion, I've instead settled on using include files which enumerate the build files.

One other improvement is that the source for the 256 byte boot loader, described previously, has been folded into the main MAXI09OS repo, along with the flasher tool for transferring new ROM images to the MAXI09 board.

All in all, it's a neater setup even if it is a little over engineered. I learned a bit more about make writing it as well. There's a few further improvements I could make if I wanted to, like a better header dependancy system then simply having a full rebuild whenever one of the headers is changed, but since a full rebuild takes only seconds it's probably pointless.

Back in the OS code itself, I have been improving my monitor by folding it into the OS as a kind of debug task. Commands are now words instead of a single letter. So "dump" instead of "d". Much nicer. The "command table" is handled through a generic subroutine, so other environments, like the Shell, can use the same mechanism.

While in use, the monitor task is the only one which will be scheduled. It is entered by hitting return on whatever IO device it is running on, which is usually a UART port. Interrupts are still enabled, but a flag variable is incremented that causes the scheduler, when it runs under the main ticker interrupt, to always return causing the same task to run each time. In this state the monitor will see a mostly static system. This is the same mechanism (forbid()/permit()) used when a task needs to be the only task running in the system.

I've added a command that shows memory stats, and the tasks in the system, or just the information about a specific task as this screenshot shows:
The "Largest" value from the memory command warrants some elaboration. This is the size of the largest free memory block. Since the simple linked list approach to the memory management lacks a mechanism to coalesce free blocks, it is very prone to memory fragmentation. The Largest value is the size of the biggest free memory block, which might well be considerably less then the total free memory. Actually after coalescing adjacent free blocks, free memory could still be fragmented.

I've also been working on making the monitor useful for exercising device drivers directly, without the need to write a specific test program.

With the sysopen command, it is possible to set the A register (which is usually the unit number) as well as the B register, which is used to set the baud rate in the UART driver but is otherwise not specifically assigned to a particular purpose.

The main motivation for doing this was to make it easier to write a driver for the IDE interface.

The IDE driver is for sector level access to the attached disk; the filesystem layer, described later, sits on top of it.

The same driver mechanism, and subroutines (sysopen, sysread, etc) are used for the IDE driver, except that in the case of sysread additional registers are used since the read is a sector read and not a byte read.

The following registers are used, in both sysread and syswrite:
  • X: the device handle, as usual
  • Y: the memory address to write to (sysread) or read from (syswrite)
  • U: the sector number (LBA) to start from
  • A: the count of sectors to read or write
Currently no interrupts are used so the IO operations busy-wait until the device is ready to send (or receive) the data. There are obstacles in MAXI09OS to doing this which I'll write about later. In reality this would only really matter if MAXI09 was ever attached to a very slow, old, hard disk. Whilst a CompactFlash is used the interrupt would fire, most likely, only a few iterations into the polling loop. Such is the speed of the MPU in MAXI09 retaliative to what a CF would more usually be attached too. All that said, getting interrupts working with the IDE interface would be nice.

I'm also using syscontrol for a few things (more will come later):
  • IDECTRL_IDENTIFY - 0: perform an identify command on the drive and fill out the 512 byte sector of information referenced by the Y register
  • IDECTRL_READ_MBR - 1: read sector 0 into device handle memory and copy partition information into a system table
The partition table, which is a section of 4 lots of 16 bytes within the MBR sector, contains start and length sector information about each partition, as well as other non pertinent data. The syscontrol action reads this in and uses it as sector offsets when doing IO on a partition. Currently no info about the partition table is returned with the syscontrol call. I will probably change this at some point so the user could view the table etc.

Inside the sysopen call partitions map nicely to units, with unit 0 being used to access the entire disk. The partition table information is used to calculate an offset for each partition / unit. At present, the lengths of each partition is not enforced and accesses for the first partition could overlap into the second, etc. This would be trivial to honour I'd I wanted to write some extra code.

This screenshot shows the monitor being used to open the IDE device and issue the IDENTITY command. The first 128 bytes of the resultant sector are dumped out, showing the vendor and model:
Here's a look at the monitor being used to:
  1. Open the entire disk
  2. Read the MBR
  3. Close the entire disk
  4. Open partition 1
  5. Read in the Minix superblock (2 sectors) into memory location 0x4000
  6. Dump out the first 128 bytes of the superblock
(The way I worked out that this was a MinixFS superblock was to spot the 0x8f13 sequence at offset 0x10. This is the magic number sequence for a Minix filesystem with 30 character file names, byte swapped since the format on disk is little-endian.)

After implementing the low level IDE layer (and MBR reading) the next task was to write routines for dealing with the filesystem layer.

For anyone interested in the guts of this ancient filesystem I suggest you read this overview, as well as this look at some of the data structures. Needless to say, MinixFS version 1 and 2 are about the simplest form of UNIX filesystem, all the more interesting (for me and this project) because the important structure fields are 16 bits wide.

The functionality nicely splits in two modules:


This wraps a mounted Minix filesystem handle.

It contains code to parse the superblock structure (including lots of little to big endian swaps), and a routine to read a arbitrary 1KB FS block which calls to the underlying device ie. the IDE layer to do the reading at the calculated physical offset. This routine uses a block offset calculated when the filesystem is mounted (of course, the underlying IDE layer will apply its own partition-based offset) The filesystem-layer offset calculation uses fields from the superblock, which includes fields which indicate the number of blocks used for the inode and data zone bitmaps.

There's also a routine to read in an arbitrary inode. This uses a simple cache; the last disk block of inodes read in. If the requested inode has already been read in then there won't be any disk access. 

An interesting aspect of this module is that it is possible to have multiple mounted file systems in the system at the same time. However to keep things simple the init task is responsible for mounting a system-wide root filesystem.

Also since an open "low level" device handle is the thing which is mounted, in theory the code written supports the adding of other block devices sitting under the filesystem code, say a SCSI disk attached to a controller.

Those good things said, I have not attempted to implement a VFS-type layer in MAXI09OS. Only Minix FS volumes can be mounted and the subroutine is called "mountminix". I did toy with writing more abstractions that would allow, hypothetically, the writing of a FAT16 layer without changing any user level code but in the end I concluded it would add yet more complexity and time and not really teach me anything useful.


This wraps an open "file", and presents the same entry points for an open file as the other drivers in the system, with the addition of a new sysseek call to move the file pointer around the file. It also contains other routines, for things like stat-ing a file by its filename.

The basic "thing which is opened" is a file referenced by its inode number. sysopen is called with X pointing to "minix", Y pointed at a mounted filesystem superblock handle obtained with mountminix, and U with the inode number. As usual the device/file handle is returned in X.

These handles are used for all types of "files". Opening one principally consists of locating and reading in its inode. This inode includes the "data zones" (block numbers) for the entry's data. For directories this data consists of an array of 32 byte directory entries AKA dirents. The structure of a dirent is trivial:
  1. 2 byte inode number
  2. 30 byte (max) null-padded filename
Thus to open a file by it's filename the first thing to do is to open the directory the file is in. We have to start somewhere, and what we start with is the root directory inode, which in Minix is always inode 1. (Inode 0 is reserved.)

The dirent array is iterated through, possibly by reading in additional data zone (filesystem blocks) if the directory contains more entries then would fit in a single filesystem block.

If a match of filename is found, the inode number for the file becomes known and its inode structure can be read from disk. The content - data zones - of the file can then be read in using the data zone pointers.

The following screenshot shows the monitor to be used to:
  1. Open the IDE disk.
  2. Read the partition table.
  3. Close the IDE disk.
  4. Open partition 1.
  5. Mount the MinixFS.
  6. Open inode 1, the root directory.
  7. Read in the first few dirents and dump them out.
As well as simple linear reading through a file it is also possible to seek to an arbitrary byte position, and continue reading from there.

One of the massive tasks I've not yet even started is writing to the filesystem. This is a pretty big job and opens up all sorts of interesting scenarios that need dealing with. For instance, how to deal with two tasks, one which is writing to a file, whilst another has it open for reading? Things get very challenging, very fast.

The last thing I have been working on is the command-line Shell. Currently it is very, very basic. You can perform the following operations:
  1. Change directory to a named directory (cd)
  2. List the current directory (list)
  3. List in long form the current directory (list -l)
  4. Output files by name (type)
These are internal commands, effectively subroutines in the ROM. But external commands should be perfectly possible too. Since I can now read from a filesystem, if the user enters the filename for a command that filename will be opened, read into RAM, and jumped too as a subroutine of the Shell process.

The list functionality warrants a little discussion. In a simple listing, it is only necessary to iterate the dirents in a directory. The user cannot tell even wether the entries being listed are files or directories, since those attributes (the file "mode") are stored in the inode and not with the filenames. List in long form opens each file's inode and displays the type of the "file" (regular, directory, pipe, device node, etc), along with its files size, user and group etc. Thus list long, on MAXI09 as it is on a real UNIX/Linux, is more expensive then simply listing the names of the files.

I've yet to write a routine to output decimal numbers, so all the values for things like file size are still in hex.

The following screenshot shows the Shell being used to wander around the Minix filesystem, listing directories etc:
The Shell is coming along quite nicely. Of course, what's not shown here is that it is possible to have multiple Shells running at the same time, on the virtual consoles and on the UART ports. There's a few limitations not shown in the screenshot, like the fact that you can only change directory into a directory in the current directory, not to an arbitrary path.

So MAXI09OS is coming along quite nicely, though you still can't really "do" anything useful with it yet.

I think I'll take a break from working on the software side for a while now and switch to working on the hardware:
  • There's the SPI controller VHDL code in DISCo. I can then write a driver for it, and finally some utilities for setting and getting the date and time from the Real Time Clock.
  • The Citizen 120D+ printer I bought about a year ago has yet to even be powered on. I could have a go at writing a driver so I can print to it, much like how they can be outputted to the console. This might also prove that I need to implement command redirection.
  • I could have a go at finishing the building of an analogue joystick I started a year or so ago, and experimenting with that
  • The keyboard controller can generate a reset signal on a particular key combination, but I've not even experimented with getting that working yet
I've had MAXI09 up and running for more then a year now, and it continues to keep on giving with no end in sight...

Thursday, 19 January 2017

More progress.... Lots of different areas

Looking again at the VHDL for my interrupt router, I realised that adding a priority encoder was fairly simple:

Instead of being the masked and active interrupt lines, ROUTED is now the number (bit position plus one) of the active line. 0 is used as a special case: no interrupt lines, which are exposed by the mask, are active. This should never happen inside the ISR because when there are no active interrupts the MPU's interrupt lines should stay high, but it is catered for "just in case". The only downside with this method is that interrupt priorities are set in the VHDL. In other words the fact that a QUART interrupt overrides (and hides) a RTC interrupt can't be changed by MPU code.

This all means my main interrupt service routine is reduced to something approximating:

As each driver is opened, it will set up its interrupt handler routine pointer in the appropriate table, and set DISCo's interrupt mask bit to allow the incoming interrupt through to the MPU. For example, here is the relevant code in the UART driver:

This is much more efficient then before, when the main ISR had to manipulate mask bits, looping over a list of possible interrupt lines. The top level (IC level) interrupt processing is now nice and fast and most of the time spent in handling an interrupt is now used dealing with the actual interrupt-generating peripheral IC's registers and not "housekeeping".

I've also been working on the keyboard microcontroller code and have implemented, at last, key repeat and support for caps lock.

Key repeat was easier then I expected. Key repeat in any keyboard generally consists of two, separately configured delay values:
  • Typematic delay: the pause between a key being pressed and the first repeat press being generated.
  • Typematic rate: the pause between subsequent repeated key press events being generated.

Both values have reasonable default values set in the MCU code. I have also introduced a command code so the 6809 can change these values via the UART channel.

Because of wanting to keep all commands in a single byte, I have had to be a bit frugal. The command byte is arranged as follows:
  • 0b00000000 - red LED off
  • 0b00000001 - red LED on
  • 0b00000010 - green LED off
  • 0b00000011 - green LED on
  • 0b00000100 - blue LED off
  • 0b00000101 - blue LED on
  • 0b00000110 - re-initialize the controller state
  • 0b01xxxxxx - set typematic delay to xxxxxx
  • 0b10xxxxxx - set typematic rate to xxxxxx

The delay values are scaled such that 63 (decimal) is a suitable - slow enough - value. There is currently no acknowledging of the byte sent to the keyboard controller. I will look at doing that when I have figured out transmission interrupts in the main computer.

From the 6809 user-level code point of view, sending a command to the controller is accomplished via a syscontrol call on any open console. However the delay values impacts all consoles.  Eventually I will write a system utility to set these values when the system starts up, as well as interactively.

I had a couple of ideas for how to program in the operation of the caps lock key and its LED. Ideally I wanted the LED to be turned on and off by the 6809 sending a control byte to the MCU when the caps lock key was pressed. This would allow the caps lock LED to be used, in a crude way, to determine if the system was responsive since the LED would only toggle if the 6809 was running and able to pick up the keypresses, generating a command to turn the LED on or off in reply.

This would have required a byte to be sent in response to one received, in the console driver's sysread function. The problem with this is that task switching would have to be disabled while the byte was sent because another task might also be wanting to send a byte to the keyboard MCU, for the same or a different reason. This is a clear millisecond at 9600 baud and whilst I could increase the rate to sidestep this problem, I instead decided on a simpler approach.

The caps lock LED is handled entirely in the keyboard MCU code, which tracks wether caps lock is on or not. Communicating caps lock changes with the main 6809 MPU is done by sending a key down scancode byte (high bit clear) when caps lock turns on, and a key up sequence (high bit set) when caps lock is turned off. Cunningly, this mirrors what an ordinary shift key does. This means that the actual event of the caps lock key being released is not sent, but there seems to be no reason why the 6809 would ever need to know about this occurrence.

If anyone is interested, the code for my keyboard controller is available on github as normal. I'm pleased with how relatively simple the controller code has remained with these two bits of extra functionality.

One small "annoyance" that I noticed, after making the initial changes to scancode translation in the console driver: caps lock does not behave exactly like shift in "real" keyboards. Indeed, some early computer keyboards had two "lock" keys, a shift lock and a caps lock. If caps lock is on, numbers should still be available instead of punctuation. This has complicated the 6809 scancode translation a little. Instead of yet another translation table, a call to a toupper subroutine is made to convert a byte, if it's a lowercase letter, to uppercase. This occurs - only if caps lock is on - after the shift and control key checks have selected an alternative scancode translation table.

I've also been busy improving the core OS itself. Tasks now have a default IO device. IO routines - character based like sysread and the string based wrappers like getstr - have been wrapped *defio variants which pull out the default IO channel from a variable in RAM. For efficiency, this variable is updated from the copy held in the task structure each time a task is scheduled. It is also possible to set this IO device when a task is created.

With this work it is possible to use the same task code in multiple tasks. The "echo test" task, as I now call it, allocates the memory to hold the inputted string and uses the default IO channel to get and put the string. Multiple tasks all use the same code, without making a copy, and operate on two virtual consoles as well as a UART port. In other words this task code is reentrant. This method will eventually be used when the echo test task is replaced with something resembling a Shell and should be a significant memory saver.

One issue to address in most multitasking systems is how a task should exit. This is a surprisingly complex operation for any multitasking OS. I have borrowed some ideas from UNIX (massively simplified) and hold an exit code in the task's structure. The exiting child signals its parent which can, in turn, extract the task structure pointer (now fee memory) and exit code, returned in x and a respectfully.

I am still not sure if I'll use the above described mechanism for the running of all sub-tasks, since it is quite a bit of setup. After assuming for years AmigaDOS used this kind of mechanism in its CLI, I have since learned that instead external commands are simply read off disk and run as subroutines of the CLI task. The reason is obvious: efficiency. However, this simple technique makes pipelining commands more awkward, since the whole output has to be buffered for the next task (this probably explains why AmigaDOS lacked pipes). I will have to experiment when I get closer to having a useable Shell to determine which approach to use.

Finally, I've been working on improving the debug output which is presented, if enabled at assembly time, on UART port 2 - the TTL header. There are code, and text output, improvements.

Each debug message now has a "section type", for example messages related to the memory allocator are marked against DEBUG_MEMORY. At assembly time, it is possible to select t which debug messages should be generated for that particular build. So if I have a problem with the interrupt processing I can choose to only output those messages, etc. Debug messages were previously always included in the generated binary; now they are only included if debug mode is enabled.

The messages also look neater because each one is prefixed by a section label. To print out that task address with the task name, the following code is used:

debugxtaskname ^'Scheduling task: ',DEBUG_TASK

This required some new uses of macros in ASxxxx. The macro has to allocate space for the message to print in the generated code, but it can't go directly into the stream of code since otherwise the MPU would try to run the message as if it as code. Instead a new "area" was created, called DEBUGMSG. This is towards the end of ROM and contains all the debug messages. This particular message only shows if DEBUG_TASK is enabled for the the build.

Typical output from the debug serial line looks like the following:
All told, I'm pretty pleased with how my weird little OS is coming along. There's still lots of interesting things to work on:
  • I'm keen to try organising the code a little better. There are now about 30 files, and it would be nice to have a directory layout with drivers in their own directory etc.
  • More drivers: joystick, printer port - I have yet to try hooking my Citizen 120D+ printer up. The SPI bus needs an interface too.
  • Improvements to the console driver: I could look at some of the VT100 codes, and try to make the serial terminal more useable with them
  • Transmission interrupts on the UART. I still have yet to crack them.
  • Extend my, very preliminary, debug monitor. I have started "porting" my old monitor to the MAXI09OS so I can use it for debugging by dumping out things like task structures, the allocated memory blocks etc.
I  could also have a crack at extending the VHDL in MuDdy and DISCo:
  • The IDE port needs a high byte latch implemented in DISCo
  • DISCo also needs a proper SPI controller, instead of the basic SPI pin interface which is currently written
Or I could have a think about how I will implement a storage interface in the OS. I have a few ideas, but more thinking and planning is needed...