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.

Conflicts (rocky backport):
  nova/compute/provider_tree.py
     The return_root kwarg to _find_with_lock was added in stein.
  nova/tests/unit/virt/libvirt/test_driver.py
     and
  nova/virt/libvirt/driver.py
     are n/a because the code iterating over the provider tree roots was
     added in stein (for vgpu handling)

Change-Id: Ibf430a8bc2a2af9353b8cdf875f8506377a1c9c2
Closes-Bug: #1816086
(cherry picked from commit 8c797450cb)
(cherry picked from commit 754d8eb76c)

nova/compute/provider_tree.py

@@ -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 _
 
@@ -226,7 +227,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
@@ -325,7 +331,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)
@@ -339,7 +346,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
@@ -375,10 +383,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):
+        # 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: