### Comp111: Operating Systems Classroom Exercise 13 Answers Memory Management Fall 2018

In class we have studied the buddy system for memory resource management. Let's do some simulation to make sure we understand it. In your simulations, please assume that:

1. no less than 16 bytes can be allocated via malloc.
2. the 16-byte block storage descriptor is physically located before the bytes to be used, so that the usable memory starts at the descriptor address+16.
3. the block descriptor has two 8-byte fields:
• a `next` pointer for use in the free list.
• a `size` integer that is the power of two that represents the block's total size.
E.g., if `size` is 5, then
• total block size is 25 = 32 bytes.
• total usable memory is 25-16 (descriptor) = 16 bytes.
4. `malloc` only calls `sbrk` in units of 8192 bytes, i.e., the call is of the form `sbrk(n*8192)` for n a positive integer.
(This is roughly the implementation of "BSD malloc".)
1. Exactly how much memory is allocated to me if I ask for 800 bytes from `malloc`? Exactly how much memory is added to the heap?
Answer: The allocator fits 800 bytes into 2p-16 for the smallest p. That is p=10, allocating 1024-16=1008 bytes. A total of 8192 bytes = 1 page is added to the heap (presuming that this is the first allocation).
2. Describe exactly what happens when one calls
```
int *foo = (int *)malloc(100*sizeof(int));
```
as the first `malloc` of a program. Assume that `sizeof(int)` is 8 (e.g., on `comp111.cs.tufts.edu`).
Answer: First note that this is related to the first problem, because `100*sizeof(int)==800`!
1. First malloc calls sbrk(8192);
2. The block of 8192 is subdivided into two 4096-byte blocks.
3. One block of 4096 is subdivided into two 2048-byte blocks.
4. One block of 2048 is subdivided into two 1024-byte blocks.
5. A pointer to the 16th byte of one of these 1024-byte blocks is returned to the process.
At the end, there is one element in the free lists for 212, 211, and 210 bytes, respectively.
3. Describe exactly what happens when one (subsequently) calls `free(foo)`.
Answer: `foo` points to 16 bytes beyond the descriptor, so a pointer to the descriptor can be recovered via the code
`struct descriptor *p=(struct descriptor *)((char *)foo-16);`
. We link `p` into the free list for 210 (`10==p->size`). `foo` is not changed.
4. Describe exactly what happens when one subsequently calls
```int *bar = (int *)malloc(10*sizeof(int));
```
Is `foo`'s memory reused? Why or why not?
Answer: Note that foo's memory is at the head of the 210 list, and we want 80 bytes, and thus want to allocate a 128-byte block.
1. We split `foo`'s memory in half to get two 512-byte blocks,
2. and then split one 512-byte block into two 256-byte blocks,
3. and then split one 256-byte block into two 128-byte blocks,
4. and then use one of these for `bar`.
Thus a small part (1/16) of the memory allocated for `foo` gets reused.
5. (Advanced) A very common programming error is to write something equivalent to:
```int *cat = (int *) malloc(sizeof(int));
int *dog = (int *) malloc(sizeof(int));
cat[3]=0;
free(dog); // segmentation fault: core dumped
```
Assuming that ints are 8 bytes, why might this cause a segmentation fault when calling `free(dog)`?
Answer: Depending upon how malloc is implemented, memory can look like this:
```
<cat descriptor>                <dog descriptor>
+-------+-------+-------+-------+-------+-------+-------+-------+
| next  | size  | cat[0]| cat[1]| next  | size  | dog[0]| dog[1]|
+-------+-------+-------+-------+-------+-------+-------+-------+
```
Thus:
1. `cat[3]=0` writes over the `next` or `size` field of the descriptor for `dog` (depending upon implementation), which is unused while the memory is in use. This does nothing.
2. `cat[3]=0` causes a segmentation fault when we try to free `dog`, because it writes garbage into the `next` or `size` field and misdirects the block to the wrong linked list or an invalid location (NULL) for the list element. But since we are concerned with speed, `free` does not check whether the size field is sane!

In other words, "real programmers don't write out of bounds" and those unreal programmers that do are in for a lot of pain.

• (Advanced) Malloc doesn't use the buddy system for things larger than a page (8192 bytes = 213). So why do we allocate 8 bytes to store a number between 5 and 13? It would seem that this number would take a total of 4 bits = 1/2 of a byte.
Answer: Remember that in an IA64 architecture, the alignment requirements for malloc are at 16 byte boundaries. Thus, if we used only 9 bytes for the descriptor, the resulting address of the allocated memory would be misaligned!