ECE 391 Exam 1, Spring 2011
Thursday, Feb 24, 2011
Name:
NetID:
TA’s name:
• Be sure that your exam booklet has 14 pages.
• Write your net ID at the top of each page.
• This is a closed book exam.
• You are allowed one 8.5× 11″ sheet of notes.
• Absolutely no interaction between students is allowed.
• Show all of your work.
• Don’t panic, and good luck!
1
NetID: ECE 391, Exam 1 Feb 24, 2011
Page Points Score
3 9
4 4
5 5
6 10
7 5
8 8
10 12
11 30
Total: 83
Page 2 of 14
NetID: ECE 391, Exam 1 Feb 24, 2011
Question 1: Short Answer (18 points)
Please answer concisely. If you find yourself writing more than a sentence or two, your answer
is probably wrong.
(a)(4) Recall the user-level test harness provided for your use with MP1. Describe one advantage
and one disadvantage of developing and using such a testing strategy when writing new
kernel code, relative to doing all testing of the new code directly in the kernel.
(b)(5) On an x86 processor, what are the two methods of communicating with an external device?
What are the differences between the two? For each method, give an example of a piece
of hardware that uses it.
Points: /9 Page 3 of 14
NetID:
Question 1 continued
ECE 391, Exam 1 Feb 24, 2011
(c)(2) Why does the C calling convention push arguments from right to left?
(d)(2) In the system call calling convention, which registers are caller-saved? Which are callee-
saved?
Points: /4 Page 4 of 14
NetID:
Question 1 continued
ECE 391, Exam 1 Feb 24, 2011
(e)(3) spin_lock_irqsave will acquire the spin lock and call CLI to clear IF. Which happens
first? Explain why.
(f)(2) When is it necessary to use spin_lock_irqsave rather than spinlock_irq or spinlock?
Points: /5 Page 5 of 14
NetID: ECE 391, Exam 1 Feb 24, 2011
Question 2: Locks and Synchronization (15 points)
(a)(10) Implement spin lock and spin unlock in assembly using the global variable lock. Use the
bit test and set atomic operation bts.
bts offset, base
bts selects the bit in base at the bit-position specified by the offset operand, stores the
value of the bit in the carry flag, and sets the selected bit to 1.
lock:
.byte 0
spin_lock:
spin_unlock:
Points: /10 Page 6 of 14
NetID:
Question 2 continued
ECE 391, Exam 1 Feb 24, 2011
(b)(5) Suppose the following variables are declared globally:
int x = 0;
int y = 0;
spinlock_t* lock;
Then, the following two threads are run in parallel:
void thread1(void)
{
y++;
spin_lock(lock);
x++;
spin_unlock(lock):
}
void thread2(void)
{
spin_lock(lock);
x++;
spin_unlock(lock);
y++;
}
What will be the values of x and y after these threads execute? Explain.
Points: /5 Page 7 of 14
NetID: ECE 391, Exam 1 Feb 24, 2011
Question 3: Calling Conventions and the Stack (20 points)
(a)(8) To improve the search speed of the mp1 blink struct list, Rich has decided to try a data
structure he saw on Reddit; Judy arrays. A Judy array is an associative array data
structure intended to be fast and have low memory usage. Unlike a normal array, a Judy
array can be sparse; that is, it can have indices which are unassigned and unallocated.
Judy arrays are allocated on-the-fly, as you insert new elements into them.
You have been provided a skeleton convert to judy that takes the current linked list and
returns a pointer to a Judy array. The Judy array will be indexed by the location field
from the mp1 blink struct.
void add_to_judy(mp1_blink_struct *current, judy_t *judy_array, int index);
judy_t *convert_to_judy(void);
judy_t *judy_init(void);
convert to judy will iterate through every element starting at mp1 list head and call the
add to judy function. add to judy takes:
• index – the index into judy array at which to insert the element. Taken from the
location field of mp1 blink struct.
• judy array – the pointer to the judy array of mp1 blink structs.
• current – the mp1 blink struct to add to judy array.
judy init simply returns a pointer to a new, empty Judy array.
Your task is to complete convert to judy by filling in the call to add to judy, following the
appropriate calling convention. The code is on the following page. You may assume that
calls to add to judy never fail.
Points: /8 Page 8 of 14
NetID:
Question 3 continued
ECE 391, Exam 1 Feb 24, 2011
.long mp1_list_head
convert_to_judy:
pushl %ebp
movl %esp,%ebp
pushl %ebx
pushl %esi
pushl %edi
call judy_init
movl mp1_list_head, %edx
xorl %ecx, %ecx
CHECK_NEXT:
cmpl $0, %edx
je DONE_INSERTING
movw LOCATION(%edx), %cx
# Insert call to add_to_judy below
movl NEXT(%edx), %edx
jmp CHECK_NEXT
DONE_INSERTING:
popl %edi
popl %esi
popl %ebx
leave
ret
Page 9 of 14
NetID:
Question 3 continued
ECE 391, Exam 1 Feb 24, 2011
(b)(12) The figures below are the state of the stack before the execution of the code given below.
Please fill in the state of the stack after execution of the code. In addition, please indicate
where %ebp and %esp are pointing to at the end of execution. Treat registers whose values
you do not know as variables; otherwise, please fill in the actual value.
Please use fig. 1 for scratch work, and write your final answer in fig. 2. Your work in fig.
1 will not be graded.
Lower Addresses
Higher Addresses
old %ebp
return address
%esp %ebp
SC
R
A
T
C
H
Fig. 1: Use this for scratch
work.
pushl $0
pushl $21
pushl $38
c a l l f oo
. . .
f oo :
pushl %ebp
movl %esp , %ebp
pushl %ebx
pushl %e s i
pushl %ed i
addl $−8, %esp
movl 8(%ebp ) , %ed i
movl 12(%ebp ) , %e s i
x o r l %ebx , %ebx
movl %ebx , 4(%esp )
addl $4 , %ed i
pushl %ed i
l e a l (%ebx ,% es i , 2 ) , %eax
movl %eax , 4(%esp )
Lower Addresses
Higher Addresses
old %ebp
return address
%esp %ebp
Fig. 2: Write your answer
here.
Points: /12 Page 10 of 14
NetID: ECE 391, Exam 1 Feb 24, 2011
Question 4: x86 Assembly (30 points)
A palindrome is a word that reads the same backward and forward. For example, RADAR is a
palindrome. Your task is to write a recursive function in x86 assembly that detects whether
a given string is a palindrome using recursion. The string is stored as a doubly-linked list
and the structure of the linked list node is:
typedef struct node_t {
char letter; /* letter */
struct node_t* next; /* Pointer to the next element in the linked list */
struct node_t* prev; /* Pointer to the previous element in the linked list */
} node_t;
The C function prototype is:
/* is_palindrome()
* Description: Recursive function that checks if the string passed in
* between left and right is a palindrome
* Input: left – left pointer of the string being checked
* right – right pointer of the string being checked
* Output: -1 if string is not a palindrome, 0 if string is a palindrome
*/
int is_palindrome(node_t* left, node_t* right);
Additional Notes:
• Assume no compiler padding.
• You can assume the arguments passed in are valid types (No NULL checking or type checking
required)
• To simplify things, you can assume the length of the string is odd.
• The initial call to is palindrome() has the head and tail of the string as arguments.
• You must adhere to the rules of the C calling convention taught in class.
You may wish to write the function in C first, using the space below. Your C code will not
be graded. It is for your convenience only.
Points: /30 Page 11 of 14
NetID:
Question 4 continued
ECE 391, Exam 1 Feb 24, 2011
# typedef struct node_t {
# char letter; /* letter */
# struct node_t* next; /* Pointer to the next element in the linked list */
# struct node_t* prev; /* Pointer to the previous element in the linked list */
# } node_t;
# is_palindrome()
# Description: Recursive function that checks if the string passed in
# between left and right is a palindrome
# Input: left – left pointer of the string being checked
# right – right pointer of the string being checked
# Output: -1 if string is not a palindrome, 0 if string is a palindrome
#
# int is_palindrome(node_t* left, node_t* right);
is_palindrome:
Page 12 of 14
You may tear off this page to use as a reference
Synchronization API reference
spinlock_t lock; Declare an uninitialized spinlock
spinlock_t lock1 = SPIN_LOCK_UNLOCKED; Declare a spinlock and initialize it
spinlock_t lock2 = SPIN_LOCK_LOCKED;
void spin_lock_init(spinlock_t* lock); Initialize a dynamically-allocated spin lock
(set to unlocked)
void spin_lock(spinlock_t *lock); Obtain a spin lock; waits until available
void spin_unlock(spinlock_t *lock); Release a spin lock
void spin_lock_irqsave(spinlock_t *lock, Save processor status in flags,
unsigned long& flags); mask interrupts and obtain spin lock
(note: flags passed by name (macro))
void spin_lock_irqrestore(spinlock_t *lock, Release a spin lock and then set
unsigned long flags); processor status to flags
struct semaphore sem; Declare an uninitialized semaphore
static DECLARE_SEMAPHORE_GENERIC (sem, val); Allocate statically and initialize to val
DECLARE_MUTEX (mutex); Allocate on stack and initialize to one
DECLARE_MUTEX_LOCKED (mutex); Allocate on stack and initialize to zero
void sema_init(struct semaphore *sem, int val); Initialize a dynamically allocated semaphore to val
void init_MUTEX(struct semaphore *sem); Initialize a dynamically allocated semaphore to one.
void init_MUTEX_LOCKED(struct semaphore *sem); Initialize a dynamically allocated semaphore to zero.
void down(struct semaphore *sem); Wait until semaphore is available and decrement (P)
vod up(struct semaphore *sem); Increment the semaphore
Page 13 of 14
You may tear off this page to use as a reference
x86 reference
AX
AL
BL
CL
DL
low
31
AH AL
EAX
8 016 15 7
8−bit
AH
BH
CH
DH
high
EAX
EBX
ECX
EDX
ESI
EDI
EBP
ESP
32−bit
AX
BX
CX
DX
SI
DI
BP
SP
16−bit
jb below CF is set
jbe below or CF or ZF
equal is set
je equal ZF is set
jl less SF 6= OF
jle less or (SF 6= OF) or
equal ZF is set
jo overflow OF is set
jp parity PF is set
(even parity)
js sign SF is set
(negative)
movb (%ebp),%al # AL ← M[EBP]
movb -4(%esp),%al # AL ← M[ESP – 4]
movb (%ebx,%edx),%al # AL ← M[EBX + EDX]
movb 13(%ecx,%ebp),%al # AL ← M[ECX + EBP + 13]
movb (,%ecx,4),%al # AL ← M[ECX * 4]
movb -6(,%edx,2),%al # AL ← M[EDX * 2 – 6]
movb (%esi,%eax,2),%al # AL ← M[ESI + EAX * 2]
movb 24(%eax,%esi,8),%al # AL ← M[EAX + ESI * 8 + 24]
movb 100,%al # AL ← M[100]
movb label,%al # AL ← M[label]
movb label+10,%al # AL ← M[label+10]
movb 10(label),%al # NOT LEGAL!
movb label(%eax),%al # AL ← M[EAX + label]
movb 7*6+label(%edx),%al # AL ← M[EDX + label + 42]
movw $label,%eax # EAX ← label
movw $label+10,%eax # EAX ← label+10
movw $label(%eax),%eax # NOT LEGAL!
call printf # (push EIP), EIP ← printf
call *%eax # (push EIP), EIP ← EAX
call *(%eax) # (push EIP), EIP ← M[EAX]
call *fptr # (push EIP), EIP ← M[fptr]
call *10(%eax,%edx,2) # (push EIP), EIP ←
# M[EAX + EDX*2 + 10]
Conditional branch sense is inverted by inserting an “N” after initial “J,” e.g., JNB. Preferred forms
in table below are those used by debugger in disassembly. Table use: after a comparison such as
cmp %ebx,%esi # set flags based on (ESI – EBX)
choose the operator to place between ESI and EBX, based on the data type. For example, if ESI and
EBX hold unsigned values, and the branch should be taken if ESI ≤ EBX, use either JBE or JNA. For
branches other than JE/JNE based on instructions other than CMP, check the branch conditions above
instead.
preferred form
jnz
jne
jnae
jb
jna
jbe
jz
je
jnb
jae
jnbe
ja
unsigned comparisons
6= < ≤ = ≥ >
preferred form jne
jnz
jl
jnge
jle
jng
je
jz
jge
jnl
jg
jnle
signed comparisons
Page 14 of 14