On stuff, and other stuff.

Well I've updated the cell tutorial with another entry. This rounds out the optimisations for the Mandelbrot Set generator, with I think some impressive results.

I spent most of the weekend (another nasty cold and wet one) plugging away at my renderer and reading up on bits and pieces. As I suspected `it was harder than that'. Oh well. Losing interest on that track, so I think I will play with some Cell code for a while - I started work on completing the IPC chapter again which I'd abandoned a couple of months ago. Then I might go back to the freetype renderer or maybe agg (the freetype renderer I was looking at turned out to be based on that).

It's amazing how much ones productivity changes from day to day. When things are kicking along you can write several thousands of lines of code in a week, and a lot of it can be good code. When you hit a wall everything seems to grind to a halt. I spent all weekend writing 50 lines of ... total worthless crap.

Oh well, another week gets under-way.

A pixel as a unit square

So while I think about whether I stick to freetype or try something else, I've started playing with ideas for my own renderer. I actually have a screen-shot capable output, but I don't have it handy right now. Maybe next time.

After a few silly mistakes with list pointers, I've been surprised at just how simple it is to get something up that looks quite reasonable. I am most certainly missing something, because it can't be this easy; the few 'i'm not sure' edge cases are probably where the problems come in that'll keep me from ever finishing it. I've basically done a simple 'classic' scan-line renderer which keeps track of the X coords as it steps down the Y coords, then scans from one side to the other keeping track of edge crossings and using that to work out when to fill or not. The only interesting thing is that I compute exact pixel coverage as I go so I can produce quite nicely anti-aliased lines with very little extra work. There are some artefacts with intersecting lines, and non-zero fill rule has some big issues, but I'm not particularly worried about them right now. I wouldn't have a clue if it is all that fast though, quite probably it isn't. The coverage calculation is particularly simple - since I treat each pixel as a unit square, much of the time the multiplications are just by a factor of 1, so the coverage is just a simple sum and a divide by 2.

I guess the more complicated part of the equation is the line stroker. The basic idea is simple enough, but there a lot of nasty cases to handle if you have unusually fat lines, and what to do about intersecting lines. Dashed lines seem like a hassle too.

Well, at least with my own implementation it might make it easier to look at making it work on a Cell B.E., which should all keep me busy for the foreseeable future should I decide to investigate that. So the OS idea is on hold for now.

Butt stroking and other stuff

Well that was a long wet dreary weekend. I managed to avoid leaving the house (getting through some old stuff in the cupboard and freezer at last) ... and of course spent an inordinate amount of time hacking away.

OpenVG needs a lot of scaffolding to get started - so I spent a lot of time doing that. Lots of code for getting and setting attributes and whatnot. And the path type. So I had to brush up on splines and geometric algorithms again, and I was back in the land of vectors and splines and whatnot - again. I wrote a nice little non-recursive adaptive spline tessellator I could use for implementing some of the features required like path length.

I originally wrote a vgpath that worked the same way as the reference implementation ... but just about the time I got most of it finished I got sick of writing yet-another-loop that parsed the data in slightly different ways, so I decided to change it around a bit, focussing on simplifying the code. So basically now I only have to canonicalise the data once, and the other functions can work on a simplified data stream, and not have to calculate relative or partial coordinates or smooth control points or arcs (although I haven't done them yet) or even data conversion every time they run. e.g. VLINE/HLINE are converted to LINE, all _RELs are converted to _ABSs, SCUBIC/SQUAD converted to QUAD, ARC's into QUAD's. I think doing that will still honour the API and it simplifies other bits of code. But since this is only the 2nd attempt I've probably got this wrong too - always seems to take 3 goes to get something right (as I write this I'm already thinking of some things I did wrong).

A few short lines of code later and I had it hooked up to the FreeType renderer and discovered the headline bug above. Butt line endings wasn't implemented, although it took a while to discover that since I just assumed it must be my code since the enumeration existed. I've submitted a patch which has already been applied (I must've been a bit tired as it took me a while to realise why 'butt stroking bug freetype' didn't find anything relevant, but seemed to probe the darker regions of the internets instead). I played around with the stroker a bit more and found other issues, and ended up delving into the source code more deeply - now I'm not sure I will use the FreeType stroker and renderer as I'd hoped to. To start with, a couple of features are missing or different. And it is, as they say on the box 'optimised for small sizes'. The algorithm is quite interesting though - basically it renders a band (ideally the whole image) into a 'sparse' bitmap, and then just steps through that to produce runs of filled pixels by keep track of edge crossings. So unlike a normal scan-line renderer it doesn't need to keep track of active lists and so forth, or update the lines piecemeal. Unfortunately I don't have a real handle on how scalable the algorithm is to screen-size resolutions. I may have to 'suck it and see', otherwise I'll get no where ...

... Since, to cut a long story short I've started delving into the mysterious and dark corridors of writing my own AA renderer. I orignally looked at FreeType because 1. I intend to use it anyway for font glyphs, and 2. It has few dependencies, and 3. It's easy to use. I'd also considered libart, but I thought was more closely tied to glib than it is, but it also no longer seems to be maintained, and apart from that it looks a bit over-engineered for my taste. And well, writing my own could be interesting - until you hit all the weird edge cases and numerical stability issues that throw it under a bridge. I still have at the back of my mind the idea of making this run well on a Cell BE too, so that's another reason to investigate since I need to know how it works, even if I just adapt another bit of code.

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.