如何纠正我的 C 程序中的分段错误 [英] How to correct segmentation fault in my C program
问题描述
我在调试以下为 knapSack 编写的程序时遇到困难
I am having hard-time in debugging the following program written for knapSack
#include <stdio.h>
#include <stdlib.h>
#include "timer.h"
#define MAX(x,y) ((x)>(y) ? (x) : (y))
#define table(i,j) table[(i)*(C+1)+(j)]
int main(int argc, char **argv) {
FILE *fp;
long N, C, opt; // # of objects, capacity
int *weights, *profits, *table, *solution; // weights and profits
int verbose;
// Temp variables
long i, j, count, size, size1, ii, jj;
// Time
double time;
// Read input file:
// first line: # of objects, knapsack capacity,
// next lines: weight and profit of next object (1 object per line)
if ( argc > 1 ) {
fp = fopen(argv[1], "r");
if ( fp == NULL) {
printf("[ERROR] : Failed to read file named '%s'.\n", argv[1]);
exit(1);
}
} else {
printf("USAGE : %s [filename].\n", argv[0]);
exit(1);
}
if (argc > 2) verbose = 1; else verbose = 0;
fscanf(fp, "%ld %ld", &N, &C);
printf("The number of objects is %ld, and the capacity is %ld.\n", N, C);
size = N * sizeof(int);
size1 = C * sizeof(int);
weights = (int *)malloc(size);
profits = (int *)malloc(size);
table = (int *)malloc(size*size1);
solution= (int *)malloc(size);
if ( weights == NULL || profits == NULL ) {
printf("[ERROR] : Failed to allocate memory for weights/profits.\n");
exit(1);
}
for ( i=0 ; i < N ; i++ ) {
count = fscanf(fp, "%d %d", &(weights[i]), &(profits[i]));
if ( count != 2 ) {
printf("[ERROR] : Input file is not well formatted.\n");
exit(1);
}
}
fclose(fp);
initialize_timer ();
start_timer();
// Solve for the optimal profit (create the table)
for(j=0; j<=C; j++) {
table(0,j)=0;
}
for(ii=1;ii<=N;ii++) {
for(jj=0; jj<=C; jj++) {
if(weights[ii-1]>jj) {
table(ii,jj)=table(ii-1,jj);
}
else {
table(ii,jj)=MAX(table(ii-1,jj),(profits[ii-1]+table(ii-1,jj-weights[ii-1])));
}
}
}
opt=table(N,C);
// We only time the creation of the table
stop_timer();
time = elapsed_time ();
printf("The optimal profit is %ld Time taken : %lf.\n",opt,time);
// End of "Solve for the optimal profit"
// Find the solution (choice vector) by backtracking through the table
printf("Solution vector is: \n");
j=C;
for(i=N;i>0;i--) {
if(table(i,j)==table(i-1,j)) {
//printf("Object %d not picked", i);
solution[i-1]=0;
}
else {
//printf("Object %d picked", i);
j=j-weights[i-1];
solution[i-1]=1;
}
}
for(i=0; i<N; i++) {
printf("%d ",solution[i]);
}
if (verbose) {
// print the solution vector
}
return 0;
}
对于小输入，代码运行良好.但是对于 N=1200 和 C= 38400000 或 C 的任何其他大输入，代码显示分段错误.以下是 Valgrind 的输出:
For small inputs the code runs fine. But for N=1200 and C= 38400000 or any other large input of C , the code shows segmentation error. Following is output from Valgrind :
The number of objects is 1200, and the capacity is 38400000.
==2297== Invalid write of size 4
==2297== at 0x400A4E: main (knap1.c:73)
==2297== Address 0x8 is not stack'd, malloc'd or (recently) free'd
==2297==
==2297==
==2297== Process terminating with default action of signal 11 (SIGSEGV)
==2297== Access not within mapped region at address 0x8
==2297== at 0x400A4E: main (knap1.c:73)
==2297== If you believe this happened as a result of a stack
==2297== overflow in your program's main thread (unlikely but
==2297== possible), you can try to increase the size of the
==2297== main thread stack using the --main-stacksize= flag.
==2297== The main thread stack size used in this run was 8388608.
==2297==
==2297== HEAP SUMMARY:
==2297== in use at exit: 14,400 bytes in 3 blocks
==2297== total heap usage: 4 allocs, 1 frees, 14,968 bytes allocated
==2297==
==2297== LEAK SUMMARY:
==2297== definitely lost: 0 bytes in 0 blocks
==2297== indirectly lost: 0 bytes in 0 blocks
==2297== possibly lost: 0 bytes in 0 blocks
==2297== still reachable: 14,400 bytes in 3 blocks
==2297== suppressed: 0 bytes in 0 blocks
==2297== Rerun with --leak-check=full to see details of leaked memory
==2297==
==2297== For counts of detected and suppressed errors, rerun with: -v
==2297== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)
Segmentation fault
以下是有关使用不同输入文件(k10.txt 到 k1200.txt)运行时本地变量(从 gdb 获取)的值的信息:
Here is info about value of locals (got from gdb) when run with different input files (k10.txt to k1200.txt) :
for files with which I got correct output until it exceeded that fix. no. of byte value
fp = 0x0 N = 4131212846 C = 140737488347792 opt = 4294967295 weights =
0x0 profits = 0x36dd221168 table = 0x7ffff7ffc6b8 solution =
0x36dd8101c0 verbose = 0 i = 0 j = 140737488348128 count = 2 size =
4198301 size1 = 1 ii = 4196160 jj = 4198224 time =
2.0728237613194911e-317
for k1200.txt
k1200.txt fp = 0x177b010 N = 1200 C = 38400000 opt = 4294967295
weights = 0x177b250 profits = 0x177c520 table = 0x8 solution =
0x7f3cd40008c0 verbose = 0 i = 1200 j = 0 count = 2 size = 4800 size1
= 153600000 ii = 4196160 jj = 4198224 time = 2.0728237613194911e-317
关于我的代码有什么问题的任何输入?以及如何更正程序使其永远不会显示分段错误?
Any inputs about what is wrong with my code ? and how can I correct the program so that it will never show segmentation fault?
推荐答案
您在这里要求太多内存:
You are asking for way too much memory here:
table = (int *)malloc(size*size1);
正是 1200 * 38400000 * sizeof (int) * sizeof (int)，大约有 74GB 的内存(假设 sizeof (int) == 4).您的计算机无法实际处理这么大的块，因此分配失败，失败时返回NULL 指针.你应该检查过这个条件:
exactly 1200 * 38400000 * sizeof (int) * sizeof (int) which is around 74GB of memory (assuming sizeof (int) == 4). Your computer cannot reastically handle such a large block, so the allocation fails, and when it fails, a NULL pointer is returned. You should have checked this condition:
if (table == NULL) {
fprintf(stderr, "Memory allocation failed :(");
exit(1);
}
您没有使用 NULL 指针，导致分段错误.
You didn't and used a NULL pointer, yielding the segmentation fault.
不幸的是，这里不容易解决.你应该重新考虑算法，看看你是否真的需要一次这么大的块，或者你可以重用一个更小的块.
Unfortunately, there is not easy fix here. You should rethink the algorithm and see if you really need such a large chunk at once, or you can reuse a smaller block.
一个小问题是您要求的内存是您需要的 4 倍(仍然假设 sizeof (int) == 4).实际上，当您 malloc size * size1 字节时，您将 sizeof (int) 考虑了两次，一次是 size =N * sizeof (int) 和一次 size1 = D * sizeof (int)，虽然很明显你想要一个 N * C * sizeof(int)矩阵.
A minor issue is that you are asking for 4x the memory you need (still assuming sizeof (int) == 4). In fact, when you malloc size * size1 bytes, you are taking sizeof (int) into account twice, once as size = N * sizeof (int) and once as size1 = D * sizeof (int), while it was clear that you wanted a N * C * sizeof(int) matrix.
74GB/4 意味着 18.5GB 仍然太多:您的操作系统可能能够在虚拟内存中处理它，但是当交换开始时它会变得非常缓慢.当然，除非您安装了 18+GB 的 RAM.
74GB / 4 means 18.5GB which is still too much: your OS might be able to handle it in virtual memory, but it will get painfully slow when swap kicks in. Unless you have 18+GB of RAM installed, of course.
无论如何，我想您正在使用 table 作为真/假布尔矩阵.每个元素可能是一个 32 位的 int，您只使用了其中的 1 位.如果使用按位运算将 32 个单元格打包成一个整数，则可以将分配的大小减少 32 倍.它可能会对性能产生影响，但肯定会将内存占用减少到您的计算机可以处理的大小.
Anyway, I suppose you are using table as a true/false boolean matrix. Each element is likely a 32-bit int, of which you are using only 1bit. You could cut off the allocated size by 32x if you packed 32 cells into one integer using bitwise operations. It might have an impact on performance, but it will certainly reduce memory footprint to a size your computer can handle.
正如评论中所建议的，您也可以使用 char 或 bool 而不是 int，因为它们通常更小.
As suggested in the comments, you could also use char or bool instead of int, since they are usually smaller.
这篇关于如何纠正我的 C 程序中的分段错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
