multi_index constraint violation if rollback callable is passed, but doesn't correct the issue

[Jon Kalb <jonkalb@…>]

If modify() is called taking two callables (the modifier and the rollback) in which the modifier changes a value one the element that results in the element not being acceptable (because a unique index would have a duplicate entry), then the rollback callable is called to correct the issue.

If the rollback callable does not correct the issue, the modification is committed anyway which leads to corruption of the unique index(es) involved.

[Jon Kalb <jonkalb@…>]

Demonstrating multi_index index corruption bug.

[Joaquín M López Muñoz]

Hi Jon,

The behavior is in conformance with the reference:

"Requires: [...] The sequence of operations mod(e), back(e) restores all keys of the element to their original state."

So, if the user-provided rollback fails to restore keys, it is a violation of requirements on the user's side, not the lib's fault. Note that the rollback function has the option to throw if, for some reason, it can't restore the keys:

"Exception safety: Strong, except if back throws an exception, in which case the modified element is erased [...]"

Another issue is whether the documented behavior should be changed so that the library re-checks invariants after back is executed. My personal opinion is that it shouldn't, as we would be imposing an uncalled for overhead on the users who provide a conforming rollback function. Also, the user has the option to set the invariant-checking mode, which detects and signals this situation.

[Jon Kalb <jonkalb@…>]

Joaquin,

Thanks very much for your library and for your quick response on this issue.

We'll just have to disagree on the correct design for this feature.

Obviously I believe that the design is so dangerous that I reported it as a bug rather than a design flaw. It never occurred to me that this design was intentional.

The possibility of error on the user's part, particularly in a non-trivial situation, the slight additional overhead of the verification (particularly given the likely uncommonness of the rollback needing to be called), and the catastrophic nature of the potential failure are what make me think that shifting the burden to the user here is ill-designed.

Consider that the user cannot verify that fallback either will or has done the correct thing, nor is there a way to query if the index has been corrupted (not that there would be a way to correct the situation if it were).

I discovered this while preparing a talk on various Boost libraries. When presenting this I will warn attendees that the rollback feature is unsafe to use in any but the most trivial cases. This warning will certainly weaken the generally positive thrust of the talk on this library, but to omit the warning would be a disservice to my audience.

Of course if it were possible for the user to themselves verify (in the rollback) if the rollback has met the requirement, then it would be a usable feature. In that case, the best practice recommendation would be for the user to *always* do the verify in any non-trivial situations (where a uniqueness constraint is or may be in place). So the user is not benefiting from the lack of "uncalled for overhead," because the best practice would be to call for it. (Of course an opt-in method of disabling the check would be a useful feature in the, uncommon, I would expect, situation where the rollback is both in a tight loop and guaranteed to be successful.)

Just rhetorically I'll ask you: Why did you make all iterators const? This design decision adds an uncalled for overhead in those situations where the user wishes to modify data that the users knows is not in any index. But it is clearly the correct decision because otherwise the burden placed on the user and the devastating nature of a mistake on the user's part would make this a dangerous library to use.

As it is, it has one very dangerous design flaw--the rollback feature.

I didn't address the invariant-checking mode issue because I feel that is clearly not relevant. It effects performance of the entire library, not just in the probably rare rollback scenario and it isn't well designed to be useful in that scenario.

But I do agree very much with one thing in the documentation describing the invariant-checking mode: "Any assertion of this kind should be regarded in principle as a bug in the library." I think that any opportunity for the user to corrupt the index in "normal" code (code without casts, buffer overruns, or language undefined behavior) is a bug in the design of the library.

Please reconsider the design of this particular feature.

Thanks again for your library and for your quick reply.

Jon

[anonymous]

Hi Jon,

Let me keep this open to think it over more carefully. I am sympathetic to, but not fully convinced about, your position. You say:

Of course if it were possible for the user to themselves verify (in the rollback) if the rollback has met the requirement, then it would be a usable feature.

I have a hard time figuring out what kind of rollback function would be unable to determine that the invariant has been restored, as this user-provided function is meant to restore the original key, not to try something new (of course the user can do whatever she pleases, but that's another matter). Following your example, she'd do:

bool succeed{name_index.modify(
        it,
        [](employee& e) {e.id = 1;},
        [original_id = it->id](employee& e) { e.id = original_id;})};

This is not a rhetorical question: could you conceive of some realistic situation in which the rollback function honestly tries to restore the key but could potentially fail to do so (exceptions aside)? The existence of such scenario would certainly make it advisable to folllow your proposed design.

One thing I readily concede to you is that my suggestion of using the invariant-checking mode for this is ill-advised. You're right this mode should be reserved to detect internal bugs, not user misbehaviors.

This warning will certainly weaken the generally positive thrust of the talk on this library, but to omit the warning would be a disservice to my audience.

I don't expect from you anything less than telling the audience about any perceived problem you observe :-)

[Jon Kalb <jonkalb@…>]

I think we are mostly in agreement here and the discussion is coming down to two issues. One is should the library ever “take the user’s word” that constraints are met and the other is how reasonable/likely is it that the user can be certain (or uncertain) that rollback is successful.

On the second, I have somewhat mixed feelings. I can see that in many cases, the only change being made is to a single field and restoring the old value of the field would seem to be a straightforward fix. This is, of course, the example I sent you. But I deliberately chose as trivial an example as possible for this report.

I can imagine that in real code, the element modification might involve calling a transformation function whose effects might be non-trivial to rollback (particularly under maintenance which might not be sensitive to the rollback issue). The solution that would make me, as a library user, feel comfortable would be to have a copy of the original element value to restore. But since the copy would have to be made in all cases (not just the rollback case), the modify() member function would, in practice, have no advantage over the replace() member function. I’d still have to make copies of the element with each modify.

On the first issue, I’m still of the opinion that the library code should always be defensive about any change that could corrupt the indexes and never just put the burden on the user to always have done the right thing. I think this is consistent with your own thinking when you wrote the comment that I quoted from the invariant-checking mode which says that any invariant validation is in principle a bug in the library.

I hope that the example of a transformation function which may be non-trivial to rollback is sufficient to sway you, but even if not, consider that the library code really should defend against corruption. Perhaps it can’t (and for performance reasons shouldn’t) guard against Machiavelli, but it should always be on guard against Murphy.

[anonymous]

Hi Jon,

OK, I think I'm buying your point. My thought process has been somewhat convoluted, though, let me explain:

Re-reading the specs for non-rollback modify I noticed this (italics mine):

"Exception safety: Basic. If an exception is thrown by some user-provided operation (except possibly mod), then the element pointed to by position is erased."

So I was like, am I really allowing the user to throw inside mod without the lib checking the consistency of the element? In fact I am:

template<typename Modifier>
bool modify_(Modifier& mod,node_type* x)
{
  mod(const_cast<value_type&>(x->value()));

  BOOST_TRY{
    ...

and this opens up a real case of consistency breach:

struct element
{
  std::string x,y;
};
...
i.modify(it,[](element& e){
  e.x="whatever"; // dynamic allocation, can throw
  e.y="and ever"; // idem
});

This example can throw in between assigments to x and y, making modify return without checking for consistency (uniqueness, rearranging). So, this is a design flaw in modify (both with and without rollback) and I have to correct it. We have two options when mod throws: delete the element or go ahead with rearranging; as throwing is an indication of failure, I think the natural thing to do is delete, and moreover going ahead in the rollback version is problematic, since the element was left in mid-modification and rollback could expect something else (your opinion on this point most welcome). The current situation is then

• mod is not guarded against throws but is guarded against inconsistency (rollback or element deletion if no rollback provided)
• rollback is guarded against throws (element deletion) but is not guarded against inconsistency

and after I correct the problem with mod we'll have

• mod is guarded against throws (element deletion) and inconsistency (rollback or element deletion if no rollback provided)
• rollback is guarded against throws (element deletion) but not guarded against inconsistency

and now I'm leaning more towards your position out of considerations of symmetry:

• mod is guarded against throws (element deletion) and inconsistency (rollback or element deletion if no rollback provided)
• rollback is guarded against throws and inconsistency (element deletion)

So, I'll put myself to clean this up. The changes required are not entirely trivial, though, and require extra care to get them right (as I guess you'll guess after this conversation), so it's going to take me some weeks before I find the time --I'm also in the process of finishing something up for Boost submission, so my current C++ slot is occupied.

Thanks for the interesting discussion,

[Joaquín M López Muñoz]

Addressed at ​b9a4467f3425cdae1d472b53516efbac74770792.