Intro to ELF & Cache
Discussion 7
Concrete Scenario: A World Without ELF
1. Compiler A
Writes binary: code at offset 0x00
2. Compiler B
Writes binary: code at offset 0x40
3. Linker
Tries to combine them — no symbol table format agreed upon → FAILS
4. OS Loader
Doesn't know where main() is — no entry point field → CRASH
✓ ELF standardizes all of this: magic bytes identify the file, e_entry gives the start address, program headers tell the loader exactly what to map.
Schedule
Intro to ELF loading and ELF format
1. ELF header
a. Data composition
b. Loading process
c. MP3 struct
2. ELF sections
a. Data composition
b. Loading process
c. MP3 struct
3. ELF example
a. Linker and Loader
b. Segment vs Sections
c. Readelf inspection
Useful Links
ELF Header Spec
https://refspecs.linuxfoundation.org/elf/gabi4+/ch4.eheader.html
ELF Man Page
https://man7.org/linux/man-pages/man5/elf.5.html
Readelf Man Page
https://man7.org/linux/man-pages/man1/readelf.1.html
ELF Wikipedia Diagram
https://en.m.wikipedia.org/wiki/File:ELF_Executable_and_Linkable_Format_diagram_by_Ange_Albertini.png
UCI Homework (ELF)
https://ics.uci.edu/~aburtsev/238P/hw/hw3-elf/hw3-elf.html
Loading an ELF File
LOADING PROCESS
1 HEADER
THE ELF HEADER IS PARSED
THE PROGRAM HEADER IS PARSED
(SECTIONS ARE NOT USED)
2 MAPPING
THE FILE IS MAPPED IN MEMORY
ACCORDING TO ITS SEGMENT(S)
3 EXECUTION
ENTRY IS CALLED
SYSCALLS ARE ACCESSED VIA:
- SYSCALL NUMBER IN THE R7 REGISTER
- CALLING INSTRUCTION SVC
file
⇒
mem
p_offset→0x00
0x8000000→p_vaddr
ELF Header: Technical Details for Identification and Execution
Every ELF file starts with a fixed-size header. It is split into two logical parts:
7F 45 4C 46 01 01 00
02 00 28 00 01 00 00
B0 00 00 00 00 00 00
04 00 03 00 00 00 00
HEADER ½
Technical details for identification and execution
e_ident (magic/class/endian) • e_type (EXEC) • e_machine (ARM)
e_entry (entry point) • e_phoff / e_shoff (table offsets)
ELF
HEADER
01 00 00 00 00 00 00 00
00 00 80 00 00 00 80 00
90 00 00 00 90 00 00 00
05 00 00 00 04 00 00 00
PROGRAM HEADER TABLE
Execution information — used by the loader
p_type (LOAD) • p_vaddr (0x8000000) • p_filesz / p_memsz
p_flags (R|X) • p_offset (file offset)
PROG
HDR
TBL
ELF Header in Loading Process
FIELDS
VALUES
EXPLANATION
e_ident
EI_MAG
0x7F, "ELF"
CONSTANT SIGNATURE
EI_CLASS, EI_DATA
_____________
32 BITS, LITTLE-ENDIAN
EI_VERSION
1EV_CURRENT
ALWAYS 1
e_type
2ET_EXEC
EXECUTABLE
e_machine
28EM_ARM
ARM PROCESSOR
e_version
1EV_CURRENT
ALWAYS 1
e_entry
0x8000060
ADDRESS WHERE EXECUTION STARTS
e_phoff
0x40
PROGRAM HEADERS' OFFSET
e_shoff
0xB0
SECTION HEADERS' OFFSET
e_ehsize
0x34
ELF HEADER'S SIZE
e_phentsize
0x20
SIZE OF A SINGLE PROGRAM HEADER
e_phnum
1
COUNT OF PROGRAM HEADERS
e_shentsize
0x28
SIZE OF A SINGLE SECTION HEADER
e_shnum
4
COUNT OF SECTION HEADERS
e_shstrndx
3*
INDEX OF THE NAMES' SECTION IN THE TABLE
ELF Header in elf.h
FIELDS
VALUES
EXPLANATION
e_ident
EI_MAG
0x7F, "ELF"
CONSTANT SIGNATURE
EI_CLASS, EI_DATA
1ELFCLASS32, 1ELFDATA2LSB
32 BITS, LITTLE-ENDIAN
EI_VERSION
1EV_CURRENT
ALWAYS 1
e_type
2ET_EXEC
EXECUTABLE
e_machine
28EM_ARM
ARM PROCESSOR
e_version
1EV_CURRENT
ALWAYS 1
e_entry
0x8000060
ADDRESS WHERE EXECUTION STARTS
e_phoff
0x40
PROGRAM HEADERS' OFFSET
e_shoff
0xB0
SECTION HEADERS' OFFSET
e_ehsize
0x34
ELF HEADER'S SIZE
e_phentsize
0x20
SIZE OF A SINGLE PROGRAM HEADER
e_phnum
1
COUNT OF PROGRAM HEADERS
e_shentsize
0x28
SIZE OF A SINGLE SECTION HEADER
e_shnum
4
COUNT OF SECTION HEADERS
e_shstrndx
3*
INDEX OF THE NAMES' SECTION IN THE TABLE
Content of the Executable
CONTENTS OF THE EXECUTABLE
0D 20 A0 E3 14 10 8F
00 00 00 EF 01 00 A0
CODE
EXECUTABLE INFORMATION
48 65 6C 6C 6F 20 57
48 65 6C 6C 6F 21 00
Hello.World!....
DATA
INFORMATION USED BY THE CODE
00 2E 73 68 73 74 72
00 2E 74 65 78 74 00
SECTIONS' NAMES
.shstrtab .text .rodata
Content of the Executable
ARM ASSEMBLY
EQUIVALENT C CODE
mov r2, #13 ; MSG_LEN
add r1, pc, #20 ; msg (pc-relative)
mov r0, #1 ; STDOUT_FILENO
mov r7, #4 ; SC_WRITE
svc 0 ; system call
mov r0, #1 ; return code
mov r7, #1 ; SC_EXIT
svc 0 ; system call
write(STDOUT_FILENO, "Hello World!\n", len("Hello World!\n"));
exit(1);
STRINGS
"Hello World!\n", 0
SECTION NAMES
"" .shrtrtab .text .rodata
Content of the Executable in elf.h
p_type
1PT_LOAD
THE SEGMENT SHOULD BE LOADED IN MEMORY
p_offset
0
OFFSET WHERE IT SHOULD BE READ
p_vaddr
0x8000000
VIRTUAL ADDRESS WHERE IT SHOULD BE LOADED
p_paddr
0x8000000
PHYSICAL ADDRESS WHERE IT SHOULD BE LOADED
p_filesz
0x90
SIZE ON FILE
p_memsz
0x90
SIZE IN MEMORY
p_flags
5PF_R|PF_X
READABLE AND EXECUTABLE
Example: elf-hello-world
elf.c :
unsigned int main(int a, int b) {
return a + b;
}
Run:
$ make
$ readelf -a elf
The linker uses the Section Header Table,
and the loader uses the Program Header Table.
Entry Point
Program Header Table
Section Header Table
Executable
Read & Write
Read Only
.init (executable)
.text
.data (Writable)
.rodata (Read Only)
.got
Segments:
Used by the Loader
Sections:
Used by the Linker
Segment vs Sections
The parts of the ELF file used by the linker are called "Sections", and the parts used by the loader are called "segments".
Sections and segments do overlap. Typically, multiple sections (like .text and .init) are all contained in one executable segment (what the loader sees).
Same parts of the ELF file belong to one section AND one segment.
Confusing, huh? It will become clear soon.
Block Cache
Thread A
Thread B
│
▼
│
▼
cache_fetch() / cache_release()
CACHE (64 slots)
0
1
2
3
4
5
6
7
blk0 blk1 blk2 ... blk63
clean
in use
dirty
evictable_cnt · dirty_cnt · nidx (clock hand)
BACKING DEVICE (struct io)
Threads never talk to disk directly.
Every fetch must be paired with exactly one release.
Cache API
Functions you need to implement:
struct cache * create_cache(struct io * bkgio, unsigned long cache_blksz)
Creates a new cache backed by bkgio with the given block size.
blksz must be a multiple of the backing device's block size (we will always pass a blksz which is equal to the vioblk’s block size)— otherwise undefined behavior.
unsigned int cache_blksz(const struct cache * ca)
Returns the cache block size in bytes. Simple accessor — no locking needed.
int cache_flush(struct cache * ca)
Blocks the caller until every dirty entry has been written back to the device.
Returns 0 on success.
Every successful cache_fetch() must be paired with exactly one cache_release().
cache_fetch + cache_release
int cache_fetch(struct cache * ca, unsigned long long pos, int exclusive, void ** pptr)
Fetch the block at byte offset pos. On return, *pptr points to the block data.
exclusive
Determines whether to acquire a block exclusively.
pos
Must be aligned to blksz — otherwise returns -EINVAL.
returns
0 on success. *pptr is valid and the block is locked.
Caller must call cache_release() exactly once after a successful fetch. Also, we do not require that you support multiple concurrent readers; our tests will acquire a block as exclusive always, and you can do the same.
note
void cache_release(struct cache * ca, void * ptr, int dirty)
Release a previously fetched block.
dirty=1
Block is marked dirty — needs to be written back at some point.
dirty=0
Block is clean — no write needed. Entry can be evicted if no other threads fetched the block.
sequential trace — two threads
Thread A
fetch(pos=0)
→ MISS → iofetch from disk → slot 0, locked
Thread A
fetch(pos=4096)
→ MISS → iofetch from disk → slot 1, locked
Thread B
fetch(pos=0)
→ HIT — but A holds lock → waits on unlocked...
Thread A
release(pos=0, dirty=1)
→ marks dirty · unlocks · Thread B wakes up
Thread B
release(pos=0, dirty=0)
→ refcnt→0, still dirty, NOT evictable
Writeback
slot 0: refcnt=0, dirty=1
→ iostore() → disk → dirty=0
Thread A
fetch(pos=99999) [64 full]
→ MISS + full → clock sweeps → evicts victim
Example
How do we change this to a write-through cache?