Updates
Feb 4: Added detail about the max depth. Specifying that the depth argument is “non-inclusive”: if the max-depth is N, then it prints the tree to depth N, not including the nodes at depth N.
Introduction
The goal of this assignment is to practice system calls and dynamic memory allocation. You’ll be writing a program that explores the /procvirtual file system to generate (and display) a tree of the processes (the executing programs) on the system. To do so, you will need to dynamically allocate and manipulate nodes in a tree structure. The end result will be output that describes the children of a given process, much like the pstreecommand does:
$ pstree -p 1123sshd(1123)---sshd(25914)---sshd(25987)---bash(25988)---pstree(1243) |-sshd(27395)---sshd(27468)---bash(27469) |-sshd(29462)---sshd(29498)---bash(29531) |-sshd(29499)---sshd(29529)---sftp-server(29530) |-sshd(29874)---sshd(29912)---bash(29913) |-sshd(30932)---sshd(30962)---sftp-server(30963) | |-sftp-server(30964) | |-sftp-server(30965) |-sshd(31511)---sshd(31547)---bash(31548)
Please remember that we are using testing scripts to evaluate your work. As a result, it’s very important that (a) all of your files are named correctly and located in the specified locations in your repository and (b) your output matches the expected output precisely.
The assignment is initially due at 10:00 p.m. on Wednesday, February 14. We will test your code on a linux lab machine immediately after the deadline and will send you the results of our tests. Second submissions are due at 10:00 p.m. on Friday, February 16, immediately before reading week.
Getting Started
Pull your git repository. There should be a new folder named a2. All of your code for this assignment should be located in this folder and includes a Makefile; print_ptree.c, which contains the mainfunction and will need some additional argument handling code; test_print.c, which contains a mainfunction for testing a single function; ptree.h, which contains function prototypes and a struct for a tree node; and ptree.c, which contains the signatures for the two functions to be written. There is also a directory for testing with simulated data.
Like Assignment 1, I recommend that you start by doing a walkthrough of the Background section and then, as you explore, create tests that you can use to verify your program. You may want to create a few proc-like directory trees that you can create for testing. Then, you can write a bash script that executes your code on the tests so that you can check the output.
Testing
Your Makefilecontains an option to help you with testing. Open it with a text editor. You should see two lines that define FLAGS, one of which is commented out:
FLAGS = -Wall -Werror -std=c99# FLAGS = -Wall -Werror -g -std=c99 -DTEST
If you wish to run tests using your tests/directory, rather than the actual /procdirectory for the system, comment out the first line and uncomment the second. Then, when you compile your code, your program will look for process information in the tests/directory rather than in /proc. You can add additional examples to your tests/directory. We have included the processes necessary to reproduce the example at the top of this handout.
Important Note: The tests in the tests/directory are likely to have small differences from the entries in /proc. For example, the exefile in our tests is a regular file, rather than a link, and none of the cmdlinefiles include anything other than just the executable name. You should also test on a linux machine with /proc, but it’s useful to have a clean, replicable example to test on (and if you are on a non-linux machin, you don’t have a proc/at all) which is why tests/will be useful.
While creating new tests — or while looking for real processes in /procto test with — you’ll find the ps commanduseful. In particular, if you type “ ps -u your_username“, you will get a listing of the processes running on the system that are owned by you. You can open up a second terminal and run commands or open a web browser to get additional processes to test.
Background
A processis an executing program. Every time that you run a program on the command line, you are creating a process. The processes on a Unix system are naturally organized in a tree structure, since each process has a parent. When you execute a progam in a shell (on the command line), the shell process is the parent. The shell process also has a parent (often the loginthat created the shell). Each process knows the identify of its parent as well as some information about itself.
The operating system must track processes to make sure that they are getting the resources they need. For many flavors of linux, the information about processes is stored in the directory /proc. (Mac users: note that OS X does not have a /procdirectory since it’s based on bsd, which uses a different interface.) /procis very special in that it is a virtual filesystem. It doesn’t contain “real” files; rather, it contains runtime system information that can be accessed as if it were stored in files. Many system utilities are simply programs that access data from the “files” in this directory. Your task is also to access the data in /procto get information about the processes running on the system.
/procStructure
Every directory in /procthat we care about is a number. (There are quite a few non-numeric directories. Those refer to mounted devices, memory information, and other system data. We’ll ignore them for this assignment.) That number is a process ID (PID)— a unique identifier for a process on the system. Every process has a PID, and every process running on the system has an entry in the /procdirectory. In this document, we’ll refer to the entry for a single PID as the directory /proc/PID.
You will need to access three files inside of /proc/PID: exe, cmdline, and children. /proc/PID/exeis the file to check to make sure the entry is for a running program. If it exists, then PID is a valid running program. /proc/PID/cmdlinecontains information about how the program was called. In particular, you’ll need it to get the name of the executable. Finally, /proc/PID/task/PID/childrencontains the PIDs of child processes. The PIDs are space (or NULL) separated.
In addition, you may find the file /proc/PID/statusto be useful for verification purposes. It contains the parent process’s ID (PPID).
Take a few minutes to log onto a linux machine and browse through its /proc. Use catand grepto view and search through these files to make sure you know how they are formatted, so you can begin to think about extracting information from them. You’ll likely find that you don’t have access to the contents of one file; you can check if that linkexists but cannot open the file it refers to. (Why?) You’ll find that the other files are sometimes empty. (What does that suggest?)
Useful C Functions
To access the data in /proc, you’ll need to use a number of system calls that access the filesystem. A filesystemis an operating system module that encapsulates the data structures used to track files on a disk and the functions used to manipulate those data structures. For this course, we don’t need to know much about those structures to use files (but just wait until CSC369!). Instead, we simply need to understand the system calls that the operating system exposes for users to access the file system and the macros that C provides to make using those system calls easier.
Here is a set of system and library calls that we think you’ll need for this assignment. You should look them up, so you know what they provide for you. From the filesystem, we expect you will need fopen, fread, and fcloseto access and read data from files. You will need lstatto determine that a file exists without opening it. You will also need the library call mallocto dynamically create nodes for the tree structure you will be creating to track process information. You may find the call sprintfhelpful for creating filenames and various functions from the stringlibrary, like strchrand strtok, useful for parsing the contents of files.
You may notuse the systemfunction or functions like it that allow you to execute commands on the shell. The intent of the assignment is to have you working with system calls — not to use shell programs that will invoke those system calls for you.
Requirements
You must write two functions, generate_ptreeand print_ptree, that are located in ptree.c. You must also write code in print_ptree.cto handle the expected command line arguments and to emit appropriate errors.
print_ptree.c
Your program should emit an appropriate error message (which we are not specifying) to stderr and return 1if an error is detected in the command line arguments used. The arguments may be incorrect if an insufficient or too many arguments are provided or if an option is provided that is not supported. (The only option we will support is “-d”.) Your program should return 0if it is able to run without error. If there is some sort of error that is not a command line error, return 2(for example, if a library call or generate_ptreewere to fail).
The expected command line usage is already provided in the starter code. The program takes one optional flag, “-d”, which requires an argument. This sets the maximum depth of the process ID tree to be displayed. If the depth is not provided, it is assumed to be 0 (which means “print the entire tree”). The program requires one argument, a process ID, which must be an integer.
While it’s not required, it’s strongly recommended that you use getopt to parse the command line.
print_ptree
You should complete the print_ptreefunction before the other required function, since you can test it by manually creating small trees for it to print. (See the starter code file test_print.cfor an example of how to test the print function separately.) Then, you can test the other function, generate_ptree, by printing the trees it generates.
This function should be recursive. It accepts the root of a tree, as described in the section about generate_ptreeand a depth argument. The function prints (to stdout) the tree to the desired depth, not including nodes at the specified depth. (i.e., Nodes from depth 0 to the specified depth are printed, not including the latter endpoint.) If the depth argument is 0, then the entire tree should be printed.
The function will print one process per line. The root of the tree will be printed flush to the left. Each child process will be indented two spaces to the right with respect to its parent. Child processes should be displayed in the order in which they occur in the list of children. Each line will contain the process’s ID (its PID), a colon and a space, and the name of the executable. If the executable is not named, then the line will just contain the PID (no colon, no space, no executable name).
generate_ptree
This function may need a recursive helper function. It takes a PID as an argument and creates a tree that describes that process and all of its children. The root of the tree is “returned” by assigning it to the parameter root. The entire tree, including the name strings in each tree node, should be dynamically allocated using malloc, and it must be built as described below.
Each node in tree is a struct TreeNode. It contains the PID of the process it is describing, as well as the name of the executable associated with that PID. If there is no executable name (from /proc/pid/cmdline), then the name pointer should be NULL. The node also contains pointers to build a linked list. This linked list is used to store the children of this node. Why do we use a list for the child nodes?
In CSC148, you probably built binarytrees: trees with two child nodes. In those cases, it makes sense to create links to just those two nodes (often named “left” and “right”). However, in this case, each node in your tree can have an arbitrary number of children: it’s not binary. Therefore, we have to use a different method for storing children: a list. If the child_procspointer has value NULL, then the node has no children. If child_procsis non-null, then the first element of the list is the first (left-most, if you prefer) child. The node it points to, using the next_siblingpointer, is the second child. If the next_siblingpointer is NULL, then the node is the last child of its parent. The children should appear in the list in the same order as they were observed in the childrenfile.
In the example we’ve been using throughout this handout, the node associated with PID 1123 is the root of our tree. Its next_siblingpointer is NULL. Its child_procspointer refers to the node for PID 25914. The node for PID 25914 has a child_procspointer that refers to the node for PID 25987. PID 25914’s node’s next_siblingpointer refers to the node for PID 27395. This handout provides a second example relating a process structure to a tree.
generate_ptreeshould return 0 if the tree is built successfully and 1 otherwise. In particular, it should return 1 if any of the system or library calls fail. Your function will also return 1 if /proc/PIDdoesn’t exist for the specified PID or if /proc/PID/exedoesn’t exist, indicating that the process was not executing. In both of these cases, no node should be created for the PID. If your function returns a 1, then the rootparameter should still contain as much of the tree as could be built. The tree should be as valid as possible: it should contain no dangling or uninitialized pointers and should contain a node for every PID that could be successfully processed.
Note: You will need to create paths to various files in order to view them. The starter code contains an example that uses sprintfto generate paths. The example also relies on a constant, MAX_PATH_LENGTH, which contains an upper bound on the length of paths we will test with. In general, defining such an upper bound is tricky, but we guarantee that our tests will not exceed this bound, so you can safely use it to define arrays for storing paths.
Submission
Please commit to your repository often, so that you don’t lose your work. We will mark the last submission to your repository that occurs before the deadline. We will look at print_ptree.cand ptree.c, so those files must be pushed for us to successfully test your code. You may want to clone your repository a second time to verify that these files have been successfully committed andpushed.
You may add test files to your repository, if you wish. When we test, we will be copying your .c and .h files to a testing folder. We will compile them using our original Makefileand then run a series of tests using the executable. We may also compile your helper functions (in ptree.c) with our own main programs to test them separately, so it’s important that they have the required signature.
Remember to also test your code on a lab machine before your final submission. Your program must compile cleanly (without any warning or error messages) on the lab machines using our original Makefileand may not crash (seg fault, bus error, abort trap, etc.) on our tests. Programs that do not compile or which crash will be assigned a 0 and will need to be resubmitted.
Reviews
There are no reviews yet.