Skip to content

kconfig: Add support for conflict resolution

Ole Schuerks kdevops linux-kbuild lkml 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v7 Latest11 patches 10 repliesIn review
  2. v611 patches 13 repliesSuperseded
  3. v511 patches 2 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v412 patches12 repliesSuperseded

Changes in v7 from the cover letter

* improve error handling when loading picosat symbols with dlsym(): use dlerror() instead of checking for NULL
* move list_at_index from scripts/include/list.h to scripts/kconfig/cf_utils.h
* change interface of list_for_each_entry_from and rename list_size to list_count_nodes to more closely match scripts/include/list.h
* change misleading name "rangefix" of fix generation algorithm to "fixgen"

Patches in v7 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/11kconfig: Add PicoSAT interfacescripts/kconfig/picosat_functions.c scripts/kconfig/picosat_functions.h+114 -01 reply
2/11kconfig: Add definitionsscripts/kconfig/Makefile scripts/kconfig/cf_defs.h scripts/kconfig/expr.h+417 -20 replies
3/11kbuild: Add list_count_nodes and list_for_each_entry_fromscripts/include/list.h+26 -01 reply
4/11kconfig: Add files for building constraintsscripts/kconfig/cf_constraints.c scripts/kconfig/cf_constraints.h+1801 -00 replies
5/11kconfig: Add files for handling expressionsscripts/kconfig/cf_expr.c scripts/kconfig/cf_expr.h+2184 -00 replies
6/11kconfig: Add files for fix generationscripts/kconfig/cf_fixgen.c scripts/kconfig/cf_fixgen.h+1157 -00 replies
7/11kconfig: Add files with utility functionsscripts/kconfig/cf_utils.c scripts/kconfig/cf_utils.h+1116 -00 replies
8/11kconfig: Add toolsscripts/kconfig/.gitignore scripts/kconfig/cfoutconfig.c scripts/kconfig/configfix.c +1 more+533 -00 replies
9/11kconfig: Add xconfig-modificationsscripts/kconfig/qconf.cc scripts/kconfig/qconf.h+785 -20 replies
10/11kconfig: Add loader.gifscripts/kconfig/loader.gif+0 -00 replies
11/11kconfig: Add documentation for the conflict resolverDocumentation/kbuild/kconfig.rst+56 -00 replies

Reviews trailers per patch

9 of 11 patches have a Reviewed-by or Acked-by.

PatchLuis ChamberlainEvgeny Groshev
1/11R-b
2/11R-b T-b
3/11R-b
4/11R-b T-b
5/11R-b T-b
6/11R-b T-b
7/11R-b T-b
8/11R-b T-b
9/11R-b T-b
10/11
11/11

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v7 thread

Cover letter [PATCH v7 00/11] kconfig: Add support for conflict resolution

Hi,

This patch series (for next-20250207) provides support to enable users to express their desired target configuration and display possible resolutions to their conflicts. This support is provided within xconfig.

Conflict resolution is provided by translating kconfig's configuration option tree to a propositional formula and allowing our resolution algorithm and PicoSAT to calculate the possible fixes for an expressed target kernel configuration. PicoSAT is the smallest and most robust C SAT solver we could find which is also GPL compatible. PicoSAT is used as a dynamically loaded library. For Debian and Fedora, the apt and dnf packages named "picosat" provide the library. For other distros, we provide instructions on how PicoSAT needs to be compiled from the sources in the documentation.

New UI extensions are made to xconfig with panes and buttons to allow users to express new desired target options, calculate fixes, and apply any of found solutions.

You can see a YouTube video demonstrating this work [2]. This effort is part of the kernelnewbies Kconfig-SAT project [3], the approach and effort is also explained in detail in our paper [4]. The results from the evaluation have significantly improved since then: Around 80 % of the conflicts could be resolved, and 99.9 % of the generated fixes resolved the conflict. It is also our attempt at contributing back to the kernel community, whose configurator researchers studied a lot.

Patches applicable to next-20250207.

[0] https://gsd.uwaterloo.ca/sites/default/files/vamos12-survey.pdf
[1] https://www.linux-magazine.com/Issues/2021/244/Kconfig-Deep-Dive
[2] https://www.youtube.com/watch?v=vn2JgK_PTbc
[3] https://kernelnewbies.org/KernelProjects/kconfig-sat
[4] http://www.cse.chalmers.se/~bergert/paper/2021-icseseip-configfix.pdf

Thanks from the team! (and thanks to Luis Chamberlain for guiding us here)

Changelog v7:
* improve error handling when loading picosat symbols with dlsym(): use dlerror() instead of checking for NULL
* move list_at_index from scripts/include/list.h to scripts/kconfig/cf_utils.h
* change interface of list_for_each_entry_from and rename list_size to list_count_nodes to more closely match scripts/include/list.h
* change misleading name "rangefix" of fix generation algorithm to "fixgen"

Changelog v6:
* remove script for manually installing PicoSAT
* adapt documentation and help text in the GUI accordingly
* convert Qt signal/slot connects to new style

Changelog v5:
* use lists from scripts/include/list.h
* use PicoSAT as a dynamically loaded library
* Fix GUI bug that made the displayed tables editable
* Allow cycling through the desired values of a symbol in the conflict view in the GUI by clicking on the cell
* Fix usage of "NO" instead of "N" etc. in some places in the GUI
* Improve function naming
* Add documentation
* Simlify xcalloc to xmalloc in some places
* Fix allocation bug in fexpr_add_to_satmap() and init_data()
* Remove functions pexpr_eliminate_dups() and print_expr()

Ole Schuerks (11):
kconfig: Add PicoSAT interface
kconfig: Add definitions
kbuild: Add list_count_nodes and list_for_each_entry_from
kconfig: Add files for building constraints
kconfig: Add files for handling expressions
kconfig: Add files for fix generation
kconfig: Add files with utility functions
kconfig: Add tools
kconfig: Add xconfig-modifications
kconfig: Add loader.gif
kconfig: Add documentation for the conflict resolver

 Documentation/kbuild/kconfig.rst    |   56 +
 scripts/include/list.h              |   26 +
 scripts/kconfig/.gitignore          |    1 +
 scripts/kconfig/Makefile            |   11 +-
 scripts/kconfig/cf_constraints.c    | 1777 ++++++++++++++++++++++++
 scripts/kconfig/cf_constraints.h    |   24 +
 scripts/kconfig/cf_defs.h           |  391 ++++++
 scripts/kconfig/cf_expr.c           | 2003 +++++++++++++++++++++++++++
 scripts/kconfig/cf_expr.h           |  181 +++
 scripts/kconfig/cf_fixgen.c         | 1136 +++++++++++++++
 scripts/kconfig/cf_fixgen.h         |   21 +
 scripts/kconfig/cf_utils.c          |  980 +++++++++++++
 scripts/kconfig/cf_utils.h          |  136 ++
 scripts/kconfig/cfoutconfig.c       |  149 ++
 scripts/kconfig/configfix.c         |  352 +++++
 scripts/kconfig/configfix.h         |   31 +
 scripts/kconfig/expr.h              |   17 +
 scripts/kconfig/loader.gif          |  Bin 0 -> 4177 bytes
 scripts/kconfig/picosat_functions.c |   79 ++
 scripts/kconfig/picosat_functions.h |   35 +
 scripts/kconfig/qconf.cc            |  676 ++++++++-
 scripts/kconfig/qconf.h             |  111 ++
 22 files changed, 8189 insertions(+), 4 deletions(-)
 create mode 100644 scripts/kconfig/cf_constraints.c
 create mode 100644 scripts/kconfig/cf_constraints.h
 create mode 100644 scripts/kconfig/cf_defs.h
 create mode 100644 scripts/kconfig/cf_expr.c
 create mode 100644 scripts/kconfig/cf_expr.h
 create mode 100644 scripts/kconfig/cf_fixgen.c
 create mode 100644 scripts/kconfig/cf_fixgen.h
 create mode 100644 scripts/kconfig/cf_utils.c
 create mode 100644 scripts/kconfig/cf_utils.h
 create mode 100644 scripts/kconfig/cfoutconfig.c
 create mode 100644 scripts/kconfig/configfix.c
 create mode 100644 scripts/kconfig/configfix.h
 create mode 100644 scripts/kconfig/loader.gif
 create mode 100644 scripts/kconfig/picosat_functions.c
 create mode 100644 scripts/kconfig/picosat_functions.h
Signature · 1 line
2.39.5