Re: [gentoo-portage-dev] Speeding up Tree Verification
On Wed, Jul 1, 2020, at 1:40 AM, Fabian Groffen wrote: > On 30-06-2020 13:13:29 -0500, Sid Spry wrote: > > On Tue, Jun 30, 2020, at 1:20 AM, Fabian Groffen wrote: > > > 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. > > > > > > > I think this is an argument for cgroups limits support on the portage > > process or > > account as opposed to an argument against picking a better algorithm. That > > is > > something I have been working towards, but I am only one man. > > But this requires a) cgroups support, and b) the privileges to use it. > Shouldn't be a problem in the normal case, but just saying. > cgroups kernel support is a fairly common dependency. It can obviously be optional, I am thinking related to MAKEOPTS or EMERGE_DEFAULT_OPTS (see: rustc/cargo not respecting or being passed -j/-l as another use for cgroups) and supported best-effort, but is there any reason to expect it to not be enabled? If the user isn't either root or portage I think it reasonable to leave resource management to the machine's administrator.
Re: [gentoo-portage-dev] Speeding up Tree Verification
On Wed, Jul 1, 2020, at 1:40 AM, Fabian Groffen wrote: > On 30-06-2020 13:13:29 -0500, Sid Spry wrote: > > On Tue, Jun 30, 2020, at 1:20 AM, Fabian Groffen wrote: > > > 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. > > > > > > > I think this is an argument for cgroups limits support on the portage > > process or > > account as opposed to an argument against picking a better algorithm. That > > is > > something I have been working towards, but I am only one man. > > But this requires a) cgroups support, and b) the privileges to use it. > Shouldn't be a problem in the normal case, but just saying. > > > > 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? > > > > > > > I ran all tests multiple times to make them warm off of a Samsung SSD, but > > nothing very precise yet. > > > > % gemato verify --openpgp-key signkey.asc /var/db/repos/gentoo > > [...] > > INFO:root:Verifying /var/db/repos/gentoo... > > INFO:root:/var/db/repos/gentoo verified in 16.45 seconds > > > > sometimes going higher, closer to 18s, vs. > > > > % ./veriftree.py > > 4.763171965983929 > > > > So roughly an order of magnitude speedup without batching to threads. > > That is kind of a change. Makes one wonder if you really did the same > work. > That was my initial reaction. I attempted to ensure I was processing all of the files that gemato processed. The full output of my script is something closer to: % ./veriftree.py x.xx 192157 126237 The first number being the time, the second the total number of manifest directives, and the third being the number of real files in the tree. If you prune the directives that correspond to no file you end up with an exact match IIRC. However, you are right, and I think this is old code. gemato times the manifest file parsing as well as the verification. It seems this change is not in the code I provided. If I do that instead, I get: % ./veriftree.py 11.708862617029808 192157 126237 With corresponding times for gemato (at same system state, etc) being ~20s. So it is a halving at worst with assured n-core speedup for 1/2 of that time, and I am fairly confident I can speed up the manifest parsing even more as well. > > > You could compare against qmanifest, which uses OpenMP-based > > > paralllelism while verifying the tree. On SSDs this does help. > > > > > > > I lost my notes -- how do I specify to either gemato or qmanifest the GnuPG > > directory? My code is partially structured as it is because I had problems > > doing > > this. I rediscovered -K/--openpgp-key in gemato but am unsure for qmanifest. > > qmanifest doesn't do much magic out of the standard gnupg practices. > (It is using gpgme.) If you want it to use a different gnupg dir, you > may change HOME, or GNUPGHOME. > Alright, I will attempt to set that. I think I like the interface of gemato a little more but will look at qmanifest and see how it performs.
Re: [gentoo-portage-dev] Speeding up Tree Verification
On Tue, 2020-06-30 at 16:51 -0500, Sid Spry wrote: > On Tue, Jun 30, 2020, at 2:29 PM, Michał Górny wrote: > > On Tue, 2020-06-30 at 12:50 -0500, Sid Spry wrote: > > > On Tue, Jun 30, 2020, at 2:28 AM, Michał Górny wrote: > > > > Dnia June 30, 2020 2:13:43 AM UTC, Sid Spry napisał(a): > > > > > 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?). > > > > > > > > Without reading the code: does your algorithm correctly detect > > > > extraneous files? > > > > > > > > > > Yes and no. > > > > > > I am not sure why this is necessary. If the file does not appear in a > > > manifest it is > > > ignored. It makes the most sense to me to put the burden of not including > > > untracked files on the publisher. If the user puts an untracked file into > > > the tree it > > > will be ignored to no consequence; the authored files don't refer to it, > > > after all. > > > > This is necessary because a malicious third party can MITM you an rsync > > tree with extraneous files (say, -r1 baselayout ebuild) that do horrible > > things on your system. If you don't reject files not in Manifest, you > > open a huge security hole. > > > > Ok, I will refer to https://www.gentoo.org/glep/glep-0074.html and implement > the > checks in detail, but will still need to spend some time looking for the best > place > to insert the code. > > I think it best to address this from two fronts. On one hand rejecting extra > files > seems to have immediate benefit but the larger issue is portage exposing > untracked potentially malicious files to the user. I've pushed two branches with two exploits I could think of. Please test your tools against them. In both cases, the directory should be rejected without any ill effects. https://github.com/mgorny/glep74-test-cases > > Has anything like a verity loopback filesystem been explored? It might reduce > duplication of work. I don't understand what a 'verity loopback filesystem' is. Could you elaborate? -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-portage-dev] Speeding up Tree Verification
On 30-06-2020 13:13:29 -0500, Sid Spry wrote: > On Tue, Jun 30, 2020, at 1:20 AM, Fabian Groffen wrote: > > 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. > > > > I think this is an argument for cgroups limits support on the portage process > or > account as opposed to an argument against picking a better algorithm. That is > something I have been working towards, but I am only one man. But this requires a) cgroups support, and b) the privileges to use it. Shouldn't be a problem in the normal case, but just saying. > > 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? > > > > I ran all tests multiple times to make them warm off of a Samsung SSD, but > nothing very precise yet. > > % gemato verify --openpgp-key signkey.asc /var/db/repos/gentoo > [...] > INFO:root:Verifying /var/db/repos/gentoo... > INFO:root:/var/db/repos/gentoo verified in 16.45 seconds > > sometimes going higher, closer to 18s, vs. > > % ./veriftree.py > 4.763171965983929 > > So roughly an order of magnitude speedup without batching to threads. That is kind of a change. Makes one wonder if you really did the same work. > > You could compare against qmanifest, which uses OpenMP-based > > paralllelism while verifying the tree. On SSDs this does help. > > > > I lost my notes -- how do I specify to either gemato or qmanifest the GnuPG > directory? My code is partially structured as it is because I had problems > doing > this. I rediscovered -K/--openpgp-key in gemato but am unsure for qmanifest. qmanifest doesn't do much magic out of the standard gnupg practices. (It is using gpgme.) If you want it to use a different gnupg dir, you may change HOME, or GNUPGHOME. Thanks, Fabian -- Fabian Groffen Gentoo on a different level signature.asc Description: PGP signature
