15-213: Introduc7on to Computer Systems Recita7on 12: Monday, Nov. 16th, 2015
Copyright By PowCoder代写 加微信 powcoder
¢ Malloc Lab due Thursday Nov 19th
¢ Some errors are iden7fied by the driver
¢ The error message is straighJorward in most cases
§ “garbled byte” means part of the payload returned to the user has
been overwriOen by your allocator
§ “out of memory” occurs when the memory is used very inefficiently, or there are lost blocks
¢ But most of the 7mes…
¢ Do “gdb mdriver” and “run” to find out which line segfaults
§ Note that a segfault occurring at line 200 could actually be caused by a bug on line 70
¢ To resolve a segfault, it is necessary to find the earliest 7me things went wrong.
¢ One way to do this is to print the whole heap before/aXer relevant func7ons
§ Scroll up from the point of segfault and find the earliest opera7on that makes the heap look wrong
§ Some7mes this gives too much informa7on, not all of which are useful
¢ The heap checker can make this easier
§ Checks viola7on of invariants (corrup7on of the heap)
Heap Checker
¢ Once you’ve seOled on a design, write the heap checker that checks all the invariants of the par7cular design
¢ The checking should be detailed enough that the heap check passes if and only if the heap is truly well-formed
¢ Call the heap checker before/aXer the major opera7ons whenever the heap should be well-formed
¢ Define macros to enable/disable it conveniently § e.g.
Invariants (non-exhaus?ve)
¢ Block level:
§ Header and footer match § Payload area is aligned
¢ List level:
§ Next/prev pointers in consecu7ve free blocks are consistent
§ Free list contains no allocated blocks
§ All free blocks are in the free list
§ No con7guous free blocks in memory (unless you defer coalescing) § No cycles in the list (unless you use circular lists)
§ Segregated list contains only blocks that belong to the size class
¢ Heap level:
§ Prologue/Epilogue blocks are at specific loca7ons (e.g. heap boundaries)
and have special size/alloc fields
§ All blocks stay in between the heap boundaries
¢ And your own invariants (e.g. address order)
Hare and Tortoise Algorithm
¢ Detects cycles in linked lists
¢ Set two pointers “hare” and “tortoise” to the beginning of
¢ During each itera7on, move the hare pointer forward two nodes and move the tortoise forward one node. If they are poin7ng to the same node aXer this, the list has a cycle.
¢ If the hare reaches the end of the list, there are no cycles.
Other things to watch for
¢ Unini7alized pointers and/or memory
¢ Make sure mm_init() ini7alizes everything
§ It is called by the driver between each itera7on of every trace
§ If something is overlooked, you might be able to pass every single trace file, but the complete driver test will fail
¢ To check for Illegal accesses, unini7alized values…
Asking for help
¢ It can be hard for the TAs to debug your allocator, because this is a more open-ended lab
¢ Before asking for help, ask yourself some ques7ons:
§ What part of which trace file triggers the error?
§ Around the point of the error, what sequence of events do you expect? § What part of the sequence already happened?
¢ If you can’t answer, it’s a good idea to gather more informa7on…
§ How can you measure which step worked OK? § prinJ, breakpoints, heap checker…
Asking for help
¢ Bring to us a detailed story, not just a “plot summary” § “Alloca7ons of size blah corrupt my heap aXer coalescing the
previous block at this line number…” is detailed § “It segfaults” is not
¢ Most importantly: don’t hesitate to come to office hours if you really need help
Beyond Debugging: Error preven?on
¢ It is hard to write code that is completely correct the first 7me, but certain prac7ces can make your code less error-prone
¢ Plan what each func7on does before wri7ng code § Draw pictures when linked list is involved
§ Consider edge cases when the block is at start/end of list
¢ Write pseudocode first
¢ Document your code as you write it
Beyond Debugging: Version control
¢ “I had 60 u7l points just 5 minutes ago!”
¢ Save the allocator aXer each major progress
¢ Most basic: copy files around using the cp command
¢ Alterna7vely: keep different versions in separate c files, and use “ln –s mm-version-x.c mm.c” to start using a par7cular version
¢ Or use git/svn/cvs…
§ Make sure your repository is private if you use remote repos
Op?miza?on
¢ To achieve beOer performance, some7mes you would want to tweak certain parameters.
§ Number of size classes, the separa7on of size classes, the amount by which the heap is extended (CHUNKSIZE)…
¢ It is beOer to write modular and encapsulated code so that changing the parameters only requires changing a few lines of code
§ Use macros wisely
Op?miza?on
¢ When you hit a boOleneck, find which part is limi7ng your performance
¢ A profiler is good for this kind of job
¢ To use gprof:
§ Change the Makefile to add “-pg” to the compila7on flag § Run the driver. This will generate a file called gmon.out § Run “gprof ./mdriver” to see the result
§ Don’t forget to change the Makefile back
Final Words
¢ Start now, if not already
¢ Come to office hours early
¢ Write the heap checker well
¢ Be prepared to start over several 7mes
¢ Before handing in, check:
§ Does the header comment contain a detailed descrip7on of your
§ Is the indenta7on correct? Any line over 80 chars? (go to autolab to verify these)
¢ Good luck!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com