Lab 3 Extra Problems (Solution)

Solutions by Nick Troccoli and Lisa Yan

Go back to this week's extra problem (without solutions) here.

Go back to this week's lab solutions here.

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

1) 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_heap.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!

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

  strstr searches for the first occurrence of pattern in text, and returns a pointer to the start of the match, or NULL if no match was found. It is used to locate the found match to remove, if any.

• 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?

  The function must always return a heap-allocated string, so it must use strdup to create a copy and return it. Otherwise, the client wouldn't know whether it needed to be freed later or not!

• 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?

  Pointer subtraction returns the number of places that differ between the two pointers, where a "place" is the size of a single element that the pointers point to. In this instance, subtracting on line 10 returns the number of characters difference between the pointers.

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

  This check is an important check to see if malloc returned NULL, indicating that there is no more heap memory. We assert here to crash the program if this occurs.

• After line 15 executes, is the result string null-terminated? Why or why not?

  The string is not null terminated, because strncpy does not add a null-terminator if it is not explicitly copied over. This is ok, however, because the following line's call to strcpy does add a null terminator.

• Your colleague proposes changing line 16 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?

  strcat assumes the string to concatenate to is null-terminated, so if it's not it may continue to walk the string until it finds one! However, heap memory here is likely initially zero, but may not be after the program has run for a while, so it may work, it may not...

• 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".

2) 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.
• What are lines 2-4 of the function doing? What would be the effect on the function's operation if these were removed?

  These functions check for overflow in the total amount of memory requested.

• 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. Explain to them why this plan won't work.

  This approach it may overflow, which is exactly the overflow we are trying to check for!

• 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.
• 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?

  This check sees if memory was in fact allocated. The loop would crash if the check was omitted, because the loop would try to dereference the NULL pointer.

• 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. 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.)

  This assumption is that malloc actually reserves a multiple of 8 bytes. So if the requested amount is not a multiple of 8, malloc will round it up to the nearest multiple. Because of this, while it technically appears that the loop might run up to 7 bytes off at the end (e.g. if the requested size is 9), it's actually safe.

• 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?

  You can assign to/from a void * without casting.

• 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.
• 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 *?

  Changing the type will not impact correctness, but it will require more loop iterations because of the smaller type size; all the mathematical operations would change underlying behavior depending on the type. Filling memory in larger chunks is best, which is why long is the best choice here. However, void * would not work, because then you couldn't dereference wp.

3) 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!

Solution not provided to this part...but one approach is to write a function that makes a long containing copies of the desired pattern. This can be built up using bit operations by copying in the pattern, shifting by the width of the pattern, and then continuing until the entire long is filled in with copies of the pattern. Then, change the line that fills in 0s in calloc to fill in with the specified pattern instead.