Dotaz: poradi prvku ve strukture v C++

[Milan Roubal]

Narazil jsem vcera na tuto stranku a tak jsem se rozhodl, ze si po dlouhe dobe drobatko zaprogramuju. Bohuzel jsem narazil na drobny problem. Kdyz jsem v reseni jedne ulohy pouzil takovouhle strukturu

typedef struct retezce {
  char retezec[21];
  struct retezce *dalsi;
} RETEZCE;

tak 6 z 10 testovacich prikladu skoncilo na chybe:

*** buffer overflow detected ***: /run-1346315753-1140906172/solution terminated
======= Backtrace: =========
/lib/i386-linux-gnu/tls/i686/nosegneg/libc.so.6(__fortify_fail+0x45)[0xb7635dd5]
/lib/i386-linux-gnu/tls/i686/nosegneg/libc.so.6(+0xfebaa)[0xb7634baa]
/lib/i386-linux-gnu/tls/i686/nosegneg/libc.so.6(+0xfdedd)[0xb7633edd]
/run-1346315753-1140906172/solution[0x8048d41]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048ceb]
/run-1346315753-1140906172/solution[0x8048902]
/lib/i386-linux-gnu/tls/i686/nosegneg/libc.so.6(__libc_start_main+0xf3)[0xb754f4d3]
/run-1346315753-1140906172/solution[0x8048a91]
======= Memory map: ========
08048000-0804a000 r-xp 00000000 ca:02 18850134 /run-1346315753-1140906172/solution
0804a000-0804b000 r--p 00001000 ca:02 18850134 /run-1346315753-1140906172/solution
0804b000-0804c000 rw-p 00002000 ca:02 18850134 /run-1346315753-1140906172/solution
09240000-0b406000 rw-p 00000000 00:00 0 [heap]
b729f000-b74eb000 rw-p 00000000 00:00 0
b74eb000-b7507000 r-xp 00000000 ca:01 394527 /lib/i386-linux-gnu/libgcc_ ...

pokud jsem ale poradi prvku v teto strukture otocil,

typedef struct retezce {
  struct retezce *dalsi;
  char retezec[21];
} RETEZCE;

tak je vysledek dobre pro vsechny testovana data.

Co tedy presne ta chybova hlaska znamena a proc zrovna otoceni prvku v te strukture to resi? Kdybych si ten ukazatel prepisoval, tak by mi ten program nefungoval vubec, tim to nebude.

---

---

Odpovědi

[George O.]

Chyba je zcela urcite v kodu, ktery nemame k dispozici. V c/c++ Muzes mit chybu treba na 250. radku a projevit se muze az o par tisic radku dal. Muze se objevovat relativne nahodne, tak jako ted tobe Takze ukaz zdrojak a my na to mrknem

[Milan Roubal]

jeste bych dodal, ze NEVIM, ktera data to dokazou schodit. Vsechny testovaci priklady, ktere jsem schopen ja sam vymyslet, tak projdou na domacim pocitaci korektne.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

using namespace std;

typedef struct pismena {
  int pocet[256];
  struct pismena *next[256];
} PISMENA;

typedef struct retezce {
  char retezec[21];
  struct retezce *dalsi;
} RETEZCE;

typedef struct vysledek {
  //int pole[300000];
  retezce *next[300001];
  retezce *last[300001];
} VYSLEDEK;
  
void store(pismena *memory, char *line, int length) {
  if(length == 1) {
    memory->pocet[line[0]]++;
    return;
  }
  if(memory->next[line[0]] == NULL) {
    memory->next[line[0]] = (PISMENA *) malloc(sizeof(PISMENA));
    for(int i=0; i<256; i++) {
      memory->next[line[0]]->pocet[i] = 0;
      memory->next[line[0]]->next[i] = NULL;
    }
  }
  store(memory->next[line[0]], line + 1, strlen(line + 1));
}

void uloz(VYSLEDEK *vysled, int kam, char* co) {
  retezce *retez = (RETEZCE *) malloc(sizeof(RETEZCE));
  retez->dalsi = NULL;
  strcpy(retez->retezec, co);
/*  cout << "co ";
  cout << co;
  cout << '\n';*/
  if(vysled->next[kam] == NULL) {
    vysled->next[kam] = retez;
    vysled->last[kam] = retez;
  } else {
    vysled->last[kam]->dalsi = retez;
    vysled->last[kam] = retez;
  }
} 

void search(VYSLEDEK *vysled, PISMENA *memory, char *max, int depth, char *curr) {
  for(int i=32; i<256; i++) {
    curr[depth] = (char)i;
    curr[depth + 1] = '\0';
    if(memory->pocet[i] > 0) {
      uloz(vysled, memory->pocet[i], curr);
      //strcpy(max, curr);
    }
    if(memory->next[i] != NULL) {
      search(vysled, memory->next[i], max, depth + 1, curr);
    }
  }
}

void remove(PISMENA *memory, char *max) {
  if(strlen(max) == 1) {
    memory->pocet[max[0]] = 0;
  } else {
    remove(memory->next[max[0]], max + 1);
  }
}
    
int main (void) {
    int total;
    cin >> total;
    char line[21];
    char max[21];
    char curr[21];
    int maxval;
    PISMENA *memory = (PISMENA *) malloc(sizeof(PISMENA));
    for(int i=0; i<256; i++) {
      memory->pocet[i] = 0;
      memory->next[i] = NULL;
    }
    for(int i=0; i < total; i++) {
      cin >> line;
      store(memory, line, strlen(line));
    }
    int k;
    cin >> k;
    /*
    for(int i=0; i < k; i++) {
      max[0] = '\0';
      curr[0] = '\0';
      maxval = 0;
      search(memory, max, &maxval, 0, curr);
      cout << max;
      cout << '\n';
      remove(memory, max);
    }
    */
    VYSLEDEK *vysled = (VYSLEDEK *) malloc(sizeof(VYSLEDEK));
    max[0] = '\0';
    curr[0] = '\0';
    maxval = 0;
    for (int i=0; i<300000; i++) {
      vysled->next[i] = NULL;
      vysled->last[i] = NULL;
    }
    search(vysled, memory, max, 0, curr);
    int counter = 0;
    int pos = 300000 - 1;
    while(pos >= 0) {
   /*   cout << "pos ";
      cout << pos;
      cout << '\n';*/
      if(vysled->next[pos] != NULL) {
	RETEZCE *ret = vysled->next[pos];
	while(ret != NULL) {
	  cout << ret->retezec;
	  cout << '\n';
	  counter++;
	/*  cout << counter;
	  cout << '\n';*/
	  if (counter == k) {
	    
	   /*   cout << "koncim\n";*/
	    /*while(true) {
	     }*/
	    exit(0);
	  }
	  if (ret != vysled->last[pos]) {
	    ret = ret->dalsi;
	  } else {
	    ret = NULL;
	  }
	}
      }
      pos--;
    } 
}

Pro jistotu jeste kompletni zadani:

Frequency Counting of Words / Top N words in a document.
 
Given N terms, your task is to find the k most frequent terms from given N terms.
 
Input format :
 
First line of input contains N, denoting the number of terms to add.
In each of the next N lines, each contains a term.
Next line contains k, most frequent terms.
 
Output format :
 
Print the k most frequent terms in descending order of their frequency. If two terms have same frequency print them in lexicographical order.
 
Sample input :
 
14
Fee
Fi
Fo
Fum
Fee
Fo
Fee 
Fee
Fo
Fi
Fi
Fo
Fum
Fee
3
 
Sample output :
 
Fee
Fo
Fi
 
Constraint :
0 < N < 300000 
0 < term length < 20.

[segfault]

Co treba slova delsi nez 20 pismen?

[Milan Roubal]

posledni radek v zadani je

0 < term length < 20

tedy slova delsi nez 20 znaku nejsou povolena.

[Jan Trávníček]

To znamená, že je nutné vložit do testovacích dat i slova delší než 20 znaků a aplikace si s tím musí umět poradit.

[Milan Roubal]

no vypada to tak, ze skutecne vstup obsahuje 22znakove slovo, coz je v rozporu se zadanim.

[Milan Roubal]

Tak po mem dotazu bylo zadani opraveno, nove je v podminkach

0 < term length < 25

Podle vysledku jsem asi motivoval i par lidi, aby si to take vyzkouseli :)

[Michal Kubeček]

Doufám, že si aspoň uvědomujete, že to na podstatě problému vůbec nic nemění.

[Milan Roubal]

Jo, v tom problem neni. Kazdy program ma nejake omezujici podminky na vstupy, bez nich se programovat neda. Podle nich se voli jak algoritmus, tak datove struktury. A pokud testovaci server dokaze vratit pouze Passed nebo Wrong, tak se kontrola vstupu ani nijak naprogramovat neda, nebot pri nesplneni podminek bude vzdycky jedinym vystupem vysledek Wrong. Nebo nejaky napad, jak tu kontrolu vstupu v tomto konkretnim pripade naprogramovat, aby byla nejak uzitecna?

Souhlasim, ze pad programu neni dobry. Ale skoro bych rekl, ze jsem mel kliku, ze se mi ten error objevil, protoze maji ve FAQ uvedeno

All runtime errors (segfaults, stack overflows, uncaught exceptions, etc) will also show up as 'Wrong answer'

. Pokud by se objevila pouze odpoved Wrong answer, tak bych na to, ze to ten server testuje vstupem mimo rozsah zadani, asi nikdy neprisel.

Mozna, ze se znalost tohoto triku, tedy ze server muze vratit nejen Passed nebo Wrong, ale i behovou chybu, bude hodit v nekterem z pristich pokracovani oblibeneho podrate.cz

[segfault]

Zrovna v c++ není problém ten program napsat tak, aby akceptoval libovolně dlouhá slova (do velikosti dostupné paměti). Byl by pak i hezčí. Přiložené řešení dost ošklivě porušuje pravidlo 0-1-∞ ( http://www.catb.org/jargon/html/Z/Zero-One-Infinity-Rule.html ).

[Kit]

Obávám se, že to opravili chybně. Měli to tak nechat, aby rozpoznali programátory, kteří umí pracovat s chybovými stavy. Když přece dám vstupní limit 20 znaků, musím předpokládat, že mi jich tam někdo narve 50 nebo více a program na tom nesmí zkolabovat.

Nehledě k tomu, že těch 20 znaků může být v UTF-8 i na více než 22 bytech.

[Milan Roubal]

Tady se ale pracuje v prostredi automaticke testovaci masiny, ktera musi nejak rozhodnout. A ta jejich masina tedy neakceptovala v pripade vstupu mimo rozsah ukonceni programu s nenulovou hodnotou jako korektni reseni :)

[l4m4]

Pokud bereš segfault jako ukončení programu s nenulovou hodnotou, tak doufám, že neprogramuješ nic, co by používali ostatní lidé.

[rastos]

Môj tip: Ten prvok, ktorý je prvý v prípade kedy to funguje, niekde pretečie. A prepíše tak dáta v nasledujúcich prvkoch. Ale nevyletí to mimo pamäť zabranú štruktúrou. Naopak ak je ten prvok neskôr, tak rovnako pretečie, ale tentokrát už mimo tvoju štruktúru a spôsobí neplechu.

Pusti to pod debuggerom a uvidíš.

[Milan Roubal]

problem je, ze u me doma to nespadne nikdy. Spadne to na jejich validacnim serveru s jejich testovacima datama, ktera ja neznam. Takze bohuzel debugger se pouzit v tomto pripade neda.

[kuka]

Otoceni prvku obecne nic neresi, je nahoda, ze to pak "funguje" - bez konkretniho kodu tezko rict, proc zrovna pro nej se chyba neprojevi. Napriklad si muzes prepsat byte, ktery je nula, zase na nulu, a vsechno funguje.

[l4m4]

Než hledat chybu, celé to zahoď a použij na počítání výskytů hashovou tabulku std::unordered_map. Výsledný program bude mít tak 20 řádků (pořád víc než two-liner v Pythonu, ale už přijatelně).

[Milan Roubal]

diky za radu. Me jde spise o to pochopit, co presne znamena ta hlaska *** buffer overflow detected *** v jakych situacich muze nastat a kdo ji detekuje. Tedy tahle hlaska se da vygenerovat pouze zapisem / ctenim pameti, ktera nepatri tomu procesu a generuje ji jadro? Nebo muze byt vygenerovana i pri jinych situacich jako je dereferencovani NULL pointeru?

[l4m4]

Buffer overflow detected vypisuje při detekci chyby libc, je-li program zkompilován s -D_FORTIFY_SOURCE=2, což znamená přidáni extra kontrol chyb přetečení mezí. Hláška se v principu může objevit i práci s pamětí, která procesu všechna patří, protože funkce typu strcmp() nemůže dostat ke zpracování úsek paměti, který je součástí více nezávislých alokací, jakkoli je spojitý.

Další obecná rada, když to nechceš napsat inteligentně: spouštěj to pod valgrindem. Nejspíš najdeš spoustu chyb i se vstupy, se kterými program viditelně nepadá.

[Milan Roubal]

vyborne, -D_FORTIFY_SOURCE=2 mi ukazalo, kde hledat skutecnou chybu. Zacal jsem tedy zvedat velikost ciloveho bufferu a pri hodnote 23 misto 21 to uz prestane tuto chybu hlasit. Tedy vstupni data na jejich serveru nesplnuji podminky zadani. Proc tu na tu stejnou chybu ale neskoncilo i to otoceni tech prvku ve strukture? Zatim si to vysvetluji tak, ze ta struktura byla interne zarovnana na 4bajty, a tedy

typedef struct retezce {
  struct retezce *dalsi;
  char retezec[21];
} RETEZCE;

je pote alokovano stejne jako

typedef struct retezce {
  struct retezce *dalsi;
  char retezec[24];
} RETEZCE;

a pak tato chyba neni odchycena. Nebo se mylim?

[Kit]

Vstupní data mají správně. Tvůj program si musí umět poradit i s nestandardním vstupem.

[Michal Kubeček]

Ano, to zarovnání je dost pravděpodobné.

Podstatné je ale něco úplně jiného: pokud chcete někdy programovat i něco jiného než jen umělé školní příklady, ve vlastním zájmu co nejrychleji zapomeňte na přístup "To, že mi program padá, je chyba nekorektních vstupních dat, program je v pořádku." Čtete-li data od uživatele, ze souboru nebo po síti, musíte počítat s tím, že nemusejí splňovat formální požadavky, a váš program se s tím musí v mezích možností rozumně vypořádat. A ne, segfault není rozumné vypořádání se.

[George O.]

Mel jsem vuli se na to podivat, ale ty cesko/anglicke nazvy promennych a funkci navic i naprosto zcestne nazvy jako napr "next" pro array, misto toho, ze by clovek cekal next referenci na ten samy objekt mi znemoznuji to pochopit a odladit v nejake rozumne dobe...

[Milan Roubal]

Kazdopadne typuju preteceni bufferu pomoci zradne funkce strcpy

[Milan Roubal]

vyborne, zasah. nahrazeni funkce strcpy funkci strncpy problem buffer overflow resi.

[George O.]

strcpy je nebezpecna funkce. Zadne kopirovani, alokovani, atd., kde nemas veskere velikosti pod kontrolou, neni bezpecne

[kuka]

Nicmene chybu tam pravdepodobne stale mas, strncpy te pouze "zachranilo" od dopadu nepredpokladane delky nejakeho retezce nebo neexistence jeho ukoncovaciho null znaku, ktery mohlo neco prepsat apod.

[George O.]

A prave v pripade kopirovani delsiho retezce, nez je cilovy buffer, se mohlo stat to, ze doslo k prepsani vrcholu stacku ukoncovaci nulou a pri zavolani instrukce RET to odskocilo na libovolne misto v pameti a udelalo to, co to udelalo... Tak proc tam nutne hledat jeste jinou chybu? Nikdo nerekl, ze tam nemuze byt, samozrejme, ale neni zatim zadny logicky duvod ji hledat, dokud o sobe nerekne sama ))

[kuka]

No jiste. A v tom prave spociva ta chyba, ze se nekde kopiruje to, co nema. To muze mit radu pricin, napr. chybi kontrola neceho na vstupu, doslo k prepsani null znaku na konci nejakeho retezce apod. A je velmi logicke takovy problem hledat, protoze zkracenim nejakeho retezce pomoci strncpy se sice zabranilo spadnuti (nebo hure zneuziti - ze chybny program spadne je celkem pohodovy stav, horsi je, kdyz umozni spustit zavadny kod apod.), ale vecne to spravne byt nemusi - ucelem programu nebyva, aby pouze nespadl.