import threading
from queue import PriorityQueue
import json
from ThreadPool import ThreadPool
from constants import constants
from Logger import Logger
from SpecData import SPECS
from StringUtils import StringUtils
class DependencyGraphNode(object):
def __init__(self, packageName, packageVersion, pkgWeight):
self.packageName = packageName
self.packageVersion = packageVersion
self.buildRequiresPkgNodes = set() # Same as in spec file
self.installRequiresPkgNodes = set() # Same as in spec file
# Auxiliary build-requires packages.
#
# This is the result of "moving up" the (weak)
# install-requires package dependencies to their ancestors
# that actually need them as a build dependency (more details
# in the code below). This is used to optimize the dependency
# graph by reorganizing parent-child relationships based on
# strong dependencies.
self.auxBuildRequiresPkgNodes = set()
# Accumulated install-requires packages.
#
# This is mostly used as a helper when building the graph
# (specifically, as an intermediate step when computing
# auxBuildRequiredPkgNodes), and is later unused.
self.accumInstallRequiresPkgNodes = set()
self.childPkgNodes = set() # Packages that I depend on.
self.parentPkgNodes = set() # Packages that depend on me.
self.selfWeight = pkgWeight # Own package weight.
# Critical-chain-weight: The key scheduling metric.
#
# Weight of the critical chain that can be built starting from
# this package. Higher the criticalChainWeight, more the
# benefit from building this package as early as possible.
self.criticalChainWeight = 0
# Internal data-structure used to perform controlled
# traversals of the dependency graph, as well as certain
# sanity checks.
self.numVisits = 0
class Scheduler(object):
lock = threading.Lock()
listOfAlreadyBuiltPackages = set()
listOfPackagesToBuild = []
listOfPackagesCurrentlyBuilding = set()
sortedList = []
listOfPackagesNextToBuild = PriorityQueue()
listOfFailedPackages = []
priorityMap = {}
pkgWeights = {}
logger = None
event = None
stopScheduling = False
mapPackagesToGraphNodes = {}
@staticmethod
def setEvent(event):
Scheduler.event = event
@staticmethod
def setLog(logName, logPath, logLevel):
Scheduler.logger = Logger.getLogger(logName, logPath, logLevel)
@staticmethod
def setParams(sortedList, listOfAlreadyBuiltPackages):
Scheduler.sortedList = sortedList
Scheduler.listOfAlreadyBuiltPackages = listOfAlreadyBuiltPackages
for pkg in Scheduler.sortedList:
pkgName, pkgVersion = StringUtils.splitPackageNameAndVersion(pkg)
if (pkg not in Scheduler.listOfAlreadyBuiltPackages
or pkgName in constants.testForceRPMS):
Scheduler.listOfPackagesToBuild.append(pkg)
Scheduler.listOfPackagesCurrentlyBuilding = set()
Scheduler.listOfPackagesNextToBuild = PriorityQueue()
Scheduler.listOfFailedPackages = []
# When performing (only) make-check, package dependencies are
# irrelevant; i.e., all the packages can be "make-checked" in
# parallel. So skip building the dependency graph. This is not
# merely an optimization! A given package can define
# additional packages to be installed in its build environment
# when performing a make-check, under %if %{with_check}.
# However, these are not really build-time-dependencies in the
# usual sense; i.e., there is no ordering requirement when
# building these packages; they only make sense when running a
# `make check`. Hence, trying to build a dependency graph out
# of them will result in anomalies such as cycles in the
# graph. So skip building the graph altogether and schedule
# all the `make check`s in parallel.
skipGraphBuild = constants.rpmCheck
Scheduler._setPriorities(skipGraphBuild)
if constants.publishBuildDependencies:
# This must be called only after calling _setPriorities(),
# which builds the dependency graph.
Scheduler._publishBuildDependencies()
@staticmethod
def notifyPackageBuildCompleted(package):
with Scheduler.lock:
if package in Scheduler.listOfPackagesCurrentlyBuilding:
Scheduler.listOfPackagesCurrentlyBuilding.remove(package)
Scheduler.listOfAlreadyBuiltPackages.add(package)
@staticmethod
def notifyPackageBuildFailed(package):
with Scheduler.lock:
if package in Scheduler.listOfPackagesCurrentlyBuilding:
Scheduler.listOfPackagesCurrentlyBuilding.remove(package)
Scheduler.listOfFailedPackages.append(package)
@staticmethod
def isAllPackagesBuilt():
if Scheduler.listOfPackagesToBuild:
return False
return True
@staticmethod
def isAnyPackagesFailedToBuild():
if Scheduler.listOfFailedPackages:
return True
return False
@staticmethod
def getNextPackageToBuild():
with Scheduler.lock:
if Scheduler.stopScheduling:
return None
if not Scheduler.listOfPackagesToBuild:
if Scheduler.event is not None:
Scheduler.event.set()
if Scheduler.listOfPackagesNextToBuild.empty():
Scheduler._getListNextPackagesReadyToBuild()
if Scheduler.listOfPackagesNextToBuild.empty():
return None
packageTup = Scheduler.listOfPackagesNextToBuild.get()
package = packageTup[1]
if Scheduler.listOfPackagesNextToBuild.qsize() > 0:
ThreadPool.activateWorkerThreads(
Scheduler.listOfPackagesNextToBuild.qsize())
Scheduler.listOfPackagesCurrentlyBuilding.add(package)
Scheduler.listOfPackagesToBuild.remove(package)
return package
@staticmethod
def getDoneList():
return list(Scheduler.listOfAlreadyBuiltPackages)
@staticmethod
def _publishBuildDependencies():
Scheduler.logger.debug("Publishing Build dependencies")
dependencyLists = {}
for package in list(Scheduler.mapPackagesToGraphNodes.keys()):
dependencyLists[package] = []
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
for childPkg in list(pkgNode.childPkgNodes):
dependencyLists[package].append(childPkg.packageName + "-" + childPkg.packageVersion)
with open(str(constants.logPath) + "/BuildDependencies.json", 'w') as graphfile:
graphfile.write(json.dumps(dependencyLists, sort_keys=True, indent=4))
@staticmethod
def __getRequiredTypePackages(pkg, requiresType):
listRPMPackages = []
if requiresType == "build":
listRPMPackages.extend(SPECS.getData().getBuildRequiresForPkg(pkg))
elif requiresType == "install":
listRPMPackages.extend(SPECS.getData().getRequiresAllForPkg(pkg))
# Remove duplicates.
listRPMPackages = list(set(listRPMPackages))
listPackages = set()
for reqPkg in listRPMPackages:
basePkg = SPECS.getData().getBasePkg(reqPkg)
listPackages.add(basePkg)
return list(listPackages)
@staticmethod
def _getBuildRequiredPackages(pkg):
return Scheduler.__getRequiredTypePackages(pkg, "build")
@staticmethod
def _getRequiredPackages(pkg):
return Scheduler.__getRequiredTypePackages(pkg, "install")
def _createGraphNodes():
# GRAPH-BUILD STEP 1: Initialize graph nodes for each package.
#
# Create a graph with a node to represent every package and all
# its dependent packages in the given list.
for package in Scheduler.sortedList:
packageName, packageVersion = StringUtils.splitPackageNameAndVersion(package)
node = DependencyGraphNode(packageName, packageVersion,
Scheduler._getWeight(package))
Scheduler.mapPackagesToGraphNodes[package] = node
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
for childPackage in Scheduler._getBuildRequiredPackages(package):
childPkgNode = Scheduler.mapPackagesToGraphNodes[childPackage]
pkgNode.buildRequiresPkgNodes.add(childPkgNode)
for childPackage in Scheduler._getRequiredPackages(package):
childPkgNode = Scheduler.mapPackagesToGraphNodes[childPackage]
pkgNode.installRequiresPkgNodes.add(childPkgNode)
# GRAPH-BUILD STEP 2: Mark package dependencies in the graph.
#
# Add parent-child relationships between dependent packages.
# If a package 'A' build-requires or install-requires package 'B', then:
# - Mark 'B' as a child of 'A' in the graph.
# - Mark 'A' as a parent of 'B' in the graph.
#
# A
#
# / \
# v v
#
# B C
#
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
for childPkgNode in pkgNode.buildRequiresPkgNodes:
pkgNode.childPkgNodes.add(childPkgNode)
childPkgNode.parentPkgNodes.add(pkgNode)
for childPkgNode in pkgNode.installRequiresPkgNodes:
pkgNode.childPkgNodes.add(childPkgNode)
childPkgNode.parentPkgNodes.add(pkgNode)
def _optimizeGraph():
# GRAPH-BUILD STEP 3: Convert weak (install-requires) dependencies
# into strong (aux-build-requires) dependencies.
#
# Consider the following graph on the left, where package 'A'
# install-requires 'B' and build-requires 'C'. Package 'C'
# install-requires 'D'. Package 'D' build-requires 'E' and
# install-requires 'F'.
#
# b : build-requires dependency
# i : install-requires dependency
# aux-b : auxiliary build-requires dependency (explained later)
#
# Now, we know that install-requires dependencies are weaker
# than build-requires dependencies. That is, for example, in the
# original graph below, package 'B' does not need to be built
# before package 'A', but package 'C' must be built before
# package 'A'.
#
# Using this knowledge, we optimize the graph by re-organizing
# the dependencies such that all of them are strong (we call
# these newly computed build-dependencies as "auxiliary build
# dependencies"). The optimized graph for the example below is
# presented on the right -- the key property of the optimized
# graph is that every child package *MUST* be built before its
# parent(s). This process helps relax package dependencies to
# a great extent, by giving us the flexibility to delay
# building certain packages until they are actually needed.
# Another important benefit of this optimization is that it
# nullifies certain dependencies altogether (eg: A->B), thereby
# enabling a greater level of build-parallelism.
#
# Original Graph Optimized Graph
# +
# A | B A
# +
# i / \ b | b/ |aux-b \aux-b
# / \ + / | \
# v v | v v v
# +
# B C | C D F
# +
# \i | b/
# \ + /
# v | v
# +
# D | E
# +
# b/ \i |
# / \ +
# v v |
# +
# E F |
#
#
# In the code below, we use 'accumulated-install-requires' set
# as a placeholder to bubble-up install-requires dependencies of
# each package to all its ancestors. In each such path, we look
# for the nearest ancestor that has a build-requires dependency
# on that path going up from the given package to that ancestor.
# If we find such an ancestor, we convert the bubbled-up
# install-requires packages accumulated so far into the
# auxiliary-build-requires set at that ancestor. (This is how
# 'D' and 'F' become aux-build-requires of 'A' in the optimized
# graph above).
#
# Graph Traversal : Bottom-up (starting with packages that
# have no children).
#
nodesToVisit = set()
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
if len(pkgNode.childPkgNodes) == 0:
nodesToVisit.add(pkgNode)
while nodesToVisit:
pkgNode = nodesToVisit.pop()
pkgNode.accumInstallRequiresPkgNodes |= pkgNode.installRequiresPkgNodes
if len(pkgNode.childPkgNodes) == 0:
# Count self-visit if you don't expect any other
# visitors.
pkgNode.numVisits += 1
for parentPkgNode in pkgNode.parentPkgNodes:
if (pkgNode not in parentPkgNode.buildRequiresPkgNodes) and \
(pkgNode not in parentPkgNode.installRequiresPkgNodes):
raise Exception ("Visitor to parent is not its child " + \
" Visitor: " + pkgNode.packageName + \
" Parent: " + parentPkgNode.packageName)
if pkgNode in parentPkgNode.buildRequiresPkgNodes:
parentPkgNode.auxBuildRequiresPkgNodes |= pkgNode.accumInstallRequiresPkgNodes
else:
parentPkgNode.accumInstallRequiresPkgNodes |= pkgNode.accumInstallRequiresPkgNodes
parentPkgNode.numVisits += 1
# Each child is expected to visit the parent once.
# Note that a package might have the same packages as
# both build-requires and install-requires children.
# They don't count twice.
numExpectedVisits = len(parentPkgNode.childPkgNodes)
if parentPkgNode.numVisits == numExpectedVisits:
nodesToVisit.add(parentPkgNode)
elif parentPkgNode.numVisits > numExpectedVisits:
raise Exception ("Parent node visit count > num of children " + \
" Parent node: " + parentPkgNode.packageName + \
" Visit count: " + str(parentPkgNode.numVisits) + \
" Num of children: " + str(numExpectedVisits))
pkgNode.accumInstallRequiresPkgNodes.clear()
# Clear out the visit counter for reuse.
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
if pkgNode.numVisits == 0:
raise Exception ("aux-build-requires calculation never visited " \
"package " + pkgNode.packageName)
else:
pkgNode.numVisits = 0
# GRAPH-BUILD STEP 4: Re-organize the dependencies in the graph based on
# the above optimization.
#
# Now re-arrange parent-child relationships between packages using the
# following criteria:
# If a package 'A' build-requires or aux-build-requires package 'B', then:
# - Mark 'B' as a child of 'A' in the graph.
# - Mark 'A' as a parent of 'B' in the graph.
# If a package 'A' only install-requires package 'B', then:
# - Remove 'B' as a child of 'A' in the graph.
# - Remove 'A' as a parent of 'B' in the graph.
# No node should have a non-zero accum-install-requires set.
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
childPkgNodesToRemove = set()
for childPkgNode in pkgNode.childPkgNodes:
if (childPkgNode not in pkgNode.buildRequiresPkgNodes) and \
(childPkgNode not in pkgNode.auxBuildRequiresPkgNodes):
# We can't modify a set during iteration, so we
# accumulate the set of children we want to
# remove, and delete them after the for-loop.
childPkgNodesToRemove.add(childPkgNode)
childPkgNode.parentPkgNodes.remove(pkgNode)
pkgNode.childPkgNodes = pkgNode.childPkgNodes - \
childPkgNodesToRemove
for newChildPkgNode in pkgNode.auxBuildRequiresPkgNodes:
pkgNode.childPkgNodes.add(newChildPkgNode)
newChildPkgNode.parentPkgNodes.add(pkgNode)
def _calculateCriticalChainWeights():
# GRAPH-BUILD STEP 5: Calculate critical-chain-weight of packages.
#
# Calculation of critical-chain-weight (the key scheduling
# metric):
# --------------------------------------------------------
# Let us define a "chain" of a given package to be the
# sequence of parent packages that can be built starting from
# that package. For example, if a package 'A' build-requires
# 'B', which in turn build-requires 'C', then one of the
# chains of 'C' is C->B->A. Now, if there are
# multiple such chains possible from 'C', then we define the
# "critical-chain" of 'C' to be the longest of those chains,
# where "longest" is determined by the time it takes to build
# all the packages in that chain. The build-times of any two
# chains can be compared based on the sum of the
# individual weights of each package in their respective
# chains.
#
# Below, we calculate the critical-chain-weight of each
# package (which is the maximum weight of all the paths
# leading up to that package). Later on, we will schedule
# package-builds by the decreasing order of the packages'
# critical-chain-weight.
#
#
# ... ... ...
# \ | /
# v v v
#
# A B C
#
# \ | /
# \ | /
# v v v
#
# D
#
# /
# /
# v
#
# E
#
#
# In the above graph, the critical chain weight of 'D' is
# computed as:
# criticalChainWeight(D) = weight(D) +
# max (criticalChainWeight(A),
# criticalChainWeight(B),
# weight(C))
#
# Graph Traversal : Top-down (starting with packages that
# have no parents).
#
nodesToVisit = set()
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
if len(pkgNode.parentPkgNodes) == 0:
nodesToVisit.add(pkgNode)
while nodesToVisit:
pkgNode = nodesToVisit.pop()
if len(pkgNode.parentPkgNodes) == 0:
pkgNode.criticalChainWeight = pkgNode.selfWeight
# Count self-visit if you don't expect any other
# visitors.
pkgNode.numVisits += 1
for childPkgNode in pkgNode.childPkgNodes:
if pkgNode not in childPkgNode.parentPkgNodes:
raise Exception ("Visitor to child node is not its parent " + \
" Visitor: " + pkgNode.packageName + \
" Child node: " + childPkgNode.packageName)
if childPkgNode.numVisits == len(childPkgNode.parentPkgNodes):
raise Exception ("Child node visit count > number of parents " + \
" Child node: " + childPkgNode.packageName + \
" Visit count: " + childPkgNode.numVisits + \
" Num of parents: " + \
str(len(childPkgNode.parentPkgNodes)))
childPkgNode.criticalChainWeight = max(
childPkgNode.criticalChainWeight,
pkgNode.criticalChainWeight + childPkgNode.selfWeight)
childPkgNode.numVisits += 1
# We can visit this package's children only after this
# package has been visited by all its parents (thus
# guaranteeing that its criticalChainWeight has
# stabilized).
if childPkgNode.numVisits == len(childPkgNode.parentPkgNodes):
nodesToVisit.add(childPkgNode)
# Clear out the visit counter for reuse.
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
if pkgNode.numVisits == 0:
raise Exception ("critical-chain-weight calculation never visited " + \
"package " + pkgNode.packageName)
else:
pkgNode.numVisits = 0
def _buildGraph():
Scheduler._createGraphNodes()
Scheduler._optimizeGraph()
Scheduler._calculateCriticalChainWeights()
@staticmethod
def _parseWeights():
Scheduler.pkgWeights.clear()
with open(constants.packageWeightsPath, 'r') as weightFile:
Scheduler.pkgWeights = json.load(weightFile)
# A package's weight is an indicator of the time required to build
# that package, relative to other packages. These weights do not
# take build-time/install-time dependencies into account -- they
# are the individual build-times of the respective packages.
# Package weights are positive integers, with a default value of 1.
@staticmethod
def _getWeight(package):
# Package weights are assumed to be independent of package
# version (i.e., in the case of multi-version packages such as
# Go or Kubernetes, all the versions have the same weight). So
# convert packageName-version to packageName before looking up
# the package weight.
package, _ = StringUtils.splitPackageNameAndVersion(package)
try:
return int(Scheduler.pkgWeights[package]) + 1
except KeyError:
return 1
@staticmethod
def _getPriority(package):
try:
return int(Scheduler.priorityMap[package])
except KeyError:
return 0
@staticmethod
def _setPriorities(skipGraphBuild):
if skipGraphBuild:
for package in Scheduler.sortedList:
Scheduler.priorityMap[package] = 0
else:
Scheduler._parseWeights()
Scheduler._buildGraph()
for package in Scheduler.sortedList:
pkgNode = Scheduler.mapPackagesToGraphNodes[package]
Scheduler.priorityMap[package] = pkgNode.criticalChainWeight
Scheduler.logger.debug("set Priorities: Priority of all packages")
Scheduler.logger.debug(Scheduler.priorityMap)
@staticmethod
def _getListNextPackagesReadyToBuild():
for pkg in Scheduler.listOfPackagesToBuild:
if pkg in Scheduler.listOfPackagesCurrentlyBuilding:
continue
listRequiredSubPackages = list(set(SPECS.getData().getBuildRequiresForPkg(pkg) + \
SPECS.getData().getRequiresAllForPkg(pkg)))
# extend to full Requires tree
for p in listRequiredSubPackages:
reqs = SPECS.getData().getRequiresAllForPkg(p)
for r in reqs:
if r not in listRequiredSubPackages:
listRequiredSubPackages.append(r)
# convert subpackages to basepkg
listRequiredPackages = set()
for p in listRequiredSubPackages:
listRequiredPackages.add(SPECS.getData().getBasePkg(p))
canBuild = True
for reqPkg in listRequiredPackages:
if reqPkg not in Scheduler.listOfAlreadyBuiltPackages:
canBuild = False
break
if canBuild:
Scheduler.listOfPackagesNextToBuild.put((-Scheduler._getPriority(pkg), pkg))
Scheduler.logger.debug("Adding " + pkg + " to the schedule list")