Category: Software


This is the second part of my introduction on kernels for 32 bit x86 machines. In this part I will be looking into how to make a kernel, which takes advantage of a boot loader which complies with the multiboot specifications as defined by GNU[1]. This allows us to avoid messing about with moving into 32 bit mode and clears the interrupt flag as well as a few other things — it will also allow us to do a few other things with the hardware before the kernel starts, but that will be something I will not be looking into now. Before I go into the kernel itself, I will be looking into how to build the kernel, which to me, was far more troublesome than writing the kernel. I will, of course, still be using GCC 4.4.2 (I believe any version will do — I’m not doing anything fancy) and make. Using the built-in rules of make the end result is this:

OBJECTS = kernel.o boot.o
CFLAGS = -Wall -ffree-standing -pedantic -m32 -std=c99
ASFLAGS = $(CFLAGS)
LDFLAGS =  -melf_i386 -Ttext 1000000

kernel: $(OBJECTS)
	$(LD) $(LDFLAGS) $(OBJECTS) -o $@
clean:
	$(RM) *~ *.o kernel

Simply save that to the file Makefile

and it should be able to compile the kernel (that I am about to supply the code for. About the Makefile: The makefile contains three symbol definitions at the top CFLAGS, ASFLAGS and LDFLAGS. The first two (being identical) are used when compiling C source (CFLAGS) and assembler source (ASFLAGS). The final symbol is used when the kernel is linked. The CFLAGS symbol contains flags for the C compiler, which tell it that the source code is not to be linked to anything other than what is explicitly given — this is what -ffree-standing is for — and is by far the most important flag given. It is this flag which allows the kernel to run at all. The flag -m32 is only important if you are compiling the kernel on a x86-64 operating system. If you’re compiling on a i386 operating system it won’t make any difference and on any other machine the compile will utterly fail if you have it or not — in that case you need a cross compiler (which is far beyond the scope of this article, yet a simple thing to get done once you know what you’re doing). The last couple of flags are ultimately unimportant, except that -std=c99 and -pedantic changes how we can express things in the source.

The kernel it builds is the sample kernel provided in the multiboot specifications — it is a simply thing that simply prints some information to the video display and then halts the computer. It contains three files: multiboot.h, boot.S and kernel.c. The files can be found here. The file is a gzip compressed tarball of the four files specified here. I have set up and environment where the commands to build the disk image explained in the first example has been compiled into a makefile which allows me to erase the image, recreate it, compile the kernel, copy it onto the disk and boot it with Qemu with one command. The makefile in question contains the following commands:

QEMU_FLAGS = -vga std

boot: disk.img
	make -C kernel	
	sudo mount -o loop,offset=16384 -t ext2 disk.img mnt
	cp kernel/kernel mnt
	sudo umount mnt 
	qemu $(QEMU_FLAGS) -hda disk.img

commit: 
	SVN_EDITOR=vim svn commit

clean:
	make -C kernel clean
	$(RM) -r mnt *~

disk.img: grub.input parted.input mnt grub.conf
	qemu-img create disk.img 20M
	sudo parted disk.img < parted.input
	sudo mount -o loop,offset=16384 -t ext2 disk.img mnt
	sudo chown `whoami` mnt -R 
	mkdir mnt/grub -p
	cp /boot/grub/stage{1,2} /boot/grub/e2fs_stage1_5 mnt/grub	
	grub --device=/dev/null < grub.input
	cp grub.conf mnt/grub
	sudo umount mnt

mnt:
	mkdir mnt

The files grub.input parted.input simply contains the commands given to the shell as specified in the first part.

That’s it. You don’t need anything else to compile a kernel for 32 bit x86 computers. For the next part I will be dissecting the source for this minimalistic, and ultimately, useless kernel.

Kernels for 32 bit x86

The following is a short introduction to writing kernels for 32 bit x86 computers. I have taken up the topic over the weekend and have found that most of the introduction and documentation I have been able to get my hands on and lacking on the most basic things — it seems they expect you to know everything before you start learning it. Some of the details in here might be a bit too low for some — they were added for completeness and to make sure I don’t leave anything out that might be vital to someone.

This part will guide you through setting up the environment which allows you to test the kernel.

I expect the following things from you and your operating system.

You:

  • You know some basic C — you don’t have to be an expert, but it helps.

If you know x86 assembler, it helps too, but since we won’t be doing a whole lot of x86 assembler it won’t hurt a lot if you don’t know any. Besides, we’re doing this in GNU as, so chances are you’ll be confused if you are used to use {M,N}ASM or anything else that’s not AT&T syntax.

The following software is installed on your computer

  • GCC (I’ve only tested this with GCC 4.4.2 on Fedora 12)
  • Make
  • Qemu
  • binutils (a linker and an assembler)
  • parted
  • mount and umount

Your tool chain must, ofcourse, be able to produce 32 bit x86 ELF files. I have no idea if you can get all of that installed on a Windows machine, so if you don’t want to run a GNU distribution (on a real or virtual machine) then you may not be able to build and test the kernel.

Parts you need

To build and test the kernel you need the following things

  1. A boot loader
  2. A kernel
  3. A disk to boot from

The bootloader of choise in this case is GRUB legacy (I plan to move to GRUB 2 at some later point — if I ever get around to it, this article will be updated). You can’t install it before you have the disk image however, so that’s the first thing to do.

Creating the disk image

The disk image doesn’t have to be large — for the kernel I am describing here, a few hundred kilobytes will suffice. I’ll be making a 20 MiB image however. The command to do so is

qemu-img create disk.img 20M

This command will create a 20MiB file filled with zero bytes — in order for it to be usefull a partition table has to be added and a partition with a usefull filesystem has to be created. To do both, parted is used. When parted is running it will open a shell where the user can enter commands — the commands (in order) to enter are:

mklabel msdos
mkpartfs primary ext2 0 20
set 1 boot on
quit

The first command (mklabel msdos) creates a label on the disk. The second command (mkpartfs primary ext2 0 20) first creates a partition and then installs an ext2 filesystem on the parition. GRUB can now be installed, but to be able to boot on it, the third command has to be run — this makes the disk bootable. The last command simply exits parted.

Installing GRUB Legacy

To install GRUB you need to copy a few files to the disk image — in order to do that, you must first mount it. On non-UNIX like operating systems, this is likely to be very tricky — I know of no way of mounting the filesystem if mount is not present. As always you will need root access (or an entry in /etc/fstab) to mount the disk image. The command for mounting the filesystem — which does not reside directly at the beginning of the file, you need to specify an offset, for where the filesystem begins. In this case (because it’s simple) the filesystem begins after the first 16KiB. The command for mounting the filesystem is

mount -o loop,offset=16384 -t ext2 disk.img mnt

where mnt is the directory you wish to mount it on (I just use a local directory relative to the disk image). Umounting is a simple matter of running umount the usual way:

umount mnt

On the disk image, you need the directory grub to store the files GRUB need to boot.

mkdir mnt/grub

Now copy the files to the image — you need ext2 support and stage 1 and 2 files.

cp /boot/grub/stage{1,2} /boot/grub/e2fs_stage1_5 mnt/grub

The ext2 file may have a slightly different name on some systems — likely something that makes more sense (try ext2fs_stage1_5). The next step is making grub the bootloader on the image. To do so, run the following command

grub --device=/dev/null

When grub is running it will (like parted) open a shell for you to enter commands in. The commands you need to enter are:

device (hd0) disk.img
root (hd0,0)
setup (hd0)
quit

The first command maps the first BIOS disk to be disk.img — this is required for grub since it depends on the BIOS mapping of disks. The second command sets the root to be the first partition of the first disk (the partition you created earlier). The third command installs grub to the first BIOS disk (that is the image) and the final command stops grub.

Configuring GRUB

You should now have grub installed on the image. If you boot it with qemu, grub should start up and offer you a shell. In order to make grub boot the kernel (which has yet to be made and copied to the image) create the file mnt/grub/grub.conf and let it have the following content

timeout 10
default 0
title kernel
root (hd0,0)
kernel /kernel

This file will instruct grub to wait for 10 seconds and the boot entry 0 in the list of operating systems. In this case entry 0 is the only entry. This entry instructs grub to use the first partition of the first disk as the root disk and to use the file kernel, found at the root of the root disk as the kernel and then boot that kernel. Once you have that file on the image you’re done setting it up and is then ready to create the kernel.

To morfik or to make things work

I think it’s about time I bitch about Morifk (www.morfik.com).

Morfik is a RAD (Rapid Application Development) tool, designed to make it easy to produce applications that reside on the net (in a browser to be accurate), allowing the programmer to do all the code in either Object Pascal, Visual Basic or C#. That idea is fine and if they got it right it would be a great thing to have. But, as you may have guesse already, Morfik doesn’t live up to it’s own promises.

The first thing you may notice when you start using Morfik is that you often have to resort to using custom built data extraction routines, unless you are doing stock webpages (in which case it would have been smarter to simply have made a template webpage and sell that) — if you do not use one  of the (few) standard layouts, you are simply not going to have any use for the database aware components of Morfik. This means using webmethods and rebuilding what is essentially the same routine over and over again (code sharing is not a strong point of Morfik).

Another thing you will soon notice is that the date type is handled differently on the server and in the browser — the (to me) most odd thing is that it’s the browser that handles dates the best. In the end I had to code my own date type that doesn’t make use of server or browser specific code (of course I still need a browser and a server implementation, but since they are identical, that’s a minor issue more than a problem).

The company behind Morfik calls Morfik the WebOS, but in reality it feels more like you’re writing software for a set of operating systems that have to communicate over the most complex channel they could think of — raw socket programming in C is less complex (not really, I’m just frustrated).

Another strangeness of morfik is how text is handled. You cannot do things like casting a character to an integer and then print the result (that is the numeric value of the character) — that means that I, for example, am not able to search and replace anything out side the basic English alphabet, since I have no idea what morfik is using nor what external datasources are using. Which brings me to another point. Morfik uses unicode. Or it claims to do. Or that is, Morfik claims to be using unicode when it doesn’t claim not to do so. That is, Morfik doesn’t really do anything with unicode. In fact, Morfik doesn’t seem to be doing much really. If you try to print the danish letters ‘æ’, ‘ø’ or ‘å’ (or the capital equivelant) you get garbage — and since you have no idea what the numeric values are and (strangely) you cannot compare those letters with themselves once they have been outside of morfik, there is no way to replace them with the html codes for those letters (nor should you have to — morfik should just do things right). In order to replace these letters I had to copy the result of printing them a HTML page and use those results to search and replace all instances with the HTML codes for the letters — of course, this doesn’t work with Reports since they use an entirely different character set. In reports I can’t use either trick (casting or copying) to get it fixed.

These issues and problems are not related to the Morfik program though — the problems with the IDE are enough to make you cry. Random crashes, lock-ups and plain weirdness is abundant. For example, I often get an error message that says “Cannot copy to clipboard”, when I hit CTRL+X. The content is always copied but the original is never deleted. Also when viewing datatables (either internal or external) I often get no result at all, which locks up the database components of Morfik forcing me to shut down and restart the IDE to restore it.

I wish I could be allowed to do things in PHP. Sigh.

Fallout 3 sucks

Some of these points are known to about every single person who has every heard of Fallout 3 (and especially those who play it). It’s a rant with no purpose but me letting steam out.

I got a Playstation 3. Then I got a couple of games. I knew that Fallout 3 had been released for the Playstation 3, and while my stationary computer is more than capable of running Fallout 3 in terms of hardware, I do not have Windows installed (and no, it’s not an option to install it) — so I got Fallout 3 for Playstation 3. Now, I love the Playstation 3 and can’t wait for people to see what potential it has. The Cell is a kickass processor — read some technical docs on it, wikipedia is definitely not enough.

Before I got the game, I was quite nervous that I would be getting some crappy rip-of of the Fallout franchise so I decided to read some non-commercial reviews (that is by people who are not paid to write nice stories or are too biased towards crappy FPS games) and found two reviews which seemed to be by people who likes Fallout as much as I do. The most important quote from these reviews where

Fallout 3 is Oblivion with guns

Having never played Oblivion, I figured it would be an advancement from Morrowind (which I have played a bit of and kinda liked a bit), so I got the game (still rather nervous).

Now, when I got the game, I looked around in a few shops and found that I could get the PS3 version for 550 DKR (that’s danish kroner) or the Windows version for 450 DKR. Let’s just repeat that — 550 DKR, An increase of 22.22% from the Windows version, for a console where there has yet to be made a single illegal copy of a game This is important because illegal copies has been used time and time again as argumentation for inflating the price of video games (oddly enough only for Windows, never for other platforms), but still the  Playstation 3 version is the more expensive one. I would have expected the reverse to be true at best, at worst that the price was the same. Finally I managed to find a shop that gave me a discount so I only had to pay 500 DKR, but the standard price (actually, the only other price I found) is 550 DKR — which includes webshops. They would have given me a discount on the Windows version too, also at 50 DKR (which means the price difference is 25% (500/400)).

Booting the game, I find several fundamental flaws in how the game develops, the basic premises and mechanics and just about anything else. I did say I love Fallout, right? Well, I love Fallout so much, in fact, that I have given a great deal of thought to just why I love Fallout. I have completed Fallout, Fallout 2 and Fallout: Tactics (which is an excellent tactical game in it’s own right, but is not a Fallout sequal). It all come down to detail. See, in Fallout and Fallout 2 details are only important when they are important. The player is never forced to figure out some detail or play a mini-game unless it’s important. That’s what the character is there for. Instead, Fallout and Fallout 2 are about exploration and expanding your world. You explore a world, which should be completely void of life (since it’s been devastated by several very large nuclear detonation), but instead you find that the world is teeming with life (although rather absurd lifeforms). Oh, and the people in the world are really cooked. Please also note that guns where actually not that important in Fallout or Fallout 2 (though it often was to me). The game spent more time on exploration, dialog and related events than combat (at least it does when I play it). Dialog and quests where often complex and combat was simple.

On anther note, regarding the main character — in Fallout and Fallout 2, the main character is actually rather unimportant. In the first game the main character is picked at random to go out and find a new water chip and in the second game, it was planned for the main character to meet another chosen one, sent prior to the game starting. In Fallout 3, Three Dogs keeps talking about the main character and his father (who seems to be trying to save the world, at least), which brings me to yet another point. Fallout and Fallout 2 have such great stories because they are much smaller than the world, but the world contains a lot of similar sized stories — some stories in Fallout 2 can take as long as the main quest to complete, and can involve more complex dialog and world interaction than the main quest. In fact, the main quest in Fallout 2 can be done in about 30 minutes (with a bit of luck).

In Fallout 3, I find the reverse is true. I constantly have to play stupid mini-games (lockpicking, hacking), combat is almost constant and exploration is almost negligible and dialog is reduce to the most basic form. Combat on the other hand is complex and a shift has been made from turnbased to real time (V.A.T.S. is still real time) and now, players have to repair their equipment (which for some reason requires you to have two of the same type or an NPC which charges money). Fallout 3 is a first person shooter (possible the best one, but still, it’s a first person shooter). V.A.T.S. reduces some of the nastiness of playing action packed games on consoles so I’m not going to bash that too much. V.A.T.S. does have one very large and one minor flaw. The large flaw is damage to gear. In V.A:T.S. you hurt your weapons more than if you don’t use V.A.T.S. (but do more damage) the small one is that combat cannot be exclusively V.A.T.S., because Action Points do not replenish once a V.A.T.S. “round” is complete.

Let’s get back to the price issue again. Like I wrote, I paid 500 DKR for my copy for Playstation 3, paying 22-25% more for a game that cannot (yet) be copied illegally. But wait — that’s not all. I don’t get the same game as the Windows version. See, the Playstation 3 version doesn’t have support for keyboards or mice (which is an absolute must] for games like these), you cannot play multiplayer games, don’t get a G.E.C.K., and (likely) will never be able to use G.E.C.K. modules — that is, you pay more for than alternative versions, and get far far less. I’m not going to talk about bugs, since that’s a completely different issue. Software engineering is not easy and complications (especially for a completely new platform) are impossible to avoid — bugs will exist.

I think Bethesda did a few things wrong here. First of all, Fallout is Oblivion with guns. This, if true (I never played Oblivion), seems rather silly. Why not just make Oblivion with guns if that’s what they wanted? Fallout is not about guns and the game style of Morrowind (which I assume is copied to Oblivion) is not really suitable for the Fallout world. The nice graphics of Fallout 3 are in fact, also not really something that fits too well with the Fallout universe. Fallout and Fallout 2 could have had nice graphics and more realistic animations, but didn’t. I think the style of the graphics fits perfectly with the style of game found in Fallout and Fallout 2, but in Fallout 3, I find that they clash — there are way too many details and too little content.

In conclusion I’d say that Fallout 3 was not made by people who knows and plays Fallout, Fallout 2, or even Fallout: Tactics (which is more of a followup to Fallout 2 than Fallout 3 is).

Drawing in the dark.

I continue to be puzzled that companies like nVidia refuses to help in developing open source drivers for their products. The reasons for this puzzlement are many. First of all, if such drivers existed, nVidia could sell their products for a whole lot more platforms than just x86 (including x86_64) based computers. As it is now, all their drivers are for x86 Windows, Linux or Solaris.

Imagine that nVidia just had the interface for their chips in the open instead of having to write drivers and update all the time. That would mean that whomever wanted to write drivers for their kernel could do so, without having to hazzle nVidia for a decade an asking them to supply the drivers. It would also mean that nVidia would only have to provide the documentation once — they have to anyway, in order to be able to write their inhouse drivers, so that cannot be an extra cost to them.

It would also mean that whomever had support for the nVidia chips could add this support out of the box. With no setup required by the user. People could start to use the chips in new ways that nVidia hadn’t seen possible — in PDAs or mobilephones for example or as array co-processors for computational heavy tasks.

If a company wants to guarantee that a particular operating system on a particular platform has a driver that meets a certain standard, they can still write it. That there are open source drivers for a chip does not mean that a company cannot write their own drivers for that chip.

We have just about everything electrical in computers standardized so that it is possible to jank out a device from an x86 board and stuff it into a Sparc board and have it functioning. The only thing missing is the drivers.

I got a plan

I installed Plan 9 today on a spare disc I had lying around. Plan 9 is an operating system which in may ways resembles Unix — only with a much much cleaner design. A lot of people say that in Unix everything is a file; this is not entirely true as many (especially network) resources are simply not available in the filesystem. In Plan 9 everything is available in the filesystem — directly.

I think that Plan 9, the operating system, is a very well designed system with a lot of great thinking — quite frankly I doubt that there is anything out there that is any better with regards to abstraction. It, however, does deserve to be called two things: unfriendly and extremely friendly. It is unfriendly not by design, but by the state it’s in — so I guess that’s not really something I should be writing at all. The unfriendliness does not come from Plan 9′s design itself but rather from the software it carries. This is very much so, possible to fix. I doubt that the current set of developers are willing to do this though as they seem to be content with the current status quo. It is extremely friendly to those who know what they are doing and allows complete — as in with no exceptions — control over the system using text manipulating programs like awk, sed and grep.

It’s damn ugly though.

I’ve finished the mouse handling parts of glw — it took me some time because I was too much in a hurry and forgot to read the documentation right. Not a good idea.

Keyboard input is messed up though — I’ve done something terribly wrong. I’ll have to have a look at it by Sunday. RIght now, I have to sleep.

glw (my portable OpenGL window library) has a few bugs in the things I have implemented — this is of course to be expected for such an early product — so far I have squashed a few bugs resulting in seg faults on shut down (apparantly I was doing too much) but I still have a few other bugs lying around. I have an old attempt which did it right so I’m going to have to investigate what the difference is and see if I can fix my newest attempt.

I have been wondering why there is no portable window mangement library for OpenGL, so I’ve started to write my own. It’s nearing completion and have the very basic features implemented already. A few vital things (OpenGL support for example) are missing — as soon as I have that done, I’ll release the code for X (sorry, I won’t be writing a Windows port).

If you have an X server running on Windows or Mac OS X you should be able to use the code, as it only depends on X and GLX (besides the standard C library of course).

The simplest sort

I am studying Dijkstra smoothsort algorithm at the moment, with the hope that I will be able to implement it at some point in time. RIght now I don’t get what he was writing at all. Anyways, I was trying to sleep but around 5-ish, I decided that I couldn’t because of something that really bothered me.

I had an idea about sorting — the simplest way to sort I could come up with looked to me like it would sort in O(n) time, so I got up and wrote down what the algorithm would do and implemented it. I then decided that this was sos simple that there had to be others who had written this before me, but alas, I have found no references to the algorithm anywhere. I call it chain sort beacuse I envision the data as being hung on chains on a bar.

The algorithm is as follows:

Let C be a collection of chains.
For each element, E, in a list of elements, L.
Add E to it's chain C[E]


Let R be a list of elements
For each chain, c, in C
For each element, e, in c
Add e to R.

I have posted a request for more information about the algorithm on fedoraforum.org.

I also implemented the algorithm in the follwoing C++ code

template vector chain_sort(vector O_)
{
T_ min = *min_element(O_.begin(), O_.end());
T_ max = *max_element(O_.begin(), O_.end());
vector result(O_.size());
vector< vector > chains( 1 + max - min );
for (unsigned int v = 0; v < O_.size(); v++)
chains[O_[v] - min].push_back(O_[v]);
unsigned int counter = 0;
for (unsigned int i = 0; i < chains.size(); i++)
for (unsigned int j = 0; j < chains[i].size(); j++)
result[counter++] = chains[i][j];
return result;
}

Follow

Get every new post delivered to your Inbox.