Tuesday 29 May 2007

Smart tricks, part 1: A bootable message

Some time ago I had been wandering how does a boot loader work. Why is it booted and what does it do. Well, I've made a research and what I found out is awesome. A boot loader works in unrestricted environment, that is it can on the contrary to a program running under Linux or Windows access all BIOS features. Unrestricted. It is of course much harder to write boot loader programs because such a restricted environment doesn't provide access to all libraries we know, not even such basic things like libc. But nevertheless I wanted to try it to write some small program to run at the OS level.

My idea was to try to create a trick program. The trick was to be to write message on the screen (or rather print) and then just stop, but leaving the message on. I googled much for help, I also read much code from Linux kernel x86 boot loader and from Lilo. What I found out is that such a program runs in an not initialized environment, it means all it's register point to hell knows what, not some reasonable RAM addresses. Only properly set register is the %eip or rather %ip for such programs start in 16-bit mode! I really tried long to create some smart Assembler program. But it just wouldn't work, although I already knew how print characters. And you can't even debug your program at this stage, for obvious reasons. Now I know the reasons. How I came around the problem I'd explain afterwards. For now I owe you an explanation why it didn't work. Well, as I got to know as I started reading "Understanding the Linux Kernel" by Daniel P. Bovet and Marco Cesati, I got to know that memory addresses you play with at any level are not the addresses that are actually accessed by the processor. They are being further translated into physical addresses according to the information you provide in some special registers. It's why it didn't work, because I didn't initialize those registers and just random data was read.

Now, the problem was, I didn't exactly know with what values to initialize my registers. Nor do I know today, but I would probably be more able to try some combinations after reading few chapters of the mentioned book. So, what I thought would be a solution was not to read some data and than process it but to hard code all the data into my executable (because as mentioned instruction pointer was the only one working right without much effort). It would of course mean much work and any changes I'd like to make in the message I wanted to display wound be just almost impossibly hard to make. But now comes why I labeled this post "python". I decided to automate the process a bit by writing a Python script that would create an Assembler file for the given data. Here it is, "bootgen.py":
from sys import argv, exit

def printc(c):
print " movw $0x%x,%%ax" % (0x0e00+c)
print " movw $0x7,%bx"
print " int $0x10"

if len(argv) < 2:
exit()

f=open(argv[1])

print ".code16"
print ".text"
print ".global _start"
print "_start:"
print " sti"
print " cld"
print " movw $0x1202,%ax" # 80x25
print " movb $0x30,%bl"
print " int $0x10"

for c in f.read():
c = ord(c)
if c == ord('\n'):
printc(13)
printc(10)
printc(0)
else:
printc(c)
print "loop:"
print " jmp loop"
Here I believe I should explain a bit. I'd leave the explanation of Python grammar, it's a topic where I assume some knowledge. As you see this script outputs an Assembler file ready to be compiled and run! What does the printc function does? Well, it prints the character onto the screen. Interrupt $0x10 is a BIOS interrupt that invokes graphic card. Why do I add 0e bit the character value? Well, it a modifier that tells your graphic card to print the character in normal mode, without any colors or effects. Yes, you're right - by playing with it one can have those effects become true! Further headers are being printed. I'd leave the explanation , I've copied them myself from Lilo and Linux, just believe me they should be there. Now, the loop is the most important part of the script. It reads a given input file character for character and outputs the equivalent Assembler code to print it onto the screen. In BIOS mode you need to have new lines with \r\n and in Unix they are indicated with \n so I add some characters there. Last two lines are just the endless loop. To create an Assembler script just prepare your text message and run ./bootgen.py text.txt > boot.s. You can compile it now. As it's AT&T syntax you must use compiler. as -o boot.o boot.s will do. Now the linking command is a bit more complicated: ld boot.o -o boot.bin --oformat binary -Ttext 1000.

Now, the boot.bin is a ready bootable executable. The only thing one needs to do now is to place it somewhere where it can get booted from. What I think is funny is to create a bootalbe CD with this file. Once because it's very easy to repair but not obvious enough to be lame ;). You can of course overwrite the MBR it will be very cruel and besides, with my technique the final executables are quite big (it's more efficient to initialize your process properly and than process a string). If you decide though to overwrite MBR mind not to overwrite whole 512 bites, because in the last 150 or so your partition tables are stored.

I hope I was helpful and gave you some idea to play around the other way. Now I'd have one more piece of code for you, it's a shell script that automates a script of CD image creation.
#!/bin/sh
/bin/cp $1 `dirname $0`
cd `dirname $0`
/bin/mkdir $2
/bin/mkdir $2/boot.catalog
python bootgen.py `basename $1` > $2/boot.s
as -o $2/boot.o $2/boot.s
ld $2/boot.o -o $2/boot.bin --oformat binary -Ttext 1000
/bin/cp `basename $1` $2/
/bin/cp `basename $0` $2/
/bin/cp bootgen.py $2/
/bin/echo $0 $* > $2/gencmd
mkisofs -b boot.bin -c boot.catalog -no-emul-boot -o $2.iso $2/
cp $2.iso $2/
mkisofs -b boot.bin -c boot.catalog -no-emul-boot -o $2.iso $2/
/bin/rm -rf $2/

Monday 28 May 2007

C Function Calling Convention

Ever wondered what does happen inside the computer when a program runs? Well, there are many levels that need to be explained. Herein, I'm going to explain the abstraction layer laid between Assembler language (the most abstract of the machine code languages) and C (the least abstract of the structural languages). And although a good assembler programmer would say he writes structured programs and good C programmer would state his programs translate 1:1 to the machine code, there is a great difference between those both languages. This difference need to be somehow handled by the compiler (best example is GCCs C compiler, which actually translates C code into Assembler firstly).

The most obvious difference is that C programs are structured. Once logically into functions and those into blocks. Secondly C lets you use data structures and operate with variables (furthermore, variables are typed in C). In assembler only thing that exists is a one-dimensional bit set. You can put there whatever you want, it will be executed from the beginning to the end (in most cases). There are no variables, no functions, no types. In the matter of fact assembler also represents an approach known from languages of very high abstraction level, like LISP. This because it does not distinguish variables or data from executable code. Executable is that what you address with %eip register (instruction pointer, guess what it does or google) and data is that what you address with any other register. In assembler also, all depends on the context.

What is then the C Function Calling Convention? It's a way C compiler translates one programming approach into the other (C into assembler). It's also a way assembler programmers tend to use when they want to practice structural programming. There is only one instruction in assembler that lets you change program flow:
jmp [offset] (and many others, but all of them derivate from it - most important conditional jumps, but unimportant for our topic). Now, CFCC is the way function calls are translated into flat assembler structure. In order to understand it you will need the knowledge of the basic data structure named stack and two additional registers named %ebp (base pointer) and %esp (stack pointer). I assume basic programming knowledge so I wont bother with explaining what a stack is, rather I would explain how it looks like in programs memory.

So, computer programs stack is an ordinary stack structure, which top address is being pointed to by
%esp register. Operating system takes care of assigning the stack all the memory it needs (or telling the program if there is no memory left). You don't need to allocate memory for stack, pushing and pulling operations do it automatically, as does direct adding/subtracting some offset. I will concentrate on Intel-compatybile processors as they're the most popular ones and the only I know. On an Intel processor stack grows down. This is very important to remember! I would say it is crucial at some points and in some uses. It means that pushing a value onto the stack actually decreases %esp and pulling a value from the top increases it. So, to extend the stack, you subtract some value from %esp.

Now we know how does the stack work we shall be able to proceed. To do it, lets consider following function:

int func(a,b,c) int a,b,c; {return 0;}

When you call
func(1,2,3); there really happens much in the assembler level. What is done first is the argument handling. They are all being pushed onto the stack in reverse order. You already know what does it mean? Yes, in the matter of fact it is really easy to implement variable length argument functions in C. va_* macros make it for you. Further, the call [offset] is invoked. This instruction is a form of jmp, but it does one additional thing. It pushes current %eip value onto the stack. Than it jumps (by overwriting %eip) to the given offset. Let's have a look at our stack at this point:

[....]
[....]
[3]
[2]
[1]
[saved %eip] <- %esp

As a function is entered, first thing that it does it to save the base pointer by pushing it onto the stack and than moving the current %esp to the %ebp register. The purpose of the base pointer is to save the address in the memory where all those crucial data is stored, while %esp is being manipulated by pushes and pulls. Now the code of our function is being executed. In the meantime our stack looks like:

[....]
[....]
[3]
[2]
[1]
[saved %eip]
[saved %ebp] <- %ebp
[....] \
[....] > local variables
[....] |
[....] / <- %esp

Next interesting moment is the return statement. At the return, the return value is being stored into the %eax register, which has no special purpose. Than %ebp is being pushed to the %esp, which points to the saved %ebp. As you already probably thought it is being retrieved back into %ebp. Now a jump is being done to the location pointed by the saved %eip, now placed at the top of the stack. Last thing that is being done is to subtract the size of arguments thathave been pushed onto the stack before the call. This is done by the calling function. At this point we've got the stack state from before running of our function and the return value in %eax register. Note that you can't expect registers to have the values you've assigned them before the call, you need to save and restore them manually (only %esp, %ebp are the same and %eip is as expected).

Why is that useful to know? Firstly, it's very helpful in debugging process, where you can than trace your program flow just by base pointer chain (they make one, if you think of it). Furthermore, you now know where your local variables are being stored and can trace them also! What other uses does it has? God knows, but not only. Aleph1 also knew, and he wrote a great and famous paper about one of those other uses. To give you some clue I'd just say that most of todays exploits wouldn't exist if the stack was growing up and not down! Just google for it. From other reading I would point "Programming from the Ground Up" book by
Jonathan Bartlett, which is a great introduction into programming in assembler, but not only. And it's freely available online!

I hope I was helpful. Response and feedback are welcome.

Sunday 27 May 2007

Laptop? Huh, never heard of...

So, I've decided to get myself an laptop. Restricted funds and full awareness of what I'm seeking gave me what I've thought would be an easy choice. I was very much mistaken. My first move was of course to start at a price-comparison engine (skapiec.pl). It's really nice, with good filtering options.

I found some nice lappies, but short afterwards I got the hint that you can buy them much cheaper in USA. It's where the fun begins. Of course checking law and import/export policies wasn't the first thing I've done, otherwise I wouldn't even bother with the next step. So I started checking the offer. Visiting HP and Dell's online stores was really nice, I've configured some really nice compilations there (just to check out pricing). Here comes the first clue. Why do they have it so nice out there? I mean, here in Poland we only have pre-configured laptops. No configuring, no flexibility at all. You can only choose from what they build for you! Besides, it was exactly the time as Dells *n (Linux preinstalled) series came out and I was really eager to get one. As mentioned above, I checked the importing possibilities and instantly I knew all this beautiful world is beyond my bounds. What concerns me most is why don't they do such things here? Are the eastern countries not worth effort or what? Possibility to tune your notebook to your real needs is just great. It's unfair...

Next problem I had to face was to choose the bast available configuration matching my needs and fitting my pocket. In the meantime already my preferences drafted from AMD to Intel. Why? Firstly, graphics. It's really not easy to find an AMD laptop with reasonable graphics. I need to mention that I run Linux and don't really need full blown 3D effects, I sought something suitable for a developer station. With AMD at my price you only get ATI (hard guess, heh?) or Nvidia Go 6150, which from what I've heard are both unsuitable for Linux. What I really wanted was Intel Graphics Accelerator. But in order to get it I needed an Intel processor. Further into the processors, I wanted a 64-bit. I think it's the most suitable for modern developer station. So, back to my choice it meant Intel Core 2 Duo, Turion 64 or Turion 64 x2. Intels are quite pricey, but as mentioned above they were my preferred choice. Once because of the graphics and secondly because of Intels extensive support for F/OSS. As for AMD, I could get Turion 64 which is a single processor unit but still 64-bit, which makes it cheaper.

So the time came to make the choice. Next thing that concerned me was that some major vendors don't even sell same preconfigured laptops oversees (or even abroad) as here locally. For example you won't get a Dell Inspiron here, at least not from Dells official web store. Same goes for HP, but they do at least offer most of their products here. But if they don't want to make money on me, I'm not going to insist. What I've chosen will remain my local secret. What I can reveal is that Asian brands tend to treat central Europe much more seriously. They also tend to have better pricing and amazing reliability.

This much as to that topic. I know it's by no means useful to you, but nevertheless I want such a voice to exist over the net. Maybe American producers will come up with some conclusion and the future generations will have any use of it. For now, they're loosing very pitifully here, I believe.