CS326 Project 01 Practice Problems with Solutions

Heap Allocator in xv6-riscv

The following questions test your understanding of the heap allocator implementation for Project 01.

Question 1: Block Header Structure (Easy)

Consider the struct block_hdr used in the heap allocator:

struct block_hdr {
  struct list_elem elem;
  char name[8];
  uint used;
  uint size;
};

a) What is the purpose of each field in this structure?

Solution:

struct list_elem elem: Used to link the block into a doubly-linked list of all blocks in the heap. This allows traversal of the block list for operations like finding a free block or merging neighboring free blocks.
char name[8]: A name assigned to the block for debugging purposes. The name can be up to 7 characters plus a null terminator.
uint used: A flag indicating whether the block is used (1) or free (0).
uint size: Size of the usable data portion of the block (not including the header).

b) In the output of memtest, there is a value called bhsz. What does this represent and what is its value?

Solution:

bhsz stands for “block header size” which is the size of the struct block_hdr in bytes.
The value is 32 bytes (in the implementation provided).
This is the overhead for each block in the heap, which is why it’s tracked separately from the usable data size (dsz).

c) When a block is freed, explain how the name field is modified.

Solution:

When a block is freed, the name field is cleared by setting the first character to the null terminator: hp->name[0] = '\0'.
This happens in the free() function and indicates that the block is no longer associated with a named allocation.
In the malloc_print() function, blocks with empty names are displayed with “NONE” for readability.

Question 2: Free Block Management (Medium)

Consider the following sequence of operations:

memtest m 0 500 A0 m 1 500 A1 m 2 500 A2 f 0 f 2 p s

a) Draw the state of the heap after these operations, showing all blocks and their headers.

Solution: Initial allocation creates 3 blocks of 500 bytes each, plus a small free block at the end:

Initial State (after all allocations):
[USED](A0) 500 bytes | [USED](A1) 500 bytes | [USED](A2) 500 bytes | [FREE] remaining bytes

After freeing A0 and A2:

[FREE](NONE) 500 bytes | [USED](A1) 500 bytes | [FREE](NONE) 500 bytes | [FREE] remaining bytes

The free block at the end gets merged with the freed A2 block:

[FREE](NONE) 500 bytes | [USED](A1) 500 bytes | [FREE](NONE) 500+remaining bytes

Final state after merging:

[FREE](NONE) 500 bytes | [USED](A1) 500 bytes | [FREE](NONE) 3000 bytes

Each block includes its header (32 bytes), so the actual values would be:

[FREE] boff=0 bhsz=32 bsz=532 doff=32 dsz=500
[USED] boff=532 bhsz=32 bsz=532 doff=564 dsz=500
[FREE] boff=1064 bhsz=32 bsz=3032 doff=1096 dsz=3000

b) Explain the process of merging free blocks when a block is freed.

Solution: When a block is freed, the heap allocator follows these steps to merge neighboring free blocks:

Mark the block as free by setting its used field to 0 and clearing its name
Check if the next block in the list is also free and contiguous in memory
- If yes, merge them by increasing the size of the current block by the size of the next block plus its header size, and removing the next block from the list
Check if the previous block in the list is also free and contiguous in memory
- If yes, merge them by increasing the size of the previous block by the size of the current block plus its header size, and removing the current block from the list

This is implemented in the free() function which calls heap_merge() twice - once for the next block and once for the previous block.

c) What conditions must be met for two blocks to be merged?

Solution: Two blocks can be merged if all of these conditions are met:

Both blocks must be free (used == 0)
The blocks must be physically adjacent in memory (the end of the first block must be the start of the second block)
The blocks must be in the correct order in the linked list (one must be the immediate predecessor or successor of the other)

In the code, this is checked with:

if((b1->used == 0 && b2->used == 0) &&
   (((void *) b1) + sizeof(struct block_hdr) + b1->size) == (void *) b2)

Question 3: Block Splitting (Medium)

When a free block is found that can satisfy a malloc request, the allocator may split the block.

a) Under what condition does the heap allocator decide to split a free block?

Solution: The heap allocator decides to split a free block if the remaining space after allocation would be sufficient to create a new usable free block. Specifically, if:

(hp->size - nbytes) >= ((sizeof(struct block_hdr) + BLOCK_MIN_SIZE))

In other words, if the difference between the free block’s size and the requested size is greater than or equal to the size of a block header (32 bytes) plus the minimum block size (4 bytes), then the block can be split.

b) Explain the steps involved in splitting a free block into a used block and a new free block.

Solution: The steps involved in splitting a free block are:

Calculate the difference between the free block’s size and the requested size
Reduce the size of the current block to match the requested size
Create a new block header at the end of the newly sized block:
- Set the new block’s pointer to: original_block_pointer + sizeof(block_hdr) + requested_size
- Set the new block’s size to: difference - sizeof(block_hdr)
- Mark the new block as free (used = 0)
- Clear the new block’s name
Insert the new block into the linked list after the current block
Mark the current block as used and set its name
Return a pointer to the data area of the current block

c) If a free block of size 100 bytes is found for a malloc request of 60 bytes, calculate the sizes of the resulting blocks (including headers) after splitting.

Solution: Given:

Free block size = 100 bytes
Requested size = 60 bytes
Block header size = 32 bytes

Step 1: Calculate the difference difference = 100 - 60 = 40 bytes

Step 2: Check if the block can be split 40 >= (32 + 4)? Yes, 40 >= 36, so the block can be split.

Step 3: Create new blocks

Original block becomes a used block of size 60 bytes
- Total size including header = 60 + 32 = 92 bytes
New free block of size = 40 - 32 = 8 bytes
- Total size including header = 8 + 32 = 40 bytes

Therefore, after splitting:

Used block: 92 bytes total (60 bytes usable data + 32 bytes header)
Free block: 40 bytes total (8 bytes usable data + 32 bytes header)

Question 4: Memory Allocation and sbrk() (Hard)

The heap allocator uses sbrk() to request memory from the kernel when needed.

a) What is the minimum increment size used when calling sbrk()? Why is this value chosen?

Solution: The minimum increment size used when calling sbrk() is 4096 bytes (defined as BLOCK_MIN_INCR).

This value is chosen because:

It aligns with the page size of the RISC-V processor (and many other processors)
Memory is allocated by the kernel in pages, so requesting multiples of the page size is most efficient
It reduces the number of system calls needed by requesting larger chunks at once
It provides a good balance between wasting memory and making frequent kernel calls

b) Explain the process the allocator uses to determine how much memory to request from the kernel when a malloc request cannot be satisfied by existing free blocks.

Solution: The process for determining how much memory to request is:

Start with the required size = requested bytes + block header size
Check if the last block in the heap is free:
- If it is, subtract its size (including header) from the required size, as it can be merged with the new memory
Check if the required size is less than the minimum increment (4096 bytes):
- If it is, set the required size to 4096 bytes
Otherwise, round up the required size to the next multiple of 4096 bytes:
- Calculate remainder = required size % 4096
- Add (4096 - remainder) to the required size
Call sbrk() with the calculated required size
If the last block was free, merge it with the newly allocated block

This ensures the heap size is always a multiple of 4096 bytes, while minimizing waste.

c) Consider a situation where the last block in the heap is a free block of size 1000 bytes, and a malloc request comes in for 3500 bytes. How much memory would the allocator request from sbrk()? Show your calculations.

Solution: Given:

Last block is free, size = 1000 bytes
Requested malloc size = 3500 bytes
Block header size = 32 bytes

Step 1: Calculate the initial required size req_size = 3500 + 32 = 3532 bytes

Step 2: Subtract the size of the last free block (including its header) req_size = 3532 - (1000 + 32) = 3532 - 1032 = 2500 bytes

Step 3: Check if the required size is less than BLOCK_MIN_INCR (4096) 2500 < 4096? Yes, so set req_size = 4096

Step 4: Request memory from sbrk() sbrk(4096)

Therefore, the allocator would request 4096 bytes from sbrk().

Question 5: Trace the Allocator (Advanced)

Consider the following sequence of operations:

memtest m 0 2000 A0 m 1 1000 A1 m 2 800 A2 f 1 m 3 600 A3 f 0 f 2 m 4 1500 A4

For each step in this sequence:

a) Draw the state of the heap showing all blocks (used and free).

b) Indicate when sbrk() is called and how much memory is requested.

c) Explain when and how block splitting and merging occurs.

d) Calculate the total heap size at the end of all operations.

Solution:

Step 1: `m 0 2000 A0`

Initial state: Empty heap
Call sbrk(4096) to get initial heap space
Split into:
- Used block A0: 2000 bytes data + 32 bytes header = 2032 bytes
- Free block: 4096 - 2032 = 2064 bytes (2032 bytes data + 32 bytes header)

[USED](A0) 2032 bytes | [FREE] 2064 bytes

Step 2: `m 1 1000 A1`

Find the free block of 2064 bytes
Split into:
- Used block A1: 1000 bytes data + 32 bytes header = 1032 bytes
- Free block: 2064 - 1032 = 1032 bytes (1000 bytes data + 32 bytes header)

[USED](A0) 2032 bytes | [USED](A1) 1032 bytes | [FREE] 1032 bytes

Step 3: `m 2 800 A2`

Find the free block of 1032 bytes
Split into:
- Used block A2: 800 bytes data + 32 bytes header = 832 bytes
- Free block: 1032 - 832 = 200 bytes (168 bytes data + 32 bytes header)

[USED](A0) 2032 bytes | [USED](A1) 1032 bytes | [USED](A2) 832 bytes | [FREE] 200 bytes

Step 4: `f 1`

Free A1 block, mark as free, clear name
No merging occurs because both neighbors are used blocks

[USED](A0) 2032 bytes | [FREE] 1032 bytes | [USED](A2) 832 bytes | [FREE] 200 bytes

Step 5: `m 3 600 A3`

Find first free block (formerly A1) of 1032 bytes
Split into:
- Used block A3: 600 bytes data + 32 bytes header = 632 bytes
- Free block: 1032 - 632 = 400 bytes (368 bytes data + 32 bytes header)

[USED](A0) 2032 bytes | [USED](A3) 632 bytes | [FREE] 400 bytes | [USED](A2) 832 bytes | [FREE] 200 bytes

Step 6: `f 0`

Free A0 block, mark as free, clear name
No merging occurs because next block (A3) is used

[FREE] 2032 bytes | [USED](A3) 632 bytes | [FREE] 400 bytes | [USED](A2) 832 bytes | [FREE] 200 bytes

Step 7: `f 2`

Free A2 block, mark as free, clear name
Merge with the following free block:
- Size of merged block = 832 + 200 = 1032 bytes

[FREE] 2032 bytes | [USED](A3) 632 bytes | [FREE] 1432 bytes

Step 8: `m 4 1500 A4`

Find first free block of 2032 bytes
Split into:
- Used block A4: 1500 bytes data + 32 bytes header = 1532 bytes
- Free block: 2032 - 1532 = 500 bytes (468 bytes data + 32 bytes header)

[USED](A4) 1532 bytes | [FREE] 500 bytes | [USED](A3) 632 bytes | [FREE] 1432 bytes

b) sbrk() is called only once at the beginning, requesting 4096 bytes of memory.

c) Block splitting occurs:

When A0 is allocated, splitting the initial block
When A1 is allocated, splitting the remaining free block
When A2 is allocated, splitting the remaining free block
When A3 is allocated, splitting the freed A1 block
When A4 is allocated, splitting the freed A0 block

Block merging occurs:

When A2 is freed, it merges with the following free block

d) The total heap size at the end is 4096 bytes, which was the initial allocation from sbrk().

Final state:

Used blocks: A3 (632 bytes), A4 (1532 bytes) = 2164 bytes
Free blocks: 500 + 400 + 1032 = 1932 bytes
Total: 2164 + 1932 = 4096 bytes

CS326 Project 01 Practice Problems with Solutions

Heap Allocator in xv6-riscv

Question 1: Block Header Structure (Easy)

Question 2: Free Block Management (Medium)

Question 3: Block Splitting (Medium)

Question 4: Memory Allocation and sbrk() (Hard)

Question 5: Trace the Allocator (Advanced)

Step 1: m 0 2000 A0

Step 2: m 1 1000 A1

Step 3: m 2 800 A2

Step 4: f 1

Step 5: m 3 600 A3

Step 6: f 0

Step 7: f 2

Step 8: m 4 1500 A4

Step 1: `m 0 2000 A0`

Step 2: `m 1 1000 A1`

Step 3: `m 2 800 A2`

Step 4: `f 1`

Step 5: `m 3 600 A3`

Step 6: `f 0`

Step 7: `f 2`

Step 8: `m 4 1500 A4`