EBoard 12: Memory, if I remember correctly

• This class will not be recorded, at least not by me.

Approximate overview

• Administrative stuff
• C isn’t a language
• The joy of memory in C
• Thinking more broadly about memory in C
• Finding memory issues

Administrivia

• Happy Thursday!
• Updates on various department issues.
• Sorry about last week.
• My computer still isn’t back.
  • As of yesterday, my computer still hadn’t been shipped out for repairs 2.5 weeks after I brought it in.
  • Amazingly, it doesn’t seem to be ITS’s fault.
• Work for next week: Write a utility program that processes “standard” command-line flags (whatever you deem those to be).
• Read “C isn’t a language” https://gankra.github.io/blah/c-isnt-a-language/
• My cards have disappeared. My memory has too. Volunteer and say your name.
• Presents!

C isn’t a language

https://gankra.github.io/blah/c-isnt-a-language/

Whoops. It looks like the Web site didn’t update. Next week!

The Joy of Memory in C

A simplified version of a buggy program a colleague gave to me.

int
main (int argc, char *argv[])
{
  func1 ();
  char *stuff2 = (char *) malloc(16 * sizeof (char));
  func2 ();
  free (stuff2);
  return 0;
} // main

Right now, it crashes. (When I was asked about the problem, it was just a standard segfault. Now we get an invalid free error.)

If you don’t call free(stuff2), it works fine, but leaks memory.

If you don’t call func2 (), it doesn’t crash, but doesn’t do what it’s supposed to do.

func1 and func2 are long enough that you don’t want to read them.

What’s the likely problem? (Or at least a possible problem.)

• Likely something to do with memory (today’s topic, the malloc and free)
• Perhaps we’re overflowing some other area of memory, and it affects stuff2. (Although we’ve written an experiment (below) that suggests that stuff2 retains its contents.)
• Perhaps we’re accidentally freeing stuff2. Nope, malloc seems to report that issue.

Potential confusion

The space given by malloc (or static declarations) is not the same as the space given by strlen.

char str[128];
strcpy (str, "Hello");
// strlen (str) will be 5, but str still occupies 128 bytes.

Improvement to check about buffer overflow

int
main (int argc, char *argv[])
{
  func1 ();
  char *stuff2 = (char *) malloc(16 * sizeof (char));
  strcpy (stuff2, "Example");
  func2 ();
  printf ("[%s]\n", stuff2);
  free (stuff2);
  return 0;
} // main

Detour: malloc and free

TPS

How would you implement them?

• You can assume that there’s a procedure out there that will give you a new “page” of memory at a time, but not smaller chunks.
• In reality, we usually get those with brk or sbrk.
• In reality, very few people reimplement malloc and free.

You have a free list, which contains all of the available chunks of memory. When you allocate memory, you either

• (a) return something from the list that contains enough memory OR
• (b) break up something bigger in the list, and return the portion requested (returning the remainder to the list)

That is, malloc has a hidden data structure that contains one or more lists of the chunks it can return. For each chunk, it stores the size.

One way to do free: (a) Verify that it’s malloced (e.g., by checking where in memory it is) and (b) add it back to the list. Maybe (c) clear it out.

When we call free, how does it know how much space the block took up in order to put it back into the list?

Memory Issues in C

TPS

What tends to cause segfaults in (your) C programs?

• Bad pointers - pointer to an area in memory that you cannot/should not access.
• Iterate over an array and go beyond the bounds. (Sometimes; you can go fairly far beyond the bounds and not get a segfault.)
• Bad pointer arithmetic!
• Neglecting to initialize pointers.
• Type mismatches. E.g.,

int *ip;
int i;
ip = &i;
// or 
ip = (int *) i; // Tihs is invalid

What errors do novices tend to make with malloc and free?

• Allocating the wrong amount of memory, e.g., int *ints = malloc(16) vs int *ints = malloc (16 * sizeof (int))
  • 16 bytes which is often 4 integers (it depends on which C it is and which architecture it is)
  • 16 integers
• Allocation the wrong amount of memory e.g.,
  • struct node *np = malloc(sizeof (struct node *));
  • struct node *np = malloc(sizeof (struct node));
• Neglecting to do malloc (see ‘uninitialized’ abovbe)
• Neglecting to call free - It will leak memory. Your program won’t crash, immediately.
• Continuing to use a block of memory that has been freed.

How do you diagnose or avoid memory issues in C programs?

• Don’t use C. Use a language that helps you avoid such things, like Java.
• Document your procedures clearly so that you know when they allocate memory and how big your arrays are.
• Test
• Experiment with your code to see when it crashes.
• Walk through your code by hand, checking as you go.
• Write procedures that always check. E.g., instead of a[i] = 2, have

void
store(int *arr, int pos, int size, int val)
{
  if (pos < 0) {
    fprintf (stderr, "Dear idiot, you should not use negative array indices.\n");
  }
  else if (pos >= size) {
    fprintf (stderr, "Out of limits!");
  }
  else {
    arr[pos] = val;
  }
} // store

• Unfortunately, that approach uses extra compute time, which violates one of the key points of using C. (And those conditionals screw up the pipeline.)
• Static program analysis: We can “prove” that we do not reference something out of bounds.
• If you compile with clang, you can use -fsanitize=address as a flag and it will report “all” memory errors.
• If you compile with gcc, you can use valgrind

Back to diagnosing errors

Historic approach (using gcc): valgrind (rhymes with wind)

Modern (clang) approach): -f sanitize=address

Some sample problems and what we see …