DynamoRIO
Support dr_delete_fragment for shared cache
Currently, dr_delete_fragment() is only supported for thread private caches.
This issue relates to adding support for dr_delete_fragment() to shared caches.
Initial information can be found in the user-group here. I am now migrating updates to Github as they are more technical in relation to DR's internals.
"I initially tried making use of the fragment_remove_shared_no_flush(). This function seemed promising because a quick look at its code showed it handles thread locking for us. However, this approach was scrapped as it was not clear how to resolve a problem associated with lock ranking order."
"Moving on; let’s investigate how dr_delete_fragment() works for thread private caches and see if we can use similar code infrastructure. Essentially the boilerplate code does the following: (1) looks up the fragment instance via fragment_lookup(), (2) appends the fragment’s tag in the client_data’s todo list found in drcontext, (3) unlinks the fragment via unlink_fragment_incoming(), and lastly (4) removes the fragment from IBT tables via fragment_remove_from_ibt_tables(). This function takes a boolean parameter, namely from_shared, which indicates whether shared IBT tables should be considered. Since current implementation of dr_delete_fragment considers private caches, the boolean is set to false (I guess I’ll have to set this to true?).
I haven’t figured out yet what the purpose of is_couldbelinking() is in the context of dr_delete_fragment().
Once the function exits, the todo list is later processed by the dispatcher upon exit of the fcache. The list is iterated and for each element representing an old fragment the delete_fragment function is called (there is a bunch of code related to fragment replacement which is not important for what I’m are trying to do).
The delete_fragment() function takes an action parameter, which indicates the resources to delete. In this case, FRAGDEL_ALL is passed. Moreover, one possible value of action is FRAGDEL_NEED_CHLINK_LOCK. This enables some locking functionality for linking (perhaps this might be useful/needed for shared cache imp.)
Now studying the delete_fragment() function; pretty much what one would expect; performs (again?) unlinking of the fragment, as well as removes its vmarea and its entry in the fcache. The deletion/removal of resources done in accordance to flags specified by the action parameter. The function also calls the delete fragment hook (if set up by client)."
"So, I think the steps to achieve this functionality are as follows:
-
In dr_delete_fragment, call the unlink_fragment_incoming() but acquire the change_linking_lock
-
Call fragment_remove_from_ibt_tables(), and pass true for from_shared. I will also need to somehow synch threads to a safe-point before calling this function in accordance to docs:
/* Removes f from any IBT tables it is in. * If f is in a shared table, only removes if from_shared is true, in * which case dcontext must be GLOBAL_DCONTEXT and we must have * dynamo_all_threads_synched (case 10137). */
- I think I will need to pass FRAGDEL_NEED_CHLINK_LOCK when calling delete_fragment as the function calls some unlinking methods.
"Alternatively, another approach is to directly call delete_fragment (with threads all synched), and then require the user to call dr_redirect_execution() (like dr_flush_region). Let's try this approach first and avoid the drcontext-specific todo list."
Close but no cigar. Almost works, but I am getting a rank violation due to fragment delete mutex set here:
/* XXX: I added the test for FRAG_WAS_DELETED for i#759: does sideline
* look at fragments after that is set? If so need to resolve rank order
* w/ shared_cache_lock.
*/
if (!TEST(FRAG_WAS_DELETED, f->flags) &&
(!TEST(FRAGDEL_NO_HEAP, actions) || !TEST(FRAGDEL_NO_FCACHE, actions))) {
acquired_fragdel_lock = true;
fragment_get_fragment_delete_mutex(dcontext);
}
If I comment out the setting of that mutex, all seems to work... but pretty sure I am introducing a race here as the fragment being deleted does not have its flags satisfy TEST(FRAG_WAS_DELETED, f->flags)
couldbelinking is described in the code: https://github.com/DynamoRIO/dynamorio/blob/master/core/fragment.h#L986
However, this approach was scrapped as it was not clear how to resolve a problem associated with lock ranking order.
Depending on the locks, the order can be changed if all other constraints are still met.
What does it mean to have safe access in the context of couldbelinking?
https://github.com/DynamoRIO/dynamorio/blob/041d94b091f11122e48106a98e23a3a33e997bf6/core/fragment.h#L991
enter_couldbelinking(dcontext_t *dcontext, fragment_t *watch, bool temporary) does not seem to suspend threads. How is it ensuring safe access?
https://github.com/DynamoRIO/dynamorio/blob/041d94b091f11122e48106a98e23a3a33e997bf6/core/fragment.c#L5747
Thanks
Okay, I managed. I'll make a PR in the weekend! Answers to the above questions would still be appreciated nonetheless.
"safe" just means "correct", "race-free". See flush_fragments_synch_priv() where it uses mutexes to ensure each other thread is in a state safe for unlinking.
The initial design of dynamic case handling performed by drbbdup assumes that traces are disabled. The rationale behind this decision is to allow drbbdup to flush, via a specified tag, the basic block required to handle the new case, thus motivating this issue.
I would now like to support dynamic handling for traces as well (currently, drbbdup works fine with traces when dynamic handling is not enabled). The problem is that traces and basic blocks can potentially share tags and therefore there can be inconsistencies with the bb and trace cache. In particular, given how DR core shadows the bb cache and gives precedence to traces, flushing a fragment based on a tag will correspond to the trace and not the basic block, keeping it stale inside the bb cache.
One way of getting around this is to use the dr_unlink_flush_region() API function, passing a PC that is contained in the target fragment. However, this approach is slow because the API function also flushes different-formed basic blocks that also contain the PC (hence motivating this issue as well).
Perhaps, dr_delete_fragment(), proposed in this issue, should be extensive in the sense that it tries to flush both traces and basic blocks associated with the passed tag. The only issue relates to flushing traces where the target basic block is not the head of the trace. How will these traces get updated?
@derekbruening Do you understand this problem and any thoughts please?
given how DR core shadows the bb cache and gives precedence to traces, flushing a fragment based on a tag will correspond to the trace and not the basic block, keeping it stale inside the bb cache.
I thought the bb with the tag of the trace was deleted once the trace was created. (There is an option for shared: -remove_shared_trace_heads, which is on by default.) So there would only be one shared fragment with a given tag, and only one private per thread, in steady state; there are brief periods with duplications.
The only issue relates to flushing traces where the target basic block is not the head of the trace. How will these traces get updated?
But I thought you said you were not interested in covering all fragments that include code from the original app block: just all blocks that start with a given tag. So I'm not sure what the concern is here? If you want to update all fragments containing code that came from a source app region I think you would have to go through the flush routines.
The only issue relates to flushing traces where the target basic block is not the head of the trace. How will these traces get updated?
But I thought you said you were not interested in covering all fragments that include code from the original app block: just all blocks that start with a given tag. So I'm not sure what the concern is here? If you want to update all fragments containing code that came from a source app region I think you would have to go through the flush routines.
I am interested in flushing a specific-structured basic block and all traces that include (not necessarily at the head) this basic block. Existing flush routines would target other different structured basic blocks that contain the PC and therefore is something I want to avoid due to performance.
Does that make sense?
The trace_t structure does record the tags of all constituent basic blocks that make up a trace, but today you would have to search all traces (can limit to the vmarea of the block): there's no fast lookup. That search is probably a lot faster than a flush though since the flush would typically include all the fragments in the vmarea being searched if not adjacent ones.