XV6 Series: MIT Labs 2024

Write-ups for Lab: Lock

Memory allocator

There are two requirements of this problem:

• Each CPU should have its own freelist and lock.
• In case, the current freelist is empty, the allocator should be able to steal the freelist of another CPU.

For the first requirement, we need to modify the kmem structure to the array of kmems as follows: From

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

To

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

Then we need to modify the knit and kfree function to adapt to the new data structure.

void
kinit()
{
  char lock_name[10]; // Each CPU should have a lock name
  for (int i = 0; i < NCPU; i++) {
    snprintf(lock_name, 10, "kmem_CPU%d", i); // Format the lock name
    initlock(&(kmem[i].lock), lock_name);
  }
  freerange(end, (void*)PHYSTOP); // Allocate all the free space to the CPU that executes this line.
}

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);
  r = (struct run*)pa;
  push_off(); // Disable Interrupt
  int cpu = cpuid();
  pop_off(); // Enable Interrupt
  acquire(&(kmem[cpu].lock));
  r->next = kmem[cpu].freelist;
  kmem[cpu].freelist = r;
  release(&(kmem[cpu].lock));
}

Finally, we modify the kalloc function as follows:

void *
kalloc(void)
{
  struct run *r;
  push_off(); // Disable Interrupt
  int cpu = cpuid();
  pop_off(); // Enable Interrupt
  acquire(&kmem[cpu].lock);
  r = kmem[cpu].freelist;
  if(r)
    kmem[cpu].freelist = r->next;
  else {
    // In case the current freelist is empty, we check the other lists of other CPUs 
    // and take the free spaces if they exist.
    struct run *tmp;
    // Loop through the list of CPUs
    for (int i = 0; i < NCPU; i++) {
      if (i == cpu) continue; // Skip if the CPU is the current CPU
      acquire(&kmem[i].lock);
      tmp = kmem[i].freelist;
      if (tmp == 0) { // Skip if the freelist is empty
        release(&(kmem[i].lock));
      } else {
        // steal 10 pages
        for (int j = 0; j < 10; j++) {
          if (tmp->next)
            tmp = tmp->next;
          else break;
        }
        kmem[cpu].freelist = kmem[i].freelist;
        kmem[i].freelist = tmp->next;
        tmp->next = 0;
        release(&(kmem[i].lock));
        break;
      }
    }
    r = kmem[cpu].freelist;
    if (r)
      kmem[cpu].freelist = r->next;
  }

  release(&(kmem[cpu].lock));

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}