xv6 Fork Bomb

In this lab, you will create a fork bomb in xv6. Recall that a shell (like bash on Linux) is a user program that reads commands entered by you (e.g., ls -l), parses that command text, and use system calls (fork, exec, wait) to execute the commands.

  • Foreground (e.g., sleep 10): The shell runs the command and waits for the command to finish. It calls wait() and blocks until sleep finishes before it gives you a new $ prompt.
  • Background (e.g., sleep 10 &): The & tells the shell: “Run this command, but do not wait for it. Give me a new $ prompt immediately.”

The current xv6 shell user/sh.c partially supports background job. It will run the command and give you a new prompt. But it reaps the background job. When the job finishes, it becomes a “zombie”. We can’t just “fix” this by having the shell call wait(). The normal wait() system call is blocking. If the shell called wait(), it would freeze until the background job finished. Let’s add a new system call to fix this behavior.

Overview

Step 1: Add Non-blocking Wait

We need a system call that lets the shell ask the kernel, “Hey, do I have any finished (zombie) children right now?” without being forced to wait. You will implement wait_noblock(). This new system call will check for zombie children:

  • If it finds one, it reaps it and returns its PID.
  • If it finds none, it returns 0 immediately instead of blocking.

Step 2: Support Background Execution

Now that we have wait_noblock(), let’s implement our background job processing as follows.

  1. Only fork once: The original xv6 shell fork()s twice to execute a command. You will modify this behavior to fork only once.
  2. Track jobs: When a background job starts, the shell will print its [pid].
  3. Reap zombies: Before the shell prints a new $ prompt, it will call your new wait_noblock() to reap background jobs that have finished.

Step 3: Add jobs Command

This lets the user ask the shell, “What background processes are you currently managing?” You will implement jobs as a “built-in” command (part of the shell itself, like cd).

  • When a background job is started, you add its PID to the array.
  • When a job is reaped by wait_noblock(), you remove its PID from the array.
  • When the user types jobs, you just print the contents of that array.

Step 4: Shell Script Execution

xv6’s shell lacks the ability to run shell script. Modify user/sh.c so that: If the shell is run with no arguments ($ sh), it reads commands from the keyboard (interactive mode). If it’s run with an argument ($ sh script.sh), it will open that file and read/execute commands from it.

Step 5: Fork Bomb Script

You will create a script that calls itself in the background, over and over, recursively. This will create new processes exponentially until the kernel has no more process slots and panics.

Implementation

Please fork or clone the starter code from Github:

open in GitHub.

Please DO NOT continue developing on the previous project, xv6-lab-syscall-tracing. You must clone or fork the new repository “xv6-lab-forkbomb” specifically for this lab, otherwise you will be missing the necessary grading programs and script files.

Build and run xv6
prompt> make qemu
How to quit qemu

Type C-a x (that is, hold down control and while doing so, press a, then let go of control, then press x). When you see (qemu), type quit to quit qemu.

Step 1: Add Non-blocking Wait (Warm-up)

Before your shell can monitor background job termination, you need a new system call to check for exited child processes without blocking.

Requirements

Add a new system call uint64 sys_wait_noblock(void):

  • If no zombie child is available, Returns 0
  • If a zombie child is reaped, Returns zombie child’s PID
  • If a zombie child is reaped, fills *exit_status with exit status of zombie child

How

  • First, modify kernel/proc.c and kernel/sysproc.c:

    proc.c

    In kernel/proc.c, here’s an example implementation of non-blocking wait. You can directly copy and paste this entire code block into a suitable location:

    int wait_noblock(uint64 exit_status) {
  // the current process, which is the shell
  struct proc *p = myproc();
  // loop through all processes
  for(struct proc *pp = proc; pp < &proc[NPROC]; pp++){
    if(pp->parent == p && pp->state == ZOMBIE){
      int pid = pp->pid;
      // Get the child's xstate (exit code) to user space:
      if(copyout(p->pagetable, exit_status, (char *)&pp->xstate, sizeof(int)) < 0)
        return -1;
      // Free the process entry from the proc table
      freeproc(pp);
      return pid;
    }
  }
  return 0; // no zombie child
}

    In the above code, we loop through all processes and check if they have entered zombie state (the child has ended but the parent doesn’t call wait() to get its exit status).

    sysproc.c

    In kernel/sysproc.c, here’s an example implementation of system call for non-blocking wait. You can directly copy and paste this entire code block into a suitable location:

    uint64
sys_wait_noblock(void)
{
  uint64 exit_status;
  argaddr(0, &exit_status);
  return wait_noblock(exit_status);
}

  • Then, register the syscall in kernel/syscall.h, kernel/syscall.c, kernel/defs.h, user/usys.pl and user/user.h. (Try it yourself)

Think About It:

Can you trace and explain the complete life cycle (or ‘journey’) of a system call, starting from the moment it’s triggered in a user program, to the moment the user process gets the return value?

Step 2: Support Background Execution

xv6 already parses commands ending with & and runs them in the background (see BACK command type in user/sh.c). However, it does not print the child PID, does not track or clean up exited background jobs.

Requirements

  • When a background job is run, print [pid] of the child in a new line and print a new command prompt $.

  • BEFORE printing a new command prompt $ and AFTER inputting a command, poll wait_noblock() to check if there is any exited background job. If there is, print it:

    [bg pid] exited with status X

  • Clarification for “AFTER inputting a command”: immediately after getcmd() returns

  • Clarification for “BEFORE printing a new command prompt $”: immediately before printing a new command prompt $

  • Example Implementation for polling wait_noblock():

    int status;
int pid;
while ((pid = wait_noblock(&status)) > 0)
  printf("[bg %d] exited with status %d\n", pid, status);

Create a user program sleep

  • Create a file user/sleep.c:

    #include "kernel/types.h"
#include "user/user.h"

int
main(int argc, char* argv[])
{
    if(argc != 2)
    {
        printf("no argument or too many arguments.\n");
        exit(1);
    }
    sleep(atoi(argv[1]));
    exit(0);
}

  • Add new path $U/_sleep\ to UPROGS in Makefile.

  • Make sure you can $ sleep 20 without running into error messages exec sleep failed in xv6.

  • You’ll notice that in xv6, $ sleep 50 doesn’t actually sleep for 50 seconds, but approximately 5 seconds. This isn’t an anomaly. you can investigate the specific reason and mechanism for this behavior.

Expected Behavior

The followings are examples about how your xv6 should behave and how your xv6 should not behave.

✔️ CASE 1: Run three background job sleep, pid increases by one:

$ sleep 1000 &
[3]
$ sleep 1000 &
[4]
$ sleep 1000 &
[5]
$

✔️ Run three background job sleep, pid increases by two:

$ sleep 1000 &
[4]
$ sleep 1000 &
[6]
$ sleep 1000 &
[8]
$ 

This undesired output is caused by xv6’s original user/sh.c implementation, which fork()s twice for a single command.

  1. The shell forks() once to create a child process.
  2. This child process then forks() again to create a grandchild process that actually exec()s the sleep command.

Even though you only want one background process, this default behavior creates two new processes. Since xv6’s allocpid function increments the PID for each new process (nextpid = nextpid + 1) and does not reuse PIDs, each background command consumes two PIDs. This is why you see the job IDs jumping by two (e.g., [4], [6], [8]).

Please change user/sh.c so that starting a background job creates only one process, not two.

✔️ CASE 2: After the user has entered a second command, the shell calls wait_noblock() and finds that pid=3 is finished. It printed [bg 3] exited with status 0 before executing the second command.

$ sleep 10 &
[3]
$ sleep 10 &
[bg 3] exited with status 0
[4]
$ sleep 10 &
[bg 4] exited with status 0
[5]
$

✔️ CASE 3: After the user has entered the fourth command, the shell calls wait_noblock() and finds that all three previous jobs have finished. It printed [bg 3] exited with status 0, [bg 4] exited with status 0, [bg 5] exited with status 0 before executing the fourth command.

$ sleep 50 &
[3]
$ sleep 50 &
[4]
$ sleep 50 &
[5]
$ sleep 10
[bg 3] exited with status 0
[bg 4] exited with status 0
[bg 5] exited with status 0
$

✔️ CASE 4: The user execute two commands connected with a pipe as background process. Print the pid of the first command in the pipeline.

$ ls README | cat &
[3]
README         2 2 2292
[bg 3] exited with status 0
$

❌ Print a new command prompt $ more than once instead of EXACTLY ONCE:

$ sleep 10 | sleep 10 &
[3]
$ $ $

  • This is likely due to incorrect control flow within main(). You can debug this by finding out when and where the $ prompt is being printed.

  • We use this command to test if you print the $ prompt only once. If this command looks strange to you, just imagine it is running two long-running programs in background.

Think about it: Printing only one [pid] for this command is the correct behavior. But why is only one [pid] printed? Does this [pid] represent either one of the sleep processes in the pipe?”

✔️ CASE 5: You execute an non-existing binary (e.g., “asdfgh”) as background job, please still print its PID and exit status.

(For the sake of simplicity, it’s ok in this lab that you don’t return exit status 127 as command not found)

$ asdfgh &
[3]
exec asdfgh failed
[bg 3] exited with status 0
$

❌ “asdfgh” does not exist but you execute it, but you don’t find it as a exited background job and you don’t print it:

$ asdfgh &
[3]
$ exec asdfgh failed

$

❌ Even though [bg 3] exited with status 0 printed successfully, the exec asdfgh failed message appeared after the $ prompt, and you still have to press ENTER again just to get a new $ prompt.

$ asdfgh &
[3]
$ exec asdfgh failed

[bg 3] exited with status 0
$

This is the hardest test case in the entire lab. If you get stuck on it for too long, we recommend you finish implementing the other features first and then come back to this one later.

✔️ CASE 6: If you run a foreground process before background jobs exit, then after that foreground process finishes (and before the $ prompt is displayed), the exit status of the background jobs should be displayed.

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ sleep 50 &
[3]
$ sleep 50
[bg 3] exited with status 0
$

❌ We expect reaping background jobs with PID == 3 but instead we end up reaping foreground process PID == 4:

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ sleep 50 &
[3]
$ sleep 50
$ 
[bg 4] exited with status 0

❌ We don’t see any [bg 3] exited with status 0, but it should be there:

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ sleep 50 &
[3]
$ sleep 50
$ 
$

Sometimes, or in this case, you may find that you are not reaping background processes but instead the foreground process as a zombie. Why?

  • What happened to background processes?

  • WHEN and WHERE do background processes being reaped?

  • Can you modify user/sh.c to properly wait for the foreground process?

A hint for one of the possible solutions
  • jobs[NPROC] in Step 3 will provide you information about who is background process and who is NOT.

Hints

  • Make good use of debugger to carefully inspect and learn how sh works when you are executing foreground or background commands (for example, $ sleep 60 and $ sleep 60 &).

  • Be careful with the process you are currently in if you don’t get any result from polling wait_noblock().

  • If you still can’t figure out how to correctly polling wait_noblock(), observe that:

    • Which process becomes orphan in sh?

    • Can you tell about why orphaned processes may exist?

    • How can you modify sh.c to avoid orphaned processes?

Step 3: Add jobs Command

Now we will add a new command jobs to show all currently running background jobs!

$ sleep 50 &
[3]
$ sleep 50 &
[4]
$ jobs
3
4
$ sleep 50 &
[5]

In the example above, jobs command prints all currently running background jobs’ PID.

Prerequisites

Please add the following code to user/sh.c first:

#include "kernel/param.h"

Requirements

  • Add jobs command that show all currently running background jobs.

  • jobs command is not a system call nor a standalone user program. It’s a shell built-in command. You should implement all the functionality of jobs command ONLY within user/sh.c.

  • You should track background PIDs in a fixed-size array.

  • Remember to remove already exited background jobs from jobs[NPROC]. Do not print any background PID which was already reaped.

  • DO NOT print anything if no background job is running.

  • For the sake of simplicity, you don’t have to parse jobs & command in this lab. It’s ok to get exec jobs failed if you input jobs & command.

How

To support jobs command that prints all live (not-yet-reaped) background PIDs, you should modify sh.c:

  1. Parse the jobs command.

  2. Create a fixed-size array jobs[NPROC] as global variable. (NPROC has been defined in kernel/param.h so you don’t have to declare it yourself).

  3. Before executing background jobs, add the new child PID into jobs[NPROC].

  4. When jobs command is called, print all PID of background jobs currently running.

Hints

  • If you don’t know how to parse jobs command, observe how cd command was parsed in user/sh.c. BUT for jobs command, things are a little different. (Is there any additional char at the tail of jobs strings when you type jobs and press ENTER in shell?)

Step 4: Shell Script Execution

Here comes the most exciting part: We will add support to user/sh.c so it can run a simple shell script file😁

Demonstration

Let’s look at the example about how to run a shell script file in xv6:

We have a file user/script.sh:

echo hello
sleep 40 &
sleep 30 &
jobs
sleep 50
echo Im awake
sleep 60 &
jobs
echo done

In xv6, we $ sh script.sh to run shell script file script.sh, and we get the following result:

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ sh script.sh
hello
[5]
[6]
5
6
[bg 6] exited with status 0
[bg 5] exited with status 0
Im awake
[9]
9
done
$

In Bash or other shells, if you run the exact same shell script, you will not get the exact same result as above, so please don’t refer to or rely on the output of other shells too much in Step 4.

How

  1. First, copy and paste the following script into user/script.sh:

    echo hello
sleep 2 &
echo done
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ sh script.sh
hello
[5]
done
$

  1. In user/sh.c, modify

    int
main(void)
{
    // some code here...
}

    to

    int
main(int argc, char* argv[])
{
    // some code here...    
}

  2. Now, it’s your turn to implement remaining features of executing shell scripts. We will describe in detail what you need to do in Requirements section.

Requirements

  • In main() of user/sh.c, open argv[1] as input if argc > 1.

    • If you don’t know how to open a file, looking around and investigate how other user programs achieve that.

    • When opening a non-existent file (more precisely, if your program can’t open a file), please print sh: cannot open xxx.sh.

      Example Output

      $ sh asdfgh.sh
sh: cannot open asdfgh.sh
$

  • Read and parse each line as a shell command.

    • xv6 already contains a lot of useful user libraries. If you don’t know how to read and parse texts line by line, looking around and investigate how other user programs achieve that.

  • Execute them in the same logic as interactive input.

  • For the sake of simplicity, you don’t have to parse $ ./script.sh in this lab. It’s ok to get exec ./script.sh failed if you input $ ./script.sh only instead of $ sh script.sh.

You might run into this problem if you are developing on Windows. This is because Windows handles line endings (newlines) differently. Please change every .sh file from CRLF mode to LF mode. If you are using VSCode, you can switch the file from CRLF to LF in the bottom-right corner of the editor.

Step 5: Fork Bomb Script

Congratulations on completing all the features! With all the features you extend, we can finally do something crazy to xv6 now!

Prerequisites

  • In kernel/param.h, please change the value of NOFILE from 16 to 24:

    from

    #define NOFILE       16  // open files per process

    to

    #define NOFILE       24  // open files per process

  • Create a file user/dummy.c:

    #include "kernel/types.h"
#include "user/user.h"

int
main(int argc, char* argv[])
{
    while(1);
}

  • Copy and paste the following script into user/bomb.sh:

    ./dummy &
./dummy &
sh /bomb.sh

  • Don’t forget to add new paths $U/_dummy\ to UPROGS in Makefile.

💣 Let’s Go… 💣

Run $ sh bomb.sh in your xv6 and see what happen.

Think About It:

A fork bomb will drain all the CPU on an unprotected OS like xv6, but modern OS like Linux has protection to prevent bad program (like the fork bomb) from taking all the resources. What are the mechanisms in Linux that enforce this CPU resource management?

Run grade script

prompt> python3 grade-lab-forkbomb

Demo

  1. “Think About It” Questions: The “Think About It” sections are for your own learning. They are interesting, but they will not be asked during the demo.
  2. Prepare Answers in Advance: The demo questions for this lab are more complex than the last one. We strongly recommend preparing your answers before your demo time to save everyone’s time.
  3. Have Your Code Ready: Before the demo starts, please open all the source code that will help you answer the questions. Close any files that are not needed. This will help you quickly find and show us your work when we ask.

Questions 1 and 2

In the int wait_noblock() implementation we provided in Step 1, there is this line:

if(copyout(p->pagetable, exit_status, (char *)&pp->xstate, sizeof(int)) < 0)

The question is: Why must we use copyout? Why can’t we just use the = (equals) sign to assign the value of xstate to exit_status?

1. Please answer this question from the perspective of Virtual Memory.

2. Please answer this question from the perspective of Protection / Security.

Questions 3

In the first example under Step 2: More Examples, we asked you to change the original xv6 behavior where running a background job creates TWO processes, so that it only creates ONE process now.

3. Please briefly explain how you changed the control flow in user/sh.c to achieve this.

Questions 4

In Step 3, we gave this specific hint:

Is there any additional char at the tail of jobs strings when you type jobs and press ENTER in shell?

4. Please briefly explain why parsing the jobs command is slightly different from the cd command.

Back to top