System Programming - Lecture 3, v3 - Memory: cache, physical, virtual

Summary

The lecture explains how memory is organized from the processor through virtual memory and heap allocation, and how that organization affects program performance and security. Its central theme is that memory is layered: faster storage is closer to the CPU but smaller, while larger storage is slower. Understanding these layers helps programmers reason about data layout, cache behavior, memory access, and performance.

1. Memory Hierarchy and CPU Registers

• A typical hierarchy runs from registers to CPU cache, main memory (RAM), and persistent storage such as flash or magnetic disks.
• As you move down the hierarchy, capacity generally increases while access speed decreases.
• Registers are the fastest storage, but they are physically part of CPU cores and very limited in number. They cannot be upgraded or replaced.
• The lecturer describes registers as tiny electronic memory elements. They are used directly in assembly and indirectly by compiled programs. General-purpose registers also help with tasks such as passing function or system-call arguments.

2. CPU Caches: Purpose, Locality, and Organization

Why Caches Exist

CPU cores became much faster than main memory, creating a bottleneck: processors could spend many cycles waiting for data. A cache is a small, fast layer between registers and main memory. The CPU checks the cache first; if the requested data is absent, it is fetched from a slower cache level or from RAM.

Cache effectiveness relies on two kinds of locality:

• Temporal locality: Recently used data or instructions are likely to be used again, as in a loop.
• Spatial locality: Nearby data is likely to be used soon, as when reading a buffer sequentially or accessing nearby structure fields.

Cache Levels and Policies

CPUs commonly have multiple cache levels. The first level is often separated into instruction and data caches, while later levels may combine them. Cache levels differ in capacity and speed. Larger caches can take longer to search and may be physically farther from the processor, so multiple levels balance speed and capacity.

The lecture compares three ways cache contents can be coordinated across levels:

• Inclusive: Data in a higher-level cache is also kept in the next level. The system must maintain this relationship when data is added or evicted.
• Exclusive: Levels hold distinct data. Data evicted from a faster level can be moved to a slower cache level.
• Neither inclusive nor exclusive: Levels may overlap, but they are not required to contain identical or entirely separate data.

For writes, the lecture contrasts two policies:

• Write-through: Propagate a write through cache levels to main memory immediately. This can be slow.
• Write-back: Update the cache first, mark the line as dirty, and write it to memory later when it is evicted. This avoids waiting for every write to reach RAM.

Cache Lines and Mapping

Caches generally move data in cache lines, not as individual bytes. The lecture uses 64 bytes as a common example, while noting that the exact size depends on the system. As a result, accessing one byte may bring its entire cache line into the cache.

The lecture presents three broad approaches to placing memory blocks in a cache:

• Fully associative: A block can go in any cache location. This is flexible but costly to search and implement.
• Direct-mapped: Each block has one possible cache location. Lookup is simple, but blocks that map to the same location can repeatedly evict one another.
• Set-associative: A block can go in one of a limited number of locations in a set. This is a compromise between lookup cost and flexibility.

Increasing associativity can reduce misses, particularly in smaller caches, but has diminishing benefits and adds hardware cost.

3. Instruction Pipelines, Prediction, and Cache Coherence

Instruction Execution and Speculation

Instructions pass through pipeline stages that broadly include fetching, decoding, execution, memory access, and writing results back. Different instructions can occupy different stages simultaneously.

Conditional branches can make it unclear which instructions should execute next. Processors use branch prediction to begin work on a likely path before the condition is fully known. If the prediction is wrong, speculative work is discarded, causing a branch misprediction penalty. Predictable branches are generally easier for processors to handle than branches whose outcomes vary frequently.

Multiple Cores and Cache Coherence

With multiple CPU cores, each core may have its own cache. If one core changes data that another core has cached, the system needs a way to keep the copies consistent.

The lecture introduces the MESI protocol, whose cache-line states are:

• Modified: Changed in this cache and not shared as a current copy elsewhere.
• Exclusive: Present only in this cache and not modified.
• Shared: Potentially present in multiple caches and not modified.
• Invalid: The line does not contain valid data.

Some state transitions require other cores to be notified and their copies invalidated. These coordination steps can be expensive.

False Sharing and How to Reduce It

False sharing occurs when threads access different variables that happen to occupy the same cache line. The program may be logically correct, yet cache-coherence traffic can make it slow.

The lecture suggests several ways to reduce false sharing:

• Place frequently modified data used by different threads in separate cache lines.
• Add padding where appropriate, rather than placing independently updated fields close together.
• In C++, consider alignment facilities such as alignas or hardware interference-size constants where supported.
• Watch for false sharing between separate objects in arrays as well as between fields in a single structure.

4. Meltdown and Cache Side Channels

The lecture uses the Meltdown vulnerability to illustrate that cache behavior can have security consequences. Its example describes speculative execution and a timing side channel: even when a program is not permitted to read a protected value directly, speculative activity may affect which data ends up in the cache. Measuring access times can then reveal information indirectly.

The example also notes that a process can handle a segmentation-fault signal and continue, helping explain how a fault might be incorporated into an attack demonstration.

The lecture presents kernel-address randomization and KAISER/KPTI-style isolation as defenses against attacks that rely on kernel memory being mapped into a process’s address space. These approaches make kernel memory harder to locate or remove most kernel mappings from user-space address spaces.

5. Main Memory (RAM)

The lecture contrasts SRAM, used for CPU caches, with DRAM, commonly used for main memory. DRAM stores bits using a transistor and capacitor, allowing comparatively compact memory, but the capacitor’s charge leaks and must be refreshed periodically.

Main memory is slower than on-chip cache in part because it is a separate device accessed through controllers and a bus. The programming lesson is not that developers control these hardware details directly, but that they should account for the cost of memory access and favor useful data locality.

6. Virtual Memory, the MMU, and Page Tables

Processes work with virtual addresses rather than directly addressing physical RAM. This gives each process an isolated address space and hides many details of the hardware and other processes.

The memory management unit (MMU) translates virtual addresses to physical addresses in hardware, so translation can happen during ordinary memory accesses without a system call each time.

Memory is divided into pages. An address can be viewed as a page number plus an offset within that page; translation maps the virtual page number to a physical page number. Storing a complete page mapping in a simple hardware table would be too large and expensive, so the lecture describes storing the full mapping in memory using multi-level page tables, which the kernel maintains.

To make common translations fast, the MMU uses a small cache called the TLB (translation lookaside buffer). A TLB hit supplies the physical page mapping quickly; on a miss, the system consults the page tables.

When different processes use the same virtual address for different physical memory, an address-space identifier can distinguish their TLB entries. The kernel updates the relevant identifier when switching between processes.

Memory mappings can be established on demand. A large virtual allocation, such as a stack, need not immediately consume an equally large amount of physical memory; physical pages can be supplied as the memory is first used. The kernel also has its own address space. The lecture connects how kernel memory is mapped—and later isolated more strictly—to both performance and security.

7. Practical Programming Guidance

The lecturer’s general advice is to understand the memory hierarchy and optimize only where measurement shows a real need. Suggestions include:

• Keep related data near each other to improve locality.
• Choose structure layouts carefully; smaller structures and nearby fields can reduce the number of cache lines needed.
• Avoid false sharing between threads.
• Avoid unnecessary system calls and batch work where practical.
• Use predictable control flow where appropriate; consider whether a frequently mispredicted branch is worth retaining.
• Use compiler or operating-system hints, such as prefetching or memory-advice facilities, only when appropriate to the platform and workload.
• Treat heap allocation as potentially expensive. Reduce allocation overhead by batching allocations, reusing memory, or testing a heap implementation suited to the workload.
• Benchmark before adopting an optimization. The lecture gives example access-time figures and a cache-speedup calculation as illustrative estimates, not universal hardware guarantees.

8. Heap Allocation and Memory APIs

Stack, heap, and memory-mapping facilities are abstractions built on virtual memory.

The lecture describes mmap as a flexible way to map memory, including mappings backed by files. It also discusses brk as a historical way to extend the heap.

malloc and C++ new are library-level allocation mechanisms. They may reuse memory already obtained by the allocator or request more memory from the kernel when necessary; they are not necessarily system calls on every allocation.

Heap allocators divide larger memory regions into smaller blocks and manage their reuse. The lecture mentions slab-style allocation as one possible approach. For performance-sensitive applications, allocation patterns and alternative allocator implementations may matter; the lecturer recommends measuring rather than assuming a replacement will help.

9. Homework

Write a simplified command-line shell. The assignment covers a subset of shell features rather than a complete shell:

• Support passing arguments to commands.
• Support connecting commands with pipes.
• Support redirecting command output to a file.
• Use the provided command parser, so the assignment focuses on implementing shell behavior rather than building a parser from scratch.

Optional extensions include logical operations and background execution. The lecturer estimates roughly 300 lines of code as a typical scale for the task, while emphasizing that the conceptual complexity may be greater than the line count suggests.

Speakers and Sources Featured

• Speaker: The lecturer and course presenter; no name is given in the subtitles.
• Course slides: Referenced throughout the lecture, including slides with diagrams and assignment information.
• World Constants: A benchmark and measurement collection described as having a 2022 update extending earlier 2012 work; the lecturer says it can be found on GitHub.
• Other technical references: CPU cache and memory hardware, MESI cache coherence, Meltdown, KAISER/KPTI, and compiler or operating-system facilities such as mmap, getpagesize, sysconf, __builtin_prefetch, madvise, and C++ alignment features.