GSoC project: Improving kconfig using a SAT solver
in [Kernel]
|
Prev: [2.6.34 PATCH] USB: option.c: OLIVETTI OLICARD100 support
Next: [PATCH] perf_events: fix errors path in perf_output_begin() (take 3)
From: Vegard Nossum on 17 May 2010 10:30 On 17 May 2010 15:21, James Bottomley <James.Bottomley(a)hansenpartnership.com> wrote: >> > I assume you got inspired by the libzypp use of a SAT solver >> > for package dependencies? One problem that is visible there >> > is that it can be hard to display conflicts in a nice and understandable >> > way to the user, especially if there are lots of dependencies. >> > >> > It might be worth planning in some time to solve that nicely. >> >> Thanks! I didn't actually get inspired by libzypp -- but somebody else >> mentioned it too, so I guess I should take a look! >> >> You bring up a valid point, and I admittedly haven't given it VERY >> much thought yet, but I think that conflicts could be displayed in the >> following way: If an instance is unsolvable, then it means that all >> possible valuations/assignments make at least one clause (disjunction) >> false. Each clause is usually generated by exactly one dependency >> specification (the "depends on" directive), so we could print these >> dependencies to the screen as suggestions for how to resolve the >> conflict. > > Actually, the problem is a bit different from the zypper one: Since each > package supplies its own dependencies and obsoletes, it is possible to > get an unsolvable installation problem. What zypper tries to do in > these situations is recommend possible courses of action (like remove > these five packages from your current system, or downgrade this one > etc.). For the Kconfig system, an unsolvable configuration is actually > a bug in the Kconfig files. You can proceed on the premise that it's a > single symbol that has the wrong depends or selects and isolate it from > there. Done right, the Kconfig SAT solver shouldn't detect this problem > only when a triggering configuration is input, but all the time, so it > becomes impossible to introduce buggy Kconfig directives into the kernel > tree. Even if the problem is different from zypper's, it is also here possible to get an unsatisfiable instance. You are right that, yes, the kconfig files on their own should always be satisfiable. But that's before the user has made any choices at all. An example of an unsatisfiable instance would be one where the user demands that 1. some USB driver is enabled, while 2. USB support in general is disabled. But yes, once the basic infrastructure is in place, checking the consistency of the kconfig files alone (not taking user's config into account) should be trivial. Vegard -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: david on 18 May 2010 02:10 On Mon, 17 May 2010, James Bottomley wrote: > On Mon, 2010-05-17 at 16:21 +0200, Vegard Nossum wrote: >> On 17 May 2010 15:21, James Bottomley >> >> Even if the problem is different from zypper's, it is also here >> possible to get an unsatisfiable instance. You are right that, yes, >> the kconfig files on their own should always be satisfiable. But >> that's before the user has made any choices at all. An example of an >> unsatisfiable instance would be one where the user demands that 1. >> some USB driver is enabled, while 2. USB support in general is >> disabled. > > Actually, these are two separate problems. The first is basic > consistency within the Kconfig subsytstem (something that select > currently damages for us). The second is what to present to the user, > which is where the inception of the select problem came from. A user > doesn't really want to know that USB device X depends on usb storage, > SCSI and a raft of other things ... they just want it to configure a > kernel that supports their device. In particular, we don't want to > present every possible option to users and then try to work out a > solution, we really need guided configuration (which, in some measure, > is what we have today: if you don't select general USB, you won't see > any USB drivers. Or more importantly, if you select an Adaptec SCSI > card, we just enable whichever transport library it needs). There are two modes people can be in when configuring a kernel. 1. I want to configure a kernel to support my hardware, enable anything else needed to make it work. 2. I really care about having a small kernel, don't enable anything I have disabled (but help me figure out why something I want isn't available) I don't think that hiding hardware from the user is ever the best thing to do. for approach #1 you obviously don't want to hide anything, but even for approach #2, someone may not realize that by disabling one option they are making it impossible to support something, and as someone who spent a bunch of time hunting through config to find options that I ended up finding were not available without enabling something else, I much prefer to see the option, but see it disabled rather than not being sure if it should be there, or somewhere else in the config. David Lang -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Jon Smirl on 18 May 2010 08:30 On Tue, May 18, 2010 at 2:03 AM, <david(a)lang.hm> wrote: > On Mon, 17 May 2010, James Bottomley wrote: > >> On Mon, 2010-05-17 at 16:21 +0200, Vegard Nossum wrote: >>> >>> On 17 May 2010 15:21, James Bottomley >>> >>> Even if the problem is different from zypper's, it is also here >>> possible to get an unsatisfiable instance. You are right that, yes, >>> the kconfig files on their own should always be satisfiable. But >>> that's before the user has made any choices at all. An example of an >>> unsatisfiable instance would be one where the user demands that 1. >>> some USB driver is enabled, while 2. USB support in general is >>> disabled. >> >> Actually, these are two separate problems. �The first is basic >> consistency within the Kconfig subsytstem (something that select >> currently damages for us). �The second is what to present to the user, >> which is where the inception of the select problem came from. �A user >> doesn't really want to know that USB device X depends on usb storage, >> SCSI and a raft of other things ... they just want it to configure a >> kernel that supports their device. �In particular, we don't want to >> present every possible option to users and then try to work out a >> solution, we really need guided configuration (which, in some measure, >> is what we have today: if you don't select general USB, you won't see >> any USB drivers. �Or more importantly, if you select an Adaptec SCSI >> card, we just enable whichever transport library it needs). > > There are two modes people can be in when configuring a kernel. > > 1. I want to configure a kernel to support my hardware, enable anything else > needed to make it work. > > 2. I really care about having a small kernel, don't enable anything I have > disabled (but help me figure out why something I want isn't available) > > I don't think that hiding hardware from the user is ever the best thing to > do. for approach #1 you obviously don't want to hide anything, but even for > approach #2, someone may not realize that by disabling one option they are > making it impossible to support something, and as someone who spent a bunch > of time hunting through config to find options that I ended up finding were > not available without enabling something else, I much prefer to see the > option, but see it disabled rather than not being sure if it should be > there, or somewhere else in the config. I have to agree with this. An example is audio drivers that disappear because something like SPI is turned off. Sometimes I have to read the Kconfig files to figure out what subsystems I need enabled in order to make the driver appear as a choice. Another way this could work... Enable the platform this causes all subsystems on the platform (usb, spi, pci, etc) to be soft enabled user selects device drivers or hard enables the subsystem on save, if the subsystem wasn't hard enabled for some reason or dependency, disable it. --------------- I'd also find it useful if Kconfig had an option that analyzed the system it is running on and then generated the minimal set of drivers needed to support it. Assume that the system is running something like the Ubuntu kernel with every driver enabled. Then figure out the minimal build footprint for a custom kernel to support the same hardware. I do this by hand, but a button for doing it would be a lot easier. > > David Lang > -- > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in > the body of a message to majordomo(a)vger.kernel.org > More majordomo info at �http://vger.kernel.org/majordomo-info.html > Please read the FAQ at �http://www.tux.org/lkml/ > -- Jon Smirl jonsmirl(a)gmail.com -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Vegard Nossum on 18 May 2010 09:00 On 18 May 2010 14:26, Jon Smirl <jonsmirl(a)gmail.com> wrote: > On Tue, May 18, 2010 at 2:03 AM, <david(a)lang.hm> wrote: >> There are two modes people can be in when configuring a kernel. >> >> 1. I want to configure a kernel to support my hardware, enable anything else >> needed to make it work. >> >> 2. I really care about having a small kernel, don't enable anything I have >> disabled (but help me figure out why something I want isn't available) >> >> I don't think that hiding hardware from the user is ever the best thing to >> do. for approach #1 you obviously don't want to hide anything, but even for >> approach #2, someone may not realize that by disabling one option they are >> making it impossible to support something, and as someone who spent a bunch >> of time hunting through config to find options that I ended up finding were >> not available without enabling something else, I much prefer to see the >> option, but see it disabled rather than not being sure if it should be >> there, or somewhere else in the config. > > I have to agree with this. An example is audio drivers that disappear > because something like SPI is turned off. Sometimes I have to read the > Kconfig files to figure out what subsystems I need enabled in order to > make the driver appear as a choice. > > Another way this could work... > Enable the platform > this causes all subsystems on the platform (usb, spi, pci, etc) to be > soft enabled > user selects device drivers or hard enables the subsystem > on save, if the subsystem wasn't hard enabled for some reason or > dependency, disable it. > > --------------- > > I'd also find it useful if Kconfig had an option that analyzed the > system it is running on and then generated the minimal set of drivers > needed to support it. Assume that the system is running something like > the Ubuntu kernel with every driver enabled. Then figure out the > minimal build footprint for a custom kernel to support the same > hardware. I do this by hand, but a button for doing it would be a lot > easier. Consider this a response to both of the above e-mails. Just to clear any confusion, a consequence of using SAT for kconfig is that you can now say for example only the following: "I want drivers A, B, and C. I don't care if that means I can't use FOO and I don't care if that means that I have to use BAR, just give me A, B, and C." I suppose another way to see it is that configuring the kernel using the current menuconfig is a top-down process, since you have to select USB before you can select any driver that depends on USB. Using SAT for kconfig puts this on its head, and the configuration process becomes bottom-up; you say only what you want to have (or not have), and the system figures out the rest. If you choose a driver that requires USB (and you haven't said that you also don't want USB support, which would be impossible), then USB _will_ be enabled automatically. For the record, I think that there are already scripts that take a running system and builds a config for that. Vegard -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: kevin granade on 18 May 2010 09:50
On Tue, May 18, 2010 at 7:54 AM, Vegard Nossum <vegard.nossum(a)gmail.com> wrote: > On 18 May 2010 14:26, Jon Smirl <jonsmirl(a)gmail.com> wrote: >> On Tue, May 18, 2010 at 2:03 AM, �<david(a)lang.hm> wrote: >>> There are two modes people can be in when configuring a kernel. >>> >>> 1. I want to configure a kernel to support my hardware, enable anything else >>> needed to make it work. >>> >>> 2. I really care about having a small kernel, don't enable anything I have >>> disabled (but help me figure out why something I want isn't available) >>> >>> I don't think that hiding hardware from the user is ever the best thing to >>> do. for approach #1 you obviously don't want to hide anything, but even for >>> approach #2, someone may not realize that by disabling one option they are >>> making it impossible to support something, and as someone who spent a bunch >>> of time hunting through config to find options that I ended up finding were >>> not available without enabling something else, I much prefer to see the >>> option, but see it disabled rather than not being sure if it should be >>> there, or somewhere else in the config. >> >> I have to agree with this. An example is audio drivers that disappear >> because something like SPI is turned off. Sometimes I have to read the >> Kconfig files to figure out what subsystems I need enabled in order to >> make the driver appear as a choice. >> >> Another way this could work... >> Enable the platform >> this causes all subsystems on the platform (usb, spi, pci, etc) to be >> soft enabled >> user selects device drivers or hard enables the subsystem >> on save, if the subsystem wasn't hard enabled for some reason or >> dependency, disable it. >> >> --------------- >> >> I'd also find it useful if Kconfig had an option that analyzed the >> system it is running on and then generated the minimal set of drivers >> needed to support it. Assume that the system is running something like >> the Ubuntu kernel with every driver enabled. Then figure out the >> minimal build footprint for a custom kernel to support the same >> hardware. �I do this by hand, but a button for doing it would be a lot >> easier. > > Consider this a response to both of the above e-mails. Just to clear > any confusion, a consequence of using SAT for kconfig is that you can > now say for example only the following: "I want drivers A, B, and C. I > don't care if that means I can't use FOO and I don't care if that > means that I have to use BAR, just give me A, B, and C." > > I suppose another way to see it is that configuring the kernel using > the current menuconfig is a top-down process, since you have to select > USB before you can select any driver that depends on USB. Using SAT > for kconfig puts this on its head, and the configuration process > becomes bottom-up; you say only what you want to have (or not have), > and the system figures out the rest. If you choose a driver that > requires USB (and you haven't said that you also don't want USB > support, which would be impossible), then USB _will_ be enabled > automatically. > > For the record, I think that there are already scripts that take a > running system and builds a config for that. At least some of what you want is provided by 'make localmodconfig' -Kevin Granade > > > Vegard > -- > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in > the body of a message to majordomo(a)vger.kernel.org > More majordomo info at �http://vger.kernel.org/majordomo-info.html > Please read the FAQ at �http://www.tux.org/lkml/ > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |