libpcap
libpcap copied to clipboard
the-tcpdump-group
[optimizer] mark value as unknown when statement is deleted so it is …
…unavailable to successor blocks.
The libpcap optimizer removes statements as dead that store certain values but does not account for the fact that a successor block may attempt to read the value written by the dead statemenent. The proposed patch marks the "val" data structure as having unknown value when statements are removed as dead to indicate to successor blocks that the value is not available. Bug / test case is further documented here: https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=144325.
Thank you for proposing this change. The reasoning above should be a comment at the added line or at least a commit message.
Unless I'm missing something, you might want to put in a comment noting that we should perhaps not remove purportedly "dead" stores if, in fact, successor blocks try to use it (because that value is not "dead", in the sense of what I understand "dead" to mean, at that point).
This has some changes other than adding
vstore(0, &b->val[atom], VAL_UNKNOWN, 0);
at the end of opt_deadstores(); are those intentional, or does this change just need to be rebased?
The pull request has been corrected. The other changes were inadvertently included.
At the time the dead stores are removed they are dead. Without this patch, however, the next block is not aware that the store has been eliminated and eliminates additional instructions assuming the value will be available in a memory location.
At the time the dead stores are removed they are dead. Without this patch, however, the next block is not aware that the store has been eliminated and eliminates additional instructions assuming the value will be available in a memory location.
If the next block would be using the value, I wouldn't call the value "dead". It might be dead within the basic block, but "dead" should mean "not used in subsequent instructions in this block and not used in subsequent blocks", so that the store is removed only if no subsequent code in the program would do a load, not just if not subsequent code in the basic block would do a load.
To clarify what I think is happening. Take the following pseudo assembly:
#block 1 begins
...
calculate some_value
store some_value -> M[1]
...
# block 1 ends
# block 2 begins
calculate some_value
store some_value -> M[1]
... # M[1] stays unchanged here
load M[1]
...
When opt_deadstores optimizes Block 1, the first store of some_value to M[1] is deleted as M[1] is not used in the block and is indeed not needed for future blocks at the time of deletion. This is because Block 2 calculates some_value independently and stores it in M[1] for its use. The bug arises when Block 2 is subsequently optimized. Because the deletion of the first store instruction did not update the val array, opt_stmt and vstore assume it can NOP the second store instruction and inherit the value from the previous block. The bug fix prevents this from happening by updating val for, e.g., M[1] to VAL_UNKNOWN when the first store instruction is converted to a NOP. Assuming this is correct, I think it makes sense to characterize the first instruction as dead when it is deleted.
Thank you for updating this. BPF compiler and optimizer bugs tend to take a long time to solve.
Thank you for preparing this and the other optimizer bug fixes. The traditional complexity here is to make sure these changes not just fix known bugs, but also do not introduce new bugs. Since you have found that a number of other bugs likely have the same root cause, let's try to progress this matter before other backlog pieces.
If it is helpful, I've added some optimizer tests to the tcpdump testing framework here. I can add the test cases raised by the various issues/bug reports related to the optimizer if an optimizer test suite pull request would be of interest.
More tests would be welcome, but libpcap tests should go into libpcap repository rather than tcpdump. It should not require more than an additional shell script, I can add that first if it helps.
@infrastation - I've taken a pass (Commit here) at a test harness and test cases for the bugs that I believe are addressed by #972 and #976. Would you prefer a separate PR for that or integrate it into this one?
Thank you, that looks useful, I have left some comments. Please make it a separate pull request.