Lab 3 Extra Problems

Go back to this week's lab writeup here.

These optional problems are an opportunity to further exercise your understanding of arrays, pointers and the heap.

1) Code Study: Heap Use

About 15 minutes Let's take a look at code that dynamically allocates memory on the heap. Specifically, the function join(strings, strings_count) in the provided bonus_heap1.c program returns a string which is the concatenation of all strings_count strings in strings. The returned string is heap-allocated and becomes the client's responsibility to free when done. A core function that makes this implementation possible is the realloc function.

1   char *join(char *strings[], int strings_count) {
2       char *result = strdup(strings[0]);
3       assert(result != NULL);
4
5       for (int i = 1; i < strings_count; i++) {
6           result = realloc(result, strlen(result) + strlen(strings[i]) + 1);
7           assert(result != NULL);
8           strcat(result, strings[i]);
9      }
10     return result;
11  }

At the outset of the loop, the total size needed is not known, so it cannot do the allocation upfront. Instead it makes an initial allocation and enlarges it for each additional string. This resize-as-you-go approach is an idiomatic use case for realloc.

Q1: Is the size argument to realloc the number of additional bytes to add to the memory block, or the total number of bytes including any previously allocated part?

Q2: The variable result is initialized to strdup(strings[0]). Why does it make a copy instead of just assigning result = strings[0]?

• The realloc manual page says the return value from realloc(ptr, newsize) may be the same as ptr, but also may be different. In the case where it is different, realloc has copied the contents from the old location to the new. The old location is also freed. Change the code to call realloc without using its return value (i.e. don't re-assign result, just drop the result). Re-compile and you should get a warning from the compiler.

Q3: What error is that warning trying to caution you against? A realloc call that doesn't catch its return value is never the right call.

• Try running the code; if you run ./heap with one or more arguments, it will join all of the arguments together using the join function.

2) Additional Code Study: Heap Use

About 15 minutes Let's take a look at code that dynamically allocates memory on the heap using malloc, strdup and realloc. Specifically, we'll look at bonus_heap2.c, which you can run or trace in gdb, containing a sample function called remove_first_occurrence.

The function remove_first_occurrence(text, pattern) returns a string which is a copy of text with the first occurrence of pattern removed. The returned string is heap-allocated and becomes the client's responsibility to free when done.

1   char *remove_first_occurrence(const char *text, 
2       const char *pattern) {
3
4       char *found = strstr(text, pattern);
5
6       if (!found) {
7           char *result = strdup(text);
8           assert(result != NULL);
9           return result;
10      }
11
12      int nbefore = found - text;
13      int nremoved = strlen(pattern);
14      char *result = malloc(strlen(text) + 1 - nremoved);
15      assert(result != NULL);
16
17      strncpy(result, text, nbefore);
18      strcpy(result + nbefore, found + nremoved);
19      return result;
20  }

Work through the following questions to understand this code. Ask questions about anything confusing!

Q1: What is the purpose of the library function strstr? What does it return?

Q2: Lines 6-8 handle the case where there is no occurrence of pattern in text, i.e. nothing to remove. Why does the function return strdup(text) rather than just returning text?

Q3: Line 10 subtracts two pointers. What is the result of subtracting two pointers? Here's a hint: if q = p + 3, then q - p => 3. How does the sizeof(pointee) affect the result of a subtraction?

Q4: assert terminates the program if the passed-in expression is false. What is the check on line 13?

Q5: After line 17 executes, is the result string null-terminated? Why or why not?

Q6: Your colleague proposes changing line 18 to instead: strcat(result, found + nremoved) claiming it will operate equivalently. You try it and it even seems to work. Is it equivalent? No, not quite... The code is just "getting lucky". In what way does it (wrongly) depend on the initial contents of newly allocated heap memory? How will the function break when that wrong assumption is not true?

Try running the code; if you run ./bonus_heap with no arguments, it will run a short test of the function, removing "time" from "centimeter".

3) Code study: calloc

About 15-20 minutes Let's take a look at the implementation of calloc, an alternative to the malloc memory-allocating function, to better understand how heap memory allocation works. First, read the manual page for the function (man calloc) and then review the implementation for musl_calloc shown below (based on code from musl):

1   void *musl_calloc(size_t nelems, size_t elemsz) {
2       if (nelems && (elemsz > SIZE_MAX / nelems)) {
3           return NULL;
4       }
5       size_t total = nelems * elemsz;
6       void *p = malloc(total);
7       if (p != NULL) {
8           long *wp;
9           size_t nw = (total + sizeof(*wp) - 1) / sizeof(*wp);
10          for (wp = p; nw != 0; nw--, wp++) {
11              *wp = 0;
12          }
13      }
14      return p;
15  }

The calloc interface is presented as allocating an array of nelems elements each of size elemsz bytes. It initializes the memory contents to zero, which is the feature that distinguishes calloc from ordinary malloc.

Here are some issues to go through to understand the operation of this function.

• The calloc interface as described in terms of arrays is somewhat misleading because there is nothing array-specific to its operation. It simply allocates a region of total size nelems * elemsz bytes. The call calloc(10, 2) has exactly the same effect as calloc(4, 5) or calloc(1, 20) and memory allocated by any of those calls could be used to store a length-20 string or an array of 5 integers, for example.

Q1: What are lines 2-4 of the function doing? What would be the effect on the function's operation if these were removed?

Q2: A colleague objects to the use of division on line 2 because division is more expensive than multiplication and it requires an extra check for a zero divisor. They propose changing it to if (nelems * elemsz > SIZE_MAX), claiming it will operate equivalently and more efficiently. Why won't this plan work?

• Line 6 declares p to be of type void*, which matches the return type of malloc. A void* pointer is a generic pointer. It stores an address, but makes no claim about the type of the pointee. It is illegal to dereference or do pointer arithmetic on a void*, since both of these operations depend on the type of the pointer, which is not known in this case. However, void * can be assigned to/from without an explicit cast.

Q3: What is the purpose of line 7? What would be the effect on the function's operation if that test were removed and it always proceeded into the loop?

• Line 9 contains the expression sizeof(*wp). Given that wp was declared and not assigned, this looks to dereference an uninitialized pointer! Not to fear, it turns out that sizeof is evaluated at compile-time by working out the size for an expression from its declared type. Since wp was declared as a long *, the expression *wp is of type long which on Myth systems has size 8 bytes. The compiler will have transformed it into (total + 8 - 1)/8. Phew! There will be no nasty runtime surprises.
• Let's further dig into line 9. It should remind you of code we've seen previously (roundup in lab1). What is the value of nw for the call calloc(20, 4), for calloc(2, 7), or for calloc(3, 1)? Aha, this is a rounding operation, as suspected.

Q4: This calculation is making an assumption about how many bytes malloc will actually reserve for a given requested size. What is that assumption? (This behavior is not a documented public feature and no client that was a true outsider should assume this, but calloc and malloc were authored by the same programmer, and thus calloc is being written by someone with firsthand knowledge of the malloc internals and acting as a privileged insider.)

Q5: The initialization of the for loop on line 10 assigns wp = p, yet wp and p are not of the same declared type. Why is no typecast required here? Would the function behave any differently if you added the typecast wp = (long *)p?

• The increment of the for loop on line 10 offers a rare glimpse of C's comma operator. You can read more about the comma operator on Wikipedia; the only use you are likely to see in practice is to pack multiple expressions into a loop init or increment. In this case, the increment will both advance the pointer and decrement the count of iterations remaining.

Q6: Imagine if line 8 instead declared char *wp with no other changes to the code. How would this change the function's behavior? What if the declaration was int *wp? What if the declaration were void *wp? For each, consider how the pointee type affects the operations wp++ and *wp = 0. What do you think is the motivation for the author's choice of long *?

4) Calloc Challenge

About 20-30min The challenge.c file contains the calloc function from the earlier problem. The task is to modify the implementation to fill the memory with a specified pattern, instead of just 0s. Here's what the function prototype could look like:

void *musl_calloc2(size_t nelems, size_t elemsz, unsigned long pattern, int width) {
    ...
}

The first two parameters are the same, but the last two are new. pattern would be a bit pattern, between 0 and 64 bits. width would be the width (in bits) of that pattern. Only the least-significant width bits should be used as the pattern, even if other bits are non-zero. In other words, you shouldn't assume what is in the sizeof(long) - width other bits.

This new version of calloc should fill in the memory with the pattern of the given size. For instance, if the pattern is 0x8 and the width is 4, if you allocate 16 bytes of memory, each byte should look like 0x8888888888888888. The pattern is used to fill in every width bits of the allocated memory. Therefore, if you allocate 16 bytes of memory with the pattern 0x8000 and width 16, each byte should look like 0x8000800080008000. If the pattern does not fit evenly into a long, it should be copied in whole as much as possible from right to left. For example, if the pattern is 0x15 with width 5 (0b10101), each byte should look like 0x0ad6b5ad6b5ad6b5 (note the 4 leading zeros).

This task should exercise your bit and memory skills. Give it a shot!