# GeekOS Project Guide

This document describes the GeekOS projects for CMSC412. Each project builds on previous work, progressively adding OS functionality.

**Prerequisites**:
- Review [geekos-architecture.md](geekos-architecture.md) for GeekOS internals
- Review [os-concepts.md](os-concepts.md) for background concepts and OSTEP readings

---

## Project Overview

| Project | Topic | Key Concepts |
|---------|-------|--------------|
| P1 | Fork and Pipe | Process creation, IPC |
| P2 | Signals | Asynchronous events, signal handlers |
| P3 | Semaphores and Scheduling | Synchronization, scheduling algorithms |
| P4 | Virtual Memory | Paging, demand paging |
| P5 | File System | Disk-based storage, directories |

### Enabling Projects

Projects are enabled via flags in `include/geekos/projects.h`:

```c
#define PROJECT_FORK true      // Enable for P1
#define PROJECT_PIPE true      // Enable for P1
#define PROJECT_SIGNALS true   // Enable for P2
// etc.
```

---

## Project 1: Fork and Pipe

### Learning Objectives

- Understand process creation and address space duplication
- Implement inter-process communication via pipes
- Work with file descriptors and the VFS layer

### OSTEP Reading

- [Process API](https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf) - fork, wait, and related calls

### Overview

Implement the `Fork` system call to create child processes and the `Pipe` system call for unidirectional byte-stream communication.

### System Calls to Implement

#### Sys_Fork

Creates a copy of the calling process.

**Behavior**:
- Allocate new `User_Context` with copy of parent's memory
- Create new `Kernel_Thread` for the child
- Copy file descriptor table (increment reference counts)
- Return child PID to parent, 0 to child

**Key Considerations**:
- The child's kernel stack must be set up to return to user mode
- Open files are shared between parent and child (same `File` structures)
- The child should have the same register state as the parent at the point of fork

#### Sys_Pipe

Creates a pipe for IPC.

**Parameters**:
- `state->ebx`: Address to store read-end file descriptor
- `state->ecx`: Address to store write-end file descriptor

**Behavior**:
- Create a pipe buffer (internal kernel structure)
- Create two `File` objects (read end, write end)
- Add both to the process's file descriptor table
- Return file descriptor indices to user space

### Key Files

| File | Purpose |
|------|---------|
| `src/geekos/syscall.c` | `Sys_Fork`, `Sys_Pipe` implementations |
| `src/geekos/pipe.c` | `Pipe_Create`, `Pipe_Read`, `Pipe_Write`, `Pipe_Close` |
| `src/geekos/userseg.c` | User context creation and management |
| `src/geekos/kthread.c` | Thread creation helpers |
| `include/geekos/user.h` | `User_Context` structure |

### Pipe Implementation Requirements

The pipe module must implement:

| Function | Description |
|----------|-------------|
| `Pipe_Create` | Allocate pipe buffer and file structures |
| `Pipe_Read` | Read bytes from pipe; block or return if empty |
| `Pipe_Write` | Write bytes to pipe; block or return if full |
| `Pipe_Close` | Handle close; free resources when both ends closed |

**Pipe Semantics**:
- Bounded buffer (typically 32KB)
- Read from empty pipe with writers: return `EWOULDBLOCK` or block
- Read from empty pipe without writers: return 0 (EOF)
- Write to pipe without readers: return `EPIPE` (and send `SIGPIPE` in P2)
- Both ends must be closed before freeing pipe resources

### Testing

Test programs in `src/user/`:
- `fork-p1.c` - Basic fork test
- `pipe-p1.c`, `pipe-p2.c` - Pipe read/write tests
- `forkpipe.c` - Combined fork and pipe test

---

## Project 2: Signals

### Learning Objectives

- Understand asynchronous event delivery
- Implement user-mode signal handlers
- Manage context switches for signal handling

### OSTEP Reading

- [Process API](https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf) - Signals section

### Overview

Implement signal delivery allowing processes to handle asynchronous events. Signals can be sent between processes or generated by the kernel.

### Signal Numbers

Defined in `include/geekos/signal.h`:

| Signal | Number | Default Action | Description |
|--------|--------|----------------|-------------|
| `SIGKILL` | 1 | Terminate | Cannot be caught or ignored |
| `SIGUSR1` | 2 | Terminate | User-defined |
| `SIGUSR2` | 3 | Terminate | User-defined |
| `SIGCHLD` | 4 | Ignore | Child terminated |
| `SIGALARM` | 5 | Ignore | Timer alarm |
| `SIGPIPE` | 6 | Terminate | Write to pipe with no readers |

### System Calls to Implement

#### Sys_Signal

Register a signal handler.

**Parameters**:
- `state->ebx`: Pointer to handler function
- `state->ecx`: Signal number (1-6)

**Returns**: 0 on success, `EINVALID` for invalid signal or attempt to handle `SIGKILL`

#### Sys_RegDeliver

Register the trampoline function (called by libc startup before main).

**Parameters**:
- `state->ebx`: Address of trampoline function

The trampoline is called after a signal handler returns to invoke `Sys_ReturnSignal`.

#### Sys_Kill

Send a signal to a process.

**Parameters**:
- `state->ebx`: Target process PID
- `state->ecx`: Signal number

**Returns**: 0 on success, `EINVALID` if process not found or invalid signal

#### Sys_ReturnSignal

Called by the trampoline after a signal handler completes.

**Behavior**: Restore the process state that was saved before the handler ran.

#### Sys_WaitNoPID

Reap any zombie child process.

**Parameters**:
- `state->ebx`: Address to store exit code

**Returns**: PID of reaped child, or `ENOZOMBIES` if none available

### Signal Handling Flow

1. **Signal Sent**: `Sys_Kill` sets pending flag in target's `User_Context`
2. **Check Pending**: Before returning to user mode, `Check_Pending_Signal` examines flags
3. **Setup Frame**: If signal pending, `Setup_Frame` saves state and redirects to handler
4. **Handler Runs**: User-mode handler runs with signal number as argument
5. **Trampoline**: After handler returns, trampoline calls `Sys_ReturnSignal`
6. **Complete Handler**: `Complete_Handler` restores original state

### Setup_Frame Details

When delivering a signal, the kernel must:

1. Save the current `User_Interrupt_State` to the user stack
2. Push the signal number onto the user stack
3. Push the trampoline address (as return address)
4. Update the kernel's copy of user ESP
5. Set EIP to point to the signal handler

When `Complete_Handler` runs, it must:

1. Pop the signal number from user stack
2. Restore `User_Interrupt_State` from user stack
3. Resume normal operation

### Additional Modifications

- **Sys_Fork**: Copy signal handlers and trampoline to child
- **Pipe_Write**: Set `SIGPIPE` pending when writing to pipe with no readers
- **Exit**: Set `SIGCHLD` pending in parent when child terminates

### Key Files

| File | Purpose |
|------|---------|
| `src/geekos/syscall.c` | System call implementations |
| `src/geekos/signal.c` | `Check_Pending_Signal`, `Setup_Frame`, `Complete_Handler` |
| `include/geekos/signal.h` | Signal definitions |
| `src/geekos/pipe.c` | SIGPIPE on write to closed pipe |
| `src/geekos/kthread.c` | SIGCHLD in Exit |

### Testing

- `sigpipe.c` - SIGPIPE handling test
- Signal handler registration and delivery tests

---

## Project 3: Semaphores and Scheduling

### Learning Objectives

- Implement counting semaphores
- Understand and implement scheduling algorithms
- Balance fairness and efficiency

### OSTEP Reading

- [Semaphores](https://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf)
- [CPU Scheduling](https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf)
- [Multi-level Feedback Queue](https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf)

### Part A: Semaphores

Implement counting semaphores as a synchronization primitive.

#### System Calls

| Call | Parameters | Description |
|------|------------|-------------|
| `Sys_CreateSemaphore` | name, initial count | Create named semaphore |
| `Sys_P` (Wait) | semaphore ID | Decrement; block if zero |
| `Sys_V` (Signal) | semaphore ID | Increment; wake one waiter |
| `Sys_DestroySemaphore` | semaphore ID | Destroy semaphore |

#### Semaphore Semantics

- **P (Wait)**: If count > 0, decrement and continue. If count = 0, block.
- **V (Signal)**: Increment count. If threads waiting, wake one.
- Named semaphores can be shared across processes

### Part B: Scheduling

Implement a custom scheduling algorithm, typically Multi-Level Feedback Queue (MLFQ).

#### MLFQ Basics

- Multiple priority queues (e.g., 4 levels)
- New processes start at highest priority
- Processes that use full quantum move to lower priority
- Processes that block before quantum move to higher priority
- Periodic boost: move all processes to highest priority

#### Key Files

| File | Purpose |
|------|---------|
| `src/geekos/syscall.c` | Semaphore system calls |
| `src/geekos/sched.c` | Scheduler implementation |
| `src/geekos/synch.c` | May add semaphore support here |

#### Scheduler Interface

The scheduler must implement:
- `Get_Next_Runnable`: Select next thread to run
- Handle thread priority changes
- Time quantum management

---

## Project 4: Virtual Memory

### Learning Objectives

- Implement page-based virtual memory
- Handle page faults
- Implement demand paging with a paging file

### OSTEP Reading

- [Introduction to Paging](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf)
- [Translation Lookaside Buffers](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-tlbs.pdf)
- [Swapping: Mechanisms](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-beyondphys.pdf)
- [Swapping: Policies](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-beyondphys-policy.pdf)

### Part A: Basic Paging

Replace segmentation-based memory with paging.

#### Requirements

- Create page directory and page tables for each process
- Map virtual addresses to physical frames
- Handle TLB management
- Support copy-on-write for fork (optional optimization)

#### Key Structures

- **Page Directory**: Top-level page table (1024 entries)
- **Page Table**: Second-level (1024 entries per table)
- **Page Table Entry**: Physical frame number + flags (present, writable, user)

### Part B: Demand Paging

Add support for paging to disk.

#### Requirements

- Handle page faults for pages not in memory
- Implement page replacement algorithm (e.g., FIFO, Clock, LRU approximation)
- Read/write pages to paging file
- Track page state (in memory, on disk, dirty)

#### Key Files

| File | Purpose |
|------|---------|
| `src/geekos/paging.c` | Page table management |
| `src/geekos/uservm.c` | User virtual memory (replaces userseg.c) |
| `src/geekos/trap.c` | Page fault handler |
| `include/geekos/paging.h` | Page table structures |

---

## Project 5: File System

### Learning Objectives

- Implement a disk-based file system
- Manage directories and files
- Handle file allocation and free space

### OSTEP Reading

- [Files and Directories](https://pages.cs.wisc.edu/~remzi/OSTEP/file-intro.pdf)
- [File System Implementation](https://pages.cs.wisc.edu/~remzi/OSTEP/file-implementation.pdf)
- [Fast File System](https://pages.cs.wisc.edu/~remzi/OSTEP/file-ffs.pdf)

### Overview

Implement GOSFS (GeekOS File System) on the secondary disk (`diskd.img`).

### Required Operations

| Operation | Description |
|-----------|-------------|
| Format | Initialize filesystem on disk |
| Mount | Make filesystem accessible |
| Create/Delete | Files and directories |
| Open/Close | File handles |
| Read/Write | File data |
| Seek | Position in file |
| Stat | File metadata |

### Filesystem Structure

Design decisions to make:
- **Block size**: How large are disk blocks?
- **Free space tracking**: Bitmap? Free list?
- **File allocation**: Contiguous? Linked? Indexed?
- **Directory structure**: Linear? Tree?
- **Metadata**: Inodes? Directory entries?

### Key Files

| File | Purpose |
|------|---------|
| `src/geekos/gosfs.c` | GOSFS implementation |
| `src/geekos/vfs.c` | VFS integration |
| `include/geekos/gosfs.h` | GOSFS structures |

---

## General Development Tips

### Building and Testing

```bash
cd build
make clean
make
make run
```

### Debugging with GDB

```bash
# Terminal 1: Start QEMU paused
make dbgrun

# Terminal 2: Connect GDB
make dbg
```

Useful GDB commands:
- `break function_name` - Set breakpoint
- `continue` - Resume
- `step` / `next` - Step through code
- `print variable` - Examine values
- `bt` - Backtrace

### Common Issues

1. **Triple fault / reboot loop**: Usually a stack overflow or bad pointer
2. **General Protection Fault**: Segment violation, often bad user pointer
3. **Page fault**: Invalid memory access (for P4+)
4. **Kernel panic (KASSERT)**: Assertion failed - check the condition

### Code Style

- Follow existing GeekOS conventions
- Use `KASSERT` for internal invariants
- Use `TODO_P(PROJECT_X, "message")` for unimplemented features
- Lock ordering: always acquire locks in consistent order to avoid deadlock

### Testing Strategy

1. Test incrementally - implement and test one feature at a time
2. Start with simple cases before complex ones
3. Test error handling paths
4. Test concurrent access where relevant
