Notes on the Cute Kernel

TOC:

----

(1)  On Intel Documents

(2)  On Data Alignment

(3)  On little-endian byte ordering

(4)  On Real Mode

(5)  On accessing fixed disk drivers (hard-disks)

(6)  On x86 jumps

(7)  On referencing global symbols

(8)  The 8259A Programmable Interrupt Controller

(9)  On x86 SMP initialization sequence

(10) On linkers 'relocation error's

(11) When %RIP-relativeness goes wrong

(12) Testing libc()-like kernel code

(13) On SMP Memory ordering models

(14) On the C 'volatile' type qualifier

(15) On the vaguely documented x86 16-bit protected mode

(16) Using light debugging techniques

(17) Musings on Memory Allocation

(18) On Virtual Memory

(19) On Partitionting the 64-bit kernel address space

(20) Debugging -O3 triggered problems

(21) The Zone!

(22) Debugging periodic timers using statistical data

(23) The Naughty Multiply

On Intel Documents:

-------------------

* Although the newer intel documents are much more sexy and detailed, the

  original i386 one describes the concepts in a much more bottom-up,

  undergraduate-book like, no forward-references way.

* Somehow the new intel documents beginning from the 1997 i686 document

  assumes some x86 familarity that wasn't obviously assumed in the original

  document.

* For an example, the 'alignment' topic is throughly explained in

  the i386 manual, what is it and why is it important to performance,

  and how the processor act if given a misaligned address, *before* ever

  using the words '16bit-aligned' and '32bit-aligned'.

  The new intel documents assume you know subtle topics as above and

  talks about critical issues related to their understandings freely

  *before* they become throughly discussed. Only at i686 chapter 5

  alignment is throughly described although several critical alignment

  related topics have already been discussed.

* Case 2: on why we should disable interrupts while switching to protected

  mode?

  New Intel document: Software must guarantee that no exceptions or interrupts

  are generated during the mode switching operation.

  Original 386 document: ``The IDTR may be loaded in either real-address or

  protected mode. However, the format of the interrupt table for protected mode

  is different than that for real-address mode. It is not possible to change to

  protected mode and change interrupt table formats at the same time; therefore,

  it is inevitable that, if IDTR selects an interrupt table, it will have the

  wrong format at some time. An interrupt or exception that occurs at this time

  will have unpredictable results. To avoid this unpredictability, interrupts

  should remain disabled until interrupt handlers are in place and a valid IDT

  has been created in protected mode.''

* Case 3: on why should we long jump after switching to protected mode?

  New intel document: ``The JMP or CALL instruction immediately after the MOV

  CR0 instruction changes the flow of execution and serializes the processor.''

  Original 386 document: ``Immediately after setting the PE flag, the

  initialization code must flush the processor's instruction prefetch queue by

  executing a JMP instruction. The 80386 fetches and decodes instructions and

  addresses before they are used; however, after a change into protected mode,

  the prefetched instruction information (which pertains to real-address mode)

  is no longer valid. A JMP forces the processor to discard the invalid

  information.''

  This is a recurring pattern.

* What's IA-32e in new Intel documents?

  Intel has really messed up the namings of their 64bit processors. The

  most logical choice I think was IA-64, but unfortunately that was taken

  by the big flop in processor's history: the Itanium. When Intel waked

  up and created their first amd64 compatible processor, they named it EMT64.

  Now intel in its new official documents call the x86_64 architecture

  "intel 64" and call those processor's 64bit mode IA-32e.

On Data Alignment:

------------------

* Note: In x86 speak, word = 2bytes/16bits, double word = 4bytes/32bits

* Each byte within a word has its own address, and the smaller of the

  addresses represent the address of the whole word.

* Each byte within the double word has its own address. The smallest of the byte

  addresses is the address of the double word.

* ``Note that words need not be aligned at even-numbered addresses and

  doublewords need not be aligned at addresses evenly divisible by four.

  This allows maximum flexibility in data structures (e.g., records containing

  mixed byte, word, and doubleword items) and efficiency in memory

  utilization.

  ** When used in a configuration with a 32-bit bus, actual transfers of

  data between processor and memory take place in units of doublewords (4bytes)

  beginning at addresses evenly divisible by four **

  However, the processor converts requests for misaligned words or doublewords

  into the appropriate sequences of requests acceptable to the memory interface.

  ** Such misaligned data transfers reduce performance by requiring extra memory

  cycles. For maximum performance, data structures (including stacks) should

  be designed in such a way that, whenever possible, word operands are aligned

  at even addresses and doubleword operands are aligned at addresses evenly

  divisible by four. **

  Due to instruction prefetching and queuing within the CPU, there is no

  requirement for instructions to be aligned on word or doubleword boundaries.

  However, a slight increase in speed results if the target addresses of control

  transfers are evenly divisible by four.''

  	    	       		    	   -- Intel 386 Reference Manual

* ``The reason for this is that the processor requires two memory accesses to

  make an unaligned memory access; whereas, aligned accesses require only one

  memory access. A word or doubleword operand that crosses a 4-byte boundary

  or a quadword operand that crosses an 8-byte boundary is considered unaligned

  and requires two separate memory bus cycles to access it; a word that starts

  on an odd address but does not cross a word boundary is considered aligned

  and can still be accessed in one bus cycle.''

      	  	   	       	       	   -- Intel 686 Reference Manual

* x86 4KB page aligned addresses:

  Decimal:

  10 ^ 0 = 1

  10 ^ 1 = 10

  10 ^ 2 = 100

  10 ^ 3 = 1000

  ...

  Binary:

  2  ^ 0 = 1

  2  ^ 1 = 10

  2  ^ 2 = 100

  ...

  2  ^ 10 = 10000000000 = 1024 = 1KB

  2  ^ 12 = 1000000000000 = 2^2 * 1KB = 4KB (x86 Page size/aligned-address)

  ...

* Common alignments offsets:

  1byte alignment = 2 ^ 0  -- any x86 RAM address

  2byte alignment = 2 ^ 1 (0b10) -- 16bit aligned address

  = any address divisable by 2

  = 0x0, 0x2, 0x4, 0x6, 0x8, ..., 0xa, 0xc, 0xe, 0x10, 0x12, ...

  4byte alignment = 2 ^ 2 (0b100) -- 32bit aligned address

  = any address divisable by 4

  = 0x0, 0x4, 0x8, 0xc, 0x10, 0x14, 0x18, 0x1c, 0x20, ...

  8byte alignment = 2 ^ 3 (0b1000) - GDT cell index/size

  = any address divisable by 8

  = 0x0, 0x8, 0x10, 0x18, 0x20, ...

     |    |    |

   null  %cs  %ds

  16byte alignment = 2 ^ 4 (0b10000) - GDT table recommended alignment

  = any address divisable by 16

  = 0x0, 0x10, 0x20, 0x30, 0x40, ..., 0xf0, 0x100, 0x110, 0x120, ...

* Useful numbers:

  0x100   = 256 bytes

  0x200   = 512 bytes  (bootsector size, number of entries in PML{4, 3, 2} tables)

  0x400   = 1KB

  0x1000  = 4KB        (x86 normal page size/alignment)

  0x8000  = 32KB

  0xffff  = 64KB -1    (max offset for a real-mode segment)

  0x10000 = 64KB

  0x80000 = 512KB      (our initial kernel size!)

On little-endian byte ordering:

-------------------------------

* From AMD64 documents:

  "The x86 and AMD64 architectures address memory using little-endian

  byte-ordering. Multibyte values are stored with their least-significant byte at

  the lowest byte address, and they are illustrated with their least significant

  byte at the right side. Strings are illustrated in reverse order, because the

  addresses of their bytes increase from right to left."

  Value =

  BYTE-7  BYTE-6  BYTE-5  BYTE-4  BYTE-3  BYTE-2  BYTE-1  BYTE-0

  Actual Mem Layout:

  BYTE-0  BYTE-1  BYTE-2  BYTE-3  BYTE-4  BYTE-5  BYTE-6  BYTE-7

  ^

  |--- Address start here

  For illustrative purposes only - not actual mem layout:

  GREATEST                 DATA STRUCTURE

  ADDRESS

   31              23              15              7             0 <--BIT

  +---------------+---------------+---------------+---------------+   OFFSET

  |    BYTE 7     |    BYTE 6     |    BYTE 5     |    BYTE 4     |4

  |---------------+---------------+---------------+---------------|  SMALLEST

  |    BYTE 3          BYTE 2          BYTE 1          BYTE 0     |0 ADDRESS

  +---------------+---------------+---------------+---------------+^

                                                                   |

                                             Address start here ---|

* Classical little-endian ordering:

  .long  0x00cf9200 = 00 92 CF 00

                      ^

                      |--- Address start

  =

  +---------------+---------------+---------------+---------------+

  |      00       |      CF       |      92       |       00      |

  +---------------+---------------+---------------+---------------+^

                                                  Address start ---|

* GAS concatenation:

  .long  0x00cf9200, 0x0000ffff  != .quad 0x00cf92000000ffff

  .long  0x00cf9200, 0x0000ffff

  =

  .long  0x00cf9200

  .long  0x0000ffff

  =

  .quad  0x0000ffff00cf9200

  =

  (actual layout in memory)

  00 92 CF 00  FF FF 00 00

  ^

  |--- Address start

  =

  (for illustrative purposes only - _NOT_ actual mem layout)

  +---------------+---------------+---------------+---------------+

  |      00       |      00       |      FF       |       FF      |

  |---------------+---------------+---------------+---------------|

  |      00       |      CF       |      92       |       00      |

  +---------------+---------------+---------------+---------------+^

                                                  Address start ---|

  BUT:

  .long  0x0000ffff

  .long  0x00cf9200

  =

  .quad  0x00cf92000000ffff

  =

  (for illustrative purposes only - _NOT_ actual mem layout)

  +---------------+---------------+---------------+---------------+

  |      00       |      CF       |       92      |      00       |4

  |---------------+---------------+---------------+---------------|

  |      00       |      00       |       FF      |      FF       |

  +---------------+---------------+---------------+---------------+^

                                                  Address start ---|

  =

  (actual layout in memory)

  FF FF 00 00  00 92 CF 00

  ^

  |--- Address start

* So:

  test.S:                           |  print.c:

                                    |

  .global test                      |  #include <stdint.h>

  test:                             |  extern uint64_t test;

        .quad 0x00cf92000000ffff    |  int main(void) { printf("test = 0x%x\n", test); }

  output: test = 0x0000ffff

  as the 64-bit value is presented as: (address-start) FF FF 00 00 00 92 ... (address-end)

* The String "WXYZ" is represented in memory as:

  'W' 'X' 'Y' 'Z'

  ^

  |--Address start

  And in the usual memory diagrams:

  +---------------+---------------+---------------+---------------+

  |      'Z'      |      'Y'      |      'X'      |      'W'      |

  +---------------+---------------+---------------+---------------+^

                                                  Address start ---|

On Real Mode:

-------------

* To achieve maximum backward compatibility, x86 processors starts in the 16bit

  8086-compatible real-mode. The 8086 had a complete 16-bit architecture - 16-bit

  internal registers, 16-bit data bus, and a *20-bit* external address bus (1 MB

  of physical memory).

  Because the 8086 processor had 16-bit index registers and memory pointers,

  it can effectively address *only* up to 64 KB of memory, which wasn't acceptable

  even by that time. 

* So, to address the memory beyond 64 KB (the remaining 20bit 1MB address space)

  with 16bit registers, Intel created a `segmented' memory addressing scheme.

  We want to access 20bit address space, namely 0xfffff at max. The 8086

  processor's registers are only 16bit, namely a max value of 0xffff. To solve

  this issue, the 8086 processor used *two* registers to address physical memory.

  The two registers are a segment described as a base address, and an offset within

  that segment.

  The goal: addressing up to the max 20bit value; 0xfffff:

  f 0 0 0 0     <-- 16bit value (segment base address) hex left shifted once to

      	  	    address the 4 highest order bits in the goal.

            +   <-- A simple adding operation

    f f f f	<-- 16bit value, max offset we can address

    -------

  f f f f f	<-- The goal (max 20bit value we can address)

  So physical memory in the 8086 is accessed through a `segment:offset' scheme

  where physical address = (segment * 16) + offset

* Note that the above segment model is very primitive that there are really no

  real `segments' identified by the processor. A *physical* 'segment' is

  basically just a 16-bit aligned physical address address with an offset

  `limit' of 64K enforced by the processor registers limit.

  Example:

  a000:0010 = a010:0000         /* Overlapping 'segments' */

  f000:ffff = ffff:000f         /* Maximum address using different 'segments' */

  40:100    = 50:00             /* Last byte in Bios Data Area */

  It's important to note that a segment register can take any value ranging

  from 0 to 0xffff including the non-16bit-aligned addresses. It's on *physical*

  memory where a segment base address is always 16-bit aligned due to the left

  shift, not the segment register value itself.

  Example of completely valid segment register values and their physical

  addresses:

  Segment register value    |   Segment physical address

  -------------------------------------------------------

          0xffff            |           0xffff0

          0x1abc            |           0x1abc0

          0x4242            |           0x42420

          ...               |           ...

          0xyyyy            |           0xyyyy0, y = /[0-f]/

* Some calculations:

  biggest segment address possible = 0xffff

  biggest offset possible = 0xffff

  biggest *physical* address that can act as a segment address =

    biggest 20-bit address which is 16-byte aligned = 0xffff0

* NOTE: There's a huge difference between real-mode `segments' and segments

  provided in 386+ protected-mode processors. The 16bit value in a segmented

  protected-mode logical address is what's called a `segment selector' which

  is basically a pointer to a `segment descriptor' stored in either the GDT or

  the LDT. The segment descriptor includes info like the protected-mode segment

  base, limit, access permissions, present bit, etc.

  On the other hand, the real-mode `segments' are just primitive addresses

  that get hex left shifted in address calculations.

* Note that using this scheme, code segments are limited to a size of 64KB.

  To reach more code, we had to jump to what's called 'far pointers', which

  not only contains an offset relative to current code segment, but also a

  new address for the code segment.

  AT&T syntax for far jumps: `ljmp  $SEGMENT, $OFFSET' where 'segment' and

  'offset' are naturally 16bit values.

  Usage example: after loading the kernel to ram at its chosen segment which

  is usually far away from the mbr code segment, we 'far jump' to this segment

  with offset 0 to execute the loaded kernel code and go beyond the mbr's 512

  bytes size limit. This is the same technique used by GRUB to loads its stages.

* The above terminology is also the root of 386+ protected mode 'far pointer'

  which is a 'logical address' containing a segment selector (16 bit) and an

  offset (32 bit) relative to the segment pointed by that selector.

On accessing fixed disk drivers (hard-disks):

---------------------------------------------

* There's the usual heads, tracks, sectors, and cylinders. 

  Track: when the head is positioned over a point on the fixed disk, ready

  to read or write, the disk platter surface spins underneath it, tracing a

  full circle. This circle is a track. A disk surface contains may tracks.

  Sectors: Fixed disk systems divides each track into short arcs called

  sectors, each sector usually holds 512 bytes. This is the smallest unit

  of storage, as tracks would mean wasting a lot of space for small files.

  Cylinder: all the heads move in and out together, so each head is always

  physically located at the same track number; we can't have one head at

  track 0, and another at 250. Because of this, often the track location of

  the heads is not referred to as a track number but rather as a cylinder

  number.

  Disk size = bytes per sector * sectors per track * number of cylinders *

              number of heads

* BIOS fixed disk services are provided through the INT 13h service

  routine. It programs the hard-disk controller; it never writes directly

  from the processor to the hard-disk drive. The hard-disk controller

  communicates directly between the hard-disk, the processor, and system

  memory.

* To support disks beyoned the 8GB limit enforced by original IBM bios

  design (max of 1024 cylinder, 256 heads, and 63 sectors), new INT13

  bios services were added to bios which offers simple sector addressing

  using a logical zero based sector number (0, 1, 2, ..)

  This addressing scheme is easier than the Cylinder-Head-Sector model

  and is supported in all bios chips post-1995, so we use it exclusively.

  Check the boot sector code for more details.

On x86 jumps:

-------------

* References:

  - Intel i686 Manual, vol. 2, Instruction Set Reference, Chapter 3: JMP

  - Sun Microsystems, [AT&T] x86 Assembly language reference manual

  - Cute: boot/bootsect.S, boot/head.S, boot/e820.S, boot/trampoline.S

* Judging by my early naive trial-and-error experiences and the nature of

  newbies questions at osdev.org forums, the most common failure point while

  developing bootloaders and early kernel stages is either an intra or an

  inter-module jump. Because of this, we'll clarify the most used x86 jumps

  here, detailing their AT&T syntax and opcodes. We don't use the Intel

  syntax in our kernel, so it won't be discussed here; it's already clearly

  defined in the official Intel manuals.

  First, let's stress that a 'jump' is only a mechanism to disrupt the CPU

  execution flow, moving EIP to a different code (hopefully not data!) region.

  Generally, x86 jumps can be classified to either near or far. Near jumps

  are 'intra-segment', meaning that they only move within the limits of the

  currently setup and cashed code segment. Meanwhile, far jumps are

  'inter-segment': they take a (mostly new) code segment descriptor and an

  offset within such segment.

  The kind of displacement in such jumps can also be either relative or

  absolute. Relative addresses (wrt the next instruction address) were

  introduced to save opcodes size. [*]

  Absolute addresses are very important when relative offsets to an

  outside-of-code-object destination address cannot be validly calculated

  at link-time. Check the 'When %RIP-relativeness goes wrong' section's

  summary for further details.

  Examples of jumps:

	<AT&T Syntax>			  |	<Objdump Disassembly>

  [A] Near jump, 8-bit relative displacement (-128):  [short jump]

  1:	movl $0xdeadbeef, %eax		  | af:     b8 ef be ad de

	jmp  1b				  | b4:     eb f9

  [B] Near jump, 8-bit relative displacement (+127):  [short jump]

  1:	movl $0xdeadbeef, %eax	      	  | af:     b8 ef be ad de

	jmp  2f				  | b4:     eb 00

  2:	movl $0xcafebabe, %ebx		  | b6:     bb be ba fe ca

  [C] Near jump, 16-bit relative displacement:

	[Not supported by GAS]

  [D] Near jump, 32-bit relative displacement:

	jmp    dst			  | 12:     e9 f8 ff 0f 00

  .skip 0xffff8				  | ...

  dst:  movl   $0xdeadbeef, %eax	  | 10000f: b8 ef be ad de

  [E] Near jump, absolute indirect displacement (register):

	mov   $0x100000, %eax             | af:     b8 00 00 10 00

	jmp   *%eax			  | b4:     ff e0

  [F] Near jump, absolute indirect displacement (memory reference):

	jmpl   *(0x7c00 + mem)		  | af:     ff 25 b5 7c 00 00

  mem:	.long  0x100000                   | b5:     00 00 10 00

  (AT&T syntax uses the '*' operator for indirect jumps)

  Note that the _only_ available way for specifying _near_ absolute

  displacements is to encode such displacements 'indirectly' (i.e. not

  in the operands themselves) using a register or a memory reference.

  [G] Far jump, absolute 32-bit far pointer in operand (16-bit %cs

  index + 16-bit offset):

  .code16				  |

	ljmp   $0x08, $(0x7c00 + rel)	  | 99:     ea 9e 7c 08 00

  .code32				  |

  rel:	movl   $0x10000, %esi             | 9e:     be 00 00 01 00

  [H] Far jump, absolute 48-bit far pointer in operand (16-bit %cs

  index + 32-bit offset):

  .code32				  |

	# KERNEL_CS = 0x08		  |

	# startup_64 = 	0x100112	  |

	ljmp   $KERNEL_CS, $startup_64	  | 10006f: ea 12 01 10 00 08 00

  [I] Far jumps, 32-bit or 48-bit absolute indirect displacement

  (memory reference):

	[Rarely used, let's only know that they exist]

  [*] footnote: On x86-32, only jumps and calls had the relative addressing

  facility. To save opcode size, especially while handling 64-bit wide virtual

  addresses, AMD introduced a global and default %RIP-relative addressing

  scheme for most ops, including most important, dereferencing global data.

On referencing global symbols:

------------------------------

* References:

  - GNU LD Manual, 'Using LD', Section 3.5.4 -'Source Code Reference'

  - Cute: include/idt.h, kernel/idt.S

* To gracefully fail instead of triple faulting the machine, one of the first

  things implemented while writing the C part of the kernel was setting up CPU

  exception handlers. To setup these handlers, we needed access to the IDT table

  and its descriptor; both were already defined in assembly files. What are the

  rules for accessing these data structures natively in C?

  When a global symbol is declared in C, two things happen. The compiler reserves

  enough space in the executable .data or .bss section holding the _value_ of the

  symbol. Second, it creates an entry in the program's symbol table which holds

  the symbol _address_ (in that section). For a small example, check below

  program and its disassembly:

  --> globals.c (a1):		|  --> [disassembly, $gcc -O3]:

  int x;			|  0000000000600800 <y>: 11 11 00 00 ... (.data)

  int *y = 0x1111;		|  0000000000600818 <x>: ...  (.bss, 8 bytes)

				|

  int main(void) {		|  0000000000400460 <main>:

    x = 0xdeadbeef;		|  400460: movq 0x200399(%rip),%rax  #600800 <y>

    *y = 0xcafebabe;		|  400467: movl $0xdeadbeef,0x2003a7(%rip) #600818 <x>

  }				|  400471: movl $0xcafebabe,(%rax)

				|  400477: retq

  As you can see, accessing the global 'x' required a single memory dereference

  of the address 0x600818 stored in the program's symbol table. Meanwhile,

  dereferencing the pointer 'y' required TWO memory dereferences: one for

  dereferencing the variable 'y' address 0x600800, getting its value/contents,

  and _another_ dereference for such value stored (0x1111); after all, a pointer

  is just a special 8-byte variable.

* Furthermore, check below program which has several symbols defined in an

  assembly file with different treatments of such symbols (and their data) in C:

  --> data.S (a2):		|  --> app.c (a2):

  .section .data		|  uint32_t x;

  .globl x			|  extern uint32_t *y;

  x:				|  extern uint32_t z[];

	.long 0xdeadbeef	|

				|  int main(void) {

  .globl y			|    printf("&x = 0x%lx\n", &x);

  y:				|    printf("&y = 0x%lx\n", &y);

	.long 0xcafebabe	|    printf("&z = 0x%lx\n", &z);

				|

  .globl z			|    printf("x = 0x%x\n", x);

  z:				|    printf("y = 0x%x\n", y);

	.long 0xeeeeeeed	|    ...    /* further code: check the output */

				|  }

  $ gcc -O3 data.S app.c -o output.elf

  $ objdump -D output.elf -j .data

  0000000000600af0 <x>:

  600af0:		ef be ad de be ba

  0000000000600af4 <y>:

  600af4:		be ba fe ca ed

  0000000000600af8 <z>:

  600af8:		ed ee ee ee

  $ ./output.elf

  'int x'   is a global located at program area (&x = ): 0x600af0

  'int *y'  is a global located at program area (&y = ): 0x600af4

  'int z[]' is a global located at program area (&z = ): 0x600af8

  x = 0xdeadbeef		|  *x = <not-applicable>

  y = 0xcafebabe		|  *y = <segmentation fault> (0xcafebabe unmapped)

  z = 0x600af8			|  *z = 0xeeeeeeed

  x[0] = <not-applicable>

  y[0] = <segmentation fault> since 0xcafebabe is not mapped

  z[0] = 0xeeeeeeed

  As seen from above introspection, y is just a global variable holding

  0xcafebabe. y _address_ is '0x600af4', buts its _value_ is 0xcafebabe. Thus,

  '*y' will produce two memory dereferences, and the second of the two will

  result in a CPU exception (segmentation fault) since 0xcafebabe is not

  mapped.

* So, if we have a structure like the below IDT table descriptor:

  /* Located at ffffffff8010e240

   * Binary value (little endian): 00 10 80 16 11 00 00 80 ff ff */

  .globl idtdesc

  idtdesc:

	.word  idt_end - idt		# limit

	.quad  VIRTUAL(KTEXT_PHYS(idt))	# base

  we can _not_ reference it in C as

  struct idt_descriptor {

	uint16_t limit;

	uint64_t base;

  } __packed;

  extern struct idt_descriptor *idtdesc;	/* WRONG!! */

  idtdesc->limit = 0;				/* Page-fault exception! */

  since in above case, the variable pointer _address_ (&idtdesc = ) will be

  0x10e240, and the pointer _value_ (idtdesc = ) will equal 0x8000001116801000.

  Thus, dereferencing such pointer as in 'idtdesc->limit' above will in fact

  dereference 0x10e240 first, then afterwards dereference the unmapped address

  0x8000001116801000! Final result: a CPU page fault exception.

  The only wrong thing above was specifying the wrong type for the 'idtdesc'

  label. Having the type as the struct itself instead of a pointer will let the

  struct address be 0x10e240, and its value will equal 0xffff8000001116801000

  which _is_ the desired result:

  extern const struct idt_descriptor idtdesc;

  idtdesc.limit = 0;				/* Safe!! */

* Now, if we want to reference the IDT table itself:

  /* IDT_GATES: number of entries in the table */

  .align 16

  .globl idt

  idt:

	.skip  IDT_GATES * 16

  idt_end:

  Assuming a pre-defined C type of 'struct idt_gate', representing a single IDT

  table entry structure, all what we need is an array of such types. Namely:

  extern struct idt_gate idt[IDT_GATES];

  Note that after all, an array 'A' is a special kind of pointer where A = &A.

  (label value and address are the same, equalling link-time label address

  stored in the symbol table)

* Finally, let's reference below exception handler stubs, where they catch the

  exception vector number through their positions in the stubs table:

  /* Each stub code size = IDT_STUB_SIZE bytes */

  .globl idt_exception_stubs

  idt_exception_stubs:

        i = 0

	.rept  EXCEPTION_GATES_CNT

	movq   $i, %rsi

	jmp    default_exception_handler

	i = i + 1

	.endr

  Well, let's first remember here that we're pointing to code, so we're only

  interested in  each stub address,  not by any mean its contents. So, after

  all, since this is a table, an array fits our goals nicely. What will be the

  base object type? We only care about addresses, so let the types be 'char*':

  char pointers makes pointer arithmetic very simple. An initial try can be

  extern const char idt_exception_stubs[EXCEPTION_GATES_CNT];

  Nice, but by this, each table cell is of size 1 byte (char). We want each

  table cell to have the size IDT_STUB_SIZE chars (bytes). Namely:

  idt_exception_stubs[EXCEPTION_GATES_CNT][IDT_STUB_SIZE]

  which makes the compiler automatically calculate any stub address for us.

  If we want the address of the third stub, we'll simply write:

  void *addr = &idt_exception_stubs[3];

* Summary: the simple declaration 'extern int x' directly reference the 4 bytes

  marked as 'x' in the executable, where 'x' address is specified at link-time

  in the program's symbol table. The operator [] in the declaration

  'extern type SYMBOL[]' leaves it open only to the number of base type objects

  which are present, not *where* they are. SYMBOL[n] just adds more static-time

  safety; SYMBOL[n][s] let the compiler automatically calculates an entry (of

  size 's')index for us.

  Meanwhile, the '*' operator in a declaration 'extern TYPE *P' only binds

  where the _8-byte variable_ P reside in the executable (its address), NOT

  where the base type object is. The base-object itself can be reached only by

  a double dereference: dereference of P address first, then a dereference of

  P's content itself (which is, in turn, an 8-byte address).

The 8259A Programmable Interrupt Controller:

--------------------------------------------

* References:

  - The Intel 8259A PIC datasheet.

  - The superb information in "The undocumented PC", chapter 17 - "Interrupt

  control and NMI".

  In subsequent text, and as said by the sheet, IRR = "Interrupt Request

  Register", ISR="In-Service Register", IMR = "Interrupt Mask Register".

* As described by Brendan Trotter (bcos) on #osdev, and the sheet:

  An interrupt request is executed by raising an IR input (low to high) and

  holding it high until it is acknowledged (Edge Triggered Mode). Where

  "acknowledged" means doing so by the PIC chip, not by the CPU/OS . Also, in

  this case "acknowledges" just means that it recognises it and sets the

  corresponding flag in the IRR

  Basically, when an interrupt is received the PIC sets the corresponding flag in

  the IRR. When the PIC sends the IRQ to the CPU it clears the flag in the IRR

  and sets the flag in the ISR. And when the CPU sends EOI the PIC clears the

  flag in the ISR. The processor sends an EOI through the the INTA pin.

  If the PIC sends a high priority IRQ to the CPU and is waiting for EOI when a

  low priority IRQ occurs, then the PIC must remember that the low priority IRQ

  occured (so that it can tell the CPU about it when the CPU is finished with the

  high priority IRQ), by setting its IRR bit.

  The 8259 cannot be used with level interrupts. This is because when

  an interrupt line goes true, it is latched internally in the IRR.

* Spuruious interrupts:

  As said by the sheet: "If no interrupt request is present at step 4 of either

  sequence (i.e., the request was too short in duration), the 8259A will issue an

  interrupt level 7. Both the vectoring bytes and the CAS lines will look like an

  interrupt number 7 was requested."

  And as said in undoc pc: "Although a noise glitch should never occur, a poor

  bus design or badly glitch will trigger an invalid interrupt. If the glitch

  occurs on IRQ 0 to IRQ7, interrupt F (which is mapped to IRQ 7) will be

  called. The service handler for interrupt Fh and 77H (assuming the PIC wasn't

  re-mapped to more sane vector-numbers) should read the in-service register to

  confirm that a real interrupt occurred. An invalid interrupt has In-Service bit

  7 cleared, and a valid interrupt has valid bit 7 set.

* So why should the PIC bother sending the CPU a spurious 7 IRQ? it could've just

  ignored the noise glitch source. The problem is that it might have told the CPU

  it's about to get an interrupt, and if it did (step 1, 2, and 3), it can not

  now decode the interrupt info since the line has been deasserted. Either the

  assert period was too short that the IRQ number was not latched internally, or

  the PIC just recognized it was a noise glitch due to the very short assertion

  period. So it gives the programmed IRQ 7 vector number to the CPU. This avoids

  unccessary communication with the real devices attached to IRQ7.

* Take care that, as said by linux kernel comments, the two spurious IRQs 7 and

  15 usually resulting from the 8259A-1|2 PICs do occur even if all the IRQs are

  masked (IMR = 0xff).

* An example of an interrupt (refs: undoc pc + intel sheet):

  1- The adapter card requests service, by driving the hardware IRQ line 5 from

     low to high

  2- The IRQ 5 line is connected to the PIC. The edge-triggered request is

     recorded in the controllers Interrupt-Request Register (IRR). In this case,

     the IRR bit 5 is set.

  3- The PIC first checks if the Interrupt Mask Register (IMR) to see if IRQ5 is

     allowed (not masked, IMR bit 5 = 0). Assuming that bit clear, the PIC moves

     to the next step.

  4- Using its priority resolver uint, the conntroller checks if any higher

     priority interrupts are active or in progress. If so, no further action is

     done till all higher priority irqs are serviced.

  5- Once all higher irqs are serviced, the controller flags the CPU over the

     dedicated INT hardware line leading to the CPU.

  6- If the CPU has hardware interrupts enabled, the CPU returns an interrupt

     acknowledgment to the PIC using the INTA pin.

  7- Directly after receiving a pulse from the INTA pin, the relevant In-Service

     register bit (bit 5) is set, and the corresponding IRR bit is reset.

  8- The processor sends another INTA pulse. During this pulse, the PIC sends

     a programmed 8-bit pointer back to the CPU, according the raised IRQ. In

     the default bios programmed PIC case, the pic will return the interrupt

     value 0x0D for IRQ5. 

  9- In an instruction boundary, the cpu interrupts the current process and

     jumps to the code address specified in the IDT entry 0xD. For x86-64 cpus,

     entry 0xD = IDT base (specified through lidt) + 0xD * 16.

 10- One of the key aspects of the interrupt handler specified in the IDT entry

     must make is to remove the interrupt request made by the adapter. The line

     maybe shared, and several ISRs got executed, where they determine first if

     they are servicing the right device using the "interrupt pending" register

     found in PCI devices, etc.

 11- At the end of the interrupt handler, the handler sends the value 0x20 to

     the PIC command port to indicate an End-of-Interrupt (EOI). The EOI command

     clears the IRQ5 bit in the In-Service Regisger.(*) The case is different in

     case of Automatic EOI (AEOI) mode, and is described later.

 12- By clearing the IRQ5 bit in the ISR, the chip is now ready to accept another

     interrupt from IRQ5 or any lower priority interrupt. This completes the

     interrupt cycle.

* On x86 SMP initialization sequence:

-------------------------------------

* References:

  - Intel MP specification v1.4, Appendix B - Operating System Programming

  Guideleins.

  - Intel Software Dev. Manual vol3A, Chapter 8, 8.4 - Multiple-Processor (MP)

  initialization.

  - Intel Software Dev. Manual vol3B, Appendix C - MP Initialization for P6

  Family Processors.

* Generally, there're two base x86 MP initialization sequences. One for the

  processors with the external APIC, and a second for processors with internal

  APIC (P6+ x86 processors).

  We won't bother ourself with the processors with external APICs (80486 and

  early Pentiums) since we're only targetting long mode.

  All long mode capable processors contains an integrated apic and comply with

  the new Intel MP bootup sequence, where no FIPI or BIPI are needed.

  On this new sequence, the INIT IPI on AP cores let them wait for the SIPI to

  get their starting execution vector instead of _unconditionally_ executing the

  BIOS init code. This avoids the ugly dependency on AT+ BIOSes hacks like the

  warm-reset vector to let the AP cores start executing from a custom address

  instead of BIOS init code. Search the MP spec for `Warm-reset vector'.

* After system-wide bootup, or reset, the MP initialization protocol is going to

  be executed. In this protocol, the hardware setup the APIC IDs for each logical

  core according to system topology and assign one of the cores as the bootstrap

  core and the others as APs (Application processors/cores).

  The core nominated as the BSC will fetch and begin executing BIOS bootstrap

  code at the reset vector physical address 0xfffffff0.

  The remaining cores (setup as APs) will enter a "wait-for-SIPI" state.

* Afterwars, the BIOS init code builds its ACPI and MP tables and count the

  number of AP cores, and update its tables entries for each new AP core

  found. For the algorithm, check Intel's volume 3A 8.4.4 MP Initialization

  Example.

* At the end, the BIOS puts each AP core to halted state with interrupts

  disabled. By the nature of the halted state with interrupts disabled, only

  INIT, #NMI, #SMI are able to start the cores again.

  IMPORTANT: The MP protocol will be executed only after a power-up or RESET. If

  the MP protocol has been completed and a BSP has been chosen, subsequent INITs

  (either to a specific processor or system wide) do not cause the MP protocol to

  be repeated. Instead, each processor examines its BSP flag (in the APIC_BASE

  MSR) to determine whether it should execute the BIOS boot-strap code (if it is

  the BSP) or enter a wait-for-SIPI state (if it is an AP).

  So any INIT to any of the AP cores by the OS boot code will let it enter a

  'wait-for-SIPI' state to be able to get its start execution vector.

* Note that the cores get started with all its states uninitialized. We have

  to update each core from real to long mode, and update its MMU and other

  system tables to match the bootstrap.

  Kernels usually call this part the SMP `trampoline', since it let the cores

  jump from its raw uninitialized state to a state similar to the bootstrap's

  one.

* On linkers 'relocation error's:

---------------------------------

* References:

  - Relocation types (R_X86_64_*): System V ABI AMD64 supplement,

    section 4.4 - Relocation

  - The Executable and Linkable Format (ELF) spec, Book I - Relocation

* One of the errors that faced me at a number of sensitive places like the

  kernel head, the SMP trampoline, and the linker script was LD linker's

  'relocation error'. Due to their relative opaqueness, they puzzled me to

  a great extent at first. An example of some of those errors from linking

  a preliminary trampoline code to the rest of the kernel image was:

  trampoline.o: In function `trampoline':

  (.text+0x1): relocation truncated to fit: R_X86_64_16 against `.text'

  trampoline.o: In function `_start':

  (.text+0xc): relocation truncated to fit: R_X86_64_16 against `.data'

  trampoline.o: In function `_start':

  (.text+0x11): relocation truncated to fit: R_X86_64_16 against `.data'

  trampoline.o: In function `_start':

  (.text+0x14): relocation truncated to fit: R_X86_64_32 against `.bss'

  trampoline.o: In function `_start':

  (.text+0x1d): relocation truncated to fit: R_X86_64_32 against `.bss'

  trampoline.o: In function `_start':

  (.text+0x21): relocation truncated to fit: R_X86_64_32 against `.bss'

  trampoline.o: In function `_start':

  (.text+0x27): relocation truncated to fit: R_X86_64_32 against `.bss'

  trampoline.o: In function `_start':

  (.text+0x2b): relocation truncated to fit: R_X86_64_32 against `.bss'

* We need to understand relocation to parse above errors. Relocation Information

  sections contain information about unresolved references. Since compilers and

  assemblers do not know at what absolute memory address a symbol will be

  allocated, and since they are unaware of definitions of symbols in other files,

  __every__ reference to such a symbol will create a relocation entry.

  The relocation entry will point to the code address where the reference is

  being made, and to the symbol table entry that contains the symbol that is

  referenced. The linker will use this information to fill in the correct address

  after it has allocated addresses to all symbols.

* Dumping the ELF object trampoline.o relocation section ($readelf -a) leads to:

  Relocation section '.rela.text' at offset 0x438 contains 8 entries:

    Offset          Info           Type           Sym. Value    Sym. Name + Addend

  000000000001  00010000000c R_X86_64_16       0000000000000000 .text + 5

  00000000000c  00020000000c R_X86_64_16       0000000000000000 .data + 0

  000000000011  00020000000c R_X86_64_16       0000000000000000 .data + 6

  000000000014  00030000000a R_X86_64_32       0000000000000000 .bss + 0

  00000000001d  00030000000a R_X86_64_32       0000000000000000 .bss + 0

  000000000021  00030000000a R_X86_64_32       0000000000000000 .bss + 1007

  000000000027  00030000000a R_X86_64_32       0000000000000000 .bss + 0

  00000000002b  00030000000a R_X86_64_32       0000000000000000 .bss + 2007

  The relocation table fields are described in the ELF specification. In summary:

  - Offset: location to apply relocation action relative to section start

  - Info: symbol table index wrt which the relocation must be made

  - Type: from the AMD64 ABI. _16: max bit width = 16 (rmode). _32: 32 bits max

  - Addend: constant addend used to compute the value to be stored in the

    relocatable field. Ex: `lgdt $(gdt + 0x10)' will print `.data + 10' where

    the addend = 0x10

* Note that all relocatable fields are filled with zeroes in the trampoline

  ELF object trampoline.o:

  # .code16 (real-mode)

  0000000000000000 <trampoline>:

   0:   ea 00 00 00 60     ljmp   $0x6000,$0x0 # ljmp $0x6000, $_start

  0000000000000005 <_start>:

   5:   e8 2a 00           call   32 <print>   # RIP-relative (7 + 0x002a = 32)

   8:   fa                 cli

   9:   0f 01 1e 00 00     lidtw  0x0          # lidt $idtdesc

   e:   0f 01 16 00 00     lgdtw  0x0          # lgdt $gdtdesc

  13:   b8 00 00 00 00     mov    $0x0,%eax    # movl %cr3, %eax

  18:   0f 22 d8           mov    %eax,%cr3

  1b:   c7 05 00 00 00     movw   $0x0,(%di)   # movl $(init_pgt+0x1007), init_pgt

  20:   00 00 00 00 00

  25:   c7 05 00 00 00     movw   $0x0,(%di)   # movl $(init_pgt+0x2007), init_pgt

  2a:   00 00 00 00 00

  2f:   f4                 hlt

  30:   eb fd              jmp    2f <_start+0x2a>

  0000000000000032 <print>:

  Also note that the offsets in the error messages (.text+0x1), (.text+0x11), ..

  are the same offsets reported in the relocation table entries, and are the

  same ones filled with zero in the above disassembly.

* With above information in hand, we can simply deduce the errors cause. We link

  the trampoline assembly code against our long mode kernel, but the kernel linker

  script sets up the virtual addresses base at 0xffffffff80000000.

  So the linker, obeying the kernel script, tries to assign huge (> -2GB) virtual

  addresses to our symbols. The linker then discovers that since the trampoline

  to-be-relocated symbols are setup with the R_X86_64_16 model, it's limited to a

  width of 16 bits, and limited to 32 bits in case of R_X86_64_32. Ofcourse those

  bits aren't sufficient, so it has to truncate the addresses producing a wrong

  final executable.

  In a nutshell, there was a reported error _for each_ relocatable symbol used,

  reflecting the number of relocation table entries with a type/bit-width that is

  insufficient to the linker script setup 64-bit virtual addresses.

* When %RIP-relativeness goes wrong:

------------------------------------

* References:

  - Intel Instruction Set Reference, A-M, vol. 2A. 3.2-CALL--Call procedure.

* One of the interesting errors I faced in jumping away from head or trampoline

  code to C code was %rip-relativeness related errors. Here are two interesting

  cases:

  In head.S, after switching to long mode, and setting up the higher-half

  virtual mappings, we jump to C code:

  .code64

  startup_64:

	movq   $stack_end, %rsp

	...

	# .. Setup identity mappings

	# .. Setup high-half virtual addresses mappings

	# .. Apply the page tables

	# .. let %RIP be its virtual address equivalent

	# .. let %RSP, and GDTR be their virtual addresses equivalent

	# .. Let NULL pointers segfault and avoid physical-address dependent

	#    code: remove identity mappings

	...

	call   kernel_start		# C method: void kernel_start(void);

  But unfortunately we get the machine constantly triple-faulting. As indicated

  by Bochs debugging output:

  [CPU1 ] BxError: Encountered an unknown instruction b1=0x0e (signalling #UD)

  [CPU1 ] modrm was 0x00, nnn was 0, rm was 6

  [CPU1 ] exception(0x06): error_code=0000

  Disassembling the object file, we see that everything is at place. And `callq'

  points to 0xffffffff80109250; the `kernel_start' method:

  # head.o

  00000000001000b9 <startup_64>:

    1000b9:       48 c7 c4 00 50 10 00    mov    $0x105000,%rsp

    ...

    10012f:       e8 1c 91 00 80          callq  ffffffff80109250 <kernel_start>

  Or does it?

  A closer inspection at the binary disassembly reveals that the call is a

  near, relative, displacement relative to next instruction, 32-bit displacement

  sign-extended to 64-bits in long mode call.

  So the instruction is at 0x10012f, with a length of 5 bytes, relative

  displacemented is calculated from 0x10012f + 5 = 0x100134.

  Code wants to call `kernel_start', so the relative displacemented =

  0xffffffff80109250 - 0x100134 = 0xffffffff8000911c, which is the value encoded

  in the `callq' instruction after sign-extension in a little-endian form. So

  what's wrong?

  Notice that by the time the CPU is executing the `callq', it's actually using a

  __different__ %RIP than 0x10012f. The %RIP is in its (%RIP + 0xffffffff80000000)

  virtual form as the identity mappings are to be removed.

  This clearly messes up the %rip-relative-displacement calculations, and sends

  the CPUs to unpredictable areas, leading to unknown opcode exceptions and

  other horrors.

* Another similar case was faced in the trampoline code, when it jumps away to

  the rest of AP cores C init code. The `callq' instruction was just sending

  the CPU to irregular places, with horrifying results.

  Why the callq misbehaved in trampoline? Because the trampoline code is linked

  to the kernel, but actually  copied to a below-1MB 4KB-page, and then executed

  from there. This messed up external %rip-relativeness.

  Calls to internal trampoline methods worked because those methods retained their

  relative distances between each other when they were copied. On the other hand,

  and by definition, external distances was not kept when calling outside code

  (like the C application_start() code):

  # trampoline.o

  ffffffff8010ae06 <startup_64>:

    ffffffff8010ae06:       48 8d a4 24 00 00 00    lea    -0x80000000(%rsp),%rsp

    ffffffff8010ae0d:       80

    ...

    ffffffff8010ae2e:       e8 0d e3 ff ff          callq  ffffffff80109140 <application_start>

    ffffffff8010ae33:       90                      nop

* Solution: The two examples are special cases of PIC, position-independent code.

  The trampoline is PIC cause it's executed from different position than where

  it's linked. The head.S code also applies as parts of it get executed using a

  different %rip than what it's linked as.

  In the two above cases, we can simply solve them by specifying the absolute

  address of destination code instead of using relative x86 calls. As said in

  Intel instruction reference, x86-64 has a near call, with absolute indirect

  addressing facility. It can be used in GNU AS as follows:

	movq   $application_start, %rax

	jmpq   *%rax

  And also for head.S:

	movq   $kernel_start, %rax

	callq  *%rax

  # head.o

  00000000001000b9 <startup_64>:

    1000b9:       48 c7 c4 00 50 10 00    mov    $0x105000,%rsp

    ...

    10012f:       48 c7 c0 50 92 10 80    mov    $0xffffffff80109250,%rax

    100136:       ff d0                   callq  *%rax

  which solves our problem nicely.

* Summary: For a code object which is run from a _different_ address than what

  it was originally linked to, a 'jmp' or 'call' op to a label (or an address)

  outside of that unlucky object needs absolute addresses instead of the

  _default_ %rip-relative ones. In this case, the 'next opcode address', being

  the base of %RIP-relativeness calculations, is not the same at both link-time

  and run-time; at run-time, the linker-calculated relative offset of the

  destination becomes completely invalid due to the _now-different_ %RIP base,

  jumping intentionally to the unknown.

  Meanwhile, relative jumps and calls to labels within the same object are still

  valid: the relative distance is still maintained within the object itself, no

  matter where it's running from. This kind of internal relativeness is usually

  calculated by the assembler (instead of the linker) and is safe here.

Testing libc()-like kernel code:

--------------------------------

* An interesting way to test libc()-like kernel code (e.g. std string methods)

  is to replace system's libc implementation with our own. Afterwards, we run a

  huge program (Firefox, OpenOffice or gcc) and observe the results.

  Those tests usually cover huge number of cases, and give a good indicator of

  tested kern code stability. I've usually found that even the smallest mistake

  in such tests produce either a non-behaving app or a direct segfault.

* Unix linkers LD_PRELOAD feature can help us immensely. Assuming our string

  methods resides at 'string_lib.c', we do something similar to:

  # Position-independent object, suitable for dynamic linking

  $ gcc --std=gnu99 -O3 -fPIC -c string_lib.c -o string_lib.o

  # Produce shared object (instead of final executable) that can

  # be linked with other objects to form an executable.

  $ gcc -shared -o string_lib.so string_lib.o

  $ LD_PRELOAD='./string_lib.so' firefox-bin

  Note: always run these tests with the binaries themselves instead of

  their bash-script wrappers. Such shell wrappers don't play very well

  with LD_PRELOAD at times.

* It is interesting to note that a 30-second run of Firefox produced

  655,227 memset() and memcpy() calls! A 1-minute run of Google Chrome

  produced 1,889,087 calls! (counted by `wc -l').

On SMP Memory ordering models:

------------------------------

* References:

  - Kourosh Gharachorloo, "Memory Consistency Models for Shared-Memory

    Multiprocessors", Digital Equipment (DEC) with Stanford and DARPA support

  - Paul McKenny, Memory ordering in modern processors, 2007.09.19 Draft

  - Paul McKenny, Memory Barriers: a Hardware View for Software Hackers, IBM

  - Linux Kernel Documentation/memory-barriers.txt, kernel.org

  - DEC/HP OpenVMS Ask the Wizard, http://www.webcitation.org/5laUMQfyi

  - Intel Manuals vol3A, chapter8, MP Management, 8.2 - Memory Ordering

  - AMD64 Architecture Programmer's Manual, chapter 7 - Memory System

* To understand memory ordering models correctly, we need to understand which

  parts of our code are loads, which are stores, and which are in fact both.

  Below example should cover basic cases of shared global variables usage,

  compare the C code with its assembly output:

  int *global_symbol = (int *)0xdeadbeef;

  int main(void) {

	/* 1) memory load + dependent memory store to stack */

	int t = global_symbol;

	/* 2) memory store */

	global_symbol = (int *)0xbbbb;

	/* A memory load + dependent memory store */

	*global_symbol = 0xcccc;

  }

  Disassembly of section .data:

  ...

  0000000000600840 <global_symbol>:

  600840:       ef

  600841:       be ad de 00 00

  Disassembly of section .text:

  ...

  0000000000400448 <main>:

  400448:       55                      push   %rbp

  400449:       48 89 e5                mov    %rsp,%rbp

  # 1) Mem. load + store to stack

  40044c:       48 8b 05 dd 03 20 00    mov    0x2003dd(%rip),%rax    # 600830 <global_symbol>

  400453:       89 45 fc                mov    %eax,-0x4(%rbp)

  # 2) Mem. store

  400456:       48 c7 05 cf 03 20 00    movq   $0xbbbb,0x2003cf(%rip) # 600830 <global_symbol>

  40045d:       bb bb 00 00

  # 3) Mem. load + store to pointed value

  400461:       48 8b 05 c8 03 20 00    mov    0x2003c8(%rip),%rax    # 600830 <global_symbol>

  400468:       c7 00 cc cc 00 00       movl   $0xcccc,(%rax)

  40046e:       c9                      leaveq

  40046f:       c3                      retq

* Terminology of memory orders:

  - Program order: the memory operations order specified in object code.

  - Perceived order: the order a CPU perceives of its and other CPUs memory ops.

* Memory ordering is a tradeoff between programming ease and performance. On

  uniprocessors, many ops are assumed to execute in program order. Processors can

  provide the illusion of sequensiality by only preserving sequential order among

  memory operations to the same location.

  Sequential consistency defined by Lamport provides a simple model to programmers,

  but it adversely affects efficiency and performance: the illusion trick provided

  in uniprocessors can't be used on MP systems to provide sequential consistency.

  Weak ordering distinguishes between ordinary memory operations and memory ops

  used for synchronization. By ensuring consistency only at the synchronization

  points, weak ordering allows ordinary operations in between pairs of

  synchronizations to be reordered with respect to one another.

  Such specifications can be considered system-centric since they in effect expose

  the low-level system optimizations to the programmer.

* General rules for all architectures:

  - A given CPU will always _perceive_ its own memory operations as occuring

    in program order, without a need for memory barriers.

  - Naturally-aligned loads and stores are always atomic

  - Code that uses standard synchronization primitives (spinlocks, RCU, ..)

    should not need explicit mem barriers. Only tricky code that bypasses those

    primitives need those barriers. An example of a linked list lockless search

    is given below.

* Example:

  Writer CPU:

  -----------

  # Linked list head is `smack_known'

  struct smack_known *smack_known;

  mutex_lock(&smack_known_lock);

  if (skp == NULL) {

	skp = kzalloc(sizeof(struct smack_known), GFP_KERNEL);

	if (skp != NULL) {

  1-		skp->smk_next = smack_known;

  2-		skp->smk_secid = smack_next_secid++;

  3-		skp->smk_cipso = NULL;

		/* 1- BUG: Write barrier needed! */

  4-		smack_known = skp;

	}

  }

  mutex_unlock(&smack_known_lock);

  Reader CPU:

  -----------

  # Just locklessly access the list

  struct smack_label *skp;

  skp = smack_known;

  while (skp) {

	/* 2- BUG: Alpha CPUs!! */

  5-	if (skp->smk_secid == 10) {

		...

	}

	...

	skp = skp->next;

  }

  Bug 1:

  ------

  In the writer CPU, the latest 3 stores can be re-ordered in any combination.

  In arhitectures that reorder stores like Alpha, Itanum, POWER, and SPARC, this

  may lead other CPUs to perceive an incomplete node added to the list: a garbage

  smk_secid value. This may even lead to graver results if you notice that the

  first line (skp->smk_next = smack_known) is actually a load followed by a

  store. So the sequence is:

  Load from smack known

  store to ->smk_next address

  ...

  store to smack_known

  The cpu can reorder the last stores, leading to a linked list head with a

  bogus next pointer; effectively a user-space segmentation fault or worse,

  a CPU exception if in kernel mode.

  Bug 2:

  ------

  As said by OpenVMS documenatation (Ask the Wizard):

  "Your producer must issue a 'memory barrier' instruction after writing the data

  to shared memory and before inserting it on the queue; likewise, your consumer

  _must_ issue a memory barrier instruction after removing an item from the queue

  and before reading from its memory.  Otherwise, you risk seeing stale data,

  since, while the Alpha processor does provide coherent memory, it does not

  provide implicit ordering of reads and writes.  (That is, the write of the

  producer's data might reach memory after the write of the queue, such that the

  consumer might read the new item from the queue but get the previous values

  from the item's memory."

  But how does the consumer sees the pointer before its data even if write

  barriers were used?

  As said by McKenny, the producer's write barrier will guarantee that the cache

  invalidates performed by the first 3 lines  will reach the interconnect before

  that of the last line, but it "makes absolutely no guarantee about the order in

  which the new values will reach the reading CPU’s core."

  So assume smack_known, and smack_known->smk_secid are on different cache banks.

  Because of the write barrier, the producer's data will reach the interconnect

  before updating the queue. The bank holding smack_known is idle, so its line

  gets invalidated and updated, while the bank holding smk_secid was busy, so the

  cache invalidates for the new element are being delayed. This leads to seeing

  new value for the pointer, but old cached values for the new element at line 5.

  Linux kernel documentation explains by stating "some versions of the Alpha CPU

  have a split data cache, permitting them to have two semantically-related cache

  lines updated at separate times.  This is where the data dependency barrier

  really becomes necessary as this synchronises both caches with the memory

  coherence system, thus making it seem like pointer changes vs new data occur in

  the right order.

* On the x86 side, only below basic memory access is guaranteed to be atomic:

  - Readnig or writing a byte

  - Reading or writing a word aligned on 16-bit boundary

  - Reading or writing a doubleword aligned on 32-bit boundary

  - Reading or writing a quadword aligned on 64-bit boundary

  On P6 family processors and up:

  - Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within

    a cache line. (but how do we know whether a memory access fits a cache line?)

On the C 'volatile' type qualifier:

-----------------------------------

* References:

  - Eric Eid & John Regehr, "Volatiles Are Miscompiled, and What to Do about It",

    Proceedings of the Eighth ACM and IEEE International Conference.

  - Attached Linux kernel's "volatile-considered-harmful.txt" document, added

    with various core developers thoughts copied from LKML.

  - ISO C99 Committee Draft - September 7, 2007

  - My OSDEV forums post: http://forum.osdev.org/viewtopic.php?t=21210&start=17

* As said by the C standard, "An object that has volatile-qualified type may be

  modified in ways unknown to the implementation or have other unknown side

  effects. Therefore any expression referring to such an object shall be evaluated

  strictly according to the rules of the abstract machine"

  "Actions on objects so declared shall not be optimized out by an implementation,

  or reordered except as permitted by the rules for evaluating expressions".

  It's in a practical manner, "for every read or write to a volatile variable

  that would be performed by a straightforward interpreter for C, exactly one

  load from or store to the memory locations allocated to the variable must be

  performed".

* Volatile is used when we don't want the memory access to be re-ordered, cached,

  or optimized away, as in accessing memory mapped I/O registers. Another case is

  where global variables get changed behind our back by other execution paths as

  in interrupt handlers or other threads:

  int var_set_by_irq_handler = 0;

  ..

  while (var_set_by_irq_handler == 0);

  The compiler has every right to optimize the loop to an infinite loop. To avoid

  this, and force the compiler to access the global variable memory at each

  iteration, we use volatile, since volatile objects "shall not be optimized out

  by an implementation".

* Take care that the volatile is a type qualifier as `constant'. So in below case:

  static volatile uint64_t *msg = NULL;		/* (1) */

  while (msg == NULL)

	asm volatile ("pause");

  The above loop will still be optimized to an infinite loop. The declaration

  states that the memory area _pointed_ by `msg' is volatile, not that the pointer

  itself is volatile. So the above declaration should've been:

  static uint64_t * volatile msg = NULL;	/* (2) */

  specifying a volatile pointer. Declaration at (1) is perfectly fine though if

  we're accessing the variable as in:

  while (*msg == 0x1234)

	asm volatile ("pause");

  cause now we're referencing the memory declared as volatile. The compiler must

  fetch the memory pointed by 'msg' at each iteration.

* As seen from above example and the ACM paper, volatiles are really subtle in C

  and many industrial compilers get them wrong. I prefer the Linux way of handling

  the issue, namely __minimizing__ 'volatile' as far as possible, and depending on

  explicit compiler and cpu _barriers_, and SMP primitives as needed.

* So instead of:

  static uint64_t * volatile msg = NULL;

  while (msg == NULL)

	asm volatile ("pause");

  We use an explicit compiler barrier:

  static uint64_t *msg = NULL;

  while (msg == NULL)

	asm volatile ("pause": : :"memory");

  The compiler barrier will assure "GCC not to keep memory values cached in

  registers across the assembler instruction and not to optimize stores or loads

  to that memory". In other words, it will force gcc to reload any values from

  memory over the busy loop.

* Instead of:

  volatile uint32_t *ioregsel = (uint32_t *)ioapic_base(apic);

  volatile uint32_t *iowin = (uint32_t *)(ioapic_base(apic) + 0x10);

  *ioregsel = reg;

  return *iowin;

  where we don't want to the compiler to re-order the last two 'independent'

  read and write cause this re-ordering will imply different semantics to the

  programmed hardware.

  We use MMIO register accessors, which internally includes compiler barriers

  and any needed volatile qualifiers (See comments at top of include/mmio.h

  for further rational):

  uint32_t *ioregsel = (uint32_t *)ioapic_base(apic);

  uint32_t *iowin = (uint32_t *)(ioapic_base(apic) + 0x10);

  writel(reg, ioregsel);

  return readl(iowin);

* Finally, check attached LKML messages for extra cases and reasonings by Linus

  and Andi Kleen.

On the vaguely documented x86 16-bit protected mode:

----------------------------------------------------

* References:

  - Rick A. Hohensee, "The well-factored 386", LKML,

    http://lkml.org/lkml/2003/7/28/55, http://www.webcitation.org/5luRetOqF

  - Intel manuals vol3A, chapter 3, 3.4.3 - segment registers

  - Intel Manuals vol3A, chapter9, Processor Management and Initialization,

    9.9.2 - Switching Back to Real-Address Mode

  - Robert R. Collins, "The Segment Descriptor Cache", Dr. Dobb's Journal

    Undocumented Corner, http://www.rcollins.org/ddj/Aug98/Aug98.html,

    http://www.webcitation.org/5lxH9NFGa

* The x86 architecture determins the default operand and address size using

  the D bit in the code segment. If D is set, it indicates 32-bit addresses

  and operands. Otherwise, we're running in 16-bit mode, using 16-bit

  addresses and operands. There's a similar C bit for 64-bit long mode.

* One of the states that really puzzled me a lot was the state occurring in

  the transition from bootup real-mode to 32-bit protected mode. Namely,

  bewteen enabling protected mode (setting PE = 1) and getting executed in

  32-bit by using a 32-bit (D = 1) code segment through a far jump. Setting

  PE and %cs together is not atomic, and there's clearly something in-between.

  An example from our bootsector:

	/* Set the protected mode PE flag */

	movl   %cr0, %eax

	orl    $0x1, %eax

	movl   %eax, %cr0

	jmp    flush_prefetch:

	/* What're the rules covering this state? we're in

	 * pmode but the cpu is still fetching and executing

	 * ops in 16-bits! */

	flush_prefetch:

	movw   $(gdt_ds - gdt), %ax

	movw   %ax, %ds

	movw   %ax, %es

	movw   %ax, %ss

	DATA32 ljmp $0x08, $(reloc - _start + 0x7c00)

* To exhaustively think about this, we need to cover all the permuatations

  of PE (pmode enabled) and the %cs D bit:

  (1)   PE=0    Dbit=0          Canonical (un)Real Mode

  (2)   PE=1    Dbit=0          16-bit protected mode

  (3)   PE=1    Dbit=1          Canonical 32-bit Protected Mode

  (4)   PE=0    Dbit=1          ..

                         _______________

                        |    WAKE-UP    |

                        |canonical rmode|

                        |  PE=0 use16   |

                        |_______________|

                            A        |set PE to 1

                            |        |

                 set PE to 0|        |

                         ___|________V__

                        |     16-bit    |

                        |     pmode     |

                        |   PE=1 use16  |

                        |_______________|

                            A       |far xfer

                            |       | to use32 CS

                far xfer to |       |

                    use16 CS|       |

                         ___|_______V___

                        |     32-bit    |

                        |     pmode     |

                        |   PE=1 use32  |

                        |_______________|

                            A        |set PE to 0

                            |        |

                 set PE to 1|        |

                         ___|________V__

                        |  Forreal Mode |

                        |      Mode     |

                        |   PE=0 use32  |

                        |_______________|

* We can not jump from (1) to (3) directly through a far jump using a D=1 code

  segment, since we'll be in canonical rmode, and %cs will always be interpreted

  as in the segmented 8086 model of (%cs << 4 + offset).

  But how can the cpu move to 32-bit execution, if 32-bit execution is controlled

  by the D bit, but we can't change the D bit due to the 8086 semanticss?

  The answer is to provide a switch. If this switch is on, the cpu will the use

  the 386 semantics of segments (and be able to modify the segment caches). If

  it's clear, the cpu will still use the same segmentation circuites but it won't

  be able to modify most of the segment caches fields like limit, and the D bit,

  (the base field can still be changed within 2-bytes size), due to the

  constraints of the 8086 semantics.

  This 'switch' is the PE (pmode Enabled) bit, which acts __independently__ of

  whether the machine is running on 16 or 32-bit mode (D bit is set or clear)

  So under this 16-bit pmode (PE set, D clear), if we do:

	movw   $0x10, %ax

	movw   %ax, %ds

  we're in fact using %ds as a segment selector, and are also updating the

  segment caches with the values found in the third GDT cell.

  But if we're in canonical 16-bit rmode (PE & D clear), if we does the same:

	movw   $0x10, %ax

	movw   %ax, %ds

  we're in fact using (%ds << 4) as the base field in the segment caches.

* We cannot also jump directly from (3) 32-bit pmode, to cacnonical/bootup rmode

  at (1). One should change the code and data segmenst limit to 64K and the D bit

  to 0 __before__ clearing the PE switch: we can not change any of those segments

  cached fields (except the base) once the PE get cleared.

  Intel's "switching back to Real-Address mode" section also states the same

  order, but without making the reasoning of this order very clear.

  Intel also elaborates that "the segment registers must be loaded with non-null

  segment selectors or the segment registers will be unusable in real-address

  mode." Simply because the segment will be marked in the segment caches as

  invalid (P = 0), and as we learned from above, we won't be able to change any

  of those cached bits after clearing PE. Due to this cached P=0 bit, even the

  usual act in canonical rmode of changing the base within the 2-bytes limit

  won't be possible, rendering the segment as unusable, as this is their only

  effective action in 8086 semantics.

* Finally, the difference between 8086 and 386 segmentation is superficial. If