linux-kernel - [RFC PATCH 0/3] Weight-balanced binary tree + KVM growable memory slots using wbtree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 22 Feb 2011 11:54:49 -0700
From:	Alex Williamson <alex.williamson@...hat.com>
To:	avi@...hat.com
Cc:	alex.williamson@...hat.com, linux-kernel@...r.kernel.org,
	kvm@...r.kernel.org, mtosatti@...hat.com,
	xiaoguangrong@...fujitsu.com
Subject: [RFC PATCH 0/3] Weight-balanced binary tree + KVM growable memory
	slots using wbtree

This series introduces a new weight-balanced binary tree (wbtree) for
general use.  It's largely leveraged from the rbtree, copying it's
rotate functions, while introducing different rebalance and erase
functions.  This tree is particularly useful for managing memory
ranges, where it's desirable to have the most likely targets (the
largest ranges) at the top of each subtree.

Patches 2 & 3 go on to convert the KVM memory slots to a growable
array and make use of wbtree for efficient managment.  Trying to
exercise the worst case for this data structure, I ran netperf
TCP_RR on an emulated rtl8139 NIC connected directly to the host
via a tap.  Both qemu-kvm and the netserver on the host were
pinned to optimal CPUs with taskset.  This series resulted in
a 3% improvement for this test.

Note that part of why this series is RFC is that the print_tree
function in the last patch is debug code that generates output
for dot.  You can copy the output to a file and run:

  dot -Tpdf foo.dot > foo.pdf

to generate a nice diagram of the tree currently in use.  I'll
follow-up with a few examples.  Thanks,

Alex

---

Alex Williamson (3):
      kvm: Use weight-balanced tree for memory slot management
      kvm: Allow memory slot array to grow on demand
      Weight-balanced tree

 arch/ia64/include/asm/kvm_host.h    |    4 -
 arch/ia64/kvm/kvm-ia64.c            |    2 
 arch/powerpc/include/asm/kvm_host.h |    3 
 arch/s390/include/asm/kvm_host.h    |    3 
 arch/x86/include/asm/kvm_host.h     |    5 -
 arch/x86/include/asm/vmx.h          |    6 -
 arch/x86/kvm/mmu.c                  |   32 ++++-
 arch/x86/kvm/x86.c                  |    6 -
 include/linux/kvm_host.h            |   25 ++++
 include/linux/wbtree.h              |   55 +++++++++
 lib/Makefile                        |    3 
 lib/wbtree.c                        |  170 ++++++++++++++++++++++++++
 virt/kvm/kvm_main.c                 |  226 +++++++++++++++++++++++++++--------
 13 files changed, 464 insertions(+), 76 deletions(-)
 create mode 100644 include/linux/wbtree.h
 create mode 100644 lib/wbtree.c
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/