Conference turris::c_plus_plus

3542.0. "problem with rb_tree on multi-threaded environment?" by TAEC::SANNA () Fri Apr 18 1997 13:18

Bonjour,

I'm trying to debug a code where there is a segmentation fault in the use of
rb_tree (when using map).
Map are used to implement Item Sets or index, for which the key is a string.

Notes : 
	* Multi-threaded environment
	* Stress situation
	* Crash is not always at the same place, the only constant thing is that
the crash always occures in rb_tree...


You can find below some debug traces with description of the objects used. The traces show that in the rb_tree
that causes the crash, NIL is not 0x0. This implies that code enters in a while loop where probably it should
not. 
Is there a known problem with rb_tree??
Could anyone help me by giving me some indications or advices??

Thanks,

Isa.






DEBUG
*****

(ladebug) where
>0  0x3ff825374f8
#1  0x3ff81ce5fa8 in ((pair<constString,AbsIndex>*)0xd0e058)->pair<constString,AbsIn
dex>(=<bad reference>) /usr/include/cxx/utility:60
#2  0x3ff81ce6324 in construct(p=0xd0e058, value=<bad reference>) /usr/include/cxx/m
emory:150
#3  0x3ff81ce81b8 in ((rb_tree<String,pair<constString,AbsIndex>,select1st<pair<cons
tString,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsIndex>>>*)0xcd8
720)->__copy(x=0x0, p=0xd0e008) /usr/include/cxx/tree:797
#4  0x3ff81cbf734 in ((rb_tree<String,pair<constString,AbsIndex>,select1st<pair<cons
tString,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsIndex>>>*)0xcd8
720)->rb_tree<String,pair<constString,AbsIndex>,select1st<pair<constString,AbsIndex>
,String>,less<String>,allocator<pair<constString,AbsIndex>>>(x=const { ... }, always
=0) /usr/include/cxx/tree
#5  0x3ff81cbfab0 in ((map<String,AbsIndex,less<String>,allocator<pair<constString,A
bsIndex>>>*)0xcd8720)->map<String,AbsIndex,less<String>,allocator<pair<constString,A
bsIndex>>>(x=const { ... }) /usr/include/cxx/map:93
#6  0x3ff81ccb22c in ((FormatStringItem*)0xc74008)->Copy() FormatStringItem.cxx:696
../..

(ladebug) up 6
>6  0x3ff81ccb22c in ((FormatStringItem*)0xc74008)->Copy() FormatStringItem.cxx:696
(Cannot find source file FormatStringItem.cxx)
(ladebug) W
../..
>   696     MarkTable tmp = markTable;
    697   //end tmp
    698   return new FormatStringItem(*this);
    699 }
(ladebug) p markTable.t
class rb_tree<String,pair<constString,AbsIndex>,select1st<pair<constString,AbsIndex>
,String>,less<String>,allocator<pair<constString,AbsIndex>>> {
  rb_tree_node_allocator = class allocator<rb_tree<String,pair<constString,AbsIndex>
,select1st<pair<constString,AbsIndex>,String>,less<String>,allocator<pair<constStrin
g,AbsIndex>>>::rb_tree_node> {
  };
  value_allocator = class allocator<pair<constString,AbsIndex>> {
  };
  buffer_allocator = class allocator<rb_tree<String,pair<constString,AbsIndex>,selec
t1st<pair<constString,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsI
ndex>>>::rb_tree_node_buffer> {
  };
  buffer_list = 0x5e0928;
  free_list = 0x0;
  next_avail = 0xc03038;
  last = 0xc03ff8;
  header = 0xc03008;
  node_count = 0;
  insert_always = 0;
  key_compare = struct less<String> {
  };
  number_of_trees = 27;
  NIL = 0xc0da88;
}
(ladebug) down
>5  0x3ff81cbfab0 in ((map<String,AbsIndex,less<String>,allocator<pair<constString,A
bsIndex>>>*)0xcd8720)->map<String,AbsIndex,less<String>,allocator<pair<constString,A
bsIndex>>>(x=const { ... }) /usr/include/cxx/map:93
     93     map(const map<Key, T, Compare, Allocator>& x) : t(x.t, false) {}
(ladebug) down
>4  0x3ff81cbf734 in ((rb_tree<String,pair<constString,AbsIndex>,select1st<pair<cons
tString,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsIndex>>>*)0xcd8
720)->rb_tree<String,pair<constString,AbsIndex>,select1st<pair<constString,AbsIndex>
,String>,less<String>,allocator<pair<constString,AbsIndex>>>(x=const { ... }, always
=0) /usr/include/cxx/tree
(ladebug) p *x.header
struct rb_tree_node {
  color_field = red;
  parent_link = 0x0;
  left_link = 0xc03008;
  right_link = 0xc03008;
  value_field = struct pair<constString,AbsIndex> {
    first = class String {
      cxxl_p = 0x0;
    };
    second = struct AbsIndex {
      pos = 0;
      stringElementType = STRING;
    };
  };
}
(ladebug) p x.node_count
0
(ladebug) down
>3  0x3ff81ce81b8 in ((rb_tree<String,pair<constString,AbsIndex>,select1st<pair<cons
tString,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsIndex>>>*)0xcd8
720)->__copy(x=0x0, p=0xd0e008) /usr/include/cxx/tree:797
    797       construct(value_allocator.address(value(y)), value(x));
(ladebug) W
    788
    789 template <class Key, class Value, class KeyOfValue, class Compare, class All
ocator>
    790 rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::link_type
    791 rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::__copy(link_type x, lin
k_type p) {
    792    // structural copy
    793    link_type r = x;
    794    while (x != NIL) {
    795       link_type y = get_node();
    796       if (r == x) r = y;  // save for return value
>   797       construct(value_allocator.address(value(y)), value(x));
    798       left(p) = y;
    799       parent(y) = p;
    800       color(y) = color(x);
    801       right(y) = __copy(right(x), y);
    802       p = y;
    803       x = left(x);
    804    }
    805    left(p) = NIL;
    806    return r;
    807 }





Classes used in this case are :
-----------------------
struct AbsIndex {
  typedef enum {STRING,LINE,WORD,CHAR} StringElementType;
  int pos;
  StringElementType stringElementType;
  void Init();
};
  
typedef map<String, AbsIndex, less<String> > MarkTable;

class FormatStringItem : public Item {
../..
protected:
../..
  MarkTable markTable;                    // table of (mark_id, AbsIndex)
../..

}

Item* FormatStringItem::Copy() const
{
  //tmp code to identify the problem 
  MarkTable tmp = markTable;//crash occures HERE
  return new FormatStringItem(*this);
}





Another one : The erase method (which caused the crash) seemed not so necessary in this case, so we attempted
to remove it, and the crash occured elsewhere, in the case described above.

(ladebug) where
>0  0x3ff81cdc894 in
((rb_tree<String,pair<constString,Item*>,select1st<pair<constString,Item*>,Strin
g>,less<String>,allocator<pair<constString,Item*>>>*)0x2c1e08)->erase(position={
... }) /usr/include/cxx/tree:743
#1  0x3ff81c94a3c in
((map<String,Item*,less<String>,allocator<pair<constString,Item*>>>*)0x2c1e08)->
erase(position={ ... }) /usr/include/cxx/map:131
#2  0x3ff81c966c0 in ((ItemSet*)0xbfca90)->Set(itemName=0x3ff8179fe28="IID",
newItem=0x5e0808) ItemSet.cxx:115
../..

When I inspected the item to erase, it seemed OK

Classes used in this case are :
-----------------------
class ItemSet {
../..
protected:
  Clone* CurrentClone;
../..
}

class Clone{
protected:
../..
  Table* table;   
};

typedef map<String, Item*, less<String> > Str2ItemMap;

class Table : public Str2ItemMap{
../..
}


"guilty" Set method is :
-----------------
void ItemSet::Set(const char* itemName, Item* newItem)
{
   // an item can only be in one set at the time.
  // we don't need to support that an item moves.

  // this is a modification of our cloned table
  Table* table = CurrentClone->ModifyTable();   
  
  // look up item
  Table::iterator i = table->find(itemName);

  // if it exists then decrement RefCnt and delete it if RefCnt == 0
  if (i != table->end()) { 
    Item* oldItem = (*i).second;
    if (--oldItem->RefCnt == 0) {
      DMALLOC_INFO
      delete oldItem;
     }

    // remove (string,Item*) from table
    table->erase(i); //!!!crash occures HERE
  }

  // name newItem and save pointer to this ItemSet
  newItem->id = itemName; // id is an String
  newItem->itemSet = this;
   
  // insert newItem in table
  (*table)[itemName] = newItem;
 
}

There are no known problems with map or rb_tree that would
cause segmentation faults.

Two suggestions:

1. Try using third degree. Your problem sure sounds
like a memory corruption problem to me.

2. Put debug statements in the constructors/destructor
of your Item class to make sure you aren't trying to
destroy an Item twice. The number of constructions
(including copy constructions) should always match the 
number of destructions.

If you can get us a complete (hopefully small) reproducable 
example then we would be happy to look into it for you. 
Often you figure out a problem as you're isolating
it.

Thanks for your answer.

The problem does not seem to come from destruction, but from wrong
initialization.
The crash always occures in the rb_tree copy constructor, when trying
to copy the tree root.
When I look at the impacted rb_tree structure, 
	*when everything works fine, I have an empty rb_tree and a root
(parent_link of header) equals to NIL.
	*when there is a segmentation fault, I still have an empty
rb_tree, but the root is either equals to a null pointer or to an
unvalid pointer.

In the second case, in the rb_tree::copy method the link_type to copy
(root() in this case) is different from NIL so there is an attempt to
access to its value which is not valid.

I thought that the root was initialized to NIL in the rb_tree init
method, so I don't understand how root can be different from NIL for an
empty tree.
Could you please try to explain me what possibly happened to lead to
this situation?

You'll find below the traces showing the structure of a valid an of an
unvalid rb_tree.

Thanks for your help,

isa.


FIRST CASE : EVERYTHING IS OK, ROOT = NIL
*****************************************
(ladebug) p id.cxxl_p->cxxl_s
0x58f738="message"
(ladebug) p markTable.t
class 
rb_tree<String,pair<constString,AbsIndex>,select1st<pair<constString,Ab
sIn
dex>,String>,less<String>,allocator<pair<constString,AbsIndex>>> {
  rb_tree_node_allocator = class 
allocator<rb_tree<String,pair<constString,AbsIn
dex>,select1st<pair<constString,AbsIndex>,String>,less<String>,allocato
r<pair<co
nstString,AbsIndex>>>::rb_tree_node> {
  };
  value_allocator = class allocator<pair<constString,AbsIndex>> {
  };
  buffer_allocator = class 
allocator<rb_tree<String,pair<constString,AbsIndex>,s
elect1st<pair<constString,AbsIndex>,String>,less<String>,allocator<pair
<constStr
ing,AbsIndex>>>::rb_tree_node_buffer> {
  };
  buffer_list = 0x5e0748;
  free_list = 0x0;
  next_avail = 0xc15038;
  last = 0xc15ff8;
  header = 0xc15008;
  node_count = 0;
  insert_always = 0;
  key_compare = struct less<String> {
  };
  number_of_trees = 5;
  NIL = 0x6fe588;
********************
}
(ladebug) p *markTable.t.header
struct rb_tree_node {
  color_field = red;
  parent_link = 0x6fe588;
**************************
  left_link = 0xc15008;
  right_link = 0xc15008;
  value_field = struct pair<constString,AbsIndex> {
    first = class String {
      cxxl_p = 0x1000000003;
    };
    second = struct AbsIndex {
      pos = 1;
      stringElementType = 7;
    };
  };
}


SECOND CASE : KO, ROOT = 0x0
****************************
(ladebug) p id.cxxl_p->cxxl_s
0x2bc648="message"
(ladebug) p markTable.t
class
rb_tree<String,pair<constString,AbsIndex>,select1st<pair<constString
,AbsIndex>,String>,less<String>,allocator<pair<constString,AbsIndex>>> 
{
  rb_tree_node_allocator = class 
allocator<rb_tree<String,pair<constString,AbsIn
dex>,select1st<pair<constString,AbsIndex>,String>,less<String>,allocato
r<pair<co
nstString,AbsIndex>>>::rb_tree_node> {
  };
  value_allocator = class allocator<pair<constString,AbsIndex>> {
  };
  buffer_allocator = class 
allocator<rb_tree<String,pair<constString,AbsIndex>,s
elect1st<pair<constString,AbsIndex>,String>,less<String>,allocator<pair
<constStr
ing,AbsIndex>>>::rb_tree_node_buffer> {
  };
  buffer_list = 0x534a88;
  free_list = 0x0;
  next_avail = 0xda3038;
  last = 0xda3ff8;
  header = 0xda3008;
  node_count = 0;
  insert_always = 0;
  key_compare = struct less<String> {
  };
  number_of_trees = 8;
  NIL = 0xd47dc8;
********************
}
(ladebug) p *markTable.t.header
struct rb_tree_node {
  color_field = red;
  parent_link = 0x0;
**********************
  left_link = 0xda3008;
  right_link = 0xda3008;
  value_field = struct pair<constString,AbsIndex> {
    first = class String {
      cxxl_p = 0x0;
    };
    second = struct AbsIndex {
      pos = 0;
      stringElementType = STRING;
    };
  };
}