Info

Übungen

timestamp 20250917

install work enviroment on Linux Arch/Manjaro:

sudo pacman -S base-devel flex bison

bitwise operations -> 10% of exam!

  • don’t do bitwise operations on signed types
  • signed type bitshift is undefined -> cast first to unsigned

common bitwise functions:

// check equality
return !(x^y);
// negative number
return ~x + 1;
// min two's complement (32bit)
return 1 << 31;
// bitwise not on 0:
// because ~0 = ~000000 = 111111 = -1
~0 = -1

timestamp 2025-09-24

Avoid including the same file multiple times with header guards:

#ifndef HEADER_FILE
#define HEADER_FILE
 
// the entire header file
 
# endif // HEADER_FILE

system include files can be found in /usr/include

timestamp 2025-10-22

cmpq %rax, %rbx
jg X

=> jumps if %rbx > %rax
  • the unusual way around!

  • important jg = signed and ja = unsigned

  • learn jumping instructions (logic)

  • purple: return
  • red: caller saved (stack pointer, base frame pointer + 2 scratch register) <- use this
  • blue: caller saved (parameters) <- use this
  • green: callee saved (scratch)

for callee-saved: one needs to restore value after using

pushq %r12       # save original value
...
popq %r12        # restore original value

inline assembly:

int a=10, b;
__asm__ ("movl %1, %%eax; movl %%eax, %0;"
		:"=r"(b) // output operands, optional
		:"r"(a)  // input operands, optional
		:"%eax"  // list of clobbered registers, optional
);

or named:

int a=10, b;
__asm__ ("movl %[in], %%eax; movl %%eax, %[out];"
		: [out] "=r"(b) // output operands, optional
		: [in]  "r"(a)  // input operands, optional
		:"%eax"  // list of clobbered registers, optional
);

of course, it can be simplified:

int a=10, b;
__asm__ ("movl %[in], %[out]"
		: [out] "=r"(b) // output operands, optional
		: [in]  "r"(a)  // input operands, optional
);

if no variable changes, use volatile to prevent the compile from deleting it!

__asm__ volatile ("movb %bh (%eax)\n\t"); // \n\t for multiple instructions needed, here optional

timestamp 2025-11-05

symbols

  • global: functions, global variables

  • local: static vars,

  • strong: function, initalized globals

  • weak: unitalized globals

  • multiple strong symbols are not allowed (linker error)

  • s.t. we know which one to use (1x strong, 1x weak -> use strong) - this happens even if the weak/strong are not of same type!!

-> modern C: always mark extern (and -fno-common flag) s.t. there is no arbitrary choosing

libraries

static libraries (.a)

  • multiple obj files in one file
  • when compiling, always put static libraries at end

dynamic libraries


append library path:

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$PWD
  • static and dynamic libraries use the same amount of memory (since dynamic -> headers included)
  • #include "sth.c" -> preprocessor copies file

32-bit PC-relative displacement

A 4-byte signed number stored in the instruction that tells the CPU how many bytes to jump forward/backwards from the next instruction. (PC = Program Counter = %rip on x86)

e.g.

400406: e8 f5 00 00 00 callq 400500 <swap>
  • current instruction: e8 (call) at 0x400406
  • next instruction (where the %rip pointer points to): 0x400406 + 5 = 0x40040b
  • displacement (signed, little-endian): f5 00 00 00 -> 0xf5
    • jump to %rip + 0xf5 -> 0x400500

CPU doesn’t know the symbol name (swap), it only sees the displacement

This comes from how the program is created:

  1. the compiler doesn’t know swap’s final address -> writes instruction + placeholder, e.g. e8 00 00 00 00 and adds a relocation entry
  2. the linker assigns final addresses to all functions, computes displacement:
    • displacement = next_address (%rip) - next_instruction_address
  3. the CPU executes callq at 0x400406, reads displacement, jumps to right place
  4. disassembly: objump read instruction, computes target address and names after the symbol table ->
    • callq 400500 <swap>

timestamp 2025-11-26

  • read-read: can be parallelised
  • read-write: too
  • write-write: can be problematic, but this too
  • write-read: -> problem

  • lower bound: CPE is bound by critical path
  • tell the compiler that for the lifetime of the restrict-annotated pointer it will be the only pointer used to access the underlying memory
    • compiler does not check, programmer responsible exection (no run-time checks that it is the only pointer)

timestamp 2025-12-03

direct mapped one line per set

timestamp 2025-12-10

write-through

  • every time when write -> update value in memory (“write through cache to memory)

write-back

  • only write to cache, update memory when other CPU try to access to memory
  • often used today

MSI

  • M - modified: newest state, can read/write, but everywhere else outdated
  • S - shared: newest state but also on other CPU caches, can read but have to write carefully
  • I - invalid: not in cache or outdated

-> each cache line has a state (additional metadata)

local (processor) transitions:

remote (snooped) transitions

MESI

  • add exclusive state: newest state, and no one else has it + less state changes than ESI - need to write back dirty data (no cache-cache transfer)

  • state machine: