Project 01: Idlebin

Overview

The first project is to build your own implementation of Busybox, which according to its website is the following:

BusyBox combines tiny versions of many common UNIX utilities into a single small executable. It provides replacements for most of the utilities you usually find in GNU fileutils, shellutils, etc.

You may think of Busybox as a complete Unix userland in a single binary executable. Because of its compact size, it is found in many embedded devices such as printers, network routers, and even some phones. In fact, Alpine Linux, the official Linux distribution for Docker, uses Busybox as its default userland rather than the traditional GNU utilities found on most Linux machines. This means commands such as ls and cat are embedded inside of a single busybox executable rather than as separate programs.

Given the Busybox executable, busybox, you can invoke any of its internal commands (i.e. applets) by specifying the desired applet as the first argument to the program:

$ busybox ls -l     # Execute ls applet with the argument -l

Alteratively, you can symlink the busybox executable to the name of any applet and then execute the applet directly:

$ ln -s busybox ls  # Create symbolic link from ls to busybox

$ ./ls -l           # Execute ls applet with the argument -l

Working in groups of one, two, or three people, you are to utilize low-level system calls to create a your own version of Busybox called idlebin that supports multiple internal applets by midnight on Friday, September 7, 2018. Additionally, your group is to present its work to a teaching assistant by Friday, September 14, 2018.

More details about this project and your deliverables are described below.

Idlebin

For this project, you are to implement various Unix utilities as applets in a single binary executable called idlebin. Specifically, you must implement clones of ls and cp as a group, and then later implement one or two additional applets individually.

Group Applets

Working as a team, you are to utilize low-level-system calls to implement both ls and cp:

$ bin/idlebin ls --help       # Display ls applet's usage message
Usage: ls [-Ra] [PATHS]...
    -R    List subdirectories recursively
    -a    Do not ignore entries starting with .

$ bin/idlebin cp --help       # Display cp applet's usage message
Usage: cp [-Rv] SOURCE... TARGET
    -R    Copy directories recursively
    -v    Explain what is being done

As with Busybox, your idlebin applets only implement a subset of the functionality (i.e. command-line options) of their traditional GNU counterparts. For instance, your ls only needs to support the -R and -a flags, which allow it to list subdirectories recursively or to display all files, even those that begin with a ..

To implement these applets, you will need to review and then utilize some of the following system calls and low-level functions: stat, open, read, write, close, readlink, symlink, opendir, readdir, closedir, scandir, and mkdir.

The behavior (in terms of operation and output) of your ls and cp applets must match that of both the GNU version and the reference implementation provided below.

Notes

1. Each group applet is worth 6 Points each.

2. For ls, consider how you would sort the command line arguments and traverse an directory in sorted order.

3. For cp, think carefully about all the different use cases (ie. copy one file to a directory, copy multiple files to a directory, etc.) and how you would detect these situations.

4. When possible create small helper functions that perform one specific action.

5. Develop your applets incrementally by supporting one feature or use case at a time.

Individual Applets

Once your group has implemented both ls and cp and have passed all the provided unit tests, you are then to work individually on one or two more applets (use the same group repository, but each member must work on different applets). Here is a table of possible applets to implement individually:

Notes

1. Each individual member can earn up 6 Points (so either implement one applet worth 6 Points or two worth 3 Points).

2. Consult the appropriate manual pages and the GNU versions of the commands to determine the correct behavior and output your applet requires.

3. The work of each individual applet must go in a separate git branch that can be later merged into the master branch (ie. make a uname branch if you are implementing that applet; only merge into master once you are complete).

4. To verify the correctness of your individual applet, you will need to write a [unit test] script in Python that provides a reasonable amount of test coverage for the features you implemented.

Reference Implementation

You can find a reference implementation of idlebin in the following location on AFS:

/afs/nd.edu/user15/pbui/pub/bin/idlebin

This will be updated periodically as more applets are written and added to the reference implementation.

Deliverables

As noted above, you are to work in groups of one or two (three is permitted, but discouraged) to implement your idlebin. You must use (C99) (not C++) as the implementation language for idlebin itself, while the test scripts are to be written in Python.

Timeline

Here is a timeline of events related to this project:

Repository

To start this project, one group member must fork the Project 01 repository on GitLab:

https://gitlab.com/nd-cse-30341-fa18/cse-30341-fa18-project01

Once this repository has been forked, follow the instructions from Reading 00 to:

1. Make the repository private.

2. Configure access to the repository.

   Make sure you add all the members of the team in addition to the instructional staff.

Source Code

As you can see, the base Project 01 repository contains a README.md file and the following folder hierarchy:

project01
    \_  Makefile        # This is the project Makefile
    \_  bin             # This contains the executable and symlinks
    \_  include         # This contains the header files
    \_  src             # This contains the C99 source code for idlebin executable
        \_ applets      # This conatins the C99 source code for idlbein applets
    \_  tests           # This contains the Python unit tests

You must maintain this folder structure for your project and place files in their appropriate place.

Compiling

To help you get started, we have provided a Makefile that will build the idlebin application for you:

$ make                  # Build idlebin executable and create applet symlinks
Compiling src/applets/basename.o
Compiling src/applets/false.o
Compiling src/applets/pwd.o
Compiling src/applets/cat.o
Compiling src/applets/yes.o
Compiling src/applets/true.o
Linking bin/idlebin
Symlinking bin/basename
Symlinking bin/false
Symlinking bin/pwd
Symlinking bin/cat
Symlinking bin/yes
Symlinking bin/true

Running

Once you have the idlebin executable, you can invoke the various applets in the same way that you do with Busybox:

$ bin/idlebin           # List all applets
Usage: idlebin applet [ARGUMENTS]...
Applets:
    basename
    false
    pwd
    cat
    yes
    true

$ bin/idlebin pwd       # Execute pwd applet
/home/pbui/src/teaching/cse.30341.fa18/project01

$ bin/pwd               # Execute pwd applet
/home/pbui/src/teaching/cse.30341.fa18/project01

$ bin/pwd --help        # Display pwd applet usage
Usage: pwd

Extending

You can create additional applets to be embedded into idlebin by placing C99 source files in the src/applets folder and defining at least the following two items:

1. {APPLET}_USAGE: This must be a const char array that contains the usage message for the new APPLET you are creating; it may consist of multiple lines.

2. {APPLET}_applet: This is a function that receives the command-line arguments (int argc, char *argv[]), performs the desired operations, and then returns an int corresponding to the applet's exit status.

Here is a simple template to follow:

/* {APPLET}.c: {APPLET} applet */

#include "idlebin.h"

/* Usage */

const char {APPLET}_USAGE[] = "Usage: {APPLET}";

/* Applet */

int {APPLET}_applet(int argc, char *argv[]) {
    return EXIT_SUCCESS;
}

The provided Makefile will automatically detect any additional applets placed in the src/applets folder and will embed them into the idlebin executable for you.

Testing

To verify the correctness of the applets in idlebin, we have provided a series of unit tests implemented in Python. These are located in the tests directory and can be executed all at once with the following command:

$ make test                 # Run all test scripts
Testing basename...
test_00_help (test_basename.BasenameTestCase) ... ok
test_01_usage (test_basename.BasenameTestCase) ... ok
test_02_basename (test_basename.BasenameTestCase) ... ok
...
----------------------------------------------------------------------
Ran 81 tests in 17.488s

FAILED (failures=25, errors=10)
make: *** [Makefile:54: test] Error 1

Note, the first time you run make test you will have failures since the ls and cp applets have not been implemented yet.

You may execute all the unit tests of a specific command by running the test Python script directly:

$ ./tests/test_pwd.py -v    # Run pwd test script
Testing pwd...
test_00_help (__main__.PwdTestCase) ... ok
test_01_curdir (__main__.PwdTestCase) ... ok
test_01_curdir_valgrind (__main__.PwdTestCase) ... ok

----------------------------------------------------------------------
Ran 3 tests in 0.570s

OK

To add your own tests, simply create the corresponding test_{APPLET}.py Python Script in the tests folder. It is recommended that you model your unit tests after the existing ones, which means utilizing Python's unittest module for creating unit tests.

Demonstration

As part of your grade, you will need to present your idlebin to a teaching assistant where you will demonstrate the correctness of your implementation along with answering any questions the TA may have. This presentation should be no more than 15 minutes long and must be scheduled ahead of time (we will provide a signup form soon).

Presentation

As part of your demonstration, you must provide a Google Drive presentation (between 5 - 10 slides) with the following content:

1. Design: Describe the overall design and organization of each of the group applets (e.g. ls and cp); that is, explain what overall control flow and logic along with how the various functions you created interact.

2. Implementation: Describe how a particular system call is used to implement a specific function in one of the group applets; explain exactly what happens in the user application and the operating system kernel for that corresponding code.

3. Testing: Identify a few tricky edge cases that you had to handle to correctly implement the group applets and explain how you addressed those challenges.

4. Summary: Described what you learned about operating systems and software development, and what you hope to improve upon in the future.

Note, you must incorporate images, graphs, diagrams and other visual elements as part of your presentation where reasonable.

Be prepared to be asked about different aspects of your project, as the TA may ask you questions to probe your understanding of the material and your work.

To arrange your demonstration time, please complete the form below:

Documentation

As noted above, the Project 01 repository includes a README.md file with the following sections:

1. Members: This should be a list of the project members (names and email).

2. Demonstration: This is where you should provide a Google Drive link to your demonstration slides.

3. Applets: This contains the list of applets you are to implement. You should check off any you completed (ie. [x]) and include any notes such as who implemented which applet and if there are any known issues or bugs.

You must complete this document report as part of your project.

Extra Credit

Once you have completed your project, you may do any of the following for individual extra credit:

1. You may implement up to two additional applets (or any of the commands found in Busybox's list of commands. You must pick a reasonable set of command-line arguments to support for each utility you implement. Each additional applet is worth 1 Point of extra credit and should be implemented in separate git branches.

2. You may borrow a [Raspberry Pi] from the instructor (or use your own), install a Linux distribution, and then compile, install, and run your idlebin on the [Raspberry Pi]. Accomplishing all of this would be worth 2 Points of extra credit.

To receive credit for either of these options, you must demonstrate your individual work after the group demonstrations.

Rubric

Your project will be scored on the following metrics: