Lab 1 - boot loader

Part 2: The Boot Loader

Q/A Section:

Q: At exactly what point does the processor transition from executing 16-bit code to executing 32-bit code?

A: Processor transitions from executing 16-bit code to executing 32-bit code on execution of following instruction:

1

    mov cr0, eax

Q: What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?

A: Last instruction of boot loader executed is call of routine in .text section of kernel:

1

    call *%eax

Q: How does the boot loader decide how many sectors it must read in order to fetch the entire kernel from disk? Where does it find this information?

A: Boot loader decides how many sectors to read using information stored in ELF header. The ELF file format is shown in following image:

At the start of main.c, first sector (512 bytes) is loaded from disk. This sector is now in memory starting on location of 0x10000 and contains ELF File Header. First check is whether this is a correct ELF file by checking if magic number (first four bytes) of ELF file are correct:

1
2
3

  if (ELFHDR->e_magic != ELF_MAGIC)
          goto bad;

ELF Program Header address is loaded to ph variable:

1

    ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);

where e_phoff is the offset of program header from the start of the file. Then we store the address of last program header to eph variable:

1

    eph = ph + ELFHDR->e_phnum;

where e_phnum is the number of entries in program header. Now we simply iterate through program header table and read segments using function readseg giving it 3 arguments:

1
2
3

    ph->p_va (Segment virtual address)
    ph->p_memsz (Segment size in memory)
    ph->p_offset (Segment file offset)

It’s obvious that read size is rounded to sector size boundary which means that we load more than we really need in most cases.

Exercise 6. Reset the machine (exit qemu and start it again). Examine the 8 words of memory at 0x00100000 at the point the BIOS enters the boot loader, and then again at the point the boot loader enters the kernel. Why are they different?

A: Entry point in kernel is 0xf0100000 which we pass as virtual address to readseg function which does 0xf0100000 & 0xFFFFFF which gives the address at which we load the program text (0x100000). First 8 words contain first 8 words of kernel program text.

Exercise 8. We have omitted a small fragment of code - the code necessary to print octal numbers using patterns of the form “%o”. Find and fill in this code fragment.

Following fragment is added starting with line 209 in printfmt.c:

1
2
3
4

    case 'o':
        num = getuint(&ap, lflag);
        base = 8;
        goto number;

Q: Explain the interface between printf.c and console.c. Specifically, what function does console.c export? How is this function used by printf.c?

A: File console.c exposes cputchar function which is used in printf.c file.

Q: Explain the following from console.c:

1
2
3
4
5
6
7

    if (crt_pos >= CRT_SIZE) {
        int i;
        memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
        for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
            crt_buf[i] = 0x0700 | ' ';
        crt_pos -= CRT_COLS;
    }

A: This code does line scrolling if crt_pos is at last line of crt + 1

Q: In the following code, what is going to be printed after ‘y=’? (note: the answer is not a specific value.) Why does this happen?

A: Random garbage will be printed since second variable is not specified.

Challenge Enhance the console to allow text to be printed in different colors.

I decided to go with standard ANSI escape sequences to define text foreground and background colors. Full specification can be found here ANSI escape sequence. Defined functions include various screen actions but for text foreground/background coloring I decided to implement just a small subset of whole specification called “Set Graphics Mode”. Following pattern is used to specify color:

Esc[Value;...;Valuem

Following attributes are defined:

Text attributes:

0 All attributes off
1 Bold on
4 Underscore (on monochrome display adapter only)
5 Blink on
7 Reverse video on
8 Concealed on

(in my implementation - text attributes are ignored)

Foreground colors:

30 Black
31 Red
32 Green
33 Yellow
34 Blue
35 Magenta
36 Cyan
37 White

Background colors:

40 Black
41 Red
42 Green
43 Yellow
44 Blue
45 Magenta
46 Cyan
47 White

ANSI defined colors and CGA colors use different codes so translation table was needed. This table is defined in following array:

1
2
3
4
5
6
7
8
9
10

static int ansi_to_cga_color[] = {
    0, /* black */
    4, /* red */
    2, /* green */
    7, /* yellow */
    1, /* blue */
    5, /* magenta */
    3, /* cyan */
    7, /* white */
};

All changes are done in lib/printfmt.c file in 6e626f5e1fa1cb8d1daccccbd775c29faf7f836a commit.

To test this feature I added ANSI coloring to one of of cprintf’s:

1

    cprintf("[32;45m395[40;31m decimal [37mis %o octal!\n", 395);

And the result is:

Exercise 11. Implement the backtrace function as specified above. Use the same format as in the example, since otherwise the grading script will be confused. When you think you have it working right, run make grade to see if its output conforms to what our grading script expects (you should pass the Count and Args tests), and fix it if it doesn’t. After you have handed in your Lab 1 code, you are welcome to change the output format of the backtrace function any way you like.

Calling stack for C programs has following layout:

I created the following C structure to read parameters from calling stack:

1
2
3
4
5

    struct c_frame {
          void *prev_ebp;
          void *eip;
          unsigned int args[5];
  };

I decided to limit it to 5 function arguments since not a single function in current JOS kernel uses more than 4 - so this should be enough. Now the only problem is how to know when to stop recursive traversing of stack and for that answer, following line is from kern\entry.S:

1

    movl    $0x0,%ebp                       # nuke frame pointer

So this way - when we reach ebp with value 0 - we know that we should stop traversing stack. This is partial code of traverse:

1
2
3
4
5
6
7

    fp = (struct c_frame *) read_ebp();
    while (NULL != fp) {
      /*
       * Do something with current stack data
       */
      fp = (struct c_frame *) fp->prev_ebp;
    }

The rest of this exercise is simply printing arguments using:

1

    fp->args[0] … fp->args[4]

Exercise 12. Modify your stack backtrace function to display, for each eip, the function name, source file name, and line number corresponding to that eip.

Excellent tutorial on stabs debug format can be found here.

Stabs structure and constants are defined in inc\stab.h. I decided to do both of those functions in one commit (036672789b00140a951cc216f4ae8066b4c28a00). Here is the result:

and grade script for this lab is satisfied:

EXTRA point This makes pretty useful backtrace function but I didn’t want to guess how many arguments there are to the function (by default we print 5 of them no matter how many of them function uses) nor arguments names so I decided to use N_PSYM stab tag to calculate number of arguments and get argument names. Now the same output with this enhancement is a bit more useful:

We can easily spot from this output that monitor function has one argument named tf, that i386_init has no arguments etc, etc. This will make troubleshooting a bit easier.

This enhancement is in commit (74818a8a7afc72da67f4c43a48a7e6bcd2f73960).

FAQ

Q: Didn’t you attend Operating Systems class in school?

A: Yes, there was one. It was good for introductory suff like using syscalls from user-land, getting to know what process is, what thread is, how to do mutual exclusion using semaphores, mutexes etc., how to use signals…. It was good but it was all user-land based. There was no hacking kernel space at all.

Q: Why this class? Why not Coursera or something else?

A: I love Coursera. I took three courses there “Machine Learning”, “Algorithms: Design and Analysis, Part 1” and “Compilers”. All three are great courses. Unfortunately there is no operating systems class. I found classes from few universities (Brown, MIT) but not all lab software is available to “outsiders”. This course is used by University of Texas as CS372H (it’s actually a MIT class) and all materials are publicly available.

Q: Why learning operating systems? Are you going for an operating system devel job?

A: Well, I am interested in operating systems. I can’t explain it - I just love low level stuff. I don’t expect to land operating systems dev job since there is no such thing as operating systems dev where I live. (There isn’t much IT wise where I live at all, but that is another story).

System setup

Linux setup

I will be doing these labs on Linux Mint 13 64-bit which is publicly available for download. There is no particular reason for this exact version - I just had it at home on DVD.

Procedure described at Tools page work as described except one little thing - I found that gcc “make” should not be started inside gcc source directory. I created build directory and started configure, make and make install from it.

Labs

Labs are available from following GIT repository. All the implementations I do as a part of this labs are available at github. Now we are done with setup and can actually start working on labs assignments.

I recently compiled R14B04 version of Erlang OTP suite and tried to make it work with Distel (current trunk version). Pretty good how-to is described on Clemensont’s blog but still had two major problems with Erlang/Distel/Emacs24 combo:

* Connect to node (C-c C-d n) and node-ping (C-c C-d g) 
  would always result in message “nodedown”
* (after first one is fixed): Sometimes when adding breakpoint 
  I would get a message “Module is not interpreted, can’t set breakpoints”

Solutions are as follows:

“Nodedown” problem

This message indicated that Emacs is unable to connect to inferior Erlang process. This is a well known problem of Distel/Erlang for versions of Erlang starting from R14. I downloaded the patch from Ralfs post and applied it to Distel epmd.el file. Now I can correctly connect to Erlang node.

“Module is not interpreted, can’t set breakpoints” problem

This is also Distel issue (so it seems). Fortunately, there is a simple workaround – when this message appears do the following:

* C-c C-d m (opens the monitor buffer)
* k (kills the monitor buffer)
* C-c C-d i (start interpreting) in the .erl buffer will now work.

That’s it.

If you never heard of mach system calls and specifically task_for_pid() call on Mac OS X, you can consider yourself lucky. If you want to stay that way – stop reading now! Still here? In that case let’s start with disclaimer – author of this text is not and can not be in any way responsible for damage produced or influenced by this article.

Prior to the Mac OS X 10.4.X (Tiger), it was completely legal for one process to control another for the purpose of influencing its execution (single stepping, resuming, stopping etc) and inspecting or modifying its memory and registers. In one of the patches for Tiger, this policy was changed so that only a process owned by root or with a “primary effective group of procmod or procview” has this privilege. In Leopard (Mac OS X 10.5), this policy was changed again (that much about consistent security policy – nice work Apple) such that an inspector process now depends on the security framework to authorize use of the task_for_pid system service which gives a process the capability to control another process.

To build a utility that will use task_for_pid(), you need to do the following:

1. Create Info.plist file which will be embedded to your executable 
   file and will enable code signing 
2. Create self-signed code signing certificate using Keychain access 
3. Write your program that uses security framework to obtain rights 
   to execute task\_for_pid() 
4. Compile your program and code-sign it.

So let’s get started.

Step 1 – Create Info.plist

I used one of the standard Info.plist files I could find in Xcode and changed some particular parts as can be seen in following example:

File /root/BLOG/clean-octopress/octopress/source/downloads/code/task_for_pid_info_plist.xml could not be found

The important part is key “SecTaskAccess” with value “allowed”.

Step 2 – Create self-signed code signing certificate

Open your Keychain Access and do the following:

When created – this certificate will be untrusted by default – change “When using this certificate” to “Always Trust” and you should be OK and ready to go for the next step.

Step 3 – Write your program

I wrote a very simple program that takes PID of a process you want to investigate (ran by your UID), connects to it and writes current register values for it. Code is pretty self-explaining so I won’t go into nifty details:

File /root/BLOG/clean-octopress/octopress/source/downloads/code/task_for_pid_prog.c could not be found

Step 4 – Compile and sign

To compile the program I used following command line:

1

gcc tfpexample.c -sectcreate __TEXT __info_plist ./Info.plist -o tfpexample -framework Security - framework CoreFoundation

To sign the code with certificate we prepared before – do this:

1

codesign -s tfpexample ./tfpexample

We can check if everything went OK:

1
2
3
4
5
6
7
8
9
10
11
12
13

[ivan]~/hoby/debuger/blog-tfp > codesign -dvvv ./tfpexample

Executable=/Users/ivan/hoby/debuger/blog-tfp/tfpexample 
Identifier=net.os-tres.tfpexample 
Format=Mach-O thin (i386)
CodeDirectory v=20001 size=187 flags=0!0(none) hashes=4+2 location=embedded 
CDHash=30c98f962fc9a2b1a2f73cff55d4584bd053aa3a 
Signature size=1454 
Authority=tfpexample
Signed Time=Feb 17, 2010 8:40:04 PM 
Info.plist entries=6 
Sealed Resources=none 
Internal requirements count=0 size=12

This looks good – let’s test it.

Step 5 – Test program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

[ivan]~/hoby/debuger/blog-tfp > 
[ivan]~/hoby/debuger/blog-tfp > ps 

PID TTY TIME CMD 
2511 ttys000 0:00.02 -zsh
2104 ttys001 0:00.08 -zsh 

[ivan]~/hoby/debuger/blog-tfp > 
[ivan]~/hoby/debuger/blog-tfp > ./tfpexample 

Enter pid: 2104 

Thread 2104 has 1 threads. Thread 0 state: 
EIP: 953d1562 
EAX: 4006f 
EBX: 2ad74 
ECX: bffff9cc 
EDX: 953d1562 SS: 1f 

[ivan]~/hoby/debuger/blog-tfp >

It works.