Single-Slot Cache Solutions

These are solutions for the Storage 3 exercise, single-slot cache.

Part 1

Q1

f->cpos = f->csz = 0;

Q2

assert(f->cpos <= f->csz);

Q3

The cache is always invalid/empty when f->csz == 0, but it is invalid/empty at other times too. The cache won’t be useful for the next sequential read when f->cpos == f->csz. Given the invariant f->cpos <= f->csz (and since f->cpos is unsigned), we can see that f->csz == 0 implies f->cpos == f->csz; so the minimal invariant is that the cache is invalid/empty when f->cpos == f->csz.

Q4

No. An invalid cache has f->cpos == f->csz, so our initialization marks the cache as invalid.

Q5

The character a is copied into buf. f->cpos advances by one, to 1. The function returns 1.

Q6

The characters bcd are copied into buf. f->cpos advances by three, to 4. The function returns 3.

Q7

First, the characters efgh are copied into buf[0]–buf[3]. f->cpos advances by four, to 8. This makes the cache invalid/empty, since f->cpos is the same as f->csz, but the user requested more characters. We must refill the cache.

The code should call read(f->f, f->cbuf, BUFSIZ) to refill the cache. The file contains the alphabet, so this will likely read ijklmnop into f->cbuf. f->csz is set to 8 (again), since read returned 8, and f->cpos is set to 0.

Then the last two requested characters, ij, are copied into buf[4] and buf[5]. f->cpos advances by two, to 2. The function returns 6.

Part 2

Q8

memcpy. We use the characters currently in the cache before we read more characters. The point of the cache is to avoid when possible access to slow storage, which in a stdio cache means read.

Q9

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->cpos != f->csz) {
            // cache is valid
        } else {
            // cache is invalid/empty
        }
    }
    return pos;
}

Q10

&buf[pos]. (Or, alternately, buf + pos.)

Q11

&f->cbuf[f->cpos].

Q12

min(f->csz - f->cpos, sz - pos).

Q13

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->cpos != f->csz) {
            size_t n = sz - pos;
            if (n > f->csz - f->cpos)
                n = f->csz - f->cpos;
            memcpy(&buf[pos], &f->cbuf[f->cpos], n);
            f->cpos += n;   // ****** Make sure you remembered these!
            pos += n;       // ******
        } else {
            // cache is invalid/empty
        }
    }
    return pos;
}

Q14

Refill it by calling read.

Q15

The -1 return value indicates an error. io61_read should return immediately. If any characters were read out of the cache, io61_read must return that number; if no characters were read yet, it should return -1.

(We’ll see later in the class that some -1 return values are not true errors, and the user should retry read, but this works for now.)

The 0 return value indicates end of file. io61_read should return however many characters it has read so far (which is pos; note that pos might be 0).

A positive return value indicates that characters were successfully read. io61_read should update f->csz appropriately.

Q16

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->cpos != f->csz) {
            size_t n = sz - pos;
            if (n > f->csz - f->cpos)
                n = f->csz - f->cpos;
            memcpy(&buf[pos], &f->cbuf[f->cpos], n);
            f->cpos += n;
            pos += n;
        } else {
            f->cpos = f->csz = 0;   // mark cache as empty
            ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
            if (n > 0)
                f->csz = n;
            else
                return pos ? pos : n;
        }
    }
    return pos;
}

Part 3

Q17

The most recent call to read returned f->csz characters, and left the file pointer at the next character (the one immediately following the f->csz characters in the cache). Thus:

assert(fd_file_pointer == f->tag + f->csz);

Q18

assert(f->end_tag >= f->tag);
assert(f->pos_tag >= f->tag && f->pos_tag <= f->end_tag);
assert(fd_file_pointer == f->end_tag);

Q19

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->cpos != f->csz) {
            size_t n = sz - pos;
            if (n > f->csz - f->cpos)
                n = f->csz - f->cpos;
            memcpy(&buf[pos], &f->cbuf[f->cpos], n);
            f->cpos += n;
            pos += n;
        } else {
            f->tag += f->csz;       // ******
            f->cpos = f->csz = 0;   // mark cache as empty
            ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
            if (n > 0)
                f->csz = n;
            else
                return pos ? pos : n;
        }
    }
    return pos;
}

Q20

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->pos_tag != f->end_tag) {
            ssize_t n = sz - pos;
            if (n > f->end_tag - f->pos_tag)
                n = f->end_tag - f->pos_tag;
            memcpy(&buf[pos], &f->cbuf[f->pos_tag - f->tag], n);
            f->pos_tag += n;
            pos += n;
        } else {
            f->tag = f->end_tag;
            ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
            if (n > 0)
                f->end_tag += n;
            else
                return pos ? pos : n;
        }
    }
    return pos;
}

Q21

cpos, because that represents the next character in the cache to read.

Q22

pos_tag.

Q23

int io61_seek(io61_file* f, off_t off) {
    if (off >= f->tag && off <= f->tag + f->csz) {
        f->cpos = off - f->tag;
        return 0;
    } else {
        off_t r = lseek(f->fd, off, SEEK_SET);
        if (r == off) {
            f->cpos = f->csz = 0;
            f->tag = off;
            return 0;
        } else
            return -1;
    }
}

Or, more compactly:

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

Q24

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;
}

Q25

Consider reading data in reverse sequential order, e.g., offsets 1024, 1023, 1022, …. We will first seek to position 1024 and read the BUFSIZ bytes starting at that position. Then we seek to position 1023; but this position is not within the range [1024, 1024+BUFSIZ), so we mark the cache as invalid, and the next read will read BUFSIZ more bytes. And so forth.

Q26

We found it easiest to write this by relaxing the assertion relating f->pos_tag with the other tags. Specifically, we allow f->pos_tag to point to a character that isn’t valid—yet. The next call to io61_read will fix that up. Our new invariant is:

assert(f->pos_tag >= f->tag && f->pos_tag <= f->tag + BUFSIZ);

And the code: (There’s just a tiny change to io61_read.)

int io61_seek(io61_file* f, off_t off) {
    if (off >= f->tag && off <= f->end_tag) {
        f->pos_tag = off;
        return 0;
    } else {
        off_t aligned_off = off - (off % BUFSIZ);      // ******
        off_t r = lseek(f->fd, aligned_off, SEEK_SET); // ******
        if (r == aligned_off) {                        // ******
            f->tag = f->end_tag = aligned_off;         // ******
            f->pos_tag = off;                          // ******
            return 0;
        } else
            return -1;
    }
}

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    size_t pos = 0;   // number of characters read so far
    while (pos != sz) {
        if (f->pos_tag < f->end_tag) {   // ****** Note: Not != any more!!!!
            ssize_t n = sz - pos;
            if (n > f->end_tag - f->pos_tag)
                n = f->end_tag - f->pos_tag;
            memcpy(&buf[pos], &f->cbuf[f->pos_tag - f->tag], n);
            f->pos_tag += n;
            pos += n;
        } else {
            f->tag = f->end_tag;
            ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
            if (n > 0)
                f->end_tag += n;
            else
                return pos ? pos : n;
        }
    }
    return pos;
}

The more compact version of io61_seek:

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