From: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire) Newsgroups: comp.os.msdos.djgpp Subject: "new" segs out! Date: 11 Oct 1997 21:45:38 GMT Organization: The National Capital FreeNet Lines: 755 Message-ID: <61os22$6o8@freenet-news.carleton.ca> Reply-To: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire) NNTP-Posting-Host: freenet3.carleton.ca To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Precedence: bulk [REPOST: news server ate it. (Our news server has been having problems of late.)] 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 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 #include #include // 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; iadd(); next=new OrderListItem(order); return next->ptr(); } bool checkfor (int *orderpattern) { bool t; t=true; for (int i=0; icheckfor(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=0) return false; // Got set in earlier force by assoc/inverse laws. t=false; for (int k=0; k0) return false; // Associative laws int s; int *array; s=efactors[i].size(); array=efactors[i].makearray(); for (int q=0; q=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=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; ksetcell(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; iadd(); for (int i=0; i