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.

What command would you type to see what number to enter?
Your friend shows you the following display:

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

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

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?

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.

Check your answers here

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 use the pos_tag, end_tag representation from last time:

struct io61_file {
   int fd;
   unsigned char cbuf[BUFSIZ];
   off_t tag;      // file offset of first character in cache
`    off_t end_tag;  // file offset one past last valid char in cache; end_tag - tag == old `csz` `
`    off_t pos_tag;  // file offset of next char to read in cache; pos_tag - tag == old `cpos` `
};

Except now we’re going to write, not read.

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

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 seeing later. We first need to determine if there is space in the buffer to write any data. What expression checks for that condition?

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

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 different places we may need to write data back?

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:

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:

The data you are writing fits nicely in your buffer.
The data you are writing does not fit into your current buffer.

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.

Check your answers here

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.)

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.)

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

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

Check your answers here

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?

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?

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

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?

Check your answers here

Survey

Don’t forget to fill out the survey!