Project 01: Files, Directories, Processes

The goal of this project is to allow you to practice utilizing system calls dealing with files, directories, and processes in C by creating a partial re-implementation of find called search, which recursively searches a directory and prints items it finds based on the specified options:

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

Options:
    -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

Expressions:

    -print          Display file path (default)
    -exec cmd {} ;  Execute command on path

For this project, you are to work in groups of 2 or 3 and record your source code and any responses to a new project01 GitLab repository. You should push your work to your GitLab repository by 11:59 PM Friday, April 21, 2017.

GitLab Repository

Because you will be working in groups, you will need to fork and clone a new project01 repository:

https://gitlab.com/nd-cse-20289-sp17/cse-20289-sp17-project01

To do this, you should follow the same instructions from Reading 00 (except adjust for the different repository location). Besure to do the following:

  1. Make your project01 repository is private.

  2. Give the teaching staff and your group members developer access to your project01 repository.

  3. Record your group members in the Project Description and in the README.md.

Note: You should only have one repository per group.

Once forked, you should clone your repository to a local machine. Inside the project01 folder, you should see the following files:

project01
    \_ Makefile       # This is the Makefile for building all the project artifacts
    \_ README.md      # This is the README file for recording your responses
    \_ execute.c      # This is the C99 implementation file for the execute function
    \_ filter.c       # This is the C99 implementation file for the filter function
    \_ main.c         # This is the C99 implementation file for the main function
    \_ search.c       # This is the C99 implementation file for the search function
    \_ search.h       # This is the C99 header file for the project
    \_ test_search.sh # This is the shell script for testing the search tool
    \_ utilities.c    # This is the C99 implementation file for a few utility functions

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

Task 0: search.h

The search.h file is the header file for whole project. In addition to the function prototypes, this header defines the following struct:

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 */

    bool    print;      /* Print (-print) */

    int     exec_argc;  /* Number of arguments for (-exec) */
    char  **exec_argv;  /* Arguments for (-exec) */
} Settings;

This Settings struct is used to hold the configuration for the application; each field corresponds to one of command line options for the search program.

For instance, if the user specifies -executable, the access field can be set to X_OK. This information can be used by filter to check if a file is executable by using the access field and the access function:

/* Check -executable, -readable, -writable */
if (settings->access && access(path, settings->access) != 0) {
    return true;
}

Additionally, this header file also defines two macros:

#define     streq(s0, s1)   (strcmp((s0), (s1)) == 0)
#define     debug(M, ...) \
    fprintf(stderr, "DEBUG %s:%d:%s: " M "\n", __FILE__, __LINE__, __func__, ##__VA_ARGS__)

The streq macro can be used to check if two strings are equal, while the debug macro can be used to insert debugging statements.

For this task, you do not need to modify this header file. Instead, you should review them and ensure you understand the provided code.

Task 1: Makefile

Once again, the Makefile contains all the rules or recipes for building the project artifacts (e.g. 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, LDFLAGS, AR, and ARFLAGS variables when appropriate in your rules.

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

# Build search
$ make
Compiling main.o...
Compiling execute.o...
Compiling filter.o...
Compiling search.o...
Compiling utilities.o...
Linking search...

# Run test
$ make test
...
Search test had 18 failures!
make: *** [Makefile:21: test] Error 18

# Simulate build with tracing output
$ make -n
echo Compiling main.o...
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o main.o main.c
echo Compiling execute.o...
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o execute.o execute.c
echo Compiling filter.o...
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o filter.o filter.c
echo Compiling search.o...
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o search.o search.c
echo Compiling utilities.o...
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o utilities.o utilities.c
echo Linking search...
gcc -L. -o search main.o execute.o filter.o search.o utilities.o

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

Task 2: utilities.c

The utilities.c file contains the C99 implementation for two utility functions:

  1. bool is_directory_empty(const char *path)

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

    Hint: You can use opendir and readdir.

  2. time_t get_mtime(const char *path)

    This function returns the modification time of the file specified by path.

    Hint: You can use lstat.

Error Checking

As discussed in class, system calls can fail and you must check and handle these failures in your code. For instance if opendir fails, you should present an error message and depending on the context return an appropriate status code.

Task 3: search.c

The search.c file contains the C99 implementation for the search function:

int search(const char *root, const Settings *settings);

This function recursively searches the provided root directory by filtering out any files or directories that don't match the given settings and then executing the appropriate expression on the paths that do pass the filters.

Hints:

Task 4: filter.c

The filter.c file contains the C99 implementation for the filter function:

bool filter(const char *path, const Settings *settings);

This function tests the file or directory specified by path against all the filters specified in the settings structure. If the file passes all the tests, then the function returns false to indicate that it should not be excluded. Otherwise, it returns true to indicate that the file should be excluded.

Hints:

Task 5: execute.c

The execute.c file contains the C99 implementation for the execute function:

int execute(const char *path, const Settings *settings);

This function executes the specified expression on the given path:

If expression is specified, then -print is assumed. It is possible that both expressions are specified and thus both should be executed.

Hints:

Task 6: main.c

The main.c file contains the C99 implementation for the main function. The purpose of this function is to parse the command line options in order to construct the Settings structure and then call the search function with these settings.

For instance, to handle the -executable flag, you can do something like this:

if (streq(arg, "-executable")) {
    settings.access |= X_OK;
}

This checks if the current argument is equal to -executable and then sets the settings.access field to X_OK. This will then be used in the filter function as demonstrated above.

Of course, this assumes that the Settings structure was properly initialized. It is recommended, that you declare it in this manner:

Settings settings = {
    .access = 0,
    .uid    = -1,
    .gid    = -1,
};

This will set all the fields except the ones specified above to 0.

Task 7: test_search.sh

To aid you in testing the search, we provided you with test_search.sh, which you can use as follows:

$ make test
Compiling main.o...
Compiling execute.o...
Compiling filter.o...
Compiling search.o...
Compiling utilities.o...
Linking search...
Testing search...
Search test successful!

$ ./test_search.sh
Search test successful!

Memory Issues

Your program must also be free of memory issues such as invalid memory accesses and memory leaks. Use valgrind to verify the correctness of your program:

$ valgrind --leak-check=full ./search /etc

Be sure to check using different command line arguments as well to ensure you verify all code paths.

Iterative and incremental development

Do not try to implement everything at once. Instead, approach this program with the iterative and incremental development mindset and slowly build pieces of your application one feature at a time:

  1. Implement walking the directories and printing everything out.

  2. Implement parsing one command line option and then filtering that option (do this one by one).

  3. Implement executing commands.

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.

Focus on one thing at a time and feel free to write small test programs to try things out.

Task 8: README.md

In your README.md, describe how you implemented search. In particular, briefly discuss:

  1. How you handled parsing the command line options.

  2. How you walked the directory tree.

  3. How you determined whether or not to print a filesystem objects path.

Likewise, use strace to compare the number of system calls your search does compared to the traditional find command on /etc:

Finally, include a Contributions section in your README.md that enumerates the contributions of each group member.

Guru Point: Easter Egg (1 Point)

In the spirit of the holiday, you are to embed an easter egg into your search program. For instance, here is a famous easter egg found in Microsoft's Excel 95:

Here are some possible easter egg ideas:

Feel free to use our friends cowsay and cmatrix.

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

$ ~pbui/pub/bin/search for the droid

$ ~pbui/pub/bin/search for a cat

$ ~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 your project01 repository on GitLab. Your project01 folder should only contain at the following files: