Description
1. Background Grep is a linux command that is used to find patterns in each file. It prints each line that matches the pattern. In this project you will be implementing “Parallel string matching” that will search for a string in all files and subdirectories of a root directory using multiple processes. 2. Project Overview You will be using File I/O, Pipes, directory operations, links and I/O redirection. In this project you are required to spawn multiple child processes. Each child process is responsible for searching some portion of the root directory and communicates the search results to the parent using pipes. Parent is responsible for reading from these pipes and printing the output to the terminal. Only the parent should print the output to the terminal. For the final submission If you are using the child program to directly print to the terminal, none of the test cases will pass the grading script. 2.1. Input PA2 program will take 2 arguments, the string to be searched and the path to the root directory. “String” is a single English word and “root directory” is any directory that needs to be searched. Example : $ ./master 2.2. Output The program prints all the lines containing the String. The output format is as follows: [Path to the file containing the String] : Line containing the string If there are multiple lines in a file containing the “String”, each such line is printed once. Example : $ ./master input/ip1 Imagine input/ip1/Imagine_By_Lennon.txt: Imagine there’s no heaven input/ip1/Imagine_By_Lennon.txt: Imagine all the people input/ip1/Imagine_By_Lennon.txt: Imagine there’s no countries input/ip1/Imagine_By_Lennon.txt: Imagine all the people input/ip1/Imagine_By_Lennon.txt: Imagine no possessions input/ip1/Imagine_By_Lennon.txt: Imagine all the people 2.3. String Matching String matching needs to be case sensitive. Use of the strstr() function provided by the string library is strongly recommended. Autograding script will take into account the number of matches your program returned. 2.4. Child processes and Root Directory The root directory may contain multiple first level subdirectories and files. One child process needs to be created for every first level subdirectory. This child process is responsible for searching all the files in its sub directories. A pipe must also be created for every child. Pipe is used by the child to communicate the results back to the parent. Consider a possible directory structure as shown in Fig 1. Here the root directory /root contains 2 first level subdirectories, namely /root/f1 and /root/f2. Child 1 as shown in the figure, is responsible for searching files in /root/f1. Child 2 as shown in the figure is responsible for searching files in /root/f2. Note that no new child is created for the /root/f2/f3 directory. Child processes are only created for the first level directories. Also note that parent is responsible for searching first level files in this case File 5 and no new child is created for this. Fig 1: Input Directory structure 2.5. Pipes and I/O redirection Pipe will be used by the child to communicate search results to the parent. Parent reads from the pipe and prints it to the console. Each child’s STDOUT must be redirected to the write end of the pipe. One pipe must be created for each child process. In Fig 1, two pipes are created, one for each child. 2.6. Directory Traversal and Soft links Each child process needs to traverse the sub-directory assigned to it recursively, searching every file in its directory sub structure and writing search results to the pipe. A file may be a regular file, link, directory etc. While traversing the directory, make sure to not parse soft links files. Hint : Type of a file may be identified by st_mode present in the stat structure returned by lstat command. 2.7. Extra credit (Handling Hard Links) A hard link is a directory entry that associates a name with a file in the file system. There can be multiple hard links pointing to the same file in the file system. For extra credit you need to identify hard linked files and parse the underlying file only once. For example : Consider the directory structure in Fig 2, where two hard links, ln1 and ln2 point to the same file (File). You are required to parse File only once although you will encounter two entries to the same File during directory traversal. Hint: This can be done using the inode number of the file present in stat structure returned by stat/lstat functions. You may also need to maintain a data structure that stores information about inode numbers already seen. Important Note: You may assume that hard links to a file are always present in the same first level subdirectory. Fig 2 : Hard Links 3. Project Folder Structure Please strictly conform with the folder structure. The conformance will be graded. You should have a project folder named “PA2_G[Your group number]” (e.g. PA2_G23 for project group 23). The project folder contains “include”, “lib”, “src”, “input” and “output” folders, as well as Makefile, README and two executables. ● “include” folder: .h header files ● “lib” folder: .o library files ● “src” folder: .c source files ● “input” folder: contains input folders ● “output” folder: Use $ make run to create output files for all test cases ● Two executables: master and child 4. Execution Syntax The usage of pa2 is as follows. 4.1. Run master program directly by using : $ ./master 4.2. Run test cases: For test case 1: $ make run1 For test case 2: $ make run2 , and so on 4.3. Generate output: $ make run 5. Assumptions and Hints – You may assume that a pipe never gets full – All hard links to a file are within a single first level directory – strstr() function from string library may be used for string matching – Maximum number of first level directories is 10 – No assumption can be made on depth of the directory – Maximum file size is 5KB – Maximum length of line is 1000 Bytes 6. Submission 6.1. Interim Submission – Complete root directory traversal (in master.c) and create the required number of child processes. – Child program should be launched with appropriate arguments using exec() – Inside the child, print path to the directory assigned to it. – Master should wait for all the child processes to complete. Interim submission should be a zip containing two .c files (master.c and child.c) and an Interim report (pdf). Interim report should include: – Project group number – Members’ name and X500. – Plan on individual contributions – Captured screenshot showing terminal output for test case 4. If the requirements are correctly implemented, 7 child processes will be created. Due date for the interim submission is Oct. 20, 2021 (Wed.), 11:59pm. No late submissions will be accepted. 6.2 Final Submission One student from each group should upload to Canvas, a zip file containing the project folder. README should include the following details: – Project group number – Group member names and x500 addresses – Members’ individual contributions – Any assumptions outside this document – How to compile and run your program The README file does not have to be long, but must properly describe the above points. Your source code should provide appropriate comments for functions. At the top of your README file and each C source file please include the following comments: /*test machine: CSELAB_machine_name * group number: G[Group Number] * name: full_name1 , [full_name2] * x500: id_for_first_name , [id_for_second_name] */ Your project folder may have all folders and files mentioned in Section 3 Folder Structure. However, please DO NOT include “input”and “output” folders in your final deliverable. You can modify the provided Makefile. Make sure the zip file you are submitting contains all the necessary files and compiles. Due date for the final submission is Oct. 27, 2021 (Wed.), 11:59pm 7. Grading Policy (tentative) 1. (10%) Interim submission a. Correct report content b. Completeness of minimum implementation requirements 2. (5%) Appropriate code style and comments 3. (5%) Conformance check a. Correct README content b. Folder structure and executable names c. Print Format 4. (60%) Test Cases a. ip1/ : Single File at root level b. ip2/: Single Folder c. ip3/ : Single Folder and some root level files d. ip4/ : 7 folders and some root level files e. ip5/ : Symlink f. ip6/ : Multi level folders 5. (20%) Code a. Correct use of process-related functions such as fork(), wait() and exec() b. Correct use of pipe, dup c. Correct use of File I/O related functions (fopen etc) d. Correct use of Directory functions(opendir, readdir etc) 6. (10%) Extra Credit a. (5%)Code b. (5%) Test case i. Ip7/: Root level hard link ii. Ip8/: Subdirectory level hard links
