Ticket #116 (closed defect: fixed)
omp-tasks/nqueens.c with MANUAL_CUTOFF has out-of-bounds array access
| Reported by: | Nathan Weeks <weeks@…> | Owned by: | xteruel |
|---|---|---|---|
| Priority: | minor | Milestone: | version 1.2 |
| Component: | nqueens | Version: | version 1.1 |
| Keywords: | Cc: | ||
| Application Version: | omp-tasks | Blocked By: | |
| Blocking: | Sensitive: | no | |
| Needs experiment: | no | ||
| Experimental observations: |
1. To verify the problem, apply the following patch to omp-tasks/nqueens.c: --- omp-tasks/nqueens/nqueens.c.orig Tue May 11 10:22:23 2010
+++ omp-tasks/nqueens/nqueens.c Tue Jan 11 20:14:13 2011
@@ -31,6 +31,7 @@
#include <alloca.h>
#include "bots.h"
#include <omp.h>
+#include <assert.h>
/* Checking information */
@@ -63,15 +64,17 @@
* <a> contains array of <n> queen positions. Returns 1
* if none of the queens conflict, and returns 0 otherwise.
*/
-int ok(int n, char *a)
+int ok(int n, char *a, int size_a)
{
int i, j;
char p, q;
for (i = 0; i < n; i++) {
+ assert(i < size_a);
p = a[i];
for (j = i + 1; j < n; j++) {
+ assert(j < size_a);
q = a[j];
if (q == p || q == p - (j - i) || q == p + (j - i))
return 0;
@@ -80,7 +83,7 @@
return 1;
}
-void nqueens_ser (int n, int j, char *a, int *solutions)
+void nqueens_ser (int n, int j, char *a, int *solutions, int size_a)
{
int i,res;
@@ -103,9 +106,10 @@
for (i = 0; i < n; i++) {
{
/* allocate a temporary array and copy <a> into it */
+ assert(j < size_a);
a[j] = i;
- if (ok(j + 1, a)) {
- nqueens_ser(n, j + 1, a,&res);
+ if (ok(j + 1, a, size_a)) {
+ nqueens_ser(n, j + 1, a,&res, size_a);
#ifndef FORCE_TIED_TASKS
*solutions += res;
#endif
@@ -217,7 +221,7 @@
#elif defined(MANUAL_CUTOFF)
-void nqueens(int n, int j, char *a, int *solutions, int depth)
+void nqueens(int n, int j, char *a, int *solutions, int depth, int size_a)
{
int i;
int *csols;
@@ -249,13 +253,14 @@
char * b = alloca((j + 1) * sizeof(char));
memcpy(b, a, j * sizeof(char));
b[j] = i;
- if (ok(j + 1, b))
- nqueens(n, j + 1, b,&csols[i],depth+1);
+ if (ok(j + 1, b, j+1))
+ nqueens(n, j + 1, b,&csols[i],depth+1, j+1);
}
} else {
+ assert(j < size_a);
a[j] = i;
- if (ok(j + 1, a))
- nqueens_ser(n, j + 1, a,&csols[i]);
+ if (ok(j + 1, a, size_a))
+ nqueens_ser(n, j + 1, a,&csols[i], size_a);
}
}
@@ -324,7 +329,7 @@
char *a;
a = alloca(size * sizeof(char));
- nqueens(size, 0, a, &total_count,0);
+ nqueens(size, 0, a, &total_count,0, size);
}
#ifdef FORCE_TIED_TASKS
#pragma omp atomic
2. Compile MANUAL_CUTOFF version with the DEBUG macro defined and run the
$ cc -xopenmp -c -I../..//common -fast -DMANUAL_CUTOFF -I. -o main-manual.o \
../..//common/bots_main.c -DCDATE="\"2011/01/11;19:57\"" -DCC="\"cc \
-xopenmp\"" -DLD="\"cc -xopenmp\"" -DCMESSAGE="\"\"" -DLDFLAGS="\"-fast \"" \
-DCFLAGS="\"-c -I../..//common -fast -DMANUAL_CUTOFF -I.\"" -DDEBUG
$ cc -xopenmp -c -I../..//common -fast -DMANUAL_CUTOFF -o nqueens-manual.o \
nqueens.c -DDEBUG
$ cc -xopenmp -fast -o ../..//bin/nqueens.suns.omp-tasks-manual main-manual.o\
nqueens-manual.o ../..//common/bots_common.o -DDEBUG
$ bin/nqueens.suns.omp-tasks-manual -n 10 -v 1 -c
Assertion failed: j < size_a, file nqueens.c, line 260
Computing N-Queens algorithm (n=10) Abort(coredump)
$ awk 'NR >=255 && NR <=265' omp-tasks/nqueens/nqueens.c
b[j] = i;
if (ok(j + 1, b, j+1))
nqueens(n, j + 1, b,&csols[i],depth+1, j+1);
}
} else {
assert(j < size_a);
a[j] = i;
if (ok(j + 1, a, size_a))
nqueens_ser(n, j + 1, a,&csols[i], size_a);
}
}
|
||
Description
The MANUAL_CUTOFF version of the BOTS 1.1 omp-tasks/nqueens/nqueens.c code
contains out-of-bounds array accesses (see below).
Changing the alloca() at line 249 to:
char * b = alloca((n + 1) * sizeof(char));
gets rid of the assertion failures introduced by the patch provided in the
"experimental evidence" section, which adds calls to "assert()" to verify
array bounds.
Change History
Note: See
TracTickets for help on using
tickets.
