Raphael S.Carvalho's Programming Blog


"A programmer that cannot debug effectively is blind."

Wednesday, January 23, 2013

Hacking over and over...

Geek quote: "The size of a word is not a universal standard."

I loved the following papers and I'm sure you'll also like them.
Reading Recomendations...
- (Excellent document) Eric S. Raymond: How to become a hacker: http://www.catb.org/esr/faqs/hacker-howto.html
- (Read carefully) Peter Norvig: Teach Yourself Programming in Ten Years: http://norvig.com/21-days.html

I also would like to share the way I solved the exercise 5 of MIT OS course...
Exercise 5. Trace through the first few instructions of the boot loader again and identify the first instruction that would "break" or otherwise do the wrong thing if you were to get the boot loader's link address wrong. Then change the link address in boot/Makefrag to something wrong, run make clean, recompile the lab with make, and trace into the boot loader again to see what happens. Don't forget to change the link address back and make clean again afterward!

Firstly, follow some details that may give you a better understanding of this exercise.
The Load address of a section is the memory address at which that section should be loaded into memory.
The Link address of a section is the memory address from which the section expects to execute.

As I said earlier, the BIOS goes through the list of available devices and performs the following action with each entry:
- Checks whether the device is bootable, and if so, loads the bootloader code into memory[1] and starts executing it.

[1]: The code of the bootloader is implicitly loaded at the physical address 0x7c00.

I traced through the bootloader code, and I was wondering whether unconditional/conditional jumps would work properly or not.
However, I got the answer. These instructions use relative addressing (base + offset) instead of absolute addressing.
So regardless of position code, any jump instruction will always work in silence.

Follow some jump instructions (Both of them are conditional jumps):
    7c0e:    75 fa                    jne    7c0a <seta20.1>
    7c18:    75 fa                    jne    7c14 <seta20.2>

Now is time to change the link address and see what will happens... The link address is specified by the makefile of bootloader, so we only need to replace the current address.

$(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x8C00 -o $@.out $^

After cleaning and compiling the source code with the new parameter, let's take a look at the first instruction to see what happened.

00008c00 <start>:
    8c00:    fa                       cli   
    8c01:    fc                       cld 

Wow, it looks like our code will be loaded into another address of memory, though it's not the truth. 
BIOS always load the boot sector into memory at physical addresses 0x7c00, so instructions that depend on a specific address will not work as we expected. Trust and believe me, that's really bad.

Brace yourself for some bad news, the LGDT[1] instruction uses absolute addressing instead. Given this information, the bootloader won't work properly if the link address is wrong.

lgdt    gdtdesc

LGDT takes as argument the address of a structure containing both the base address and limit of the GDT[2].

  .word   0x17                            # sizeof(gdt) - 1
  .long   gdt                             # address gdt

In protected mode, selector values are interpreted as a index into the GDT. So if the GDT wasn't loaded or defined correctly, the processor will raises an exception (triple fault).

[1]: LGDT is used to load the base address and the limit of the GDT. Basically, it turns the GDT on.
[2]: GDT (Global Descriptor Table) works as a lookup table. It's used by the x86 processors which support protected mode.
It contains entries telling the CPU about memory segments. (Borrowed from http://wiki.osdev.org/)


Att, Raphael S.Carvalho

Monday, January 21, 2013

MIT OS course - 6828 (Lab 1)

Follow a list of solved exercises below.
They provide a basic understand of how JOS kernel boots.

Exercise 1.
The first exercise was to familiarize ourselves with the Assembly language.
I found available materials on the 6.828 reference page. Btw, I'm still reading the PCASM book.

Follow the link of the book if you're interested:

Exercise 2.
Use GDB's si (Step Instruction) command to trace into the ROM BIOS for a few more instructions, and try to guess what it might be doing.

; This is the first instruction that BIOS executes when PC starts off.
; It does a far jump. CS: 0xf000 : IP: 0xe05b = 0xfe05b (Segmented address)

{1}: [f000:fff0] 0xffff0:    ljmp   $0xf000,$0xe05b

; Another jump
{2}: [f000:e05b] 0xfe05b:    jmp    0xfc85e

; MOV cr0 content to eax
{3}: [f000:c85e] 0xfc85e:    mov    %cr0,%eax

; Bitwise AND with the content of eax (cr0)
; It will disable two bits (CPU features)

{4}: [f000:c861] 0xfc861:    and    $0x9fffffff,%eax

; MOV eax content to cr0

{5}: [f000:c867] 0xfc867:    mov    %eax,%cr0

; Clean interrupt and direction flag
{6}: [f000:c86a] 0xfc86a:    cli
{7}: [f000:c86b] 0xfc86b:    cld

; MOV 0x8f (1000 1111) to eax
{8}: [f000:c86c] 0xfc86c:    mov    $0x8f,%eax

* [It looks the following commands set up the CMOS Ram Flag]
; 0070    w    CMOS RAM index register port (ISA, EISA)
;         bit 7     = 1  NMI disabled
;                     = 0  NMI enabled
;        bit 6-0      CMOS RAM index (64 bytes, sometimes 128 bytes)
; As I'm seeing, first we need to set the address we want to read from 

; or  write to.
{9}: [f000:c872] 0xfc872:    out    %al,$0x70

; 0071    r/w    CMOS RAM data port (ISA, EISA)
;         any write to 0070 should be followed by an action to 0071
;        or the RTC wil be left in an unknown state.
; Read from or write to the address we set in the previous command.
{10}: [f000:c874] 0xfc874:    in     $0x71,%al

; Compare what we read to zero.
{11}: [f000:c876] 0xfc876:    cmp    $0x0,%al

; Jump to that address if the value is not equals.
{12}: [f000:c878] 0xfc878:    jne    0xfc88d

* [Setting up the segment registers]
; Clean ax value.
{13}: [f000:c87a] 0xfc87a:    xor    %ax,%ax

; Set stack segment to zero.
{14}: [f000:c87c] 0xfc87c:    mov    %ax,%ss

; Set stack pointer to 0x7000
{15}: [f000:c87e] 0xfc87e:    mov    $0x7000,%esp

; (gdb) i r
; edx            0xf4b2c    1002284
{16}: [f000:c884] 0xfc884:    mov    $0xf4b2c,%edx

{17}: [f000:c88a] 0xfc88a:    jmp    0xfc719

; Clean ecx value
{18}: [f000:c719] 0xfc719:    mov    %eax,%ecx

; Clean interrupt and direction flag again
{19}: [f000:c71c] 0xfc71c:    cli 
{20}: [f000:c71d] 0xfc71d:    cld

Btw, there is no need to figure out all the details - just the general idea of what the BIOS is doing first.
The BIOS is also responsible for:
- checking if there is enough memory to keep going;
- setting up an interrupt descriptor table;
- initializing various devices such as VGA display;
- searching for a bootable device.

When the BIOS finds a bootable device it loads the boot loader from the disk to the physical address range 0x7c00-0x7dff,
and then uses a jmp instruction to set the CS:IP to 0000:7c00. Consequently, passing control to the boot loader.
If no bootable disk was found, it shows up a warning message explaining what happened. Probably: "No bootable device was found."
If the disk is bootable, the first sector is called the boot sector.   

Exercise 3. Take a look at the lab tools guide, especially the section on GDB commands. Even if you're familiar with GDB, this includes some esoteric GDB commands that are useful for OS work.

0x7cf1:    cmp    %edi,%ebx ; while (pa < end_pa) {

0x7cf7:    call   0x7c81 ; readsect function address

(gdb) c
0x7d67:    call   *0x10018 ; Entry point of the kernel

- At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?
; Load a descriptor table that contains information for translating segmented addresses.
; Translation of segmented address into physical address happens differently in protected mode.
  lgdt    gdtdesc

; The snippet of code below enables the protected mode flag of the control register, so here is where the switching happens.
  movl    %cr0, %eax
  orl     $CR0_PE_ON, %eax
  movl    %eax, %cr0

- What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?
If everything works fine, then the last instruction would be the following:
0x7d67:    call   *0x10018 ; Entry point of the kernel
This instruction calls the kernel by using the entry point stored in the elf header.
Follow the first instruction of the kernel: 0x10000c:    movw   $0x1234,0x472

- Where is the first instruction of the kernel?
It was answered in the last question: 0x10000c:    movw   $0x1234,0x472

- 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?
First of all, it loads an arbitrary number of sectors, specifically five sectors. By doing that, it assumes that the Elf header of the kernel image will be loaded at all in the memory. Follow the arbitrary address of the Elf header: #define ELFHDR        ((struct Elf *) 0x10000).
After loading that amount of sectors, it check whether the Elf signature is consistent or not, if so the bootloader will load each program header in a pre-defined memory address (All required informations about a program header are stored in its respective structure).
Consequently, the kernel image will be loaded successfully by the bootloader. The bootloader can jump into the kernel code by looking at the entry point stored in the ELF header.

Att, Raphael S.C

Thursday, January 17, 2013

The Diary of an Operating System Developer

Today, I spent most of my time working on the shell exercise provided by MIT operating system course.
Before I get started, I read the chapter 0 of the xv6 book which teaches the major concepts for implementing new features, such as Pipeline, I/O redirection and Background processes.
I didn't need to implement the shell from the ground up because the course I enrolled provides a skeleton shell.
So my work was to read the snippets of code so that I could understand how the shell actually works.
After studying the source code, I realized that the shell uses an incredible algorithm for the parser (through the use of recursivity), and by knowing that, I felt engaged to complete this exercise properly.

I didn't do too much today, however, I started reading LAB1 from MIT and compiled a custom QEMU (provides new features) which will be used massivelly throughout the OS course.
I hope I'll be learning many things while studying it, and as I said few weeks earlier, I'll be sharing nice stuffs as I gain knowledge.

The 2011 MIT OS course provides videos, well, not good image quality, but I have been learning a lot watching them.
Finally, I found out what I want to do until the last day of my life, and I wouldn't face this challenge if I'm not going to do the best in-class homework.

Today, I was also talking with a friend at #GCC (IRC channel hosted by Freenode Server), and the following doubt arises: I didn't understand the meaning of the below sentence.
"It's even smart enough to know that if you tell it to put (x+1) in a register, then if you don't clobber it, and later C code refers to (x+1), and it was able to keep that register free, it will reuse the computation."

After much thinking and throwing my own head against the wall (I'm kidding =]), I got its actual meaning.
When you clobber a register, you're telling that this register may be changed unexpectedly, so GCC can no longer count on the values you loaded into the clobbered registers.
Also, it means it's smart enough to know that if you load an expression into a register you should never clobber it unless it's really needed.
For example, if the code refers to that expression later the GCC would optimize it by avoiding another processing of the same expression.

That's all for this post. I hope you liked it.
Regards, Raphael S.Carvalho

Tuesday, January 8, 2013

Hard and Exciting Challenge

Dear readers,

I'm going to face the hardest challenge in my career as a computer scientist. I'll write my own Operating System, and as the time goes on, I'll be posting everything about this wonderful in-home project.
Its purpose is to teach me how the x86 architecture actually works, besides improving my programming and other related skills.
In the past few months, I was learning OS development through several articles provided by actual developers. Indeed, I got a depth knowledge, though there are many things waiting to be learned.
I'm feeling engaged and excited to get started, and I hope you'll be an active reader of my blog from now on.

Q: You may be asking yourself: What am I going to gain by reading your blog massively?
A: I'll put all of my effort into the following task: Write both useful and detailed tutorials/articles as much as possible.

That's all for now. You know, we can't lose our time by talking about non-related subject to each other.

Raphael S. Carvalho

[PT-BR] Introduction to Linux Processes.

Uma das fundamentais abstrações em sistemas operacionais Unix-like.

Esse artigo é destinado àqueles que gostariam de obter um simples entendimento do assunto, ou àqueles que desejam aprender por simples curiosidade.
Neste artigo, quando eu falar Linux, eu estarei referindo ao Linux Kernel. Estritamente dizendo, o termo Linux faz referência apenas ao Kernel.

- Definição
O processo é um programa (código objeto armazenado em alguma mídia) no meio da execução.

É interessante mencionar que os processos são mais que códigos de um programa em execução (também conhecido como text section).
Além do código, os processos também possuem vários recursos que possibilita a transparência e eficácia do gerenciamento realizado pelo Kernel.

Alguns deles são:
o Arquivos abertos pelo processo (Open Files).
o Sinais Pendentes (Pending Signals).
o Estado do processo (Processor state).
o Internal Kernel Data.
o Espaço de memória (Com um ou mais mapeamentos).
o Um ou mais threads de execução.
o Data section contendo variáveis globais.

Definitivamente, processos podem ser definidos como o resultado final do código de programa em execução.

- Threads de execução
Threads de execução (frequentemente referenciada como Threads), são objetos de atividade dentro de um processo. Cada thread contém um exclusivo program counter (registrador), stack, e um conjunto de registradores do processador (virtuais).

É muito interessante dizer que o Linux tem uma única implementação de threads. O Linux não diferencia entre processos e threads. Para ele, as threads são apenas um tipo especial de processo.

- Virtualizações

Os sistemas operacionais modernos fornecem duas virtualizações:
o processador virtualizado e a memória virtual.

O processador virtual fornece ao processo a impressão que ele sozinho monopoliza o sistema. Na realidade, ele irá compartilhar o processador físico com um número mais elevado de processos.

Memória virtual segue o mesmo conceito, ela deixa o processo alocar e gerenciar a memória como se o processo fosse o único utilizador da memória do sistema (física).

Interessantemente, vale a pena notar que thread compartilha a abstração de memória virtual, porém cada uma possui seu próprio processador virtualizado.

- Note que...
Um programa não é um processo, um processo é um programa em execução e seus respectivos recursos (tais recursos foram abordados acima).
De fato, dois ou mais processos podem existir executando o mesmo programa. Processos também podem compartilhar recursos entre si (arquivos abertos, espaço de memória, etc...).

- Criação de processos
Um processo inicia sua vida quando, não surpresamente, ele é criado.
O Linux faz isso por meio da fork() system call (chamadas de sistema).

Essa chamada de sistema cria um novo processo duplicando o existente, ou seja, o caller(o chamador).
O processo que chama fork() é o parent(pai), enquanto o novo processo é o child(filho).
Dessa forma, o processo parent retoma a execução e o filho inicia a execução apartir do mesmo lugar (onde o fork retorna).

É muito interessante saber que a chamada de sistema fork() recebe dois valores do kernel, um é destinado ao pai e outro ao recém-nascido filho.

Término de um processo
Um programa é finalizado via chamada de sistema exit().
Além de terminar um processo, ela libera todos os seus recursos.

Um processo pai pode indagar a respeito do status de um processo filho finalizado via chamada de sistema wait(), a qual ativa um processo para esperar pelo término de um processo específico.
Quando tal processo é finalizado, ele é colocado em um estado especial chamado estado zombie. Eles representam processos finalizados, a única forma de removê-los é o processo pai chamar wait().

Note: Outro nome para um processo é 'task'. Internamente, o Linux refere aos processos dessa forma.

Eu tentei abordar de forma simples os conceitos necessários para seguirmos em frente. Abstraindo tais informações você será capaz de acompanhar o próximo artigo. Estaremos utilizando a árvore do Linux e criando módulos para obter um conhecimento profundo desse assunto.


Raphael S.Carvalho