●​ Void * sbrk(increment)

●​ int brk(void* addr);

○​ Returns 0 if successful and -1 if not
○​ Sets errno to indicate error
Error handling in C
●​ Error handling for many standard library functions is done through two key compentns:
errno and perror
●​ What is errno?
○​ Errno is a global variable defined in the <errno.h> header file
○​ Used to idnicate the error code when a function fails
○​ Many standard library functions (like open, read, write, malloc, etc.) set errno to a
specific value when they encounter an error
○​ If a function fails, it typically sent errno to a predefined code which can be used to
understand what went wrong
○​ Thread-safe: in multi threaded programs, errno is implemented per thread to
avoid conflicts between threads
○​ strerror(errno) - converts errno to a readable string

○​
●​ What is perrror?
○​ Function define din <stdio.h>
○​ Prints an error message to standard error, describing the last error that occurred
based on errno
○​ Void perror(const char *s)
■​ S is a user defined string that’s prefixed to the error message
●​ Malloc interacts with the operating system through system calls
●​ Sbrk and brk are traditional UNIX system calls for managing program break
●​ Brk
○​ Sets The break pointer which marks the end of the heap
○​ Int brk(void* addr)
○​ Parameters:
■​ Addr: A pointer to the new end of the heap
○​ Returns
 ■​ 0 on success
■​ -1 on failure (Sets errno)
○​ Heap is a contiguous block of memory that starts just after the program’s data
segment
○​ Brk moves the program break directly to the specific addr, expanding or shrinking
the heap accordingly
○​ If the request address exceeds system limits or it overlaps with other segments, it
fails
■​ void* current_break = sbrk(0); // Get current program break
●​ Sbrk
○​ Adjusts the program’s break pointer by a specified increment (amount to increase
or decrease the program break)
○​ Moves program break up or down by the increment value
○​ Internally calls brk to adjust the pointer
○​ Returns:
■​ Previous break pointer on success
■​ Failure: (void*) -1 on failure (sets errno).
○​ sbrk(0) - used to get the current program break
●​ Malloc
○​ Allocates a block of memory on the heap
○​ void* malloc(size_t size);
○​ Parameters:
■​ Size: number of bytes to allocate
○​ Returns:
■​ Pointer to the allocated memory block
■​ NULL if the allocation fails
○​ Malloc uses brk and sbrk to allocate memory on teh heap
○​ It manages a memory pool and returns a block from this pool
○​ The memory is uninitialized so the contents of the allocated block are undefined
○​ Pointers:
■​ Always check if malloc returned null
■​ Memory allocated with malloc should be freed using free to avoid memory
leaks
○​ Free
■​ Deallocates memory rpevously allocated by malloc, calloc, or realloc
■​ void free(void* ptr);
■​ Parameter = pointer to memory block to be freed
■​ Behavior:
●​ Memory becomes available
●​ Memory allocator strategies
○​ First Fit
■​ Search for first block >= requested size and put block in there but this can
lead to fragmentation
○​ Best Fit
 ■​ Search for the smallest block >= requested size
●​ Less fragmentation but slower
○​ Worst Fit
■​ Search for largest block
●​ Good for splitting, poor memory utilization
●​ Strcpy, strcat, strncpy, strncat, strtok
●​ int compare(const void* a, const void* b) {
●​ return (*(int*)a - *(int*)b);
●​ }
○​ Result determines the relative order of the two elements (negative value: a < b;
positive value: a > b; zero a= b)
○​ Used with qsort which sorts arrays:
■​ void qsort(void* base, size_t num, size_t size, int (*compare)(const void*,
const void*));
●​ Error handling
○​ // Return value error checking
○​ FILE* file = fopen("data.txt", "r");
○​ if (file == NULL)
■​ { perror("Error opening file");
■​ return 1; }
●​ Introduction to GCC
○​ GCC: A robust, open source compiler system that support multiple programming
languages
○​ Used primarily on linux/unix
○​ Compiles code into machine-readable executables
○​ Supports optimizations, warnings, debugging, and linking with libraries
●​ Basic Compilation with GCC
○​ gcc -o output_file source_file.c
■​ -o output_file: specifies the name of the output file
■​ Source_file.c: the C source code to compile
■​ Ex.
●​ Gcc -o hello hello.c
■​ If you don’t specify -o, GCC outputs the executable as a.out
●​ Compilation without linking
○​ Use -c to generate an object file (.o) from a source file without linking (useful for
separating compilation and linking stages, especially for larger projects)
●​ Include Paths for header files
○​ Use -I to specify directories containing header files
○​ Ex. for a project structure like this:
■​ project/
■​ ├── src/
■​ │ ├── main.c
■​ │ ├── functions.c
■​ ├── include/
 ■​ ├── functions.h
■​
○​ Compile as shown:
■​ Gcc -I include -o program src/main.c src/functions.c
●​ LInking with libraries
○​ Use -L to specify the directory containing libraries and -l to link a specific library
○​ Example project structure:
■​ project/
■​ ├── src/
■​ │ ├── main.c
■​ ├── libs/
■​ │ ├── libmylib.a
■​ ├── include/
■​ ├── mylib.h
■​
○​ Compile with:
■​ gcc -Iinclude -Llibs -o program src/main.c -lmylib
■​ -lmylib: links libmylib.a
●​ Use -Wall to enable all common warnings, which help detect potential issues
○​ gcc -Wall -o program program.c
●​ Use -g to include debugging symbols for tools like gdb
○​ gcc -g -o program program.c
●​ Optimizations -0 followed by a number to control optimization levels
○​ -O0: No optimization (useful during debugging).
○​ -O1: Minimal optimization.
○​ -O2: Default optimization for speed.
○​ -O3: Maximum optimization for speed.
●​ Compile and link multiple files together
○​ gcc -o program file1.c file2.c
●​ Or you can separate compilation and linking:
○​ Compile each file:
■​ gcc -c file1.c
■​ gcc -c file2.c
○​ Link the object files:
■​ gcc -o program file1.o file2.o
●​ Use the linker (ld)
○​ Ld is the linker GCC invokes internally. Use it directly for:
■​ Fine control over linking
■​ Skipping redundant calls to gcc
■​ gcc -c main.c # Creates main.o
■​ gcc -c helper.c # Creates helper.o
■​ ld -o program main.o helper.o
Advanced example:
Given the project structure:
project/
├── src/
│ ├── main.c
│ ├── functions.c
├── libs/
│ ├── libmylib.a
├── include/
│ ├── functions.h

Gcc - I include -c src/main.c main.o

Gcc - Include -c src/functions.c functions.o
Gcc -Llibs -o program main.o function.o -lmylib
./program

Understanding Linking
●​ What is linking
○​ Linking is the step after compilation where
■​ The object field generated during compilation are combined
■​ External symbols are resolved
■​ Libraries are included to provide additional functionality
○​ Static linking
■​ Libraries are included directly in executable (results in larger executables
w/o dependency on external library files)
 ○​ Dynamic linking
■​ Libraries are not included in the executable but are linked at runtime
■​ Result in smaller executables and allows sharing of libraries among
multiple programs
○​ Ld
■​ Command that’s a low level linker used to combine object field and
libraries into an executable
■​ While gcc autoamtes linking internally, ld provides control over the
process
○​ Key concepts:
■​ Undefined symbols may be resolved during linking (external function
calls)
■​ Object files: contain machine code and symbol information
■​ Produced using the -c flag in gcc
■​ Librairies; .a (archive of object field)
■​ .so (shared libareis linked at runtime)
Header files, implementation files, and main files in c
Header files
-​ #ifndef FUNCTIONS_H
-​ #define FUNCTIONS_H
-​
-​ // Function prototypes
-​ void greet();
-​ int add(int a, int b);
-​
-​ #endif // FUNCTIONS_H
-​
-​ #include “functions.h” in both the corresponding functions.c file and main.c
Makefiles
Explicit rules says
-​ Makefiles are a build automation tool that help to compile and manage projects
-​ When adn how to remake one or more files, called the rule’s targets
-​ Lists the other files that the targets depend on called prereqs of the target
-​ May also give recipe to use to create or update teh targets
Implicit rules says
●​ When adn how to remake a class of files based on their names
●​ Describes how a target may depend on a file with a name similar to the target
●​ A recipe to create or update such a target
Variable definition
●​ A line that specifies a text string value for a variable
●​ Be substituted into the text later
Directive
●​ Instruction for make to do something special while reading the makefile
○​ Reading another makefile
○​ Deciding (based on value of vars) wether to use or ignore a part of the makefile
○​ Defining a variable from a verbatim string containing multiple lines
Comments
●​ # in a line of a makefile is used to start a comment
●​ It and rest of the line are ignored
●​ Except that a trailing backslash not escaped by another backslash will continue the
comment across multiple lines
Anu’s notes
●​ Two main types of rules to define how targets are built
○​ Implicit rules
○​ Explicit rules
■​ Explicitly defines hwo to build a target from its prerequisites
■​ These results are written for specific files or targets and explicitly list all
the prerequisites and the recipe commands to build the target
○​ Implicit rule
■​ Is a predefined rule that tell snake how to build certain kinds of files
depending on their names, without needing to explicitly define each one
■​ Rules are built into make and applied automatically when certain patterns
are matched
■​ Ex.
●​ %.o: %.c
○​ Gcc -c $< -o $@
■​ In the example above the pattern is: %.o:%.c which tells make that for any
.o file (target) that corresponds to a .c file, use the gcc command to
compile it
■​ $< represents the first prerequisite, which in this case is the .c file
■​ $@ represent the target file (which in this case is the .o file)
●​ If main.c is updated, make will automatically use this rule to create main.o without
needing to explicitly define it for each file
●​ Directives in makefiles
○​ Directives are special instructions that modify how make processes the makefile
○​ Directives are not rules for building targets; they are commands that change the
behavior of make
○​ They provide additional functionality like including other files, setting variables, or
defining conditional logic
○​ Command directives in makefiles:
■​ Include: include another makefile inside this one
●​ Purpose: the directive is used to include another makefile. This
allows you to break a large makefile into smaller, more
manageable pieces
●​ Syntax:
○​ Include filename.mk
■​ Includes the contents of filename.mk into the
current makefile. If filename.mk contains rules or
variables, they will be available in the current
makefile
■​ Define
●​ Purpose: defines a multiline variable (useful when you need a
variable to span more than one line)
●​ Ex.
○​ define VARIABLE_NAME
○​ line1
○​ line2
○​ Endef
■​ ifeq/ifneq (conditional directives)
●​ Purpose: conditional statements that allow make to execute part of
the makefile depending on wether certain conditions are true
●​ Ex.
○​ ifeq($(CC), gcc)
■​ CFLAGS += -02
○​ Else
■​ CFLAGS += -00
○​ Endif
●​ This conditional checks wether the CC variable is equal to gcc. If it
is, -02 optimization flags are added ot the CFLAGS variable.
Otherwise -00 (no optimization) is used
■​ Export​
●​ Purpose: makes a variable available to sub-make processes
○​ Syntax:
■​ Export VAR_NAME = value
■​ Ex. export CC = gcc
 ●​ Makes teh CC var available to any child
make processes
■​ Override
●​ Used to ensure that a variable is set to a particular value even if it
was defined earlier in teh Makefile or from the environment
○​ Override VARNAME = value
○​ Override CFLAGS = -g -Wall
●​ Basic Structure
○​ Cosnisits of rules of the following format:
■​ Target: the file to be created or action to be executed
■​ Dependencies: files need to build the target
■​ Commands: shell commands to build the target (MUST be indented with
a TAB)
●​ Command text itself will print out
●​ Ex. if you said echo “This WILL be printed to the console”
(everything including echo will be outputeed?)
●​ To suppress use the @ in front to nto see verbose
●​ Ex. @echo “This will be printed to the console”
●​ Managing dependencies and file locations
○​ Full paths
■​ You can specify full paths to your source adn header files directl yin
makefile but it can become cumbersome as project grows
■​ Make has built-in rules that allow it to search for prerequisites in certain
locations automatically. These built-in tools will handle common file types
and their default locations without the need to manually specify paths
each time
●​ Ex. main.o: main.c
●​ gcc -c main.c -o main.o
■​ Make automatically knows to look for main.c in the current directory
because .c files are implicitly searched for in the current working directory
■​ However, if the file is in another directory, you may need to use one of the
other methods to specify the path
○​ VPATH variable
■​ VPATH variable in Makefiles specifies the directories where make should
search for field that are used as prerequisites (depdnencies)
■​ Useful wehn your source files and headers are in diff directories adn you
want to keep makefile clean
■​ VPATH = src:../headers
●​ Tells make to search teh src and ../headers directories for the
prerequisites
●​ This way make will look for main.c in src/ and main.h in ../headers
without needing to specify the full paths
■​ Vapth directive
●​ Vpath pattern directory
 ○​ Ex. vpath %.h ../headers
●​ Makefile variables
○​ Make makefiles more maintainable with text replacement
○​ Ex.
■​ Objects = program.o foo.o utils.o
■​ Program: $(objects)
●​ cc -o program $(objects)
○​ $(objects) : defs.h
●​ Variable expansion in makefiles (simple vs recursive)
○​ Recursive variable expansion - the value of the variable is evaluated at hte time
of use; can lead to diff results
■​ Ex.
■​ foo = abc
■​ bar = $(foo)
■​ foo = xyz
■​
■​ all:
■​ echo $(bar)
■​ Return xyz
○​ Simple variable expansion
■​ foo := abc
■​ bar := $(foo)
■​ foo := xyz
■​ all: echo $(bar) # Prints abc
○​ Undefined conditional
■​ FOO ?= bar
■​ FOO ?= bar checks if the variable FOO is undefined or empty.
■​ If FOO is not already defined (i.e., its value is empty or it doesn't exist), it
will be assigned the value bar.
■​ If FOO already has a value, this assignment will not change it.
○​ SRCS = $(wildcard $(SRC_DIR)/*.c)
■​ Wildcard function in make - selects all files which match the pattern
●​ $(SRC_DIR)/*.c
■​ Pattern substitution example:
●​ OBJS = $(SRCS:$(SRC_DIR)/%.c=$(OBJ_DIR)/%.o)
●​ % acts as a placeholder for the filename without the extension
●​ Trasnofms the name of .c files to object field
○​ $@: Target name
○​ $<: First dependency
○​ $^: All dependencies
○​ $*: Stem (part that matched the %)
●​ Phony Targets
○​ Declare targets that don;t create files
■​ Avoid a conflict with a file of the same name
 ■​ Improve performance
●​ -DDEBUG: Defines the DEBUG macro for the preprocessor. This is useful for conditionally
including debug-specific code (e.g., using #ifdef DEBUG in C source files).
●​ Multilayer make files
○​ $(MAKE) -C lib: Recursively calls the Makefile in the lib directory
●​ -I../include
○​ Tells compiler to search for header files in a certain directory (in this case
../include) for the preprocessing step
Low level C programming and GCC internals
●​ Stage 1: preprocessing (gcc -E)
○​ The preprocessor handles directives like #include, #define, and #ifdef
■​ Expands macros (all macros you define like #define are replaced with
their values or instructions)
●​ Ex. #define SQUARE(x) (x*x)
●​ After preprocessing SQUARE(5) becomes (5*5)
■​ Includes header files (copies and pastes everything from teh header files
into this code wherever you have the #include)
■​ Removes comments
○​ Gcc - E example.c -o example.i
■​ Example of producing a preprocessed file
○​ GCC automatically adds built in macros like
■​ __STDC__: says your compiler is following the C standard
■​ __GNUC__: Gives the GCC version (ex. 11)
■​ __linux__: says you’re on linux
●​ These macros can help make your code portable across diff
systems
○​ The preprocessor keeps track of where code comes from using lines like
■​ #1 “example.c”
●​ We’re now working on line 1 of the file example.c - this is the
output from the preprocessor indicating which files nd line
numbers are being processed and show show preprocessor
handles file inclusions, built in defs, and command line options
●​ Why does this matter?
○​ If an error happens, these line directives help the compiler
and you know where the problem is in your og file
○​ Preprocessed output shows you exactly what the compiler
sees after macros and includes are processed
●​ Stage 2: Compilation to Assembly (gcc -S)
○​ Gcc -S example.i -o example.s
○​ Generate assembly with detailed comments explaining each assembly
instruction:
■​ gcc -fverbose-asm -S example.c
○​ Check stack usage

😭
■​ gcc -fstack-usage example.c
○​ CS 33 flashbacks
●​ Stage 3: Assembly to object code (gcc - c)
○​ Converts assembly code to machine code in object file format
●​ Stage 4: Linking (gcc example.o -o example)
○​ Combines object fiels into single executable file and resolves external references
(these are functions/varaibles declared in one file but defined in another)
○​ Ex.
■​ When you compile files separately with -c they become object files
 ●​ Gcc -c file1.c file2.c
■​ The linker combines them into one executable file
●​ Gcc file1.o file2.o -o program
○​ What happens with external library calls?
■​ When your program uses a function from an external library (like printf
from libc) the actual location of that function in memory isn’t known until
that program runs. Instead of hardcoding the address, your program uses
a mechanism called PLT (Procedure Linkage Table) and GOT (Global
Offset Table) to figure it out during runtime
○​ PLT (procedure linkage table)
■​ Think of PLT as a “to do list” or a shortcut table for calling external
functions
■​ Doesn’t store the real address of a function at first (it know how to ask
dynamic linker to find the address when needed)
○​ GOT (Global Offset table)
■​ The GOT is like a notebook where the real address of functions are
written once they are known
■​ Initially the entries in the GOT don’t have the actual address but they get
filled during program execution
○​ Lazy Resolution
■​ Functions are only resolved when you call them for the first time (lazy
resolution)
●​ PLT tells dynamic linker “hey find the real address of this function”
when it first encounters an external function
●​ The dynamic linker looks up the function in external library, finds
the actual address in memory and updates the GOT with that
address
●​ Now every future call to that function uses the address from the
GOT (no need to ask linker again)
○​ Why lazy resolution
■​ Prgoram doesn’t need to know exact address ofhte library functions
beforehand (maeks it easier to replace/update libraries without chiangng
your program)
○​ What is inside the executable?
■​ Once linked, the executable contains different parts or segments
■​ Text segment(code)
●​ Contains actual instructions for program
●​ Read-only and shared
■​ Data segment (initialized data)
●​ Holds global and static varaibels that are initialized
●​ Read-write property during program execution (values can be
updated)
●​ Take space in the executable file
■​ BSS Segment (Uniinitalized Data)
 ●​ Holds globala nd static varaibels that are NOT initialized
●​ These variables are automatically set to 0 at runtime
●​ They take no space in the executable file (only metadata is stored)
●​ Name: stands for block started by symbol
■​ Dynamic Linking information
●​ Information that helps the program find and use external libraries
(like libc)
●​ Symbol tables and reallocation information tell the dynamic linker
(ld.so) where to find external functions like printf
●​ These are resolved at funtime using PLT and GOT

Using debugger to view outputs

gcc -g example.c -o example
-​ This command ocmpiles th source code into an executable. The -g flag tells the compiler
to include debugging info which allows tools like gdb and nm to display more useful info
about the prgoram such as symbol names, source code, numbers, adn types
-​ Nm example output
-​ 0000000000004010 D _GLOBAL_OFFSET_TABLE_
-​ 0000000000002004 d _DYNAMIC
-​ 0000000000004000 D global_var
-​ U _init
-​ 0000000000001139 T main
-​ 0000000000001129 T function
-​ 0000000000004008 d static_var
-​ U puts@GLIBC_2.2.5
-​ U __libc_start_main@GLIBC_2.2.5
-​ 0000000000002000 r __GNU_EH_FRAME_HDR
-​ 0000000000001000 T _start
-​ The nm command shows the symbol table of the program, which includes addresses,
names, and types of symbols defined or used in the program
-​ Columns in the nm output
 -​ Addresses: the memory address of the symbol
-​ Type: the symbol’s type (see blow)
-​ Symbol name
-​ Symbol Types
-​ D (Data): a symbol in the data section (which contains initailized global vars;
values store din memory)
-​ d(Data, local): a symbol in the data section but its a local variables (symbol has
initailized data but only used within the compilation unit)
-​ T(text): A symbol in the text section (contains code (functions, etc.))
-​ U(Undefined): used but not defined in this object file (usually defined in another
library or object file that will be resolved during linking stage
-​ r(Read-only): a symbol in the read-only section (used for constants/string literals)
-​ Analyzing the nm Output:
1.​ Global Offset Table (GOT) - special symbol used for dynamic linking to hold addresses
of external symbols that are resolved at runtime
2.​ Dynamic - symbol related to dynamic linking, storing info used by dynami clinker (local
initialized data in the .data section)
3.​ Global_var - global variable defined somewhere in the program thats initalized and
stored in .data sections o has global scope
4.​ _init - symbol is undefined; often used for initialization code adn would normally be
defined in another object file or library
a.​ U means undefined symbol, which will also be resolved during linking
5.​ Main
a.​ Main function part of text (T)
6.​ Function
a.​ Another function (possibly user defined) that’s in text section
7.​ Static_var - local static variable
8.​ puts@GLIBC_2.2.5
a.​ The puts function is an undefined symbol, meaning its is calle din porgram but its
definition is in an external library (GNU C library)
b.​ U means undefined symbol that linker will resolve

local_var:

●​ Explanation: You mentioned that local_var is not visible in the symbol table. This is
because it’s a local variable created on the stack and doesn't have a global or static
scope. It won't appear in the symbol table because it is managed at runtime and only
exists during the execution of the function in which it is declared.
9.​
10.​For debugger optimizatons:
a.​ Performs instruction scheduling: Rearranges instructions to improve CPU
efficiency.
b.​ Inlines small functions: Replaces function calls with their actual code.
c.​ Adds vectorization: Converts scalar operations into SIMD (Single Instruction,
Multiple Data) for parallel execution.
d.​ What is SIMD
i.​ Single instruction, multiple data - technique used in modern processors to
perform the same operation on multiple pieces of data at the same time
ii.​ Makes programs run faster, especially when dealing with repretitive tasks
lik eprocessing arrays
iii.​ Ex. instead of mulitplying numbers one by one (multiply them all in one
swing)
11.​Loop Optimization in GCC
a.​ Loop vectorization
i.​ gcc -ftree-vectorize -fopt-info-vec example.c
1.​ Transform sloops to use SIMD instructions allowing multiple
iterations to be executed simultaneously
2.​ Makes loops process multipel data points at once, speeding up
tasks like mathematical calculations on arrays
b.​ Enabling SMD with native instructions
i.​ gcc -march=native -ftree-vectorize example.c
1.​ Generates code that uses the best SIMD instructions available on
you CPU
c.​ Cache optimization reports
i.​ gcc -fopt-info-vec-optimized example.c
ii.​ Tells you if the compiler optimized your loops for cache performance
 iii.​ Loops that work well with the CPU’s cache run faster because accessing
memory from cache is quicker than RAM
d.​ Cache prefetching
i.​ gcc -fprefetch-loop-arrays example.c
ii.​ Tells the CPU to load data into the cache ahead of time
iii.​ Reduces waiting times when the loop needs the data
Can we tell the compiler what to do/ what I am doing gin advance?
-​ Compiler attributes are hints we give to the compiler to optimize, enforce, or modify how
our code behaves
-​ Can apply to functions, variables, or types and let us fine tune performance
-​ __attribute__((attribute_name))
-​ Attributes appear before or after the function/variable declaration
-​ __attribute__((noreturn))
-​ Indicates function will enver return
-​ __attribute__((const))
-​ Specifies that the return value depends only on input parameters (no global
memory or side effects)
-​ __attribute__((deprecated("Use new_function() instead")))
-​ Marks a function as outdated and issues warning when used
-​ __attribute__((always_inline))
-​ Forces a compiler to inline a function (avoiding function call overhead)
-​ An inline function is one for which the compiler copies the code from the
function definition directly into the code of the calling function rather than
creating a separate set of instructions in memory.
-​ variable/type attributes
-​int matrix[4][4] __attribute__((aligned(16)));
-​ Specifies the memory alignment for variables or structures
-​ Ensures compatibility with SIMD instructions (minimizes padding between
struct members)
Memory Alignment Basics
-​ Memory alignments ensures data is stored at memory addresses that are MULTIPLES of
the data size
-​ Aligned vs unaligned data
-​ Aligned data
-​ Stored at addresses that are multiples of the data size
-​ Accessing aligned data required single memory access which is faster
-​ Unaligned data
-​ Stored at arbitrary addresses (not a multiple of the data size)
-​ Accessing unaligned data requires two memory access (slower))
-​ Struct Padding and Memory Optimizaton
-​ When defining structs, padding bytes may be added to maintain proper alignment
for faster memory access but this can increase memory footprint

Cache Memory
Cache memory is a small, fast memory located close to the CPU. It stores copies of frequently
accessed data to speed up subsequent access to that data. When the CPU accesses memory,
it first checks the cache. If the data is found there (a cache hit), it can be accessed much faster
than if it has to be fetched from the main memory (a cache miss).

Spatial and Temporal Locality

●​ Spatial Locality: Refers to the use of data elements within relatively close storage
locations. If your program accesses memory locations that are close to each other in a
short period, it benefits from spatial locality.
●​ Temporal Locality: Refers to the reuse of specific data within relatively short time
periods. If your program accesses the same memory locations multiple times in a short
period, it benefits from temporal locality.

How These Concepts Apply to Our Example

Matrix A Access Pattern (a[i*n + k]):

●​ Spatial Locality: High, because it accesses elements in a row (consecutive memory

locations).
●​ Temporal Locality: Medium, because each row is accessed multiple times for different
values of j.

Matrix B Access Pattern (b[k*n + j]):

●​ Spatial Locality: Low, because it accesses elements in a column (strided access,

jumping over large areas of memory).
●​ Temporal Locality: Low, because different parts of memory are accessed in a strided
pattern.

Matrix C Access Pattern (c[i*n + j]):

●​ Spatial Locality: High, because it writes elements in a row (consecutive memory

locations).
●​ Temporal Locality: Not applicable, as it writes each element once.

Cache Misses

A cache miss occurs when the CPU tries to read or write data that is not in the cache, causing
it to fetch the data from the slower main memory. Cache misses can significantly slow down a
program.
In our matrix multiplication example, accessing matrix b in a column-major order causes
frequent cache misses because of its poor spatial locality. Every access to b[k*n + j] may
require fetching a new cache line, leading to inefficient cache usage.

Optimization Techniques

One common optimization technique is blocking or tiling. This technique involves dividing the
matrices into smaller blocks that fit into the cache, improving both spatial and temporal locality.

Explanation of Optimization

●​ Blocking/Tiling: By breaking the matrices into smaller blocks, the data within each block
can fit into the cache. This reduces the number of cache misses because the data is
accessed in a more cache-friendly manner.

System call vs library functions

-​ System calls are the interface between user applications and the operating system in
Unix-like system → allow programs to request services from the kernel, such as file
operations, process control, and communication
-​ Common system calls in C:
-​ Open: opens a file and returns file descriptor
-​ int open(const char *pathname, int flags);
-​ int open(const char *pathname, int flags, mode_t mode);
-​ #include <fcntl.h>
-​ #include <unistd.h>
-​ #include <stdio.h>
-​
-​ int main() {
-​ int fd = open("example.txt", O_RDONLY);
-​ if (fd == -1) {
-​ perror("open");
-​ return 1;
-​ }
-​ // Use the file descriptor...
-​ close(fd);
-​ return 0;
-​ }
-​ Read:
-​ ssize_t read(int fd, void *buf, size_t count);
-​
 -​ int main() { int fd = open("example.txt", O_RDONLY); if (fd == -1) { perror("open");
return 1; } char buffer[128]; ssize_t bytesRead = read(fd, buffer, sizeof(buffer) -
1); if (bytesRead == -1) { perror("read"); close(fd); return 1; } buffer[bytesRead] =
'\0'; printf("Read: %s\n", buffer); close(fd); return 0; }
-​ ssize_t write(int fd, const void *buf, size_t count);
-​ #include <fcntl.h>
-​ #include <unistd.h>
-​ #include <stdio.h>
-​ #include <string.h>
-​ int main() {
-​ int fd = open("example.txt", O_WRONLY | O_CREAT, 0644);
-​ if (fd == -1) {
-​ perror("open");
-​ return 1;
-​ }
-​ const char *message = "Hello, world!\n";
-​ ssize_t bytesWritten = write(fd, message, strlen(message));
-​ if (bytesWritten == -1) {
-​ perror("write");
-​ close(fd);
-​ return 1;
-​ }
-​ close(fd);
-​ return 0;
-​ }

FLAGS for open

Access Modes:

●​ STDOUT_FILENO
●​ O_RDONLY: Open the file for read-only access.
●​ O_WRONLY: Open the file for write-only access.
●​ O_RDWR: Open the file for both reading and writing
-​ O_CREAT: Create the file if it does not exist. This flag requires a third argument
specifying the file permissions.
-​ O_EXCL: Ensure that this call creates the file. If this flag is specified and the file already
exists, the open call will fail.
-​ O_TRUNC: If the file exists and is opened for write access, its length will be truncated to
0.
-​ O_APPEND: Open the file in append mode. All writes will be added to the end of the file.
-​ O_NONBLOCK: Open the file in non-blocking mode. This is useful for special files like
FIFOs and device files.
 -​ O_SYNC: Open the file for synchronous I/O. Writes to the file will block until the data has
been physically written.

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

Parameters

1.​ char **lineptr (e.g., &buffer):

○​ A pointer to a char * variable (typically buffer).
○​ This variable holds the address of a buffer that stores the read line.
○​ If *lineptr is NULL, getline will allocate memory for the buffer.
2.​ size_t *n (e.g., &len):
○​ A pointer to a size_t variable (typically len).
○​ This variable specifies the size of the buffer that *lineptr points to.
○​ If *lineptr is NULL or not large enough, getline will allocate or resize the
buffer and update *n to reflect the new size.
3.​ FILE *stream (e.g., fp):
○​ A pointer to a FILE object, which represents the input file stream from which
getline reads.