C:Workshop:2018:D0

Introduction

This session is dedicated to debugging. Your goal is to explore gdb, valgrind and similar tools as much as you can.

Since, debugging is an unbound process the subject is open.

Warm-up

The first part is a warm-up: a series of coding exercises, similar to exam or coding interview questions.

For each subject:

• solve the problem (i.e. find an algorithm)
• implement your solution
• test and debug it
• see if you can do better

Two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
  Given nums = [2, 7, 11, 15], target = 9,
  Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Longest substring without repeating characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
  Given "abcabcbb", the answer is "abc", which the length is 3.
  Given "bbbbb", the answer is "b", with the length of 1.
  Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

All permutations

Given a string (without repeating characters), print, one by one, all the permutations of the characters in that string. The order of permutations is not important.

Example:
  Given "abc", prints:

      abc
      acb
      bac
      bca
      cab
      cba

More ?

If you want to train more on that matter, you can check website like:

• http://leetcode.com
• https://www.codingame.com/
• https://www.interviewcake.com/
• http://codingforinterviews.com/practice
• https://www.hackerrank.com/domains/tutorials/30-days-of-code
• https://careercup.com/
• ...

First Step: find the bug !

Here are some code samples with bugs, the idea is to use debugging tools to track the bug.

First a simple Makefile:

# Makefile
 
# CC=clang -fsanitize=address
# CC=gcc -fsanitize=address
CC=gcc
CPPFLAGS=
CFLAGS= -Wall -Wextra -std=c99 -O0 -g3
LDFLAGS=
LDLIBS=
 
all:
 
clean:
	rm -f *.o
 
# END

Next: the most basic segfault, basic.c:

# include <stdio.h>
# include <stdlib.h>
 
int main() {
  int *p = NULL;
  *p = 42;
  printf("*p = %d\n", *p);
  return 0;
}

Then, more hideous bug, overflow.c:

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
 
void foo(char *str) {
  char buf[8];
  strcpy(buf, str);
  printf("buf: %s\n", buf);
}
 
int main() {
  char str[32];
  for (size_t i = 0; i < 31; i++)
    str[i] = 'a';
  str[31] = 0;
  foo(str);
  return 0;
}

For these files, you job is too:

• Compile, run and observe
• Use gdb to find the bug(s)
• Use valgrind to find the bug(s)
• Use the address sanitizer of the compiler to find the bug(s)

Memory Leaks

Similar to the previous section, we now want to find memory leaks, and of course correct them in the following files.

First, leak01.c:

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
 
void foo(char *str) {
  char *buf = NULL;
  size_t len = 1 + strlen(str);
  buf = calloc(len, 1);
  strncpy(buf, str, len);
  printf("buf = %s\n", buf);
}
 
int main() {
  char *str = "A simple string ...";
  foo(str);
  return 0;
}

Then, leak02.c:

# include <stdlib.h>
# include <stdio.h>
# include <string.h>
 
struct list {
  int          data;
  struct list *next;
};
 
static
struct list* add_front(struct list *list, int val) {
  struct list *tmp = malloc(sizeof (struct list));
  tmp->data = val;
  tmp->next = list;
  return tmp;
}
 
static
void print_list(struct list *list) {
  int line = 2;
  printf("list = [\n  ");
  for (; list; list = list->next) {
    if (line > 72) {
      printf("\n  ");
      line = 2;
    }
    line += printf("%4d;", list->data);
  }
  printf("\n]\n");
}
 
static
struct list* fill_list(size_t len) {
  struct list *list = NULL;
  for (size_t i = 0; i < len; i++)
    list = add_front(list, i);
  return list;
}
 
static
void delete_list(struct list *list) {
  struct list *tmp = list;
  while (tmp) {
    memset(tmp, 0, sizeof (struct list));
    list = tmp->next;
    free(tmp);
    tmp = list;
  }
}
 
int main(int argc, char *argv[]) {
  size_t len = 8;
  if (argc > 1)
    len = strtoul(argv[1], NULL, 10);
  struct list *list = fill_list(len);
  print_list(list);
  delete_list(list);
  return 0;
}

Finally, leak03.c:

# define _XOPEN_SOURCE 700
 
# include <err.h>
# include <stdio.h>
# include <stdlib.h>
 
void mycat(FILE *in, FILE *out) {
  for (;;) {
    char *line = NULL;
    size_t n = 0;
    if (getline(&line, &n, in) == -1) break;
    fprintf(out, "%s", line);
  }
}
 
int main(int argc, char *argv[]) {
  FILE *in = stdin;
  if (argc > 1) {
    in = fopen(argv[1], "r");
    if (!in) err(1, "can't open %s", argv[1]);
  }
  mycat(in, stdout);
  if (argc > 1)
    fclose(in);
  return 0;
}

For each files, you must:

• Run, compile and observe
• Find memory leaks using valgrind
• Find memory leaks using the address sanitizer of your compiler
• Correct the code