Homework 08: System Calls (Files, Directories)

The goal of this homework assignment is to allow you to practice using system calls involving files and directories in C by implementing a partial clone of find:

search: This utility uses system calls dealing with files and directories to implement find, which recursively searches a directory and prints the items it finds based on the specified user options.

$ ./search -help
Usage: ./search PATH [OPTIONS]

Options:
    -help           Display this help message

    -executable     File is executable or directory is searchable to user
    -readable       File readable to user
    -writable       File is writable to user

    -type [f|d]     File is of type f for regular file or d for directory

    -empty          File or directory is empty

    -name  PATTERN  Base of file name matches shell PATTERN
    -path  PATTERN  Path of file matches shell PATTERN

    -perm  MODE     File's permission bits are exactly MODE (octal)
    -newer fILE     File was modified more recently than FILE

    -uid   N        File's numeric user ID is N
    -gid   N        File's numeric group ID is N

For this assignment, record your source code and any responses to the following activities in the homework08 folder of your assignments GitLab repository and push your work by noon Saturday, April 6.

Activity 0: Preparation

Before starting this homework assignment, you should first perform a git pull to retrieve any changes in your remote GitLab repository:

$ cd path/to/repository                   # Go to assignments repository

$ git checkout master                     # Make sure we are in master branch

$ git pull --rebase                       # Get any remote changes not present locally

Next, create a new branch for this assignment:

$ git checkout -b homework08              # Create homework08 branch and check it out

Starter Code

To help you get started, the instructor has provided you with some starter code.

# Download starter code tarball
$ curl -sLOk https://gitlab.com/nd-cse-20289-sp19/cse-20289-sp19-assignments/raw/master/homework08/homework08.tar.gz

# Extract starter code tarball
$ tar xzvf homework08.tar.gz

# Add and commit starter code
$ git add homework08
$ git commit -m "homework08: starter code"

Once downloaded and extracted, you should see the following files in your homework08 directory:

homework08
    \_ Makefile               # This is the Makefile for building all the project artifacts
    \_ README.md              # This is the README file for recording your responses
    \_ bin/test_filters.py    # This is the Python test script for the search filter functions
    \_ bin/test_search.sh     # This is the Shell test script for the search utility
    \_ include/search.h       # This is the C99 header file for the search utility
    \_ src/filter.c           # This is the C99 source file for the search filter functions
    \_ src/main.c             # This is the C99 source file for the search main function
    \_ src/options.c          # This is the C99 source file for the search options functions
    \_ src/utilities.c        # This is the C99 source file for the search utility functions
    \_ src/walk.c             # This is the C99 source file for the search walk function

File: `Makefile`

Before you implement the search utility, you should first complete the provided Makefile. Remeber, the Makefile contains all the rules or recipes for building the project artifacts (e.g. duplicate, search, etc.). Although the provided Makefile contains most of the variable definitions and test recipes, you must add the appropriate rules for search and any intermediate objects. The dependencies for these targets are shown in the DAG below:

Makefile Variables

You must use the CC, CFLAGS, LD, and LDFLAGS variables when appropriate in your rules.

Moreover, since there are a lot of object files, it is recommend that you use a pattern rule for compiling *.c files into *.o files (rather than explicitly specifying each object rule).

Once you have a working Makefile, you should be able to run the following commands:

$ make                    # Build all targets
Compiling src/main.o...
Compiling src/filter.o...
Compiling src/options.o...
Compiling src/utilities.o...
Compiling src/walk.o...
Linking bin/search...

$ make clean              # Clean targets and intermediate files
Cleaning...

$ make -n                 # Simulate build with tracing output
echo Compiling src/main.o...
gcc -g -Wall -Werror -std=gnu99 -Iinclude -o src/main.o -c src/main.c
echo Compiling src/filter.o...
gcc -g -Wall -Werror -std=gnu99 -Iinclude -o src/filter.o -c src/filter.c
echo Compiling src/options.o...
gcc -g -Wall -Werror -std=gnu99 -Iinclude -o src/options.o -c src/options.c
echo Compiling src/utilities.o...
gcc -g -Wall -Werror -std=gnu99 -Iinclude -o src/utilities.o -c src/utilities.c
echo Compiling src/walk.o...
gcc -g -Wall -Werror -std=gnu99 -Iinclude -o src/walk.o -c src/walk.c
echo Linking bin/search...
gcc -Llib -o bin/search src/main.o src/filter.o src/options.o src/utilities.o src/walk.o

$ make test               # Run all tests
...

Depending on your compiler, you may see some warnings with the initial starter code. Likewise, the test programs will all fail in some fashion.

Warnings

You must include the -Wall flag in your CFLAGS when you compile. This also means that your code must compile without any warnings, otherwise points will be deducted.

The details on what you need to implement are described in the following sections.

Activity 1: Search Utility

The utility you are to implement in this assignment is search, which is a partial re-implementation of the find command. Given an initial root directory, this program recursively walks the specified path and prints out the name of any files that match the specified criteria. For instance, only output files that are executable, the user can specify the -executable flag:

$ ./bin/search root -executable

For more details on what the various flags do, please consult the manual for find.

Iterative and Incremental Development

Once again, you should approach this program with the iterative and incremental development mindset and slowly build pieces of your application one feature at a time:

Implement parsing the root directory.
Implement walking the root directory.
Implement recursively walking the root directory.
Implement parsing one filter option.
Implement checking one filter option.
Repeat 4 and 5 until all options are implemented!

Remember that the goal at the end of each iteration is that you have a working program that successfully implements all of the features up to that point.

File: `include/search.h`

The include/search.h file is the header file for search utility. In addition to the function prototypes, this header defines the following types:

typedef struct {
    int     access;     /* Access modes (-executable, -readable, -writable) */
    int     type;       /* File type (-type); */
    bool    empty;      /* Empty files and directories (-empty) */
    char   *name;       /* Base of file name matches shell pattern (-name) */
    char   *path;       /* Path of file matches shell pattern (-path) */
    int     perm;       /* File's permission bits are exactly octal mode (-perm) */
    time_t  newer;      /* File was modified more recently than file (-newer) */
    int     uid;        /* File's numeric user ID is n */
    int     gid;        /* File's numeric group ID is n */
} Options;

The Options struct stores the results of parsing the command-line options and contains the following attributes:

access: This is an integer that contains a bitmask for the access function.

type: This is an integer that contains the file type (corresponding to the st_mode from in the stat structure).

empty: This is a boolean value that if set means only empty files and directories should be outputted.

name: This is a string that contains a shell pattern each item's name should match.

path: This is a string that contains a shell pattern each item's path should match.

perm: This is an integer that contains permissions each item should match.

newer: This is an integer that contains the timestamp each item should be newer (ie. greater) than.

uid: This is an integer that contains the uid each item should match.

gid: This is an integer that contains the gid each item should match.

Notes

Many of these attributes correspond to fields in the stat structure.
By default, these attributes should have values that mark the corresponding filters as disabled.

typedef bool (*FilterFunc)(const char *path, const struct stat *stat, const Options *options);

This FilterFunc type definition specifies a function that given a path to a file, its stat information, and the options to the utility, returns whether or not the specified file should be excluded from the output (if so return true, otherwise return false to indicate it should be included).

The include/search.h header file also defines the following macros:

#define     streq(s0, s1)     (strcmp((s0), (s1)) == 0)

The streq macro can be used to test if two strings are equal.

#define     debug(M, ...)     fprintf(stderr, "DEBUG %s:%d:%s: " M "\n", __FILE__, __LINE__, __func__, ##__VA_ARGS__)

The debug macro can be used to output debugging messages that contain the name of the file, the line number, and the function name.

File: `src/options.c`

The src/options.c file contains the C99 implementation for the following functions:

/**
 * Display usage message and exit.
 * @param   progname        Name of program.
 * @param   status          Exit status.
 */
void        usage(const char *progname, int status);

The provided usage function displays the usage message and exists with the provided status code.

/**
 * Parse command-line options.
 * @param   argc            Number of command-line arguments.
 * @param   argv            Array of command-line arguments.
 * @param   root            Pointer to root string.
 * @param   options         Pointer to Options structure.
 * @return  Whether or not parsing the command-line options was successful.
 */
bool        parse_options(int argc, char **argv, char **root, Options *options);

The parse_options function parses the command-line options and sets the appropriate fields in the Options structure.

Notes

The root comes first, followed by any filter options. If no root is specified, then it should default to the current directory.
You can use the streq macro to compare strings.
You can use strtol to parse a string into a long integer.

File: `src/walk.c`

The src/walk.c file contains the C99 implementation for the following functions:

/**
 * Recursively walk the root directory with specified options.
 * @param   root        Root directory path.
 * @param   options     User specified filter options.
 * @return  Whether or not walking this directory was successful.
 */
int         walk(const char *root, const Options *options);

This walk function recursively traverses the given root directory by checking if each item in the directory passes the specified Options filters; if so, it simply prints out the path of the item. If the item is a directory, the function will recurse on this item before processing the next entry in its own listing.

Notes

You should use opendir, readdir, and closedir. Alternatively, you can use scandir, but order isn't really important.
You can use snprintf to build the full path of each entry.
Be sure to skip the current directory and parent directory when iterating through the items in each directory.

File: `src/utilities.c`

The src/utilities.c file contains the C99 implementation for the following functions:

/**
 * Checks whether or not the directory is empty.
 * @param   path    Path to directory.
 * @return  Whether or not the path is an empty directory.
 */
bool        is_directory_empty(const char *path);

This is_directory_empty function returns whether or not the specified path is an empty directory.

Notes

Be sure to account for the fact that each directory has an entry for itself and its parent.
If the directory does not exist, then it is not empty.

/**
 * Retrieves modification time of file.
 * @param   path    Path to file.
 * @return  The modification time of the file.
 */
time_t      get_mtime(const char *path);

The get_mtime function returns the modification time of the file at the specified path.

Notes

You should use lstat rather than stat.

File: `src/filter.c`

The src/filter.c file contains the C99 implementation for the following items:

FilterFunc FILTER_FUNCTIONS[] = {   /* Array of function pointers. */
    filter_access,
    NULL,
};

The FILTER_FUNCTIONS is a NULL terminated array of function pointers, where each item is a FilterFunc.

Notes

For each attribute in the Options structure, you should have a corresponding filter_{attribute} function that checks and tests that option on a given file. For example, the provided filter_access function can be completed by doing the following:
```
bool        filter_access(const char *path, const struct stat *stat, const Options *options) {
    return options->access && access(path, options->access) != 0;
}
```
This checks if options->access is set and if so, it returns the result of the access function on those options.
For name and path, you should use the fnmatch function to test for shell patterns.
You are to implement a FilterFunc for each corresponding attribute in Options structure and add it to the FILTER_FUNCTIONS array.

/**
 * Filter path based on options.
 * @param   path        Path to file to filter.
 * @param   options     Pointer to Options structure.
 * @return  Whether or not the path should be filtered out (false means include
 * it in output, true means exclude it from output).
 */
bool        filter(const char *path, const Options *options);

The filter function checks if the file specified by path passes all filters specified in options. The function returns true if the file is to be excluded from output and false if it is to be included in the output.

Notes

The filter function should perform an lstat on the given path and then simply iterate through the FILTER_FUNCTIONS array. If any of the FilterFuncs return true, then the specified file should be excluded from the output.

This is an example of what the instructor calls the gauntlet pattern: perform a series of checks and if any fail, return immediately. If all the checks pass, then perform the final operation. This is somewhat related to what is known as the Guard Clause, which is a technique that can be used to refactor nested conditionals.

File: `bin/test_filters.py`

As you implement src/filter.c, you can test the individual filter_{attribute} functions by running the bin/test_filters.py script:

$ ./bin/test_filters.py -v
test_00_filter_access (__main__.FiltersTestCase) ... ok
test_01_filter_type (__main__.FiltersTestCase) ... ok
test_02_filter_empty (__main__.FiltersTestCase) ... ok
test_03_filter_name (__main__.FiltersTestCase) ... ok
test_04_filter_path (__main__.FiltersTestCase) ... ok
test_05_filter_perm (__main__.FiltersTestCase) ... ok
test_06_filter_newer (__main__.FiltersTestCase) ... ok
test_07_filter_uid (__main__.FiltersTestCase) ... ok
test_08_filter_gid (__main__.FiltersTestCase) ... ok
  Score 5.00

----------------------------------------------------------------------
Ran 9 tests in 0.062s

OK

As with Homework 06, this script uses Python to test your C code. For debugging purposes, you may wish to modify the script or write your own test programs.

Unit Tests

Unlike in the previous assignment, the starter code provided in this homework does not contain an extensive set of unit tests for every function. Instead it is up to you to write unit tests or small test programs to verify the correctness of your functions. While you are not required to do so, writing such small tests will help in debugging your code and exploring how to use the system calls.

File: `src/main.c`

The src/main.c file contains the C99 implementation for the main function of the search utility, which should accomplish the following:

Declare and initialize an Options struct with the appropriate default settings.
Parse the command-line options.
Check the root directory (ie. see if it passes the filters and output its path).
Recursively walk the root directory.

File: `bin/test_search.sh`

As you implement search, you can test it by running the test-search target:

$ make test-search
Testing search...
 usage                                                                    ... Success
 usage (valgrind)                                                         ... Success
 no arguments                                                             ... Success
 no arguments (valgrind)                                                  ... Success
 /etc                                                                     ... Success
 /etc (valgrind)                                                          ... Success
 /etc -executable                                                         ... Success
 /etc -executable (valgrind)                                              ... Success
 /etc -readable                                                           ... Success
 /etc -readable (valgrind)                                                ... Success
 /etc -writable                                                           ... Success
 /etc -writable (valgrind)                                                ... Success
 /etc -type f                                                             ... Success
 /etc -type f (valgrind)                                                  ... Success
 /etc -type d                                                             ... Success
 /etc -type d (valgrind)                                                  ... Success
 /etc -name '*.conf'                                                      ... Success
 /etc -name '*.conf' (valgrind)                                           ... Success
 /etc -path '*security/*.conf'                                            ... Success
 /etc -path '*security/*.conf' (valgrind)                                 ... Success
 /etc -perm 600                                                           ... Success
 /etc -perm 600 (valgrind)                                                ... Success
 /etc -newer /etc/hosts                                                   ... Success
 /etc -newer /etc/hosts (valgrind)                                        ... Success
 /etc -uid 0                                                              ... Success
 /etc -uid 0 (valgrind)                                                   ... Success
 /etc -gid 0                                                              ... Success
 /etc -gid 0 (valgrind)                                                   ... Success
 /etc -empty                                                              ... Success
 /etc -empty (valgrind)                                                   ... Success
 /etc -type f -executable                                                 ... Success
 /etc -type f -executable (valgrind)                                      ... Success
 /etc -type d -readable                                                   ... Success
 /etc -type d -readable (valgrind)                                        ... Success
 /etc -type d -name '*conf*'                                              ... Success
 /etc -type d -name '*conf*' (valgrind)                                   ... Success
 /etc -type f -executable -readable                                       ... Success
 /etc -type f -executable -readable (valgrind)                            ... Success
 /etc -perm 755 -uid 0                                                    ... Success
 /etc -perm 755 -uid 0 (valgrind)                                         ... Success
   Score 6.00

Note: You can always compare the behavior of your search utility directly with the actual find command.

Activity 2: Reflection

Once you have a working version of search, you are to use the strace command to compare the system calls used by your utility versus those utilized by find.

$ strace -c ./bin/search /etc > /dev/null
  % time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 51.24    0.002266           2       809           lstat
 23.27    0.001029           4       234           getdents64
  9.70    0.000429           3       136        18 openat
  8.41    0.000372           3       118           close
  6.22    0.000275           2       119           fstat
  0.66    0.000029           3         9           write
  0.50    0.000022           2         8           brk
  0.00    0.000000           0         1           read
  0.00    0.000000           0        15        14 stat
  0.00    0.000000           0         6           mmap
  0.00    0.000000           0         3           mprotect
  0.00    0.000000           0         1         1 ioctl
  0.00    0.000000           0         1         1 access
  0.00    0.000000           0         1           execve
  0.00    0.000000           0         1           arch_prctl
------ ----------- ----------- --------- --------- ----------------
100.00    0.004422                  1462        34 total

Questions

In your README.md, record the output of the strace information for search vs find, and then answer the following questions:

Describe the differences you see between the number and type of system calls used by your utility as compared to the standard Unix program.
Did you notice anything surprising about the trace of your utility or the trace of the standard Unix program? Which implementation is faster or more efficient? Explain.

Guru Point: Easter Egg (1 Point)

In the spirit of the Easter Season, you are to embed an easter egg into your search program. For instance, here is the first video game easter egg (as discussed in History of Computing):

Here are some possible easter egg ideas:

Display scrolling text of credits on the project or your favorite song lyrics.
Run a game (ie. rogue, nethack, or any of the BSD games).
Play sounds or a song.
Display some sort of animation.

For instance, the instructor's version of search on the student machines contains the following easter eggs:

$ ~pbui/pub/bin/search the matrix

To receive credit, simply demonstrate the easter egg to the instructor or a TA.

Submission

To submit your assignment, please commit your work to the homework08 folder of your homework08 branch in your assignments GitLab repository. Your homework08 folder should only contain the following files:

Makefile
README.md
bin/test_filters.py
bin/test_search.sh
include/search.h
src/filter.c
src/main.c
src/options.c
src/utilities.c
src/walk.c

Note: Don't include any object files or executables.

#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS IN ACTIVITY 0
#--------------------------------------------------

$ cd homework08                           # Go to Homework 07 directory
...
$ git add Makefile                        # Mark changes for commit
$ git commit -m "homework08: Makefile"    # Record changes
...
$ git add src/*.c                         # Mark changes for commit
$ git commit -m "homework08: search"      # Record changes
...
$ git add README.md                       # Mark changes for commit
$ git commit -m "homework08: README"      # Record changes
...
$ git push -u origin homework08           # Push branch to GitLab

Remember to create a merge request and assign the appropriate TA from the Reading 10 TA List.

Homework 08: System Calls (Files, Directories)

Activity 0: Preparation

Starter Code

File: Makefile

Makefile Variables

Warnings

Activity 1: Search Utility

Iterative and Incremental Development

File: include/search.h

Notes

File: src/options.c

Notes

File: src/walk.c

Notes

File: src/utilities.c

Notes

Notes

File: src/filter.c

Notes

Notes

File: bin/test_filters.py

Unit Tests

File: src/main.c

File: bin/test_search.sh

Activity 2: Reflection

Questions

Guru Point: Easter Egg (1 Point)

Submission

File: `Makefile`

File: `include/search.h`

File: `src/options.c`

File: `src/walk.c`

File: `src/utilities.c`

File: `src/filter.c`

File: `bin/test_filters.py`

File: `src/main.c`

File: `bin/test_search.sh`