std::map nodes alignment

I'm facing something very amazing. (Scenario: Win7 pro 64 bit, VC2008 compiling 32 bit code)

Say a main program instantiate a Class that uses a std::map.

It's a std::map<std::string,Props> where class Props has only two members:

class Props {
public:
  /**
   * value of property
   * @var boost::any 
   */
  boost::any _a ;

  /**
   * expire time
   * @var time_t
   */
  time_t _tExpiry ;

  /* Somethign more I'm not writing down here... */
}

Now... I build a DLL, using the same class for it's own business.

The DLL instantiate that class and feed the std::map.

Well... When the main program feed the map everythig goes fine, while the DLL crashes after the first item insertion.

Something (very interesting) more.

If I go deep into insert done by the main program I reach the constructor of the single _Node into the std::map

_Node appear as follows (c:\Programmi\Microsoft Visual Studio 9.0\VC\include\xtree)

struct _Node
    {   // tree node
    _Node(_Nodeptr _Larg, _Nodeptr _Parg, _Nodeptr _Rarg,
        const value_type& _Val, char _Carg)
        : _Left(_Larg), _Parent(_Parg), _Right(_Rarg),
            _Myval(_Val), _Color(_Carg), _Isnil(false)
        {   // construct a node with value
        }

    _Nodeptr _Left; // left subtree, or smallest element if head
    _Nodeptr _Parent;   // parent, or root of tree if head
    _Nodeptr _Right;    // right subtree, or largest element if head
    value_type _Myval;  // the stored value, unused if head
    char _Color;    // _Red or _Black, _Black if head
    char _Isnil;    // true only if head (also nil) node
    };

Very fine... so our _Node structure hase _Left (4bytes), _Parent (4 bytes), _Right (4 bytes) _Myval (sizeof key and value of the map), _Color (1byte) and _Isnil(1 byte).

Now... the element I want to feed the map with is a pair of <std::string, Props>.

According to my debugger, std::string requires 0x20 bytes, while Props only 8.

Now, when I ask my debugger the size of the single node, I can see it's 0x38. So...0x4 + 0x4 + 0x4 + 0x20 + 0x8 + 0x1 + 0x1 = 0x36 + padding = 0x38.

This means that _Color member starts 0x34 bytes after the beginning of the _Node.

(Ok...I'd rather specify that all my projects use /Zp4 so all structures are 4 bytes packed).

Let's go on... When I follow the DLL behaviour I can se something very amazing.

The _Buynode() method of std::map calls the allocator to have new size for the new element I'm going to insert. The allocator is called than the _Node() in-place constructor is called.... and it acts another way!!

In this case, the constructor behaves as _Color member starts after 0x38 bytes from the beginning of the _Node... as if there's a different padding.

After this, on the following tryal to insert a new value, the procedure fails since the values of _Color and _Isnil are... wrong (0xcc since that part of memory isn't initialized).

I'm sure I set /Zp4 in all the projects into the solution so...

What's wrong?

I "feel" there's something wrong about aligment but I just can't say what...

Thanks in advance!

---

Ok... I'm going to add something more.

This is _Node structure from c:\Programmi\Microsoft Visual Studio 9.0\VC\include\xtree

struct _Node
    {   // tree node
    _Node(_Nodeptr _Larg, _Nodeptr _Parg, _Nodeptr _Rarg,
        const value_type& _Val, char _Carg)
        : _Left(_Larg), _Parent(_Parg), _Right(_Rarg),
            _Myval(_Val), _Color(_Carg), _Isnil(false)
        {   // construct a node with value
        }

    _Nodeptr _Left; // left subtree, or smallest element if head
    _Nodeptr _Parent;   // parent, or root of tree if head
    _Nodeptr _Right;    // right subtree, or largest element if head
    value_type _Myval;  // the stored value, unused if head
    char _Color;    // _Red or _Black, _Black if head
    char _Isnil;    // true only if head (also nil) node
    };

_Tree_nod(const key_compare& _Parg,
    allocator_type _Al)
    : _Traits(_Parg, _Al), _Alnod(_Al)
    {   // construct traits from _Parg and allocator from _Al
    }

typename allocator_type::template rebind<_Node>::other
    _Alnod; // allocator object for nodes
};

As you can see, it's costructor is pretty simple.

Looking at the memory used from this structure when I asf for a std::map as told before I have.

- 4 bytes for _Left

- 4 bytes for _Parent

- 4 bytes for _Right

- 0x28 bytes for _Myval (0x20 for the std::string and 8 for my own class. I checked, it's alqays 8 bytes)

- 1 byte for _Color

- 1 byte for _Isnil

When a new element placetd atop of the tree (I mean, the left most) is created, this costructor fills _Left, _Parent, _Right, _Myval, than lat 4 bytes uninitialized (say filled with 0xcc) and fills what it thinks should be _开发者_开发知识库Color and _Isnil 4 bytes ahead.

The most absurde thing is that the other methods of std::map don't "feel" those 4 bytes.

Those are the lines that cause de assertion.

        if (_Isnil(_Ptr))
        {
            _Ptr = _Right(_Ptr);    // end() ==> rightmost
            if (_Isnil(_Ptr))
#if _HAS_ITERATOR_DEBUGGING
            {
                _DEBUG_ERROR("map/set iterator not decrementable");
                _SCL_SECURE_OUT_OF_RANGE;
            }
#elif _SECURE_SCL
            {
                _SCL_SECURE_OUT_OF_RANGE;
            }
#else
            return; // begin() shouldn't be incremented, don't move
#endif
        }

This happens since the test for _IsNil(_Ptr), finding that _Isnil is 0xcc, gives an error. Release version probably don't nut this is not a joy.

Any idea?

---

Another Step!

I took the whole solution (2 Big projects, 18 small ones, about 250000 C/C++ code lines), and compile it under Linux (gcc4.1.2).

Everything works veeeeeery fine. No problems at all and std::map works properly.

I have to say that Linux Makefile make everything more easy and complex at the same time. Complex because you have to do everything on your own, easy because nothing happens if you don't want to.

This tells me one thing: there's somethign wrong in Visual Studio 2008, something that jumps on the stage in some particular condition... the problem is "what's the condition that causes this?".

Waiting for an idea...

---

I'm only guessing, but my immediate guess would be that your problem doesn't stem from alignment issues.

With VC++, if you put something like this in a DLL, you have to compile the code (both the main program and the DLL) to use the standard library in a DLL. When you do this, the main program and the DLL share a common heap, so they can allocate/free memory and things stay in synch.

If you link to the standard library statically, your main program and your DLL will have separate heaps. When/if code in one tries to delete an item that was allocated in the other (for one example), you'll run into major problems, because it'll try to return it to a heap that it didn't come from in the first place.

---

The compiler option is /Zp4. Are you sure you used the correct option in all cases?

---

Your description surely points in the direction of a alignment/packing problem.

Maybe you could add a compile-time check on the sizeof(Props) == 8. Boost has a compile-time check template, but it's not that hard to find one on internet or roll your own.

If the sizeof turns out to be always the same, let me point at checked iterators for an alternative thing to check.

After that, I'm running out of ideas.