From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51952) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1X04t2-00047f-OY for qemu-devel@nongnu.org; Thu, 26 Jun 2014 04:18:34 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1X04sx-0004sc-A8 for qemu-devel@nongnu.org; Thu, 26 Jun 2014 04:18:28 -0400 Received: from mail-wg0-x229.google.com ([2a00:1450:400c:c00::229]:62131) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1X04sw-0004sK-QF for qemu-devel@nongnu.org; Thu, 26 Jun 2014 04:18:23 -0400 Received: by mail-wg0-f41.google.com with SMTP id a1so3201520wgh.12 for ; Thu, 26 Jun 2014 01:18:21 -0700 (PDT) Message-ID: <53ABD74A.2070607@gmail.com> Date: Thu, 26 Jun 2014 11:18:18 +0300 From: Avi Kivity MIME-Version: 1.0 References: <53AB0C7C.1050805@gmail.com> In-Reply-To: <53AB0C7C.1050805@gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] memory: memory_region_transaction_commit() slow List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Etienne Martineau , gonglei , Fam , Paolo Bonzini , Peter Crosthwaite , qemu-devel@nongnu.org On 06/25/2014 08:53 PM, Etienne Martineau wrote: > Hi, > > It seems to me that there is a scale issue O(n) in memory_region_transaction_commit(). It's actually O(n^3). Flatview is kept sorted but is just a vector, so if you insert n regions, you have n^2 operations. In addition every PCI device has an address space, so we get n^3 (technically the third n is different from the first two, but they are related). The first problem can be solved by implementing Flatview with an std::set<> or equivalent, the second by memoization - most pci address spaces are equal (they only differ based on whether bus mastering is enabled or not), so a clever cache can reduce the effort to generate them. However I'm not at all sure that the problem is cpu time in qemu. It could be due to rcu_synchronize delays when the new memory maps are fed to kvm and vfio. I recommend trying to isolate exactly where the time is spent. > Basically the time it takes to rebuild the memory view during device assignment > pci_bridge_update_mappings() increase linearly with respect to the number of > device already assigned to the guest. > > I'm running on a recent qemu.git and I merged from git://github.com/bonzini/qemu.git memory > the following patches that seems to be related to the scale issue I'm facing: > Fam Zheng (1): > memory: Don't call memory_region_update_coalesced_range if nothing changed > Gonglei (1): > memory: Don't update all memory region when ioeventfd changed > > Those patches help but don't fix the issue. The problem become more noticeable > when lots of device are being assigned to the guest. > > I'm running my test on a QEMU q35 machine with the following topology: > ioh3420 ( root port ) > x3130-upstream > xio3130-downstream > xio3130-downstream > xio3130-downstream > ... > > I have added instrumentation in kvm_cpu_exec() to track to amount of time spend > in the emulation ( patch at the end but not relevant for this discussion ) > > Here what I see when I assign device one after to other. NOTE the time-stamp is in > msec. The linear increase in the time comes from memory_region_transaction_commit(). > > (qemu) device_add pci-assign,host=28:10.1,bus=pciehp.3.7 > QEMU long exit vCPU 0 25 2 > QEMU long exit vCPU 0 22 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 22 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 21 2 > QEMU long exit vCPU 0 45 2 <<< > QEMU long exit vCPU 0 23 2 > > (qemu) device_add pci-assign,host=28:10.2,bus=pciehp.3.8 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 23 2 > QEMU long exit vCPU 0 49 2 <<< > QEMU long exit vCPU 0 25 2 > > > (qemu) device_add pci-assign,host=28:10.3,bus=pciehp.3.9 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 25 2 > QEMU long exit vCPU 0 25 2 > QEMU long exit vCPU 0 25 2 > QEMU long exit vCPU 0 25 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 24 2 > QEMU long exit vCPU 0 52 2 <<< > QEMU long exit vCPU 0 26 2 > > (qemu) device_add pci-assign,host=28:10.4,bus=pciehp.3.10 > QEMU long exit vCPU 0 35 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 27 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 26 2 > QEMU long exit vCPU 0 56 2 <<< > QEMU long exit vCPU 0 28 2 > > (qemu) device_add pci-assign,host=28:10.5,bus=pciehp.3.11 > QEMU long exit vCPU 0 33 2 > QEMU long exit vCPU 0 30 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 29 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 28 2 > QEMU long exit vCPU 0 59 2 <<< > QEMU long exit vCPU 0 30 2 > > > > diff --git a/kvm-all.c b/kvm-all.c > index 3ae30ee..e3a1964 100644 > --- a/kvm-all.c > +++ b/kvm-all.c > @@ -1685,6 +1685,8 @@ int kvm_cpu_exec(CPUState *cpu) > { > struct kvm_run *run = cpu->kvm_run; > int ret, run_ret; > + int64_t clock_ns, delta_ms; > + __u32 last_exit_reason, last_vcpu; > > DPRINTF("kvm_cpu_exec()\n"); > > @@ -1711,6 +1713,12 @@ int kvm_cpu_exec(CPUState *cpu) > } > qemu_mutex_unlock_iothread(); > > + delta_ms = (get_clock() - clock_ns)/(1000*1000); > + if( delta_ms >= 10){ > + fprintf(stderr, "QEMU long exit vCPU %d %ld %d\n",last_vcpu, > + delta_ms, last_exit_reason); > + } > + > run_ret = kvm_vcpu_ioctl(cpu, KVM_RUN, 0); > > qemu_mutex_lock_iothread(); > @@ -1727,7 +1735,15 @@ int kvm_cpu_exec(CPUState *cpu) > abort(); > } > > + /* > + * Capture exit reasons > + */ > + clock_ns = get_clock(); > + last_exit_reason = run->exit_reason; > + last_vcpu = cpu->cpu_index; > + > > thanks, > Etienne >