• Takuya Yoshikawa's avatar
    KVM: MMU: Improve iteration through sptes from rmap · 1e3f42f0
    Takuya Yoshikawa authored
    Iteration using rmap_next(), the actual body is pte_list_next(), is
    inefficient: every time we call it we start from checking whether rmap
    holds a single spte or points to a descriptor which links more sptes.
    
    In the case of shadow paging, this quadratic total iteration cost is a
    problem.  Even for two dimensional paging, with EPT/NPT on, in which we
    almost always have a single mapping, the extra checks at the end of the
    iteration should be eliminated.
    
    This patch fixes this by introducing rmap_iterator which keeps the
    iteration context for the next search.  Furthermore the implementation
    of rmap_next() is splitted into two functions, rmap_get_first() and
    rmap_get_next(), to avoid repeatedly checking whether the rmap being
    iterated on has only one spte.
    
    Although there seemed to be only a slight change for EPT/NPT, the actual
    improvement was significant: we observed that GET_DIRTY_LOG for 1GB
    dirty memory became 15% faster than before.  This is probably because
    the new code is easy to make branch predictions.
    
    Note: we just remove pte_list_next() because we can think of parent_ptes
    as a reverse mapping.
    Signed-off-by: default avatarTakuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
    Signed-off-by: default avatarAvi Kivity <avi@redhat.com>
    1e3f42f0
mmu_audit.c 6.58 KB