malloc:损坏的顶部尺寸无法找出问题所在

malloc: corrupted top size can not figure out the problem

提问人:andrey-dru-mel 提问时间:8/20/2023 最后编辑:andrey-dru-mel 更新时间:8/20/2023 访问量:147

问:

我想编写一个简单的 C 程序来接收矩阵(它的大小首先)并反转它,所以我编写了一些代码,编译它,运行并为大小大于 2 的矩阵获得“malloc:损坏的顶部大小”错误。我检查了代码中是否有未释放的内存,但我只是没有看到我搞砸了哪里。

代码本身:

#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double det(double **matrix, int n, int m);
int invert(double **matrix, int n, int m);

int input(double ***matrix, int *n, int *m);
void output(double **matrix, int n, int m);

double **allocate_matrix(int n, int m);

int main(void) {
    double **matrix;
    int n, m;
    if (input(&matrix, &n, &m) == 0 && invert(matrix, n, m) == 0) {
        output(matrix, n, m);
        free(matrix);
    } else
        printf("n/a");
    return 0;
}

// Secondary functions

void swap(void *a, void *b, size_t size) {
    void *c = malloc(size);
    memcpy(c, a, size);
    memcpy(a, b, size);
    memcpy(b, c, size);
    free(c);
}

// Matrix allocation

double **allocate_matrix(int n, int m) {
    double **matrix = malloc(n * m * sizeof(double) + n * sizeof(double *));
    double *data = (double *)(matrix + n);
    for (int i = 0; i < n; i++) matrix[i] = data + m * i;
    for (int i = 0; i < n * m; i++) data[i] = 0;
    return matrix;
}

// Matrix operations

void matrix_for_det(double **matrix, int n, int m, double **res, int y, int x) {
    int in = 0, jn = 0;
    for (int i = 0; i < n; i++) {
        if (i == y) continue;
        for (int j = 0; j < m; j++) {
            if (j == x) continue;
            res[in][jn] = matrix[i][j];
            jn++;
        }
        in++;
    }
}

void matrix_const_mul(double **matrix, int n, int m, double c) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            matrix[i][j] *= c;
        }
    }
}

double det(double **matrix, int n, int m) {
    if (n != m) return NAN;
    if (n == 2) return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix [1][0];
    if(n == 1) return matrix[0][0];
    double result = 0;
    double **next = allocate_matrix(n - 1, m - 1);
    if (next != NULL) {
        for (int col = 0; col < m; col++) {
            matrix_for_det(matrix, n, m, next, 0, col);
            double atom = matrix[0][col] * det(next, n - 1, m - 1);
            if (col % 2 == 0)
                result += atom;
            else
                result -= atom;
        }
        free(next);
    } else
        result = NAN;
    return result;
}

int transpose(double ***matrix, int *n, int *m) {
    int exit_status = 0;
    double **result = allocate_matrix(*m, *n);
    if (result != NULL) {
        for (int i = 0; i < *n; i++) {
            for (int j = 0; j < *m; j++) {
                result[j][i] = (*matrix)[i][j];
            }
        }
        free(*matrix);
        *matrix = result;
        swap(n, m, sizeof(int));
    } else
        exit_status = -1;
    return exit_status;
}

int invert(double **matrix, int n, int m) {
    int exit_status = 0;
    double **new = allocate_matrix(n, m);
    double **next = allocate_matrix(n - 1, m - 1);
    if (new != NULL && next != NULL) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix_for_det(matrix, n, m, next, i, j);
                new[i][j] = det(next, n - 1, m - 1);
                if ((i + j) % 2 == 1) new[i][j] *= -1;
            }
        }
        free(next);

        if (transpose(&new, &n, &m) == 0) {
            double det_v = det(matrix, n, m);
            matrix_const_mul(new, n, m, 1. / det_v);

            memcpy(matrix[0], new[0], n * m * sizeof(double));
        } else
            exit_status = -1;

        free(new);
    } else {
        if (new) free(new);
        if (next) free(next);
    }
    return exit_status;
}

// Input Output

int check_string() {
    int exit_status = 0;
    int c;
    while ((c = getchar()) != EOF && c != '\n' && exit_status == 0) {
        if (!isspace(c)) exit_status = -1;
    }
    return exit_status;
}

int input(double ***matrix, int *n, int *m) {
    int exit_status = 0;
    if (scanf("%d %d", n, m) == 2 && *n > 0 && *n == *m) {
        *matrix = allocate_matrix(*n, *m);
        for (int i = 0; i < *n && exit_status == 0; i++) {
            for (int j = 0; j < *m && exit_status == 0; j++) {
                if (scanf("%lf", (*matrix)[i] + j) != 1) exit_status = -1;
            }
        }
        exit_status += check_string();
        if (exit_status != 0) free(*matrix);
    } else
        exit_status = -1;
    return exit_status;
}

void output(double **matrix, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) {
            printf("%.6lf ", matrix[i][j]);
        }
        if (m > 0) printf("%.6lf", matrix[i][m - 1]);
        if (i < n - 1) puts("");
    }
}

我尝试使用debug来查看哪里出了问题,但它告诉我,在初始化malloc中调用的函数中,malloc中止。我不明白为什么它不像内部错误那样返回 NULL,而是中止所有程序。allocate_matrix()transpose()result

c malloc 动态内存分配

评论

0赞 Weather Vane 8/20/2023
乍一看,它太复杂了。你有两个维度,但又说它们必须相同:一个方阵。input()
0赞 Toby Speight 8/20/2023
Valgrind(或您喜欢的任何内存检查器)告诉您什么?这通常是调查此类问题的第一站。
1赞 chux - Reinstate Monica 8/20/2023
@andrey-dru-mel,请注意,在首选不溢出的情况下可能会溢出。malloc(n * m * sizeof(double) + n * sizeof(double *))intmalloc(sizeof(double) * n * m + n * sizeof(double *))
0赞 andrey-dru-mel 8/20/2023
链接是的,我知道,但我有某种数据输入要求 ̄_(ツ)_/ ̄
1赞 andrey-dru-mel 8/20/2023
@chux-ReinstateMonica,明白了。它按顺序、逐步完成计算。这不像数学,我没有考虑到这个事实。但从现在开始我会的,谢谢)

答:

3赞 Ted Lyngmo 8/20/2023 #1

该函数有问题,因为它访问越界。您在错误的位置初始化,因此将继续增加,远远超出 的限制。matrix_for_detresjnjnm-1

固定:

void matrix_for_det(double **matrix, int n, int m, double **res, int y, int x) {
    int in = 0;                          // don't initialize `jn`  here
    for (int i = 0; i < n; i++) {
        if (i == y) continue;
        int jn = 0;                      // initialize `jn` here
        for (int j = 0; j < m; j++) {
            if (j == x) continue;
            res[in][jn] = matrix[i][j];
            jn++;
        }
        in++;
    }
}

...或者在循环 init-clauses 中进行初始化。for

void matrix_for_det(double **matrix, int n, int m, double **res, int y, int x) {
    for (int i = 0, in = 0; i < n; i++) {
        if (i == y) continue;
        for (int j = 0, jn = 0; j < m; j++) {
            if (j == x) continue;
            res[in][jn] = matrix[i][j];
            jn++;
        }
        in++;
    }
}

评论

0赞 andrey-dru-mel 8/20/2023
我的天啊。非常感谢,错误是如此愚蠢,一如既往。我需要提高我的调试技能:)
0赞 Ted Lyngmo 8/20/2023
@andrey-dru-mel:不客气。如果使用 gcc 或 clang,则使用 编译。它为解决此类问题提供了很大帮助。还要注意下面 chux 的回答,它指出了一个重要的发现。-g -fsanitize=address,undefined
2赞 chux - Reinstate Monica 8/20/2023 #2

代码有各种各样的问题,到目前为止还没有指出:

对准

OP 尝试分配一次可能会有未定义行为的风险。

double **matrix = malloc(n * m * sizeof(double) + n * sizeof(double *));
double *data = double *data = (double *)(matrix + n);;  // Maybe UB

考虑以下情况:需要指向一个 8 字节对齐的地址,因为目标对象是一个,并且指向一个 4 字节对齐的地址,因为该目标对象是一个指针double *doubledouble **

When is odd 是一个 4 字节对齐的值,并强制转换为导致未定义的行为 (UB)。n(matrix + n)double *

更好的方法是分配和赋值,同时考虑到 和 之间可能需要存在填充。matrix[n-1]data


IMO,只需进行 2 次分配。

如果仍然想做一个分配,可以做类似的事情

// Illustrative code
size_t row_size = sizeof(double*) * n;
size_t padding = 0;
size_t alignment = alignof(double);
if (row_size % alignment > 0) {
  padding = alignment - row_size % alignment;
}
size_t data_size = sizeof(double) * n * m;  // Note the order to reduce overflow risk.
double **matrix = malloc(row_size + padding + data_size);
if (matrix) {
  double *data = (double *)((char *)matrix + row_size + padding);

以上可以更优雅地完成,但这是一个炎热的八月下午。是时候提神了。

评论

0赞 andrey-dru-mel 8/20/2023
我在某个地方看到过这个记忆分配案例,对我来说,它就像是对类型化这个概念的嘲弄,但我无法解释为什么这可能是一个错误的决定。所以。。。这就是原因。感谢您的提示,这很有帮助:)