Hi,

I just wanted to say that I've been accepted into this year's Google
Summer of Code program and will spend this summer working on improving
the kconfig system in a very particular direction: I want to integrate
a proper boolean constraint satisfiability solver into the
configuration editors (menuconfig, etc.) in order to allow
partial/incomplete configuration specifications. In short, this means
that the user can choose to not specify a particular value for some
config options, but let the system deduce their values. This will
hopefully improve usability and also solve the select problem once and
for all.

A slightly shortened version of the project proposal that was accepted
can be found here:

http://userweb.kernel.org/~vegard/gsoc2010/proposal-short.html

In case anybody would like to track my progress throughout the summer,
I have set up my public project repositories at:

http://github.com/vegard/dpll
http://github.com/vegard/linux-2.6-kconfig-sat

I am also planning to post some updates to LKML as milestones are
completed.  (Please let me know if you would like to be added to or
removed from the Cc list.) The official end date is August 16, by
which time I hope to have submitted my work for mainline inclusion.

Feedback is appreciated -- I am also prepared to respond to
constructive criticism.

Lastly, I would like to thank Google for sponsoring me, and to thank
Portland State University and my mentor Bart Massey for believing in
this idea and project.


Vegard
--

[ message continues ]

Nice idea. I read your proposal and it looks good.

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.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.
--

[ message continues ]

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.


Vegard
--

[ message continues ]

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.

James


--

[ message continues ]

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.

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
--

[ message continues ]

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

Right, this will solve our current kernel developer issue ... I'm
betting the guiding users one will be slightly harder.

James


--

[ message continues ]

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
--

[ message continues ]

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



-- 
Jon Smirl
jonsmirl@gmail.com
--

[ message continues ]

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
--

[ message continues ]

At least some of what you want is provided by 'make localmodconfig'

--

[ message continues ]

There are more...

...part of the problem is that kconfig is both user-dependend (what
filesystems do I use) and machine dependend (what does hw need).

Current defconfig system is unfortunately not quite there :-(.

What would be nice for machines like Sharp Zaurus (spitz) would be
defconfig which answered =Y for hardware spitz definitely has (sound),
=N for hardware that can't be connected (anything pci), and something
different (=M?)  for hardware that can be connected to it
(pcmcia)... leaving 'user' options like filesystems configured ... up
to the user.
								Pavel

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--

[ message continues ]

The problem is that might be a lot of entries, e.g. for "depends on PCI"

You then end up displaying pages and pages of information, which
is very hard to make sense of.

You can see that by playing around with libzypp dependencies.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.
--

[ message continues ]

Very nice! I thought on this idea too.

Does this means that if you have a pristine kernel, and you do 'make
menuconfig' and don't change anything, the .config file will be empty?
And then, anything that you change will be in the .config file?

On another case I do 'make ARCH=arm omap3_beagle_defconfig' then my
.config file will point to that particular defconfig, and I can add
only the changes that I want. Also, omap3_beagle_defconfig probably
points omap3_defconfig and only makes certain changes.

If so, that would be awesome :)

-- 
Felipe Contreras
--

[ message continues ]

Yes and no -- I think the plan is to retain the .config file as it is
(i.e. it specifies more or less every option completely), so that it
remains backwards compatible; bisection, for example, is very
important. But yes, I think there will be a new file, say, .satconfig,
which contains only the specific choices of the user. And this one
would be empty, as you say, with a pristine kernel.

I think, then, that the .config file will be regenerated from the

Do you mean essentially a sort of cascade of configurations that
inherit options from a different file? That shouldn't be very hard to
do -- I'll make a note of it for when I get that far! That has the
potential to make the defconfig files a bit shorter and more
manageable (not sure how big a problem that is in practice today,
though).

Thanks,


Vegard
--

[ message continues ]

I see. As long as people can use .satconfig only if they want, I think

Exactly. Well, I don't know if anybody considers that a problem, but
just check arch/arm/configs/*. All of them are much bigger than
needed, and some have not been updated in a long time (even as old as
2.6.11). So if you do make ARCH=arm assabet_defconfig and do a 'diff
.config assabet_defconfig' they would be completely different. This
way it's hard to keep track of the general config changes, and ARM
related changes, and OMAP3 changes, and compare with board-specific
ones.

Cheers.

-- 
Felipe Contreras
--

[ message continues ]