A new mechanism to compiler kernel modules using llvm: Defer type evaluation in clang?

Hi,

First of all, I didn't study on compiler too much, I'm a Linux kernel developer,
Now I have one idea about compile kernel module by using llvm framework.

In Linux world, traditionally compile Linux kernel module only have one way:
compile it to machine code directly, deploy to target machine, then
run it in target machine.

This have some problem from long term view, especially kernel module
compatibility issue,
we know that Linux kernel change fast, when kernel change the data
structure exposed to external
kernel modules, then all ko depend on that data structure will need
recompile, one case is
kernel upgrade.
This is really a problem, we already suffered it many years, in whole
Linux world.
Linux distribution suffer it, third party kernel modules developers suffer it.
hardware driver developers also suffer it, we cannot avoid re-compile
kernel modules whenever new kernel
release if the structure changed, why? because kernel modules depend
on kernel header data structure, this is the point.

Is there have any method to fix it? let's try to decouple kernel
modules with kernel, by using llvm.
Please give comments on following mechanism, 3 steps:

1) kernel modules developer compile C file into high level IR, not to
machine code.

2) In install time, the high level IR file "link" with kernel header
data structure file, generate low level
IR file, it could be .bc or .ll file in llvm form.

3) llvm compile the low level IR file into machine code in target
machine, then insert kernel modules, run it.

Using this method, kernel module code is not need to change when
kernel header file change, because it evaluate
structure type info at install time, not C code compile time. it fix
compatibility issue in a clean way.
The key point of this method is we need defer structure type
evaluation into install time, Is Clang support
this "feature" at present?

How about this idea sounds? I really think llvm design is nature to
suit this idea, benefit from llvm's IR.
If we really implement this idea, it would be very valuable for whole
Linux community, trust me:)

I would appreciate if you can give me some technical comments on this design.
Thanks very much.

.jovi

Just out of curiosity, what would be the main benefit of this approach vs DKMS which is already widely used ?

I am not sure this would work. It might be able to handle changes in structure, but what about changes in the accessor functions?
I also don’t see how this would be easier than compiling from source on the target machine. You still need all the kernel headers on the target machine because llvm with your patch would need them so that it uses the correct structure.
The best approach for kernel stuff is to get the source code into mainline, then the source code will be kept up to date for you.

Thanks Dupas.

I checked DKMS you mentioned, basically DKMS is just a ko and its
sources management tool.

It's not easy to deploy ko source into target machine, and it's more
harder to build ko in target machine,
this is a very common case, especially in embedded Linux, you really
cannot put source into target device,
for example, you didn't see any kernel module source in android phone, right?

What I really want to see is kernel module source don't need to to
change when kernel changes, whatever kernel
upgrade or minor structure change, DKMS cannot meet this.

what's the benefit of that?

we can replace kernel as we want, and don't need to worry ko cannot
work in new kernel, this is the true decouple,
not the decouple implementation in DKMS claimed.
Imaging that you want upgrade the android kernel to kernel mainline by
yourself, you really could do this if using the mechanism
I said, but you definitely cannot achieve this currently or use DKMS.

Another case is fast kernel debugging, just replace kernel, to check
functionality or performance in new kernel, without ko recompile,
ko may provided by different vendor, we cannot contact every vendor to
request they deliver new ko to let us try our new kernel.

I am not sure this would work. It might be able to handle changes in
structure, but what about changes in the accessor functions?

function change is not a big deal, take a example, one function
referenced in ko,
but not exist in new kernel, how could we replace new kernel in this case?
This is not a compatibility issue, because we can add some
compatibility code into new kernel
to maintain old functions for those old ko, so in this case, we still
not need to rebuild ko, right?

The case I really want to solve is some kernel change cause ko must
need to recompile,
like data structure field offset changed in new kernel, this will make
offset mismatch between new kernel
and old ko.

This is the reason why I want to delay type structure evaluation into
install time in Clang,
In theory, ko compiled now could work in 10 years later whatever how
kernel changes.

I also don't see how this would be easier than compiling from source on the
target machine. You still need all the kernel headers on the target machine
because llvm with your patch would need them so that it uses the correct
structure.

We cannot deliver source into target machine. :slight_smile:
the new method don't need kernel headers in target machine, it just
need a KABI file(whatever binary or text form),
for linking with high-level IR file which compiled by ko source,
output is the low level IR file could accept by llvm,
this is the key design.

The best approach for kernel stuff is to get the source code into mainline,
then the source code will be kept up to date for you.

I hope that, but you know, this is not possible to put all hardware
driver and all company private ko into upstream. :slight_smile:

This kind of fix is not possible with LLVM IR right now and generally not possible with C code ever unless you make a lot of simplifying assumptions. Note that, for example, offsetof and sizeof are resolved to a constant by Clang before they are ever lowered to LLVM IR in the first place. Also, the way that structs are referenced in LLVM IR do not satisfy binary compatibility: a struct is lowered to a sequence of its constituent members accessed by their index and not be a given name. This means that inserting a member into the struct invalidates the IR.

We arrived the key part: offsetof and sizeof are resolved to a
constant by Clang before
they are lowered to LLVM IR, so that's the main reason why there have
a high-level IR file except
LLVM IR file, that high-level IR file contain unresolved structure
field reference info and unresolved
sizeof, that high-level IR file "link" with kernel header ABI file
which contain structure offset and sizeof info,
then generate to LLVM IR file, this is the design picture.

I don't want to change LLVM IR format, I'm just thinking on hack Clang
to output that high-level IR file without
resolved offset/sizeof info, how about this sounds?

I think that is much less feasible then it sounds. Since offsetof/sizeof are both compiled to a constant, they are both compile-time constants. In particular, you can do things in C like:

#if sizeof(T) == 10

#endif

This means that the only truly portable way to late-resolve offsetof/sizeof is to save the source code of the program and compile it as late as possible. I’m skeptical that you could convince all the stakeholders you would need to support this approach, especially since you are probably neither willing to implement any optimizations on your “high-level IR” nor able to make it close enough to LLVM IR to reuse LLVM’s optimization passes–as a result, you would pretty much be distributing the source code to your driver module, just without the comments and less resilient to kernel changes than the original source.

We arrived the key part: offsetof and sizeof are resolved to a
constant by Clang before they are lowered to LLVM IR, so that's the
main reason why there have a high-level IR file except LLVM IR file,
that high-level IR file contain unresolved structure field reference
info and unresolved sizeof, that high-level IR file "link" with
kernel header ABI file which contain structure offset and sizeof
info, then generate to LLVM IR file, this is the design picture.

I don't want to change LLVM IR format, I'm just thinking on hack
Clang to output that high-level IR file without resolved
offset/sizeof info, how about this sounds?

I think that is much less feasible then it sounds. Since offsetof/sizeof are
both compiled to a constant, they are both compile-time constants. In
particular, you can do things in C like:

#if sizeof(T) == 10
...
#endif

Thanks Joshua, you comments is quite technical valuable.

I have to admit that putting sizeof into #if guard is a problem
against with my design,
but I think we can afford it, since there must have some workaround to
not write code like that in ko.
so if possible, code cannot compile if ko is writing code like that.

This means that the only truly portable way to late-resolve offsetof/sizeof
is to save the source code of the program and compile it as late as
possible. I'm skeptical that you could convince all the stakeholders you
would need to support this approach, especially since you are probably
neither willing to implement any optimizations on your "high-level IR" nor
able to make it close enough to LLVM IR to reuse LLVM's optimization
passes--as a result, you would pretty much be distributing the source code
to your driver module, just without the comments and less resilient to
kernel changes than the original source.

Currently the idea is in design phase, so there may have many
possibility in final.

I hope the high-level IR file form is similar with LLVM IR, so it
would be simple to
link with kernel abi file, also I want it to be a IR form far from source code.
The main problem is structure offset/sizeof resolving.

I took many implementation design idea in mind, like use ffi library
in runtime, so it wouldn't be
engaging with compiler modification, but this cannot solve kernel
structure type fast reference problem.
I also thought about use some high-level language like Golang/Rust to
write kernel module,
then also have the type reference problem, and it will have problem if
those language have different
memory mode with C. writing kernel module in interpreter or JIT
statically typed language, like java,
but the performance will not accept by community.

So that's why I don't want to change the language of kernel module
currently, at least without big change
or limitation. LLVM meet my requirement mostly, mainly because it's
low level IR design,
LLVM is most near my solution at present :slight_smile: isn't it?

You can write that, but it almost certainly doesn't mean what you appear to think it means...

David

Hi,

First of all, I didn't study on compiler too much, I'm a Linux kernel developer,
Now I have one idea about compile kernel module by using llvm framework.

In Linux world, traditionally compile Linux kernel module only have one way:
compile it to machine code directly, deploy to target machine, then
run it in target machine.

This have some problem from long term view, especially kernel module
compatibility issue,
we know that Linux kernel change fast, when kernel change the data
structure exposed to external
kernel modules, then all ko depend on that data structure will need
recompile, one case is
kernel upgrade.
This is really a problem, we already suffered it many years, in whole
Linux world.
Linux distribution suffer it, third party kernel modules developers suffer it.
hardware driver developers also suffer it, we cannot avoid re-compile
kernel modules whenever new kernel
release if the structure changed, why? because kernel modules depend
on kernel header data structure, this is the point.

The basic idea seems feasible, but I think this is a "devil in the details" sort of project. As Joshua has pointed out, there are certain constructs you can't use (such as sizeof() in preprocessor #if statements), and I think you'd need to enhance the LLVM IR to represent unknown structure sizes symbolically. There is also the fact that the Clang frontend generates architecture-specific code and that there are LLVM optimizations that use the size of structures for optimization. That is all stuff that your project would have to "fix." You'd be swimming against a strong current, so to speak.

More importantly, while you raise a number of limitations of linking native code for kernel modules, I don't think the Linux community sees this is a disadvantage. Rather, they see it as a way of encouraging developers to open-source their drivers and have them included in the Linux kernel tree. I'm not convinced that you'd get buy-in from the Linux community.

If this sort of project interests you, then I think you should aim for something smaller and that has more interest. For example, I think the NaCL developers at Google were looking at ways to make the LLVM IR more suitable as a format for shipping NaCL plugins. If that hasn't been done yet, it's an easier problem to tackle, and there is a group that is already interested in having it.

Finally, as a shameless plug, your project idea reminds me of the LLVA work that was done here at Illinois (which became the foundation for my own research on the Secure Virtual Architecture). That work aimed to replace the processor native instruction set with the LLVM IR to allow the processor to adapt without requiring manual recompilation of software. You can find those papers on the llvm.org publications page if you're interested.

-- John T.

I sounds me that you are just substituting "compile C source file" for
"compile LLVM IR source file" or "compile LLVM IR .o file"
The problem is you wish to link in the linux kernel headers at "install" time.
The problem I see is that the linux kernel headers are C source files,
so how is that going to work?
You need a C compiler to understand the Linux kernel headers.

Hello,
Based on my many years of lurking on linux kernel development lists, IMHO,
that is never going to happen. You need the full support of the linux kernel
development community to succeed with your goal. You need to be talking to
the linux kernel development community. You are on the wrong list.

Folks who are truly linux kernel experts have no problem with embedded development
environments. In my experience, linux server environments are orders of magnitude
more complex than embedded environments. True linux kernel experts don't even use
debuggers.

Of course I wish you well with your efforts. But you need to fully grasp the ethos
of the linux kernel development community, before you can succeed at such a goal.

enjoy,
Karen

Thanks, not that complicated.
We indeed need to handle kernel header file in install time, but not
the raw header .h file,
likely it will be a raw text file include all structure offset/sizeof
info, this is the file I called
as kernel ABI file, its size is small in target machine.

whatever how this raw text generated, that's not the core part of design.

Hi,

First of all, I didn't study on compiler too much, I'm a Linux kernel
developer,
Now I have one idea about compile kernel module by using llvm framework.

In Linux world, traditionally compile Linux kernel module only have one
way:
compile it to machine code directly, deploy to target machine, then
run it in target machine.

This have some problem from long term view, especially kernel module
compatibility issue,
we know that Linux kernel change fast, when kernel change the data
structure exposed to external
kernel modules, then all ko depend on that data structure will need
recompile, one case is
kernel upgrade.
This is really a problem, we already suffered it many years, in whole
Linux world.
Linux distribution suffer it, third party kernel modules developers suffer
it.
hardware driver developers also suffer it, we cannot avoid re-compile
kernel modules whenever new kernel
release if the structure changed, why? because kernel modules depend
on kernel header data structure, this is the point.

The basic idea seems feasible, but I think this is a "devil in the details"
sort of project. As Joshua has pointed out, there are certain constructs
you can't use (such as sizeof() in preprocessor #if statements), and I think
you'd need to enhance the LLVM IR to represent unknown structure sizes
symbolically. There is also the fact that the Clang frontend generates
architecture-specific code and that there are LLVM optimizations that use
the size of structures for optimization. That is all stuff that your
project would have to "fix." You'd be swimming against a strong current, so
to speak.

Thanks.

From LLVM's point of view, the design I described could be interpreted as:

     "Implementing Portable sizeof, offsetof and Variable Sized
Structures in LLVM"

It's a random LLVM notes at:
    http://nondot.org/sabre/LLVMNotes/
    http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt

Basically the note wrote in there will solve main part of my problem,
only another problem
is structure field name need pass into IR file, I don't think it's a
hard technical problem, we have choose
many way to solve this, even put structure field name as comments into IR file.

Look, it's not that complicated, what we need is implementing a
portable sizeof/offsetof in LLVM,
and most likely my design is only another use case for this "portable
sizeof/offset" feature.

More importantly, while you raise a number of limitations of linking native
code for kernel modules, I don't think the Linux community sees this is a
disadvantage. Rather, they see it as a way of encouraging developers to
open-source their drivers and have them included in the Linux kernel tree.
I'm not convinced that you'd get buy-in from the Linux community.

Your opinion is same as Karen Shaeffer.
We cannot upstream all kernel modules source code into mainline, this
is not simply a
technical problem or community problem, I believe that every company
have its own
kernel module which cannot upstream, or not worthwhile, if the company
is working
on kernel module development. upstream kernel modules just is a small
part of all kernel
modules in Linux world, this is the truth we need admit it.

> Just out of curiosity, what would be the main benefit of this approach vs DKMS which is already widely used ?
>
Thanks Dupas.

I checked DKMS you mentioned, basically DKMS is just a ko and its
sources management tool.

It's not easy to deploy ko source into target machine, and it's more
harder to build ko in target machine,
this is a very common case, especially in embedded Linux, you really
cannot put source into target device,
for example, you didn't see any kernel module source in android phone, right?

What I really want to see is kernel module source don't need to to
change when kernel changes, whatever kernel
upgrade or minor structure change, DKMS cannot meet this.

Hello,
Based on my many years of lurking on linux kernel development lists, IMHO,
that is never going to happen. You need the full support of the linux kernel
development community to succeed with your goal. You need to be talking to
the linux kernel development community. You are on the wrong list.

Thanks karen.
Main implementation part is engaging with LLVM, not the kernel, that's
why I send it to here firstly.
I'm also on the LKML many years, and I know how they will say:
"Just upstream your kernel module"

the point is "upstream my kernel module" doesn't fix the problem I
want to solve:
kernel module binary compatibility issue.

(Possibility I will involve LKML in some day as you suggest, thanks:) )

Thanks James.

I can list hundreds of reasons on why there exist out of tree kernel modules:
code quality is not good to upstream;
kernel community think the feature is not very common, so it's not
worth to upstream;
kernel community reject the kernel modules;
company don't want to assign a long term module maintainer;
company don't want to release kernel modules source, kernel allow for
this(see EXPORT_SYMBOL);
the functionality is duplicated in mainline, but company must maintain
the interface for old customers;
company have many kernel version product, so it have to maintain
different modules sources, but mainline only maintain one version.
many famous open source kernel modules also not upstream, like
Systemtap from redhat, why this happen?
...

The truth is there, many kernel modules is out of tree, why we need to
argue this truth?

Frankly, we have a little out of topic now, I guess you don't have
engaged this kernel module
binary compatibility issue before, the world is not that simple as
upstream can solve anything.

(Look Microsoft, is all drive company upstream the driver source to
Microsoft? to solve driver compatibility issue)

Let's back to original topic: how to use LLVM mechanism to solve
kernel module binary compatibility issue in a good way?

Thanks.

Hi,

First of all, I didn't study on compiler too much, I'm a Linux kernel
developer,
Now I have one idea about compile kernel module by using llvm framework.

In Linux world, traditionally compile Linux kernel module only have one
way:
compile it to machine code directly, deploy to target machine, then
run it in target machine.

This have some problem from long term view, especially kernel module
compatibility issue,
we know that Linux kernel change fast, when kernel change the data
structure exposed to external
kernel modules, then all ko depend on that data structure will need
recompile, one case is
kernel upgrade.
This is really a problem, we already suffered it many years, in whole
Linux world.
Linux distribution suffer it, third party kernel modules developers suffer
it.
hardware driver developers also suffer it, we cannot avoid re-compile
kernel modules whenever new kernel
release if the structure changed, why? because kernel modules depend
on kernel header data structure, this is the point.

The basic idea seems feasible, but I think this is a "devil in the details"
sort of project. As Joshua has pointed out, there are certain constructs
you can't use (such as sizeof() in preprocessor #if statements), and I think
you'd need to enhance the LLVM IR to represent unknown structure sizes
symbolically. There is also the fact that the Clang frontend generates
architecture-specific code and that there are LLVM optimizations that use
the size of structures for optimization. That is all stuff that your
project would have to "fix." You'd be swimming against a strong current, so
to speak.

Thanks.

From LLVM's point of view, the design I described could be interpreted as:
      "Implementing Portable sizeof, offsetof and Variable Sized
Structures in LLVM"

It's a random LLVM notes at:
     http://nondot.org/sabre/LLVMNotes/
     http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt

Basically the note wrote in there will solve main part of my problem,
only another problem
is structure field name need pass into IR file, I don't think it's a
hard technical problem, we have choose
many way to solve this, even put structure field name as comments into IR file.

Look, it's not that complicated, what we need is implementing a
portable sizeof/offsetof in LLVM,
and most likely my design is only another use case for this "portable
sizeof/offset" feature.

Good point. What I'd recommend you do is write a proposal for supporting those features and list several applications of that feature (portable kernel modules being one such application). That will give your proposal a better chance at being accepted; the more potential uses of your work there are, the more likely a reviewer will find one use which he or she cares about and think favorably of the proposal.

More importantly, while you raise a number of limitations of linking native
code for kernel modules, I don't think the Linux community sees this is a
disadvantage. Rather, they see it as a way of encouraging developers to
open-source their drivers and have them included in the Linux kernel tree.
I'm not convinced that you'd get buy-in from the Linux community.

Your opinion is same as Karen Shaeffer.
We cannot upstream all kernel modules source code into mainline, this
is not simply a
technical problem or community problem, I believe that every company
have its own
kernel module which cannot upstream, or not worthwhile, if the company
is working
on kernel module development. upstream kernel modules just is a small
part of all kernel
modules in Linux world, this is the truth we need admit it.

I don't agree with the idea that the Linux kernel should change its kernel module API arbitrarily, but that is the policy and intent that the Linux kernel developers appear to have. If your proposal requires changes to the Linux kernel to get this to work, then I think your project has a serious adoption problem because the kernel developers may not want to upstream the changes necessary to make your solution work.

If your proposed solution does not require any Linux kernel changes, then you should state that explicitly in your proposal.

The reason that people here are concerned with the Linux community's philosophy is that they want to see a realistic plan for your work to get adopted. If some Linux kernel development policy/philosophy is going to complicate adoption, it hurts your proposal.

In summary, I think you can strengthen your proposal by doing the following:

1) Make the focus of your proposal be the variable offset and sizeof features in LLVM IR.

2) Argue that variable offset and sizeof features have several interesting uses, including portable kernel modules for Linux (and other operating systems) and any other applications you can think of.

3) Describe how you will address the technical challenges. How will you handle all the optimizations that use DataLayout to make non-portable LLVM IR transformations? Will you need to add support to the Clang frontend, and if so, what? Will you handle the use of sizeof() in preprocessor macros, or is that feature so seldom used that you can ignore it?

I think doing those things will give you a better chance of getting your proposal accepted.

-- John T.

Thanks, john, your suggestion is very helpful for me.

I will review my design more detail, then I will follow your guide.

.jovi