From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 04:34:32 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 04:34:22 -0400 Received: from mail.alphalink.com.au ([203.24.205.7]:11014 "EHLO mail.alphalink.com.au") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 04:34:12 -0400 Message-ID: <3AF11A0D.FB206A2B@alphalink.com.au> Date: Thu, 03 May 2001 18:42:53 +1000 From: Greg Banks X-Mailer: Mozilla 4.07 [en] (X11; I; Linux 2.2.1 i586) MIME-Version: 1.0 To: esr@thyrsus.com CC: CML2 Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard In-Reply-To: <20010503034755.A27693@thyrsus.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Eric S. Raymond wrote: > I agree with the main thrust of your argument, but > It would be hard to know how to order your candidates to present > them to the user in a natural sequence -- and the problem of deciding > which variable to present for mutation by the user next, if you choose > that UI, equates to this. There is a natural order for presenting variables to the user, and that's the menu tree order. At least in the Linux kernel CML2 corpus the menus are roughly organised from most general to most specific options, so options appearing earlier in the tree are likely to appear in more constraints and you probably want to ask the user to mutate them later. Greg. -- If it's a choice between being a paranoid, hyper-suspicious global village idiot, or a gullible, mega-trusting sheep, I don't look good in mint sauce. - jd, slashdot, 11Feb2000. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 04:51:52 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 04:51:42 -0400 Received: from snark.tuxedo.org ([207.106.50.26]:1031 "EHLO snark.thyrsus.com") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 04:51:37 -0400 Date: Thu, 3 May 2001 04:52:22 -0400 From: "Eric S. Raymond" To: Greg Banks Cc: CML2 Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard Message-ID: <20010503045222.A28728@thyrsus.com> Reply-To: esr@thyrsus.com Mail-Followup-To: "Eric S. Raymond" , Greg Banks , CML2 In-Reply-To: <20010503034755.A27693@thyrsus.com> <3AF11A0D.FB206A2B@alphalink.com.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <3AF11A0D.FB206A2B@alphalink.com.au>; from gnb@alphalink.com.au on Thu, May 03, 2001 at 06:42:53PM +1000 Organization: Eric Conspiracy Secret Labs X-Eric-Conspiracy: There is no conspiracy Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Greg Banks : > There is a natural order for presenting variables to the > user, and that's the menu tree order. At least in the Linux > kernel CML2 corpus the menus are roughly organised from most > general to most specific options, so options appearing earlier > in the tree are likely to appear in more constraints and you > probably want to ask the user to mutate them later. OK. Agreed, but it doesn't solve the general problem. Generating models is still hard. -- Eric S. Raymond To make inexpensive guns impossible to get is to say that you're putting a money test on getting a gun. It's racism in its worst form. -- Roy Innis, president of the Congress of Racial Equality (CORE), 1988 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 06:16:00 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 06:15:41 -0400 Received: from ppp0.ocs.com.au ([203.34.97.3]:2058 "HELO mail.ocs.com.au") by vger.kernel.org with SMTP id ; Thu, 3 May 2001 06:15:34 -0400 X-Mailer: exmh version 2.1.1 10/15/1999 From: Keith Owens To: esr@thyrsus.com cc: CML2 , kbuild-devel@lists.sourceforge.net Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard In-Reply-To: Your message of "Thu, 03 May 2001 03:47:55 -0400." <20010503034755.A27693@thyrsus.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Thu, 03 May 2001 20:15:26 +1000 Message-ID: <15180.988884926@ocs3.ocs-net> Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 3 May 2001 03:47:55 -0400, "Eric S. Raymond" wrote: >OK, so you want CML2's "make oldconfig" to do something more graceful than >simply say "Foo! You violated this constraint! Go fix it!" (i) Start with a valid config. CML2 will not allow any changes that violate the constraints. Not a problem. (ii) Start with a invalid config. CML2 makes best effort at correcting it. (a) Interactive mode (menuconfig, xconfig) - tell the user to fix it. (b) Batch mode (oldconfig). Attempt to automatically correct the config using these rules. (1) Earlier constraints take priority over later constraints. That is, scan the constraints from top to bottom as listed by the rules. (2) For valid constraints, freeze all variables in the constraint, both guard and dependent. (3) For failing constraints, freeze the guard variables, change the dependent variable to satisfy the constraint then freeze it. (4) If a dependent variable is already frozen then give up, human intervention is required. This includes any variables that are changed as side effects of updating a dependent variable. (5) Backtracking is required between (4) and (3) if the dependent variables in (3) can take more than one value. For example with RTC!=n then set RTC=y, freeze it and try to complete the remaining constraints. If you cannot find a consistent set of values, unfreeze all variables from the later constraints, unfreeze RTC, set RTC=m, freeze and go forward again. >Worst-case you wind up having to filter 3^1976 or > >61886985104344314262549831301497223184442226760005632366142367454062\ >53798069007245829607511803014461980205195265648765807533359692422405\ >26663343478651948197640717559171334587246360190820597462466618699616\ >83769466038480440588536443139761873343981834731232898868121056624288\ >25175698197266097855144317654507849536499564272166336474891989097438\ >35187399533347347604275259693285565328638904436467418552386274533685\ >91327533953419273284845915678229675363862482902467758788105098892672\ >89040426968478652648633090613090819909922898996729964073665423236084\ >87819939319685920863027286269975666073166040062426792612975756185462\ >81534154977458915332736966975415596732075433912438120798023875787687\ >12139869442963906795755406077094024235937984546041146032870399467676\ >50750114775766120549985366981610796100249952621482595580440335923663\ >89536648507944663518188694691546583650254496327051865064380044199561\ >11898186436375597975714968012719658007155903874756222061921 bc is a wonderful tool :) Worst case with my algorithm is the product of the number of possible values that each dependent variable can take over all constraint rules. In the vast majority of cases, there is only one possible value, either because the constraint is already valid or because the dependency requires a single value. So the number of possible cases to test is governed by how many rules use != or < or > instead of ==. Is this perfect? No, you can construct pathological constraints that involve a lot of backtracking and even then there may be no valid set of values. Do we care? No, we do not write rules like that. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 12:59:06 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 12:58:56 -0400 Received: from snark.tuxedo.org ([207.106.50.26]:1801 "EHLO snark.thyrsus.com") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 12:58:46 -0400 Date: Thu, 3 May 2001 12:59:21 -0400 From: "Eric S. Raymond" To: Keith Owens Cc: CML2 , kbuild-devel@lists.sourceforge.net Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard Message-ID: <20010503125921.A347@thyrsus.com> Reply-To: esr@thyrsus.com Mail-Followup-To: "Eric S. Raymond" , Keith Owens , CML2 , kbuild-devel@lists.sourceforge.net In-Reply-To: <20010503034755.A27693@thyrsus.com> <15180.988884926@ocs3.ocs-net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <15180.988884926@ocs3.ocs-net>; from kaos@ocs.com.au on Thu, May 03, 2001 at 08:15:26PM +1000 Organization: Eric Conspiracy Secret Labs X-Eric-Conspiracy: There is no conspiracy Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Keith Owens : > On Thu, 3 May 2001 03:47:55 -0400, > "Eric S. Raymond" wrote: > >OK, so you want CML2's "make oldconfig" to do something more graceful than > >simply say "Foo! You violated this constraint! Go fix it!" > > (i) Start with a valid config. CML2 will not allow any changes that > violate the constraints. Not a problem. Right. This is 99.9% of cases. All this heat and argument is over a very, very unusual situation. Much more unusual than most of the people arguing about it realize. (For those of you haven't caught up with this, *missing symbols do not make a configuration invalid*. Only inconsistencies between explicitly set symbols can do that.) > (ii) Start with a invalid config. CML2 makes best effort at correcting > it. > > (a) Interactive mode (menuconfig, xconfig) - tell the user to fix > it. The problem with this is that in order to support it I have to throw away the configurator's central invariant -- which is that every change that does not lead to a valid configuration is rejected (with an explanation). I'm not going to do that. It's not worth it to handle a case this marginal. > (b) Batch mode (oldconfig). Attempt to automatically correct the > config using these rules. > > (1) Earlier constraints take priority over later constraints. > That is, scan the constraints from top to bottom as listed > by the rules. > > (2) For valid constraints, freeze all variables in the > constraint, both guard and dependent. > > (3) For failing constraints, freeze the guard variables, change > the dependent variable to satisfy the constraint then > freeze it. There's the problem. You don't know which variable(s) are dependent. That's not a well-defined notion here. Consider the case that stimulated this whole argument: (X86 and SMP) implies RTC!=n You think you know that RTC is 'dependent', but this is an illusion created by the presence of the asymmetrical `implies'. Go look at the hierarchy. You'll see what I mean. -- Eric S. Raymond Are we at last brought to such a humiliating and debasing degradation, that we cannot be trusted with arms for our own defence? Where is the difference between having our arms in our own possession and under our own direction, and having them under the management of Congress? If our defence be the *real* object of having those arms, in whose hands can they be trusted with more propriety, or equal safety to us, as in our own hands? -- Patrick Henry, speech of June 9 1788 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 13:45:32 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 13:45:22 -0400 Received: from router-100M.swansea.linux.org.uk ([194.168.151.17]:4104 "EHLO the-village.bc.nu") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 13:45:10 -0400 Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard To: esr@thyrsus.com Date: Thu, 3 May 2001 18:48:10 +0100 (BST) Cc: kaos@ocs.com.au (Keith Owens), linux-kernel@vger.kernel.org (CML2), kbuild-devel@lists.sourceforge.net In-Reply-To: <20010503125921.A347@thyrsus.com> from "Eric S. Raymond" at May 03, 2001 12:59:21 PM X-Mailer: ELM [version 2.5 PL1] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: From: Alan Cox Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org > (For those of you haven't caught up with this, *missing symbols do not > make a configuration invalid*. Only inconsistencies between explicitly > set symbols can do that.) If they make it invalid the tools should fix it. > > (ii) Start with a invalid config. CML2 makes best effort at correcting > > it. > > > > (a) Interactive mode (menuconfig, xconfig) - tell the user to fix > > it. > > The problem with this is that in order to support it I have to throw away the > configurator's central invariant -- which is that every change that does not > lead to a valid configuration is rejected (with an explanation). If you get a conflict, turn the second feature in config file order off/on as appropriate then tell the user you did it. Then continue to verify. If you accidentally turn off the whole scsi layer well the user has been told it happens and its still no worse than having no tool. While if it fixes it up happily the user is pleased and it saved a lot of time. Also remember many kernel builders are not gurus. CML2 already poses a huge barrier to such people because its different to the stuff in the book and the stuff their friend showed them. Thats a barrier worth climbing because its a better tool for such people in the longer run. But please don't add spikes on the top of said wall > I'm not going to do that. It's not worth it to handle a case this marginal. In which case CML2 appears to be inferior to our current tools. It depends on python2 which nobody ships by default yet. It doesn't handle this case. Why should we be using it ;) > There's the problem. You don't know which variable(s) are dependent. > That's not a well-defined notion here. Consider the case that stimulated > this whole argument: Actually I think the problem is different. You are trying to solve a mathematical graph theory problem elegantly. Make oldconfig solves a real world problem by a mixture of brutality and heuristics. Alan PS: your .sig length checker still seems broken From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 14:30:44 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 14:30:35 -0400 Received: from snark.tuxedo.org ([207.106.50.26]:26889 "EHLO snark.thyrsus.com") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 14:30:16 -0400 Date: Thu, 3 May 2001 14:30:37 -0400 From: "Eric S. Raymond" To: Alan Cox Cc: Keith Owens , CML2 , kbuild-devel@lists.sourceforge.net Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard Message-ID: <20010503143037.A1822@thyrsus.com> Reply-To: esr@thyrsus.com Mail-Followup-To: "Eric S. Raymond" , Alan Cox , Keith Owens , CML2 , kbuild-devel@lists.sourceforge.net In-Reply-To: <20010503125921.A347@thyrsus.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: ; from alan@lxorguk.ukuu.org.uk on Thu, May 03, 2001 at 06:48:10PM +0100 Organization: Eric Conspiracy Secret Labs X-Eric-Conspiracy: There is no conspiracy Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Alan Cox : > If you get a conflict, turn the second feature in config file order off/on > as appropriate then tell the user you did it. Then continue to verify. > Actually I think the problem is different. You are trying to solve a > mathematical graph theory problem elegantly. Make oldconfig solves a real > world problem by a mixture of brutality and heuristics. You want brutality and heuristics? I'll give you brutality and heuristics... I could just treat a config as a sequence of assignments, as though the user had typed them in sequence, rejecting any later ones that throw constraint violations. That way we can avoid ever accepting or having to deal with an invalid configuration. The invariant that every symbol assignment either augments a valid configuration or is rejected would be conserved. This isn't "recovery", it's more like high-handedly throwing away assignments that don't happen to fit stuff bound earlier in the tree traverse that defines symbol print order. And it's going to give odd, "brutal" results in some cases because guard symbols are ordered before their dependents. But if all you want is brutality and heuristics, it might do. I guess you didn't know that I trained as a mathematical logician. On the one hand, that predisposes me to try to find "elegant" solutions where you might regard brutality and heuristics as more appropriate. On the other hand, without that kind of background you don't get people building constraint-satisfaction systems to give you provably-correct results, either. So perhaps, on the whole, mine is a more positive predisposition than not ;-). -- Eric S. Raymond Men trained in arms from their infancy, and animated by the love of liberty, will afford neither a cheap or easy conquest. -- From the Declaration of the Continental Congress, July 1775. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 14:38:54 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 14:38:45 -0400 Received: from router-100M.swansea.linux.org.uk ([194.168.151.17]:32264 "EHLO the-village.bc.nu") by vger.kernel.org with ESMTP id ; Thu, 3 May 2001 14:38:31 -0400 Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard To: esr@thyrsus.com Date: Thu, 3 May 2001 19:41:33 +0100 (BST) Cc: alan@lxorguk.ukuu.org.uk (Alan Cox), kaos@ocs.com.au (Keith Owens), linux-kernel@vger.kernel.org (CML2), kbuild-devel@lists.sourceforge.net In-Reply-To: <20010503143037.A1822@thyrsus.com> from "Eric S. Raymond" at May 03, 2001 02:30:37 PM X-Mailer: ELM [version 2.5 PL1] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: From: Alan Cox Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org > You want brutality and heuristics? I'll give you brutality and heuristics... > I could just treat a config as a sequence of assignments, as though > the user had typed them in sequence, rejecting any later ones that > throw constraint violations. That way we can avoid ever accepting or > having to deal with an invalid configuration. The invariant that every > symbol assignment either augments a valid configuration or is rejected > would be conserved. Which is pretty much what make oldconfig does. Go from the top asking users about new symbols and just killing stuff that would break the rules. > This isn't "recovery", it's more like high-handedly throwing away > assignments that don't happen to fit stuff bound earlier in the tree > traverse that defines symbol print order. And it's going to give odd, > "brutal" results in some cases because guard symbols are ordered > before their dependents. Thats the mathematician speaking again > But if all you want is brutality and heuristics, it might do. Its worked well enough for the past five years. On odd occasions you do find you've inadventantly unconfigured something but normally the conflict vanishes with almost no ripples. I'm quite happy for oldconfig to continue to do what it did before. I'm quite happy to accept its mathematically imperfect, because it hasnt gone far wrong yet Alan From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 15:32:52 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 15:32:38 -0400 Received: from smtpnotes.altec.com ([209.149.164.10]:52752 "HELO smtpnotes.altec.com") by vger.kernel.org with SMTP id ; Thu, 3 May 2001 15:30:59 -0400 X-Lotus-FromDomain: ALTEC From: Wayne.Brown@altec.com To: Alan Cox cc: esr@thyrsus.com, alan@lxorguk.ukuu.org.uk (Alan Cox), kaos@ocs.com.au (Keith Owens), linux-kernel@vger.kernel.org (CML2), kbuild-devel@lists.sourceforge.net Message-ID: <86256A41.006B2177.00@smtpnotes.altec.com> Date: Thu, 3 May 2001 14:30:14 -0500 Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard Mime-Version: 1.0 Content-type: text/plain; charset=us-ascii Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Alan Cox wrote: >Its worked well enough for the past five years. On odd occasions you do find >you've inadventantly unconfigured something but normally the conflict vanishes >with almost no ripples. >I'm quite happy for oldconfig to continue to do what it did before. I'm quite >happy to accept its mathematically imperfect, because it hasnt gone far wrong >yet Here's a real-life example of how well it works. I tend to bounce back and forth between Linus' -pre patches and your -ac patches. For instance, when 2.4.4-ac4 came out, I was running 2.4.5-pre1. Here's what I did: zcat patch-2.4.5-pre1.gz | patch -p1 -s -E -R zcat patch-2.4.4-ac4.gz | patch -p1 -s -E mv .config .. make mrproper mv ../.config . make oldconfig make dep && make bzlilo modules modules_install I apply nearly every patch set that comes along from you or Linus, and this is the way I usually do it. Every once in a while, I run through all the options in menuconfig just to make certain nothing has gotten hosed up. Only once can I remember needing to change an option that had been set incorrectly by oldconfig. Wayne From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 3 May 2001 18:59:32 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 3 May 2001 18:59:12 -0400 Received: from ppp0.ocs.com.au ([203.34.97.3]:55824 "HELO mail.ocs.com.au") by vger.kernel.org with SMTP id ; Thu, 3 May 2001 18:59:04 -0400 X-Mailer: exmh version 2.1.1 10/15/1999 From: Keith Owens To: esr@thyrsus.com cc: CML2 , kbuild-devel@lists.sourceforge.net Subject: Re: [kbuild-devel] Why recovering from broken configs is too hard In-Reply-To: Your message of "Thu, 03 May 2001 12:59:21 -0400." <20010503125921.A347@thyrsus.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 04 May 2001 08:58:58 +1000 Message-ID: <22710.988930738@ocs3.ocs-net> Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 3 May 2001 12:59:21 -0400, "Eric S. Raymond" wrote: >Keith Owens : >> (3) For failing constraints, freeze the guard variables, change >> the dependent variable to satisfy the constraint then >> freeze it. > >There's the problem. You don't know which variable(s) are dependent. >That's not a well-defined notion here. Consider the case that stimulated >this whole argument: > > (X86 and SMP) implies RTC!=n > >You think you know that RTC is 'dependent', but this is an illusion created >by the presence of the asymmetrical `implies'. Go look at the hierarchy. >You'll see what I mean. On the contrary, I know what the hierarchy says and I also know that that implies is normally bidirectional. In the case of batch mode, where you cannot ask the user to solve the violation, I suggest that CML2 treat implies as unidirectional, but only for this case. IOW, the order of the constraints (not the hierarchy) and the ordering of the guard and dependent variables in each constraint are hints by the rules writer to CML2 about which variables are more important. Earlier constraints are more important than later ones. Guard variables are more important that dependent variables. So when CML2 reaches the end of a batch config run and has a violation on 'require X86 and SMP implies RTC!=n', X86 and SMP will not be considered for changing, RTC will be. Using hints from the order of the constraints reduces the solution space from 3^1957 to 2.