Erwägen Sie, eine Implementierung für einen nicht so offensichtlichen Algorithmus in C zu schreiben. Lassen Sie es zum Beispiel rekursives Quicksort sein, das ich in KN Kings Buch “C Programming: A Modern Approach, 2nd Edition” gefunden habe, von dem es verfügbar ist hier. Der interessanteste Teil besteht aus zwei folgenden Definitionen:
void quicksort(int a[], int low, int high)
{
int middle;
if (low >= high)
return;
middle = split(a, low, high);
quicksort(a, low, middle - 1);
quicksort(a, middle + 1, high);
}
int split(int a[], int low, int high)
{
int part_element = a[low];
for (;;) {
while (low < high && part_element <= a[high])
high--;
if (low >= high)
break;
a[low++] = a[high];
while (low < high && a[low] <= part_element)
low++;
if (low >= high)
break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}
Beide while Schleifen können durch Entfernen optimiert werden low < high Prüfungen:
for (;;) {
while (part_element < a[high])
high--;
if (low >= high)
break;
a[low++] = a[high];
a[high] = part_element;
while (a[low] <= part_element)
low++;
if (low >= high)
break;
a[high--] = a[low];
a[low] = part_element;
}
Was ist die empfohlene Methode, um sicherzustellen, dass jeder Zugriff oder Schreibvorgang auf das Array (zugewiesen auf Stapel) tatsächlich gültig ist (dh kein undefiniertes Verhalten provoziert) ? Was ich bereits versucht habe ist:
- manuell debuggen mit
gdbauf einigen tatsächlichen Daten - Übergeben Sie den Quellcode an statische Analysetools wie z
splitodercppcheck valgrindmit--tool=exp-sgcheckSchalter
Zum Beispiel mit einem Array aus fünf Elementen {8, 1, 2, 3, 4}:
#define N 5
int main(void)
{
int a[N] = {8, 1, 2, 3, 4}, i;
quicksort(a, 0, N - 1);
printf("After sort:");
for (i = 0; i < N; i++)
printf(" %d", a[i]);
putchar('\n');
return 0;
}
Ergebnis ist (höchstwahrscheinlich ist es implementierungsabhängig):
After sort: 1 1 2 4 8
1. GBB
(gdb) p low
$1 = 3
(gdb) p high
$2 = 4
(gdb) p a[low]
$3 = 1
(gdb) p part_element
$4 = 8
(gdb) s
47 low++;
(gdb) s
46 while (a[low] <= part_element)
(gdb) s
47 low++;
(gdb) s
46 while (a[low] <= part_element)
(gdb) p low
$5 = 5
(gdb) p high
$6 = 4
(gdb) bt full
#0 split (a=0x7fffffffe140, low=5, high=4) at qsort.c:46
part_element = 8
#1 0x00000000004005df in quicksort (a=0x7fffffffe140, low=0, high=4) at qsort.c:30
middle = <value optimized out>
#2 0x0000000000400656 in main () at qsort.c:14
a = {4, 1, 2, 1, 8}
i = <value optimized out>
Wie du siehst low Variable ging außerhalb der Grenze:
(gdb) p low
$5 = 5
2. Statische Analysewerkzeuge
$ splint -retvalint -exportlocal qsort.c
Splint 3.1.2 --- 07 Feb 2011
Finished checking --- no warnings
$ cppcheck qsort.c
Checking qsort.c...
3. Valgrind mit --tool=exp-sgcheck
$ valgrind --tool=exp-sgcheck ./a.out
==5480== exp-sgcheck, a stack and global array overrun detector
==5480== NOTE: This is an Experimental-Class Valgrind Tool
==5480== Copyright (C) 2003-2012, and GNU GPL'd, by OpenWorks Ltd et al.
==5480== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==5480== Command: ./a.out
==5480==
==5480== Invalid read of size 4
==5480== at 0x4005A0: split (qsort.c:46)
==5480== by 0x4005DE: quicksort (qsort.c:30)
==5480== by 0x400655: main (qsort.c:14)
==5480== Address 0x7ff000114 expected vs actual:
==5480== Expected: stack array "a" of size 20 in frame 2 back from here
==5480== Actual: unknown
==5480== Actual: is 0 after Expected
==5480==
After sort: 1 1 2 4 8
==5480==
==5480== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Der Standort at 0x4005A0: split (qsort.c:46) stimmt mit dem gleichen Ort überein, den ich gefunden habe gdb manuell.
Ich verlasse mich normalerweise auf valgrind, um Speicherprobleme zu debuggen.
– Pawel
18. Juni 2014 um 11:29 Uhr
Auch hier kann ein Elektrozaun (-lefence) helfen
– Werden
18. Juni 2014 um 11:42 Uhr
Valgrind ist äußerst hilfreich bei dynamischem Speicher (ich bin mir fast sicher, dass es garantiert, dass es hier jede illegale Speicheroperation findet), aber bei Stack ist es nicht so offensichtlich. Dennoch denke ich, dass es das beste verfügbare Werkzeug ist, obwohl es nicht immer Probleme finden würde.
gcc‘s-fstack-protector-allauch manchmal helfen, zu sehr geringen Kosten.– Kelter
18. Juni 2014 um 16:27 Uhr
Danke kelter. Ich fand in Valgrinds Dokumentation das für Stack-Arrays, die ich verwenden muss
exp-sgcheck, die noch experimentell ist. Ich weiß, dass C keine Überprüfung der Array-Grenze anbietet, außerdem nach der Übergabe des Arrays an die FunktionsizeofInformationen gehen verloren, daher ist es nicht trivial, sie aufzuspüren. Abgesehen davon dachte ich, dass statische Code-Analyse-Tools auch hier nützlich sein könnten.– Grzegorz Szpetkowski
18. Juni 2014 um 16:55 Uhr