Generate soname dependency metadata (bug 282639)

Generate soname dependency metadata for binary and installed packages,
in the form of PROVIDES and REQUIRES metadata. It is useful to generate
PROVIDES and REQUIRES metadata now, so that it will be available
when dependency resolver support is added in the future. Note that
slot-operator dependencies will not be able to serve as a substitute
for soname dependencies for the forseeable future, because system
dependencies are frequently unspecified (according to Gentoo policy).

The PROVIDES/REQUIRES system is very similar to the automatic Requires
and Provides system which is supported by RPM. The PROVIDES/REQUIRES
metadata is generated automatically from the ELF files that are
installed by a package. The PROVIDES/REQUIRES syntax is described in
the /var/db/pkg section of the portage(5) man page. REQUIRES_EXCLUDE
and PROVIDES_EXCLUDE ebuild variables allow for filtering of the
sonames that are saved in REQUIRES and PROVIDES (see the ebuild(5) man
page for details).

The /var/db/pkg NEEDED.ELF.2 format now includes an additional field
which indicates the multilib category, as discussed in bug #534206. The
multilib category is used to categorize the sonames that are listed in
PROVIDES/REQUIRES metadata, since sonames need to be resolved
separately for each multilib category. The complete list of supported
multilib categories is documented in the comments of the
portage.dep.soname.multilib_category module.

X-Gentoo-Bug: 282639
X-Gentoo-Bug-URL: https://bugs.gentoo.org/show_bug.cgi?id=282639
Acked-by: Brian Dolbec <dolsen@gentoo.org>

18 files changed, 668 insertions, 27 deletions

diff --git a/bin/ebuild.sh b/bin/ebuild.sh
index e6f9cb909..b6b372348 100755
--- a/bin/ebuild.sh
+++ b/bin/ebuild.sh
@@ -578,7 +578,7 @@ if ! has "$EBUILD_PHASE" clean cleanrm ; then
 		# interaction begins.
 		unset EAPI DEPEND RDEPEND PDEPEND HDEPEND INHERITED IUSE REQUIRED_USE \
 			ECLASS E_IUSE E_REQUIRED_USE E_DEPEND E_RDEPEND E_PDEPEND \
-			E_HDEPEND
+			E_HDEPEND PROVIDES_EXCLUDE REQUIRES_EXCLUDE
 
 		if [[ $PORTAGE_DEBUG != 1 || ${-/x/} != $- ]] ; then
 			source "$EBUILD" || die "error sourcing ebuild"
diff --git a/bin/phase-functions.sh b/bin/phase-functions.sh
index aec86fd49..def2080a9 100644
--- a/bin/phase-functions.sh
+++ b/bin/phase-functions.sh
@@ -580,7 +580,7 @@ __dyn_install() {
 		for f in ASFLAGS CBUILD CC CFLAGS CHOST CTARGET CXX \
 			CXXFLAGS EXTRA_ECONF EXTRA_EINSTALL EXTRA_MAKE \
 			LDFLAGS LIBCFLAGS LIBCXXFLAGS QA_CONFIGURE_OPTIONS \
-			QA_DESKTOP_FILE ; do
+			QA_DESKTOP_FILE PROVIDES_EXCLUDE REQUIRES_EXCLUDE ; do
 			x=$(echo -n ${!f})
 			[[ -n $x ]] && echo "$x" > $f
 		done
diff --git a/man/ebuild.5 b/man/ebuild.5
index 3f3518001..95d045349 100644
--- a/man/ebuild.5
+++ b/man/ebuild.5
@@ -480,6 +480,12 @@ source	source\-build which is scheduled for merge
 .TE
 .RE
 .TP
+.B PROVIDES_EXCLUDE\fR = \fI[space delimited list of fnmatch patterns]\fR
+Sonames and file paths matched by these fnmatch patterns will be
+excluded during genertion of \fBPROVIDES\fR metadata (see
+\fBportage\fR(5)). Patterns are delimited by whitespace, and it is
+possible to create patterns containing quoted whitespace.
+.TP
 .B PORTAGE_LOG_FILE
 Contains the path of the build log. If \fBPORT_LOGDIR\fR variable is unset then
 PORTAGE_LOG_FILE=\fI"${T}/build.log"\fR.
@@ -506,6 +512,12 @@ to the package version(s) being replaced. Typically, this variable will
 not contain more than one version, but according to PMS it can contain
 more.
 .TP
+.B REQUIRES_EXCLUDE\fR = \fI[space delimited list of fnmatch patterns]\fR
+Sonames and file paths matched by these fnmatch patterns will be
+excluded during generation of \fBREQUIRES\fR metadata (see
+\fBportage\fR(5)). Patterns are delimited by whitespace, and it is
+possible to create patterns containing quoted whitespace.
+.TP
 .B ROOT\fR = \fI"/"
 Contains the path that portage should use as the root of the live filesystem.
 When packages wish to make changes to the live filesystem, they should do so in
diff --git a/man/portage.5 b/man/portage.5
index 8bebd3290..cec4e2fe3 100644
--- a/man/portage.5
+++ b/man/portage.5
@@ -1479,6 +1479,31 @@ can be changed quickly.  Generally though there is one file per environment
 variable that "matters" (like CFLAGS) with the contents stored inside of it.
 Another common file is the CONTENTS file which lists the path and hashes of
 all objects that the package installed onto your system.
+.TP
+.BR PROVIDES
+Contains information about the sonames that a package provides, which is
+automatically generated from the files that it installs. The sonames
+may have been filtered by the \fBPROVIDES_EXCLUDE\fR \fBebuild\fR(5)
+variable. A multilib category, followed by a colon, always preceeds a
+list of one or more sonames.
+
+.I Example:
+.nf
+x86_32: libcom_err.so.2 libss.so.2 x86_64: libcom_err.so.2 libss.so.2
+.fi
+.TP
+.BR REQUIRES
+Contains information about the sonames that a package requires, which is
+automatically generated from the files that it installs. The sonames
+may have been filtered by the \fBREQUIRES_EXCLUDE\fR \fBebuild\fR(5)
+variable. Any sonames that a package provides are automatically excluded
+from \fBREQUIRES\fR. A multilib category, followed by a colon, always
+preceeds a list of one or more sonames.
+
+.I Example:
+.nf
+x86_32: ld-linux.so.2 libc.so.6 x86_64: ld-linux-x86-64.so.2 libc.so.6
+.fi
 .RE
 .TP
 .BR /var/lib/portage/
diff --git a/pym/_emerge/Package.py b/pym/_emerge/Package.py
index 8612e8b72..518dbf67d 100644
--- a/pym/_emerge/Package.py
+++ b/pym/_emerge/Package.py
@@ -43,7 +43,8 @@ class Package(Task):
 		"HDEPEND", "INHERITED", "IUSE", "KEYWORDS",
 		"LICENSE", "PDEPEND", "PROVIDE", "RDEPEND",
 		"repository", "PROPERTIES", "RESTRICT", "SLOT", "USE",
-		"_mtime_", "DEFINED_PHASES", "REQUIRED_USE"]
+		"_mtime_", "DEFINED_PHASES", "REQUIRED_USE", "PROVIDES",
+		"REQUIRES"]
 
 	_dep_keys = ('DEPEND', 'HDEPEND', 'PDEPEND', 'RDEPEND')
 	_buildtime_keys = ('DEPEND', 'HDEPEND')
diff --git a/pym/portage/dbapi/bintree.py b/pym/portage/dbapi/bintree.py
index 1156b6678..583e208ad 100644
--- a/pym/portage/dbapi/bintree.py
+++ b/pym/portage/dbapi/bintree.py
@@ -81,7 +81,8 @@ class bindbapi(fakedbapi):
 			["BUILD_TIME", "CHOST", "DEPEND", "EAPI",
 			"HDEPEND", "IUSE", "KEYWORDS",
 			"LICENSE", "PDEPEND", "PROPERTIES", "PROVIDE",
-			"RDEPEND", "repository", "RESTRICT", "SLOT", "USE", "DEFINED_PHASES"
+			"RDEPEND", "repository", "RESTRICT", "SLOT", "USE",
+			"DEFINED_PHASES", "PROVIDES", "REQUIRES"
 			])
 		self._aux_cache_slot_dict = slot_dict_class(self._aux_cache_keys)
 		self._aux_cache = {}
@@ -322,7 +323,7 @@ class binarytree(object):
 				["BUILD_TIME", "CHOST", "DEPEND", "DESCRIPTION", "EAPI",
 				"HDEPEND", "IUSE", "KEYWORDS", "LICENSE", "PDEPEND", "PROPERTIES",
 				"PROVIDE", "RESTRICT", "RDEPEND", "repository", "SLOT", "USE", "DEFINED_PHASES",
-				"BASE_URI"]
+				"BASE_URI", "PROVIDES", "REQUIRES"]
 			self._pkgindex_aux_keys = list(self._pkgindex_aux_keys)
 			self._pkgindex_use_evaluated_keys = \
 				("DEPEND", "HDEPEND", "LICENSE", "RDEPEND",
diff --git a/pym/portage/dbapi/vartree.py b/pym/portage/dbapi/vartree.py
index 2d4d32dec..cf31c8e9c 100644
--- a/pym/portage/dbapi/vartree.py
+++ b/pym/portage/dbapi/vartree.py
@@ -176,6 +176,7 @@ class vardbapi(dbapi):
 			"EAPI", "HDEPEND", "HOMEPAGE", "IUSE", "KEYWORDS",
 			"LICENSE", "PDEPEND", "PROPERTIES", "PROVIDE", "RDEPEND",
 			"repository", "RESTRICT" , "SLOT", "USE", "DEFINED_PHASES",
+			"PROVIDES", "REQUIRES"
 			])
 		self._aux_cache_obj = None
 		self._aux_cache_filename = os.path.join(self._eroot,
diff --git a/pym/portage/dep/soname/__init__.py b/pym/portage/dep/soname/__init__.py
new file mode 100644
index 000000000..4725d3317
--- /dev/null
+++ b/pym/portage/dep/soname/__init__.py
@@ -0,0 +1,2 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
diff --git a/pym/portage/dep/soname/multilib_category.py b/pym/portage/dep/soname/multilib_category.py
new file mode 100644
index 000000000..30dbe1dd8
--- /dev/null
+++ b/pym/portage/dep/soname/multilib_category.py
@@ -0,0 +1,114 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+#
+# Compute a multilib category, as discussed here:
+#
+# 	https://bugs.gentoo.org/show_bug.cgi?id=534206
+#
+# Supported categories:
+#
+#	alpha_{32,64}
+#	arm_{32,64}
+#	hppa_{32,64}
+#	ia_{32,64}
+#	m68k_{32,64}
+#	mips_{eabi32,eabi64,n32,n64,o32,o64}
+#	ppc_{32,64}
+#	s390_{32,64}
+#	sh_{32,64}
+#	sparc_{32,64}
+#	x86_{32,64,x32}
+#
+# NOTES:
+#
+# * The ABIs referenced by some of the above *_32 and *_64 categories
+#   may be imaginary, but they are listed anyway, since the goal is to
+#   establish a naming convention that is as consistent and uniform as
+#   possible.
+#
+# * The Elf header's e_ident[EI_OSABI] byte is completely ignored,
+#   since OS-independence is one of the goals. The assumption is that,
+#   for given installation, we are only interested in tracking multilib
+#   ABIs for a single OS.
+
+from __future__ import unicode_literals
+
+from portage.util.elf.constants import (
+	EF_MIPS_ABI, EF_MIPS_ABI2, ELFCLASS32, ELFCLASS64,
+	EM_386, EM_68K, EM_AARCH64, EM_ALPHA, EM_ARM, EM_IA_64, EM_MIPS,
+	EM_PARISC, EM_PPC, EM_PPC64, EM_S390, EM_SH, EM_SPARC,
+	EM_SPARC32PLUS, EM_SPARCV9, EM_X86_64, E_MIPS_ABI_EABI32,
+	E_MIPS_ABI_EABI64, E_MIPS_ABI_O32, E_MIPS_ABI_O64)
+
+_machine_prefix_map = {
+	EM_386:             "x86",
+	EM_68K:             "m68k",
+	EM_AARCH64:         "arm",
+	EM_ALPHA:           "alpha",
+	EM_ARM:             "arm",
+	EM_IA_64:           "ia",
+	EM_MIPS:            "mips",
+	EM_PARISC:          "hppa",
+	EM_PPC:             "ppc",
+	EM_PPC64:           "ppc",
+	EM_S390:            "s390",
+	EM_SH:              "sh",
+	EM_SPARC:           "sparc",
+	EM_SPARC32PLUS:     "sparc",
+	EM_SPARCV9:         "sparc",
+	EM_X86_64:          "x86",
+}
+
+_mips_abi_map = {
+	E_MIPS_ABI_EABI32:  "eabi32",
+	E_MIPS_ABI_EABI64:  "eabi64",
+	E_MIPS_ABI_O32:     "o32",
+	E_MIPS_ABI_O64:     "o64",
+}
+
+def _compute_suffix_mips(elf_header):
+
+	name = None
+	mips_abi = elf_header.e_flags & EF_MIPS_ABI
+
+	if mips_abi:
+		name = _mips_abi_map.get(mips_abi)
+	elif elf_header.e_flags & EF_MIPS_ABI2:
+		name = "n32"
+	elif elf_header.ei_class == ELFCLASS64:
+		name = "n64"
+
+	return name
+
+def compute_multilib_category(elf_header):
+	"""
+	Compute a multilib category from an ELF header.
+
+	@param elf_header: an ELFHeader instance
+	@type elf_header: ELFHeader
+	@rtype: str
+	@return: A multilib category, or None if elf_header does not fit
+		into a recognized category
+	"""
+	category = None
+	if elf_header.e_machine is not None:
+
+		prefix = _machine_prefix_map.get(elf_header.e_machine)
+		suffix = None
+
+		if prefix == "mips":
+			suffix = _compute_suffix_mips(elf_header)
+		elif elf_header.ei_class == ELFCLASS64:
+			suffix = "64"
+		elif elf_header.ei_class == ELFCLASS32:
+			if elf_header.e_machine == EM_X86_64:
+				suffix = "x32"
+			else:
+				suffix = "32"
+
+		if prefix is None or suffix is None:
+			category = None
+		else:
+			category = "%s_%s" % (prefix, suffix)
+
+	return category
diff --git a/pym/portage/package/ebuild/doebuild.py b/pym/portage/package/ebuild/doebuild.py
index 0ac016694..a5970d5ec 100644
--- a/pym/portage/package/ebuild/doebuild.py
+++ b/pym/portage/package/ebuild/doebuild.py
@@ -33,7 +33,11 @@ portage.proxy.lazyimport.lazyimport(globals(),
 	'portage.package.ebuild._ipc.QueryCommand:QueryCommand',
 	'portage.dep._slot_operator:evaluate_slot_operator_equal_deps',
 	'portage.package.ebuild._spawn_nofetch:spawn_nofetch',
+	'portage.util.elf.header:ELFHeader',
+	'portage.dep.soname.multilib_category:compute_multilib_category',
 	'portage.util._desktop_entry:validate_desktop_entry',
+	'portage.util._dyn_libs.NeededEntry:NeededEntry',
+	'portage.util._dyn_libs.soname_deps:SonameDepsProcessor',
 	'portage.util._async.SchedulerInterface:SchedulerInterface',
 	'portage.util._eventloop.EventLoop:EventLoop',
 	'portage.util._eventloop.global_event_loop:global_event_loop',
@@ -57,9 +61,9 @@ from portage.eapi import eapi_exports_KV, eapi_exports_merge_type, \
 	eapi_has_pkg_pretend, _get_eapi_attrs
 from portage.elog import elog_process, _preload_elog_modules
 from portage.elog.messages import eerror, eqawarn
-from portage.exception import DigestException, FileNotFound, \
-	IncorrectParameter, InvalidDependString, PermissionDenied, \
-	UnsupportedAPIException
+from portage.exception import (DigestException, FileNotFound,
+	IncorrectParameter, InvalidData, InvalidDependString,
+	PermissionDenied, UnsupportedAPIException)
 from portage.localization import _
 from portage.output import colormap
 from portage.package.ebuild.prepare_build_dirs import prepare_build_dirs
@@ -77,6 +81,11 @@ from _emerge.EbuildSpawnProcess import EbuildSpawnProcess
 from _emerge.Package import Package
 from _emerge.RootConfig import RootConfig
 
+if sys.hexversion >= 0x3000000:
+	_unicode = str
+else:
+	_unicode = unicode
+
 _unsandboxed_phases = frozenset([
 	"clean", "cleanrm", "config",
 	"help", "info", "postinst",
@@ -2261,21 +2270,64 @@ def _post_src_install_soname_symlinks(mysettings, out):
 		is_libdir_cache[obj_parent] = rval
 		return rval
 
+	build_info_dir = os.path.join(
+		mysettings['PORTAGE_BUILDDIR'], 'build-info')
+	try:
+		with io.open(_unicode_encode(os.path.join(build_info_dir,
+			"PROVIDES_EXCLUDE"), encoding=_encodings['fs'],
+			errors='strict'), mode='r', encoding=_encodings['repo.content'],
+			errors='replace') as f:
+			provides_exclude = f.read()
+	except IOError as e:
+		if e.errno not in (errno.ENOENT, errno.ESTALE):
+			raise
+		provides_exclude = ""
+
+	try:
+		with io.open(_unicode_encode(os.path.join(build_info_dir,
+			"REQUIRES_EXCLUDE"), encoding=_encodings['fs'],
+			errors='strict'), mode='r', encoding=_encodings['repo.content'],
+			errors='replace') as f:
+			requires_exclude = f.read()
+	except IOError as e:
+		if e.errno not in (errno.ENOENT, errno.ESTALE):
+			raise
+		requires_exclude = ""
+
 	missing_symlinks = []
+	soname_deps = SonameDepsProcessor(
+		provides_exclude, requires_exclude)
+
+	# Parse NEEDED.ELF.2 like LinkageMapELF.rebuild() does, and
+	# rewrite it to include multilib categories.
+	needed_file = portage.util.atomic_ofstream(needed_filename,
+		encoding=_encodings["repo.content"], errors="strict")
 
-	# Parse NEEDED.ELF.2 like LinkageMapELF.rebuild() does.
 	for l in lines:
 		l = l.rstrip("\n")
 		if not l:
 			continue
-		fields = l.split(";")
-		if len(fields) < 5:
-			portage.util.writemsg_level(_("\nWrong number of fields " \
-				"in %s: %s\n\n") % (needed_filename, l),
+		try:
+			entry = NeededEntry.parse(needed_filename, l)
+		except InvalidData as e:
+			portage.util.writemsg_level("\n%s\n\n" % (e,),
 				level=logging.ERROR, noiselevel=-1)
 			continue
 
-		obj, soname = fields[1:3]
+		filename = os.path.join(image_dir,
+			entry.filename.lstrip(os.sep))
+		with open(_unicode_encode(filename, encoding=_encodings['fs'],
+			errors='strict'), 'rb') as f:
+			elf_header = ELFHeader.read(f)
+
+		# Compute the multilib category and write it back to the file.
+		entry.multilib_category = compute_multilib_category(elf_header)
+		needed_file.write(_unicode(entry))
+
+		soname_deps.add(entry)
+		obj = entry.filename
+		soname = entry.soname
+
 		if not soname:
 			continue
 		if not is_libdir(os.path.dirname(obj)):
@@ -2295,6 +2347,22 @@ def _post_src_install_soname_symlinks(mysettings, out):
 
 		missing_symlinks.append((obj, soname))
 
+	needed_file.close()
+
+	if soname_deps.requires is not None:
+		with io.open(_unicode_encode(os.path.join(build_info_dir,
+			'REQUIRES'), encoding=_encodings['fs'], errors='strict'),
+			mode='w', encoding=_encodings['repo.content'],
+			errors='strict') as f:
+			f.write(soname_deps.requires)
+
+	if soname_deps.provides is not None:
+		with io.open(_unicode_encode(os.path.join(build_info_dir,
+			'PROVIDES'), encoding=_encodings['fs'], errors='strict'),
+			mode='w', encoding=_encodings['repo.content'],
+			errors='strict') as f:
+			f.write(soname_deps.provides)
+
 	if not missing_symlinks:
 		return
 
diff --git a/pym/portage/util/_dyn_libs/LinkageMapELF.py b/pym/portage/util/_dyn_libs/LinkageMapELF.py
index 3920f9487..c44666ac3 100644
--- a/pym/portage/util/_dyn_libs/LinkageMapELF.py
+++ b/pym/portage/util/_dyn_libs/LinkageMapELF.py
@@ -11,12 +11,37 @@ from portage import _os_merge
 from portage import _unicode_decode
 from portage import _unicode_encode
 from portage.cache.mappings import slot_dict_class
-from portage.exception import CommandNotFound
+from portage.exception import CommandNotFound, InvalidData
 from portage.localization import _
 from portage.util import getlibpaths
 from portage.util import grabfile
 from portage.util import normalize_path
+from portage.util import varexpand
 from portage.util import writemsg_level
+from portage.util._dyn_libs.NeededEntry import NeededEntry
+
+# Map ELF e_machine values from NEEDED.ELF.2 to approximate multilib
+# categories. This approximation will produce incorrect results on x32
+# and mips systems, but the result is not worse than using the raw
+# e_machine value which was used by earlier versions of portage.
+_approx_multilib_categories = {
+	"386":           "x86_32",
+	"68K":           "m68k_32",
+	"AARCH64":       "arm_64",
+	"ALPHA":         "alpha_64",
+	"ARM":           "arm_32",
+	"IA_64":         "ia_64",
+	"MIPS":          "mips_o32",
+	"PARISC":        "hppa_64",
+	"PPC":           "ppc_32",
+	"PPC64":         "ppc_64",
+	"S390":          "s390_64",
+	"SH":            "sh_32",
+	"SPARC":         "sparc_32",
+	"SPARC32PLUS":   "sparc_32",
+	"SPARCV9":       "sparc_64",
+	"X86_64":        "x86_64",
+}
 
 class LinkageMapELF(object):
 
@@ -294,21 +319,31 @@ class LinkageMapELF(object):
 					"in %s: %s\n\n") % (location, l),
 					level=logging.ERROR, noiselevel=-1)
 				continue
-			fields = l.split(";")
-			if len(fields) < 5:
-				writemsg_level(_("\nWrong number of fields " \
-					"in %s: %s\n\n") % (location, l),
+			try:
+				entry = NeededEntry.parse(location, l)
+			except InvalidData as e:
+				writemsg_level("\n%s\n\n" % (e,),
 					level=logging.ERROR, noiselevel=-1)
 				continue
-			arch = fields[0]
-			obj = fields[1]
-			soname = fields[2]
-			path = frozenset(normalize_path(x) \
-				for x in filter(None, fields[3].replace(
-				"${ORIGIN}", os.path.dirname(obj)).replace(
-				"$ORIGIN", os.path.dirname(obj)).split(":")))
+
+			# If NEEDED.ELF.2 contains the new multilib category field,
+			# then use that for categorization. Otherwise, if a mapping
+			# exists, map e_machine (entry.arch) to an approximate
+			# multilib category. If all else fails, use e_machine, just
+			# as older versions of portage did.
+			arch = entry.multilib_category
+			if arch is None:
+				arch = _approx_multilib_categories.get(
+					entry.arch, entry.arch)
+
+			obj = entry.filename
+			soname = entry.soname
+			expand = {"ORIGIN": os.path.dirname(entry.filename)}
+			path = frozenset(normalize_path(varexpand(x, expand))
+				for x in entry.runpaths)
 			path = frozensets.setdefault(path, path)
-			needed = frozenset(x for x in fields[4].split(",") if x)
+			needed = frozenset(entry.needed)
+
 			needed = frozensets.setdefault(needed, needed)
 
 			obj_key = self._obj_key(obj)
diff --git a/pym/portage/util/_dyn_libs/NeededEntry.py b/pym/portage/util/_dyn_libs/NeededEntry.py
new file mode 100644
index 000000000..c52cfce3c
--- /dev/null
+++ b/pym/portage/util/_dyn_libs/NeededEntry.py
@@ -0,0 +1,82 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import unicode_literals
+
+import sys
+
+from portage import _encodings, _unicode_encode
+from portage.exception import InvalidData
+from portage.localization import _
+
+class NeededEntry(object):
+	"""
+	Represents one entry (line) from a NEEDED.ELF.2 file. The entry
+	must have 5 or more semicolon-delimited fields in order to be
+	considered valid. The sixth field is optional, corresponding
+	to the multilib category. The multilib_category attribute is
+	None if the corresponding field is either empty or missing.
+	"""
+
+	__slots__ = ("arch", "filename", "multilib_category", "needed",
+		"runpaths", "soname")
+
+	_MIN_FIELDS = 5
+	_MULTILIB_CAT_INDEX = 5
+
+	@classmethod
+	def parse(cls, filename, line):
+		"""
+		Parse a NEEDED.ELF.2 entry. Raises InvalidData if necessary.
+
+		@param filename: file name for use in exception messages
+		@type filename: str
+		@param line: a single line of text from a NEEDED.ELF.2 file,
+			without a trailing newline
+		@type line: str
+		@rtype: NeededEntry
+		@return: A new NeededEntry instance containing data from line
+		"""
+		fields = line.split(";")
+		if len(fields) < cls._MIN_FIELDS:
+			raise InvalidData(_("Wrong number of fields "
+				"in %s: %s\n\n") % (filename, line))
+
+		obj = cls()
+		# Extra fields may exist (for future extensions).
+		if (len(fields) > cls._MULTILIB_CAT_INDEX and
+			fields[cls._MULTILIB_CAT_INDEX]):
+			obj.multilib_category = fields[cls._MULTILIB_CAT_INDEX]
+		else:
+			obj.multilib_category = None
+
+		del fields[cls._MIN_FIELDS:]
+		obj.arch, obj.filename, obj.soname, rpaths, needed = fields
+		obj.runpaths = tuple(filter(None, rpaths.split(":")))
+		obj.needed = tuple(filter(None, needed.split(",")))
+
+		return obj
+
+	def __str__(self):
+		"""
+		Format this entry for writing to a NEEDED.ELF.2 file.
+		"""
+		return ";".join([
+				self.arch,
+				self.filename,
+				self.soname,
+				":".join(self.runpaths),
+				",".join(self.needed),
+				(self.multilib_category if self.multilib_category
+				is not None else "")
+		]) + "\n"
+
+	if sys.hexversion < 0x3000000:
+
+		__unicode__ = __str__
+
+		def __str__(self):
+			return _unicode_encode(self.__unicode__(),
+				encoding=_encodings['content'])
+
+		__str__.__doc__ = __unicode__.__doc__
diff --git a/pym/portage/util/_dyn_libs/soname_deps.py b/pym/portage/util/_dyn_libs/soname_deps.py
new file mode 100644
index 000000000..a7d595429
--- /dev/null
+++ b/pym/portage/util/_dyn_libs/soname_deps.py
@@ -0,0 +1,138 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import unicode_literals
+
+import fnmatch
+from itertools import chain
+import os
+import re
+
+from portage.util import shlex_split
+
+class SonameDepsProcessor(object):
+	"""
+	Processes NEEDED.ELF.2 entries for one package, in order to generate
+	REQUIRES and PROVIDES metadata.
+
+	Any sonames provided by the package will automatically be filtered
+	from the generated REQUIRES values.
+	"""
+
+	def __init__(self, provides_exclude, requires_exclude):
+		"""
+		@param provides_exclude: PROVIDES_EXCLUDE value
+		@type provides_exclude: str
+		@param requires_exclude: REQUIRES_EXCLUDE value
+		@type requires_exclude: str
+		"""
+		self._provides_exclude = self._exclude_pattern(provides_exclude)
+		self._requires_exclude = self._exclude_pattern(requires_exclude)
+		self._requires_map = {}
+		self._provides_map = {}
+		self._provides_unfiltered = {}
+		self._provides = None
+		self._requires = None
+		self._intersected = False
+
+	@staticmethod
+	def _exclude_pattern(s):
+		# shlex_split enables quoted whitespace inside patterns
+		if s:
+			pat = re.compile("|".join(
+				fnmatch.translate(x.lstrip(os.sep))
+				for x in shlex_split(s)))
+		else:
+			pat = None
+		return pat
+
+	def add(self, entry):
+		"""
+		Add one NEEDED.ELF.2 entry, for inclusion in the generated
+		REQUIRES and PROVIDES values.
+
+		@param entry: NEEDED.ELF.2 entry
+		@type entry: NeededEntry
+		"""
+
+		multilib_cat = entry.multilib_category
+		if multilib_cat is None:
+			# This usage is invalid. The caller must ensure that
+			# the multilib category data is supplied here.
+			raise AssertionError(
+				"Missing multilib category data: %s" % entry.filename)
+
+		if entry.needed and (
+			self._requires_exclude is None or
+			self._requires_exclude.match(
+			entry.filename.lstrip(os.sep)) is None):
+			for x in entry.needed:
+				if (self._requires_exclude is None or
+					self._requires_exclude.match(x) is None):
+					self._requires_map.setdefault(
+						multilib_cat, set()).add(x)
+
+		if entry.soname:
+			self._provides_unfiltered.setdefault(
+				multilib_cat, set()).add(entry.soname)
+
+		if entry.soname and (
+			self._provides_exclude is None or
+			(self._provides_exclude.match(
+			entry.filename.lstrip(os.sep)) is None and
+			self._provides_exclude.match(entry.soname) is None)):
+			self._provides_map.setdefault(
+				multilib_cat, set()).add(entry.soname)
+
+	def _intersect(self):
+		requires_map = self._requires_map
+		provides_map = self._provides_map
+		provides_unfiltered = self._provides_unfiltered
+
+		for multilib_cat in set(chain(requires_map, provides_map)):
+			requires_map.setdefault(multilib_cat, set())
+			provides_map.setdefault(multilib_cat, set())
+			provides_unfiltered.setdefault(multilib_cat, set())
+			for soname in list(requires_map[multilib_cat]):
+				if soname in provides_unfiltered[multilib_cat]:
+					requires_map[multilib_cat].remove(soname)
+
+		provides_data = []
+		for multilib_cat in sorted(provides_map):
+			if provides_map[multilib_cat]:
+				provides_data.append(multilib_cat + ":")
+				provides_data.extend(sorted(provides_map[multilib_cat]))
+
+		if provides_data:
+			self._provides = " ".join(provides_data) + "\n"
+
+		requires_data = []
+		for multilib_cat in sorted(requires_map):
+			if requires_map[multilib_cat]:
+				requires_data.append(multilib_cat + ":")
+				requires_data.extend(sorted(requires_map[multilib_cat]))
+
+		if requires_data:
+			self._requires = " ".join(requires_data) + "\n"
+
+		self._intersected = True
+
+	@property
+	def provides(self):
+		"""
+		@rtype: str
+		@return: PROVIDES value generated from NEEDED.ELF.2 entries
+		"""
+		if not self._intersected:
+			self._intersect()
+		return self._provides
+
+	@property
+	def requires(self):
+		"""
+		@rtype: str
+		@return: REQUIRES value generated from NEEDED.ELF.2 entries
+		"""
+		if not self._intersected:
+			self._intersect()
+		return self._requires
diff --git a/pym/portage/util/elf/__init__.py b/pym/portage/util/elf/__init__.py
new file mode 100644
index 000000000..4725d3317
--- /dev/null
+++ b/pym/portage/util/elf/__init__.py
@@ -0,0 +1,2 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
diff --git a/pym/portage/util/elf/constants.py b/pym/portage/util/elf/constants.py
new file mode 100644
index 000000000..f687fdbcc
--- /dev/null
+++ b/pym/portage/util/elf/constants.py
@@ -0,0 +1,45 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+#
+# These constants are available from elfutils:
+# https://git.fedorahosted.org/cgit/elfutils.git/tree/libelf/elf.h
+
+EI_CLASS           = 4
+ELFCLASS32         = 1
+ELFCLASS64         = 2
+
+EI_DATA            = 5
+ELFDATA2LSB        = 1
+ELFDATA2MSB        = 2
+
+E_TYPE             = 16
+ET_REL             = 1
+ET_EXEC            = 2
+ET_DYN             = 3
+ET_CORE            = 4
+
+E_MACHINE          = 18
+EM_SPARC           = 2
+EM_386             = 3
+EM_68K             = 4
+EM_MIPS            = 8
+EM_PARISC          = 15
+EM_SPARC32PLUS     = 18
+EM_PPC             = 20
+EM_PPC64           = 21
+EM_S390            = 22
+EM_ARM             = 40
+EM_SH              = 42
+EM_SPARCV9         = 43
+EM_IA_64           = 50
+EM_X86_64          = 62
+EM_AARCH64         = 183
+EM_ALPHA           = 0x9026
+
+E_ENTRY            = 24
+EF_MIPS_ABI        = 0x0000f000
+EF_MIPS_ABI2       = 0x00000020
+E_MIPS_ABI_O32     = 0x00001000
+E_MIPS_ABI_O64     = 0x00002000
+E_MIPS_ABI_EABI32  = 0x00003000
+E_MIPS_ABI_EABI64  = 0x00004000
diff --git a/pym/portage/util/elf/header.py b/pym/portage/util/elf/header.py
new file mode 100644
index 000000000..3d2307402
--- /dev/null
+++ b/pym/portage/util/elf/header.py
@@ -0,0 +1,65 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.util.endian.decode import (decode_uint16_le,
+	decode_uint32_le, decode_uint16_be, decode_uint32_be)
+from portage.util.elf.constants import (E_ENTRY, E_MACHINE, E_TYPE,
+	EI_CLASS, ELFCLASS32, ELFCLASS64, ELFDATA2LSB, ELFDATA2MSB)
+
+class ELFHeader(object):
+
+	__slots__ = ('e_flags', 'e_machine', 'e_type', 'ei_class',
+		'ei_data')
+
+	@classmethod
+	def read(cls, f):
+		"""
+		@param f: an open ELF file
+		@type f: file
+		@rtype: ELFHeader
+		@return: A new ELFHeader instance containing data from f
+		"""
+		f.seek(EI_CLASS)
+		ei_class = ord(f.read(1))
+		ei_data = ord(f.read(1))
+
+		if ei_class == ELFCLASS32:
+			width = 32
+		elif ei_class == ELFCLASS64:
+			width = 64
+		else:
+			width = None
+
+		if ei_data == ELFDATA2LSB:
+			uint16 = decode_uint16_le
+			uint32 = decode_uint32_le
+		elif ei_data == ELFDATA2MSB:
+			uint16 = decode_uint16_be
+			uint32 = decode_uint32_be
+		else:
+			uint16 = None
+			uint32 = None
+
+		if width is None or uint16 is None:
+			e_flags = None
+			e_machine = None
+			e_type = None
+		else:
+			f.seek(E_TYPE)
+			e_type = uint16(f.read(2))
+			f.seek(E_MACHINE)
+			e_machine = uint16(f.read(2))
+
+			# E_ENTRY + 3 * sizeof(uintN)
+			e_flags_offset = E_ENTRY + 3 * width // 8
+			f.seek(e_flags_offset)
+			e_flags = uint32(f.read(4))
+
+		obj = cls()
+		obj.e_flags = e_flags
+		obj.e_machine = e_machine
+		obj.e_type = e_type
+		obj.ei_class = ei_class
+		obj.ei_data = ei_data
+
+		return obj
diff --git a/pym/portage/util/endian/__init__.py b/pym/portage/util/endian/__init__.py
new file mode 100644
index 000000000..4725d3317
--- /dev/null
+++ b/pym/portage/util/endian/__init__.py
@@ -0,0 +1,2 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
diff --git a/pym/portage/util/endian/decode.py b/pym/portage/util/endian/decode.py
new file mode 100644
index 000000000..9833b53ca
--- /dev/null
+++ b/pym/portage/util/endian/decode.py
@@ -0,0 +1,48 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+import struct
+
+def decode_uint16_be(data):
+	"""
+	Decode an unsigned 16-bit integer with big-endian encoding.
+
+	@param data: string of bytes of length 2
+	@type data: bytes
+	@rtype: int
+	@return: unsigned integer value of the decoded data
+	"""
+	return struct.unpack_from(">H", data)[0]
+
+def decode_uint16_le(data):
+	"""
+	Decode an unsigned 16-bit integer with little-endian encoding.
+
+	@param data: string of bytes of length 2
+	@type data: bytes
+	@rtype: int
+	@return: unsigned integer value of the decoded data
+	"""
+	return struct.unpack_from("<H", data)[0]
+
+def decode_uint32_be(data):
+	"""
+	Decode an unsigned 32-bit integer with big-endian encoding.
+
+	@param data: string of bytes of length 4
+	@type data: bytes
+	@rtype: int
+	@return: unsigned integer value of the decoded data
+	"""
+	return struct.unpack_from(">I", data)[0]
+
+def decode_uint32_le(data):
+	"""
+	Decode an unsigned 32-bit integer with little-endian encoding.
+
+	@param data: string of bytes of length 4
+	@type data: bytes
+	@rtype: int
+	@return: unsigned integer value of the decoded data
+	"""
+	return struct.unpack_from("<I", data)[0]