Lab sessions Tue Apr 06 to Thu Apr 08
Lab written by Julie Zelenski, with modifications by Nick Troccoli
Your weekly lab is a chance to collaboratively experiment and explore, ask and answer questions, and get hands-on practice in a supported environment. You will work in small groups, and as a whole section, on a set of lab exercises that revisit topics from recent lectures/readings. We are all working together to advance our knowledge of the material! Use the time to further practice your skills, help others, ask questions, and explore. We have also designed labs specifically to prepare you for assignments - the more you put into exploring problems and concepts during labs, the more it will pay off when you start the next assignment!
Lab starts all together in the main lab room, where you'll get a chance to get to know others in your lab. Your TA will then assign you to groups to start working on the first problem together. After each problem, the TA will have everyone return to the main room to discuss the problem, what you found, and what questions you have. Then you'll return to your small group rooms to work on the next problem.
For lab each week, we plan to mine our favorite open-source projects (musl libc, BusyBox unix utilities, Apple, Google and more) for interesting systems code to use as an object of study. We use this code to learn how various programming techniques are used in context, give insight into industry best practices, and provide opportunities for reflection and critique.
During this lab you will:
- practice with bits, bitwise operators and bitmasks
- read and analyze C code that manipulates bits/ints
- further practice with the edit-compile-test-debug cycle in the Unix environment
Clone the lab starter code by using the command below. This command creates a
lab1 directory containing the project files.
git clone /afs/ir/class/cs107/repos/lab1/shared lab1
1) Sharing Unix Joy (5 minutes)
Once you're in your assigned group room, introduce yourself to your fellow group-mates! How is everyone doing so far on getting comfortable in the Unix environment? What questions or tips do you have to share? Let's hear it!
In your shared lab document, write down (at least one) Unix/command-line video/resource/tip that your group wants to share with the rest of the lab. Prefix your idea with your group number and a fun name for your group--that way you'll remember it for next week, too!
2) Round Up (25 minutes)
round.c file to review the
round_up functions. Try compiling and running the program as you explore it! (you can ignore the warning generated by the parity program for now).
is_power_of_2is the same function we saw in lecture, that takes advantage of a unique bit-level property of powers of two. Review with your group what that property is, and what the relationship is between a power of two and its predecessor (e.g. number - 1) in terms of the bits the two values have in common.
round_upfunction returns the value of the first argument (
value) rounded up to the nearest multiple of the second (
multiple). The first (non-power of 2) case works for every number, power of 2 or not, but if the number is a power of 2, we can implement a more efficient alternative, which we've done here.
Q1: For the first case (non-power of 2), how are the arithmetic operations used to round up to the next multiple? Hint: watch out for integer division!
Q2: For the special case (power of 2), how is bitwise manipulation able to take the place of the expensive multiply/divide portion of the first case?
These functions show the advantage of being able to flip between interpretations. A number is just a bit pattern and can be manipulated arithmetically or bitwise at your convenience.
parity.c (20 minutes)
Now it's your turn to write some bitwise code and practice with Unix tools!
parity program reports the parity of its command-line argument. A value has odd parity if there are an odd number of "on" bits in the value, and even parity otherwise. Confirm your understanding by running the
samples/parity_soln program on various arguments.
The code in
parity.c was written by your colleague who claimed it is "complete", but on their way out the door they mutter something unintelligible about unfixed bugs. Uh oh... Your task is to test and debug the program using sanitycheck and the
Let's investigate! Work with your group, but follow the steps individually as well - hands-on practice is the best way to become familiar with GDB!
A helpful GDB reference is the CS107 GDB guide, listed under "Handouts" in the top toolbar.
- Compile the program using
make(ignore the ominous warning for now...) and run
./paritya few times on various values. Uh oh! It thinks every value has odd parity!
- Run it under the debugger. Start
gdb parity. We can use the
listcommand to print out parts of the code GDB is examining. Use
list compute_parityto print the
compute_parityfunction and note the line number where it updates the result inside the loop.
- Set a breakpoint on that line so that when we run the program in GDB, GDB will pause before executing that line and await further instructions. You can add a breakpoint by typing
XXXis either a function name or line number.
- Start the program by entering the
runcommand, followed by a command line argument (for the number to examine). GDB will start running the program and pause when it hits the breakpoint. Note that it pauses before it executes the line the breakpoint is on.
- When stopped at the breakpoint, print the value of
resultby using the
resultappears to be garbage. D'oh, it was never initialized! Is that even legal? In a safety-conscious language such as Java, the compiler may guard against this.
- Do a
maketo review the build warnings - luckily in this case (but perhaps not always!), the compiler seems to catch the issue. At runtime, the variable will use whatever junk value was left over in its memory location. But, lesson learned -- you will need to up your own vigilance when working with C.
- Add a correct initialization, build, and re-run to test your fix.
Now, run sanitycheck on
lab1 to see that your fixed parity passes all included tests. Looks good! However, sanitycheck is only as thorough as its test cases. We should continue testing.
- Run custom sanitycheck (
tools/sanitycheck custom_tests) with the additional test cases in
custom_tests. One of these tests fails due to timeout. It's not that the program is horribly inefficient, it is just stuck in an infinite loop.
- The best way to debug an infinite loop is to run the program under GDB, and once it stalls, stop the program using
Control-c. GDB will show you where the program was executing when it was stopped, and you can poke around and see what is going on. Run the parity program in GDB on a negative argument and let it go unresponsive.
Control-cto interrupt it and return control to gdb. Use the gdb
backtracecommand to see where the program is executing - this will display the current call stack, meaning what functions are currently executing.
stepthrough a few statements as it goes around the loop and gather information to diagnose why the loop is not exiting.
- Once you know what's gone wrong, edit the code to fix, rebuild, and test under both default and custom sanitycheck to verify you have squashed the bug. Way to go!
- Discuss with your group; what caused the infinite loop in the parity program? Review your process for narrowing in on this bug.
[Optional] Extra Problems
Finished with lab and itching to further exercise your bitwise skills? Check out our extra problems!
Nice work during lab1! It's okay if you don't completely finish all of the exercises during lab; your sincere participation for the full lab period is sufficient for credit. However, we highly encourage you to finish on your own whatever is need to solidify your knowledge.
TODO: At this time, if you'd like to make a CS107 study group with your group members, we encourage you to exchange contact info!
Also take a chance to reflect on what you got what from this lab and whether you feel ready for what comes next! The takeaways from lab1 should be proficiency with bitwise operations, constructing and using bitmasks, and a solid grasp on the representation of unsigned values as a binary polynomial and signed values in two's complement. Here are some questions to verify your understanding and get you thinking further about these concepts:
- 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). How does the bit pattern of a positive int differ from the bit pattern of the value after rounding to power of two? What about for a negative int?
- Give a bitwise expression to zero the upper N bits of an unsigned int V. What does this expression compute numerically?
- When do you supply the command-line arguments to a program you wish to run under gdb: when starting gdb or from within gdb when running the program?
- Chapter 2 of B&O has many excellent practice problems presented with solutions - check them out!