Ian Jack’s Blog

I’ve now updated the documentation and uploaded the latest version which includes all the changes mentioned here to date. Let me know if you spot any problems or bad links.

I’ve now implemented the first useful program – a very simple version of “ls”. It’s not much, but it’s a start!

Interesting how many bugs come to light when doing something like this. A particularly nasty one was the situation when a memory allocation was called for with a requested size of zero (of course this should never happen, so a few more checks are needed). The result was that the first memory entry in the list was used (even though it was already allocated elsewhere) and susequently deallocated, with unpredictable results. That was quite a tough one to track down as it didn’t show up immediately. As always, without SimNow I don’t know how I’d ever have found it.

When I have the energy I’ll try to document this latest version and upload it to the web site as I think it represents a significant step.

Whilst modifying the memory allocation routines to include the Pid of the task that owns the memory it occurred to me that I had made the most elementary oversight by not accounting for the possibility of multiple tasks trying to allocate memory at the same time. In the wrong circumstances this could cause havoc by completely wrecking the linked lists of memory allocation. The answer is trivial – I have now implemented a system of semaphors so that only one task can access the memory allocation/deallocation routines at a time.

This is almost trivial on the x86_64 processors by using the CMPXCHG instruction. This tests and, if required, sets a memory location as an atomic instruction; in other words, it is guaranteed that the instruction will complete without being interrupted. If the semaphore can’t be set (i.e. if another task has already set it) a task switch is done and the operation will be retried next time the task runs.

At the start of the memory allocation/deallocation routines a semaphore is now set, and it is cleared at the end of these routines. This should guard against the possibility of some particulary obscure bugs at a future time.

The more I work on the system the more obvious it is that I’m going to have to be a little more clever when allocating and, particularly, deallocating memory. I’m most concerned with deallocating memory when a task ends. User heap memory is no problem, as it is part of a memory map that gets discarded and (I think) kernel heap allocation doesn’t occur in user tasks. However there is still shared memory to worry about. Currently it’s up to the task to make sure that it deallocates everything – but that’s really not good enough; it should happen automatically.

I’m thinking at the moment of adding an additional field to each allocated block of memory to record the task of the PID that it belongs to. A separate task could then clean up resources once a task ends (and perhaps periodically sweep the system looking for zombie resources). It doesn’t sound too difficut to implement.

Actually, I’m not totally convinced that the use of shared memory is a good thing (except where absolutely necessary) - there are obvious security implications. It’s needed to pass information between tasks (other than the limited amount of data that can be passed directly in a message), but there must be an alternative way of doing this. I must look carefully at where shared memory is used and whether it is necessary.

There’s also the separate problem of keeping track of which task an FCB belongs to so that the filesystem can deallocate it when it is no longer needed.

Work on this is now pretty much complete for the time being. It turned out to be much easier than I anticipated. Write access now works; directory structure and time stamps don’t. I’m not too bothered about a directory structure right now, as the root directory can hold 512 entries – in any case I don’t intend FAT to be the long-term file system, so I don’t want to do more than the necessary minimum of work on it. Time stamping would be of little use until some form of time-of-day clock is implemented (shouldn’t be too difficult). I’ll now work on documenting and publishing this latest version.

What next? Current work has shown up a problem when running under QEMU; sometimes it needs two or three attempts before the system runs. These problems don’t occur under SimNow, so I’m guessing it’s a question of uninitialized variables. Other than that, I think that I’ll look at implementing a few simple commands – cat, ls, cp, that sort of thing. Another thing that I think I may look at is changing the memory map to give more available memory to the various parts of the system.

Whilst working on the filesystem code I realized that the timer code definitely need improving. As presented the system only has a single timer; this obviously causes problems if more than one task calls sys_Sleep(). I hadn’t really thought about how to implement multiple timers, but it suddenly occurred to me (whilst I was out walking the dog on the South Downs) that it was really simple. By adding another field to the task structure to hold a timer count, the job is practically done! During the timer interrupt it’s just a question of checking which tasks are waiting on a timer, decrementing the timer field in the task structure and, if it’s reached zero, unblocking the task. Really simple! Things sometimes work that way.

Now, back to the filesystem.

Time to enhance the file system, I think. Currently it can only read from the disk, and doesn’t know about subdirectories. First step will be to add write access. The IDE part of this should be fairly straightforward, but the FAT part is possibly a little more complicated. We need to be able to create directory entries and manage the FAT itself.

This is going to mean accessing the FAT itself quite a bit, so it’s going to be necessary to buffer it; memory accesses are obviously preferable to a lot of disk accesses. One possibility is just to keep the whole FAT in memory as an array; this does seem a little wasteful on memory, and makes it more difficult to ascertain which sectors of the FAT need to be rewritten to disk when changes are made (easy if the FAT is rewritten for each change, but more difficult is we want to do these updates in batches). Another possibility is to have an array of pointers to structures containing each sector of the FAT and information about whether the sector has changed since it was read from disk. This would be much more efficient memory-wise, as it would only be necessary to create structures for FAT sectors that have been read, but complicates access to the FAT slightly. I’m not quite sure which is more important – memory space or efficient access. But I do prefer the ellegance of the sparse-memory approach (the second possibility). Also, it’s a little more complicated to program – but as the whole point of this exercise is to have fun, that’s an advantage not a disadvantage!

I’ve now uploaded, and documented, the current version. Let me know if there are any problems with the code or the site.

I made another fairly minor change today. Previously the kernel and user stacks (I’m not quite clear in my mind why we have two stacks, or if the kernel one is ever used – must read the AMD documentation to find out more about this) were being allocated by the tasks themselves. It was just easier, initially, to do things that way. Now I’ve moved the code for this to the task-creation routines. This makes the code cleaner, prevents possible multiple use of the same stack, and makes the tasks themselves easier to write.

The code now is quite a lot cleaner and more logical than that documented on the main site, so I shall make an effort to document it and update things.

I’ve now implemented two tasking queues (actually three). There is a queue of runnable tasks, one of blocked tasks, and a low-priority queue. Actually, the last is not a real queue but just a pointer to a single task, which is guaranteed always to be runnable. The task-switch code will only pick this low-priority task if no other task is ready to run. The separation into queues of runnable and non-runnable tasks makes it slightly easier, and more efficient, to find the next runnable task.

The work involved in doing this took longer than I expected; it’s amazing how many unforeseen bugs turn up when making such a change. The main things that I now realize I have to be a bit more careful about are checking that any registers that may be altered by a routine are preserved, and making sure that any variables are initialized before they are used. Both these may seem obvious, but it is very easy to overlook things when calling a C routine from assembler code.

What becomes more and more obvious when trying to find these sort of bugs is just how useful it is being able to run the Operating System within a debugger (SimNow). I can’t imagine how people found these sort of errors without debuggers. I think the next move is to carefully review the current code with these points in view before looking to implement more features. Once I’ve done that I’ll post the new version and document it on the main site.