Re: [Fink-devel] On dependency engines
On Thursday, January 30, 2003, at 07:01 pm, Max Horn wrote: So, for now, instead of charging ahead and trying to write a new dependency engine from scratch or trying to retrofit an existing one, I went to try to write down what our needs are. Then based on this, I started to develop ideas on how to realize these needs in actual code. I try to present all my ideas and findings in this email. That includes a list of problematic cases the engine needs to handle, as well as fundamental problems, and problems that are also affecting our current system. It'll be a long email, and maybe I should put it on a web page later, too. Why dependency deciding is difficult Life would be easy if a dependency would just say "install foo", and there was exactly one foo. However, foo may exist in 5 A feature that would be nice to have which Fink currently does not handle dynamically, when deciding on package dependencies the engine would also consider whether to download/install any binary debs when available, and compile the rest which are not available in deb archives. I'll also explain the chroot/fakeroot approach for package building and how it would help us in many many ways (at the cost of more time/disk space, though). This is an obvious question, but does a fakeroot jail mean duplicating files of any required dependencies into a sandbox(jail) during the build phase? So, wouldn't hard links eliminate any additional disk-space penalty? Carsten --- This SF.NET email is sponsored by: FREE SSL Guide from Thawte are you planning your Web Server Security? Click here to get a FREE Thawte SSL guide and find the answers to all your SSL security issues. http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0026en ___ Fink-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/fink-devel
Re: [Fink-devel] On dependency engines
OK, my promised second mail will have to wait till tomorrow. I just got home after spending 8 hours in my car, 4 of those standing in one spot on the highway, at -2 degree celsius with no car heating (highway was blocked for hours due to a crash). I really don't feel like anything but sleep right now. Max --- This SF.NET email is sponsored by: SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! http://www.vasoftware.com ___ Fink-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/fink-devel
Re: [Fink-devel] On dependency engines
Hmm, I might be able to do some of that... I know enough PPC assembler to do __asm__ statements inside C, but not enough to write whole functions (don't know how to do stack frames). I am learning it already. Found some pretty good information on it. Things like linked lists, btrees and other stuff can be done even smarter by human asm than compiler produced asm due tot he fact that you know which operation to especially accelerate, the compiler will most likely try to optimise the operation as a whole. Depends on what we will actually be doing but if we really start using some sort of queuing, btrees, ntrees or large linked lists might come into play. Although my method for optimizing KDE and XFree86 seems to work... read the gcc3 man page and use all the compiler flags that look good > :) hehe -d - Face me and you shall surely perish. --- This SF.NET email is sponsored by: SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! http://www.vasoftware.com ___ Fink-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/fink-devel
Re: [Fink-devel] On dependency engines
On Friday, January 31, 2003, at 07:24 AM, David wrote: oh yes please.. C baby ;) Maybe I can start optimising some of the linking and calculating and node moving in asm *drool* -d :) - Face me and you shall surely perish. Hmm, I might be able to do some of that... I know enough PPC assembler to do __asm__ statements inside C, but not enough to write whole functions (don't know how to do stack frames). Although my method for optimizing KDE and XFree86 seems to work... read the gcc3 man page and use all the compiler flags that look good :) --- This SF.NET email is sponsored by: SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! http://www.vasoftware.com ___ Fink-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/fink-devel
Re: [Fink-devel] On dependency engines
Never got the hang of Wiki's, but if you want to isntall one, why not. Well I do not use them either, but I thought they would be suited. But then again.. who cares Luckily in many cases one can use a "BuildDepends" instead of a "BuildConflict". But adding this ensures our system is fully orthogonal and really doesn't cost us anything. Thank you, now I get it. I don't think that will work, unless you modify dpkg and apt-get to use them, too. The only way I see (and which I briefly mentioned in my original post) is to make fink use the same locking mechanism as those two, but it's not fine grained at all, and at least to me would be a serious limitation. It would prevent me from doing e.g. a "fink install figlet" while my "fink install bundle-kde" is running. Yes, I tend to forget, that we have to work with apt/dpkg as well. Anyway, the "chroot jail" approach that I'll explain in the next full email covers this rather nicely without the need of any locks. chrooting is indeed a choice which seems feasible, yet as you already mentioned this might increase HD use in an exponential way, especially when we start allowing parallel builds in a way that it is safe to use them. But while you already mention parallelism, I also made my thoughts about this. The "objective optimizer" I talked about could also be made clever enough to distribute objectivies onto multiple processes (or even machines in the distant future :-). Like it could detect that we are on a two processor machine, and in that case spaw multiple subproceses and then try to keep them saturated with building packages. Of course that still has the same problems it used to have (like, we can't just print the output to the terminal anymore, or we'd get a big mess), but at least with the new approach it would be possible to do this. Which is important, since the new system would also easily allow a "fink build-all" (Justin, your dream come true, eh? :-) I agree. I do see some problems though because locking is a real issue then. Unless the system is able to distribute multiple "objects" across multiple "jails" while still keeping the build coherent. This might be doable one day, but I would not want to do this at the beginning. We can keep it in mind, but right now I think it would complicate the system. It's already difficult enough to get this all done, so let's postpone that for a later version. as I said, it was merely a question, keeping this in mind then. >learn that (thank god I have Randall's book and the Perl book, too... at home, 400 km away :-). The part of Fink which deals with "structs" But you have the author much closer... right here.. on the list (just kidding, sorry Mr. Schwartz) and linked list etc. is after all the single most complicated part of Fink. I am just more home in C/C++/Java/... so I might scribble down (non working) designs in one of these languages. Or maybe I just use pseudo code :-) oh yes please.. C baby ;) Maybe I can start optimising some of the linking and calculating and node moving in asm *drool* -d :) - Face me and you shall surely perish. --- This SF.NET email is sponsored by: SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! http://www.vasoftware.com ___ Fink-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/fink-devel
Re: [Fink-devel] On dependency engines
At 12:50 Uhr +0100 31.01.2003, David wrote: On Freitag, J§nner 31, 2003, at 01:01 Uhr, Max Horn wrote: [...] I think that it would be an excellent idea to use something like a Wiki. If you want I can install such a system on one of the boxen I have authority over. Never got the hang of Wiki's, but if you want to isntall one, why not. Basic needs and issues == First off: the engine needs to deal with 4 basic types of dependency: * build conflicts I never quite understood what a build conflict is. Maybe you could point me toward and example? For example sdl-ttf which can be installed parallel to freetype 1.x, but if you build it while freetype 1.x is installed, it'll fail. Luckily in many cases one can use a "BuildDepends" instead of a "BuildConflict". But adding this ensures our system is fully orthogonal and really doesn't cost us anything. * build dependencies * install conflicts * install dependencies Note that the current "Depends" field in fink in fact represent both a build time *and* a install time dependency; in a future fink package manager release, we will hence add new fields InstallDepends and InstallConflicts (names subject to change); this will increase the flexibility w/o adding any complexity. So an install dependency is something like a run dependency in FreeBSD? Those packages would list other packages which need to be present prior to installing the package because: a) it needs them to install properly (because it uses tetex to generate doc during install) b) it needs them to run properly afterwards You a) is our build dependency, and b) is an install (or "runtime" as I used to call it) dependency. It's debatable which term ("install" or "runtime") is better suited, IMHO none is quite correct. [...] I would like to suggest the following addition then. I have been working for many years in areas where parallel processing was able to mess with data structures. Would it be possible to implement a "locking" mechanism within fink? Take your example. If a package starts at time X and needs package DFG to build those packages will be locked exclusively to that build process. If you run fink at time Y while teh first build is still in progress, the packages DFG will still be locked and thus they cannot be altered or removed. Of course I am referring to special locks. I don't think that will work, unless you modify dpkg and apt-get to use them, too. The only way I see (and which I briefly mentioned in my original post) is to make fink use the same locking mechanism as those two, but it's not fine grained at all, and at least to me would be a serious limitation. It would prevent me from doing e.g. a "fink install figlet" while my "fink install bundle-kde" is running. Anyway, the "chroot jail" approach that I'll explain in the next full email covers this rather nicely without the need of any locks. But while you already mention parallelism, I also made my thoughts about this. The "objective optimizer" I talked about could also be made clever enough to distribute objectivies onto multiple processes (or even machines in the distant future :-). Like it could detect that we are on a two processor machine, and in that case spaw multiple subproceses and then try to keep them saturated with building packages. Of course that still has the same problems it used to have (like, we can't just print the output to the terminal anymore, or we'd get a big mess), but at least with the new approach it would be possible to do this. Which is important, since the new system would also easily allow a "fink build-all" (Justin, your dream come true, eh? :-) [...] This can lead to three cases: 1) we can find one version of "foo" that leads to no issues 2) we can find more than possibility What happens when we find more than one choice and one of the choices is not available? For example the download fails. Now one choice only requires XXX as dependency. The other choice requires XXXYY and that might force a recalculation and a new queue which needs to be calculated. Does the system do something like: You could either install X or Y you chose Y but it is not available, shall I install X and recalculate the dependencies? This might be doable one day, but I would not want to do this at the beginning. We can keep it in mind, but right now I think it would complicate the system. It's already difficult enough to get this all done, so let's postpone that for a later version. Ignore my rambling if I am talking bullshit, I am just getting the hang of this and how it is being handled. I simply feel, that it is important to let go of all the ideas which might swirl in my head, no matter if they make sense at the first attempt. Yup yup, you are most welcome to do so! I think your ideas all made sense. Now for anybody who got this far reading, my second email will probably be coming this evening/night. And I slowly start to think maybe I can even start w
Re: [Fink-devel] On dependency engines
On Freitag, Jänner 31, 2003, at 01:01 Uhr, Max Horn wrote: Hi folks, Hello Max. For some time, I hoped we might be able to just reuse the apt engine (and the hope is still not completely gone), but as far as I can tell it can't cope with build time only dependencies (but there is the possibility to work around that, see below). If somebody is interested to look into this (that means you have to know C++, and ideally also the apt sources, or are willing to work into it), feel free to contact me. I do not know nor do I like C++, but since I am rather grown up with my C, I am sure I can push the OO syntax into the back of my brain quick enough. However if we write something new, can't I be the wizard if C ? *grins* So, for now, instead of charging ahead and trying to write a new dependency engine from scratch or trying to retrofit an existing one, I went to try to write down what our needs are. Then based on this, I started to develop ideas on how to realize these needs in actual code. I try to present all my ideas and findings in this email. That includes a list of problematic cases the engine needs to handle, as well as fundamental problems, and problems that are also affecting our current system. It'll be a long email, and maybe I should put it on a web page later, too. I think that it would be an excellent idea to use something like a Wiki. If you want I can install such a system on one of the boxen I have authority over. Basic needs and issues == First off: the engine needs to deal with 4 basic types of dependency: * build conflicts I never quite understood what a build conflict is. Maybe you could point me toward and example? * build dependencies * install conflicts * install dependencies Note that the current "Depends" field in fink in fact represent both a build time *and* a install time dependency; in a future fink package manager release, we will hence add new fields InstallDepends and InstallConflicts (names subject to change); this will increase the flexibility w/o adding any complexity. So an install dependency is something like a run dependency in FreeBSD? Those packages would list other packages which need to be present prior to installing the package because: a) it needs them to install properly (because it uses tetex to generate doc during install) b) it needs them to run properly afterwards Another trouble area are build time dependencies, and build time in general. Right now, fink installs build time dependencies if needed, but doesn't remove them later (which might or might not be the right approach, you can argue either way). We don't handle build conflicts at all. Also, there issues when users run multiple fink's at once (I do that frequently - no need to interrupt KDE building if I just want to quickly install figlet). Right now, this can easily lead to screw up. Just imagine openssh is building and the user removes the openssl package. Ouch, either the build fails, or gets messed because the openssh build now starts using Apple's openssl - just imagine if the version of openssl differ, then half of openssh is linked against openssl 0.9.7, the other against 0.9.6 - ouch). dpkg doesn't (and can't) handle build time dependencies at all. Fink should do that, but right now it does a very poor job at it. apt only handles them in a very limited way (for the apt-get source command), not sufficient for our needs. I would like to suggest the following addition then. I have been working for many years in areas where parallel processing was able to mess with data structures. Would it be possible to implement a "locking" mechanism within fink? Take your example. If a package starts at time X and needs package DFG to build those packages will be locked exclusively to that build process. If you run fink at time Y while teh first build is still in progress, the packages DFG will still be locked and thus they cannot be altered or removed. Of course I am referring to special locks. Let us assume this. a) a remove lock (packages which are locked that way cannot be removed until the lock has been released) Now that means we either queue the release passively or the package is being removed actively by the locking build b) insert your idea here .. Ideas & Solutions = I developed various ideas on how to tackle the problems above and other problems I encountered while researching this. Note that I am still not finished yet with all this (one of the reason for me to finally write this down was to get my thoughts ordered, it's easy to get lost :-). And basically, this assumes we use write own engine... rock on.. yes.. This can lead to three cases: 1) we can find one version of "foo" that leads to no issues 2) we can find more than possibility What happens when we find more than one choice and one of the choices is not available? For example the download fails. Now one c
[Fink-devel] On dependency engines
Hi folks, in the recent months, the problems with Fink's dependency engine (and dpkg's, and the way they interact) have become more and more apparent. Various problems are basically impossible to overcome with the current design, hence it seems we need a new full fledged dependency engine. For some time, I hoped we might be able to just reuse the apt engine (and the hope is still not completely gone), but as far as I can tell it can't cope with build time only dependencies (but there is the possibility to work around that, see below). If somebody is interested to look into this (that means you have to know C++, and ideally also the apt sources, or are willing to work into it), feel free to contact me. So, for now, instead of charging ahead and trying to write a new dependency engine from scratch or trying to retrofit an existing one, I went to try to write down what our needs are. Then based on this, I started to develop ideas on how to realize these needs in actual code. I try to present all my ideas and findings in this email. That includes a list of problematic cases the engine needs to handle, as well as fundamental problems, and problems that are also affecting our current system. It'll be a long email, and maybe I should put it on a web page later, too. Basic needs and issues == First off: the engine needs to deal with 4 basic types of dependency: * build conflicts * build dependencies * install conflicts * install dependencies Note that the current "Depends" field in fink in fact represent both a build time *and* a install time dependency; in a future fink package manager release, we will hence add new fields InstallDepends and InstallConflicts (names subject to change); this will increase the flexibility w/o adding any complexity. Due to the way fink works, it's hard to use dpkg's engine properly; e.g. fink "knows" it'll install all requirements for a package, but dpkg will not know that unless we install them all at the same time. There are more many scenarios where install/remove fails because fink "knows more" than dpkg. The only way to overcome this is to use "--force-depends" at least for some operations. But if we do that, we *have* to handle all dependency issues manually (be it with a complete new engine or with an existing engine, it doesn't matter). Right now fink gets off cheap as it relies on the dpkg engine to remove conflicting packages automatically, or to refuse to remove a package which is still needed. If we override this, we have to do it ourselves, increasing the complexity. Another trouble area are build time dependencies, and build time in general. Right now, fink installs build time dependencies if needed, but doesn't remove them later (which might or might not be the right approach, you can argue either way). We don't handle build conflicts at all. Also, there issues when users run multiple fink's at once (I do that frequently - no need to interrupt KDE building if I just want to quickly install figlet). Right now, this can easily lead to screw up. Just imagine openssh is building and the user removes the openssl package. Ouch, either the build fails, or gets messed because the openssh build now starts using Apple's openssl - just imagine if the version of openssl differ, then half of openssh is linked against openssl 0.9.7, the other against 0.9.6 - ouch). dpkg doesn't (and can't) handle build time dependencies at all. Fink should do that, but right now it does a very poor job at it. apt only handles them in a very limited way (for the apt-get source command), not sufficient for our needs. Ideas & Solutions = I developed various ideas on how to tackle the problems above and other problems I encountered while researching this. Note that I am still not finished yet with all this (one of the reason for me to finally write this down was to get my thoughts ordered, it's easy to get lost :-). And basically, this assumes we use write own engine... Note: when I say deps (=dependencies) in the following, I usually also mean conflicts, which are also a kind of (anti)dependencies. You can view the net of packages as a graph, the packages are nodes, the (anti)dependencies are directed edges. It's actually a bit more complicated, a package can consist of many version (PkgVersion in fink), and a dependency can specify version ranges. But the idea should be clear. First, I tried to split down the problems in small units. This makes reasoning easier. For example, some of the problems we used to have in the (limited) fink dep code was caused by the fact that the "Depends" field actually has a blurred meaning and is *not* the same as the dpkg "Depends" - because it also covers build time. Realizing this and getting it straight helped a lot. Continuing this, the difference between build & install time deps. Fink can either "install" or "build" or "build & install" a package. So i