Show all solutions
Rules
The exam is open book, open note, open computer. You may access the book, and your own notes in paper form. You may also use a computer or equivalent to access your own class materials and public class materials. However, you may not access other materials except as explicitly allowed below. Specifically:
- You may access a browser and a PDF reader.
- You may access your own notes and problem set code electronically.
- You may access an internet site on which your own notes and problem set code are stored.
- You may access this year’s course site.
- You may access pages directly linked from the course site, including our lectures, exercises, and section notes, and our preparation materials for the midterm.
- You may run a C/C++ compiler, including an assembler and linker, or a calculator.
- You may use a Python interpreter.
- You may access manual pages.
But:
- You absolutely may not contact other humans via IM or anything like it.
- You may not access Piazza.
- You may not access Google or Wikipedia or anything else except as directly linked from the course site.
- You may not access solutions from any previous exam, by paper or computer, except for those on the course site.
Any violations of this policy, or the spirit of this policy, are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.
Completing your exam
Create a cs61-exams repository if you have not already. Then, before beginning the exam, merge your local cs61-exams repository with our handout:
$ git pull git://github.com/cs61/cs61-f19-exams.git master
You will enter your answers in the midterm/midterm.md
file. Do not place
your name in this file. (This enables us to grade all exams blindly.)
When you have completed the exam, edit the file midterm/policy.txt
to sign
your name. This is your promise that you have obeyed the exam rules in letter
and spirit.
Then commit your changes and push them to your repository on GitHub:
$ git commit -a -m "Midterm Exam Answers"
$ git push
If you get an error message that you do not have access to push to github.com/cs61/cs61-f19-exams.git, this means that you are trying to push to our repository. Instead, push explicitly to your own repository:
$ git push https://github.com/cs61/cs61-f19-exams-YOURGITHUBREPONAMEHERE master
Make sure that you have entered your exam repository URL on the grading server for the midterm exam.
Notes
Assume a Linux operating system running on the x86-64 architecture unless otherwise stated. If you get stuck, move on to the next question. If you’re confused, explain your thinking briefly for potential partial credit.
1. Bitwise (10 points)
QUESTION 1A. Assuming x
is an unsigned
value, simplify the following
expressions. Your answer in each case should be either a constant or an
expression that mentions x
only once.
x ^ x
x & x
x - x
x | x
x ^ ~x
x & ~x
x | ~x
x ^ x ^ x
(x | -x) + (x & -x)
5pts. 1-2 wrong -1; 3-4 wrong -2; 5-6 wrong -3; 7-8 wrong -4
- 0
x
- 0
x
- -1 or 0xFFFF'FFFF
- 0
- -1
x
- 0
Many programs manipulate arrays of boolean (true/false) values. A bitvector can compactly represent such arrays as an array of unsigned integers: The Nth boolean is stored in the Nth least significant bit of the array.
struct bitvector {
size_t size; // number of booleans
unsigned* v; // points to a dynamically-allocated array of unsigned integers;
// contains at least `size` valid bits
};
So, for example, bit 0 (the least significant bit) of bv.v[0]
holds the
index-0 boolean in the bitvector; bit 1 (the next-least-significant bit) of
bv.v[0]
holds the index-1 boolean; bit 2 of bv.v[0]
holds the index-2
boolean; and so forth, switching to later elements of bv.v
as required.
QUESTION 1B. Complete this function, which returns the value of the n
th
boolean in the bitvector. Do not assume x86-64 (so sizeof(unsigned)
might
not be 4), but you may assume that char
contains 8 bits (so unsigned
has a
multiple of 8 bits).
bool bitvector_test(bitvector* bv, size_t n) {
assert(n < bv->size);
}
3pts.
size_t ubits = sizeof(unsigned) * CHAR_BIT; return (bv->v[n / ubits] & (1U << (n % ubits))) != 0;
or
size_t ubits = sizeof(unsigned) * 8; return (bv->v[n / ubits] & (1U << (n % ubits))) != 0;
QUESTION 1C. Bitvectors can use any unsigned integer type for their
elements; unsigned char
, say:
struct bitvector_char {
size_t size; // number of booleans
unsigned char* v;
};
On some machines, the contents of the v
memory will not depend on element
type; for instance, whenever bitvector bv1
and bitvector_char bv2
represent the same boolean values in the same order, memcmp(bv1.v, bv2.v,
bv1.size / 8) == 0
(the v
arrays will be bytewise identical). What is the
common property of such machines?
2pts. They are little endian.
2. Undefined behavior (10 points)
QUESTION 2A. Complete main
so as to cause undefined behavior in
loopy1
, or explain briefly why that cannot be done.
void loopy1(int minval, int maxval) {
for (int i = minval; i != maxval; ++i) {
printf("%d\n", i);
}
}
int main() {
// *your code here*, including at least one call to `loopy1`
}
3pts.
loopy1(0, -1)
; this will cause signed overflow which is undefined
QUESTION 2B. Complete main
so as to cause undefined behavior in
loopy2
, or explain briefly why that cannot be done.
void loopy2(unsigned minval, unsigned maxval) {
for (unsigned i = minval; i != maxval; ++i) {
printf("%u\n", i);
}
}
int main() {
// *your code here*, including at least one call to `loopy2`
}
2pts. cannot be done: unsigned overflow is always defined, the loop will always terminate
QUESTION 2C. Complete main
to call loopy3
WITHOUT causing
undefined behavior, or explain briefly why that cannot be done. For full
credit loopy3
should print at least one line.
void loopy3(uintptr_t minval, uintptr_t maxval) {
for (uintptr_t i = minval; i != maxval; ++i) {
printf("%d\n", *(int*) i);
}
}
int main() {
// *your code here*, including at least one call to `loopy3`
}
3pts.
int x = 1; loopy3((uintptr_t) &x, (uintptr_t) &x + 1);
Note that we can't usesizeof
here!
QUESTION 2D. Valid C++ expressions involving 32-bit int
values produce
the same results as if the values were unsized mathematical integers. What’s
the best reason why? Pick one.
- 32-bit signed integer arithmetic is modulo 232.
- If the inputs to a mathematical expression fit in 32-bit
int
s, then the result of the mathematical expression always fits in a 32-bitint
. - Any program that causes undefined behavior, including signed integer overflow, must be rejected by the compiler.
- Any program that causes undefined behavior, including signed integer overflow, is not a valid C++ program.
- Thanks to a French-Canadian software engineer at Apple, the C++20 version of the C++ standard requires that signed integers use two’s complement representation.
2pts. 4. 1-3 are flat out false; 5 is true but irrelevant.
3. Memory layout (10 points)
QUESTION 3A. Which of these statements are true of Linux x86-64 stacks? List all that apply.
- Stacks contain objects with static lifetime.
- Stacks contain objects with automatic lifetime.
- Every stack frame has the same size.
- If function
f
calls functiong
, thenf
’s stack pointer has a larger value thang
’s stack pointer. - None of the above.
2pts. 2, 4
QUESTION 3B. Which of these statements are true of Linux x86-64 C++ structures? List all that apply or say “none”.
- The size of a structure might be larger than the sum of the sizes of its components.
- The alignment of a structure might be larger than the largest alignment of its components.
- All structures with size 7 have the same alignment.
- All structures with size 16 have the same alignment.
- None of the above.
2pts. 1, 3
QUESTION 3C. This function prints the addresses of three local objects:
void f() {
int x = ...;
int y = ...;
int z = ...;
printf("ax=%p ay=%p az=%p\n", &x, &y, &z);
}
Which statements are true about the printed addresses on any C++
implementation (not just Linux x86-64) with alignof(int) == 4
? List all that
apply.
ax != ay && ay != az && ax != az
ax < ay && ay < az
ay - ax >= sizeof(int) && az - ay >= sizeof(int) && az - ax >= sizeof(int)
ax % 4 == 0 && ay % 4 == 0 && az % 4 == 0
- None of the above
Hint: Remember that addresses and the size_t
type are unsigned.
4pts for C-E. 1-3 wrong -1; 4-6 wrong -2; 7-8 wrong -3
1, 3, 4
QUESTION 3D. What about three subobjects in a structure? Again, assume any
C++ implementation with alignof(int) == 4
.
struct point {
int x;
int y;
int z;
};
point p = ...;
void f() {
printf("ax=%p ay=%p az=%p\n", &p.x, &p.y, &p.z);
}
ax != ay && ay != az && ax != az
ax < ay && ay < az
ay - ax >= sizeof(int) && az - ay >= sizeof(int) && az - ax >= sizeof(int)
ax % 4 == 0 && ay % 4 == 0 && az % 4 == 0
- None of the above
1, 2, 3, 4
QUESTION 3E. What about three local objects in different functions? Again,
assume any C++ implementation with alignof(int) == 4
.
void f1() {
int x = ...;
printf("ax=%p ", &x);
}
void f2() {
int y = ...;
printf("ay=%p ", &y);
}
void f3() {
int z = ...;
printf("az=%p\n", &z);
}
void f() {
f1(); f2(); f3();
}
ax != ay && ay != az && ax != az
ax < ay && ay < az
ay - ax >= sizeof(int) && az - ay >= sizeof(int) && az - ax >= sizeof(int)
ax % 4 == 0 && ay % 4 == 0 && az % 4 == 0
- None of the above
4
QUESTION 3F. A C++ compiler on Linux x86-64 is laying out a structure with
two components, x
and y
, in that order. If nonzero padding is required
between x
and y
, which of these conditions might hold? List all that
apply.
sizeof(x) < sizeof(y)
alignof(x) < alignof(y)
sizeof(x) == sizeof(y)
alignof(x) == alignof(y)
sizeof(x) > sizeof(y)
alignof(x) > alignof(y)
- None of the above.
2pts. 1, 2, 3, 5
4. Vector representations (15 points)
A vector data structure is a dynamically-sized array. The C++ standard
library uses std::vector<T>
to represent vectors. The push_back
function adds an element to the end of the vector; the data
function returns
a pointer to the first element in the vector; and the size
function returns
the number of elements in the vector.
QUESTION 4A. Assume a function that declares a local variable
std::vector<int> v
. In which segment is the v
object located, stack, heap,
or data?
2pts. Only take 2 pts off between A-B if they get it switched.
Stack
QUESTION 4B. In which segment is the v.data()
array located, stack, heap,
or data?
2pts. Heap
The Linux C++ library’s vector representation uses three pointers, first
, last
,
and reserved
.
struct vector_T_representation {
T* first;
T* last;
T* reserved;
};
In this representation, first
points at the first element in the data array
and last
points one past the last element in the data array.
QUESTION 4C. Complete this function assuming this representation.
T* vector_T_data(vector_T_representation* v) {
// Return a pointer to the first element in the array.
}
2pts.
return v->first;
QUESTION 4D. Complete this function assuming this representation.
size_t vector_T_size(vector_T_representation* v) {
// Return the number of elements in the array.
}
2pts.
return v->last - v->first;
The reserved
pointer represents space reserved for future growth. A vector
with N elements uses a data array with space for up to M elements, where M≥N;
the vector can add up to (M−N) elements before reallocating the data array.
reserved
points one past the last element in the allocated space. It’s
always true that last >= first
and reserved >= last
.
QUESTION 4E. Complete this function, which allocates memory big enough to
hold an array of M
elements of type T
. Use malloc
to allocate memory.
Call abort
if the allocation fails or M
is too big.
T* vector_T_allocate(size_t M) {
// Allocate and return space for an array of M elements of type T; abort() on failure.
}
2pts.
if (M > SIZE_MAX / sizeof(T)) { abort(); } T* x = (T*) malloc(M * sizeof(T)); if (!x) { abort(); } return x;
This is the best solution. Unfortunately, simpler overflow checks, such as
M * sizeof(T) < M
, aren’t reliable. considerM == 0xA000'0000'0000'0000
andsizeof(T) == 0xE
.M * sizeof(T) == 0xC000'0000'0000'0000
, which is larger thanM
!
QUESTION 4F. Complete this function, which allocates a vector with initial
size 0 and reserved space for M
elements. Use vector_T_allocate
to
allocate memory.
void vector_T_initialize(vector_T_representation* v, size_t M) {
// Initialize `v` to an empty vector with reserved space for `M` elements.
}
2pts.
v->first = v->last = vector_T_allocate(M); v->reserved = v->first + M;
QUESTION 4G. Complete this implementation of push_back
. For substantial
partial credit, you may assert that there is enough reserved space for
new_element
.
void vector_T_push_back(vector_T_representation* v, T new_element) {
// Add a copy of `new_element` to the end of `v`.
}
3pts.
if (v->last == v->reserved) { size_t size = v->last - v->first; size_t new_size = size * 2; assert(new_size > size); T* x = vector_T_allocate(new_size); memcpy(x, v->first, sizeof(T) * size); free(v->first); v->first = x; v->last = x + size; v->reserved = x + new_size; } *v->last = new_element; ++v->last;
or
if (v->last == v->reserved) { size_t bytes = (uintptr_t) v->last - (uintptr_t) v->first; size_t new_bytes = bytes * 2; assert(new_bytes > bytes); T* x = (T*) malloc(new_bytes); memcpy(x, v->first, bytes); free(v->first); v->first = x; v->last = (T*) ((uintptr_t) x + bytes); v->reserved = (T*) ((uintptr_t) x + new_bytes); }
5. Allocation metadata (12 points)
These questions concern the metadata required to implement a Problem Set 1-style debugging memory allocator.
QUESTION 5A. True or false? The number of active allocations statistic
(nactive
) requires per-allocation metadata.
1pt. False
QUESTION 5B. List all the statistics in m61_statistics
(nactive
,
active_size
, ntotal
, total_size
, nfail
, fail_size
, heap_min
, and
heap_max
) that require per-allocation metadata to track. (“Per-allocation
metadata” refers to information associated with each individual allocation,
either via pointer arithmetic or via some external mapping like a hash table.)
2pts.
active_size
only. It is possible to maintain all the other statistics without metadata per allocation. For example,nactive
can be maintained with a single global variable that’s incremented inm61_malloc
and decremented inm61_free
.
QUESTION 5C. Some programming environments offer the following extension to the standard library:
size_t malloc_usable_size(void* ptr)
returns the number of allocated bytes in the block pointed to byptr
, which must be a non-null pointer to a block of memory allocated bymalloc
or a related function. The returned value might not equal the requested size passed tomalloc
because of alignment and other constraints.
Use malloc_usable_size
to amend the following m61_malloc
and m61_free
functions so that they maintain an estimate of the active_size
statistic
without additional per-allocation metadata.
unsigned long long active_size_estimate;
void* m61_malloc(size_t sz, const char* file, int line) {
void* ptr = malloc(sz);
// *your code will go here*
return ptr;
}
void m61_free(void* ptr, const char* file, int line) {
// *your code will go here*
free(ptr);
}
3pts.
// malloc if (ptr) { active_size_estimate += malloc_usable_size(ptr); } // free if (ptr) { active_size_estimate -= malloc_usable_size(ptr); }
QUESTION 5D. List all that apply for your implementation of 5C.
active_size_estimate
might equal the active size tracked by a full-credit Problem Set 1 debugging allocator.active_size_estimate
might be greater than the active size tracked by a full-credit Problem Set 1 debugging allocator.active_size_estimate
might be less than the active size tracked by a full-credit Problem Set 1 debugging allocator.
2pts. 1 and 2
Louise Bogan’s Problem Set 1 includes this code:
struct metadata { ... };
void* m61_malloc(size_t sz, ...) {
void* ptr = base_malloc(sz + sizeof(metadata));
if (ptr) {
metadata* m = (metadata*) ptr;
... initialize `*m` ...
ptr = (void*) ((uintptr_t) ptr + sizeof(metadata));
}
return ptr;
}
void m61_free(void* ptr, ...) {
if (ptr) {
metadata* m = (metadata*) ((uintptr_t) ptr - sizeof(metadata));
... validate `*m` ...
base_free(m);
}
}
QUESTION 5E. Give an example sz
for which Louise’s m61_malloc(sz)
will
misbehave, and name the reason for this misbehavior.
1pt.
(size_t) -1
; overflow
QUESTION 5F. Assuming that Louise’s implementation is otherwise correct, what
must be true about sizeof(metadata)
?
1pt. It is a multiple of 16 for alignment reasons
QUESTION 5G. Louise’s m61_free
initializes m
using a complex
expression. Which of the following expressions would have equivalent effect?
List all that apply.
(metadata*) (ptr - 1)
&((metadata*) ptr)[-1]
((metadata*) ptr) - 1
(metadata*) (((char*) ptr) - 1)
(metadata*) (((char*) ptr) - sizeof(metadata))
2pts. 2, 3, 5
6. Calling convention (10 points)
Here is some assembly produced by compiling a C++ program for Linux x86-64.
f:
pushq %rbp
movq %rsp, %rbp
pushq %rbx
subq $8, %rsp
addq %rdx, %rsi
movq %rcx, %rbx
movq %rcx, %rdx
callq memcpy@plt
.L1:
movb $0, (%rax,%rbx)
addq $8, %rsp
popq %rbx
popq %rbp
retq
QUESTION 6A. What is the minimum number of parameters that f
takes?
1pt. 4
QUESTION 6B. Assuming that the memcpy
function obeys the calling
convention, what is the value of %rbp - %rsp
at label .L1
, immediately
before the movb
instruction?
1pt. 16
QUESTION 6C. What value does f
return? (Hint: What does memcpy
return?)
1pt. Its first parameter.
void*
gets 1 point.
QUESTION 6D. Which callee-saved registers does f
modify? (Restoring to a
saved value counts as modification.)
2pts.
%rbp
and%rbx
(and%rsp
,%rip
). The original version of this question modified%r12
, and we accepted that too.
QUESTION 6E. What memory might f
modify, directly or via memcpy
?
2pts.
- The stack
- The memory pointed to by the first parameter
QUESTION 6F. Each of f
’s parameters has at least one evil value, where in
any Linux x86-64 system, passing the evil value for that parameter will always
cause a crash (assuming the other parameters have reasonable values). List at
least one evil value per parameter.
2pts.
- Set first parameter to
nullptr
- Set second parameter to
nullptr
- Set third parameter to
0x8000'0000'0000'0000
- Set fourth parameter to
(size_t) -1
QUESTION 6G. Write a C++ signature for this function, including types.
1pt.
char* f(char* dst, char* src, long off, size_t len)
7. Optimize this (15 points)
In the following problems, you are asked to think like a compiler optimizer. When we say “optimize” assembly, that means write new assembly that behaves identically to the old assembly on all inputs. (Cycle count doesn’t count.)
QUESTION 7A. The following assembly code was generated by an unoptimized
compiler for a function named f
.
__Z1fjj:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
L6:
cmpl $0, -8(%rbp)
je L5
subl $1, -8(%rbp)
addl $1, -4(%rbp)
jmp L6
L5:
movl -4(%rbp), %eax
popq %rbp
ret
Which of these statements are likely true about the source code for f
? List
all that apply. If ambiguous, explain your reasoning.
f
takes one argument.f
takes two arguments.- The arguments to
f
have different types. - At least one argument to
f
is a pointer. - At least one argument to
f
has size 8 bytes. - None of the above.
2pts. 2.
QUESTION 7B. Optimize f
’s assembly so that the new assembly never
accesses stack memory, or explain briefly why this is not possible.
3pt.
__Z1fjj: L6: cmpl $0, %esi je L5 subl $1, %esi addl $1, %edi jmp L6 L5: movl %edi, %eax ret
QUESTION 7C. Optimize f
’s assembly so that the new assembly contains no
backward jumps, or explain briefly why this is not possible.
2pt.
__Z1fjj: addl $esi, %edi movl %edi, %eax ret
QUESTION 7D. The following assembly code was generated by an unoptimized
compiler for a function named g
.
__Z1gjj:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
L7:
cmpl $0, -8(%rbp)
je L6
addl $1, -4(%rbp)
jmp L7
L6:
movl -4(%rbp), %eax
popq %rbp
ret
Optimize g
’s assembly so that the new assembly contains no backward jumps,
or explain briefly why this is not possible.
2pts. It isn’t possible. If the second parameter is not zero, the function loops forever.
QUESTION 7E. Write C++ code that has the same effect as function g
.
2pts.
int g(int a, int b) { while (b != 0) { } // OK to put `a++` or `a--` or `a=0` or whatever in there return a; }
QUESTION 7F. The following assembly code was generated by an unoptimized compiler for a function named h
.
__Z1hPiim:
pushq %rbp
movq %rsp, %rbp
movq %rdi, -24(%rbp)
movl %esi, -28(%rbp)
movq %rdx, -40(%rbp)
movq $0, -8(%rbp)
L11:
movq -8(%rbp), %rax
cmpq -40(%rbp), %rax
je L10
movq -8(%rbp), %rax
shlq $2, %rax
movq -24(%rbp), %rdi
movl (%rdi,%rax), %eax
cmpl %eax, -28(%rbp)
je L10
addq $1, -8(%rbp)
jmp L11
L10:
movq -8(%rbp), %rax
popq %rbp
ret
Which of the arguments to h
must be pointers? List all that apply.
1pt. The first.
QUESTION 7G. h
declares one local variable other than its parameters. Where
is that variable stored, and what is its size?
1pt.
-8(%rbp)
, 8 bytes.
QUESTION 7H. Which of these statements are true about h
? List all that
apply.
h
accesses an array in sequential order (starting at the first element, then the second, and so on).h
accesses an array in reverse sequential order (starting at the last element, then the next-to-last, and so on).h
accesses an array in non-sequential order.- The maximum amount of time
h
takes is determined by the value of its first argument. - The maximum amount of time
h
takes is determined by the value of its third argument. - The amount of time
h
takes may differ depending on the contents of the array. - None of the above.
2pts. 1, 5, 6
8. Disassembly (10 points)
Here is part of the assembly code of a function as reported by objdump -d
:
685: 83 c1 01 add $0x1,%ecx
688: 48 63 d1 movslq %ecx,%rdx
QUESTION 8A. objdump
has left off the size indicator on the add
instruction, but we can still tell the size of the destination operand. What
is that size, and how do you know?
1pt. 32 bits/4 bytes.
%ecx
is the lower 32-bit portion of the%rcx
register.
QUESTION 8B. Considering both instructions, is the value in %ecx
a signed
or unsigned number? How do you know?
1pt. Signed.
movslq
sign extends the 32-bit (Intel long) in%ecx
into the 64-bit%rdx
(Intel quad) register.
QUESTION 8C. What value does the processor add to its %rip
register as it executes the add
instruction in this sequence of two instructions? Explain briefly.
2pts.
0x3
.%rip
is the instruction pointer. At the start of the execution of theadd
instruction, the processor needs to increment the instruction pointer by the number of bytes in this particular add instruction, which is 3 (or0x3
).
Let’s now look at the entire function from which we took these two instructions.
66a: 0f b6 17 movzbl (%rdi),%edx
66d: 84 d2 test %dl,%dl
66f: 74 24 je 695 <f+0x2b>
671: b9 00 00 00 00 mov $0x0,%ecx
676: b8 00 00 00 00 mov $0x0,%eax
67b: 8d 04 80 lea (%rax,%rax,4),%eax
67e: 0f be d2 movsbl %dl,%edx
681: 8d 44 42 d0 lea -0x30(%rdx,%rax,2),%eax
685: 83 c1 01 add $0x1,%ecx
688: 48 63 d1 movslq %ecx,%rdx
68b: 0f b6 14 17 movzbl (%rdi,%rdx,1),%edx
68f: 84 d2 test %dl,%dl
691: 75 e8 jne 67b <f+0x11>
693: f3 c3 repz retq
695: b8 00 00 00 00 mov $0x0,%eax
69a: c3 retq
QUESTION 8D. Does this set of instructions contain a loop? If yes, please list the starting and ending addresses of the loop body; if not, explain briefly.
1pt. Yes, The loop instructions go from address
0x67b
to address0x692
.
QUESTION 8E. The instruction at address 0x67b
is not computing an address, but is instead performing a simple multiplication. By what (base 10) number is it multiplying the value in %rax
?
1pt. 5
QUESTION 8F. Rewrite the three instructions starting at 0x67b
so they have
the same effect on %rax
, but do not use lea
. You may use any x86-64
instructions, including arithmetic (add
, sub
, mul
, div
), shifts
(sal
, sar
, shl
, shr
), and moves (mov
), and you may use %r10
and
%r11
as scratch registers if required. The original instructions:
67b: 8d 04 80 lea (%rax,%rax,4),%eax
67e: 0f be d2 movsbl %dl,%edx
681: 8d 44 42 d0 lea -0x30(%rdx,%rax,2),%eax
2pts.
mull $10, %eax movsbl %dl, %edx addl %edx, %eax subl $0x30, %eax
QUESTION 8G. Describe an input to this function that will cause the function to return 0.
1pt.
""
QUESTION 8H. Describe an input to this function that will cause the function to return 61.
1pt.
"61"
9. Kernel and protection (10 points)
QUESTION 9A. True or false? The only goal of an operating system kernel is to enforce fair sharing of machine resources. Explain briefly.
2pt. False. We also talked about how WeensyOS enforces process isolation, which makes the entire system more robust to programming errors and malicious user programs, and provides safe, convenient abstractions for machine resources.
QUESTION 9B. Which entity is most responsible for ensuring that processes run with reduced machine privilege? Pick the best answer and explain briefly.
- Processes.
- The kernel.
- The processor (the CPU).
4pts for B-D. 3pts if 1 wrong, 2pts if 2 wrong.
2. The kernel defines what privilege level processes run with.
QUESTION 9C. Which entity is most responsible for ensuring that full machine privilege is required for code to disable interrupts? Pick the best answer and explain briefly.
- Processes.
- The kernel.
- The processor.
3. The processor ensures that
cli
can only run in privileged mode.
QUESTION 9D. Which entity is most responsible for ensuring that processes perform a useful function? Pick the best answer and explain briefly.
- Processes.
- The kernel.
- The processor.
1. Only processes can do this!
QUESTION 9E. Kernel memory protection is a shared responsibility between the kernel and the processor. Briefly describe one part of this responsibility that is primarily the kernel’s.
2pts. Defining a page table that prevents unprivileged processes from accessing kernel memory.
QUESTION 9F. All WeensyOS user processes share read/write access to the
CGA console, a memory-mapped I/O device located at physical address
CONSOLE_ADDR = 0XB8000
. Let’s pretend that QEMU emulator has been enhanced
to allow access to our laptop’s camera, a memory-mapped I/O device located at
physical address CAMERA_ADDR
, the page of physical memory immediately
following the console. What is the value of CAMERA_ADDR
in hexadecimal?
1pt. 0xB9000. Each x86-64 page is 0x1000 bytes (or 4KB).
QUESTION 9G. Write a line of code that, if executed by the kernel during
process setup, would give a process with page table pt
read/write access to
the camera at virtual address 0x101000.
1pt. vmiter(pt, 0x101000).map(CAMERA_ADDR, PTE_P | PTE_W | PTE_U);
10. Debugging (10 points)
The following questions assume that you are debugging using GDB. The term
“subsequent instruction” refers to the instruction stored immediately after
the current instruction in memory. In each case assume that .L2
doesn’t
refer to the subsequent instruction.
QUESTION 10A. Assume GDB is debugging a Linux process. In which of these
situations will the ni
command stop on an instruction that is not the
subsequent instruction? List all that apply.
- The current instruction is
jmp .L2
. - The current instruction is
je .L2
, and the processor’sZF
flag is zero. - The current instruction is a
call
. - A timer interrupt occurs.
- None of the above.
3pts. 1 only
QUESTION 10B. Assume GDB is debugging a Linux process. In which of these
situations will the si
command stop on an instruction that is not the
subsequent instruction? List all that apply.
- The current instruction is
jmp .L2
. - The current instruction is
je .L2
, and the processor’sZF
flag is zero. - The current instruction is a
call
. - A timer interrupt occurs.
- None of the above.
3pts. 1 and 3
QUESTION 10C. WeensyOS can also be debugged using GDB. GDB connects to
QEMU and controls the whole emulated x86-64 machine, including the WeensyOS
kernel. When debugging WeensyOS, in which of these situations will the ni
command stop on an instruction that is not the subsequent instruction? List
all that apply.
- The current instruction is
jmp .L2
. - The current instruction is
je .L2
, and the processor’sZF
flag is zero. - The current instruction is a
call
. - A timer interrupt occurs in the emulated QEMU hardware.
- A timer interrupt occurs in the real hardware.
- None of the above.
3pts. 1, 3, 4
QUESTION 10D. Assume that the %rax
register contains the value 4. What is
the most sensible command for printing %rax
’s value, p $rax
or x $rax
?
Explain briefly.
1pt.
p $rax
.x
is for examining memory and will attempt to examine the memory at address 4.
11. The end (10 points)
QUESTION 11A. What improvements would you suggest to the class? Any answer but no answer will receive full credit.
QUESTION 11B. What topics do you wish we had spent more time on? Any answer but no answer will receive full credit.
QUESTION 11C. Write any secret words you know. Or, if you are in DCE or simultaneously enrolled, write any words you know.
+10 points for all three