NOTOC

Exercise IO Solutions

Q1

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

Q2

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

Q3

The cache is invalid/empty when f->csz == 0, but this is only partially correct. 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.

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.

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

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) {
            ssize_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;
}

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(FILE POINTER(f->fd) == f->tag + f->csz);

Q18

assert(f->end_tag >= f->tag);
assert(f->pos_tag >= f->tag && f->pos_tag <= f->end_tag);
assert(FILE POINTER(f->fd) == 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) {
            ssize_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) {
        f->pos_tag = off;
        return 0;
    } else {
        off_t r = lseek(f->fd, off, SEEK_SET);
        if (r == off) {
            f->tag = f->pos_tag = f->end_tag = r;
            return 0;
        } else
            return -1;
    }
}

Or, more compactly:

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

Unfortunately, no, because this code doesn’t align its accesses. We saw that speeding up reverse sequential I/O requires that the cache read data in aligned fashion from its remote storage. (Other policies work too, but alignment is easiest and most flexible.)

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