Unix Concepts: Use <th> for table headers.
[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 <th> &nbsp;&nbsp; </th>
800 <th> Directories </th>
801 <th> Non-directories </th>
802 </tr> <tr>
803 <th> <code>r</code> </th>
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 <th> <code>w</code> </th>
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 <th> <code>x</code> </th>
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 <th> Octal Value </th>
862 <th> Symbolic Representation </th>
863 <th> Meaning </th>
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 the situation further.
1135 »)
1136
1137 HOMEWORK(«
1138 Given two paths, how can one tell if they refer to the same file?
1139 », «
1140
1141 Among other information, the metadata record of each file contains the
1142 so-called <em>inode number</em>, which uniquely identifies the file
1143 within the file system that contains the file. Therefore, if both
1144 paths are known to refer to files stored on the same file system,
1145 a comparison of the two inode numbers is sufficient to tell whether
1146 the two paths refer to the same file. The inode number can be obtained
1147 with the command <code>ls -i</code>.
1148
1149 In the general case one additionally has to check that the
1150 two <code>device IDs</code> which identify the underlying file
1151 systems are also identical. Like the inode number, the device ID
1152 is part of the metadata of the file. It can be obtained by running
1153 <code>stat(1)</code>.
1154
1155 »)
1156
1157 HOMEWORK(«
1158 Device nodes come in two flavors: Character and block devices. Explain
1159 the difference between the two device flavors.
1160 »)
1161
1162 HOMEWORK(«
1163
1164 <ul>
1165 <li> Nine of the 12 mode bits of each file are the permission
1166 bits. The remaining three are the <em>sticky</em>, <em>setuid</em>
1167 and <em>setgid</em> bits. Explain the purpose of each. </li>
1168
1169 <li> Run <code>find /usr/bin/ -perm -2000 -ls</code> to see all SUID
1170 executables in <code>/usr/bin</code>. Discuss why those programs have
1171 the SUID bit set. </li>
1172 </ul>
1173
1174 »)
1175
1176 HOMEWORK(«
1177 How many possible permission modes exist for a file or directory on
1178 a Unix System?
1179 », «
1180 There are nine permission bits that can be turned on and off
1181 independently. Hence we have 2^9=512 possibilities. When taking into
1182 account the three special bits (sticky, setuid, setgid), the number
1183 increases to 2^12=4096.
1184 »)
1185
1186 HOMEWORK(«
1187 Explain each command of the <a href="«#»symlink_madness">script</a>
1188 below. Show the arrangement of all files and links in a figure,
1189 drawing a directory as a circle and a file as a square. How many
1190 different paths exist for the file <code> a</code>? Discuss whether
1191 the question "What's the path of a given file?" makes sense.
1192
1193 », «
1194
1195 <div>
1196 <svg
1197 width="150" height="125"
1198 xmlns="http://www.w3.org/2000/svg"
1199 xmlns:xlink="http://www.w3.org/1999/xlink"
1200 >
1201 <marker
1202 id="slm_arrow"
1203 viewBox="0 0 10 10" refX="5" refY="5"
1204 markerWidth="4" markerHeight="4"
1205 orient="auto-start-reverse">
1206 <path d="M 0 0 L 10 5 L 0 10 z" />
1207 </marker>
1208 <circle
1209 fill="#ccc"
1210 stroke-width="1"
1211 stroke="black"
1212 r=20
1213 cx=51
1214 cy=21
1215 />
1216 <text
1217 x="51"
1218 y="21"
1219 stroke="black"
1220 text-anchor="middle"
1221 dy="0.3em"
1222 >foo</text>
1223 <rect
1224 fill="#ccc"
1225 stroke-width="1"
1226 stroke="black"
1227 x=1
1228 y=81
1229 width="40"
1230 height="40"
1231 rx="5"
1232 />
1233 <text
1234 x="21"
1235 y="101"
1236 stroke="black"
1237 text-anchor="middle"
1238 dy="0.3em"
1239 >a</text>
1240 <ellipse
1241 cx=81
1242 cy=101
1243 rx=30
1244 ry=20
1245 fill="#ccc"
1246 stroke-width="1"
1247 stroke="black"
1248 />
1249 <text
1250 x="81"
1251 y="101"
1252 stroke="black"
1253 text-anchor="middle"
1254 dy="0.3em"
1255 >testdir</text>
1256 <line
1257 stroke="black"
1258 stroke-width="1"
1259 x1="41"
1260 y1="45"
1261 x2="24"
1262 y2="75"
1263 />
1264 <line
1265 stroke="black"
1266 stroke-width="1"
1267 x1="61"
1268 y1="45"
1269 x2="77"
1270 y2="75"
1271 />
1272 <path
1273 d="
1274 M 118,101
1275 C 150,90 150,30 80,20
1276 "
1277 stroke-width="2"
1278 stroke="black"
1279 fill="none"
1280 marker-end="url(#slm_arrow)"
1281 />
1282 </svg>
1283 </div>
1284
1285 Since <code> foo/a</code>, <code> foo/testdir/a</code>, <code>
1286 foo/testdir/testdir/a </code> etc. all refer to the same file, there
1287 are infinitely many paths for the file <code> a</code>. Hence the
1288 question makes no sense: There is no such thing as <em> the </em>
1289 path to a file.
1290
1291 »)
1292
1293 HOMEWORK(«
1294
1295 Recall that the path component <code>..</code> refers to the
1296 parent directory. Give an example of a path to a directory where
1297 "parent directory" and "directory identified by the path obtained by
1298 removing the last path component" are different. Which of the two
1299 interpretations of <code>..</code> does bash apply when you type
1300 <code>cd ..</code> at the bash prompt?
1301
1302 »)
1303
1304 HOMEWORK(«
1305
1306 Is it possible to choose among all possible paths which refer to the
1307 same file a <em>canonical</em> path? That is, a shortest (counting
1308 characters) absolute path which does not contain any soft links?
1309
1310 », «
1311
1312 <p> The POSIX standard requires each Unix system library to provide
1313 the <code>realpath()</code> function which performs the following
1314 substitutions on the given path: First, the path to the current
1315 working directory is prepended if the given path is relative
1316 (does not begin with a slash). Second, symbolic links are replaced
1317 by their targets. Third, any occurrences of <code>/.</code> and
1318 <code>foo/..</code> are removed. The thusly transformed path is
1319 returned by the function as the canonical path. </p>
1320
1321 <p> Although each path can be canonicalized in this way, not all paths
1322 which refer to the same file give rise to the same canonical path. For
1323 example, <code>/tmp/foo</code> and <code>/tmp/bar</code> could refer
1324 to regular files which are hard links of each other. In this case the
1325 paths refer to the same file, yet the paths are different and already
1326 canonicalized. The same can happen when a file system (or a subtree
1327 of it) is <em>bind mounted</em>. That is, the file system tree is
1328 visible at two or more locations in the global directory tree. </p>
1329
1330 The message of this exercise is to convince the reader that it is
1331 incorrect to assume that two files are different because their paths
1332 are different.
1333
1334 »)
1335
1336 SECTION(«Processes»)
1337
1338 <p> A <em>program</em> consists of instructions and data stored in
1339 a regular file. A <em> user process</em> is an instance of a running
1340 program. This is in contrast to <em>kernel processes</em> which are
1341 created directly by the kernel and have no relationship to executable
1342 files. Since we shall only be concerned with user processes, we will
1343 refer to these as "processes" from now on. In this section we'll see
1344 how processes are created and removed. We will then take a closer look
1345 at the enviroment of a process and discuss how processes communicate
1346 with each other. </p>
1347
1348 SUBSECTION(«Process Tree, Zombies and Orphans»)
1349
1350 <p> When the system boots, there is only one process, the
1351 <em>init</em> process, which is created by the kernel at the end
1352 of the boot sequence by executing <code>/sbin/init</code>. All
1353 other processess are created from existing processes by means of
1354 the <code>fork(2)</code> system call. The process which called
1355 <code>fork(2)</code> is said to be the <em>parent</em> of the newly
1356 created <em>child</em>. After <code>fork(2)</code> returns, both
1357 parent and child are executing independently of each other. Both
1358 processes may call <code>fork(2)</code> again to create further
1359 processes. This gives rise to a tree structure where the processes
1360 are the nodes of the tree with init being the root node. The edges
1361 of the tree describe the parent-child relationships. </p>
1362
1363 <p> If there are more processes than CPUs, not all processes can
1364 run simultaneously. It is the mission of the kernel's <em>task
1365 scheduler</em> to assign processes to CPUs and to perform <em>context
1366 switches</em>. That is, to take away the CPU from a running process
1367 in order to give another process the chance to run. The scheduler
1368 has to choose the duration of each process' time slice and it must
1369 pick the process to switch to when the time slice of the current
1370 process has expired or the process gives up the CPU voluntarily, for
1371 example because it is waiting for an I/O operation to complete. This
1372 is a non-trivial task at least for modern multi-CPU systems with
1373 <em>non-uniform memory access</em> (NUMA) where the memory access times
1374 depend on the memory location and the processor core. Things don't
1375 get easier if the CPU clock speed can vary and/or scheduling must be
1376 power-aware to optimize battery time. To make good decisions, some
1377 information has to be provided by the processes or by a system-wide
1378 policy. One elementary way to prioritize certain processes over others
1379 is via <em>nice levels</em> which we shall discuss below. </p>
1380
1381 <p> The normal way for a process to terminate is to call
1382 <code>exit(3)</code> after it has done its work. This function
1383 transfers an integer value, the <em>exit status</em>, to the
1384 kernel. The exit status can only be retrieved by the parent of
1385 the terminating process. To illustrate this concept, imagine an
1386 interactive shell which creates one child each time the user enters
1387 a command. The children are short living while the parent, the shell,
1388 stays around for much longer. During command execution the parent needs
1389 to wait for its child to terminate. It may then want to tell whether
1390 the child has terminated successfully. To achieve this, the parent
1391 calls one of the <em>wait</em> system calls (<code>wait(2)</code>,
1392 <code>waitpid(2)</code>, <code>waitid(2)</code>) which block until the
1393 child has terminated, then return the child's exit status. After the
1394 child called <code>exit(3)</code> but before the parent has called
1395 one of the wait functions, the kernel needs to keep at least the
1396 exit status (and possibly further information) about the terminated
1397 child. During this time window the child has already terminated but
1398 a part of it still exists in kernel memory. Processes in this state
1399 are aptly called <em>zombies</em>. </p>
1400
1401 <p> Unlike in the shell scenario outlined above, a process might well
1402 have any number of children at the time it terminates. Its children
1403 then become <em>orphans</em> as they lose their parent. The kernel
1404 cannot simply remove the terminated process from the process tree
1405 because this would disconnect its orphaned children from the other
1406 processes in the tree, destroying the tree structure. To avoid this,
1407 orphans are <em>reparented to init</em>, that is, made children
1408 of the init process. This works because the init process never
1409 terminates. </p>
1410
1411 <p> There are several programs which show information about
1412 processes. The POSIX <code>ps(1)</code> command prints a list of
1413 processes. It has many options that control which processes are
1414 shown and how the output is formatted. Similar programs which are not
1415 covered by POSIX are <code>pstree(1)</code>, <code>top(1)</code> and
1416 <code>htop(1)</code>. The former shows the tree structure while the
1417 latter two provide a dynamic real-time view of the process tree. The
1418 exercises of this section invite the reader to become familiar with
1419 these essential programs. </p>
1420
1421 SUBSECTION(«File Execution»)
1422
1423 <p> When a process calls <code>fork(2)</code>, the newly created
1424 child process starts out as a copy of the calling process. However,
1425 the reason to create a new process is usually to let the child do
1426 something different than the parent. Therefore, <code>fork(2)</code>
1427 is often followed by a second system call which replaces the child
1428 process with a different program. There are several similar system
1429 calls which do this, with slight semantic differences. We refer to
1430 this family of system calls as the <em>exec system calls</em>. </p>
1431
1432 <p> All exec system calls receive a path argument from which they
1433 determine an executable file that contains the program to run. Linux
1434 and BSD store executables in <em>Executable and Linkable Format</em>
1435 (ELF). Executables are typically linked <em>dynamically</em>.
1436 That is, the dependent libraries (at least libc, but possibly many
1437 more) are loaded at runtime from separate files. This is in contrast
1438 to <em>static linking</em> which includes all dependencies in the
1439 executable, making the executable self-contained but also larger
1440 and harder to maintain. Regardless of the type of linking, when the
1441 program is loaded, it completely replaces the previously running
1442 program. Note that there can be more than one process at the same
1443 time which executes the same program. </p>
1444
1445 <p> Files in ELF format are called <em>native</em> executables because
1446 they contain machine instructions which can be executed directly
1447 by the CPU. Another type of executables are <em>scripts</em>,
1448 also known as <em>interpreter files</em>. Scripts are text files
1449 which start with the <em>shebang</em> (<code>#!</code>). They can
1450 not run directly but have to be <em>interpreted</em> at runtime
1451 by another program, the <em>interpreter</em>. Nevertheless, it is
1452 possible to execute a script as if it were a native executable:
1453 by passing the path to one of the exec system calls or by typing
1454 the path at the shell prompt. The exec system call recognizes that
1455 the given file is a script by investigating the first line, which
1456 contains the path to the interpreter after the shebang, optionally
1457 followed by options to the interpreter. The kernel then executes the
1458 interpreter rather than the script, passing the path to the script as
1459 an argument. For example, if <code>/foo/bar</code> is being executed,
1460 and the first line of this file is <code>#!/bin/sh</code>, the kernel
1461 executes <code>/bin/sh /foo/bar</code> instead. Popular interpreters
1462 besides <code>/bin/sh</code> include <code>/bin/bash</code>,
1463 <code>/usr/bin/perl</code>, <code>/usr/bin/python</code> and
1464 <code>/usr/bin/awk</code>. </p>
1465
1466 SUBSECTION(«File Descriptions and File Descriptors»)
1467
1468 <p> The kernel must always be aware of the set of all objects which are
1469 currently in use. This set is often called the <em>system-wide table
1470 of open files</em> although not all entries refer to files. In fact, an
1471 entry may refer to any object that supports I/O operations, for example
1472 a network socket. Each entry is called a <em>file description</em>,
1473 which is a somewhat unfortunate term that was coined by POSIX. A
1474 file description records information about the object itself as well
1475 as the current state of the reference, including the file offset,
1476 if applicable, and the <em>status flags</em> which affect how future
1477 I/O operations are going to be performed through this reference. </p>
1478
1479 <p> The kernel maintains for each process an array of pointers to file
1480 descriptions. Each such pointer is a <em>file descriptor</em>. Unlike
1481 files and file descriptions, a file descriptor always corresponds
1482 to a process and is identified by a non-negative number, the index
1483 into the pointer array of that process. This index is returned by
1484 system calls like <code>open(2)</code> or <code>socket(2)</code>.
1485 As far as user space programs are concerned, a file descriptor is
1486 synonymous with this integer. It can be regarded as an abstract
1487 <em>handle</em> that must be supplied to subsequent I/O operations
1488 like <code>read(2)</code> or <code>write(2)</code> to tell the system
1489 call the target object of the operation. </p>
1490
1491 <p> The shell automatically creates three file descriptors for each
1492 process which are identified by the integers 0, 1 and 2. They are
1493 called <em>stdin</em>, <em>stdout</em>, and <em>stderr</em>, which is
1494 short for <em>standard input/output/error</em>. It is possible, and in
1495 fact common, that all three file descriptors point to the same file
1496 description: the terminal device. Many command line tools read their
1497 input from stdin, write normal output to stdout, and error messages
1498 to stderr. For example, when the POSIX command <code>cat(1)</code>
1499 is invoked with no arguments, it reads data from stdin and writes
1500 the same data to stdout. </p>
1501
1502 SUBSECTION(«Signals»)
1503
1504 <p> Signals are another ancient Unix concept that dates back to the
1505 early 1970s and was standardized in POSIX long ago. This concept
1506 facilitates a rudimentary form of <em>inter process communication</em>
1507 (IPC) between unrelated processes. Signals can be regarded as software
1508 interrupts that transmit a notification event from the sending process
1509 to the target process. The event is sent <em>asynchronously</em>,
1510 meaning that the interruption can happen at any location of the code
1511 flow. </p>
1512
1513 <p> It is fair to say that most non-trivial programs, including
1514 scripts, have to deal with signals. All major scripting languages
1515 (bash, python, perl, ruby, etc.) provide an API for signal
1516 handling. The interpreter of the scripting language ends up calling
1517 the POSIX system functions, so we will only look at these. </p>
1518
1519 <p> Signals are identified by name or by a numerical ID. For example,
1520 <code>SIGINT</code> (interrupt from keyboard) is the name for signal
1521 number 2. POSIX defines 31 <em>standard signals</em> plus at least
1522 eight <em>real-time signals</em>. The standard signals can be
1523 subdivided according to the origin of the signal as follows. </p>
1524
1525 <dl>
1526 <dt> hardware related signals </dt>
1527
1528 <dd> These signals originate from <em>hardware traps</em> that force
1529 the CPU back into kernel mode. The kernel responds to the trap by
1530 generating a signal for the process that caused the trap. For example,
1531 a division by zero in a user space program triggers a hardware trap
1532 in the <em>floating point unit</em> (FPU) of the CPU. The kernel
1533 then generates the <code>SIGFPE</code> (floating-point exception)
1534 signal for the process. Another example for a signal that originates
1535 from a hardware trap is <code>SIGSEGV</code> (segmentation fault)
1536 which occurs when a process attempts to reference a memory address
1537 that has not been mapped (i.e., marked as valid) by the <em>memory
1538 management unit</em> (MMU) of the CPU. </dd>
1539
1540 <dt> kernel generated signals </dt>
1541
1542 <dd> Signals which originate from the kernel rather than from
1543 hardware. One example is <code>SIGCHLD</code> (child terminated),
1544 which is sent to the parent process when one of its child processes
1545 terminates. Another example is <code>SIGWINCH</code> (window resize),
1546 which is generated when the geometry of the controlling terminal of
1547 a process changes. </dd>
1548
1549 <dt> user-space generated signals </dt>
1550
1551 <dd> These signals can only originate from user space when a process,
1552 for example <code>kill(1)</code>, calls <code>raise(2)</code>
1553 or <code>kill(2)</code> to instruct the kernel to generate a
1554 signal. Examples are <code>SIGTERM</code>, which issues a termination
1555 request, and <code>SIGUSR1</code> and <code>SIGUSR2</code> which are
1556 reserved for use by application programs. </dd>
1557 </dl>
1558
1559 The following signals are used frequently and deserve to the described
1560 explicitly. We refer to <code>signal(7)</code> for the full list of
1561 signals and their semantics.
1562
1563 <dl>
1564 <dt> <code>SIGINT, SIGTERM</code> and <code>SIGKILL</code> </dt>
1565
1566 <dd> All three signals terminate the process by default.
1567 <code>SIGINT</code> is generated for the <em>foreground processes</em>
1568 when the <em>interrupt character</em> (CTRL+C) is pressed in a
1569 terminal. For example, if CTRL+C is pressed while the shell pipeline
1570 <code>find | wc </code> is executing, <code>SIGINT</code> is sent
1571 to both processes of the pipeline. <code>SIGTERM</code> is the
1572 default signal for the <code>kill(1)</code> command. It requests
1573 the target process to run its shutdown procedure, if any, then
1574 terminate. <code>SIGKILL</code> instructs the kernel to terminate the
1575 target process immediately, without giving the process the chance to
1576 clean up. This signal can originate from a process or from the kernel
1577 in response to running out of memory. To keep the system working, the
1578 kernel invokes the infamous <em>out of memory killer</em> (OOM killer)
1579 which terminates one memory-hungry process to free some memory. </dd>
1580
1581 <dt> <code>SIGSTOP</code>, <code>SIGTSTP</code> and <code>SIGCONT</code> </dt>
1582
1583 <dd> <code>SIGSTOP</code> instructs the task scheduler of the kernel to
1584 no longer assign any CPU time to the target process until the process
1585 is woken up by a subsequent <code>SIGCONT</code>. <code>SIGTSTP</code>
1586 (stop typed at terminal) stops all foreground processes of a terminal
1587 session. It is generated when the <em>stop character</em> (CTRL+Z)
1588 is pressed in a terminal. </dd>
1589 </dl>
1590
1591 <p> Processes may set the <em>signal disposition</em> of most signals
1592 to control what happens when the signal arrives. When no disposition
1593 has been set, the signal is left at its <em>default disposition</em> so
1594 that the <em>default action</em> is performed to deliver the signal.
1595 For most signals the default action is to terminate the process,
1596 but for others the default action is to <em>ignore</em> the signal.
1597 If the signal is neither ignored nor left at its default disposition,
1598 it is said to be <em>caught</em> by the process. To catch a signal the
1599 process must tell the kernel the address of a function, the <em>signal
1600 handler</em>, to call in order to deliver the signal. The set of
1601 signal dispositions of a process can thus be imagined as an array
1602 of function pointers with one pointer per possible signal. If the
1603 process catches the signal, the pointer points to the corresponding
1604 signal handler. A NULL pointer represents a signal that was left at
1605 its default disposition while the special value <code>SIG_IGN</code>
1606 indicates that the process explicitly asked to ignore this signal. </p>
1607
1608 <p> Signals can also be <em>blocked</em> and <em>unblocked</em>. When
1609 a signal is generated for a process that has it blocked, it remains
1610 <em>pending</em>. Pending signals cause no action as long as the
1611 signal remains blocked but the action will be performed once the
1612 signal gets unblocked. <code>SIGKILL</code> and <code>SIGSTOP</code>
1613 can not be caught, blocked, or ignored. </p>
1614
1615 <p> Real-time signals are similar to <code>SIGUSR1</code> and
1616 <code>SIGUSR2</code> in that they have no predefined meaning but
1617 can be used for any purpose. However, they have different semantics
1618 than the standard signals and support additional features. Most
1619 importantly, real-time signals are <em>queued</em>, meaning that in
1620 contrast to standard signals the same real-time signal can be pending
1621 multiple times. Also, the sending process may pass an <em>accompanying
1622 value</em> along with the signal. The target process can obtain this
1623 value from its signal handler along with additional information like
1624 the PID and the UID of the process that sent the signal. </p>
1625
1626 <p> Some system calls including <code>read(2)</code> and
1627 <code>write(2)</code> may block for an indefinite time. For
1628 example, reading from a network socket blocks until there is data
1629 available. What should happen when a signal arrives while the process
1630 is blocked in a system call? There are two reasonable answers: Either
1631 the system call is <em>restarted</em>, or the call fails with the
1632 <code>Interrupted system call</code> error. Unfortunately, different
1633 flavors of Unix handle this case differently by default. However,
1634 applications may request either behaviour by setting or clearing the
1635 <code>SA_RESTART</code> flag on a per-signal basis. </p>
1636
1637 SUBSECTION(«Environment of a Process»)
1638
1639 <p> Now that we have a rough understanding of processes we look
1640 closer at the information the kernel maintains for each process. We
1641 already discussed the array of file descriptors and the array of
1642 signal dispositions. Clearly both are process specific properties.
1643 As we shall see, there is much more what constitutes the environment
1644 of a process. </p>
1645
1646 <p> Each process is identified by a unique <em>process ID</em>
1647 (PID), which is a positive integer. The <code>init</code> process is
1648 identified by PID 1. PIDs are assigned in ascending order, but are
1649 usually restricted to the range 1..32767. After this many processes
1650 have been created, PIDs wrap and unused PIDs are recycled for new
1651 processes. Thus, on a busy system on which processes are created and
1652 terminated frequently, the same PID is assigned to multiple processes
1653 over time. </p>
1654
1655 <p> Not all processes call <code>fork(2)</code> to create a child
1656 process, but each process except the init process has a unique
1657 parent. As described before, this is either the "real" parent (the
1658 process which created the process earlier) or the init process that
1659 "adopted" the orphaned process in case the real parent terminated
1660 before the child. The process ID of the parent (PPID) is thus
1661 well-defined. A process can obtain its PID and PPID with the
1662 <code>getpid(2)</code> and <code>getppid(2)</code> system calls. </p>
1663
1664 <p> Each process runs on behalf of a user (possibly the superuser)
1665 which is identified by its <em>user ID</em> (UID) and belongs to
1666 one or more groups, identified by one or more <em>group IDs</em>
1667 (GIDs). The superuser is identified by UID zero. When we talked
1668 about the permission bits of files and directories, we said that
1669 suitable permissions are needed for system calls which operate on
1670 files (<code>open(2)</code>, <code>stat(2)</code>, etc.). A more
1671 precise statement is that the <em>process</em> which calls, say,
1672 <code>open(2)</code> needs to have these permissions. To decide this,
1673 the kernel needs to take into account the UID and GIDs of the process
1674 that called <code>open(2)</code>, the UID and the GID stored in the
1675 inode of the file that is being opened, and the permission bits of
1676 this file. The UID is also taken into account for <code>kill(2)</code>
1677 because unprivileged processes (non-zero UID) can only send signals
1678 to processes which run on behalf of the same user while the superuser
1679 may target any process. </p>
1680
1681 <p> Each process has a <em>current working directory</em> (CWD)
1682 associated with it. When the user logs in, the CWD of the login shell
1683 process is set to his <em>home directory</em>, which should always
1684 exist and have the read, write and execute permission bits set for
1685 the user. The CWD can later be changed with <code>chdir(2)</code>
1686 and be retrieved with <code>getcwd(3)</code>. The CWD is used as the
1687 starting point for path searches for relative paths. It affects most
1688 system calls which receive a path argument. For example, if the CWD
1689 is <code>/foo/bar</code> and the relative path <code>baz/qux</code>
1690 is passed to <code>open(2)</code>, the kernel will attempt to open
1691 the file which is identified by <code>/foo/bar/baz/qux</code>. </p>
1692
1693 <p> Many programs accept arguments to control their behavior.
1694 In addition to the path to the program that is to be executed,
1695 all variants of the exec system calls receive an array of arguments
1696 called the <em>argument vector</em>. For example, when the command
1697 <code>ls -l foo</code> is executed, the argument vector contains
1698 the two strings <code>"-l"</code> and <code>"foo"</code>. Note that
1699 the argument vector is not part of the program but is tied to the
1700 process. It is passed to the main function at startup so that the
1701 program may evaluate it and act accordingly. </p>
1702
1703 <p> Another way to pass information to a program is via <em>environment
1704 variables</em>. Environment variables are strings of the form
1705 <code>name=value</code>. POSIX describes the API to maintain the
1706 environment variables of a process. Environment variables are set
1707 with <code>setenv(3)</code> or <code>putenv(3)</code>, the value of a
1708 variable can be retrieved with <code>getenv(3)</code>, and a variable
1709 and its value can be deleted with <code>unsetenv(3)</code>. The set of
1710 environment variables is sometimes called the <em>environment</em>
1711 of the process, although we use this term in a broader sense to
1712 describe the entirety of all metadata maintained by the kernel about
1713 the process, including but not limited to environment variables. </p>
1714
1715 <p> Each process also has about a dozen <em>resource limits</em>
1716 that can be set and queried with the POSIX <code>setrlimit(2)</code>
1717 and <code>getrlimit(2)</code> functions. Each limit controls a
1718 different aspect. For example, <code>RLIMIT_CPU</code> limits the
1719 CPU time the process is allowed to use and <code>RLIMIT_NOFILE</code>
1720 controls how many open files it may have at a time. For each resource
1721 there is a <em>soft</em> and a <em>hard</em> limit. The kernel
1722 enforces the value stored as the soft limit. This value may be set
1723 by an unprivileged process to any value between zero and the hard
1724 limit. Unprivileged processes may also reduce (but not increase) their
1725 hard limits. Once a hard limit is reduced, it can not be increased
1726 any more. For <code>RLIMIT_CPU</code> a special convention applies:
1727 If the soft limit is reached, the kernel sends <code>SIGXCPU</code>
1728 (CPU time limit exceeded) to notify the process about this fact so
1729 that it can terminate orderly (e.g., remove temporary files). When
1730 the hard limit is reached, the kernel terminates the process as if
1731 it received <code>SIGKILL</code>. </p>
1732
1733 <p> The <em>nice level</em> of a process provides a hint for
1734 the task scheduler to give the process a lower or higher priority
1735 relative to other processes. Nice levels range between -20 and 19. A
1736 high nice level means that the process wants to be nice to other
1737 processes, that is, should run with reduced priority. Low nice levels
1738 indicate important processes that should be prioritized over other
1739 processes. The default nice level is zero. Unprivileged users may
1740 set the nice level of new processes with the <code>nice(1)</code>
1741 command to any non-negative value. They can also increase the nice
1742 level of their existing processes with <code>renice(1)</code>, but
1743 never decrease it. The superuser, however, may set the nice level
1744 of any process to an arbitrary value in the valid range. </p>
1745
1746 <p> The bulk of the properties discussed so far are inherited by the
1747 child after a <code>fork(2)</code>. Specifically, the child gets the
1748 same array of file descriptors and signal dispositions as its parent,
1749 runs on behalf of the same user, has the same working directory,
1750 the same resource limits and nice level, and also the same set
1751 of environment variables with identical values. The PID and PPID,
1752 however, are different of course. </p>
1753
1754 <p> After a process has called an exec function to replace itself with
1755 a new program, its signal handlers no longer exist because they were
1756 part of the program code which has been replaced. Therefore the exec
1757 system calls reset the disposition of all signals that were caught to
1758 the default disposition. Signals that were being ignored keep being
1759 ignored, however. </p>
1760
1761 SUBSECTION(«The Process Filesystem»)
1762
1763 <p> Although not covered by POSIX, at least Linux, NetBSD and FreeBSD
1764 provide information about processes via the <em>process filesystem</em>
1765 (procfs), which is usually mounted on <code>/proc</code>. The process
1766 filesystem is a <em>pseudo-filesystem</em>, i.e., it has no underlying
1767 storage device. Files and directories are faked by the kernel as they
1768 are accessed. Each process is represented by a numerical subdirectory
1769 of <code>/proc</code> which is named by the PID. For example,
1770 <code>/proc/1</code> represents the init process. The aforementioned
1771 process utilities (<code>ps(1)</code>, <code>top(1)</code>, etc.) read
1772 the contents of the process filesystem in order to do their job. <p>
1773
1774 <p> Each <code>/proc/[pid]</code> directory contains the same set
1775 of files although this set is different between Unixes. These files
1776 expose much of the environment of the process to user space. The Linux
1777 procfs implementation provides text files named <code>environ</code>
1778 and <code>limits</code> which contain the current environment and
1779 the resource limits of the process, respectively. Moreover, the
1780 file descriptor array of each process is exposed in the files of
1781 the <code>/proc/[pid]/fd</code> directory. Linux and NetBSD (but not
1782 FreeBSD) also provide a <code>cwd</code> soft link which points to
1783 the current working directory of the process. </p>
1784
1785 SUBSECTION(«Pipes and Redirections»)
1786
1787 <p> The <code>pipe(2)</code> system call takes no arguments and
1788 creates two file descriptors for the calling process which are tied
1789 together as a unidirectional first in, first out data channel that
1790 works just like a fifo, but without any files being involved. One
1791 file descriptor is the <em>read end</em> of the pipe, the other is
1792 the <em>write end</em>. Data written to the write end is buffered by
1793 the kernel and can be obtained by reading from the read end. </p>
1794
1795 <p> One application of pipes is communication between
1796 related processes. A process first creates a pipe, then calls
1797 <code>fork(2)</code> to create a child process. The child inherits
1798 a copy of both pipe file descriptors. Hence the parent process can
1799 communicate with the child by writing a message to the write end of
1800 the pipe for the child to read. </p>
1801
1802 <p> The POSIX <code>dup(2)</code> and <code>dup2(2)</code> system
1803 calls allow a process to manipulate the entries of its file descriptor
1804 array. In particular the standard file descriptors 0, 1, and 2 can be
1805 replaced. By doing so before performing an exec system call, it can
1806 be arranged that the replacement program starts with, say, its stdout
1807 file descriptor be redirected to the write end of a pipe. Note that
1808 the replacement program does not need any modifications for this to
1809 work, and might not even be aware of the fact that it is not writing
1810 its output to the terminal as usual. </p>
1811
1812 <p> Shells employ this technique to implement the <code>|</code>
1813 operator which "pipes" the output of one command "into" another
1814 command. For example, the pipeline <code>ls | wc</code> works
1815 as follows: First the shell creates a pipe, then it calls
1816 <code>fork(2)</code> twice to create two processes which both
1817 get a copy of the two pipe file descriptors. The first process
1818 replaces its stdout file descriptor with the write end of the
1819 pipe and performs an exec system call to replace itself with the
1820 <code>ls(1)</code> program. The second process replaces its stdin
1821 file descriptor with the read end of the pipe and replaces itself
1822 with <code>wc(1)</code>. Since <code>ls(1)</code> writes to stdout
1823 and <code>wc(1)</code> reads from stdin, <code>wc(1)</code> processes
1824 the output of <code>ls(1)</code>. </p>
1825
1826 <p> Note that this trick does not work to establish a connection
1827 between two <em>existing</em> processes because it depends on file
1828 descriptor inheritance across <code>fork(2)</code>. In the general
1829 case one has to fall back to sockets or fifos to create the data
1830 channel. </p>
1831
1832 SUBSECTION(«Stdio»)
1833
1834 <p> The POSIX standard requires a compliant Unix system to provide
1835 a collection of functions that let applications perform input and
1836 output by means of operations on <em>streams</em>. This programming
1837 interface, known as <em>stdio</em> for <em>standard input/output</em>,
1838 is part of every Unix system since 1979. Every program which contains
1839 a <code>printf(3)</code> statement relies on stdio. </p>
1840
1841 <p> The stdio functions are implemented as part of libc on top of the
1842 <code>open(2)</code>, <code>read(2)</code> and <code>write(2)</code>
1843 system calls which are implemented in the kernel. Roughly speaking,
1844 stdio replaces the file descriptor API by a more abstract API
1845 which centers around streams. A stream is an opaque data structure
1846 which comprises a file descriptor and an associated data buffer for
1847 I/O. Each program has three predefined streams which correspond to
1848 the three standard file descriptors (stdin, stdout and stderr). The
1849 stdio API contains well over 50 functions to create and maintain
1850 streams and to perform I/O on streams. These functions take care of
1851 the characteristics of the underlying file description. For example,
1852 they automatically try to select the optimal I/O buffer size. </p>
1853
1854 <p> Many applications rely on stdio because of convenience. For
1855 one, the buffers for <code>read(2)</code> and <code>write(2)</code>
1856 must be allocated and freed explicitly by the application, and care
1857 must be taken to not overflow these buffers. With stdio, this task
1858 is done by the stdio library. Second, <em>formatted</em> I/O is
1859 much easier to do with the stdio functions because the programmer
1860 only has to provide a suitable <em>format string</em> to convert
1861 between the machine representation and the textual representation of
1862 numbers. For example, by passing the format string <code>"%f"</code>
1863 to <code>scanf(3)</code>, the programmer tells the stdio library to
1864 read a floating point number stored in textual representation from the
1865 specified stream, convert it to machine representation and store it
1866 in the given variable. The <code>fprintf(3)</code> function works the
1867 other way round: the value is converted from machine representation
1868 to text, and this text is written to the stream. Both functions can
1869 deal with various formats, like scientific notation for floating
1870 point numbers (e.g., 0.42E-23). With stdio it is easy to customize
1871 the formatted output, for example add leading zeros or select the
1872 number of decimal digits in the textual representation of a floating
1873 point number. </p>
1874
1875 <p> Another reason why many programs rely on stdio is that it performs
1876 <em>buffered</em> I/O. With buffered I/O not each read/write operation
1877 results in a system call. Instead, data read from or written to the
1878 stream is first stored in the user space buffer that is associated
1879 with the stream. This is a performance improvement for applications
1880 which perform many small I/O operations because every system call
1881 incurs some overhead. Buffers may be <em>flushed</em> explicitly by
1882 calling <code>fflush(3)</code>, or implicitly by the stdio library. The
1883 criteria which cause an implicit flush depend on the <em>buffering
1884 type</em> of the stream. Three buffering types exist. </p>
1885
1886 <dl>
1887 <dt> unbuffered </dt>
1888
1889 <dd> The stdio library does not buffer any reads or writes. Instead,
1890 each I/O operation results in a <code>read(2)</code> or
1891 <code>write(2)</code> system call. By default the stderr stream is
1892 unbuffered to display error messages as quickly as possible. </dd>
1893
1894 <dt> line buffered </dt>
1895
1896 <dd> System calls are performed when a newline character is
1897 encountered. This buffering type applies by default to interactive
1898 sessions where the file descriptor of the stream refers to a terminal
1899 device (as determined by <code>isatty(3)</code>). </dd>
1900
1901 <dt> fully buffered </dt>
1902
1903 <dd> I/O takes place only if the buffer of the stream is empty/full. By
1904 default, if the file descriptor refers to a regular file, the
1905 stream is fully buffered. POSIX requires that stderr is never fully
1906 buffered. </dd>
1907 </dl>
1908
1909 <p> The exercises on stdio focus on the three different buffering
1910 types because this is a common source of confusion. </p>
1911
1912 SUBSECTION(«The Virtual Address Space of a Process»)
1913
1914 <p> Isolation refers to the concept that each process gets its own
1915 <em>virtual address space</em>. A rough understanding of the memory
1916 management system and the layout of the virtual address space of
1917 a process helps to locate the source of common problems like the
1918 infamous <code>segmentation fault</code> error, and to realize that
1919 putatively simple questions such as "how much memory is my process
1920 currently using?" are in fact not simple at all, and need to be made
1921 more precise before they can be answered. </p>
1922
1923 <div>
1924
1925 define(«vas_width», «200»)
1926 define(«vas_height», «300»)
1927 define(«vas_vmem_left_margin», «5»)
1928 define(«vas_vmem_top_margin», «5»)
1929 define(«vas_mem_width», «20»)
1930 define(«vas_gap_width», «30»)
1931 define(«vas_vmem_height», «140»)
1932 define(«vas_vmem_color», «#34b»)
1933 define(«vas_pmem_height», «100»)
1934 define(«vas_pmem_color», «#7e5»)
1935 define(«vas_vmem_unmapped_color», «#a22»)
1936 define(«vas_vmem_swapped_color», «yellow»)
1937 define(«vas_pmem_unavail_color», «orange»)
1938 define(«vas_disk_gap», «15»)
1939 define(«vas_disk_height», «20»)
1940 define(«vas_disk_color», «grey»)
1941 define(«vas_x1», «vas_vmem_left_margin()»)
1942 define(«vas_x2», «eval(vas_x1() + vas_mem_width())»)
1943 define(«vas_x3», «eval(vas_x2() + vas_gap_width())»)
1944 define(«vas_x4», «eval(vas_x3() + vas_mem_width())»)
1945
1946 define(«vas_membox», «
1947 <rect
1948 fill="$1" stroke="black" stroke-width="1"
1949 x="eval(vas_vmem_left_margin() + $3)"
1950 y="vas_vmem_top_margin()"
1951 width="vas_mem_width()" height="$2"
1952 />
1953 »)
1954 define(«vas_vmem_unmapped_box», «
1955 <rect
1956 fill="vas_vmem_unmapped_color()" stroke="black" stroke-width="1"
1957 x="eval(vas_vmem_left_margin())"
1958 y="eval(vas_vmem_top_margin() + $1)"
1959 width="vas_mem_width()"
1960 height="eval($2)"
1961 />
1962
1963 »)
1964 define(«vas_vmem_swapped_box», «
1965 <rect
1966 fill="vas_vmem_swapped_color()" stroke="black" stroke-width="1"
1967 x="eval(vas_vmem_left_margin())"
1968 y="eval(vas_vmem_top_margin() + $1)"
1969 width="vas_mem_width()"
1970 height="eval($2)"
1971 />
1972
1973 »)
1974 define(«vas_pmem_unavail_box», «
1975 <rect
1976 fill="vas_pmem_unavail_color()" stroke="black" stroke-width="1"
1977 x="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width())"
1978 y="eval(vas_vmem_top_margin() + $1)"
1979 width="vas_mem_width()"
1980 height="$2"
1981 />
1982
1983 »)
1984 define(«vas_vmem_hline», «
1985 <line
1986 x1="vas_vmem_left_margin()"
1987 y1="eval(vas_vmem_top_margin() + $1)"
1988 x2="eval(vas_vmem_left_margin() + vas_mem_width())"
1989 y2="eval(vas_vmem_top_margin() + $1)"
1990 stroke-width="1"
1991 stroke="black"
1992 />
1993
1994 »)
1995
1996 define(«vas_pmem_hline», «
1997 «<!-- pmem hline -->»
1998 <line
1999 x1="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width())"
2000 y1="eval(vas_vmem_top_margin() + $1)"
2001 x2="eval(vas_vmem_left_margin() + 2 * vas_mem_width() + vas_gap_width())"
2002 y2="eval(vas_vmem_top_margin() + $1)"
2003 stroke-width="1"
2004 stroke="black"
2005 />
2006
2007 »)
2008 define(«vas_arrow», «
2009 <line
2010 x1="eval(vas_vmem_left_margin() + vas_mem_width())"
2011 y1="eval(vas_vmem_top_margin() + $1)"
2012 x2="eval(vas_vmem_left_margin() + vas_mem_width() + vas_gap_width() - 2)"
2013 y2="eval(vas_vmem_top_margin() + $2)"
2014 stroke-width="1"
2015 stroke="black"
2016 marker-end="url(#arrow)"
2017 />
2018 »)
2019 define(«vas_disk», «
2020 <rect
2021 fill="vas_disk_color()" stroke="black" stroke-width="1"
2022 x="vas_x3()"
2023 y="eval(vas_vmem_top_margin() + vas_pmem_height()
2024 + vas_disk_gap())"
2025 width="eval(vas_x4() - vas_x3())"
2026 height="eval(vas_disk_height())"
2027 />
2028 <ellipse
2029 cx="eval(vas_x3() + vas_mem_width() / 2)"
2030 cy="eval(vas_vmem_top_margin() + vas_pmem_height() + vas_disk_gap())"
2031 rx="eval(vas_mem_width() / 2)"
2032 ry="eval(vas_mem_width() / 4)"
2033 fill="vas_disk_color()" stroke="black"
2034 />
2035 <ellipse
2036 cx="eval(vas_x3() + vas_mem_width() / 2)"
2037 cy="eval(vas_vmem_top_margin() + vas_pmem_height()
2038 + vas_disk_gap() + vas_disk_height())"
2039 rx="eval(vas_mem_width() / 2)"
2040 ry="eval(vas_mem_width() / 4)"
2041 fill="vas_disk_color()" stroke="black"
2042 />
2043 »)
2044
2045 <svg
2046 width="vas_width()" height="vas_height()"
2047 viewBox="0 0 100 eval(100 * vas_height() / vas_width())"
2048 xmlns="http://www.w3.org/2000/svg"
2049 xmlns:xlink="http://www.w3.org/1999/xlink"
2050 >
2051 <marker
2052 id="arrow"
2053 viewBox="0 0 10 10" refX="5" refY="5"
2054 markerWidth="4" markerHeight="4"
2055 orient="auto-start-reverse">
2056 <path d="M 0 0 L 10 5 L 0 10 z" />
2057 </marker>
2058 vas_membox(«vas_vmem_color()», «vas_vmem_height()», «0»)
2059 vas_membox(«vas_pmem_color()», «vas_pmem_height()»,
2060 «eval(vas_gap_width() + vas_mem_width())»)
2061 vas_vmem_hline(«10»)
2062 vas_vmem_hline(«40»)
2063 vas_vmem_unmapped_box(«40», «20»)
2064 vas_vmem_swapped_box(«60», «60»)
2065
2066 vas_pmem_unavail_box(«0», «10»)
2067 vas_pmem_hline(«20»)
2068 vas_pmem_unavail_box(«20», «30»)
2069 vas_pmem_hline(«80»)
2070
2071 vas_arrow(«5», «15»)
2072 vas_arrow(«25», «65»)
2073 vas_arrow(«130», «90»)
2074 vas_disk()
2075 vas_arrow(«90», «eval(vas_pmem_height() + vas_disk_gap()
2076 + vas_disk_height() / 2)»)
2077 </svg>
2078 </div>
2079
2080 <p> Virtual memory is an abstraction of the available memory resources.
2081 When a process reads from or writes to a memory location, it refers
2082 to <em>virtual addresses</em> (illustrated as the left box of the
2083 diagram). Virtual addresses are mapped by the MMU to <em>physical
2084 addresses</em> which refer to physical memory locations (right
2085 box). The <em>mapped</em> virtual address space of a process is a
2086 collection of ranges of virtual addresses which correspond to physical
2087 memory addresses (blue areas). By storing less frequently-accessed
2088 chunks of virtual memory (yellow) on the swap area (grey), applications
2089 can use more memory than is physically available. In this case the
2090 size of the valid virtual addresses (blue and yellow areas together)
2091 exceeds the amount of physical memory (orange and green areas). Any
2092 attempt to access an unmapped memory location (red and yellow areas)
2093 results in a <em>page fault</em>, a hardware trap which forces the CPU
2094 back into kernel mode. The kernel then checks whether the address is
2095 valid (yellow) or invalid (red). If it is invalid, the kernel sends
2096 <code>SIGSEGV</code>, which usually terminates the process with
2097 the <code>segmentation fault</code> error. Otherwise it allocates
2098 a chunk of unused physical memory, copies the chunk from the swap
2099 area to the newly allocated memory and adjusts the mapping (i.e.,
2100 a yellow part becomes blue). The virtual memory concept increases
2101 stability and security because no process can access physical memory
2102 which belongs to the kernel or to other processes (orange areas). </p>
2103
2104 <p> We've already seen that the <code> fork(2) </code> system call
2105 creates a new process as a duplicate of the calling process. Since
2106 the virtual address space of the calling process (a) might be large
2107 and (b) is likely to be replaced in the child by a subsequent call
2108 to an exec function, it would be both wasteful and pointless to
2109 copy the full address space of the parent process to the child. To
2110 implement <code> fork(2) </code> efficiently, operating systems
2111 employ an optimization strategy known as <em> Copy on Write </em>
2112 (CoW). The idea of CoW is that if multiple callers ask for resources
2113 which are initially indistinguishable, you can give them pointers to
2114 the same resource. This function can be maintained until a caller
2115 tries to modify its copy of the resource, at which point a true
2116 private copy is created to prevent the changes becoming visible to
2117 everyone else. The primary advantage is that if a caller never makes
2118 any modifications, no private copy needs ever be created. The <code>
2119 fork(2) </code> system call marks the pages of the virtual address
2120 space of both the parent and the child process as CoW by setting a
2121 special bit in the <em> page table entry </em> which describes the
2122 mapping between virtual and physical addresses of the MMU. As for
2123 invalid memory accesses, the attempt to write to a CoW page results
2124 in a page fault that puts the CPU back into kernel mode. The kernel
2125 then allocates a new memory page on behalf of the process, copies
2126 the contents of the page which caused the fault, changes the page
2127 table mappings for the process accordingly and returns to user space.
2128 This all happens transparently to the process. </p>
2129
2130 <div>
2131 define(«asl_width», «300»)
2132 define(«asl_height», «400»)
2133 define(«asl_top_margin», «10»)
2134 define(«asl_text_width», «35»)
2135 define(«asl_mem_width», «25»)
2136 define(«asl_mem_color_env», «#fc8»)
2137 define(«asl_mem_color_stack», «#8fc»)
2138 define(«asl_mem_color_empty», «#ccc»)
2139 define(«asl_mem_color_heap», «#c8f»)
2140 define(«asl_mem_color_bss», «#8cf»)
2141 define(«asl_mem_color_data», «#cf8»)
2142 define(«asl_mem_color_text», «#f8c»)
2143 define(«asl_font_size», «5»)
2144
2145 define(«asl_arrow», «
2146 <line
2147 x1="0"
2148 y1="$1"
2149 x2="eval(asl_text_width() - 2)"
2150 y2="$1"
2151 stroke-width="1"
2152 stroke="black"
2153 marker-end="url(#arrow)"
2154 />
2155 »)
2156 define(«asl_arrow_text», «
2157 <text
2158 x="0"
2159 y="$1"
2160 font-size="asl_font_size()"
2161 >
2162 $2
2163 </text>
2164 »)
2165
2166 dnl $1: y0, $2; height, $3: color, $4: high arrow text
2167 dnl $5: low arrow text, $6: desc
2168
2169 define(«asl_box», «
2170 <rect
2171 stroke="black"
2172 stroke-width="1"
2173 x="asl_text_width()"
2174 y="eval($1 + asl_top_margin())"
2175 height="$2"
2176 fill="$3"
2177 width="asl_mem_width()"
2178 />
2179 ifelse(«$4», «», «», «
2180 asl_arrow(«eval($1 + asl_top_margin())»)
2181 asl_arrow_text(«eval($1 + asl_top_margin() - 2)», «$4»)
2182 »)
2183 ifelse(«$5», «», «», «
2184 asl_arrow(«eval($1 + $2 + asl_top_margin())»)
2185 asl_arrow_text(«eval(asl_top_margin()
2186 + $1 + $2 - 2)», «$5»)
2187 »)
2188 <text
2189 x="eval(asl_text_width() + asl_mem_width() + 2)"
2190 y="eval($1 + $2 / 2 + asl_top_margin())"
2191 dy="0.3em"
2192 font-size="asl_font_size()"
2193 >
2194 $6
2195 </text>
2196 »)
2197
2198 <svg
2199 width="asl_width()" height="asl_height()"
2200 viewBox="0 0 100 eval(100 * asl_height() / asl_width())"
2201 xmlns="http://www.w3.org/2000/svg"
2202 xmlns:xlink="http://www.w3.org/1999/xlink"
2203 >
2204 asl_box(«0», «10», «asl_mem_color_env», «2^64 - 1», «»,
2205 «Environment»)
2206 asl_box(«10», «15», «asl_mem_color_stack», «», «base pointer»,
2207 «Stack»)
2208 asl_box(«25», «30», «asl_mem_color_empty», «», «break point»,
2209 «Empty»)
2210 asl_box(«55», «35», «asl_mem_color_heap», «», «», «Heap»)
2211 asl_box(«90», «10», «asl_mem_color_bss», «», «», «BSS»)
2212 asl_box(«100», «10», «asl_mem_color_data», «», «», «Data»)
2213 asl_box(«110», «10», «asl_mem_color_text», «», «0», «Text»)
2214 </svg>
2215 </div>
2216
2217 <p> The diagram on the left illustrates the layout of the virtual
2218 address space of a process. At the top of the address space are the
2219 argument vector and the environment variables. The <em>stack</em>
2220 stores the local variables of the functions which are currently
2221 being called, plus house-keeping data like the return addresses
2222 of these functions. As more functions are called, the stack grows
2223 downwards towards the lower addresses. Its current lower end is
2224 called the <em> base pointer</em>. The other variable area of the
2225 address space is the <em>heap</em>, which contains the memory that
2226 has been allocated on behalf of the process, for example with <code>
2227 malloc(3)</code>. As the process allocates more memory, the heap grows
2228 upwards, towards the stack. The current end of the heap is called the
2229 <em> break point</em>. The lower part of the address space contains
2230 three segments of fixed size. The <em>text</em> segment contains the
2231 compiled machine instructions of the executable, the <em>data</em>
2232 segment contains the initialized variables which are already known
2233 at compile time. Finally, the <em>BSS</em> segment is allocated and
2234 zeroed at execution time. This segment contains variables which should
2235 initialized to zero at startup. Unlike the data segment it is not
2236 stored in the executable. BSS stands for "Block Started by Symbol",
2237 which is a historic name coined in the 1950s. It has no relation to
2238 the real meaning of the segment. </p>
2239
2240 The exercises of this section invite the reader to look at the virtual
2241 address space of running processes to learn what happens when a
2242 dynamically-linked executable is being executed and how the resulting
2243 memory maps affect the virtual address space of the newly created
2244 process.
2245
2246 EXERCISES()
2247
2248 <ul>
2249 <li> Examine your own processes with <code>htop</code>, <code>ps
2250 ux</code> and <code>pstree -panuch $LOGNAME</code>. </li>
2251
2252 <li> Run <code>ls -l /proc/$$</code> and examine the environment of
2253 your shell process. </li>
2254
2255 <li> Run <code>kill -l</code> and discuss the meaning of signals
2256 1-15. Use <code>signal(7)</code> as a reference. </li>
2257
2258 <li> Create a zombie process: run <code>sleep 100&</code>. From
2259 another terminal, send <code>SIGSTOP</code> to the parent process
2260 of the sleep process (the shell), then send <code>SIGKILL</code>
2261 to the sleep process. Run <code>cat /proc/$PID/status</code> where
2262 <code>$PID</code> is the process ID of the sleep process. </li>
2263
2264 <li> Run <code>echo $$</code> to obtain the PID of an interactive
2265 shell that is running in a terminal. Send the <code>SIGSTOP</code>
2266 and <code>SIGCONT</code> signals to this PID from another terminal
2267 and see what happens when you type in the terminal that contains the
2268 stopped shell process. </li>
2269
2270 <li> The <code>ping(8)</code> utility catches <code>SIGQUIT</code>.
2271 In one terminal execute <code>ping localhost</code>. While this
2272 command runs in an endless loop, send <code>SIGQUIT</code> to the
2273 ping process from another terminal and see what happens. </li>
2274
2275 <li> Read <code>kill(2)</code> to learn what <code>kill -9 -1</code>
2276 does. Run this command if you are brave. </li>
2277
2278 <li> Why doesn't the <a href="«#»cd_script">cd script</a> work as
2279 expected? </li>
2280
2281 <li> Explain the difference between the two commands <code>X=foo
2282 bar</code> and <code>X=foo; bar</code>. </li>
2283
2284 <li> Run <code>set</code> and examine the environment variables of
2285 an interactive shell session. </li>
2286
2287 <li> Check this <a
2288 href="https://public-inbox.org/git/Pine.LNX.4.64.0609141023130.4388@g5.osdl.org/">email</a>
2289 from Linus Torvalds about why stdio is not that simple at all. </li>
2290
2291 <li> Run the command <code>ls / /does-not-exist</code>, redirect
2292 stdout and stderr to different files. </li>
2293
2294 <li> Consider the following shell code which uses stdio to first write
2295 to stdout, then to stderr. <code>echo foo; echo bar 1>&2</code>. Which
2296 circumstances guarantee that the "foo" line appears before the "bar"
2297 line in the output? </li>
2298
2299 <li> In the pipeline <code> foo | bar</code>, what is the
2300 buffering type of the file descriptor which corresponds to
2301 the <code> stdin </code> stream of the <code> bar </code>
2302 process? </li>
2303
2304 <li> Assume <code>foo</code> is a log file which increases due to
2305 some process appending data to it. Explain why the command <code>
2306 tail -f foo | while read; do echo new data; done </code> does not
2307 work as expected. Fix the flaw by changing the buffering type with
2308 <code>stdbuf(1)</code>. </li>
2309
2310 <li> Run <code>sleep 100 > /dev/null &</code>, examine open
2311 files of the sleep process by looking at suitable files in
2312 <code>/proc</code>. Do the same with <code>sleep 100 | head
2313 &</code>. </li>
2314
2315 <li> Run <code>ldd /bin/sh</code> and explain what happens when a
2316 shell is executed. </li>
2317
2318 <li> On a Linux system, run <code>cat /proc/$$/maps</code> or
2319 <code>pmap -x $$</code> to see the address space layout of your
2320 shell. Check <code>Documentation/filesystems/proc.txt</code>
2321 in the linux kernel source tree for the format of
2322 <code>/proc/$$/maps</code>. </li>
2323
2324 <li> Run <code>cat /proc/$$/smaps</code> and examine the values of
2325 the heap section. </li>
2326
2327 <li> Assume some program allocates a lot of memory so that the size of
2328 the valid virtual addresses is 1T large. Assume further that a software
2329 bug causes the content of a pointer variable to be overwritten with
2330 random garbage. Determine the probability that this pointer variable
2331 contains a valid address (assuming a 64 bit system). </li>
2332 </ul>
2333
2334 HOMEWORK(«
2335
2336 Explain how <code>PR_SET_CHILD_SUBREAPER</code> works and possible
2337 use-cases for this (Linux) feature.
2338
2339 »)
2340
2341 HOMEWORK(«
2342
2343 Explain in one paragraph of text the purpose of the <em>file
2344 creation mask</em> (also known as <em>umask</em>) of a process.
2345
2346 »)
2347
2348 HOMEWORK(«
2349
2350 When we said that each process runs on behalf of a user and that the
2351 ID of this user is part of the process metadata, we were simplifying
2352 matters. There are actually three different UIDs and three different
2353 GIDs: the <em>real UID</em>, the <em>effective UID</em>, and the
2354 <em>saved set-user ID</em>, and analogous for the group IDs. Explain
2355 the purpose of the three UIDs.
2356
2357 »)
2358
2359
2360 HOMEWORK(«
2361
2362 On a multi-CPU system the performance of a program can be
2363 enhanced by allowing for multiple flows of control. This is the
2364 idea behind <em>threads</em>, which are also called <em>lightweight
2365 processes</em>. Give an overview of threads, summarize the POSIX thread
2366 API (see <code>pthreads(7)</code>) and explain how the Linux-specific
2367 <code>clone(2)</code> system call can used to implement threads.
2368
2369 »)
2370
2371 HOMEWORK(«
2372
2373 Explain what the command <code>find /etc > /dev/null</code> does,
2374 and why you get some error messages. Assume you'd like to extract
2375 only those error messages which contain the string "lvm". Explain
2376 why <code>find /etc > /dev/null | grep lvm</code> does not work as
2377 expected. Come up with a similiar command that works.
2378
2379 », «
2380
2381 The command traverses the <code>/etc</code> directory recursively and
2382 prints all files and directories it encounters during the traversal to
2383 stdout. Since stdout is redirected to the NULL device by the <code>>
2384 /dev/null</code> construct, only the stderr stream containing the error
2385 messages makes it to the terminal. This includes all subdirectories
2386 of <code>/etc</code> which cannot be traversed due to insufficient
2387 permissions (no "r" bit set). The proposed <code>find | grep</code>
2388 command does not work since the <code>|</code> operator is evaluated
2389 <em>before</em> any redirections specified by the find command
2390 take place. More precisely, stdout of the find process is redirected
2391 <em>twice</em>: First to one end of the pipe due to the <code>|</code>,
2392 then to the NULL device due to the <code>> /dev/null</code>. The
2393 last redirection "wins", so the <code>grep</code> process does not
2394 see any input. The command <code>find /etc 2>&1 > /dev/null | grep
2395 lvm</code> works. The following four redirections take place: First
2396 stdout of the <code>find</code> process and stdin of <code>grep</code>
2397 process are redirected to the two ends of the pipe. Next, due to
2398 the <code>2>&1</code> the stderr stream of the <code>find</code>
2399 process is redirected to the current destination of stdout, i.e.,
2400 to the pipe. Finally the <code>> /dev/null</code> redirects stdout
2401 of the find process to the NULL device. Hence error messages go to
2402 the pipe and are processed by <code>grep</code> as desired.
2403
2404 »)
2405
2406 HOMEWORK(«
2407 Run <code>ulimit -n</code> to see the maximal number of file descriptors you
2408 are allowed to create. Explain what this limit means with respect
2409 to multiple processes, multiple logins, and the <code>fork(2</code>) system
2410 call. Write a program in your language of choice which creates file
2411 descriptors in a loop until it fails due to the file descriptor
2412 limit. Then print the number of file descriptors the program was able
2413 to create.
2414 », «
2415 On our systems the limit is set to 1024. This means a single process
2416 can only have this many files open at any given time. Independent
2417 processes (like those coming from different login sessions) have no
2418 common file descriptors, even though they may open the same files. In
2419 this sense the file descriptor limit is a per-process limit. However,
2420 when a process calls <code>«fork(</code>») to create a new process, the new
2421 process inherits all open file descriptors from the parent. This can
2422 lead to the situation where a newly created process is unable to open
2423 <em>any</em> files. This property was actually used to break computer
2424 security. The <code>«O_CLOEXEC»</code> flag was introduced not too long
2425 ago to deal with this problem. See <code>open(2</code>) for details.
2426
2427 C program that opens the maximal possible number of file descriptors:
2428
2429 <pre>
2430 int main(void)
2431 {
2432 int i;
2433
2434 for (i == 0; open("/dev/null", O_RDONLY) >= 0; i++)
2435 ;
2436 printf("opened %d file descriptors\n", i);
2437 exit(0);
2438 }
2439 </pre>
2440 »)
2441
2442 HOMEWORK(«
2443
2444 Search the web for the document called
2445 <code>vm/overcommit-accounting</code>. Discuss the pros and cons of
2446 the three possible overcommit handling modes.
2447
2448 »)
2449
2450 HOMEWORK(«
2451
2452 Read this
2453 <a
2454 href="https://utcc.utoronto.ca/~cks/space/blog/unix/MemoryOvercommit">blog
2455 posting</a> on the virtual memory overcommit issue. Explain the
2456 catch-22 situation described there in no more than two sentences.
2457
2458 »)
2459
2460 HOMEWORK(«
2461
2462 Describe, in a single paragraph of text, what a virtual dynamic
2463 shared object (VDSO) is and which type of applications benefit most
2464 from it.
2465
2466 »)
2467
2468 HOMEWORK(«
2469
2470 Describe the concept of <em> huge pages </em> and the Linux-specific
2471 implementation of <em> transparent </em> huge pages. Discuss the pros
2472 and cons of huge tables and explain the workloads which would benefit
2473 from a setup with huge pages enabled.
2474
2475 »)
2476
2477 HOMEWORK(«
2478 <ul>
2479 <li> Explain the concept of <em>address space layout randomization</em>
2480 (ASLR). </li>
2481
2482 <li> Run <code>bash -c</code> '<code>cat /proc/$$/maps</code>'
2483 repeatedly to see address space layout randomization in action. Discuss
2484 the pros and cons of ASLR. </li>
2485 </ul>
2486 »)
2487
2488 SUPPLEMENTS()
2489
2490 SUBSECTION(«cd_script»)
2491
2492 <pre>
2493 #!/bin/sh
2494 echo "changing CWD to $1"
2495 cd "$1"
2496 </pre>
2497
2498 SUBSECTION(«hello_world»)
2499
2500 <pre>
2501 #!/bin/sh
2502 echo "hello world"
2503 </pre>
2504
2505 SUBSECTION(«symlink_madness»)
2506
2507 <pre>
2508 #!/bin/sh
2509 mkdir foo
2510 touch foo/a
2511 ln -s ../foo foo/testdir
2512 ls -l foo/a foo/testdir/a foo/testdir/testdir/a
2513 </pre>
2514
2515 SECTION(«Further Reading»)
2516 <ul>
2517 <li> <a href="https://lwn.net/Articles/411845/">Ghosts of Unix Past:
2518 a historical search for design patterns</a>, by Neil Brown. </li>
2519
2520 <li> W. Richard Stevens: Advanced Programming in the Unix
2521 Environment. Addison Wesley. </li>
2522
2523 </ul>