-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
150 lines (116 loc) · 5.76 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
Brandon Wu
****************************************************************************
* CS 111 Lab 1C *
****************************************************************************
DESIGN PROJECT:
The interactive shell is reachable by commandline option ./timetrash -i
0. CONTENTS
1. Implementation Details ................. 11
2. Limitations ............................ 71
1. IMPLEMENTATION DETAILS
This POSIX shell command reader employs a token-centric implementation of
the parser. The command_stream object is implemented as a linked list of
command_nodes which is a structure defined with the following members:
command_node* nxt;
command_t cmd;
I.e. it contains a pointer to a command_node containing the subsequent
command if it exists (or NULL if it is the last command in the stream). The
"cmd" member is a pointer to the command object.
The command structure follows the definition provided in
"command-internals.h".
The "read_command_stream" function processes each command in the stream
individually until the stream is empty (returns NULL).
The "make_command_stream" function calls the "make_command" function
until it returns NULL (no commands remain in the filestream).
The "make_command" function is an interface that calls its auxilary
function "make_cmd_aux".
The "make_cmd_aux" function parses the filestream for a valid command.
In the basic case, it reads in a single line from the filestream using
the "get_line" function and stores the line in a line buffer array.
The line buffer is parsed for individual tokens by calling the
"get_token" function. A token is a structure defined with the following
members:
token_type type;
char* word;
The type "token_type" is an enum of all special tokens and words
(not including white space). The word member is only utilized for
token_type = WORD, in which it contains an array of characters that
compose the word.
Make cmd_aux asks get_token to categorize and return the next token
in the line buffer and processes each type differently:
For token_type = WORD, each token sequentially. The word member is
copied into the cmd->u.word field. This operation is terminated
when the end of the line buffer is reached or if another special
character is encountered.
For token_type = {IN,OUT}, corresponding to the I/O redirection
characters, if the current command does not already have such field defined,the following token returned by get_token is placed in the
cmd->{input,output} field.
For token_type = {AND, OR, PIPE, SEMI} corresponding to all sequence-type
tokens of the form A <token> B, all tokens processed thusfar are copied intoa newly allocated command at cmd->u.command[0]. The contents of
cmd->u.command[1] are found by calling make_cmd_aux recursively.
For token_type = OPAREN (open parenthesis), a SUBSHELL_COMMAND is present.
The contents of this command are determined recursively, until a ')' is
discovered or EOF.
PART B:
Execute command works trivially for all commands once execute command
for a SIMPLE_COMMAND is estabilished. For a SIMPLE_COMMAND, the execution
calls "exec_simple" which performs a fork() system call. For the serial
case (time_travel == 0), the parent waits on the child pid to finish,
storing the exit status of the child it its appropriate location.
The child calls an exec() system call to change the program of execution
to that of the command that is called. This approach works well for
the parallelization case.
The AND and OR command recursively calls the execute_command function,
either one or two recursive calls is made depending on the type of command
and the exit status of the first executed command (if exit is 0 for AND
or exit is 1 for OR). Sequence command also works similarly.
The PIPE_COMMAND is handled by a special case. Consider the following
pipe command: A | B. This is interpreted as A > temp; B < temp. Therefore,
for a large stream of pipe commands, e.g. A | B | C | D, we utilize
two temporary files and interleave them so there is no R/W thrashing.
The SUBSHELL_COMMAND simply calls the execute command function
recursively on its subshell command.
PART C:
PART C introduces support for "time_travel" mode. The basic idea here
is that when the fork() system call is made, the parent need not wait for
the child to terminate, it simply moves onto executing the next command.
The only time a wait occurs is when a child should wait on another child.
In this case, the entire thread of execution enters a critical section,
so the new process is not forked until the one it is blocked on finishes.
This is implemented using a dependency table held by the main function
but manipulated by sub-routines in execute_command.c. The Dependency table
is implemented as a linked list with the following structure:
struct depend_node
{
depend_node_t nxt;
char* handle;
pid_t pid;
};
The handle member contains a string of the file handle name. The pid
field holds the pid that the current command is blocked on (i.e. it should
wait for pid to exit before forking its own child).
2. LIMITATIONS
The following limitations are present within the design:
1. Under some very special cases that have not been completely identified,
syntax errors are reported at lines > than the actual line of the error.
Most common seen in multi-line subshell commands
2. When a nested subshell is used, the inner subshell command must be
contained within a single line. For example,
(
echo hello
)
is valid, and so is
(
( echo hello )
)
but
(
(
echo hello
)
)
is a syntax error
3. When in time_travel mode, sometimes the process will exit before all
commands are done. This happens because the parent does not wait for the
children to exit unless the next command to be scheduled is blocked by
one of the previous commands.