Initial commit.
[aple.git] / Unix_Concepts.m4
1 TITLE(«
2
3 Unix is user-friendly. It's just very selective about who
4 its friends are. -- Unknown
5
6 », __file__)
7
8 SECTION(«History and Philosophy»)
9
10 SUBSECTION(«Early Unix History»)
11
12 <p> Unix was created in 1969 as a successor of Multics, the
13 <em>MULTiplexed Information and Computing Service</em>, which had been
14 in use since the mid 1960s as the successor of CTSS, the <em>Compatible
15 Time-Sharing System</em> of the early 1960s. Multics aimed to get
16 CTSS right, but failed in this regard and was eventually discontinued
17 because of its complexity. The Unix approach was very different as it
18 was brainstormed by only three people and then implemented by Ken
19 Thompson at Bell Laboratories in two days. Unlike its predecessors it
20 focused on elegance and simplicity. The name was originally spelt
21 UNICS (<em>UNiplexed Information and Computing Service</em>) to
22 emphasize the contrast to Multics. </p>
23
24 <p> The original Unix implementation was written in assembly
25 language for the 18 bit processor of the PDP-7 "minicomputer", a
26 device of the size of a wardrobe which was considered small by the
27 standards of the day. Like all computers of this era, the PDP-7 was
28 not connected to a video screen. Instead, input had to be typed in on
29 the <em>console</em>, a device which looked much like an electric
30 typewriter. Output from the computer was printed on rolls of paper.
31 Since the assembly instructions could not easily be ported to different
32 hardware, Dennis Ritchie invented the C programming language in
33 1971. By 1973 the complete Unix implementation had been rewritten in C.
34 The C language was another corner stone in the history of Unix which
35 turned out to be very successful. While other programming languages
36 of that time have long been abandoned or play merely a niche role, C
37 is still one of the most widely used programming languages today. The
38 first Unix application was <code>roff</code>, a typesetting program
39 which is still ubiquitous as the manual pages which ship with every
40 Unix system are formatted with roff. </p>
41
42 <p> From the beginning, Thompson and his early collaborators encouraged
43 close communication between programmers, creating an early form of
44 community. Up to the present day, this "hacker culture" has been a
45 stimulus for countless improvements. Copies of Unix were distributed
46 on tapes, hand-signed with "Love, Ken". Over time many universities
47 contributed to Unix. By the end of the 1970s, Unix accumulated a
48 whole bunch of utilities that made it a fully flavored operating
49 system which was also free of any copyright claims. </p>
50
51 <p> Despite the primitive hardware of the time, the early Unix was
52 remarkably similar to modern Linux systems. For example, the task
53 scheduler, the hierarchical filesystem tree and the shell already
54 existed back then. </p>
55
56 SUBSECTION(«Networking»)
57
58 <p> The <em>Advanced Research Projects Agency</em> (ARPA) was a
59 military research unit that was part of the USA's department of
60 defence. It was established in the early 1960s with the mandate to
61 create systems that could survive a nuclear war. The agency created
62 the <em>arpanet</em>, the predecessor of today's internet, which was
63 designed to stay operational after subordinate network losses. By
64 the end of the 1960s and the early 1970s, the fundamental networking
65 protocols were established: telnet for remote login was standardized
66 in 1969, email (SMTP) in 1971, and the file transfer protocol (FTP)
67 in 1973. </p>
68
69 <p> By the end of the 1970s many Unix installations existed in
70 all parts of the world. However, the arpanet was mostly powered by
71 commercial Multics systems because Unix only had rudimentary network
72 support (UUCP, the <em>Unix to Unix copy</em>) which could copy files
73 over telephone lines via modems but not much more. This changed in
74 1983 when TCP/IP networking was developed by the ARPA to replace the
75 arpanet. Unix support for TCP/IP was developed at Berkeley University
76 which had become the "Mecca" for Unix development and started already
77 in 1977 to release their own Unix system named BSD, the <em>Berkeley
78 Software Distribution</em>. </p>
79
80 SUBSECTION(«Commercialization, POSIX and GNU»)
81
82 <p> With excellent networking support and no licensing issues, it
83 was only a matter of time until companies became interested in Unix
84 in order to make money. Several companies started to commercialize
85 Unix by adding features to the common code base but keeping their
86 improvements closed, effectively stopping the source code from being
87 freely distributable. At the same time Microsoft began to sell their
88 DOS operating system, targeting small businesses and the home market.
89 DOS lacked many features that Unix already had for a decade, like
90 multi-tasking and multi-user support, but it did run on the cheap
91 Intel 286 processors that were too weak for Unix. </p>
92
93 <p> By 1985 the commercialization of Unix and the success of Microsoft
94 had damaged the Unix community badly. But also the various companies
95 that sold their particular proprietary Unix brand realized that
96 too many incompatible Unix implementations would only hurt their
97 business. That's where the Computer Society of the <em>Institute of
98 Electrical and Electronics Engineers</em> (IEEE) became involved
99 in Unix. The IEEE is an organization which was already founded in
100 1946 to advance the theory, practice, and application of computer
101 technology. This organization created POSIX, the <em>Portable Operating
102 System Interface for Unix</em>, which is a family of specifications
103 for maintaining compatibility between operating systems. The first
104 version of POSIX was published in 1988. It covered several command
105 line utilities including <code>vi(1)</code> and <code>awk(1)</code>,
106 the shell scripting language, application programmer interfaces (APIs)
107 for I/O (input/output) and networking, and more. Up to the present
108 day POSIX is maintained by the IEEE and new revisions of the POSIX
109 standard are published regularly. </p>
110
111 <p> In 1983 Richard Stallman launched the GNU project and the Free
112 Software Foundation as a reaction to the ongoing commercialization
113 of Unix. GNU, which is is a recursive acronym for "GNU's not Unix",
114 aimed to keep the Unix source code free, or to replace non-free parts
115 by open source equivalents. To this aim the GNU project created
116 the <em>GNU General Public License</em> (GPL), which requires not
117 only the source code to stay free, but also that all subsequent
118 modifications to the code base remain free. By the end of the 80s,
119 the GNU toolset had become a full developer software stack licensed
120 under the GPL. This set of software packages was complemented by
121 the <em>X window system</em>, which was also released under a free
122 license and enabled programmers to build graphical applications for
123 desktop systems. Moreover, the first open source scripting language,
124 <em>perl</em>, was released in 1987. </p>
125
126 SUBSECTION(«Linux»)
127
128 <p> In 1985 Intel announced the 386 processor which, unlike its 286
129 predecessor, was powerful enough to run Unix. There were efforts to
130 port the Unix operating system kernel to this hardware, but these
131 efforts were impaired by pending lawsuits about who owns the copyright
132 on the BSD source code. Due to the unclear legal situation of the BSD
133 code, the major missing piece in the GNU toolset was a free operating
134 system kernel. This hole was filled in 1991 when Linus Torvalds,
135 a student from Helsinki in Finland, announced the first version of
136 his <em>Linux</em> kernel. </p>
137
138 <p> Linux did not repeat the licensing problems of the original Unix
139 because the Linux source code was written from scratch and licensed
140 under the GPL. Due to this difference many developers moved from
141 Unix to Linux, so Linux grew quickly and started soon to outperform
142 the commercial Unix kernels in almost every benchmark. The cheap 386
143 hardware, the Linux kernel, the GNU toolset and the graphical user
144 interface based on the X window system facilitated cheap workstations
145 which ran a complete open source software stack. </p>
146
147 <p> The success of Linux, or <em>GNU/Linux</em> as some prefer to
148 call it for reasons that should now be clear, has only increased
149 over time, to the point where commercial Unix systems are mostly
150 irrelevant. Today Linux runs on a wide variety of machines ranging
151 from supercomputers to workstations, smart phones and IOT (internet
152 of things) devices with very limited resources.
153
154 <p> The same companies which almost killed Unix by commercializing it
155 in order to maximize their profit make money with Linux today. However,
156 they had to adjust their business model in order to comply with the
157 GPL. Rather than selling proprietary software, they bundle open source
158 software and sell support to paying customers. Some companies also
159 sell hardware with Linux pre-installed. </p>
160
161 SUBSECTION(«Linux Distributions»)
162
163 <p> A <em>Linux Distribution</em> is a conglomeration of free software,
164 including the Linux kernel, the GNU toolset and the X window system,
165 plus possibly other, proprietary software on top of that. Usually a
166 distribution also includes an installer and a package manager to
167 make it easy to install and update packages according to the users'
168 needs. </p>
169
170 <p> There are hundreds of Linux distributions, and new distributions
171 are created all the time while others are discontinued. Many
172 distributions are backed by companies which target specific
173 classes of users or hardware, but there are also non-commercial
174 Linux distributions which are solely driven by a community of
175 volunteers. </p>
176
177 <p> One of the most popular company-backed Linux distributions is
178 <em>Ubuntu</em>, which is led since 2004 by the UK-based Canonical Ltd.
179 It targets unskilled desktop users which would like to switch away
180 from Microsoft Windows. One reason for the popularity of Ubuntu
181 is that it is very easy to install on standard desktop and laptop
182 hardware. A distinguishing feature of Ubuntu is its strict release
183 cycles: New versions are released in April and October of each year,
184 and every fourth release is a <em>long-term support</em> (LTS) release
185 which will be supported for at least five years. Ubuntu also features
186 a variant for server hardware which contains a different Linux kernel
187 and ships with most desktop packages excluded. </p>
188
189 <p> The main community-driven Linux distribution is
190 <em>Debian</em>. The Debian project was founded in 1993 and the first
191 stable version was released in 1996. Debian is used as the basis for
192 many other distributions. In fact, Ubuntu is based on Debian. The
193 development of Debian closely follows the Unix culture in that it
194 is developed openly and distributed freely. A team of about 1000
195 core developers work together with countless package maintainers
196 according to the Debian Social Contract, the Debian Constitution,
197 and the Debian Free Software Guidelines. </p>
198
199 EXERCISES()
200
201 <ul>
202 <li> Run <code>uname -a</code> on various Unix machines to see the
203 OS type and the kernel version. </li>
204
205 <li> Nice read on the
206 <a href="http://www.catb.org/~esr/writings/taoup/html/ch02s01.html">Origins and
207 History of Unix</a>, 1969-1995. </li>
208
209 <li> Explore the <a
210 href="https://upload.wikimedia.org/wikipedia/commons/7/77/Unix_history-simple.svg">Unix
211 time line</a>. </li>
212
213 <li> Try out the <a
214 href="http://www.gnu.org/cgi-bin/license-quiz.cgi">Free Software
215 licensing quiz</a>. </li>
216
217 <li> Read the <a
218 href="https://www.newyorker.com/business/currency/the-gnu-manifesto-turns-thirty">
219 notes on the 30th anniversary</a> of the GNU Manifesto. </li>
220
221 <li> Read the <a
222 href="http://www.catb.org/~esr/writings/unix-koans/end-user.html">
223 Koan of Master Foo and the End User</a>. </li>
224
225 <li> On a Debian or Ubuntu system, run <code>aptitude search
226 python</code> to list all python-related Ubuntu packages. Run
227 <code>aptitude show python-biopython</code> to see the description
228 of the biopython package. Repeat with different search patterns and
229 packages. </li>
230
231 <li> The Debian Social Contract (DSC) describes the agenda of Debian.
232 Find the DSC online, read it and form your own opinion about the key
233 points stated in this document. </li>
234 </ul>
235
236 SECTION(«Characteristics of a Unix system»)
237
238 <p> After having briefly reviewed the history of Unix, we now look
239 closer at the various components which comprise a Unix system and
240 which distinguish Unix from other operating systems. We focus on
241 general design patterns that have existed since the early Unix days
242 and are still present on recent Linux systems. </p>
243
244 SUBSECTION(«Single Hierarchy of Files»)
245
246 <p> The most striking difference between Unix and Windows is perhaps
247 that on Unix the files of all devices are combined to form a single
248 hierarchy with no concept of drive letters. When the system boots,
249 there is only one device, the <em>root device</em>, which contains the
250 <em>root directory</em>. To make the files of other devices visible,
251 the <em>mount</em> operation must be employed. This operation attaches
252 the file hierarchy of the given device to the existing hierarchy
253 at a given location which is then called the <em>mountpoint</em>
254 of the device. Mountpoints are thus the locations in the hierarchy
255 where the underlying storage device changes. </p>
256
257 <p> The root directory contains a couple of well-known subdirectories,
258 each of which is supposed to contain files of a certain type or for
259 a certain purpose. The following table lists a subset:
260
261 <ul>
262 <li> <code>/bin</code>: Essential commands for all users </li>
263 <li> <code>/sbin</code>: Essential system binaries </li>
264 <li> <code>/lib</code>: Essential libraries </li>
265 <li> <code>/usr</code>: Non-essential read-only user data </li>
266 <li> <code>/etc</code>: Static configuration files </li>
267 <li> <code>/home</code>: Home directories </li>
268 <li> <code>/tmp</code>: Temporary files </li>
269 <li> <code>/run</code>: Files which describe the state of running programs </li>
270 <li> <code>/var</code>: Log and spool files </li>
271 </ul>
272
273 <p> The <em>Filesystem Hierarchy Standard</em> describes the various
274 subdirectories in more detail. The exercises ask the reader to become
275 acquainted with this directory structure. </p>
276
277 SUBSECTION(«POSIX Commands and Shell»)
278
279 <p> The Filesystem Hierarchy Standard lists <code>/bin</code>
280 and <code>/sbin</code> and several other directories for executable
281 files. The POSIX standard defines which executables must exist in one
282 of these directories for the system to be POSIX-compliant. Well over
283 100 <em>POSIX commands</em> are listed in the XCU volume of this
284 standard. Besides the names of the commands, the general behaviour
285 of each and the set of command line options and their semantics are
286 described. POSIX versions are designed with backwards compatibility
287 in mind. For example, a new POSIX version might require a command
288 to support additional command line options, but existing options are
289 never dropped and never change semantics in incompatible ways. The
290 target audience of the POSIX document are programmers who implement
291 and maintain the POSIX commands and users which want to keep their
292 software portable across different Unix flavors. </p>
293
294 <p> One of the POSIX commands is the <em>shell</em>,
295 <code>/bin/sh</code>, an interpreter that reads input expressed in
296 the <em>shell command language</em>, which is also part of POSIX.
297 The shell transforms the input in various ways to produce commands
298 and then executes these commands. The user may enter shell code
299 (i.e., code written in the shell command language) interactively at
300 the <em>command prompt</em>, or supply the input for the shell as a
301 <em>shell script</em>, a text file which contains shell code. Shell
302 scripts which only contain POSIX commands and use only POSIX options
303 are portable between different shell implementations and between
304 different Unix flavors. They should therefore never cease to work after
305 an upgrade. Among the many available POSIX shell implementations,
306 <em>GNU bash</em> is one of the more popular choices. Bash is fully
307 POSIX compatible and offers many more features on top of what is
308 required by POSIX. </p>
309
310 <p> Several implementations of the POSIX commands exist. On Linux
311 the GNU implementation is typically installed while FreeBSD, NetBSD
312 and MacOS contain the BSD versions. Although all implementations
313 are POSIX-compliant, they differ considerably because different
314 implementations support different sets of additional features and
315 options which are not required by POSIX. These extensions are not
316 portable, and should thus be avoided in shell scripts that must work
317 on different Unix flavors. </p>
318
319 <p> In addition to the POSIX commands, a typical Unix system might well
320 contain thousands of other commands. This illustrates another aspect
321 that is characteristic for Unix: Tools should do only one specific
322 task, and do it well. The operating system provides mechanisms
323 to combine the simple commands in order to form more powerful
324 programs. For example, commands can be <em>chained</em> together so
325 that the output of one command becomes the input for the next command
326 in the chain. This is the idea behind <em>pipes</em>, a Unix concept
327 which dates back to 1973 and which is also covered by POSIX. We shall
328 come back to pipes and related concepts in a later section. </p>
329
330 SUBSECTION(«Multi-User, Multi-Tasking, Isolation»)
331
332 <p> From the very beginning Unix was designed to be a multi-user
333 and a multi-tasking operating system. That is, it could run multiple
334 programs on behalf of different users independently of each other and
335 isolated from each other. This design was chosen to improve hardware
336 utilization and robustness. In contrast, DOS and early versions
337 of Windows were designed for <em>personal computing</em> (PC) and
338 had no notion of user accounts, access permissions or isolation.
339 This resulted in an unstable system because a single misbehaving
340 program was enough to take down the whole system. Therefore these
341 features had to be retrofitted later. </p>
342
343 <p> While multi-tasking makes all tasks appear to run simultaneously
344 even if there are more tasks than CPUs, isolation refers to
345 <em>memory protection</em>, a mechanism which prevents applications
346 from interfering with each other and with the internals of the
347 operating system. A running Unix system maintains two sets of
348 running tasks: besides the <em>application tasks</em> there is
349 also a set of <em>kernel tasks</em>. Unlike the application tasks,
350 the kernel tasks are privileged in that they can access the memory
351 of the application tasks while applications tasks can only access
352 their own memory. Isolation is achieved by a hardware concept called
353 <em>protection domains</em>, which existed already in Multics and thus
354 predates Unix. In the simplest case, there are only two protection
355 domains: a privileged domain called <em>ring 0</em> for the kernel
356 tasks, and an unprivileged domain for application tasks, also called
357 <em>user processes</em> in this context. The CPU is always aware
358 of the current protection domain as this information is stored in a
359 special CPU register.
360
361 SUBSECTION(«System Calls and the C POSIX Library»)
362
363 <p> Only when the CPU is running in the privileged ring 0 domain
364 (also known as <em>kernel mode</em>, as opposed to <em>user mode</em>
365 for application tasks), it can interact directly with hardware and
366 memory. If an application wants to access hardware, for example read a
367 data block from a storage device, it can not do so by itself. Instead,
368 it has to ask the operating system to perform the read operation
369 on behalf of the application. This is done by issuing a <em>system
370 call</em>. Like function calls, system calls interrupt the current
371 program, continue execution at a different address and eventually
372 return to the instruction right after the call. However, in addition
373 to this, they also cause the CPU to enter kernel mode so that it can
374 perform the privileged operation. When the system call has done its
375 work and is about to return to the application, the protection domain
376 is changed again to let the CPU re-enter user mode. </p>
377
378 <p> The system calls thus define the interface between applications
379 and the operating system. For backwards compatibility it is of utmost
380 importance that system calls never change semantics in an incompatible
381 way. Moreover, system calls must never be removed because this would
382 again break existing applications. The syntax and the semantics
383 of many system calls are specified in POSIX, although POSIX does
384 not distinguish between functions and system calls and refers to
385 both as <em>system functions</em>. This is because system calls are
386 typically not performed by the application directly. Instead, if an
387 application calls, for example, <code>read()</code>, it actually calls
388 the compatibility wrapper for the <code>read</code> system call which
389 is implemented as a function in the <em>C POSIX Library</em> (libc),
390 which ships with every Unix system. It is this library which does the
391 hard work, like figuring out which system calls are supported on the
392 currently running kernel, and how kernel mode must be entered on this
393 CPU type. Like the POSIX commands, the system functions described in
394 POSIX never change in incompatible ways, so programs which exclusively
395 use POSIX system functions are portable between different Unix flavors
396 and stay operational after an upgrade. </p>
397
398 SUBSECTION(«Multi-Layer Configuration Through Text Files»)
399
400 <p> On a multi-user system it becomes necessary to configure programs
401 according to each user's personal preferences. The Unix way to
402 achieve this is to provide four levels of configuration options
403 for each program. First, there are the built-in defaults which are
404 provided by the author of the program. Next, there is the system-wide
405 configuration that is controlled by the administrator. Third,
406 there is the user-defined configuration, and finally there are the
407 command line options. Each time the program is executed, the four
408 sets of configuration options are applied one after another so
409 that the later sets of options override the earlier settings. The
410 system-wide configuration is stored in <code>/etc</code> while the
411 user-defined configuration is stored in that user's home directory.
412 Both are are simple text files that can be examined and modified with
413 any text editor. This makes it easy to compare two configurations
414 and to transfer the configuration across different machines or user
415 accounts. </p>
416
417 SUBSECTION(«Everything is a File»)
418
419 <p> Another mantra which is often heard in connection with Unix is
420 <em>everything is a file</em>. This phrase, while certainly catchy,
421 is slightly incorrect. A more precise version would be <em>everything
422 is controlled by a file descriptor</em>, or, as Ritchie and Thompson
423 stated it, Unix has <em>compatible file, device, and inter-process
424 I/O</em>. Modern Unix systems have pushed this idea further and employ
425 file descriptors also for networking, process management, system
426 configuration, and for certain types of events. The file descriptor
427 concept is thus an abstraction which hides the differences between the
428 objects the file descriptors refer to. It provides a uniform interface
429 for the application programmer who does not need to care about whether
430 a file descriptor refers to a file, a network connection, a peripheral
431 device or something else because the basic I/O operations like open,
432 read, write are the same. </p>
433
434 <p> File descriptors are ubiquitous since every Unix program uses
435 them, albeit perhaps implicitly via higher-level interfaces provided
436 by a scripting language. We shall return to this topic when we discuss
437 processes. </p>
438
439 SUBSECTION(«Manual Pages»)
440
441 <p> All POSIX commands and most other programs are installed along
442 with one or more <em>man pages</em> (short for <em>manual pages</em>),
443 which are plain text files that can be formatted and displayed in
444 various ways. This concept was introduced in 1971 as part of the
445 <em>Unix Programmer's Manual</em>. The characteristic page layout
446 and the typical sections (NAME, SYNOPSIS, DESCRIPTION, EXAMPLES,
447 SEE ALSO) of a man page have not changed since then. The POSIX
448 <code>man</code> command is used to view man pages in a terminal. For
449 example, the command <code>man ls</code> opens the man page of the
450 <code>ls</code> command, and <code>man man</code> shows the man page
451 of the <code>man</code> command itself. Most implementations also
452 maintain a database of the existing man pages and provide additional
453 commands to query this database. For example, the <code>whatis</code>
454 command prints the one-line description of all man pages which match
455 a pattern while the <code>apropos</code> command searches the manual
456 page names and descriptions. </p>
457
458 <p> In addition to the man pages for commands, there are man pages for
459 system calls, library functions, configuration files and more. Each
460 man page belongs to one of several <em>man sections</em>. For example,
461 the aforementioned man pages for <code>ls</code> and <code>man</code>
462 are part of section 1 (user commands) while section 2 is reserved for
463 system calls and section 8 for administration commands that can only be
464 executed by privileged users. By convention, to indicate which section
465 a command or a function belongs to, the man section is appended in
466 parenthesis as in <code>mount(8)</code>. Most Unix systems also offer
467 translated man pages for many languages as an optional package. Note
468 that the same name may refer to more than one man page. For example
469 there is <code>kill(1)</code> for the user command that kills processes
470 and also <code>kill(2)</code> which describes the corresponding system
471 call. To open the man page of a specific section, one may use a command
472 like <code>man 2 kill</code>. The <code>MANSECT</code> environment
473 variable can be set to a colon-delimited list of man sections to
474 change the order in which the man sections are searched. </p>
475
476 <p> Consulting the local man pages rather than searching the web has
477 some advantages. Most importantly, the local pages will always give
478 correct answers since they always match the installed software while
479 there is no such relationship between a particular web documentation
480 page and the version of the software package that is installed on the
481 local computer. Working with man pages is also faster, works offline
482 and helps the user to stay focused on the topic at hand. </p>
483
484 EXERCISES()
485
486 <ul>
487 <li> Run <code>df</code> on as many systems as possible to see the
488 mount points of each filesystem. Then discuss the pros and cons of
489 a single file hierarchy as opposed to one hierarchy per device. </li>
490
491 <li> Run <code>ls /</code> to list all top-level subdirectories of
492 the root file system and discuss the purpose of each. Consult the
493 Filesystem Hierarchy Standard if in doubt. </li>
494
495 <li> Execute <code>cd / && mc</code> and start surfing at the root
496 directory. </li>
497
498 <li> Compare the list of top-level directories that exist on different
499 Unix systems, for example Linux and MacOS. </li>
500
501 <li> Find out which type of files are supposed to be stored in
502 <code>/usr/local/bin</code>. Run <code>ls /usr/local/bin</code>
503 to list this directory. </li>
504
505 <li> Find out what the term <em>bashism</em> means and learn how to
506 avoid bashishms. </li>
507
508 <li> Find the POSIX specification of the <code>cp(1)</code> command
509 online and compare the set of options with the options supported by
510 the GNU version of that command, as obtained with <code>man cp</code>
511 on a Linux system. </li>
512
513 <li>&nbsp;
514 <ul>
515 <li> Run <code>time ls /</code> and discuss the meaning of
516 the three time values shown at the end of the output (see
517 <code>bash(1)</code>). </li>
518
519 <li> Guess the user/real and the sys/real ratios for the following
520 commands. Answer, before you run the commands.
521
522 <ul>
523 <li> <code>time head -c 100000000 /dev/urandom > /dev/null</code> </li>
524
525 <li> <code>i=0; time while ((i++ &lt; 1000000)); do :; done</code>
526 </li>
527 </ul>
528 </li>
529
530 <li> Run the above two commands again, this time run
531 <code>htop(1)</code> in parallel on another terminal and observe the
532 difference. </li>
533 </ul>
534 </li>
535
536 <li> On a Linux system, check the list of all system calls in
537 <code>syscalls(8)</code>. </li>
538
539 <li> The <code>strace(1)</code> command prints the system calls that
540 the given command performs. Guess how many system calls the command
541 <code>ls -l</code> will make. Run <code>strace -c ls -l</code> for
542 the answer. Read the <code>strace(1)</code> man page to find suitable
543 command line options to only see the system calls which try to open
544 a file. </li>
545
546 <li> Guess how many man pages a given system has. Run <code>whatis -w
547 '*' | wc -l</code> to see how close your guess was. </li>
548
549 <li> Search the web for "cp(1) manual page" and count how many
550 <em>different</em> manual pages are shown in the first 20 hits. </li>
551 </ul>
552
553 HOMEWORK(«
554
555 Think about printers, sound cards, or displays as a file. Specifically,
556 describe what <code>open, read</code>, and <code>write</code> should
557 mean for these devices.
558
559 », «
560
561 Opening would establish a (probably exclusive) connection
562 to the device. Reading from the file descriptor returned by
563 <code>open(2)</code> could return all kinds of status information,
564 like the type, model and capabilities of the device. For example,
565 printers could return the number of paper trays, the amount of toner
566 left etc. Writing to the file descriptor would cause output on the
567 device. This would mean to print the text that is written, play the
568 audio samples, or show the given text on the display. The point to
569 take away is that the <code>open, read, write</code> interface is a
570 generic concept that works for different kinds of devices, not only
571 for storing data in a file on a hard disk.
572
573 »)
574
575 SECTION(«Paths, Files and Directories»)
576
577 In this section we look in some detail at paths, at a matching
578 language for paths, and at the connection between paths and files. We
579 then describe the seven Unix file types and how file metadata are
580 stored. We conclude with the characteristics of soft and hard links.
581
582 SUBSECTION(«Paths»)
583
584 <p> The path concept was introduced in the 1960s with the Multics
585 operating system. Paths will be familiar to the reader because
586 they are often specified as arguments to commands. Also many
587 system calls receive a path argument. A path is a non-empty
588 string of <em>path components</em> which are separated by slash
589 characters. An <em>absolute path</em> is a path that starts with a
590 slash, all other paths are called <em>relative</em>. A relative path
591 has to be interpreted within a context that implies the leading
592 part of the path. For example, if the implied leading part is
593 <code>/foo/bar</code>, the relative path <code>baz/qux</code> is
594 equivalent to the absolute path <code>/foo/bar/baz/qux</code>. </p>
595
596 <p> Given a path, there may or may not exist a file or a
597 directory that corresponds to the path. <em>Path lookup</em> is the
598 operation which determines the answer to this question, taking the
599 implied leading part into account in case of relative paths. This
600 operation is always performed within the kernel and turns out to
601 be surprisingly complex due to concurrency and performance issues.
602 Consult <code>path_resolution(7)</code> on a Linux system to learn
603 more about how pathnames are resolved to files. </p>
604
605 <p> If a path was successfully looked up, each path component up to the
606 second-last refers to an existing directory while the last component
607 refers to either a file or a directory. In both cases the directory
608 identified by the second-last component contains an entry named by the
609 last component. We call those paths <em>valid</em>. The valid paths
610 give rise to a rooted tree whose interior nodes are directories and
611 whose leaf nodes are files or directories. Note that the validity of a
612 path depends on the set of existing files, not just on the path itself,
613 and that a valid path may become invalid at any time, for example if
614 a file is deleted or renamed. Many system calls which receive a path
615 argument perform path lookup and fail with the <code>No such file or
616 directory</code> error if the lookup operation fails. </p>
617
618 <p> It depends on the underlying filesystem whether the path components
619 are <em>case-sensitive</em> or <em>case-insensitive</em>. That is,
620 whether paths which differ only in capitalization (for example
621 <code>foo</code> and <code>Foo</code>) refer to the same file.
622 Since the hierarchy of files may be comprised of several filesystems,
623 some components of the path may be case-sensitive while others are
624 case-insensitive. As a rule of thumb, Unix filesystems are case
625 sensitive while Microsoft filesystems are case-insensitive even when
626 mounted on a Unix system. </p>
627
628 <p> Path components may contain every character except the Null
629 character and the slash. In particular, space and newline characters
630 are allowed. However, while dots are allowed in path components if
631 they are used together with other characters, the path components
632 <code>.</code> and <code>..</code> have a special meaning: every
633 directory contains two subdirectories named <code>.</code> and
634 <code>..</code> which refer to the directory itself and its parent
635 directory, respectively. </p>
636
637 SUBSECTION(«Globbing»)
638
639 <p> Globbing, also known as <em>pathname expansion</em>, is a pattern
640 matching language for paths which was already present in the earliest
641 Unix versions. The glob operation generates a set of valid paths from
642 a <em>glob pattern</em> by replacing the pattern by all <em>matching
643 paths</em>. </p>
644
645 <p> Glob patterns may contain special characters called
646 <em>wildcards</em>. The wildcard characters are: </p>
647
648 <ul>
649 <li> <code>*</code>: match any string, </li>
650 <li> <code>?</code>: match any simple character, </li>
651 <li> <code>[...]</code>: match any of the enclosed characters. </li>
652 </ul>
653
654 <p> The complete syntax rules for glob patterns and the exact
655 semantics for pattern matching are described in POSIX and in
656 <code>glob(7)</code>. Any POSIX-compliant shell performs globbing
657 to construct the command to be executed from the line entered at
658 the prompt. However, POSIX also demands system functions which make
659 globbing available to other applications. These are implemented as
660 part of libc. </p>
661
662
663 <p> There are a few quirks related to globbing which are worth to
664 point out. First, if no valid path matches the given pattern, the
665 expansion of the pattern is, by definition according to POSIX, the
666 pattern itself. This can lead to unexpected results. Second, files
667 which start with a dot (so-called <em>hidden</em> files) must be
668 matched explicitly. For example, <code>rm *</code> does <em>not</em>
669 remove these files. Third, the tilde character is <em>no</em> wildcard,
670 although it is also expanded by the shell. See the exercises for more
671 examples. </p>
672
673 <p> POSIX globbing has some limitations. For example, there is no
674 glob pattern which matches exactly those files that start with an
675 arbitrary number of <code>a</code> characters. To overcome these
676 limitations, some shells extend the matching language by implementing
677 <em>extended glob patterns</em> which are not covered by POSIX. For
678 example, if extended globbing feature of <code>bash(1)</code> is
679 activated via the <code>extglob</code> option, the extended glob
680 pattern <code>+(a)</code> matches the above set of files. </p>
681
682 SUBSECTION(«File Types»)
683
684 We have seen that all but the last component of a valid path refer
685 to directories while the last component may refer to either a file
686 or a directory. The first character in the output of <code>ls
687 -l</code> indicates the type of the last path component: for
688 directories a <code>d</code> character is shown while files (also
689 called <em>regular</em> files in this context) get a hyphen character
690 (<code>-</code>). Besides directories and regular files, the following
691 special file types exist:
692
693 <dl>
694 <dt> Soft link (<code>l</code>) </dt>
695
696 <dd> A file which acts as a pointer to another file. We shall cover
697 links in a dedicated subsection below. </dd>
698
699 <dt> Device node (<code>c</code> and <code>b</code>) </dt>
700
701 <dd> Also called <em>device special</em>. These files refer to devices
702 on the local system. Device nodes come in two flavors: character
703 devices (<code>c</code>) and block devices (<code>b</code>). Regardless
704 of the flavor, each device node has a major and a minor number
705 associated with it. The major number indicates the type of the
706 device (e.g. a hard drive, a serial connector, etc.) while the
707 minor number enumerates devices of the same type. On most systems
708 the device nodes are created and deleted on the fly as the set of
709 connected devices changes, for example due to a USB device being
710 added or removed. However, device nodes can also be created manually
711 with the <code>mknod(1)</code> command or the <code>mknod(2)</code>
712 system call. Device nodes do not necessarily correspond to physical
713 devices. In fact, POSIX demands the existence of a couple of
714 <em>virtual devices</em> with certain properties. We look at some of
715 these in the exercises. The access to device nodes which do correspond
716 to physical devices is usually restricted to privileged users. </dd>
717
718 <dt> Socket (<code>s</code>) </dt>
719
720 <dd> Sockets provide an interface between a running program and the
721 network stack of the kernel. They are subdivided into <em>address
722 families</em> which correspond to the various network protocols. For
723 example, the <code>AF_INET</code> and <code>AF_INET6</code> address
724 families are for internet protocols (IP) while <code>AF_LOCAL</code>
725 (also known as <code>AF_UNIX</code>) is used for communication between
726 processes on the same machine. These local sockets are also called
727 <em>Unix domain sockets</em>. They can be bound to a path which
728 refers to a file of type socket. Regardless of the address family,
729 processes can exchange data via sockets in both directions, but
730 the local sockets support additional features, like passing process
731 credentials to other processes. </dd>
732
733 <dt> Fifo (<code>p</code>) </dt>
734
735 <dd> Files of type <em>fifo</em> are also known as <em>named
736 pipes</em>. They associate a path with a kernel object that provides a
737 <em>First In, First Out</em> data channel for user space programs. Data
738 written to the fifo by one program can be read back by another program
739 in the same order. Fifos are created with the <code>mkfifo(1)</code>
740 command or the <code>mkfifo(3)</code> library function. </dd>
741 </dl>
742
743 <p> Note that the type of a file is never inferred from the path.
744 In particular the suffix of the path (everything after the last
745 dot) is just a convention and has no strict connection to the file
746 type. Also there is no difference between text and binary files. </p>
747
748 SUBSECTION(«Metadata and Inodes»)
749
750 <p> The <code>stat(2)</code> system call returns the metadata
751 of the file or directory that corresponds to the given path. The
752 <code>stat(1)</code> command is a simple program which executes this
753 system call and prints the thusly obtained metadata in human-readable
754 form, including the file type. This is done without looking at the
755 contents of the file because metadata are stored in a special area
756 called the <em>inode</em>. All types of files (including directories)
757 have an associated inode. Besides the file type, the inode stores
758 several other properties prescribed by POSIX. For example the file
759 size, the owner and group IDs, and the access permissions are all
760 stored in the inode. Moreover, POSIX requires to maintain three
761 timestamps in each inode: </p>
762
763 <ul>
764 <li> modification time (mtime): time of last content change. </li>
765
766 <li> access time (atime): time of last access. </li>
767
768 <li> status change time (ctime): time of last modification to the
769 inode. </li>
770 </ul>
771
772 <p> To illustrate the difference between the mtime and the ctime,
773 consider the <code>chgrp(1)</code> command which changes the group
774 ID of the file or directory identified by its path argument. This
775 command sets the ctime to the current time while the mtime is left
776 unmodified. On the other hand, commands which modify the contents of
777 a file, such as <code>echo foo >> bar</code>, change both the mtime
778 and the ctime. </p>
779
780 <p> The inode of each file or directory contains twelve <em>mode
781 bits</em>, nine of which are the <em>permission bits</em> which
782 control who is allowed to access the file or directory, and how. The
783 permission bits are broken up into three classes called <em>user</em>
784 (<code>u</code>), <em>group</em> (<code>g</code>) and <em>others</em>
785 (<code>o</code>). Some texts refer to the first and last class as
786 "owner" and "world" instead, but we won't use this naming to avoid
787 confusion. Each class contains three bits. The bits of the "user"
788 class apply to the file owner, that is, the user whose ID is stored in
789 the inode. The "group" category applies to all non-owners who belong
790 to the group whose ID is stored in the inode. The third category
791 applies to all remaining users. The three bits of each class refer to
792 read/write/execute permission. They are therefore named <code>r</code>,
793 <code>w</code> and <code>x</code>, respectively. The permission
794 bits mean different things for directories and non-directories,
795 as described below. </p>
796
797 <table>
798 <tr>
799 <td> </td>
800 <td> <em>Directories</em> </td>
801 <td> <em>Non-directories</em> </td>
802 </tr> <tr>
803 <td> <code>&nbsp;r&nbsp;</code> </td>
804
805 <td> The permission to list the directory contents. More precisely,
806 this bit grants the permission to call <code>opendir(3)</code>
807 to obtain a handle to the directory which can then be passed to
808 <code>readdir(3)</code> to obtain the directory contents. </td>
809
810 <td> If read permission is granted, the <code>open(2)</code> system
811 call does not fail with the <code>permission denied</code> error,
812 provided the file is opened in read-only mode. The system call may
813 fail for other reasons, though.
814
815 </tr> <tr>
816 <td> <code>&nbsp;w&nbsp;</code> </td>
817
818 <td> The permission to add or remove directory entries. That is,
819 to create new files or to remove existing files. Note that write
820 permission is not required for the file that is being removed. </td>
821
822 <td> Permission to open the file in write-only mode in order
823 to perform subsequent operations like <code>write(2)</code>
824 and <code>truncate(2)</code> which change the contents of the
825 file. Non-directories are often opened with the intention to both
826 read and write. Naturally, such opens require both read and write
827 permissions. </td>
828
829 </tr> <tr>
830 <td> <code>&nbsp;x&nbsp;</code> </td>
831
832 <td> The permission to <em>search</em> the directory. Searching
833 a directory means to access its entries, either by retrieving
834 inode information with <code>stat(2)</code> or by calling
835 <code>open(2)</code> on a directory entry. </td>
836
837 <td> Run the file. This applies to <em>binary executables</em> as well
838 as to text files which start with a <em>shebang</em>, <code>#!</code>,
839 followed by the path to an interpreter. We shall cover file execution
840 in more detail below. </td>
841
842 </tr>
843 </table>
844
845 <p> To run the regular file <code>/foo/bar/baz</code>, search
846 permission is needed for both <code>foo</code> and <code>bar</code>,
847 and execute permission is needed for <code>baz</code>. Similarly, to
848 open the regular file <code>foo/bar</code> for reading, we need execute
849 permissions on the current working directory and on <code>foo</code>,
850 and read permissions on <code>bar</code>. </p>
851
852 <p> A <em>numeric permission mode</em> is a three octal digit (0-7)
853 number, where the digits correspond to the user, group, other classes
854 described above, in that order. The value of each digit is derived by
855 adding up the bits with values 4 (read), 2 (write), and 1 (execute).
856 The following table lists all eight possibilities for each of the
857 three digits. </p>
858
859 <table>
860 <tr>
861 <td> octal value </td>
862 <td> symbolic representation </td>
863 <td> meaning </td>
864 </tr> <tr>
865 <td> 0 </td>
866 <td> <code>---</code> </td>
867 <td> no permissions at all </td>
868 </tr> <tr>
869 <td> 1 </td>
870 <td> <code>--x</code> </td>
871 <td> only execute permission </td>
872 </tr> <tr>
873 <td> 2 </td>
874 <td> <code>-w-</code> </td>
875 <td> only write permission </td>
876 </tr> <tr>
877 <td> 3 </td>
878 <td> <code>-wx</code> </td>
879 <td> write and execute permission </td>
880 </tr> <tr>
881 <td> 4 </td>
882 <td> <code>r--</code> </td>
883 <td> only read permission </td>
884 </tr> <tr>
885 <td> 5 </td>
886 <td> <code>r-x</code> </td>
887 <td> read and execute permission </td>
888 </tr> <tr>
889 <td> 6 </td>
890 <td> <code>rw-</code> </td>
891 <td> read and write permission </td>
892 </tr> <tr>
893 <td> 7 </td>
894 <td> <code>rwx</code> </td>
895 <td> read, write and execute permission </td>
896 </tr>
897 </table>
898
899 <p> The <code>chmod(1)</code> command changes the permission
900 bits of the file identified by the path argument. For example,
901 <code>chmod 600 foo</code> sets the permissions of <code>foo</code> to
902 <code>rw-------</code>. Besides the octal values, <code>chmod(1)</code>
903 supports symbolic notation to address the three classes described
904 above: <code>u</code> selects the user class, <code>g</code> the
905 group class, <code>o</code> the class of other users. The symbolic
906 value <code>a</code> selects all three classes. Moreover, the letters
907 <code>r</code>, <code>w</code> and <code>x</code> are used to set or
908 unset the read, write and execute permission, respectively. The above
909 command is equivalent to <code>chmod u=rw,g=---,o=--- foo</code>. The
910 <code>+</code> and <code>-</code> characters can be specified instead
911 of <code>=</code> to set or unset specific permission bits while
912 leaving the remaining bits unchanged. For example <code>chmod go-rw
913 foo</code> turns off read and write permissions for non-owners. </p>
914
915 <p> Unprivileged users can only change the mode bits of their own
916 files or directories while there is no such restriction for the
917 superuser. </p>
918
919 SUBSECTION(«Hard and Soft Links»)
920
921 <p> Links make it possible to refer to identical files through
922 different paths. They come in two flavors: hard and soft. Both
923 types of links have advantages and disadvantages, and different
924 limitations. We start with hard links because these existed already
925 in the earliest Unix versions. </p>
926
927 <p> A file can have more than one directory entry that points to its
928 inode. If two directory entries point to the same inode, they are
929 said to be <em> hard links</em> of each other. The two entries are
930 equivalent in that they refer to the same file. It is impossible
931 to tell which of the two is the "origin" from which the "link"
932 was created. Hard links are created with the <code>link(2)</code>
933 system call or the <code>ln(1)</code> command. Both take two path
934 arguments, one for the existing file and one for the directory entry
935 to be created. The filesystem maintains in each inode a link counter
936 which keeps track of the number of directory entries which point to the
937 inode. The <code>link(2)</code> system call increases the link count
938 while <code>unlink(2)</code> decrements the link count and removes
939 the directory entry. If the decremented counter remains positive,
940 there is still at least one other directory entry which points to
941 the inode. Hence the file is still accessible through this other
942 directory entry and the file contents must not be released. Otherwise,
943 when the link counter reached zero, the inode and the file contents
944 may be deleted (assuming the file is not in use). </p>
945
946 <p> There are several issues with hard links. For one, hard links
947 can not span filesystems. That is, the two path arguments for
948 <code>link(2)</code> have to refer to files which reside on the
949 same filesystem. Second, it is problematic to create hard links to
950 directories. Early Unix systems allowed this for the superuser,
951 but on Linux the attempt to hard-link a directory always fails.
952 To address the limitations of hard links, <em>soft links</em>, also
953 called <em>symbolic links</em> (or <em>symlinks</em> for short),
954 were introduced. A soft link can be imagined as a special text file
955 containing a single absolute or relative path, the <em>target</em> of
956 the link. For relative paths the implied leading part is the directory
957 that contains the link. A soft link is thus a named reference in
958 the global hierarchy of files. Unlike hard links, the soft link
959 and its target do not need to reside on the same filesystem, and
960 there is a clear distinction between the link and its target. Soft
961 links are created with <code>symlink(2)</code> or by specifying the
962 <code>-s</code> option to the <code>ln(1)</code> command. </p>
963
964 <p> A soft link and its target usually point to different inodes. This
965 raises the following question: Should system calls which receive a
966 path argument that happens to be a soft link operate on the link
967 itself, or should they <em>follow</em> (or <em>dereference</em>)
968 the link and perform the operation on the target? Most system calls
969 follow soft links, but some don't. For example, if the path argument
970 to <code>chdir(2)</code> happens to be a soft link, the link is
971 dereferenced and the working directory is changed to the target of
972 the link instead. The <code>rename(2)</code> system call, however,
973 does not follow soft links and renames the link rather than its
974 target. Other system calls, including <code>open(2)</code>, allow
975 the caller to specify the desired behaviour by passing a flag to the
976 system call. For yet others there is a second version of the system
977 call to control the behaviour. For example, <code>lstat(2)</code> is
978 identical to <code>stat(2)</code>, but does not follow soft links. </p>
979
980 <p> It is possible for a soft link to refer to an invalid path. In
981 fact, <code>ln(1)</code> and <code>symlink(2)</code> do not consider
982 it an error if the target does not exist, and happily create a soft
983 link which points to an invalid path. Such soft links are called
984 <em>dangling</em> or <em>broken</em>. Dangling soft links also occur
985 when the target file is removed or renamed, or after a mount point
986 change. </p>
987
988 <p> Soft links may refer to other soft links. System calls which
989 follow soft links must therefore be prepared to resolve chains of
990 soft links to determine the file to operate on. However, this is not
991 always possible because soft links can easily introduce loops into the
992 hierarchy of files. For example, the commands <code>ln -s foo bar;
993 ln -s bar foo</code> create such a loop. System calls detect this
994 and fail with the <code>Too many levels of symbolic links</code>
995 error when they encounter a loop. </p>
996
997 <p> Another issue with both soft and hard links is that there is no
998 simple way to find all directory entries which point to the same path
999 (soft links) or inode (hard links). The only way to achieve this is
1000 to traverse the whole hierarchy of files. This may be prohibitive
1001 for large filesystems, and the result is unreliable anyway unless
1002 the filesystems are mounted read-only. </p>
1003
1004 EXERCISES()
1005
1006 <ul>
1007 <li> A path can lack both slashes and components. Give an example
1008 of a path that lacks a slash and another example of a path that has
1009 no components. </li>
1010
1011 <li> Assume <code>foo</code> is an existing directory. Guess what the
1012 command <code>mv foo bar</code> will do in each of the following cases:
1013 (a) <code>bar</code> does not exist, (b) <code>bar</code> exists and
1014 is a regular file, (c) <code>bar</code> exists and is a directory.
1015 Verify your guess by running the command. </li>
1016
1017 <li> Many programs check if a path is valid and act differently
1018 according to the result. For example, a shell script might
1019 check for the existence of a file with code like <code>if test
1020 -e "$file"; do something_with "$file"; fi</code>. Explain
1021 why this approach is not bullet-proof. How could this be
1022 fixed? </li>
1023
1024 <li> Run <code>touch file-{1..100}</code> to create 100 files. Guess
1025 what the following commands will print. Run each command to confirm.
1026
1027 <ul>
1028 <li> <code>ls file-</code> </li>
1029 <li> <code>ls file-*</code> </li>
1030 <li> <code>ls file-?</code> </li>
1031 <li> <code>ls file-[1-4]</code> </li>
1032 <li> <code>ls file-[1,3,5,7,9]*</code> </li>
1033 </ul>
1034 </li>
1035
1036 <li> Find an extended glob pattern for <code>bash(1)</code>
1037 that matches all valid paths whose last component starts with
1038 <code>file-</code>, followed by any number of odd digits (1, 3, 5,
1039 7, or 9). </li>
1040
1041 <li> Point out the flaw in the following shell code: <code>for
1042 f in file-*; do something_with "$f"; done</code>. Hint: Search
1043 <code>bash(1)</code> for "nullglob".
1044
1045 <li> Create a file named <code>-r</code> with <code>echo >
1046 -r</code>. Try to remove the file with <code>rm -r</code> and
1047 discuss why this doesn't work as expected. Find a way to get rid
1048 of the file. Discuss what happens if you run <code>rm *</code> in a
1049 directory which contains a file named <code>-r</code>. </li>
1050
1051 <li> The content of the <code>PATH</code> variable is a
1052 colon-separated list of directories in which the shell looks for
1053 commands to execute. Discuss the dangers of including the current
1054 working directory in this list. </li>
1055
1056 <li> Run <code>id</code> to determine a group <code>G</code> you
1057 belong to but is not your primary group. Consider the following
1058 commands <code>mkdir foo; chgrp $G foo; touch foo/bar</code>. What
1059 is the group ID of <code>foo/bar</code>? Run the same commands, but
1060 insert <code>chmod g+s foo</code> as the second-to-last command. </li>
1061
1062 <li> Run <code>man null</code> and <code>man zero</code> to learn
1063 about the properties of these two character devices. </li>
1064
1065 <li> Assume the modification time stored in the inode of some file
1066 suggests that the file was last modified two years ago. How sure
1067 can you be that the file was never changed since then? Hint: See the
1068 <code>-d</code> option of <code>touch(1)</code>. </li>
1069
1070 <li> Run the following commands <code>echo hello > foo</code>,
1071 <code>cat foo</code>, <code>chmod 600 foo</code>, <code>echo world >>
1072 foo</code>. Check the three timestamps with <code>stat foo</code>
1073 after each command. </li>
1074
1075 <li> Determine the state of the permission bits of your own
1076 home directory by running <code>ls -ld ~</code>. Who can
1077 access its contents? Also look at the permission bits of
1078 other people's home directory. </li>
1079
1080 <li> A file or directory is called <em>world-writeable</em>
1081 if the <code>w</code> bit is set in the <code>others</code>
1082 class of the permission bits. Create a world-writable
1083 directory with <code>mkdir foo; chmod 777 foo</code>
1084 and create a file in the new directory: <code>echo hello
1085 > foo/bar</code>. Is a different user allowed to create
1086 another file there (<code>echo world > foo/baz</code>)? Can
1087 he remove it again (<code>rm foo/baz</code>)? Will he succeed
1088 in removing <code>foo/bar</code> although it is owned by you
1089 and <em>not</em> writable to him? Try the same with the sticky
1090 bit turned on (<code>chmod 1777 foo</code>). </li>
1091
1092 <li> Translate <code>rw-r--r--</code> into octal, and 755 into
1093 <code>rwx</code>-notation. </li>
1094
1095 <li> Create a <a href="#hello_world">hello world script</a>, make it
1096 executable and run it. Create a subdirectory of your home directory
1097 and move the script into this directory. Set the permissions of the
1098 directory to <code>r--------</code>, check whether you still can
1099 list/execute it. Do the same with <code>--x------</code>. </li>
1100
1101 <li> Create a file with <code>echo hello > foo</code>,
1102 create soft and hard links with <code>ln -s foo soft</code>
1103 and <code>ln foo hard</code>. Examine the inode numbers
1104 and link counts using the command <code>stat foo soft
1105 hard</code>. Remove <code>foo</code> and repeat. Try to
1106 access the file content through both links. Guess what
1107 <code>realpath foo soft hard</code> will print. Run the
1108 command to confirm. </li>
1109
1110 <li> Create a dangling symlink with <code>ln -s /nope foo</code>. Would
1111 you expect the commands <code>ls -l foo</code> and <code>cat foo</code>
1112 succeed? Run these commands to verify your guess. </li>
1113
1114 <li> One of the seven Unix file types is symlink. Why is there no
1115 file type for hard links? </li>
1116 </ul>
1117
1118 HOMEWORK(«
1119 How many paths are there that refer to the same file?
1120 », «
1121 Given the path <code>/foo/bar</code>, one may construct different paths
1122 which refer to the same file by inserting any number of <code>/.</code>
1123 or <code>../foo</code> after the first component. For example,
1124 <code>/foo/./bar</code> and <code>/foo/../foo/bar</code> both refer
1125 to the same file. If relative paths have to be taken into account as
1126 well, even more paths can be constructed easily. Hence the answer is:
1127 arbitrary many.
1128
1129 This illustrates the fundamental difference between a path and a
1130 file. Paths can be mapped to files, but not the other way around. In
1131 particular, there is no such thing like "the list of paths which have
1132 changed since yesterday".
1133
1134 The concept of hard- and soft links complicates
1135 the situation further. This topic is discussed in a <a
1136 href="#soft_and_hard_links">subsequent section</a>. See the exercises
1137 therein for more information.
1138
1139 »)
1140
1141 HOMEWORK(«
1142 Given two paths, how can one tell if they refer to the same file?
1143 », «
1144
1145 Among other information, the metadata record of each file contains the
1146 so-called <em>inode number</em>, which uniquely identifies the file
1147 within the file system that contains the file. Therefore, if both
1148 paths are known to refer to files stored on the same file system,
1149 a comparison of the two inode numbers is sufficient to tell whether
1150 the two paths refer to the same file. The inode number can be obtained
1151 with the command <code>ls -i</code>.
1152
1153 In the general case one additionally has to check that the
1154 two <code>device IDs</code> which identify the underlying file
1155 systems are also identical. Like the inode number, the device ID
1156 is part of the metadata of the file. It can be obtained by running
1157 <code>stat(1)</code>.
1158
1159 »)
1160
1161 HOMEWORK(«
1162 Device nodes come in two flavors: Character and block devices. Explain
1163 the difference between the two device flavors.
1164 »)
1165
1166 HOMEWORK(«
1167
1168 <ul>
1169 <li> Nine of the 12 mode bits of each file are the permission
1170 bits. The remaining three are the <em>sticky</em>, <em>setuid</em>
1171 and <em>setgid</em> bits. Explain the purpose of each. </li>
1172
1173 <li> Run <code>find /usr/bin/ -perm -2000 -ls</code> to see all SUID
1174 executables in <code>/usr/bin</code>. Discuss why those programs have
1175 the SUID bit set. </li>
1176 </ul>
1177
1178 »)
1179
1180 HOMEWORK(«
1181 How many possible permission modes exist for a file or directory on
1182 a Unix System?
1183 », «
1184 There are nine permission bits that can be turned on and off
1185 independently. Hence we have 2^9=512 possibilities. When taking into
1186 account the three special bits (sticky, setuid, setgid), the number
1187 increases to 2^12=4096.
1188 »)
1189
1190 HOMEWORK(«
1191 Explain each command of the <a href="«#»symlink_madness">script</a>
1192 below. Show the arrangement of all files and links in a figure,
1193 drawing a directory as a circle and a file as a square. How many
1194 different paths exist for the file <code> a</code>? Discuss whether
1195 the question "What's the path of a given file?" makes sense.
1196
1197 », «
1198
1199 <div>
1200 <svg
1201 width="150" height="125"
1202 xmlns="http://www.w3.org/2000/svg"
1203 xmlns:xlink="http://www.w3.org/1999/xlink"
1204 >
1205 <marker
1206 id="slm_arrow"
1207 viewBox="0 0 10 10" refX="5" refY="5"
1208 markerWidth="4" markerHeight="4"
1209 orient="auto-start-reverse">
1210 <path d="M 0 0 L 10 5 L 0 10 z" />
1211 </marker>
1212 <circle
1213 fill="#ccc"
1214 stroke-width="1"
1215 stroke="black"
1216 r=20
1217 cx=51
1218 cy=21
1219 />
1220 <text
1221 x="51"
1222 y="21"
1223 stroke="black"
1224 text-anchor="middle"
1225 dy="0.3em"
1226 >foo</text>
1227 <rect
1228 fill="#ccc"
1229 stroke-width="1"
1230 stroke="black"
1231 x=1
1232 y=81
1233 width="40"
1234 height="40"
1235 rx="5"
1236 />
1237 <text
1238 x="21"
1239 y="101"
1240 stroke="black"
1241 text-anchor="middle"
1242 dy="0.3em"
1243 >a</text>
1244 <ellipse
1245 cx=81
1246 cy=101
1247 rx=30
1248 ry=20
1249 fill="#ccc"
1250 stroke-width="1"
1251 stroke="black"
1252 />
1253 <text
1254 x="81"
1255 y="101"
1256 stroke="black"
1257 text-anchor="middle"
1258 dy="0.3em"
1259 >testdir</text>
1260 <line
1261 stroke="black"
1262 stroke-width="1"
1263 x1="41"
1264 y1="45"
1265 x2="24"
1266 y2="75"
1267 />
1268 <line
1269 stroke="black"
1270 stroke-width="1"
1271 x1="61"
1272 y1="45"
1273 x2="77"
1274 y2="75"
1275 />
1276 <path
1277 d="
1278 M 118,101
1279 C 150,90 150,30 80,20
1280 "
1281 stroke-width="2"
1282 stroke="black"
1283 fill="none"
1284 marker-end="url(#slm_arrow)"
1285 />
1286 </svg>
1287 </div>
1288
1289 Since <code> foo/a</code>, <code> foo/testdir/a</code>, <code>
1290 foo/testdir/testdir/a </code> etc. all refer to the same file, there
1291 are infinitely many paths for the file <code> a</code>. Hence the
1292 question makes no sense: There is no such thing as <em> the </em>
1293 path to a file.
1294
1295 »)
1296
1297 HOMEWORK(«
1298
1299 Recall that the path component <code>..</code> refers to the
1300 parent directory. Give an example of a path to a directory where
1301 "parent directory" and "directory identified by the path obtained by
1302 removing the last path component" are different. Which of the two
1303 interpretations of <code>..</code> does bash apply when you type
1304 <code>cd ..</code> at the bash prompt?
1305
1306 »)
1307
1308 HOMEWORK(«
1309
1310 Is it possible to choose among all possible paths which refer to the
1311 same file a <em>canonical</em> path? That is, a shortest (counting
1312 characters) absolute path which does not contain any soft links?
1313
1314 », «
1315
1316 <p> The POSIX standard requires each Unix system library to provide
1317 the <code>realpath()</code> function which performs the following
1318 substitutions on the given path: First, the path to the current
1319 working directory is prepended if the given path is relative
1320 (does not begin with a slash). Second, symbolic links are replaced
1321 by their targets. Third, any occurrences of <code>/.</code> and
1322 <code>foo/..</code> are removed. The thusly transformed path is
1323 returned by the function as the canonical path. </p>
1324
1325 <p> Although each path can be canonicalized in this way, not all paths
1326 which refer to the same file give rise to the same canonical path. For
1327 example, <code>/tmp/foo</code> and <code>/tmp/bar</code> could refer
1328 to regular files which are hard links of each other. In this case the
1329 paths refer to the same file, yet the paths are different and already
1330 canonicalized. The same can happen when a file system (or a subtree
1331 of it) is <em>bind mounted</em>. That is, the file system tree is
1332 visible at two or more locations in the global directory tree. </p>
1333
1334 The message of this exercise is to convince the reader that it is
1335 incorrect to assume that two files are different because their paths
1336 are different.
1337
1338 »)
1339
1340 SECTION(«Processes»)
1341
1342 <p> A <em>program</em> consists of instructions and data stored in
1343 a regular file. A <em> user process</em> is an instance of a running
1344 program. This is in contrast to <em>kernel processes</em> which are
1345 created directly by the kernel and have no relationship to executable
1346 files. Since we shall only be concerned with user processes, we will
1347 refer to these as "processes" from now on. In this section we'll see
1348 how processes are created and removed. We will then take a closer look
1349 at the enviroment of a process and discuss how processes communicate
1350 with each other. </p>
1351
1352 SUBSECTION(«Process Tree, Zombies and Orphans»)
1353
1354 <p> When the system boots, there is only one process, the
1355 <em>init</em> process, which is created by the kernel at the end
1356 of the boot sequence by executing <code>/sbin/init</code>. All
1357 other processess are created from existing processes by means of
1358 the <code>fork(2)</code> system call. The process which called
1359 <code>fork(2)</code> is said to be the <em>parent</em> of the newly
1360 created <em>child</em>. After <code>fork(2)</code> returns, both
1361 parent and child are executing independently of each other. Both
1362 processes may call <code>fork(2)</code> again to create further
1363 processes. This gives rise to a tree structure where the processes
1364 are the nodes of the tree with init being the root node. The edges
1365 of the tree describe the parent-child relationships. </p>
1366
1367 <p> If there are more processes than CPUs, not all processes can
1368 run simultaneously. It is the mission of the kernel's <em>task
1369 scheduler</em> to assign processes to CPUs and to perform <em>context
1370 switches</em>. That is, to take away the CPU from a running process
1371 in order to give another process the chance to run. The scheduler
1372 has to choose the duration of each process' time slice and it must
1373 pick the process to switch to when the time slice of the current
1374 process has expired or the process gives up the CPU voluntarily, for
1375 example because it is waiting for an I/O operation to complete. This
1376 is a non-trivial task at least for modern multi-CPU systems with
1377 <em>non-uniform memory access</em> (NUMA) where the memory access times
1378 depend on the memory location and the processor core. Things don't
1379 get easier if the CPU clock speed can vary and/or scheduling must be
1380 power-aware to optimize battery time. To make good decisions, some
1381 information has to be provided by the processes or by a system-wide
1382 policy. One elementary way to prioritize certain processes over others
1383 is via <em>nice levels</em> which we shall discuss below. </p>
1384
1385 <p> The normal way for a process to terminate is to call
1386 <code>exit(3)</code> after it has done its work. This function
1387 transfers an integer value, the <em>exit status</em>, to the
1388 kernel. The exit status can only be retrieved by the parent of
1389 the terminating process. To illustrate this concept, imagine an
1390 interactive shell which creates one child each time the user enters
1391 a command. The children are short living while the parent, the shell,
1392 stays around for much longer. During command execution the parent needs
1393 to wait for its child to terminate. It may then want to tell whether
1394 the child has terminated successfully. To achieve this, the parent
1395 calls one of the <em>wait</em> system calls (<code>wait(2)</code>,
1396 <code>waitpid(2)</code>, <code>waitid(2)</code>) which block until the
1397 child has terminated, then return the child's exit status. After the
1398 child called <code>exit(3)</code> but before the parent has called
1399 one of the wait functions, the kernel needs to keep at least the
1400 exit status (and possibly further information) about the terminated
1401 child. During this time window the child has already terminated but
1402 a part of it still exists in kernel memory. Processes in this state
1403 are aptly called <em>zombies</em>. </p>
1404
1405 <p> Unlike in the shell scenario outlined above, a process might well
1406 have any number of children at the time it terminates. Its children
1407 then become <em>orphans</em> as they lose their parent. The kernel
1408 cannot simply remove the terminated process from the process tree
1409 because this would disconnect its orphaned children from the other
1410 processes in the tree, destroying the tree structure. To avoid this,
1411 orphans are <em>reparented to init</em>, that is, made children
1412 of the init process. This works because the init process never
1413 terminates. </p>
1414
1415 <p> There are several programs which show information about
1416 processes. The POSIX <code>ps(1)</code> command prints a list of
1417 processes. It has many options that control which processes are
1418 shown and how the output is formatted. Similar programs which are not
1419 covered by POSIX are <code>pstree(1)</code>, <code>top(1)</code> and
1420 <code>htop(1)</code>. The former shows the tree structure while the
1421 latter two provide a dynamic real-time view of the process tree. The
1422 exercises of this section invite the reader to become familiar with
1423 these essential programs. </p>
1424
1425 SUBSECTION(«File Execution»)
1426
1427 <p> When a process calls <code>fork(2)</code>, the newly created
1428 child process starts out as a copy of the calling process. However,
1429 the reason to create a new process is usually to let the child do
1430 something different than the parent. Therefore, <code>fork(2)</code>
1431 is often followed by a second system call which replaces the child
1432 process with a different program. There are several similar system
1433 calls which do this, with slight semantic differences. We refer to
1434 this family of system calls as the <em>exec system calls</em>. </p>
1435
1436 <p> All exec system calls receive a path argument from which they
1437 determine an executable file that contains the program to run. Linux
1438 and BSD store executables in <em>Executable and Linkable Format</em>
1439 (ELF). Executables are typically linked <em>dynamically</em>.
1440 That is, the dependent libraries (at least libc, but possibly many
1441 more) are loaded at runtime from separate files. This is in contrast
1442 to <em>static linking</em> which includes all dependencies in the
1443 executable, making the executable self-contained but also larger
1444 and harder to maintain. Regardless of the type of linking, when the
1445 program is loaded, it completely replaces the previously running
1446 program. Note that there can be more than one process at the same
1447 time which executes the same program. </p>
1448
1449 <p> Files in ELF format are called <em>native</em> executables because
1450 they contain machine instructions which can be executed directly
1451 by the CPU. Another type of executables are <em>scripts</em>,
1452 also known as <em>interpreter files</em>. Scripts are text files
1453 which start with the <em>shebang</em> (<code>#!</code>). They can
1454 not run directly but have to be <em>interpreted</em> at runtime
1455 by another program, the <em>interpreter</em>. Nevertheless, it is
1456 possible to execute a script as if it were a native executable:
1457 by passing the path to one of the exec system calls or by typing
1458 the path at the shell prompt. The exec system call recognizes that
1459 the given file is a script by investigating the first line, which
1460 contains the path to the interpreter after the shebang, optionally
1461 followed by options to the interpreter. The kernel then executes the
1462 interpreter rather than the script, passing the path to the script as
1463 an argument. For example, if <code>/foo/bar</code> is being executed,
1464 and the first line of this file is <code>#!/bin/sh</code>, the kernel
1465 executes <code>/bin/sh /foo/bar</code> instead. Popular interpreters
1466 besides <code>/bin/sh</code> include <code>/bin/bash</code>,
1467 <code>/usr/bin/perl</code>, <code>/usr/bin/python</code> and
1468 <code>/usr/bin/awk</code>. </p>
1469
1470 SUBSECTION(«File Descriptions and File Descriptors»)
1471
1472 <p> The kernel must always be aware of the set of all objects which are
1473 currently in use. This set is often called the <em>system-wide table
1474 of open files</em> although not all entries refer to files. In fact, an
1475 entry may refer to any object that supports I/O operations, for example
1476 a network socket. Each entry is called a <em>file description</em>,
1477 which is a somewhat unfortunate term that was coined by POSIX. A
1478 file description records information about the object itself as well
1479 as the current state of the reference, including the file offset,
1480 if applicable, and the <em>status flags</em> which affect how future
1481 I/O operations are going to be performed through this reference. </p>
1482
1483 <p> The kernel maintains for each process an array of pointers to file
1484 descriptions. Each such pointer is a <em>file descriptor</em>. Unlike
1485 files and file descriptions, a file descriptor always corresponds
1486 to a process and is identified by a non-negative number, the index
1487 into the pointer array of that process. This index is returned by
1488 system calls like <code>open(2)</code> or <code>socket(2)</code>.
1489 As far as user space programs are concerned, a file descriptor is
1490 synonymous with this integer. It can be regarded as an abstract
1491 <em>handle</em> that must be supplied to subsequent I/O operations
1492 like <code>read(2)</code> or <code>write(2)</code> to tell the system
1493 call the target object of the operation. </p>
1494
1495 <p> The shell automatically creates three file descriptors for each
1496 process which are identified by the integers 0, 1 and 2. They are
1497 called <em>stdin</em>, <em>stdout</em>, and <em>stderr</em>, which is
1498 short for <em>standard input/output/error</em>. It is possible, and in
1499 fact common, that all three file descriptors point to the same file
1500 description: the terminal device. Many command line tools read their
1501 input from stdin, write normal output to stdout, and error messages
1502 to stderr. For example, when the POSIX command <code>cat(1)</code>
1503 is invoked with no arguments, it reads data from stdin and writes
1504 the same data to stdout. </p>
1505
1506 SUBSECTION(«Signals»)
1507
1508 <p> Signals are another ancient Unix concept that dates back to the
1509 early 1970s and was standardized in POSIX long ago. This concept
1510 facilitates a rudimentary form of <em>inter process communication</em>
1511 (IPC) between unrelated processes. Signals can be regarded as software
1512 interrupts that transmit a notification event from the sending process
1513 to the target process. The event is sent <em>asynchronously</em>,
1514 meaning that the interruption can happen at any location of the code
1515 flow. </p>
1516
1517 <p> It is fair to say that most non-trivial programs, including
1518 scripts, have to deal with signals. All major scripting languages
1519 (bash, python, perl, ruby, etc.) provide an API for signal
1520 handling. The interpreter of the scripting language ends up calling
1521 the POSIX system functions, so we will only look at these. </p>
1522
1523 <p> Signals are identified by name or by a numerical ID. For example,
1524 <code>SIGINT</code> (interrupt from keyboard) is the name for signal
1525 number 2. POSIX defines 31 <em>standard signals</em> plus at least
1526 eight <em>real-time signals</em>. The standard signals can be
1527 subdivided according to the origin of the signal as follows. </p>
1528
1529 <dl>
1530 <dt> hardware related signals </dt>
1531
1532 <dd> These signals originate from <em>hardware traps</em> that force
1533 the CPU back into kernel mode. The kernel responds to the trap by
1534 generating a signal for the process that caused the trap. For example,
1535 a division by zero in a user space program triggers a hardware trap
1536 in the <em>floating point unit</em> (FPU) of the CPU. The kernel
1537 then generates the <code>SIGFPE</code> (floating-point exception)
1538 signal for the process. Another example for a signal that originates
1539 from a hardware trap is <code>SIGSEGV</code> (segmentation fault)
1540 which occurs when a process attempts to reference a memory address
1541 that has not been mapped (i.e., marked as valid) by the <em>memory
1542 management unit</em> (MMU) of the CPU. </dd>
1543
1544 <dt> kernel generated signals </dt>
1545
1546 <dd> Signals which originate from the kernel rather than from
1547 hardware. One example is <code>SIGCHLD</code> (child terminated),
1548 which is sent to the parent process when one of its child processes
1549 terminates. Another example is <code>SIGWINCH</code> (window resize),
1550 which is generated when the geometry of the controlling terminal of
1551 a process changes. </dd>
1552
1553 <dt> user-space generated signals </dt>
1554
1555 <dd> These signals can only originate from user space when a process,
1556 for example <code>kill(1)</code>, calls <code>raise(2)</code>
1557 or <code>kill(2)</code> to instruct the kernel to generate a
1558 signal. Examples are <code>SIGTERM</code>, which issues a termination
1559 request, and <code>SIGUSR1</code> and <code>SIGUSR2</code> which are
1560 reserved for use by application programs. </dd>
1561 </dl>
1562
1563 The following signals are used frequently and deserve to the described
1564 explicitly. We refer to <code>signal(7)</code> for the full list of
1565 signals and their semantics.
1566
1567 <dl>
1568 <dt> <code>SIGINT, SIGTERM</code> and <code>SIGKILL</code> </dt>
1569
1570 <dd> All three signals terminate the process by default.
1571 <code>SIGINT</code> is generated for the <em>foreground processes</em>
1572 when the <em>interrupt character</em> (CTRL+C) is pressed in a
1573 terminal. For example, if CTRL+C is pressed while the shell pipeline
1574 <code>find | wc </code> is executing, <code>SIGINT</code> is sent
1575 to both processes of the pipeline. <code>SIGTERM</code> is the
1576 default signal for the <code>kill(1)</code> command. It requests
1577 the target process to run its shutdown procedure, if any, then
1578 terminate. <code>SIGKILL</code> instructs the kernel to terminate the
1579 target process immediately, without giving the process the chance to
1580 clean up. This signal can originate from a process or from the kernel
1581 in response to running out of memory. To keep the system working, the
1582 kernel invokes the infamous <em>out of memory killer</em> (OOM killer)
1583 which terminates one memory-hungry process to free some memory. </dd>
1584
1585 <dt> <code>SIGSTOP</code>, <code>SIGTSTP</code> and <code>SIGCONT</code> </dt>
1586
1587 <dd> <code>SIGSTOP</code> instructs the task scheduler of the kernel to
1588 no longer assign any CPU time to the target process until the process
1589 is woken up by a subsequent <code>SIGCONT</code>. <code>SIGTSTP</code>
1590 (stop typed at terminal) stops all foreground processes of a terminal
1591 session. It is generated when the <em>stop character</em> (CTRL+Z)
1592 is pressed in a terminal. </dd>
1593 </dl>
1594
1595 <p> Processes may set the <em>signal disposition</em> of most signals
1596 to control what happens when the signal arrives. When no disposition
1597 has been set, the signal is left at its <em>default disposition</em> so
1598 that the <em>default action</em> is performed to deliver the signal.
1599 For most signals the default action is to terminate the process,
1600 but for others the default action is to <em>ignore</em> the signal.
1601 If the signal is neither ignored nor left at its default disposition,
1602 it is said to be <em>caught</em> by the process. To catch a signal the
1603 process must tell the kernel the address of a function, the <em>signal
1604 handler</em>, to call in order to deliver the signal. The set of
1605 signal dispositions of a process can thus be imagined as an array
1606 of function pointers with one pointer per possible signal. If the
1607 process catches the signal, the pointer points to the corresponding
1608 signal handler. A NULL pointer represents a signal that was left at
1609 its default disposition while the special value <code>SIG_IGN</code>
1610 indicates that the process explicitly asked to ignore this signal. </p>
1611
1612 <p> Signals can also be <em>blocked</em> and <em>unblocked</em>. When
1613 a signal is generated for a process that has it blocked, it remains
1614 <em>pending</em>. Pending signals cause no action as long as the
1615 signal remains blocked but the action will be performed once the
1616 signal gets unblocked. <code>SIGKILL</code> and <code>SIGSTOP</code>
1617 can not be caught, blocked, or ignored. </p>
1618
1619 <p> Real-time signals are similar to <code>SIGUSR1</code> and
1620 <code>SIGUSR2</code> in that they have no predefined meaning but
1621 can be used for any purpose. However, they have different semantics
1622 than the standard signals and support additional features. Most
1623 importantly, real-time signals are <em>queued</em>, meaning that in
1624 contrast to standard signals the same real-time signal can be pending
1625 multiple times. Also, the sending process may pass an <em>accompanying
1626 value</em> along with the signal. The target process can obtain this
1627 value from its signal handler along with additional information like
1628 the PID and the UID of the process that sent the signal. </p>
1629
1630 <p> Some system calls including <code>read(2)</code> and
1631 <code>write(2)</code> may block for an indefinite time. For
1632 example, reading from a network socket blocks until there is data
1633 available. What should happen when a signal arrives while the process
1634 is blocked in a system call? There are two reasonable answers: Either
1635 the system call is <em>restarted</em>, or the call fails with the
1636 <code>Interrupted system call</code> error. Unfortunately, different
1637 flavors of Unix handle this case differently by default. However,
1638 applications may request either behaviour by setting or clearing the
1639 <code>SA_RESTART</code> flag on a per-signal basis. </p>
1640
1641 SUBSECTION(«Environment of a Process»)
1642
1643 <p> Now that we have a rough understanding of processes we look
1644 closer at the information the kernel maintains for each process. We
1645 already discussed the array of file descriptors and the array of
1646 signal dispositions. Clearly both are process specific properties.
1647 As we shall see, there is much more what constitutes the environment
1648 of a process. </p>
1649
1650 <p> Each process is identified by a unique <em>process ID</em>
1651 (PID), which is a positive integer. The <code>init</code> process is
1652 identified by PID 1. PIDs are assigned in ascending order, but are
1653 usually restricted to the range 1..32767. After this many processes
1654 have been created, PIDs wrap and unused PIDs are recycled for new
1655 processes. Thus, on a busy system on which processes are created and
1656 terminated frequently, the same PID is assigned to multiple processes
1657 over time. </p>
1658
1659 <p> Not all processes call <code>fork(2)</code> to create a child
1660 process, but each process except the init process has a unique
1661 parent. As described before, this is either the "real" parent (the
1662 process which created the process earlier) or the init process that
1663 "adopted" the orphaned process in case the real parent terminated
1664 before the child. The process ID of the parent (PPID) is thus
1665 well-defined. A process can obtain its PID and PPID with the
1666 <code>getpid(2)</code> and <code>getppid(2)</code> system calls. </p>
1667
1668 <p> Each process runs on behalf of a user (possibly the superuser)
1669 which is identified by its <em>user ID</em> (UID) and belongs to
1670 one or more groups, identified by one or more <em>group IDs</em>
1671 (GIDs). The superuser is identified by UID zero. When we talked
1672 about the permission bits of files and directories, we said that
1673 suitable permissions are needed for system calls which operate on
1674 files (<code>open(2)</code>, <code>stat(2)</code>, etc.). A more
1675 precise statement is that the <em>process</em> which calls, say,
1676 <code>open(2)</code> needs to have these permissions. To decide this,
1677 the kernel needs to take into account the UID and GIDs of the process
1678 that called <code>open(2)</code>, the UID and the GID stored in the
1679 inode of the file that is being opened, and the permission bits of
1680 this file. The UID is also taken into account for <code>kill(2)</code>
1681 because unprivileged processes (non-zero UID) can only send signals
1682 to processes which run on behalf of the same user while the superuser
1683 may target any process. </p>
1684
1685 <p> Each process has a <em>current working directory</em> (CWD)
1686 associated with it. When the user logs in, the CWD of the login shell
1687 process is set to his <em>home directory</em>, which should always
1688 exist and have the read, write and execute permission bits set for
1689 the user. The CWD can later be changed with <code>chdir(2)</code>
1690 and be retrieved with <code>getcwd(3)</code>. The CWD is used as the
1691 starting point for path searches for relative paths. It affects most
1692 system calls which receive a path argument. For example, if the CWD
1693 is <code>/foo/bar</code> and the relative path <code>baz/qux</code>
1694 is passed to <code>open(2)</code>, the kernel will attempt to open
1695 the file which is identified by <code>/foo/bar/baz/qux</code>. </p>
1696
1697 <p> Many programs accept arguments to control their behavior.
1698 In addition to the path to the program that is to be executed,
1699 all variants of the exec system calls receive an array of arguments
1700 called the <em>argument vector</em>. For example, when the command
1701 <code>ls -l foo</code> is executed, the argument vector contains
1702 the two strings <code>"-l"</code> and <code>"foo"</code>. Note that
1703 the argument vector is not part of the program but is tied to the
1704 process. It is passed to the main function at startup so that the
1705 program may evaluate it and act accordingly. </p>
1706
1707 <p> Another way to pass information to a program is via <em>environment
1708 variables</em>. Environment variables are strings of the form
1709 <code>name=value</code>. POSIX describes the API to maintain the
1710 environment variables of a process. Environment variables are set
1711 with <code>setenv(3)</code> or <code>putenv(3)</code>, the value of a
1712 variable can be retrieved with <code>getenv(3)</code>, and a variable
1713 and its value can be deleted with <code>unsetenv(3)</code>. The set of
1714 environment variables is sometimes called the <em>environment</em>
1715 of the process, although we use this term in a broader sense to
1716 describe the entirety of all metadata maintained by the kernel about
1717 the process, including but not limited to environment variables. </p>
1718
1719 <p> Each process also has about a dozen <em>resource limits</em>
1720 that can be set and queried with the POSIX <code>setrlimit(2)</code>
1721 and <code>getrlimit(2)</code> functions. Each limit controls a
1722 different aspect. For example, <code>RLIMIT_CPU</code> limits the
1723 CPU time the process is allowed to use and <code>RLIMIT_NOFILE</code>
1724 controls how many open files it may have at a time. For each resource
1725 there is a <em>soft</em> and a <em>hard</em> limit. The kernel
1726 enforces the value stored as the soft limit. This value may be set
1727 by an unprivileged process to any value between zero and the hard
1728 limit. Unprivileged processes may also reduce (but not increase) their
1729 hard limits. Once a hard limit is reduced, it can not be increased
1730 any more. For <code>RLIMIT_CPU</code> a special convention applies:
1731 If the soft limit is reached, the kernel sends <code>SIGXCPU</code>
1732 (CPU time limit exceeded) to notify the process about this fact so
1733 that it can terminate orderly (e.g., remove temporary files). When
1734 the hard limit is reached, the kernel terminates the process as if
1735 it received <code>SIGKILL</code>. </p>
1736
1737 <p> The <em>nice level</em> of a process provides a hint for
1738 the task scheduler to give the process a lower or higher priority
1739 relative to other processes. Nice levels range between -20 and 19. A
1740 high nice level means that the process wants to be nice to other
1741 processes, that is, should run with reduced priority. Low nice levels
1742 indicate important processes that should be prioritized over other
1743 processes. The default nice level is zero. Unprivileged users may
1744 set the nice level of new processes with the <code>nice(1)</code>
1745 command to any non-negative value. They can also increase the nice
1746 level of their existing processes with <code>renice(1)</code>, but
1747 never decrease it. The superuser, however, may set the nice level
1748 of any process to an arbitrary value in the valid range. </p>
1749
1750 <p> The bulk of the properties discussed so far are inherited by the
1751 child after a <code>fork(2)</code>. Specifically, the child gets the
1752 same array of file descriptors and signal dispositions as its parent,
1753 runs on behalf of the same user, has the same working directory,
1754 the same resource limits and nice level, and also the same set
1755 of environment variables with identical values. The PID and PPID,
1756 however, are different of course. </p>
1757
1758 <p> After a process has called an exec function to replace itself with
1759 a new program, its signal handlers no longer exist because they were
1760 part of the program code which has been replaced. Therefore the exec
1761 system calls reset the disposition of all signals that were caught to
1762 the default disposition. Signals that were being ignored keep being
1763 ignored, however. </p>
1764
1765 SUBSECTION(«The Process Filesystem»)
1766
1767 <p> Although not covered by POSIX, at least Linux, NetBSD and FreeBSD
1768 provide information about processes via the <em>process filesystem</em>
1769 (procfs), which is usually mounted on <code>/proc</code>. The process
1770 filesystem is a <em>pseudo-filesystem</em>, i.e., it has no underlying
1771 storage device. Files and directories are faked by the kernel as they
1772 are accessed. Each process is represented by a numerical subdirectory
1773 of <code>/proc</code> which is named by the PID. For example,
1774 <code>/proc/1</code> represents the init process. The aforementioned
1775 process utilities (<code>ps(1)</code>, <code>top(1)</code>, etc.) read
1776 the contents of the process filesystem in order to do their job. <p>
1777
1778 <p> Each <code>/proc/[pid]</code> directory contains the same set
1779 of files although this set is different between Unixes. These files
1780 expose much of the environment of the process to user space. The Linux
1781 procfs implementation provides text files named <code>environ</code>
1782 and <code>limits</code> which contain the current environment and
1783 the resource limits of the process, respectively. Moreover, the
1784 file descriptor array of each process is exposed in the files of
1785 the <code>/proc/[pid]/fd</code> directory. Linux and NetBSD (but not
1786 FreeBSD) also provide a <code>cwd</code> soft link which points to
1787 the current working directory of the process. </p>
1788
1789 SUBSECTION(«Pipes and Redirections»)
1790
1791 <p> The <code>pipe(2)</code> system call takes no arguments and
1792 creates two file descriptors for the calling process which are tied
1793 together as a unidirectional first in, first out data channel that
1794 works just like a fifo, but without any files being involved. One
1795 file descriptor is the <em>read end</em> of the pipe, the other is
1796 the <em>write end</em>. Data written to the write end is buffered by
1797 the kernel and can be obtained by reading from the read end. </p>
1798
1799 <p> One application of pipes is communication between
1800 related processes. A process first creates a pipe, then calls
1801 <code>fork(2)</code> to create a child process. The child inherits
1802 a copy of both pipe file descriptors. Hence the parent process can
1803 communicate with the child by writing a message to the write end of
1804 the pipe for the child to read. </p>
1805
1806 <p> The POSIX <code>dup(2)</code> and <code>dup2(2)</code> system
1807 calls allow a process to manipulate the entries of its file descriptor
1808 array. In particular the standard file descriptors 0, 1, and 2 can be
1809 replaced. By doing so before performing an exec system call, it can
1810 be arranged that the replacement program starts with, say, its stdout
1811 file descriptor be redirected to the write end of a pipe. Note that
1812 the replacement program does not need any modifications for this to
1813 work, and might not even be aware of the fact that it is not writing
1814 its output to the terminal as usual. </p>
1815
1816 <p> Shells employ this technique to implement the <code>|</code>
1817 operator which "pipes" the output of one command "into" another
1818 command. For example, the pipeline <code>ls | wc</code> works
1819 as follows: First the shell creates a pipe, then it calls
1820 <code>fork(2)</code> twice to create two processes which both
1821 get a copy of the two pipe file descriptors. The first process
1822 replaces its stdout file descriptor with the write end of the
1823 pipe and performs an exec system call to replace itself with the
1824 <code>ls(1)</code> program. The second process replaces its stdin
1825 file descriptor with the read end of the pipe and replaces itself
1826 with <code>wc(1)</code>. Since <code>ls(1)</code> writes to stdout
1827 and <code>wc(1)</code> reads from stdin, <code>wc(1)</code> processes
1828 the output of <code>ls(1)</code>. </p>
1829
1830 <p> Note that this trick does not work to establish a connection
1831 between two <em>existing</em> processes because it depends on file
1832 descriptor inheritance across <code>fork(2)</code>. In the general
1833 case one has to fall back to sockets or fifos to create the data
1834 channel. </p>
1835
1836 SUBSECTION(«Stdio»)
1837
1838 <p> The POSIX standard requires a compliant Unix system to provide
1839 a collection of functions that let applications perform input and
1840 output by means of operations on <em>streams</em>. This programming
1841 interface, known as <em>stdio</em> for <em>standard input/output</em>,
1842 is part of every Unix system since 1979. Every program which contains
1843 a <code>printf(3)</code> statement relies on stdio. </p>
1844
1845 <p> The stdio functions are implemented as part of libc on top of the
1846 <code>open(2)</code>, <code>read(2)</code> and <code>write(2)</code>
1847 system calls which are implemented in the kernel. Roughly speaking,
1848 stdio replaces the file descriptor API by a more abstract API
1849 which centers around streams. A stream is an opaque data structure
1850 which comprises a file descriptor and an associated data buffer for
1851 I/O. Each program has three predefined streams which correspond to
1852 the three standard file descriptors (stdin, stdout and stderr). The
1853 stdio API contains well over 50 functions to create and maintain
1854 streams and to perform I/O on streams. These functions take care of
1855 the characteristics of the underlying file description. For example,
1856 they automatically try to select the optimal I/O buffer size. </p>
1857
1858 <p> Many applications rely on stdio because of convenience. For
1859 one, the buffers for <code>read(2)</code> and <code>write(2)</code>
1860 must be allocated and freed explicitly by the application, and care
1861 must be taken to not overflow these buffers. With stdio, this task
1862 is done by the stdio library. Second, <em>formatted</em> I/O is
1863 much easier to do with the stdio functions because the programmer
1864 only has to provide a suitable <em>format string</em> to convert
1865 between the machine representation and the textual representation of
1866 numbers. For example, by passing the format string <code>"%f"</code>
1867 to <code>scanf(3)</code>, the programmer tells the stdio library to
1868 read a floating point number stored in textual representation from the
1869 specified stream, convert it to machine representation and store it
1870 in the given variable. The <code>fprintf(3)</code> function works the
1871 other way round: the value is converted from machine representation
1872 to text, and this text is written to the stream. Both functions can
1873 deal with various formats, like scientific notation for floating
1874 point numbers (e.g., 0.42E-23). With stdio it is easy to customize
1875 the formatted output, for example add leading zeros or select the
1876 number of decimal digits in the textual representation of a floating
1877 point number. </p>
1878
1879 <p> Another reason why many programs rely on stdio is that it performs
1880 <em>buffered</em> I/O. With buffered I/O not each read/write operation
1881 results in a system call. Instead, data read from or written to the
1882 stream is first stored in the user space buffer that is associated
1883 with the stream. This is a performance improvement for applications
1884 which perform many small I/O operations because every system call
1885 incurs some overhead. Buffers may be <em>flushed</em> explicitly by
1886 calling <code>fflush(3)</code>, or implicitly by the stdio library. The
1887 criteria which cause an implicit flush depend on the <em>buffering
1888 type</em> of the stream. Three buffering types exist. </p>
1889
1890 <dl>
1891 <dt> unbuffered </dt>
1892
1893 <dd> The stdio library does not buffer any reads or writes. Instead,
1894 each I/O operation results in a <code>read(2)</code> or
1895 <code>write(2)</code> system call. By default the stderr stream is
1896 unbuffered to display error messages as quickly as possible. </dd>
1897
1898 <dt> line buffered </dt>
1899
1900 <dd> System calls are performed when a newline character is
1901 encountered. This buffering type applies by default to interactive
1902 sessions where the file descriptor of the stream refers to a terminal
1903 device (as determined by <code>isatty(3)</code>). </dd>
1904
1905 <dt> fully buffered </dt>
1906
1907 <dd> I/O takes place only if the buffer of the stream is empty/full. By
1908 default, if the file descriptor refers to a regular file, the
1909 stream is fully buffered. POSIX requires that stderr is never fully
1910 buffered. </dd>
1911 </dl>
1912
1913 <p> The exercises on stdio focus on the three different buffering
1914 types because this is a common source of confusion. </p>
1915
1916 SUBSECTION(«The Virtual Address Space of a Process»)
1917
1918 <p> Isolation refers to the concept that each process gets its own
1919 <em>virtual address space</em>. A rough understanding of the memory
1920 management system and the layout of the virtual address space of
1921 a process helps to locate the source of common problems like the
1922 infamous <code>segmentation fault</code> error, and to realize that
1923 putatively simple questions such as "how much memory is my process
1924 currently using?" are in fact not simple at all, and need to be made
1925 more precise before they can be answered. </p>
1926
1927 <div>
1928
1929 define(«vas_width», «200»)
1930 define(«vas_height», «300»)
1931 define(«vas_vmem_left_margin», «5»)
1932 define(«vas_vmem_top_margin», «5»)
1933 define(«vas_mem_width», «20»)
1934 define(«vas_gap_width», «30»)
1935 define(«vas_vmem_height», «140»)
1936 define(«vas_vmem_color», «#34b»)
1937 define(«vas_pmem_height», «100»)
1938 define(«vas_pmem_color», «#7e5»)
1939 define(«vas_vmem_unmapped_color», «#a22»)
1940 define(«vas_vmem_swapped_color», «yellow»)
1941 define(«vas_pmem_unavail_color», «orange»)
1942 define(«vas_disk_gap», «15»)
1943 define(«vas_disk_height», «20»)
1944 define(«vas_disk_color», «grey»)
1945 define(«vas_x1», «vas_vmem_left_margin()»)
1946 define(«vas_x2», «eval(vas_x1() + vas_mem_width())»)
1947 define(«vas_x3», «eval(vas_x2() + vas_gap_width())»)
1948 define(«vas_x4», «eval(vas_x3() + vas_mem_width())»)
1949
1950 define(«vas_membox», «
1951 <rect
1952 fill="$1" stroke="black" stroke-width="1"
1953 x="eval(vas_vmem_left_margin() + $3)"
1954 y="vas_vmem_top_margin()"
1955 width="vas_mem_width()" height="$2"
1956 />
1957 »)
1958 define(«vas_vmem_unmapped_box», «
1959 <rect
1960 fill="vas_vmem_unmapped_color()" stroke="black" stroke-width="1"
1961 x="eval(vas_vmem_left_margin())"
1962 y="eval(vas_vmem_top_margin() + $1)"
1963 width="vas_mem_width()"
1964 height="eval($2)"
1965 />
1966
1967 »)
1968 define(«vas_vmem_swapped_box», «
1969 <rect
1970 fill="vas_vmem_swapped_color()" stroke="black" stroke-width="1"
1971 x="eval(vas_vmem_left_margin())"
1972 y="eval(vas_vmem_top_margin() + $1)"
1973 width="vas_mem_width()"
1974 height="eval($2)"
1975 />
1976
1977 »)
1978 define(«vas_pmem_unavail_box», «
1979 <rect
1980 fill="vas_pmem_unavail_color()" stroke="black" stroke-width="1"
1981 x="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width())"
1982 y="eval(vas_vmem_top_margin() + $1)"
1983 width="vas_mem_width()"
1984 height="$2"
1985 />
1986
1987 »)
1988 define(«vas_vmem_hline», «
1989 <line
1990 x1="vas_vmem_left_margin()"
1991 y1="eval(vas_vmem_top_margin() + $1)"
1992 x2="eval(vas_vmem_left_margin() + vas_mem_width())"
1993 y2="eval(vas_vmem_top_margin() + $1)"
1994 stroke-width="1"
1995 stroke="black"
1996 />
1997
1998 »)
1999
2000 define(«vas_pmem_hline», «
2001 «<!-- pmem hline -->»
2002 <line
2003 x1="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width())"
2004 y1="eval(vas_vmem_top_margin() + $1)"
2005 x2="eval(vas_vmem_left_margin() + 2 * vas_mem_width() + vas_gap_width())"
2006 y2="eval(vas_vmem_top_margin() + $1)"
2007 stroke-width="1"
2008 stroke="black"
2009 />
2010
2011 »)
2012 define(«vas_arrow», «
2013 <line
2014 x1="eval(vas_vmem_left_margin() + vas_mem_width())"
2015 y1="eval(vas_vmem_top_margin() + $1)"
2016 x2="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width() - 2)"
2017 y2="eval(vas_vmem_top_margin() + $2)"
2018 stroke-width="1"
2019 stroke="black"
2020 marker-end="url(#arrow)"
2021 />
2022 »)
2023 define(«vas_disk», «
2024 <rect
2025 fill="vas_disk_color()" stroke="black" stroke-width="1"
2026 x="vas_x3()"
2027 y="eval(vas_vmem_top_margin() + vas_pmem_height()
2028 + vas_disk_gap())"
2029 width="eval(vas_x4() - vas_x3())"
2030 height="eval(vas_disk_height())"
2031 />
2032 <ellipse
2033 cx="eval(vas_x3() + vas_mem_width() / 2)"
2034 cy="eval(vas_vmem_top_margin() + vas_pmem_height() + vas_disk_gap())"
2035 rx="eval(vas_mem_width() / 2)"
2036 ry="eval(vas_mem_width() / 4)"
2037 fill="vas_disk_color()" stroke="black"
2038 />
2039 <ellipse
2040 cx="eval(vas_x3() + vas_mem_width() / 2)"
2041 cy="eval(vas_vmem_top_margin() + vas_pmem_height()
2042 + vas_disk_gap() + vas_disk_height())"
2043 rx="eval(vas_mem_width() / 2)"
2044 ry="eval(vas_mem_width() / 4)"
2045 fill="vas_disk_color()" stroke="black"
2046 />
2047 »)
2048
2049 <svg
2050 width="vas_width()" height="vas_height()"
2051 viewBox="0 0 100 eval(100 * vas_height() / vas_width())"
2052 xmlns="http://www.w3.org/2000/svg"
2053 xmlns:xlink="http://www.w3.org/1999/xlink"
2054 >
2055 <marker
2056 id="arrow"
2057 viewBox="0 0 10 10" refX="5" refY="5"
2058 markerWidth="4" markerHeight="4"
2059 orient="auto-start-reverse">
2060 <path d="M 0 0 L 10 5 L 0 10 z" />
2061 </marker>
2062 vas_membox(«vas_vmem_color()», «vas_vmem_height()», «0»)
2063 vas_membox(«vas_pmem_color()», «vas_pmem_height()»,
2064 «eval(vas_gap_width() + vas_mem_width())»)
2065 vas_vmem_hline(«10»)
2066 vas_vmem_hline(«40»)
2067 vas_vmem_unmapped_box(«40», «20»)
2068 vas_vmem_swapped_box(«60», «60»)
2069
2070 vas_pmem_unavail_box(«0», «10»)
2071 vas_pmem_hline(«20»)
2072 vas_pmem_unavail_box(«20», «30»)
2073 vas_pmem_hline(«80»)
2074
2075 vas_arrow(«5», «15»)
2076 vas_arrow(«25», «65»)
2077 vas_arrow(«130», «90»)
2078 vas_disk()
2079 vas_arrow(«90», «eval(vas_pmem_height() + vas_disk_gap()
2080 + vas_disk_height() / 2)»)
2081 </svg>
2082 </div>
2083
2084 <p> Virtual memory is an abstraction of the available memory resources.
2085 When a process reads from or writes to a memory location, it refers
2086 to <em>virtual addresses</em> (illustrated as the left box of the
2087 diagram). Virtual addresses are mapped by the MMU to <em>physical
2088 addresses</em> which refer to physical memory locations (right
2089 box). The <em>mapped</em> virtual address space of a process is a
2090 collection of ranges of virtual addresses which correspond to physical
2091 memory addresses (blue areas). By storing less frequently-accessed
2092 chunks of virtual memory (yellow) on the swap area (grey), applications
2093 can use more memory than is physically available. In this case the
2094 size of the valid virtual addresses (blue and yellow areas together)
2095 exceeds the amount of physical memory (orange and green areas). Any
2096 attempt to access an unmapped memory location (red and yellow areas)
2097 results in a <em>page fault</em>, a hardware trap which forces the CPU
2098 back into kernel mode. The kernel then checks whether the address is
2099 valid (yellow) or invalid (red). If it is invalid, the kernel sends
2100 <code>SIGSEGV</code>, which usually terminates the process with
2101 the <code>segmentation fault</code> error. Otherwise it allocates
2102 a chunk of unused physical memory, copies the chunk from the swap
2103 area to the newly allocated memory and adjusts the mapping (i.e.,
2104 a yellow part becomes blue). The virtual memory concept increases
2105 stability and security because no process can access physical memory
2106 which belongs to the kernel or to other processes (orange areas). </p>
2107
2108 <p> We've already seen that the <code> fork(2) </code> system call
2109 creates a new process as a duplicate of the calling process. Since
2110 the virtual address space of the calling process (a) might be large
2111 and (b) is likely to be replaced in the child by a subsequent call
2112 to an exec function, it would be both wasteful and pointless to
2113 copy the full address space of the parent process to the child. To
2114 implement <code> fork(2) </code> efficiently, operating systems
2115 employ an optimization strategy known as <em> Copy on Write </em>
2116 (CoW). The idea of CoW is that if multiple callers ask for resources
2117 which are initially indistinguishable, you can give them pointers to
2118 the same resource. This function can be maintained until a caller
2119 tries to modify its copy of the resource, at which point a true
2120 private copy is created to prevent the changes becoming visible to
2121 everyone else. The primary advantage is that if a caller never makes
2122 any modifications, no private copy needs ever be created. The <code>
2123 fork(2) </code> system call marks the pages of the virtual address
2124 space of both the parent and the child process as CoW by setting a
2125 special bit in the <em> page table entry </em> which describes the
2126 mapping between virtual and physical addresses of the MMU. As for
2127 invalid memory accesses, the attempt to write to a CoW page results
2128 in a page fault that puts the CPU back into kernel mode. The kernel
2129 then allocates a new memory page on behalf of the process, copies
2130 the contents of the page which caused the fault, changes the page
2131 table mappings for the process accordingly and returns to user space.
2132 This all happens transparently to the process. </p>
2133
2134 <div>
2135 define(«asl_width», «300»)
2136 define(«asl_height», «400»)
2137 define(«asl_top_margin», «10»)
2138 define(«asl_text_width», «35»)
2139 define(«asl_mem_width», «25»)
2140 define(«asl_mem_color_env», «#fc8»)
2141 define(«asl_mem_color_stack», «#8fc»)
2142 define(«asl_mem_color_empty», «#ccc»)
2143 define(«asl_mem_color_heap», «#c8f»)
2144 define(«asl_mem_color_bss», «#8cf»)
2145 define(«asl_mem_color_data», «#cf8»)
2146 define(«asl_mem_color_text», «#f8c»)
2147 define(«asl_font_size», «5»)
2148
2149 define(«asl_arrow», «
2150 <line
2151 x1="0"
2152 y1="$1"
2153 x2="eval(asl_text_width() - 2)"
2154 y2="$1"
2155 stroke-width="1"
2156 stroke="black"
2157 marker-end="url(#arrow)"
2158 />
2159 »)
2160 define(«asl_arrow_text», «
2161 <text
2162 x="0"
2163 y="$1"
2164 font-size="asl_font_size()"
2165 >
2166 $2
2167 </text>
2168 »)
2169
2170 dnl $1: y0, $2; height, $3: color, $4: high arrow text
2171 dnl $5: low arrow text, $6: desc
2172
2173 define(«asl_box», «
2174 <rect
2175 stroke="black"
2176 stroke-width="1"
2177 x="asl_text_width()"
2178 y="eval($1 + asl_top_margin())"
2179 height="$2"
2180 fill="$3"
2181 width="asl_mem_width()"
2182 />
2183 ifelse(«$4», «», «», «
2184 asl_arrow(«eval($1 + asl_top_margin())»)
2185 asl_arrow_text(«eval($1 + asl_top_margin() - 2)», «$4»)
2186 »)
2187 ifelse(«$5», «», «», «
2188 asl_arrow(«eval($1 + $2 + asl_top_margin())»)
2189 asl_arrow_text(«eval(asl_top_margin()
2190 + $1 + $2 - 2)», «$5»)
2191 »)
2192 <text
2193 x="eval(asl_text_width() + asl_mem_width() + 2)"
2194 y="eval($1 + $2 / 2 + asl_top_margin())"
2195 dy="0.3em"
2196 font-size="asl_font_size()"
2197 >
2198 $6
2199 </text>
2200 »)
2201
2202 <svg
2203 width="asl_width()" height="asl_height()"
2204 viewBox="0 0 100 eval(100 * asl_height() / asl_width())"
2205 xmlns="http://www.w3.org/2000/svg"
2206 xmlns:xlink="http://www.w3.org/1999/xlink"
2207 >
2208 asl_box(«0», «10», «asl_mem_color_env», «2^64 - 1», «»,
2209 «Environment»)
2210 asl_box(«10», «15», «asl_mem_color_stack», «», «base pointer»,
2211 «Stack»)
2212 asl_box(«25», «30», «asl_mem_color_empty», «», «break point»,
2213 «Empty»)
2214 asl_box(«55», «35», «asl_mem_color_heap», «», «», «Heap»)
2215 asl_box(«90», «10», «asl_mem_color_bss», «», «», «BSS»)
2216 asl_box(«100», «10», «asl_mem_color_data», «», «», «Data»)
2217 asl_box(«110», «10», «asl_mem_color_text», «», «0», «Text»)
2218 </svg>
2219 </div>
2220
2221 <p> The diagram on the left illustrates the layout of the virtual
2222 address space of a process. At the top of the address space are the
2223 argument vector and the environment variables. The <em>stack</em>
2224 stores the local variables of the functions which are currently
2225 being called, plus house-keeping data like the return addresses
2226 of these functions. As more functions are called, the stack grows
2227 downwards towards the lower addresses. Its current lower end is
2228 called the <em> base pointer</em>. The other variable area of the
2229 address space is the <em>heap</em>, which contains the memory that
2230 has been allocated on behalf of the process, for example with <code>
2231 malloc(3)</code>. As the process allocates more memory, the heap grows
2232 upwards, towards the stack. The current end of the heap is called the
2233 <em> break point</em>. The lower part of the address space contains
2234 three segments of fixed size. The <em>text</em> segment contains the
2235 compiled machine instructions of the executable, the <em>data</em>
2236 segment contains the initialized variables which are already known
2237 at compile time. Finally, the <em>BSS</em> segment is allocated and
2238 zeroed at execution time. This segment contains variables which should
2239 initialized to zero at startup. Unlike the data segment it is not
2240 stored in the executable. BSS stands for "Block Started by Symbol",
2241 which is a historic name coined in the 1950s. It has no relation to
2242 the real meaning of the segment. </p>
2243
2244 The exercises of this section invite the reader to look at the virtual
2245 address space of running processes to learn what happens when a
2246 dynamically-linked executable is being executed and how the resulting
2247 memory maps affect the virtual address space of the newly created
2248 process.
2249
2250 EXERCISES()
2251
2252 <ul>
2253 <li> Examine your own processes with <code>htop</code>, <code>ps
2254 ux</code> and <code>pstree -panuch $LOGNAME</code>. </li>
2255
2256 <li> Run <code>ls -l /proc/$$</code> and examine the environment of
2257 your shell process. </li>
2258
2259 <li> Run <code>kill -l</code> and discuss the meaning of signals
2260 1-15. Use <code>signal(7)</code> as a reference. </li>
2261
2262 <li> Create a zombie process: run <code>sleep 100&</code>. From
2263 another terminal, send <code>SIGSTOP</code> to the parent process
2264 of the sleep process (the shell), then send <code>SIGKILL</code>
2265 to the sleep process. Run <code>cat /proc/$PID/status</code> where
2266 <code>$PID</code> is the process ID of the sleep process. </li>
2267
2268 <li> Run <code>echo $$</code> to obtain the PID of an interactive
2269 shell that is running in a terminal. Send the <code>SIGSTOP</code>
2270 and <code>SIGCONT</code> signals to this PID from another terminal
2271 and see what happens when you type in the terminal that contains the
2272 stopped shell process. </li>
2273
2274 <li> The <code>ping(8)</code> utility catches <code>SIGQUIT</code>.
2275 In one terminal execute <code>ping localhost</code>. While this
2276 command runs in an endless loop, send <code>SIGQUIT</code> to the
2277 ping process from another terminal and see what happens. </li>
2278
2279 <li> Read <code>kill(2)</code> to learn what <code>kill -9 -1</code>
2280 does. Run this command if you are brave. </li>
2281
2282 <li> Why doesn't the <a href="«#»cd_script">cd script</a> work as
2283 expected? </li>
2284
2285 <li> Explain the difference between the two commands <code>X=foo
2286 bar</code> and <code>X=foo; bar</code>. </li>
2287
2288 <li> Run <code>set</code> and examine the environment variables of
2289 an interactive shell session. </li>
2290
2291 <li> Check this <a
2292 href="https://public-inbox.org/git/Pine.LNX.4.64.0609141023130.4388@g5.osdl.org/">email</a>
2293 from Linus Torvalds about why stdio is not that simple at all. </li>
2294
2295 <li> Run the command <code>ls / /does-not-exist</code>, redirect
2296 stdout and stderr to different files. </li>
2297
2298 <li> Consider the following shell code which uses stdio to first write
2299 to stdout, then to stderr. <code>echo foo; echo bar 1>&2</code>. Which
2300 circumstances guarantee that the "foo" line appears before the "bar"
2301 line in the output? </li>
2302
2303 <li> In the pipeline <code> foo | bar</code>, what is the
2304 buffering type of the file descriptor which corresponds to
2305 the <code> stdin </code> stream of the <code> bar </code>
2306 process? </li>
2307
2308 <li> Assume <code>foo</code> is a log file which increases due to
2309 some process appending data to it. Explain why the command <code>
2310 tail -f foo | while read; do echo new data; done </code> does not
2311 work as expected. Fix the flaw by changing the buffering type with
2312 <code>stdbuf(1)</code>. </li>
2313
2314 <li> Run <code>sleep 100 > /dev/null &</code>, examine open
2315 files of the sleep process by looking at suitable files in
2316 <code>/proc</code>. Do the same with <code>sleep 100 | head
2317 &</code>. </li>
2318
2319 <li> Run <code>ldd /bin/sh</code> and explain what happens when a
2320 shell is executed. </li>
2321
2322 <li> On a Linux system, run <code>cat /proc/$$/maps</code> or
2323 <code>pmap -x $$</code> to see the address space layout of your
2324 shell. Check <code>Documentation/filesystems/proc.txt</code>
2325 in the linux kernel source tree for the format of
2326 <code>/proc/$$/maps</code>. </li>
2327
2328 <li> Run <code>cat /proc/$$/smaps</code> and examine the values of
2329 the heap section. </li>
2330
2331 <li> Assume some program allocates a lot of memory so that the size of
2332 the valid virtual addresses is 1T large. Assume further that a software
2333 bug causes the content of a pointer variable to be overwritten with
2334 random garbage. Determine the probability that this pointer variable
2335 contains a valid address (assuming a 64 bit system). </li>
2336 </ul>
2337
2338 HOMEWORK(«
2339
2340 Explain how <code>PR_SET_CHILD_SUBREAPER</code> works and possible
2341 use-cases for this (Linux) feature.
2342
2343 »)
2344
2345 HOMEWORK(«
2346
2347 Explain in one paragraph of text the purpose of the <em>file
2348 creation mask</em> (also known as <em>umask</em>) of a process.
2349
2350 »)
2351
2352 HOMEWORK(«
2353
2354 When we said that each process runs on behalf of a user and that the
2355 ID of this user is part of the process metadata, we were simplifying
2356 matters. There are actually three different UIDs and three different
2357 GIDs: the <em>real UID</em>, the <em>effective UID</em>, and the
2358 <em>saved set-user ID</em>, and analogous for the group IDs. Explain
2359 the purpose of the three UIDs.
2360
2361 »)
2362
2363
2364 HOMEWORK(«
2365
2366 On a multi-CPU system the performance of a program can be
2367 enhanced by allowing for multiple flows of control. This is the
2368 idea behind <em>threads</em>, which are also called <em>lightweight
2369 processes</em>. Give an overview of threads, summarize the POSIX thread
2370 API (see <code>pthreads(7)</code>) and explain how the Linux-specific
2371 <code>clone(2)</code> system call can used to implement threads.
2372
2373 »)
2374
2375 HOMEWORK(«
2376
2377 Explain what the command <code>find /etc > /dev/null</code> does,
2378 and why you get some error messages. Assume you'd like to extract
2379 only those error messages which contain the string "lvm". Explain
2380 why <code>find /etc > /dev/null | grep lvm</code> does not work as
2381 expected. Come up with a similiar command that works.
2382
2383 », «
2384
2385 The command traverses the <code>/etc</code> directory recursively and
2386 prints all files and directories it encounters during the traversal to
2387 stdout. Since stdout is redirected to the NULL device by the <code>>
2388 /dev/null</code> construct, only the stderr stream containing the error
2389 messages makes it to the terminal. This includes all subdirectories
2390 of <code>/etc</code> which cannot be traversed due to insufficient
2391 permissions (no "r" bit set). The proposed <code>find | grep</code>
2392 command does not work since the <code>|</code> operator is evaluated
2393 <em>before</em> any redirections specified by the find command
2394 take place. More precisely, stdout of the find process is redirected
2395 <em>twice</em>: First to one end of the pipe due to the <code>|</code>,
2396 then to the NULL device due to the <code>> /dev/null</code>. The
2397 last redirection "wins", so the <code>grep</code> process does not
2398 see any input. The command <code>find /etc 2>&1 > /dev/null | grep
2399 lvm</code> works. The following four redirections take place: First
2400 stdout of the <code>find</code> process and stdin of <code>grep</code>
2401 process are redirected to the two ends of the pipe. Next, due to
2402 the <code>2>&1</code> the stderr stream of the <code>find</code>
2403 process is redirected to the current destination of stdout, i.e.,
2404 to the pipe. Finally the <code>> /dev/null</code> redirects stdout
2405 of the find process to the NULL device. Hence error messages go to
2406 the pipe and are processed by <code>grep</code> as desired.
2407
2408 »)
2409
2410 HOMEWORK(«
2411 Run <code>ulimit -n</code> to see the maximal number of file descriptors you
2412 are allowed to create. Explain what this limit means with respect
2413 to multiple processes, multiple logins, and the <code>fork(2</code>) system
2414 call. Write a program in your language of choice which creates file
2415 descriptors in a loop until it fails due to the file descriptor
2416 limit. Then print the number of file descriptors the program was able
2417 to create.
2418 », «
2419 On our systems the limit is set to 1024. This means a single process
2420 can only have this many files open at any given time. Independent
2421 processes (like those coming from different login sessions) have no
2422 common file descriptors, even though they may open the same files. In
2423 this sense the file descriptor limit is a per-process limit. However,
2424 when a process calls <code>«fork(</code>») to create a new process, the new
2425 process inherits all open file descriptors from the parent. This can
2426 lead to the situation where a newly created process is unable to open
2427 <em>any</em> files. This property was actually used to break computer
2428 security. The <code>«O_CLOEXEC»</code> flag was introduced not too long
2429 ago to deal with this problem. See <code>open(2</code>) for details.
2430
2431 C program that opens the maximal possible number of file descriptors:
2432
2433 <pre>
2434 int main(void)
2435 {
2436 int i;
2437
2438 for (i == 0; open("/dev/null", O_RDONLY) >= 0; i++)
2439 ;
2440 printf("opened %d file descriptors\n", i);
2441 exit(0);
2442 }
2443 </pre>
2444 »)
2445
2446 HOMEWORK(«
2447
2448 Search the web for the document called
2449 <code>vm/overcommit-accounting</code>. Discuss the pros and cons of
2450 the three possible overcommit handling modes.
2451
2452 »)
2453
2454 HOMEWORK(«
2455
2456 Read this
2457 <a
2458 href="https://utcc.utoronto.ca/~cks/space/blog/unix/MemoryOvercommit">blog
2459 posting</a> on the virtual memory overcommit issue. Explain the
2460 catch-22 situation described there in no more than two sentences.
2461
2462 »)
2463
2464 HOMEWORK(«
2465
2466 Describe, in a single paragraph of text, what a virtual dynamic
2467 shared object (VDSO) is and which type of applications benefit most
2468 from it.
2469
2470 »)
2471
2472 HOMEWORK(«
2473
2474 Describe the concept of <em> huge pages </em> and the Linux-specific
2475 implementation of <em> transparent </em> huge pages. Discuss the pros
2476 and cons of huge tables and explain the workloads which would benefit
2477 from a setup with huge pages enabled.
2478
2479 »)
2480
2481 HOMEWORK(«
2482 <ul>
2483 <li> Explain the concept of <em>address space layout randomization</em>
2484 (ASLR). </li>
2485
2486 <li> Run <code>bash -c</code> '<code>cat /proc/$$/maps</code>'
2487 repeatedly to see address space layout randomization in action. Discuss
2488 the pros and cons of ASLR. </li>
2489 </ul>
2490 »)
2491
2492 SUPPLEMENTS()
2493
2494 SUBSECTION(«cd_script»)
2495
2496 <pre>
2497 #!/bin/sh
2498 echo "changing CWD to $1"
2499 cd "$1"
2500 </pre>
2501
2502 SUBSECTION(«hello_world»)
2503
2504 <pre>
2505 #!/bin/sh
2506 echo "hello world"
2507 </pre>
2508
2509 SUBSECTION(«symlink_madness»)
2510
2511 <pre>
2512 #!/bin/sh
2513 mkdir foo
2514 touch foo/a
2515 ln -s ../foo foo/testdir
2516 ls -l foo/a foo/testdir/a foo/testdir/testdir/a
2517 </pre>
2518
2519 SECTION(«Further Reading»)
2520 <ul>
2521 <li> <a href="https://lwn.net/Articles/411845/">Ghosts of Unix Past:
2522 a historical search for design patterns</a>, by Neil Brown. </li>
2523
2524 <li> W. Richard Stevens: Advanced Programming in the Unix
2525 Environment. Addison Wesley. </li>
2526
2527 </ul>