openstack
/
nova
Code Issues Proposed changes

Perf: Use dicts for ProviderTree roots 

ProviderTree used to keep track of root providers in a list. Since we
don't yet have sharing providers, this would always be a list of one for
non-ironic deployments, or N for ironic deployments of N nodes.

To find a provider (by name or UUID), we would iterate over this list,
an O(N) operation. For large ironic deployments, this added up fast -
see the referenced bug.

With this change, we store roots in two dicts: one keyed by UUID, one
keyed by name. To find a provider, we first check these dicts. If the
provider we're looking for is a root, this is now O(1). (If it's a
child, it would still be O(N), because we iterate over all the roots
looking for a descendant that matches. But ironic deployments don't have
child providers (yet?) (right?) so that should be n/a. For non-ironic
deployments it's unchanged: O(M) where M is the number of descendants,
which should be very small for the time being.)

Test note: Existing tests in nova.tests.unit.compute.test_provider_tree
thoroughly cover all the affected code paths. There was one usage of
ProviderTree.roots that was untested and broken (even before this
change) which is now fixed.

Change-Id: Ibf430a8bc2a2af9353b8cdf875f8506377a1c9c2
Closes-Bug: #1816086
This commit is contained in:
Eric Fried 2019-02-15 10:54:36 -06:00
parent 1f46fafcf5
commit 8c797450cb
3 changed files with 34 additions and 10 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

27
nova/compute/provider_tree.py
View File

@ -25,6 +25,7 @@ import os_traits
from oslo_concurrency import lockutils
from oslo_log import log as logging
from oslo_utils import uuidutils
import six
from nova.i18n import _
@ -232,7 +233,12 @@ class ProviderTree(object):
def __init__(self):
"""Create an empty provider tree."""
self.lock = lockutils.internal_lock(_LOCK_NAME)
self.roots = []
self.roots_by_uuid = {}
self.roots_by_name = {}
@property
def roots(self):
return six.itervalues(self.roots_by_uuid)
def get_provider_uuids(self, name_or_uuid=None):
"""Return a list, in top-down traversable order, of the UUIDs of all
@ -343,7 +349,8 @@ class ProviderTree(object):
provider = _Provider.from_dict(pd)
if parent_uuid is None:
self.roots.append(provider)
self.roots_by_uuid[provider.uuid] = provider
self.roots_by_name[provider.name] = provider
else:
parent = self._find_with_lock(parent_uuid)
parent.add_child(provider)
@ -357,7 +364,8 @@ class ProviderTree(object):
parent = self._find_with_lock(found.parent_uuid)
parent.remove_child(found)
else:
self.roots.remove(found)
del self.roots_by_uuid[found.uuid]
del self.roots_by_name[found.name]
def remove(self, name_or_uuid):
"""Safely removes the provider identified by the supplied name_or_uuid
@ -393,10 +401,21 @@ class ProviderTree(object):
raise ValueError(err % uuid)
p = _Provider(name, uuid=uuid, generation=generation)
self.roots.append(p)
self.roots_by_uuid[uuid] = p
self.roots_by_name[name] = p
return p.uuid
def _find_with_lock(self, name_or_uuid, return_root=False):
# Optimization for large number of roots (e.g. ironic): if name_or_uuid
# represents a root, this is O(1).
found = self.roots_by_uuid.get(name_or_uuid)
if found:
return found
found = self.roots_by_name.get(name_or_uuid)
if found:
return found
# Okay, it's a child; do it the hard way.
for root in self.roots:
found = root.find(name_or_uuid)
if found:

6
nova/tests/unit/virt/libvirt/test_driver.py
View File

@ -21530,7 +21530,8 @@ class LibvirtDriverTestCase(test.NoDBTestCase, TraitsComparisonMixin):
self.assertRaises(exception.ComputeResourcesUnavailable,
drvr._allocate_mdevs, allocations=allocations)
def test_allocate_mdevs_with_no_idea_of_the_provider(self):
@mock.patch.object(libvirt_driver.LOG, 'warning')
def test_allocate_mdevs_with_no_idea_of_the_provider(self, mock_warning):
drvr = libvirt_driver.LibvirtDriver(fake.FakeVirtAPI(), True)
# Mock the fact update_provider_tree() should have run
drvr.provider_tree = self._get_fake_provider_tree_with_vgpu()
@ -21557,6 +21558,9 @@ class LibvirtDriverTestCase(test.NoDBTestCase, TraitsComparisonMixin):
# Remember, rp2 has a wrong naming convention
self.assertRaises(exception.ComputeResourcesUnavailable,
drvr._allocate_mdevs, allocations=allocations)
mock_warning.assert_called_once_with(
"pGPU device name %(name)s can't be guessed from the ProviderTree "
"roots %(roots)s", {'name': 'oops_I_did_it_again', 'roots': 'cn'})
@mock.patch.object(libvirt_driver.LibvirtDriver, '_get_mediated_devices')
@mock.patch.object(libvirt_driver.LibvirtDriver,

11
nova/virt/libvirt/driver.py
View File

@ -6462,7 +6462,7 @@ class LibvirtDriver(driver.ComputeDriver):
rp_name = allocated_rp.name
# There can be multiple roots, we need to find the root name
# to guess the physical device name
roots = self.provider_tree.roots
roots = list(self.provider_tree.roots)
for root in roots:
if rp_name.startswith(root.name + '_'):
# The RP name convention is :
@ -6470,10 +6470,11 @@ class LibvirtDriver(driver.ComputeDriver):
parent_device = rp_name[len(root.name) + 1:]
break
else:
LOG.warning("pGPU device name %(name)s can't be guessed from "
"the ProviderTree "
"roots %(roots)s", {'name': rp_name,
'roots': roots})
LOG.warning(
"pGPU device name %(name)s can't be guessed from the "
"ProviderTree roots %(roots)s",
{'name': rp_name,
'roots': ', '.join([root.name for root in roots])})
# We f... have no idea what was the parent device
# If we can't find devices having available VGPUs, just raise
raise exception.ComputeResourcesUnavailable(