Тема: бъг в gcc ? (Прочетена 969 пъти)

iskren · « -: Jun 16, 2007, 18:47 »

Здравейте!

Днес ми се случи най-станното нещо

'>. Значи написах аз една програмка на C++, и при едни специфични входни данни дава следния резултат:

Примерен код

*** glibc detected *** ./tribe.bin: double free or corruption (out): 0x0000000000e3dca0 ***
======= Backtrace: =========
/lib64/libc.so.6[0x3377a6ea30]
/lib64/libc.so.6(cfree+0x8c)[0x3377a7214c]
./tribe.bin[0x400e93]
/lib64/libc.so.6(exit+0xe5)[0x3377a32ed5]
/lib64/libc.so.6(gxx_personality_v0+0x59)[0x400959]
======= Memory map: ========
00400000-00402000 r-xp 00000000 08:05 3905373 /mnt/disk1/home/info/boi/testdir/2003/tribe/tribe.bin
00601000-00602000 rw-p 00001000 08:05 3905373 /mnt/disk1/home/info/boi/testdir/2003/tribe/tribe.bin
00602000-00e4c000 rw-p 00602000 00:00 0 [heap]
3377600000-337761a000 r-xp 00000000 08:06 1920336 /lib64/ld-2.5.so
3377819000-337781a000 r--p 00019000 08:06 1920336 /lib64/ld-2.5.so
337781a000-337781b000 rw-p 0001a000 08:06 1920336 /lib64/ld-2.5.so
3377a00000-3377b44000 r-xp 00000000 08:06 1920344 /lib64/libc-2.5.so
3377b44000-3377d44000 ---p 00144000 08:06 1920344 /lib64/libc-2.5.so
3377d44000-3377d48000 r--p 00144000 08:06 1920344 /lib64/libc-2.5.so
3377d48000-3377d49000 rw-p 00148000 08:06 1920344 /lib64/libc-2.5.so
3377d49000-3377d4e000 rw-p 3377d49000 00:00 0
3377e00000-3377e82000 r-xp 00000000 08:06 1920382 /lib64/libm-2.5.so
3377e82000-3378081000 ---p 00082000 08:06 1920382 /lib64/libm-2.5.so
3378081000-3378082000 r--p 00081000 08:06 1920382 /lib64/libm-2.5.so
3378082000-3378083000 rw-p 00082000 08:06 1920382 /lib64/libm-2.5.so
337c200000-337c20d000 r-xp 00000000 08:06 1920386 /lib64/libgcc_s-4.1.1-20070105.so.1
337c20d000-337c40c000 ---p 0000d000 08:06 1920386 /lib64/libgcc_s-4.1.1-20070105.so.1
337c40c000-337c40d000 rw-p 0000c000 08:06 1920386 /lib64/libgcc_s-4.1.1-20070105.so.1
337c600000-337c6e6000 r-xp 00000000 08:06 2690831 /usr/lib64/libstdc++.so.6.0.8
337c6e6000-337c8e5000 ---p 000e6000 08:06 2690831 /usr/lib64/libstdc++.so.6.0.8
337c8e5000-337c8eb000 r--p 000e5000 08:06 2690831 /usr/lib64/libstdc++.so.6.0.8
337c8eb000-337c8ee000 rw-p 000eb000 08:06 2690831 /usr/lib64/libstdc++.so.6.0.8
337c8ee000-337c900000 rw-p 337c8ee000 00:00 0
2aaaaaaab000-2aaaaaaae000 rw-p 2aaaaaaab000 00:00 0
2aaaaaaca000-2aaaaaacd000 rw-p 2aaaaaaca000 00:00 0
2aaaac000000-2aaaac021000 rw-p 2aaaac000000 00:00 0
2aaaac021000-2aaab0000000 ---p 2aaaac021000 00:00 0
7fff882ac000-7fff882c2000 rw-p 7fff882ac000 00:00 0 [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vdso]
./test.sh: line 2: 1536 Aborted ./$1.bin <$2-$1.in >$2-$1.m

или подобно нещо, но първия ред е:

Примерен код

*** glibc detected *** ./tribe.bin: munmap_chunk(): invalid pointer: 0x0000000000d05ca0 ***

интересното в случая е, че на последния ред пише че програмата е abort-ната, но в същото време тя вади правилния отговор за тези входни данни /*става дума за задача по информатика - трябва да се напише програма, която чете входни данни описващи нещо си и смята според заданието и изписва на изхода съответния отговор - та мойта програма изписва верния отговор (след като е аbort-ната??)*/

искам да питам тази грешка на какво може да се дължи, дали не е бъг в компилатора??

neter · « **Отговор #1 -:** Jun 16, 2007, 19:10 »

След като е задача по информатика, значи не е нещо строго секретно. Покажи кода, за да може този, който поиска да ти отговори, да изтества нещата при себе си. Аз едва ли ще мога да ти помогна, защото пиша на други езици, но като дадеш кода може и да ми хрумне нещо

'> Кажи и с коя версия на gcc си: gcc -v

iskren · « **Отговор #2 -:** Jun 16, 2007, 19:15 »

съзнателно не дадох сорс... защото е супер неясен (абсолютно неясен) защото алгоритъма само аз си го знам, да тръгна да обяснявам ще ми трябват 5 страници тема, но ще го сложа все пак
gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-51)
edit: защо няма отстъпи

'>? - вече има като го прекарах през sed и махнах табулациите ...

условие на задачата

Примерен код

/*
FROM: Balkan Olympiad in Informatics (BOI) 2003 day 2
PROB: tribe council
KEYW: 2 phase dynamical programming on tree. O (N) solution
*/

#include <cstdio>
#include <cassert>
#include <vector>

const int MAXN = 1 << 17;

struct el {
   int to;
   int next;
   el () {}
   el (int _to, int _next) : to (_to), next (_next) {}
};

int N;
int prev[MAXN];
int vec[MAXN];
el buf[MAXN];

int q[MAXN];//order of visit

int dp[MAXN];
int first_tight[MAXN];
std::vector <int> kinfo[MAXN];
int kk[MAXN];
int ans = 1;

void bfs () {
   int p3, i, j;
   q[p3 = 0, p3++] = 0;
   for (i = 0; i < p3; ++i)
   for (j = vec[q[i]]; j != -1; j = buf[j].next) {
   q[p3++] = buf[j].to;
   ++kk[q[i]];
   }
   assert (p3 == N);
}

void upd (int v) {
   static int i, csum, exp;
   csum = exp = 0;
   for (i = kk[v]; i >= 0; --i) {
   ++exp;
   csum += kinfo[v][i];
   if (csum < exp) exp = csum;
   if (csum == exp) first_tight[v] = i;
   }
   ans >?= (dp[v] = exp);
}

void stage1 (int v) {
   static int i;
   if (!kk[v]) return;

   kinfo[v].resize (kk[v] + 1, 0);
   for (i = vec[v]; i != -1; i = buf[i].next)
   ++kinfo[v][dp[buf[i].to] <? kk[v]];

   upd (v);
}

void stage2 (int v) {
   if (!kk[v]) return;
   ++kinfo[v][dp[prev[v]] - (dp[v] >= first_tight[prev[v]])];
   upd (v);
}

void prnt (int v) {
   printf ("%d -- %d %d :", v, dp[v], first_tight[v]);
   for (int i = 0; i < (int)kinfo[v].size (); ++i) printf (" %d", kinfo[v][i]); puts ("");
}

int main () {
   scanf ("%d", &N);

   memset (vec, -1, sizeof (vec));
   int i;
   int a, b;
   for (i = 0; i < N - 1; ++i) {
   scanf ("%d %d", &a, &b);
   --a; --b;
   buf[i] = el (b, vec[a]);
   vec[a] = i;

   prev[b] = a;
   }

   bfs ();

   for (i = N-1; i >= 0; --i) stage1 (q[i]);//, printf ("%d -1> %d %d\n", q[i] + 1, dp[q[i]], first_tight[q[i]]);
   for (i = 1; i < N; ++i) stage2 (q[i]);//, prnt (q[i]);

   printf ("%d\n", ans + 1);

   return 0;
}

ето и линк:
tribe.cpp

така. Ето и входните данни (бяха малко сгрешени едни тестове но аз ги поправих - проблема беше че такзват дадена връзка за father->son, а тя се оказва обратната). Ето старите и новите варианти, както и грешките които програмата ми дава за отделните тестове (грешки на компилатора - иначе дава верен отговор (сравнен с отговора на журито))

стари тестове (2 7 8 9 грешни)
нови тестове (2 7 8 9 поправени със обръщане на част от ребрата)
error- message-ите за тестовете за които дава такива

значи като цяло *.in значи входен файл, *.ok значи какво трябва да е извела програмата, а *.m e това което програмата всъщност е извела. На тези тестове на които няма error_X не прави никакъв проблем (0 1 6 8 9)

iskren · « **Отговор #3 -:** Jun 16, 2007, 21:27 »

съжалявам за суматохата ... оказа се 4е на 69-ти ред в някой специфични случаи излизам out-of-bounds. Замених всички индексирания във vector-а със at () и то се обади. Съжалявам че ви притесних - просто ми стана супер интересно как хем гърми хем не гърми и дава верен отговор на всичкото отгоре ...

neter · « **Отговор #4 -:** Jun 17, 2007, 03:29 »

Браво на теб ':ok:'

Ето такива краища на теми ми харесват най-много

'>

Автор Тема: бъг в gcc ? (Прочетена 969 пъти)