Some memory management trouble: Error AddressSanitizer

Question

I was trying to solve LeetCode problem: #14 Longest Common Prefix. Here is the problem statement:

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

While solving it, I encountered some error. From the error message, I understand that there's invalid memory operations. However, still can't get points from the error messages:

=================================================================
==29==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000110 at pc 0x55b10cc03190 bp 0x7fff30b617c0 sp 0x7fff30b617b0
READ of size 8 at 0x602000000110 thread T0
    #1 0x7f5a70bb00b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000111 is located 0 bytes to the right of 1-byte region [0x602000000110,0x602000000111)
allocated by thread T0 here:
    #0 0x7f5a717f5bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7f5a70bb00b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 07 fa fa fa 05 fa fa fa 07 fa fa fa 07 fa
  0x0c047fff8010: fa fa 04 fa fa fa 00 fa fa fa 04 fa fa fa 03 fa
=>0x0c047fff8020: fa fa[01]fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==29==ABORTING

Here is my C code:

#include <stdio.h>
#include <stdlib.h>

char *func(char ** strs, int strsSize){
    char *ans = strs[0];
    int n, i;

    for(i = 1;i < strsSize;i++){
        n = 0;
        while(1){
            if(ans[n] == strs[i][n]){
                n++;
            }
            else{
                break;
            }
        }
        ans[n] = '\0';
    }

    return ans;
}

int main()
{
    char *s[] = {"flower","flow","flight"};
    printf("%s", func(s, 3));
    return 0;
}

Does there anyone know where I got wrong?

Answer 1

Compiler warnings will give a hint at the problem. Turning on compiler warnings is not simple, but here's what I find useful.

cc -Wall -Wshadow -Wwrite-strings -Wextra -Wconversion -std=c11 -pedantic -g   -c -o test.o test.c

You can look up what those mean here and here.

These give a series of warnings.

test.c:26:18: warning: initializing 'char *' with an expression of type 'const char [7]' discards
      qualifiers [-Wincompatible-pointer-types-discards-qualifiers]
    char *s[] = {"flower","flow","flight"};
                 ^~~~~~~~
test.c:26:27: warning: initializing 'char *' with an expression of type 'const char [5]' discards
      qualifiers [-Wincompatible-pointer-types-discards-qualifiers]
    char *s[] = {"flower","flow","flight"};
                          ^~~~~~
test.c:26:34: warning: initializing 'char *' with an expression of type 'const char [7]' discards
      qualifiers [-Wincompatible-pointer-types-discards-qualifiers]
    char *s[] = {"flower","flow","flight"};
                                 ^~~~~~~~

What that tells us is we have a const char [] that we're using as a char *. If we naively fix that...

const char *s[] = {"flower","flow","flight"};

Now there's a new warning.

test.c:27:23: warning: passing 'const char *[3]' to parameter of type 'char **' discards qualifiers
      in nested pointer types [-Wincompatible-pointer-types-discards-qualifiers]
    printf("%s", func(s, 3));
                      ^
test.c:4:20: note: passing argument to parameter 'strs' here
char *func(char ** strs, int strsSize){
                   ^

Again, we're using a const char *[] as a char **. Ok, let's naively fix that.

char *func(const char ** strs, int strsSize){

Another warning.

test.c:5:11: warning: initializing 'char *' with an expression of type 'const char *' discards
      qualifiers [-Wincompatible-pointer-types-discards-qualifiers]
    char *ans = strs[0];
          ^     ~~~~~~~

Same problem, now we're using a const char * as a char *. Let's naively fix that.

const char *ans = strs[0];

Now we get an error.

test.c:18:16: error: read-only variable is not assignable
        ans[n] = '\0';
        ~~~~~~ ^

Finally there's the problem. {"flower","flow","flight"} are string literals which are read-only. Those strings are in the executable itself and cannot be changed.

$ strings test
flower
flow
flight

When you assign them to a char * you're trying to modify them, but that's not possible. ans[n] = '\0'; is undefined behavior and you get an error.

---

Those strings need to be writable. I don't know of an elegant way to do this, one way is to use strdup to copy the string literals into dynamic memory.

    char *s[] = {
        strdup("flower"),
        strdup("flow"),
        strdup("flight")
    };

Since they're dynamically allocated they need to be freed.

    for(int i = 0; i < 3; i++) {
        free(s[i]);
    }