Comment 7 for bug 1816086

Reviewed: https://review.opendev.org/670182
Committed: https://git.openstack.org/cgit/openstack/nova/commit/?id=00e5e3a7443dd31720244497013b040729490dcd
Submitter: Zuul
Branch: stable/rocky

commit 00e5e3a7443dd31720244497013b040729490dcd
Author: Eric Fried <email address hidden>
Date: Fri Feb 15 10:54:36 2019 -0600

    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 8c797450cbff5194fb6791cd0a07fa060dc8af72)
    (cherry picked from commit 754d8eb76c6fcd539fc2c32f0e2f90f6503b9f0c)