[COMPSCI 210] Recitation 1: Programming C
14th Jan 2013, Vamsi Thummala

-- Concept Checkers

    o Discuss briefly the classical view of an OS vs. a modern OS?

    o List some examples of modern operating systems.

    o List some abstractions provided by an OS.

    o What is an address space?

    o What is a system call (syscall)?

    We will periodically revisit some of these questions during the course of
    the semester.

-- Logistics

    o Labs: are important. Labs are designed to supplement the lectures and
      provide the hands-on experience of building real systems. You will learn
      a lot in this class through lab assignments. You should submit all labs 
      to pass this course!

    o Unix accounts: You are free to program in any OS you want. However, we
      provide support only for Linux systems. If you do not have a CS account
      and wish to have one, please write to me (vamsi AT cs.duke.edu) asap!

    o Recitations: You will benefit most from the recitations if you revisit
      the lectures notes from the previous week and participate in the
      discussion. I will revise the primary concepts but focus mostly from the
      labs perspective.

    o Piazza: Great resource for posting questions and discussion.

    o UTA: Seven highly qualified UTAs. Office hours every day
      in the Link. Check piazza staff page for timings.

    o Lab1: Dynamic Memory Allocation aka Heap Manager is out. Two due dates:
      Design (filled README) due on 21st Jan and code with revised design due
      on 28th Jan.

-- Why C?

    o Concise, high-level (w.r.t assembly languages), provides explicit control
      over memory (pointers), compiled and fast! Just the right features
      required for building an operating system.

    o Most operating systems are written in C or its variants (C++ to a
      limited extent).

    o Dennis Ritchie, the father of C, went on to design Unix along with Ken
      Thompson. 

    o Rebirth in pop culture. Rated as top language for the year 2012 [1].
      Check also the recent discussion on HN [2].

-- Resources for learning C 

    o The first book on C by Dennis Ritchie and Brian Kernighan is concise and
      still the best resource to learn C! However, you do not need to master C
      for doing the labs. The __Essential C__ notes on the resources page
      provides a good primer for you to get started. Check the other
      references on the resources page.

    o Also, check the C directory under lab1, which contains the basic C
      programs for you to get started.

-- Let's get started
   
    o Open a shell and editor

    /* Obligatory Hello World example*/
    void helloWorld() {
        char string[] = "Hello COMPSCI 210";
        printf("Using format specifier: %s\n", string);
    }

    o Compile using gcc and make

-- Pointers in C 

    o Pointers: Major conceptual change for most of you coming from a Java
      background. In Java, storage objects are automatically garbage collected. In
      C, you need to manage your own memory explicitly.

      A pointer is a data type (int) whose value refers to another value
      stored elsewhere in the computer memory, i.e., a pointer contains the
      address of a variable, and fetching the value of the variable given the
      pointer is called dereferencing the pointer.

      float pi = 3.14;
      printf("%f\n", pi);
      printf("%p\n", &pi);  // & provides the address of pi

      int *ptr1, *ptr2; // ptr is a pointer of type int
      ptr1 = 0x444; // assigning an address to a pointer; is this valid?
      printf("%p\n", ptr1);
      *ptr1 = 4;
      printf("%d\n", *ptr1); // is this valid?

      ptr1 = (int *) malloc(sizeof(int)*1);
      printf("%p\n", ptr1);
      printf("%d\n", *ptr1); // any guesses?

      *ptr1 = 4;
      printf("%d\n", *ptr1);

      ptr2 = ptr1;
      printf("%d\n", *ptr2); 

      *ptr2 = 5;
      printf("%d, %d\n", *ptr1, *ptr2);       

    o Address space

	int main(int argc, char *argv[]) {

	    printf("location of code : %p\n", (void *) main);

	    printf("location of heap : %p\n", (void *) malloc(1));

	    int x = 210;

	    printf("location of stack : %p\n", (void *) &x);

	    return x;
	}

    o Swap function in C

      /* Local swap using call by value*/
        void swap_local(int x, int y) {
            int temp;
            printf("Before swap: %d, %d\n", x, y);
            temp = x;
            x = y;
            y = temp;
            printf("After swap: %d, %d\n", x, y);
        }
 
      int x = 4, y = 5;
      swap_local(x,y);
      printf("%d, %d\n", x, y); // What is the expected output?

       /* Swap using call by reference */
        void swap(int *x, int *y) {
            int temp;
            temp = *x;
            *x = *y;
            *y = temp;
        } 
          
      swap(&x,&y);
      printf("%d, %d\n", x, y); // What is the expected output?
  
    o Arithmetic on pointers

     int *iptr = 0x444;
     iptr = iptr + 1;
     printf("%p\n", iptr); // What is the expected output? 

     float *fptr = 0x444;
     fptr = fptr + 1;
     printf("%p\n", fptr); // What is the expected output?

    o Dynamic memory allocation example

     char *arr; // declare a variable arr, a pointer to char

     /* allocate a block of memory big enough to hold 11 chars*/
     arr = (char *) malloc(sizeof(char)*11); 

     if(arr == NULL) { // Error checking
        /* Throw an error using a perror syscall */
        perror("Error in memory allocation");
       /* Exit the program with failure status*/
        exit(EXIT_FAILURE);     
     }

     strcpy(arr,"compsci210"); // Is this safe?

     printf("%s, %s, %c, %c, %c, %c\n",arr, arr+0, arr[0], 0[arr], arr[1], 1[arr]);

     printf("%s\n",arr+12); // Is this valid?

     free(arr); // Free the memory associated with the pointer

     printf("%s\n",arr); // Is this valid now?

     arr = NULL;

     printf("%s\n",arr); // What is the expected output? 

    o What actually happens in a pointer cast?
    
        -- Nothing! It's just an assignment. Also remember that all pointers
           are of the same size. 

        -- The magic happens in dereferencing and arithmetic!

-- Structures

    o Just like Java classes but does not contain any methods (functions).

     typedef struct {
        int id;
        float PI;
        char ch;
        char* name;
     } student_t ;

    int size_int = sizeof(int);
    int size_float = sizeof(float);
    int size_char = sizeof(char);
    int size_charArr = sizeof(char *);

    printf("Size of int: %d\n", size_int);
    printf("Size of float: %d\n", size_float);
    printf("Size of char: %d\n", size_char);
    printf("Size of char *: %d\n", size_charArr);
    printf("Estimated size of the student_t structure: %d\n", size_int + size_float + size_char + size_charArr);
    printf("Actual size of student_t structure: %d\n", sizeof(student_t));


    student_t *alice, *bob, *charlie;
    alice = (student_t *) malloc (sizeof(student_t));

    /* Check if memory is available */
    if(alice == NULL) {
        perror("Error in malloc\n");
        exit(EXIT_FAILURE);
    }

    (*alice).id = 10;
    (*alice).PI = 3.14;
    (*alice).ch = 'A';
    (*alice).name = "Alice";

    printf("Id: %d, %d\n", (*alice).id, alice->id);
    printf("PI: %.2f, %.2f\n", (*alice).PI, alice->PI);
    printf("ch: %c, %c\n", (*alice).ch, alice->ch);
    printf("name: %s, %s\n", (*alice).name, alice->name);

-- Macros in C
    
    o #define WORD_SIZE 4 // OK
      #define DWORD(x) 2*x // NOT OK
      
      DWORD(x+1) becomes 2*x + 1

    o Powerful (think Lisp) but often misused

    o Why macros?
        -- Faster than function calls
        -- At compile time replaces function calls with code

     /* ALIGN rounds up to the nearest multiple of ALIGNMENT;
      * Q: What is the result of x & ~x? (note the bitwise operators)
      *    Now, what is the result of (size + x) & ~x?
      */

    #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))

-- Heap Manager (Lab1)

    o Implement simplified malloc and free versions called dmalloc and dfree

    o Metadata structure

      typedef struct metadata {
      /* size contains the size of the data object or the amount 
       * of free bytes 
       */
        size_t size;
        struct metadata* next;
        struct metadata* prev;  // Why is this needed?
      } metadata_t;


    o Syscalls  sbrk, mmap fetch large block of memory from heap

     metadata_t* freelist = (metadata_t*) sbrk(MAX_HEAP_SIZE);

     Why is invoking a syscall an expensive operation?

    o Concepts: Splitting, coalescing, freeing space, and fragementation

    o Fragementation analogy: Car parking example

-- Practice C problems: C directory under lab1. Start with util.h and 
   test_util.c

-- Next recitation

    o Birth of a program: Illustration through C

-----
[1] http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html        
[2] http://news.ycombinator.com/item?id=5037089