---
# System prepended metadata

title: Checkpoint 1

---



```c
/* kernel.h
 *  - Uses Region 0 for all kernel data (PCB, kernel heap, kernel stacks, frame table).
 *  - Each process has:
 *      * a full UserContext (uctxt) saved in PCB (pc, sp, regs, vector, code, addr)
 *      * a full KernelContext (kctx) saved in PCB (used by KernelContextSwitch)
 *      * region-1 page-table pointer (ptbr) and ptlr
 *  - KernelContextSwitch helper (from hardware.h) is used to perform kernel-mode context switches.
 */

#ifndef _KERNEL_H
#define _KERNEL_H

#include <ylib.h>
#include <yalnix.h>
#include <hardware.h> 
#include "ykernel.h"   

/* =============== Configuration Constants ================ */

#define MAX_PROCS        64        /* size of proc table/array */
#define IDLE_PID         0         /* pid reserved for the kernel idle process */
#define INVALID_PID      (-1)  /* Entries in the processes table that have this value mean that this pid is free to use */

#define KERNEL_STACK_PAGES   2     /* kernel stack size in pages */
#define KERNEL_STACK_SIZE    (KERNEL_STACK_PAGES * PAGESIZE)

/* Kernel return codes */
#define SUCCESS  (0)
#define ERROR    (-1)
#define KILL     (-2)

/* =============== Frames Bookeeping =============== */

/* Categorizes each frame as either free, used by kernel or used by user */
typedef enum {
    FRAME_FREE = 0,
    FRAME_KERNEL,
    FRAME_USER
} frame_usage_t;

/* Descriptors for each physical frame in memory */
typedef struct frame_desc {
    unsigned int pfn;        /* physical frame number */
    frame_usage_t usage;     /* usage type */
    int owner_pid;           /* owning pid if usage == FRAME_USER (or -1) */
    unsigned int last_used_tick; /* for eviction heuristics if needed */
} frame_desc_t;

extern frame_desc_t *frame_table;   /* allocated during InitMemory */
extern unsigned int nframes;        /* number of frames available */

/* Find free frame, modify frame_table; returns PFN or -1 on error */
int AllocFrame(void);
void FreeFrame(unsigned int pfn);    /* Free a frame by its pfn and return its descriptors if found and freed and Null otherwise */

/* ============= Process Control Block (PCB) ================ */

/* process state */
typedef enum {
    PROC_FREE = 0,
    PROC_IDLE,     /* the kernel's initial idle process */
    PROC_READY,
    PROC_RUNNING,
    PROC_BLOCKED,  /* waiting for I/O or wait() */
    PROC_ZOMBIE
} proc_state_t;

/* Process Control Block */
typedef struct pcb {
    int pid;                 /* process id (unique) */
    proc_state_t state;      /* current state */
    int ppid;                /* parent pid (-1 if none) */
    int exit_status;         /* status for Wait; valid if PROC_ZOMBIE */

    /* Region 1 page table
     * The MMU registers REG_PTBR1/REG_PTLR1 are set to these during context-switch. */
    pte_t *ptbr;             /* virtual address of page table for region 1 */
    unsigned int ptlr;       /* length (number of entries) */

    /* Full user CPU state snapshot.  The handout requires storing the full */
    UserContext uctxt;

    /* Kernel context & kernel stack */
    KernelContext kctx;

    /* Kernel stack bookkeeping in region 0*/
    void *kstack_base;       /* base virtual address of the kernel stack (Region 0) */
    unsigned int kstack_npages;

    /* User-region memory accounting */
    unsigned int user_heap_start_vaddr; /* page-aligned lowest heap address */
    unsigned int user_heap_end_vaddr;   /* current brk */
    unsigned int user_stack_base_vaddr; /* top of user stack (initial) */

    /* Scheduling queue pointers implemented as linked list*/
    struct pcb *next;

    /* bookkeeping flags */
    int waiting_for_child_pid;  /* if parent is blocked waiting for child */
    int last_run_tick;          /* last tick when this process ran for scheduler info */

} PCB;

/* Global process table and runqueues */
extern PCB *proc_table;       /* array of MAX_PROCS PCBs allocated at kernel startup */
extern unsigned int proc_table_len;

extern PCB *current_proc;     /* currently running process */

/* Idle PCB convenience */
extern PCB *idle_proc;

/* Allocate / free PCBs */
PCB *AllocPCB(void);   /* returns pointer to free PCB, or NULL if none */
void FreePCB(PCB *p);  /* free data structures; for exit/reap */

/* ================== Kernel Start ================== */

/* Primary kernel entry point called by hardware at boot:
 *   KernelStart(char **cmd_args, unsigned int pmem_size, UserContext *initial_uctxt)
 *
 * Expected boot sequence:
 *  1) Init memory subsystem: InitMemory(pmem_size) -> allocate frame_table, compute nframes.
 *  2) Build initial Region 0 page table, mark kernel text/data pages valid.
 *  3) Initialize kernel_brk to orig kernel brk page provided via build info.
 *  4) Create idle PCB (current kernel) from initial_uctxt and helper_new_pid().
 *  5) Create region1 mapping for idle (single page stack entry), and set REG_PTBR1/REG_PTLR1.
 *  6) Initialize scheduler (SchedulerInit) and ready queues.
 *  7) Create init user process (CreateInitProcess)
 *  8) Write REG_VECTOR_BASE to point to interrupt vector table and set vector entries to TrapHandlers.
 *  9) Enable VM.
 * 10) Enter scheduling loop.
 *
 */
extern void KernelStart(char **cmd_args, unsigned int pmem_size, UserContext *initial_uctxt);


/* Provided by framework (see ykernel.h in the project): */
extern int helper_new_pid(struct pte *ptbr1);
extern void helper_retire_pid(int pid);
extern void helper_abort(char *msg);
extern void helper_maybort(char *msg);
extern void helper_check_heap(char *msg);
extern void helper_force_free(int frame);


#endif /* _KERNEL_H */

```


## Major Functions
### `KernelStart`
```
function KernelStart(cmd_args, pmem_size, uctxt):
    TracePrintf(KERNEL_TRACE_LEVEL, "Entering KernelStart")

    InitializeKernelDataStructures()
    InitializeFreeFrameList(pmem_size)
    InitializeVM()   // Build region 0 & 1 page tables

    EnableVM()  // Turn on virtual memory via WriteRegister(REG_VM_ENABLE, 1)

    // Create the first process (init)
    init_pcb = CreateProcess(INIT_PID)
    CopyUserContext(uctxt, init_pcb)
    current = init_pcb
    Enqueue(ready_queue, init_pcb)

    // Create idle process (runs when no one else ready)
    idle_pcb = CreateIdleProcess()

    // Begin scheduling
    Scheduler()
```
### `InitializeVM`
```
function InitializeVM():
    TracePrintf(KERNEL_TRACE_LEVEL, "Building initial page tables")

    // Allocate and zero region 0 page table
    pt_region0 = AllocPhysicalPage()
    memset(pt_region0, 0, PAGESIZE)

    // Map kernel text, data, and stack into region 0
    for vaddr in [KERNEL_BASE .. KERNEL_STACK_LIMIT):
        pfn = vaddr >> PAGESHIFT
        pt_region0[vaddr >> PAGESHIFT].valid = 1
        pt_region0[vaddr >> PAGESHIFT].prot = PROT_READ | PROT_WRITE
        pt_region0[vaddr >> PAGESHIFT].pfn = pfn

    // Create a blank region 1 page table
    pt_region1 = AllocPhysicalPage()
    memset(pt_region1, 0, PAGESIZE)

    // Write base and limit registers for both regions
    WriteRegister(REG_PTBR0, (unsigned int) pt_region0)
    WriteRegister(REG_PTLR0, MAX_PT_LEN)
    WriteRegister(REG_PTBR1, (unsigned int) pt_region1)
    WriteRegister(REG_PTLR1, MAX_PT_LEN)

    TracePrintf(KERNEL_TRACE_LEVEL, "VM initialization complete")

```
### `EnableVM`
```
function EnableVM():
    WriteRegister(REG_PTBR0, address_of(region0_pt))
    WriteRegister(REG_PTLR0, num_entries(region0_pt))
    WriteRegister(REG_PTBR1, address_of(region1_pt))
    WriteRegister(REG_PTLR1, num_entries(region1_pt))
    WriteRegister(REG_VM_ENABLE, 1)

```
### `InitializeFreeFrameList()`
```
function InitializeFreeFrameList(pmem_size):
    TracePrintf(KERNEL_TRACE_LEVEL, "Initializing free frame list")

    num_frames = pmem_size / PAGESIZE

    for i in 0..num_frames-1:
        frame_table[i].pfn = i
        if i < KERNEL_RESERVED_FRAMES:
            frame_table[i].usage = FRAME_KERNEL
            frame_table[i].owner_pid = IDLE_PID
            frame_table[i].refcount = 1
        else:
            frame_table[i].usage = FRAME_FREE
            frame_table[i].owner_pid = -1
            frame_table[i].refcount = 0

    free_frame_count = num_frames - KERNEL_RESERVED_FRAMES
```
### `KCSwitch()` for switching between two processes
```
function KCSwitch(KernelContext *kc_in, void *curr_pcb_p, void *next_pcb_p):
    curr = (PCB *)curr_pcb_p
    next = (PCB *)next_pcb_p

    // Save kernel context of current process
    memcpy(&curr->kctx, kc_in, sizeof(KernelContext))

    // Switch page tables for region 1
    WriteRegister(REG_PTBR1, (unsigned int) next->ptbr1)
    WriteRegister(REG_PTLR1, MAX_PT_LEN)
    WriteRegister(REG_TLB_FLUSH, TLB_FLUSH_1)

    current = next
    return &(next->kctx)
```
### `KCCopy()` for cloning a new process
```
function KCCopy(KernelContext *kc_in, void *new_pcb_p, void *unused):
    newpcb = (PCB *) new_pcb_p

    // Copy kernel context
    memcpy(&newpcb->kctx, kc_in, sizeof(KernelContext))

    // Allocate kernel stack for new process
    CopyKernelStack(newpcb)

    // Return kc_in (so parent resumes after KernelContextSwitch)
    return kc_in
```
### `Scheduler()` 
```
function Scheduler():
    while true:
        next = Dequeue(ready_queue)
        if next == NULL:
            next = idle_pcb  // run idle if no ready processes

        rc = KernelContextSwitch(KCSwitch, current, next)

        if rc == -1:
            TracePrintf(0, "Context switch failed")
            Halt()

        // When we return here, current process has resumed
        HandlePendingTrapsOrSyscalls()
```
## Memory Management Helpers
### `AllocFrame(usage)`
```
function AllocFrame(usage):
    for f in frame_table:
        if f.usage == FREE:
            f.usage = usage
            f.refcount = 1
            return f.pfn
    Panic("Out of physical frames")
```
### `FreeFrame(pfn)`
```
function FreeFrame(pfn):
    frame_table[pfn].usage = FREE
    frame_table[pfn].refcount = 0
```