Build Systems & Toolchain

Question 1

(a) [4]

• Preprocessing (1): #include/macro expansion; a missing solve.h (bad #include) fails here (fatal error: solve.h: No such file).
• Compilation (1): C → assembly; type/syntax errors here. solve used but undeclared → compile-time error (implicit decl warning in C).
• Assembly (1): asm → main.o object with solve as an undefined symbol in symbol table (UND entry + relocation).
• Linking (1): resolves solve. "undefined reference to solve" is emitted here, not earlier — the compiler trusts the declaration; only the linker knows no definition exists.

(b) [6]

• Linker processes inputs left to right, maintaining a set of currently-undefined symbols (2). When it meets an archive, it pulls in only those members that satisfy a currently-unresolved symbol (1).
• main.o -lsolve -lmath: after main.o, undefined = {solve, norm}. -lsolve pulls solve.o (defines solve; adds dot to undefined) → undefined = {norm, dot}. -lmath pulls math.o → resolves norm, dot. ✓ (1)
• main.o -lmath -lsolve: after main.o, undefined={solve,norm}. -lmath provides norm/dot, but dot isn't yet needed (solve not pulled), so math.o satisfies norm (pulled). Then -lsolve pulls solve.o which newly references norm, dot — but libmath was already passed and won't be re-scanned → undefined reference to 'norm'. ✗ (1)
• Fix (1): gcc main.o -lsolve -lmath -lmath (repeat) OR wrap in -Wl,--start-group -lsolve -lmath -Wl,--end-group.

(c) [6]

• PIC accesses norm not by absolute address but via the GOT (Global Offset Table): code loads the function address from a GOT slot; calls to external functions go through a PLT stub (2).
• Lazy binding: first call jumps to PLT stub → GOT still points back into PLT → invokes dynamic linker (_dl_runtime_resolve) which resolves the real address, patches GOT (1).
• Indirections (3): First call = PLT stub + GOT load (points to resolver) + resolver work → the address is resolved once (extra resolver cost). Subsequent calls = 1 extra memory indirection (GOT load) vs direct call. So: first call ≈ resolver overhead; steady state = 1 extra GOT indirection per call.

(d) [6]

• Static total = $Nc$. PIC total: one call pays resolver $r$ (once), every call pays $c+g$: $T_{PIC}(N) = r + N(c+g)$ (2). (Accept $r + (c+g) + (N-1)(c+g) = r+N(c+g)$.)
• Overhead relative to static $= T_{PIC} - Nc = r + Ng$ (1).
• Per-call ratio asymptote: $\dfrac{T_{PIC}}{Nc} = \dfrac{r+N(c+g)}{Nc} \to \dfrac{c+g}{c} = \dfrac{2+1}{2} = 1.5$ as $N\to\infty$ (1). So steady-state overhead ratio $\to 1.5$ (50% over static, from the GOT indirection).
• "Within 60%": need $\dfrac{r+N(c+g)}{Nc} \le 1.6$ (1). With $c=2,g=1,r=200$: $\dfrac{200+3N}{2N}\le 1.6 \Rightarrow 200+3N \le 3.2N \Rightarrow 200 \le 0.2N \Rightarrow N \ge 1000$. Smallest $N = 1000$ (1).

Question 2

(a) [8]

• (i) [3] $^ = all prerequisites (main.o solve.o math.o); $< = first prerequisite (the .c); $@ = target name (app or the .o).
• (ii) [3] Object rule depends only on %.c, not solve.h; changing solve.h does not trigger recompilation → stale object with old header → silently wrong. Fix: add header prerequisites, ideally auto-generated:

CFLAGS += -MMD -MP
-include $(OBJ:.o=.d)

(Accept explicit main.o solve.o: solve.h.)

• (iii) [2] Add .PHONY: clean. Mechanism: phony targets tell Make the target is not a file, so it always runs regardless of a same-named file/timestamp.

(b) [6]

cmake_minimum_required(VERSION 3.10)
project(app C)
set(CMAKE_C_STANDARD 17)
add_library(solve STATIC solve.c math.c)
add_executable(app main.c)
target_link_libraries(app PRIVATE solve)
target_compile_options(solve PRIVATE $<$<CONFIG:Debug>:-fsanitize=address>)
target_link_options(app PRIVATE $<$<CONFIG:Debug>:-fsanitize=address>)

(4 for correct structure/lib/link/standard, 1 for generator-expression config guard.) Explanation (1): CMAKE_BUILD_TYPE=Debug selects CMAKE_C_FLAGS_DEBUG (-g), Release selects -O3 -DNDEBUG; $<CONFIG:Debug> applies flags only in that config. target_link_libraries(... PRIVATE) propagates usage requirements (include dirs, defines) of solve to app but not transitively past app.

(c) [6]

• Toolchain [2]: aarch64-linux-gnu-gcc is a cross-compiler — runs on x86-64 but emits AArch64 machine code + uses the ARM64 assembler/linker.
• Sysroot [2]: --sysroot=/path/to/arm64/root redirects header (/usr/include) and library (/usr/lib) searches to the target's filesystem, not the host's.
• Why host lib wrong [1]: host libmath.so contains x86-64 code — link/load would fail (wrong ELF machine, wrong ABI/symbol versions). --sysroot guarantees ARM64 libmath.so + matching headers.
• ELF field [1]: e_machine = EM_AARCH64 (0xB7) vs host EM_X86_64 (0x3E).

Question 3

(a) [8]

• (i) [3] Loop condition i <= n iterates i = 0..n, i.e. n+1 accesses. Valid indices of a size-n array are 0..n-1. Access at i=n reads a[n], exactly one element (sizeof(int) bytes) past the end → out-of-bounds read. Proof: last legal index n-1 < n, so a[n] is beyond allocation.
• (ii) [3] ASan surrounds each heap allocation with redzones (poisoned bytes) tracked in shadow memory (1 shadow byte per 8 app bytes). Every load/store is instrumented to check the shadow; accessing a[n] lands in the redzone → shadow marks it poisoned → runtime reports heap-buffer-overflow READ of size 4.
• (iii) [2] UBSan (-fsanitize=signed-integer-overflow). Signed integer overflow is undefined behavior per the C standard (§6.5/5) because signed representation/overflow wraparound is not defined; compilers may assume it never happens (enabling optimizations), so it must be caught at runtime, not by ASan (memory) or TSan (data races).

(b) [6]

• (i) [2] counter++ decomposes into: load counter → register; add 1; store register → counter. Non-atomic: another thread can interleave between load and store, reading the stale value.
• (ii) [3] Max = $2k$ (perfectly interleaved without lost updates). Min = $2$ (with $k\ge1$). Proof of min: thread A reads 0, is preempted; thread B does all $k$ increments (counter = $k$); A finishes its remaining $k-1$ then writes back 1 (its stale load+adds accumulate to 1 on its held register only for the first, but the classic lost-update lower bound): the minimum is 2 — one thread reads 0 early and eventually stores 1; the other stores 1 last; every intermediate update from the interleaving-loser is overwritten. (Full marks for identifying max $=2k$, min $=2$ with the lost-update argument.)
• (iii) [1] TSan (Thread Sanitizer). Principle: tracks a happens-before relation via vector clocks / shadow memory of memory accesses; two accesses to the same location, at least one a write, with no ordering → reported data race.

(c) [4]

• lea (%rdi,%rdi,1),%eax: effective address = %rdi + %rdi*1 = 2*%rdi, stored (as computed value, not a load) into %eax (2). lea computes the address arithmetic without dereferencing (1).
• Therefore f(x) = 2*x (returns double the argument) (1).

[
 {"claim":"Q1d smallest N within 60% overhead is 1000","code":"c,g,r=2,1,200; import sympy as sp; N=sp.symbols('N',positive=True); sol=sp.solve(sp.Eq((r+N*(c+g)),sp.Rational(16,10)*N*c),N); Nmin=sp.ceiling(sol[0]); result=(Nmin==1000)"},
 {"claim":"Q1d asymptotic per-call overhead ratio is 3/2","code":"c,g=2,1; import sympy as sp; N=sp.symbols('N',positive=True); ratio=sp.limit((200+N*(c+g))/(N*c),N,sp.oo); result=(ratio==sp.Rational(3,2))"},
 {"claim":"Q3a off-by-one: i<=n accesses n+1 elements, index n out of bounds for size n","code":"n=5; accesses=[i for i in range(0,n+1)]; result=(len(accesses)==n+1 and max(accesses)==n and n not in range(0,n))"},
 {"claim":"Q3c lea (rdi,rdi,1) computes 2*x","code":"x=sp.symbols('x'); val=x + x*1; result=(sp.simplify(val-2*x)==0)"}
]