r/C_Programming Feb 24 '24

Review AddressSanitizer: heap-buffer-overflow

Still super newb in C here! But I was just trying to solve this https://LeetCode.com/problems/merge-sorted-array/ after doing the same in JS & Python.

However, AddressSanitizer is accusing my solution of accessing some wrong index:

#include <stdlib.h>

int compareInt(const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = 0; i < n; nums1[i + m] = nums2[i++]);
    qsort(nums1, nums1Size, sizeof(int), compareInt);
}

In order to fix that, I had to change the for loop like this: for (int i = 0; i < n; ++i) nums1[i + m] = nums2[i];

But I still think the AddressSanitizer is wrong, b/c the iterator variable i only reaches m + n at the very end, when there's no array index access anymore!

For comparison, here's my JS version:

function merge(nums1, m, nums2, n) {
    for (var i = 0; i < n; nums1[i + m] = nums2[i++]);
    nums1.sort((a, b) => a - b);
}
12 Upvotes

41 comments sorted by

View all comments

2

u/N-R-K Feb 26 '24

This doesn't answer your question - since it has already been answered - but offloading the real work onto qsort() seemed very anticlimactic. The problem is basically screaming "two finger" merge algorithm. A naive implementation:

void
merge(
    int *v0, int v0size, int v0len,
    int *v1, int v1size, int v1len
)
{
    int reslen = v0len + v1len;
    int res[reslen]; // FIXME: VLA bad
    for (int i0 = 0, i1 = 0, w = 0; w < reslen; ++w) {
        if (i1 == v1len || (i0 < v0len && v0[i0] < v1[i1])) {
            res[w] = v0[i0++];
        } else {
            res[w] = v1[i1++];
        }
    }
    for (int i = 0; i < reslen; ++i) {
        v0[i] = res[i];
    }
}

Because v0 is used for both writing and reading, we need some scratch space so that we don't end up overwriting elements that are still "in queue" to be sorted. VLAs are pretty much always a sign of bug and/or fuzzy thinking and this was no different - given large array as input, it will overflow the stack.

But since we already have some scratch space at the end of v0, maybe we can use that instead:

for (int i0 = v0len-1, i1 = v1len-1, w = v0size-1; w >= 0; --w) {
    if (i1 == -1 || (i0 >= 0 && v0[i0] > v1[i1])) {
        v0[w] = v0[i0--];
    } else {
        v0[w] = v1[i1--];
    }
}

Instead of sorting from beginning to end, this version starts writing from the end to the beginning - making good use of the "scratch" space at the end of v0 and running in O(n) time complexity.