FEAT: Extend pmreorder with information about state

[igchor]

FEAT: Extend pmreorder with information about state

Rationale

Currently, the consistency checker under pmreorder is basically stateless. It doesn't have any information about the last successful operation or anything like this.

For example, if we are testing insert operations for a linked list, the only thing which we can reliably test right now is if the list is consistent (there is no crash while iterating, all next/prev pointers match, etc.). We don't have any information about the expected size and so on.

Description

To extend consistency checker with state information we could allow user to pass some extra data from the application through markers. E.g. for a sequence of insert/remove operations for a list:

VALGRIND_EMIT_LOG("INSERT.START[3,10]");
list.insert(10);
VALGRIND_EMIT_LOG("INSERT.END");
VALGRIND_EMIT_LOG("INSERT.START[4,11]");
list.insert(11);
VALGRIND_EMIT_LOG("INSERT.END");
VALGRIND_EMIT_LOG("REMOVE.START[5, 10]");
list.remove(10);
VALGRIND_EMIT_LOG("REMOVE.END");

The values in [] brackets (ideally for all markers before the operation) would be then passed to the consistency checker and the user can interpret them. In the example above the first value in brackets can be interpreted as the size of the list and the second as the element inserted/removed.

If a consistency checker gets a following list of markers: VALGRIND_EMIT_LOG("INSERT.START[3,10]"); VALGRIND_EMIT_LOG("INSERT.END"); VALGRIND_EMIT_LOG("INSERT.START[4,11]"); it means that the list should contain element 10 and possibly also element 11 (we don't know if inserting of element 11 completed or not).

API Changes

Extending markers format?

Implementation details

Allow passing extra parameters through VALGRIND_EMIT_LOG. The parameters could be passed either as strings or using printf-like format maybe?

Each time pmreorder executes consistency-checker it should pass all previous markers (along with user-provided parameters) to the checker. This could be done through env variables or cmd arguments.

POC: https://github.com/igchor/pmdk/tree/pmreorder_pass_markers

[igchor]

This is quite similar to approaches for checking data consistency in concurrent environments, for example: https://github.com/facebook/CacheLib/blob/v2022.04.11.00/cachelib/cachebench/consistency/ValueHistory.h

[karczex]

You already may pass arbitrary (also runtime generated) string via VALGRIND_PMC_EMIT_LOG for example: https://github.com/karczex/libpmemobj-cpp/tree/pmemcheck_arbitrary_string_log

So it seems that only changes in pmreorder are needed.
It may be more flexible to just pass trimmed store log to checker application, and do state deduction on the application level (based on markers format defined in the checker itself).

[igchor]

A few additionals feature that would be useful for debugging:

1. Add an option to pmreorder to execute storelog up to a certain point so that user can inspect pool at any state. Alternatively, add an option to pmreorder to stop on first failure and do not revert stores. Pmreorder could also support running consistency checker under GDB. This could be done in 2 stages. First pmreorder is run normally and on failure we would store information about where the crash happened. Then, pmreorder could revert all operations and run the application again, this time, e.g. under gdb and put a breakpoiont/watchpoint just before the expected crash/failure location so that entering 'next' in gdb would trigger consistency checker failure.

2. Add an option to allow "reverse debugging" (similar to rr). Since we have all stores logged, we could support applying and reverting them (directly in GDB perhaps? maybe we could just implement some gdb script/parser from a storelog?)