Mail Archives: djgpp/1997/10/10/23:33:20
Compiling a C++ program I encountered repeated SIGSEGV in __builtin_new.
The lines causing the problem are
array=new int[_size*2]
and
if (!_next) _next=new BlankListItem
Debugger use showed that _size is a legit value in the former occurrence,
namely 1, so _size*2 is 2. Array is a local variable of type int *. _size
is a member of an object and the object came from a pointer, but the
object exists (pointer is valid) so accessing _size isn't causing it to seg
out.
In the latter case, similarly _next is legitimate, has value NULL, and
this time there aren't even any arguments to new.
I am forced to conclude that there is a bug in GCC's implementation of
new, because new is apparently segging out when every input to new is
legit. I verified that the malloc arena is not being corrupted.
Specifically, I am nowhere writing arrays out of bounds, everything I new
I delete, everything I array-new I array-delete, and I'm not leaking core.
Here is a traceback for the latter occurrence:
7....Exiting due to signal SIGSEGV
General Protection Fault at eip=00013cf8
eax=0000001c ebx=00000002 ecx=fffffffc edx=00d203ef esi=00000014
edi=00060004 ebp=000afa20 esp=000afa18 program=C:\GRTH\GROUPS.EXE
cs: sel=00a7 base=83216000 limit=000affff
ds: sel=00af base=83216000 limit=000affff
es: sel=00af base=83216000 limit=000affff
fs: sel=0087 base=0000e490 limit=0000ffff
gs: sel=00c7 base=00000000 limit=ffffffff
ss: sel=00af base=83216000 limit=000affff
Call frame traceback EIPs:
0x00013cf8 _malloc+192
0x00012d64 ___builtin_new+44
0x0000392d _add__13BlankListItemii+45, line 49 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
0x00003968 _add__13BlankListItemii+104, line 52 of groups.cc
C:\grth>symify groups.exe
C:\grth>
Attached below is the ENTIRE source (long).
There are two distinct crashes. One happens if you run this as is and
enter 1 and 8. The other happens when a chunk of code commented out
in GroupTable::setcell() is uncommented-out (the program runs the same but
slower with it commented out) and you enter 1 and 6. Strangely it fails to
happen if you enter 3 and 6.
// groups.cc
// Copyright (C) 1997 PGD
// Finds algebraic groups of orders startorder to endorder specified by user.
// Saves their tables in groups.dat text file.
#include "groups.h"
#include <time.h>
int main (void) {
int startorder;
int endorder;
GroupStats all_stats;
GroupStats *order_stats;
ofstream *out;
cout << "This program will determine all the distinct (nonisomorphic) finite groups\n";
cout << "for orders between a starting order and ending order inclusive.\n";
cout << "Group information will be saved to a file groups.dat in the current\n";
cout << "directory. This file will be overwritten! If you don't want it\n";
cout << "overwritten hit your interrupt key now.\n";
cout << "\nEnter the starting order: " << flush;
cin >> startorder;
cout << "\n\nEnter the ending order: " << flush;
cin >> endorder;
cout << "\n\nThis may take a while.\n";
cout << "Enumerating groups from order " << startorder << " to order " << endorder << "...\n";
order_stats=new GroupStats[endorder-startorder+1];
out = new ofstream("groups.dat");
(*out) << "Finding groups of orders " << startorder << " to order " << endorder << "...\n\n\n";
for (int i=startorder; i<=endorder; i++) {
GroupTable *g;
OrderList *orders;
int et;
cout << i << flush;
orders=new OrderList(i);
g=new GroupTable(i);
(*out) << "Finding groups of order " << i << ".\n\n";
et=time(0);
g->generate(&all_stats,order_stats+i-startorder,orders,out);
et=time(0)-et;
delete g;
delete orders;
all_stats.elapsed_time+=et;
order_stats[i-startorder].elapsed_time=et;
cout << endl << flush;
}
cout << "\nDone.\n\n";
(*out) << "\nDone.\n\n";
for (int i=startorder; i<=endorder; i++) {
cout << "Found " << order_stats[i-startorder].numgroups << " nonisomorphic groups of order " << i << ".\n";
cout << order_stats[i-startorder].numabelian << " were abelian. " << order_stats[i-startorder].numgroups-order_stats[i-startorder].numabelian << " were nonabelian.\n";
cout << "Spent " << order_stats[i-startorder].elapsed_time << " seconds finding order " << i << " groups.\n\n";
(*out) << "Found " << order_stats[i-startorder].numgroups << " nonisomorphic groups of order " << i << ".\n";
(*out) << order_stats[i-startorder].numabelian << " were abelian. " << order_stats[i-startorder].numgroups-order_stats[i-startorder].numabelian << " were nonabelian.\n";
(*out) << "Spent " << order_stats[i-startorder].elapsed_time << " seconds finding order " << i << " groups.\n\n";
}
delete [] order_stats;
cout << "Found " << all_stats.numgroups << " nonisomorphic groups altogether.\n";
cout << all_stats.numabelian << " were abelian. " << all_stats.numgroups-all_stats.numabelian << " were nonabelian.\n";
cout << "Spent " << all_stats.elapsed_time << " seconds finding these groups.\n\n";
(*out) << "Found " << all_stats.numgroups << " nonisomorphic groups altogether.\n";
(*out) << all_stats.numabelian << " were abelian. " << all_stats.numgroups-all_stats.numabelian << " were nonabelian.\n";
(*out) << "Spent " << all_stats.elapsed_time << " seconds finding these groups.\n\n";
out->close();
return 0;
}
// groups.h
// Copyright (C) 1997 PGD
// Header with classes and declarations
#include <iostream.h>
#include <fstream.h>
#include <memory.h> // For NULL, malloc.
// Track statistics for orders and whole execution.
struct GroupStats {
int numgroups;
int numabelian;
int elapsed_time;
GroupStats (void) { numgroups=0; numabelian=0; elapsed_time=0; }
};
// Forward declarations
class BlankList;
class GroupTable;
// Track a linked list item
class BlankListItem {
private:
int the_blank_i;
int the_blank_j;
BlankListItem *_next;
BlankListItem *_prev;
BlankList *_parent;
public:
BlankListItem (void) { the_blank_i=-1; the_blank_j=-1; _next=NULL; _prev=NULL; _parent=NULL; }
~BlankListItem (void) { if (_next) delete _next; }
void nuke (void) { _next=NULL; }
void nukenext (void);
int i_val (void) { return the_blank_i; }
int j_val (void) { return the_blank_j; }
BlankListItem *next (void) { return _next; }
BlankListItem *prev (void) { return _prev; }
BlankList *parent (void) { return _parent; }
void setprev (BlankListItem *p) { _prev=p; }
void setparent (BlankList *p) { _parent=p; }
BlankListItem *add (int i, int j) {
if (the_blank_i==-1) { the_blank_i=i; the_blank_j=j; return this; }
if (!_next) _next=new BlankListItem;
// *********************************************
// Run and put '1' and '8'. The line above crashes in new!
// *********************************************
_next->setprev(this);
_next->setparent(_parent);
return _next->add(i,j);
}
void makearray (int *array) {
array[0]=the_blank_i;
array[1]=the_blank_j;
if(_next) _next->makearray(array+2);
}
};
void destroy (BlankListItem *);
// Track a linked list of blanks
class BlankList {
private:
BlankListItem *head;
int _size;
public:
BlankList (void) { head=new BlankListItem; head->setparent(this); _size=0; }
~BlankList (void) { delete head; }
BlankListItem *add (int i, int j) { _size++; return head->add(i,j); }
void removefirst (void) {
BlankListItem *t;
t=head;
head=t->next();
t->nuke();
delete t;
if (!head) { head=new BlankListItem; head->setparent(this); }
head->setprev(NULL);
_size--;
}
void nukedone (void) { _size--; }
int size (void) { return _size; }
bool is_empty (void) { return _size==0; }
int *makearray (void) {
int *array;
if (_size==0) return NULL;
array=new int[_size*2];
head->makearray(array);
return array;
}
int first_i (void) { return head->i_val(); }
int first_j (void) { return head->j_val(); }
};
inline void BlankListItem::nukenext (void) {
BlankListItem *t;
t=_next->next();
if (t) t->setprev(this);
_next->nuke();
delete _next;
_next=t;
_parent->nukedone();
}
inline void destroy (BlankListItem *p) {
BlankListItem *v;
v=p->prev();
if (v) { v->nukenext(); return; }
p->parent()->removefirst();
}
class ChoiceSetItem {
private:
int _item;
ChoiceSetItem *_next;
public:
ChoiceSetItem (void) { _item=-1; _next=NULL; }
~ChoiceSetItem (void) { if (_next) delete _next; }
int item (void) { return _item; }
ChoiceSetItem *next (void) { return _next; }
void nuke (void) { _next=NULL; }
void add (int i) {
if (_item==-1) { _item=i; return; }
if (!_next) _next=new ChoiceSetItem;
_next->add(i);
}
};
class ChoiceSet {
private:
ChoiceSetItem *head;
int _size;
public:
ChoiceSet (void) { head=new ChoiceSetItem; _size=0; }
~ChoiceSet (void) { delete head; }
void add (int i) { head->add(i); _size++; }
int size (void) { return _size; }
int pop (void) {
int j;
ChoiceSetItem *t;
j=head->item();
t=head;
head=t->next();
t->nuke();
delete t;
if (!head) head=new ChoiceSetItem;
_size--;
return j;
}
};
class FactorListItem {
private:
int _factors[2];
FactorListItem *_next;
public:
FactorListItem (void) { _factors[0]=-1; _next=NULL; }
~FactorListItem (void) { if (_next) delete _next; }
int *factors (void) { return _factors; }
void add (int i, int j) {
if (_factors[0]==-1) {
_factors[0]=i;
_factors[1]=j;
return;
}
if (!_next) _next=new FactorListItem;
_next->add(i,j);
}
void makearray (int *array) {
if (_factors[0]==-1) return;
array[0]=_factors[0];
array[1]=_factors[1];
if(_next) _next->makearray(array+2);
}
};
class FactorList {
private:
FactorListItem *head;
int _size;
public:
FactorList (void) { head=new FactorListItem; _size=0; }
~FactorList (void) { delete head; }
void add (int i, int j) { head->add(i,j); _size++; }
int size (void) { return _size; }
int *makearray (void) {
int *array;
if (_size==0) return NULL;
array=new int[_size*2];
// *********************************************
// Uncomment the commented out section of
// GroupTable::setcell() and run and answer 1
// and 6. Then the line above crashes in new!
// *********************************************
head->makearray(array);
return array;
}
};
class OrderListItem {
private:
int order;
int *orders;
OrderListItem *next;
public:
OrderListItem (int o) {
order=o;
orders=new int[o];
for (int i=0; i<o; i++) { orders[i]=0; }
next=NULL;
}
~OrderListItem (void) { delete next; delete [] orders; }
int *ptr (void) { return orders; }
int *add (void) {
if (next) return next->add();
next=new OrderListItem(order);
return next->ptr();
}
bool checkfor (int *orderpattern) {
bool t;
t=true;
for (int i=0; i<order; i++) {
if (orderpattern[i]!=orders[i]) t=false;
}
if (t) return true;
if (next) return next->checkfor(orderpattern);
return false;
}
};
class OrderList {
private:
OrderListItem *head;
bool fresh;
public:
OrderList (int o) { head=new OrderListItem(o); fresh=true; }
~OrderList (void) { delete head; }
int *add (void) {
if (fresh) {
fresh=false;
return head->ptr();
}
return head->add();
}
bool checkfor (int *orderpattern) {
if (fresh) return false;
return head->checkfor(orderpattern);
}
};
// Track a Group Table
class GroupTable {
private:
int order;
int **table;
BlankList blanks;
BlankListItem ***bp;
bool abelian;
bool invalid_group;
FactorList *efactors;
int *orderpattern;
public:
GroupTable (int o) {
order=o;
abelian=true;
invalid_group=false;
table=new (int *)[order];
bp=new (BlankListItem **)[order];
orderpattern=new int[order];
for (int i=0; i<order; i++) {
table[i]=new int[order];
bp[i]=new (BlankListItem *)[order];
}
efactors=new FactorList[o];
for (int i=0; i<order; i++) { table[i][0]=i; table[0][i]=i; bp[i][0]=NULL; bp[0][i]=NULL; }
for (int i=1; i<order; i++) {
for (int j=1; j<order; j++) {
table[j][i]=-1;
bp[j][i]=blanks.add(j,i);
}
}
}
GroupTable (GroupTable &g) {
order=g.order;
abelian=g.abelian;
table=new (int *)[order];
bp=new (BlankListItem **)[order];
invalid_group=false;
for (int i=0; i<order; i++) {
table[i]=new int[order];
bp[i]=new (BlankListItem *)[order];
}
efactors=new FactorList[order];
orderpattern=new int[order];
for (int i=0; i<order; i++) {
int s;
int *array;
s=g.efactors[i].size();
array=g.efactors[i].makearray();
for (int j=0; j<2*s; j+=2) {
efactors[i].add(array[j],array[j+1]);
}
delete [] array;
}
for (int i=0; i<order; i++) {
for (int j=0; j<order; j++) {
int t;
t=g.table[j][i];
table[j][i]=t;
if (t==-1) {
bp[j][i]=blanks.add(j,i);
} else {
bp[j][i]=NULL;
}
}
}
}
~GroupTable (void) {
for (int i=0; i<order; i++) {
delete [] table[i];
delete [] bp[i];
}
delete [] table;
delete [] bp;
delete [] efactors;
delete [] orderpattern;
}
void generate (GroupStats *all_stats, GroupStats *order_stats, OrderList *orders, ofstream *out) {
// Generate some groups!
while (!invalid_group && !(blanks.is_empty())) {
while (do_forces()); // do_forces returns true if it finds any.
if (!invalid_group && !(blanks.is_empty())) {
// Got a choice to make
make_choice(all_stats,order_stats,orders,out);
}
}
done_group(all_stats,order_stats,orders,out);
}
bool do_forces (void) {
bool t,t2;
int s;
int *array;
t=false;
s=blanks.size();
array=blanks.makearray();
for (int i=0; i<2*s; i+=2) {
t2=do_force(array[i],array[i+1]);
t=t||t2; // Avoid short-circuiting
}
delete [] array;
return t && !invalid_group;
}
bool do_force (int i, int j) {
bool t;
ChoiceSet c;
int s;
if (table[i][j]>=0) return false; // Got set in earlier force by assoc/inverse laws.
t=false;
for (int k=0; k<order; k++) {
if (test(i,j,k)) c.add(k);
}
s=c.size();
if (s==1) {
setcell(i,j,c.pop());
t=true;
} else if (s==0) {
// Trouble
invalid_group=true;
}
return t;
}
bool test (int i, int j, int k) {
// Test if k can be inserted at i, j without trouble
// Cancellation laws
for (int l=0; l<order; l++) {
if (table[i][l]==k) return false;
if (table[l][j]==k) return false;
}
// Inverse laws
if (k==0 && table[j][i]>0) return false;
// Associative laws
int s;
int *array;
s=efactors[i].size();
array=efactors[i].makearray();
for (int q=0; q<s*2; q+=2) {
if (check_left_assoc(array[q],array[q+1],j,k)) { delete [] array; return false; }
}
delete [] array;
s=efactors[j].size();
array=efactors[j].makearray();
for (int q=0; q<s*2; q+=2) {
if (check_right_assoc(array[q],array[q+1],i,k)) { delete [] array; return false; }
}
delete [] array;
for (int l=0; l<order; l++) {
int t1,t2, t3;
t1=table[l][k];
if (t1>=0) {
t2=table[l][i];
if (t2>=0) {
t3=table[t2][j];
if (t3>=0 && t3!=t1) return false;
}
}
t1=table[k][l];
if (t1>=0) {
t2=table[j][l];
if (t2>=0) {
t3=table[i][t2];
if (t3>=0 && t3!=t1) return false;
}
}
}
return true;
}
bool check_left_assoc (int i1, int i2, int j, int k) {
int t1,t2;
t1=table[i2][j];
if (t1>=0) {
t2=table[i1][t1];
if (t2>=0 && t2!=k) return true;
}
return false;
}
bool check_right_assoc (int j1, int j2, int i, int k) {
int t1,t2;
t1=table[i][j1];
if (t1>=0) {
t2=table[t1][j2];
if (t2>=0 && t2!=k) return true;
}
return false;
}
bool set_left_assoc (int i1, int i2, int j, int k) {
int t1,t2;
t1=table[i2][j];
if (t1>=0) {
t2=table[i1][t1];
if (t2==-1) setcell(i1,t1,k);
}
return false;
}
bool set_right_assoc (int j1, int j2, int i, int k) {
int t1,t2;
t1=table[i][j1];
if (t1>=0) {
t2=table[t1][j2];
if (t2==-1) setcell(t1,j2,k);
}
return false;
}
void setcell (int i, int j, int k) {
if (!test(i,j,k)) { invalid_group=true; return; }
table[i][j]=k;
if (k==0) {
if (table[j][i]==-1) setcell(j,i,k);
} else {
if (table[j][i]>=0 && table[j][i]!=k) abelian=false;
}
// Uncomment this code to make the other crash happen.
/*int s;
int *array;
s=efactors[i].size();
array=efactors[i].makearray();
for (int q=0; q<s*2; q+=2) {
set_left_assoc(array[q],array[q+1],j,k);
}
delete [] array;
s=efactors[j].size();
array=efactors[j].makearray();
for (int q=0; q<s*2; q+=2) {
set_right_assoc(array[q],array[q+1],i,k);
}
delete [] array;*/
for (int l=0; l<order; l++) {
int t1,t2, t3;
t1=table[l][k];
if (t1>=0) {
t2=table[l][i];
if (t2>=0) {
t3=table[t2][j];
if (t3==-1) setcell(t2,j,t1);
}
}
t1=table[k][l];
if (t1>=0) {
t2=table[j][l];
if (t2>=0) {
t3=table[i][t2];
if (t3==-1) setcell(i,t2,t1);
}
}
}
efactors[k].add(i,j);
if (bp[i][j]) {
destroy(bp[i][j]);
bp[i][j]=NULL;
}
}
void make_choice (GroupStats *all_stats, GroupStats *order_stats, OrderList *orders, ofstream *out) {
int i, j;
int s;
int last_k;
int next_k;
i=blanks.first_i();
j=blanks.first_j();
ChoiceSet c;
for (int k=0; k<order; k++) {
if (test(i,j,k)) c.add(k);
}
s=c.size();
last_k=c.pop();
s--;
cout << '.' << flush;
for (int k=0; k<s; k++) {
GroupTable *g;
next_k=c.pop();
g=new GroupTable(*this);
g->setcell(i,j,next_k);
g->generate(all_stats,order_stats,orders,out);
delete g;
}
setcell(i,j,last_k);
cout << '\b' << ' ' << '\b' << flush;
}
void done_group (GroupStats *all_stats, GroupStats *order_stats, OrderList *orders, ofstream *out) {
if (invalid_group) return;
makeorderpattern();
check_for_duplicates(orders);
if (invalid_group) return;
add_to_orderlist(orders);
all_stats->numgroups++;
order_stats->numgroups++;
if (abelian) {
all_stats->numabelian++;
order_stats->numabelian++;
}
output_to(out);
}
void check_for_duplicates (OrderList *orders) {
if (orders->checkfor(orderpattern)) invalid_group=true;
}
void makeorderpattern (void) {
for (int i=0; i<order; i++) { orderpattern[i]=0; }
for (int i=0; i<order; i++) {
int element;
int e_order;
e_order=1;
element=i;
while (element!=0) {
element=table[element][i];
e_order++;
}
orderpattern[e_order]++;
}
}
void add_to_orderlist (OrderList *orders) {
int *ords;
ords=orders->add();
for (int i=0; i<order; i++) { ords[i]=orderpattern[i]; }
}
void output_to (ostream *out) {
static char names[] = "eabcdfghijklmnopqrstuvwxyz";
static char names2[] = " abcdfghijklmnopqrstuvwxyz";
(*out) << endl;
if (!abelian) {
(*out) << "Non-abelian ";
} else {
(*out) << "Abelian ";
}
(*out) << "group of order " << order << ":" << endl;
(*out) << '+';
for (int i=0; i<order; i++) {
(*out) << "---+";
}
(*out) << endl;
for (int i=0; i<order; i++) {
(*out) << '|';
for (int j=0; j<order; j++) {
int t,t1,t2,t3;
t=table[j][i];
t1=t%26;
t2=(t/26)%26;
t3=((t/26)/26)%26;
(*out) << names[t1] << names2[t2] << names2[t3] << '|';
}
(*out) << endl;
(*out) << '+';
for (int j=0; j<order; j++) {
(*out) << "---+";
}
(*out) << endl;
}
(*out) << endl;
}
};
Can someone tell me what the FUCK is going ON?!
--
.*. Where feelings are concerned, answers are rarely simple [GeneDeWeese]
-() < When I go to the theater, I always go straight to the "bag and mix"
`*' bulk candy section...because variety is the spice of life... [me]
Paul Derbyshire ao950 AT freenet DOT carleton DOT ca, http://chat.carleton.ca/~pderbysh
- Raw text -