Undercroft — Sky Yoo

Nothing upstairs runs without the vaults and corridors kept below. An undercroft is the vaulted level beneath a house — where stores are kept and corridors run unseen, carrying orders between rooms that never see each other. Two small systems built on that same idea: a heap allocator that plays the vault, claiming space and returning it, coalescing what’s adjacent so nothing goes to waste — and a command shell that plays the corridor, parsing what’s asked and routing it to the right process, redirected wherever told.

The allocator tracks free blocks with an explicit list and boundary-tag coalescing, first-fit placement, benchmarked against real allocation traces for utilization and throughput. The shell parses and forks/execs each command, handling built-ins, output redirection, and batch scripts of its own. Small systems work — the ceiling was correctness against a fixed set of benchmarks.

The instrument

A free list that gives space back, not just takes it

Blocks live on an explicit free list with boundary-tag coalescing — freeing one merges it into an adjacent free neighbor immediately, so fragmentation doesn't creep in silently over a long run.

First-fit placement, benchmarked against real traces

Requests are satisfied by the first block that's big enough, then split if there's room to spare. Run against a battery of allocation traces, it holds heap utilization high and passes every correctness check.

One dispatcher, redirection and all

Every line is tokenized, checked for `>` and `>+` redirection, then forked and exec'd — built-ins like cd, pwd, and exit handled without spawning a process at all. A batch mode replays whole scripts the same way.

The movement

The engineering underneath

Two systems, same discipline underneath — hand back exactly what you borrowed, and don't block on anything you don't have to.

Coalescing happens on free, not on a sweep

There's no garbage-collection pass. The instant a block is freed, its header and footer are checked against both neighbors and merged right there, so the free list never accumulates fragments waiting to be cleaned up later.

mm.c

static void *coalesce(void *bp) {
  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  size_t no_prev = PREV_BLKP(bp) == bp;
  prev_alloc |= no_prev;
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));
  void* next_blkp = NEXT_BLKP(bp);
  void* prev_blkp = PREV_BLKP(bp);
  if (prev_alloc && next_alloc) {
    push(bp);
    return bp;
  }
  else if (prev_alloc && !next_alloc) {
    size += GET_SIZE(HDRP(next_blkp));
    pop(next_blkp);
    pack_alloc(bp, size ,0);
    push(bp);
    return bp;
  }
  else if (!prev_alloc && next_alloc) {
    size += GET_SIZE(HDRP(prev_blkp));
    bp = prev_blkp;
    pop(bp);
    pack_alloc(bp, size ,0);
    push(bp);
    return bp;
  }
  else {
    size += GET_SIZE(HDRP(prev_blkp)) +
      GET_SIZE(HDRP(next_blkp));
    pop(prev_blkp);
    pop(next_blkp);
    bp = prev_blkp;
    pack_alloc(bp, size ,0);
    push(bp);
    return bp;
  }
}

Redirection parses before the fork, not after

The `>` and `>+` (append) forms are stripped out of the command line before tokenizing, so `execvp` only ever sees the argument vector it needs — the child process doesn't carry any shell-specific logic with it.

myshell.c

int check_redirect(char* buff, char** argv, char** file_name)
{
  int len = strlen(buff);
  int i;
  int result = 0;
  for (i = 0; i < len; i ++) {
    if (buff[i] == '>' && buff[i+1] != '+') {
      result = 1;
      break;
    } else if (i < len - 1 && buff[i] == '>' && buff[i+1] == '+') {
      result = 2;
      break;
    }
  }
  int j;
  *argv = (char*)malloc(i * sizeof(char));
  for (j = 0; j < i; j ++) {
    (*argv)[j] = buff[j];
  }
  (*argv)[i] = 0;

  if (result) {
    int k;
    char name[len - i - result];
    int t = 0;
    for (k = i+result; k < len; k ++) {
      name[t++] = buff[k];
    }
    name[t] = 0;
    *file_name = strdup(name);
  } else {
    *file_name = NULL;
  }
  return result;
}

Specification

Language: C
Memory management: Explicit free list, boundary-tag coalescing, first-fit placement
Shell: Built-ins, I/O redirection, interactive and batch modes
Benchmarks: Heap utilization and throughput against synthetic allocation traces
Origin: University of Chicago · CMSC 15400 (Introduction to Computer Systems) · Winter 2018