www.cs.cmu.edu

www.cs.cmu.edu

Carnegie Mellon Recitation 10: Malloc Lab Instructors October 21, 2019 Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 1 Carnegie Mellon Administrivia Malloc checkpoint due Tuesday, October 29! yeeT Malloc final due the week, Tuesday, November 5! yooT Malloc Bootcamp: Sunday, October 27 at Rashid Auditorium, 7-9PM

We will cover fun and flirty ways to succeed post-malloc checkpoint! Tell your friends to come (if theyre in 213 (if they want to come (dont force your friends to do things they dont want to do thats not what friends are for))) Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 2 Carnegie Mellon 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 3 Carnegie Mellon Outline Concept How to choose blocks Metadata

Debugging / GDB Exercises Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 4 Carnegie Mellon 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 5 Carnegie Mellon Concept 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 6 Carnegie Mellon 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 7 Carnegie Mellon Concept (Implicit list)

2. Uses the structure made to choose an appropriate location to allocate new memory. Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 8 Carnegie Mellon Concept (Implicit list) 3. Updates the structure when the user frees a block of memory. Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 9 Carnegie Mellon

Concept (Implicit list) 3. Updates the structure when the user frees a block of memory. Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 10 Carnegie Mellon Goals 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 11 Carnegie Mellon This is pretty slow most explicit list implementations get above 2000 Kops/sec Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 12

Carnegie Mellon Allocation methods in a nutshell Implicit list: a list is implicitly formed by jumping between blocks, using knowledge about their sizes. Allocated Free Allocated Free Allocated Explicit list: Free blocks explicitly point to other blocks, like in a linked list.

Understanding explicit lists requires understanding implicit lists Free Free Segregated list: Multiple linked lists, each containing blocks in a certain range of sizes. Understanding segregated lists requires understanding explicit lists Free Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition Free 13 Carnegie Mellon

Choices 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%. Dont hard-code for individual trace files - youll 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition

14 Carnegie Mellon Finding a Best Block 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 dont have to implement seglists and run mdriver to answer this. Thats, 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 15 Carnegie Mellon Metadata 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 16 Carnegie Mellon 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 17

Carnegie Mellon 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 18 Carnegie Mellon Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 19

Carnegie Mellon 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 youre overwriting by stepping through with gdb Overlapping payloads Problem: having unique blocks whose payloads overlap in memory Solution: literally print debugging everywhere finding where youre overlapping by stepping through with gdb Segmentation fault Problem: accessing invalid memory Solution: crying a little finding where youre accessing invalid memory by stepping through with gdb

Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 20 Carnegie Mellon 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, weve 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 21 Carnegie Mellon The *Real* Activity: GDB Practice Using GDB well in malloclab can save you HOURS1, 2 of debugging time Average 20 hours using GDB for B on malloclab Average 23 hours not using GDB for B on malloclab * Average time is based on Summer 2016 survey results Form pairs wget https://www.cs.cmu.edu/~213/activities/f19-rec-malloc.tar tar xvf f19-rec-malloc.tar cd f19-rec-malloc make

Two buggy mdrivers Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 22 Carnegie Mellon Debugging Guidelines If you have this problem... Ran into segfault Trace results dont match yours Dont know what trace output should be Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition

You might want to... Locate a segfault - run <> backtrace list Reproduce results of a trace - Run with gdb - gdb args 23 Carnegie Mellon

Debugging mdriver $ gdb --args ./mdriver -c traces/syn-mix-short.rep (gdb) run (gdb) backtrace (gdb) list Optional: Type Ctrl-X Ctrl-A to see the source code. Dont linger there for long, since this visual mode is buggy. Type that key combination again to go back to console mode. (Or use cgdb - see Piazza post) 1) What function is listed on the top of backtrace? 2) What line of code crashed? 3) How did that line cause the crash? Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 24 Carnegie Mellon

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 *)

Shows struct contents Remember the output from (gdb) bt? (gdb) frame 1 Jumps to the function one level down the call stack (aka the function that called write_footer) Ctrl-X, Ctrl-A again if you want to see visuals

What was the caller function? What is its purpose? Was it writing to block or block_next when it crashed? Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 25 Carnegie Mellon Thought process while debugging write_footer crashed because it got the wrong address for the footer The address was wrong because the header of the block was some garbage value Since write_footer uses get_size(block) after all But why in the world does the header contain garbage?? The crash happened in place, which basically splits a free block into two and uses the first one to store things.

Hm, block_next would be the new block created after the split? The one on the right? The header would be in the middle of the original free block actually. Wait, but I wrote a new header before I wrote the footer! Right? Oh, I didnt. Darn. Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 26 Carnegie Mellon Heap consistency checker mm-2.c activates debug mode, and so mm_checkheap runs at the beginning and end of many of its functions. The next bug will be a total nightmare to find without this heap consistency checker*.

Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition *Even though the checker in mm-2.c is short and buggy 27 Carnegie Mellon Now you try debugging this - second example! $ gdb --args ./mdriver-2 -c traces/syn-array-short.rep (gdb) run Yikes what error are we getting? Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 28

Carnegie Mellon Now you try debugging this - second example! $ gdb --args ./mdriver-2 -c traces/syn-array-short.rep (gdb) run Yikes what error are we getting? ~garbled bytes~ * an accurate representation of whats actually going on in your blocks Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 29 Carnegie Mellon Now you try debugging this - second example!

(gdb) watch *0x8000026d0 (gdb) run (gdb) continue (gdb) continue /* Track from first garbled payload */ /* Keep going until coalesce_block */ (gdb) backtrace (gdb) list Ah, it seems like nothings amiss Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 30

Carnegie Mellon Running with mdriver-2-dbg... Lets run it with mdriver-2-dbg, which has a lower optimization - will give us more insight, like the stack trace below (in the same gdb session) (gdb) file mdriver-2-dbg (gdb) run (gdb) continue (gdb) list Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 31 Carnegie Mellon

Running with mdriver-2-dbg... Now try printing out the values of prev_alloc / next_alloc... (gdb) print prev_alloc (gdb) $1 = %rip, theyre optimized out! We have to change the optimization level to get what we truly want. Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 32 Carnegie Mellon Running with mdriver-2-dbg... Go into your Makefile (vim Makefile) => change COPT_DBG = O0 so that all local variables are preserved $ make clean $ make $ gdb --args ./mdriver-2-dbg -d 2 -c

traces/syn-mix-short.rep (gdb) b mm-2.c:450 /* Cut to the chase */ (gdb) run (gdb) continue (gdb) print next_alloc (gdb) $1 = true /* SUCCESS! */ Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 33 Carnegie Mellon Strategy - Suggested Plan for Completing Malloc 0. Start writing your checkheap!

1. Get an explicit list implementation to work with proper coalescing and splitting 3. Get to a segregated list implementation to improve utilization 4. Work on optimizations (each has its own challenges!) - Remove footers - Decrease minimum block size - Reduce header sizes Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 34 Carnegie Mellon Strategy - Suggested Plan for Completing Malloc 0. Start writing your checkheap! Keep writing your checkheap! 1. Get an explicit list implementation to work with proper

coalescing and splitting Keep writing your checkheap! 3. Get to a segregated list implementation to improve utilization Keep writing your checkheap! 4. Work on optimizations (each has its own challenges!) - Remove footers Keep writing your checkheap! - Decrease minimum block size - Reduce header sizes Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 35 Carnegie Mellon MallocLab Checkpoint Due next Tuesday!

Checkpoint should take a bit less than half of the time you spend overall on the lab. please write checkheap or we will scream Read the write-up. Slowly. Carefully. Use GDB - watch, backtrace 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition 36 Carnegie Mellon 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 if : Only stops execution when the expression holds true

Ctrl-X Ctrl-A or cgdb for visualization Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition 37

Recently Viewed Presentations

  • Evolution  The process of biological change by which

    Evolution The process of biological change by which

    Gradualism emphasizes slow changes on Earth over long periods of time, while catastrophism emphasizes change through natural disasters. In 1831, what ship did Darwin take that enabled him to travel around the world for 5 years collecting specimens and making...
  • PERITONITES - Free

    PERITONITES - Free

    PERITONITES TRAITEMENT Urgent associant traitement chirurgical et médical Aspiration gastrique, sondage urinaire, voie veineuse EXPANSION VOLEMIQUE Hypovolémie constante vraie et relative Arrêt des apports oraux Vomissements Accroissement des pertes insensibles/fièvre Troisième secteur CORRECTION DES TROUBLES METABOLIQUES SUPPORT VASO ...
  • Beyond Lab Reports: A Fresh Approach to Technical Writing

    Beyond Lab Reports: A Fresh Approach to Technical Writing

    You will be presenting seakeeping results on your capstone designs to a panel of naval architecture and marine engineering professionals. The software package used, Maxsurf. Motions, depends on a simplified analysis method (known as strip theory).
  • Chemical Kinetics Study of how rapidly reactions proceed

    Chemical Kinetics Study of how rapidly reactions proceed

    Details of process from reactants to products - mechanism Thermodynamics determines the direction in which reactions proceed spontaneously and equilibrium conditions, but not the rate at which equilibrium is reached. For a complete picture of a chemical reaction need information...
  • Session 2 Welcome to the Self-Esteem in Second

    Session 2 Welcome to the Self-Esteem in Second

    Self-Esteem in Second Life. Workshop for Women with SCI. A research study conducted by: Center for Research on Women with Disabilities (CROWD) Spinal Cord Injury and Disability Research Center (SCIDR) Reminders. Turn off phones, pagers, and non-adaptive equipment.
  • Plug-In 2009 Template

    Plug-In 2009 Template

    Workshop. Life is an electric highway: A review of successful PEV uptake policies globally. Jonn Axsen. Simon Fraser University. May 14, 2015. Renewable Cities: Global Learning Forum
  • Annual Rate of Ambulatory Care Visits, U.S. 2001-2002

    Annual Rate of Ambulatory Care Visits, U.S. 2001-2002

    EFFICIENCY Percent of primary care physicians using electronic medical records Source: Commonwealth Fund National Scorecard on U.S. Health System Performance, 2008 2001 2006 United States Ambulatory rate data from Vital and Health Statistics, Series 13, Number 159, February 2006 Hospital...
  • Community Action Agency Board Governance May 16, 2017

    Community Action Agency Board Governance May 16, 2017

    One must be in for the ups and downs. Each member is representing the home agency, as well as the nationwide network. At the start of service to the board, not only is there a hope of collective difference because...