Files, pipes, the console and the UART

1warm-upChoose one

wc calls read(0, buf, 512). Inside the kernel, fileread must decide whether this read goes to a pipe, the console driver or a file on disk. What does it look at?

kernel/file.c

104// Read from file f.
105// addr is a user virtual address.
106int
107fileread(struct file *f, uint64 addr, int n)
108{
109  int r = 0;
110
111  if (f->readable == 0 || n < 0)
112    return -1;
113
114  if (f->type == FD_PIPE) {
115    r = piperead(f->pipe, addr, n);
116  } else if (f->type == FD_DEVICE) {
117    if (f->major < 0 || f->major >= NDEV || !devsw[f->major].read)
118      return -1;
119    r = devsw[f->major].read(1, addr, n);
120  } else if (f->type == FD_INODE) {
121    ilock(f->ip);
122    if ((r = readi(f->ip, 1, addr, f->off, n)) > 0)
123      f->off += r;
124    iunlock(f->ip);
125  } else {
126    panic("fileread");
127  }
128
129  return r;
130}

Whether the user buffer address is in the kernel or user half of memoryThe type field of the struct file that descriptor 0 points toThe name of the program that opened the fileThe descriptor number: 0 always means the console

2warm-upType a number

A process creates a pipe and writes to it, and nobody ever reads. How many bytes can it write into the empty pipe before pipewrite puts it to sleep?

kernel/pipe.c

11#define PIPESIZE 512
12
13struct pipe {
14  struct spinlock lock;
15  char data[PIPESIZE];
16  uint nread;    // number of bytes read
17  uint nwrite;   // number of bytes written
18  int readopen;  // read fd is still open
19  int writeopen; // write fd is still open
20};

decimal, 0x hex or 0b binary

3warm-upTrue or false, and why

True or false: after kfork, the parent and the child each have their own struct file for the console, so the child moving a file offset or closing its copy cannot affect the parent’s.

TrueFalse

Why?

fork copies only the pointers in ofile[] and calls filedup on each, so both processes share one struct file whose ref goes up by one.fork never copies descriptors at all; the child must reopen the console.The console is the only exception: device files are shared, but every regular file gets a fresh copy at fork.

4warm-upChoose one

wc is reading from a pipe. The pipe is empty, and the last write end has been closed (writeopen == 0). What does piperead do?

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}
for (i = 0; i < n; i++) { //DOC: piperead-copy
  if (pi->nread == pi->nwrite)
    break;
  ch = pi->data[pi->nread % PIPESIZE];
  if (copyout(pr->pagetable, pr->sz, addr + i, &ch, 1) == -1) {
    if (i == 0)
      i = -1;
    break;
  }
  pi->nread++;
}
wakeup(&pi->nwrite); //DOC: piperead-wakeup
release(&pi->lock);
return i;
143}

Returns 0 at once; wc treats that as end of fileReturns -1, because reading a closed pipe is an errorPanics, because the pipe page has already been freedSleeps on &pi->nread until a writer appears

5warm-upClick the line

In piperead, click the line that checks whether any writer is still left on the pipe.

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}
for (i = 0; i < n; i++) { //DOC: piperead-copy
  if (pi->nread == pi->nwrite)
    break;
  ch = pi->data[pi->nread % PIPESIZE];
  if (copyout(pr->pagetable, pr->sz, addr + i, &ch, 1) == -1) {
    if (i == 0)
      i = -1;
    break;
  }
  pi->nread++;
}
wakeup(&pi->nwrite); //DOC: piperead-wakeup
release(&pi->lock);
return i;
143}

Your pick: none yet (click a line in the code)

6warm-upMatch the pairs

consoleintr treats some typed characters specially. Match each key with what the kernel does when it arrives.

kernel/console.c

146void
147consoleintr(int c)
148{
acquire(&cons.lock);
150
switch (c) {
case C('P'): // Print process list.
  procdump();
  break;
case C('U'): // Kill line.
  while (cons.e != cons.w &&
         cons.buf[(cons.e - 1) % INPUT_BUF_SIZE] != '\n') {
    cons.e--;
    consputc(BACKSPACE);
  }
  break;
case C('H'): // Backspace
case '\x7f': // Delete key
  if (cons.e != cons.w) {
    cons.e--;
    consputc(BACKSPACE);
  }
  break;
default:
  if (c != 0 && cons.e - cons.r < INPUT_BUF_SIZE) {
    c = (c == '\r') ? '\n' : c;
172
    // echo back to the user.
    consputc(c);
175
    // store for consumption by consoleread().
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
178
    if (c == '\n' || c == C('D') || cons.e - cons.r == INPUT_BUF_SIZE) {
      // wake up consoleread() if a whole line (or end-of-file)
      // has arrived.
      cons.w = cons.e;
      wakeup(&cons.r);
    }
  }
  break;
}
188
release(&cons.lock);
190}

Control-H or DeleteControl-UControl-DControl-PEnter (the terminal sends \r)

7warm-upChoose one

When you type a key, consoleintr echoes it with consputc, which calls uartputc_sync and spins on the UART. Why does it not send the echo through uartwrite, like a process’s write does?

kernel/console.c

28//
29// send one character to the uart, but don't use
30// interrupts or sleep(). safe to be called from
31// interrupts, e.g. by printk and to echo input
32// characters.
33//
34void
35consputc(int c)
36{
37  if (c == BACKSPACE) {
38    // if the user typed backspace, overwrite with a space.
39    uartputc_sync('\b');
40    uartputc_sync(' ');
41    uartputc_sync('\b');
42  } else {
43    uartputc_sync(c);
44  }
45}

consoleintr runs in an interrupt handler holding cons.lock, and uartwrite may sleep; sleeping there is forbiddenuartwrite only accepts user addresses, and the echoed character is in the kerneluartwrite can only run on hart 0Echoes must be faster, and uartwrite buffers bytes in a ring buffer that is drained later

8warm-upChoose all that apply

A process with only descriptors 0, 1 and 2 open calls pipe(p), which succeeds. Which statements are true right afterwards?

kernel/pipe.c

22int
23pipealloc(struct file **f0, struct file **f1)
24{
struct pipe *pi;
26
pi = 0;
*f0 = *f1 = 0;
if ((*f0 = filealloc()) == 0 || (*f1 = filealloc()) == 0)
  goto bad;
if ((pi = (struct pipe *)kalloc()) == 0)
  goto bad;
pi->readopen = 1;
pi->writeopen = 1;
pi->nwrite = 0;
pi->nread = 0;
initlock(&pi->lock, "pipe");
(*f0)->type = FD_PIPE;
(*f0)->readable = 1;
(*f0)->writable = 0;
(*f0)->pipe = pi;
(*f1)->type = FD_PIPE;
(*f1)->readable = 0;
(*f1)->writable = 1;
(*f1)->pipe = pi;
return 0;

Both struct files point to the same struct pipep[0] is 3 and p[1] is 4read(p[1], ...) returns -1The 512-byte buffer is inside one of the two struct filesEach end has its own spinlock, so a reader and a writer never contend

9solidType a number

cat makes one write(1, buf, 512) to the console. How many times does consolewrite call uartwrite for it?

kernel/console.c

58//
59// user write() system calls to the console go here.
60// uses sleep() and UART interrupts.
61//
62int
63consolewrite(int user_src, uint64 src, int n)
64{
65  char buf[32]; // move batches from user space to uart.
66  int i = 0;
67
68  while (i < n) {
69    int nn = sizeof(buf);
70    if (nn > n - i)
71      nn = n - i;
72    if (either_copyin(buf, user_src, src + i, nn) == -1)
73      break;
74    uartwrite(buf, nn);
75    i += nn;
76  }
77
78  return i;
79}

decimal, 0x hex or 0b binary

10solidChoose one

When the last reference to a file goes away, fileclose copies *f into the local ff, frees the slot and releases ftable.lock, and only then calls pipeclose or iput. Why not do the cleanup while still holding ftable.lock?

kernel/file.c

58// Close file f.  (Decrement ref count, close when reaches 0.)
59void
60fileclose(struct file *f)
61{
struct file ff;
63
acquire(&ftable.lock);
if (f->ref < 1)
  panic("fileclose");
if (--f->ref > 0) {
  release(&ftable.lock);
  return;
}
ff = *f;
f->ref = 0;
f->type = FD_NONE;
release(&ftable.lock);
75
if (ff.type == FD_PIPE) {
  pipeclose(ff.pipe, ff.writable);
} else if (ff.type == FD_INODE || ff.type == FD_DEVICE) {
  begin_op();
  iput(ff.ip);
  end_op();
}
83}

To let other harts read the file’s data while it is being closedBecause pipeclose and iput take ftable.lock themselves, and acquiring it twice would panicThe cleanup can sleep (iput inside a log transaction may wait for the disk), and a spinlock must not be held while sleepingThe copy is only an optimization; doing the cleanup under the lock would also be correct

11solidPut in order

In ls | wc, wc is asleep in piperead on an empty pipe. ls has written all its output and now exits. Put the events that end wc’s reading in order.

pipeclose sets writeopen = 0 and calls wakeup(&pi->nread)
wc returns from sleep, retakes pi->lock and re-checks the loop condition on line 119
The copy loop breaks at once with i = 0, and read returns 0 to wc
wc’s read loop ends and it prints its counts
ls calls exit(0); kexit starts closing its open descriptors
fileclose drops the write end’s ref to 0 and frees the ftable slot

12solidChoose one

nread and nwrite are never reset; they only count up, and positions are found with % PIPESIZE. What does this design buy compared with two indices that wrap back to 0 at 512?

kernel/pipe.c

11#define PIPESIZE 512
12
13struct pipe {
14  struct spinlock lock;
15  char data[PIPESIZE];
16  uint nread;    // number of bytes read
17  uint nwrite;   // number of bytes written
18  int readopen;  // read fd is still open
19  int writeopen; // write fd is still open
20};

They let the pipe hold more than 512 bytes once the counters growThey make the pipe lock unnecessary, because counters can be updated atomicallyFull and empty become different tests (nwrite == nread + 512 vs nread == nwrite) without wasting a slot or adding a flagThey avoid overflow, because a 32-bit counter can never wrap in practice

13solidTrue or false, and why

True or false: pipewrite calls copyin while holding the spinlock pi->lock, and this is safe in this kernel.

kernel/pipe.c

76int
77pipewrite(struct pipe *pi, uint64 addr, int n)
78{
int i = 0;
struct proc *pr = myproc();
81
acquire(&pi->lock);
while (i < n) {
  if (pi->readopen == 0 || killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  if (pi->nwrite == pi->nread + PIPESIZE) { //DOC: pipewrite-full
    wakeup(&pi->nread);
    sleep_prepare(&pi->nwrite);
    release(&pi->lock);
    sleep();
    acquire(&pi->lock);
  } else {
    char ch;
    if (copyin(pr->pagetable, pr->sz, &ch, addr + i, 1) == -1) {
      if (i == 0)
        i = -1;
      break;
    }
    pi->data[pi->nwrite++ % PIPESIZE] = ch;
    i++;
  }
}
wakeup(&pi->nread);
release(&pi->lock);
107
return i;
109}

TrueFalse

Why?

It is safe because a user page fault inside copyin is handled by usertrap, which sleeps until the page is loaded.It is safe because copyin turns interrupts back on while it copies.copyin never sleeps: it walks the page table and, at worst, allocates a zeroed page with kalloc, which only spins briefly on kmem.lock.

14solidChoose one

cat with no arguments is in read(0, buf, 512) on the console. You type h, i, then Control-D (no Enter). What does that read return?

kernel/console.c

87int
88consoleread(int user_dst, uint64 dst, int n)
89{
uint target;
int c;
char cbuf;
93
target = n;
acquire(&cons.lock);
while (n > 0) {
  // wait until interrupt handler has put some
  // input into cons.buffer.
  while (cons.r == cons.w) {
    if (killed(myproc())) {
      release(&cons.lock);
      return -1;
    }
    sleep_prepare(&cons.r);
    release(&cons.lock);
    sleep();
    acquire(&cons.lock);
  }
109
  c = cons.buf[cons.r++ % INPUT_BUF_SIZE];
111
  if (c == C('D')) { // end-of-file
    if (n < target) {
      // Save ^D for next time, to make sure
      // caller gets a 0-byte result.
      cons.r--;
    }
    break;
  }
120
  // copy the input byte to the user-space buffer.
  cbuf = c;
  if (either_copyout(user_dst, dst, &cbuf, 1) == -1)
    break;
125
  dst++;
  --n;
128
  if (c == '\n') {
    // a whole line has arrived, return to
    // the user-level read().
    break;
  }
}
release(&cons.lock);
136
return target - n;
138}

Nothing yet: read keeps waiting until you press Enter0: Control-D means end of file2: the bytes hi; the Control-D is left in the buffer for the next read3: the bytes h, i and the Control-D character

15solidFill in the machine state

Hart 2 is idle in its scheduler (between intr_on and intr_off) when a UART interrupt arrives. uartintr calls consoleintr, which takes cons.lock and echoes the key. Hart 2 is now inside uartputc_sync, just after its push_off(). What is its state?

kernel/uart.c

98// write a byte to the uart without using
99// interrupts, for use by kernel printk() and
100// to echo characters. it spins waiting for the uart's
101// output register to be empty.
102void
103uartputc_sync(int c)
104{
105  if (panicking == 0)
106    push_off();
107
108  if (panicked) {
109    for (;;)
110      ;
111  }
112
113  // wait for UART to set Transmit Holding Empty in LSR.
114  while ((ReadReg(LSR) & LSR_TX_IDLE) == 0)
115    ;
116  WriteReg(THR, c);
117
118  if (panicking == 0)
119    pop_off();
120}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

16solidChoose one

uartwrite serializes writers with tx_lock, a sleep-lock. Why would an ordinary spinlock not work here?

kernel/uart.c

76// transmit buf[] to the uart. it blocks if the
77// uart is busy, so it cannot be called from
78// interrupts, only from write() system calls.
79void
80uartwrite(char buf[], int n)
81{
82  acquiresleep(&tx_lock);
83
84  int i = 0;
85  while (i < n) {
86    sleep_prepare(&tx_chan);
87    if (ReadReg(LSR) & LSR_TX_IDLE) {
88      WriteReg(THR, buf[i]);
89      i += 1;
90    } else {
91      sleep();
92    }
93  }
94
95  releasesleep(&tx_lock);
96}

The holder may call sleep() in the middle of a batch, waiting for the transmitter, and nobody may sleep holding a spinlockInterrupt handlers also take tx_lock, and they need it to be a sleep-lockA sleep-lock is faster when there is no contentionSpinlocks cannot protect memory-mapped device registers

17solidClick the line

Three harts call printk at the same moment. Click the line that keeps their messages from interleaving character by character.

kernel/printk.c

62// Print to the console.
63int
64printk(char *fmt, ...)
65{
66  va_list ap;
67  int i, cx, c0, c1, c2;
68  char *s;
69
70  if (panicking == 0)
71    acquire(&pr.lock);
72
73  va_start(ap, fmt);
74  for (i = 0; (cx = fmt[i] & 0xff) != 0; i++) {
75    if (cx != '%') {
76      consputc(cx);
77      continue;
78    }

Your pick: none yet (click a line in the code)

18solidDecode the bits

A program calls open("README", omode) with omode = 0x401. Using kernel/fcntl.h and sys_open, decode it and predict the result.

kernel/sysfile.c

if (ip->type == T_DEVICE) {
  f->type = FD_DEVICE;
  f->major = ip->major;
} else {
  f->type = FD_INODE;
  f->off = 0;
}
f->ip = ip;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
386
if ((omode & O_TRUNC) && ip->type == T_FILE) {
  itrunc(ip);
}

Value: 0x401

O_WRONLY (0x001)O_CREATE (0x200)O_TRUNC (0x400)f->readable after a successful openREADME is an existing 2441-byte regular file. Its size after the open

19solidChoose all that apply

A process’s write to the console goes consolewrite → uartwrite. Which of these can happen on that path in this kernel?

kernel/uart.c

76// transmit buf[] to the uart. it blocks if the
77// uart is busy, so it cannot be called from
78// interrupts, only from write() system calls.
79void
80uartwrite(char buf[], int n)
81{
82  acquiresleep(&tx_lock);
83
84  int i = 0;
85  while (i < n) {
86    sleep_prepare(&tx_chan);
87    if (ReadReg(LSR) & LSR_TX_IDLE) {
88      WriteReg(THR, buf[i]);
89      i += 1;
90    } else {
91      sleep();
92    }
93  }
94
95  releasesleep(&tx_lock);
96}

The process sleeps on &tx_chan until the UART’s transmit interruptThe bytes are queued in a transmit ring buffer that the interrupt handler drains laterThe process sleeps waiting for another process to release tx_lockThe process takes cons.lock for the whole writeThe bytes are copied from user memory into a 32-byte buffer on the kernel stack

20deepType a number

A long program runs that never reads the console, so nobody calls consoleread. Before it started, the console input buffer was empty (r == w == e). You now type 200 ordinary letters without pressing Enter. How many of them are echoed on the screen?

kernel/console.c

default:
  if (c != 0 && cons.e - cons.r < INPUT_BUF_SIZE) {
    c = (c == '\r') ? '\n' : c;
172
    // echo back to the user.
    consputc(c);
175
    // store for consumption by consoleread().
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
178
    if (c == '\n' || c == C('D') || cons.e - cons.r == INPUT_BUF_SIZE) {
      // wake up consoleread() if a whole line (or end-of-file)
      // has arrived.
      cons.w = cons.e;
      wakeup(&cons.r);
    }
  }
  break;

decimal, 0x hex or 0b binary

21deepChoose all that apply

On hart 0, cat is in uartwrite holding tx_lock, halfway through a 32-byte batch. On harts 1 and 2 other things are happening. Which of these can put bytes on the screen between two bytes of cat’s batch?

The echo of a key you type, handled on hart 2Another process’s write(1, buf, 32) on hart 2wc on hart 1 calling printf (one write per character)A kernel message printed with printk on hart 1

22deepTrue or false, and why

True or false: uartwrite calls sleep_prepare without holding any spinlock, so if the transmit-done interrupt arrives between the LSR check on line 87 and the sleep on line 91, the wakeup is lost and the process can sleep forever.

kernel/uart.c

79void
80uartwrite(char buf[], int n)
81{
82  acquiresleep(&tx_lock);
83
84  int i = 0;
85  while (i < n) {
86    sleep_prepare(&tx_chan);
87    if (ReadReg(LSR) & LSR_TX_IDLE) {
88      WriteReg(THR, buf[i]);
89      i += 1;
90    } else {
91      sleep();
92    }
93  }
94
95  releasesleep(&tx_lock);
96}

TrueFalse

Why?

It is safe because interrupts are off between line 86 and line 91.It is safe because the UART raises its interrupt again every few microseconds until someone writes THR.sleep_prepare already set p->chan; the interrupt’s wakeup(&tx_chan) clears it, and sleep() sees p->chan == 0 and returns without sleeping.

23deepType a number

A program calls write(fd, buf, 10000) on a regular file, and every writei succeeds. How many file-system transactions (begin_op … end_op pairs) does filewrite run? (MAXOPBLOCKS is 10, BSIZE is 1024.)

kernel/file.c

} else if (f->type == FD_INODE) {
  // write a few blocks at a time to avoid exceeding
  // the maximum log transaction size, including
  // i-node, indirect block, allocation blocks,
  // and 2 blocks of slop for non-aligned writes.
  int max = ((MAXOPBLOCKS - 1 - 1 - 2) / 2) * BSIZE;
  int i = 0;
  while (i < n) {
    int n1 = n - i;
    if (n1 > max)
      n1 = max;
159
    begin_op();
    ilock(f->ip);
    if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
      f->off += r;
    iunlock(f->ip);
    end_op();
166
    if (r != n1) {
      // error from writei
      break;
    }
    i += r;
  }
  ret = (i == n ? n : -1);

decimal, 0x hex or 0b binary

24deepChoose one

Continue from cat reading h, i, Control-D: the first read returned 2. cat writes hi and calls read(0, buf, 512) again. Why does this second read return 0 immediately instead of sleeping?

kernel/console.c

87int
88consoleread(int user_dst, uint64 dst, int n)
89{
uint target;
int c;
char cbuf;
93
target = n;
acquire(&cons.lock);
while (n > 0) {
  // wait until interrupt handler has put some
  // input into cons.buffer.
  while (cons.r == cons.w) {
    if (killed(myproc())) {
      release(&cons.lock);
      return -1;
    }
    sleep_prepare(&cons.r);
    release(&cons.lock);
    sleep();
    acquire(&cons.lock);
  }
109
  c = cons.buf[cons.r++ % INPUT_BUF_SIZE];
111
  if (c == C('D')) { // end-of-file
    if (n < target) {
      // Save ^D for next time, to make sure
      // caller gets a 0-byte result.
      cons.r--;
    }
    break;
  }
120
  // copy the input byte to the user-space buffer.
  cbuf = c;
  if (either_copyout(user_dst, dst, &cbuf, 1) == -1)
    break;
125
  dst++;
  --n;
128
  if (c == '\n') {
    // a whole line has arrived, return to
    // the user-level read().
    break;
  }
}
release(&cons.lock);
136
return target - n;
138}

Line 116 left the Control-D in the buffer; the second read finds it as its first character (n == target), so it does not put it back and returns 0consoleread remembers in a flag that end of file was reachedfileread returns 0 for any device once a read returned less than requestedThe second read sleeps, and Control-D’s wakeup returns it with 0

25deepChoose one

When both ends of a pipe are closed, pipeclose runs release(&pi->lock) on line 70 and only then kfree((char *)pi) on line 71. What would go wrong if the two lines were swapped?

kernel/pipe.c

58void
59pipeclose(struct pipe *pi, int writable)
60{
acquire(&pi->lock);
if (writable) {
  pi->writeopen = 0;
  wakeup(&pi->nread);
} else {
  pi->readopen = 0;
  wakeup(&pi->nwrite);
}
if (pi->readopen == 0 && pi->writeopen == 0) {
  release(&pi->lock);
  kfree((char *)pi);
} else
  release(&pi->lock);
74}

The lock lives inside the page being freed; release would act on memory that kfree has already filled with junk and handed back for reuseNothing: kfree never touches the contents of the pagekfree takes pi->lock itself, so it would deadlockAnother process might still be asleep on the pipe and would miss its wakeup