Leetcode error: address sanitizer: detailed analysis and solution of deadlysignal

Problem description, problem analysis, case analysis, error source code, OK code after source code analysis and solution

For more summary, please refer to: C brush questions: leetcode brush questions step on the pit common bug summary

Problem description

Error: addresssanitizer: deadlysignal, details are as follows

===42====ERROR:AddressSanitizer: SEGV on unknown address xx. 
The signal is caused by a READ memory access.

Problem analysis

In general, there may be the following problems:

Out of bounds, the array reference exceeds the left and right bounds, infinite recursion, the code can not normally end, return function input and output parameters, return processing error

According to the above ideas, the example code is analyzed to solve the bug.

Case analysis

The questions come from leetcode topic 46. Please refer to the problem analysis blog for details. Paste the problem code of the above error in the first edition:

Error source code

Main key code of the first layer:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int g_trackNum; // Used for temporary stacking during recursive calls
int g_rowPos;

// Subfunction declaration
int isContanin(int *nums, int len, int val)；
void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track);

// Main call function
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    // Calculate all possible totals
    int row = 1, i;
    for (i = numsSize; i > 0; i--) {
        row *= i;
    }
    *returnSize = row;

    printf("row = %d\n", row);

    // Request a two-dimensional array of the corresponding size and allocate space
    returnColumnSizes = (int **)malloc((row + 10) * sizeof(int*));
    if (returnColumnSizes == NULL) {
        return NULL;
    }
    int *p;
    for (i = 0; i < row; i++) {
        p = (int*)malloc((numsSize + 10) * sizeof(int));
        if (p == NULL) {
            return NULL;
        }
        returnColumnSizes[i] = p;
    }
    p = (int*)malloc(numsSize * sizeof(int));
    if (p == NULL) {
        return NULL;
    }
    int *track = p;

    // Backtrack to exhaust all possible permutations
    g_trackNum = 0;
    g_rowPos = 0;
    backtrack(nums, numsSize, returnColumnSizes, track); // Put the result from line 0

    // Returns returnSize and a two-dimensional pointer
    return returnColumnSizes;
}

Recursive code for backtracking implementation:

void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track)
{
    // Reach the leaf node track join returnColumSizes, the recorded path has been equal to the length of the array stop
    int i;
    if (g_trackNum == numsSize) {
        // printf("back: g_rowPos = %d\n", g_rowPos);
        for (i = 0; i < numsSize; i++) {
            // printf("back: g_rowPos = %d\n", g_rowPos);
            returnColumnSizes[g_rowPos][i] = track[i];
        }
        g_rowPos++;
        return;
    }

    // Recursive traversal
    for (i = 0; i < numsSize; i++) {
        // check if the current value is in the track
        if (isContanin(track, g_trackNum, nums[i])) {
            continue;
        }

        // If not, join track
        // printf("back: g_trackNum = %d\n", g_trackNum);
        track[g_trackNum++] = nums[i];
        
        // Continue traversing backwards
        backtrack(nums, numsSize, returnColumnSizes, track);
        // After the node returns, retrieve the value in the track
        g_trackNum--;
    }

    return;
}

Sub function to determine whether the current value has been traversed

int isContanin(int *nums, int len, int val)
{
    int flag = 0;
    int i;
    for (i = 0; i < len; i++) {
        if (nums[i] == val) {
            flag = 1;
            break;
        }
    }
    return flag;
}

Source code analysis

check possible problem 1 : out of bounds, array reference out of bounds

There are two main ideas:
1. Try to allocate enough space first to see if it is a space problem
2. Print subscript value in advance where it may cross the boundary to see if it overflows. Because address disinfection is interrupted at runtime, you can use printf to print the situation before the interruption.

Method 1

At each possible cross-border reference, the subscript is printed in advance to record the subscript coefficient printed before the program crashes. An example of the printing code is as follows: printf ("row = D/N", row)printf("back: g_ rowPos = %d\n", g_ rowPos);printf("back: g_ trackNum = %d\n", g_ trackNum);

Method 2

When initializing the array allocation space, forcibly allocates enough space to ensure that the space is sufficient. If there is no error after increasing the space, it means that the array reference is out of bounds

After running the code, it was found that subscript printing was normal, and no problem was found, so we continued to investigate possible problem 2.

check possible problem 2 : infinite recursion, the code can’t end and return normally

Print the output record directly in the termination condition of the recursive function backtrack, and observe whether the recursion is carried out according to the expected recursion mode. If there is no print record, then the function is not terminated and recursion is infinite all the time

After running the code, it is found that there is no such problem.

check possible problem 3 : error in the return processing of function input and output parameters
after carefully reading the input and output instructions of the first line of the code and comparing the implementation of online C code, it is found that the understanding of output parameters is wrong.

Variable secondary pointer returncolumnsizes stores the number of columns output in each row. Although the number of columns in the title is fixed, it needs to be assigned to the corresponding number of columns. And I first understood that this is the return pointer of a two-dimensional array. The return pointer of the two-dimensional array is passed through the function return parameter. The first address of the two-dimensional array allocated by direct return can be used.

After modifying the above problems, the code output is normal and no error is reported.

OK code after solution

// Determine if an element has been traversed
int isContain(int *nums, int len, int val)
{
    int flag = 0;
    int i;
    for (i = 0; i < len; i++) {
        if (nums[i] == val) {
            flag = 1;
            break;
        }
    }
    return flag;
}

// Note that this global variable is best defined by declaration only and initialized before backtrack
// in case the LeetCode judge does not re-initialize it, resulting in a miscalculation
int g_trackNum; // Used for temporary stacking during recursive calls
int g_rowPos; // Record each row

void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track)
{
    // Reach the leaf node track join returnColumSizes, the recorded path has been equal to the length of the array stop
    int i;
    if (g_trackNum == numsSize) {
        for (i = 0; i < numsSize; i++) {
            returnColumnSizes[g_rowPos][i] = track[i];
        }
        g_rowPos++;
        return;
    }

    // Recursive traversal
    for (i = 0; i < numsSize; i++) {
        // check if the current value is in the track
        if (isContain(track, g_trackNum, nums[i])) {
            continue;
        }

        // If not, add track
        track[g_trackNum++] = nums[i];
        // continue traversing backwards
        backtrack(nums, numsSize, returnColumnSizes, track);
        // After the node returns, retrieve the value in track
        g_trackNum--;
    }

    return;
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    // Calculate the total number of all possible n!
    int row = 1, i;
    for (i = numsSize; i > 0; i--) {
        row *= i;
    }
    *returnSize = row;

    // Calculate the number of columns in each row of the returned array
    *returnColumnSizes = (int *)malloc(sizeof(int) * (*returnSize));
    if (returnColumnSizes == NULL) {
        return NULL;
    }
    for (int i = 0; i < row; i++) {
        returnColumnSizes[0][i] = numsSize;
    }

    // Request a two-dimensional array of the corresponding size and allocate space
    int **res = (int **)malloc((row + 10) * sizeof(int*));
    if (res == NULL) {
        return NULL;
    }
    int *p;
    for (i = 0; i < row; i++) {
        p = (int*)malloc((numsSize + 10) * sizeof(int));
        if (p == NULL) {
            return NULL;
        }
        res[i] = p;
    }
    p = (int*)malloc(numsSize * sizeof(int));
    if (p == NULL) {
        return NULL;
    }
    int *track = p;

    // Backtrack to exhaust all possible permutations
    g_trackNum = 0;
    g_rowPos = 0;
    backtrack(nums, numsSize, res, track); // put the result from row 0

    return res;
}