Lab 2

Part 2

1

Admin

• Lab 2 Part 1 due TOMORROW (@11:59pm, one day grace)
• Note we won’t be grading the Gradescope questions until the part 2 due date. (so you have a bit more time there :-))

​

• Part 2 Design Doc due 10/28, next Wednesday (@11:59pm, no grace period)
• Code + Gradescope questions due 11/4 (one day grace)

​

• Pset 2 due 10/28, next Wednesday(@11:59pm, one day grace)

​

2

Admin

• Midterm is coming!! 11/6, during lecture
• Note ALL of lab 2 is fair game, plan accordingly

​

• Updates to grading policy:
• For PSets AND lab questions: 24-hour grace period ONLY, anything after the grace period will not be accepted for credit
• The lab code and design docs follow the same policy as before
• Design docs: No grace period
• Lab code: 24-hour grace period + 1% deduction per day after the grace period

3

Monitors

4

What’s a monitor?

• A monitor is made up of a lock and at least one condition variable

​

Why do we use monitors?

​

5

What the heck is a monitor?

• A monitor is made up of a lock and at least one condition variable

​

Why do we use monitors?

• Similar to locks but…
• Allow processes to wait for certain conditions to become true while “holding lock” (waiter atomically releases the lock and reacquires the lock on wakeup).

​

6

Monitors in xk

• Lock
• xk condition variable API only supports spinlock (an impl. choice)
• Condition
• the shared data that threads are synchronizing on
• E.g. for wait/exit this would be child's state
• Condition Variable
• the waiter list is tracked by the process table
• proc in SLEEPING state with the same chan are part of the same CV
• chan is a pointer, can be anything (think of it as a cv identifier)

7

No Condition Variables in xk

The starter code does not provide the object-oriented std::condition_variable API you can find in C++: LINK

Instead it provides the sleep and wakeup helper functions (which together can implement the monitor pattern)

• sleep ~= wait
• wakeup ~= broadcast

8

Sleep

• sleep(void* chan, struct spinlock* lk)
• atomically release your current lock and grabs the process table (ptable) lock
• if your current lock is the ptable lock do nothing
• why might your current lock be the ptable lock?
• sets myproc()->state to SLEEPING
• sets myproc()->chan to whatever channel we are waiting on
• yields so that scheduler can run another process

9

Wakeup

• wakeup(void* chan)
• acquires the process table lock
• looks for all SLEEPING processes with the given channel (chan)
• sets each proc->state to RUNNABLE (ready)
• proc->chan is also cleared to NULL

​

10

Monitors in xk

• You will use monitors to implement wait(), exit(), and pipe() for lab2!

​

wait(), exit()

• Coordinating children and parent processes

pipe()

• Coordinating reader and writer processes

​

​

​

11

Lab 2 - Pipe

12

What is a Pipe?

A pipe is essentially a queue of bytes with two ends:

• One end designated for input, the other for output

When you type ‘ls | wc’ into the shell, you are using a pipe!!!

• ‘ls’ lists the directory contents
• ‘wc’ counts the number of lines output from the ls command
• The pipe joins the output from ‘ls’ to the input of ‘wc’

13

pipe(fds)

• Creates a pipe (kernel buffer) that can be read from/written to.
• From the user perspective: returns two new file descriptors
• fds[0] = “read end”, O_RDONLY
• fds[1] = “write end”, O_WRONLY
• Pipes allow processes to communicate with each other
• Parent opens a pipe, forks a child (now they both have access to the pipe ends)
• Typically each process only leaves one end open (closes the read end or the write end)

14

An Example to Illustrate Pipes

Now let’s go through a demonstration of what happens as a sample user uses the pipe API (in the context of multiprocessing)!

​

15

Pipe usage

• Process 1 starts with no open files

16

Pipe usage

• Process 1 calls pipe()

17

18

File Struct

(Read only)

File Struct

(Write only)

Pipe

What will the newly allocated pipe fds point to?

Pipe usage

19

Process 1’s File Descriptor Array

0

1

2

3

PROC_MAX_FILE

struct proc

read end

Process 2’s File Descriptor Array

0

1

2

3

PROC_MAX_FILE

struct proc

• Process 1 calls fork(), fd table is duplicated

​

write end

read end

write end

• Note: fork() is called by user and should not be called within the actual pipe() call

pipe in user’s shell

• In user/sh.c, when runcmd detects a pipe command
• Fork two processes, one running left command, one running right command
• Still want to keep the parent process running our shell
• The left process should have output (stdout) redirected to the pipe’s write end -> close stdout and dup the write end file descriptor
• Any subsequent printf(stdout, …) or write(stdout, …) will write to pipe write end
• The right process should have input (stdin) redirected to the pipe’s read end -> close stdin and dup the read end file descriptor

20

Pipe usage

• Process 1 close(1), process 2 close(0)
• The process with the write end open is a writer, and the one with the read end open is a reader

21

Process 1’s File Descriptor Array

0

1

2

3

PROC_MAX_FILE

struct proc

Process 2’s File Descriptor Array

0

1

2

3

struct proc

PROC_MAX_FILE

Abstraction of a pipe

write end

read end

pipe FAQs

• When should pipe be allocated?
• dynamically! when pipe() is called!
• How does xk do dynamic memory allocation?
• hint: kstack is also dynamically allocated
• `kalloc` allocates a page (4096 bytes) of memory from the kernel heap
• wait, but how do I put a pipe onto the page?

22

struct pipe* p = kalloc();

p->buffer = ???

should be right past the struct, and what would that be?

23

a page of memory (4096 bytes)

struct pipe {

metadata…

char* buffer;

}

actual buffer

pipe FAQs

• When can you free the pipe and its buffer?
• remember there may be multiple references to read end and write end
• Can we always write to or read from the buffer? (Hint: bounded buffer sync)
• What if there's no room to write, or no data to read?
• What happens if all read/write ends are closed?
• How will pipes integrate with the file syscalls?
• Need a way to determine if a struct file is an inode or a pipe

24

Interaction with File API

Pipes are accessed through file descriptors.

This means you need to think through how the lab 1 syscalls will work when called on pipe file descriptors:

25

• read
• write
• stat

​

• close
• dup

What should pipe contain?

• What metadata/information do you need for pipe?

​

​

​

​

​

26

What should pipe contain?

• What metadata/information do you need for pipe?
• Read offset
• Write offset
• # of bytes available in the buffer
• Whether the read end is still open
• Whether the write end is still open
• Lock and condition variables
• A way to track the active writer [ why? ]
• Similar to the bounded buffer problem

27

28

And that’s pipe!

… But wait! There’s more! (that you have to do in lab 2 part 2)

But wait! …. There’s more! (in lab 2 part 2)

In lab 2 part 2 you are also implementing exec

29

Lab 2 - exec

30

Motivation

Why do we have exec?

• To let user code execute user programs!
• E.g. Shell commands like ‘ls’ and ‘cat’ commands are exec’ed by the ‘sh’ program.

31

exec(program, args)

• Fully replaces the current program; it does not create a new process
• How do we replace the current program?
• need to set up a new virtual address space and new registers states
• and then switch to using the new VAS and register states
• file descriptors and pid remain the same

​

​

32

exec(path, argv) arguments validation

33

must be validated for an 8 byte pointer before we can access argv[0] and validate string0

argv / &argv[0]

exec(path, argv) arguments validation

34

must be validated for an 8 byte pointer before we can access argv[1] and validate string1

&argv[1]

exec(path, argv) arguments validation

35

must be validated for an 8 byte pointer before we can access argv[2] and validate string2

&argv[2]

repeat this process until

• a NULL entry is reached
• a validation error

exec(program, args)

• Setting up a new virtual address space (pseudocode)
• vspaceinit for initialization
• vspaceloadcode to load code
• vspaceinitstack to allocate stack vregion
• you still need to populate user stack with arguments
• vspacewritetova to write data into the stack of the new VAS
• vspaceupdate to build new page-table mappings
• vspaceinstall to swap in the new vspace
• vspacefree to release the old vspace
• The swapover to the new vspace can be tricky to get right!
• To swap: Assign the new vspace to current vspace

36

How are the args set up in exec?

37

Another look at main()

exec sets up the function arguments for main!

int main(int argc, char** argv)

• argc: The number of elements in argv
• argv: An array of strings representing program arguments� - First is always the name of the program� - Argv[argc] = 0

38

Setting up the Stack

39

Quick Review: X86_64 Calling Conventions

From 351:

• %rdi: holds the first argument
• %rsi: holds the second argument
• %rdx, %rcx, %r8, %r9 comes next
• overflows (arg7, arg8 …) onto the stack
• %rsp: points to the top of the stack (lowest address)

40

Quick Review: X86_64 Calling Conventions

From 351:

• Local variables are stored on the stack
• If an array is an argument, the array contents are stored on the stack and the register contains a pointer to the array’s beginning

41

Stack For User Process

42

argc

%RDI

argv

%RSI

*

%RSP

Return PC

argv[0]

argv[1]

[ … ]

argv[argc - 1]

argv[argc] = NULL

Arg #0 string

Arg #1 string

[ … ]

Arg #(argc-1)string

// High addresses

// Stack grows

// down

• Since argv is an array of pointers, %RSI points to an array on the stack
• Since each element of argv is a char*, each element points to a string elsewhere on the stack
• Why? Alignment
• Why NULL pointer? Convention

SZ_2G

\0… (padding)

Let’s Practice!

43

Practice Exercise 1

44

%RDI

%RSI

%RSP

// High addresses

Now it’s your turn!

​

Draw stack layout and determine register values for exec() called with:

​

“cat cat.txt”

Stack grows down

Practice Exercise 1: “cat cat.txt” Solution

45

%RDI

%RSI

%RSP

// High addresses

// Stack grows

// down

Practice Exercise 1: “cat cat.txt” Solution

46

%RDI

%RSI

%RSP

“cat.txt”

// High addresses

// Stack grows

// down

Practice Exercise 1: “cat cat.txt” Solution

47

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

Practice Exercise 1: “cat cat.txt” Solution

48

2

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

Practice Exercise 1: “cat cat.txt” Solution

49

\0\0\0\0

2

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

Practice Exercise 1: “cat cat.txt” Solution

50

\0\0\0\0

NULL (argv[2])

2

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

Practice Exercise 1: “cat cat.txt” Solution

51

addr of "cat.txt" (argv[1])

\0\0\0\0

NULL (argv[2])

2

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

Practice Exercise 1: “cat cat.txt” Solution

52

addr of "cat" (argv[0])

addr of "cat.txt" (argv[1])

\0\0\0\0

NULL (argv[2])

2

%RDI

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

Practice Exercise 1: “cat cat.txt” Solution

53

addr of "cat" (argv[0])

addr of "cat.txt" (argv[1])

\0\0\0\0

NULL (argv[2])

2

%RDI

argv

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

• RSI holds argv: the beginning of the argv array

Practice Exercise 1: “cat cat.txt” Solution

54

Return PC

addr of "cat" (argv[0])

addr of "cat.txt" (argv[1])

\0\0\0\0

NULL (argv[2])

2

%RDI

argv

%RSI

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

• RSI holds argv: the beginning of the argv array

• The specific value of the return PC doesn’t matter (program exits from main without returning)

Practice Exercise 1: “cat cat.txt” Solution

55

Return PC

addr of "cat" (argv[0])

addr of "cat.txt" (argv[1])

\0\0\0\0

NULL (argv[2])

2

%RDI

argv

%RSI

stackptr

%RSP

“cat”

“cat.txt”

// High addresses

// Stack grows

// down

• RDI holds argc, which is 2

• RSI holds argv: the beginning of the argv array

• The specific value of the return PC doesn’t matter (program exits from main without returning)

• RSP is properly set to the bottom of the stack.

Practice Exercise 2

56

%RDI

%RSI

%RSP

// High addresses

Now it’s your turn!

​

Draw stack layout and determine register values for exec() called with:

​

“kill -9 500”

Stack grows down

Practice Exercise 2: “kill -9 500” Solution

57

3

%RDI

argv

%RSI

*

%RSP

• RDI holds argc, which is 3
• RSI holds argv: the beginning of the argv array
• RSP is properly set to the bottom of the stack.
• The specific value of the return PC doesn’t matter (program exits from main without returning)

Return PC

argv[0]

argv[1]

argv[2]

argv[3] = NULL

“kill”

“-9”

“500”

// High addresses

// Stack grows

// down

\0\0\0\0