Argh.

I've been umming and aahing about working on a ps3 version of the kernel, because although there is plenty of other stuff to do, i've gotten to the point i'd like to have a framebuffer to work in. And since VGA hardware is such a pita to work with ... maybe the ps3 is the go.

So I did a lot of reading and digging, about powerpc64 hardware (hmm, this is really a mainframe chip, not a game console one!), hypervisor calls (so little documentation), instruction sets, etc etc. Hmm, a lot of work, but it seemed like a good challenge.

But then I thought i'd look at extracting a vga driver from some library - i looked at svgalib only because it had the least dependencies. I thought maybe I could get something going just to get started, or at least evaluate the size of the task. And after wasting a couple of days and very late nights on this ... I finally (re)discovered bochs and qemu had their own framebuffer device which was trivial to setup (I had seen the page a couple of weeks ago and 'noting it for later' promptly forgot it). Ho hum, what a total waste of time that was then. I still need a real driver if i want to get something up on real hardware, but it isn't exactly a priority right now.

So given I now have a framebuffer to work with I might postpone the ps3 stuff. I'm still mulling over an ARM based stuff too, so maybe I will look at that next instead - i imagine it will be somewhat simpler, and I can use qemu for that too.

Now I have a framebuffer ... what to do with it. OpenVG looks interesting, I might start there.

Cells and ratty rodents

Got off me arse and posted a new intro to Cell tutorial. It gets into SIMD coding so it's one of the more interesting ones.

And I managed to get a ps2 mouse driver working, of sorts (well, i'm getting the bytes from the port). And what a pile of shit the PS2 AUX port is. There doesn't seem to be any official documentation, just a few old text files from the days before the internets. Anyway, after a lot of mucking about I got it to work on bochs, qemu and and old PC I have - so that's good enough for me and it didn't take too much code. I'm still not sure if I should combine the keyboard and mouse 'devices' since they share the same io port.

Of course, in the process of testing on real hardware I found everything was broken. Everything. Ho hum. After much frobnication I found the APIC maybe wasn't as easy to use as I thought - or it's just buggy. And my old laptop doesn't even have one (early celeron). So I had to remove all the APIC code so it booted (i'm not doing any run-time stuff yet). And then I moved to using the RTC for timing instead. But that didn't work on real hardware either. Arg. In the end I got it to work but i'm not sure if it was just setting values directly (rather than read-twiddle-write) or clearing the interrupts first.

The apic thing is a bit of a bummer, I guess I'll need to use the pic instead for timing. Which sucks because it can only measure very short periods of time. I suppose if I use the RTC for longer periods - either by just using the 64Hz signal to count down, or the alarm function, and just resort to the pic for the last bit if more accuracy is required, it should be an ok balance between accuracy, overhead, and simplicity.

Hmm, wonder what to do next. A framebuffer would be nice - i'd really rather piss off the text mode entirely. And a disk driver - although then i'd need a filesystem too. Maybe it'd be less effort working out the hypervisor on the ps3 ... Hmm, perhaps a forth based monitor? Something to think about ...

Press Any Key

Well that was a strange weekend. I felt very odd Saturday - very sore throat, dizzy, really nasty headache and a bit of a fever for a while. The fever and dizziness went but I've still got a damn sore throat (a bit less so). I slept a lot.

I managed to get sucked in to poking on code again ... and once I start it's hard to stop.

I wrote up a basic keyboard device - it's a user-mode server which listens to an incoming message port for requests messages and for interrupts. If it gets an interrupt it buffers the keys (and provides decoding/etc), and if it gets a request it returns a key from the buffer (or queues it until one comes along). Very simple code. Then I wanted to have it synthesize key repeats too -- I find the pc keyboard repeats too slowly -- so that meant looking at writing a timing sub system. I tried to think of how these devices should be setup and initialised but for now I've just hardcoded their process creation from the kickstart routine, and use a simple manual process for accessing them via a public port name.

So then I had to work out how to use the APIC for timing - I'll leave the PIC timer for scheduling for now. And with that, I wrote a preliminary 'timer.device', although I haven't tried to see if it works yet. I ummed and ahhed over putting the timing service directly in the kernel, rather than in a user-service. But the kernel can only send signals to processes, and the timer device can send messages, so it seems like it's more useful, even if there is a somewhat more overhead involved. Sigh, I wish there was another APIC timer or two, it would be nice to have a good reliable period counter as well as one to be reprogrammed for varying intervals.

It works

Well, the next thing works.

I finally implemented 'protected non-copying message passing', after a pretty lengthy effort. Phew.

Once I started putting it together I realised I needed a 'virtual address range' allocator, since I want to have a fixed global address range for messages. After a bit of mucking around I settled on an AVL tree based implementation, using first-fit. Although I'd written an AVL tree before (one perfect for the purpose) I'm not sure which version works anymore or where it is, so I just took the parent-based libavl implementation and 'tweaked' it to be more suitable - tree nodes are 'embedded' in objects (no data pointer), and never allocated, and there is no tree object or traversers (comparision functions are passed as arguments if needed). So basically it now has the same api as the one I wrote, but I know it's already debugged and working.

The nodes keep track of the unallocated memory range, and are sorted by address. This makes it easy to coalese blocks if adjacent ones are freed, and so on. Looking up an empty block is O(n) but the empty block list should be pretty short. It shouldn't end up with much fragmentation since it's allocating groups of pages at a time. In the past I did a lot of research on memory algorithms and it ends up that first fit has some desirable characteristics that best fit doesn't - which is nice since it's simpler too.

Anyway, once I had a range of memory, it was simply a matter of mapping that to the callee process when they allocate a message, and re-mapping it to the destination process when it is sent. Well, almost. I was going to have the kernel take ownership of the memory but since it just uses the last-process's page table it can't, at least without globally sharing it and that loses any protection from other processes. So instead a PutMsg maps the memory to the target process's page table immediately, and tracks the object separately (unfortunately requiring dynamic memory allocation). Page tables are only changed when the thread changes - so the page table update shouldn't involve any unexpected overhreads. Once the target process invokes GetMsg, the kernel just returns it's pointer. It's something that needs to run fast (although 'fast' is relative when the cpu is so fast), so it would've been better to avoid the AllocMem/FreeMem overhead required to queue the message, but maybe I can find some other mechanism if it becomes an issue.

I also ran into an optimisation thing that interfered with the nasty hack I'm using to implement 'tag lists' - which basically treat a varargs list as an array of pairs of ints. Anyway, I had a small inline wrapper to call the real function (that takes an array) and all the varag arguments were getting optimised out. __attribute__ ((noinline, unused)) works for now.

Now that stuff is sorted, I guess I can start looking at 'devices' next (funny, I thought I was at that point a couple of weeks ago). Although I think I need to rest this weekend - I've gone and bloody gotten sick again. I usually don't get sick too often, so 3 times in a month is a bit of a shock. Just a sore throat so far this time, but it's enough to get in the way of things.

One door closes ...

... and another opens, in a never-ending corridor of closed doors. Or so it seems.

I managed to get at least some virtual memory stuff working. I can now create processes which have independent address spaces. Yay. After having to fix a lot of lazy coding errors along the way too. Hmm.

And i've got some initial process startup code done. It can initialise the 'exec' library for use by the process before it calls the entry point - from this it will then eventually access all other resources on the system. I'm still working on some of these mechanisms, but it'll do for a start. What makes these things tricky is the virtual memory (and memory protection), for example I can only easily pass a few registers to the initial entry point, unless I add a lot of messy page mapping stuff to pre-load the stack or data space. And I can't call anything inside exec until the structures are setup, so it all has to be done manually (i.e. prone to error). So i'm getting by with 2 arguments; real entry point, and the start of a 16kb block of pre-allocated application memory. Once exec is setup, the startup code can then use various calls to get arguments and whatnot if it needs them - which will be stored in the in-kernel process object.

But, with one hurdle out of the way, another pops up. I have to get message passing working again since all memory is now effectively process-private. I guess I will have to go with some sort of system call to allocate messages in a memory space that can be accessed by all processes (eventually moved amongst them), although I can probably hide that behind the memory allocation interface (MEMF_PUBLIC allocation flag, or so). I'd like any solution to work reasonably efficiently for intra-process message passing too, but I have a feeling that'll probably just about fall out of any solution anyway.

I still need to work out how i'm going to bring up the whole system too - the initial setup of all 'internal' libraries and devices and so on; if there ever is any that is.

One step at a time.

MMUmbling along

Twas a bit of a slow weekend, still feeling a bit funny from the cold last week and started hung over from a few beers in town on Friday night. Saturday we went to McLaren Vale with a friend and I ended up buying way too much wine as usual. It always seems to taste better the further you go ... And I was pretty wasted by the time we got home and cooked up a BBQ.

When I had time to code I was just re-arranging stuff again. I hadn't really 'interface-ised' the code properly so I needed to finish that off. Plus I decided to move all of the supervisor level code to a different directory and make it run off it's own management structure rather than 'execbase', and to settle on a consistent naming convention for structure members. So lots of killing and yanking lines of code and renaming stuff and mucking about with makefiles.

Last night I nutted out some of the main mechanics of process creation, although I still have a little way to go. I've again (about the 3rd time) written a set of utilities for MMU management but I've decided to go with the page tables allocated directly in kernel space, and I keep track of the virtual and real address of these using separate pointers. For memory pages I don't need to know physical address after i've setup the PTE, so I just track those by index in an array.

I was going to map the whole page table to the last 4MB of memory using the self-referential PDE 'hack', but I decided against it. For one, I need to be able to easily manipulate more than 1 page table if I want to re-map messages between processes. And the overhead of keeping track of the page table virtual addresses is small.

For keeping track of physical pages I just have an array of ints, one for each available page of memory (to make it easy, it will be every page from address 0 to the highest physical address present). For available pages I have a linked list stored inside those ints. And once they've been used they're unlinked and the content becomes a reference count. And I have up to 12 bits I can use to indicate other things if required. I'm thinking the reference counting might be handy for keeping track of shared memory - on the other hand, I may just use globally shared sections to load shared library code into, so it might not be necessary at all. For now, it's also the simplest implementation.

I'm still thinking about the process creation primitives too. Maybe a CreateProc that takes either a function address in the current process, or a loaded ELF image. In the former case, i'll just copy the process and call the function, similar to fork() although there may be more specific argument passing system. With the other case it will 'steal' the pages from the calling process and map them to the new process and kick it off. Might need to allocate the memory in a special range so it can be 'stolen' easily , or do some other sort of magic so it works, or even use a process loader server; in either case the loader would manage the details.

The first is required so I can start some initial in-`rom' processes, and also to implement fork() for some possible future posix layer. The second allows a process to load another one relatively efficiently, and do most of the work in user-space on the callee context.

I will have a separate task creation primitive which basically works like pthread_create does.

And I was thinking about alternative platforms again. I'm still dreading the point where I have to deal with even more fucked up components of the PC architecture like video and sound. I should really bite the bullet and get some sort of ARM platform - they're just not that easy to get around here yet. Maybe I should delve into the PS3 as well.

Cold, kernel, KDE

After the cold I had last weekend I haven't been able to do much. I can't seem to get up in the morning and remain light-headed most of the day. So I've been dithering a bit with my coding and getting caught up in too many irrelevant details.

I got stuck contemplating the 'object' system used by libraries, and got side-tracked thinking up different approaches. I think i'll stick to what I have for now (similar to OS4's); as an 'object system' it is limited, and actually 'backwards', but as a collection of 'interfaces' it makes some sense. I still might go with something a lot simpler too (it's not like I'll really have to worry about keeping a stable api 'going forward', if it's never finished and/or never used). I've also been thinking of the user/kernel split some more. I'm liking the idea that each process will be more like a protected virtual os environment, and the 'exec' library will just run the same as any other local library. It will then have a very limited set of system calls only it can make to do things which require supervisor mode, or call a server for things which require global data. The 'supervisor' kernel code will then have its own data structures apart from the rest of the system and be quite limited in functionality.

• Processes and Tasks
• Signals
• Ports and Message Passing
• IO Port Management
• Cache Management (for DMA/etc)
• Virtual Memory Management

I thought i'd setup KDE on my old laptop for my flatmate, until now it has just had blackbox and xdm on it (xdm is rather difficult to get running on fedora too). Wow. KDE is so ... quaint. I can sort of see where they're coming from but they've missed the boat on in so many ways it is difficult to enumerate them all. The launch menu is just odd - let's put a scrolling window inside a menu? The 'shutdown' button is even more confusing than xp. And everything runs like a total pig, why is resizing windows so slow? Just bringing up kdm vs xdm is another 20 seconds on the boot time and logging in another 20 or so. The sound scheme is really annoying. It's probably better than XP. But that isn't saying much.

Share And Enjoy

Well I finished moving the executive library over to use object interfaces, and managed to get enough of the bootstrap process done so that it can now launch a `user process' which may one day complete the job. Still no virtual memory management but it's a start.

Then I started looking at the process of creating and initialising libraries. InitResident is the function that creates libraries and devices from simple (rommable) definitions. It allocates the base object and sets up it's interfaces and may call init functions on either.

But the real issue is how to handle this type of shared library in a protected memory environment.

Basically the library (and device or resource) is just an object. It has a data area referenced through an instance pointer (with public and private parts), and it has a set of interfaces (function table). In the no-mmu case when you 'open' a library it (normally) only gets initialised once (for the entire system), and can contain global data within its `base' object. If it needs to do a lot of initialisation work (in time or space) then this can be a huge win since every process using the same library doesn't need to do it every time. But how to do that with multiple processes with virtual memory? In OS4 they just stick to using `public memory' - globally shared read/write memory. It's not as bad as it sounds, for a single-user system, but I'm looking at adding more protection.

Code is easy, it can just be relocated to the same virtual address range and then mapped to all processes. BSS+Data is a pita. I will need to either force no globals (no Data or BSS) or implement copy-on-write. Forcing no global data is fine for any libraries I write, but if I were to `wrap' existing libraries it might be too limiting. Library bases (the data component of library objects) are another issue. Basically once the init code is run, a library expects these to be initialised and accssible for all interface calls.

About the only idea I can see working is to completely re-init the library base again for every process that opens it. If the library wants some sort of global shared state it could start its own server process and use message ports to communicate; I will need to do this anyway for devices so maybe I'll put the feature into libraries instead. It loses some of the benefits but there are big gains in security and isolation.

The executive library is a special case, for one it needs to be set up before the setup functions inside it can be called. However it may make sense to have per-process data structures the library can access from process space too. So far I have had the supervisor-state code use the library base to store global system data, and I was thinking of having it accessible read-only to all processes. But maybe they can have their own copy of some of the data, e.g. memory allocator tables or current thread-id or thread-local-storage stuff. That way processes get their own copy of 'execbase', and the supervisor code has its own structure (or perhaps its own instance of the same structure to allow for maximal code re-use). Although I don't want to be duplicating any significant amount of data during a context switch a pointer or two might be ok. More thought required.