Recitation 7: Malloc Lab
Monday, October 18th, 2021
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Copyright By PowCoder代写 加微信 powcoder
⬛ Malloc checkpoint due October 26th
⬛ Malloc final due November 2nd
⬛ October 29th 7-9 pm (recommended)
⬛ PLEASE START EARLY!
⬛ WRITE CHECKHEAP OR NO OH HELP!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Checkpoint Submission
Style Grading
▪ We will grade your checkheap with your checkpoint submission!
Things to Remember:
▪ Document checkheap
▪ See writeup for what to include in checkheap
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Git Reminders
⬛ Style grades for CacheLab have been released!
▪ Please use detailed commit messages – things like “DONE” or “did
a thing” aren’t enough
▪ You should be committing often as you work on your code
▪ Especially for malloc: git diff can show what you changed since your last working commit
▪ Also allows you to restore your hard work in case your file gets deleted accidentally…
⬛ Commit early, commit often 😤
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ How to choose blocks
⬛ Metadata
⬛ Debugging / GDB Exercises
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
What is malloc?
⬛ A function to allocate memory during runtime (dynamic memory allocation).
▪ More useful when the size or number of allocations is unknown until runtime (e.g., data structures)
⬛ The heap is a segment of memory addresses reserved almost exclusively for malloc to use.
▪ Your code directly manipulates the bytes of memory in this section.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ Overall, malloc does three things:
1. Organizes all blocks and stores information about them
in a structured way.
2. Uses the structure made to choose an appropriate location to allocate new memory.
3. Updates the structure when the user frees a block of memory.
This process occurs even for a complicated algorithm like segregated lists.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Concept (Implicit list)
1. Connects and organizes all blocks and stores information about them in a structured way, typically implemented as a singly linked list
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Concept (Implicit list)
2. Uses the structure made to choose an appropriate location to allocate new memory.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Concept (Implicit list)
3. Updates the structure when the user frees a block of memory.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Concept (Implicit list)
3. Updates the structure when the user frees a block of memory.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Coalesce: Case 1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Coalesce: Case 2
Block to be freed
Combined A+B C
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Coalesce: Case 3
Block to be freed
Combined B+C
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Coalesce: Case 4
Block to be freed
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Combined A+B+C
⬛ Run as fast as possible
⬛ Waste as little memory as possible
⬛ Seemingly conflicting goals, but with the library malloc call cleverness you can do very well in both areas!
⬛ The simplest implementation is the implicit list. mm.c uses this method.
▪ Unfortunately…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
This is pretty slow… most explicit list implementations get above 2000 Kops/sec
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Allocation methods in a nutshell
⬛ Implicit list: a list is implicitly formed by jumping between blocks, using knowledge about their sizes.
⬛ Explicit list: Free blocks explicitly point to other blocks, like in a linked list.
▪ Understanding explicit lists requires understanding implicit lists
⬛ Segregated list: Multiple linked lists, each containing
blocks in a certain range of sizes.
▪ Understanding segregated lists requires understanding explicit lists Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ What kind of implementation to use?
▪ Implicit list, explicit list, segregated lists, binary tree methods, etc.
▪ You can use specialized strategies depending on the size of allocations
▪ Adaptive algorithms are fine, though not necessary to get 100%.
▪ Don’t hard-code for individual trace files – you’ll get no credit/code deductions!
⬛ What fit algorithm to use?
▪ Best fit: choose the smallest block that is big enough to fit the requested
allocation size
▪ First fit / next fit: search linearly starting from some location, and pick the first block that fits.
▪ Which is faster? Which uses less memory?
▪ “Good enough” fit: a blend between the two
⬛ This lab has many more ways to get an A+ than, say, Cache Lab Part 2 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ Suppose you have implemented the explicit list approach ▪ You were using best fit with explicit lists
⬛ You experiment with using segregated lists instead. Still using best fits.
▪ Will your memory utilization score improve?
Note: you don’t have to implement seglists and run mdriver to
answer this. That’s, uh, hard to do within one recitation session.
▪ What other advantages does segregated lists provide?
⬛ Losing memory because of the way you choose your free
blocks is called external fragmentation.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ All blocks need to store some data about themselves in order for malloc to keep track of them (e.g. headers)
▪ This takes memory too…
▪ Losing memory for this reason is called internal fragmentation.
⬛ What data might a block need?
▪ Does it depend on the malloc implementation you use? ▪ Is it different between free and allocated blocks?
⬛ Can we use the extra space in free blocks? ▪ Or do we have to leave the space alone?
⬛ How can we overlap two different types of data at the same location?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
In a perfect world…
Setting up the blocks, metadata, lists… etc (500 LoC)
+ Finding and allocating the right blocks (500 LoC)
+ Updating your heap structure when you free (500 LoC) =
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
In reality…
Setting up the blocks, metadata, lists… etc (500 LoC)
+ Finding and allocating the right blocks (500 LoC)
+ Updating your heap structure when you free (500 LoC) + One bug, somewhere lost in those 1500 LoC =
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Common errors you might see
⬛ Garbled bytes
▪ Problem: overwriting data in an allocated block
▪ Solution: remembering data lab and the good ol’ days finding where you’re overwriting by stepping through with gdb
⬛ Overlapping payloads
▪ Problem: having unique blocks whose payloads overlap in memory
▪ Solution: literally print debugging everywhere finding where you’re overlapping by stepping through with gdb
⬛ Segmentation fault
▪ Problem: accessing invalid memory
▪ Solution: crying a little finding where you’re accessing invalid memory by stepping through with gdb
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
⬛ Try running $ make
If you look closely, our code compiles your malloc implementation with the -O3 flag.
This is an optimization flag. -O3 makes your code run as efficiently as the compiler can manage, but also makes it horrible for debugging (almost everything is “optimized out”).
For malloclab, we’ve provide you a driver, mdriver-dbg, that not only enables debugging macros, but compiles your code with -O0. This allows more useful information to be displayed in GDB
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Debugging Strategies
⬛ Write a heap checker!
▪ Checks the invariants of your heap to make sure everything is
well-formed
▪ If you write detailed error messages, you can see exactly why your heap is incorrectly formed
⬛ Use assertions in your functions!
▪ 122 style contracts can also help you catch where things go amiss
▪ Gives more information than a segfault
⬛ Use a debugger!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Debugging Guidelines
If you have this problem…
Ran into segfault
You might want to…
Locate a segfault
– backtrace – list
Reproduce results of a trace – Run with gdb
– gdb args
Trace results don’t match yours
Don’t know what trace output should be
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
What’s better than printf? Using GDB
● Use GDB to determine where segfaults happen!
● gdb mdriver will open the malloc driver in gdb
○ Type run and your program will run until it hits the segfault! ● step/next – (abbrev. s/n) step to the next line of code
○ next steps over function calls
● finish – continue execution until end of current function, then break
● print
results of function calls!)
○ Consider writing a heap printing function to use in GDB!
● x
○ x /a
○ See help p and help x for information about more formats
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Debugging mdriver
⬛ (gdb) x /gx block
▪ Shows the memory contents within the block
▪ In particular, look for the header.
⬛ (gdb) print *block
▪ Alternative: (gdb) print *(block_t *)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Using GDB – Fun with frames
■ backtrace – (abbrev. bt) print call stack up until current function
■ backtrace full – (abbrev. bt full) print local variables in each frame
(gdb) backtrace
#0 find_fit (…)
#1 mm_malloc (…)
#2 0x0000000000403352 in eval_mm_valid
(…) #3 run_tests (…)
#4 0x0000000000403c39 in main (…)
■ frame 1 – (abbrev. f 1) switch to mm_malloc’s stack frame ■ Good for inspecting local variables of calling functions
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Using GDB – Setting breakpoints/watchpoints
■ break mm_checkheap – (abbrev. b) break on “mm_checkheap()” ■ b mm.c:25 – break on line 25 of file “mm.c” – very useful!
■ b find_fit if size == 24 – break on function “find_fit()” if the local variable “size” is equal to 24 – “conditional breakpoint”
■ watch heap_listp – (abbrev. w) break if value of “heap_listp” changes – “watchpoint”
■ w block == 0x80000010 – break if “block” is equal to this value
■ w *0x15213 – watch for changes at memory location 0x15213
■ Can be very slow
■ rwatch
■ awatch
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Heap consistency checker
⬛ mm-2.c activates debug mode, and so mm_checkheap runs at the beginning and end of many of its functions.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
*Even though the checker in mm-2.c is short and buggy 33
CarneeggieieMelelollnon
Heap Checker
■ int mm_checkheap(int verbose); ■ critical for debugging
■ write this function early!
■ update it when you change your implementation
■ check all heap invariants, make sure you haven’t lost track of any part
of your heap
■ check should pass if and only if the heap is truly well-formed
■ should only generate output if a problem is found, to avoid cluttering up your program’s output
■ meant to be correct, not efficient
■ call before/after major operations when the heap should be
well-formed
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Heap Invariants (Non-Exhaustive)
■ Block level
■ What are some things which should always be true of every block
in the heap?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Heap Invariants (Non-Exhaustive)
■ Block level
■ header and footer match
■ payload area is aligned, size is valid
■ no contiguous free blocks unless you defer coalescing
■ List level
■ What are some things which should always be true of every
element of a free list?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Heap Invariants (Non-Exhaustive)
■ Block level
■ header and footer match
■ payload area is aligned, size is valid
■ no contiguous free blocks unless you defer coalescing
■ List level
■ next/prev pointers in consecutive free blocks are consistent
■ no allocated blocks in free list, all free blocks are in the free list
■ no cycles in free list unless you use a circular list
■ each segregated list contains only blocks in the appropriate size
■ Heap level
■ What are some things that should be true of the heap as a whole?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
CarneeggieieMelelollnon
Heap Invariants (Non-Exhaustive)
■ Block level
■ header and footer match
■ payload area is aligned, size is valid
■ no contiguous free blocks unless you defer coalescing
■ List level
■ next/prev pointers in consecutive free blocks are consistent
■ no allocated blocks in free list, all free blocks are in the free list
■ no cycles in free list unless you use a circular list
■ each segregated list contains only blocks in the appropriate size
■ Heap level
■ all blocks between heap boundaries, correct sentinel blocks (if used)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Strategy – Suggested Plan for Completing Malloc
0. Start writing your checkheap!
1. Get an explicit list implementation to work with proper
coalescing and splitting
2. Get to a segregated list implementation to improve utilization 3. Work on optimizations (each has its own challenges!)
– Remove footers
– Decrease minimum block size – Reduce header sizes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Strategy – Suggested Plan for Completing Malloc
0. Start writing your checkheap!
1. Get an explicit list implementation to work with proper
coalescing and splitting
2. Get to a segregated list implementation to improve utilization
Keep writing your checkheap!
3. Work on optimizations (each has its own challenges!)
Keep writing your checkheap!
– Remove footers
– Decrease minimum block size – Reduce header sizes
Keep writing your checkheap!
Keep writing your checkheap!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
MallocLab Checkpoint
⬛ Checkpoint should take a bit less than half of the time you spend overall on the lab.
Read the write-up. Slowly. Carefully.
⬛ Use GDB – watch, backtrace
please write checkheap or we will scream
⬛ Ask us for debugging help
▪ Only after you implement mm_checkheap though! You gotta learn
how to understand your own code – help us help you!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Appendix: Advanced GDB Usage
⬛ backtrace: Shows the call stack
⬛ up/down: Lets you go up/down one level in the call stack
⬛ frame: Lets you go to one of the levels in the call stack
⬛ list: Shows source code
⬛ print
▪ Runs any valid C command, even something with side effects like
mm_malloc(10) or mm_checkheap(1337)
⬛ watch
▪ Breaks when the value of the expression changes
⬛ break
⬛ Ctrl-X Ctrl-A or cgdb for visualization Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com