Assignment 2, Solutions

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Some machines have position independent code, where all branch and call instructions use PC-relative instructions. On such machines, no relocation is needed for such instructions, so it is potentiall possible to load a program in any addresses in memory.

    In a conventional linker, when memory location x is marked as a reference to label L, once the value of L is found during linking, the linker simply does M[x]=value(L) in order to link the instruciton to the label.

    a) If the reference to label L is in the context of a PC-relative branch or call instruction, how does th linker link the instruction to the label? (0.5 points)

    the linker does M[x]=value(L)-X.

    b) Position independent code allows the program's code to be loaded anywhere in memory without relocation. Does it give similar freedom with respect to the program's stack segment? (0.5 points)

    No, but not because there is no such freedom. Position independent code is irrelevant to the question of whether or not the stack can be relocated. The stack can be put anywhere in memory because the stack pointer register points to the stack. The program will use whatever memory is allocated to the stack, so long as it is started with the stack pointer register pointing to that memory.

    c) Position independent code allows the program's code to be loaded anywhere in memory without relocation. Does it give similar freedom with respect to the program's static segment? (0.5 points)

    No. If the program contains absolute addresses of global variables, it moving the static segment requires changing all of these addresses.

  2. Background: LaTeX is a text formatting system that is most useful for large documents such as books. The source for a LaTeX document generally consists of a large collection of files (typically all in one directory) with the file type indicated by the suffix. You might, for example, find:

    The following shell commands build (in the appropriate combination) book.pdf from all of the above, plus several intermediate files (simplified):

    In the above, some files are both read and written by the same shell command. In these cases, the original is read first, and then the replacement written.

    A Problem: Write a makefile to generate book.pdf. (There is no perfect answer because of the cyclic dependencies between some of the files.) (1.0 points)

    book.pdf: book.tex book.bbl book.ind book.aux
           pdflatex book
    book.ind: book.idx
           makeindex book
    book.bbl: book.tex
           bibtex book

  3. Background: In preparation for the first machine problem, the global variable environ provides access to the entire environment, an array of strings. The routine getenv() in the standard library gets the value of an environment variable, so getenv("PATH") gets the current search path. The search path is a single string with colons separating components, where each component is the name of a directory that should be checked whenever an application is launched.

    The C standard library includes a number of string manipulation routines, notably strncpy() for copying a null-terminated string, strstr() searches for one null-terminated string within another, and strchr() searches for the first occurance of a character in a string.

    A Problem: Write a brief chunk of code to enumerate the successive directory names in the current search path. (0.5 points)

    char path = getenv("PATH");
    char buffer[MAXPATH];
    char * p; /* will point to a copy of the path. */
    strncpy( buffer, path, MAXPATH-1 );
    while ((p != NULL) && (*p != '\0')) {
            /* p points to one component of the path,
               where that component either ends with ':' or '\0' */
            char * component = p;
            /* find and fix the end of the component */
            p = strchr(p,':');
    	if (p != NULL) {
                    *p = '\0';
    	/* component points to a null-terminated component of the path */
    	enumerate( component )