]> git.baikalelectronics.ru Git - kernel.git/commit
KVM: MMU: Improve iteration through sptes from rmap
authorTakuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
Wed, 21 Mar 2012 14:50:34 +0000 (23:50 +0900)
committerAvi Kivity <avi@redhat.com>
Sun, 8 Apr 2012 13:08:27 +0000 (16:08 +0300)
commit8f33cca6527d2a65488cc6268c13db4a701cfcf0
tree0ceba904d28e89ded0954dcf40361a6ec235cce3
parent2cc417b120266d962507cb4b214133ab8cc0b69f
KVM: MMU: Improve iteration through sptes from rmap

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: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
Signed-off-by: Avi Kivity <avi@redhat.com>
arch/x86/kvm/mmu.c
arch/x86/kvm/mmu_audit.c