Re: [gentoo-portage-dev] Speeding up Tree Verification

[Michał Górny]

Dnia June 30, 2020 6:20:37 AM UTC, Fabian Groffen <grobian@g.o> napisał(a):
>Hi,
>
>On 29-06-2020 21:13:43 -0500, Sid Spry wrote:
>> Hello,
>>
>> I have some runnable pseudocode outlining a faster tree verification
>algorithm.
>> Before I create patches I'd like to see if there is any guidance on
>making the
>> changes as unobtrusive as possible. If the radical change in
>algorithm is
>> acceptable I can work on adding the changes.
>>
>> Instead of composing any kind of structured data out of the portage
>tree my
>> algorithm just lists all files and then optionally batches them out
>to threads.
>> There is a noticeable speedup by eliding the tree traversal
>operations which
>> can be seen when running the algorithm with a single thread and
>comparing it to
>> the current algorithm in gemato (which should still be discussed
>here?).
>
>I remember something that gemato used to use multiple threads, but
>because it totally saturated disk-IO, it was brought back to a single
>thread.  People were complaining about unusable systems.

No, it gave significant speedup even on spinning HDDs. However, it hang on some people due to some bug that I couldn't reproduce.

>
>In any case, can you share your performance results?  What speedup did
>you see, on warm and hot FS caches?  Which type of disk do you use?
>
>You could compare against qmanifest, which uses OpenMP-based
>paralllelism while verifying the tree.  On SSDs this does help.
>
>Thanks,
>Fabian
>
>>
>> Some simple tests like counting all objects traversed and verified
>returns the
>> same(ish). Once it is put into portage it could be tested in detail.
>>
>> There is also my partial attempt at removing the brittle interface to
>GnuPG
>> (it's not as if the current code is badly designed, just that parsing
>the
>> output of GnuPG directly is likely not the best idea).
>>
>> Needs gemato, dnspython, and requests. Slightly better than random
>code because
>> I took inspiration from the existing gemato classes.
>>
>> ```python (veriftree.py)
>> #!/usr/bin/env python3
>> import os, sys, zlib, hashlib, tempfile, shutil, timeit
>> import subprocess
>> from typing import List
>> from pprint import pprint
>>
>> from gemato.manifest import (
>>     ManifestFile,
>>     ManifestFileEntry,
>> )
>> from wkd import (
>>     check_domain_signature,
>>     hash_localpart,
>>     build_web_key_uri,
>>     stream_to_file
>> )
>> from fetchmedia import (
>>     OpenPGPEnvironment,
>>     setup_verification_environment
>> )
>>
>> # 0. Top level directory (repository) contains Manifest, a PGP
>signature of
>> #    blake2b and sha512 hashes of Manifest.files.gz.
>> # 1. Manifest.files contains hashes of each category Manifest.gz.
>> # 2. The category Manifest contains hashes of each package Manifest.
>> # 3. The package Manifest contains hashes of each package file.
>> #    Must be aware of PMS, e.g. aux tag specifies a file in files/.
>>
>> # 0. Check signature of repo Manifest.
>> # 1. Merge items in Manifest.files, each category Manifest, and each
>package
>> #    Manifest into one big list. The path must be made absolute.
>> # 2. Distribute items to threads.
>>
>> # To check operation compare directory tree to files appearing in all
>> # ManifestRecords.
>>
>> class ManifestTree(object):
>>     __slots__ = ['_directory', '_manifest_list', '_manifest_records',
>>         '_manifest_results']
>>
>>     def __init__(self, directory: str):
>>         self._directory = directory
>>         # Tuples of (base_path, full_path).
>>         self._manifest_list = []
>>         self._manifest_records = []
>>         self._manifest_results = []
>>
>>     def build_manifest_list(self):
>>         for path, dirs, files in os.walk(self._directory):
>>             #if 'glsa' in path or 'news' in path:
>>             #if 'metadata' in path:
>>             #    continue # Skip the metadata directory for now.
>>                 # It contains a repository. Current algo barfs on
>Manifest
>>                 # containing only sig.
>>
>>             if 'Manifest.files.gz' in files:
>>                 self._manifest_list += [(path, path +
>'/Manifest.files.gz')]
>>             if 'Manifest.gz' in files:
>>                 self._manifest_list += [(path, path +
>'/Manifest.gz')]
>>
>>             if path == self._directory:
>>                 continue # Skip the repo manifest. Order matters, fix
>eventually.
>>             if 'Manifest' in files:
>>                 self._manifest_list += [(path, path + '/Manifest')]
>>
>>     def parse_manifests(self):
>>         td = tempfile.TemporaryDirectory(dir='./')
>>         for manifest in self._manifest_list:
>>             def inner():
>>                 if manifest[1].endswith('.gz'):
>>                     name = 'Manifest.files' # Need to also handle
>Manifest.gz.
>>                     path = '{0}/{1}'.format(td.name, name)
>>                     subprocess.run(['sh', '-c', 'gunzip -c {0} > {1}'
>>                         .format(manifest[1], path)])
>>                     for line in open(path):
>>                         mr = ManifestRecord(line)
>>                         mr.make_absolute(manifest[0])
>>                         self._manifest_records += [mr]
>>                 else:
>>                     for line in open(manifest[1]):
>>                         if line.startswith('-'):
>>                             return # Skip the signed manifest.
>>                         mr = ManifestRecord(line)
>>                         mr.make_absolute(manifest[0])
>>                         self._manifest_records += [mr]
>>             inner()
>>
>>     def verify_manifests(self):
>>         for record in self._manifest_records:
>>             self._manifest_results += [record.verify()]
>>
>>
>> class ManifestRecord(object):
>>     __slots__ = ['_tag', '_abs_path', '_path', '_size', '_hashes']
>>
>>     def __init__(self, line: str=None):
>>         self._tag = None
>>         self._abs_path = None
>>         self._path = None
>>         self._size = None
>>         self._hashes = []
>>         if line:
>>             self.from_string(line)
>>
>>     def from_string(self, line: str) -> None:
>>         parts = line.split()
>>         if len(parts) == 2:
>>             self._tag = 'ignore'
>>             return
>>         self._tag = parts[0]
>>         self._path = parts[1]
>>         self._size = parts[2]
>>         self._hashes = parts[3:]
>>
>>     def make_absolute(self, abs_path: str) -> None:
>>         self._abs_path = abs_path
>>         try:
>>             pass
>>             #if 'md5-cache' in abs_path:
>>             #    print(abs_path + '/' + self._path)
>>         except TypeError as exc:
>>             return
>>
>>     def verify(self) -> bool:
>>         if self._tag == 'ignore':
>>             return None
>>
>>         # Where is best place to do this? Before?
>>         if self._tag.lower() == 'aux':
>>             self._path = self._abs_path + '/files/' + self._path
>>         elif self._abs_path:
>>             self._path = self._abs_path + '/' + self._path
>>
>>         # Distfiles will not be present.
>>         if self._tag.lower() == 'dist':
>>             return None
>>
>>         if not os.path.exists(self._path):
>>             return False
>>
>>         fd = open(self._path, 'rb')
>>         sha512 = hashlib.sha512()
>>         blake2b = hashlib.blake2b()
>>         while True:
>>             d = fd.read(8192)
>>             if not d:
>>                 break
>>             sha512.update(d)
>>             blake2b.update(d)
>>         rsha512 = sha512.hexdigest()
>>         rblake2b = blake2b.hexdigest()
>>
>>         if rblake2b != self._hashes[1]:
>>             return False
>>
>>         if rsha512 != self._hashes[3]:
>>             return False
>>
>>         return True
>>
>>     def __repr__(self) -> str:
>>         #return repr(self._hashes)
>>         return '\t'.join([self._tag, self._size, self._path])
>>
>> def main() -> int:
>>     # Step 0: verify the repo manifest.
>>     #publishers = ['infrastructure@g.o']
>>     #ev = setup_verification_environment(publishers)
>>     #mf = ManifestFile()
>>     #mf.load(open('/var/db/repos/gentoo/Manifest'),
>>     #    verify_openpgp=True, openpgp_env=ev)
>>     #pprint(mf)
>>     #pprint(mf.openpgp_signed)
>>     #pprint(mf.openpgp_signature)
>>
>>     # Step 1: merge manifests.
>>     #mt = ManifestTree('/var/db/repos/gentoo')
>>     #mt.build_manifest_list()
>>     #mt.parse_manifests()
>>     #mt.verify_manifests()
>>
>>     glsa = ManifestTree('/var/db/repos/gentoo')
>>     glsa.build_manifest_list()
>>     glsa.parse_manifests()
>>
>>     start = timeit.default_timer()
>>     glsa.verify_manifests()
>>     end = timeit.default_timer()
>>     pprint(end - start)
>>
>>     # Handled by checking for None.
>>     #no_ignore = filter(lambda x: x._tag != 'ignore',
>glsa_manifest_results)
>>
>>
>>     #pprint(glsa._manifest_results)
>>     real_files = [x for x in filter(lambda x: x is not None,
>glsa._manifest_results)]
>>     #pprint(real_files)
>>     pprint(len(glsa._manifest_results))
>>     pprint(len(real_files))
>>
>>     all_files = []
>>     for path, dirs, files in os.walk('/var/db/repos/gentoo'):
>>         pass
>>
>>     return 0
>>
>> if __name__ == '__main__':
>>     sys.exit(main())
>> ```
>>
>> ```python (wkd.py, likely unneeded but I didn't want to redo these
>files yet)
>> #!/usr/bin/env python3
>> import sys, hashlib
>> import dns
>> from dns import (
>>     name, query, dnssec,
>>     message, resolver, rdatatype
>> )
>> import shutil, requests
>>
>> def check_domain_signature(domain: str) -> bool:
>>     response = dns.resolver.query(domain, dns.rdatatype.NS)
>>     nsname = response.rrset[0]
>>     response = dns.resolver.query(str(nsname), dns.rdatatype.A)
>>     nsaddr = response.rrset[0].to_text()
>>
>>     # DNSKEY
>>     request = dns.message.make_query(domain,
>>         dns.rdatatype.DNSKEY, want_dnssec=True)
>>     response = dns.query.udp(request, nsaddr)
>>     if response.rcode() != 0:
>>         raise Exception('Unable to request dnskey.')
>>
>>     answer = response.answer
>>     if len(answer) != 2:
>>         raise Exception('Malformed answer to dnskey query.')
>>
>>     name = dns.name.from_text(domain)
>>     try:
>>         dns.dnssec.validate(answer[0], answer[1], {name: answer[0]})
>>     except dns.dnssec.ValidationFailure as exc:
>>         # Validation failed. The raise causes python to abort with
>status 1.
>>         #raise exc
>>         return False
>>     except AttributeError as exc:
>>         # Validation may have failed; DNSKEY missing signer
>attribute. dig may report
>>         # domain as valid.
>>         #
>>         # TODO: Additional state where subdomain of valid domain may
>fail with 3 nested
>>         # KeyErrors. Avoid temptation to wildcard catch. Safer to put
>in process?
>>         #raise exc
>>         return False
>>     else:
>>         return True
>>
>> def hash_localpart(incoming: bytes) -> str:
>>     '''Z-base32 the localpart of an e-mail address
>>
>>
>https://tools.ietf.org/html/draft-koch-openpgp-webkey-service-08#section-3.1
>>     describes why this is needed.
>>
>>     See https://tools.ietf.org/html/rfc6189#section-5.1.6 for a
>>     description of the z-base32 scheme.
>>     '''
>>     zb32 = "ybndrfg8ejkmcpqxot1uwisza345h769"
>>
>>     b = hashlib.sha1(incoming).digest()
>>     ret = ""
>>     assert(len(b) * 8 == 160)
>>     for i in range(0, 160, 5):
>>         byte = i // 8
>>         offset = i - byte * 8
>>         # offset | bits remaining in k+1 | right-shift k+1
>>         # 3 | 0 | x
>>         # 4 | 1 | 7
>>         # 5 | 2 | 6
>>         # 6 | 3 | 5
>>         # 7 | 4 | 4
>>         if offset < 4:
>>             n = (b[byte] >> (3 - offset))
>>         else:
>>             n = (b[byte] << (offset - 3)) + (b[byte + 1] >> (11 -
>offset))
>>
>>         ret += zb32[n & 0b11111]
>>     return ret
>>
>> def build_web_key_uri(address: str) -> str:
>>     local, remote = address.split('@')
>>     local = hash_localpart(local.encode('utf-8'))
>>     return 'https://' + remote + '/.well-known/openpgpkey/hu/' + \
>>         local
>>
>> def stream_to_file(uri: str, fname: str) -> None:
>>     with requests.get(uri, verify=True, stream=True) as r:
>>         from pprint import pprint
>>         pprint(r.headers)
>>         with open(fname, 'wb') as f:
>>             shutil.copyfileobj(r.raw, f)
>> ```
>>


--
Best regards, 
Michał Górny