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.

#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);
  }
}

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 kilobytes or so.

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

#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]);  
}

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!

#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));
}

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.

#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);
}

Example program output:

~> ./hw2i2b 10 hello world
hello0cruel0world
hello1hello0cruel0world1world
hello2hello1hello0cruel0world1world2world
hello3hello2hello1hello0cruel0world1world2world3world
hello4hello3hello2hello1hello0cruel0world1world2world3world4world
hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world
hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world
hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world
hello8hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world8world
hello9hello8hello7hello6hello5hello4hello3hello2hello1hello0cruel0world1world2world3world4world5world6world7world8world9world
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).


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);
}

example output:

./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

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:

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

and an iterative implementation

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;
 }
}

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:

./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

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.

Topic revision: r1 - 2012-01-17 - 21:06:00 - Main.jakob
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF