Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

9/11/16: Caches: Writing and the Single Slot Cache

But first -- some midterm review!

A couple of midterm review problems

Q1

Your friend shows you a binary bomb and explains that the number to be entered has to match the integer stored at the address 0x601048.

0x601048 <arr+8>:  0xe0    0xd1    0xee    0x0b    0x43    0x65    0x87    0x09

What number would you suggest entering? (You may express it in hexidecimal.)

They key here is that this is a little endian machine, so the byte at 0x601048 is the least significant byte. So, the value would need to be 0x0beed1e0

Q2

Another friend is working on the debugging malloc and shows you the following code (assume sz is properly defined and refers to the size the caller to the debugging malloc wishes to allocate):

void *m, *payload;

m = malloc(sizeof(struct meta) + sz); payload = m + sizeof(struct meta);

Your friend says that this runs just fine on the appliance but crashes on a different machine. Explain why?

Pointer arithmetic on void * types is undefined behavior -- the compiler is allowed to do anything it wants! If you want to add sizeof(meta), you should be using a char *; but better still is to make the variable m be of type struct meta * and then set payload (properly cast) to m + 1.

Q3

In class you worked on a garbage collector implementation. Even if you did the exercise entirely correctly, there are cases where you might not successfully reclaim all unused space. Explain how this could happen.

We mark any allocation that might still be active and we determine that by scanning all the places variables might be and looking for things that look like addresses. However, if I have some value that happens to match the address of an allocation, the collector will assume that that value is, in fact, a pointer to the allocated region and will not free it. The allocator must make this conservative assumption to avoid destroying data that is still being used.

And now back to caching

We are going to continue to work in the context of Thursday's exercise. Once again, write out your answers using pencil and paper -- don't worry about compiling and running this.

Part 1: Writing

Let's see if we can make our single slot cache do some writing. For the remainder of this exercise, let's build on the pos_tag, end_tag representation from last time (modifying meanings slightly):

struct io61_file {
   int fd;
   unsigned char cbuf[BUFSIZ];
   off_t tag;          // file offset of the first character in the cache
   off_t end_tag;  // file offset of first invalid position in cache
   off_t pos_tag;  // file offset of next char to write
};

Q1: If we open a file for writing, how should we initialize the three tag fields of the io61_file structure?

We need to position our buffer at the beginning of the file and the buffer should not contain anything, so:

   f->tag = f->pos_tag = f->end_tag = 0;

Now let's look at the write call:

// io61_write(f, buf, sz)
` //    Write `sz` characters from `buf` to `f`. Returns the number of `
` //    characters written on success; normally this is `sz`. Returns -1 if `
//    an error occurred before any characters were written.
ssize_t io61_write(io61_file* f, const char* buf, size_t sz) {
}

Q2: For now, let's just worry about sequential writing; we'll get to seeking later. We first need to determine if there is space in the buffer to write any data. What expression checks for that condition?

 if (f->pos_tag - f->tag < BUFSIZ)

Q3: What condition indicates that our buffer is full and we need to write data to the backing file?

 if (f->pos_tag - f->tag == BUFSIZ)

Because standard IO implements a write-back cache, we may need to invoke the write system call at times in addition to inside io61_write.

Q4: Can you think of two places (other than inside io61_write) where we may need to write data back?

When the user asks us to
When we close the file

Rather than invoke the write system call directly from io61_write, we'll invoke in a function called io61_flush, which looks like this:

// io61_flush(f)
` //  Write all buffered data written to `f`. `
// Leaves tag, pos_tag, and end_tag in position to handle a sequential write.

Q5: Write the io61_flush(f) function:

int io61_flush(io61_file* f) {
        if (f->end_tag != f->tag) {
            ssize_t n = write(f->fd, f->cbuf, f->end_tag - f->tag);
            assert(n == f->end_tag - f->tag);
        }
        f->pos_tag = f->tag = f->end_tag;
        return 0;
}

Q6: Now that you have io61_flush written, complete the io61_write function.

If you want some guidance on implementing io61_write, consider the two cases:

As we did with the io61_read call, you should be able to implement this function calling memcpy and io61_flush from just one place.

ssize_t io61_write(io61_file* f, const char* buf, size_t sz) {
   size_t pos = 0;
   while (pos != sz) {
       if (f->pos_tag - f->tag < BUFSIZ) { // There is still space in the buffer
           ssize_t n = sz - pos; // Calculate bytes left to write
           if (BUFSIZ - (f->pos_tag - f->tag) < n)
               n = BUFSIZ - (f->pos_tag - f->tag);
           memcpy(&f->cbuf[f->pos_tag - f->tag], &buf[pos], n);
           f->pos_tag += n;
           if (f->pos_tag > f->end_tag)
                     f->end_tag = f->pos_tag;
           pos += n;
       }
       // The position should never exceed the end tag.
       assert(f->pos_tag <= f->end_tag);

       // Check if we've filled the buffer and if so, call flush to write data.
       if (f->pos_tag - f->tag == BUFSIZ)
           io61_flush(f);
   }

   return pos;

}

Part 2

It's time to handle seeks.

Here is our seek routine from last time:

int io61_seek(io61_file* f, off_t off) {
    if (off < f->tag || off > f->end_tag) {
        off_t r = lseek(f->fd, off, SEEK_SET);
        if (r != off)
            return -1;
        f->tag = f->end_tag = off;
    }
    f->pos_tag = off;
    return 0;
}

Q7: What must you do before calling lseek? (Hint: think about the possible state of your buffer.)

If you were writing this file, then you might have dirty data left in your buffer. Before you go seeking somewhere else and writing new data into your buffer, you'd better flush what's there.

Q8: Add a new field to your io61_file structure so you can track the information necessary to deal with Q7. (Hint: Take a look at the arguments to io61_fdopen in Assignment 3.)

int mode;

Q9: List all the functions you should update to reflect this new field.

io61_fdopen (set the mode)
io61_write (check the mode)
io61_close (check mode and call flush)
io61_flush (check mode for flushing)

Q10: Now modify io61_seek to work in the presence of writes.

int io61_seek(io61_file* f, off_t off) {
    if ((f->mode & O_ACCMODE) != O_RDONLY)
        io61_flush(f);
    if (off < f->tag || off > f->end_tag
        || (f->mode & O_ACCMODE) != O_RDONLY) {
        off_t r = lseek(f->fd, off, SEEK_SET);
        if (r != off)
              return -1;
        f->tag = f->end_tag = off;
    }
    f->pos_tag = off;
    return 0;
}

Part 3

At the very end of last exercise, we offered the following Hint: Ensure that f->pos_tag is always aligned on a multiple of BUFSIZ.

Q11: Why might you want the tag to be a multiple of BUFSIZ?

There are at least two good reasons to make the the tag a multiple of the BUFSIZ. First, note that in the sequential case, this will happen naturally. By enforcing this we make sure that sequential and random access work well together. Second, if we look ahead to making our single-slot cache a multi-slot cache, then making tags be a multiple of BUFSIZ ensures that we'll never have data from a specific offset in the file reside in two different slots (and we will never have to explicitly check for this condition).

Q12: In the exercise, we left BUFSIZ unspecified. Let's now talk about some constraints we might want to impose on BUFSIZ . We started off by suggesting you consider a BUFSIZ of 8. Do you think this is a good BUFSIZ for Assignment 3? Why/Why not?

This is probably way too small to provide good performance. Eight bytes can just hold a long or a pointer! We want to amortize the cost of each disk IO by improving the likelihood that we'll get a lot of cache hits. So, we probably want something much larger than eight bytes.

Q13: Do you think 10 MB would be a good value for BUFSIZ ? Why/Why not?

OK, we said larger, but 10 MB seems a bit on the large side. That would mean that even for a tiny file, we'd allocate multiple MB of memory. While memories are large, that seems quite wasteful.

Q14: Can you think of some constraints you want to place on BUFSIZ or some guidelines you'd like to use to select its value?

So, how do we pick a BUFSIZ? What features would we like to have in our buffer size?

  • BUFSIZ should be larger than the minimum block size of the storage layer from which we are obtaining data. In other words, if we can't actually access data from the lower layer in units smaller than N bytes, we should make our BUFSIZ at least N bytes. While standard IO can read any number of bytes from the operating system, we might want to think of designing for an underlying file system. Today's file systems rarely support blocks smaller than 4 KB, so that might be a reasonable minimum size.
  • Hmmm -- notice that 4 KB, we seem to naturally be thinking in powers of 2 -- that seems like a good idea too.
  • Ideally we'd like to get enough data when we make the system call that we amortize the fixed overhead across a lot of bytes.
  • At the same time, we don't want to read so much data that we consume an exorbitant amount of memory.
  • So, we probably want some relatively small multiple of 4 KB