Memory and the heap

The last time I posted, I had written a basic memory allocator. Since then, I've debugged it and integrated it more into the rest of the system. For example, I converted the proc[] array from an array of struct proc to an array of pointers to struct proc, which means 1) process structures are allocated when they are needed, 2) it takes a lot less static memory.

Each proc structure took up 902 bytes—though I'm trying to trim that down—and NPROC was set to 150 (this is the number of proc structures in the system), so the whole proc[] array took up 135,300 bytes of memory. This doesn't seem like a whole lot, but out of only 262,144 bytes of RAM that the TI-92+ has, it's over half of the total system memory! With all the other global variables, there were only about 74 kilobytes of available RAM. By changing it to an array of dynamically-allocated structures, and with NPROC set to 64 (a more realistic value than 150 on this size of machine), the array now takes up a measly 256 bytes.

There are other static arrays that are good candidates for also becoming dynamically-allocated like the proc[] array, but they are all less than 10K each, so I'll hold off on changing those for now.

In addition to the memory allocator and the immense space savings, I added some simple diagnostic tests in the heap init routine that sorted and listed the global variables and their relative sizes (as percentages of the total size of all global variables):



As you can see, the inode[], buffers[], file[] arrays are the biggest, and I'll probably change those to dynamically-allocated arrays next. The heaplist[] is used for managing the heap itself, so it cannot be dynamically-allocated like the other arrays (though its size can be reduced as it currently contains 1024 heap entries, which is probably excessive).

Last, you may have noticed in that screenshot that I changed the font yet again, at least temporarily. :) I'm still playing with various glyph sets, and I'm kind of leaning toward one that has smaller lowercase letters. If you have any opinions on this (I need feedback!), please share them in the comments.

More demos of the virtual terminal

Here are a few more animated screenshots demonstrating the virtual terminal in Punix.

This one demonstrates some escape codes for clearing parts of the current line or screen:


This demonstrates scrolling the screen up and down:


This demonstrates the use of the graphics character set, invoked with the Shift In (SI) character, or Ctrl-N:


This last screenshot demonstrates the compose key feature, which is similar to Multi_key in X:

Currently the driver uses the MODE key as the compose key, as that was one of the few obvious choices for this function. The digraphs I used in the demo are as follows:

Digraph	Resulting character
U'	Ü
^0	°
12	½
ss	ß
L-	£
xo	¤
so	§

Update 2008-11-18: I added a tag named "vtdemo" in the Subversion repository for this revision, so you can check it out and play with it using the command svn co https://punix.svn.sourceforge.net/svnroot/punix/tags/vtdemo

Virtual Terminal demo!

Today I got the terminal emulator in a usable state. On the input side of it, the modifier keys—shift, diamond, and 2nd—work, and most of the keys translate correctly with these modifiers (the mechanisms are in place, but the translation table needs to be tweaked). On the output side, the terminal correctly parses nearly all of the common escape codes of the VT-100 (upon which I based my terminal emulator).

Here is an animated screenshot of the terminal in action as I typed the text at the bottom of the screen:



Note that the keyboard input is not actually going anywhere yet. All of it is only sent to the output. I still need to debug the tty code to make the input go into a raw queue and a canonicalized queue after the appropriate character conversions.

The changing pixels in the bottom row is a binary counter of interrupt 1 (running at 256 Hz). I discovered a possible bug in TiEmu in that it doesn't trigger interrupt 1 while a single-instruction loop (such as bra .) is running. I'd like to investigate this bug in TiEmu further, but for now I just added a workaround to my code: no loops of this kind!

Status update 2008-10-12

Recently I've phased out the old text rendering code in favor of the newer "vt" virtual terminal emulator. This character device driver supports almost every VT-100 escape code. I tested the snot out of it, even running things like "links" (a text-only web browser) on it, to make sure it handles the codes correctly. The following screenshot shows the new terminal emulator in action. It doesn't look a lot different from the previous screenshot, but the font is a little bit different (better, I think):



I'm also making a lot of behind-the-scenes changes (the terminal emulator is one of the smaller changes, in fact):

• For one, the flash device driver is nearly complete. I haven't tested it yet, but it should be able to read blocks from and write blocks to FlashROM, buffering the block data as needed and caching block numbers for faster lookup. This leads me to another point: I redesigned the filesystem and flash device layout...again. I decided to keep the separation of the FlashROM and the filesystem, if only for simplifying the filesystem code. The flash device driver is responsible for translating logical block numbers—which the filesystem sees—to the actual locations in FlashROM. It will store the 32-bit block number immediately preceding the 128-byte block data itself, but I reserve the right to change this so that the block number table is separate from the block data.
  
  The block number will have one of the following values:

  Value	Meaning
  0xFFFFFFFF	Block is free, and all blocks following in this sector are also free
  0x00000000	Block is dirty
  n	Block is used, and the block number is n

  
  The filesystem, as in previous designs, will use the upper 16 bits of the block number as the inode number and the lower 16 bits as the block number within the file. This gives the filesystem up to 65,534 inode numbers and 65,536 file block numbers (the filesystem uses file block number 0 as the inode header). Given that the FlashROM is only 2MB, each block is 128 bytes, and each inode header is 32 bytes, there can be at most 13,107 non-empty files in this filesystem. I still need to work on the filesystem at the moment.


• I've updated the process scheduler to better allocate processor time depending on recent CPU usage of each process. Hopefully this will result in a responsive system when multiple processes are running simultaneously.


• I've implemented signal handling a little more thoroughly. It's not complete, but it's enough to get the rest of the system working first.


• I've removed a lot of "dead" code, such as code that's from PedroM but commented out. For example, I reimplemented the KeyScan() and AddKey() routines in C and made some Punix-specific changes to them (which were easier to make in C than in 68k assembly), and then I removed the large commented-out version from entry.s. I also reimplemented the BattCheck() routine from PedroM in C and removed it from entry.s. Now Punix can monitor the battery level (this is kind of important on a real calculator!).


• I fixed the link character device driver so it will restart transmitting and receiving when the write queue has data and when the read queue has room for more data, respectively. I had overlooked this detail when I first wrote it. D:


• I added load average calculations. These are made once every 5 seconds to measure how many processes are in the "run" state. The load averages can't be queried yet, so I'll need to add a way for a user process to get that information.


• I wrote a basic memory allocator, finally! This allocator can allocate blocks of memory in multiples of 128 bytes. I chose 128 bytes because it is the block size in Punix, so most memory allocations (e.g., buffers) in the kernel will be 128 bytes. Since this allocator will also be available to userland processes, the plan is for applications to allocate a large block or blocks of memory and then use a finer-grained malloc() routine to allocate memory from this pool of memory. This is the way uCLinux works (generally).

As you can see, I've been busy trying to make Punix work! There are also many other little changes than are listed here. Look at the Subversion repository if you're curious to see what else hass changed in the last several months!

At this time, there are about 12 kilobytes left in the first sector of FlashROM for more code in Punix. This is a good thing because I still need to implement the inode allocator and other little bits of the middle-level filesystem code, as well as the execv*() system calls. These should all take less than 12 kilobytes when they're done.

Code Layout Change

I've been meaning to change the layout of the kernel source for a long time now, but I was reluctant to change it for fear of breaking the build process (and also because CVS isn't very good when it comes to renaming or moving files and directories). However, today I finally changed the names of the kernel source directories:

sys is now known as h
kern is now known as sys

This naming convention is more in line with the older Unix V7 through 2.11BSD. Apparently I got the kern and sys names from FreeBSD (NetBSD and OpenBSD also use these names), but I just prefer the convention of V7 and 2.11BSD over FreeBSD for some reason. I suppose the names don't really matter, though; it's not as if anyone else is working on Punix now anyway. :)

The Punix File System (with some background history)

It's been a while since I first designed a version of the file system for Punix. It first started out with the block translation occurring in the flash device driver; the file system driver would not know where in Flash ROM the blocks would be stored. Recently I considered moving this process into the file system driver and keeping the flash device driver simple; this would mean that the flash driver would address blocks directly. The interface to the flash driver would also have to include a (non-standard) method to erase pages.

Even more recently, I decided to remove the separation of the file system driver and device driver. After all, this operating system's only block device is the Flash ROM device, and the only file system it will support (in the near future) is the Punix File System (PFS). Also, since the Flash ROM is directly readable, I think this removal is reasonable.

It took me a while to settle on this design, and I reasoned that if I or someone else wishes to add support for additional file systems (e.g., FAT32 on external storage via USB), only the higher-level file system layer needs to change (I or someone else would have to add a true virtual file system layer for this to work). The PFS layer would remain largely the same, still accessing the Flash ROM directly.

Now without further ado, here is the layout of the file system. (Note: this design is not yet implemented in code as of this entry's date, so it would be futile to look for it.)

Flash ROM on the TI-92+ is composed of 32 64KB pages. The Punix File System uses 128-byte blocks. Each page can contain up to 512 of these blocks. I-node numbers are 16 bits wide and block numbers to address blocks within a file are 14 bits wide. Every file block can be directly addressed using its block number, which is simply the file offset divided by the block size (128 bytes). This is in contrast to typical *nix file systems which contain indexed tables (direct and single, double, and triple indirect) of block numbers. These tables are overhead in the i-node in those file systems which will not be in the PFS.

Each flash page will contain a signature or "magic" number (2 bytes), block number table (1984 bytes), pad (or allocation bitmap if it's useful) (62 bytes), and the blocks themselves (63488 bytes). This is only about 3% overhead for the block number table. The magic number is a value that is used to indicate that the page was successfully erased (it is written after the page is completely erased) to protect against attempts to write to partially-erased pages in case of system crashes. The block number table contains a list of block numbers (composed of the 16-bit i-node and 14-bit data block number) and 2 bits for flags. One of these flags is the "deleted" flag to indicate that the file is deleted from the file system but is still open in the operating system. If any "deleted" files are found during mounting of the file system (at boot-up time), they can safely be deleted permanently (that is, the "obsoleted" flag is set).

In the block number table, all numbers are initially all set bits (Flash ROM starts with all bits set). When a block is allocated, its block number is written over its index in the table. When the block is "obsoleted", its number in the table is cleared to zero to indicate that it is dirty. Only when all blocks in a page are dirty, the page can be erased, making all blocks in that page free.

An i-node will be, at most, 32 bytes in size (as it doesn't have to contain a table of file blocks), so four i-nodes will be stored inside one block. The bottom 2 bits of the i-node number and the file block number are cleared to give the number of the block that contains the four i-nodes. The bottom 2 bits of the i-node number indicate where in that block the i-node is stored.

While in operation, the file system will use one page at a time to store new or revised blocks. When a page gets full, it will move to the next page that has free blocks. If, while allocating a block using this method, the file system would "paint itself into a corner" by not leaving enough "slack space" or free blocks to move around, it will have to perform garbage collection. This involves moving all used blocks from one page to other pages and then erasing the old page. This then results in a whole page of free blocks, likely allowing the block allocation to succeed. (To be precise, "slack space" is the total number of free blocks in all pages ("num_free_blks"). As long as this value is greater than the number of used blocks in the page with the fewest number of used blocks ("min_used_page"), the file system need not do garbage collection.)

To avoid garbage collection (which can take a noticeable amount of time), the file system will occasionally preemptively move used blocks to a "fresher" page so that the old page will become mostly empty (but dirty). (This is essentially "progressive garbage collection".) The same will be done to pages that contain blocks of "static" files, or files which change infrequently (such as system binaries), in order to avoid wearing "active" pages sooner than "static" pages.

That's all I have for now, and I will update this post as I revise the file system layout.

Subversion and scheduler

A couple days ago I finally put the Punix source code into the Subversion repository on SourceForge. I figured it was about time that I used Subversion instead of the older CVS. This also means that the CVS repository is deprecated and will not be maintained. It will exist only for looking at code history.

Also, during the past couple of days I have been working on fixing the scheduler. To do this I wrote a simple program that simulates the scheduler that I can run on my computer and that shows everything that happens in the scheduler (such as clock ticks and the results of priority calculations). As a result of this, I found one small but serious bug in nextready() which would cause a crash in the real system. Besides that, I tuned the algorithm so it would take the process's nice value into account with a reasonable weight relative to the cpu time of the process (higher nice and/or higher cpu time means lower priority). I implemented the computation of load averages in the simulation, so I still need to copy that over to the real version.

execve() starts to take shape

Despite the lack of a memory allocator and a working file system, I decided to start working on the execve() system call. In its current state, it doesn't load the text and data sections from a file; instead, it uses a hard-coded location for the program code, and it doesn't have a data section. Also, the stack pointer points to a global array variable with a fixed size. However, execve() has rudimentary code to pass arguments and environment variables to the new process image through its stack.

As a result, instead of executing /etc/init as it expects, the kernel's icode() actually executes something entirely different. I took the opportunity to test the argument- and environment-passing mechanism of execve() inside the new user program simply by printing the arguments and environment passed to it. That program essentially consists of this code:

#include <stdio.h>
#include <string.h>

static void println(char *s)
{
 write(2, s, strlen(s));
 write(2, "\n", 1);
}

int main(int argc, char *argv[], char *envp[])
{
 println("This is a user program.");
 
 println("\narguments:");
 for (; *argv; ++argv)
  println(*argv);
 
 println("\nenvironment:");
 for (; *envp; ++envp)
  println(*envp);
 
 return 0;
}

which is a fully-working standalone C program. You can run the above program and see all of the arguments and environment passed to it. Here is the result of running this program in Punix (the text after the copyright and warranty information but before the kernel panic message):



The arguments and environment are those passed to it by icode(). The first argument to the program, "-00000", comes from 2.11BSD (one of many sources I'm using to write Punix). I kept it in there when I transliterated my icode() routine from PDP to 68k assembly language code. When I get a real "init" program I'll change the argument to whatever it expects and accepts as arguments (such as to specify the run level to enter after booting). It will also depend on the (possible) presence of a boot loader that can pass arguments to the kernel and to init. That will be some time in the future, so I won't worry about it for now.

Status 2008-01-19

The development of Punix is still hobbling along. It still needs a few things implemented before it can boot up completely; the three major components it needs are a memory allocator, a file system, and a Flash ROM block device driver. It already has most of the upper and middle layers of the file system written, but it lacks the low-level code to read and write an actual file system on a block device.

In the last month I've been adding a lot of support code for the file system, mostly taking code from UNIX V6 and V7 and re-writing it for Punix. I've been adding this and other low-level driver code (including a new and improved virtual terminal driver!) without testing each time. In fact, until last night it wouldn't completely link because it had some unresolved symbols.

A few nights ago I resolved the symbols (either by implementing the missing functions or by commenting out each reference to them) and linked it all together. Then I ran it in TiEmu to test it. I could step through it instruction-by-instruction, but at one point it tries to write to an illegal address and goes to the "address error" exception. At this point I discovered that the vector table containing the "address error" and other vectors is partially corrupted! See http://p094.ezboard.com/ftichessteamhqfrm5.showMessage?topicID=3486.topic, starting at the third post. I tried moving symbols around, even inserting literal values in the vector table, but those incorrect values (which Lionel Debroux suggests may be a certificate field) still appear there in the TIB file, even before it's loaded onto the calculator.

Today I reduced the test program to one file. I found that if the vectors table contains a symbol reference (even to a symbol in the same file), the certificate field appears. However, if the values are all hard-coded, the certificate field does not appear. This probably means it's a bug, or at least an undocumented feature, in the TIGCC linker.

Last, I'd like to mention that someone has volunteered to help work on some of the missing components, so hopefully this means development will pick up pace.