Exam 3 practice questions
A. Linking, shared libraries
A1) Here is the disassembly of a possible implementation of the hex_write_string function from Assignment 2, as observed in a non-position-independent executable (asm_hextests):
0000000000400904 <hex_write_string>:
400904: 41 54 push %r12
400906: 49 89 fc mov %rdi,%r12
400909: e8 b9 ff ff ff callq 4008c7 <str_len>
40090e: 48 89 c2 mov %rax,%rdx
400911: bf 01 00 00 00 mov $0x1,%edi
400916: 4c 89 e6 mov %r12,%rsi
400919: b8 01 00 00 00 mov $0x1,%eax
40091e: 0f 05 syscall
400920: 41 5c pop %r12
400922: c3 retq
Note that in the encoding of the callq instruction, the address of the function being called is specified by a signed 32 bit offset, which is relative to the address of the instruction following the callq instruction. Observe that the bytes B9 FF FF FF, when interpreted as a little endian signed two’s complement integer, encode the value -71, and subtracting 71 from the address of the successor of the callq instruction, 0x40090E, yields 0x4008C7, the exact address of the called function.
What are some advantages of encoding the address of a called function as a relative displacement rather than an absolute address? What are some disadvantages?
A2) Let’s say that you have a Linux executable that you don’t have the source code for, and you want to change its behavior so that whenever it tries to open a file, it will be forced to look in a particular directory. For example, if the process wants to open the file foobar.txt, it will actually open /tmp/look_here/foobar.txt. What would be an easy way to accomplish this that doesn’t require any modifications to the executable or any system libraries? You may assume that all files will be opened via calls to the open function in the shared C library, which is a wrapper for the open system call.
B. Exceptions and processes
B1) Consider the following function:
uint64_t sum_array(uint32_t arr[], unsigned len) {
uint64_t sum = 0;
for (unsigned i = 0; i < len; i++) {
sum += arr[i];
}
return sum;
}
Assume that this function is called to find the sum of the elements in a very large (hundreds of millions of elements.) State some possible reasons why the process executing this function might be suspended and resumed during the execution of the function.
B2) Most operating systems use a periodic timer interrupt to ensure that the OS kernel is able to make scheduling decisions on a regular basis. I.e., the timer interrupt handler can ensure that no process is able to have exclusive use of a CPU core for an indefinite period of time.
Assume a uniprocessor (single core) system in which the timer interrupt occurs at fixed intervals. State some advantages and disadvantages of making the timer interval longer rather than shorter.
C. Signals
C1) On Linux, the printf function is not “async signal safe”, which means that it can’t be called safely from a signal handler function. Describe a scenario where calling printf from a signal handler function might result in undesirable program behavior.
D. Virtual memory
D1) Consider the following function:
uint32_t sum_up_to(unsigned n) {
uint32_t sum = 0;
for (unsigned i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
Assume that all of the variables in this function (n, sum, and i) are allocated by the compiler as CPU registers, so that there are no memory references in the assembly code generated for this function. Is it possible for any page faults to occur as a result of executing this function? Briefly explain why or why not.
D2) Say that you have a CPU with 64 bit virtual addresses and a 16K (214 bytes) page size. Assume that page table entries (at all levels of the page table hierarchy) are the same size as addresses, i.e., 8 bytes.
(a) If the full 64 bit address space is usable, how many levels of page tables are necessary?
(b) Show a proposed format for a virtual address, assuming that the entire 64 bit virtual address space is usable, showing the ranges of address bits used for the page offset and the index at each level of the hierarchy.
(c) Explain why, from a practical standpoint, it might be a good idea to support an effective virtual address space of less than 264 bytes.
D3) On x86-64 systems, there are four levels of page tables, with each page table having 512 (29) entries. The page size is 4096 (212) bytes. This scheme provides an effective virtual address size of 248 bytes, since
29 × 29 × 29 × 29 × 212 = 248
(a) In the page directory, which is the page table at the root of the tree, how much virtual address space (in bytes) does each entry represent?
(b) What is the total number of second level, third level, and fourth level page tables that could be reached from a single entry in the page directory? How many bytes of physical memory are required if all of these page tables are present?