EECS 471 Networked Operating Systems

Instructor: Patrick Troy

Teaching Assistant: Arunkumar Elango

Time: 1:00 - 2:00 MTWF

Room: LC E2

Description:
EECS 471 is a 4 credit ( 5 credits for graduate students ) course and covers network programming
and systems programming from the operating system viewpoint. Special emphasis is given on
standards based APIs, with explanation of typical interfaces.
The course work consists of:

4 Programming Assignments
2 Midterms
1 final

Tests will cover conceptual issues from kernel design and programming techniques covered in the
class.

Prerequisites:
EECS 371

Topics:

Process
Interprocessor Communication
Network and Network Protocols
Distributed processing
Network Programming

Academic integrity:

Students who fail to demonstrate on tests an understanding of the programs they have handed in will fail
the course.

You are not to show your program to anyone nor to look at anyone else's program. You may discuss
programming concepts but only in general terms.

A word of caution : Unix gives read permissions on your files to everyone, by default. This means, unless
you turn the permissions off, you run the risk of someone looking into your code.
Syllabus

1. The Unix Kernel and Processes System calls, POSIX and XOPEN APIs, Kernel design, Processes

2. Signals POSIX signals, signal handlers, default actions

3. Creating New Processes fork, wait, waitpid, exec

4. File systems File Table, File Descriptor Table, open, close, write, read, dup.

5. Inter-Process Communication pipes, named pipes, message queues, shared memory, and
semaphores

6. Networking Ethernet, internetwork, naming, ip numbers and resolution, ARP, IP semantics.

7. Sockets TCP and UDP.

Course Notes:
Kernel
Signals
Processes
Files
IPC
Networking
Sockets
TCP/IP
RPC
Kernel
In this section, we examine the basics of kernels and processes. These are the fundamental building blocks of
operating systems, and of sophisticated services.

Processes
Consider a process is a program in execution. A pure process is said to run on a virtual processor and thus has
the following properties:

Finite progress: over each period of time of length t, the probability that some process executes is bounded
by p>0.
Execution of a pure process is independent of any other process that is executing on the system (and is, in
particular, independent of the order or "interleaving" of execution.

The definition of pure process does not allow any interaction between processes, and that is not desirable.
However, the amount of interaction needs to be strictly controlled, to prevent errors in one process from being
propagated to unrelated processes. This unconstrained error propagation occurs in MS/DOS and MS/Windows
(But not Windows NT), enabling faulty programs to corrupt working programs.

Hence, we begin from pure processes and enable carefully controlled visibility of other processes. The most
central inter-process visibility is the file system, which is always available for sharing without any special
arrangements. For example, it is possible use an editor to modify a program's source code, save it, and then
without exiting the editor to invoke the compiler on the source code file.

Other types of interaction can be controlled through both protection mechanisms and explict calls. Examples of
these impurities are:

Signals: notification of asynchronous events (including control of some processes by other processes).
Message passing: sending data directly to another process (not indirectly through another process.
Shared memory: this is physical memory which is mapped into multiple processes address space.
Semaphores
Sockets codes

Kernel
The kernel is not a process. Rather it extends the base hardware to a virtual machine, which hides various details
of the low level implementation. The purpose of the kernel is to:

Implement the process abstraction

To provide protection for different users from each other and from the outside world.
To deal with error conditions and architectural ideosyncracies.

The Unix kernel is written almost entirely in C, with about 4,000-8,000 lines of code of assembler. Since the
kernel is the only part of the system which can execute privileged instructions, these instructions are coded in
assembly language.

Failures

The kernel is extremely important; if the kernel detects a failure its typical response is to panic, which causes a
reboot. There are two alternatives.
 Ignore the error: this technique is almost never used. Although the computer would reboot less often, the
error may contaminate the system allowing unauthorized accessed, giving incorrect results, etc.
Correct the state of a kernel: thereby removing the effect of the error. This is much more difficult, and may
allow errors to propagate.

The complexity of failed systems is much higher than of working systems; moreover failures are relatively rare.
Hence, trying to determine and fixed a problem is fraught with perils, and is impossible to exhaustively test.
Instead, it is a better policy to fail fast (ie. fail at the earliest detection of erroneous state), and restart, rather than
correct problems.

System calls
Processes communicate with the kernel via system calls which are entry points into the kernel. The set of system
calls in Unix can be found in section 2 of the manual pages (see man -s 2 Intro in Solaris). In addition, there are
many library calls listed in section 3 of the manual; all library codes invoke system calls for kernel services.
These code for these library calls are linked with the user executable by ld; by default the standard C library
(libc) is linked in together with C code. System calls themselves are implemented with trap instructions which
simultaneously enter the kernel at an indexed entry point and enable the execution of privileged instructions.

The limited number of system calls is prefered to branching to arbitrary location is the kernel since it restricts the
number of entry points. Since the kernel is charged with providing security, every one of these entry points must
be well guarded, checking that the process parameters are legal and that the process has permission to perform
the required operations.

Superuser

In Unix, the operating system functions are split between system processes and the kernel. Unix has two levels
of users in the system: ordinary users and the superuser. The difference between these two is that the super user
is allowed much less restriction on the system calls that are made--for example, the superuser can modify any
user's files whereas ordinary users can modify only their files and the files for which they have been given
explict access.

To be sure that these permissions are not abused, it is the processes responsibility to check appropriate
conditions since the kernel is extremely permissive with the superusers. Most violations of security in Unix
systems are the result of superuser processes failing in this responsibility--not kernel problems.

Concurrency
The Unix kernel is designed so that it is always in the context of a single process (after the first process, init is
created). The traditional Unix kernel allows only one process to be executing in the kernel at a time, and control
is given up voluntarily while in the kernel. Hence, there is no need for semaphores when constructing a Unix
systems. More modern Unix systems allow multiple processes to be executing in the kernel (in a multiprocessor
system), but the kernel has be modularized into subsystems which are largely independent. Any interactions
between subsystems must then be guarded with semaphores.

Process failures

There are many conditions which can cause a process to terminate, such as divide by zero, external termination
via kill -9, etc. The kernel cleans up after these processes as best it can, so for each process the kernel keeps
some process related info in the kernel.

Kernel-based process structures

The kernel tracks two types of information on a per process basis:

Infomation which is needed only when the process is running is kept in the u-area. The u-area is part of
the process and can be swapped out when the process is not running. But it exists in kernel space, not user
space, and hence can only be accessed by the kernel.
Information which is needed at all times is kept in the process table.
Signals
Signals are (primarily) asynchronous notification of events. There are many different signals which can arise
from within or outside the process.

Signals arrive for a process and are posted in the kernel. The kernel can then arrange:

Perform some default action on the process

To notify the process by causing a signal handler to be invoked in the process. The handler is a user level
procedure.

Where do signals come from

Signals come from either:

A different process: the process invokes a system call which posts a signal to the target process.
The same process: typically, an error such as divide-by-zero.
from the kernel: timer signal (requested by process)

Example:

Signals allow users to control processes. For example, typing the following in csh results:

^C in csh causes the shell to send a SIGINT to the current foreground process if any.
^Z in csh causes the shell to send a SIGSTOP to the current foreground process.
typing "fg" sends a SIGCONT signal to the foreground process.

Signal types:
termination of a process: death of a child
process induced exceptions: address violation, floating point error
unrecoverable errors during a system call: running out of resources such as memory
unexpected error during a system call: writing a pipe which has no reader, non existant system call, illegal
return. Could send an error indication, but programs which don't test error indications would never know.
emanating from processes in user mode: timer alarm or by sending a signal.
Terminal interaction: hangup on a login terminal
Tracing execution of the program.

What can be done with a signal?

abort:
ignore: as if it never happened (tosses the signal)
handle: provide a procedure to be called when the signal arrives (is pending)

In addition, another variable for each signal is for:

block: don't allow it to be serviced for now

What are the signal data structures in the Kernel?

a bit/signal for pending signals

 a bit/signal for blocked signals
a bit vector for each signals describing other signals to be blocked while in the signal handler.
a pointer/signal for handler

When are signals posted?

Either a process is executing (process in user mode) or the kernel is executing. After system startup, the
kernel executes in the context of some process (that in the u area), and the process is said to execute
in kernel mode.
Processes running in kernel mode are non-pre-emptible. The only way to give up control of the kernel is to
exit the kernel or to go to sleep. (Processes running in user mode are pre-emtable.)
The kernel selects another process to run either:
1. when the current process goes to sleep
2. when the current process is coming out of kernel mode.
When the process executing changes, it is called a context switch.
Signals are posted only when in kernel mode. These signals can come from:
The kernel executing on behalf of the process
Other processes which trap
Interrupts
trap for the current process
Since a process can send another process a signal, the set of posted signals are kept in the process table
(not the u area).
Note that signals are represented by a bit in the kernel. Multiple signals can result in a single call

What happens if there is a signal handler?

the signal is caught as follows

the kernel fakes a procedure call on the user stack, and the signal is blocked
the procedure is called (by the process returning to user mode)
when it returns the procedure executing at the time of the call is invoked.
delivery of the caught signal is unblocked when the handler completes

Why do we want signal handlers?

Signal handlers allows us to defer signal actions until cleanup, allow us to prevent corruption of data structures
(ex iosignal arrives while we are updating I/O structure), to paint the screen (in an editor when we bring it to the
foreground).

POSIX signals

POSIX signals
Signal name Use action
SIGALRM Timer alarm (see alarm()) exit
SIGABORT Abort process (see abort()) core
SIGFPE Illegal floating point operation (hardware fp exeption) core
SIGHUP Controlling terminal hung up exit
SIGILL Executed an illegal machine instruction core
SIGINT Process interuption (type ^C) exit
SIGKILL Kills a process (cannot be ignored) (kill -9) exit
SIGPIPE Illegal write to a pipe exit
 SIGQUIT Process quit (type ^\) core
SIGSEGV Memory address violation (ex. deref null pointer) core
SIGTERM Process termination (kill pid) exit
SIGUSR1 User defined signals exit
SIGUSR2 User defined signals exit
SIGCHLD Sent to a parent when it's child dies ignore
SIGCONT Resume execution of a stopped process (type fg) ignore
SIGSTOP Stop a process stop
SIGTTIN Stop a background process when it tries to read to its controlling terminal stop
SIGTSTP Stop a process by sending a ^Z stop
SIGTIOU Stop a background process when it tries to write to its controlling terminal stop

Signal library call

The original version of signals, which described actions associated with signals via the signal system call, had a
race condition. When a handler was called, the default behavior was installed into the handler. If another call
occured before the handler could call signal again, the default behavior (ex. termination) could occur.

sigaction

Installs/removes a signal handler.

#include < signal.h >

int sigaction(int signum, struct sigaction *action, struct sigaction *oldAction);

where

struct sigaction {
void (*sa_handler)(int);
sigset_t sa_mask;
int sa_flag;
};

where sa_handler is one of:

SIG_IGN: ignore
SIG_DFL: reinstall default action
handler function pointer

and sa_mask is set of signals to block while in the handler in addition to signum and currently blocked signals.
The third element sa_flag is either 0 or SA_NOCLDSTOP.

SA_NOCLDSTOP can be used with SIGCHLD which causes a signal to be sent to the parent when the child is
terminated but not when the child is stopped.

sigprocmask
We can set the set of signals to be blocked with the call:

int sigprocmask(int cmd, const sigset_t *new_mask, sigset_t *old_mask)

Where cmd is one of the following:

SIG_SETMASK: set the set of blocked signals to exactly that contained in new_mask. (old_mask is set to
the previous value)
SIG_BLOCK: add the signals specified in new_mask to the set of signals already blocked.
SIG_UNBLOCK: remove the signals specified in new_mask from the set of signals already blocked.

Creating masks
Since the type of a signal mask will differ between system, portable code requiers the manipulation of signal
masks through an API.

int sigemptyset(sigset_t *sigmask);

int sigaddset(sigset_t *sigmask, const int signal_num);
int sigdelset(sigset_t *sigmask, const int signal_num);
int sigfillset(sigset_t *sigmask);
int sigismember(const sigset_t *sigmask, const int signal_num);

Concurrency issues

Consider a signal handler which maniputes a data structure which is also maniputated in non-signal handler part
of the code. Then it is possible that the signal handler is called while the data structure is being manipulated,
leaving the data stucture in an inconsistent state.

In such cases, it is necessary to block the signal during the manipulation of the data structure
using sigprocmaskIt is also possible that two signal handler manipulate the same data structure (or that the same
handler is called for different signals). In that case, it is necesssary to block all of these signals when servicing
any of them. For this purpose of sigaction element sa_mask is used.

Long jump vs. Exceptions

A signal may make it desirable to go back to a previous point in the program. This is useful when an error must
be dealt with at a higher level than the context in which it appears.

The APIs setjmp and longjmp allow multiple procedure call nesting levels to be returned from at once. The
signal versions of these reset signal flags.

int sigsetjmp(sigjmpbuf env, int save_sigmask)

If save_sigmask is non-zero, then the sigmask is saved at the sigsetjmp point in the env.

int siglongjmp(sigjmpbuf env, int ret_val)

Jumps bak to the sight of the sigsetjmp and "completes" the call by giving a non-zero return value of ret_val. (A
zero return value is returned the first time). In C++, exception handling is used for this purpose via
the try/catch/throw language primitives. The advantage of C++ exception handling is that automatic variables
(local variable allocated on the stack) are destucted, while longjmp does not.
kill

The kill call enables a signal to be sent between processes. The processes must have the same real or effective
user ID, or the sender must be super user.

The call specifies the process Id to be the target and the signal to be sent to that process
int kill(pid_t pid, int signal_number)

which returns 0 if success and -1 on failure.

The meaning of pid is as follows:

pid > 0: the process id to receive the signal

pid=0: to all processes in the same process group as the sender
pid=-1: send to all processes whose real user ID is the same as the effective user ID of the calling process.
If superuser, to all processes (This is not POSIX behavior, just UNIX).

Alarm

Some work needs to be done periodically in a system. Ex. clock synchronization, check that all the processes for
an application are running, forcing disk writes out to physical storage.

unsigned int alarm(unsigned int time_interval);

Where time_interval is in seconds. If time interval is 0 the alarm is turned offed. After the timer expires, a
SIGALRM signal is sent to the process. Returns the amount of time from the previous alarm call.

BSD has ualarm in which time is specified in microseconds.

File Descriptor, Tables, and Operations

In this section, we describe the basic way in which files are accessed through the kernel. We defer to a later
section the means by which files are constructed on disk, and the data structures which are used to represent
files.
Processes
Information stored in the process:
Field Meaning
rUID the real user ID (UID of parent)
rGID the real group ID (GID of parent)
eUID the effective user ID (changed on setuid bit or seteuid)
eGID the effective group ID (changed on setgid bit or setegid)
saved set-UIC
saved set-GIC
Process group ID: process ID which identifies multiple processes and is the PID of the
PGID
lead (ancestor) process
Session ID: process ID which identfies multiple processes which are part of the same
SID
terminal session
Additional GIDs a user can belong to multiple groups
Current directory current working directory inode id
Root directory root directory inode id
Signal handling pending signals, signal handlers, blocking during signal handlers
Blocked signals set of signals which are blocked
Umask set of permissions which are removed from created files
Nice value priority level of the process
Controlling
Terminal associated with process
Termininal

Ordinary users cannot change UID/GID except from the set of UIDs/GIDs (effective, real, or saved) or via
setuid/setgid bit.

Process creation and management

New process creation

The initial process init is created by the kernel. All other processes are created from some process by a fork. On
a fork, a new process is cloned from the original process (including the u area). The cloned process is called
the child, the original process is called the parent.

The child differs from the parent in the following way:

Process ID (PID)
Parent Process ID (PPID)
Pending Signals are cleared in the child
Alarm clock time: reset to 0
file locks are not inherited by child

Calls
The process management calls are:

fork:
 exec:
wait:
exit:

fork

prototype:

pid_t fork(void);

If the fork succeeds, it returns 0 to the child, and the PID of the child to the parent.

If the fork fails, it returns -1 and sets the value errno with the value:

ENOMEM: Insufficient memory to create the new process

EAGAIN: The number of processes in the system exceeds the limit

POSIX defines the maximum number of processes that can exist in a system (MAXPID) and for a single user
(CHILD_MAX).

Clearly, a new process means copying over the u area, and inserting a new process in the process table. There are
three parts of the process which reside in user space:

text region: contains executable machine instructions

stack:
data:

The text region, like file table entries, are shared (since they are read-only). Stack and data are not, and logically
need to be copied, even though most likely a forked process will exec a different executable, replacing all the
regions associated with the parent.

To save extraneous copies, a common implementation technique is copy-on-write in which the child shares read
only copies of all regions. If the process writes a read-only region, a copy is then made with write permission.

_exit

The exit call terminates a process, freeing up the regions associated with the process (user memory), closing file
descriptors, and releasing the u area. However, the process table entry remains intact. A process without u area
but with a process table entry is called a zombie.

void _exit(int exit_code)

where the lower 8 bits of exit code is the value returned for the process. By convention, 0 indicates a successful
termination.

Usually, users call exit, which performs the following functions:

flushes all streams

calls procedures registered with atexit
calls _exit

Removing zombies
If a child process, c, dies before its parent, than c becomes a child of init. To remove the zombied process, a wait
(or waitpid) must be performed by the parent.

pid_t wait(int *status_p);

pid_t waitpid(pid_t child_pid, int *status_p, int options);

Returns the process id of the child process, or -1 on failure. The parameters are:

child_pid
> 0: Waits for the child with that PID
= 0: Waits for any child in the same process group as parent
=-1: Waits for any child
< -1: Waits for any child whose process group is the absolute value of child_pid
status_p
child exit status (bits 8-15)
core file flag (bit 7)
signal number (bits 0-6): zero if termination was via _exit
options
WFNOHANG: declared in . Non-blocking call
WNOTRACED: will wait for a process that is stopped (for shell job control)

The errno for wait/waitpid are:

EINTR system call interupted by signal

ECHILD
wait calling process has no unwaited-for child processes
waitpid childPid value illegal or process cannot be in state defined by option value.
EFAULT statusPtr is an illegal address
EINVAL options value is illegal

waitpid can be either blocking or non-blocking, and can wait for any child that is stopped due to job control.

Rather than use the bit positions, you should use the following macros:

WIFEXITED(* status_p): returns non-zero iff process was terminated via _exit.
WEEXITSTATUS(* status_p): If process terminated via _exit, this returns the exit paramter
WIFSIGNALED(* status_p): Returns a non-zero value iff a child was terminated due to a signal.
WTERMSIG(*status_p): If process terminated via a signal, signal number that caused termination
WSTOPPED(*status_p): Returns a non-zero value if a child process has been stopped due to job control
WSTOPSIG(*status_P): Returns the signal number that had stopped a child process.

exec
There are several different exec calls, enabling:

The exec call contains either a filename or path:

filename: if the file name contains a "/", then it specifies the location of the file, otherwise the shell
PATH variable is used to specfy the directories to look into for filename. (Can be either shell script
or binary)
path: specifies the directory of the file. (must be binary)
An environment to be passed to the executable (has an e in the exec name.
A null terminated set of arguments or a null terminated argument vector.

int execl(const char *path, const char *arg, ...):

 int execlp(const char *filename, const char *arg, ...):
int execle(const char *path, const char *arg, ..., const char **env);
int execv(const char *path, const char *argv[]):
int execvp(const char *filename, const char *argv[]):
int execve(const char *path, const char *argv[], const char **env);

The exec system call does the following:

It passes the arguments (strings) to the new program. These arguments are passed to main in the following
two variables
argc: the count of the number of arguments - 1.
argv: an array of strings 0...argc
It passes the environment which is an array of name=value strings. The array comes from:
the exec system call (if there is an "e" in the name after exec),
otherwise
the environ global variable if ANSI C, otherwise
as a third argument from main.
Note that by default, most compilers are ANSI C although some (gcc) also support K&R C.
It changes a number of settings in the u area based on the executable file name

If the exec succeeds:

the process's stack, data, and text regions will be replaced

file descriptors will be closed if fcntl close-on-exec flags were set.
effective UID: changed if exec'ed program has set-UID flag set
effective GID: changed if exec'ed program has set-GID flag set
saved set-UID: changed if exec'ed program has set-UID flag set
installed signal handlers are replaced with signal's default action.

Note that fork and exec are seperate calls, increasing the flexibility and enabling actions to occur between the
fork and exec.

Race conditions, etc.

Process fork, wait and exec are a very effective means of building multi-process applications.

When fork returns to either both parent and child exist

Parent can execute system calls to define the state of the child at start up (eg. blocking signals).
Parent can synchronize with the termination of child (via wait), and hence know that all the childs actions
have completed.

We shall see when we get to networked machines, that these conditions do not hold.

Process groups

A process group is a set of process with the same PGID. The PGID is the PID of the lead process.

This is the primary mechanism for dealing with groups of processes.

#include
#include

pid_t setpgp(void);
pid_t getpgid(void);
The setpgp sets the process group id to the PID.

The getpgid returns the process group ID.

Sessions
A session contain one or more process groups
#include
#include

pid_t setsid(void);

The setsid sets the session Id and pocess group id to the PID.

Other API's
#include <sys/types.h>
#include <unistd.h>

pid_t getpid(void); // get process id

pid_t getppid(void); // get parent process id
pid_t getuid(void); // get real user id
pid_t getgid(void); // get real group id
pid_t geteuid(void); // get effective user id
pid_t getegid(void); // get effective group id
pid_t setuid(uid_t uid); // get real user id
pid_t setgid(gid_t gid); // get real group id
pid_t seteuid(uid_t uid); // get effective user id
pid_t setegid(gid_t gid); // get effective group id

Notes:

setuid (setgid)
Superuser: set real, effective, and save-set uid (gid)
otherwise: set effective UID to the parameter if it matches the real or saved-set UID.
seteuid (seteuid) like setuid, but if superuser only sets the effective UID
File types

regular: ordinary Unix files

directory: similar to ordinary files but can only be accessed and modified through restrictive system calls
device files: associates device names with their driver. There exists two types of devices:
block special: Memory devices such as disk which enable caching (ie buffering in the kernel) and
block accesses.
character files: also called raw devices. (It is possible for disks to be both a character and block
device).
fifo: pipes
symbolic links

Of course, new types can be added as Unix evolves.

Disk data structures

A disk is divided into partitions.

Partitions are joined together logically only after the kernel boots, via mount. However, this is system
administration, and hence not covered by POSIX.

Partitions

The disk is divided into partitions, which are logical disks. Each partition contains a logical file system.

Not only is each partition logically complete, but different types of filesystems can be stored on different
partitions. For example, a linux file system in one partition and a windows FAT16 file system in a different
partition.

It is necessary to perform a file system specific format on the disk to lay down the data structures on which the
file system will be built. We describe this in the following sections.

A partition is divided into blocks, typically of 4-8Kb. The blocks are of the following forms:

boot block: used to start the OS

super block: describes the partition
inode blocks: describes a file
file blocks: the data contained in the file
indirect blocks: used to construct large files
double indirect blocks: used to construct very large files

Boot block

Not all partitions are boot partitions. However, there must be a bootable partitions, which enables the kernel to
be loaded. Only after the kernel is loaded, can the kernel understand the rest of the partitions to access the file
system.

Superblock

Each partition is described by a superblock. The super block contains:

The size of the partition

The number of inodes
 The number of file blocks
The size of flile blocks
the set of free blocks
the set of free inodes
Shutdown status

inodes

Each file on disk is described by an inode, which contains the following information about a file:

inode number
file type
hard link count
UID
GID
size in bytes
permissions: read,write,execute, set-uid, set-gid
last accessed time
last modified time
last change time: last time the file access permissions, UID, GID, or hardlink count have changed.
indirect block
double indirect block

Each inode is kept at a fixed address, and the root inode is at index 2 within the partition.

Directories

A directory could almost be an ordinary file, but because of its importance structurally to the filesystem, there
are special APIs to manipulate it.

The directories consist of a number of pairs of <names, inode>.

File operations

open: create a new entry in the File Descriptor table

creat: like open, but a new file is created
dup: copy over a file descriptor into the lowest number file descriptor
pipe: create a pipe
close: remove a File Descriptor entry
mknod: creates special, regular file, or named pipe
link: Create a directory entry for an existing file
unlink: remove a directory entry
chown: Change the owner and group of a file
chmod: Change access modes of the file
stat: Info about files
read: input
write: output
lseek: change the file pointer
chdir: Change the current directory

File Descriptor Table

There is a File Descriptor table per process in the u area. A file descriptor entry contains:
 A pointer to a file table entry

Several File Descriptors are opened for every process:

1. stdin
2. stdout
3. stderr

The File Descriptor table contains OPEN_MAX entries, which must be at least as large as
POSIX_OPEN_MAX.

File Table
There is one File Table in the kernel. File Table entries are pointed to by File Descriptors, and in turn point to
file IDs:

count of the number of File Descriptors pointing to this entry

access mode: read or write
file ID: (called inode in Unix parlance)
current offset into the file

Opening, Closing and Manipulating file description table

Open

Finds the lowest numbered free file descriptor entry, and creates a new entry which points to a new file table
entry.
#include <sys/types.h>
#include <fcnt.h>

int open(const char *pathName, int accessMode, mode_t permission);

which returns -1 on failure, the file descriptor table index on success.

The parameters are:

pathName is either an:

absolute path: if it begins with a /
relative to current working directory: otherwise
accessMode contains one of the following:
O_RDONLY: open the file with read only access
O_WRONLY: open the file with write only access
O_RDWR: open the file with both read and write access.
In addition, the following options may be ored with the above:
O_APPEND: Append data to the end of the file. (regular file only)
O_CREAT: Create the file if it does not exist. (regular file only)
O_EXCL: Used only w/O_CREAT, to specify that the open fails if the file already exists. (regular
file only)
O_TRUNC: If the file exists, delete its contents setting file size to zero. (regular file only)
O_NONBLOCK: Any subsequent read or write on the file is non-blocking. (FIFO and device files
only)
O_NOCTTY: Specifies that the named terminal device file is not to be used as the calling process
control terminal. (terminal device files only)
 permission: used only if the file is created to set the owner/group/other file permissions, otherwise
ignored. Defined in <sys/stat.h>. The actual file permissions set are permission - umask.

Creat
Create a new file and open it using first unused file descriptor.
#include <sys/types.h>
#include <fcnt.h>

int creat(const char *pathName, mode_t permission);

This is equivalent to:

open(pathname, O_WRONLY|O_CREAT|O_TRUNC, permissions);

Dup
int dup(int fd)

Finds the first unused file descriptor and copies the file descriptor at fd to it.

Example of replacing stdin with "/tmp/x": close(0); fd = open("/tmp/x", O_RDONLY); dup(fd); close(fd);

Close
Frees the file descriptor in the process.
#include <unistd.h>

int close(int fdesc)

returns -1 on failure, 0 on success.

Controlling open files

Read

Read a specified number of bytes into a buffer, given a file descriptor.

#include <sys/types.h>
#include <unistd.h>

ssize_t read(int fdesc, void *buff, size_t size)

returns number of bytes read on success, -1 on failure. The number of bytes read can be less than that requested
on end-of-file. arguments:

fdesc: an open file descriptor

buff: buffer of at least size bytes
size: number of bytes to be read.

Can be interupted by a signal.

Write
Write size bytes from buff to file specified by fdesc.
#include <sys/types.h>
#include <unistd.h>

ssize_t write(int fdesc, const void *buff, size_t size)

returns -1 on failure, number of bytes written on success.

fsync
#include

int fsync(int fildes);

The fsync() function moves all modified data and attributes of the file descriptor fildes to a storage device. When
fsync() returns, all in-memory modified copies of buffers associated with fildes have been written to the physical
medium.

This call is useful since write to block devices (such as file systems) are buffered and not written for up to 30
seconds typically. In cases where the completion or ordering of writes is important, fsync's must be performed.

Lseek

Change the position in the file.

#include <sys/types.h>
#include <unistd.h>

off_t lseek(int fdesc, off_t pos, int whence);

returns -1 on failure, number of bytes written on success.

Whence specifies what pos is relative to

SEEK_CURR: Current file pointer address

SEEK_SET: the beggining of the file
SEEK_END: the end of the file

if lseek seeks to a position beyond the end of the file, and the file has been open for write then the file is
extended with missing blocks (which are given default value of 0). Hence, a file may have a megabyte size, but
not consume a megabyte of storage. (If file was open read-only, the operation fails)

fcntl
#include <fcntl.h>

int fcntl(int fdesc, int cmd, ...);

G_GETFL: returns the access control flags of the file descriptor fdesc
G_SETFL: Sets the O_NONBLOCK and O_APPEND to the values specified in the third argument of
fcntl.
G_GETFD: returns the close-on-exec flag (0 for false, non-zero for true).
G_SETFD: third argument is 0 to clear and 1 to set the close-on-exec flag.
G_DUPFD: duplicates the file descriptor in the first unused file descriptor which is greater than or equal
to the third paramenter. Returns the duplicated file descriptor.
Miscellaneous
Chown

Change the owner or group of the file

#include <unistd.h>

int fchown(int fdesc, uid_t uid, gid_t gid);

int chown(const char *pathName, uid_t uid, gid_t gid);
int lchown(const char *pathName, uid_t uid, gid_t gid);

fchown works on the file descriptor, while chown and lchown work on path. The difference between chown and
lchown is that if the pathName specifies a symbolic link, lchown changes the symbolic link's UID and GID,
while chown changes the referenced files UID and GID.

If _POSIX_CHOWN_RESTRICTED is

defined: then if superuser can change any uid,gid otherwise if eUID=fileUID and gid is either an effective
or supplemental group id, then the gid can be changed.
undefined: if eUID=fileUID or eUID=0, then we can change the fileUID and fileGID. If not super user,
changing fileUID (fileGID) will clear the set-UID (set-GID) bit. (implementation dependent if superuser).

The above restrictions are to prevent security holes.

If uid (gid) is equal to -1, then uid (gid) is unchanged.

Chmod

Change owner, group, other permissions, set-UID, set-GID, and sticky bit. The caller must be the owner of the
file or super user.
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

int fchmod(int fdesc, mode_t flag);

int chmod(const char *pathName, mode_t flag);

Directory
Link

Adds another directory entry which points to the file's inode.

#include <unistd.h>

int link(const char *currPathName, const char *newPathName);

returns -1 on failure, 0 on success. Arguments

currPathName is a absolute or relative pathname of a file

newPathName is an absolute or relative pathname

In unix, both pathnames must be in the same partition.

Unlink

Removes a directory entry.

#include <unistd.h>

int unlink(const char *pathName);

returns -1 on failure, 0 on success.

Rename

Removes a file name from one directory and adds it to another.

#include <unistd.h>

int rename(const char *currPathName, const char *newPathName);

returns -1 on failure, 0 on success.

Mkdir

Create a new empty directory.

#include <sys/stat.h>
#include <unistd.h>

int mkdir(const char *pathName, mode_t mode);

returns 0 on success, -1 on failure.

The pathName specifies the directory to be created, the mode less the umask is used to set the file access
permissions.

Rmdir

Remove an empty directory

#include <sys/stat.h>
#include <unistd.h>

int rmdir(const char *pathName);

returns 0 on success, -1 on failure.

The pathName specifies the directory to be created, the mode less the umask is used to set the file access
permissions.

Traversing the directory

Read-only access to the directory can be provided by the following calls:
#include <sys/types.h>
#include <dirent.h>

typedef struct dirent Dirent;

DIR *opendir(const char *pathName); // open the directory for read & point to first entry
Dirent *readir(DIR *dirFdesc); // get the next directory entry in the file
int closedir(DIR* dirFdesc); // close the directory file
void rewinddir(DIR *dirFdesc); // point DIR at the first entry in the directory

Fifo Files (named pipes)

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

int mkfifo(const char *pathName, mode_t mode);

Symbolic Links
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

int symlink(const char *existingPathName, const char *symLinkPath);

int readlink(const char *existingPathName, char *symLinkPath, int size);
int lstat(const char *existingPathName, struct stat *StatPtr);

File locking
Unix is highly oriented towards shared access of files. File locking can either be mandatory (enforced by the
kernel on all accesses) or advisory (correct locking requires processes to use a given locking sequence.

POSIX supports only advisory locks. To use advisory locks all accesses to possibly locked files follow the
following sequence.

set a lock on the file region desired

access the locked region
release the lock

Fcntl for file locking

#include <fcntl.h>

int fcntl(int fdesc, int cmd, ...);

where cmd is one of:

F_SETLK: set file lock, but don't block if cannot succeed immediatly.
F_SETLKW: set file lock, blocking if cannot succeed immediatly
F_GETLK: finds out what process has locked the given file.

the third argument is a pointer to the flock structure:

struct flock {
short l_type; /* lock type */
short l_whence; /* relative to where */
off_t l_start; /* starting offset relative to whence */
off_t l_len; /* length of locked region */
pid_t l_pid; /* PID of a process which has locked the file */
};

where l_type is one of

 F_RDLCK: sets a read (shared) lock
F_WRLCK: sets a write (exclusive) lock
F_UNLCK: unlocks a specified region

where l_len:

>0: size of the locked region in bytes

=0: lock the entire rest of the file, even if it grows.
Interprocessor Communication
We have already discuss one very limited form of communications, called signals. Signals are used primarily to
control groups of processes.

System calls are atomic in Unix. That is either all of the effects of a system call are visible to other processes or
none of them are. Hence, basic synchronization is performed using system calls.

There are two types of system calls; fast and slow. Fast system calls can be performed without any waiting; an
example is reading the processes PID. Slow system calls may require waiting; for example, many file system
syscalls (including all that use a pathname) may have one or more waits as they traverse directories and inodes.

A slow system call can be suspended, but only at well defined points which are explicitly coded into the kernel.
Hence, the filesystem path accessing syscall may suspend and wake up after each inode or directory read. If the
system call is suspended (as opposed to completed) the process will be blocked.

There are two ways to make slow system calls into fast (non-blocking) calls:

Non-blocking: these calls fail rather than block.

Asynchronous: these calls provide fast returns, even if they don't complete. The process (user space)
continues executing after the system call returns. The process must later check whether the call completed,
via system call or with a signal.

We now begin discussion of other forms of communications between processes. This communication includes:

Files: most basic form of communication (And the only one that survives system crashes).
Pipes: specialized file "streams"
POSIX 1.b (Formerly POSIX 4)
Message: atomic variable length communications
Shared Memory: multiple processes sharing the same physical memory
Semaphores: memory-based synchronization
Unix History
IPC Uses
Domain Name System (DNS)
The name scheme of the internet is heirarchical. A name such as [Link] shows for level of the
heirarchy:

1. edu: is the top level domain, and contains all universities

2. uic: is a subdomain of edu
3. eecs: is a subdomain of uic
4. bert: is a hostname, not a subdomain

This scheme allows universities to determine and administer third level names (which must be unique at uic) and
hostnames can be chosen and administered by the units.

Names

Can be either absolute or relative. Relative name end with a period (and must be interpreted in some
context) absolute names are fully qualified.
Domain Names are case insensitive, components are up to 63 characters long, and full name is less than
255 characters.
Administration of subdomains or hosts is determined by the (sub)domain which contains the entity.

Name servers
Domains are divided into non-overlapping zones

Example: [Link] wants to communicate with [Link].

it requests its local domain name server [Link] to look up [Link].

if the server does not know [Link], it requests [Link].
[Link] knows where [Link] is.
[Link] knows where [Link] is.
[Link] knows where [Link] is.

Address Resolution Protocol (ARP)

To find the data link address (typically ethernet) for a given IP number, a hosts broadcasts "who is IP address
x.y.z.w?" and encloses its return address. Host x.y.z.w responds with its ethernet address which can be used to
transmit the data.
Network Layers
Networks are divided into layers:

Network layer: Adds routing beyond the local network. (packet)

Data link layer: takes a raw transmission layer and converts it into a form that is free from undetected
errors. Data link works on the "local network". (frame)
Physical layer: includes electrical characteristics, connector characteristics, length of wires. (bit)

We first describe the Physical and Link layers, and then show how they are connected into the network layer.

Physical and Link layer

We describe the base technology with a joint description of the Physical and Data link levels. We are primarily
interested in ethernet, since that is the dominant technology, on the LAN.

Ethernet
Ethernet is a shared, single logical wire system:

Each wire segment is limited to 250m

Up to 4 segments allowed (using 3 repeaters) yielding a 1km maximum on an ethernet.
Vampire taps (which puncture the cable) can be made in the wire at 2 meter intervals

The ethernet protocol needs to ensure one adapter gets exclusive use of the ethernet. Protocol is as follows:

An adapter desiring to transmit listens to the ethernet and waits until no one else is transmitting
The adapter simultaneously transmits and listens to the ethernet. If there is no conflict, the transmission is
successful and the protocol ends.
if there is a conflict, the adapter waits a random amount of time, and then starts at the beginning.

The wait period doubles with every unsuccessful transmission (up to some maximum), increasing by a factor of
2 the probability of a successful transmission. (This is called binary exponential backoff)

Ethernet is one of a family of protocols based on CSMA/CD, which stands for Carrier Sense Multiple
Access/Collision Detection. The first CSMA/CD network was AloahNet, a wireless network in Hawaii which
was designed to communicate between the Hawaiian islands.

The works well when traffic is light---in which case there is no waiting--- and when traffic is heavy, the protocol
rapidly converges and hence the permission to broadcast does not use too much bandwidth (logarithmic in the
number of transmitters).

Packet format:

Preamble: 7 bytes (10101010)

Start of frame: 1 byte (10101011)
Destination Address: 2 or 6 bytes
Source Address: 2 or 6 bytes
Length of data: 2 bytes
Data: 0--1500 bytes
Padding: 0-46 bytes
Checksum: 4 bytes
Notes:

Addresses which start with a 1 are group addresses (which can have multiple recipients) and all 1s is a
broadcast which goes to every ethernet address on the network.
10MBit ethernet requires 6 byte addresses.
Minimum packet size is 64 bytes, to ensure detection of conflicts everywhere (This is called 512 bit
times).

Vampire taps are not as reliable as connectors, since it is possible to break a cable, and also the tap if missplaced
can cause problems. Hence, most ethernet installations usedn hubs, which allow all the computers in an area to
be connected to the hub, and then the hub is connected to the backbone (by a vampire tap).

Cabling has also change from coaxial cabling to telephone style using modular connectors (RJ-45). The
connectors are slightly larger than telephone connectors (RJ-11) since RJ-45 has 8 wires vs. RJ-11's 4.

Ethernet Switching
As computers became faster, the 10Mb speed of ethernet (1.25 MByte) became a bottleneck. Moreover, the
ethernet segment is shared so that is the total bandwidth.

To increase the bandwidth available per processor, the industry invented ethernet switches. Switches look like
hubs: the difference is that computers connected up do not share the switches bandwidth. Switches are
physically different ethernets but logically the same network; one consequence is that wire lenght segments on
switch is for each port (in hubs they sum).

In other words, if 4 computers, A,B,C, and D, are connected to a switch, then A can communicate with B
simultaneously with C communicating with D. Nevertheless, the ethernet acts logically as a single ethernet.

An N port switch can increase bandwidth up N/2 times an N port hub.

Fast Ethernet
Ethernet runs at 10Mbit per second, and is rapidly being replace by fast ethernet 100Mb/s. The Fast ethernet
standard, 802.3u, is actually an addendum to the base ethernet standard. So everything was designed to be as
little changed as possible from the original standard.

Because the length of the ethernet packet is tied to maximum ethernet size, increasing the speed by a factor of
10, means decreasing the maximum length to 100m. This cabling is usually either:

100 Base-TX -- Unshielded Twisted Pair Category 5 cable (2 pair)

100 Base-T4 -- Unshielded Twisted Pair Category 3 cable (4 pair)

Category 3 has inferior performance to Category 5 (need twice as much of it), but is common telephone wire, so
it already exist in many buildings. Unless there is some reason why this cable must be used, Category 5 is
preferred.

Of course, buildings are not going to shrink as new ethernet technology is introduced, so there must be a way to
connect together ethernets. The solution is fiber optic (100 Base-FX) for lengths of up to 2000m of multimode
fiber (dual strand).

Fast ethernet also allows full duplex operation, but only in non-shared media environments such as a switch. Full
duplex is supported in 100 Base-TX and 100 Base-Fx. Full duplex enables distance requirements to be based
only on signal strength, not timing considerations since there can be no conflict on a full duplex link.
Other networking
Ethernet is the dominant local area networking technology, and is likely to remain so. In addition to fast ethernet,
there is Gigabit ethernet (1000Mbit/second). As performance increases, there will be an increasing emphasis on
point-to-point designs.

Other networking technologies, such as ATM and FDDI are fiber optic and switch based.
Network Programming
Sockets
Sockets are a protocol independent method of creating a connection between processes. Sockets can be either

connection based or connectionless: Is a connection established before communication or does each

packet describe the destination.
packet based or streams based: Are there message boundaries is it one stream.
reliable or unreliable. Can messages be lost, duplicated, reordered, or corrupted?

Socket are characterized by their domain, type and transport protocol. Common domains are:

AF_UNIX: address format is UNIX pathname

AF_INET: address format is host and port number

Common types are:

virtual circuit: received in order transmitted and reliably

datagram: arbitrary order, unreliable

Each socket has one or more protocols. Ex:

TCP/IP (virtual circuits)

UDP (datagram)

Connection--based sockets communicate client-server: the server waits for a connection from the client
Connectionless sockets are peer-to-peer: each process is symmetric.

socket: creates a socket of a given domain, type, protocol (buy a phone)

bind: assigns a name to the socket (get a telephone number)
listen: specifies the number of pending client messages that can be queued for a server socket. (call
waiting allowance)
accept: server accepts a connection request from a client (answer phone)
connect: client requests a connection request to a server (call)
send, sendto: write to connection
recv, recvfrom: read from connection
shutdown: end the call

Connection based communication

Server performs the following actions

socket: create the socket

bind: give the address of the socket on the server
listen: specifies the maximum number of connection requests that can be pending for this process
accept: establish the connection with a specific client
send,recv: stream-based equivalents of read and write (repeated)
shutdown: end reading or writing
close: release kernel data stuctures

Client performs the following actions

 socket: create the socket
connect: connect to a server
send,recv: (repeated)
shutdown
close

Connectionless communication
Communication is symmetric (peer-to-peer)

socket
bind
sendto, recvfrom (repeated)
shutdown
close

Sockets API

socket

#include <sys/types.h>
#include <sys/socket.h>

int socket(int domain, int type, int protocol)

Returns a file descriptor (called a socket ID) if successful, -1 otherwise.

The type arguments are

SOCK_STREAM: Established a virtual circuit for stream

SOCK_DGRAM: Establishes a datagram for communication
SOCK_SEQPACKET: Establishes a reliable, connection based, two way communication with maximum
message size. (This is not available on most machines.)

Protocol is usually zero, so the.

Note that the socket returns a socket descriptor which is the same as a file descriptor (-1 if failure).

bind

#include <sys/types.h>
#include <sys/socket.h>

int bind(int sid, struct sockaddr *addrPtr, int len)

Where

sid: is the socket id

addrPtr: is a pointer to the address family dependent address structure
len: is the size of *addrPtr

For the internet family:

struct sockaddr_in {
short sin_family; // = AF_INET
u_short sin_port; // is a port number
struct in_addr sin_addr; // an IP address
}

For unix sockets (only works between processes on the same machine)
struct sockaddr {
short sin_family; // = AF_UNIX
char sin_port[]; // is a port number
}

listen

#include <sys/types.h>
#include <sys/socket.h>

int listen(int sid, int size)

Where size it the number of pending connection requests allowed (typically limited by Unix kernels to 5).

accept

#include <sys/types.h>
#include <sys/socket.h>

int accept(int sid, struct sockaddr *addrPtr, int *lenPtr)

Returns the address of client connecting to socket

if lenPtr or addrPtr equal zero, no address structure is returned

lenPtr is the maximum size of address structure that can be called, returns the actual value.

send

#include <sys/types.h>
#include <sys/socket.h>

int send(int sid, const char *bufferPtr, int len, int flags)

flag is either

0: default
MSG_OOB: Out-of-band high priority communication

recv

#include <sys/types.h>
#include <sys/socket.h>

int recv(int sid, char *bufferPtr, int len, int flags)

flags can be either

0: default
MSG_OOB: out-of-bound message
MSG_PEEK: look at message without removing

shutdown

#include <sys/types.h>
#include <sys/socket.h>

int shutdown(int sid, int how)

Disables sending (how=1 or how=2) or receiving (how=0 or how=2).

Client calls

connect

#include <sys/types.h>
#include <sys/socket.h>

int connect(int sid, struct sockaddr *addrPtr, int len)

Connectionless protocols

sendto

#include <sys/types.h>
#include <sys/socket.h>

int sendto(int sid, const char *bufferPtr, int len, int flag,
struct sockaddr *addrPtr, int len)

recvfrom

#include <sys/types.h>
#include <sys/socket.h>

int recvfrom(int sid, const char *bufferPtr, int len, int flag,
struct sockaddr *addrPtr, int *lenPtr)

Auxiliary functions

Gethostbyname

#include <netdb.h>

struct hostent *gethostbyname(const char *hostname)

Translates a DNS name into a hostent.

The hostent stucture is as follows:
struct hostent {
char *h_name; // official (canonical) name of the host
char **h_aliases; // null terminated array of alternative hostnames
int h_addrtype; // host address type AF_INET or AF_INET6
int h_length; // 4 or 16 bytes
char **h_addr_list;// IPv4 or IPv6 list of addresses
}

Error is return through h_error which can be:

HOST_NOT_FOUND
TRY_AGAIN
NO_RECOVERY
NO_DATA

Gethostname

#include <unistd.h>

int gethostname(char *hostname, size_t nameLength)

Returns -1 on failure, 0 on success.

MAXHOSTNAMELEN is defined in <sys/param.h>.

Network byte ordering

Network ordering in big endian. (Sparc is big endian, Intel is little endian).

htons

Host to network byte order for shorts (16 bit)

uint_16t htons(uint_16t v);

htonl

Host to network byte order for long (32 bit)

uint_32t htonl(uint_32t v);

ntohs

Network to host byte order for long (16 bit)

uint_16t ntohs(uint_16t v);

ntohl

Network to host byte order for long (32 bit)

uint_32t ntohl(uint_32t v);

IP address strings to 32 bit number

In what follows, 'p' stands for presentation.

inet_pton

#include <arpa/inet.h>

int inet_pton(int family, const char *strPtr, void *addrPtr);

returns 1 if OK, 0 if presentation error, -1 error

Where family is either AF_INET or AF_INET6.

The strPtr is the ip address as a dotted string.

Finally, addrPtr points to either the 32 bit result (AF_INET) or 128 bit result (AF_INET6).

inet_ntop

#include <arpa/inet.h>

int inet_ntop(int family, const char *addrPtr, char *strPtr, size_t len);

returns 1 if OK, 0 if presentation error, -1 error

Where family is either AF_INET or AF_INET6.

The strPtr is the return ip address as a dotted string.

Finally, addrPtr points to either the 32 bit (AF_INET) or 128 bit (AF_INET6).

Length is the size of destination.

Example

TCP/IP Server

Without error checking.

int listenFd, connectFd;
struct sockaddr_in serverAddr;

listenFd = socket(AF_INET, SOCK_STREAM, 0); // get a tcp/ip socket

bzero(&serverAddr, sizeof(serverAddr));
serverAddr.sin_family = AF_INET;
serverAddr.sin_addr.s_addr = htonl(INADDR_ANY); // any iternet interface
// on this server.
serverAddr.sin_port = htons(13);

bind(listenFd, (struct sockaddr_in *) &serverAddr, sizeof(serverAddr));

listen(listenFd, 5);

for ( ; ; ) {
connectFd = accept(listenFd, (struct sockaddr_in *) NULL, NULL);
// .. read and write operations on connectFd ..
shutdown(connectFd, 2);
close(connectFd);
}

Note that the above is an iterative server, which means that it serves one connection at a time.

To build a concurrent server, a fork is performed after the accept. The child process closes listenFd, and
communicates using connectFd. The parent process closses connectFd, and then loops back to the accept to wait
for another connection request.

TCP/IP Client code

int sockFd;
struct sockaddr_in serverAddr;

sockFd = socket(AF_INET, SOCK_STREAM, 0); // get a tcp/ip socket

bzero(&serverAddr, sizeof(serverAddr));
serverAddr.sin_family = AF_INET;
inet_pton(AF_INET, serverName, serverAddr.sin_addr); // host IP #
serverAddr.sin_port = htons(13);

connect(sockFd, (struct sockaddr_in *) serverAddr, sizeof(serverAddr));

// .. read and write operations on sockFd ..
shutdown(sockFd, 2);
close(sockFd);
TCP/IP
TCP/IP provides a streams, connection-oriented abstraction. It must therefore be reliable in the presence of
"network problems" which do not completely disrupt communications. Network problems which cannot be
masked include a downed host or partitioned network.

In addition, TCP/IP performs congestion control. Here, the problem is two fold:

If the network fills up, a router can just throw away packets.
If a router fills up, it cannot receive any packets.

Reliability
In order to be reliable, we need to model the types of failures that can occur. In IP these are:

Lost packets
duplicated messages
arbitrarily delayed packets
packets received out of order
corrupted packets

Corrupted packets

Lets consider the corrupted packets issue first. Assume that the corrupted packets occur as the result of randomly
occuring failures. Than we can extend each packet with a checksum, such that random errors can be detecting.
(The checksum, in terms depend upon modeling the way that corruption can occur, but that is coding theory).

If on the other hand, packets could be systematically corrupted by an advesary, then cryptographic techniques
would be required to recognize whether packets come from a known source.

Once a corrupted packet is found, it can be thrown away, that is, treated as a lost packet.

Ensuring packets arrive, and are in sequence

The primary technique is to include in each packet a serial number, so that the ith packet from C1 to C2 has
serial number i. (Packets sent in the other direction, C2 to C1 are seperately numbered.)

The recipient initiates a counter at 0. If a message arrives which is equal to the counter, the recipient sends an
ACK packet with the counter, and then increments the counter. If a message arrives whose serial number is less
than the counter it is thrown away (it is a duplicate). If it is greater than the counter NACKs (negative
acknowledgements) are sent for the packets greater than the counter through the serial number of the arriving
packet, and the arriving packet is thrown away.

The ACKs/NACKs can be lost as well. Hence the sender sets a timer, by which it expects an ACK. If the ACK
does not arrive by the timeout, the packet is resent. This also protects against the last message in a session being
lost, which would not be NAKed.

Optimizations

Acknowledge groups of messages instead of individual messages. Works best if the probabilty of message lost is
low. If its high, that individual messages should be acknowledged.
Send many messages before waiting for an acknowledgement enables toleration of long latencies (eg. satelight
links), but is slower to detect errors.
Remote Procedure Call
On this page, we consider the general issue of remote procedure call. An RPC is a procedure call across
processes, whether they are located on the same or different hosts. (Sometimes the term local RPC is used to
indicate an RPC within a hosts).

RPCs have several advantages over sockets-level programming:

Procedure calls are a convenient abstraction for the request of remote services.
RPCs are type safe, and transparently manage host differences in datatypes and layouts
RPC seperates the interface from the implementation, yielding more readable designs.

Type safety
Computer architecture-Operating Systems differ from one another in several aspects of datatype representation.
These include:

alignment
endianess
floating point format

The first two issues are because there are multibyte primitive data types (such as 4-byte integers), yet memory is
byte addressible. The last issue is because there still exists some legacy floating point formats, although all
microprocessor originated designs are based on IEEE floating point format.

Alignment

High performance computers require multibyte primitive to be aligned. That is, a k byte primitive must have a
starting address which is divisible by k in an aligned architecture.

For example, the structure:

struct {
char a;
int i;
}

in an aligned architecture requires 8 bytes (a is followed by three bytes of padding), since newly allocated
storage is always at the highest alignment of the architecture: in an unaligned archtecture it would require 5
bytes.

A more subtle example is:

struct {
char a;
int i;
char b;
}

At first glance, this might seem to require only 9 bytes in an aligned archecture (data elements cannot be
reordered in C). However, this requires 12 bytes (three bytes of padding at the end) since the size of a array
element is the same as the size of an object. (Note that an array of characters needs no internal padding since the
requirement is only that the size of an object must be a multiple of its largest primitive object).
Endianess

Architectures can either be:

big endian: most significant byte at lowest address

little endian: least signifcant byte at lowest address.

Network standard traffic is big endian. (htonl and htons do this endian conversion, if necessary).

Floating point

Before IEEE floating point standard in the 1980's each computer manufacturer designed its own floating point
system. Of those, perhaps the two most important are Cray and IBM.

Between IEEE floating point, issues of byte order are still important but the size and meaning of mantissa and
exponent have been standardized.

ONC RPC
RPC Interface Definition Language (IDL)

definition-list := definition ;|
definition ; definition-list
definition := const-definition |
enum-definition |
struct-definition |
union-definition |
typedef-definition |
program-definition
const-definition := const ident = integer
enum-definition := enum ident { enum-value-list }
enum-value-list := enum-value |
enum-value , enum-value-list
enum-value := ident = value |
ident
struct-definition := struct ident { declaration-list }
declaration-list := declaration ; |
declaration ; declaration-list
union-definition := union ident switch ( declaration ) { case-list }
case-list := case value : declaration ; case-list |
case value : declaration ; |
default : declaration ;
typedef-definition := typedef declaration
program-definition := program ident { version-list } = program-number
version-list := version-decl ;|
version-decl ; version-list
version-decl := version ident { procedure-list } = version-number
procedure-list := procedure ; |
procedure ; procedure-list
procedure := type ident ( type ) = procedure-number
declaration := simple-declaration |
fixed-array-declaration |
variable-array-declaration |
pointer-declaration
simple-declaration := type ident
fixed-array-declaration := type ident [ integer ]
variable-array-declaration := type ident < integer > |
type ident < >
pointer-declaration := type * ident

Notes:
union-definition is a descriminated union, meaning that there is a tag that gives the type
program-definition describes just the interfaces, but none of the code.
union-declaration must specify a value associated with each type.
program-number is assigned as follows:
0x00000000 - 0x1fffffff defined by SUN
0x20000000 - 0x3fffffff defined by user
0x40000000 - 0x5fffffff transient
0x60000000 - 0xffffffff reserved
Use a program number in the defined by user range (adding in last 4 digits of your social security
number).
ONC-RPC allows only a single parameter and a single result (these can each be void).
The procedures defined by the IDL are obtained by converting the procedure to lower case and appending
"_" and the version number. This allows an RPC definition to support multiple version of procedure calls.
procedure-number should start from 1 (0 is reserved for the ping (or null) procedure which can be used to
test if the server is alive).
variable-array-declaration specified either a maximum size (if there is an integer between angle brackets)
or does not specify a maximum size.
pointer-declaration pointers across processes are not very useful. Pointer types are used to copy over
sparse structures such as linked lists from server to client.

rpcgen

The RPC IDL (also called RPCL) needs to be compiled into C so that it can be used in a program. Assume the
IDL is stored inprog.x. Then:
rpcgen prog.x

Running rpcgen creates three files:

prog.h: which contains common information for the server and client.
prog_svc.c: C code to be linked with the server.
prog_cli.c: C code to be linked with the client.

Compiling on solaris
Then you can compile as follows:
gcc client.c prog_cli.c -o client -lnsl
gcc server.c prog_svc.c -o server -lnsl

client.c and server.c should include:

#include < rpc/rpc.h >
#include < netconfig.h >
#include "prog.h"

Calling remote procedures

Remote procedure proc, version v is called with the name proc_v. The parameters and the return value for the
procedure each have an exra level of indirection. For example:

procedure p
version 2
declared as int p(char)

The procedure is a bit different on the client and server side:

On the client side it would be written in C as: int *p_2(char *, CLIENT *)

where the CLIENT * argument specifies the target of the RPC.

On the server side it would be written in C as: int *p_2(char *)

In addtion, the value returned (if declared within the procedure) must be declared static.

RPC data types in C program

Most data types are directly mappable into C. The exceptions include:

Variable size arrays

Unions
Pointers

Pointers cannot be easily used across process boundaries, so the primary reason for using pointers is to copy
over sparse structures (such as linked lists or trees), between processes. ONC-RPC provides for pointer-chasing
to do this automatically, but this is beyond the scope of the notes. Both of the remaining types, Variable size
arrays and Uninos, are described by structures.

Variable size arrays

Consider the variable size array vararray whose components are of type int.
typedef int vararray<100>;

generates the structure:

typedef struct {
u_int vararray_len;
int *vararray_val;
} vararray;
Where the type vararray is a structure in C with two components, a length field vararray_len and a pointer to the
arrayvararray_val which is of course type int.

Unions

Consider the RPC specification:

union retval switch (int desc) {
case 0: headline hl;
default: void;
};

This gets compiled into the following C structure.

struct retval {
int desc;
union {
headline hl;
} retval_u;
};

To use this structure, the C programmer must set both the descriminator (desc) to 0 (or something outside the
range of defined values), and the union component to the appropriate value.

Using RPC

You need to write client.c and server.c code.

client

The client will need initialize the RPC

CLIENT *cl;

if (( cl = clnt_create(server, PROG_NUMBER, PROG_VERS, "tcp")) == NULL) {

/* error, could not open server */
}

and to close down the connection:

clnt_destroy(cl);

server

The server does not have a main (this is supplied by the stub). It need only implement the remote procedures.
Recommended Texts
Unix Network Programming, W. Richard Stevens, Prentice Hall. (The bible on network programming)

The Design of the Unix Operating System, Maurice Bach, Prentice Hall. (Dated description of Unix
internals, but very readable)

POSIX.4:Programming for the Real World, Bill O. Gallmeister, O'Reilly and Associates. (The book on
real-time POSIX programming covering IPC, async. I/O, and more).

Computer Networks (3rd Edition), Andrew S. Tannenbaum, Prentice Hall. (Detailed coverage of low level
network stuff)

Computer Networks: A Systems Approach Larry L. Peterson and Bruce S. Davies, Morgan Kaufman.
(More advanced coverage then Tannenbaum)

The Magic Garden Explained, Benny Goodheart and James Cox, Prentice Hall. (Describes basis for
Solaris [SrV5R4] internals).

STL Tutorial and Reference Guide David R. Musser and Atul Saini, Addison-Wesley. #

Power Programming with RPC # John Bloomer, # O'Reilly and Associates. # (ONC RPC in depth)
Assignments
Assignment 1
Write up
Sample solution
Assignment 2
Write up
Assignment 3
Write up
Sample socket progams
Assignment 4
Write up
 Assignment 1

For this assignment, we will use signals to solve the problem of cascading termination. This problem is when a
parent process terminates, the child processes are allowed to continue to execute. This can result in orphan and
zombie processes being left on the system.

When a process terminates, it is to first force the termination of all of its child processes (to prevent any
orphaned or zombie processes left on the system) and then terminate itself. It should force the termination of its
children by sending the SIGTERM signal to all of its children. The safest method to do this is to use the atexit()
function. The atexit() function takes as its parameter a pointer to a function. This function will be called as the
program terminates. This function must of type void and have no parameters.

We will want to run our program in background mode executing an infinite pause() loop. This will allow us to
interact with each process by using the command line kill(1) operation to send various signals to each process.
We will be sending four different signal: SIGHUP, SIGUSR1, SIGUSR2 and SIGTERM.

When a process receives the SIGHUP signal, it is to create a new child process. As each process is created, the
program must print a message stating the process ID's of the child and the parent.

When a process receives the SIGUSR1 signal, it is to print out the process ID's of all child processes that are
currently running.

When a process receives the SIGUSR2 signal, it is to (again) print out the process ID's of all child processes that
are currently running and send the SIGUSR2 signal to all of these processes. This will cause the process ID's of
all descendants of the original process to be printed. Since we are printing the processes descendent tree, we
should attempt to print these values in some "tree-like" manner.

When a process receives the SIGTERM signal, it is to first force the termination of all of its children and then
terminate itself. The use of the atexit() function may be helpful with this in case the process terminates normally.

As each child process is created, its process ID must be remembered. This should be done by writing a special
creation function that performs the fork() command and maintains a list of child process ID's. This function
should add the necessary information to the list for the parent process, while creating an empty list to hold any
future children that may be created by the current child process. Remember the child will get a copy of the
parent's list, so it may need to remove the parent's information from its list.

When the child process terminates, its process ID must be removed from its parent's list. The SIGCHLD signal
should be caught so it can perform the necessary wait() operation and then remove the proper information from
the list.

To aid with the creation of the processes, we will use an optional command line argument. If the user enters the
value of "1" as an argument to the command to execute the program, the original process is to create four (4)
child processes and three (3) "grandchild" processes. Two of the "grandchild" processes will be the child
processes of the original process's first child process. The third "grandchild" process will be the child process of
the original process's second child process. The easiest way to create these additional processes will be to have
the original process send the SIGHUP signal to itself four times, then send the SIGHUP signal to its first child
twice and finally send the SIGHUP signal to its second child once. If no command line argument is given (or a
command line argument other than "1"), all child processes will be created explicitly by the user.

Remember to use the UNIX ps command to make sure you do not leave any extra processes on the system.
The assignment is expected to be the result of individual work. You will submit the project electronically using
the UNIX "turnin" command. Refer to the man page on the system for information about the command.

All of your programs must be written in a good programming style. This is to include in-line comments, a file
header, function headers, blank lines, indentation, meaningful variable names, readable output, etc. The first two
line of your file must comments stating how you compiled your program on the EECS department's UNIX
machines and how you ran your program.
 Assignment 2
Due Date: Wednesday, October 20, 1999, at 11:59 pm
Entended to: Monday, October 25, 1999, at 11:59 pm

For this assignment, you are to create a two player-two process tic-tac-toe game using IPC message
queues for communication between the two players. The input and output of the program is to be text
based.

Since there are nine positions on the tic-tac-toe board, a move by a player is indicated by entering the
value from 1 through 9 as follows:

1 2 3

4 5 6

7 8 9

The object of the game is to get three places in a row either horizontally, vertically or diagonally.
Traditionally, the first player uses an X to mark their moves and the second player uses an O to mark
their moves. For the first round, the player that creates the IPC message queue goes first. After each
game, both players are asked if they want to play again. If both players respond "yes", another game is
played. After the first game, which ever player lost the previous game goes first. If the previous game
ended in a tie (sometimes called "cats"), the player that went second in the previous game goes first in
the current game.

For a players turn, they enter in the values from 1-9 to indicate a move. If the position is already taken,
give an error message and allow the player to make another choice. If the player's move gets three in a
row, the program should announce the winner immediately. The ninth move of a game should be
made automatically (since there is only one position where the move could go). During the player's
turn, the player could enter in a "h" or "?" to get some help on the game. This help should list basics of
the game and the table that shows the correspondence between the playing board positions and the
values 1 through 9. During the player's turn, the player may concede the game (admit they have lost)
by entering a "c". During the player's turn, the player may quit the game and the program by entering
a "q". If this happens, your program is to prompt to see if the player really wants to quit.

While a player is waiting for the other player to take their turn, the program should print a message
such as:

Waiting for the other player's turn......

where a new period should get printed at some regular interval (i.e. every 5 seconds). You will most
likely need to use signals for allow for this.

Your program is to be written in good programming style and should attempt to take advantage of
C++ classes and the C++ Standard Template Library. You will find a number of good links from
the EECS 471 home page.
 Assignment 3
Due Date: Wednesday, November 17, 1999, at 11:59 pm

For this assignment, you are to create a two player-two process tic-tac-toe game using sockets for
communication between the two players.
You are to write two programs, one for the server (with the executable file named ttts) and one for the
client (with the executable file named tttc). The client is to take an optional command line argument of
a machine name that specifies the machine the server is running on. If no machine name is give
assume the server is running on the same machine as the client. The communication between the two
processes is to use the client's socket.

The input and output of the program is to be text based. Since there are nine positions on the tic-tac-
toe board, a move by a player is indicated by entering the value from 1 through 9 as follows:

1 2 3

4 5 6

7 8 9

The object of the game is to get three places in a row either horizontally, vertically or diagonally.
Traditionally, the first player uses an X to mark their moves and the second player uses an O to mark
their moves. For the first round, the server goes first. After each game, both players are asked if they
want to play again. If both players respond "yes", another game is played. After the first game, which
ever player lost the previous game goes first. If the previous game ended in a tie (sometimes called
"cats"), the player that went second in the previous game goes first in the current game.

For a players turn, they enter in the values from 1-9 to indicate a move. If the position is already taken,
give an error message and allow the player to make another choice. If the player's move gets three in a
row, the program should announce the winner immediately. The ninth move of a game should be
made automatically (since there is only one position where the move could go). During the player's
turn, the player could enter in a "h" or "?" to get some help on the game. This help should list basics of
the game and the table that shows the correspondence between the playing board positions and the
values 1 through 9. During the player's turn, the player may concede the game (admit they have lost)
by entering a "c". During the player's turn, the player may quit the game and the program by entering
a "q". If this happens, your program is to prompt to see if the player really wants to quit.

While a player is waiting for the other player to take their turn, the program should print a message
such as:

Waiting for the other player's turn......

Where a new period gets printed at some regular interval (i.e. every 5 seconds). You will most likely
need to use signals to allow for this.
Your program is to be written in good programming style and should attempt to take advantage of
C++ classes and the C++ Standard Template Library.
You will find a number of good links from the EECS 471 home page
([Link]
MP 4 - Network Database Server
Due: 12/3/1999

For this assignment, you are to create a client/server socket program that will allow multiple clients to
simultaneously connect to a simple database. When a client wishes to use the database, it will first make a
connection request to the server. The server will then fork a child to communication with the client across the
client's socket. The server child will perform the actual reading and writing to the file database. The file
database must make use of read and write locks on individual records to allow/disallow simultaneous accesses
to the database.

The server process must have the name of dbs, and the client process must have the name of dbc. The client
process must take on optional command line argument. If no argument is given, it will assume the current
machine contains the server socket. If an argument is given, it will assume that the argument is the name of
the machine that contains the server socket.

The database will have ten records, numbered from 0 to 9. Each record will have two fields: a name field (of
size 30 characters) and a phone number field (of size 20 characters). When accesses either field in the record,
the entire record must be locked.

To use the database, the client will send a command across the client socket. The server child will retrieve this
command and attempt to perform the desired action. If the action is successful, the server child will send
either the resulting information across the client socket or a confirmation that the command was successfully
performed to the client. If the action is unsuccessful, the server child will send a message stating the action
was unable to be performed. The reasons for the unsuccessful action is because of conflicting locks set on the
desired record(s). Your program is not to block the process, but simply to report the unsuccessful action.

The interactive commands that the client process must access are:

s <pos> <name>

Set the name field to <name> at record <pos>. The <name> will start with the first non-white
space character after <pos> and continue until the end of the line. If there are no non-white
space characters after <pos>, the name is to be set to the null string. If there are more than 30
characters after the first non-white space character, truncate the name to the first 30 characters.
This command must a write lock at record <pos> prior to the writing of the field. It must
unlock the record after the writing of the field. If the write lock cannot be set, report an
unsuccessful access to the record.

f <pos> <phone number>

Set the phone number field to <phone number> at record <pos>. The <phone number> will
start with the first non-white space character after <pos> and continue until the end of the line.
If there are no non-white space characters after <pos>, the phone number is to be set to the null
string. If there are more than 20 characters after the first non-white space character, truncate
the phone number to the first 20 characters. This command must a write lock at record <pos>
prior to the writing of the field. It must unlock the record after the writing of the field. If the
write lock cannot be set, report an unsuccessful access to the record.
n <pos>

Retrieve the name field from record <pos>. This command must set a read lock at record
<pos> prior to the access and unlock the record after the access. If the read lock cannot be set,
report an unsuccessful access to the record.

p <pos>

Retrieve the phone number field from record <pos>. This command must set a read lock at
record <pos> prior to the access and unlock the record after the access. If the read lock cannot
be set, report an unsuccessful access to the record.

b <pos>

Retrieve both the name and phone number fields from record <pos>. This command must set a
read lock at record <pos> prior to the access and unlock the record after the access. If the read
lock cannot be set, report an unsuccessful access to the record.

Retrieve both the name and phone number fields from all records. This command must set a
read lock at each record prior to the access of that record and unlock the record after the
access. If the read lock cannot be set for a particular record, report an unsuccessful access to
that record and continue with the access to the other rocords.

r <pos>

Set a read lock at record <pos>. If the read lock cannot be set, report an unsuccessful access to
the record.

w <pos>

Set a write lock at record <pos>. If the write lock cannot be set, report an unsuccessful access
to the record.

u <pos>

Unlock the record <pos>.

List all of the commands for this program with a short description on how to use each one.

Have the client process exit. This will cause the server child process to exit as well. The server
process must properly clean up (i.e. wait() ) after the termination of its child (i.e. catch the
SIGCHILD signal).
Once started, the server will remain running until it is killed by the SIGKILL signal. For 10 points extra credit,
allow for graceful shutdown of the server. When the server receives a SIGTERM signal, before it shuts down
it must:

1. Close the server socket.

2. Send a signal to all server children, stating that they must terminate. As each server child terminates it
must send some message to its client that the server is no longer available and will not be accepting
any more database requests.

3. Wait for all server children to terminate before the server terminates.

For additional extra credit the assignment may be turned in early. If the assignment is turned in by Wednesday
11/24/99, you will get 20 points extra credit. If the assignment is turned in by Saturday 11/27/99, you will get
15 points extra credit (note, if the system goes down over the Thanksgiving Break there will be no extensions
given to allow for this situation). If the assignment is turned in by Monday 11/29/99, you will get 10 points
extra credit. If the assignment is turned in by Wednesday 12/1/99, you will get 5 points extra credit.

Your program is to be written in good programming style and should attempt to take advantage of C++ classes
and the C++ Standard Template Library. All programs must be turned in electronically using the UNIX turnin
command with the project name of mp4.