Sunday, March 18, 2012

[Preface] A Hope That My Crude Remarks May Draw Forth By Abler People

    By these articles and courses, I want to have much more discussion and make much more friends.
Share passion and fun about OS between you and me.
Dear Friends:
    Hello. Each MIT 6.828 article is my transcripts about problem solving and some other interesting questions, After Lesson. Under the pressure of time and work, some questions have been answered by me, some not. This place is open for all masters and enthusiasts. Any questions or issues about OS and related domains are welcomed. Welcome!.

  Hope that we can share delight of the journey.

Indent - My Coding Style

Coding Style不統一,是在跟人寫code中最大的不耐之一。

套一句 Knuth的名言
"A person does not really understand something until after teaching it to a computer"
在下就把自已習慣的coding style 極大部份是採用GNU的風格。
用indent 去令電腦懂 我要排什麼樣的style,協作的一方 也清楚多了。
也真的不習慣用已套裝好的指令 還不知道各參數是什麼意思…。

#man indent


My C coding style based on the GNU style.
 indent -nbad -bap -nbc -bbo -bl -bli0 -bls -ncdb -ncdw 
           -nce -cp1 -cs -di1 -ndj -nfc1 -nfca -hnl -i4 -ip5 
            -lp -pcs -nprs -psl -saf -sai -saw -nsc -nsob -blf
            -nut -ts4
-nbad: 宣告變數後無空行
-bap: 強迫在function body前必有空行
-nbc: each comma(逗行)前必換行
-bbo: 強迫在&& ||前換行
-bl:   braces-{ 需在if(...)換到下一行
-blin: { 需在if(...) 換行時,縮入多少空白
-bls: 於struct name及{ 置入newline
-blf: 需在function def及{置入newline
-ncdb: Don't put comment delimeters on the blank line
-ncdw: do{...} while 其}  while 之間會置入newline
-nce: } 及 else間會置入newline
-cp1: Put comments to the right of #else and #endif statements in column n
-cs: 於Type cast opertator及變數間會有空白
-di1: 於declaration時的type 及 Identitier中間會有1個空白(換行時亦會有1空白)
-ndj: 對declarations 後的comments 等同於其他位於statements後的comment
-hnl: prefer use the input file to break the long line
-i4: indentation level to n spaces.
-ip5: for old coding style其引數宣告需內縮5格
-lp: 若(...)有斷行 則 對齊 left parenthesis
-pcs: 在function name被call時,其name及 ( 之間不會有空白
-nprs: 於parentheses(括號)後無空白
-psl: 令procedure的type 及 name 為上下行
-saf: 令for及括號間有一個空白
-sai: 令if及括號間有一個空白
-saw: 令while及括號間有一個空白 
-nsc: Do not put the '*' character at the left of comments
-nsob: Do'nt swallow optional blank lines
-nut: no tab
-ts4: 1 tab 為4spaces

Saturday, March 17, 2012

Lab1-Part C-2/2: The Kernel (Stack)


  •  Something needed to know
    • Understand how did kernel perform its stack creation. 
  • Discussion:
    1. Determine where the kernel initializes its stack
      • At kern/entry.S
        • # Set the stack pointer
        • movl    $(bootstacktop),%esp
        • f0100034:       bc 00 00 11 f0          mov    $0xf0110000,%esp
    2. Where in memory its stack is located
      • as above: 0xf0110000
    3. How does the kernel reserve space for its stack
      • .space KSTKSIZE
        • 8*4096 bytes = 8192 stack frames each 4 bytes
    4. At which "end" of this reserved area is the stack pointer initialized to point to?
      • bootstack
    5. push data from bootstacktop to bootstack (each one put is -4)

  • Something needed to know
    • To be familiar with x86 calling convention.
      • Each EBP pused into stack
        • the base pointer into the stack used by that function: 
      • Each EIP pushed into stack
        • return instruction. : the instruction address to which control will return when the function returns.
    • Set breakpoint at test_backtrace 
      1. Examine what happens each time it gets called after the kernel starts
      2. How many 32-bit words does each recursive nesting level of test_backtrace push on the stack what are those words?
        • EIP/ARGS/EBP
        • registers waited to be used
          • push its value in, before return, just pop out them.
  •  Recursive Calling Stack
    • stack as linked list array
      • From current EIP
      • Old EIPs by finding EBP+4 pushed by gcc calling convention 
    • PIC
  • Question
    • read_eip
      • Doesn't work if inlined
      • Putting at the end of the file seems to prevent inlining.


  • Something needed to know
    • Based on Exercise10
    • Pointer usage
      • int*p
        • (int)p + 1  -   1base
        • (int)(p + 1) - 4base
  • GitHub Link
  • Something needed to know
    • Based on Exercise11
    • printf(%.*) usage
    • Stab format
    •  Trace kern/kdebug.c
  • GitHub Link:


Enjoy OS travel :)

Lab1-Part C -1/2: The Kernel (Taste of MM/Output)

[Preface] A Hope That My Crude Remarks May Draw Forth By Abler People

  • Something needed to know.
    • Examine before and after Paging Enable.
      1. brack at  movl %eas,%cr0 to check 0x00100000/0xf0100000
        • x/20h 0x100000
          0x100000:       0xb002  0x1bad  0x0000  0x0000  0x4ffe  0xe452  0xc766  0x72050
          x100010:       0x0004  0x3400  0xb812  0x0000  0x0011  0x220f  0x0fd8  0xc020
          0x100020:       0x010d  0x0100  0x0f80  0xc022
        • x/20h 0xf0100000
          0xf0100000:     0xffff  0xffff  0xffff  0xffff  0xffff  0xffff  0xffff  0xffff
          0xf0100010:     0xffff  0xffff  0xffff  0xffff  0xffff  0xffff  0xffff  0xffff
          0xf0100020:     0xffff  0xffff  0xffff  0xffff
      2. si then check again.
        • x/20h 0x100000
          0x100000:       0xb002  0x1bad  0x0000  0x0000  0x4ffe  0xe452  0xc766  0x7205
          0x100010:       0x0004  0x3400  0xb812  0x0000  0x0011  0x220f  0x0fd8  0xc020
          0x100020:       0x010d  0x0100  0x0f80  0xc022
        • x/20h 0xf0100000
          0x100000:       0xb002  0x1bad  0x0000  0x0000  0x4ffe  0xe452  0xc766  0x7205
          0x100010:       0x0004  0x3400  0xb812  0x0000  0x0011  0x220f  0x0fd8  0xc020
          0x100020:       0x010d  0x0100  0x0f80  0xc022  
      3. They are mapped.
    • Geuss where would be happaned, if mapping weren't in place by commenting out movl %eas,%cr0.
      • mov     $relocated, %eax
        jmp     *%eax #<---Here
      • Why?
        1. $relocate is addressed as 0xf0100025(by VMA:0xf0100000), but commenting out the line,enabling protected mode. It resulted in mapping failed.
          • No protected mode no mapping from 0xf010000c to 0x10000c(phy address) at view of entry address.
        2. By the way, above code could be executed because the bootloader directly move/copy/jmp in real address. (know details by the following discussion)
  • Discussion:
    • How did kernel execute its start address at 0x10000c?
      1. BIOS read disk's #0 sector(boot sector) and load them into ram:0x7C00 to execute
      2. bootload read disk's #1 sector and load them into ram:0x100000 to execute
        • dd command put kernel into #1 sector.
      3. bootloader jump to kernel's start entry address by ((void (*)(void)) (ELFHDR->e_entry))();
  • After Lesson:
    • What did kernel.asm do from 0x100000 to 0x10000c
      • .globl entry
      • entry:
      •         movw    $0x1234,0x472                   # warm boot                                         f0100000:       02 b0 ad 1b 00 00       add    0x1bad(%eax),%dh
      • f0100006:       00 00                   add    %al,(%eax)
      • f0100008:       fe 4f 52                decb   0x52(%edi)                                           f010000b:       e4 66                   in     $0x66,%al
      • f010000c <entry>:

    • Something needed to kow
      • Trace code to understand the following code's relateionship.
        • kern/printf.c
          • kernel internal API function 
        • lib/printfmt.c
          • Utility to format output used by Kernel/User mode
        • kern/console.c
          • Driver
      • Accomplish to print "%o" for octal.
        • 209                         num = getuint(&ap, lflag);
        • 210                         base = 8;
        • 211                         goto number;
    • Discussion:
      1. Interface between console.c and printf.c
        • Exported by inc/stdio.h
          • cputchar by printf.c
          • getchar;by readline.c
          • iscons ;by readline.c
        • Exported by inc/console.h
          • cons_init; by init.c
          • cons_getc;
          • kbd_intr
          • serial_intr
      2.  Roll up One Empty line.
      3. check arguments
        • cprintf
          • fmt=0xf0101a69 "x:%d,y:%d,z:%d\n"
          • ap=0xf010ffe4 ("\001")
          •  x/4w 0xf010ffe0
            0xf010ffe0:     0xf0101a69      0x00000001      0x00000003      0x00000004
          • push order: arg4(0x0000004) arg3 arg2 arg1(0xf0101a69)
            • pop order is the reverse.
        • cons_putc/va_arg/vcprintf
          1. order: vcprintf->va_arg->cons_putc
          2. vcprintf:
            • fmt=0xf0101a69 "x:%d,y:%d,z:%d\n"
            • ap=0xf010ffe4 ("\001"
          3. va_arg:
            • the next stack address to print
          4. cons_putc: 
            • the int type variable to be printed on Screen.
      4.  type translation and ASCII table
        • Output "He110 World"
        • 57616 (Decimal) = E110 (Hex)
        • 0x00646c72 
          • 0x72 :'r'
          • 0x6c :'l'
          • 0x64 :'d'
          • 0x00 :'\0'
        • Note: little endian printed.
      5.  cprintf("x=%d y=%d",3)
        •  y=%d in va_arg, it gets the next stack frame's value.
      6. reverse order.
      7. After Lesson:
        • Why is printfmt.c located in the separate lib directory?
      8. GitHub Link

      Lab1-Part B: Boot loader & Bootstrap

      [Preface] A Hope That My Crude Remarks May Draw Forth By Abler People
      Boot loader: 1st stage, don't need to depend on kernel
      Bootstrap: 2nd stage, related about kernel image not part of the kernel code, do kernel uncompressing ...etc

      • Something needed to know
        • Addressing methodology and its adv/disadv in real-mode/16-bit protected mode/32-bit protected mode
      • Trace boot loader:
      1. .globl start : 為0x7c00
      2. 16bit ASM section is on
      3. cli ; cld;
      4. Set %ds,%es,%ss to 0
      5. %cs is 0 set by BIOS  CS:IP = 0000:7c00
      6. Enable A20
      7. lgdt gdtdesc //load global descriptor table
      8. set %cr0 to Enable Protected mode
      9. 16 bit ASM is off
      10.  ljmp   $0xb866,$0x87c32
        • CS is replaced as #8 slot at gdt table (PROT_MODE_CSEG)and  plus 0xb866 base.
        • immed is 0x87c32
      11.  set %ds,%es,%fs,%gs,%ss as #10 at gdt table(PROT_MODE_DSEG)
      12.  set esp as 0x7c00 to form stack base address ; stack address: [ss:esp]
      13. call bootmain(void)
      14. call readseg((uint32_t) ELFHDR, SECTSIZE*8, 0); read in ELF headers
      15. call readseg to read in every program header.
      16. jump to kernel.
        • ((void (*)(void)) (ELFHDR->e_entry))();
      17. #
      • Trace readseg
        1. end_pa = pa + memsize
        2.  round down it-physical address for loading program into ram by pa&= 0x(FFFFFE00)  // ~(SECTSIZE-1)
        3. Translate offset into Sector number
          • Note: The offset must start from #1, #0 is the boot sec  
        4. Read enough data by pa and sector number  
          • Because paging is not enable, just direct map into memory. by $PROT_MODE_DSEG, %ax
        5. #
      • Trace readsect
        • do IDE HardDisk read in data.
      • Reply for its questions
        1. At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?
          • before long jump, and set cr0's 1st bit to 1
        2. What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?
          1. Last instruction in boot loader
            • In "C": ((void (*)(void)) (ELFHDR->e_entry))();
            • In "GAS": call   *0x10018  to jmp at kernel's entry point 0x10000c
              • 0x10018 is the byte address of at ELFHDR's  #24 byte.
          2. First Instruction in Kernel
            • movw    $0x1234,0x472   //warm boot
        3. Where is the first instruction of the kernel?
          • At kern/entry.S  . .globl entry
          • 0x10000c
        4. 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?
          1. 由ELF info 穿針引線。
            • #man elf
            • readelf -l obj/kern/kernel
            • From its ELF header 
              • get Program header's start offset: e_phoff
              • get how many are the program headers: e_phnum
          2. 由program header 
            • readelf -l  obj/kern/kernel
          • From program headers to do readseg
            • ph->p_pa : the address for prgram segment loaded into ram
              • On systems for which physical addressing is relevant, this member is  reserved for  the  segment's  physical  address.  Under BSD this member is not used and must be zero.
            • ph->p_memsz: 
              • This  member holds the number of bytes in the memory image of the segment.  It may be zero.
            • ph->p_offset
              •  This member holds the offset from the beginning of the file at which the first byte of the segment resides.
      • Discussion
        • Calling conventions gcc at  i386
          • Saved by Caller
            • eax : contain return value
            • ecx: possibly trashed
            • edx: possibly trashed
          • Saved by Callee
            • ebp
            • ebx
            • esi
            • edi
            • must be saved before call
          • Sample
            1. In bootmain, why did it need following instructions?
              • push   %ebp  #x86 gcc calling convention
              • mov    %esp,%ebp  #x86 gcc calling convention
              • push   %edi
              • push   %ebx
            2. In readseg, ...
              • push   %ebp  #x86 gcc calling convention
              • mov    %esp,%ebp  #x86 gcc calling convention
              • push   %edi
      • After Lesson:
      1. Drivers. How did it execute IDE device I/O
        • Ans: Not Yet.
      2. How to decide program headers?
          •   LOAD //PT_LOAD
          •   LOAD //PT_LOAD
          •   GNU_STACK .//PT_GNU_SACK
        • Ans: By session's default orgnization.
      3. In program header, 
        1. Why is memsz and filesz? Loading it totally is not better?
        2. Why is GNU_Stack's Memsize  zero?
        • Program Headers:
        •   Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
        •   LOAD           0x001000 0xf0100000 0x00100000 0x075b9 0x075b9 R E 0x1000
        •   LOAD           0x009000 0xf0108000 0x00108000 0x0a300 0x0a960 RW  0x1000
        •   GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4
      4. ljmp: how did it decide to do TSS  related stuff
        • Guess: by segment descriptor's field.

        • Just Read The C Programming Language K&R chap5.
        • Address Arithmetic. The Byte added to l-value is by its type.
          • c = (int *) ((char *) c + 1); //added by 1
          • b = (int *) a + 1;//added by 4

        • Something needed to know
          • Change boo/Makefrag的-Ttext : 0x7c000 for link address
          • VMA: Link address. Expected address for it to rum.
          • LMA: Load address. Expected address for it to load into memory.
          • objdump -h:Display the contents of the section headers -See VMA/LMA.
          • objdump -f: Display the contents of the section headers -See entry_point for execution start address
        • objdump -f obj/boot/boot.out
          •  start address 0x00007c00
        • objdump -h obj/boot/boot.out
          • VMA:0x00007c00
          • LMA:0x00007c00
        • Modify boot/Makefrag -Ttext to 0x8C00
          • Error happaned at  ljmp    $PROT_MODE_CSEG, $protcseg @ boot/boot.S
          • .Ttext .text/.org tell assembler its start address 0x8C00 , but BIOS load it into 0x7C00 that .gdt related data follow 0x7C00, at 0x7c64.  When executing ljmp error happened instruction, it will use 0x8c64 by .Ttext claimed, but in reality it is loaded at 0x7C64 by BIOS.
        • After Lesson:
          • Modify -Ttext0x7900. How and Why did it change VMA/LAM not just only entry(.start)?  
            • Ans: Not Yet.
          • How did CPU's chip view reject to execute ljmp instruction if gdt field was something wrong?
            • Ans: Not Yet.

        • Something needed to know
          • Set 1st break point at 0x7c00
            • examine 0x100000
          • Set 2nd breakpoint at 0x10000c
            • examine  0x100000
          • Addresses for obj/kern/kernel
            • VMA:0xf0100000
            • LMA: 0x00100000
            • Entry: 0x10000c
        •  Result
          • BIOS enter Bootloader
            • x/8h 0x100000:       0x0000  0x0000  0x0000  0x0000  0x0000  0x0000  0x0000  0x0000
          • Bootloader enter OS Kernel
            • x/8h 0x100000:       0xb002  0x1bad  0x0000  0x0000  0x4ffe  0xe452  0xc766  0x7205
            • x8h 0x10000c:       0xc766  0x7205  0x0004  0x3400  0xb812  0x0000  0x0011  0x220f
        • Discussion: Why are they different?
          • By LMA's value
          • bootloader load kernel by claim form program header of kernel's elf info.
            • readelf -l obj/kern/kernel
              • Elf file type is EXEC (Executable file)
                Entry point 0x10000c

        Lab1-Part A: Boot a PC (BIOS Run)

        Just read inline assembly
        Ref Link Linux assemblers: A comparison of GAS and NASM

        Just run GDB for remote debugging by the given script. See the GAS code if you can.

        Boot ASM code explanation.
        1. [f000:fff0] 0xffff0:    ljmp   $0xf000,$0xe05b  //For Real-Mode's ljmp
        2. jmp 0xfc85e
        3. %cr0 = %cr0  0x9ffffff  0 For  follows
          30CDCache disableGlobally enables/disable the memory cache
          29NWNot-write throughGlobally enables/disable write-back caching
        4. cli
        5. cld
        6. set port 0x70 = 0x8f
          •  to enable NMI- Non Maskable Interrupt
        7. port 0x71 
          • RTC是否為0 此例中為0 故續往下exec
        8. set %ss =0  and %esp = 0x7000 
          • to form SS:[ESP] stack segment (PS: Code Segment: CS:[EIP])
        9. mov $0xf4b2c, %edx 
          • //for  DMA controller setup section.
        10. jmp 0xfc719 
        11. enable 0x92 ; System devices A20 line. fast A20
        12. 0xfc726: in     $0x71,%al
          0xfc728: in     $0x92,%al
          0xfc72a: or     $0x2,%al
          0xfc72c: out    %al,$0x92
          for (11.)
        13. lidtw  %cs:-0x31cc    
          • set IDT
        14. lgdtw  %cs:-0x3188 
          •  set GDT
        15. enable %Cr0's 1st bit. 
          • Enable Protected Mode
        16. 0xfc744:    ljmpl  $0x8,$0xfc74c 
          • //For Protected Mode's ljmp, 換code segment 並跳至其code segment 下的0xfc74c
        17. set ds es ss fs gs 為0x10 from gdt
        18. jmp to *%edx  (look item.9) 
        19. out 0 to slave dma controller- port: 0xd
        20. out 0 to master dma controller-port 0xda/0xd6/0xd4
        21. jmp to 0x7c00
          •  The address in ram to load the boot sector into.
        22. #
        After Lesson:
        Question1: Why did not I find  /boot/boot.S, /boot/main.c by GDB: info sources ; Its symbol
                           readelf -a obj/boot/main.o
        Ans: That belongs to the boot loader placed on the #1 sector at disk. and load it into 0x7C00 to execute.

        Question2: Where is the Code's symbol?
        Ans: Symbol is in obj/boot/boot.out.$file obj/boot/boot.out

        Question3: How to Assume It? when ljmp called show the following msg.
                          "The target architecture is assumed to be i386"
        Ans: Not Yet.

        Question4: In BIOS ROM code, when to set %cs value, so as to use for (item13/14)
         Ans: %CS為0xf0000 因為是BIOS section.

        Question5: How/What did MIT patch the QEMU?
        Ans: Not Yet.

        Question6: Why did BIOS need to switch to Protected Mode?
        Ans: It wants to use the Protected Mode's functionality .
                Like ljmp mem48 :In Real Address Mode or Virtual 8086 mode, the long pointer provides 16 bits for the CS register and 16 or 32 bits for the EIP register
                Ref Link: bootloader - switching processor to protected mode By Stackoverflow
        1. cr0
          BitNameFull NameDescription
          31PGPagingIf 1, enable paging and use the CR3 register, else disable paging
          30CDCache disableGlobally enables/disable the memory cache
          29NWNot-write throughGlobally enables/disable write-back caching
          18AMAlignment maskAlignment check enabled if AM set, AC flag (in EFLAGS register) set, and privilege level is 3
          16WPWrite protectDetermines whether the CPU can write to pages marked read-only
          5NENumeric errorEnable internal x87 floating point error reporting when set, else enables PC style x87 error detection
          4ETExtension typeOn the 386, it allowed to specify whether the external math coprocessor was an 80287 or 80387
          3TSTask switchedAllows saving x87 task context only after x87 instruction used after task switch
          2EMEmulationIf set, no x87 floating point unit present, if clear, x87 FPU present
          1MPMonitor co-processorControls interaction of WAIT/FWAIT instructions with TS flag in CR0
          0PEProtected Mode EnableIf 1, system is in protected mode, else system is in real mode