AOS - Lecture Notes Summary

Lecture Info

BAKERY/bakery.c

Modern Architectures

Scheduling

• Speculation

• Synchronization

Parallelism

Program Flow Speed

Pipeline

• Logical Stages

• Speedup Factor

• Breaks

RE: Pipeline Test

Lecture Info

Pipeline Conflicts

x86 History

• Intel 8086 (iAPX 86)

• Intel 80486 (i486)

• Intel Pentium Pro (1995)

OoOE Concepts

• Imprecise Exceptions

Tomasulo's algorithm

• Conflicts to manage

• Algorithmic ideas

  • Register Renaming

  • Reservation Stations

OoOE Architecture

OoOE Example

Hyper-Threading

Misc

• Microarchitecture

• CPUID

Lecture Info

Interrupts and OoOE

Exceptions and OoOE

• Exceptions Types

• Exception Handling

x86 Details

• Data Transfer

• Linear Addressing

Meltdown

• How it works?

• Why it works?

• PoC

• Cache Latency

• Side Channels

• Possible Fixes

Branch Prediction

• 1-bit Predictors

Lecture Info

Branch Prediction

• 2-Bit Predictors

• Beyond 2-Bit

• Indirect Branches

Spectre

• PoC

• RE: SIDE-CHANNEL-MEMORY-READS

• Cross-Context Attacks

• Possible Fixes

Loop Unrolling

Power Wall

Distributed Architectures

NUMA

Lecture Info

Cache Coherency

• Definition

• CC Protocols Basics

• CC Protocols Families

Bus snooping

• MSI

• MESI

False Cache Sharing

• RE: FALSE-CACHE-SHARING

ASM Inline

FLUSH+RELOAD

• RDTSC

• CFLUSH

• RE 1: FLUSH-AND-RELOAD

• RE 2: FLUSH-AND-RELOAD

• Do we need RDTSC?

• Cache Inclusiveness

Lecture Info

Memory Consistency

• Terminology

• Sequential Consistency

• Total Store Order

  • Store Bypass

x86 Memory Synch

• Memory Fences

• Serializing Instructions

• RMW Instructions

• gcc built-ins

• Trylock via CMPXCHG

• Active-Wait Barrier

Scalability

• Linearizability

Lecture Info

Scalability

• Linearizability

• Locks vs RMW

Non-Blocking Algorithms

• Lock-Freedom

  • Linked List

• Wait-Freedom

  • ARC

• Buffer re-usage

RCU

• Operations

• Kernel Space

• User Space

• RE: RCU

Vettorizzazione

• Processor Scheme

• Vectorization in x86

• C Intrinsics for SEE

• Memory Alignment

• RE: SSE

Lecture Info

Processori di Sistema

Schemi di Indirizzamento

• Indirizzamento lineare

• Segmentazione

• Segmentazione in uno spazio lineare

• Indirizzamento nei sistemi moderni

• x86 example

X86 Memory Access Modes

• Real mode (286)

• Protected mode (80386)

• Long mode (x86-64)

x86 Segment Tables

Segmentation vs Paging

The x86-64 revision

Ring Model

• Types of GATEs

• Ring Model in x86

Lecture Info

Segment Selectors in x86

x86 GDT Entries

• Accessing GDT entries

• GDT-AND-SEGMENTS/gdt.c

• Linux GDT on x86

Access Scheme

• GDT-AND-SEGMENTS/segments.c

• Segment Selectors Update Rules

Lecture Info

Task State Segment (TSS)

GDT Replication

Per-CPU Memory

Thread Local Storage (TLS)

• GDT-AND-SEGMENTS/thread-segment-management.c

x86-64 Control Registers

Interrupts and Traps

• x86 Control Flow Variations

• GATE Details for x86

Trap-Based On-Demand Kernel Access

• Conventional Method

• System Call Table

• Modificare la system call table

Lecture Info

Linux Versions

System call (software) Components

System Call Formats

• System Call Numerical Codes

• Macros to Trigger System Calls

• Manage Return Value of Syscalls

• Stub for Syscall with 6 Parameters

• Calling Conventions

  • ABI vs reality

  • i386 stack allignment

  • x86-64 stack allignment

Running Examples

• SYS-CALL/asm-terminal-echo.c

• SYS-CALL/sys-call-macro.c

Homework #1: TLS

• Requirements

• Solution

Lecture Info

INT 0x80 performance

Fast System Call Path

• sysenter/syscall

• sysexit/sysret

• Model Specific Registers

• The syscall() Construct

• SYS-CALL/sys-call-function.c

The System Call Table

• Limitations

• Structure (in i386)

Add a New System Call

• User Side

• Kernel Side

BASELINE-SYS-CALL-TABLE-HACKING/sys_call_table_hacker.c

• Utilizzo della System Map

• Codice kernel

• Compilazione

• Nota su kASLR

• Nota su write_cr0()

• Codice user

Lecture Info

Homework #2: SCTD

• Requirements

• Solution

Syscall Dispatcher

• Dispatcher for int 0x80 (kernel 2.4)

• Dispatcher for syscall (kernel 2.4)

  • swapgs instruction

• Dispatcher (kernel 4.17)

  • SYSCALL_DEFINE macros

  • PTI

Virtual Dynamic Shared Object (VDSO)

• Addr of VDSO

• SYS-CALL/vdso.c

SYS-CALL/fast-vs-slow-syscall.c

DUAL-SYSCALL-TABLE-HACKING/sys_call_table_hacker.c

Kernel Software Organization

• Kernel Compilation

  • Configuring the Kernel

  • Compilation steps

  • Role of initrd

• System Map

Lecture Info

Startup Tasks

BIOS e UEFI

• BIOS e MBR in x86

• UEFI

Kernel Start-Up Process

• Multi-Core Startup Process

• head.S

• __init Functions

• Botmem

• Memblock

• Addr Resolution

Modern RAM Organization

• numactl

Structure for Steady-State Memory Management

Directly Mapped Memory Pages

Lecture Info

Paging in x86 protected mode

• Page Table Structure in i386

Linux Paging vs i386

• Page Table Data Structures

Table Entries in i386

• i386 PDE entries

• i386 PTE entries

• Granularity and Procetion Bits

• Bit Masking in Linux

• Order of Flag Checking by Firmware

• Runtime Detection of Current Page Size

Kernel Page Table Expansion (Kernel 2.4/i386)

• pagetable_init()

Lecture Info

Physical Address Extension (PAE)

x86-64 Architectures

• Canonical Addresses

• Linux Address Space on x86-64

• 48-bit Addessing in x86-64

• PAGE-TABLE-AUDITOR/page-table-auditor.c

• Huge Pages for Users

L1 Terminal Fault (L1TF)

• L1TF and Virtualization

• Hardware Supported "virtual memory" Virtualization

Core Map

Lecture Info

Homework #3: VTPMO

Memory Management at Steady State

Memory Organization in UMA Architectures

Free Lists

• Buddy Allocator System

Dealing With NUMA machines

Releasing Boot Memory

Memory Allocation Contexts

Buddy-System API

Mem-Policy

• Mem-Policy API

• NUMA/numa-test.c

Lecture Info

Quicklists

• Quicklist Implementation

• Quicklist API

Logical to Physical Addr Translation

BUDDY-VS-PER-CPU-QUICK-LIST/allocators.c

SLUB Allocator

Kernel Page and TLB State

• Types of TLB Events

• TLB Flush Costs

• Linux TLB Flush APIs

Lecture Info

User/Kernel Interactions

• Flexisble Segmentation

• Constrained Segmentation

Per-Thread Memory Limits

User/Kernel Data Move API

• copy_to_user() timeline

Service Redundancy

Constrained Supervisor Mode

Kernel Masked Segfaults

RUNNING EXAMPLES

• message-exchange-service

• message-exchange-service-intermediate-buffering

Lecture Info

Linux Module Basics

• Requirements

• Who is Responsible?

Kernel Modules APIs

• Module Struct

• API for kernel <= 2.4

• API for kernel >= 2.6

• Common Parts

• Module Parameters

  • Pseudo-files Interface

  • Array as Module Parameter

• Loading/Unloading Modules

• Building A Kernel Object (.ko)

• Module Headings

• Management of usage_count

Kernel Exported Symbols

Dynamic Symbol Querying

PARAMETRIC-MESSAGE-EXCHANGE-SERVICE

Lecture Info

Kernel Probing

• kprobe Data Structure

• Kprobe Mechanism

  • Pre-handler

  • Post-handler

• Kprobe API

• Denial of Probing

Useful Macros

dmesg

• printk()

• Message Priority Levels

• Message Priority Treatment

• syslog()

Kernel Panic

RUNNING EXAMPLES

• RUNNING EXAMPLE #1

  • KPROBE-USAGE-EXAMPLE

  • KERNEL-FUNCTION-POINTER-EXHIBITION

• STDIN-KPROBE-INTERCEPTOR

Lecture Info

Homework #4

Homework #5

Tasks vs Processes/Threads

Time-Sharing With Work Deferring

• Reconciliation Points

• Top/Bottom Half Programminng

  • Implementation in Linux

Task Queues

• Pre-Defined Task Queues

• Task Queue Data Structure

• Task Queues API

• Reconciliation Points

• Limitations

SoftIRQ Architecture

• Tasklets

Lecture Info

SoftIRQ (Kernels > 2.5)

• SoftIRQ Entries

• SoftIRQ Workers

• Tasklet

• Tasklet API

  • tasklet_init()

Work Queues

• Original Work Queues API

• Work Queue Issues

• Concurrency Managed Work Queues

container_of() macro

Running Examples

• RE: TASKLET

• RE: WORK-QUEUS

Lecture Info

Timer Interrupts

• Timer Interrupts and CPU Reschedules

• Disable Timer Interrupts on Demand

Kernel Execution and Busy-Waiting

How Time is Measured in x86

• LAPIC-T Timer Interrupts

  • old-style (task queus)

  • new-style (softIRQ)

• High Resolution (HR) Timers

  • usleep()

  • HR-Timer Kernel API

Preemption Request

• Preemption API

• Per-CPU Variables

Thread Control Block (TCB)

• CPU-Dispatchability

Runqueue and Waitqueues

Sleep/Wait Kernel Services

Lecture Info

Thread Control Block (TCB)

• TCB Structure

• TCB Allocation

  • TCB in kernel < 2.6

  • TCB in 2.6 <= kernel <= 4.8

• Current Macro

• Thread States

Virtually Mapped Stacks

Run Queue (kernel 2.4)

Wait Queues (kernel 2.4)

• Wait Queues APIs

• Thundering Herd Effect

• Wait Queues and TCB Linkage Dynamics

Wait Event Queues (5.x style)

• Scheme for Interruptible Waits

RUNNING EXAMPLES

• CPU-POSITIONING-SWITCHING-SERVICE

  • module #1

  • module #2

• SLEEP-WAKEUP-QUEUE

  • sys_goto_sleep()

  • sys_awake()

Lecture Info

TCB and Memory Management

• vm_area_struct

Threads Identification

• PID Namespaces Scheme

  • Namespace Visibility

  • Namespace Implementation

• PID to task_struct Mapping

  • find_task_by_pid (old way)

  • find_task_by_vpid (new way)

Creation of Processes/Threads

• clone()

• do_fork()

RUNNING EXAMPLES

• O1-SLEEP-WAKEUP-QUEUE

• USLEEP

• VM-CHECKER

• VIRTUAL-PIDS

• NAMESPACES

Lecture Info

Thread Syncronization

• Semaphore API

• Spinlock API

• Read/Write Locks API

Linux Scheduler Logic

• Schedule Baseline Aspect

• POSIX Priority Scheme

• Lists Macro Facilities

Scheduler #1: Perfect Load Sharing

• scheduler()

• Goodness Value

  • mm and active_mm

  • Formula Used

• Epochs Management

• Overview

Scheduler #2: Load Balancing

• Main Characteristics

• Implementation Scheme

• Calcolo dei Ticks

• Static and Dynamic Priorities

• CPU-Scheduling API

• Explicit Stack Refresh

• Runqueue Structure

Lecture Info

Scheduer #3: Completely Fair Scheduling

• Basic Concepts

• VCPU Advacement

Kernel Threads

• arch_kernel_thread()

• Kernel Thread APIs

KT-STARTUP-SERVICE

Lecture Info

Single-Core Concepts

Issues with Multi-Core

Inter Process Interrupt (IPI)

Advanced Programmable Interrupt Controller (APIC)

• IRQ vs INT

• I/O APIC

Interrupt Descriptor Table (IDT)

• IDT Entries Usage in Linux

• Spurious Interrupts

• IDT Entries

  • x86 protected mode

  • x86-64

• IDT APIs

Trap/Interrupts Handlers

• Page Table Isolation

• Top-Level Interrupts Handlers

Lecture Info

IPI Usage

• IPI in Linux

• IPI API

• Sequentialization of IPIs

• Preemption Effects of IPIs

RUNNING EXAMPLES

• IDT-NEW-TRAP-INSTALLATION

• TRAP-BASED-CONTEXT-SWITCH

• IDT-NEW-TRAP-INSTALLATION-ON-SPURIOUS

• MASTER-SLAVE-SYNCH-AND-KERNEL-PATCHING

Lecture Info

File System Basics

• Virtual File System

• Example: True files

• Block Drivers and Char Drivers

superblock_read()

VFS Startup in LINUX

struct file_system_type

Linking RootFS

Data Structures for VFS

• struct vfsmount

• struct super_block

• struct dentry

• struct inode

Randomize Layout in Structs

Initializing the RootFS instance

• Process Working Directory and Root Directory

FS Mounting and Namespaces

Lecture Info

Threads e VFS

• Isolamento a grana fine

• struct fs_struct

File Descriptor Table

VFS API Layering

• Example #1: Path-based API

• Example #2: Data-structure based API

Device-Drivers Table

• Major Numbers

• Drivers a Istanza Multipla

• Minor Numbers

Oggetti di I/O

• mknod() system call

• Device Numbers in x86

• Block-device drivers

• Char-device drivers

MAJOR-MINOR-MANAGEMENT/baseline-char-dev.c

Lecture Info

DRIVER-CONCURRENCY/driver-concurrency.c

• dev_open()

• dev_release()

• dev_write()

• dev_read()

• init_module()

• cleanup_module()

• Esecuzione e Testing

BROADCAST-DEV/broadcast.c

Homework: PC

Note generali

• __register_chrdev()

Lecture Info

ioctl()

Final Part of Boot

RamFS /proc and /sys

• /proc

  • Struttura di /proc

  • Registrazione di /proc

  • proc API

• /sys

  • /sys API

• /proc vs /sys