Why recovering from broken configs is too hard
OK, so you want CML2's "make oldconfig" to do something more graceful than simply say "Foo! You violated this constraint! Go fix it!"
Let's start by formulating the general problem. We'll simplify it by ignoring the existence of string- and numeric-valued symbols and talk only about tristates. We have an old configuration which is broken; that is, it's a set of symbol bindings that violates one of the rule predicates.
Note that by a "configuration" I don't mean just a set of three bindings like {X86=y, SMP=y, RTC=n}. I mean an *entire* configuration of (at last count) 1976 settable options. Many are linked by constraints in complex ways (there are constraints in the Linux ruleset involving twelve or more symbols). Thus you can't consider the variables in the broken constraint(s) in isolation from the others.
What you know, to start with, is (a) the configuration, (b) the constraints, (c) the shape of the menu tree, and (d) which constraints have failed. What you want to do is find a set of corrected configurations which fulfill all constraints and are in some sense "close" to the broken one you have.
Ideally, the corrected configurations will only require you to change symbols already occurring in the broken constraints. But in any case, once you have your list of known-good configurations, you intend to prompt the user to select one of them.
First problem: you don't know how to find *any* correct configuration. from the information you have. That's because you don't know in advance what side-effects flipping the symbols in the broken constraints will have -- every time you flip a symbol, other constraints may force variables that are arbitrarily far away.
Computer scientists call this the "satisfaction problem" -- given a set of constraints, generate a "model" (set of variable bindings) that satisfies them.
The obvious thing to try is to start with the configuration you have and try mutating the variables that occur in the broken constraint(s). Of course, there are 3^n of these where n is the number of distinct variables, so this is going to blow up really fast; 3, 9, 27, 81, 243 and we ain't even to six symbols yet. By the time we get to the twelve variables that could be linked by just *one* constraint, there are 531,441. Even if you can check 500 configurations a second it's going to take 16 minutes just to get a candidate list.
But wait! There's more! If some of the variables participate in multiple constraints, the numbers get *really* large. 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
distinct configurations. The heat-death of the Universe happens while you're still crunching.
Obviously this is a stupid, brute-force, doomed approach. Can we be smarter by using the structure of the constraints to narrow the configuration search space? Well, sort of.
The best-known algorithm for this is called SATO, I give a reference for it in my paper. It's (a) complicated, (b) expensive, and (c) slow, but it's there.
The good news is that we could use SATO to crank out some model that will satisfy the constraints (we know there is at least one because my ruleset compiler won't compile a set of defaults that is invalid). The bad news is that there's no way to make it generate a model that's "close" to our broken one!
There's a third way. The cheap, dirty attack on the satisfaction problem is to use what's called a "stochastic" or "hill-climbing" algorithm. It's a less ambitious version of the brute-force search that essentially random-walks through the configuration space looking for valid ones.
The problem with stochastic search is that (a) it's not guaranteed to find a model even if models exist, and (b) you can't predict its running time. Oops...
Even assuming we could generate large numbers of candidate models quickly, I've been putting the word "close" in quotes because there's another nasty problem lurking here. "Close" is not well-defined in this space.
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.
Have I got the point across yet? There are *no* good solutions to this problem. There aren't even any clean ways to separate easy cases from hard ones.
Signature · 11 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
The conclusion is thus inescapable that the history, concept, and
wording of the second amendment to the Constitution of the United
States, as well as its interpretation by every major commentator and
court in the first half-century after its ratification, indicates
that what is protected is an individual right of a private citizen
to own and carry firearms in a peaceful manner.
-- Report of the Subcommittee On The Constitution of the Committee On
The Judiciary, United States Senate, 97th Congress, second session
(February, 1982), SuDoc# Y4.J 89/2: Ar 5/5Quoted 2 lines · Eric S. Raymond
OK, so you want CML2's "make oldconfig" to do something more graceful than simply say "Foo! You violated this constraint! Go fix it!"
[...]
Quoted 3 lines
Have I got the point across yet? There are *no* good solutions to this problem. There aren't even any clean ways to separate easy cases from hard ones.
No good solutions? Then how come I use "make oldconfig" every day...
Are we to assume from your long missive that you are turning the possible into the impossible? :)
IMHO "make oldconfig" must stay.
Signature · 3 lines
Jeff Garzik | Game called on account of naked chick Building 1024 | MandrakeSoft |
Jeff Garzik <[email protected]>:
Quoted 9 lines
Quoted 2 lines · Eric S. Raymond
OK, so you want CML2's "make oldconfig" to do something more graceful than simply say "Foo! You violated this constraint! Go fix it!"
[...]
Quoted 3 lines
Have I got the point across yet? There are *no* good solutions to this problem. There aren't even any clean ways to separate easy cases from hard ones.
No good solutions? Then how come I use "make oldconfig" every day...
You fix broken configs by hand. That's what you'll do in the new system, too.
Quoted 1 line
IMHO "make oldconfig" must stay.
There was never any risk it would go away.
Signature · 3 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a> Everything you know is wrong. But some of it is a useful first approximation.
Quoted 9 lines · Eric S. Raymond
The obvious thing to try is to start with the configuration you have and try mutating the variables that occur in the broken constraint(s). Of course, there are 3^n of these where n is the number of distinct variables, so this is going to blow up really fast; 3, 9, 27, 81, 243 and we ain't even to six symbols yet. By the time we get to the twelve variables that could be linked by just *one* constraint, there are 531,441. Even if you can check 500 configurations a second it's going to take 16 minutes just to get a candidate list.
Quoted 3 lines
But wait! There's more! If some of the variables participate in multiple constraints, the numbers get *really* large. Worst-case you wind up having to filter 3^1976 or
<DSW>
I see your 3^1976 and raise "unsolvable". It's a special case of termination problem, dontcha see.
</DSW>
Yes, generic problem is damn hard. The thing being, _this_ problem is damn far from generic.
Quoted 1 line · Eric S. Raymond
I agree with the main thrust of your argument, but
Quoted 4 lines
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.
Signature · 3 lines
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.
Quoted 2 lines · Eric S. Raymond
OK, so you want CML2's "make oldconfig" to do something more graceful than simply say "Foo! You violated this constraint! Go fix it!"
Yes, that would be nice.
Quoted 2 lines
The obvious thing to try is to start with the configuration you have and try mutating the variables that occur in the broken constraint(s).
No, that is not the obvious way for me.
Quoted 3 lines
Have I got the point across yet? There are *no* good solutions to this problem. There aren't even any clean ways to separate easy cases from hard ones.
There might be.
If the current dependencies of the symbols can be represented as a tree (or can be topologically sorted, to be CS-correct), then I would only care about the "leaves" of that tree.
Most added symbols in newer configs are added as leaves. So this should suffice in most situations.
We also have defaults for all new values in our arch/$ARCH/defconfig.
So we read all symbols from .config and from defconfig into 2 flat tables (no constraints applied here!) together with their values.
If we miss a symbol from .config, we ask the user, using the one from defconfig as default, if we cannot derive its value from our constraints.
If we have a symbol in .config, that we don't know about, we simply ignore it (and tell the user that it's "obsolete or renamed").
If the value for a symbol is there, but doesn't fit our
constraints: Ask the user or use the opposite (if it is boolean).
That was the 99% case: "leaves". They are easy.
Now the nodes. We can try fixing the config by changing the symbols from leaves, to root (to save derives).
But we only give this solution a certain amount of "tries" and give up (or tell the user, that we have a hard time here and aks for continue or abort and fixing by hand), if we either tried to often or a certain amount of time has passed (30secs maximum until next prompt).
This is no "perfect" solution, but it covers the common cases well enough.
Eric, what do you think about that "dirty hack" variant? ;-)
And will the derivation be in nearly constant time, if I change one symbol?
Regards
Ingo Oeser
Signature · 2 lines
10.+11.03.2001 - 3. Chemnitzer LinuxTag <http://www.tu-chemnitz.de/linux/tag>
<<<<<<<<<<<< been there and had much fun >>>>>>>>>>>>Quoted 5 lines · Ingo Oeser
But we only give this solution a certain amount of "tries" and give up (or tell the user, that we have a hard time here and aks for continue or abort and fixing by hand), if we either tried to often or a certain amount of time has passed (30secs maximum until next prompt).
Actually, I suspect that problem is much easier than Eric had described it.
Assertion: you can split the set of variables into disjoint union of small subsets X, Y_1,...,Y_m such that each constraint is concerned only with variables from X and at most one of Y_i.
IOW, there is a small "core" and for fixed values of core variables constraints fall into groups, each dealing with its own _small_ set of variables.
If that assertion is true the complexity is nowhere near 3^N.
Eric, you probably have the most accurate information about the existing constraints. Care to verify the assertion above? I'm serious - the set of constraints is very far from generic and if nothing else, such preprocessing (splitting variables into core and peripherial groups) can make life easier in other parts of the thing.
Alexander Viro <[email protected]>:
Quoted 8 lines
Assertion: you can split the set of variables into disjoint union of small subsets X, Y_1,...,Y_m such that each constraint is concerned only with variables from X and at most one of
Y_i.IOW, there is a small "core" and for fixed values of core variables constraints fall into groups, each dealing with its own _small_ set of variables.
Quoted 8 lines
If that assertion is true the complexity is nowhere near 3^N.
Eric, you probably have the most accurate information about the existing constraints. Care to verify the assertion above? I'm serious - the set of constraints is very far from generic and if nothing else, such preprocessing (splitting variables into core and peripherial groups) can make life easier in other parts of the thing.
You're almost right. If you counted only explicit constraints, created by require statements, you get a bunch of cliques that aren't that large.
Unfortunately....there are a huge bunch of implicit constraints created by dependency relationships in the menu tree. For example, all SCSI cards are dependents of the SCSI symbol. Set SCSI to N and all the card symbols get turned off; set any card symbol to Y or M and the value of SCSI goes to Y or M correspondingly.
So the way it actually works (I think; I've have to write code to do a topological analysis to be sure) out is that there's sort of a light dust of atoms (BSD quota is one of them) surrounding one huge gnarly menu-tree-shaped clique.
Signature · 6 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
Strict gun laws are about as effective as strict drug laws...It pains
me to say this, but the NRA seems to be right: The cities and states
that have the toughest gun laws have the most murder and mayhem.
-- Mike Royko, Chicago TribuneQuoted 5 lines
Unfortunately....there are a huge bunch of implicit constraints created by dependency relationships in the menu tree. For example, all SCSI cards are dependents of the SCSI symbol. Set SCSI to N and all the card symbols get turned off; set any card symbol to Y or M and the value of SCSI goes to Y or M correspondingly.
For any given option you have a tree of options that tell you what to change. This means you can allow the user to set any conflicting variable either way and ripple the changes into the tree then start again
For real world cases that will terminate pretty fast.
Alan
Quoted 10 lines · Eric S. Raymond
You're almost right. If you counted only explicit constraints, created by require statements, you get a bunch of cliques that aren't that large.
Unfortunately....there are a huge bunch of implicit constraints created by dependency relationships in the menu tree. For example, all SCSI cards are dependents of the SCSI symbol. Set SCSI to N and all the card symbols get turned off; set any card symbol to Y or M and the value of SCSI goes to Y or M correspondingly.
Quoted 4 lines
So the way it actually works (I think; I've have to write code to do a topological analysis to be sure) out is that there's sort of a light dust of atoms (BSD quota is one of them) surrounding one huge gnarly menu-tree-shaped clique.
Errrmmm... _That_ is not too horrible - e.g. SCSI definitely belongs to core. Individual drivers, OTOH, do not and there's a lot of them.
I'm not talking about connectedness of the thing. However, I suspect that graph has a small subset such that removing it makes it fall apart.
IOW, you have a small well-connected backbone and a lot of small groups around it, such that each path from one group to another hits the backbone. ACK? Picture you've described doesn't contradict that - there's a relatively small number of symbols that correspond to subsystems and tons of stuff hanging from that subset.
Look at it as a network. How many sites do you need to nuke to break it into tiny bits?
Alexander Viro <[email protected]>:
Quoted 2 lines
I'm not talking about connectedness of the thing. However, I suspect that graph has a small subset such that removing it makes it fall apart.
Um. So how does that help?
Signature · 7 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
The most foolish mistake we could possibly make would be to permit
the conquered Eastern peoples to have arms. History teaches that all
conquerors who have allowed their subject races to carry arms have
prepared their own downfall by doing so.
-- Hitler, April 11 1942, revealing the real agenda of "gun control"Quoted 5 lines · Eric S. Raymond
Alexander Viro <[email protected]>:
Quoted 2 lines
I'm not talking about connectedness of the thing. However, I suspect that graph has a small subset such that removing it makes it fall apart.
Um. So how does that help?
First of all, it reduces the complexity of finding the best valid approximation (mind you, I'm not saying that it's the problem you need to solve, just that you don't need anything close to 3^1976 even for _that_).
And simple variation of the full thing can be used for "find a valid approximation within given distance".
Full (and dumb) variant first:
for all combinations of values of core variables
for each peripherial group
find the best valid approximation within that group, given the values of core variables.
The cost is 3^(size of core) * 3^(size of maximal peripherial group) * number of peripherial groups * size of maximal periph. group * maximal number of constraints for periph. group.
Again, I'm _not_ suggesting to do that. However, limited variant of the problem (find valid approximation within 10 changes from given or complain) is much easier.
Eric, could you point me to a place where I could grab the current set of constraints? In any case I have a very strong gut feeling that separation the variables into core and peripherial is essential part of data and ignoring it makes problem much harder than it really is. I'd like to see how large the core actually is and how large periph. groups are.
Quoted 23 lines · Eric S. Raymond
Alexander Viro <[email protected]>:
Quoted 8 lines
Assertion: you can split the set of variables into disjoint union of small subsets X, Y_1,...,Y_m such that each constraint is concerned only with variables from X and at most one of
Y_i.IOW, there is a small "core" and for fixed values of core variables constraints fall into groups, each dealing with its own _small_ set of variables.
Quoted 8 lines
If that assertion is true the complexity is nowhere near 3^N.
Eric, you probably have the most accurate information about the existing constraints. Care to verify the assertion above? I'm serious - the set of constraints is very far from generic and if nothing else, such preprocessing (splitting variables into core and peripherial groups) can make life easier in other parts of the thing.
You're almost right. If you counted only explicit constraints, created by require statements, you get a bunch of cliques that aren't that large.
Quoted 6 lines
Unfortunately....there are a huge bunch of implicit constraints created by dependency relationships in the menu tree. For example, all SCSI cards are dependents of the SCSI symbol. Set SCSI to N and all the card symbols get turned off; set any card symbol to Y or M and the value of SCSI goes to Y or M correspondingly.
Are the dependencies for each disjoint union kept hierarchically? Such as:
setting C = 'y' requires B = 'y'
setting B = 'y' requires A = 'y'
etc.
If so, given the above ruleset involving symbols A, B and C, and given that such a ruleset is violated for some reason (you don't even care why), use the following approach:
set C to 'n' -> are we ok?
set B to 'n' -> are we ok?
set A to 'n' -> are we ok?
Inform the user of each change. In a massively broken configuration you could end up with a lot of stuff set to 'n' ultimately, but I think that this generally would just end up shutting off troublesome configuration settings, and requiring that the user then reset them manually.
In my example above I've idealized your idealized world of tristates into a world of bistates. How do you like that :-)
Instead of trying all possible combinations, instead for 2000 symbols you only need (worst case) to check 2000 - each iteration you will have changed one setting from y to n, so the most you can do is 2000 checks.
David
Signature · 3 lines
David Mansfield (718) 963-2020 [email protected] Ultramaster Group, LLC www.ultramaster.com
David Mansfield <[email protected]>:
Quoted 4 lines
If so, given the above ruleset involving symbols A, B and C, and given that such a ruleset is violated for some reason (you don't even care why), use the following approach:
Quoted 8 lines
set C to 'n' -> are we ok?
set B to 'n' -> are we ok?
set A to 'n' -> are we ok?Inform the user of each change. In a massively broken configuration you could end up with a lot of stuff set to 'n' ultimately, but I think that this generally would just end up shutting off troublesome configuration settings, and requiring that the user then reset them manually.
Actually this is the best idea I've seen yet, because the single "known-good" configuration is almost all n values.
Signature · 11 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
Let us hope our weapons are never needed --but do not forget what
the common people knew when they demanded the Bill of Rights: An
armed citizenry is the first defense, the best defense, and the
final defense against tyranny.
If guns are outlawed, only the government will have guns. Only
the police, the secret police, the military, the hired servants of
our rulers. Only the government -- and a few outlaws. I intend to
be among the outlaws.
-- Edward Abbey, "Abbey's Road", 1979Eric> David Mansfield <[email protected]>:
Quoted 4 lines
Quoted 4 lines
If so, given the above ruleset involving symbols A, B and C, and given that such a ruleset is violated for some reason (you don't even care why), use the following approach:
Quoted 8 lines
Quoted 8 lines
set C to 'n' -> are we ok?
set B to 'n' -> are we ok?
set A to 'n' -> are we ok?Inform the user of each change. In a massively broken configuration you could end up with a lot of stuff set to 'n' ultimately, but I think that this generally would just end up shutting off troublesome configuration settings, and requiring that the user then reset them manually.
Eric> Actually this is the best idea I've seen yet, because the single Eric> "known-good" configuration is almost all n values.
Darnit! Someone else beat me to this idea, though David did a much better job of describing the solution here. *grin*
What Eric has been arguing about with the 3^n problem of finding the correct constrained state is interesting (and mathematically over my head), I wanted to point out that our real world setting here has some easy to do fixes, but just turning stuff off (and telling the user you did so!) and then letting the user turn stuff back on.
Keith Owens also had a good comment on how to deal with an broken config.
A) go interactive! Don't dump the user to vi, just put them in and tell them to fix their constraints themselves. This was my original beef with CML2, it didn't continue interactive so I could fix the problem, I had to hack it by hand.
For the non-interactive, setting stuff to 'n' should prune away problem states by the *ton* drastically simplifying the set of constraints to be satisfied.
Thanks for everyone chipping in here, it's been a interesting discussion to follow, and I'm hoping to see that we can prune back the problem easily enough to handle most cases of broken configs by working towards the known good config of mostly 'n' answers.
John
Greg Banks <[email protected]>:
Quoted 6 lines
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.
Signature · 5 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
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), 1988Ingo Oeser <[email protected]>:
Quoted 3 lines
If the current dependencies of the symbols can be represented as a tree (or can be topologically sorted, to be CS-correct), then I would only care about the "leaves" of that tree.
Sorry, there are crosslinks, it's a DAG. The example that triggered this displays one.
Quoted 2 lines
Most added symbols in newer configs are added as leaves. So this should suffice in most situations.
Oh? What if the leaf participates in a newly-added constraint such that when you flip it, something else (node or leaf) has to change? There could be ripple effects all through the tree.
This isn't a farfetched case, either. The new leaf might be a PCMCIA card (for example) in which case enabling it would force generic PCMCIA support on. Sound harmless? OK. Suppose the new capability is some new IP filtering capability that interacts with NAT and connection tracking. Now go look at the cross-constraints in IP filtering. Take a bottle of strong analgesic with you, because you're going to need it.
I told you there's no way to separate the easy cases from the hard ones. I didn't say that casually. I've been thinking about problems like this since last May. The configuration-state space is all tangled together by the the constraints in such a way that it's hard to put a bound beforehand on the side-effects effects of what might at first look like a single-point change. Even in a new leaf node.
The most relevant distinction isn't "leaf vs. interior node"; it's the size of a symbol's clique. Consider the relation "X participates in a constraint with Y" (X co Y). Now consider the transitive completion of that relationship; we'll say that X is "related" to Y if there is any chain of co relations between them. The set of all Y related to X is its clique.
Quoted 3 lines
If we miss a symbol from .config, we ask the user, using the one from defconfig as default, if we cannot derive its value from our constraints.
That's almost the way it works now. If the user doesn't supply a config the defconfig gets used. Falling back on the defconfig for *individual* symbols if the user's config didn't supply a value...hmm. technically possible but doesn't strike me as a good idea.
What if the defconfig is set up for IDE but the user wants to do SCSI? He doesn't supply a value for IDE, it gets picked up as y from the defconfig...user is now carrying code he doesn't want and didn't expect.
Quoted 3 lines
If we have a symbol in .config, that we don't know about, we simply ignore it (and tell the user that it's "obsolete or renamed").
Yup, I do that.
Quoted 2 lines
If the value for a symbol is there, but doesn't fit our
constraints: Ask the user or use the opposite (if it is boolean).
*You don't know which symbol is wrong* That's the whole point!
Quoted 2 lines
And will the derivation be in nearly constant time, if I change one symbol?
Deduction time is...hm. Linear in tbe symbol's clique size. I think.
Signature · 9 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
Certainly one of the chief guarantees of freedom under any government,
no matter how popular and respected, is the right of the citizens to
keep and bear arms. [...] the right of the citizens to bear arms is
just one guarantee against arbitrary government and one more safeguard
against a tyranny which now appears remote in America, but which
historically has proved to be always possible.
-- Hubert H. Humphrey, 1960Quoted 2 lines · Eric S. Raymond
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.
Quoted 16 lines
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.
Keith Owens <[email protected]>:
Quoted 7 lines
Quoted 2 lines · Eric S. Raymond
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.)
Quoted 5 lines
(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.
Quoted 7 lines
(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.
Quoted 6 lines
(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.
Signature · 10 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
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 1788Quoted 3 lines
(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.
Quoted 9 lines
Quoted 5 lines
(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
Quoted 1 line
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 ;)
Quoted 3 lines
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
Alan Cox <[email protected]>:
Quoted 6 lines
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 ;-).
Signature · 5 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
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.Quoted 7 lines
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.
Quoted 5 lines
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
Quoted 1 line
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
Device driver from kernel2.2.x to kernel2.4
I want to port a Network driver from kernel2.2.x to 2.4. Could anyone please point me a handy pointer where i can find a complete documentation.
I could find some, but not the complete changes required.
Also, Approximate time estimation for this migration from an experienced developer would be much helpful.
Thanks in Advance,
Jalaja
__________________________________________________
Do You Yahoo!?
Yahoo! Auctions - buy the things you want at great prices
http://auctions.yahoo.com/
Re: Device driver from kernel2.2.x to kernel2.4
In reply to Alan CoxQuoted 4 lines · jalaja devi
I want to port a Network driver from kernel2.2.x to 2.4. Could anyone please point me a handy pointer where i can find a complete documentation.
http://www.firstfloor.org/~andi/softnet/
Also, take a look at acenic.c and eepro100.c. They both support 2.2 and 2.4. The compatibility macros will provide pointers.
Quoted 5 lines
I could find some, but not the complete changes required.
Also, Approximate time estimation for this migration from an experienced developer would be much helpful.
It took me about 30 minutes to scruffily hack a 2.2 net driver into the 2.4 APIs. I'd allow a day to do it properly. Plus another day for testing, especially if you want to support SMP well.
-
Quoted 9 lines · Eric S. Raymond
Keith Owens <[email protected]>:
Quoted 3 lines
(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:
Quoted 5 lines
(X86 and SMP) implies RTC!=nYou 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.
Quoted 2 lines · Eric S. Raymond
OK, so you want CML2's "make oldconfig" to do something more graceful than simply say "Foo! You violated this constraint! Go fix it!"
After all this combinatorics I still do not know an answer to a simple question. With the current system I can do
grep -v '^#' .config > config.stripped
copy 'config.stripped' back to .config, type 'make oldconfig' and hold <Return> for a while to get my old .config back. This is actually very useful, and used every day, although maybe not precisely in the manner as above. :-)
So, the question is: can I do something something like that with CML2? If the answer is "no" then something is very seriously missing and no references to halting problems can cover that. If, OTOH, the answer is "yes" then what is a big trouble?
Michal
Quoted 5 lines · Eric S. Raymond
What you know, to start with, is (a) the configuration, (b) the constraints, (c) the shape of the menu tree, and (d) which constraints have failed. What you want to do is find a set of corrected configurations which fulfill all constraints and are in some sense "close" to the broken one you have.
You also know:
(e) the default config, with which you may compare the broken one
Quoted 8 lines
The obvious thing to try is to start with the configuration you have and try mutating the variables that occur in the broken constraint(s). Of course, there are 3^n of these where n is the number of distinct variables, so this is going to blow up really fast; 3, 9, 27, 81, 243 and we ain't even to six symbols yet. By the time we get to the twelve variables that could be linked by just *one* constraint, there are 531,441. Even if you can check 500 configurations a second it's going to take 16 minutes just to get a candidate list.
500/second seems very slow. Can't you do 1000 times that?
http://www.cs.bgu.ac.il/~omri/Humor/write_in_c.html
You could keep the bulk of your code in Python, and write a separate config fixer in C.
Quoted 6 lines
There's a third way. The cheap, dirty attack on the satisfaction problem is to use what's called a "stochastic" or "hill-climbing" algorithm. It's a less ambitious version of the brute-force search that essentially random-walks through the configuration space looking for valid ones.
Quoted 8 lines
The problem with stochastic search is that (a) it's not guaranteed to find a model even if models exist, and (b) you can't predict its running time. Oops...
Even assuming we could generate large numbers of candidate models quickly, I've been putting the word "close" in quotes because there's another nasty problem lurking here. "Close" is not well-defined in this space.
Procedure:
1. throw out all junk symbols (could try spell checking first)
2. mark non-default settings as read-only
3. add missing symbols as needed to meet constraints
4. add any additional missing symbols
5. mutate the config until it works... user may ^C when bored
Rules for mutation:
1. do not modify what the user set (see #2 above)
2. configs that differ little from the one you start with are more fit
3. configs that violate fewer constraints are more fit
4. option 'm' should be the most likely mutation
5. symbols that were missing should be most likely to mutate
6. fit configs breed with each other of course
This will fix common errors. Obviously it can't fix the case of a user with non-default settings that conflict. That is good, because I don't want a tool to disobey me.
The above ought to work well for a config file with only a half dozen entries. List what you care about, and let the tool make everything right.
but the case where this is an issue is when you have non-default items that conflict.
unless I am mssing somethign the existing tool already handles the case where new features get added (upgradeing kernel) or the case where some items are not defined that are needed.
the case that Eric is saying is so hard is when you have two options selected by the user that conflict.
David Lang
Quoted 77 lines · Albert D. Cahalan
Date: Thu, 3 May 2001 19:58:24 -0400 (EDT)
From: Albert D. Cahalan <[email protected]>
To: [email protected]
Cc: [email protected], [email protected]
Subject: Re: Why recovering from broken configs is too hardQuoted 5 lines · Eric S. Raymond
What you know, to start with, is (a) the configuration, (b) the constraints, (c) the shape of the menu tree, and (d) which constraints have failed. What you want to do is find a set of corrected configurations which fulfill all constraints and are in some sense "close" to the broken one you have.
You also know:
(e) the default config, with which you may compare the broken oneQuoted 8 lines
The obvious thing to try is to start with the configuration you have and try mutating the variables that occur in the broken constraint(s). Of course, there are 3^n of these where n is the number of distinct variables, so this is going to blow up really fast; 3, 9, 27, 81, 243 and we ain't even to six symbols yet. By the time we get to the twelve variables that could be linked by just *one* constraint, there are 531,441. Even if you can check 500 configurations a second it's going to take 16 minutes just to get a candidate list.
500/second seems very slow. Can't you do 1000 times that?
http://www.cs.bgu.ac.il/~omri/Humor/write_in_c.htmlYou could keep the bulk of your code in Python, and write a separate config fixer in C.
Quoted 6 lines
There's a third way. The cheap, dirty attack on the satisfaction problem is to use what's called a "stochastic" or "hill-climbing" algorithm. It's a less ambitious version of the brute-force search that essentially random-walks through the configuration space looking for valid ones.
Quoted 8 lines
The problem with stochastic search is that (a) it's not guaranteed to find a model even if models exist, and (b) you can't predict its running time. Oops...
Even assuming we could generate large numbers of candidate models quickly, I've been putting the word "close" in quotes because there's another nasty problem lurking here. "Close" is not well-defined in this space.
Procedure:
1. throw out all junk symbols (could try spell checking first)
2. mark non-default settings as read-only
3. add missing symbols as needed to meet constraints
4. add any additional missing symbols
5. mutate the config until it works... user may ^C when boredRules for mutation:
1. do not modify what the user set (see #2 above)
2. configs that differ little from the one you start with are more fit
3. configs that violate fewer constraints are more fit
4. option 'm' should be the most likely mutation
5. symbols that were missing should be most likely to mutate
6. fit configs breed with each other of courseThis will fix common errors. Obviously it can't fix the case of a user with non-default settings that conflict. That is good, because I don't want a tool to disobey me.
The above ought to work well for a config file with only a half dozen entries. List what you care about, and let the
tool make everything right.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Albert D. Cahalan <[email protected]>:
Quoted 7 lines
Procedure:
1. throw out all junk symbols (could try spell checking first)
2. mark non-default settings as read-only
3. add missing symbols as needed to meet constraints
4. add any additional missing symbols
5. mutate the config until it works... user may ^C when bored
You can't be serious. You invite the poor user to sit through an indefinite, unpredictable, and *large* number of mutation passes hoping the stupid search will trip over a solution? That's a far worse waste of their time than telling them to correct by hand in the exceedingly rare cases that would be necessary, in my considered opinion.
A more egregious case of using a bazooka to swat a fly I've seldom seen. Can we restore some sense of *proportion* here?
Signature · 7 lines
<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>
Rifles, muskets, long-bows and hand-grenades are inherently democratic
weapons. A complex weapon makes the strong stronger, while a simple
weapon -- so long as there is no answer to it -- gives claws to the
weak.
-- George Orwell, "You and the Atom Bomb", 1945