Editing the wiki to update my project status

[Vegard Nossum]

Hi,

On the main wiki page
(http://kernelnewbies.org/KernelProjects/kconfig-sat) it says:

"""
Previous SAT solver kconfig integration work

A GSoC student claimed to have been accepted to work on integrating a
SAT solver into Linux and announced this on lkml on May 2010 but after
that we never heard back from the student...
"""

That's me, and my project is 95% complete and usable in practice
(though not really ready to be merged). I have a 'make satconfig'
target that gives you a minimal working .config given an incomplete
.satconfig (I am using this in practice for another larger kernel
fuzzing project, so I know it works) and a 'make satmenuconfig' proof
of concept that allows the user to see every menu option and runs the
sat solver for every change you make, though this mode is not quite
finished yet.

I'd like to update the wiki with instructions on how to use my branch,
but it says the page is immutable, so what do I do to edit it?

Thanks,


Vegard

[Luis R. Rodriguez]

On Thu, Mar 03, 2016 at 12:53:14PM +0100, Vegard Nossum wrote:
> Hi,
>
> On the main wiki page
> (http://kernelnewbies.org/KernelProjects/kconfig-sat) it says:
>
> """
> Previous SAT solver kconfig integration work
>
> A GSoC student claimed to have been accepted to work on integrating a
> SAT solver into Linux and announced this on lkml on May 2010 but after
> that we never heard back from the student...
> """
>
> That's me, and my project is 95% complete and usable in practice

Awesome!

> (though not really ready to be merged).

What's left BTW?

> I have a 'make satconfig'
> target that gives you a minimal working .config given an incomplete
> .satconfig (I am using this in practice for another larger kernel
> fuzzing project, so I know it works) and a 'make satmenuconfig' proof
> of concept that allows the user to see every menu option and runs the
> sat solver for every change you make, though this mode is not quite
> finished yet.

Sounds great!

> I'd like to update the wiki with instructions on how to use my branch,
> but it says the page is immutable, so what do I do to edit it?

Did you sign up for an account and log in?

Luis

[Vegard Nossum]

On 3 March 2016 at 18:24, Luis R. Rodriguez <mcg...@kernel.org> wrote:
> On Thu, Mar 03, 2016 at 12:53:14PM +0100, Vegard Nossum wrote:
>> Hi,
>>
>> On the main wiki page
>> (http://kernelnewbies.org/KernelProjects/kconfig-sat) it says:
>>
>> """
>> Previous SAT solver kconfig integration work
>>
>> A GSoC student claimed to have been accepted to work on integrating a
>> SAT solver into Linux and announced this on lkml on May 2010 but after
>> that we never heard back from the student...
>> """
>>
>> That's me, and my project is 95% complete and usable in practice
>
> Awesome!
>
>> (though not really ready to be merged).
>
> What's left BTW?

There's a small issue in the encoding where a selected symbol
sometimes ends up with the value 'm' instead of 'y' -- it's not a big
issue in practice because the kconfig machinery detects it and forces
it to 'y' when writing out the final .config.

There is a testcase (which currently fails) for this specific bug in my branch:

commit 3a019324044ede3c503812cd3dfcaf10e238c1d4
Author: Vegard Nossum <vegard...@oracle.com>
Date: Fri Jan 1 15:03:15 2016 +0100

satconfig: add ASN1 (=m + select) testcase

(from g...@github.com:vegard/linux-2.6.git branch v4.3+kconfig-sat)

It really shouldn't be too difficult to fix, I'm guessing an afternoon
should do it, but it's a big mental effort to jump back into all the
encoding rules and a lot of fiddling around to ensure that everything
else keeps working as it should (but the regression suite really helps
with that).

I also don't support ranges/ints/hex/strings, their values are simply
taken from the defaults, an existing .config, or verbatim from
.satconfig. Again, this is a very minor issue compared to getting all
the stuff with prompts and defaults correct, in the sense that it's
very rare to have expressions involving these types so the actual
benefit of implementing it is very small (in fact, I have to admit I
haven't seen a single case in practice where it was necessary to do
something with these config options). Still something that should be
done before a potential merge, though.

>> I'd like to update the wiki with instructions on how to use my branch,
>> but it says the page is immutable, so what do I do to edit it?
>
> Did you sign up for an account and log in?

Yes. I've attached a screenshot of what I see. Under "More actions"
there is no option to edit either.

Thanks,


Vegard

[Luis R. Rodriguez]

We should feel free to want to limit the scope of kconfig if we find some
issues or limitations with the current design -- the semantics are a bit
loose and that's just due to history. Restricting semantics for the
gain of supporting things better with a SAT solver should be reasonable
specially if we can replace some uses with alternative semantics.

Just be sure to document things well and later if you determine we need this.

BTW I see you're still on v4.3, rebase to Linus will be a big jump
so one thing you can do is to move forward slowly, so you can rebase
onto v4.4 as follows:

git rebase v4.4-rc1
git rebase v4.4-rc2

We go up to v4.4-rc8

For v4.5, we're on v4.5-rc5.

Once on v4.5-rc5 then I'd recommend to just rebase as Linus moves things,
doing this regularly ensures you are always up to date and it means less
work in the end.

> >> I'd like to update the wiki with instructions on how to use my branch,
> >> but it says the page is immutable, so what do I do to edit it?
> >
> > Did you sign up for an account and log in?
>
> Yes. I've attached a screenshot of what I see. Under "More actions"
> there is no option to edit either.

Ah as per the EditorsGroup page [0], it seems I needed to add you there.
I added you on the list but I am not sure if that was enough, can you
logout and back in and test and see if that fixed it.

[0] http://kernelnewbies.org/EditorsGroup

Luis

[Andrzej Wasowski]

This is a bit off topic:

Vegard, what is your kernel fuzzing project? Could you mention something about that? Is there any website? or writing?

Andrzej

--
associate prof. Andrzej Wąsowski, http://www.itu.dk/~wasowski
IT University, Rued Langgaards Vej 7, 2300 Copenhagen, Denmark
room 4D10 phone +45 7218 5086 fax *5001 skype wasowski_andrzej

________________________________________
From: kconf...@googlegroups.com <kconf...@googlegroups.com> on behalf of Vegard Nossum <vegard...@gmail.com>
Sent: Thursday, March 3, 2016 12:53
To: kconfig-sat
Subject: [kconfig-sat] Editing the wiki to update my project status

--
Project details:

http://kernelnewbies.org/KernelProjects/kconfig-sat
---
You received this message because you are subscribed to the Google Groups "kconfig-sat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kconfig-sat...@googlegroups.com.
Visit this group at https://groups.google.com/group/kconfig-sat.
To view this discussion on the web visit https://groups.google.com/d/msgid/kconfig-sat/CAOMGZ%3DEj19BHiiqBqR_q%2B_FD_kSZb7CqGeSmObj8XJRn0oQybg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Vegard Nossum]

On 4 March 2016 at 21:33, Andrzej Wasowski <waso...@itu.dk> wrote:
> This is a bit off topic:
>
> Vegard, what is your kernel fuzzing project? Could you mention something about that? Is there any website? or writing?
>
> Andrzej
>

We are giving a talk about the fuzzing project at Vault 2016:

http://vault2016.sched.org/event/68kL/filesystem-fuzzing-with-american-fuzzy-lop-afl-vegard-nossum-quentin-casasnovas-oracle

Until then, you can have a look at syzkaller (which has found a TON of
kernel bugs already) and AFL:

https://github.com/google/syzkaller
http://lcamtuf.coredump.cx/afl/

syzkaller and AFL both rely on code instrumentation to see what
branches are taken to discover the "interesting" test cases. The
difference (AFAICT, don't quote me on this) is that AFL is more
systematic/deterministic whereas syzkaller simply tries to hit/cover
as much code as possible. So, very simplified, AFL would be better for
things like fuzzing filesystem images whereas syzkaller is better at
discovering race conditions between different system calls.


Vegard

[Daniel Jonsson]

On 03/04/2016 06:57 PM, Luis R. Rodriguez wrote:
> Ah as per the EditorsGroup page [0], it seems I needed to add you there.
> I added you on the list but I am not sure if that was enough, can you
> logout and back in and test and see if that fixed it.
>
> [0]http://kernelnewbies.org/EditorsGroup
>
> Luis

Could you add me too? My username is DanielJonsson.

Thanks,
Daniel

[Luis R. Rodriguez]

Done! Let me know if there are any issues.

Luis

[Daniel Jonsson]

Hi Vegard,

I am working on a project [0] where I am utilizing your code for
building the
propositional constraints and calling PicoSAT with them. I have therefore
examined your implementation and I think it works very well. However, I am
curious about your thoughts on the tristate logic.

To start with, here is a basic Kconfig file which I will save as
`KconfigExample`:

config MODULES
bool "Enable loadable module support"
option modules

config A
tristate "A prompt"

config B
tristate "B prompt"
depends on A

In xconfig and menuconfig, A works as an upper-bound for B. If A is set
to mod,
then B can be set to either no or mod. But if A is set to yes, then B can be
set to no, mod or yes.

Let's create the following .satconfig file:

CONFIG_MODULES=y
CONFIG_A=m
CONFIG_B=y

It contains an error: B cannot be set to yes since A is only set to mod.
If we
run that through satconfig with the commands

$ export KBUILD_KCONFIG=KconfigExample
$ make satconfig

it writes the following .config file:

CONFIG_MODULES=y
CONFIG_A=m
CONFIG_B=y

I.e., satconfig found the configuration to be satisfiable since it ran
successfully without throwing any errors. So there seems to be something
missing in the constructed constraints. I can see that you have written some
good documentation about translating the Kconfig expressions into CNF
formulas
that handle the tristate logic [1], however, I cannot find it being used in
satconf.c [2]. I can also see that you are doing Tseytin transformations
[3] in
the function _add_clauses [4], but I guess it somehow needs to be
extended to
also take the intricate tristate details into consideration. What is
your take
on this? Maybe I have just glossed something over?

Best regards,
Daniel

[0]: https://github.com/matachi/linux/tree/rangefix-c
[1]:
https://github.com/vegard/linux-2.6/blob/v4.3%2Bkconfig-sat/Documentation/kbuild/kconfig-sat.txt
[2]:
https://github.com/vegard/linux-2.6/blob/v4.3%2Bkconfig-sat/scripts/kconfig/satconf.c
[3]: https://en.wikipedia.org/wiki/Tseytin_transformation
[4]:
https://github.com/vegard/linux-2.6/blob/v4.3%2Bkconfig-sat/scripts/kconfig/satconf.c#L460

[Vegard Nossum]

Hi Daniel,

First of all: Sorry for the delay in getting back to you and thank you
so much for looking at my code and the detailed bug report! You are
definitely right: there is a bug.

You've pointed out that if A and B are tristates, then "B depends on
A" has the following "truth table":

+---+---+-------------------+
| A | B | B -> A satisfied? |
+---+---+-------------------+
| n | n | 1 |
| y | n | 1 |
| m | n | 1 |
+---+---+-------------------+
| n | y | 0 |
| y | y | 1 |
| m | y | 0 |
+---+---+-------------------+
| n | m | 0 |
| y | m | 1 |
| m | m | 1 |
+---+---+-------------------+

In particular, in the current implementation, (A=m, B=y) appears to
satisfy "B depends on A", which it shouldn't according to the table.

In my code, the "depends on" constraints are encoded by
build_prompt_visibility_clauses() and expr_to_bool_expr():

static bool build_prompt_visibility_clauses(struct property *prop)
{
struct bool_expr *e[2];
...
/* visible.expr is a conjunction of the menu's dependencies
* (parent menus' "depends on", this menu' "depends on", and the
* "if" part of the prompt). Which is exactly what we need.
*
* For choices, it is a conjunction of the choice block symbol
* and the choice's "depends on". */
if (prop->visible.expr) {
expr_to_bool_expr(prop->sym, prop->visible.expr, e);
} else {
e[0] = bool_const(true);
e[1] = bool_const(false);
}

/* Prompts are visible if and only if
* - the menu is visible ("depends on", etc.)
* - the prompt's dependencies are satisfied (the "if" part) */
assert(prop->sat_variable <= nr_sat_variables);
t1 = bool_eq_put(bool_var(prop->sat_variable), e[0]);
bool_put(e[1]);

...
}

In our example, 'prop' is the prompt for B and 'prop->visible.expr' is
the expression "A".

The function encodes: (B is y or m) iff (A is y or m). Which is a
weaker statement that what we really wanted. Let's set up a Karnaugh
map for the table above:

\zw|
xy\ | 00 01 11 10
----+------------
00 | 1 - 0 0
01 | - - - -
11 | 1 - 1 0
10 | 1 - 1 1

(with x=A_y, y=A_m, z=B_y, w=B_m in the format of kconfig-sat.txt)

So this would make... (¬B_y) ∨ (A_y ∧ B_m) ∨ (A_y ∧ ¬A_m)

Quick verification with a Python script:

n = ('n', 0, 0)
y = ('y', 1, 0)
m = ('m', 1, 1)

for B_kc, B_y, B_m in (n, y, m):
for A_kc, A_y, A_m in (n, y, m):
sat = (not B_y) or (A_y and B_m) or (A_y and not A_m)
print A_kc, B_kc, int(sat)
print '-----'

$ python truthtable.py
n n 1
y n 1
m n 1
-----
n y 0
y y 1
m y 0
-----
n m 0
y m 1
m m 1

This prints the same table as we had above, so that means the (new)
encoding/expressions should be correct.

I haven't checked if this actually gives the same result as
transforming (B depends on A) into (!B or A) in tristate logic and
then encoding that with propositional logic, but I suspect that it
does. That would be a little bit simpler, I guess.

Actually fixing satconf.c is not very straightforward: I've assumed
that "prompt visibility" only needs 1 variable and is sufficient to
encode dependencies, but it seems like what we really want to encode
is for each prompt, what is the maximal value that it allows the
symbol to have (which would need 2 variables per prompt). Then, when
actually determining the value of a symbol, it would have to take a
max() over all its prompts (so that if one prompt is y and another
prompt is m -- for the same symbol -- then the result would be the
maximum over all the prompts' values).

If what I said so far is not very clear, consider this modified example:

config MODULES
bool "Enable loadable module support"
option modules

config A
tristate "A prompt"

config B
tristate "B prompt"

config C
tristate "C prompt 1"
depends on A

config C
tristate "C prompt 2"
depends on B

Here, you can set A=y and B=m and C can be either y or m. So the
dependency doesn't restrict the value of C directly, just the value of
the prompt (which is then used together with all the other prompts for
the same symbol to determine the final value of C).

I'll give fixing satconf.c a shot -- if my head doesn't explode ;-)
Again, thanks for the report!


Vegard

[Vegard Nossum]

On 28 March 2016 at 00:10, Daniel Jonsson <dani...@student.chalmers.se> wrote:

> I.e., satconfig found the configuration to be satisfiable since it ran
> successfully without throwing any errors. So there seems to be something
> missing in the constructed constraints. I can see that you have written some
> good documentation about translating the Kconfig expressions into CNF
> formulas
> that handle the tristate logic [1], however, I cannot find it being used in
> satconf.c [2]. I can also see that you are doing Tseytin transformations [3]
> in
> the function _add_clauses [4], but I guess it somehow needs to be extended
> to
> also take the intricate tristate details into consideration. What is your
> take
> on this? Maybe I have just glossed something over?

I realised didn't quite answer this.

I am reusing the existing kconfig structures for tristate logic
(struct expr, struct symbol, struct prompt, etc.).

The encoding documented in [1] uses two boolean variables V_y and V_m
to represent one tristate variable V. The idea is that V_y is true iff
V is either y or m and V_m is true iff V is m. You can find this all
over the place in satconf.c, usually recognisable by a 2-long array of
struct bool_expr pointers, e.g.:

struct bool_expr *a[2];
a[0] = bool_const(true);
a[1] = bool_const(false);

(This constant specifically represents a tristate value of "y".)

The following functions deal with translating tristate expressions
into boolean expressions:

static void or_expr_to_bool_expr(struct symbol *lhs,
struct expr *in_a, struct expr *in_b, struct bool_expr *out[2]);
static void and_expr_to_bool_expr(struct symbol *lhs,
struct expr *in_a, struct expr *in_b, struct bool_expr *out[2]);
static void not_expr_to_bool_expr(struct symbol *lhs,
struct expr *in, struct bool_expr *out[2]);
static struct bool_expr *equal_expr_to_bool_expr(struct symbol *in_a,
struct symbol *in_b);
static void expr_to_bool_expr(struct symbol *lhs,
struct expr *e, struct bool_expr *result[2]);

The implementations of these functions should at least in theory
mirror the documentation I wrote on translating tristate logic to
boolean logic.

The bug you pointed out is (AFAICT) not a bug in handling the
translation of not/and/or tristate expressions into propositional
logic, but rather in how the final value of a symbol is calculated.
It's rather complicated and messy: each symbol can have multiple
prompts, each prompt places different restrictions on the symbol's
value, prompts should not determine the symbol's value if the symbol
is selected, each prompt can have one or more default values, default
values should not be enforced/used if the symbol is selected, etc.

Also, in my previous e-mail I didn't quite make a distinction between
whether a prompt is visible, whether a prompt is used to set a value
for the symbol, and what restrictions a prompt places on the config
variable. In the current (buggy) code, I use one propositional
variable to encode "prompt is visible", the question now is whether I
should really be encoding something else (like "prompt is visible AND
restricts symbol to be =m").


Vegard

[Luis Chamberlain]

Vegard,

3 years have flown by now. I am curious how things are moving forward,
or not, for your efforts on this front. Brendan is now CC'd, and he is
now interested in this as well. Figured it would be good to pick this
up on a thread which had at least the last known status.

Luis

> --
> Project details:
>
> http://kernelnewbies.org/KernelProjects/kconfig-sat
> ---
> You received this message because you are subscribed to the Google Groups "kconfig-sat" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kconfig-sat...@googlegroups.com.
> Visit this group at https://groups.google.com/group/kconfig-sat.

> To view this discussion on the web visit https://groups.google.com/d/msgid/kconfig-sat/CAOMGZ%3DFmnQwdbfpsvFiPDzFH1rLW19Zm1jht_Ehk%3DLV7r9CKzw%40mail.gmail.com.

[Thorsten Berger]

Hi Luis,

Following up the work of Daniel, my student Patrick Franz (CC) is
working on this currently, with the help of Ibrahim (also CC), both
supervised by Sarah (CC) and me. Patrick had to reimplement the
translation into SAT, since none of the previous ones was accurate
enough to realize a conflict resolution algorithm (remember the
complexity of the Kconfig semantics). The translation is now done, and
we have a UI prototype. Patrick is now working on the
conflict-resolution algorithm, which will work similar to the one in the
eCos CDL configurator tool and the rangeFix tool, but will rely on a SAT
solver (we're planning to use picosat to completely stay in the C
realm). I think we've never been closer to an actual working implementation.

We'll keep you posted, but if so. wants to attend our next supervision
meeting (via Skype), let us know.

Best, Thorsten

--
Thorsten Berger
Associate Professor

Department of Computer Science and Engineering
Chalmers | University of Gothenburg, Sweden
http://www.cse.chalmers.se/~bergert
Tel.: +46 (0) 31 772 6075
Mob.: +46 (0) 729 746 246
Skype: tberger.work

[Thorsten Berger]

(now also with Patrick in CC :) )

[Luis Chamberlain]

That's awesome ! When is the skype session BTW?

Luis

> To view this discussion on the web visit https://groups.google.com/d/msgid/kconfig-sat/97977a8e-927a-e41e-994c-ffc368cbbfa3%40chalmers.se.

[Thorsten Berger]

The next is planned on Juli 10th at 5:30pm CEST (we have the longer
meetings every two weeks, and just had one yesterday ;) ).

Best, Thorsten

[Armin Biere]

I you have issues with PicoSAT let me know (all: build, porting, performance etc.).

The C vs C++ issue is otherwise quite interesting (I have a quote from Donald Knuth who

congratulated me on having C with PicoSAT).

I have moved to C++ with my latest solver (CaDiCaL) because people complained, that

it is hard to change and understand.  Maybe I should reconsider this decision for the next

solver.   CaDiCaL is way superior to PicoSAT but needs a C++ (11 even) build environment.

Armin

To view this discussion on the web visit https://groups.google.com/d/msgid/kconfig-sat/88881469-112a-ddfe-4788-8b4320a3f961%40chalmers.se.

[Thorsten Berger]

Great, thanks for the offer, Armin! We'll let you know.

Best, Thorsten

[Patrick Franz]

Hej Luis,

Am Donnerstag, 27. Juni 2019, 00:12:00 CEST schrieb Luis Chamberlain:
> Vegard,
>
> 3 years have flown by now. I am curious how things are moving forward,
> or not, for your efforts on this front. Brendan is now CC'd, and he
> is now interested in this as well. Figured it would be good to pick
> this up on a thread which had at least the last known status.
>
> Luis

I'm the student doing the implementation under Thorsten's and Sarah's
supervision. Maybe you or anyone else on this list can advise with the
following:

So far I've used plain C and only libraries/functions that were part of
the kernel tree. However this has sometimes resulted in less-than-
optimal code, since C is lacking e.g. advanced datastructures.
I was wondering, if it's acceptable to use external libraries which have
support for more advanced datastructures. One possibility might be
GLib...or maybe someone has a better suggestion ?

Thanks.


--
Med vänliga hälsningar

Patrick Franz

[Luis Chamberlain]

On Wed, Jul 31, 2019 at 11:07 AM Patrick Franz <patf...@gmail.com> wrote:
>
> Hej Luis,
>
> Am Donnerstag, 27. Juni 2019, 00:12:00 CEST schrieb Luis Chamberlain:
> > Vegard,
> >
> > 3 years have flown by now. I am curious how things are moving forward,
> > or not, for your efforts on this front. Brendan is now CC'd, and he
> > is now interested in this as well. Figured it would be good to pick
> > this up on a thread which had at least the last known status.
> >
> > Luis
>
> I'm the student doing the implementation under Thorsten's and Sarah's
> supervision. Maybe you or anyone else on this list can advise with the
> following:
>
> So far I've used plain C and only libraries/functions that were part of
> the kernel tree.

Neat!

> However this has sometimes resulted in less-than-
> optimal code, since C is lacking e.g. advanced datastructures.

Like which ones exactly?

You'd be surprised how many complex data structures have been written
in the kernel in lieu of a libc, for instance. We have linked lists,
radix trees, etc. Every now and then a userspace tool we need to write
creeps up and as kernel developers we tend to want to re-use some of
these data structures implemented in Linux but for userspace, so quite
the opposite problem exists. This has persisted for years now and so
-- we now have a userspace port of all of these, refer to
tools/include/linux/list.h, as an example, so any tools/include/*
stuff. There is no rule though that if you write something for the
kernel you *must* write a userspace port, in fact, what exists in
tools is more as best effort. And yet more and more tools have been
using these helpers.

> I was wondering, if it's acceptable to use external libraries which have
> support for more advanced datastructures. One possibility might be
> GLib...or maybe someone has a better suggestion ?

The reason for the goal to only use C is the possible potential to
also use the code later elsewhere, say, in-kernel. Even if we restrict
the use-case to be fully in userspace, say for kconfig -- it'd be
rather difficult requirement to get folks to agree to have now
configure the kernel. However we tools under tools/ which does use
external libraries, so its certainly possible for userspace.

Its just that if and when possible it be great to not have to. And if
we ever wish to make code usable in-kernel, then yeah, no libraries at
all. Just plain ol' C. But you can technically add new data
structures. Would it suffice to port / add ones that you need so that
they can be used in plain C ?

Luis

[Patrick Franz]

Hej Luis,

Am Mittwoch, 31. Juli 2019, 21:55:41 CEST schrieb Luis Chamberlain:
[...]

> > However this has sometimes resulted in less-than-
> > optimal code, since C is lacking e.g. advanced datastructures.
>
> Like which ones exactly?
>
> You'd be surprised how many complex data structures have been written
> in the kernel in lieu of a libc, for instance. We have linked lists,
> radix trees, etc. Every now and then a userspace tool we need to write
> creeps up and as kernel developers we tend to want to re-use some of
> these data structures implemented in Linux but for userspace, so
> quite the opposite problem exists. This has persisted for years now
> and so -- we now have a userspace port of all of these, refer to
> tools/include/linux/list.h, as an example, so any tools/include/*
> stuff. There is no rule though that if you write something for the
> kernel you *must* write a userspace port, in fact, what exists in
> tools is more as best effort. And yet more and more tools have been
> using these helpers.

A dynamic array (a list would probably also do) and a hash-map for
starters.

> > I was wondering, if it's acceptable to use external libraries which
> > have support for more advanced datastructures. One possibility
> > might be GLib...or maybe someone has a better suggestion ?
>
> The reason for the goal to only use C is the possible potential to
> also use the code later elsewhere, say, in-kernel. Even if we restrict
> the use-case to be fully in userspace, say for kconfig -- it'd be
> rather difficult requirement to get folks to agree to have now
> configure the kernel. However we tools under tools/ which does use
> external libraries, so its certainly possible for userspace.
>
> Its just that if and when possible it be great to not have to. And if
> we ever wish to make code usable in-kernel, then yeah, no libraries at
> all. Just plain ol' C. But you can technically add new data
> structures. Would it suffice to port / add ones that you need so that
> they can be used in plain C ?

So I could just take those 5-6 files I need from GLib and copy them into
a sub-directory of 'scripts/kconfig' ?

[Luis Chamberlain]

On Wed, Jul 31, 2019 at 2:13 PM Patrick Franz <patf...@gmail.com> wrote:
>
> Hej Luis,
>
> Am Mittwoch, 31. Juli 2019, 21:55:41 CEST schrieb Luis Chamberlain:
> [...]
> > > However this has sometimes resulted in less-than-
> > > optimal code, since C is lacking e.g. advanced datastructures.
> >
> > Like which ones exactly?
> >
> > You'd be surprised how many complex data structures have been written
> > in the kernel in lieu of a libc, for instance. We have linked lists,
> > radix trees, etc. Every now and then a userspace tool we need to write
> > creeps up and as kernel developers we tend to want to re-use some of
> > these data structures implemented in Linux but for userspace, so
> > quite the opposite problem exists. This has persisted for years now
> > and so -- we now have a userspace port of all of these, refer to
> > tools/include/linux/list.h, as an example, so any tools/include/*
> > stuff. There is no rule though that if you write something for the
> > kernel you *must* write a userspace port, in fact, what exists in
> > tools is more as best effort. And yet more and more tools have been
> > using these helpers.
>
> A dynamic array (a list would probably also do)

tools/include/linux/list.h

> and a hash-map for
> starters.

Would this do it? tools/include/linux/hashtable.h

Current users in tools:

mcgrof@phoebe ~/linux-next (git::master)$ git grep hash_init tools
tools/bpf/bpftool/main.c: hash_init(prog_table.table);
tools/bpf/bpftool/main.c: hash_init(map_table.table);
tools/include/linux/hashtable.h:static inline void __hash_init(struct
hlist_head *ht, unsigned int sz)
tools/include/linux/hashtable.h: * hash_init - initialize a hash table
tools/include/linux/hashtable.h: * same as hash_init_size.
tools/include/linux/hashtable.h:#define hash_init(hashtable)
__hash_init(hashtable, HASH_SIZE(hashtable))
tools/objtool/check.c: hash_init(file.insn_hash);
tools/objtool/elf.c: hash_init(sec->rela_hash);
tools/objtool/elf.c: hash_init(sec->symbol_hash);
tools/objtool/elf.c: hash_init(sec->rela_hash);

So I guess you can see if how objtool and bfp use it are a good
example which matches your criteria. Or these articles covers them
pretty well:

https://kernelnewbies.org/FAQ/LinkedLists
https://kernelnewbies.org/FAQ/Hashtables
https://lwn.net/Articles/510202/

> > > I was wondering, if it's acceptable to use external libraries which
> > > have support for more advanced datastructures. One possibility
> > > might be GLib...or maybe someone has a better suggestion ?
> >
> > The reason for the goal to only use C is the possible potential to
> > also use the code later elsewhere, say, in-kernel. Even if we restrict
> > the use-case to be fully in userspace, say for kconfig -- it'd be
> > rather difficult requirement to get folks to agree to have now
> > configure the kernel. However we tools under tools/ which does use
> > external libraries, so its certainly possible for userspace.
> >
> > Its just that if and when possible it be great to not have to. And if
> > we ever wish to make code usable in-kernel, then yeah, no libraries at
> > all. Just plain ol' C. But you can technically add new data
> > structures. Would it suffice to port / add ones that you need so that
> > they can be used in plain C ?
>
> So I could just take those 5-6 files I need from GLib and copy them into
> a sub-directory of 'scripts/kconfig' ?

"Copying" is possible if the license is compatible with the licenses
we accept in the Linux kernel, what license are they under? But
copying over stuff like that would only be *reasonable* for inclusion
upstream if and only if proper due diligence was done to ensure
nothing already present suits your needs. And if we have something
already close to it, could it be just extended a bit? And even if you
do copy them, typically we want to have code follow upstream Linux
coding standards, so you'd likely need to massage it to fit the style
used in Linux.

So, I'd try to see if the above would work first.

Luis

[Luis Chamberlain]

Another set of data structures is resizable hash table rhashtable:

https://lwn.net/Articles/751374/

However this one has no tools/ (userspace) port yet. But if you need
it, you can do the port. Its typically easy to do unless it relies on
something else which has not yet been ported. Most of the work of
porting involves doing away with some kernel optimizations too, which
may not apply to userspace.

Luis