COMPUTER SYSTEMS PROG
COMPUTER SYSTEMS PROG CS 201
Popular in Course
Popular in ComputerScienence
This 265 page Class Notes was uploaded by Orrin Rutherford on Wednesday September 2, 2015. The Class Notes belongs to CS 201 at Portland State University taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/168300/cs-201-portland-state-university in ComputerScienence at Portland State University.
Reviews for COMPUTER SYSTEMS PROG
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/02/15
15213 The course that gives CMU its Zip lnternetworking Nov 19 2002 Topics I Clientserver programming model I Networks I lnternetworks I Global IP Internet 0 IP addresses 0 Domain names 0 Connections classZSppt A ClientServer Transaction Every network application is based on the clientserver model I A server process and one or more client processes I Server manages some resource I Server provides service by manipulating resource for clients 1 Client sends request Client quotquotquotquotquotquotquotquotquotquotquotquotquot quot Server process process 4 Client 2 3 Server sends response handles response Resource Server handles request Note clients and servers are processes running on hosts can be the same or different hosts 15213 F O2 Hardware Org of a Network Host CPU chip register file ALU system bus memory bus 3 l M quot0 ltgt main bridge memory I Expansion slots lt lO bus USB graphics disk network controller adapter controller adapter 1 mouse keyboard monitor m l network I 3 15213 F O2 Computer Networks A network is a hierarchical system of boxes and wires organized by geographical proximity I LAN local area network spans a building or campus 0 Ethernet is most prominent example I WAN widearea network spans country or world 0 Typically highspeed pointtopoint phone lines An internetwork internet is an interconnected set of networks I The Gobal IP Internet uppercase l is the most famous example of an internet lowercase i Let s see how we would build an internet from the ground up 4 15213 F 02 Lowest Level Ethernet Segment Ethernet segment consists of a collection of hosts connected by wires twisted pairs to a hub Spans room or floor in a building host host host s ports Operation I Each Ethernet adapter has a unique 48bit address I Hosts send bits to any other host in chunks called frames I Hub slavishly copies each bit from each port to every other port 0 Every host sees every bit 15213 F O2 Next Level Bridged Ethernet Segment Spans building or campus Bridges cleverly learn which hosts are reachable from which ports and then selectively copy frames from port to port A B l5l lhostl lhostl lhostl lhostl 100 Mbs 1oo Mbs nun 1lt3ne lhostl lhostl mmm C 6 15213 F O2 Conceptual View of LANs For simplicity hubs bridges and wires are often shown as a collection of hosts attached to a single wire 7 15213 F O2 Next Level internets Multiple incompatible LANs can be physically connected by specialized computers called routers The connected networks are called an internet LAN 1 and LAN 2 might be completely different totally incompatible LANs eg Ethernet and ATM 8 15213 F 02 The Notion of an internet Protocol How is it possible to send bits across incompatible LANs and WANs Solution protocol software running on each host and router smoothes out the differences between the different networks Implements an internet protocolie set of rules that governs how hosts and routers should cooperate when they transfer data from network to network TCPIP is the protocol for the global IP Internet 9 15213 F 02 What Does an internet Protocol Do 1 Provides a naming scheme I An internet protocol defines a uniform format for host addresses I Each host and router is assigned at least one of these internet addresses that uniquely identifies it 2 Provides a delivery mechanism I An internet protocol defines a standard transfer unit packet I Packet consists of header and payload o Header contains info such as packet size source and destination addresses 0 Payload contains data bits sent from source host 10 15213 F 02 Transferring Data Over an internet internet packet f E 2 IliEFEI FH1 LAN1 ve 4 3 Ii 1 FH1 LAN1 4 ll Hi i WI 11 Host A client LAN1 Host B server LAN2 Router adapter 4 LAN1 adapter adapter 5 4 5 LAN2 frame LAN2 t protocol software E Jl PH IFH2 5 15213 F O2 Other Issues We are glossing over a number of important questions I What if different networks have different maximum frame sizes segmentation I How do routers know where to forward frames I How are routers informed when the network topology changes I What if packets get lost These and other questions are addressed by the area of systems known as computer networking 12 15213 F 02 Global IP Internet Most famous example of an internet Based on the TCPIP protocol family I IP Internet protocol 0 Provides basic naming scheme and unreliable delivery capability of packets datagrams from hosttohost I UDP Unreliable Datagram Protocol 0 Uses IP to provide unreliable datagram delivery from process toprocess I TCP Transmission Control Protocol 0 Uses IP to provide reliable byte streams from processto process over connections Accessed via a mix of Unix file lO and functions from the sockets interface 13 15213 F O2 Hardware and Software Org of an Internet Application Internet client host Internet server host EUser code I I IE I I I I I I I I I Il I I I I I I I I if I I I E A 7 system calls 5 i V TC Pl P Kernel code 5 Tc p p I I IE I I I I I I I I Il I I I I I I I I f I i A interrupts v V 39 Network 5 Hardware 5 Network adapter 5 and firmware adapter V V Global IP Internet 14 15213 F O2 Basic Internet Components An Internet backbone is a collection of routers nationwide or worldwide connected by highspeed pointtopoint networks A NetworkAccess Point NAP is a router that connects multiple backbones sometimes referred to as peers Regional networks are smaller backbones that cover smaller geographical areas eg cities or states A point of presence POP is a machine that is connected to the Internet Internet Service Providers ISPs provide dialup or direct access to POPs 15 15213 F O2 The Internet Circa 1993 In 1993 the Internet consisted of one backbone NSFNET that connected 13 sites via 45 Mbs T3 links I Merit Univ of Mich NCSA Illinois Cornell Theory Center Pittsburgh Supercomputing Center San Diego Supercomputing Center John von Neumann Center Princeton BARRNet Palo Alto MidNet Lincoln NE WestNet Salt Lake City NorthwestNet Seattle SESQUINET Rice SURANET Georgia Tech Connecting to the Internet involved connecting one of your routers to a router at a backbone site or to a regional network that was already connected to the backbone 16 15213 F 02 NSFNET Internet Backbone source wwweeforg 17 15213 F 02 Current NAPBased Internet Architecture In the early 90 s commercial outfits were building their own highspeed backbones connecting to NSFNET and selling access to their POPs to companies ISPs and individuals In 1995 NSF decommissioned NSFNET and fostered creation of a collection of NAPs to connect the commercial backbones Currently in the US there are about 50 commercial backbones connected by 12 NAPs peering points Similar architecture worldwide connects national networks to the Internet 18 15213 F 02 Internet Connection Hierarchy Private peering NAP NAP NAP agreements between I two backbone Colocanon Sites companies BackboneBackbone Backbone Backbone 34 POP POP POP POP POP POP POP Regional net ISP Big Business POP POP POP POP POP POP POP T1 T1 dialup dialup ISP for individuals Small Business Pgh employee DC employee 19 15213 F 02 Network Access Points NAPS THE INTERNET hf f38 a39NEw YORK NAP SprintLink quot39Pennsauken NJ 9 FlXWESTH V 1 39 0 Ames Research Center r 39L a 39 1 I l gt V if FIXEAST Mountain View College Park MD 553 x 39 MAELA MAJOR US pEER Note Peers in thie context are INTERCONNECT POINTS commercial backbonesdroh Source Boardwathgo 3 P02 20 MCINVorIdComAJUNET Global Backbone UUNET39s Global Internet Backbone B d th 21 Source oar wac1 9 3 FO2 A Programmer s View of the Internet 1 Hosts are mapped to a set of 32bit IP addresses 1282203179 2 The set of IP addresses is mapped to a set of identifiers called Internet domain names I 1282203179 is mapped to wwwcscmuedu 3 A process on one Internet host can communicate with a process on another Internet host over a connec bn 22 15213 F 02 1 IP Addresses 32bit IP addresses are stored in an IP address struct I IP addresses are always stored in memory in network byte order bigendian byte order I True in general for any integer transferred in a packet header from one machine to another 0 Eg the port number used to identify an Internet connection fa EEEt Q gggs s gue uge gae i Q g ampii dgg t kbg b g iamb i Handy network byteorder conversion functions htonl convert long int from host to network byte order htons convert short int from host to network byte order ntohl convert long int from network to host byte order ntohs convert short int from network to host byte order 23 15213 F 02 Dotted Decimal Notation By convention each byte in a 32bit IP address is represented by its decimal value and separated by a penod 0 IP address 0x8002C2F2 1282194242 Functions for converting between binary IP addresses and dotted decimal strings I inetaton converts a dotted decimal string to an IP address in network byte order I inetntoa converts an IP address in network by order to its corresponding dotted decimal string I n denotes network representation a denotes application representation 24 15213 F 02 2 Internet Domain Names unnamed root A mil edu gov com Firstlevel domain names A mit cmu berkeley amazon Secondlevel domain names ece www Thirde vel domain names cs 20821618115 cmcl pdl kittyhawk imperial 1282194242 128218940 25 15213 F O2 Domain Naming System DNS The Internet maintains a mapping between IP addresses and domain names in a huge worldwide distributed database called DNS I Conceptually programmers can view the DNS database as a collection of millions of host entry structures DNS host entry structure struct hostent char hname official domain name of host char haliases null terminated array of domain names int haddrtype host address type AEINET int hlength length of an address in bytes char haddrlist null terminated array of inaddr structs Functions for retrieving host entries from DNS l gethostbyname query key is a DNS domain name 26 gethostbyaddr query key is an IP address 15213 P02 Properties of DNS Host Entries Each host entry is an equivalence class of domain names and IP addresses Each host has a locally defined domain name localhost which always maps to the Ioopback address 127 0 0 1 Different kinds of mappings are possible I Simple case 11 mapping between domain name and IP addr O kittyhawk cmcl cs cmu edu maps to 128 2 194 242 I Multiple domain names mapped to the same IP address 0 eecs mit edu and cs mit edu both map to 18 62 1 6 I Multiple domain names mapped to multiple IP addresses 0 aol com and www aol com map to multiple IP addrs I Some valid domain names don t map to any IP address 0 for example cmcl cs cmu edu 27 15213 F O2 A Program That Queries DNS int mainint argc char argv char pp struct inaddr addr struct hostent hostp if inetatonargv1 ampaddr hostp Gethostbyaddrconst AFINET else hostp Gethostbynameargv1 printfquotofficial hostname snquot hostp gthname for pp hostp gthaliases pp NULL pp printfquotalias snquot pp for pp addrsaddr hostp gthaddlist pp NULL pp unsigned int pp printfquotaddress snquot inetntoaaddr argvl is a domain name or dotted decimal IP addr 0 char ampaddr sizeofaddr 28 15213 F O2 Querying DNS from the Command Line Domain Information Groper dig provides a scriptable command line interface to DNS linuxgt dig short 1282194242 linuxgt dig short KITTYHAWK CMCL CS linuxgt dig short 205188145215 205188160121 641214924 641218725 linuxgt dig short aol v5websysaol kittyhawkcmclcscmuedu x 1282194242 CMUEDU aolcom x 641218725 com 29 15213 F O2 3 Internet Connections Clients and servers communicate by sending streams of bytes over connections I Pointtopoint fullduplex 2way communication and reliable A socket is an endpoint of a connection I Socket address is an IPaddress port pair A port is a 16bit integer that identifies a process I Ephemeral port Assigned automatically on client when client makes a connection request I Wellknown port Associated with some service provided by a server eg port 80 is associated with Web servers A connection is uniquely identified by the socket addresses of its endpoints socket pair I cliaddr cliport servaddr servport 30 15213 F 02 Putting it all Together Anatomy of an Internet Connection Client socket address Server socket address 128219424251213 2082161811580 r 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39v I rt l Connection socket pair 128219424251213 2082161811580 Client host address Server host address 1282194242 20821618115 31 15213 F 02 Next Time How to use the sockets interface to establish Internet connections between clients and servers How to use Unix O to copy data from one host to another over an Internet connection 32 15213 F 02 CS 201 Interface Gerson Robboy Portland State University System Calls A system call is a request to the operating system for a service I typically made via a trap into the kernel The UNIX system call interfaces are defined in section 2 of the man pages I man 2 intro shows how they are actually called These are the real UNIX services everything else is I An abstraction I Built on top of them I See unistdh in Linux kernel tree for details 15213 F O2 System calls for process control We ve already seen these fork execl execv signal sigaction wait waitpid alarm sleep exit 3 15213 F O2 File Manipulation open get a file descriptor for named file close free a file descriptor read read data from a file descriptor write write data to a file descriptor stat get file meta data dup2 duplicate a descriptor seek change the current offset creat createrewrite a named file unlink remove a directory entry chmod change permissions associated with file fcntl file control mmap map file contents Jk We ve seen gt these in action akeady We ll look at these 15213 F O2 creat System Call creat is used to create new files I int creatconst char path modet mode I Equivalent to o openpath OWRONLY OCREAT OTRUNC mode If file already exists truncates to zero include ltfcnthgt int fd modet mode SIRUSR SWUSR SIRGRP SIROTH char filename quottmpfilequot fd creatfilename mode 5 15213 F 02 unlink System Call Removes a directory entry I int unlinkconst char path The unlink function removes a link to a file I If path names a symbolic link unlink removes the symbolic link named by path 15213 F O2 Exercise Write a simple remove utility that removes a single file The program must take one command argument the name of the file to remove The program must check to make sure there is exactly one argument then unlink the file and check to see whether it was successfully unlinked 7 15213 F 02 chmod System Call Change access permission mode of a file I int chmodconst char path modet mode I int fchmodint fildes modet mode The effective user ID of the process must match the owner of the file or be 0 Mode is constructed by the bitwise OR operation of the access permission bits I modet mode SISUID SIRWXU SIRWXG 8 15213 F 02 chmod Example int inCIUde ltStdi0hgt mainint argc char argv include ltsysltypeshgt include ltsyslstathgt int rc include ltstringhgt modet newMode SIRUSR SIRGRP include lterrnohgt if argc 2 extern int errno fprintfstderr quotUsage s ltfiegtnquot argv0 return 1 rc chmodargv1 newMode if rc lt 0 fprintfstderr quotError snquot strerrorerrno return 1 return 0 9 15213 F 02 fcntl System Call include ltfcnthgt int fcntlint fd int cmd arg Number of args depends on cmd A whole collection of things you can do with files Make lO synchronous or asynchronous File locking Receive signal when file is available for readwrite Receive signal when file is modified by another process Keep file open across exec I Anything else a particular device driver needs to do FDUPFD duplicates a file descriptor I Find the lowest numbered available file descriptor greater than or equal to arg and make it be a copy of fd I Compare to dup2 system call a dup2 returns the named descriptor and will close the named descriptor if it was in use before the call 10 15213 F 02 fcntl example You want to write tests for a new processor I You want to do this using a Linux kernel 0 Ability to run many processes do lO handle interrupts etc 0 Really exercise the system not just individual CPU tests in isolation I There are things you need to do in supervisor mode I You don t want to rewrite the Linux kernel or define a new system call interface Write a device driver for a pseudodevice I dynamically linked to the kernel at run time I Open this device as a file and you can do fcntl on it I Individual supervisor mode operations can be fcntl commands Write your tests as userspace programs I Can be multiprocess multithreaded do lO do whatever you want with memory I System calls to do small specific operations 11 15213 F 02 mmap System Call Establishes a mapping between a process39s address space and a file or shared memory object I void mmapvoid addr sizet len int prot int flags int fildes offt off I pa mmapaddr len prot flags fildes off Allows files to be treated as memory buffers Unmapping saves changes automatically I int munmapvoid start sizet length 12 15213 F 02 mmap maps a file into your memory space Instead of a readwrite paradigm you use a memory access paradigm What does this buy you Does it improve performance by avoiding the overhead of system calls 13 15213 F O2 Directory Manipulation Directories while technically files are handled in a special manner opendh readdir closedir rewinddir 14 15213 F 02 opendir System Call Open a directory stream corresponding to the named directory I DIR opendirconst char name Equivalent to the open system call for files 15 15213 F O2 readdir Read a directory entry I int readdirunsigned int fd struct dirent dirp unsigned int counn Reads the next directory entry to dirp Count is ignored struct dirent long dino l inode number I offt doff I offset to this dirent I unsigned short dreclen l length of this dname l char dname NAMEMAX1 I file name nullterminated l 16 15213 F 02 closedir and rewinddir closedir closes the directory stream I Equivalent to the close system call for files rewinddir resets the position of the directory stream to the beginning I Seeks to the first entry in the directory seekdir sets the location of the directory stream I Equivalent to the seek system call for files What kind of program would use these 17 15213 F O2 Finding file permissions Suppose you want to know if a certain path is an executable file I usrhomeoscarabc How can you do it without traversing the path and reading all the individual directories 18 15213 F 02 Memory Allocation Malloc calloc realloc free alloca These are really library calls not system calls The actual system call is sbrk I Sets the limit on the heap you are allowed to use I Essentially gives us a hunk of virtual address space to use I But as users we don t normally call sbrk Malloc free and friends manage the memory I No system calls I Just touch the virtual address and the VM system allocates the actual memory we need 19 15213 F 02 Memory Allocation The main players Oxffffffff I I malloc Oxcooooooo Kernel Virtual Memory I calloc User Stack created at run time I realloc I free Shared Libraries I alloca memory mapped 0X 000000 Runtime Heap created at run time Readwrite data Readonly code and data 20 15213 F 02 A Note on Alignment Alignment is important when accessing data Memory allocators really allocate chunks of bytes so misalignment is easy to do Making sure that you allocate memory in proper chunks and casting the return to the chunk size is critical I Always cast return value of malloc to data type you want to point to 21 15213 F 02 alloca alloca allocates memory in the stack frame of the caller I The specific function main foobar etc I Alloca ing beyond the current stack limit results in undefined behavior There is no corresponding free call I The memory is automatically freed when the function returns I Warning don t pass pointers to alloca d memory back up the call stack 0 Can safely pass down though 22 15213 F 02 malloc Returns a pointer to a block of at least size bytes not zero filled Allocated from the heap I void mallocsizet size I int ptr int mallocvaue sizeofint Be careful to allocate enough memory I Overrun on the space is undefined I Common error 0 char cptr char malloc strlenbuf sizeofchar strlen doesn t account for the NULL terminator I Fix 0 char cptr char malloc strlenbuf1 sizeofchar 23 15213 F 02 Zeroing Memory Sometimes before you use memory returned by malloc you want to zero it I Or maybe set it to a specific value memset sets a chunk of memory to a specific value I void memsetvoid s int c sizet n 24 15213 F 02 calloc void callocsizet nelem sizet elsize Will always zero memory that is returned Essentially equivalent to malloc memset It takes time to zero the memory so frequent calls to calloc can be more costly that just malloc I A design consideration for your program 25 15213 F 02 reaHoc Allows modification of the specified block I void reallocvoid ptr sizet size Special semantics I Changes the size of the block pointed to by ptr to size bytes and returns a pointer to the possibly moved block I Contents unchanged up to the smaller of the new or old sizes 0 Implied copy when block is moved I If ptr is NULL behaves like malloc I If pts in nonNULL and size is 0 behaves like free 26 15213 F 02 free Returns memory to the process for possible later reallocation I Memory is not returned to the system until the process actually terminates Memory is automatically free d on process termination I However it is always a good idea to explicitly free any memory that is allocated from the heap o Helps to avoid memory leaks aids program checkers During program execution you should always free alloc d memory when you don t need it anymore I In this class it is considered an error not to do so I But you don t have to free everything before exiting I Only during execution 27 15213 F 02 malloc vs calloc Sometimes performance considerations dictate which one to use I Writing to memory is really bad for performance if you don t have to What if you are allocating a buffer and you are going to copy a string into it I What if the string is not as big as the buffer What if you are allocating a data structure containing pointers 28 15213 F 02 Memory Leak A leak in a program39s dynamic store allocation logic that causes it to fail to reclaim memory in the heap after it has finished using it eventually causing the program to fail due to lack of memory Simple example Initial allocation char ptr char mallocf ptr char mallocL Program loses track of initial allocation when ptr is overwritten with address of new chunk 29 15213 F 02 Summary of kernellevel lO The Unix kernel gives us files as an abstraction a named stream of bytes System calls for access open close read write Higher level abstractions are at the application level or libraries 30 15213 F 02 Standard lO Functions The C standard library libc a contains a collection of higherlevel standard lO functions I Documented in Appendix B of KampR Examples of standard lO functions I Opening and closing files fopen and fclose I Reading and writing bytes fread and fwrite I Reading and writing text lines fgets and fputs I Formatted reading and writing fscanf and fprintf 31 15213 F 02 Simple Buffered lO What does buffering buy us Simple Unbuffered IIO int getcharvoid charc return read0 ampc 1 1 unsigned char c EOF Note where EOF comes from 32 Simple Buffered IIO int getcharvoid static char bufBUFSZE static char bufp buf static int n 0 if n 0 buffer is empty n read0 buf sizeofbuf bufp buf return n gt 0 unsigned char bufp EOF 3 F O2 Stanar l Strems Standard O models open files as streams I Abstraction for a file descriptor and a buffer in memory C programs begin life with three open streams defined in stdio h I stdin standard input I stdout standard output I stderr standard error c EEEE I gt ems quot59 ii i maize i 43 Br 33 15213 F 02 Buffering in Standard IO Standard O functions use buffered O printf h printf e printf l printf l printf e buf printf n v 7 V V Ihlel on fflushstdout write1 buf 6 buf 6 34 15213 F 02 Standard lO Buffering in Action You can see this buffering in action for yourself using the Unix strace program lt i13lt bi imt lt3 at linuxgt strace hello E r execve quot helloquot quothellOquot write1 quothellonquot 6 6 E213 1E5quot 7 79 2 iot riiimwy exit 0 moron bio Q 75 P3 Lt in J39 bro 3 J J J 119 92 mi 1 439 m 35 15213 F 02 Unix lO vs Standard lO Standard lO is implemented using lowlevel Unix lO fopen fdopen fread fwrite fscanf fprintf sscanf sprintf fgets fputs fflush fseek fclose open read write lseek stat close Which ones should you use in your programs 36 C application program Standard lO functions Unix IO functions accessed via system calls 15213 F O2 Exercise A program needs to seek to random places in a file and write one small record in each place Should it use the stdio library or Unix system calls What about a compiler which reads one character at a time sequentially through a file containing source code 37 15213 F 02 Pros and Cons of Unix lO Pros I Unix lO is the most general and lowest overhead form of lO o All other lO packages are implemented using Unix lO functions I Unix lO provides functions for accessing file metadata Cons I Dealing with short counts is tricky and error prone I Efficient reading of text lines requires some form of buffering also tricky and error prone I Both of these issues are addressed by the standard lO package 38 15213 F 02 Pros and Cons of Standard lO Pros I Buffering increases efficiency by decreasing the number of read and write system calls 0 Usually 0 Unless you re transferring blocks of data gt the buffer size 0 Or unless you re seeking randomly not using the buffer I Higher level of abstraction makes it easier to use 0 Usually 0 Example Short counts are handled automatically There s a concept of EOF o More likely to avoid bugs I Portability o Defacto part of the C language independent of O S 39 15213 F 02 Pros and Cons of Standard lO Cons I Usually more efficient and easier to use 0 For big blocks of data an extra layer of library calls reduces efficiency 0 For many seeks it s even worse Fill a buffer and don t use it I Provides no function for accessing file metadata I Not appropriate for input and output on network sockets I There are poorly documented restrictions on streams that interact badly with restrictions on sockets 40 15213 F 02 Pros and Cons of Standard lO cont Restrictions on streams I Restriction 1 input function cannot follow output function without intervening call to fflush fseek fsetpos or rewind o Latter three functions all use lseek to change file position I Restriction 2 output function cannot follow an input function with intervening call to fseek fsetpos or rewind Restriction on sockets I You are not allowed to change the file position of a socket 41 15213 F 02 Choosing lO Functions Use the highestlevel lO functions you can I Many C programmers are able to do all of their work using the standard lO functions When to use standard lO I Usually I Especially when working with disk or terminal files I Especially when you re doing something that standard lO does anyway 0 Don t reinvent library functions yourself When to use raw Unix lO I When you need to fetch file metadata I In rare cases when you need absolute highest performance 42 15213 F 02 Question Suppose a program generates huge arrays of data in memory multimegabytes and periodically the program writes a whole array to a file Each array is written in its entirety and just once Is it more efficient to use write system calls or the stdio library to write the array 43 15213 F 02 Question The operating system kernel has a pool of buffers for disk blocks If you read a file one character at a time the kernel does not go to the disk for each character because it has the whole disk block in a buffer When a program uses fread the library function has its own buffer in user space So essentially data is being copied from the buffer pool to fread s buffer and then to the application s own buffer So the data is copied at least twice In that case is it more efficient to use fread to read a character at a time than to use read 44 15213 F O2 For Further Information W Richard Stevens Advanced Programming in the Unix Environment Addison Wesley 1993 Brian W Kernighan and Rob Pike The Unix Programming Environment PrenticeHall 1984 45 15213 F O2 15213 The course that gives CMU its Zip Dynamic Memory Allocation ll Nov 7 2002 Topics I Explicit doublylinked free lists I Segregated free lists I Garbage collection I Memoryrelated perils and pitfalls cla5522ppt Keeping Track of Free locks 0 Method 1 Implicit list using lengths links all blocks ga ie elmem this use arising winters W l l 39 the free cleans j ar u Lv l quotIllall 0 Method 3 Segregated free lists I Different free lists for different size classes 0 Method 4 Blocks sorted by size not discussed I Can use a balanced tree eg RedBlack tree with pointers within each free block and the length used as a key 2 15213 F 02 Explicit Free Lists lt AT BT 0 Use data space for link pointers I Typically doubly linked I Still need boundary tags for coalescing Forward links 43 Back links I It is important to realize that links are not necessarily in the same order as the blocks 3 15213 F O2 Allocating From Explicit Free Lists pred succ Before free block pred succ After with splitting free block 4 15213 F 02 Freeing With Explicit Free Lists Insertion policy Where in the free list do you put a newly freed block I LIFO lastinfirstout policy 0 Insert freed block at the beginning of the free list 0 Pro simple and constant time 0 Con studies suggest fragmentation is worse than address ordered I Addressordered policy 0 Insert freed blocks so that free list blocks are always in address order ie addrpred lt addrcurr lt addrsucc 0 Con requires search 0 Pro studies suggest fragmentation is better than LIFO 5 15213 F 02 Freeini a LIF Policy lpi e x l K I Case 1 aaa I Insert self at beginning of free list Case 2 aaf before I Splice out next coalesce self and next and add to beginning of free list after NV 10 r ngt is Freeing before Case 3 faa I Splice out prev coalesce with self and add to beginning of free list after before Case 4 faf I Splice out prev and next coalesce with self and add to beginning of list Explicit List Summary Comparison to implicit list I Allocate is linear time in number of free blocks instead of total blocks much faster allocates when most of the memory is full I Slightly more complicated allocate and free since needs to splice blocks in and out of the list I Some extra space for the links 2 extra words needed for each block Main use of linked lists is in conjunction with segregated free lists I Keep multiple linked lists of different size classes or possibly for different types of objects 8 15213 F 02 Keeping Track of Free Blocks Method 1 Implicit list using lengths links all blocks 546 Method 2 Explicit list among the free blocks using pointers within the free blocks 54 4 6 2 Method 3 Segregated free list I Different free lists for different size classes Method 4 Blocks sorted by size I Can use a balanced tree eg RedBlack tree with pointers within each free block and the length used as a key 9 15213 F 02 Segregated Storage Each size class has its own collection of blocks 4gtgtgt 58gtgt 916gt l Often have separate size class for every small size 234 I For larger sizes typically have a size class for each power of 2 10 15213 F 02 Simple Segregated Storage Separate heap and free list for each size class No splitting To allocate a block of size n I If free list for size n is not empty 0 allocate first block on list note list can be implicit or explicit I If free list is empty 0 get a new page a create new free list from all blocks in page 0 allocate first block on list I Constant time To free a block I Add to free list I If page is empty return the page for use by another size optional Tradeoffs I Fast but can fragment badly 15213 F O2 Segregated Fits Array of free lists each one for some size class To allocate a block of size n I Search appropriate free list for block of size m gt n I If an appropriate block is found 0 Split block and place fragment on appropriate list optional I If no block is found try next larger class I Repeat until block is found To free a block I Coalesce and place on appropriate list optional Tradeoffs I Faster search than sequential fits ie log time for power of two size classes I Controls fragmentation of simple segregated storage I Coalescing can increase search times 0 Deferred coalescing can help 12 15213 F O2 For More Info on Allocators D Knuth The Art of Computer Programming Second Edition Addison Wesley 1973 I The classic reference on dynamic storage allocation Wilson et al Dynamic Storage Allocation A Survey and Critical Review Proc 1995 lnt l Workshop on Memory Management Kinross Scotland Sept 1995 I Comprehensive survey I Available from CSAPP student site csappcscmuedu 13 15213 F 02 Implicit Memory Management Garbage Collection Garbage collection automatic reclamation of heap allocated storage application never has to free ovoid foo int p m alloc1quot28 return p block is now garbage Common in functional languages scripting languages and modern object oriented languages I Lisp ML Java Perl Mathematica Variants conservative garbage collectors exist for C and C I Cannot collect all garbage 14 15213P02 Garbage Collection How does the memory manager know when memory can be freed I In general we cannot know what is going to be used in the future since it depends on conditionals I But we can tell that certain blocks cannot be used if there are no pointers to them Need to make certain assumptions about pointers I Memory manager can distinguish pointers from non pointers I All pointers point to the start of a block I Cannot hide pointers eg by coercing them to an int and then back again 15 15213 F O2 Classical GC algorithms Mark and sweep collection McCarthy 1960 I Does not move blocks unless you also compact Reference counting Collins 1960 I Does not move blocks not discussed Copying collection Minsky 1963 I Moves blocks not discussed For more information see Jones and Lin Garbage Collection Algorithms for A utomatic Dynamic Memory John Wiley amp Sons 1996 16 15213 F 02 Memory as a Grah We view memory as a directed graph I Each block is a node in the graph I Each pointer is an edge in the graph I Locations not in the heap that contain pointers into the heap are called root nodes eg registers locations on the stack global variables Root nodes Hiram l f O reachable g I r 4 Notreachable 7 39 j garbage A node block is reachable if there is a path from any root to that node Nonreachable nodes are garbage never needed by the application 17 15213 F 02 Assumptions For This Lecture Application I new n returns pointer to new block with all locations cleared I read bi read location i of blockb into register I write b i v write v into location i of block b Each block will have a header word I addressed as b 1 for a block b I Used for different purposes in different collectors Instructions used by the Garbage Collector I isptr p determines whether p is a pointer I length b returns the length of block b not including the header I getroots returns all the roots 18 15213 F 02 Mark and Sweep Collecting Can build on top of mallocfree package I Allocate using malloc until you run out of space When out of space I Use extra mark bitin the head of each block I Mark Start at roots and set mark bit on all reachable memory I Sweep Scan all blocks and free blocks that are not marked Mark bit set foot mark l A After mark After sweep 19 15213 F 02 Mark and Sweep cont Mark using depthfirst traversal of the memory graph ptr markptr p if isptrp return do nothing if not pointer if markBitSetp return check if already marked setMarkBitp set the mark bit for i0 i lt lengthp i mark all children markpi return Sweep using lengths to find next block ptr sweepptr p ptr end while p lt end if markBitSetp clearMarkBit else if allocateBitSetp freep p lengthp 20 15213 F 02 Conservative Mark and Sweep in C A conservative collector for C programs I Isptr determines if a word is a pointer by checking if it points to an allocated block of memory I But in C pointers can point to the middle of a block ptr header a l I I I II I I I I So how do we find the beginning of the block I Can use balanced tree to keep track of all allocated blocks where the key is the location I Balanced tree pointers can be stored in header use two additional words data 21 right 15213 F 02 MemoryRelated Bugs Dereferencing bad pointers Reading uninitialized memory Overwriting memory Referencing nonexistent variables Freeing blocks multiple times Referencing freed blocks Failing to free blocks 22 15213 F 02 Dereferencing Bad Pointers The classic scanf bug f df val 23 15213 F 02 Rin Uninitilize Assuming that heap data is initialized to zero 5 JL r C1355 it n 4 pwd db 24 15213 F 02 riti Allocating the possibly wrong sized object quot msllcaxa Emmi E vw g f iss 2 25 15213 F 02 Offbyone error 26 15213 F 02 Overwritin Memory Not checking the max string size h Q it i w t t In A 5 quot 39v r 1 w r quot39l f 397 9 7 Basis for classic buffer overflow attacks I 1988 Internet worm I Modern attacks on Web servers I AOLMicrosoft IM war 27 15213 F O2 4 Referencing a pointer instead of the object it points to ritin 28 15213 F 02 riti n Misunderstanding pointer arithmetic c4quot A rv u 394 w 29 15213 F 02 Referencin Nonexistent Variales Forgetting that local variables disappear when a function returns iim f Q If quotmt mama a m ma l 30 15213 F 02 Frein Nasty 31 15213 F 02 Rferncind Frw Evil 32 15213 F 02 Failing to Free cks Memry Leks Slow longterm killer SE E E 3133311 E Emma gt 4w AH O Eil l g 5 33 15213 F O2 Failing to Free Blocks Memory Leaks Freeing only part of a data structure 34 struct list int val struct list next foo struct list head mallocsizeofstruct list head gtval 0 head gtnext NULL ltcreate and manipulate the rest of the listgt freehead return 15213 F O2 Dealing With Memory Bugs Conventional debugger gdb I Good for finding bad pointer dereferences I Hard to detect the other memory bugs Debugging malloc CSRI UToronto malloc I Wrapper around conventional malloc I Detects memory bugs at malloc and free boundaries 0 Memory overwrites that corrupt heap structures 0 Some instances of freeing blocks multiple times 0 Memory leaks I Cannot detect all memory bugs 0 Overwrites into the middle of allocated blocks 0 Freeing block twice that has been reallocated in the interim o Referencing freed blocks 35 15213 F 02 Dealing With Memory Bugs cont Binary translator Atom Purify I Powerful debugging and analysis technique I Rewrites text section of executable object file I Can detect all errors as debugging malloc I Can also check each individual reference at runtime 0 Bad pointers o Overwriting o Referencing outside of allocated block Garbage collection BoehmWeiser Conservative GC I Let the system free blocks instead of the programmer 36 15213 F 02 CS 201 Files and V0 Gerson Robboy Portland State University A Typical Hardware System CPU chip register file ALU system bus memory bus 3 K i b s interface V0 ltgt main u bridge memory l V0 bus Expansion slots for other devices such USB graphics disk as network adapters controller adapter controller mouse keyboard monitor 2 m 15213 F O2 Some typical hardware components I Hard disk I CDROM I Printer Screen Keyboard Mouse Floppy disk Zip drive Network controller Modem Each of these has a detailed unique interface I Not standardized between different manufacturers 3 15213 F O2 Hard Disk DrivePhysical Layer We shall stack 1 to 20 metal discs each side covered with magnetic recording material platters and bind them by a central 0 1 to 20 spindle They will be spun at 7200 500 to 2500 racks RPMS Seek time hierarchy of Platter controllers transfer rate Segtors Sgcgr T k l Sector d ta E C rac pgaps l l l 4 15213 F 02 As programmers we don t want to see all that c We want a simple portable abstraction for lO 0 Device drivers in the operating system take care of the device interfaces 0 As application programmers we want all devices to look alike 5 15213 F 02 And here s another problem 0 We don t want to manage data allocation on a disk I Nor do we want to know about platters sectors tracks o The O S file manager allows us to deal with files not disks 0 What is a file anyway I A collection of data managed by the O S I We can open it by name 0 We don t care where it is only its name I We don t have to allocate space for it I We don t have to know what the underlying medium looks like 6 15213 F 02 Can devices and files be handled by one single abstraction 7 15213 F O2 Unix Files A file is a named sequence of m bytes BO 3 Bk B m1 We open it by name Then we see it as a stream of bytes I At the O S level there is no internal structure to a file 8 15213 F 02 Unix Files a brief digression If a file is a sequence of bytes does that mean files always contain strings of characters The declaration of read according to KampR int readint fd char buf int n Does char buf mean buf contains ascii characters I If not then why declare it as char Declaration of read in newer versions of Linux ssizet readint fd void buf sizet count 9 15213 F 02 Unix Files Unix Bell Labs late 1960s introduced two profound innovations regarding files mnAlmost everything is a file 0 One abstraction for accessing most external things including lO devices and data stored in files on a disk A file is a stream of bytes with no other structure 0 No records 0 Higher levels of structure are an application concept not an operating system concept 0 Libraries are available if you want structured files 10 15213 F 02 Internally Unix has two kinds of Files Regular files I Data maintained on a storage device such as a hard disk I The O S file manager organizes and retrieves the data Special files I All lO devices are represented as files 0 devsda2 usr disk partition 0 devtty2 terminal I Even the kernel is represented as a file 0 devkmem kernel memory image 0 proc kernel data structures for processes To us as programmers they re all just files 11 15213 F 02 Well OK a few more types have crept in Regular file I File system on a disk managed by the O S Directory I A file that contains the names and locations of other files I Normally user programs don t open and read directories The ls utility is an exception Character special and block special files I Terminals character special and disks block special FIFO named pipe I A file type used for interprocess comunication Socket I A file type used for network communication between 12 processes 15213 P02 Unix lO Key Unix idea All input and output is handled in a consistent and uniform way Basic Unix O operations system calls I Opening and closing files 0 open and close I Changing the current file position seeking O lseek I Reading and writing a file 0 read and write 13 15213 F O2 til Each process created by a Unix shell begins life with three open files normally associated with a terminal I 0 standard input I 1 standard output I 2 standard error 14 15213 F O2 Opening Files The second argument is a constant defined in syscallsh There are a zillion values for it Some important ones 15 OCREAT Create a new file if it doesn t exist ORDRW Open for reading and writing ORDONLY Open for reading only OWRONLY Open for writing only OTRUNC Truncate the file to length zero 0 If the file existed and had data that data will disappear for all users 15213 F O2 Opening files that don t already exist include ltsyscallshgt int fd file descriptor if fd open etchosts ORDWROCREAT SIRWXU lt 0 perror open exit1 The third argument sets permissions I In this example read write and execute for user I The argument is required if creating a new file else ignored What if you leave this argument out 16 15213 F O2 Opening Files Why do you have to check for errors after opening a file What kinds of things can make it fail 17 15213 F O2 Writing Files include ltsyscallshgt char buf512 int fd file descriptor int nbytes number of bytes read Open the file fd Then write up to 512 bytes from buf to file fd if nbytes writefd buf sizeofbuf lt 0 perror write exit1 Returns number of bytes written from buf to file fd I nbytes lt 0 indicates that an error occurred I As with reads short counts are possible and are not errors 18 1eman2 char buf512 int fd int nbytes file descriptor number of bytes read if fd open somefilequot ORDWR lt 0 perror openquot exit1 if nbytes writefd buf perror writequot exit1 sizeofbuf lt 0 What is the current file position 19 15213 F O2 i le Closing a file informs the kernel that you are finished accessing that file 20 15213 F 02 Fi Reading a file copies bytes from the current file position to memory and then updates file position 6 H 4 quot Returns number of bytes read I nbytes lt 0 an error occurred l short counts nbytes lt sizeof buf are possible and are not errors 21 15213 F O2 Questions In Unix using the read system call if you read past the end of a file what do you get How do you know you ve gone past the end of the file What if you make system calls and you don t include syscallsh or stdioh I Will the compiler give you an error message I Will your code be correct 22 15213 F 02 Seeking seek sets the position in the file where the next read or write will occur include ltsyscallshgt char buf512 int fd int offset if if nbytes file descriptor seek to offset in the file lseekfd offset SEEKET lt 0 handle error Then write from buf to file at that offset nbytes writefd buf perror write exit1 sizeofbuf lt 0 F O2 Seeking The last argument is a constant defined in syscallsh Values I SEEKSET The offset is set to offset bytes I SEEKCUR The offset is set to its current location plus offset bytes I SEEKEND The offset is set to the end of the file plus offset bytes What does SEEKEND do to the file I Does it change the size of the file I What if you write out past the end of the file leaving a gap 0 What is the size of the file after you write 0 What happens if you read within the gap 24 15213 F 02 Exercise Suppose a file called fpfile contains an array of floating point values of type float in C Write a few lines of code to open the file seek to the fifth element of the array of floats and read that one element into a variable in memory Never mind about main or include Just write a few lines out of the middle of an imaginary program Don t forget to check for errors 25 15213 F 02 Open File Representation Two descriptors referencing two distinct open disk files Descriptor 1 stdout points to terminal and descriptor 4 points to open disk file Global open Global Per process file table vnode table descriptor table File A terminal stdin fd 0 39File access StdOUt 1 pos size in stderr fd 2 stat fd 3 refcnt1 Flle struct File B disk 5 File access File pos File Slze refcnt1 Flle type 26 15213 F 02 File Sharing Calling open twice with the same filename argument 27 Open file table Per process descriptor table de fd1 fd2 fd3 fd4 shared by all processes File A File pos refcnt1 File B File pos refcnt1 gt vnode table shared by all processes File accesg File size FHetype 15213 F O2 File Sharing Between Processes A child process inherits its parent s open files Here is the situation 28 immediately after a fork Descriptor Parent39s table de fd1 fd2 fd3 fd4 Child39s table de fd1 fd2 fd3 fd4 tables A Global open Global file table vnode table File A gtFile access File pos File size refcnt2 File type File B i File access File pos File size refcnt2 Flle type 15213 F O2 Exercise Suppose a disk file called foobar contains 6 characters foobar What is the output of this program include ltsyscallshgt main int fd file descriptor char 0 fd open foobar ORDONLY 0 if fork 0 readfd ampc l else waitNULL readfd ampc 1 printf c cn c exit0 29 15213 F 02 Exercise Suppose a disk file called foobar contains 6 characters foobar What is the output of this program include ltsyscallshgt main int fd file descriptor char 0 fd open foobar ORDONLY 0 readfd ampc 1 if fork 0 printf c cn c else waitNULL readfd ampc 1 printf c cn c exit0 30 15213 F 02 dup2 duplicate an open file descriptor The dup2 function causes the file descriptor fildesz to refer to the same file as fildes The fildes argument is a file descriptor referring to an open file and fildesz is a nonnegative integer less than the current value for the maximum number of open file descriptors allowed the calling process If fildesz already refers to an open file not fildes it is closed first Do not panic Continue breathing normally We will explore what this means 31 15213 F 02 Exercise Write some code to redirect the standard input to a file called infile That is the process executing this code will get its standard input from infile instead of wherever it came from before 32 15213 F 02 Sharing Files Files are inherently shared 0 If process x writes data to a file and process y has the file open then process y can read the data Sharing can be avoided I locks on files I file permissions 33 15213 F 02 Sharing Files continued Suppose two processes write different data to the same offset in the same file What happens This is perfectly legal I It s exactly analogous to shared memory I If you don t want this to happen it s up to you the application programmer to avoid it The data in a file is consistent in this sense All processes that read the file will see the same data 34 15213 F 02 File Metadata The stat and fstat functions give us information about files struct stat devt stdev inot stino modet st4mode nlinkt stnlink uidt stuid gidt stgid devt strdev offt stsize unsigned long stblksize unsigned long stblocks timet statime timet st4mtime timet stctime Metadata returned by the stat and fstat functions device inode protection and file type number of hard links user ID of owner group ID of owner device type if inode device total size in bytes blocksize for filesystem IO number of blocks allocated time of last access time of last modification time of last change 35 15213 F O2 Example of Accessing File Metadata statcheckc Querying and manipulating a file s meta data include quotcsapphquot int main int argc struct stat stat char argv bassgt statcheck statcheckc type regular read yes bassgt chmod 000 statcheckc bassgt statcheck statcheckc char type readok type regular read no Statargv1 ampstat if SISREGstatstmode file type type quotregularquot else if SISDIRstatstmode type quotdirectoryquot else type quototherquot if statstmode amp SIRUSR OK to read readok quotyesquot else readok quotnoquot printfquottype s read snquot type readok exit0 36 15213 F 02 What about files that aren t ascii strings Here s a program to copy a file containing ascii strings from stdin to stdout include ltstdiohgt define MAXLINE 32 1024 define MAXBUF 4096 main int n char bufMAXLINE while fgetsbuf MAXLINE 1 stdin 0 fputsbuf stdout Exercise Change the program to copy MAXBUF bytes at a time Hint these function declarations may come in handy sizet freadvoid ptr sizet size sizet nobj FILE stream sizet fwritevoid ptr sizet size sizet nobj FILE stream 37 15213 F 02 1quot C8201 Lectures Exercise Solutions Unit 2 Global Symbols Unit 2 Static locals Unit 4 fork Unit 4 fork again 7 Unit 5 SIGSEGV handler Unit 6 The Fifth Element The Fifth Element Unit 6 Sharing files Unit 7 Unlink a Unit 8 Lowercase void lower char 5 i i lt st1ens 14 ampamp sli lt 39239 39a39 39 For loop is just On 39 bL i39 sirlen is ALSO On 39 9 ower is On2 39 Compiler is stuck because sirlen might have side effects Unit 8 To what degree ls the loopu Wlth what degree of hr 112017 8 parallel uhmlhhg7 4 Whlch vanable ls spllledto the stack7 le gth Why ls that agood cholce ofwhlch vanable to Splll7 aeeessed lhfhequehlly any microrops does lttake to execute 2 lhslmemhy for last 2 addl39s 2m empl M 21 total CS 201 Linking Gerson Robboy Portland State University 1 15213 F 02 A Simplistic Program Translation Scheme m c ASCII source file Binary executable object file p memory image on disk Problems Efficiency small change requires complete recompilation Modularity hard to share common functions eg printf Solution LInker 2 15213 F 02 A Better Scheme Using a Linker Separately compiled relocatable object files p Executable object file 3 15213 F O2 Translating the Example Program Compiler driver coordinates all steps in the translation and linking process I Included with each compilation system cc or gcc I lnvokes preprocessor opp compiler ccl assembler as and linker 1d I Passes command line arguments to appropriate phases Example create executable p from m c and a c bassgt gcc 02 v o p mc ac cpp args mc tmpcca07630i ccl tmpcca07630i mc 02 args 0 tmpcca07630s as args 0 tmpcca076301o tmpcca07630s ltsimilar process for acgt 1d 0 p system obj files tmpcca076301o tmpcca076302o bassgt 4 15213 F O2 A picture of the tool set mc ac ml a s s m ao Libraries 0 libca p This is the executable program 5 1bd1dl J2 What Does a Linker Do Merges object files I Merges multiple relocatable 0 object files into a single executable program Resolves external references I External reference reference to a symbol defined in another object file Relocates symbols I Relocates symbols from their relative locations in the 0 files to new absolute positions in the executable I Updates all references to these symbols to reflect their new positions 0 References in both code and data gtgtcodea reference to symbol a gtgtdauu int xpampx reference to symbol x 6 15213 F O2 Why Linkers Modularity I Program can be written as a collection of smaller source files rather than one monolithic mass I Can build libraries of common functions more on this later 0 eg Math library standard C library Efficiency I Time 0 Change one source file compile and then relink o No need to recompile other source files I Space 0 Libraries of common functions can be aggregated into a single file 0 Yet executable files and running memory images contain only code for the functions they actually use 7 15213 F O2 Questions for you When a linker combines relocatable object files into an executable file why does the linker have to modify instructions in the actual code How does the linker know what values to put into the code How does the linker know exactly where to insert those values 8 15213 F 02 Executable and Linkable Format ELF Standard binary format for object files Derives from ATampT System V Unix I Later adopted by BSD Unix variants and Linux One unified format for I Relocatable object files o I Executable object files I Shared object files so Generic name ELF binaries Better support for shared libraries than old a out formats Also better more complete information for debuggers 9 15213 F O2 ELF Object File Format Elf header I Magic number type 0 exec so machine byte ordering etc Program header table I Page size virtual addresses of memory segments sections segment sizes text section I Code data section I lnitialized static data bss section I Uninitialized static data I Block Started by Symbol I Has section header but occupies no space in the disk file 10 15213 F 02 ELF Object File Format cont symtab section I Symbol table I Procedure and static variable names I Section names and locations rel text section I Relocation info for text section I Addresses of instructions that will need to be modified in the executable I Instructions for modifying rel data section I Relocation info for data section I Addresses of pointer data that will need to be modified in the merged executable debug section I Info for symbolic debugging gcc g 11 15213 F O2 Example C Program 12 15213 F O2 Relocatable Object Files into an Executable Object File Relocatable Object Files Executable Object File text 0 headers data M gt text system data int e 7 data int ep ampe int x 15 bss symtab debug 13 15213 F 02 Relocating Symbols and Resolving External References I Symbols are lexical entities that name functions and variables I Each symbol has a value typically a memory address I Code consists of symbol definitions and references I References can be either local or external mc ac Def of local symbol e Ref to external symbol e Def of local Defs of Ref to external symbol local SymbOI eXlt Ref to external ep symgms defined in symbo a Def of X an Y libc so local Refs Of local symbols epxy 14 SymbOI a 15213 F 02 Questions for you In the function main on the previous slide why is there no arrow pointing to the variable r Does rhave to be relocated when the program is linked What information about r has to be in the symbol table What does the debugger need to know about r 15 15213 F O2 External functions In main notice that the names a and exit are external symbols The compiler knows they are functions and the linker will resolve the references Exit is just another function call I The compiler doesn t know anything about Unix system calls I The compiler knows about names and data types 16 15213 F 02 m 0 Relocation Info source objdump 17 Disassembly of section text 00000000 ltmaingt 00000000 ltmaingt 0 55 pushl 1 89 e5 movl 3 e8 fc ff ff ff call ebp espebp 4 ltmain0x4gt 4 R386PC32 a 8 6a 00 a e8 fc ff ff ff call pushl 0x0 b ltmain0xbgt b R386PC32 exit f 90 nop Disassembly of section data 00000000 ltegt 0 07 00 00 00 15213 F 02 a 0 Relocation Info text Disassembly of section text 00000000 ltagt 0 55 pushl ebp 1 8b 15 00 00 00 movl 0x0edx 6 00 3 R38632 ep 7 a1 00 00 00 00 movl 0x0eax 8 R38632 x c 89 e5 movl espebp e 03 02 addl edxeax 10 89 ec movl ebpesp 12 03 05 00 00 00 addl 0x0eax 17 00 14 R38632 y 18 5d popl ebp 19 03 ret 18 15213 F O2 Question On the previous slide the variables ep x and y are local in the same source file So why can t the compiler just generate completed code Why is relocation information necessary 19 15213 F 02 a 0 Relocation Info data ac 20 15213 F O2 Executable After Relocation and External Reference Resolutiondata mc 15213 F O2 Exercise Will the C compiler accept this code without an error Will the C compiler give a warning Will the C compiler overload the two symbols x because they have different data types Will the linker link these modules or abort with an error What will this program print when it runs 22 15213 F O2 In the previous slide what can you change to make the program work correctly i e print the initialized values of x and y 23 15213 F O2 Exercise Will the C compiler accept this code without an error Are the two variables X temporary What is their scope Is there a conflict between the two variables X How does the compiler handle these two variables How does the linker handle them 24 15213 F O2 Relocation In a relocatable file each section text data bss starts at address zero Offsets in the section are relative to zero In an executable file each section is bound to the absolute address at which it will be loaded in memory How does the linker know what address to bind each section to I That is how does the linker know where the program will be loaded in memory 25 15213 F 02 Where are programs loaded in memory To start with imagine a primitive operating system 0 Single tasking 0 Physical memory addresses go from zero to N o The problem of loading is simple load the program starting at address zero I Use as much memory as it takes 0 The linker binds the program to absolute addresses I Code starts at zero I Data concatenated after that I etc 26 15213 F 02 Where are programs loaded cont d Next imagine a multitasking operating system on a primitive computer 0 A physical memory space from zero to N 0 Memory must be allocated at load time o The linker does not know where the program will be loaded l The linker binds together all the modules but keeps them relocatable How does the operating system load this program I Not a pretty solution 27 15213 F 02 Where are programs loaded cont d Next imagine a multitasking operating system on a modern computer with hardwareassisted dynamic relocation o The O S creates a virtual memory space for each user s program I As though there is a single user with the whole memory all to itself 0 Now we re back to the simple model I The linker statically binds the program to virtual addresses I At load time the operating system allocates memory creates a virtual address space and loads the code and data I More about how this is done in a few weeks 28 15213 F 02 The linker binds programs to absolute addresses Nothing is left relocatable no relocation at load time Oxffffffff kernel virtual memory memory code data heap stack invisible to OXCOOOOOOO User COde user stack created at runtime A esp stack pomter memory mapped region for shared libraries 0x40000000 T k brk runtime heap managed by malloc readwrite segment 39data 39bSS loaded from the readonly segment executable file OX08O48OOO init text rodata O unused 29 15213 F 02 More details on program loading How does the O S know where to load the program and how much memory to allocate o The linker and the O S loader must agree on an object module format I The linker writes an executable file I The O S loader reads that file to load the program I The O S allocates the appropriate memory and reads the program code and data into memory 0 More on this in CS 333 30 15213 F 02 Loading Executable Binaries Executable object file for example program p 0 ELF header V t I dd Ir ua a r Program header table Process 39mage required for executables init and shared quotb 0x08048390 k rdtrr 0x08048494 symtab r H xt e e data segment 0x0804a010 reldata initialized rw debug Section header table OXO804a3bo required for relocatables 31 15213 F O2 Static Libraries archives p1 0 p2 c i i static library archive of 0 p1 p2 o libc a relocatable object files concatenated into one file executable object file only contains code P and data for libc functions that are called from pl c andp2 c 32 15213 F 02 Creating Static Libraries atoic printfc randomc atoic pr1ntfo randomc ar rs libca atoic printfc m randomc libc a 0 standard library 33 15213 F 02 Why do we need static libraries Why not just use Id to link atoio printfo randomo into a big relocatable file Iibca instead of an archive Iibca 34 15213 F 02 Commonly Used Libraries libc a the C standard library I 8 MB archive of 900 object files I lO memory allocation signal handling string handling data and time random numbers integer math libm a the C math library I 1 MB archive of 226 object files I floating point math sin cos tan log exp sqrt ar t usrliblibca sort forko fprintfo fpucontrolo fputco freopeno fscanfo fseeko fstabo ar t usrliblibma sort eacoso eacosfo eacosho eacoshfo eacoshlo eacoslo easino easinfo easinlo Using Static Libraries The linker tries to resolve all references by scanning the files on the command line in order I As each new 0 or a file obj is encountered try to resolve each unresolved reference in the list against the symbols in obj Command line order matters I In your Makefile where should libraries go on the command line 36 15213 F 02 Exercise Suppose you write a program that uses the powfunction from ibma which takes two double arguments double powdouble x double y Suppose you pass it an integer for y instead of a double and you find that it works correctly 1 How can you tell if pow implemented as a macro or a library function call List three different ways you can find out 2 When you assign an integer value to a float or double variable the compiler does the conversion for you Does the compiler do that when you pass an integer as an argument to a function that takes a double How can you tell 3 If pow or some other function is implemented as a macro that takes a double as an argument and the programmer passes it an int instead of a double then how can the macro still work correctly 37 15213 F 02 Shared Libraries Invented by ATampT in 1986 for Unix System V on PCs I In 1986 the Intel 386 came out I The PC was at last capable of meaningfully running Unix Microsoft later copied the idea DLLs What problem was ATampT trying to solve I PC distribution of Unix was on floppy disks 0 Lots and lots of floppy disks I Reduce the aggregate size of the distribution I Also conserve memory at run time 38 15213 F 02 Shared Libraries What problems do shared libraries solve today I Avoid duplicating code in the virtual memory space of many processes I Minor bug fixes of system libraries don t require a relink of all the user space programs 39 15213 F 02 Dynamically Linked Shared Libraries mc ac Partially linked executable libc so Shared library 0 dynammally relocatable object files P on disk libc so functions called by m c and a c are loaded linked and potentially shared among processes Fully linked executable p in memory 15213 F O2 The Complete Picture 4 0 ao libwhatevera libcso libmso i 41 15213 F 02 Problems to solve with shared libraries Where do you put them in memory I Solution Reserve a region of virtual memory for shared libraries What s the problem if each shared library function has its own reserved fixed address What s the problem if shared libraries can be relocated when loaded 42 15213 F 02 Problems with dynamic relocation Within your own program I Where are the shared library functions I How do you call them Within the shared library code itself I How to call other functions within the shared library I How to call functions in other shared libraries I How to access global variables if they are relocated 0 External global variables 0 Defined in the same file but relocated 43 15213 F 02 Version Control The biggest problem with shared libraries is version control Is a newly installed program compatible with the shared libraries that came with the O S A hassle on linux l Copy a binary program from another linux system I It won t run because of different version of shared libraries Are shared libraries worth the hassle Do they really solve a problem today 44 15213 F O2 A note on installable device drivers Byproduct of shared library technology These are cool I Buy commodity components retail I Install a device vendor s driver from a CD or Internet I No need to compile or link the kernel I Anyone can do it at home 45 15213 F O2 PIC problem with shared libraries could assign a chunk of address space to each possible shared lib but this is pain in posteriori therefore use Position Independent Code code more or less references addresses via table lookup plus offset more expensive but solves shared lib problem on UNIX maybe 5 instructions per single instruction for nonshared approach 46 15213 F 02 PIC workings with gcc 47 compile and link to create shared lib so gcc shared fPlC o ibmumbeso ac bc zc link to previous program that wants to use shared lib gcc o program mainprogc ibmumbleso NOTE table lookup info but no code added to program load and run execvp however first dynamic linking is done so that program can find ibmumbeso 15213 F O2 list of tools mentioned in 30 ar library archive tool libca lt o strings find C strings in a binary file strip throw out the symbol table nm list the symbol table enemy of strip 91pr readelf display structure of object file including elf header 9 objdump dump binary file in various ways l size simple info about textbss etc for size of binary file 8 hexdumpod hexoctal dumper 9 don t leave out ld linker and ldd dynamic loader 48 15213 F 02 Memory Management Gerson Roboy Portland State University Topics I P6 address translation I Linux memory management I Linux page fault handling I memory mapping classZOppt Building the Address Space Source Library ther v code 39 code vobjects Secondary memory 3 Q lgt Link Primary 1 39 Edit gt memory gt Load time 0Allocate primary memory Adjust addresses in address space 2 Copy address space from secondary to primary memory15213 F 02 Going way back in history Operating Unused S stem E In Use Process Limited versatility 3 15213 F 02 With multiple processes Operating Unused System E In Use Process 3 Issue Where do you load Process 2 pi s address space into primary memory Process 1 4 15213 F 02 Dynamic Memory Allocation Process wants to change the size of its address space I Mallocsbrk I Stack growth temporary variables May have to dynamically relocate the program 5 15213 F 02 A System with Physical Memory Only Examples I most Cray machines early PCs nearly all embedded systems Memory Physical Addresses I Addresses generated by the CPU correspond directly to bytes in physical memory 6 15213 F O2 Some problems with physical memory only I With multitasking you have to dynamically relocate programs when loading them I If the stack overflows the area allocated for it we re in trouble I The same with the heap I With swapping you have to dynamically relocate programs each time they are swapped in o Is that even possible How would you handle locally declared pointers 7 15213 F 02 VM Address Translation Processor I Onchip Main a MMU Memory a39 virtual address physical address 8 15213 F O2 A System with Virtual Memory Examples I Memory I workstatlons servers modern PCs etc Page Table Virtual Addresses PhySICal Addresses liltilull lllllllllllll l Address Translation Hardware converts virtual addresses to physical addresses via a lookup table page table 9 15213 F O2 Example 32 bit addresses page size is 4096 0x1000 How many bits is the offset into a page A pagealigned address has how many low order zero bits 10 15213 F 02 Example 32 bit addresses page size is 4096 0x1000 Consider some address 0x3e80a123 Low order 12 bits offset within the page 0x123 Address with low order 12 bits masked out address of the page 0x3e80a000 High order 20 bits alone are the page number 0x3e80a 11 15213 F 02 Previous example continued 32 bit addresses 4K pages Page table 1 page I 1 page 4096 bytes4 byte entry 1024 entries I 1024 entries x 4096 bytes 4 MB of virtual memory per page table 4 MB X 1024 page tables 4GB memory space 12 15213 F 02 Clarification Page tables and page directories are data structures in memory The O S kernel software sets them up and manages them The format of the contents is defined by hardware The hardware uses them on every memory reference to convert a virtual address to a physical address The PDBR tells the hardware where to look 13 15213 F 02 To allocate memory for a process now the O S doesn t have to manage contiguous blocks of memory All it has to do is find a set of available pages I The pages can be scattered all over the place I The pages are mapped into contiguous virtual memory regions I No more fragmentation Analogous to allocating files on a disk fixed size blocks 14 15213 F 02 What this means for linkingloading The linker binds programs to absolute addresses I No relocation at load time I No allocation of memory segments at load time kernel virtual memory memory invisible to usercode esp V stack V A Memory mapped region processes forshared libraries look just 4 llkethls In runtime heap via malloc Virtual uninitialized data bss memory initialized data data program text text forbidden 15 the brk ptr 15213 F O2 How ia32 Maps Virtual Addresses to Physical Ones 10 Virtual address word offset into physical and Virtual page 1 0 1 2 VPN1 VPN2 VPO word offset into word offset into page directory page table page directory page table pTE physical PDE address of page base PDBR if P1 physical address phys ca address of page directory of page table base if P 1 20 i 1 2 v PPN PPO Physical address 16 15213 F O2 Exercise Suppose a computer has 16bit virtual addresses 16bit physical addresses a page size of 64 bytes and two level page tables like a pentium How many bits is the VP0 How many entries in a page table How many bits is VPNO How many bits is VPN1 17 15213 F O2 Enquotv282 088 0 091 212 100 121 200 232 133 222 134 202 135 292 078 290 079 280 136 270 088 260 099 160 077 170 011 180 021 111 15 079 222 18 Entry 16 Previous exercise continued Here is a page table in 2 columns so it fits on the slide Consider virtual address 0x3e72 Suppose VPN1 points to a PDE which points to this page table The page table contains 10bit page numbers shown in hexadecimal To what physical address does V A 0x3e72 translate Entry 31 15213 F O2 Some Arithmetic VPO of 12 bits A page is 4096 bytes Each PD and PT occupies one page Each PDE and PTE is 32 bits 4 bytes I Each page directory contains 1024 PDEs I Each page table contains 1024 PTEs I Each page table points to 1024 pages 1024 pages 4Kbytes 4 MB covered by a page table 4MB 1024 PDEs 4 GB memory space covered by a page directory 19 15213 F 02 ia32 Page Table Structure Page directory 352 I 1024 4byte page directory page entries PDEs that point to page tables tables 1024 I one page directory per process PTEs I page directory must be in dil39f39e gr memory when its process is 1024 y 1024 running PDEs PTEs I always pointed to by PDBR Page tables 1024 I 1024 4byte page table entries PTEs PTEs that point to pages I page tables can be paged in and out 20 15213 F 02 ia32 Page Table Structure co ntI n ued Page directory 1152quot I A page directory defines the page virtual memory mapping for a tames process I Not all PDEs point to a valid PT c That is a process does not a e necessarily use its entire 4GB direcgory memory space 1024 1024 o The valid PDEs may be sparse in the PD PDEs PTEs Page tables I Valid PTEs may be sparse in the 1024 PT also PTEs I Some pages may be valid but not present 21 15213 F 02 Exercise Suppose we had a paging scheme on a computer with 8 bit addressing a page size of 16 bytes and 8bit page table entries How big a memory space can be expressed with 8 bits How many bits is a VPO How many bits is a VPN How many pages does it take to cover a memory space How many page tables do you need How many entries are there in a page directory 22 15213 F 02 P6 Page Directory Entry PDE 31 12119876543210 Page table physical base addr Avail G PS A CD WT USRNVP1 Page table physical base address 20 most significant bits of physical page table address forces page tables to be 4KB aligned vail These bits available for system programmers global page don t evict from TLB on task switch PS page size 4K 0 or 4M 1 accessed set by MMU on reads and writes cleared by software D cache disabled 1 or enabled 0 T writethrough or writeback cache policy for this page table Dgt IO gt US user or supervisor mode access RNV readonly or readwrite access E page table is present in memory 1 or not 0 31 1 0 Available for OS page table location in secondary storage P0 23 15213 F 02 P6 Page Table Entry PTE 31 12119876543210 Page physical base address Avail G 0 D A CD WT US RNV P1 31 Page base address 20 most significant bits of physical page address forces pages to be 4 KB aligned Avail available for system programmers g global page don t evict from TLB on task switch Q dirty set by MMU on writes A accessed set by MMU on reads and writes CD cache disabled or enabled W T writethrough or writeback cache policy for this page usersupervisor RNV readwrite E page is present in physical memory 1 or not 0 C 1 0 Available for OS page location in secondary storage P0 24 15213 F O2 Representation of Virtual Address Space PT 3 Page Directory P1 M1 0 P1 M1 K 2 PO MO o PO M1 0 PT 0 P1 M1 POMO P1 M1 POM1 1 P1 M1 POMO P1 M1 POM1 77 P0M1 PO M1 POMO POMO 0 Simplified Example I 16 page virtual address space Flags I P ls entry in physical memory I M Has this part of VA space been mapped 25 Page15 Page14 Page13 Page12 Page11 Page10 Page9 Page8 Page7 Page6 Page5 Page4 Page3 Page2 Page1 Page0 gt Mem Addr gt Disk Addr 15213 F O2 Questions If for every memory reference we had to do a twolevel table lookup then every memory reference would actually involve three memory references I Page directory page table and memory containing data Would this be good for performance How can it be optimized 26 15213 F O2 Translation Lookaside Buffer CPU ILI I result 394 L2 andDRAM A 12 virtual address VA L PM VPOJr L1 L1 16 y 4 Miss TLBT TLBI l i l i TLB L1 128 sets 4 linesset TLB hit I L III III gtI I I I I I I I I lt A A A A 10 TLB 16 sets VPN1 VPN 4 entriess 20 v v12 20 7 5 PPN PPO gt CT CI co PDE gt PTE PhYSical I 1 address PA PDBR Page tables 15213 F O2 What is the TLB The TLB is an onchip cache of page mappings The TLB converts a virtual page address to a physical page address On a TLB hit the TLB delivers a physical page address I Bypasses the page tables entirely Even on a TLB miss the page table entries may be in the memory cache 28 15213 F 02 Review of Abbreviations Symbols I Components of the virtual address VA 0 TLBI TLB index 0 TLBT TLB tag 0 VPO virtual page offset 0 VPN virtual page number I Components of the physical address PA 0 PFC physical page offset same as VPO o PPN physical page number 0 CO byte offset within cache line 0 Cl cache index 0 CT cache tag 29 15213 F 02 P6 TLB TLB entry not all documented so this is speculative 32 16 1 1 PDEPTE Tag PD V I 1 indicates a valid 1 or invalid 0 TLB entry I is this entry a PDE 1 or a PTE 0 I taq disambiguates entries cached in the same set I PDEPTE page directory or page table entry 0 Structure of the data TLB I 16 sets 4 entriesset entry entry entry entry set 0 entry entry entry entry set 1 entry entry entry entry set 2 entry entry entry entry set 15 30 15213 F 02 Translating with the P6 TLB 1 Partition VPN into CPU TLBT and TLBI 20 I 12 virtual address 2 Is the PTE for VPN VPN lVPOJI cached in set TLBI 16 4 I 3 m then build physical TL address TLB V B miss P E P E I Q 4 then read PTE and I I I I 20 l 12 PDE if not cached I PP IPPOI from memory and physical build physical page table translation address address GD 31 15213 F O2 The operating system kernel manages page tables in memory When the kernel modifies a page table entry what has to happen with the TLB 32 15213 F O2 Exercise With 32 bit addressing and a 4K page size why did they decide to use 2level page translation What size page table would you need with single level page translation 33 15213 F O2 Exercise The Pentium processor family has another paging mode with 4 megabyte pages How many pages are there in a 46 memory space How many bits are there in a virtual page offset How many bits are there in the page number 34 15213 F 02 Exercise With 4 meg pages what kind of scheme would work for address translation A disadvantage Internal fragmentation if you don t use the whole 4M page What s the advantage 35 15213 F 02 CS 201 Signals Gerson Robboy Portland State University Signals A signal is a message that notifies a process that an event of some type has occurred Signals are the operating system abstraction for exceptions and interrupts I Asynchronous l Interrupts the process like an interrupt but via software 2 15213 F O2 Signal Concepts Sending a signal I Kernel sends delivers a signal to a destination process I Kernel sends a signal for one of the following reasons 0 Kernel has detected a system event such as dividebyzero SIGFPE or the termination of a child process SIGCHLD 0 Another process has invoked the kill system call to request the kernel to send a signal to the destination process 3 15213 F 02 Let s pause for a concrete example A process dereferences a null pointer What happens at the hardware level You see something like Segmentation fault Core dumped Your program terminates The operating system lingo for how the kernel propagates an exception to the process is it sends the process a signal The process receives the signal I Usually this means the signal kills the process 4 15213 F 02 Signal Concepts cont Receiving a signal I A destination process receives a signal sent by the kernel I By default most signals cause the process to terminate I But there s a way a process can handle most signals We ll see how I Three possible ways to react o Ignore the signal do nothing 0 Terminate the process 0 Catch the signal by executing a userlevel function called a signal handler Analogous to a kernel exception handler Asynchronous A signal is pending if it has been sent but not yet received 5 15213 F 02 Signals Sent by the kernel to a process Different signals are identified by small integer ID s The only information in a signal is its ID and the fact that it arrived A few frequently seen signals ID Name Default Action Corresponding Event 2 SIGIN39I Terminate Interrupt from keyboard ctlc 9 SIGKILL Terminate Kill program cannot override or ignore 11 SIGSEGV Terminate amp Dump Segmentation violation 14 SIGALRM Terminate Timer signal 17 SIGCHLD Ignore Child stopped or terminated 6 15213 F 02 Default Actions Each signal type has a predefined default action which is one of I The process terminates I The process terminates and dumps core I The process stops until restarted by a SIGCONT signal I The process ignores the signal 7 15213 F 02 Putting it all together Remember exceptions An exception is an event that alters the flow of control at the hardware level I Control goes to the kernel via an interrupt vector I The kernel has a handler for each kind of event I Usually this detour of control is invisible to the user process For some events particularly faults the kernel handles the event by sending a signal to the process Signals are the higher level software abstraction of exceptions I Alters the flow of control of a process I Can also have a handler analogous to an exception handler 15213 F O2 Putting it all together continued Signals typically alter the flow of control at the user level I By default most signals but not all terminate the process I Can send control to a signal handlerin the user program 9 15213 F 02 Installing Signal Handlers The signal function modifies the default action associated with the receipt of signal signum handlert signal int signum handlert handler Different values for handler I SIGIGN ignore signals of type signum I SIGDFL revert to the default action for signals of type signum 0 Yes this is weird but you can assign these integer values to a pointer I Otherwise handler is the address of a signal handler 10 15213 F 02 Signal Handling Example void siginthandlerint sig printfquotProcess d received signal dnquot getpid Sig exit0 main Do stuff signalSIGINT siginthandler Do more stuff What exactly happens when signal is called from main What will happen when the user hits ControlC 11 15213 F O2 Signal Handlers A signal handler is a function you write to handle a signal I Called when process receives signal of type signum I Referred to as installing the handler I Executing handler is called catching or handling the signal When a signal is received control is diverted to the handler When the handler returns control passes back to I In some cases the next instruction I In some cases the instruction that was interrupted by an exception 12 15213 F 02 wait Synchronizing with children int waitint childstatus o What does the wait system call actually do 0 What is the default action of SIGCHLD o What does a SIGCHLD signal do if you have called wait 0 What does it do if you haven t called wait 0 Can you catch a SIGCHLD signal with a handler o What happens if you fork a child the child exits you don t have a SIGCHLD handler and you never call wait 13 15213 F 02 Exercise Write a small program that installs a handler for the SIGSEGV signal and then accesses an illegal memory address in order to execute the handler 14 15213 F 02 Sending Signals with kill Program kill program sends arbitrary signal to a process or process group Examples I kill 9 24818 0 Send SIGKILL to process 24818 I kill 9 24817 0 Send SIGKILL to every process in process group 24817 15 linuxgt forks 16 linuxgt Childl pid24818 pgrp24817 Child2 pid24819 pgrp24817 linuxgt ps PID TTY TIME CMD 24788 pts2 000000 tcsh 24818 pts2 000002 forks 24819 pts2 000002 forks 24820 pts2 000000 ps linuxgt kill 9 24817 linuxgt ps PID TTY TIME CMD 24788 pts2 000000 tcsh 24823 pts2 000000 ps linuxgt 15213 F O2 Other useful system calls include ltsystypeshgt include ltsignalhgt int killpidt pid int sig 0 Sends signal sig to process pid 0 Although the name is kill it can be used for communication l The recipient process can catch the signal if not SIGKILL I Synchronization between processes m 1smaPm Other useful system calls include ltsystypeshgt include ltsyswaithgt pidt waitpidpidt pid int status int options 0 A newer more versatile form of wait 0 Can wait on a particular pid a process group or all child processes 0 Options I WNOHANG Return immediately if no child has exited and if a child has exited return the pid I WUNTRACED Also return for children which are stopped but not traced 17 15213 F O2