Boost C++ Libraries: Ticket #3604: Access violation on diamond inheritance

attachment set

kondo@… — Tue, 10 Nov 2009 12:42:58 GMT

attachment → main.cpp

attachment set

kondo@… — Tue, 10 Nov 2009 12:43:22 GMT

attachment → structure.png

status changed

Robert Ramey — Fri, 27 Nov 2009 22:53:29 GMT

status new → assigned

Well, I've looked at this.

a) Looks like you've found a real problem b) Looks like you've done a lot work already. Without this I couldn't have spend any time on it. c) Looks like this is a bitch of a problem to find. I'll spend a little more time on it - but can't make any promises.

Robert Ramey

status changed; resolution set

Robert Ramey — Sun, 29 Nov 2009 07:29:18 GMT

status assigned → closed
resolution → invalid

Making a small change in your example illustrates the problem here.

Turns out you can downcast a pointer from a virtual base class. It makes sense when you think about it. The serialization library does this at runtime through an intermediate void * so it doesn't detect the error at compile time. And the MSVC compiler doesn't detect it unless it's done with a static cast. It turns out that the vbc data is "attached" to the first subclass. So the problem only occurs when we try to use the second - sub2.

If you make the following change in your program, and try to compile I think the problem will be obvious. (note to self, always use static_cast rather than implicit pointer conversions !!!)

	// Serialize pTarget via VBase pointer.
	{
        std::ofstream ofs("outtarget.xml");
        boost::archive::xml_oarchive oa(ofs);
        assert(ofs);
	Target* pTarget = new Target;
	VBase * pVBase = static_cast<VBase *>(pTarget);
        Target* pTarget2 = static_cast<Target *>(pVBase);
	oa << boost::serialization::make_nvp("pVBase", pVBase);
    }
    {
        std::ifstream ifs("outtarget.xml");
        assert(ifs);
        boost::archive::xml_iarchive ia(ifs);
	VBase * pVBase;
        ia >> boost::serialization::make_nvp("pVBase", pVBase);
    }

PS I did in fact find some problems with void cast registry - but I don't think they're related to this. After I fixed them, I still had the problem.

Robert Ramey

status changed; resolution deleted

kondo@… — Sun, 29 Nov 2009 14:38:18 GMT

status closed → reopened
resolution invalid

Sorry, I couldn't understand enough your comment.

I modified my code (main.cpp) , and it made compile error.

The compile error is in next code.

        Target* pTarget2 = static_cast<Target *>(pVBase);

And next, I checked that use only static_cast from Target* to Vbase *, it doesn't make compile error, but run result is not changed.

I think that we can't use static_cast as downcast.

(Does it mean library internal behavior??)

When we used BOOST_CLASS_EXPORT, I think that we can serialize sub-class via virtual base class.

Please point out the wrong point of my code.

status changed; resolution set

Robert Ramey — Sun, 29 Nov 2009 17:52:29 GMT

status reopened → closed
resolution → invalid

The library does a downcast from VBase * to Target * which is illegal in C++ if VBase is a virtual base class. However msvc doesn't always detect this and will sometimes work anyway. The following code WILL do the serialization, but not through a virtual base class pointer.

    // Serialize pTarget
    {
        std::ofstream ofs("outtarget.xml");
        boost::archive::xml_oarchive oa(ofs);
        assert(ofs);
	Target* pTarget = new Target;
	oa << boost::serialization::make_nvp("pTarget", pTarget);
    }
    {
        std::ifstream ifs("outtarget.xml");
        assert(ifs);
        boost::archive::xml_iarchive ia(ifs);
	Target* pTarget = new Target;
        ia >> boost::serialization::make_nvp("pTarget", pTarget);
        // if you want you could then use
        VBase *pVbase = pTarget.
    }

the way you want to do can't be done in legal/portable C++ even though it seems to work sometimes with MSVC.

Robert Ramey

attachment set

kondo@… — Mon, 30 Nov 2009 11:47:42 GMT

attachment → UML_META.png

kondo@… — Mon, 30 Nov 2009 11:48:49 GMT

Thanks for reply.

I understand it is illegal that static down cast from virtual base class.

I have 3 questions.

Q1

There is the test that serialize via the virtual base class.

https://svn.boost.org/trac/boost/browser/tags/release/Boost_1_41_0/libs/serialization/test/test_diamond.cpp#L184

And It seems to work correctly.

It it illegal?

Is it only accidental correct behavior?

It makes me confusing. Why does such test exist?

Q2

This question depends on the answer of Q1.

If the test of Q1 is not illegal, Is the number of bottom classes of diamond inherit is important?

Is only one bottom class allowed ?

Q3

We often need to treat the collection of the virtual base class, and we often want to serialize them.

For example, UML meta-model structure.(Attached file UML_META.png)

Doesn't current serialization library support such needs?

Of course I understand that this is my problem (not your problem).If possible, Could you give me some advice?

type, severity changed

Robert Ramey — Mon, 30 Nov 2009 18:22:23 GMT

type Bugs → Support Requests
severity Problem → Not Applicable

Q1: Now I'm wondering about this test. It currently passes on all platforms but it has failed for unexplained reasons in the past. I'm not really sure about this. Your test case is more ambiguous in that there are several "bottom" objects besides "Target". Perhaps this is what makes the difference. Also, "Target" derives from another "bottom" class. Perhaps this can be made to work by avoiding this situation.

Q2: When I run this with the MSVC debugger an examine pVBASE . It shows garbage in the derived class. This is not what I expect to see. When you export in the other sequence, it shows OK. This is what led me to try the static downcast (which is similar to what the serialization library does to make this work). The static downcast shows a compile time error which leads me to believe that we're depending on undefined behavior. What I believe is happening is that the data looks like

when we

EXPORT(Target) EXPORT(sub1)

Target object:

VBase data Mid2 data Sub2 data target data

Sub1 object

pointer to VBase data Mid1 data Sub1 data

So we can downcast from pVbase to pTarget because downcast just adjusts the pointer according to the size of the embedded data structures.

But when we do

EXPORT(sub1) EXPORT(Target)

Sub1 object

VBase data Mid1 data Sub1 data

Target object:

pointer VBase data Mid2 data Sub2 data target data

and we try to downcast from pVBase to pTarget it doesnt work because the address cannot be properly adjusted. The difference is that the single instance of Vbase data is included only in the first instance created.

So that's my guess. That is I believe that my test and your example work depend upon C++ undefined behavior. I think that knowing this will permit you to tweak your structure so that it does what you want on all compilers. But you'll really be going beyond the guarentees of the C++ language.

BTW:C++ is now so complex in it's details that I don't have 100% confidence when I'm dealing with these kinds of details. So you're free be skeptical of my assessment.

Q3: Assuming I'm correct in my answer to Q2, there's two approaches:

a) Code strictly according to standard C++ and don't depend on any undefined behavior. That makes your program "provably correct" b) Make it work and move on.

Generally I prefer a). Unfortunately, sometimes I have to do b). One such case is the EXPORT functionality which is very convenient (perhaps necessary) but relies on undefined C++ behavior from all compilers. If you need export you're already in b) territory to some extent. A couple of options.

a) craft your application in accordance with the hypothesis in my answer to Q2 which would mean : export only one bottom class. This probably would be OK.

b) avoid virtual base class by including a static member in the Base class. Extra work and not exactly equivalent but it might be a better choice. This would not depend on any undefined C++ behavior.

c) note that this whole issue comes from the usage of the EXPORT. If you were to avoid using this, there would no problem. This does however required "pre-registration" using Archive::register. This is not as convenient as EXPORT, but it has the advantage that it doesn't depended on undefined C++ behavior such as EXPORT does so it is not as "fragile".

I think any the above would likely work well.

c) restructure the class hierarchy so that there is one (non-virtual) base class which is used as the "universal pointer". Lower classes would use multiple in heritance to "add-in" the virtual base class functionality.

d) note that I addressed some similar issues with boost::serialization::singleton<T> template.

These later approaches would be more experimental.

Good luck.

Robert Ramey

kondo@… — Tue, 01 Dec 2009 12:54:06 GMT

It may be out of C++ standard topic. The static down cast via virtual base class is illegal. But I think that using void pointer, the most of compiler works correctly. And it is one of the essence of void-cast mechanism. See next exmample.

        Target* pTarget = new Target;
        Sub1* pSub1 = new Sub1;
        VBase *pVbTarget = pTarget;
        VBase *pVbSub1 = pSub1;
        std::ptrdiff_t dTargetToVBase =
            static_cast<unsigned char *>(static_cast<void *>(pTarget)) -
            static_cast<unsigned char *>(static_cast<void *>(pVbTarget));
        std::ptrdiff_t dSub12VBase =
            static_cast<unsigned char *>(static_cast<void *>(pSub1)) -
            static_cast<unsigned char *>(static_cast<void *>(pVbSub1));
        Target *pTarget_2 = static_cast<Target *>(static_cast<void *>(
            static_cast<unsigned char *>(static_cast<void *>(pVbTarget)) + dTargetToVBase));
        Sub1 *pSub1_2 = static_cast<Sub1 *>(static_cast<void *>(
            static_cast<unsigned char *>(static_cast<void *>(pVbSub1)) + dSub12VBase));

My understanding of serialization library is not perfect.

But I think that there is a possibility that serialize via virtual base class.

Please hear me.

I found a part of code that seems to support void downcast via virtual base class.

void_caster_shortcut::vbc_downcas is it.

https://svn.boost.org/trac/boost/browser/trunk/libs/serialization/src/void_cast.cpp#L126

This function is called from void_caster_shortcut::downcast.

https://svn.boost.org/trac/boost/browser/trunk/libs/serialization/src/void_cast.cpp#L95

In function void_caster_shortcut::downcast, the data member m_includes_virtual_base is very important.

https://svn.boost.org/trac/boost/browser/trunk/libs/serialization/src/void_cast.cpp#L90

My code (main.cpp) failure case,

94	    virtual void const *
95	    downcast(void const * const t) const{
96	        if(m_includes_virtual_base) // false
97	            return vbc_downcast(t);
98	=>      return static_cast<const char *> ( t ) + m_difference;
99	    }

success case,

94	    virtual void const *
95	    downcast(void const * const t) const{
96	        if(m_includes_virtual_base) // true
97	=>          return vbc_downcast(t);
98	        return static_cast<const char *> ( t ) + m_difference;
99	    }

In failure case, I think that the data member m_includes_virtual_base is set to false in spite of the virtual inheritance.

I modified the library code to always call vbc_downcast. Of course it's temporary.

94	    virtual void const *
95	    downcast(void const * const t) const{
96	        if(true) // temporary always true
97	=>          return vbc_downcast(t);
98	        return static_cast<const char *> ( t ) + m_difference;
99	    }

Both EXPORT sequences work correctly.

The data member m_includes_virtual_base is set in void_caster_shortcut's constructor, And it is called in void_caster::recursive_register. (Return to my analysis.)

I think it may be possible to modify m_includes_virtual_base registration algorithm.

Am I missing any big problems?

attachment set

kondo@… — Wed, 02 Dec 2009 08:02:59 GMT

attachment → ticket3604.patch

status changed; resolution deleted

kondo@… — Wed, 02 Dec 2009 08:03:33 GMT

status closed → reopened
resolution invalid

I hesitated to reopen this ticket.

If the serialization library doesn't support the object serialization via virtual base class, this idea might be a expansion proposal.

Should I create a new ticket as enhancement?

I wrote the patch(ticket3604.patch) seems to resolve this problem.

After applying this patch, Both EXPORT sequences in main.cpp work correctly.

This patch is for trunk.

Please try it.

It is based on next idea.

Background (My opinion)

I think if the information in void_caster_registry is correct, we can serialize the target class via virtual base class.

The void_caster_registry means a table that we can get it to call void_caster_registry::get_mutable_instance().

It might be out of standard C++, but most of compiler works correctly.

Strategy

Avoid overwriting the virtual inheritance information in recursive register process.

Modification

Add the new data member m_includes_virtual_base to class void_caster.

In void_caster::recursive_register() member function, m_includes_virtual_base memorize virtual inheritance information from the argument includes_virtual_base.

When the program creates the void_caster_shortcut object in void_caster::recursive_register(), pass the 4th argument '(*it)->m_includes_virtual_base

includes_virtual_base' instead of includes_virtual_base.

As a result, the virtual inheritance information in void_caster_registry is kept.

Result report

void_caster_registry information

OK Case

EXPORT seruqnce:Target,Sub1

Before patching and after patching made same result.

MIVB means m_includes_virtual_base.

No	MIVB	Derived	Base
0	FALSE	Target	Sub2
1	FALSE	Sub1	Mid1
2	FALSE	Sub1	Mid2
3	FALSE	Sub2	Mid1
4	FALSE	Target	Mid1
5	FALSE	Sub2	Mid2
6	FALSE	Target	Mid2
7	TRUE	Mid1	VBase
8	TRUE	Sub1	VBase
9	TRUE	Sub2	VBase

NG Case

EXPORT seruqnce:Sub1,Target

Before patching

No	MIVB	Derived	Base
0	FALSE	Sub1	Mid1
1	FALSE	Sub1	Mid2
2	FALSE	Target	Sub2
3	TRUE	Mid1	VBase
4	TRUE	Sub1	VBase
5	TRUE	Mid2	VBase
6	TRUE	Sub1	VBase
7	FALSE	Sub2	Mid1
8	FALSE	Sub2	VBase
9	FALSE	Target	VBase

No.8 and 9 seem to incorrect.Their MIVB should be true.

Afret patching

No	MIVB	Derived	Base
0	FALSE	Sub1	Mid1
1	FALSE	Sub1	Mid2
2	FALSE	Target	Sub2
3	TRUE	Mid1	VBase
4	TRUE	Sub1	VBase
5	TRUE	Mid2	VBase
6	TRUE	Sub1	VBase
7	FALSE	Sub2	Mid1
8	TRUE	Sub2	VBase
9	TRUE	Target	VBase

All information seems to be correct!

attachment set

kondo@… — Sun, 20 Dec 2009 13:28:20 GMT

attachment → ticket3064_remove_const.patch

attachment set

kondo@… — Sun, 20 Dec 2009 13:29:06 GMT

attachment → test_diamond_complex.cpp

kondo@… — Sun, 20 Dec 2009 13:49:17 GMT

I modify my patch. (Attached file:ticket3064_remove_const.patch)

The new patch removes const from void_caster::recursive_register() instead of using mutable data member.

Behavior is not changed. But it is more clear about an intention.

And I did the regression test of serialization.

All of them have passed.

In addition, I did the exhaustive test about this problem. (Attached file:test_diamond_complex.cpp)

After applying my patch, this test also have passed.

(Before applying my patch, this test didn't pass.)

Please check my test and patch, and if result is OK, accept them.

attachment set

Robert Ramey — Tue, 30 Mar 2010 15:46:38 GMT

attachment → void_cast.cpp

attachment set

Robert Ramey — Tue, 30 Mar 2010 15:47:11 GMT

attachment → void_cast.hpp

Robert Ramey — Tue, 30 Mar 2010 15:48:07 GMT

I looked at this again. I made some changes based on your code. Basically, I wasn't happy with the movement duplication of m_is_virtual base. When I made these changes, your test failed so I'm still not convinced that the passing of a test is a good indicator that I'm wrong that static downcasting from a virtual base class can only work as a matter of coincidence. I've attached the copies of void_cast.* that I've used.

attachment set

kondo@… — Sat, 03 Apr 2010 05:11:36 GMT

attachment → void_cast_add_or.cpp

Additional modified file based on Comment 10

attachment set

kondo@… — Sat, 03 Apr 2010 05:13:36 GMT

attachment → cls1.png

Simple class diagram pattern1

attachment set

kondo@… — Sat, 03 Apr 2010 05:14:13 GMT

attachment → cls2.png

Simple class diagram pattern2

attachment set

kondo@… — Sat, 03 Apr 2010 05:42:49 GMT

attachment → abc1.cpp

the test code corresponding to cls1.

attachment set

kondo@… — Sat, 03 Apr 2010 05:44:17 GMT

attachment → abc2.cpp

the test code corresponding to cls2.

kondo@… — Sat, 03 Apr 2010 05:46:33 GMT

Thanks for reply. I checked your modification. It is surely based on my idea. And My test failed.

I think there are some problems in your modification. Consider the case of cls1.png, abc1.cpp, cls2.png and abc2.cpp (attached.file).

The new shortcut element of void_caster_registry is made by already registered member and current registering member.

And if either includes virtual base, it shall include virtual base.

110    void_caster_shortcut(
111        extended_type_info const * derived,
112        extended_type_info const * base,
113        std::ptrdiff_t difference,
114        bool includes_virtual_base,
115        void_caster const * const parent
116    ) :
117        void_caster(derived, base, difference, parent),
118        m_includes_virtual_base(includes_virtual_base)
119    {
120        recursive_register(includes_virtual_base);
121    }

I think the member function recursive_register() needs the argument includes_virtual_base.

And in the member function recursive_register(), 'logical OR' operation is needed.

243        if(* m_derived == * (*it)->m_base){
244            const void_caster_argument vca(
245                (*it)->m_derived,
246                m_base
247            );
248            void_cast_detail::set_type::const_iterator i;
249            i = s.find(& vca);
250            if(i == s.end()){
251                new void_caster_shortcut(
252                    (*it)->m_derived,
253                    m_base,
254                    m_difference + (*it)->m_difference,
255                    (*it)->has_virtual_base() || includes_virtual_base,
256                    this
257                );
258            }
259        }
260        if(* (*it)->m_derived == * m_base){
261            const void_caster_argument vca(
262                m_derived,
263                (*it)->m_base
264            );
265            void_cast_detail::set_type::const_iterator i;
266            i = s.find(& vca);
267            if(i == s.end()){
268                new void_caster_shortcut(
269                    m_derived,
270                    (*it)->m_base,
271                    m_difference + (*it)->m_difference,
272                    (*it)->has_virtual_base() || includes_virtual_base,
273                    this
274                );
275            }
276        }

Based on this idea, I modified the void_caster.cpp you attached.

It is void_cast_add_or.cpp (attached file).

After this modification, my test succeeded.

What do you think?

kondo@… — Sat, 10 Apr 2010 00:18:13 GMT

I offer additional information. I believe that if the virtual inheritance inclusion distinguished correctly, static downcast from a virtual base class does not occur anymore.

Because the void cast includes virtual inheritance case, the void cast code is dispatched below class.

void_cast.hpp

template <class Derived, class Base>
class void_caster_virtual_base :
    public void_caster
{
    virtual bool has_virtual_base() const {
        return true;
    }
public:
    virtual void const * downcast(void const * const t) const {
        const Derived * d =
            dynamic_cast<const Derived *>(
                static_cast<const Base *>(t)
            );
        return d;
    }
    virtual void const * upcast(void const * const t) const {
        const Base * b =
            dynamic_cast<const Base *>(
                static_cast<const Derived *>(t)
            );
        return b;
    }
    void_caster_virtual_base();
    virtual ~void_caster_virtual_base();
};

And the void cast use dynamic_cast instead of static_cast.

Robert Ramey — Sun, 16 May 2010 22:30:35 GMT

This is still not working for me.

I'm using:

test_diamond_complex.cpp latest 1.43 release version void_cast_add_or.cpp as you've added void_cast.hpp as above MSVC 7.1 static version of the library

As far as I can tell, the following code

    virtual void const * upcast(void const * const t) const {
        const Base * b =
            dynamic_cast<const Base *>(
                static_cast<const Derived *>(t)
            );
        return b;
    }

on line # 219 of void_cast.hpp isn't working.

It should do a dynamic_cast to EX1Level2_A * from a EX1Level1 * but the pointer doesn't change and subsequent to that the program crashes.

I should say that the next item in the stack shows line # 348 in void_cast.cpp which is a mystery to me.

Double check this to see if we're still getting the same results. If not, I can check my change into the trunk and you can run from there. I might also check with another compiler - but I'm curious to know what you're using so we be sure that's not a source of difference.

So nice to meet you in person at BoostCon 2010

Robert Ramey

status changed; resolution set

Robert Ramey — Mon, 17 May 2010 18:18:18 GMT

status reopened → closed
resolution → fixed

I found an error in my build set up and re-ran your test.

Congratulations ! - looks like it works well.

Sooooooo

I'm adding this change to the library. I'm adding your test_diamond_complex to the test suite I'm updating the "acknowledgments" section to include your contribution.

Thanks for persevering with this.

Robert Ramey

Since you've invested a lot of understanding in the library, you might want to consider investigating some other issues.

a) My original implementation and your fix of virtual base class serialization depends on the compiler enabling RTTI. This is not a huge limitation, I'll note it in the documentation. But wonder if there is a way around this?

kondo@… — Mon, 24 May 2010 12:32:45 GMT

I'm adding this change to the library. I'm adding your test_diamond_complex to the test suite I'm updating the "acknowledgments" section to include your contribution.

It's my honor. I'm very glad to contribute to your library.

Since you've invested a lot of understanding in the library, you might want to consider investigating some other issues.

a) My original implementation and your fix of virtual base class serialization depends on the compiler enabling RTTI. This is not a huge limitation, I'll note it in the documentation. But wonder if there is a way around this?

I think that if we follow the C++ standard, it is impossible. As you know, downcasting via virtual base class must use dynamic_cast.

But...

If we go out of the C++ stantard, there might be some possibilities. Of course it depends on the compiler implementation. I think it is dangerous. Nevertheless, Do you think that RTTI free implementation is still important? If you think so, I'll consider about it.