greptile

HW2: greptile 🦎

Submission

We will be using GitHub for distributing and collecting your assignments. At this point you should already have a repository created on your behalf in the cs4157-hw GitHub org. Follow the instructions on the class listserv to get access to that repository.

To obtain the skeleton files that we have provided for you, you need to clone your private repository. Your repository page should have a button titled “< > Code”. Click on it, and under the “Clone” section, select “SSH” and copy the link from there. For example:

$ git clone git@github.com:cs4157-hw/hw2-<id>-<your-team-name>.git

The TAs will use scripts to download, extract, build, and display your code. It is essential that you DO NOT change the names of the skeleton files provided to you. If you deviate from the requirements, the grading scripts will fail and you will not receive credit for your work.

You need to have at least 5 git commits total, but we encourage you to have many more. Your final submission should be pushed to the main branch.

As always, your submission should not contain any binary files.

At a minimum, README.txt should contain the following info:

• Name & UNI for all group members
• Homework assignment number
• Description for each part

The description should indicate whether your solution for the part is working or not. You may also want to include anything else you would like to communicate to the grader, such as extra functionality you implemented or how you tried to fix your non-working code.

Answers to written questions, if applicable, must be added to the skeleton file we have provided.

Overview

In this assignment, you will implement a multi-threaded grep-like utility called greptile. The utility will recursively search a directory for files that contain a given string. In Part 1, you will implement the core functionality of greptile in a single-threaded manner. In Part 2, you will parallelize the search using POSIX threads, creating a utility similar to ripgrep (a.k.a. rg).

Your program must compile with no warnings, and should not produce any memory leaks or errors when run under valgrind. This requirement applies to all parts of the assignment.

Part 1: Single-threaded greptile 🐍

Reading

• APUE 4.2: stat, fstat, fstatat, and lstat Functions
• APUE 4.17: Symbolic Links
• APUE 4.22: Reading Directories: opendir, readdir, and closedir

Requirements

• Implement the traverse_directory() and search_file() functions given in the skeleton code.
• greptile should terminate with exit code 0 if a match is found, 1 if no match was found, and 2 if an error occurred. This mimics the behavior of the grep utility.
• We only handle regular files and directories. You should not follow symbolic links.
  • Think about why following symbolic links might be dangerous.
  • Think about which function in the stat family you should use.
• If a file is a regular file, you should search it for the given string. You may find the strstr() and strsep() functions useful.
  • Assume that the file is a text file. You can leave the behavior on binary files undefined.
  • Recall, however, that these functions operate on null-terminated strings.
  • Unlike grep, greptile will not support regular expression search.
  • You should use malloc() to allocate a buffer to read the entire file into.
• If a file is a directory, you should recursively search through all files and directories within it. See APUE 4.22.
  • Be careful not to start searching the same directory (or its parent) again.
• If a file or subdirectory cannot be opened, print an error message to stderr and continue with the search.
• Your output should match that of the sample executable located in /opt/asp/bin exactly.
  • Note that we use ANSI escape sequences to colorize the output, given to you in the skeleton code as the COLOR_* macros. See this Stack Overflow article for more information. Unlike grep, however, we only colorize the first match of a line.
  • Recall that printf()’s %s format specifier prints null-terminated strings. You may find the %.*s format specifier helpful when printing the output with color. See the section about printf()’s precision specifier in APUE 5.11.
  • If the output of greptile is redirected to a file, you should not colorize the output. See APUE 18.9.
    • Think about why we might want to do this.
  • If the directory command line argument is not given – in which case the search directory is set to . – do not prepend the file path with ./ in the output. This mimics the behavior of the ripgrep utility.

Testing

You should test your implementation of greptile against a directory containing a large number of subdirectories and files. We have provided a copy of the Linux kernel source code in the /opt/asp directory on SPOC. You should use this directory to test your program, and are encouraged to test your program with other directories as well. You can use the provided sample executable to verify that your program is working correctly.

Deliverables

• Makefile, greptile.c, and any other source files under part1/.

Part 2: Multi-threaded greptile 🦖

Requirements

• Your program should keep the same semantics as in Part 1.
• Parallelize the search using POSIX threads. We’ve defined NUM_THREADS in the skeleton code as the number of worker threads you should create. The main thread will iterate over directories, passing files to worker threads using a bounded ring buffer.
• The bounded ring buffer will be implemented as struct search_ring_buffer. We provide some definitions and skeleton code for working with this ring buffer. Do NOT modify the provided type definitions or the function signatures. A couple of additional notes:
  • rb_enqueue() and rb_dequeue() should be “thread-safe” functions. That is, the implementations of these functions must employ the necessary synchronization to safely access the ring buffer.
  • After an element is added or removed from the ring buffer, should you call pthread_cond_signal() or pthread_cond_broadcast()? Or will the program behave correctly both ways (assuming everything else is correct)?
• Note that multiple threads will be performing searches on different files at the same time. Without any coordination between the threads, their outputs may be interleaved. You should ensure that the threads’ outputs are not interleaved.
  • We provided a partial implementation of a FIFO queue called struct print_queue, which stores the search results for a single file. Do NOT modify the provided type definitions or the function signatures.
  • When a worker thread completes its search of a file, it will print the results collected in its struct print_queue. In order to prevent outputs from different threads from being interleaved, each thread will hold a lock while printing the entirety of its struct print_queue. You can use the lock associated with stdout. See the flockfile() function in APUE 12.5.
    • When printing error messages to stderr, you should hold stdout’s lock to ensure that your error messages do not interleave with other worker threads’ output.
• Your worker threads must exit cleanly once there are no more files to search. You can accomplish this by “poisoning” the ring buffer. Enqueue null values and have the worker threads exit if they dequeue a null value.

Deliverables

• Makefile, greptile.c, and any other source files under part2/.

Part 3: Performance Evaluation (Optional) 🐢

Reading

• CSAPP 9.3: VM as a Tool for Caching
• mmap() man page: MAP_FIXED
• grep design
• ripgrep design

Tasks

This part is optional and will not be graded.

In this part, you will evaluate the performance of your greptile program, using two different implementations. In Part 1, you used malloc() to allocate a buffer for reading the file. In this part, you will use the mmap() function to create a file-backed mapping instead.

This part is purposefully left open-ended to encourage you to think about performance and to experiment with different tools and techniques.

• Create a part3 directory, and copy your part1 implementation into it.
• Modify your part3 implementation to use mmap() and munmap() instead of malloc() and free() to read files.
  • Recall that strsep() and strstr() operate on null-terminated strings. As in Part 1, what does this imply about the necessary size of the mapping?
  • Note that mmap() allocates memory in multiples of the system’s page size, and fills the extra bytes with 0’s. When creating a file-backed mapping, we can allocate more pages than the file would occupy. However, even if the allocation succeeds, the kernel does not let us access these extra pages. See the SIGBUS section in mmap()’s man page. This leads to a problem with using mmap() for our purposes when the file size is a multiple of the page size.
  • In that case, you can take advantage of MAP_FIXED, which forces the kernel to map the file at the specified address. You should read the relevant section in mmap()’s man page, including the NOTES section.
  • First, you create an anonymous mapping of the necessary size without MAP_FIXED. Then, you create a file-backed mapping of the file’s size with MAP_FIXED at the address of the anonymous mapping. In this way, MAP_FIXED effectively serves as dup2() for memory mappings.
  • Your implementation should handle both cases (when the file size is and isn’t a multiple of the page size) cleanly, without calling mmap() more times than necessary in each case.
  • Note that munmap() can unmap multiple mappings at once. See its man page for more details.
• Now, compare the performance of the two implementations and summarize your observations in part3/perf.txt.
  • You may find the /usr/bin/time -v command useful. You should compare the time taken, the number of page faults, and the amount of memory used (resident set size), along with any other relevant statistics. Describe why these differences occur and their impact on performance based on the reading in CSAPP 9.3.
  • You may also find the malloc_stats() function useful for analyzing memory usage across the two implementations.
  • You may use any other tools you find useful for performance analysis.
• If you have time, port your part2 implementation to use mmap() and munmap() instead of malloc() and free(). There is no need to submit this implementation – it should be straightforward once you’ve converted your part1 implementation.
  • Compare the performance of the single-threaded mmap() implementation with the implementation of the multi-threaded mmap() implementation. Summarize your observations in part3/perf.txt.
  • You may use any other tools you find useful for performance analysis.

---

Acknowledgments

Tal Zussman implemented the solution for this assignment in Spring 2024.

---

Last Updated: 2024-09-25