The program runs without errors when using only one thread. However, when using 2 or more threads, I get one of three errors depending on the run. Either segmentation fault, double free or corruption or free(): invalid pointer occurs. The code in main that matters is in thread_routine. Any help is appreciated.
Backtrace from gdb in the case of segmentation fault:
#0 __memmove_sse2_unaligned_erms () at ../sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S:525
#1 0x0000555555557153 in std::__copy_move::__copy_m (__result=, __last=, __first=) at /usr/include/c++/7/bits/stl_algobase.h:368
#2 std::__copy_move_a (__result=, __last=, __first=) at /usr/include/c++/7/bits/stl_algobase.h:386
#3 std::__copy_move_a2 (__result=, __last=0x55555577e910, __first=) at /usr/include/c++/7/bits/stl_algobase.h:424
#4 std::copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_algobase.h:456
#5 std::__uninitialized_copy::__uninit_copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:101
#6 std::uninitialized_copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:134
#7 std::__uninitialized_copy_a, particle_t**, particle_t*> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:289
#8 std::__uninitialized_move_if_noexcept_a > (__alloc=..., __result=, __last=0x55555577e910, __first=) at /usr/include/c++/7/bits/stl_uninitialized.h:312
#9 std::vector >::_M_realloc_insert (this=0x555555779088, __position=0x55555576b170, __args#0=@0x7ffff6e84e18: 0x555555776000) at /usr/include/c++/7/bits/vector.tcc:424
#10 0x00005555555569ca in std::vector >::push_back (__x=@0x7ffff6e84e18: 0x555555776000, this=) at /usr/include/c++/7/bits/stl_vector.h:948
#11 Grid::addParticleToGrid (this=0x555555776a00, param=) at Grid.cpp:50
#12 0x00005555555559b1 in thread_routine (pthread_id=) at pthreads.cpp:67
#13 0x00007ffff7bbd6db in start_thread (arg=0x7ffff6e85700) at pthread_create.c:463
#14 0x00007ffff6fa788f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95
Trace for free() invalid pointer
#0 __memmove_sse2_unaligned_erms () at ../sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S:486
#1 0x0000555555557153 in std::__copy_move::__copy_m (__result=, __last=, __first=) at /usr/include/c++/7/bits/stl_algobase.h:368
#2 std::__copy_move_a (__result=, __last=, __first=) at /usr/include/c++/7/bits/stl_algobase.h:386
#3 std::__copy_move_a2 (__result=, __last=0x55555577ec38, __first=) at /usr/include/c++/7/bits/stl_algobase.h:424
#4 std::copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_algobase.h:456
#5 std::__uninitialized_copy::__uninit_copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:101
#6 std::uninitialized_copy, particle_t**> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:134
#7 std::__uninitialized_copy_a, particle_t**, particle_t*> (__result=, __last=..., __first=...) at /usr/include/c++/7/bits/stl_uninitialized.h:289
#8 std::__uninitialized_move_if_noexcept_a > (__alloc=..., __result=, __last=0x55555577ec38, __first=) at /usr/include/c++/7/bits/stl_uninitialized.h:312
#9 std::vector >::_M_realloc_insert (this=0x55555577bdd0, __position=0x0, __args#0=@0x7fffffffdb48: 0x55555576e320) at /usr/include/c++/7/bits/vector.tcc:424
#10 0x00005555555569ca in std::vector >::push_back (__x=@0x7fffffffdb48: 0x55555576e320, this=) at /usr/include/c++/7/bits/stl_vector.h:948
#11 Grid::addParticleToGrid (this=0x555555776a00, param=) at Grid.cpp:50
#12 0x00005555555559b1 in thread_routine (pthread_id=) at pthreads.cpp:67
#13 0x0000555555555575 in main (argc=, argv=) at pthreads.cpp:137
Trace for double free or corruption()
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1 0x00007ffff6ec6801 in __GI_abort () at abort.c:79
#2 0x00007ffff6f0f897 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff703cb9a "%s\n") at ../sysdeps/posix/libc_fatal.c:181
#3 0x00007ffff6f1690a in malloc_printerr (str=str@entry=0x7ffff703e828 "double free or corruption (fasttop)") at malloc.c:5350
#4 0x00007ffff6f1e004 in _int_free (have_lock=0, p=0x55555577e360, av=0x7ffff7271c40 ) at malloc.c:4230
#5 __GI___libc_free (mem=0x55555577e370) at malloc.c:3124
#6 0x000055555555718d in __gnu_cxx::new_allocator::deallocate (this=, __p=) at /usr/include/c++/7/ext/new_allocator.h:125
#7 std::allocator_traits >::deallocate (__a=..., __n=, __p=) at /usr/include/c++/7/bits/alloc_traits.h:462
#8 std::_Vector_base >::_M_deallocate (this=, __n=, __p=) at /usr/include/c++/7/bits/stl_vector.h:180
#9 std::vector >::_M_realloc_insert (this=0x55555577a7e0, __position=0x4, __args#0=@0x7ffff6e84e18: 0x555555776480) at /usr/include/c++/7/bits/vector.tcc:448
#10 0x00005555555569ca in std::vector >::push_back (__x=@0x7ffff6e84e18: 0x555555776480, this=) at /usr/include/c++/7/bits/stl_vector.h:948
#11 Grid::addParticleToGrid (this=0x555555776a00, param=) at Grid.cpp:50
#12 0x00005555555559b1 in thread_routine (pthread_id=) at pthreads.cpp:67
#13 0x00007ffff7bbd6db in start_thread (arg=0x7ffff6e85700) at pthread_create.c:463
#14 0x00007ffff6fa788f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95
Main code:
#include
#include
#include
#include
#include
#include "common.h"
#include "Grid.h"
std::unique_ptr> grid = nullptr;
//
// global variables
//
int n, n_threads, saveFreq;
particle_t *particles;
FILE *fsave;
pthread_barrier_t barrier;
//
// check that pthreads routine call was successful
//
#define P( condition ) {if( (condition) != 0 ) { printf( "\n FAILURE in %s, line %d\n", __FILE__, __LINE__ );exit( 1 );}}
//
// This is where the action happens
//
void *thread_routine( void *pthread_id )
{
int thread_id = *(int*)pthread_id;
int particles_per_thread = (n + n_threads - 1) / n_threads;
int first = min( thread_id * particles_per_thread, n );
int last = min( (thread_id+1) * particles_per_thread, n );
//
// simulate a number of time steps
//
for( int step = 0; step < NSTEPS; step++ )
{
//
// compute forces
//
for( int i = first; i < last; i++ )
{
particles[i].ax = particles[i].ay = 0;
std::unique_ptr> neighbours = grid->getNeighbouringParticles(particles[i]);
for (long j = 0; j < neighbours->size(); j++) {
particle_t *p = neighbours->at(j);
particle_t part = *p;
apply_force( particles[i], part);
}
}
pthread_barrier_wait( &barrier );
if (thread_id == 0) {
grid->clearGrid();
}
pthread_barrier_wait( &barrier );
//
// move particles
//
for( int i = first; i < last; i++ ) {
move( particles[i] );
grid->addParticleToGrid(&particles[i]);
}
pthread_barrier_wait( &barrier );
//
// save if necessary
//
if( thread_id == 0 && fsave && (step%saveFreq) == 0 )
save( fsave, n, particles );
}
return NULL;
}
//
// benchmarking program
//
int main( int argc, char **argv )
{
//
// process command line
//
if( find_option( argc, argv, "-h" ) >= 0 )
{
printf( "Options:\n" );
printf( "-h to see this help\n" );
printf( "-n to set the number of particles\n" );
printf( "-p to set the number of threads\n" );
printf( "-o to specify the output file name\n" );
printf( "-f to specify the savefreq\n" );
return 0;
}
n = read_int( argc, argv, "-n", 1000 );
n_threads = read_int( argc, argv, "-p", 1 );
char *savename = read_string( argc, argv, "-o", NULL );
saveFreq = read_int( argc, argv, "-f", SAVEFREQ );
//
// allocate resources
//
fsave = savename ? fopen( savename, "w" ) : NULL;
particles = (particle_t*) malloc( n * sizeof(particle_t) );
set_size( n );
init_particles( n, particles );
grid = std::unique_ptr(new Grid(n, size));
grid->addParticlesToGrid(particles, n);
pthread_attr_t attr;
P( pthread_attr_init( &attr ) );
P( pthread_barrier_init( &barrier, NULL, n_threads ) );
int *thread_ids = (int *) malloc( n_threads * sizeof( int ) );
for( int i = 0; i < n_threads; i++ )
thread_ids[i] = i;
pthread_t *threads = (pthread_t *) malloc( n_threads * sizeof( pthread_t ) );
//
// do the parallel work
//
double simulation_time = read_timer( );
for( int i = 1; i < n_threads; i++ )
P( pthread_create( &threads[i], &attr, thread_routine, &thread_ids[i] ) );
thread_routine( &thread_ids[0] );
for( int i = 1; i < n_threads; i++ )
P( pthread_join( threads[i], NULL ) );
simulation_time = read_timer( ) - simulation_time;
printf( "n = %d, n_threads = %d, simulation time = %g seconds\n", n, n_threads, simulation_time );
//
// release resources
//
P( pthread_barrier_destroy( &barrier ) );
P( pthread_attr_destroy( &attr ) );
free( thread_ids );
free( threads );
free( particles );
if( fsave )
fclose( fsave );
return 0;
}
My Grid Class
//
// Created by sharf on 2019-02-26.
//
#include
#include
#include
#include
#include "Grid.h"
Grid::Grid(int len, double width) :
gridWidth(width)
{
numColumns = (long) ceil(sqrt(len));
numRows = (long) ceil(len / (double)numColumns);
columnWidth = width/((double)numColumns - 1);
numBoxes = numRows * numColumns;
boxes = std::unique_ptr[]>(new std::vector[numBoxes]);
}
Grid::~Grid()
{
}
long Grid::getSqrIdFromCoord(double x, double y)
{
long iX = (long) floor(x/getColWidth());
long iY = (long) floor(y/getColWidth());
return iX + iY*getNumColumns();
}
long Grid::getNumBoxes() const { return numBoxes; }
double Grid::getGridWidth() const { return gridWidth; }
long Grid::getNumColumns() const { return numColumns; }
long Grid::getNumRows() const { return numRows; }
double Grid::getColWidth() const { return columnWidth; }
void Grid::clearGrid() {
for (long i = 0; i < numBoxes; i++) {
boxes[i].clear();
}
}
void Grid::addParticleToGrid(particle_t *param) {
long index = getSqrIdFromCoord(param->x, param->y);
boxes[index].push_back(param);
}
void Grid::addParticlesToGrid(particle_t *particles, int numParticles)
{
for (long i = 0; i < numParticles; i++)
{
long index = getSqrIdFromCoord(particles[i].x, particles[i].y);
boxes[index].push_back(&particles[i]);
}
}
std::unique_ptr> Grid::getNeighbouringParticles(particle_t param) {
long particleIndex = getSqrIdFromCoord(param.x, param.y);
std::vector particles;
// Get right neighbour if possible
if ((particleIndex % numColumns) < (numColumns - 1)) {
for (int i = 0; i < boxes[particleIndex+1].size(); i++) {
particles.push_back(boxes[particleIndex+1][i]);
}
}
// Get left neighbour if possible
if ((particleIndex % numColumns) > 0) {
for (int i = 0; i < boxes[particleIndex-1].size(); i++)
particles.push_back(boxes[particleIndex-1][i]);
}
// Get top neighbour if possible
long rowIndex = ((long) floor(particleIndex / numColumns));
if (rowIndex < (numRows - 1)) {
for (int i = 0; i < boxes[particleIndex + numColumns].size(); i++)
particles.push_back(boxes[particleIndex + numColumns][i]);
}
// Get bot neighbour if possible
if (rowIndex > 0) {
for (int i = 0; i < boxes[particleIndex - numColumns].size(); i++)
particles.push_back(boxes[particleIndex - numColumns][i]);
}
// Get top right neighbour if possible
if (rowIndex < (numRows - 1) && (particleIndex % numColumns) < (numColumns - 1)) {
for (int i = 0; i < boxes[particleIndex + numColumns + 1].size(); i++)
particles.push_back(boxes[particleIndex + numColumns + 1][i]);
}
// Get top left neighbour if possible
if ((particleIndex % numColumns) > 0 && rowIndex < (numRows - 1)) {
for (int i = 0; i < boxes[particleIndex + numColumns - 1].size(); i++)
particles.push_back(boxes[particleIndex + numColumns - 1][i]);
}
// Get bot right neighbour if possible
if (rowIndex > 0 && (particleIndex % numColumns) < (numColumns - 1)) {
for (int i = 0; i < boxes[particleIndex - numColumns + 1].size(); i++) {
particles.push_back(boxes[particleIndex - numColumns + 1][i]);
}
}
// Get bot left neighbour if possible
if (rowIndex > 0 && (particleIndex % numColumns) > 0) {
for (int i = 0; i < boxes[particleIndex - numColumns - 1].size(); i++)
particles.push_back(boxes[particleIndex - numColumns - 1][i]);
}
return std::unique_ptr> (new std::vector(particles));
}
Grid.h
#ifndef PROJECT_GRID_H
#define PROJECT_GRID_H
#include
#include "common.h"
#include
class Grid {
std::unique_ptr[]> boxes;
long numBoxes, numColumns, numRows;
double gridWidth, columnWidth;
long getSqrIdFromCoord(double x, double y);
public:
Grid(int len, double width);
~Grid();
long getNumBoxes() const;
long getNumRows() const;
long getNumColumns() const;
double getGridWidth() const;
double getColWidth() const;
void clearGrid();
void addParticlesToGrid(particle_t *particles, int numParticles);
std::unique_ptr> getNeighbouringParticles(particle_t param);
void addParticleToGrid(particle_t *param);
};
#endif //PROJECT_GRID_H
Common.h
#ifndef __CS267_COMMON_H__
#define __CS267_COMMON_H__
extern double size;
inline int min( int a, int b ) { return a < b ? a : b; }
inline int max( int a, int b ) { return a > b ? a : b; }
//
// saving parameters
//
const int NSTEPS = 1000;
const int SAVEFREQ = 10;
//
// particle data structure
//
typedef struct
{
double x;
double y;
double vx;
double vy;
double ax;
double ay;
} particle_t;
//
// timing routines
//
double read_timer( );
double findMedian(double *arr, int len);
//
// simulation routines
//
void set_size( int n );
void init_particles( int n, particle_t *p );
void apply_force( particle_t &particle, particle_t &neighbor );
void move( particle_t &p );
//
// I/O routines
//
FILE *open_save( char *filename, int n );
void save( FILE *f, int n, particle_t *p );
//
// argument processing routines
//
int find_option( int argc, char **argv, const char *option );
int read_int( int argc, char **argv, const char *option, int default_value );
char *read_string( int argc, char **argv, const char *option, char *default_value );
#endif
Common.cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include "common.h"
double size;
//
// tuned constants
//
#define density 0.0005
#define mass 0.01
#define cutoff 0.01
#define min_r (cutoff/100)
#define dt 0.0005
//
// timer
//
double read_timer( )
{
static bool initialized = false;
static struct timeval start;
struct timeval end;
if( !initialized )
{
gettimeofday( &start, NULL );
initialized = true;
}
gettimeofday( &end, NULL );
return (end.tv_sec - start.tv_sec) + 1.0e-6 * (end.tv_usec - start.tv_usec);
}
// compares two doubles and returns if theyre equal
int comp(const void * x, const void * y)
{
double f = *((double *)x);
double s = *((double *)y);
if (f > s) return 1;
if (f < s) return -1;
return 0;
}
// Finds a media from a sorted array.
double findMedian(double *arr, int len) {
qsort(arr, len, sizeof(double), comp);
if (len % 2 != 0)
return arr[len/2];
return (arr[len/2] + arr[(len/2) - 1])/2;
}
//
// keep density constant
//
void set_size( int n )
{
size = sqrt( density * n );
}
//
// Initialize the particle positions and velocities
//
void init_particles( int n, particle_t *p )
{
srand48( time( NULL ) );
int sx = (int)ceil(sqrt((double)n));
int sy = (n+sx-1)/sx;
int *shuffle = (int*)malloc( n * sizeof(int) );
for( int i = 0; i < n; i++ )
shuffle[i] = i;
for( int i = 0; i < n; i++ )
{
//
// make sure particles are not spatially sorted
//
int j = lrand48()%(n-i);
int k = shuffle[j];
shuffle[j] = shuffle[n-i-1];
//
// distribute particles evenly to ensure proper spacing
//
p[i].x = size*(1.+(k%sx))/(1+sx);
p[i].y = size*(1.+(k/sx))/(1+sy);
//
// assign random velocities within a bound
//
p[i].vx = drand48()*2-1;
p[i].vy = drand48()*2-1;
}
free( shuffle );
}
//
// interact two particles
//
void apply_force( particle_t &particle, particle_t &neighbor )
{
double dx = neighbor.x - particle.x;
double dy = neighbor.y - particle.y;
double r2 = dx * dx + dy * dy;
if( r2 > cutoff*cutoff )
return;
r2 = fmax( r2, min_r*min_r );
double r = sqrt( r2 );
//
// very simple short-range repulsive force
//
double coef = ( 1 - cutoff / r ) / r2 / mass;
particle.ax += coef * dx;
particle.ay += coef * dy;
}
//
// integrate the ODE
//
void move( particle_t &p )
{
//
// slightly simplified Velocity Verlet integration
// conserves energy better than explicit Euler method
//
p.vx += p.ax * dt;
p.vy += p.ay * dt;
p.x += p.vx * dt;
p.y += p.vy * dt;
//
// bounce from walls
//
while( p.x < 0 || p.x > size )
{
p.x = p.x < 0 ? -p.x : 2*size-p.x;
p.vx = -p.vx;
}
while( p.y < 0 || p.y > size )
{
p.y = p.y < 0 ? -p.y : 2*size-p.y;
p.vy = -p.vy;
}
}
//
// I/O routines
//
void save( FILE *f, int n, particle_t *p )
{
static bool first = true;
if( first )
{
fprintf( f, "%d %g\n", n, size );
first = false;
}
for( int i = 0; i < n; i++ )
fprintf( f, "%g %g\n", p[i].x, p[i].y );
}
//
// command line option processing
//
int find_option( int argc, char **argv, const char *option )
{
for( int i = 1; i < argc; i++ )
if( strcmp( argv[i], option ) == 0 )
return i;
return -1;
}
int read_int( int argc, char **argv, const char *option, int default_value )
{
int iplace = find_option( argc, argv, option );
if( iplace >= 0 && iplace < argc-1 )
return atoi( argv[iplace+1] );
return default_value;
}
char *read_string( int argc, char **argv, const char *option, char *default_value )
{
int iplace = find_option( argc, argv, option );
if( iplace >= 0 && iplace < argc-1 )
return argv[iplace+1];
return default_value;
}
Answer
Looking at all three stack traces, the common area they all have that is your code (before getting lost in the world of vectors) is Grid::addParticleToGrid, specifically the boxes[index].push_back(param); line. Since boxes[index] is a std::vector, and vectors are not thread safe, you're getting the same index value in multiple threads, resulting in multiple threads trying to modify the vector at the same time.
Since this is a homework problem, I'll leave it as an "exercise for the reader" to figure out how to fix the problem.
No comments:
Post a Comment