Homework2 < CS385spring11

CS385spring11 Web>Syllabus>Homeworks>Homework2 (2011-01-25, Main.jakob) (raw view)EditAttach
---+ Homework 2 - functions calls and memory management

In this homework, we study how parameters are passed and memory is allocated throughout the execution of a program through a variety of mechanisms. 

---++ 1. Pass by value vs. pass by reference

Function parameters (and return values) in C can be passed in two fundamentally different ways:
   * *By value*, the parameter value is copied into a new variable for use by the callee. Since the value is copied into a new variable, changes to the parameter value by the callee have no effect on the callers variable. 
   * *By reference*, where a pointer to the intended parameter value is provided to the callee. Since caller and callee operate on the same variable, any changes made by the callee are seen by the caller. 

Passing by value results in a pure and easy to understand program from a mathematical perspective. However, in programs that _do something, rather than calculate something_, passing by reference is sometimes necessary. Let us explore this distinction through a few exercises.   

---+++ a. From call-by-reference to call-by-value

The following program unnecessarily uses the call-by-reference method for the function =addfive=. Change the function =addfive()= and parts of =main()= to use call-by-value instead.

<verbatim>
#include<stdio.h>
#include<stdlib.h>
void addfive(int *value) {
  *value=(*value)+5;
}

int main(int argc, char **argv) {
  if(argc!=2) { printf("Usage: hw2i1a <integer>\n"); exit(1); }
  int times = atoi(argv[1]);
  int accumulator=0;
  while(times--) {
    printf("Accumulator = %d\n",accumulator);
    addfive(&accumulator);
  }
}
</verbatim>

*Turn-in requirement:* submit your program as a file called =hw2i1a.c= in your hw2 directory, and add =hw2i1a= as a target to the Makefile. 

---+++ b. From call-by-value to call-by-reference

This program crashes with a stack overflow error when we try to pass a very large struct by value. To see the program work, try changing the size of the largearray field to something much smaller. It should break when the size exceeds 4090 bytes or so. 

Change the function =incrementCharAtOffset()= (and part of =main()=) to use call-by-reference for this call instead.  

<verbatim>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct LargeStruct {
  char largearray[4096*1024];
};

struct LargeStruct 
incrementCharAtOffset(struct LargeStruct s, int offset)
{
  s.largearray[offset]++;
  return s;
}

struct LargeStruct myLargeStruct;
main() {
  int incrementOffset = 10;
  printf("Value at offset %d before incrementing %d\n",
          incrementOffset,
          myLargeStruct.largearray[incrementOffset]);

  myLargeStruct=incrementCharAtOffset(myLargeStruct,incrementOffset);

  printf("Value at offset %d after incrementing %d\n",
           incrementOffset,
           myLargeStruct.largearray[incrementOffset]);  
}
</verbatim>

*Turn-in requirement:* submit your program as a file called =hw2i1b.c= in your hw2 directory, and add =hw2i1b= as a target to the Makefile. 

---++ Dynamic memory allocation

Memory is allocated in C in three primary ways.

   * Static allocation, which is used for global variables. Static memory allocation is determined at compile time, and is the same for every execution of a program. This memory is released only upon program exit.
   * Stack allocation, which is used for local variables, function parameters and return values. Space for these variables is allocated from the stack on each function call, and thus depends on the execution flow of a program. The maximum size of the stack is typically set externally. Memory allocated from the stack is released upon function return.
   * Dynamic allocation, often referred to as the 'heap'. Dynamic memory allocation is done using the malloc() or mmap() calls in C. Dynamically allocated memory is released upon program exit, or using the functions free() or munmap(). 

---+++ a. Use dynamic memory allocation instead of static

The program below reverses a word provided on the command line. Unfortunately, we don't know how long the word might be. To be on the safe side, the current program statically allocates one megabyte to hold the reversed version of the string before printing it out. Try compiling the code, to see the size of the binary: over one megabyte!

Change the code to instead allocate only the required amount of memory at runtime, using malloc(), and don't forget to free() the memory at the end!

<verbatim>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char reversed[1024*1024]="Huge";
int main(int argc, char** argv) {
 if(argc != 2) { fprintf(stderr,"Usage: hw2i2a <word>\n"); exit(1); }

 memset(reversed,0,sizeof(reversed));
 int i;
 for(i=0;i<strlen(argv[1]);i++) {
  reversed[i]=argv[1][strlen(argv[1])-i-1];
 }
  
 printf("%s = reversed(%s)\n",reversed,argv[1]);
 printf("The reversed string array is %ld bytes.\n",sizeof(reversed));
}
</verbatim>

*Turn-in requirement:* submit your program as a file called =hw2i2a.c= in your hw2 directory, and add =hw2i2a= as a target to the Makefile. 

---+++ b. implement a (leaky) string concatenation function 

Change (only) the function =concatenate()=, so that it returns the result of concatenating strings a and b. For example, =concatenate("fire","cracker")= returns the string "firecracker". You'll need to use =malloc()= inside concatenate. However, since there are no calls to free(), this code is leaking memory. That's ok for now.

*NOTE:* as before, you may not use existing string library functions, such as sprintf, strcpy, etc for this homework. strlen() is ok. 

<verbatim>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *concatenate(char* a, char* b) {
   return a; // replace this with your string concatenation code
}

int main(int argc, char** argv) {
  if(argc<4) { printf("Usage: hw2i2b <count> <firstword> <secondword>\n");
              exit(1); }

  char *middle="cruel";
  char number[10];
  int i;
    
  for(i=0;i<atoi(argv[1]);i++) {
    sprintf(number,"%d",i); // update the number string

    // begin leaky
    char *line = concatenate( // not leaked
                  concatenate(argv[2],number), // leaked
                  concatenate(middle, // leaked
                   concatenate(number, argv[3]))); // leaked
    if(i>0)  // can't free the statically allocated "cruel" string above
      free(middle); 
    // end leaky      
    printf("%s\n",line);
    middle=line;
  }
  free(middle);
}

</verbatim>

Example program output:

<verbatim>
~> ./hw2i2b 10 hello world
hello0cruel0world
hello1hello0cruel0world1world
hello2hello1hello0cruel0world1world2world
hello3hello2hello1hello0cruel0world1world2world3world
hello4hello3hello2hello1hello0cruel0world1world2world3world4world
hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world
hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world
hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world
hello8hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world8world
hello9hello8hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world8world9world
</verbatim>
*Turn-in requirement:* submit your program as a file called =hw2i2b.c= in your hw2 directory, and add =hw2i2b= as a target to the Makefile. 

---+++ c. manual garbage collection

Without garbage collection, it's difficult to write the above program both elegantly and leak-free at the same time: all those nested concatenate calls are forgetting the pointers to the =malloc()ed=  strings before we get a chance to =free()= them. 

Without resorting to much stronger measures, the only way to fix these leaks is to keep a pointer to each string until we don't need the string any more, and then =free()= it. Make a copy of your hw2i2b.c, calling it hw2i2c.c. Changing only the lines between the "begin leaky" and "end leaky" comments, make sure to plug every memory leak in this program. 

To help with the debugging, add the following before =concatenate()=, change the =malloc()= call in concatenate to =mymalloc()=, and use =myfree()= instead of =free()= (yes, you're allowed to make those changes).

<verbatim>

void* mymalloc(int size) {
  void* ptr = malloc(size);
  fprintf(stderr,"malloc: %p\n",ptr);
  return ptr;
}
void myfree(void* ptr) {
  fprintf(stderr,"free: %p\n",ptr);
  free(ptr);
}
</verbatim>

example output: 

<verbatim>
./a.out 2 hello world
malloc: 100080
malloc: 100090
malloc: 1000a0
malloc: 1000b0
free: 100080
free: 100090
free: 1000a0
hello0cruel0world
malloc: 1000a0
malloc: 100080
malloc: 1000d0
malloc: 1000e0
free: 1000a0
free: 100080
free: 1000d0
free: 1000b0
hello1hello0cruel0world1world
free: 1000e0
</verbatim>

*Turn-in requirements:* hw2i2c.c and a hw2i2c Makefile target, you know the drill.

---++ 3. Three reverse Fibonaccis

The fibonacci series ought to be familiar to you by now: 1,1,2,3,5,8,13.... or f(x)=f(x-1)+f(x-2), f(0)=1, f(1)=1. Here is a typical implementation using recursion:

<verbatim>
long long fib(x) {
 if(x<2) return 1;
 else return fib(x-1)+fib(x-2);
}
</verbatim>

and an iterative implementation
<verbatim>
main() {
 long long back1=1,back2=1;
 printf("1, 1, ");
 int i;
 for(i=2;i<75;i++) {
  long long fib=back1+back2;
  printf("%lld, ",fib);
  back2=back1;
  back1=fib;
 }
}
</verbatim>

Both solutions use the 64-bit type "long long" to support large integers. You are to implement a "reverse fibonacci series" program, in three different ways. All three programs take the same input and produce the same output:

<verbatim>
./hw2i3a 6
8,5,3,2,1,1
./hw2i3b 3
2,1,1
./hw2i3c 9
34,21,13,8,5,3,2,1,1
./hw2i3a 70
190392490709135,117669030460994,72723460248141,44945570212853,27777890035288,17167680177565,10610209857723,6557470319842,4052739537881,2504730781961,1548008755920,956722026041,591286729879,365435296162,225851433717,139583862445,86267571272,53316291173,32951280099,20365011074,12586269025,7778742049,4807526976,2971215073,1836311903,1134903170,701408733,433494437,267914296,165580141,102334155,63245986,39088169,24157817,14930352,9227465,5702887,3524578,2178309,1346269,832040,514229,317811,196418,121393,75025,46368,28657,17711,10946,6765,4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2,1,1
</verbatim>

In our tests, the input number will always be below 75 and above 2.

---+++ a. Functional: No loops, no global variables, no arrays
Use recursive function calls instead of loops. 

*HINT:* your recursive function will probably need several arguments to make this work.

---+++ b. Iterative: No functions, no arrays
Do not declare any functions of your own, and use no arrays or pointers. 

*HINT:* use an outer loop to count down from the input number to 0, and an inner loop to compute the appropriate fibonacci number.

---+++ c. Efficient: No functions, and no nested loops
You may have several loops, but no loops within loops, or any functions of your own.

*HINT:* use a first loop to compute and store the appropriate fibonacci sequence in an array. Use a second loop to print the numbers in the array in reverse order. 

*Turn-in requirement:* submit your programs as files called =hw2i3a.c=, =hw2i3b.c= and =hw2i3c.c= in your hw2 directory, and add the corresponding targets to the Makefile. 

---++ 4. Download, build and install a custom linux kernel 

Finally, a non-programming exercise. From [[http://www.kernel.org/][kernel.org]], download the full source of the most recent mainline linux kernel (currently 2.6.37). Uncompress this archive into the directory /usr/src in your virtual machine. Once it is done, you should have a directory called =/usr/src/linux-2.6.37=. This directory contains the entire source code for the linux kernel, including support for dozens of hardware architectures, and thousands of peripheral devices. 

Before we can build our new kernel, we need to configure it for our system. We have prepared an initial configuration for you, which you can download from here: [[%ATTACHURL%/config][config]]. Because the default configuration comes with nearly everything enabled, this stripped down config file will reduce the compile time. Place the file in your =/usr/src/linux-2.6.37= and rename it to  =.config=.

HINT: Because some of the steps in this process take a great deal of time, it is a good idea to save the state of your virtual machine just in case a later step messes things up. From the "Virtual Machine" menu select "Take a snapshot" to save your machine's state. If something goes wrong you can then restore that state by selecting "revert to snapshot" from the "Virtual Machine" menu.

Place the .config file in the =/usr/src/linux-2.6.37= directory. There are several ways to edit the config file, we will use menuconfig. In order to run menuconfig use apt-get to install the following packages: libncurses5, libncurses5-dev. Then run:
<verbatim>
make menuconfig
</verbatim>

Turn-in requirement: Lets change the version information of this kernel to something a bit more personal. From inside menuconfig select =General setup= and then select =Local version=. Type in your name here without any spaces ex: =DennisRitchie=.

Later on, once you compile the kernel you will run a command that prints out the current installed kernel version and your name should be displayed.

Now that the configuration is complete it is time to perform the compilation. We start by building the kernel executable:
<verbatim>
sudo make
</verbatim>
This should take about a 1/2 hour or so. Next run:

<verbatim>
sudo make install
</verbatim>

After this is complete do a =ls /boot= to print out the contents of the boot directory. You should now see three files in the directory with your name on it: the kernel (starts with vmlinuz), the config file and the system map.

Next we will need to compile the loadable modules. This will take longer than the kernel compile, perhaps an hour or so. Run the following command to build the modules:

<verbatim>
sudo make modules
</verbatim>

Once that finishes you will want to install the modules into the right directory using the following command:

<verbatim>
sudo make modules_install
</verbatim>

Now we need to create an initial ram disk image. This allows us to perform the necessary work for loading up our kernel without actually having an operating system. You can read a bit about this here: [[http://en.wikipedia.org/wiki/Initrd][initrd from wikipedia]]. We can use the mkinitframfs program to create the image:

<verbatim>
sudo mkinitramfs -o /boot/initrd.img-2.6.37DennisRitchie 2.6.37DennisRitchie
</verbatim>

GRUB is the de facto bootloader for Linux. We now need to let GRUB know that we built a new kernel. The first thing we'll do with GRUB is change it's configuration file so that we force the user to have to choose a kernel before we boot. Open up the file =/etc/default/grub= and modify the =GRUB_TIMEOUT= parameter to be =-1=. Now we need to regenerate our grub config file. We can do this by running this command:

<verbatim>
sudo grub-mkconfig -o /boot/grub/grub.cfg
</verbatim>

This program finds new kernels and generate the grub.cfg configuration file, including our new timeout parameter.

Now it is time to load up our kernel! This would be a great time to take a snap shot of your virtual machine! Now we will reboot the machine and see what happens.

<verbatim>
sudo reboot
</verbatim>

Success! (Hopefully). 

*Turn in requirement* Take a snapshot of the VMware machine from your host machine. In the terminal window type: =uname -r=. You should see: =2.6.37DennisRitchie=. Make sure that this appears in the snapshot. Name the file =kernel.png= when you submit it.
Attachments
Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
EXT	config	manage	125.1 K	2011-01-18 - 18:40	UnknownUser	kernel config file
Topic revision: r20 - 2011-01-25 - 00:35:11 - Main.jakob
CS385spring11
WISEST
Helping Women Faculty Advance
Funded by NSF