Re: [gentoo-dev] SAT-based dependency solver: request for test cases
Hi Michael, I haven't fully understood SAT yet and I haven't completely follow the discussion. But I think this is a logical direction to improve dependency solving in Gentoo. Keep on the good work, I am interested in knowing how well it performs. Yours, Benda
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
Dear Michał, I understand your concerns, and for some time I shared them too. Portage is a very complex piece of software that evolved for almost 20 years to perform a very difficult task quite quickly with good results, so it is bound to contain many ad-hoc fixes and tweaks that can hardly be encoded into SAT constraints. However, I think there are two arguments strongly in favor of my approach. 1. it seems to me that there is a real effort from the gentoo community and management to have a precise description of how Portage should behave, with the PMS and all the documentation on the wiki and devmanual. My work is based on this documentation and goes in the same direction by giving a simple and unambiguous description (i.e., a formal semantics) of Portage's dependencies as described in Section 8.2 of the PMS. 2. My work currently *only* focuses on the package dependencies. I don't deal with eclasses (I use egencache files), I don't deal with installation order (I just compute which packages must be installed in the end: in doing so, I avoid the circular dependency problem you were talking about), I don't deal with actual package compilation, installation, etc. I focus on a very precise part of Portage, dependency solving, subject on which I have some expertise. So I agree with you that it is unlikely that my prototype's outputs will correspond one to one to emerge's. However, I think it can be positive for Portage. As my prototype uses an off-the-shelf solver as backend, in principle it just consists of a translation of Section 8.2 of the PMS into SAT constraints: consequently, it is a rather small piece of code compared to Portage, and once I finish reading the PMS and clean up my implementation, it would likely be a correct implementation of the PMS, or at least simple enough to be easily checked and corrected. Then, testing my prototype to check for bugs is also a good opportunity to check for bugs into Portage itself, by taking the PMS as reference. And if you are right and my prototype --a direct translation of the PMS-- ends up worse than Portage, then maybe this means that the PMS should be revised. Also, in the long run, having an alternative implementation of one of Portage's functionality instead of a complete alternative to Portage like paludis or pkgcore, could help in the discussion about a modular implementation of Portage (I've heard some people talking about it), or about a next version of the PMS. I'll finish my prototype as soon as possible and see what the tests will tell. Best regards, Michael Lienhardt Il 10/02/2018 09:20, Michał Górny ha scritto: W dniu wto, 06.02.2018 o godzinie 11∶52 +0100, użytkownik Michael Lienhardt napisał: Dear all, With the help of some friends and colleagues, I am working on an SAT-based dependency solver for portage. We need your help to test it and possibly improve in the long run the already great portage toolset. To help, you can send us the tar generated by this bash script: https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh This bash script extracts your world file, the USE flags and keywords configuration of your system and the list of installed packages you have (it should not take more than few seconds). With this, we will see if our solver is able to recreate your system and how much time it takes. To be honest, I don't think this is the right approach to the problem. Truth is, dependencies in Gentoo are seriously broken, and most of the developers aren't even aware of that because of layers upon layers of hacks in Portage that make emerge somewhat go on. If you are really able to build something on top of the input you receive, it's probably going to be even worse than what's already in Portage. Example: many packages have impossible circular dependencies. However, Portage conditionally pretends they don't exist, preferring some random install-time breakage over fixing the packages in question.
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
Sorry for the late reply. This is a very interesting offer :) However, I don't have the capacity to manage such quantity of data yet. Up until now, I performed my tests in a VM on my laptop without anything else running... Few days ago, my department lent me a dedicated laptop to perform the tests, which I still need to set up... I'll definitively get back to you soonish. Thanks! Michael Il 08/02/2018 20:57, Toralf Förster ha scritto: On 02/06/2018 11:52 AM, Michael Lienhardt wrote: To help, you can send us the tar generated by this bash script: https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh This bash script extracts your world file, the USE flags and keywords configuration of your system and the list of installed packages you have (it should not take more than few seconds). With this, we will see if our solver is able to recreate your system and how much time it takes. You can send everything to my professional email: mlien...@di.unito.it Just send an email to that with an uunencoded tar.xz file from one of the tinderbox images [1] I do run. I can adapt the scripts to send the result file of each of the currently 7 running images daily. [1] https://zwiebeltoralf.de/tinderbox.html -- Toralf PGP 23217DA7 9B888F45
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
On 10/02/2018 09:20, Michał Górny wrote: > To be honest, I don't think this is the right approach to the problem. Feel free to suggest a better one. > Truth is, dependencies in Gentoo are seriously broken, and most of > the developers aren't even aware of that because of layers upon layers > of hacks in Portage that make emerge somewhat go on. Indeed, I may not be aware of many such problems. Is there a place where the known ones can be documented? Paweł signature.asc Description: OpenPGP digital signature
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
W dniu sob, 10.02.2018 o godzinie 11∶20 +0100, użytkownik Ulrich Mueller napisał: > > > > > > On Sat, 10 Feb 2018, Michał Górny wrote: > > Example: many packages have impossible circular dependencies. > > However, Portage conditionally pretends they don't exist, preferring > > some random install-time breakage over fixing the packages in > > question. > > Isn't that what the PMS allows, though? RDEPEND must be fulfilled, > "unless the particular dependency results in a circular dependency, > in which case it may be installed later". > Yes, and I regret ever adjusting this to match the horribly misjudged Portage behavior. -- Best regards, Michał Górny
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
> On Sat, 10 Feb 2018, Michał Górny wrote: > Example: many packages have impossible circular dependencies. > However, Portage conditionally pretends they don't exist, preferring > some random install-time breakage over fixing the packages in > question. Isn't that what the PMS allows, though? RDEPEND must be fulfilled, "unless the particular dependency results in a circular dependency, in which case it may be installed later". Ulrich pgpXtmrhff4GE.pgp Description: PGP signature
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
W dniu wto, 06.02.2018 o godzinie 11∶52 +0100, użytkownik Michael Lienhardt napisał: > Dear all, > > With the help of some friends and colleagues, I am working on an SAT-based > dependency solver for portage. > We need your help to test it and possibly improve in the long run the already > great portage toolset. > > To help, you can send us the tar generated by this bash script: > https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh > This bash script extracts your world file, the USE flags and keywords > configuration of your system and the list of installed packages you have (it > should not take more than few seconds). > With this, we will see if our solver is able to recreate your system and how > much time it takes. > To be honest, I don't think this is the right approach to the problem. Truth is, dependencies in Gentoo are seriously broken, and most of the developers aren't even aware of that because of layers upon layers of hacks in Portage that make emerge somewhat go on. If you are really able to build something on top of the input you receive, it's probably going to be even worse than what's already in Portage. Example: many packages have impossible circular dependencies. However, Portage conditionally pretends they don't exist, preferring some random install-time breakage over fixing the packages in question. -- Best regards, Michał Górny
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
On 02/06/2018 11:52 AM, Michael Lienhardt wrote: > > To help, you can send us the tar generated by this bash script: > https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh > > This bash script extracts your world file, the USE flags and keywords > configuration of your system and the list of installed packages you > have (it should not take more than few seconds). > With this, we will see if our solver is able to recreate your system > and how much time it takes. > > You can send everything to my professional email: mlien...@di.unito.it > Just send an email to that with an uunencoded tar.xz file from one of the tinderbox images [1] I do run. I can adapt the scripts to send the result file of each of the currently 7 running images daily. [1] https://zwiebeltoralf.de/tinderbox.html -- Toralf PGP 23217DA7 9B888F45 signature.asc Description: OpenPGP digital signature
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
Il 06/02/2018 15:00, Roy Bamford ha scritto: Posting here to alert other potential helpers. Your script uses PACKAGE_KEYWORDS="/etc/portage/package.accept_keywords" but thats a recent name change. PACKAGE_KEYWORDS="/etc/portage/package.keywords" is the old name and my older systems still use that. You probably need to harvest both and process both as portage does. You are right, I was lazy (and hoped that everyone already made the switch because, as I understand it, package.keywords and package.accept_keywords do not have the same semantics). I added the package.keywords file/folder in the script. Thank you, Michael Lienhardt
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
On 18-02-06 11:52:10, Michael Lienhardt wrote: > Dear all, > > With the help of some friends and colleagues, I am working on an SAT-based > dependency solver for portage. > We need your help to test it and possibly improve in the long run the already > great portage toolset. > > To help, you can send us the tar generated by this bash script: > https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh > This bash script extracts your world file, the USE flags and keywords > configuration of your system and the list of installed packages you have (it > should not take more than few seconds). > With this, we will see if our solver is able to recreate your system and how > much time it takes. > > You can send everything to my professional email: mlien...@di.unito.it > > > The goal of this alternative solver is to overcome some of the limitations of > emerge. > Thanks to some users of the forum and the gentoo-user mailing list, I already > tested the solver on 8 systems, and the results for now are: > - emerge is not able to recreate any of these systems (i.e., 'cat > world_of_test_configuration | xargs emerge -vp' on a gentoo osboxes VM does > not succeed, even with the right /etc/portage/package.* files) > - our solver takes 2 minutes in average (with little variation), and gives > either a yes answer (with what to install, which USE flags to set, which > packages to keyword) or a no answer (with the set of conflicting constraints) > for every systems > - we solved one bug in our solver (a behavior of emerge that seems > documented only in the PMS document, not in devmanual nor in the wiki, and > that is visible only in 15 packages), but at least one seems to still be > around. > > I started discussing this on the gentoo-portage-dev and the gentoo-user > mailing lists (sorry for the duplicates), and on the forum with three posts: > - https://forums.gentoo.org/viewtopic-t-1074170.html about the documentation > I collected to implement the solver > - https://forums.gentoo.org/viewtopic-t-1074202.html about the solver and > its motivations > - https://forums.gentoo.org/viewtopic-t-1075286.html about the tests I'm > doing > > > About me: > I'm a researcher in computer science, about formal methods, concurrency and > software engineering. > Friday, I will present my first paper on portage, showing that its packages > and their dependencies constitute what is called a "Multi-Software Product > Line" in software engineering. If you skip the algebraic definition, it > should be readable ^^: http://www.di.unito.it/~mlienhar/vamos.pdf > In 2013, I designed and contributed to the implementation of a dependency > solver for dynamic cloud architecture (currently maintained by Jacopo Mauro > https://bitbucket.org/jacopomauro/zephyrus2/src ) > I'm a gentoo user since 2007, and I'm very happy by this opportunity to > contribute back :). > > This sounds intresting, I wonder how it'd handle things like sys-cluster/openstack-meta which can sometimes require masking a package (gentoo stablizes a package ahead of what openstack has tested support for). -- Matthew Thode (prometheanfire) signature.asc Description: PGP signature
Re: [gentoo-dev] SAT-based dependency solver: request for test cases
On 2018.02.06 10:52, Michael Lienhardt wrote: > Dear all, > > With the help of some friends and colleagues, I am working on an > SAT-based dependency solver for portage. > We need your help to test it and possibly improve in the long run the > already great portage toolset. > > To help, you can send us the tar generated by this bash script: > https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh > This bash script extracts your world file, the USE flags and keywords > configuration of your system and the list of installed packages you > have (it should not take more than few seconds). > With this, we will see if our solver is able to recreate your system > and how much time it takes. > > You can send everything to my professional email: mlien...@di.unito.it > > > The goal of this alternative solver is to overcome some of the > limitations of emerge. > Thanks to some users of the forum and the gentoo-user mailing list, I > already tested the solver on 8 systems, and the results for now are: > - emerge is not able to recreate any of these systems (i.e., 'cat > world_of_test_configuration | xargs emerge -vp' on a gentoo osboxes VM > does not succeed, even with the right /etc/portage/package.* files) > - our solver takes 2 minutes in average (with little variation), and > gives either a yes answer (with what to install, which USE flags to > set, which packages to keyword) or a no answer (with the set of > conflicting constraints) for every systems > - we solved one bug in our solver (a behavior of emerge that seems > documented only in the PMS document, not in devmanual nor in the wiki, > and that is visible only in 15 packages), but at least one seems to > still be around. > > I started discussing this on the gentoo-portage-dev and the > gentoo-user mailing lists (sorry for the duplicates), and on the forum > with three posts: > - https://forums.gentoo.org/viewtopic-t-1074170.html about the > documentation I collected to implement the solver > - https://forums.gentoo.org/viewtopic-t-1074202.html about the > solver and its motivations > - https://forums.gentoo.org/viewtopic-t-1075286.html about the tests > I'm doing > > > About me: > I'm a researcher in computer science, about formal methods, > concurrency and software engineering. > Friday, I will present my first paper on portage, showing that its > packages and their dependencies constitute what is called a > "Multi-Software Product Line" in software engineering. If you skip the > algebraic definition, it should be readable ^^: > http://www.di.unito.it/~mlienhar/vamos.pdf > In 2013, I designed and contributed to the implementation of a > dependency solver for dynamic cloud architecture (currently maintained > by Jacopo Mauro https://bitbucket.org/jacopomauro/zephyrus2/src ) > I'm a gentoo user since 2007, and I'm very happy by this opportunity > to contribute back :). > > > Thank you! > Michael Lienhardt > > > Michael, Posting here to alert other potential helpers. Your script uses PACKAGE_KEYWORDS="/etc/portage/package.accept_keywords" but thats a recent name change. PACKAGE_KEYWORDS="/etc/portage/package.keywords" is the old name and my older systems still use that. You probably need to harvest both and process both as portage does. -- Regards, Roy Bamford (Neddyseagoon) a member of elections gentoo-ops forum-mods pgpjZkguBNLdT.pgp Description: PGP signature
