Simple OS - bootloader part1

The past few days, I've finished writing the bootloader. I summarize some of them and will post them on the blog.

Introduction:
Before we started writing our code, there are some background knowlege.


Bootloader:
what is a bootloader?
A bootloader is a program that will load the kernel image into the memory, and jumps to it.

how does it works?
First when you press the power bottom, the bios will start first. And after the bios is loaded into the memory,
it will first check which device you want to boot and check the first sector(The MBR) of the device. If it is OK, the bios will put the MBR code into the memory address 0x7c00 and jump to it.

MBR:
what is MBR?
MBR is the abbreviation of master boot record. As the name suggest the code inside the MBR is the bootloader. In most cases, the MBR is in the first sector of your devices, such as the hard disk, floopy disk , compact disk and so on.

The size of the MBR is 512 bytes. There are many fields contains in a MBR.
a. code                 440bytes
b. Disk signature   4 bytes.
c. null                   2 bytes
d. Partition tables. 64bytes
e. MBR signature 2 bytes.

BIOS interrupt:


what is bios interrupt?
bios interrupt is a low level interrupt which is loaded before the bootloader. BIOS interrupt contains many useful functions which can communicate with the I/O without fully understand the architecture.

why using bios interrupt?
as I previous mentioned, bootloader is to load the kernel image into the memory, and therefore there is no os system call or drivers to help you communicate with the I/O. The best way and the most convenient way is to use the bios interrupt to handle the I/O.

Coding time:
After understand the information, it's time to write a simple hello world program in the boot loader.
Helloworld.S

.code16
.section .text
.global main
main:
#FAT12 file system format
#there is nothing to change in this part
        jmp start_prog
        .byte   0x90
        .ascii  "MicrMike"
        .word   512
        .byte   1
        .word   1
        .byte   2
        .word   224
        .word   2880
        .byte   0xf0
        .word   9
        .word   18
        .word   2
        .long   0
        .long   2880
        .byte   0
        .byte   0
        .byte   0x29
        .long   0x19900303
        .ascii  "HELLO-OS   "
        .ascii  "FAT12   "
        .fill   18, 1, 0
start_prog:
        movw $0, %ax
        movw %ax, %ss
        movw %ax, %ds
        movw %ax, %es
        movw $msg, %si
#using bios interrupt 10h
#parameter of bios interrupt 10h
#%ah: function number
#%al: the offset of the message
loop:
        movb    $0xe, %ah
        movb    (%si), %al
        cmpb    $0, %al
        je      fin
        int     $0x10
        addw    $1, %si
        jmp     loop
fin:
        jmp     fin
msg:
        .ascii  "Hello world!!."
        .byte 0
        .org    0x1fe, 0x00
        .word   0xaa55

P.S the above source code is using the at&t syntax. In this article I won't tell you how to write assembly, but you can google to find some great tutorial.

Comment:
There are many things that is worth notice in the source code.
1. The red highlight is the FAT12 file system format. Do not change this part.
2. Since we are in the real mode and the ld will assume that the code is in 0x0, I need to initial the whole base register, such as ds, ss and so on.
3. In order to print a message on the screen, I use the bios interrupt.
    bios interrupt 10h
    %ah stores the function number, in this case use the $0xe.
    %al stores the address of the message.
4. in the bottom of the code, don't forget to put the MBR signature, otherwise the bios will think the MBR is     useless.


Compile:
1. use gcc to compile the source code:
  gcc -c Helloworld.S
2. use ld to link the obj file into the binary:
  ld -Ttext=0x0 --oformat binary Helloworld.o -o Helloworld.bin
3. use mkdosfs to create a virtual floppy disk
  mkdosfs -C os.flp 1440
4. install the binary file into the virtual floppy disk by using dd 
  dd status=noxfer conv=notrunc if=$boot_bin of=os.flp
reference website:

Result:
using qemu to test the result.
qemu -fda os.flp
and you will see a hello world in the qemu.
http://duartes.org/gustavo/blog/post/how-computers-boot-up

Shell code 3(print message)

After the exit_shell.out program is finished, it's time to move on.
This time I will use a new system call which will print a message to the screen.

Background Knowlege:
the way I use the system call is still the same, using the int $0x80.
The parameters of print system call:
eax = 4  => this is the system call number.
ebx = 1  => we want to print the message to the stdout.
ecx =  msg => the address of the message.
edx = len   => the length of the message.

OK, coding time.
1.wrote the program into inline assembly.
print.c

char msg[]="Run Han";
int main(){
        __asm__("
                 movl $4,%eax;\
                 movl $1,%ebx;\
                 movl $0x7,%edx;\
                 movl $msg,%ecx;\
                 int  $0x80;\
                 movl $1,%eax;\
                 movl $0,%ebx;\
                 int  $0x80;\
                 ");
        return 0;
}

2.compile the source code with the following command:

gcc -g -o print.out print.c

3. execute the program

As u can see, the output message is in the global data, that's not good. I want the message is inside the shell code. Let's modified the source code a bit.

print_1.c

int main(){
        __asm__("
                 movl $4,%eax;\
                 movl $1,%ebx;\
                 movl $0x7,%edx;\
                 movl $msg,%ecx;\
                 int  $0x80;\
                 movl $1,%eax;\
                 movl $0,%ebx;\
                 int  $0x80;\
                 .string "Run Han"\
                 ");
        return 0;
}

However, in this way, how do I know the address of the message.

Thanks to this web site: http://insecure.org/stf/smashstack.html

I found the solution. The following is the modified version of the code.

print_2.c

int main(){
        __asm__("jmp 2f;\n\                   #2bytes
                 1:;\n\
                 popl %esi;\n\                #1bytes
                 movl $4,%eax;\n\             #5bytes
                 movl $1,%ebx;\n\             #5bytes
                 movl $0x7,%edx;\n\           #5bytes
                 movl %esi,%ecx;\n\           #2bytes
                 int  $0x80;\n\               #2bytes
                 movl $1,%eax;\n\             #5bytes
                 movl $0,%ebx;\n\             #5bytes
                 int  $0x80;\n\               #2bytes
                 2:;\n\
                 call 1b;\n\                  #5bytes
                 .string "Run Han";\n\
                 ");
        return 0;
}

Explanation:

Use the relative jmp/call to accomplish this job.

1. we first use the relative jump to jump to the call instruction.

2. next we use the relative call instruction to transfer the execution flow to the label 1.

So how does these steps has anything to do with the address of the message.

This is a very tricky way. When u call a function, the cpu will automatically push the eip into the stack. And look what is behind the call function, it is the message. So the cpu will help us to push the address of the message to the stack.

And now let's compile the file, and test the output.

It works.

The next step is much easier than above, all I have to do is use the objdump to dump the file, and change the inline assembly into shell code.

print_shell.c

char shellcode[]=
"\xeb\x20"
"\x5e"
"\xb8\x04\x00\x00\x00"
"\xbb\x01\x00\x00\x00"
"\xba\x07\x00\x00\x00"
"\x89\xf1"
"\xcd\x80"
"\xb8\x01\x00\x00\x00"
"\xbb\x00\x00\x00\x00"
"\xcd\x80"
"\xe8\xdb\xff\xff\xff"
"Run Han";
int main(){
        int *ptr;
        int i;
        /*
         *overflow the return address.
         *transfer the execution flow to shellcode.
         */
        for(i=0;i<10;i++){
                ptr = (int*)&ptr+i;
                *(ptr) = (int)shellcode;
        }
        return 0;
}

compile the program and don't forget to use the execstack command to enable the executable stack.
demo video:
http://www.youtube.com/watch?v=WpfShXa1iEk

Shell code 2 (cont.)

After the previous article, I wrote a program which use a shell code to exit normally.
However, there is a more simple way to accomplish this job. We can use the linux system call.

In linux, when you want to use a system call in assembly, just use the int $0x80.
The system call number is store in the %eax, and the parameter of the system call is store in the %ebx and so on.

Ok, it's time to use these information and write them into shell code.

First write a normal program and use inline assembly in the program.

exit.c

int main(){
     __asm__("movw $1, %eax;\
              movw $0, %ebx;\
              int  $0x80;");
     return 0;
}

and now compile it with the following command.
gcc -static -g -o exit.out exit.c
objdump -d exit.out >> dump.txt

dump.txt main function

080482c0 <main>:
 80482c0:       55                      push   %ebp
 80482c1:       89 e5                   mov    %esp,%ebp
 80482c3:       b8 01 00 00 00          mov    $0x1,%eax
 80482c8:       bb 00 00 00 00          mov    $0x0,%ebx
 80482cd:       cd 80                   int    $0x80
 80482cf:       b8 00 00 00 00          mov    $0x0,%eax
 80482d4:       5d                      pop    %ebp
 80482d5:       c3                      ret

the machine code part is what we need.
Let's change them into shell code.

exit_shell.c

char shellcode[]=
"\xb8\x01\x00\x00\x00"
"\xbb\x00\x00\x00\x00"
"\xcd\x80";
int main(){
        int *ptr;
        int i;
        for(i=0;i<10;i++){
                ptr = (int*)&ptr+i;
                *(ptr) = (int)shellcode;
        }
        return 0;
}

P.S The for loop is to overflow the return address and transfer the execution flow to the shellcode.

compile it with the following and remember to use the execstack to enable the executable stack.
gcc -static -g -o exit_shell.out exit_shell.c
execstack -s exit_shell.out


Result:
now use gdb to verify our thoughts.

(gdb) disassem main
Dump of assembler code for function main:
   0x080482c0 <+0>: push   %ebp
   0x080482c1 <+1>: mov    %esp,%ebp
   0x080482c3 <+3>: sub    $0x10,%esp
   0x080482c6 <+6>: movl   $0x0,-0x8(%ebp)
   0x080482cd <+13>: jmp    0x80482eb <main+43>
   0x080482cf <+15>: lea    -0x4(%ebp),%eax
   0x080482d2 <+18>: mov    -0x8(%ebp),%edx
   0x080482d5 <+21>: shl    $0x2,%edx
   0x080482d8 <+24>: add    %edx,%eax
   0x080482da <+26>: mov    %eax,-0x4(%ebp)
   0x080482dd <+29>: mov    -0x4(%ebp),%eax
   0x080482e0 <+32>: mov    $0x80ce028,%edx
   0x080482e5 <+37>: mov    %edx,(%eax)
   0x080482e7 <+39>: addl   $0x1,-0x8(%ebp)
   0x080482eb <+43>: cmpl   $0x9,-0x8(%ebp)
   0x080482ef <+47>: jle    0x80482cf <main+15>
   0x080482f1 <+49>: mov    $0x0,%eax
   0x080482f6 <+54>: leave  
   0x080482f7 <+55>: ret    
End of assembler dump.
(gdb) b *(main+55)
Breakpoint 1 at 0x80482f7: file exit_shell.c, line 12.
(gdb) r
Breakpoint 1, 0x080482f7 in main () at exit_shell.c:12
12 }
(gdb) ni
0x080ce028 in shellcode ()
(gdb) x/4i $eip
=> 0x80ce028 <shellcode>: mov    $0x1,%eax
   0x80ce02d <shellcode+5>: mov    $0x0,%ebx
   0x80ce032 <shellcode+10>: int    $0x80
   0x80ce034 <shellcode+12>: add    %al,(%eax)
(gdb) ni
0x080ce02d in shellcode ()
(gdb) ni
0x080ce032 in shellcode ()
(gdb) ni
Program exited normally.

The result is just what we expected. When main function returned, it will start execute the shellcode.
And exited normally.
video demo is right here (using full screen is better):
http://www.youtube.com/watch?v=I6iYFQl-3kk&feature=player_embedded#at=14

nachos (cont.)

After building and install the nachos, the second project is to fix a bug in nachos.

Bug description:
When nachos is executing two different executable files, the result will be weird.
The following is picture is how the bug looks like.

Finding the Bug:
Now I know what the bug looks like, It's time to find out what cause the bug.
Since our TA have told us that the bug may be in the ./userprog/addrspace.h and ./userprog/addrspace.cc, my team mate and I start to understand what this two files are doing.

what we are interested are 
1. AddrSpace::Load(), which will load the image into the physical addrspace.
2. AddrSpace::AddrSpace, which is the constructor of this class, and will create the page table of this process.


In the source code of AddrSpace::Load()
these code is to load the .text and .data into the physical memory

if (noffH.code.size > 0) {        
        executable->ReadAt(&(kernel->machine->mainMemory[noffH.code.virtualAddr]),noffH.code.size, noffH.code.inFileAddr);
    }
if (noffH.initData.size > 0) {        
        executable->ReadAt(&(kernel->machine->mainMemory[noffH.initData.virtualAddr]),noffH.initData.size, noffH.initData.inFileAddr);
    }


The allocating process will allocate the virtual address space into the physical address space.
However as the red highlight suggest, the physical address of the process is exactly the same as the virtual address of the process.
If the second process is allocate into the memory, it will overwrite the previous process. Hence, when the previous process restore the state, it will execute the code of another process, not the one belongs to it.
Here, we may find our problem.


But not so fast, before we modified the code and fixed the bug, there is one thing that we need to be aware.Nachos is using paging to map the virtual address to physical address. Therefore, when we modified the allocating part, we also need to modified the paging (page tables).The mapping of the page table is in the constructor. As the code suggest, the page table is one to one linear mapping. Therefore, if another process is load into the memory, and the process 1 restore the state. The page table of process 1 will tell that the physical address space of process1 in in the old place where it has already been overwritten by process 2.


Fixed the bug:
Now we have the information we need. It's time to modified the code and fix the bug.
The method of our team is to add a static unsigned int variable which will record how many physical frame is being used, and when process 2 is load into the memory, it will not overwritten the address space of process 1.


1. first add a static unsigned int variable in the addrspace.h

addrspace.h

class AddrSpace {

  public:

   .....

  private:

    TranslationEntry *pageTable;

    unsigned int numPages;

    static unsigned int usedPhys;

    

    bool Load(char *fileName);

    void InitRegisters();

};

2. initialize the static variable in the addrspace.cc

    #include "addrspace.h"

  unsigned int AddrSpace::usedPhys=0;

3. modified the AddrSpace::Load()

    executable->ReadAt(

&(kernel->machine->mainMemory[noffH.code.virtualAddr+128*usedPhys]),noffH.code.size, noffH.code.inFileAddr);

P.S 

why usedPhys multiply 128 before adding to the virtualAddr?

The reason is simple, cuz the usedPhys is the page frame which is being used, not the physical memory.

Therefore, when we are adding the usedPhys we also need to multiply the page size of the page frame, which is 128 byte per page.

4.remapping the page table

   for (unsigned int i = 0; i < numPages; i++) {

pageTable[i].virtualPage = i;

pageTable[i].physicalPage = i+usedPhys; 

    }

P.S

   the numPages is the number of the page frame the current process is using.

   there is no need to map the whole page again, just those the process is using.

5. record the usedPhys

    usedPhys += numPages;

P.S

   after those steps, adding the numPages to the usedPhys. Therefore, when the process 2 is loading it will not overwritten the address space of process 1.

6. the last steps is to compile the source code again and test the result.

Result:

building nachos

My Operating system final project came out recently. The project is to build the nachos and modify some of the source code to let us understand more about operating system.

However, the GCC version to compile the nachos OS is pretty low(gcc 2.95). This is not good since my environment is ubuntu 10.10 and the gcc version under ubuntu is 4.45.(way too high for building nachos). Fortunately, the source code of the nachos  is not very long, so I modified some of the source code and Makefile to accomplished the building process.

Here is how I done it:
1. download the nachos source code.
    wget http://neuron.csie.ntust.edu.tw/homework/99/os/materials/nachos-4.0.tar.gz
2.download the mips cross compile tool
   wget http://neuron.csie.ntust.edu.tw/homework/99/os/materials/mips-decstation.linux-xgcc.gz
3.move the mips cross compile tool to the root directory
  sudo mv  mips-decstation.linux-xgcc.gz /
4.unzip the file
  sudo tar zxvf mips-decstation.linux-xgcc.gz /
5.unzip the nachos 
  tar zxvf nachos-4.0.tar.gz


It's time to build the source file.
  cd ${nachos directory}/code
  make
after doing this some problems pop up.
First
     /bin/sh: gmake: not found
solution:
    use any text editor to change the Makefile. 
    Change
    MAKE = gmake make
Second
   the second problem is the ../lib/sysdep.h
   the iostream.h not found
solution:
   simply change the <iostream.h> to <iostream> and add a new line using namespace std;
Third
   the reason of the third problem is the gcc version
solution:
   use text editor the modified the Makefile.common,
   modified the line called "CFLAGS =  -g -Wall -fwritable-strings ........"
Fourth
   the terminal will echo many errors.
solution:
   the solution is very simple, add this-> to the error variables or functions.

this is it, the nachos is finished, enjoyed.

Here is the video tutorial by Isaias

 
The original link:http://os-fime.blogspot.com/2011/08/how-to-compile-nachos.html

reference website:http://neuron.csie.ntust.edu.tw/homework/99/OS/homework/homework1/B9715017-hw1-1/#ubuntu10

Shell code

After studying computer science for about two years, I have change my thought about executable files.
A executable format may contains many section, such as .text(where your code is stored), .data(where your global variables and static variables is stored)...
Have you ever wonder if we stored the executable bytes in the .data section? This is what a shell code is.

here is an example to demonstrate how it works.
My environment is ubuntu 10.10 and gcc version is 4.4.5.
First writing a simple program which just do nothing at all.


example1.c

#include <stdlib.h>

int main()

{

     exit(0);

     return 0;

}


makefile:
gcc -g -static -o example1.out example1.c       //compile the source file with static link
objdump -D example1.out >> example1.dump          //dump the executable file

now lets see what happened by looking at the example1.dump.

080482c0 <main>
80482c0:    55                                 push   %ebp
80482c1:    89 e5                              mov    %esp,%ebp
80482c3:    83 e4 f0                           and    $0xfffffff0,%esp
80482c6:    83 ec 10                           sub    $0x10,%esp
80482c9:    c7 04 24 00 00 00 00               movl   $0x0,(%esp)
80482d0:    e8 db 08 00 00                     call   8048bb0 <exit>


the first two instructions is to set the stack frame of main.
the third instruction is to align the stack segment.
the last two instruction is to push the parameter into the stack and call function exit. 
What we are interested in is the last two instruction.


lets write a second example.


example2.c

#include <stdlib.h>
int main()
{
     asm("movl $0x0,(%esp);\
              call 0x8048bb0;\
              ");
}

lets see the dump file.
080482c0 <main>:
80482c0:    55                                   push   %ebp
80482c1:    89 e5                                mov    %esp,%ebp
80482c3:    c7 04 24 00 00 00 00                 movl   $0x0,(%esp)
80482ca:    e8 e1 08 00 00                       call   8048bb0 <exit>


and now lets turn it into shell code.
but before we do that there are something we should know first.
when gcc transfer the assembly into machine code, it will use a related call which will called the function by the offset.
Therefore, when we turn this into shell code, the address will be different depending on where your shell code is located.
Therefore, we need to use an absolute call instead of a related call.
lets first write them into assembly language.


example3.c

#include <stdlib.h>
int main()
{
     asm("movl $0x0,(%esp);\
              movl $0x8048bb0,%eax;\
              call *%eax;\
             ");
}

and the dump file:
080482c0 <main>:
80482c0:    55                                  push   %ebp
80482c1:    89 e5                               mov    %esp,%ebp
80482c3:    c7 04 24 00 00 00 00                movl   $0x0,(%esp)
80482ca:    b8 b0 8b 04 08                      mov    $0x8048bb0,%eax
80482cf:    ff d0                               call   *%eax
80482d1:    5d                                  pop    %ebp
80482d2:    c3                                  ret

In example3 the highlight is the main difference. The instruction byte become 0xff instead of 0xe8
and now let's transfer 0x80482c3~ 0x80482cf into shell code.

example4.c

#include <stdlib.h>
char shellcode[] = "\xc7\x04\x24\x00\x00\x00\x00\xb8\xb0\x8b\x04\x08\xff\xd0";
int main()
{
     int *ptr;
     int i;
     for(i=0;i<10;i++)
     {
          ptr = (int*)&ptr+i;
          (*ptr) = (int)shellcode;
     }
     return 0;   
}

you  may wonder what is the purpose of the for loop and the int pointer.
When we finished writing the shellcode,  the executable bytes is in the data section.
Therefore we need to find a way to transfer the executable path to the shellcode.
And the method I used is to override the Return address of the main function, so when the main function is return, it will return to the shellcode instead of the caller function.

now execute it, and you will meet a segmentation fault.
it's time to use gdb to debug this program.


(gdb) disassem main
Dump of assembler code for function main:
   0x080482c0 <+0>:     push   %ebp
   0x080482c1 <+1>:     mov    %esp,%ebp
   0x080482c3 <+3>:     sub    $0x10,%esp
   0x080482c6 <+6>:     movl   $0x0,-0x8(%ebp)
   0x080482cd <+13>:    jmp    0x80482eb <main+43>
   0x080482cf <+15>:    lea    -0x4(%ebp),%eax
   0x080482d2 <+18>:    mov    -0x8(%ebp),%edx
   0x080482d5 <+21>:    shl    $0x2,%edx
   0x080482d8 <+24>:    add    %edx,%eax
   0x080482da <+26>:    mov    %eax,-0x4(%ebp)
   0x080482dd <+29>:    mov    -0x4(%ebp),%eax
   0x080482e0 <+32>:    mov    $0x80ce028,%edx
   0x080482e5 <+37>:    mov    %edx,(%eax)
   0x080482e7 <+39>:    addl   $0x1,-0x8(%ebp)
   0x080482eb <+43>:    cmpl   $0x9,-0x8(%ebp)
   0x080482ef <+47>:    jle    0x80482cf <main+15>
   0x080482f1 <+49>:    mov    $0x0,%eax
   0x080482f6 <+54>:    leave 
   0x080482f7 <+55>:    ret   
End of assembler dump.
(gdb) b *(main+55)
Breakpoint 1 at 0x80482f7: file example4.c, line 13.
(gdb) r
Starting program: example4.out Breakpoint 1, 0x080482f7 in main () at example4.c:13
13    }
(gdb) x/a $esp
0xbffff2ec:    0x80ce028 <shellcode>
(gdb) x/3i 0x80ce028
   0x80ce028 <shellcode>:       movl   $0x0,(%esp)
   0x80ce02f <shellcode+7>:     mov    $0x8048bb0,%eax
   0x80ce034 <shellcode+12>:    call   *%eax

(gdb) disassem exit
Dump of assembler code for function exit:
   0x08048bd0 <+0>:    push   %ebp
   0x08048bd1 <+1>:    mov    %esp,%ebp
   0x08048bd3 <+3>:    sub    $0x18,%esp
   0x08048bd6 <+6>:    mov    0x8(%ebp),%eax
   0x08048bd9 <+9>:    movl   $0x1,0x8(%esp)
   0x08048be1 <+17>:    movl   $0x80ce03c,0x4(%esp)
   0x08048be9 <+25>:    mov    %eax,(%esp)
   0x08048bec <+28>:    call   0x8048ad0 <__run_exit_handlers>
End of assembler dump.


oh no, the address of exit() is changed.
this may be our problem, let's modify the shellcode


example5.c


#include <stdlib.h>
char shellcode[] = "\xc7\x04\x24\x00\x00\x00\x00\xb8\xd0\x8b\x04\x08\xff\xd0";
int main()
{
     int *ptr;
     int i;
     for(i=0;i<10;i++)
     {
          ptr = (int*)&ptr+i;
          (*ptr) = (int)shellcode;
     }
     return 0;    
}

compile it and execute it. and still meet segmentation fault.
let's use gdb again.
(gdb) b *(main+55)
Breakpoint 1 at 0x80482f7: file example5.c, line 13.
(gdb) r
Starting program: example5.out
Breakpoint 1, 0x080482f7 in main () at example5.c:13
13    }
(gdb) x/a $esp
0xbffff2ec:    0x80ce028 <shellcode>
(gdb) x/3i 0x80ce028
   0x80ce028 <shellcode>:        movl   $0x0,(%esp)
   0x80ce02f <shellcode+7>:      mov    $0x8048bd0,%eax
   0x80ce034 <shellcode+12>:     call   *%eax
(gdb) x/i exit
   0x8048bd0 <exit>:    push   %ebp

everything looks ok, so where is the problem.
the reason causing this problem is the nonexecutable stack.
type sudo apt-get install execstack in your command shell.
        execstack -s example5.out
after that the program is finally finished as expected.

next article: shell code 2 (cont.)
reference website:
https://paulmakowski.wordpress.com/2011/01/25/smashing-the-stack-in-2011/
http://stackoverflow.com/questions/5850524/buffer-overflow-problem