#ifndef BLOCKDEVICE_H
#define BLOCKDEVICE_H

/* BlockDevice
 * Simulates a block device (e.g. solid-state/magnetic drive)
 * on a file.  The file will not necessarily be the same
 * size as the device as we only allocate physical space up to 
 * and including the last used block.
 */
class BlockDevice {

 public:
   /*
   * Success and error codes.
   * If these are changed, be sure to change human/readable
   * message string array in class definition.
   */
  typedef enum {
    success,      // operation completed successfully
    nosuchblock,  // bad block index
    badblock,     // cannot access block
    badreadwrite, // unable to complete read or write
    nosynch,      // unable to synchronize buffers with blocks
  } result;

  // messages corresponding to result enumerations
  // values declared in class definition, e.g. messages[nosuchblock]
  // contains a human readable explanation that the requested block
  // does not exist.
  static const char *messages[];  

 /*
   * BlockDevice(const char *filename, uint32_t blocks, uint32_t
   * block_size)
   * Create or open a simulated block I/O device backed by the
   * specified filename.  If blocks > 0, the device is created,
   * otherwise we try to open the device.  (We don't use two different
   * constructors to ensure C compatibility.)
   */
  BlockDevice(const char *filename, uint32_t blocks = 0,
       uint32_t block_size = 4096);

  ...

#include <sys/stat.h>
#include <math.h>
#include <stdexcept>

#include "BlockDevice.h"

using namespace std;

/* BlockDevice
 * Simulates a block device (e.g. solid-state/magnetic drive)
 * on a file.  The file will not necessarily be the same
 * size as the device as we only allocate physical space up to 
 * and including the last used block.
 *
 * Arguments:
 * filename - File that will be used to simulate the device.
 * blocks - Maximum capacity of device in data blocks
 * block_size - Number of bytes in each block
 * If blocks is omitted or 0, the constructor opens an existing device file.
 */

BlockDevice::BlockDevice(const char *filename, uint32_t blocks,
 uint32_t block_size)
{

  // If block_size is specified, ensure that it is divisible by 32 bits
  // Real devices are usually a power of 2
  if (block_size && (block_size % sizeof(int32_t) != 0))
    throw runtime_error("Device block size must be a multiple of 4 bytes");
  
  size_t count = 0;  // header fields read/written

  // We really only need a a few bytes (sizeof(device_meta) for the device metadata
  // However, it will make our life much simpler if we extend that to the standard 
  // block size as everything will be aligned.
  // Find the number of blocks we need to hold the device meta information
  uint32_t complete_blocks = sizeof(device_meta) / block_size;
  uint32_t partial_blocks = sizeof(device_meta) % block_size > 0 ? 1 : 0;
  this->offset = (complete_blocks + partial_blocks) * block_size;
  
  size_t expected_hdr_count = 2;  // # fields in hdr

  if (blocks == 0) {
    // User did not specify device characteristics, assume existing
    // block device and check if simulation file exists.
    struct stat status;
    bool exists = stat(filename, &status) != -1;
    if (! exists)
      throw runtime_error("Device file does not exist");

    // open and read metadata
    this->file_h = fopen(filename, "r+");
    if (this->file_h == NULL)
      throw runtime_error("Unable to open file");

    // Read in metadata and verify that we read the expected amount.
    count += fread(&this->block_size, sizeof(uint32_t), 1, this->file_h);
    count += fread(&this->blocks, sizeof(uint32_t), 1, this->file_h);
    if (count != expected_hdr_count)
      throw runtime_error("Unable to read device metadata");

  } else {
    // New device
    this->file_h = fopen(filename, "w+b");
    if (this->file_h == NULL)
      throw runtime_error("Unable to create new device");

    this->blocks = blocks;
    this->block_size = block_size;
    // Write header
    count += fwrite(&this->block_size, sizeof(uint32_t), 1, this->file_h);
    count += fwrite(&this->blocks, sizeof(uint32_t), 1, this->file_h);
    if (count != expected_hdr_count)
      throw runtime_error("Unable to initialize device metadata");
  }
}

I highly reccomend that you comment your code as you write. I find that it reduces code faults as it makes you thin about what you want to do. It also makes it much easier for people to follow your code. In this class, commenting is mandatory. If you come for help, I will expect to see commented code.

Program submission

All submissions must include an affidavit indicating that the submitted work is your own. Place the affidavit statement in the comments of the main entry point to your program. Use either the single or pair affidavit as appropropriate.

How can I securely connect to other computers or transfer files using secure shell (ssh), secure copy (scp) or secure ftp (sftp)?

You should always try to avoid using telnet or ftp for non anonymous connections. When you use telnet or ftp, your password is transmitted in clear text (unencrypted form) and is thus more vulnerable to being observed by unsavory characters :-). Secure shell/copy/ftp are a set of protocols that encrypt your entire session so that both your passwords and other data are protected.

Secure shell (ssh) allows you to run terminal sessions to other machines. Getting started with secure shell provides a basic introduction to ssh, there are more complex tutorials that will tell you how to use secure copy/ftp (scp/sftp) permit you to transfer files to or from the client machine as well as set up public key authentication to log in without a password.

Command line versions of the secure shell suites come with UNIX/Linux and MacOS distributions. Manuals for the traditional command line interfaces can be found on the respective systems. You can easily add command line versions to Windows with CYGWIN, a free POSIX interface for Windows which has lots of nice things available such as an X Windows server.

Wikipedia maintains a compariosn of ssh clients PuTTY and WinSCP are popular clients for Windows. WinSCP is for file transfer only.

How can I use a graphical interface on edoras?

• X Windows over a slow connection is painful. If you have a slow connection, you are better off working on campus or going old school with a tty (teletype terminal) connection. Wearing a pocket protector is mandatory with tty connections :-). You can also try turning on compression with your the -C option to ssh.
• If graphical programs that you start from your shell on edoras will not display (typical error message: Cannot open display), you might not have 1) started your X server on your local machine, or 2) not enabled X window forwarding (-Y flag on standard ssh implementations) when you made the connection with ssh.

In summary:

1. Start an X11 server if one is not already running.
2. Connect via ssh:
   • if on campus, use: ssh -Y youraccount@edoras.sdsu.edu
   • if off campuse, use: ssh -Y -C youraccount@edoras.sdsu.edu
3. Start your programs, e.g. gedit, cdtdebug, etc. Remember you can put an & at the end of graphical programs to detach them from the shell and continue using your shell. See the UNIX primer to learn more aobut UNIX.

Windows 10 provides support for the Windows subsystem for Linux (WSL). You can download Ubuntu or other linux variants from the Miscrosoft store and have a bash shell. This works fairly well. It does not contain an X11 Windows server.

Alterntively, the cygwin project consists libraries to support POSIX functionality and most of the tools that one would typically see on a UNIX/Linux platform such as secure shell servers and clients, X windows servers, compilters, shells, etc. If you are a UNIX/Linux die hard forced to use Windows or need to compie a UNIX program for Windows, this project is a good place to start.

• cc - system provided C compiler
• CC - system provided C++ compiler
• gcc - GNU C compilter
• g++ - GNU C++ compiler

 edoras> gcc foo.c 

 edoras> a.out 

 edoras> gcc -o foo foo.c 

My program compiled correctly, but when I try to execute I receive a file not found error.

My C program had a compilation error telling me to compile in C99 mode.

What is the PATH and how do I set it?

For shells which are descended from the Bourne shell (sh), which include the Korn shell (ksh) and the Born Again Shell (bash), you can add to your path with the following:

PATH=$PATH:~mroch/bin

edoras% set path = ( $path ~mroch/bin )

What is separate compilation and how do I use it?

Suppose that we have written a program consisting of three files: huey.C, louie.C, and dewie.C. (These are the names of the cartoon character Donald Duck's nephews and have no particular significance.) If we wanted to compile them together, we could just type:

 edoras> g++ -o duckprogram huey.C louie.C dewie.C 

edoras> cc -c huey.C 
edoras> g++ -c louie.C 
edoras> g++ -c dewie.C 

 edoras> ln -o duckprogram huey.o louie.o dewie.o 

 edoras> g++ -o duckprogram huey.o louie.o dewie.o 

edoras> g++ -c louie.C 
edoras> ln -o duckprogram huey.o louie.o dewie.o 
edoras> # OR g++ -o duckprogram huey.o louie.o dewie.o 

This may seem like a lot of hassle, but fortunately it can be automated with a makefile. To tantalize you, once we have a makefile, all we'll have to do is type "make" and the make program will automatically determine what needs to be recompiled and link for us.

How can I process command line arguments?

#include <iostream.h>

// Small C++ program to show the command line arguments
// A C program would be similar except it would use:
//		printf()/stdio.h as opposed to cout/iostream.h
//		/* */ style comments only instead of /* */ and //
void main(int argc, char *argv[]) {

  /* argc contains the number of entries in argv: 0 to argc-1
   * argv[] contains pointers to the strings
   * Note that the program name is argv[0]
   */

  int	i;	// loop variable
  
  // Print the program name and arguments
  for (i=0; i < argc; i++) {
    cout << argv[i] << '\n';
  }
}

#include <unistd.h>
int main(int argc, char **argv) {
  bool verbose = false;  // chatty or quiet program
  int idx;  // general purpose index variable
  int count = 100;  // some counter set by -n, set default
  // other stuff (e.g. declarations)

  /*
   * This example uses the standard C library getopt (man -s3 getopt)
   * It relies on several external variables that are defined when
   * the getopt.h routine is included. On POSIX2 compliant machines
   * <getopt.h> is included in <unistd.h> and only the unix standard
   * header need be included.
   *
   * getopt takes:
   *    argc - Number of strings in argv
   *    argv - Strings for each token (contiguous characters in the
   *           command line. Example:
   *           a.out -n 56 -v boo bear
   *           argv[0] = "a.out", argv[1] = "-n", argv[2] = "56"
   *           argv[3] = "-v", argv[4] = "boo", argv[5] = "bear"
   *    optionstr - String indicating optional arguments to process
   *           Options with a : after them expect some type of value
   *           after them.  Example:  "n:o:v" n and o expect arguments,
   *           v does not
   */
  while ( (Option = getopt(argc, argv, "n:o:v")) != -1) {
    /* If the option has an argument, optarg is set to point to the 
     * argument associated with the option.  For example, if
     * -n is processed, optarg points to "56" in the example above.
     */
    switch (Option) {
    case 'n': /* Assume this takes a number */
      /* optarg will contain the string following -n
       * -n is expected to be an integer in this case, so convert the
       * string to an integer.
       */
      count = atoi(optarg);  
      break;

    case 'o': /* optarg points to whatever follows -o */
      // optarg contains the output, do something appropriate
      break;

    case 'v':  /* optarg is undefined */
      verbose = true;
      break;

    default:
      // print something about the usage and exit
      exit(BADFLAG); // BADFLAG is an error # defined in a header
    }

  }

  /*
   * Once the getop loop is done external variable optind contains
   * a number.  This is the first argument of argv to process
   * after all options have been processed.
   * argv[optind] is the next mandatory argument.
   */

  int idx = optind;

  /* If idx < argc, there are mandatory arguments to process */
  if (idx < argc) {
    /* Process positional arguments:
     *argv[idx] argv[idx+1], ..., argv[argc-1]
     */

    ...
  }


  /* continue processing */
}

What is an appropriate level of commenting?

/*
 * factorial - A recursive function to compute factorials of integer n.
 * if n < 0, the result is undefined.
 */
int factorial(int n)
{
  int result;
  
  if (n <= 1) {
    /* base case:  n! = 1 */
    result = 1;
  } else {
    /* recursive case:  n! = n * (n-1)! */
    result = n * factorial(n-1);
  }

  return result;
}

  ...

  // Check to see if a large enough block exists by stepping through
  // free memory segments
  
  Found = false;
  Segment = FreeList.First();
  // Loop until we find large enough block or Segment set to NULL
  while (! Found  && Segment) {
    if (Segment->Size() >= RequestedSize) { 
      Found = true;
    } else {
      Segment = Segment->Next();
    }
  }

  if (! Found) {
    // No free segments of the appropriate size available.
    // See if consecutive segments can be merged to satisfy
    // request.

    /* more code... */

What is make and makefiles?

For people not working in an integrated development environment and with multiple files, this is a must have tool. You can also look at the man page for make or the O'Reilly Nustshell book Managing Products With Make by Andrew Oram. There are numerous tutorials on line. One excellent make tutorial has been created by the Ben Yoshino at the College of Engineering, University of Hawaii.

One caveat, make is picky about spacing between items in a makefile. Leave a blank line between each target (targets are explained in the tutorial).

How can I understand UNIX system & library calls?

Note that if you are an emacs user, you can type M-x man<Return> fork<Return> (don't forget that in emacs-speak M-x is Escape followed by x) and get a nicely formatted manual page that you can treat like any other emacs buffer.

Each manual page is divided into labeled sections. The first is simply the name of the command and what it does. Next a synopsis is presented which gives very basic information on how to use the command. For instance, with fork you will see:

System Calls                                              fork(2)

NAME
     fork, fork1 - create a new process

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

     pid_t fork(void);

     pid_t fork1(void);

DESCRIPTION
     The fork() and fork1() functions create a new  process.  The
     new  process (child process) is an exact copy of the calling
     process (parent process). The  child  process  inherits  the
     following attributes from the parent process:

...

This indicates that you will need to include the header files sys/types.h and unistd.h. In addition, the fork(void) means that there are no arguments required for this call. pid_t indicated that it returns a variable of type "pid_t". For now, just think of pid_t as an integer. If you wanted to see what pid_t was, you could trace through the include files which for UNIX usually reside in /usr/include/, but reading through the description would tell you that this is an integer indicating the return status of the fork call. Read the description section to find out what the return codes mean. There are other sections of the manual page which discuss standards conformance, caveats (things you can get into trouble with), and other related manual pages.

The answer to the next question discusses in greater detail how to interpret what functions require and return.

How can I interpret function signatures (prototypes)?

	void *memcpy(void *s1, const void *s2, size_t n);

#define	MAXSIZE	1024

	double	SourceAry[MAXSIZE];
	double	DestinationAry[MAXSIZE];

	void	*ResultAddr;

	/*
	 * code to populate SourceAry omitted...
	 */

	 /* copy source to destination */
	 /* The previous line is a good enough comment, but
	  * if you are new to C/C++, there are several things
	  * going on here:
	  *	1) When you have an array, typing the name of
	  *		the array without an index returns a
	  *		pointer to the beginning of the array.
	  *	2) We could have done the same thing by taking
	  *		the address of the first element:
	  *			&SourceAry[0]
	  *	3) The sizeof operator returns the number of bytes
	  *		in a type or structure.
	  */
	 ResultAddr =
		memcpy(DestinationAry, SourceAry, MAXSIZE * sizeof(double));

How can I use a nonstandard library?

This FAQ only covers static libraries. To use a static library, you need to know the name of the library. When the object files are linked together (see separate compilation), the library is treated as another object file and only the routines that are referenced by the user code are included. (The situation is actually a little more complicated as routines within libraries may depend on one another.)

Some libraries that are almost always used (such as the standard I/O library) are automatically linked for you. When the library you need is not automatically linked, you need to tell the linker to include it. In UNIX, you can tell the linker to link a static library by postpending the -l flag on the compilation line, e.g.:

edoras> gcc -o demo_program demofile1.o ... demofileN.o -lm

How do we know that the math library is needed? When we look at the documentation for a math library function it will tell us so. In UNIX, the sin function's synopsis (see man sin) shows -lm. Other operating systems may have different syntax, but the idea is similar.

How can I create my own library?

In UNIX, the archiver tool (ar) is used to create a library. The object files (.o's) are given as arguments to ar. The following example will create a library called libid.a. Traditionally, static UNIX libraries end in .a, but there is nothing special about the name. The following command takes the functions in three different object files and creates a library archive in libMyLib.a.

edoras> ar -rcs libMyLib.a MyFuncA.o MyFuncB.o MyFuncC.o

Special note for C++ users

Which editors can I use to write my program?

• emacs (Control+h t in emacs for a tutorial or menu help tutorial)
• vi/vim (use vimtutor command for an interactive tutorial)
• nano

If you have an X Windows connection (see X11), you can use any of the above (emacs has a GUI mode) as well as gedit and nedit. See edoras's file editor list for details.

On a personal note, having used a number of editors over the years, I believe that emacs is worth learning. Once you get past the learning curve, it has a number of useful features which do not exist in other editors.

When output is to a terminal, some UNIXes flush the buffer before after the printf/cout. However, when output is to a file, it does not, resulting in two copies of the output. You can avoid this by calling flush (see man flush) before executing the fork.

Alternatively, you can use script to capture the output rather doing the redirect.

How can I capture all output to a file (including output from more than one process)?

How can I have a thread sleep for a specified amount of time?

Sometimes, you would like to delay for less than a second. The POSIX nanosleep function lets you specify a delay in nanoseconds up to a limit (see "man nanosleep" for details) To use nanosleep you must link with the realtime library "-lrt" and it should be specified after the thread library.

Sample invocation:

#include <time.h>

/* One million nanoseconds per millisecond */
#define	NSPERMS		1000000	
/* One thousand milliseconds per second */
#define MSPERSEC	1000
{
	struct timespec	SleepTime;

	... initialize DelayMS to desired time to sleep ...
	
	/* Set up delay */
	SleepTime.tv_sec = DelayMS / MSPERSEC;	 /* # secs */
	SleepTime.tv_nsec = (DelayMS % MSPERSEC) * NSPERMS; /* # nanosecs */

	/* In this case, we don't care whether or not we fail, but be
	 * sure to check the return code if you do
	 */
	nanosleep(&SleepTime, NULL);

	... rest of code
}

How can I handle POSIX signals?

Processes can be configured such that specific functions are executed when signals are sent to the process. Such functions are called signal handlers, and it is important that you understand pointers to functions before you read further.

The POSIX sigaction function can be used to specify a function to run when a certain signal (e.g. interrupt, timer) occurs:

int sigaction(int signum, const struct sigaction *action, struct sigaction *oldaction)

It returns 0 on success and -1 on failure. The signum field is any valid signal such as SIGINT (interrupt) or ITIMER_VIRTUAL (periodic timer). The pointer to the action structure must be intitialized. The action structure has the following fields:

sa_flags - Optional flags, may be initialized to 0.

sa_mask - A set of signals that should be masked (blocked) when the handler is executing.. Use sigemptyset/sigaddset/etc. to manipulate (see man page, to default with no masking, call setemptyset(&action->sa_flags)).

If oldaction is non NULL, the oldaction structure is populated with the previous action for this signal.

Example: Handling the interrupt signal (typically generated by control C in UNIX command line environments).

/*
 * Small program to demonstrate the use of POSIX interrupt handlers
 */

#include <stdio.h>
#include <signal.h>
#include <time.h>
#include <stdlib.h>

/* exit codes */
#define NORMAL 0	/* normal exit */
#define HANDLERINIT 5	/* problem with setting up interrupt handler */
#define INTERRUPTED 10  /* exited due to interrupt */

/* time conversions */
#define NSPERMS		1000000 /* million ns/ms */
#define MSPERSEC	1000  /* thousand ms/s */

#define DELAYMS	333	/* delay time in loop */

#if defined(__cplusplus)
using namespace std;	// only if compiling in C++ 
#endif

/* Number of actions to handle before exiting program */
#define EXIT_ON_NTH	3

/* void CantTouchThis(void)
 * Interrupt handler - prints out a message on first
 * EXIT_ON_NTH-1 invocations, then allows program to terminate.
 */
void CantTouchThis(int SignalNo) {
  static int InvokedCount = 0;  /* persistent across invocations */

  InvokedCount++;  /* track # times invoked */
  if (InvokedCount < EXIT_ON_NTH) {
    printf("Can't touch this\n");  /* inform user of event */
  } else {
    printf("exiting\n");
    exit(INTERRUPTED);
  }
  return;
}

int main(int argc, char **argv) {
  struct sigaction	actions;
  struct timespec	SleepTime;

  /* set up data structures for our interrupt handler */

  /* specify which signals to ignore (mask) while we are
   * handing our interrupt.  We use sigemptyset to
   * specify that none should be masked.  There are 
   * a number of ways to modify and query the mask
   * set, see man sigemptyset to see the other functions.
   */
  sigemptyset(&actions.sa_mask);	/* no masks */
  actions.sa_flags = SA_RESTART; /* permit system call restart */
  actions.sa_handler = CantTouchThis;	/* function to run */
  
  /* set the signal handler
   * In this case we set the interrupt signal.
   *
   * Note that many people count on the interrupt signal to kill a
   * process which is the default action when the user does not
   * provide one.  If you wish to kill a process whose interrupt
   * signal has been remapped to a different action, you could use the
   * SIGKILL signal which is usually generated in UNIX shells by
   * CONTROL \ (the key binding could have been changed by the user,
   * but this is the traditional way to send a kill signal).
   */
  if (sigaction(SIGINT, &actions, NULL) != 0) {
    perror("Unable to set handler\n");
    return HANDLERINIT;
  }

  /* Set up delay */
  SleepTime.tv_sec = DELAYMS / MSPERSEC; /* # secs */
  SleepTime.tv_nsec = (DELAYMS % MSPERSEC) * NSPERMS; /* # nanosecs */
  
  /* print out series of dots forever */
  while (1) {
    /* In this case, we don't care whether or not we fail, but be
     * sure to check the return code if you do
     */
    nanosleep(&SleepTime, NULL);
    printf(".");
    fflush(stdout);	/* don't buffer - see immediately */
  }
  exit(NORMAL);	/* never reached, keep the compiler happy */
}

In most cases, when a signal is generated for a process, execution is interrupted and the execution handler is run. Upon completion, execution is resumed. One tricky thing that can occur is when signals are generated during a system call. The system call will be interrupted, but it will not resume automatically unless the SA_RESTART flag is set as in the above example.

Note that is possible to temporarily prevent a signal from being received by blocking the signal. A signal set (sigset_t) is populated with the signals that the user wishes to block (the library functions sigemptyset and sigaddset are useful for this) and sigprocmask is called with SIG_BLOCK, a pointer to the mask, and either NULL or a pointer to where the old mask should be saved. The signal can be unblocked by calling sigprocmask a second time with SIG_UNBLOCK and pointer(s) to the new (and possibly old) signal set. Pending signals are delivered to the process once they are unblocked. See the man pages for details.

How can I use a POSIX timer to interrupt a process?

The POSIX XSI extension provides a way to have a signal sent to a process after a specified period of time. The delay time is specified via the itimerval structure which is specified in <sys/time.h>:

struct itimerval {
 struct  timeval it_interval;    /* timer interval */
 struct  timeval it_value;       /* current value */
};

The it_value field should be populated to describe how much time will pass before the signal is sent. Once the timer expires, it is reset to the value specified in it_interval, permitting the caller to easily create periodic events. The time is expressed as a combination of seconds and microseconds. As an example, to set a one time timer for 3.5 s, an instance of itimerval should be set as follows:

struct itimerval timer;
timer.it_interval.tv_sec = 0;	/* do not rearm timer */
timer.it_interval.tv_usec = 0;
timer.it_value.tv_sec = 3;
timer.it_value.tv_usec = 500000;

Once the interval timer structure is populated, the alarm can be scheduled using the setitimer function which has the following structure:

int setitimer(int whichtimer, const struct itimerval *newvalue, struct itimerval *oldvalue);

where whichtimer indicates one of three possible timers:

1. ITIMER_REAL - Based on actual time (wall clock), generates SIGALRM on expiration.
2. ITIMER_VIRTUAL -Only decrements when process is scheduled, generates SIGVTALRM on expiration.
3. ITIMER_PROF - Decrements when process is scheduled and when the process is making a system call. Generates SIGPROF on expiration.

newvalue must be a pointer to an itimerval structure. If oldvalue is non-NULL, the previous value of the interval timer will be copied to the structure pointed to by oldvalue. This function returns 0 on success and -1 on error.

Note that setting the timer simply permits one to generate SIGALRM, SIGVTALRM, or SIGPROF signals to a process. See the question on signal handlers to detemine how to handle a signal.

How can I use a POSIX timer to determine execution time?

Once you understand POSIX timers (see POSIX timer question), it is relatively easy to use a timer to determine how long it takes to execute code. The itimerval structure should be populated with a time that is much larger than one expects for the execution (e.g. some large number of seconds). The timer_create function can be used to create the timer that will be used. Its first argument is the type of timer (see man timer_create, the types are similar to the interval timers described above) which should be chosen based upon the desired application. The second argument specifies the event handler which in our case will be NULL. Finally, a pointer to a valid timer_t object must be passed which will be populated with the id of the new timer.

An itimerspec structure (which has the same it_interval and it_value fields as the itimerval structure) is populated with a duration longer than the code is expected to execute (some big number) and no interval. The timer_settime function can be used to set the timer (see man timer_settime). After the code is completed, timer_gettime (see man timer_gettime) can be used to populate a second structure with the time remaining. By computing the difference between the two times, you can determine how long it took the code to execute.

1. Isolate where the error occurs. There are a number of ways that this can be done:
   • Use assert statements that only print if a certain condition is met.
   • Print out variable values, progress messages, etc.
   • Use a symbolic debugger to either:
     • Set breakpoints near where the error occurs and step through the program.
     • Catch an error that causes the program to fail (e.g. a bad pointer reference)
     • Examine the log of a program (e.g. a UNIX/Linux core dump file)
2. Think about what caused the problem. This is by far the hardest part of debugging. Questions to ask yourself:
   • Does the error happen every time? If not, can you come up with a set of conditions that make it repeatable?
   • What happened prior to the line where you actually noticed the software fault? In many, if not most cases, an earlier line of code may be the culprit. Examples:
     • An earlier loop may have gone past the end of the array, overwriting a variable that is adjacent to the array. (This is not a problem in languages with array bounds checking.)
     • A write to a bad pointer may have corrupted memory.
     • A data structure such as a list or tree may have been updated improperly.
     • When using multiple threads of execution, another thread may have overwritten data in the thread where the fault occurs, or a race condition may have occurred. Multi-threaded code can be very hard to debug, and it is highly recommended that you think very carefully about where synchronization is needed and use syncrhonization constructs such as semaphores as appropriate.

Symbolic debuggers let you set breakpoints in your code and inspect/modify variables. There are a number of debuggers for UNIX and linux. One of the most widely available is gdb, the GNU debugger. It is command line oriented, which makes it useful in many situations when graphical interfaces are not available (e.g. debugging remotely over a low bandwidth connection). Several GUI front-ends have been built for gdb, such as ddd and it has been integrated into emacs. Other debuggers such as sdb and dbx are also available on some systems.

GNU debugger (gdb)

When using gdb, you will need to compile with gcc or g++ and provide the "-g" flag. If you compile and link as separate steps, you will need to use -g for both steps. Gdb lets you set breakpoints, conditional breakpoints, modify variables and even attach to a running program or core dump.

The gdb user manual is available by typing "info gdb" from most UNIX/linux/cygwin prompts. Before doing this, you may want to type "info info" to learn how to use the GNU info browser. Alternatively, you browse the documentation on the web. There are several good gdb tutorials on the Internet. A very brief but informative one is available from Professor Donahoo at Baylor. Salzman and Matloff also published a book, The Art of Debugging with GDB and DDD that is available on Safari online through our library.

If you are an emacs user, emacs has a very nice interface to gdb where you can see the code in half of the window and the code in the other. Just type M-x gdb to start it. Emac's debugger is called the grand unified debugger (gud) and actually works with several debugging programs. Read about Debuggers in the Emacs documentation to learn more about gud.

ddd

eclipse

How can I use POSIX threads (pthreads)?

Sample program using pthreads:

• You must include the header file pthread.h.
• You must link the library (-lpthread) at the end of the compilation line. If you do not do this, your program will not work although it will compile without any warnings.
• If you use sched_yield, you must include sched.h and link the real time library (-lrt). The real time library should be linked after the thread library: -lpthread -lrt
• If you use C++, you should provide a C linkage for the function that you plan on starting in the thread. This should be in a header file or someplace before the call to pthread_create(). In the following example, it would be: extern "C" void * print_message_function(void *);

	#include <stdio.h>
	#include <pthread.h>
	#include <sched.h>	/* Only necessary for sched_yield */
	
	void * print_message_function( void * VoidPtr )
	{
	  char *message;
	  message = (char *) VoidPtr;
	  printf("%s", message);
	  fflush(stdout);	/* Make sure we see it right away */

	  /* If we wanted to return something, we would return a pointer
	   * to the data that we wanted to return.
	   *
	   * Instead of simply using return, we could also call
	   * pthread_exit.
	   */
	  return NULL;
	}
	
	int main()
	{
	  pthread_attr_t	pthread_attributes;
	  
	  pthread_t thread1, thread2;
	  char *message1 = "Hello";
	  char *message2 = " World";
	  
	  /* Populate attributes with defaults
	   * If we wanted to customize this, we would probably
	   * first set the defaults and then change as need. 
	   */
	  pthread_attr_init(&pthread_attributes);

	  /* Start threads to write out messages 
	   * Please note that we are not checking the return,
	   * this is something that you should figure out how
	   * to do on your own.
	   */
	  pthread_create( &thread1, &pthread_attributes,
			  &print_message_function, (void *) message1);

	  /* Provide N secs for completion (very bad idea to rely on this)
	   * Use pthread_join instead, but you should learn to do this
	   * on your own.
	   */
	  sleep(5);

	  /* Note that this time we don't pass the pthread_attributes
	   * structure.  Instead we pass NULL which tells POSIX threads
	   * to just use the defaults.
	   */
	  pthread_create(&thread2, NULL,
			 &print_message_function, (void *) message2);

	  /* Provide N secs for completion (very bad idea) */
	  sleep(5);
	  
	  exit(0);
	}
	

How can I use POSIX unnamed semaphores?

To use a POSIX semaphore, you must include semaphore.h and declare a variable of type sem_t. We will consider three operations on the semaphores although POSIX defines a few others: sem_init, sem_wait, and sem_post. In addition, you must include the POSIX real time library -lrt while compiling It should go after the POSIX thread library.

As an example, suppose that you are doing separate compilation and have objects for demofiles 1 through N that you want to link:

edoras> gcc -o semaphore_demo demofile1.o ... demofileN.o -lpthread -lrt

• sem_init(sem_t *SemaphorePtr, int pshared, unsigned int Value) - Initializes the semaphore pointed to by SemaphorePtr to the count contained in Value. Parameter pshared is not used for unnamed semaphores and should always be set to zero.
• sem_wait(sem_t *SemaphorePtr) - Performs a down on the semaphore pointed to by SemaphorePtr.
• sem_post(sem_t *SemaphorePtr) - Performs an up on the semaphore (post is yet another pseudonym for up/v/signal)

#include "semaphore.h"

void foo() {
   sem_t	MutualExclusion;

   /* 
    * Initialize semaphore.
    * Conceptually, this is:  Semaphore MutualExclusion = 1 
    */
   if (sem_init(&MutualExclusion, 0, 1) == -1)
	unable to initialize semaphore, report failure;

   /* launch threads bar_none, bar_chocolate 
    * These routines are passed a pointer to MutualExclusion
    * and any other parameters they might need.  As POSIX
    * threads only permits one argument, this will have to
    * be packaged into a data structure.
    */

    /* wait for threads to exit */
}

void bar_none(parameter structure) {
   /*
    * Assume SemaphorePtr is of type sem_t *
    * and points to the MutualExclusion semaphore 
    * passed in via the parameter structure
    */

    control structure (i.e. loop) {
       /* remainder */

       sem_wait(SemaphorePtr);	/* entry */

       /* mutual exclusion - do what we need to do */

       sem_post(SemaphorePtr);	/* exit */

       /* remainder */
    }
}

It is possible for sem_post and sem_wait to fail, but only when using signal handlers. As we will not be doing this, you may ignore the sem_wait and sem_post return codes for this assignment, but you should remember that they are a possibility. The man pages may be helpful for all three of these operations.

In addition, I have written a toy program which implements a critical region for the x++ and x-- example that we have done in class. You may find it useful to look at this program. Note that as the time slices per thread are reasonably large, you will need to put large values for the number of times that you increment or decrement before you start to see interleaving between the threads.

I have two structures/classes that I would like to point to one another. How can I do this?

class foo {
private:
  class bar *BarPtr;	// Compiler will not complain as it knows how many
			// bytes a pointer is and has been reassured that
			// you will define bar someplace else.  
			// It is very important that we used the word "class"
			// in the class bar declaration as bar does
			// not exist yet.  

			// As an alternative, we could have placed the
			// line "class bar;" before the class foo
			// declaration, and the compiler would have
			// been satisfied with a "bar *BarPtr;" declaration.
			
			// Note that the declaration:
			//    class bar Bar;
			// would be illegal as the compiler would not know
			// how much memory to allocate (since bar has not
			// been defined yet.

  // other things to make this class useful
};

class bar {
private:
  class foo	*FooPtr;	// Pointer to class foo.
				// The word class is optional.

  // other things to make this class useful
};  

struct foo {
	struct bar	*BarPtr;	/* Pointer to a bar structure 
                                         * It is important to include the 
                                         * word struct as the bar structure
                                         * has not yet been defined.
                                         */
	/* other information... */
};

struct bar {
	struct foo	*FooPtr;	/* Pointer to a foo structure
					 * Note that we could have simply
					 * typed foo here as foo has already
					 * been declared.  (Although I think
					 * most C programmers would probably
					 * write the words struct to make this
					 * obvious.)
					 */
	
	/* other information... */
};

How can I have an array of unspecified size be part of a structure/class?

struct xyzzy {
	struct great_underground_empire	*zork;
};

	struct xyzzy a_struct;
	/* we could also use calloc which has slightly 
	 * different syntax, see man pages for details
	 */
	a_struct.zork = malloc(sizeof(struct great_underground_empire) * N);

	/* ... check if pointer allocated okay ... */
	
	/* use item.  We'll assume name is a valid field
	 * and idx is */
	a_struct->zork[idx].name = "Flood Control Dam #3";

	/* Don't forget to visit the great underground empire (Zork I)
	 * at http://zorkonline.net/
	 */
    

Just what exactly goes in a header file?

Header files should only include type definitions (including function prototypes) and macros. As an example, suppose we had an implementation of the abstract data type stack in file stack.c. It might have a typedef for items on the stack, and routines to push onto and pop from the stack. We could define a header file, stack.h that could then be used by callers who wish to use the stack data type. Our stack.h might look like the following:

typedef struct _stacknode {
    void *data_ptr;  /* pointer to arbitrary data */
    /* pointers to next and previous node in stack */
    struct _stacknode *next;
    struct _stacknode *prev;
} STACKNODE;

typedef struct _stack {
    STACKNODE *last;
} STACK;

/*
 * bool push(STACK s, STACKNODE item)
 * push item onto stack s
 * returns true if successfull, otherwise false
 *
 * The next line is a signature.  The implementation is in the .c file
 */
bool push(STACK, STACKNODE); 

/*
 * STACKNODE *pop(STACK s)
 * Pop a stack node from the stack, returns NULL if empty
 */
STACKNODE *pop(STACK);

/*
 * STACK * create_stack()
 * Return a pointer to a new stack, NULL on failure.
 */
STACK * create_stack();

Never declare functions in header files. The only exception to this is C++ templates, and then only if you know what you are doing. Many students have a tendency to include functions in a header file, i.e. "kitchen_ops.h" and then include those functions into another file. This is a bad programming habit.

Header files are frequently included by more than one file. Suppose leonidas.c and neuhaus.c are both part of the same program and both need to use the functions whose signatures are defined by the prototypes in kitchen_ops.h. If we were to put actual code in kitchen_ops.h, the compiler would generate two different sets of functions. One for the object code associated with leonidas.c and the other for the neuhaus object code. When the linker tries to combine these two object files, errors will result due to the duplication of functions.

The correct way to do this is to put the prototypes in the header file and the functions in a .c file such as kitchen_ops.c. While our example was for the C language (or so one would assume by the .c file extension), the same is true of C++.

Sometimes people get in trouble when the same header file is included from multiple places, e.g. you include foo.h and bar.h and they both include ohoh.h. One trick to keep problems from arising is to use the macro preprocessor to only process statements if they have not been seen before. Here is an example for ohoh.h:

/* OHOH_H is a name that is unique to our program.  It is usualy easiest
 * to derive this from the filename.  The basic idea is that the first time
 * we load this file, the macro preprocessor will not have seen the name
 * and we define the name, then load everything from the header.  If it is
 * loaded again in the same compilation target, then we skip over the content
 * as it is already defined.
 */
#ifndef OHOH_H  
#define OHOH_H

/* standard header stuff here */

#endif

How do I determine the number of bytes (size) of various data structures?

How can I use pointers to functions?

In order to do this, we need to declare pointers to functions. In C and C++, the type of a function is defined by its signature.

Suppose that we wished to compare two integers and return -1 of the first was smaller, 0 if they are the same, and 1 if they are different. We might write a function like this:

/* Avoid sprinkling our code with magic numbers */
#define X_LESS_THAN__Y	-1
#define	X_EQUALS_Y	 0
#define X_GREATER_THAN_Y	 1

/* compare_ints(x, y)
 * Returns:  x == y -> 0, x < 1 -> -1, x > y -> 1
 */
int compare_ints(int x, int y) {
	if (x > y) 
		return X_GREATER_THAN_Y;
	else if (x < y)
		return X_LESS_THAN_Y;
	else
		return X_EQUALS_Y;
}

It has a function signature of: int compare_ints(int, int).

Let us declare a pointer to this function:

	int (* Pointer)(int, int);

	/* Set Pointer to the address of compare_ints using the
	 * address operator &
	 */
	Pointer = &compare_ints;

	/* Also sets Pointer to the address of compare_ints */
	Pointer = compare_ints;

	/* Assume other variables of the appropriate type... */

	/* call compare_ints(Array[i], Array[j] */
	Result = (* Pointer) (Array[i], Array[j]);

	/* For similar reasons as to why we permitted dropping the
	 * address operator (&), we can also omit the dereferencing
	 * operator (*).
	 */

	 /* Another way to do it... */
	 Result = Pointer(Array[i], Array[j]);

This is pretty neat, but it does not solve the problem that we originally had, how to pass in a generic comparison routine. C/C++'s solution to this is the pointer to void type. A variable of type pointer to void (void *) points to something without knowing the type.

So in our quicksort routine, we could declare the following as one of the arguments:

	int (*ComparisonFn)(void *, void *)

int compare_ints(void * xVoidPtr, void * yVoidPtr) {
	int *xIntPtr, *yIntPtr;

	/* type cast the void pointers to int pointers */
	xPtr = (int *) xVoidPtr;
	yPtr = (int *) yVoidPtr;
	
	/* dereference and compare */
	if (*xPtr > yPtr) 
		return X_GREATER_THAN_Y;
	else if (*xPtr < *yPtr)
		return X_LESS_THAN_Y;
	else
		return X_EQUALS_Y;
}

Now we can use the same function signature to compare any two items, and pass the function name to our quicksort routine. Note that for this example, we should have declared the arguments to be const as we are not modifying them, but this was omitted for pedagogical reasons.

#include "foobar.h"

// Functions in foobar.h are compiled with a C compiler
extern "C" {
#include "foobar.h"
}