15-410 HW2 solutions (Fall, 2008)

Question 1 - Public Key Practicum

If you did this problem correctly, in a couple of hours your hw2 directory should contain a $USER.message.decrypted file. If not, check to see if there is a $USER.ERROR file. If not, a popular problem is that you used file names other than the ones specified in the assignment, the grading script wasn't able to guess what you meant, and the grader hasn't yet had the time to manually intervene.

By the way, your encrypted messages to us were read and, generally, appreciated.

The message with the best technical content was Benjamin Blum's. The most evocative message was Gabriel Levi's. Of course we're not going to reveal the messages--they're secret!

Question 2 - Demand Loading

Part A

Explain what housekeeping information would be required by the page-fault handler in order to enable demand loading of pages from the text region. Briefly outline how the page-fault handler would access and use that information.

The page-fault handler needs to classify the fault address as belonging to the executable file. One way to do this is to, at the time of the initial load, crack the executable file into a region list of the same sort as might be used to implement new_pages(). Each region would be characterized by the virtual address range it covers, a byte offset into the executable file, and flags (e.g., r/o vs. r/w). Then, assuming a fault address hits one of the executable-file ranges, the page can be brought in from the file with appropriate permissions. Kernels doing inter-process memory sharing at the granularity of pages instead of regions might find it tricky to share demand-loaded pages.

Part B

Now choose another memory region to discuss in the same fashion as your answer for Part A. Try to select the "most interesting" region, and briefly state why you chose the one you did.

Probably the "most interesting" region would be BSS, since it needs to be flagged in such a way that the fault handler doesn't look anywhere in the executable file, but instead obtains a blank page.

Part C

Some systems may benefit more from demand loading than others. ... What does this examination suggest to you?

Most Pebbles executables have two or three read-only pages (text and rodata together) and less than a page each of writable data and BSS. In order to execute the program at all, we will need to load (manually or via a fault) the page containing the entry point and a page of stack. With demand loading, in the best case we could avoid loading "everything else"--four more pages. The cost of loading four pages we don't need in the best case should be compared against the cost of taking one to four page faults in the not-best case. (Also in the mix, of course, should be the fun of implementing demand loading, which we wouldn't want to talk anybody out of.)

However, even a cursory examination of Linux executable files (and, given their size, perhaps a cursory examination would be best) indicates that Pebbles executables might not be the best data set to use when making OS design decisions.

Part D

It is possible to use the nm command to produce a list of the C "objects" (code or data items) in an executable file, sorted by size. If you apply this to a few files in 410user/progs/, what surprising (or at least interesting) pattern emerges?

There are many ways to apply the many options of nm and sort (or to write a script to analyze the output of nm). Below is one approach, which shows C entities sorted by increasing order of size (it skips most entities generated by assembly code, because they are missing compiler-emitted optional metadata, but that is ok in our circumstance, because we have no substantial data or code which didn't come from the compiler).

% nm --size-sort -S -t d -n 410user/progs/exit_test1
16788904 00000004 B _doprnt_truncates
16788900 00000004 d zero.0
16788852 00000012 d test_name
16788881 00000017 d digits.0
16788864 00000017 d digs
16781912 00000022 T exit
16777328 00000032 T _main
16781936 00000036 T strlen
16777795 00000045 T sprintf
16784107 00000048 T __udivdi3
16777840 00000052 T snprintf
16784054 00000053 T __umoddi3
16777580 00000060 t savechar
16777360 00000073 T SIM_printf
16777718 00000077 T vsnprintf
16777640 00000078 T vsprintf
16777892 00000103 t printnum
16777995 00000107 t printnum_16
16777216 00000112 T main
16783905 00000149 t shl
16781972 00001933 T __qdivrem
16778102 00003807 T _doprnt

A simpler command invocation, which requires a little more eyeball or script work to interpret, appears below.

% nm -t d -n 410user/progs/exit_test1
[output omitted]

Boy howdy, _doprnt() is almost a page all by itself! That means it's nearly half of the text size of most Pebbles executables! And half of the remainder, loosely speaking, is __qdivrem(); what on Earth might that be?

You might have expected some printf() code to be of significant size, but you were probably not expecting __qdivrem(). And this is part of the argument for shared libraries.

For further reading...

Here is last semester's homework page.

[Last modified Saturday December 06, 2008]