Assignment 9, Solutions

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

  1. Background: Look up the Linux/Unix mmap() and munmap() operation with the man command.

    Consider the following design for an object file for use in a Unix or Linux system (note: This is fiction, not the real object format): An object file consists of a header, a code segment, and a static segment. The header contains 4 words: code, the offset of the first byte of the code segment within the file, codelen, the length of the code segment, stat, the offset of the static segment, and statlen, the length of the static segment. Offsets and lengths are guaranteed to be divisible by the disk sector size.

    Consider implementing execve() with the equivalent of two consecutive calls to mmap, one to map the code segment and one to map the static segment of the new program. (It can continue to use the old stack segment.)

    a) Work out the correct values of the parameters to the two mmap calls, assuming that the header of the object file has already been read. (0.5 points)

    First, read the object file header; then call

    mmap( NULL, codelen, PROT_READ | PROT_EXEC, MAP_FILE, objectfd, code );
    mmap( NULL, statlen, PROT_READ | PROT_WRITE, MAP_PRIVATE, objectfd, stat );

    b) This design poses problems for the machine architecture and object code. What information must the new implementation of execve pass to the executed program for this to work. Hint: think about the addressing modes that will work under this scheme to access local variables, static variables, and other parts of the program. (0.5 points)

    How does the executed program know where its code segment begins? How does the executed program know where its static segment begins? If these two items are passed in registers, and if the destination program addresses all code and object locations relative to these registers (or uses position independent code), it should be possible to make this work.

  2. Background: You wish you could work with an object-oriented programming language, but you're stuck in pure old-fashioned C, with malloc() available for dynamic allocation of memory. The class you want is called myclass. In C, you create a structure called struct myclass to represent each object, and you create a function, myclass_init() that returns a pointer to an initialized struct myclass structure.

    Problem: Write an appropriate C statement to allocate (but not initialize) a new object in your class, pointed to by the variable new which is a pointer to struct myclass. This statement would be an appropriate first executable statement in the body of myclass_init() -- the rest of the body would consist of code to initialize the newly allocated object. (0.5 points)

    struct myclass new = malloc( sizeof( struct myclass ) );

  3. Background: Consider the following array definition:
    char * heap[VERYBIGNUMBER]; char * freepointer = &heap[0];

    Recall that, in C, casting can convert between pointer types, so (int *)freepointer is a pointer to an integer stored in memory. Furthermore, in C, &freepointer is a pointer to the variable freepointer with type char * * (which means a pointer to a pointer to a character).

    a) Write the simplest version of malloc() you can, assuming that it allocates memory from the variable called heap using freepointer to keep track of the not-yet-allocated memory locations. Your implementation does not need to support any deallocation mechanism. Once allocated, memory stays allocated forever. (0.5 points)

            void * malloc( int size )
    	        void * retval = freepointer;
                    freepointer = freepointer + size;
                    return retval;

    b) To maintain a list of free blocks, the first word of each free block would contain a pointer to the next free block. Given that a and b are of type char * (pointer to character), write C code that makes the block of memory pointed to by a begin with a pointer to b. (0.5 points)

            (char * *)a = b;

  4. A Problem Why would it be impossible to write a heap manager entirely in Java or C#? (0.5 points)

    These two languages are strongly typed. As such, there is no way to convert the address of an untyped block of memory maintained by the heap manager into an object handle.