On Mon, Dec 2, 2019 at 6:15 PM Sean Christopherson
<sean.j.christopherson@xxxxxxxxx> wrote:
>
> On Thu, Sep 26, 2019 at 04:18:09PM -0700, Ben Gardon wrote:
> > Add a utility for concurrent paging structure traversals. This iterator
> > uses several mechanisms to ensure that its accesses to paging structure
> > memory are safe, and that memory can be freed safely in the face of
> > lockless access. The purpose of the iterator is to create a unified
> > pattern for concurrent paging structure traversals and simplify the
> > implementation of other MMU functions.
> >
> > This iterator implements a pre-order traversal of PTEs for a given GFN
> > range within a given address space. The iterator abstracts away
> > bookkeeping on successful changes to PTEs, retrying on failed PTE
> > modifications, TLB flushing, and yielding during long operations.
> >
> > Signed-off-by: Ben Gardon <bgardon@xxxxxxxxxx>
> > ---
> > arch/x86/kvm/mmu.c | 455 ++++++++++++++++++++++++++++++++++++++++
> > arch/x86/kvm/mmutrace.h | 50 +++++
> > 2 files changed, 505 insertions(+)
>
> ...
>
> > +/*
> > + * Sets a direct walk iterator to seek the gfn range [start, end).
> > + * If end is greater than the maximum possible GFN, it will be changed to the
> > + * maximum possible gfn + 1. (Note that start/end is and inclusive/exclusive
> > + * range, so the last gfn to be interated over would be the largest possible
> > + * GFN, in this scenario.)
> > + */
> > +__attribute__((unused))
> > +static void direct_walk_iterator_setup_walk(struct direct_walk_iterator *iter,
> > + struct kvm *kvm, int as_id, gfn_t start, gfn_t end,
> > + enum mmu_lock_mode lock_mode)
>
> Echoing earlier patches, please introduce variables/flags/functions along
> with their users. I have a feeling you're adding some of the unused
> functions so that all flags/variables in struct direct_walk_iterator can
> be in place from the get-go, but that actually makes everything much harder
> to review.
>
> > +{
> > + BUG_ON(!kvm->arch.direct_mmu_enabled);
> > + BUG_ON((lock_mode & MMU_WRITE_LOCK) && (lock_mode & MMU_READ_LOCK));
> > + BUG_ON(as_id < 0);
> > + BUG_ON(as_id >= KVM_ADDRESS_SPACE_NUM);
> > + BUG_ON(!VALID_PAGE(kvm->arch.direct_root_hpa[as_id]));
> > +
> > + /* End cannot be greater than the maximum possible gfn. */
> > + end = min(end, 1ULL << (PT64_ROOT_4LEVEL * PT64_PT_BITS));
> > +
> > + iter->as_id = as_id;
> > + iter->pt_path[PT64_ROOT_4LEVEL - 1] =
> > + (u64 *)__va(kvm->arch.direct_root_hpa[as_id]);
> > +
> > + iter->walk_start = start;
> > + iter->walk_end = end;
> > + iter->target_gfn = start;
> > +
> > + iter->lock_mode = lock_mode;
> > + iter->kvm = kvm;
> > + iter->tlbs_dirty = 0;
> > +
> > + direct_walk_iterator_start_traversal(iter);
> > +}
>
> ...
>
> > +static void direct_walk_iterator_cond_resched(struct direct_walk_iterator *iter)
> > +{
> > + if (!(iter->lock_mode & MMU_LOCK_MAY_RESCHED) || !need_resched())
> > + return;
> > +
> > + direct_walk_iterator_prepare_cond_resched(iter);
> > + cond_resched();
> > + direct_walk_iterator_finish_cond_resched(iter);
> > +}
> > +
> > +static bool direct_walk_iterator_next_pte(struct direct_walk_iterator *iter)
> > +{
> > + /*
> > + * This iterator could be iterating over a large number of PTEs, such
> > + * that if this thread did not yield, it would cause scheduler\
> > + * problems. To avoid this, yield if needed. Note the check on
> > + * MMU_LOCK_MAY_RESCHED in direct_walk_iterator_cond_resched. This
> > + * iterator will not yield unless that flag is set in its lock_mode.
> > + */
> > + direct_walk_iterator_cond_resched(iter);
>
> This looks very fragile, e.g. one of the future patches even has to avoid
> problems with this code by limiting the number of PTEs it processes.
With this, functions either need to limit the number of PTEs they
process or pass the MMU_LOCK_MAY_RESCHED to the iterator. It would
probably be safer to invert the flag and make it
MMU_LOCK_MAY_NOT_RESCHED for functions that can self-regulate the
number of PTEs they process or have weird synchronization
requirements. For example, the page fault handler can't reschedule and
we know it won't process many entries, so we could pass
MMU_LOCK_MAY_NOT_RESCHED in there.
>
> > +
> > + while (true) {
> > + if (!direct_walk_iterator_next_pte_raw(iter))
>
> Implicitly initializing the iterator during next_pte_raw() is asking for
> problems, e.g. @walk_in_progress should not exist. The standard kernel
> pattern for fancy iterators is to wrap the initialization, deref, and
> advancement operators in a macro, e.g. something like:
>
> for_each_direct_pte(...) {
>
> }
>
> That might require additional control flow logic in the users of the
> iterator, but if so that's probably a good thing in terms of readability
> and robustness. E.g. verifying that rcu_read_unlock() is guaranteed to
> be called is extremely difficult as rcu_read_lock() is buried in this
> low level helper but the iterator relies on the top-level caller to
> terminate traversal.
>
> See mem_cgroup_iter_break() for one example of handling an iter walk
> where an action needs to taken when the walk terminates early.
>
> > + return false;
> > +
> > + direct_walk_iterator_recalculate_output_fields(iter);
> > + if (iter->old_pte != DISCONNECTED_PTE)
> > + break;
> > +
> > + /*
> > + * The iterator has encountered a disconnected pte, so it is in
> > + * a page that has been disconnected from the root. Restart the
> > + * traversal from the root in this case.
> > + */
> > + direct_walk_iterator_reset_traversal(iter);
>
> I understand wanting to hide details to eliminate copy-paste, but this
> goes too far and makes it too difficult to understand the flow of the
> top-level walks. Ditto for burying retry_pte() in set_pte(). I'd say it
> also applies to skip_step_down(), but AFAICT that's dead code.
>
> Off-topic for a second, the super long direct_walk_iterator_... names
> make me want to simply call this new MMU the "tdp MMU" and just live with
> the discrepancy until the old shadow-based TDP MMU can be nuked. Then we
> could have tdp_iter_blah_blah_blah(), for_each_tdp_present_pte(), etc...
>
> Back to the iterator, I think it can be massaged into a standard for loop
> approach without polluting the top level walkers much. The below code is
> the basic idea, e.g. the macros won't compile, probably doesn't terminate
> the walk correct, rescheduling is missing, etc...
>
> Note, open coding the down/sideways/up helpers is 50% personal preference,
> 50% because gfn_start and gfn_end are now local variables, and 50% because
> it was the easiest way to learn the code. I wouldn't argue too much about
> having one or more of the helpers.
>
>
> static void tdp_iter_break(struct tdp_iter *iter)
> {
> /* TLB flush, RCU unlock, etc...)
> }
>
> static void tdp_iter_next(struct tdp_iter *iter, bool *retry)
> {
> gfn_t gfn_start, gfn_end;
> u64 *child_pt;
>
> if (*retry) {
> *retry = false;
> return;
> }
>
> /*
> * Reread the pte before stepping down to avoid traversing into page
> * tables that are no longer linked from this entry. This is not
> * needed for correctness - just a small optimization.
> */
> iter->old_pte = READ_ONCE(*iter->ptep);
>
> /* Try to step down. */
> child_pt = pte_to_child_pt(iter->old_pte, iter->level);
> if (child_pt) {
> child_pt = rcu_dereference(child_pt);
> iter->level--;
> iter->pt_path[iter->level - 1] = child_pt;
> return;
> }
>
> step_sideways:
> /* Try to step sideways. */
> gfn_start = ALIGN_DOWN(iter->target_gfn,
> KVM_PAGES_PER_HPAGE(iter->level));
> gfn_end = gfn_start + KVM_PAGES_PER_HPAGE(iter->level)
>
> /*
> * If the current gfn maps past the target gfn range, the next entry in
> * the current page table will be outside the target range.
> */
> if (gfn_end >= iter->walk_end ||
> !(gfn_end % KVM_PAGES_PER_HPAGE(iter->level + 1))) {
> /* Try to step up. */
> iter->level++;
>
> if (iter->level > PT64_ROOT_4LEVEL; {
> /* This is ugly, there's probably a better solution. */
> tdp_iter_break(iter);
> return;
> }
> goto step_sideways;
> }
>
> iter->target_gfn = gfn_end;
> iter->ptep = iter->pt_path[iter->level - 1] +
> PT64_INDEX(iter->target_gfn << PAGE_SHIFT, iter->level);
> iter->old_pte = READ_ONCE(*iter->ptep);
> }
>
> #define for_each_tdp_pte(iter, start, end, retry)
> for (tdp_iter_start(&iter, start, end);
> iter->level <= PT64_ROOT_4LEVEL;
> tdp_iter_next(&iter, &retry))
>
> #define for_each_tdp_present_pte(iter, start, end, retry)
> for_each_tdp_pte(iter, start, end, retry)
> if (!is_present_direct_pte(iter->old_pte)) {
>
> } else
>
> #define for_each_tdp_present_leaf_pte(iter, start, end, retry)
> for_each_tdp_pte(iter, start, end, retry)
> if (!is_present_direct_pte(iter->old_pte) ||
> !is_last_spte(iter->old_pte, iter->level))
> {
>
> } else
>
> /*
> * Marks the range of gfns, [start, end), non-present.
> */
> static bool zap_direct_gfn_range(struct kvm *kvm, int as_id, gfn_t start,
> gfn_t end, enum mmu_lock_mode lock_mode)
> {
> struct direct_walk_iterator iter;
> bool retry;
>
> tdp_iter_init(&iter, kvm, as_id, lock_mode);
>
> restart:
> retry = false;
> for_each_tdp_present_pte(iter, start, end, retry) {
> if (tdp_iter_set_pte(&iter, 0))
> retry = true;
>
> if (tdp_iter_disconnected(&iter)) {
> tdp_iter_break(&iter);
> goto restart;
> }
> }
> }
>
