IntroductionSimple LibrariesFreeing Internal StructureFunction PointersDouble FreeStack AllocationPointer Arithmetic in COperations on Generic DataLecture Notes onMemory Management15-122: Principles of Imperative ComputationFrank PfenningLecture 22November 11, 20101 IntroductionUnlike C0 and other modern languages like Java, C#, or ML, C requires pro-grams to explicitly manage their memory. Allocation is relatively straight-forward, like in C0, requiring only that we correctly calculate the size ofallocated memory. Deallocating (“freeing”) memory, however, is difficultand error-prone, even for experienced C programmers. Mistakes can ei-ther lead to attempts to access memory that has already been deallocated,in which case the result is undefined and may be catastrophic, or it canlead the running program to hold on to memory no longer in use, whichmay slow it down and eventually crash it when it runs out of memory. Thesecond 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 shouldnot free memory twice. And, indeed, in C the behavior of freeing mem-ory that has already been freed is undefined and may be exploited by andadversary.The golden rule of memory management in C isYou 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 incommon situations.LECTURE NOTES NOVEMBER 11, 2010Memory Management L22.22 Simple LibrariesAs a first example, consider again the stack data structure discussed in thelast lecture. As a client, we are not supposed to know or exploit the im-plementation of stacks and we therefore cannot free the elements of thestructure directly. Moreoever, we (as the client) did not perform the ac-tual 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 aninterface 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 implementationis 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 stackstack S = stack_new();...stack_free(S);In this simple scenario we could successively pop elements of the stack andfree them until the stack is empty, and then free S in the manner shownabove.3 Freeing Internal StructureWe 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 elementsmay not be possible and not even be supported in the interface. This meansthe 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);}LECTURE NOTES NOVEMBER 11, 2010Memory Management L22.3Clearly, the list_free function should not be visible to the client, just likethe whole list type is not visible. This function would go over the list andfree 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 ispointing to, but this has been deallocated in the preceding line. We mustintroduce a temporary variable q to hold the next pointer, which is a char-acteristic 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 codecannot free this data, because it did not allocate it. Doing so would violatethe Golden Rule! On the other hand, the client may not have any way todo 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 deal-located. With a garbage collector, this is a common occurrence and thecorrect behavior, because the garbage collector will now deallocate the un-reachable data. With explicit memory management we need a differentsolution.4 Function PointersA general solution is to pass a function as an argument to stack_free (andin turn to list_free) whose reponsibility it is to free the embedded dataelements. The client knows what this function should be, and is therefore inLECTURE NOTES NOVEMBER 11, 2010Memory Management L22.4a position to pass it to the library. The library then applies this function toeach 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 func-tion instead. The syntax for function pointers is somewhat arcane. Here iswhat 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 namedata_free. We read the declaration starting at the inside and moving out-wards, 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 apointer.3. (*data_free)(void* x) means that the result of dereferencing data_freemust be a function that can be applied to an argument of type void*.4. void (*data_free)(void* x) finally shows that this function doesnot 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 freethe data element it was given. The stack is a generic data structure, so forreasons discussed in the last lecture, the data element is viewed as havingtype void*.The implementation of stack_free is actually quite straightforward.Since it doesn’t hold any data element, it just passes the function pointer tothe 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);}LECTURE NOTES NOVEMBER 11, 2010Memory Management L22.5Freeing the list elements has some pitfalls. Consider the following sim-ple 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 =