Lecture Notes on Memory Management 15 122 Principles of Imperative Computation Frank Pfenning Lecture 22 November 11 2010 1 Introduction Unlike C0 and other modern languages like Java C or ML C requires programs to explicitly manage their memory Allocation is relatively straightforward like in C0 requiring only that we correctly calculate the size of allocated memory Deallocating freeing memory however is difficult and error prone even for experienced C programmers Mistakes can either lead to attempts to access memory that has already been deallocated in which case the result is undefined and may be catastrophic or it can lead the running program to hold on to memory no longer in use which may slow it down and eventually crash it when it runs out of memory The second category is a so called memory leak Your goal as a programmer should therefore be You should never free memory that is still in use You should always free memory that is no longer in use Freeing memory counts as a final use so the goals imply that you should not free memory twice And indeed in C the behavior of freeing memory that has already been freed is undefined and may be exploited by and adversary The golden rule of memory management in C is You allocate it you free it By inference if you didn t allocate it you are not allowed to free it In the remainder of the lecture we explore how this rule plays out in common situations L ECTURE N OTES N OVEMBER 11 2010 Memory Management 2 L22 2 Simple Libraries As a first example consider again the stack data structure discussed in the last lecture As a client we are not supposed to know or exploit the implementation of stacks and we therefore cannot free the elements of the structure directly Moreoever we as the client did not perform the actual allocation so it is up to them the library to free the allocated space In order to allow this the data structure implementation must provide an interface function to free allocated memory void stack free stack S S must be empty Because in this first scenario the stack must be empty the implementation is simple void stack free stack S REQUIRES is stack S stack empty S free S As a client we call this usually in the same scope in which we create a stack stack S stack new stack free S In this simple scenario we could successively pop elements of the stack and free them until the stack is empty and then free S in the manner shown above 3 Freeing Internal Structure We would like to call stack free S even if S is non empty In general for richer data structures the simple idea of successively deleting elements may not be possible and not even be supported in the interface This means the stack free function would have to look something like the following passing the buck to another function to free lists void stack free stack S REQUIRES is stack S list free S top free S L ECTURE N OTES N OVEMBER 11 2010 Memory Management L22 3 Clearly the list free function should not be visible to the client just like the whole list type is not visible This function would go over the list and free each node but it would be incorrect to write the following void list free list p while p NULL free p p p next incorrectly uses deallocated memory return In the marked line we would access the next field of the struct that p is pointing to but this has been deallocated in the preceding line We must introduce a temporary variable q to hold the next pointer which is a characteristic pattern for deallocation void list free list p while p NULL list q p next free p p q return What happens to the data stored at each node Clearly the library code cannot free this data because it did not allocate it Doing so would violate the Golden Rule On the other hand the client may not have any way to do so For example the stack might be the only place the data are stored in which case they would become unreachable after the list has been deallocated With a garbage collector this is a common occurrence and the correct behavior because the garbage collector will now deallocate the unreachable data With explicit memory management we need a different solution 4 Function Pointers A general solution is to pass a function as an argument to stack free and in turn to list free whose reponsibility it is to free the embedded data elements The client knows what this function should be and is therefore in L ECTURE N OTES N OVEMBER 11 2010 Memory Management L22 4 a position to pass it to the library The library then applies this function to each data element in the list just before freeing the node where it is stored Actually in C functions are not first class so we pass a pointer to a function instead The syntax for function pointers is somewhat arcane Here is what the interface declaration of stack free looks like void stack free stack S void data free void x The first argument name S is a stack The second argument has name data free We read the declaration starting at the inside and moving outwards considering what kind of operation can be applied to the argument 1 data free names an argument 2 data free shows it can be dereferenced and therefore must be a pointer 3 data free void x means that the result of dereferencing data free must be a function that can be applied to an argument of type void 4 void data free void x finally shows that this function does not return a value In summary data free names a pointer to a function expecting a void pointer as argument and returning no value Its effect is inteded to free the data element it was given The stack is a generic data structure so for reasons discussed in the last lecture the data element is viewed as having type void The implementation of stack free is actually quite straightforward Since it doesn t hold any data element it just passes the function pointer to the list free function void stack free stack S void data free void x REQUIRES is stack S list free S top data free free S L ECTURE N OTES N OVEMBER 11 2010 Memory Management L22 5 Freeing the list elements has some pitfalls Consider the following simple attempt void list free list p void data free void x while p NULL list q p next data free p data free p p q return This actually has two somewhat subtle bugs See if you can spot them before reading on L ECTURE N OTES N OVEMBER 11 2010 Memory Management L22 6 The first problem is that data free is a function pointer and therefore could be null Attempting to dereference it would yield undefined behavior The convention …