<!-- Abstract: CS 211 Computer Architecture Lecture 06: File I/O and Structs --> # CS 211 - Lecture 06 - Structs and Modular Code Bernhard Firner 2025-02-09 --- ## Review * We've been covering memory * Stack and heap * Stack memory is mostly automatic * The compiler will write code to allocate and deallocate stack memory * Heap memory is up to the programmer to manage --- ## Heap Memory * Heap memory does *not* go out of scope * Functions are in `stdlib.h` ```C void *malloc(size_t size); void free(void *_Nullable ptr); void *calloc(size_t nmemb, size_t size); ``` --- ## Using Heap Memory * We can allocate memory in one function and return it to another * This allows for more complex programs * But we have to manage the complexity ourselves --- ## Class Example Code ```C #include <stdbool.h> #include <stdio.h> #include <stdlib.h> unsigned int* sieve(int max, size_t* num_primes) { // Set to 0 because I don't trust the caller *num_primes = 0; bool not_prime[max] = {}; not_prime[0] = true; not_prime[1] = true; for (int i = 2; i < max; ++i) { if (!not_prime[i]) { ++(*num_primes); // Set all multiples to be not prime for (int j = 2*i; j < max; j += i) { not_prime[j] = true; } } } // Calloc sets the memory to 0 unsigned int* primes = calloc(*num_primes, sizeof(unsigned int)); // Malloc doesn't change the values /* unsigned int* primes = malloc(*num_primes * sizeof(unsigned int)); for (int i = 0; i < *num_primes; ++i) { primes[0] = 0; } */ int cur_idx = 0; unsigned int* cur_ptr = primes; // Put the primes inside for (int i = 2; i < max; ++i) { if (!not_prime[i]) { //primes[cur_idx] = i; //++cur_idx; //*(primes + cur_idx) = i; //++cur_idx; *cur_ptr = i; ++cur_ptr; } } return primes; } int main(int argc, char** argv) { if (argc < 2) { printf("We need a number!\n"); return 1; } int size = atoi(argv[1]); if (size < 2) { printf("The number %i is too small!\n", size); return 1; } size_t num_primes; unsigned int* primes = sieve(size, &num_primes); // Print out the primes unsigned int* end = primes+num_primes; for (unsigned int* p = primes; p != end; ++p) { printf("%u is prime\n", *p); } free(primes); return 0; } ``` --- ## Debugging * Dynamic memory allocation is a common source of errors * So use **valgrind** to check for memory mistakes * And use **gdb** to debug crashes or confusing problems * At this point, running valgrind should become a common habit * gdb will require practice --- ## Improving Our Code * This is still a computer architecture class * But we're going to talk more about C * Why? * Because computer architecture is built around how we program * This will become clear when we talk about memory and cacheing --- ## Structs * We awkwardly added a return value into the sieve function arguments * `unsigned int* sieve(int max, size_t* num_primes);` * There is a better way to group related data, called `structs` * Similar to classes in other languages, but with little overhead --- ## Declaring a struct * `struct <name> { declaration-list };` ```C struct twoNumbers { int a; int b; }; ``` --- ## new struct * The name of the struct is "struct twoNumbers" * It can be used anywhere you would use another type * function arguments and returns * array declarations * inside other structs --- ## typedef * The names of our structs are awkward * `struct name` * C has a way to make new names, and we can use it to simplify our structs * `typedef <existing name> <new name>` * You can do this before making the struct, which is a `forward declaration` ```C typedef struct twoNumbers twoNumbers; struct twoNumbers { int a; int b; }; ``` --- ## More C Cruft * A quick note * You will see some odd struct usage in the wild * You can instantiate a variable of the new type immediately ```C struct twoNumbers { int a; int b; } instance; ``` --- ## Avoid confusion ```C typedef struct twoNumbers twoNumbers; struct twoNumbers { int a; int b; }; twoNumbers instance; ``` --- ## Member initialization ```C typedef struct twoNumbers twoNumbers; struct twoNumbers { int a; int b; }; twoNumbers first = {10, 20}; twoNumbers second = {.a = 10, .b = 20}; ``` --- ## Accessing struct members * The '.' (dot) operator * Used in optional initialization syntax * also used to access individual values ```C twoNumbers first = {10, 20}; first.a = 50; ``` --- ## note on operators * Our regular operators (+, -, etc) aren't supported * We will have to write our own functions ```C twoNumbers addTwoNumbers(twoNumbers left, twoNumbers right) { twoNumbers sum = {.a = left.a + right.a, .b = left.b + right.b}; return sum; } ``` --- ## Passing structs * Function arguments are copied when passed * Avoid passing by value if structs are large * Use a pointer to the struct in those cases * Use `const` to protect current values --- ## passing pointers to struct ```C twoNumbers addTwoNumbers(twoNumbers* left, twoNumbers* right) { twoNumbers sum{.a = (*left).a + (*right).a, .b = (*left).b + (*right).b}; return sum; } ``` --- ## -> operator Annoying to keep using * to get the pointer values ```C twoNumbers addTwoNumbers(twoNumbers* left, twoNumbers* right) { twoNumbers sum = {.a = left->a + right->a, .b = left->b + right->b}; return sum; } ``` --- ## Using const qualifier * Some functions we've seen have `const` in their arguments * This tells the compiler that the variable, or what it points to, should not be modified --- ## Const example ```C /* * Demonstrate const with struct pointers */ #include <stdio.h> typedef struct bigData bigData; struct bigData { long long numbers[1000]; }; // This function modifies data's members, so it cannot be const. void modifyData(bigData* data) { for (int i = 0; i < sizeof(data->numbers)/sizeof(long long); ++i) { data->numbers[i] = i; } } // This function does not modify data's members, so it can be const. long long sumData(const bigData* data) { long long sum = 0; for (int i = 0; i < sizeof(data->numbers)/sizeof(long long); ++i) { sum += data->numbers[i]; } return sum; } int main(void) { bigData data = {.numbers = {}}; // Modify the data modifyData(&data); // Sum the data printf("Sum is %lli\n", sumData(&data)); return 0; } ``` --- ## Passing pointers in structs * Passing a pointer does not copy that memory * Likewise, passing a struct with a pointer only copies the pointer * So passing a struct of pointers is okay * Only copies the pointers, which are numbers * This means that we can return structs with pointer members safely * Just be sure to have a way to indicate errors --- ## Pointers with Sizes ```C typedef struct nicePtr nicePtr; struct nicePtr { unsigned int* memory; size_t elements; }; ``` * We can use this to clean up our sieve --- ## sieve example ```C #include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef struct nicePtr nicePtr; struct nicePtr { unsigned long* memory; size_t elements; }; nicePtr sieve(int max) { size_t num_primes = 0; bool not_prime[max] = {}; not_prime[0] = true; not_prime[1] = true; for (int i = 2; i < max; ++i) { if (!not_prime[i]) { ++(*num_primes); // Set all multiples to be not prime for (int j = 2*i; j < max; j += i) { not_prime[j] = true; } } } // Calloc sets the memory to 0 unsigned int* primes = calloc(*num_primes, sizeof(unsigned int)); unsigned int* cur_ptr = primes; // Put the primes inside for (int i = 2; i < max; ++i) { if (!not_prime[i]) { *cur_ptr = i; ++cur_ptr; } } nicePtr result = {.memory = primes, .elements = num_primes}; return result; } int main(int argc, char** argv) { if (argc < 2) { printf("We need a number!\n"); return 1; } int size = atoi(argv[1]); if (size < 2) { printf("The number %i is too small!\n", size); return 1; } size_t num_primes; nicePtr primes = sieve(size); // Print out the primes unsigned int* end = primes.memory+primes.num_primes; for (unsigned int* p = primes.memory; p != end; ++p) { printf("%u is prime\n", *p); } free(primes.memory); return 0; } ``` --- ## Pause * So far, so good? * We'll cover a quality of life feature that simplifies building code * Then we'll review for the quiz --- ## Modular Code * Everyone likes `modular`, `reusable` code * Libraries of functions like `<stdlib.h>` * We should clean up the sieve code and put it into a library --- ## Header files * Notice that the file we include ends in `.h` * `h` stands for `header` * Declares things variables and functions * [declaration syntax](https://cppreference.com/w/c/language/declarations.html) --- ## sieve header file * Make a file named `sieve.h` ```C /* * This header file declares the sieve function. */ typedef struct nicePtr nicePtr; struct nicePtr { unsigned int* memory; size_t elements; }; nicePtr sieve(int max); ``` --- ## Header file usage * Header files may be included in multiple other files * C allows you to declare the same things multiple times * But no conflicting declarations! * So we will have to put values and implementations elsewhere * Let's make a c file called sieve_main.c --- ## sieve_main.c ```C #include <stdio.h> // For printf #include <stdlib.h> // For free // Include sieve.h after the standard library includes // Use quotes instead of angle brackets #include "sieve.h" int main(int argc, char** argv) { if (argc < 2) { printf("We need a number!\n"); return 1; } int size = atoi(argv[1]); if (size < 2) { printf("The number %i is too small!\n", size); return 1; } nicePtr primes = sieve(size); // Print out the primes unsigned int* end = primes.memory+primes.elements; for (unsigned int* p = primes.memory; p != end; ++p) { printf("%u is prime\n", *p); } free(primes.memory); return 0; } ``` --- ## \#include syntax * Notice that we now use quotes instead of <> * #include "sieve.h" * #include <stdio.h> * This changes where gcc searches for the file * Quotes checks the current directory * Angle brackets check system paths -v- ## Search path * If you are curious, you can get gcc to spit out its search paths with a dummy compile command ``` bfirner@ilab3:~$ gcc -xc -E -v /dev/null Using built-in specs. COLLECT_GCC=gcc OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa OFFLOAD_TARGET_DEFAULT=1 Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu 13.3.0-6ubuntu2~24.04' --with-bugurl=file:///usr/share/doc/gcc-13/README.Bugs --enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-13 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/libexec --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-libstdcxx-backtrace --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2 Thread model: posix Supported LTO compression algorithms: zlib zstd gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04) COLLECT_GCC_OPTIONS='-E' '-v' '-mtune=generic' '-march=x86-64' /usr/libexec/gcc/x86_64-linux-gnu/13/cc1 -E -quiet -v -imultiarch x86_64-linux-gnu - -mtune=generic -march=x86-64 -fasynchronous-unwind-tables -fstack-protector-strong -Wformat -Wformat-security -fstack-clash-protection -fcf-protection -dumpbase - ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu" ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/13/include-fixed/x86_64-linux-gnu" ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/13/include-fixed" ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/13/../../../../x86_64-linux-gnu/include" #include "..." search starts here: #include <...> search starts here: /usr/lib/gcc/x86_64-linux-gnu/13/include /usr/local/include /usr/include/x86_64-linux-gnu /usr/include End of search list. # 0 "<stdin>" # 0 "<built-in>" # 0 "<command-line>" # 1 "/usr/include/stdc-predef.h" 1 3 4 # 0 "<command-line>" 2 # 1 "<stdin>" COMPILER_PATH=/usr/libexec/gcc/x86_64-linux-gnu/13/:/usr/libexec/gcc/x86_64-linux-gnu/13/:/usr/libexec/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/13/:/usr/lib/gcc/x86_64-linux-gnu/ LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/13/:/usr/lib/gcc/x86_64-linux-gnu/13/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/13/../../../../lib/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/13/../../../:/lib/:/usr/lib/ COLLECT_GCC_OPTIONS='-E' '-v' '-mtune=generic' '-march=x86-64' ``` -v- ## Results * Quotes only search current directory * Angle brackets search a few directories <pre> #include "..." search starts here: #include <...> search starts here: /usr/lib/gcc/x86_64-linux-gnu/13/include /usr/local/include /usr/include/x86_64-linux-gnu /usr/include </pre> --- ## Using the sieve * If you try to compile now, things won't quite work <pre> $ gcc using_sieve.c /usr/bin/ld: /tmp/ccquSqAu.o: in function `main': sieve_main.c:(.text+0x8e): undefined reference to `sieve' collect2: error: ld returned 1 exit status </pre> * We need to compile the actual sieve code, from sieve.c --- ## sieve.c ```C #include <stdbool.h> #include <stdlib.h> #include "sieve.h" nicePtr sieve(int max) { size_t num_primes = 0; bool not_prime[max] = {}; not_prime[0] = true; not_prime[1] = true; for (int i = 2; i < max; ++i) { if (!not_prime[i]) { ++(num_primes); // Set all multiples to be not prime for (int j = 2*i; j < max; j += i) { not_prime[j] = true; } } } // Calloc sets the memory to 0 unsigned int* primes = calloc(num_primes, sizeof(unsigned int)); unsigned int* cur_ptr = primes; // Put the primes inside for (int i = 2; i < max; ++i) { if (!not_prime[i]) { *cur_ptr = i; ++cur_ptr; } } nicePtr result = {.memory = primes, .elements = num_primes}; return result; } ``` --- ## Compiling * You can compile everything yourself * In short, `gcc sieve_main.c sieve.c -o sieve` * But specifying everything manually will get awkward * And you obviously aren't compiling other libraries, like stdlib --- ## Proper Way * First, compile your code with `-c` * `gcc -c sieve_main.c -o sieve_main.o` * Be careful with output filenames (-o) that you don't overwrite a code file * The output (sieve.o) is an object file * It cannot run on its own because it is missing pieces * Needs the code from `sieve.c` --- ## More object files * Build the object file for `sieve.c` * `gcc -c sieve.c -o sieve.o` --- ## Linking * Now `gcc` can link the object files * `gcc sieve.o sieve_main.o -o sieve_example` * Linking combines the memory and functions of multiple pieces of code together --- ## Why? * Some of the programs you link to are very large * Recompiling all of them for your <100 lines of code would be a waste of time * Doing all of this manually is a pain though, so most people use **make files** * Rules placed into a file named `makefile` --- ## Makefile aside * These will *simplify* your lives * Never going to test you on the syntax, just explaining it * Feel free to copy and paste the examples * [makefiletutorial.com](https://makefiletutorial.com) has a fuller explanation --- ## Make example ```Makefile # Any filename that ends in .o is made with the command gcc <filename.c> -o <filename.o> # $@ is the list of targets (the thing before the colon) # $^ is the list of dependencies (the things after the colon) %.o: %.c gcc -c $^ -o $@ # The sieve_example program depends upon both using_sieve.o and sieve.o # $^ expands to 'using_sieve.o sieve.o' # $@ expands to 'sieve_example' sieve_example: sieve_main.o sieve.o gcc $^ -o $@ ``` -v- ## Note on Makefile copy & paste * If you copy and paste that makefile code it may not work * Something is converting tabs into spaces, but makefiles require tabs in the rules * Converting the indentations into tabs fixes the problem --- ## Building <pre> $ make sieve_example gcc -c sieve_main.c -o sieve_main.o gcc -c sieve.c -o sieve.o gcc sieve_main.o sieve.o -o sieve_example </pre> * If you try to build it again without modifying any files <pre> $ make sieve_example make: 'sieve_example' is up to date. </pre> * Make only rebuilds targets with updated dependencies * Helpful in giant software projects --- ## Compiler Flags * One reason to use makefiles is to keep track of compiler flags * `-Wall` to turn all possible warnings * `-O2` to turn on optimization level 2 * Speed optimizations that will not compromise program size * `-O3` to turn on optimization level 3 * Which may compromise program size for speed * `-g` debug symbols --- ## Final makefile ```makefile # Compile anything with debug flags (-g) debug_%.o: %.c gcc -g -c $^ -o $@ # Compile anything with debug flags debug_%: debug_%.o gcc -g $^ -o $@ # Any filename that ends in .o is made with the command gcc <filename.c> -o <filename.o> # $@ is the list of targets (the thing before the colon) # $^ is the list of dependencies (the things after the colon) %.o: %.c gcc -O2 -c $^ -o $@ # Compiles directly to a target. %: %.c gcc -O2 $^ -o $@ # The sieve_example program depends upon both using_sieve.o and sieve.o # $^ expands to 'using_sieve.o sieve.o' # $@ expands to 'sieve_example' sieve_example: sieve_main.o sieve.o gcc $^ -o $@ debug_sieve_example: debug_sieve_main.o debug_sieve.o gcc $^ -o $@ ``` --- ## Quiz Review * The quiz content will be through today's lecture * We'll have one more lecture before the quiz, but the content won't be on the quiz * We'll go through a few examples * But remember, I may ask other things, these are just examples --- ## Q1 <div style="text-align: left;"> What is the output of the following code snippet? printf("6 / 4 = %i\n", 6/4); a. 1 b. 1.5 c. 1.0 d. This code is not syntactically correct and will not compile. </div> --- ## Q1 <div style="text-align: left;"> What is the output of the following code snippet? printf("6 / 4 = %i\n", 6/4); **a. 1** b. 1.5 c. 1.0 d. This code is not syntactically correct and will not compile. </div> --- ## Q2 <div style="text-align: left;"> Using the code below, if an instance of the nicePtr struct is passed into someFunction, which statement is **true**? ``` typedef struct nicePtr nicePtr; struct nicePtr { unsigned long* memory; size_t elements; }; void someFunction(nicePtr p); ``` a. The values of the array pointed to by p.memory will be copied automatically. b. The value of p.memory will be copied, but this will not copy the elements of the array. c. The typedef has an error and this will not compile. d. Structs must be passed as pointers, so this will not compile. </div> --- ## Q2 <div style="text-align: left;"> Using the code below, if an instance of the nicePtr struct is passed into someFunction, which statement is **true**? ``` typedef struct nicePtr nicePtr; struct nicePtr { unsigned long* memory; size_t elements; }; void someFunction(nicePtr p); ``` a. The values of the array pointed to by p.memory will be copied automatically. **b. The value of p.memory will be copied, but this will not copy the elements of the array.** c. The typedef has an error and this will not compile. d. Structs must be passed as pointers, so this will not compile. </div> --- ## Q3 <div style="text-align: left;"> Which of the following statements of the stack and heap is **false**? a. Stack memory and heap memory grow from opposite ends of the memory space. b. Heap memory is allocated and freed by the user. c. Stack memory is allocated and freed by the user. d. Variable length arrays may allocate memory on the stack or the heap. </div> --- ## Q3 <div style="text-align: left;"> Which of the following statements of the stack and heap is **false**? a. Stack memory and heap memory grow from opposite ends of the memory space. b. Heap memory is allocated and freed by the user. **c. Stack memory is allocated and freed by the user.** d. Variable length arrays may allocate memory on the stack or the heap. </div> --- ## Q4 <div style="text-align: left;"> The exit status of a program is NOT: a. Always an integer. b. Generally nonzero to indicate failure. c. The value of the last variable cleaned up from the stack. d. The value returned from the main function. </div> --- ## Q4 <div style="text-align: left;"> The exit status of a program is NOT: a. Always an integer. b. Generally nonzero to indicate failure. **c. The value of the last variable cleaned up from the stack.** d. The value returned from the main function. </div> --- ## Q5 <div style="text-align: left;"> After the following line of code, what is the value of a? ``` int a = 2.7; ``` a. 2.7 b. 2 c. The value will be architecture specific. d. This code is not syntactically correct and will not compile. </div> --- ## Q5 <div style="text-align: left;"> After the following line of code, what is the value of a? ``` int a = 2.7; ``` a. 2.7 **b. 2** c. The value will be architecture specific. d. This code is not syntactically correct and will not compile. </div> --- ## Q6 <div style="text-align: left;"> Which of the following statements about argc and argv are **false**? a. The values of argc and argv are only known at run time. b. The main function must have argc and argv as arguments to compile. c. argv is a pointer that points to other pointers. d. argv[0] is the program name itself. </div> --- ## Q6 <div style="text-align: left;"> Which of the following statements about argc and argv are **false**? a. The values of argc and argv are only known at run time. **b. The main function must have argc and argv as arguments to compile.** c. argv is a pointer that points to other pointers. d. argv[0] is the program name itself. </div> --- ## Q7 <div style="text-align: left;"> ``` #include <stdio.h> int main(int argc, char** argv) { printf("%lu\n", sizeof(int*)); return 0; } ``` The above code will: a. Print the size of a pointer on the current architecture. b. Print the size of an int on the current architecture. c. It will not compile because sizeof cannot be used with int*. d. It will not compile for other reasons. </div> --- ## Q7 <div style="text-align: left;"> ``` #include <stdio.h> int main(int argc, char** argv) { printf("%lu\n", sizeof(int*)); return 0; } ``` The above code will: **a. Print the size of a pointer on the current architecture.** b. Print the size of an int on the current architecture. c. It will not compile because sizeof cannot be used with int*. d. It will not compile for other reasons. </div> --- ## Q8 <div style="text-align: left;"> ```C int a = 6; int *b = &a; b[0] = 2; *b += 10; ``` After the above, code, what is the value of a? a. 6 b. 12 c. 16 d. None of those. </div> --- ## Q9 <div style="text-align: left;"> ```C int a = 6; int *b = &a; b[0] = 2; *b += 10; ``` After the above, code, what is the value of a? a. 6 **b. 12** c. 16 d. None of those. </div> --- ## Q10 <div style="text-align: left;"> In a little endian system, the first byte of an integer is a. Always set to 0 b. Where the sign bit is stored c. The least significant d. The most significant </div> --- ## Q10 <div style="text-align: left;"> In a little endian system, the first byte of an integer is a. Always set to 0 b. Where the sign bit is stored **c. The least significant** d. The most significant </div> --- ## Q11 <div style="text-align: left;"> What is the 2's complement negation of the byte value 0000 0001? <br> \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ </div> <!-- At some point sizeof and show optimizations with packing show bitfields and unions -->