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?

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

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

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.

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

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

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?

b) Explain the steps involved in splitting a free block into a used block and a new free 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.

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?

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.

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.