From: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire)
Newsgroups: comp.os.msdos.djgpp
Subject: Bug in __builtin_new in GCC!!
Date: 10 Oct 1997 21:55:45 GMT
Organization: The National Capital FreeNet
Lines: 746
Message-ID: <61m891$dv5@freenet-news.carleton.ca>
Reply-To: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire)
NNTP-Posting-Host: freenet2.carleton.ca
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk



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