We know that xv6 uses a simple freelist, keeping that in mind, let’s take a look at kalloc.c!

•   extern char end[];

  First memory address after kernel. Defined by kernel.ld

•   struct run {
      struct run *next;
    };

  This is the freelist.

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

  Protects the freelist with a lock.

•   void
    kinit()
    {
      initlock(&kmem.lock, "kmem");
      freerange(end, (void*)PHYSTOP);
    }

  Initialises the lock and frees the entire memory space above the kernel.

•   void
    freerange(void *pa_start, void *pa_end)
    {
      char *p;
      p = (char*)PGROUNDUP((uint64)pa_start);
      for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
        kfree(p);
    }

  We go from pa_start to pa_end and free each page!

The next two functions do require a closer look-

kfree

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;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

Let’s go line by line here.

1.    void
      kfree(void *pa)
      {
        struct run *r;
   
        ...
      }

   • We take in physical address (pa) as input, which is a pointer that points to the page we want to free.
   • We also create struct run to actually manipulate memory.

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

   Here, we define the conditions in which kfree is invalid to run and should panic-

   • (uint64)pa % PGSIZE != 0 -> The pointer pa is not page-aligned!

   • (char*)pa < end -> pa points to a kernel page!

   • (uint64)pa >= PHYSTOP -> pa points to a memory address larger than the physical memory!

3.    memset(pa, 1, PGSIZE);

   As is quite obvious here, we fill the entire page with junk value so a snooping program cannot see the residual data. It also helps in debugging and catching dangling refs.

4.    r = (struct run*)pa;
   
      acquire(&kmem.lock);
      r->next = kmem.freelist;
      kmem.freelist = r;
      release(&kmem.lock);

   Step-by-step execution of this block-

   • We assign the page to r.

   • We acquire the lock to memory.

   • We prepend this page to the start of the freelist.

   • We point the freelist pointer to r.

   • We release the lock on memory we are currently holding.

And that concludes the kfree function!

kalloc

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

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

Let’s again analyse each line (only unique ones)-

1.   struct run *r;
   
     acquire(&kmem.lock);
     r = kmem.freelist;

   We acquire the memory lock and point a variable r to it.

2.   if(r)
       kmem.freelist = r->next;
     release(&kmem.lock);

   If r exists, we move freelist pointer to the 2nd node and release the lock.

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

   Again, if r exists, we fill it with junk to foil any would be snooper’s plan!

And that concludes the kalloc.c file in xv6 kernel! You are finally ready to conquer your memory!!

Our final kalloc.c

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

struct run {
  struct run *next;
};

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

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
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;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

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