[Gems-users] XACT consistency checker problem

[Ricardo Quislant del Barrio <quislant@xxxxxxxxx>]

Hi, i have collected the following error when simulating a Minimun 
Spanning Tree solver:
############################################################################
2 XACT CONSISTENCY CHECKER: FAILED 0x[0x3c023d80, line 0x3c023d80] 
ACCESS TYPE: LD IN WRITE SET OF 10
2 XACT CONSISTENCY CHECK FAILURE DUE TO OVERLAP BETWEEN ESCAPE ACTIONS 
AND TRANSACTIONS  Address: [0x3c023d80, line 0x3c023d80] PC: [0x12b70, 
line 0x12b40]
2 XACT CONSISTENCY CHECKER: FAILED 0x[0x3c023d80, line 0x3c023d80] 
ACCESS TYPE: LD_XACT IN WRITE SET OF 10
simics-common: log_tm/TransactionSimicsProcessor.C:399: void 
TransactionSimicsProcessor::xactIsolationCheck(memory_transaction_t*, 
CacheRequestType): Assertion `false' failed.
Abort (SIGABRT) in main thread
The simulation state has been corrupted. Simulation cannot continue.
Please restart Simics.
[0] Makegraph. Transaccion Command aborted
Starting command line. (May have skipped commands in script files.)
fork failed: Cannot allocate memory
Unable to start readhist; only limited command line editing available
[cpu2] v:0x0000000000011d7c p:0x0003ed11d7c  lduw [%l3 + 428], %o4
Setting new inspection cpu: cpu2
simics> Traceback (most recent call last):
 File "../../../gen-scripts/mfacet.py", line 308, in 
console_branch_internal
   wait_for_string(get_console(), __prompt)
 File 
"/opt/virtutech/simics-3.0.29/x86-linux/lib/python/text_console_common.py", 
line 10, in wait_for_string
   wait_for_obj_hap("Xterm_Break_String", obj, break_id)
 File "/opt/virtutech/simics-3.0.29/x86-linux/lib/python/cli_impl.py", 
line 3374, in wait_for_obj_hap
   return wait_for_hap_common([hap_name, name, idx0])
 File "/opt/virtutech/simics-3.0.29/x86-linux/lib/python/cli_impl.py", 
line 3352, in wait_for_hap_common
   raise SimExc_Break, "Script branch interrupted"
sim_core.SimExc_Break: Script branch interrupted
Exception in python branch
############################################################################

The code i have simulated is the next:
##########################################################
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
/**********#include "txlocks.h"**********/
#include "transaction.h"

#define CONST_m1 10000
#define CONST_b 31415821
#define RANGE 2048

/* Edge data structure of the input graph */
typedef struct edge_st {
 unsigned int vert;
 int dist;
 struct edge_st *next;
} *Edge;

/* Vertex data structure of the input graph */
typedef struct vert_st {
 int vid;
 int mindist;
 int minvid;
 Edge edg;
 struct vert_st *next;
} *Vertex;

/* Auxiliary vertex data structure */
typedef struct vertex_pos {
 Vertex vertexptr;
 int vertexidx;
} VertexPos;

int vid_cnt = 0;
/* Input graph: Complete weighted undirected graph */
Vertex *graph;
int gsize = 0; /* number of vertices */

Vertex mst_vertex = NULL;
Vertex mst_vertexR = NULL;
int insertion_cnt;
/* Output MST */
Vertex *mst;

/* Number of threads */
int num_threads;

/* Other shared variables */
VertexPos vertpos_g;
int first_reduc;
extern volatile int sense; /*Definida en ../common/transcation.c*/

/* pThreads variables */
pthread_attr_t pthread_custom_attr;
/*pthread_barrier_t barr;*/

static int mult(int p, int q)
{
 int p1, p0, q1, q0;

 p1 = p/CONST_m1;
 p0 = p%CONST_m1;
 q1 = q/CONST_m1;
 q0 = q%CONST_m1;
 return (((p0*q1+p1*q0)%CONST_m1)*CONST_m1+p0*q0);
}

static int d_rand(int seed)
{
 int tmp;
 tmp = (mult(seed,CONST_b)+1);
 return tmp;
}

static int compute_dist(int i, int j, int numvert)
{
 int less, gt;
 if (i < j)
 {
   less = i;
   gt = j;
 }
 else
 {
   less = j;
   gt = i;
 }
 return (d_rand(less*numvert+gt)%RANGE)+1;
}

/* Insert an edge in the edge list of the graph */
void EdgeInsert(Vertex vorg,Edge edg)
{
 Edge tmp, tmpp;

 tmpp = tmp = vorg->edg;
 if (tmp != NULL)
 {
   tmp = tmp->next;
   while (tmp != NULL)
   {
     tmpp = tmpp->next;
     tmp = tmp->next;
   }
   tmpp->next = edg;
 }
 else vorg->edg = edg;
}

/* Insert a vertex in the vertex list of the graph */
void VertexInsert(Vertex ver)
{
 Vertex tmp,tmpp;

 if (*graph == NULL) *graph = ver;
 else
 {
   tmpp = *graph;
   tmp = tmpp->next;
   while (tmp != NULL)
   {
     tmpp = tmpp->next;
     tmp = tmp->next;
   }
   tmpp->next = ver;
 }
}

/* Get a vertex from the vertex list */
VertexPos VertexGet()
{
 VertexPos vp;

 if (vertpos_g.vertexptr != NULL)
 {
   if (vertpos_g.vertexptr == (Vertex) -1)
   {
     vertpos_g.vertexptr = *graph;
     vertpos_g.vertexidx = 0;
   }
   else
   {
     vertpos_g.vertexptr = vertpos_g.vertexptr->next;
     vertpos_g.vertexidx++;
   }
 }
 vp.vertexptr = vertpos_g.vertexptr;
 vp.vertexidx = vertpos_g.vertexidx;
 return vp;
}

/* Vertex block partitioning of the graph */
void GraphPartition(int myid,int tsize)
{
 Vertex tmp, tmpp;
 int count, local_sense = sense;

   /*printf("[%d] GraphPartition phase 1: Vertex block 
partitioning\n",myid);*/
 tmpp = tmp = *graph;
 count = myid * tsize;
 if (count)
 {
   tmp = tmp->next;
   count--;
 }
 while (count-- > 0)
 {
   tmp = tmp->next;
   tmpp = tmpp->next;
 }
 *(graph+myid) = tmp;
 /* printf("[%d] *(graph+%d) 0x%x\n",myid,myid,*(graph+myid)); */

 /* Threads waiting until graph partitioned */
 /*pthread_barrier_wait(&barr);*/
   Barrier_non_breaking(&local_sense, myid, num_threads);

 /* printf("[%d] GraphPartition phase 2: Isolating subgraphs\n",myid); */
 if (tmpp != tmp) tmpp->next = NULL;
 /*printf("[%d] GraphPartition done.\n",myid);*/
}

/* Making the input graph in parallel (vertex parallelism) */
void MakeGraph(int myid,int tsize)
{
 Vertex ver, tmp;
 VertexPos vp;
 Edge edg;
 int dist;
 int i, local_sense=sense;

 /*printf("[%d] MakeGraph phase 1: Vertices (%d verts per 
thread)\n",myid,tsize);*/
 /* Creating in parallel the vertex list */
 for (i=0; i<tsize; i++)
 {
   ver = (Vertex) malloc(sizeof(*ver));
   ver->mindist = 9999999;
   ver->minvid = 0;
   ver->edg = NULL;
   ver->next = NULL;
   BEGIN_TRANSACTION(0);
   ver->vid = vid_cnt++;
   VertexInsert(ver);
   COMMIT_TRANSACTION(0);
 }

 /* Threads waiting until all vertices built */
 /*pthread_barrier_wait(&barr);*/
   Barrier_non_breaking(&local_sense, myid, num_threads);
   tmp = *graph;
   i=0;
   while(tmp!=NULL){ tmp = tmp->next; i++;}
       printf("[%d] Mis %d vertices creados.Total:%d\n", myid, tsize,i);

 /* printf("[%d] MakeGraph phase 2: Edges\n",myid); */
 /* Creating the edge list in parallel for each vertex */
 BEGIN_TRANSACTION(1);
 vp = VertexGet();
 COMMIT_TRANSACTION(1);
 while (vp.vertexptr != NULL)
 {
   for (ver=*graph,i=0; ver!=NULL; ver=ver->next,i++)
   {
     if (i != vp.vertexidx)
     {
       dist = compute_dist(i,vp.vertexidx,num_threads*tsize);
       edg = (Edge) malloc(sizeof(*edg));
       edg->vert = (unsigned int) ver;
       edg->dist = dist;
       edg->next = NULL;
       EdgeInsert(vp.vertexptr,edg);
       /*printf("[%d] Edge orig 0x%x dest 0x%x dist 
%d\n",myid,vp.vertexptr,ver,dist);*/
     }
   }
   printf("[%d] Makegraph. Transaccion inicio\n",myid);
   BEGIN_TRANSACTION(2);
   vp = VertexGet();
   COMMIT_TRANSACTION(2);
   printf("[%d] Makegraph. Transaccion final\n",myid);
 }

 /* printf("[%d] MakeGraph done\n",myid); */
}

/* Obtaining weight of the edge between two vertices */
int distance(Vertex ver, Vertex vref)
{
 Edge edge;
 Vertex v;
 int done = 0;

 edge = ver->edg;
 while (!done)
 {
   if (edge == NULL) done = 2;
   else if (vref == (Vertex) edge->vert) done = 1;
   else edge = edge->next;
 }
 if (done == 2) return 0;
 else return edge->dist;
}

/* Obtaining the nearest vertex in a subgraph */
Vertex mstVertexExtract(int myid, Vertex ver, Vertex vref)
{
 Vertex retval;
 Vertex tmp, prev;
 int dist,dist2;

 /* printf("[%d] ver 0x%x vref 0x%x\n",myid,ver,vref); */
 /* If the subgraph is null return an invalid vertex */
 if (!ver)
 {
   retval = (Vertex) malloc (sizeof(*retval));
   retval->mindist = 999999;
   retval->minvid = 0;
   return retval;
 }

 /* Select the first vertex in the subgraph as the default nearest one */
 retval = ver;
 dist = distance(ver,vref);
 if (dist)
 {
   if (dist < retval->mindist)
   {
     retval->mindist = dist;
     retval->minvid = vref->vid;
   }
 }
 else printf("[%d] FAIL: Vertex not found\n",myid);

 /* Check the rest of the vertices in the subgraph and select the 
nearest one */
 prev = ver;
 for (tmp=ver->next; tmp; prev=tmp,tmp=tmp->next)
 {
   if (tmp == vref)
   {
     Vertex next;

     next = tmp->next;
     prev->next = next;
   }
   else
   {
      dist2 = tmp->mindist;
      dist = distance(tmp,vref);
      /* printf("[%d] Found dist %d from inserted 0x%x to vertex 0x%x 
(tmp)\n",dist,inserted,tmp); */
      if (dist)
      {
        if (dist < dist2)
        {
          tmp->mindist = dist;
          tmp->minvid = vref->vid;
          dist2 = dist;
        }
      }
      else printf("[%d] FAIL: Vertex not found\n",myid);
      if (dist2 < retval->mindist) retval = tmp;
   }
 }

 /* printf("[%d] mstVE: ver 0x%x vref 0x%x retval 0x%x retval->mindist 
%d\n",myid,ver,vref,retval,retval->mindist); */
 return retval;
}

/* Insert a new node in the MST */
void mstInsert(Vertex ver, Vertex *mstv)
{
 Vertex tmp, tmpp, tmppp;

 insertion_cnt++;

 tmppp = NULL;
 tmpp = *mst;
 tmp = tmpp->next;
 while (tmp != NULL)
 {
   if (tmppp == NULL) tmppp = *mst;
   else tmppp = tmppp->next;
   tmpp = tmpp->next;
   tmp = tmp->next;
 }

 if (insertion_cnt == 1)
 {
   /* The first thread append the new locally nearest node */
   tmpp->next = (Vertex) malloc(sizeof(*tmpp));
   tmp = tmpp->next;
   tmp->vid = ver->vid;
   tmp->mindist = ver->mindist;
   tmp->minvid = ver->minvid;
   tmp->next = NULL;
   *mstv = ver;
 }
 else
 {
   /* The rest of threads compare their node with the appended one and 
replaced it if nearer */
   if (ver->mindist < tmpp->mindist)
   {
     tmppp->next = (Vertex) malloc(sizeof(*tmpp));
     tmp = tmppp->next;
     tmp->vid = ver->vid;
     tmp->mindist = ver->mindist;
     tmp->minvid = ver->minvid;
     tmp->next = NULL;
     *mstv = ver;
   }
 }
 if (insertion_cnt == num_threads) insertion_cnt = 0;
}

/* Computes an MST from the input graph using a greedy approach */
void ComputeMst(int myid, int tsize)
{
 Vertex ver, trv;
 int i/*, sense, sense_r*/, local_sense=sense, senseRev;

 /* printf("[%d] Compute MST phase 1: Inserting first (arbitrary) 
vertex of MST\n",myid); */
 /* Select an arbitrary vertex as the root of the MST */
 insertion_cnt = 0;
 gsize = tsize*num_threads;
 ver = *(graph+myid);
 if (myid == 0)
 {
   *mst = (Vertex) malloc(sizeof(*ver));
   (*mst)->vid = ver->vid;
   (*mst)->mindist = 0;
   (*mst)->minvid = 0;
   (*mst)->next = NULL;
   mst_vertex = ver;
   /* printf("[%d] ver 0x%x mindist %d\n",myid,ver,(*mst)->mindist); */
   ver = ver->next;
   tsize--;
 }
 /*printf("[%d] ver 0x%x mst_vertex 0x%x 
0x%x\n",myid,ver,mst_vertex,mst_vertexR);*/
 /* Threads start together computing a MST */
 /*pthread_barrier_wait(&barr);*/
   Barrier_non_breaking(&local_sense, myid, num_threads);

 /* printf("[%d] Compute MST phase 2\n",myid); */
 /* Find next vertex in the MST using a one-by-one approach (greedy) */
 /* Use a sense reversal technique to avoid two barrier fences */
 for (i=0, senseRev=1; i<gsize-1; i++)
 {
   if (senseRev)
   {
     if (mst_vertex == ver) ver = ver->next;
     trv = mstVertexExtract(myid,ver,mst_vertex);
   }
   else
   {
     if (mst_vertexR == ver) ver = ver->next;
     trv = mstVertexExtract(myid,ver,mst_vertexR);
   }
   /* printf("[%d] i %d trv 0x%x\n",myid,i,trv); */
   BEGIN_TRANSACTION(3);
   if (senseRev) mstInsert(trv, &mst_vertexR);
   else mstInsert(trv, &mst_vertex);
   COMMIT_TRANSACTION(3);
       Barrier_non_breaking(&local_sense, myid, num_threads);
   /*pthread_barrier_wait(&barr);*/
   senseRev = !senseRev;
 }
}

/* Main parallel routine */
void *Graph_MST(void *tid)
{
 int myid;
 int tsize;
   int local_sense = sense;
 /*time_t stime1, etime1;
 time_t stime2, etime2;
 time_t stime3, etime3;*/

 myid = *((int*) tid);
 tm_bind_to_cabinet(myid+1);
 Barrier_breaking(&local_sense, myid, num_threads);
 set_transaction_registers(myid);

 tsize = gsize/num_threads;

   BEGIN_WORKLOAD_TRANSACTION;
 /* Computing input graph */
 printf("[%d] Making graph of size %d\n",myid,gsize);
 /*stime1 = time(NULL);*/
 MakeGraph(myid,tsize);
   /*etime1 = time(NULL);*/
 printf("[%d] Graph created.\n", myid);

 /* Partitioning input graph */
 /* printf("[%d] Partition graph across threads\n",myid); */
 /*stime2 = time(NULL);*/
 GraphPartition(myid,tsize);
 /*etime2 = time(NULL);*/
 /*printf("[%d] Graph partitioned. Time: %f s.\n", myid, 
difftime(etime2, stime2));*/
   /* Put magic call here to simulate the MST computing only */
   /*  NEW_RUBY_MAGIC_CALL(3) */
 /* Computing a MST of the input graph */
 /* printf("[%d] Computing MST of graph\n",myid); */
 /*stime3 = time(NULL);*/
 ComputeMst(myid,tsize);
 /*etime3 = time(NULL);*/
 /*printf("[%d] MST computed. Time: %f s.\n", myid, difftime(etime3, 
stime3));*/
 /* printf("[%d] Times: %lld %lld 
%lld\n",myid,etime1-stime1,etime2-stime2,etime3-stime3); */
   END_WORKLOAD_TRANSACTION;
   Barrier_breaking(&local_sense, myid, num_threads);
}

int main(int argc, char *argv[])
{
 Vertex ver;
 /* Thread parameters */
 pthread_t *threads;
 int *ids;
 int i, mst_weight;
 /*time_t stime, etime;*/

 /* Command line arguments processing */
 if (argc > 2) num_threads = atoi(argv[2]);
 else num_threads = 1;
 if (argc > 1) gsize = atoi(argv[1]);
 else gsize = 1024;

 printf("[%d] Computing a MST of a graph using the Prim-Dijkstra 
algorithm\n",-1);
 /* Thread initializations */
 init_transaction_state(num_threads);
 threads = (pthread_t *) malloc(num_threads*sizeof(*threads));
 ids = (int *) calloc(num_threads, sizeof(int));
 pthread_attr_init(&pthread_custom_attr);
 pthread_attr_setscope(&pthread_custom_attr, PTHREAD_SCOPE_SYSTEM);
 /*pthread_barrier_init(&barr,NULL,num_threads);*/

 /* Graph initializations */
 graph = (Vertex *) malloc(num_threads*sizeof(*graph));
 for (i=0; i<num_threads; i++) *(graph+i) = NULL;
 mst = (Vertex *) malloc(sizeof(*mst));
 *mst = NULL;
 vertpos_g.vertexptr = (Vertex) -1;
 vertpos_g.vertexidx = -1;
 mst_vertex = (Vertex) malloc(sizeof(*mst_vertex));

 /* Creating threads */
   /*stime = time(NULL);*/
 for (i=0; i<num_threads-1; i++)
 {
   ids[i] = i;
   pthread_create(&threads[i], &pthread_custom_attr, Graph_MST, (void 
*)(ids+i));
 }
 ids[i] = i;
 Graph_MST(ids+i);

 for (i=0; i<num_threads-1; i++)
 {
   pthread_join(threads[i], NULL);
 }
 /*etime = time(NULL);*/

 ver = *mst;
 mst_weight = ver->mindist;
 ver = ver->next;
 while (ver != NULL)
 {
   mst_weight += ver->mindist;
   /* printf("[%d] MST: Org %d Dst %d (weg 
%d)\n",-1,ver->vid,ver->minvid,ver->mindist); */
   ver = ver->next;
 }
 printf("[%d] MST done with weight %d \n",-1,mst_weight);
}
##########################################################

Could anybody tell me what is going wrong?

Sorry for the long message.

Regards and thanks in advance, Ricardo Quislant.