On Tue, Dec 15, 2020 at 06:38:02PM -0600, Josh Poimboeuf wrote: > On Tue, Dec 15, 2020 at 03:54:08PM +0100, Peter Zijlstra wrote: > > The problem is that a single instance of unwind information (ORC) must > > capture and correctly unwind all alternatives. Since the trivially > > correct mandate is out, implement the straight forward brute-force > > approach: > > > > 1) generate CFI information for each alternative > > > > 2) unwind every alternative with the merge-sort of the previously > > generated CFI information -- O(n^2) > > > > 3) for any possible conflict: yell. > > > > 4) Generate ORC with merge-sort > > > > Specifically for 3 there are two possible classes of conflicts: > > > > - the merge-sort itself could find conflicting CFI for the same > > offset. > > > > - the unwind can fail with the merged CFI. > > So much algorithm. :-) It's not really hard, but it has a few pesky details (as always). > Could we make it easier by caching the shared > per-alt-group CFI state somewhere along the way? Yes, but when I tried it grew the code required. Runtime costs would be less, but I figured that since alternatives are typically few and small, that wasn't a real consideration. That is, it would basically cache the results of find_alt_unwind(), but you still need find_alt_unwind() to generate that data, and so you gain the code for filling and using the extra data structure. Yes, computing it 3 times is naf, but meh. > [ 'offset' is a byte offset from the beginning of the group. It could > be calculated based on 'orig_insn' or 'orig_insn->alts', depending on > whether 'insn' is an original or a replacement. ] That's exactly what it already does ofcourse ;-) > If the array entry is NULL, just update it with a pointer to the CFI. > If it's not NULL, make sure it matches the existing CFI, and WARN if it > doesn't. > > Also, with this data structure, the ORC generation should also be a lot > more straightforward, just ignore the NULL entries. Yeah, I suppose it gets rid of the memcmp-prev thing. > Thoughts? This is all theoretical of course, I could try to do a patch > tomorrow. No real objection, I just didn't do it because 1) it works, and 2) even moar lines. _______________________________________________ Virtualization mailing list Virtualization@xxxxxxxxxxxxxxxxxxxxxxxxxx https://lists.linuxfoundation.org/mailman/listinfo/virtualization
