[gentoo-soc] Progress Report - Revdep-rebuild

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

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

Last week's work was interesting.  As mentioned in the last report, I
significantly modified LinkageMap to utilize path's inodes rather
os.path.realpath for path comparisons -- basically, reducing the
amount of filesystem access.  It turned out to improve its efficiency,
which in turn improved the efficiency of MisingLibraryConsumerSet as
it relies on LinkageMap.listBrokenBinaries.

I previously mentioned there would be problems in cases where
LinkageMap is rebuilt when files have been removed but the /var/db/pkg
database has not been updated accordingly.  I got around this by
falling back on os.path.realpath for missing files (or more generally,
when os.stat fails).

For future endeavors, I will explore adding a new entry into
/var/db/pkg to catalog libtool libraries (similar in nature to
NEEDED.ELF.2).  Currently, the contents of all packages are searched
in order to find libtool libraries, so having them available in the
vdb_path will speed things up.

Here are the known problems:

1) I've noticed that on my older systems, I had to re-emerge several
packages, which appeared broken due older/incomplete NEEDED.ELF.2
entries.  They appeared to be missing entries for various files.  I
suppose this is due to modifications to the scripts that generate
these files as those systems had been using older versions of portage.
 Everything worked fine after updating these files.

2) In certain situations, packages may be ordered such that a second
emerge is necessary.  This is due to dependency neglection in portage.
[1]  The flag --complete-graph can be used to properly order packages
in these situations.

3) In the last report [2], I mentioned the functionality to emerge the
set of packages containing consumers of libraries matched by a regular
expression.  The libraries returned by LinkageMap.listLibraryObjects()
are matched against that regular expression.  Consequently, only files
cataloged in LinkageMap will be considered.  Since symlinks aren't
entered into NEEDED.ELF.2 files, LinkageMap doesn't catalog them.  So
if /usr/lib were a symlink to /usr/lib64 and the regular expression
were /usr/lib/libfoo*, nothing would be matched (libfoo would work
however).  This can be fixed by adding symlink entries into
LinkageMap, searching CONTENTS files for symlinks, or utilizing the
find utility.  I'll decide to search CONTENTS files to resolve this.

4) As masks are used to filter out specially evaluated binaries, there
is always the potential for false positives until the correct masks
are added.

Attached are three patches[3] for portage-2.2_rc8 for the files:
/usr/lib/portage/pym/portage/dbapi/vartree.py
/usr/lib/portage/pym/portage/sets/libs.py
/usr/share/portage/config/sets.conf

Lucian


[1] http://dev.gentoo.org/~zmedico/portage/doc/portage.html#dependency-resolution-package-modeling-dependency-neglection
[2] http://archives.gentoo.org/gentoo-soc/msg_b8a874ceac9b58c1badf86f3eaff4803.xml
[3] http://repo.or.cz/w/revdep-rebuild-reimplementation.git?a=shortlog;h=refs/heads/rc3

[-- Attachment #2: libs.py.2.2_rc8.patch --]
[-- Type: application/octet-stream, Size: 12013 bytes --]

--- libs.py.2.2_rc8	2008-08-14 15:45:30.000000000 -0500
+++ pym/portage/sets/libs.py	2008-08-18 04:25:32.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,324 @@
 		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
+
+		# Rebuild LinkageMap.
+		if self.debug:
+			timeStart = time.time()
+		self.linkmap.rebuild()
+		if self.debug:
+			timeRebuild = time.time() - timeStart
+
+		# Get the list of broken dependencies from LinkageMap.
+		if self.debug:
+			timeStart = time.time()
+		brokenDependencies = self.linkmap.listBrokenBinaries(self.debug)
+		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 "Rebuild time:", timeRebuild
+			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 directory 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(directory):
+						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')
+		# app-accessibility/speech-tools-1.2.96_beta  missing sonames
+		libMask.add('libestools.so')
+		libMask.add('libestbase.so')
+		libMask.add('libeststring.so')
+		# app-emulation/emul-linux-x86-soundlibs-20080418
+		dirMask.add('/usr/kde/3.5/lib32')
+
+		return (dirMask, libMask)
+
+	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 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 = self.linkmap.listLibraryObjects()
+		_librarySearch_re = re.compile(searchString)
+
+		# Find libraries matching searchString.
+		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 singleBuilder(self, options, settings, trees):
+		debug = get_boolean(options, "debug", False)
+		return MissingLibraryConsumerSet(trees["vartree"].dbapi, debug)
+	singleBuilder = classmethod(singleBuilder)

[-- Attachment #3: vartree.py.2.2_rc8.patch --]
[-- Type: application/octet-stream, Size: 21012 bytes --]

--- vartree.py.2.2_rc8	2008-08-17 21:11:41.000000000 -0500
+++ pym/portage/dbapi/vartree.py	2008-08-18 04:13:33.000000000 -0500
@@ -143,10 +143,12 @@
 		self._dbapi = vardbapi
 		self._libs = {}
 		self._obj_properties = {}
-		self._defpath = getlibpaths()
-	
+		self._defpath = set(getlibpaths())
+		self._obj_key_cache = {}
+
 	def rebuild(self, include_file=None):
 		libs = {}
+		obj_key_cache = {}
 		obj_properties = {}
 		lines = []
 		for cpv in self._dbapi.cpv_all():
@@ -176,29 +178,61 @@
 				# insufficient field length
 				continue
 			arch = fields[0]
-			obj = os.path.realpath(fields[1])
+			obj = fields[1]
+			obj_key = self._generateObjKey(obj)
 			soname = fields[2]
-			path = filter(None, fields[3].replace(
+			path = set([normalize_path(x)
+				for x in filter(None, fields[3].replace(
 				"${ORIGIN}", os.path.dirname(obj)).replace(
-				"$ORIGIN", os.path.dirname(obj)).split(":"))
+				"$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": []})
-				libs[soname][arch]["providers"].append(obj)
+				libs.setdefault(soname, \
+						{arch: {"providers": set(), "consumers": set()}})
+				libs[soname].setdefault(arch, \
+						{"providers": set(), "consumers": set()})
+				libs[soname][arch]["providers"].add(obj_key)
 			for x in needed:
-				libs.setdefault(x, {arch: {"providers": [], "consumers": []}})
-				libs[x].setdefault(arch, {"providers": [], "consumers": []})
-				libs[x][arch]["consumers"].append(obj)
-			obj_properties[obj] = (arch, needed, path, soname)
-		
+				libs.setdefault(x, \
+						{arch: {"providers": set(), "consumers": set()}})
+				libs[x].setdefault(arch, {"providers": set(), "consumers": set()})
+				libs[x][arch]["consumers"].add(obj_key)
+			obj_key_cache.setdefault(obj, obj_key)
+			# All object paths are added into the obj_properties tuple
+			obj_properties.setdefault(obj_key, \
+					(arch, needed, path, soname, set()))[4].add(obj)
+
 		self._libs = libs
 		self._obj_properties = obj_properties
+		self._obj_key_cache = obj_key_cache
 
-	def listBrokenBinaries(self):
+	def _generateObjKey(self, obj):
+		"""
+		Generate obj key for a given object.
+
+		@param obj: path to an existing file
+		@type obj: string (example: '/usr/bin/bar')
+		@rtype: 2-tuple of longs if obj exists. string if obj does not exist.
+		@return:
+			1. 2-tuple of obj's inode and device from a stat call, if obj exists.
+			2. realpath of object if obj does not exist.
+
+		"""
+		try:
+			obj_st = os.stat(obj)
+		except OSError:
+			# Use the realpath as the key if the file does not exists on the
+			# filesystem.
+			return os.path.realpath(obj)
+		# Return a tuple of the device and inode.
+		return (obj_st.st_dev, obj_st.st_ino)
+
+	def listBrokenBinaries(self, debug=False):
 		"""
 		Find binaries and their needed sonames, which have no providers.
 
+		@param debug: Boolean to enable debug output
+		@type debug: Boolean
 		@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
@@ -208,65 +242,66 @@
 		class LibraryCache(object):
 
 			"""
-			Caches sonames and realpaths associated with paths.
+			Caches properties 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.
+			_generateObjKey on the same paths.
 
 			"""
 
 			def __init__(cache_self):
 				cache_self.cache = {}
 
-			def get(cache_self, path):
+			def get(cache_self, obj):
 				"""
-				Caches and returns the soname and realpath for a path.
+				Caches and returns properties associated with an object.
 
-				@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))
+				@param obj: absolute path (can be symlink)
+				@type obj: string (example: '/usr/lib/libfoo.so')
+				@rtype: 4-tuple with types
+					(string or None, string or None, 2-tuple, Boolean)
+				@return: 4-tuple with the following components:
+					1. arch as a string or None if it does not exist,
+					2. soname as a string or None if it does not exist,
+					3. obj_key as 2-tuple,
+					4. Boolean representing whether the object exists.
+					(example: ('libfoo.so.1', (123L, 456L), True))
 
 				"""
-				if path in cache_self.cache:
-					return cache_self.cache[path]
+				if obj in cache_self.cache:
+					return cache_self.cache[obj]
 				else:
-					realpath = os.path.realpath(path)
+					if obj in self._obj_key_cache:
+						obj_key = self._obj_key_cache.get(obj)
+					else:
+						obj_key = self._generateObjKey(obj)
 					# 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))
+					if isinstance(obj_key, tuple):
+						# Get the arch and soname from LinkageMap._obj_properties if
+						# it exists. Otherwise, None.
+						arch, _, _, soname, _ = \
+								self._obj_properties.get(obj_key, (None,)*5)
+						return cache_self.cache.setdefault(obj, \
+								(arch, soname, obj_key, 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))
+						return cache_self.cache.setdefault(obj, \
+								(None, None, obj_key, False))
 
-		debug = False
 		rValue = {}
 		cache = LibraryCache()
 		providers = self.listProviders()
 
-		# Iterate over all binaries and their providers.
-		for obj, sonames in providers.items():
+		# Iterate over all obj_keys and their providers.
+		for obj_key, sonames in providers.items():
+			arch, _, path, _, objs = self._obj_properties[obj_key]
+			path = path.union(self._defpath)
 			# 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.
+				# for obj_key.  If unsatisfied, objects associated with obj_key
+				# 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
@@ -274,67 +309,60 @@
 				# 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 d in path:
-					cachedSoname, cachedRealpath, cachedExists = \
-							cache.get(os.path.join(d, soname))
-					# Check that the this library provides the needed soname.  Doing
+				# XXX If we catalog symlinks in LinkageMap, this could be improved.
+				for directory in path:
+					cachedArch, cachedSoname, cachedKey, cachedExists = \
+							cache.get(os.path.join(directory, soname))
+					# Check that 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:
+					if cachedSoname == soname and cachedArch == arch:
+						validLibraries.add(cachedKey)
+						if debug and cachedKey not in \
+								set(map(self._obj_key_cache.get, libraries)):
+							# XXX This is most often due to soname symlinks not in
+							# a library's directory.  We could catalog symlinks in
+							# LinkageMap to avoid checking for this edge case here.
 							print "Found provider outside of findProviders:", \
-									os.path.join(d, soname), "->", cachedRealpath
+									os.path.join(directory, soname), "->", \
+									self._obj_properties[cachedKey][4], libraries
 						# A valid library has been found, so there is no need to
 						# continue.
 						break
-					if debug and cachedRealpath in self._obj_properties:
+					if debug and cachedArch == arch and \
+							cachedKey in self._obj_properties:
 						print "Broken symlink or missing/bad soname:", \
-								os.path.join(d, soname), '->', cachedRealpath, \
-								"with soname", cachedSoname, "but expecting", soname
+								os.path.join(directory, soname), '->', \
+								self._obj_properties[cachedKey], "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)
+					for obj in objs:
+						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.
+					# likely that soname symlinks or the actual libraries are
+					# missing or broken.  Thus those 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)
+						rValue.setdefault(lib, set()).add(soname)
 						if debug:
-							if not cachedExists:
+							if not os.path.isfile(lib):
 								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.
+		Find the providers for all object keys in LinkageMap.
 
 		@rtype: dict (example:
-			{'/usr/bin/foo': {'libbar.so': set(['/lib/libbar.so.1.5'])}})
-		@return: The return value is an object -> providers mapping, where
+			{(123L, 456L): {'libbar.so': set(['/lib/libbar.so.1.5'])}})
+		@return: The return value is an object key -> providers mapping, where
 			providers is a mapping of soname -> set-of-library-paths returned
 			from the findProviders method.
 
@@ -342,118 +370,188 @@
 		rValue = {}
 		if not self._libs:
 			self.rebuild()
-		# Iterate over all binaries within LinkageMap.
-		for obj in self._obj_properties:
-			rValue.setdefault(obj, self.findProviders(obj))
+		# Iterate over all object keys within LinkageMap.
+		for obj_key in self._obj_properties:
+			rValue.setdefault(obj_key, self.findProviders(obj_key=obj_key))
 		return rValue
 
 	def isMasterLink(self, obj):
+		"""
+		Determine whether an object is a master link.
+
+		@param obj: absolute path to an object
+		@type obj: string (example: '/usr/bin/foo')
+		@rtype: Boolean
+		@return:
+			1. True if obj is a master link
+			2. False if obj is not a master link
+
+		"""
 		basename = os.path.basename(obj)
-		if obj not in self._obj_properties:
-			obj = os.path.realpath(obj)
-			if obj not in self._obj_properties:
-				raise KeyError("%s not in object list" % obj)
-		soname = self._obj_properties[obj][3]
+		obj_key = self._generateObjKey(obj)
+		if obj_key not in self._obj_properties:
+			raise KeyError("%s (%s) not in object list" % (obj_key, obj))
+		soname = self._obj_properties[obj_key][3]
 		return (len(basename) < len(soname))
-		
+
 	def listLibraryObjects(self):
+		"""
+		Return a list of library objects.
+
+		Known limitation: library objects lacking an soname are not included.
+
+		@rtype: list of strings
+		@return: list of paths to all providers
+
+		"""
 		rValue = []
 		if not self._libs:
 			self.rebuild()
 		for soname in self._libs:
 			for arch in self._libs[soname]:
-				rValue.extend(self._libs[soname][arch]["providers"])
+				for obj_key in self._libs[soname][arch]["providers"]:
+					rValue.extend(self._obj_properties[obj_key][4])
 		return rValue
 
 	def getSoname(self, obj):
+		"""
+		Return the soname associated with an object.
+
+		@param obj: absolute path to an object
+		@type obj: string (example: '/usr/bin/bar')
+		@rtype: string
+		@return: soname as a string
+
+		"""
 		if not self._libs:
 			self.rebuild()
-		if obj not in self._obj_properties:
-			obj = os.path.realpath(obj)
-			if obj not in self._obj_properties:
-				raise KeyError("%s not in object list" % obj)
-		arch, needed, path, soname = self._obj_properties[obj]
-		return soname
+		if obj not in self._obj_key_cache:
+			raise KeyError("%s not in object list" % obj)
+		return self._obj_properties[self._obj_key_cache[obj]][3]
+
+	def findProviders(self, obj=None, obj_key=None):
+		"""
+		Find providers for an object or object key.
+
+		This method should be called with either an obj or obj_key.  If called
+		with both, the obj_key is ignored.  If called with neither, KeyError is
+		raised as if an invalid obj was passed.
+
+		In some cases, not all valid libraries are returned.  This may occur when
+		an soname symlink referencing a library is in an object's runpath while
+		the actual library is not.
+
+		@param obj: absolute path to an object
+		@type obj: string (example: '/usr/bin/bar')
+		@param obj_key: key from LinkageMap._generateObjKey
+		@type obj_key: 2-tuple of longs or string
+		@rtype: dict (example: {'libbar.so': set(['/lib/libbar.so.1.5'])})
+		@return: The return value is a soname -> set-of-library-paths, where
+		set-of-library-paths satisfy soname.
+
+		"""
+		rValue = {}
 
-	def findProviders(self, obj):
 		if not self._libs:
 			self.rebuild()
 
-		realpath_cache = {}
-		def realpath(p):
-			real_path = realpath_cache.get(p)
-			if real_path is None:
-				real_path = os.path.realpath(p)
-				realpath_cache[p] = real_path
-			return real_path
-
-		rValue = {}
-		if obj not in self._obj_properties:
-			obj = realpath(obj)
-			if obj not in self._obj_properties:
-				raise KeyError("%s not in object list" % obj)
-		arch, needed, path, soname = self._obj_properties[obj]
-		path = path[:]
-		path.extend(self._defpath)
-		path = set(realpath(x) for x in path)
-		for x in needed:
-			rValue[x] = set()
-			if x not in self._libs or arch not in self._libs[x]:
-				continue
-			for y in self._libs[x][arch]["providers"]:
-				if x[0] == os.sep and realpath(x) == realpath(y):
-					rValue[x].add(y)
-				elif realpath(os.path.dirname(y)) in path:
-					rValue[x].add(y)
+		# Determine the obj_key from the arguments.
+		if obj is not None:
+			obj_key = self._obj_key_cache.get(obj)
+			if obj_key not in self._obj_properties:
+				obj_key = self._generateObjKey(obj)
+				if obj_key not in self._obj_properties:
+					raise KeyError("%s (%s) not in object list" % (obj_key, obj))
+		elif obj_key not in self._obj_properties:
+			raise KeyError("%s not in object list" % obj_key)
+
+		arch, needed, path, _, _ = self._obj_properties[obj_key]
+		path = path.union(self._defpath)
+		for soname in needed:
+			rValue[soname] = set()
+			if soname not in self._libs or arch not in self._libs[soname]:
+				continue
+			# For each potential provider of the soname, add it to rValue if it
+			# resides in the obj's runpath.
+			for provider_key in self._libs[soname][arch]["providers"]:
+				providers = self._obj_properties[provider_key][4]
+				for provider in providers:
+					if os.path.dirname(provider) in path:
+						rValue[soname].add(provider)
 		return rValue
-	
-	def findConsumers(self, obj):
+
+	def findConsumers(self, obj=None, obj_key=None):
+		"""
+		Find consumers of an object or object key.
+
+		This method should be called with either an obj or obj_key.  If called
+		with both, the obj_key is ignored.  If called with neither, KeyError is
+		raised as if an invalid obj was passed.
+
+		In some cases, not all consumers are returned.  This may occur when
+		an soname symlink referencing a library is in an object's runpath while
+		the actual library is not.
+
+		@param obj: absolute path to an object
+		@type obj: string (example: '/usr/bin/bar')
+		@param obj_key: key from LinkageMap._generateObjKey
+		@type obj_key: 2-tuple of longs or string
+		@rtype: set of strings (example: )
+		@return: The return value is a soname -> set-of-library-paths, where
+		set-of-library-paths satisfy soname.
+
+		"""
+		rValue = set()
+
 		if not self._libs:
 			self.rebuild()
 
-		realpath_cache = {}
-		def realpath(p):
-			real_path = realpath_cache.get(p)
-			if real_path is None:
-				real_path = os.path.realpath(p)
-				realpath_cache[p] = real_path
-			return real_path
-
-		if obj not in self._obj_properties:
-			obj = realpath(obj)
-			if obj not in self._obj_properties:
-				raise KeyError("%s not in object list" % obj)
+		# Determine the obj_key and the set of objects matching the arguments.
+		if obj is not None:
+			objs = set([obj])
+			obj_key = self._obj_key_cache.get(obj)
+			if obj_key not in self._obj_properties:
+				obj_key = self._generateObjKey(obj)
+				if obj_key not in self._obj_properties:
+					raise KeyError("%s (%s) not in object list" % (obj_key, obj))
+		else:
+			if obj_key not in self._obj_properties:
+				raise KeyError("%s not in object list" % obj_key)
+			objs = self._obj_properties[obj_key][4]
+
+		# Determine the directory(ies) from the set of objects.
+		objs_dirs = set([os.path.dirname(x) for x in objs])
 
 		# If there is another version of this lib with the
 		# same soname and the master link points to that
 		# other version, this lib will be shadowed and won't
 		# have any consumers.
-		arch, needed, path, soname = self._obj_properties[obj]
-		obj_dir = os.path.dirname(obj)
-		master_link = os.path.join(obj_dir, soname)
-		try:
-			master_st = os.stat(master_link)
-			obj_st = os.stat(obj)
-		except OSError:
-			pass
-		else:
-			if (obj_st.st_dev, obj_st.st_ino) != \
-				(master_st.st_dev, master_st.st_ino):
-				return set()
-
-		rValue = set()
-		for soname in self._libs:
-			for arch in self._libs[soname]:
-				if obj in self._libs[soname][arch]["providers"]:
-					for x in self._libs[soname][arch]["consumers"]:
-						path = self._obj_properties[x][2]
-						path = [realpath(y) for y in path+self._defpath]
-						if soname[0] == os.sep and realpath(soname) == realpath(obj):
-							rValue.add(x)
-						elif realpath(obj_dir) in path:
-							rValue.add(x)
+		if obj is not None:
+			soname = self._obj_properties[obj_key][3]
+			obj_dir = os.path.dirname(obj)
+			master_link = os.path.join(obj_dir, soname)
+			try:
+				master_st = os.stat(master_link)
+				obj_st = os.stat(obj)
+			except OSError:
+				pass
+			else:
+				if (obj_st.st_dev, obj_st.st_ino) != \
+					(master_st.st_dev, master_st.st_ino):
+					return set()
+
+		arch, _, _, soname, _ = self._obj_properties[obj_key]
+		if soname in self._libs and arch in self._libs[soname]:
+			# For each potential consumer, add it to rValue if an object from the
+			# arguments resides in the consumer's runpath.
+			for consumer_key in self._libs[soname][arch]["consumers"]:
+				_, _, path, _, consumer_objs = \
+						self._obj_properties[consumer_key]
+				path = path.union(self._defpath)
+				if objs_dirs.intersection(path):
+					rValue.update(consumer_objs)
 		return rValue
-					
+
 class vardbapi(dbapi):
 
 	_excluded_dirs = ["CVS", "lost+found"]

[-- Attachment #4: sets.conf.2.2_rc8.patch --]
[-- Type: application/octet-stream, Size: 382 bytes --]

--- sets.conf.2.2_rc8	2008-08-14 15:46:20.000000000 -0500
+++ /usr/share/portage/config/sets.conf	2008-08-14 15:56:18.000000000 -0500
@@ -63,3 +63,8 @@
 [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