Post-task self check

Written by Julie Zelenski

As you vanquish each CS107 assignment and lab, a little celebration is definitely in order, but once the excitement dies down, take a moment to reflect on how far you've come and what new knowledge and skills you have to take forward. To help you gauge your progress, for each assignment/lab, we identify some of its takeaways and offer a few thought questions you can use as a self-check on your post-task understanding. If you find the responses don't come easily, it may be a sign a little extra review is warranted. These questions are not to be handed in or graded. You're encouraged to freely discuss these with your peers and course staff to solidify any gaps in you understanding before moving on from a task. They could also be useful as review before the exams.

Assign0: Testing

You now have your environment configured and edit files, make commits, and execute programs. You've also been getting into a testing mindset, developing testing strategies, and using tools such as sanity check and Valgrind. Off to a great start!

• How do you customize the tests used by sanity check?
• Which is the bigger problem: memory errors or memory leaks? Why? How can you tell which is which in a Valgrind report?
• What is the difference between commit and submit?

Lab1: Tools and debugging

You should now feel acquainted with basic use of make, Mercurial, gdb, and Valgrind and have identified resources to tap info when you need more information about the tools or the C language and its libraries. You also have done a little wrangling with C-strings and I/O. All of these skills are very helpful for assignment 1!

• What does the hg diff command do?
• What are the steps to run a program that takes command-line arguments (such as piglatin) under gdb?
• Why is a field width essential when using scanf for strings? What happens when scanning a too-long string without one? What happens when scanning a too-long string with one?
• How would you allocate a string buffer of length 10 in the stack? What about in the heap? How are each of those deallocated?
• Does strncpy null-terminate the destination string? What about strncat? Where could you look to find this information if you don't already know it?

Assign1: C-strings

Congrats on your first complete C-program! This was great practice with C-strings, strxxx functions, dynamic memory, use of tools, and software testing. At the end of the quarter, many students recall this first assignment as one of the tougher ones -- not so much due to code/algorithm complexity, but because of the effort needed to become comfortable with the new tools/environment and find your way through the sparse, unforgiving world of C. Celebrate this important milestone and remember the investment you make now in gaining proficiency will pay off throughout the quarter.

• What does the return value from fscanf signify? Why is it important to check it?
• The fragment-reading code employs the idiom of using maximum-sized storage on stack temporarily and copying to persistent right-sized dynamic memory. Explain why this technique is necessary/appropriate given the characteristics of the stack and heap.
• Write an expression that reports whether a given char* has a matching prefix/suffix N chars long. What would happen if your expression were evaluated with a value for N that was longer the string's length?
• What is the purpose of the realloc function? What happens if you attempt to realloc a string that wasn't malloc'ed in the first place?
• How can you gauge whether your program has acceptable performance in terms of runtime or memory efficiency?

Lab2: Arrays and pointers

You should be continuing to build up your gdb and Valgrind repertoire and becoming comfortable with thinking about and manipulating memory/pointers in terms of raw bytes and addresses. Arrays and pointers are ubiquitous in C and a good understanding of them is essential.

• Although & applied to the name of a stack-allocated array (e.g. &buffer) is a legal and well-defined expression, it isn't really sensible. Explain why such use is a sure sign of an error/misunderstanding on the part of the programmer.
• Why must the caller catch the return value from realloc? Why doesn't realloc just re-assign the pointer when it's necessary to move the memory block?
• A Valgrind report complains that Address 0x420d50 is 0 bytes after a block of size 24 alloc'd . Your roommate insists Valgrind is off-base and paranoid because the program runs just fine. Explain to them why accessing memory "0 bytes after" is an actual problem, even though it might be asymptomatic in some contexts.
• Explain how to use lfind with an appropriate callback to re-implement the functionality of strlen.

Assign2: Void* client

All these gyrations with CMap/CVector were to bring about a rock-solid understanding of the client use of a void* interface. The critical mastery is correctly passing/receiving the void*s flying around: what level of indirection to use, what typecasts are needed, using * and & in exactly and only the necessary places. You should know without question how to determine the necessary level of indirection and correctly apply it. It's also valuable to understand and be able to reason through the consequences of getting it wrong.

• The CVector and regular C array fill similar needs. What CVector features make it more client-friendly than direct use of a raw C array? In what ways can the CVector be more difficult to use correctly than an array?
• Explain how ownership of memory works when storing a key/value pair into a CMap. The key passed to cmap_put is a char* -- where does it point to? is allocation required? who allocates it? is the pointer itself copied or its contents (the pointee)? will memory need to be freed? who will free it? What are the answers to those same questions for the void* value passed to cmap_put?
• The client can create a collection to store elements of any desired type, whether it be int, bool, struct, or pointers to any type. In which situations is it appropriate for the element to be a pointer type? What extra precautions need to be taken by the client when storing elements of pointer type?
• The stdlib function free matches the prototype for the cleanup client callback used by CVector/CMap. However it is never the right function to use as a cleanup fn. Explain why not.
• The original version of searchdir stored a char array as the CVector element. Your revised version stores a char* instead. Although arrays and pointers have a kind of equivalence in certain contexts, this is not the case here. Explain/diagram the differences between the two designs and the effect is has on the storage used and code needed.

Lab3: Bits, bytes, and ints

Now with command of the bitwise operators and understanding of masks, you can access and manipulate bits. Be sure to have a solid grasp on the representation of unsigned values as a binary polynomial and signed values in two's complement and be comfortable relating bitwise tweaks to changes in numeric value. Know what happens on assignment between integer family types of different bitwidths and signed-ness.

• Explain the difference between memcpy and memmove and when to use each.
• What are the three modifiers to gdb's x command? Show the x command to print a 2-member array of 4-byte integers in hex and again to print that same memory as 8 single-byte characters.
• Write an expression to create the integer bit mask that has all ones in the N most significant bits and zeros elsewhere.
• How can you determine if an integer bit pattern has a pair of consecutive 'on' bits? (Straightforward to do using a loop, but there is also a clever single expression...)
• Consider rounding the magnitude of an integer up to power of two (e.g. 3 rounds to 4, 4 to 4, 5 to 8, for negative: -3 rounds to -4, -4 to -4, and so on). What changes do you make to the bit pattern of a positive int to round to power of two? What about for a negative int?
• The argument to malloc is size_t (unsigned). Consider the erroneous call malloc(-1), which seems to make no sense at all. What happens when you try to compile such a call? What happens when it executes?

Assign3: Void* implementation

You are now unstoppable in terms of manipulating raw memory. You know how to use the type system to your advantage wherever you can, but also how to work without it where you must. You know the care required to make a proper call to memcpy/memmove, exactly where and why you need a typecast, and have increased vigilant about using the correct level of indirection.

• Why is it so beneficial to decompose the common expressions from CVector/CMap into shared helper functions rather than repeat code?
• Why must you typecast a void* in a pointer-arithmetic expression?
• Setting each field of a CMap cell (next, key, value) is best done with its own specific technique: next as assignment with typecast, key with strcpy, value using memcpy. What's the difference between those options? What makes one technique more appropriate than the others in a given situation?
• How does cvec_next use the previous to orient itself within the iteration? What happens if the client passes an invalid pointer for previous? How about for cmap_next? Would it be possible to reliably detect/assert that the client has passed an invalid pointer? Why or why not?

Lab4: Floats

You have worked through bit patterns for a variety of float values and learned how the representation is organized. You have a feel for the inherent compromises in this system: which values are representable, which are not, the gaps in the floating point number line, and what kind of error/approximation to expect from a floating point calculation.

• Explain the reasons why a floating point constant may have to be rounded on assignment to a float variable. Are any integer constants rounded on assignment to a float? Which?
• Consider rounding a float down to the nearest power of two (e.g. 120 rounds down to 64, .82 rounds to .5, and so on). What changes do you make to the bit pattern of a normalized float value to round down to power of two? What about rounding down a denormalized float value?
• Explain how a lexicographical comparison of the float bits can be used determine relative ordering. Does this also work for negative floats? Why or why not?
• Is floating point addition guaranteed to be associative? Explain why or why not.
• What is the difference between the assignments below that assign ui from float f?

  unsigned int ui = (unsigned int)f;
  unsigned int ui = *(unsigned int *)&f;
  

Assign4: Bits and numbers

You should feel a growing mastery of bitwise manipulation. You have a solid understanding of bit patterns as they relate to the representations for ints and floats and how they dictate the behavior and limitations of the two numeric systems.

• Consider all negative int’s whose absolute value is an exact power of two (-8, -32 and so on). What do their bit patterns have in common?
• Give a bitwise expression to zero the upper N bits of an unsigned int V. What does this expression compute numerically?
• If the float bits were re-apportioned to designate 7 bits for the exponent and 24 for the significand, how would this change what float values could be represented (e.g. epsilon, bias, dynamic range, number of denorms)?
• When moving downward from a float that is an exact power of two to its neighbor, the exponent decrements by one, except for the special case of moving from the minimum normalized float to the largest denormalized. The exponent bits change from 00000001 to 00000000, but the value of the exponent 2-126 is unchanged. Explain why the special case. What would be the effect if the exponent 2-127 was used for the denorms instead?
• The older IA32 architecture is limited to eight integer registers (%eax-%esi). When transitioning to the 64-bit x86-64, eight new registers (%r8-%r15) were added. This is a very welcome improvement but this extension had a profound effect on the instruction set and instruction encoding. Explain, using pushq as an example.

Lab5: Assembly

You now have tools for disassembling object files and have been introduced to the debugger commands used at the assembly level. The hands-on practice relating C code to its compiled assembly and reverse-engineering from assembly to C is great preparation for the upcoming binary bomb assignment.

• How can you get the value of a variable during execution that gdb reports has been <optimized out>?
• Give an example of a C sequence/expression that could be compiled into a variety of different, but equivalent, asm instruction(s).
• What is the difference between sar and shr?
• How is the return value of a function communicated from the callee to the caller?
• For the instruction sequence below, what must be true about values of op1 and op2 for the branch to be taken? What changes if ja is substituted for jg?

  cmp op1,op2 
  jg target
  

Assign5: Assembly

After reverse-engineering the bomb, the assembly skills of CS107 students are unstoppable!

• What are some of the gdb commands that allow re-routing control in an executing program?
• How can you tell whether an lea instruction is doing an address calculation versus when it is merely arithmetic?
• What is the main indication that a passage of asm instructions contains a loop?
• Explain how the mechanics of function pointer work at the assembly level. (i.e. how a function is passed as an argument, how call is set up, what is same/what is different in a call through a function pointer versus an ordinary function call?)

Lab6: Stack

This is one of my favorites among the labs -- lots of neat exercises to explore! Having learned the gdb commands to dig around in the stack frames and being able to relate the contents of the stack to the runtime program state is valuable insight when debugging.

• Why are the registers used for function parameters completely fixed, yet no conventions apply to where locals are stored?
• Explain the rules for caller-saved versus callee-saved register use. What is the advantage of this arrangement relative to a simpler scheme such treating all registers as caller-saved (or callee-saved)?
• How is possible that the insertion/deletion of seemingly unrelated printf statement can make a difference in a program's behavior? (Michael showed one such situation in lecture, there was a slightly different variant in this lab)
• Compare the relative efficiency of passing a struct by value versus by reference.
• What are the signs in gdb that help you diagnose a stack overrun has trashed the return address?

Lab7: Build process

An important takeaway from this lab is to become familiar with various build tools (make, preprocessor, compiler, assembler, linker) and how each fits into the build process, especially so as to be able to diagnose and address any build issue you might run into now and in the future.

• Explain how a #define is processed.
• What is the difference between #include <math.h> and linking with the math library?
• Why are symbol addresses in a .o file such small values and so large in an executable?
• There are exactly two kinds of errors detected by the linker. What are they?

Assign6: Executable files and runtime stack

You have dissected your way through an ELF file and learned how to insert your code into a program to monitor/probe its runtime activities and in the process written a pretty cool developer tool -- way to go!

• Explain how the contents of an ELF file are designed for efficient, direct access which requires no translation from the on-disk representation.
• What does strip do to an object file? If you strip a .o file, can it still be linked into an executable? If you strip an executable, can it still be run?
• Explain the mechanism behind the ccp approach to interposing on a library function. How does it differ from the ld approach?

Lab8: Optimization

Your killer reversing skills are just what is needed for examining the generated assembly and identifying gcc's cool transformations to make code run faster. Learning how to use Valgrind callgrind is another key tool to add to your developer arsenal.

• How can you use the callgrind profiler to measure instruction counts? What about to report on cache hits/misses?
• Do all asm instructions have an equivalent runtime cost (i.e. does a push instruction require same cycles to complete as cmp or div?) Does every instance of a particular asm instruction have a fixed cost (i.e. every push same? every xor same? every mov same?) Explain.
• Avoiding expense of function call/return is often cited for the motivation for inlining a function. What are the estimated savings in terms of number of instructions and effect on cache? Inlining also enables additional optimization opportunities, given that gcc applies most transformations within a function, but not inter-procedurally. Do you expect these gains to be more or less significant than the call overhead? Explain.
• What is meant by loop unrolling? In what situations might it provide a performance win?

Assign7: Heap

A former student likened heap allocator to a "victory lap" -- a chance to put your hard-won expertise to work and enjoy the triumph of seeing what you are now capable of! Success requires heroic skills with void* pointers, raw memory manipulation, assembly, optimization of both code/memory, and deep proficiency with tools. You have just written an allocator that competes head-on with the industrial-strength libc version -- how crazy-awesome is that??!

• What are the main challenges in making malloc fast? What makes for a fast free?
• Explain the difference between internal and external fragmentation. Which is the greater threat to utilization?
• True or False: If you have built a super-fast malloc/free, implementing realloc in terms of those operations will also be super-fast.
• Throughput and utilization are often viewed in opposition. How might improved throughput come at the expense of lowered utilization (or vice versa). Are there choices that lead to wins in both?