⚙️ OS 10: Compilation Pipeline, Low-Level CPU Execution, Hardware Puzzles & Kernel Architecture

Targeted for: Juspay Elimination Round, Systems Interview & Low-Level Technical Rounds
Key Focus: C/C++ compilation stages (Preprocessor $\to$ Compiler $\to$ Assembler $\to$ Linker $\to$ Loader), CPU execution cycles (Fetch-Decode-Execute), Assembly trace of integer addition, Array 0-indexing hardware proof, Kernel architecture (Ring 0 vs 3, Interrupts, Syscalls), and the 100-key keyboard matrix multiplexing puzzle.

📑 Quick Navigation

1. How C/C++ Source Code Becomes an Executable (Step-by-Step)
2. Compiler vs Interpreter: Deep Internal Mechanics
3. Why Does Array Indexing Start at 0? (Hardware & Mathematical Proof)
4. Adding Two Numbers: C Code to Low-Level CPU Processing & Assembly
5. Role & Architecture of the Operating System Kernel
6. Hardware Engineering Puzzle: Wiring a 100-Key Keyboard Cable

1. How C/C++ Source Code Becomes an Executable (Step-by-Step)

The transformation of human-readable C/C++ code into a running process in RAM involves a 5-phase toolchain pipeline: Preprocessing $\to$ Compilation $\to$ Assembly $\to$ Linking $\to$ Loading.

Phase 1: Preprocessing (cpp / gcc -E)

• Input: Source code files (.c, .cpp, .h).
• Commands Executed:
  1. Header File Inclusion: Replaces #include <stdio.h> or #include "my_header.h" with the exact textual content of the included header file.
  2. Macro Expansion: Replaces all #define MAX 100 occurrences with their literal replacement tokens.
  3. Conditional Compilation: Strips out blocks disabled by #ifdef, #ifndef, #elif, #endif.
  4. Comment Removal: Strips single-line (//) and multi-line (/* */) comments, converting them to single whitespace.
  5. Line Markers: Inserts line markers (e.g., # 1 "main.c") so the compiler can report accurate line numbers for warnings and errors.
• Output: Preprocessed source file (main.i for C, main.ii for C++).

Phase 2: Compilation Proper (cc1 / gcc -S)

Translates preprocessed C code into target-specific assembly code. Modern compilers (like GCC, Clang/LLVM) split this into three distinct sub-stages:

1. Frontend:
   • Lexical Analysis (Lexer/Scanner): Converts stream of characters into tokens (KEYWORD, IDENTIFIER, OPERATOR, LITERAL).
   • Syntax Analysis (Parser): Validates grammar against the C language specification (Context-Free Grammar). Constructs an Abstract Syntax Tree (AST).
   • Semantic Analysis: Performs type checking, verifies variable declarations, scope validation, and function signature matching.
2. Middle-End (Optimization on Intermediate Representation - IR):
   • Converts AST to target-independent IR (e.g., LLVM IR or GCC GIMPLE/RTL).
   • Optimizations applied:
     • Constant Folding & Propagation: int x = 3 + 4; $\to$ int x = 7;.
     • Dead Code Elimination: Removes code paths that can never execute.
     • Loop Invariant Code Motion (LICM): Hoists calculations outside loop bodies if their inputs never change inside the loop.
     • Function Inlining: Replaces function call overhead with the actual function body for small, hot functions.
3. Backend (Code Generation & Register Allocation):
   • Converts optimized IR into architecture-specific assembly language (x86_64, ARM64, or RISC-V).
   • Register Allocation: Uses Graph Coloring algorithms (Kempe's heuristic) to map infinite IR virtual registers to the CPU's limited physical registers (%rax, %rbx, %rcx, etc.). Spills excess variables onto the stack frame.

• Output: Assembly file (main.s).

Phase 3: Assembly (as / gcc -c)

• Input: Assembly file (main.s).
• Operation: Translates human-readable mnemonic instructions (mov, add, push, jmp) into raw binary machine code opcodes (0x89, 0x01, 0xE9).
• File Format: Generates an Object File formatted according to the OS standard:
  • Linux: ELF (Executable and Linkable Format - Relocatable .o).
  • Windows: PE/COFF (Portable Executable / Common Object File Format - .obj).
  • macOS: Mach-O.
• Internal Structure of an Object File (.o):
  • .text section: Compiled binary machine instructions.
  • .data section: Initialized global and static variables.
  • .bss section: Uninitialized global/static variables (reserves size only, zero bytes on disk).
  • .rodata section: Read-only data (string literals, const values).
  • Symbol Table: List of all functions and global variables defined in this file (exported) or needed from external files (imported).
  • Relocation Table: List of memory references that cannot be resolved yet because their final memory address depends on other object files.
• Output: Relocatable Object File (main.o).

Phase 4: Linking (ld / gcc)

The linker merges multiple .o files and pre-compiled libraries into a single executable binary.

1. Symbol Resolution:
   • Matches undefined external symbol references in one object file (e.g., call to printf or calculate_tax()) with their definitions in another object file or library (libc.so).
   • Detects undefined reference to 'xyz' (missing definition) or multiple definition of 'xyz' (duplicate symbol).
2. Relocation:
   • Merges identical sections from all input files (e.g., all .text sections merged into one contiguous .text segment).
   • Computes final runtime virtual addresses for every instruction and data item.
   • Patches placeholder addresses in code with real relative or absolute target addresses.
3. Static vs Dynamic Linking:
   • Static Linking (.a / .lib): The linker copies the actual machine code of library functions directly into the final executable.
     • Pros: Standalone binary, zero runtime dependency mismatch.
     • Cons: Bloated binary size, high memory footprint (cannot share library code across processes in RAM).
   • Dynamic Linking (.so / .dll): The linker inserts references to shared libraries rather than copying code.
     • Resolved at runtime by the dynamic linker (/lib64/ld-linux-x86-64.so.2).
     • Uses PIC (Position-Independent Code), GOT (Global Offset Table), and PLT (Procedure Linkage Table) to allow multiple running processes to share a single copy of libc.so in physical memory.

• Output: Executable file (a.out, my_app, or app.exe).

Phase 5: Loading & Execution (execve() / OS Loader)

What happens when you run ./my_app in the shell:

1. Shell calls fork(): Clones the shell process.
2. Child calls execve("./my_app", argv, envp):
   • Traps into Kernel Mode (Ring 0).
   • OS reads the binary header (ELF Magic bytes 0x7F 'E' 'L' 'F' or PE Magic MZ).
   • Tears down the old address space.
3. Creates Virtual Address Space:
   • Maps .text, .rodata as Read-Only + Execute (RX).
   • Maps .data, .bss as Read-Write (RW).
   • Sets up initial User Stack (grows downwards) and Heap (grows upwards via brk/mmap).
4. Loads Dynamic Interpreter: If dynamically linked, loads ld-linux.so, which loads dependent .so files into memory.
5. Initializes CPU Registers:
   • Pushes argc, argv, envp onto the user stack.
   • Sets Instruction Pointer (%rip on x86_64) to the entry point: _start in CRT (C Runtime library crt1.o).
6. C Runtime (crt0 / crt1):
   • Initializes thread-local storage, registers global destructors (atexit).
   • Calls __libc_start_main().
   • Calls user main(argc, argv).
7. Transition to User Space: CPU changes privilege level from Ring 0 to Ring 3. Your code is now executing!

2. Compiler vs Interpreter: Deep Internal Mechanics

Core Definitions

• Compiler: A program that translates source code written in a high-level language into machine code or bytecode all at once, before execution begins. The resulting output is stored on disk and executed independently by hardware or a virtual machine.
• Interpreter: A program that reads source code (or pre-compiled bytecode) and executes instructions directly, step-by-step, at runtime, without producing a separate machine-code binary beforehand.

Internal Workings of an Interpreter

A traditional interpreter runs a classic REPL / Dispatch Loop:

Why Pure Interpreters are Slower ($10\times - 50\times$ slower than C):

1. Instruction Dispatch Overhead: Every single virtual operation incurs branch prediction penalties, pointer indirection, and loop checks.
2. Type Checking at Every Step: In Python/JavaScript, a + b must inspect whether a and b are integers, strings, floats, or objects with custom __add__ overrides on every single iteration.
3. No Register Allocation: Everything is pushed and popped to/from an artificial software stack in RAM rather than fast CPU hardware registers.

Comprehensive Comparison Matrix

3. Why Does Array Indexing Start at 0? (Hardware & Mathematical Proof)

A classic interview inquiry at Juspay. The answer lies in hardware pointer arithmetic and mathematical range elegance.

1. The Hardware & Pointer Arithmetic Argument (C Language Heritage)

In low-level systems (C/C++ and assembly), an array variable arr is not an object with metadata. arr is simply a symbolic label representing the base memory address of the first element.

To access element at index $i$, the CPU computes: $$\text{Memory Address}(arr[i]) = \text{Base_Address} + (i \times \text{Size_of_Element})$$

Case A: 0-Based Indexing

• To access the 1st element ($i = 0$): $$\text{Address} = \text{Base} + (0 \times \text{size}) = \text{Base}$$
• To access the 2nd element ($i = 1$): $$\text{Address} = \text{Base} + (1 \times \text{size})$$
• In C syntax, arr[i] is defined syntactically as *(arr + i).
• Notice that the index $i$ represents the offset (displacement) from the base pointer.
• Hardware Instruction: The x86 CPU has a dedicated hardware addressing mode designed specifically for this:
  mov eax, [rbx + rdi * 4] ; rbx = Base Address, rdi = Index, 4 = sizeof(int)
  The hardware executes the index calculation in a single clock cycle without extra arithmetic!

Case B: If Indexing Were 1-Based

• If the first element were index 1, the address formula would become: $$\text{Memory Address}(arr[i]) = \text{Base_Address} + ((i - 1) \times \text{Size_of_Element})$$
• To access the element at index $i$, the CPU would be forced to execute:
  dec rdi ; Must subtract 1 from index first! mov eax, [rbx + rdi * 4] ; Then compute address
• Consequence: Every single array access in every loop would require an extra sub / dec machine instruction, wasting billions of CPU cycles globally across programs!

2. The Mathematical Elegance Argument (Edsger W. Dijkstra)

In 1982, renowned computer scientist Edsger W. Dijkstra published the classic paper: "Why numbering should start at zero" (EWD831).

Consider representing a sequence of natural numbers $2, 3, 4, \dots, 12$: There are 4 conventions to represent a range between $a$ and $b$:

1. $a \le i < b$ (Half-open, lower inclusive, upper exclusive)
2. $a < i \le b$
3. $a \le i \le b$ (Both inclusive)
4. $a < i < b$ (Both exclusive)

Dijkstra demonstrated that Convention 1 ($a \le i < b$) is mathematically superior because:

1. The number of elements in the range is simply $b - a$ (e.g., $2 \le i < 13 \implies 13 - 2 = 11$ elements). Under convention 3 ($a \le i \le b$), the count is $b - a + 1$, introducing artificial +1 terms everywhere.
2. Two adjacent sub-ranges can be joined seamlessly: $[a, b)$ and $[b, c)$ combine into $[a, c)$. The upper bound of the first sub-range equals the lower bound of the second.
3. When the range starts from the smallest natural number (0): $$0 \le i < N$$ The upper bound $N$ is identically equal to the length of the array!
   • 1-based indexing using inclusive ranges ($1 \le i \le N$) forces unnatural $-1$ corrections whenever computing offsets, strides, and multidimensional matrix mappings ($row \times cols + col$).

4. Adding Two Numbers: C Code to Low-Level CPU Processing & Assembly

High-Level Source Code (C)

x86-64 Assembly Code (Unoptimized GCC Output)

(Note: Under -O2 compiler optimization, the compiler eliminates stack allocations entirely via register allocation and constant folding, reducing the whole function to just: mov eax, 12; ret).

What Happens Inside the CPU Hardware (Clock Cycle by Clock Cycle)

The instruction add eax, edx represents raw machine code bytes 0x01 0xD0. Here is how the micro-architectural CPU pipeline executes it:

1. Instruction Fetch (IF):
   • The CPU's Program Counter (PC / %rip) holds the physical/virtual address of the instruction.
   • The instruction bytes (0x01 0xD0) are retrieved from the L1 Instruction Cache into the Instruction Register (IR).
   • PC is incremented to point to the next instruction.
2. Instruction Decode (ID):
   • The Control Unit decodes the opcode 0x01 (denoting integer ADD in x86).
   • Identifies source register edx and destination register eax.
   • Reads the 32-bit values from the Register File (edx = 5, eax = 7) onto internal CPU buses.
3. Execution (EX - ALU):
   • The Arithmetic Logic Unit (ALU) receives inputs $A = 00000101_2$ (5) and $B = 00000111_2$ (7).
   • A chain of Carry-Lookahead Adders (CLA) executes binary addition through hardware logic gates (XOR, AND, OR gates): $$\text{Sum Bit } S_i = A_i \oplus B_i \oplus C_i$$ $$\text{Carry Out } C_{i+1} = (A_i \cdot B_i) + (C_i \cdot (A_i \oplus B_i))$$
   • The ALU outputs the raw binary result: $00001100_2$ (decimal 12).
   • Updates the EFLAGS / Status Register:
     • ZF (Zero Flag) = 0 (result is non-zero).
     • CF (Carry Flag) = 0 (no unsigned overflow).
     • OF (Overflow Flag) = 0 (no signed overflow).
     • SF (Sign Flag) = 0 (result is positive).
4. Memory Access (MEM):
   • Register-to-register operations require no RAM/cache access. This stage is a no-op cycle (bypassed).
5. Writeback (WB):
   • The output value (12) is latched back into the destination register eax in the CPU register file.

5. Role & Architecture of the Operating System Kernel

What is the Kernel?

The Kernel is the core program of an Operating System that has complete, unrestricted control over everything in the system. It is the first software loaded into RAM during boot (after the bootloader like GRUB) and remains permanently resident in memory until shutdown.

Hardware Privilege Levels: Ring 0 vs Ring 3 (x86 Protection Rings)

• Ring 3 (User Space): Untrusted user code runs here. An invalid pointer access triggers a General Protection Fault (SIGSEGV) caught by the OS, terminating only that application without crashing the machine.
• Ring 0 (Supervisor / Kernel Space): The kernel and low-level drivers run here. A crash here results in a Kernel Panic (Linux) or Blue Screen of Death (BSOD) (Windows).

The 6 Core Responsibilities of the Kernel

1. Process & Thread Management (CPU Scheduling):
   • Creates and tears down processes (fork, execve, exit).
   • Maintains the Process Control Block (task_struct): tracks registers, PID, state, open file descriptors.
   • Manages CPU Scheduling via algorithms like the Linux Completely Fair Scheduler (CFS) using Red-Black trees.
   • Performs Context Switching (saving CPU registers of Process A, switching Page Table Base Register CR3, restoring registers of Process B).
2. Memory Management (Virtual Address Space):
   • Isolates process memory via Paging and multi-level page tables.
   • Manages physical RAM allocation, frame tables, and free memory lists.
   • Handles Page Faults (swapping pages from disk/SSD to RAM via demand paging).
   • Configures the hardware MMU (Memory Management Unit) and handles TLB (Translation Lookaside Buffer) invalidations / TLB shootdowns.
3. File System & Virtual File System (VFS):
   • Provides an abstracted POSIX API (open, read, write, close) over disparate physical storage devices (ext4, XFS, NTFS, NFS).
   • Manages disk caching (Page Cache, Buffer Cache) and inode management.
4. Device Drivers & Hardware I/O:
   • Acts as intermediary between hardware chips and software.
   • Handles Hardware Interrupts:
     • Top Half (Hard IRQ): Acknowledges the hardware immediately and masks interrupts (runs in microseconds).
     • Bottom Half (SoftIRQs / Tasklets / Workqueues): Processes heavy data (e.g., copying network packets from NIC DMA buffers) asynchronously.
   • Manages DMA (Direct Memory Access) engines so hardware can transfer data to RAM without wasting CPU cycles.
5. System Call Interface (Syscalls):
   • Mediates access whenever user-space applications need hardware access (disk, screen, network).
   • User program loads syscall number into register (%rax), sets arguments, and executes syscall instruction. CPU switches hardware context from Ring 3 to Ring 0.
6. Network Subsystem:
   • Implements the complete TCP/IP network stack inside the kernel (sk_buff packet structures, routing tables, TCP state machines, socket buffers, firewall rules via Netfilter/iptables).

Monolithic Kernel vs Microkernel

6. Hardware Engineering Puzzle: Wiring a 100-Key Keyboard Cable

Interview Question: "You are designing a keyboard with 100 keys. How many physical wires must the cable contain to connect it to a computer?"

This is a classic systems and hardware reasoning question asked at Juspay. A candidate who answers "101 wires" fails the interview. The optimal answer requires evaluating 4 distinct engineering architectures:

Architecture 1: Naive Direct Connection (101 Wires)

• Concept: Connect 1 wire to each individual key switch, plus 1 common Ground wire.
• Wire Count: $100 + 1 = \mathbf{101\text{ wires}}$.
• Why it fails: A 101-wire cable would be thick as a garden hose, extremely stiff, fragile, and prohibitively expensive.

Architecture 2: Key Matrix Multiplexing (20 Wires)

Instead of wiring keys independently, organize the 100 keys into a two-dimensional Row $\times$ Column Grid (Matrix).

$$\text{Total Keys} \le \text{Rows} \times \text{Columns}$$ To minimize total wires ($R + C$) for a given product $R \times C \ge 100$: By the Arithmetic Mean-Geometric Mean inequality (AM-GM), $R + C$ is minimized when $R = C = \sqrt{100} = 10$. $$\text{Number of Wires} = 10 \text{ Rows} + 10 \text{ Columns} = \mathbf{20\text{ wires}}$$

How Matrix Scanning Works:

1. The computer (or controller) sets all 10 Column pins as Inputs with internal pull-up resistors (reading logic HIGH / 1 by default).
2. The controller drives Row 0 LOW (0V) while leaving Rows 1–9 HIGH (or high-impedance).
3. If Key at (Row 0, Col 3) is pressed, it shorts Col 3 to Ground, pulling Col 3 LOW. The controller registers key (0, 3).
4. The controller cycles through Rows 0 to 9 in sequence (typically 1,000 times a second / 1 kHz polling rate).

• The "Ghosting" Problem: When 3 keys forming a rectangle are pressed simultaneously, current sneaks backward, registering a 4th phantom key press ("ghost key").
• Solution: Place a small diode in series with every single key switch (enabling Full NKRO - N-Key Rollover).

Architecture 3: Charlieplexing (11 Wires)

Using microcontroller pins that support Tri-State Logic (HIGH, LOW, HIGH-IMPEDANCE / INPUT), Charlieplexing allows $N$ pins to address: $$\text{Addressable Keys} = N \times (N - 1)$$ To accommodate 100 keys: $$N(N - 1) \ge 100 \implies 11 \times 10 = 110 \ge 100$$

• Wire Count: Only 11 wires!
• Trade-off: Requires complex back-to-back diode arrangements on every key and higher software scanning complexity.

Architecture 4: Real-World Commercial Standard — Onboard Microcontroller with Serial Bus (4 Wires!)

In real commercial engineering, the raw matrix is not exposed to the external cable.

1. The keyboard case contains an inexpensive 8-bit microcontroller (e.g., Intel 8051, ATmega32U4, or STM32 ARM Cortex-M0 costing < $0.50).
2. The microcontroller connects to the internal 10x10 matrix using short PCB copper traces.
3. The microcontroller scans the matrix, applies software debounce (filtering out mechanical switch chatter over 5ms), and transmits key event packets over a standard Serial Cable:

🎯 Summary Matrix: The Perfect Spoken Answer for Juspay

When asked this in the interview, structure your answer hierarchically:

1. "If we connect raw switches directly without internal electronics, a $10 \times 10$ matrix multiplexer requires 20 wires (10 row wires + 10 column wires with anti-ghosting diodes)."
2. "Using Charlieplexing with tri-state logic pins, we can mathematically drive 110 keys using just 11 wires ($11 \times 10 = 110$)."
3. "However, in production system design, keyboards contain an onboard MCU that translates matrix scans into serial packets. Thus, the external cable connecting the keyboard to the computer needs only 4 wires for USB ($VCC$, $GND$, $D+$, $D-$) or PS/2."