调用free函数触发段错误的原因（Myers Diff算法C实现）

在用C语言实现Myers Diff算法时，尝试释放path变量的内存时触发段错误。path通过malloc分配，释放时不为空，但执行free(path)时崩溃。相关代码如下：

int ** MakeMoveSet(Comparison_t * comp) {
  int **moveset, *path;
  int64_t n = comp->file1LineCount, m = comp->file2LineCount;
  int64_t max_tries = n + m;
  int64_t max_index = 2 * max_tries + 1;
  int64_t prev, next;
  int x,y;

  fprintf(stderr, "max_tries=%ju, max_index=%ju\n", max_tries, max_index);
  
  path = malloc(sizeof(int) * max_index); //Array of ints;
  moveset = malloc(sizeof(path) * max_tries); //Array of paths

  path[1] = 0;

  for (int d = 0; d < max_tries; d++) {

    for (int k = -d; k <=d; k+=2) {
      fprintf(stderr, "d=%d,k=%d\n", d, k);
      prev = k - 1;
      next = k + 1;

      // Determine whether to move up or down
      if (k == -d || (k != d && path[prev] < path[next])) {
        x = path[next];
      } else {
        x = path[prev] + 1;
      }

      y = x - k;
      
      // Check diagonals to settle x at deepest point
      while ((x < n && y < m) && (strcmp(comp->file1Lines[x], comp->file2Lines[y]) == 0)) {
        x ++;
        y ++;
      }
      
      path[k] = x;

      fprintf(stderr, "x = %d, y=%d\n", x, y);

      if (x >= n && y >= m) {
        free(path); //Segfault occurs here
        fprintf(stderr, "Bailing\n");
        comp->shortest_edit_path = d;
        fprintf(stderr, "Shortest edit path = %d\n", d);
        return moveset;
      }
    }
  }

  return NULL;
  
}

错误原因分析 #

• 数组负索引访问破坏内存：
  C语言不支持数组负索引，但代码中k的取值范围是-d到d（比如d=1时k=-1、1），直接用k作为path数组的索引（如path[k]、path[prev]）会访问非法内存区域。这会覆盖malloc分配的内存块之外的空间，破坏内存分配器的元数据，最终导致free(path)时触发段错误。

  解决办法是给索引加上偏移量，把负的k转换为合法的非负索引：比如用k + max_tries作为path的索引，因为max_tries = n+m，k的最小值是-(n+m)，加上max_tries后索引范围变为0到2*(n+m)，刚好匹配max_index = 2*max_tries +1的数组大小。

• 未初始化数组元素引发逻辑错误：
  代码只初始化了path[1]，但循环中会访问path[prev]、path[next]等未初始化的位置，这些位置的值是随机垃圾值，可能导致逻辑错误，进一步加剧内存访问问题。需要在分配path后用memset初始化所有元素，或者根据逻辑初始化必要的位置。

• moveset分配的潜在问题：
  moveset = malloc(sizeof(path) * max_tries);中sizeof(path)是指针的大小（比如64位系统是8字节），而moveset是int**类型，应该用sizeof(int*)来分配，虽然这不是直接导致段错误的原因，但会导致分配的内存大小不符合预期，后续使用moveset时可能出现问题。

核心修复示例 #

修改索引计算，添加偏移量：

// 计算索引时加上偏移量max_tries
int64_t offset = max_tries;
// 初始化正确的索引位置
path[offset + 1] = 0;

for (int d = 0; d < max_tries; d++) {
  for (int k = -d; k <=d; k+=2) {
    prev = k - 1;
    next = k + 1;
    // 访问path时加上偏移量
    if (k == -d || (k != d && path[offset + prev] < path[offset + next])) {
      x = path[offset + next];
    } else {
      x = path[offset + prev] + 1;
    }
    // ...
    // 赋值时也加上偏移量
    path[offset + k] = x;
    // ...
  }
}

内容的提问来源于stack exchange，提问作者Charlie Benger-Stevenson