CSE 121 Spring 2003

Homework 2 Solutions

Problem 1

1. Please read the section on checkpointing and recovery in Rosenblum's LFS paper that was passed out in class.

In Sprite LFS, segments are written from back to front. For example, below is a diagram showing a segment that has had one write performed on it.

After one more write, the segment could look like this:

A third write would fill the segment (in this diagram, it would write two data/inode blocks and one summary block) and then start filling a new segment.

1. Consider the roll-forward procedure in crash recovery for Sprite LFS. How does the roll-forward procedure determine when to stop rolling forward? If you can't determine this from the paper, then make an educated guess and justify your guess.


The segment summary block points to where the next segment summary block will be written. Either that block does not contain a segment summary block (the format would not match) or it does contain a segment summary block. If the latter is true, roll-forward must be able to determine whether it was written before or after the last checkpoint. A simple timestamp can be used to determine this.
 

2. Sprite LFS wrote the segments as outlined above because it allowed the cleaner and the roll-forward procedure to make the assumption that if a segment summary block was safely written to disk (such as the last block in the segment shown above), then all of the blocks described by the segment were also safely written to disk. Unfortunately, this is based on the assumption that a disk controller writes blocks in the sequence they are stored in memory. In order to reduce rotational latency, some controllers start the write transfer depending on the current rotational position of the head. For example, in the first write shown above, the controller could first write out the last three green blocks, and then the segment summary block, and then finally the first three green blocks.

What impact does this have on recovery? How would you change the way that LFS writes data to disk (the order, the contents, or both) in order to accommodate such disk controllers.

It has a very serious impact on recovery - roll-forward cannot determine whether all of the segment pages were written or not. If they were not, then some of the disk pages will contain garbage. A simple technique to detect such cases is to include in the segment summary block a checksum of the pages in the segment. If the checksum doesn't match, then some pages were not written out. 

Problem 2

void InsertNode (Node* first, last, new) {
   Node *at = first;
   while (at != NULL && at->key > new->key) at = at->next;
   if (at == NULL) {          // Insert as last node in list
     new->prev = last;
     new->next = NULL;
     if (last == NULL) first = new;
     else last->next = new;
     last = new;
     }
   else {                     // Insert before at
     new->prev = at->prev;
     new->next = at;
     if (at->prev == NULL) first = new;
     else at->prev->next = new;
     at->prev = new;
     }
   }

1. Consider using the Rio cache approach: this routine is used to maintain a data structure that is read after the machine recovers from a crash. How could a machine failure leave this doubly linked-list in an unsafe condition? The forward links and the backward links my not agree. For example, when inserting a node before another one, the prev pointer is updated after the next pointer. Thus, a poorly-timed crash could make it possible for a routine that walks the list backwards to see a different list than one that walks the list forward.
    
   
2. Suppose that Rio indeed used such a doubly-linked list. How would you design Rio to deal with the problem? (Note that you have two general choices to consider: either doing something so that the datastructure is not seen in an unsafe condition or doing something to make it consistent). A simple recovery strategy would be, upon recovery, to enumerate the list starting from the value of first. Once the list has been enumerated, the back pointers could be set to the correct value. Invoking the routine below as CorrectList(first, &last) will do this:
   
   void CorrectList (Node * first, Node ** last) {
      Node * at = NULL;
      *last = first;
      while (first != null) {
         first->last = at;
         at = first;
         first = first->next;
         }
      }
    
   
3. The Rio paper does not discuss the impact of either the L1 or L2 cache. The existence of such caches complicate building Rio. Explain why, and how one could change Rio to accomodate such hardware caches. There's no telling when a value from cache will be flushed to memory. Cache is lost when a crash occurs, and so Rio can only count on what is on disk and in physical memory to recover.
   
   Thus, Rio would need to implement some kind of "flush" mechanism to ensure that cache has made it to disk. In practice, this is often done by writing enough memory (and thus loading the caches) to ensure prior writes are complete. Then, since there is no determinable order as to when cache makes it to memory, Rio would need to implement some kind of transactional abstraction. For example, considering the linked list described in this question, Rio could maintain two lists, say list A and list B. There would also be a memory location x whose value would be either A or B: it would have an initial value of A. To update the list, Rio first adds it to the list not indicated by x and flushes the contents of cache. It then sets x to indicate the other list and flushes cache again. Finally, Rio updates updates the list that was not updated. During recovery, Rio reads the list indicated by the value x.
   

Problem 3

#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define bufSize 8192
#define passes 5

char buf[bufSize];

int main (int argc, char **argv) {
  int count, pass;
  int nblocks;
  int file;
  int rstatus;
  hrtime_t rt_elapsed[passes+1];
  if (argc != 3) {
    printf("Need file name and number of MB to read.\n");
    exit(1);
    }
  nblocks = atoi(argv[2]);
  if (nblocks <= 0) {
    printf("%s is not an integer that is at least 1.\n", argv[2]);
    exit(1);
    }
  nblocks = nblocks * 256;
  file = open(argv[1], O_RDONLY);
  if (file < 0) {
    printf("Could not open file %s.\n", argv[1]);
    exit(1);
    }
  printf("Reading first %s MB of %s.\n", argv[2], argv[1]);
  pass = passes;
  rt_elapsed[0] = gethrtime();
  for (pass = 0; pass < passes; pass++) {
    count = nblocks;
    while (count-- > 0) {
      rstatus = read(file, buf, bufSize);
      if (rstatus < bufSize) {
        printf("Read returned with status %d", rstatus);
        exit(1);
        }
      }
    rt_elapsed[pass+1] =gethrtime();
    lseek(file, 0, SEEK_SET);
    }
  for (pass = passes; pass > 0; pass--)
    rt_elapsed[pass] = rt_elapsed[pass] - rt_elapsed[pass-1];
  for (pass = 1; pass <= passes; pass++)
    printf("The average time to read a block in pass %d was %lld usec.\n",
            pass, rt_elapsed[pass]/(1000*nblocks));
  close(file);
  exit(0);
}