Goals

This homework (shorter than usual since project 1 is due the same day) is intended to get you thinking about how bugs in the storage allocation code or in a user program might cause damage to the free block list.

Reading

Section 8.7 in K&R. The code is available for experimenting online at ~cs61c/files/lab/3/stgmgmt.c.

Submission instructions

For exercise 1, submit a file named freeListIsOK.txt in a directory named hw3_1. This homework is due before class on Wednesday, September 19.

This is not a partnership assignment. Hand in your own work.

Exercise 1 (2 points)

The K&R code is rather concise; an attempt to modify it might result in bugs due to the code's complexity. Moreover, the users of the storage management functions might have bugs in their own programs, for instance, accidentally freeing a section of memory twice, or overwriting an array. Some of these bugs will result in infinite loops or crashes. With others, the program will keep running, but its internal data structures may be damaged. In this exercise, you will think of ways that the free list of blocks can be damaged, and design a consistency-checking function to reveal them.

In pseudocode, design a C function named freeListIsOK that checks the consistency of the free list managed by the K&R storage management code. Your function should return true if the free list passes all your tests, and false otherwise. Your pseudocode should be written in detail specific enough for another CS 61C student to immediately be able to translate it to C.

One example of something you would be unable to detect is a missing free block, that is, a block that's been freed that doesn't appear in the free list. Your freeListIsOK function should, however, check that entries in the list are correct, for instance, that the sizes of all blocks other than the first are at least 2, and that the size of the first block is 0. There are at least four other significantly different things to check for. A good place to start is to examine the consequences of overwriting part of a block, or passing an inappropriate argument to free.

Put your pseudocode in a file named freeListIsOK.txt in a top-level directory named hw3_1 for submission.

Exercise 2 (2 points)

This is for CS 61C students only, not CS 61CL students.

Point a browser at bspace.berkeley.edu, use your Calnet ID to authenticate yourself, click on the "COMPSCI 61C LEC 001 Fa07" tab at the top, and click on "Introductory Survey" on the first screen. (You may have to click on "Quiz and Survey" first.) Then answer the survey questions. When you're finished, click the "Submit" button.