[gentoo-soc] Progress Report - Revdep-rebuild

["Lucian Poston" <lucianposton@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2656 bytes --]

This week didn't see much movement in the repository due to life
happening (moving and lack of internet at new apt).  On the plus side,
I believe the majority of the work is complete, and I urge everyone to
give it a test to help me discover problems.  :)

I'm happy with the overall results so far.  One thing that irks me is
the dependence on directory and library masks found in
/etc/revdep-rebuild/*.  I was really hoping to find a more elegant
solution than parsing masks from config files, but all my attempts at
a different solution were not successful.  Unfortunately, as long as
masks are used, there is the potential of false positives for
libraries that are not properly masked, which as far as I know is the
only major issue.

My work over the last week was largely polishing details in
docstrings/comments and contemplating final modifications (or future
endeavors).  During this last week of gsoc, I'm going to (hopefully)
improve the performance of LinkageMap and MissingLibraryConsumerSet
before the deadline.  It was suggested on the gentoo-portage-dev
mailing list [1] that efficiency in path comparisons in LinkageMap
could be improved by comparing inodes rather than os.path.realpath in
python's os.path module, which is what I started to implement
recently; however, this appears to require changes outside of the
class, which will take time to finalize e.g. during the unmerge
process, LinkageMap.rebuild is called after files have been removed
but before /var/db/pkg has been correspondingly updated, which is
problematic since.  I may not get all the kinks worked out of changing
LinkageMap before the gsoc deadline, so I'll have something to work on
afterwards.  :)

The attached patches add the library dependency rebuilder as a set,
@missing-rebuild, to portage-2.2_rc6.  Similar to the --library flag
in revdep-rebuild, the user can additionally emerge the set of
packages containing consumers of libraries matched by a (python)
regular expression; however, until a better solution is found, the
regexp must be passed through the LIBRARY environment variable to
enable that feature.

Attached are patches for
/usr/lib/portage/pym/portage/dbapi/vartree.py,
/usr/lib/portage/pym/portage/sets/libs.py and
/usr/share/portage/config/sets.conf, which can also be found in the
repository.[2]  After applying the three patches, one can test the set
with emerge -p @missing-rebuild.  If anyone is brave enough to do so,
let me know how it goes!

Lucian


[1] http://archives.gentoo.org/gentoo-portage-dev/msg_abcbac026ed8670f6dc61bb28be6151e.xml
[2] http://repo.or.cz/w/revdep-rebuild-reimplementation.git?a=tree;h=refs/heads/rc1;hb=rc1

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: libs.py.2.2_rc6.patch --]
[-- Type: text/x-patch; name=libs.py.2.2_rc6.patch, Size: 11563 bytes --]

--- libs.py.2.2_rc6	2008-08-01 15:41:14.000000000 -0500
+++ pym/portage/sets/libs.py	2008-08-11 13:38:01.000000000 -0500
@@ -2,10 +2,18 @@
 # Distributed under the terms of the GNU General Public License v2
 # $Id: libs.py 10759 2008-06-22 04:04:50Z zmedico $
 
+import os
+import re
+import time
+from portage.dbapi.vartree import dblink
+from portage.versions import catsplit
 from portage.sets.base import PackageSet
 from portage.sets import get_boolean
 from portage.versions import catpkgsplit
 
+__all__ = ["LibraryConsumerSet", "PreservedLibraryConsumerSet",
+		"MissingLibraryConsumerSet"]
+
 class LibraryConsumerSet(PackageSet):
 	_operations = ["merge", "unmerge"]
 
@@ -45,3 +53,311 @@
 		debug = get_boolean(options, "debug", False)
 		return PreservedLibraryConsumerSet(trees["vartree"].dbapi, debug)
 	singleBuilder = classmethod(singleBuilder)
+
+
+class MissingLibraryConsumerSet(LibraryConsumerSet):
+
+	"""
+	This class is the set of packages to emerge due to missing libraries.
+
+	This class scans binaries for missing and broken shared library dependencies
+	and fixes them by emerging the packages containing the broken binaries.
+
+	The user may also emerge packages containing consumers of specified
+	libraries by passing the name or a python regular expression through the
+	environment variable, LIBRARY.  Due to a limitation in passing flags to
+	package sets through the portage cli, the user must set environment
+	variables to modify the behaviour of this package set.  So if the
+	environment variable LIBRARY is set, the behaviour of this set changes.
+
+	"""
+
+	description = "The set of packages to emerge due to missing libraries."
+	_operations = ["merge"]
+
+	def __init__(self, vardbapi, debug=False):
+		super(MissingLibraryConsumerSet, self).__init__(vardbapi, debug)
+		# FIXME Since we can't get command line arguments from the user, the
+		# soname can be passed through an environment variable for now.
+		self.libraryRegexp = os.getenv("LIBRARY")
+		self.root = self.dbapi.root
+		self.linkmap = self.dbapi.linkmap
+
+	def load(self):
+		# brokenDependencies: object -> set-of-unsatisfied-dependencies, where
+		# object is an installed binary/library and
+		# set-of-unsatisfied-dependencies are sonames or libraries required by
+		# the object but have no corresponding libraries to fulfill the
+		# dependency.
+		brokenDependencies = {}
+		atoms = set()
+
+		# If the LIBRARY environment variable is set, the resulting package set
+		# will be packages containing consumers of the libraries matched by the
+		# variable.
+		if self.libraryRegexp:
+			atoms = self.findAtomsOfLibraryConsumers(self.libraryRegexp)
+			self._setAtoms(atoms)
+			if self.debug:
+				print
+				print "atoms to be emerged:"
+				for x in sorted(atoms):
+					print x
+			return
+
+		# Get the list of broken dependencies from LinkageMap.
+		if self.debug:
+			timeStart = time.time()
+		brokenDependencies = self.linkmap.listBrokenBinaries()
+		if self.debug:
+			timeListBrokenBinaries = time.time() - timeStart
+
+		# Add broken libtool libraries into the brokenDependencies dict.
+		if self.debug:
+			timeStart = time.time()
+		brokenDependencies.update(self.listBrokenLibtoolLibraries())
+		if self.debug:
+			timeLibtool = time.time() - timeStart
+
+		# FIXME Too many atoms may be emerged because libraries in binary
+		# packages are not being handled properly eg openoffice, nvidia-drivers,
+		# sun-jdk.  Certain binaries are run in an environment where additional
+		# library paths are added via LD_LIBRARY_PATH.  Since these paths aren't
+		# registered in _obj_properties, they appear broken (and are if not run
+		# in the correct environment).  I have to determine if libraries and lib
+		# paths should be masked using /etc/revdep-rebuild/* as done in
+		# revdep-rebuild or if there is a better way to identify and deal with
+		# these problematic packages (or if something entirely different should
+		# be done).  For now directory and library masks are used.
+
+		# Remove masked directories and libraries.
+		if self.debug:
+			timeStart = time.time()
+		if brokenDependencies:
+			brokenDependencies = self.removeMaskedDependencies(brokenDependencies)
+		if self.debug:
+			timeMask = time.time() - timeStart
+
+		# Determine atoms to emerge based on broken objects in
+		# brokenDependencies.
+		if self.debug:
+			timeStart = time.time()
+		if brokenDependencies:
+			atoms = self.mapPathsToAtoms(set(brokenDependencies.keys()))
+		if self.debug:
+			timeAtoms = time.time() - timeStart
+
+		# Debug output
+		if self.debug:
+			print
+			print len(brokenDependencies), "brokenDependencies:"
+			for x in sorted(brokenDependencies.keys()):
+				print
+				print x, "->"
+				print '\t', brokenDependencies[x]
+			print
+			print "atoms to be emerged:"
+			for x in sorted(atoms):
+				print x
+			print
+			print "Broken binaries time:", timeListBrokenBinaries
+			print "Broken libtool time:", timeLibtool
+			print "Remove mask time:", timeMask
+			print "mapPathsToAtoms time:", timeAtoms
+			print
+
+		self._setAtoms(atoms)
+
+	def removeMaskedDependencies(self, dependencies):
+		"""
+		Remove all masked dependencies and return the updated mapping.
+
+		@param dependencies: dependencies from which to removed masked
+			dependencies
+		@type dependencies: dict (example: {'/usr/bin/foo': set(['libfoo.so'])})
+		@rtype: dict
+		@return: shallow copy of dependencies with masked items removed
+
+		"""
+		rValue = dependencies.copy()
+		dirMask, libMask = self.getDependencyMasks()
+
+		# Remove entries that are masked.
+		if dirMask or libMask:
+			if self.debug:
+				print "The following are masked:"
+			for binary, libSet in rValue.items():
+				for dir in dirMask:
+					# Check if the broken binary lies within the masked directory or
+					# its subdirectories.
+					# XXX Perhaps we should allow regexps as masks.
+					if binary.startswith(dir):
+						del rValue[binary]
+						if self.debug:
+							print "dirMask:",binary
+						break
+				# Check if all the required libraries are masked.
+				if binary in rValue and libSet.issubset(libMask):
+					del rValue[binary]
+					if self.debug:
+						print "libMask:", binary, libSet & libMask
+
+		if self.debug:
+			print
+			print "Directory mask:", dirMask
+			print
+			print "Library mask:", libMask
+
+		return rValue
+
+	def getDependencyMasks(self):
+		"""
+		Return all dependency masks as a tuple.
+
+		@rtype: 2-tuple of sets of strings
+		@return: 2-tuple in which the first component is a set of directory
+			masks and the second component is a set of library masks
+
+		"""
+		dirMask = set()
+		libMask = set()
+		_dirMask_re = re.compile(r'SEARCH_DIRS_MASK\s*=\s*"([^"]*)"')
+		_libMask_re = re.compile(r'LD_LIBRARY_MASK\s*=\s*"([^"]*)"')
+		lines = []
+
+		# Reads the contents of /etc/revdep-rebuild/*
+		libMaskDir = os.path.join(self.root, "etc", "revdep-rebuild")
+		if os.path.exists(libMaskDir):
+			for file in os.listdir(libMaskDir):
+				try:
+					f = open(os.path.join(libMaskDir, file), "r")
+					try:
+						lines.extend(f.readlines())
+					finally:
+						f.close()
+				except IOError: # OSError?
+					continue
+			# The following parses SEARCH_DIRS_MASK and LD_LIBRARY_MASK variables
+			# from /etc/revdep-rebuild/*
+			for line in lines:
+				matchDir = _dirMask_re.match(line)
+				matchLib = _libMask_re.match(line)
+				if matchDir:
+					dirMask.update(set(matchDir.group(1).split()))
+				if matchLib:
+					libMask.update(set(matchLib.group(1).split()))
+
+		# These directories contain specially evaluated libraries.
+		# app-emulation/vmware-workstation-6.0.1.55017
+		dirMask.add('/opt/vmware/workstation/lib')
+		# app-emulation/vmware-server-console-1.0.6.91891
+		dirMask.add('/opt/vmware/server/console/lib')
+		# www-client/mozilla-firefox-2.0.0.15
+		dirMask.add('/usr/lib/mozilla-firefox/plugins')
+		dirMask.add('/usr/lib64/mozilla-firefox/plugins')
+		# app-office/openoffice-2.4.1
+		dirMask.add('/opt/OpenOffice')
+		dirMask.add('/usr/lib/openoffice')
+		# dev-libs/libmix-2.05  libmix.so is missing soname entry
+		libMask.add('libmix.so')
+
+		return (dirMask, libMask)
+
+	def findAtomsOfLibraryConsumers(self, searchString):
+		"""
+		Return atoms containing consumers of libraries matching the argument.
+
+		@param searchString: a string used to search for libraries
+		@type searchString: string to be compiled as a regular expression
+			(example: 'libfoo.*')
+		@rtype: set of strings
+		@return: the returned set of atoms are valid to be used by package sets
+
+		"""
+		atoms = set()
+		consumers = set()
+		matchedLibraries = set()
+		libraryObjects = []
+		_librarySearch_re = re.compile(searchString)
+
+		# Find libraries matching searchString.
+		libraryObjects = self.linkmap.listLibraryObjects()
+		for library in libraryObjects:
+			m = _librarySearch_re.search(library)
+			if m:
+				matchedLibraries.add(library)
+				consumers.update(self.linkmap.findConsumers(library))
+
+		if self.debug:
+			print
+			print "Consumers of the following libraries will be emerged:"
+			for x in matchedLibraries:
+				print x
+
+		if consumers:
+			# The following prevents emerging the packages that own the matched
+			# libraries.  Note that this will prevent updating the packages owning
+			# the libraries if there are newer versions available in the installed
+			# slot.  See bug #30095
+			atoms = self.mapPathsToAtoms(consumers)
+			libraryOwners = self.mapPathsToAtoms(matchedLibraries)
+			atoms.difference_update(libraryOwners)
+
+		return atoms
+
+	def listBrokenLibtoolLibraries(self):
+		"""
+		Find broken libtool libraries and their missing dependencies.
+
+		@rtype: dict (example: {'/lib/libfoo.la': set(['/lib/libbar.la'])})
+		@return: The return value is a library -> set-of-libraries mapping, where
+			library is a broken library and the set consists of dependencies
+			needed by library that do not exist on the filesystem.
+
+		"""
+		rValue = {}
+		lines = []
+		dependencies = []
+		_la_re = re.compile(r".*\.la$")
+		_dependency_libs_re = re.compile(r"^dependency_libs\s*=\s*'(.*)'")
+
+		# Loop over the contents of all packages.
+		for cpv in self.dbapi.cpv_all():
+			mysplit = catsplit(cpv)
+			link = dblink(mysplit[0], mysplit[1], myroot=self.dbapi.root, \
+					mysettings=self.dbapi.settings, treetype='vartree', \
+					vartree=self.dbapi.vartree)
+			for file in link.getcontents():
+				# Check if the file ends with '.la'.
+				matchLib = _la_re.match(file)
+				if matchLib:
+					# Read the lines from the library.
+					lines = []
+					try:
+						f = open(file, "r")
+						try:
+							lines.extend(f.readlines())
+						finally:
+							f.close()
+					except IOError:
+						continue
+					# Find the line listing the dependencies.
+					for line in lines:
+						matchLine = _dependency_libs_re.match(line)
+						if matchLine:
+							dependencies = matchLine.group(1).split()
+							# For each dependency that is a pathname (begins with
+							# os.sep), check that it exists on the filesystem.  If it
+							# does not exist, then add the library and the missing
+							# dependency to rValue.
+							for dependency in dependencies:
+								if dependency[0] == os.sep and \
+										not os.path.isfile(dependency):
+									rValue.setdefault(file, set()).add(dependency)
+
+		return rValue
+
+	def singleBuilder(self, options, settings, trees):
+		debug = get_boolean(options, "debug", False)
+		return MissingLibraryConsumerSet(trees["vartree"].dbapi, debug)
+	singleBuilder = classmethod(singleBuilder)

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: vartree.py.2.2_rc6.patch --]
[-- Type: text/x-patch; name=vartree.py.2.2_rc6.patch, Size: 7256 bytes --]

--- vartree.py.2.2_rc6	2008-08-01 15:41:03.000000000 -0500
+++ pym/portage/dbapi/vartree.py	2008-08-11 15:45:55.000000000 -0500
@@ -173,8 +173,10 @@
 			arch = fields[0]
 			obj = os.path.realpath(fields[1])
 			soname = fields[2]
-			path = fields[3].replace("${ORIGIN}", os.path.dirname(obj)).replace("$ORIGIN", os.path.dirname(obj)).split(":")
-			needed = fields[4].split(",")
+			path = filter(None, fields[3].replace(
+				"${ORIGIN}", os.path.dirname(obj)).replace(
+				"$ORIGIN", os.path.dirname(obj)).split(":"))
+			needed = filter(None, fields[4].split(","))
 			if soname:
 				libs.setdefault(soname, {arch: {"providers": [], "consumers": []}})
 				libs[soname].setdefault(arch, {"providers": [], "consumers": []})
@@ -188,6 +190,159 @@
 		self._libs = libs
 		self._obj_properties = obj_properties
 
+	def listBrokenBinaries(self):
+		"""
+		Find binaries and their needed sonames, which have no providers.
+
+		@rtype: dict (example: {'/usr/bin/foo': set(['libbar.so'])})
+		@return: The return value is an object -> set-of-sonames mapping, where
+			object is a broken binary and the set consists of sonames needed by
+			object that have no corresponding libraries to fulfill the dependency.
+
+		"""
+		class LibraryCache(object):
+
+			"""
+			Caches sonames and realpaths associated with paths.
+
+			The purpose of this class is to prevent multiple calls of
+			os.path.realpath and os.path.isfile on the same paths.
+
+			"""
+
+			def __init__(cache_self):
+				cache_self.cache = {}
+
+			def get(cache_self, path):
+				"""
+				Caches and returns the soname and realpath for a path.
+
+				@param path: absolute path (can be symlink)
+				@type path: string (example: '/usr/lib/libfoo.so')
+				@rtype: 3-tuple with types (string or None, string, boolean)
+				@return: 3-tuple with the following components:
+					1. soname as a string or None if it does not exist,
+					2. realpath as a string,
+					3. the result of os.path.isfile(realpath)
+					(example: ('libfoo.so.1', '/usr/lib/libfoo.so.1.5.1', True))
+
+				"""
+				if path in cache_self.cache:
+					return cache_self.cache[path]
+				else:
+					realpath = os.path.realpath(path)
+					# Check that the library exists on the filesystem.
+					if os.path.isfile(realpath):
+						# Get the soname from LinkageMap._obj_properties if it
+						# exists. Otherwise, None.
+						soname = self._obj_properties.get(realpath, (None,)*3)[3]
+						# Both path and realpath are cached and the result is
+						# returned.
+						cache_self.cache.setdefault(realpath, \
+								(soname, realpath, True))
+						return cache_self.cache.setdefault(path, \
+								(soname, realpath, True))
+					else:
+						# realpath is not cached here, because the majority of cases
+						# where realpath is not a file, path is the same as realpath.
+						# Thus storing twice slows down the cache performance.
+						return cache_self.cache.setdefault(path, \
+								(None, realpath, False))
+
+		debug = False
+		rValue = {}
+		cache = LibraryCache()
+		providers = self.listProviders()
+#		providers = self.listProvidersForReachableBinaries(self.getBinaries())
+
+		# Iterate over all binaries and their providers.
+		for obj, sonames in providers.items():
+			# Iterate over each needed soname and the set of library paths that
+			# fulfill the soname to determine if the dependency is broken.
+			for soname, libraries in sonames.items():
+				# validLibraries is used to store libraries, which satisfy soname,
+				# so if no valid libraries are found, the soname is not satisfied
+				# for obj.  Thus obj must be emerged.
+				validLibraries = set()
+				# It could be the case that the library to satisfy the soname is
+				# not in the obj's runpath, but a symlink to the library is (eg
+				# libnvidia-tls.so.1 in nvidia-drivers).  Also, since LinkageMap
+				# does not catalog symlinks, broken or missing symlinks may go
+				# unnoticed.  As a result of these cases, check that a file with
+				# the same name as the soname exists in obj's runpath.
+				path = self._obj_properties[obj][2] + self._defpath
+				for dir in path:
+					cachedSoname, cachedRealpath, cachedExists = \
+							cache.get(os.path.join(dir, soname))
+					# Check that the this library provides the needed soname.  Doing
+					# this, however, will cause consumers of libraries missing
+					# sonames to be unnecessarily emerged. (eg libmix.so)
+					if cachedSoname == soname:
+						validLibraries.add(cachedRealpath)
+						if debug and cachedRealpath not in libraries:
+							print "Found provider outside of findProviders:", \
+									os.path.join(dir, soname), "->", cachedRealpath
+						# A valid library has been found, so there is no need to
+						# continue.
+						break
+					if debug and cachedRealpath in self._obj_properties:
+						print "Broken symlink or missing/bad soname:", \
+								os.path.join(dir, soname), '->', cachedRealpath, \
+								"with soname", cachedSoname, "but expecting", soname
+				# This conditional checks if there are no libraries to satisfy the
+				# soname (empty set).
+				if not validLibraries:
+					rValue.setdefault(obj, set()).add(soname)
+					# If no valid libraries have been found by this point, then
+					# there are no files named with the soname within obj's runpath,
+					# but if there are libraries (from the providers mapping), it is
+					# likely that symlinks or the actual libraries are missing.
+					# Thus possible symlinks and missing libraries are added to
+					# rValue in order to emerge corrupt library packages.
+					for lib in libraries:
+						cachedSoname, cachedRealpath, cachedExists = cache.get(lib)
+						if not cachedExists:
+							# The library's package needs to be emerged to repair the
+							# missing library.
+							rValue.setdefault(lib, set()).add(soname)
+						else:
+							# A library providing the soname exists in the obj's
+							# runpath, but no file named as the soname exists, so add
+							# the path constructed from the lib's directory and the
+							# soname to rValue to fix cases of vanishing (or modified)
+							# symlinks.  This path is not guaranteed to exist, but it
+							# follows the symlink convention found in the majority of
+							# packages.
+							rValue.setdefault(os.path.join(os.path.dirname(lib), \
+									soname), set()).add(soname)
+						if debug:
+							if not cachedExists:
+								print "Missing library:", lib
+							else:
+								print "Possibly missing symlink:", \
+										os.path.join(os.path.dirname(lib), soname)
+
+		return rValue
+
+	def listProviders(self):
+		"""
+		Find the providers for all binaries.
+
+		@rtype: dict (example:
+			{'/usr/bin/foo': {'libbar.so': set(['/lib/libbar.so.1.5'])}})
+		@return: The return value is an object -> providers mapping, where
+			providers is a mapping of soname -> set-of-library-paths returned
+			from the findProviders method.
+
+		"""
+		rValue = {}
+		if not self._libs:
+			self.rebuild()
+		# Iterate over all binaries within LinkageMap.
+		for obj in self._obj_properties.keys():
+			rValue.setdefault(obj, self.findProviders(obj))
+		return rValue
+
 	def isMasterLink(self, obj):
 		basename = os.path.basename(obj)
 		if obj not in self._obj_properties:

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: sets.conf.2.2_rc6.patch --]
[-- Type: text/x-patch; name=sets.conf.2.2_rc6.patch, Size: 397 bytes --]

--- sets.conf.2.2_rc6	2008-08-08 13:50:04.000000000 -0500
+++ /usr/share/portage/config/sets.conf	2008-08-08 13:41:01.000000000 -0500
@@ -59,3 +59,9 @@
 [downgrade]
 class = portage.sets.dbapi.DowngradeSet
 world-candidate = False
+
+# Packages to rebuild broken library dependencies.
+[missing-rebuild]
+class = portage.sets.libs.MissingLibraryConsumerSet
+world-candidate = False
+debug = False