LINUX INTERNALS - Computer Science and Engineering

1 LINUXINTERNALSP eter Chubb and Etienne Le BIT OF HISTORY Ken Thompson and Dennis Ritchie in 1967 70 USG and BSD John Lions 1976 95 Andrew Tanenbaum 1987 LINUX Torvalds 1991 NICTA Copyrightc 2011 From Imagination to Impact2 The history of UNIX-like operating systems is a history of peoplebeing dissatisfied with what they have and wanting to do some-thing better. It started when Ken Thompson got bored with MUL-TICS and wanted to write a Computer game (Space Travel). Hefound a disused PDP-7, and wrote an interactive operating sys-tem to run his game. The main contribution at this point was thesimple file-system abstraction. (Ritchie 1984)Other people found it interesting enough to want to port it to othersystems, which led to the first major rewrite from assembly toC. In some ways UNIXwas the first successfully portable Ritchie & Thompson (1974) was published, AT&T becameaware of a growing market for UNIX. They wanted to discourageit: it was common for AT&T salesmen to say, Here s what youget: A whole lot of tapes, and an invoice for $10 000.

2 Fortunatelyeducational licences were (almost) free, and universities aroundthe world took up UNIXas the basis for teaching and University of California at Berkeley was one of those univer-NICTA Copyrightc 2011 From Imagination to Impact2-1sities. In 1977, Bill Joy (a postgrad) put together and releasedthe first Berkeley Software Distribution in this instance, themain additions were a pascal compiler and Bill Joy BSDs contained contributed code from other universities,including UNSW. The BSD tapes were freely shared betweensource licensees of AT&T s Lions and Ken Robinson read Ritchie & Thompson (1974),and decided to try to use UNIXas a teaching tool here. Ken sentoff for the tapes, the department put them on a PDP-11, andstarted exploring. The license that came with the tapes alloweddisclosure of the source code for Education and Research so John started his famous OS course, which involved readingand commenting on the Edition 6 source 1979, AT&T changed their source licence (it s conjectured, inresponse to the popularity of the Lions book), and future AT&TNICTA Copyrightc 2011 From Imagination to Impact2-2licencees were not able to use the book legally any more.

3 UNSW obtained an exemption of some sort; but the upshot was that theLions book was copied and copied and studied around the , the licence change also meant that an alternative wasneeded for OS universities stopped teaching OS at any depth. One stand-out was Andy Tanenbaum s group in the Netherlands. He andhis students wrote an OS called Minix which was (almost) sys-tem call compatible with Edition 7 UNIX, and ran on readily avail-able PC hardware. Minix gained popularity not only as a teach-ing tool but as a hobbyist almost open source 1991, Linus Torvalds decided to write his own OS after all,how hard could it be? to fix what he saw as some of theshortcomings of Minix. The rest is Copyrightc 2011 From Imagination to Impact2-3 NICTA Copyrightc 2011 From Imagination to Impact2-4 ALITTLE BIT OF HISTORY Basic concepts well established Process model File system model IPC Additions: Paged virtual memory (3 BSD, 1979) TCP/IP Networking (BSD , 1983) Multiprocessing (Vendor Unices such asSequent s Balance , 1984)NICTA Copyrightc 2011 From Imagination to Impact3 The UNIX core concepts have remained more-or-less the samesince Ritchie and Thompson published their CACM paper.

4 Theprocess model and the file system model have remained thesame. The IPC model (inherited from MERT, a different real-timeOS being developed in Bell Labs in the 70s) also is the there have been some significant most important of these were Paged Virtual Memory (intro-duced when UNIXwas ported to the VAX), which also introducedthe idea of Memory-mapped files; TCP/IP networking, Graphi-cal terminals, and multiprocessing, in all variants, master-slave,SMP and NUMA. Most of these improvements were from outsideBell Labs, and fed into AT&T s product via an open-source the late 80s the core interfaces were standardised by theIEEE, in the so-called POSIX Copyrightc 2011 From Imagination to Impact3-1 ABSTRACTIONSL inux KernelFilesThread of ControlMemory SpaceNICTA Copyrightc 2011 From Imagination to Impact4As in any POSIX operating system, the basic idea is to abstractaway physical memory, processors and I/O devices (which canbe arranged in arbitrarily complex topologies in a modern sys-tem), and provide threads, which are gathered into processes (aprocess is a group of threads sharing an address space and afew other resources), that access files (a file is something thatcan be read from or written to.)

5 Thus the file abstraction incor-porates most devices). There are some other features provided:the OS tries to allocate resources according to some system-defined policies. It enforces security (processes in general can-not see each others address spaces, and files have owners).NICTA Copyrightc 2011 From Imagination to Impact4-1 PROCESS MODEL Root process (init) fork()creates (almost) exact copy Much is shared with parent Copy-On-Writeavoids overmuch copying exec()overwrites memory image from a file Allows a process to control what is sharedNICTA Copyrightc 2011 From Imagination to Impact5 The POSIX process model works by inheritance. At boot time,an initial process (process 1) is hand-crafted and set running. Itthen sets up the rest of the system in Copyrightc 2011 From Imagination to Impact5-1 FORK()ANDEXEC() A process can clone itself by callingfork(). Most attributescopied: Address space (actually shared, marked copy-on-write) current directory, current root File descriptors permissions, etc.

6 Some attributesshared: Memory segments markedMAPSHARED Open filesNICTA Copyrightc 2011 From Imagination to Impact6 First I want to review the UNIX process model. Processes clonethemselves by callingfork(). The only difference between thechild and parent process after afork()is the return value fromfork() it is zero in the child, and the value of the child sprocess ID in the parent. Most properties child are logicalcopiesof the parent s; but open files and shared memory segments aresharedbetween the child and the particular, seek operations by either parent or child will affectand be seen by the other Copyrightc 2011 From Imagination to Impact6-1 FORK()ANDEXEC()..01234567 File descriptor tableProcess Bfork()dup()Open file descriptorOffsetIn kernel descriptor tableProcess ANICTA Copyrightc 2011 From Imagination to Impact7 Each process has a file descriptor table. Logically this is an arrayindexed by a small integer. Each entry in the array contains a flag(theclose-on-execflag and a pointer to an entry in anopenfile table.)

7 (The actual data structures used are more complexthan this, for performance and SMP locking).When a process callsopen(), the file descriptor table is scannedfrom 0, and the index of the next available entry is returned. Thepointer is instantiated to point to anopen file descriptorwhich inturn points to an in-kernel representation of an index node aninode which describes where on disc the bits of the file canbe found, and where in the buffer cache can in memory bits befound. (Remember, this is only a logical view; the implementa-tion is a lot more complex.)A process canduplicatea file descriptor by callingdup()ordup2(). Alldupdoes is find the lowest-numbered empty slot inNICTA Copyrightc 2011 From Imagination to Impact7-1the file descriptor table, and copy its target into it. All file descrip-tors that are dups share the open file table entry, and so sharethe current position in the file for read and a processfork()s, its file descriptor table is it too shares its open file table entry with its Copyrightc 2011 From Imagination to Impact7-2 NICTA Copyrightc 2011 From Imagination to Impact7-3 FORK()ANDEXEC()switch (kidpid = fork()) {case 0: /*child*/close(0); close(1); close(2);dup(infd); dup(outfd); dup(outfd);execve("path/to/prog", argv, envp);_exit(EXIT_FAILURE);case -1:/*handle error*/default:waitpid(kidpid, &status, 0);}NICTA Copyrightc 2011 From Imagination to Impact8So a typical chunk of code to start a process looks somethinglike ()returns 0 in the child, and the process id of thechild in the parent.

8 The child process closes the three lowest-numbered file descriptors, then callsdup()to populate themagain from the file descriptors for input and output. It then in-vokesexecve(), one of a family of exec functions, to could alternatively usedup2(), which says which targetfile descriptor to use, and closes it if it s in use. Be careful of thecalls tocloseanddupas order is significant!Some of the exec family functions do not pass the environmentexplicitly (envp); these cause the child to inherit a copy of theparent s file descriptors markedclose on execwill be closed in thechild after theexec; any others will be Copyrightc 2011 From Imagination to Impact8-1 STANDARDFILEDESCRIPTORS0 Standard Input1 Standard Output2 Standard Error Inherited from parent On login, all are set tocontrolling ttyNICTA Copyrightc 2011 From Imagination to Impact9 There are three file descriptors with conventional meanings. Filedescriptor 0 is the standard input file descriptor. Many commandline utilities expect their input on file descriptor descriptor 1 is the standard output.

9 Almost all command lineutilities output to file descriptor descriptor 2 is the standard error output. Error messagesare output on this descriptor so that they don t get mixed intothe output stream. Almost all command line utilities, and manygraphical utilities, write error messages to file descriptor with all other file descriptors, these are inherited from you first log in, or when you start an X terminal, all threeare set to point to thecontrolling terminalfor the login Copyrightc 2011 From Imagination to Impact9-1 FILE MODEL Separation of names from content. regular files just bytes structure/meaningsupplied by userspace Devices represented by files. Directories map names to index node indices(inums) Simple permissions modelNICTA Copyrightc 2011 From Imagination to Impact10 The file model is very simple. In operating systems before UNIX,the OS was expected to understand the structure of all kinds offiles: typically files were organised as fixed (or variable) lengthrecords with one or more indices into them.

10 By contrast, UNIX regular files are just a stream of directories were also just files, albeait with a structureunderstood by the kernel. To give more flexibility, they are nowopaque to userspace, and managed by each individual Copyrightc 2011 From Imagination to Impact10-1 FILE bin / 324230030030132434576223248125 NICTA Copyrightc 2011 From Imagination to Impact11 The diagram shows how the kernel finds a it gets a file name that starts with a slash (/), it starts at theroot of the directory hierarchy (otherwise it starts at the currentprocess s current directory). The first link in the pathname isextracted ("bin") by calling into the filesystem, and searchedfor in the root yields an inode number, that can be used to find the con-tents of the directory. The next pathname component is thenextracted from the name and looked up. In this case, that s theend, and inode 301 contains the metadata for"/bin/ls".NICTA Copyrightc 2011 From Imagination to Impact11-1 NAMEI translate name inode abstracted per filesystem in VFS layer Can be slow: extensive use of caches to speed it updentry cache hide filesystem and device boundaries walks pathname, translating symbolic linksNICTA Copyrightc 2011 From Imagination to Impact12 LINUX has many different filesystem types.