The next speaker is going to be talking to us about Macros gone wild.
Good morning.
The original alternative title for this talk was you are not expended to understand this
after a famous comment that appeared the sixth edition of the research Unix.
Who of you are familiar with what the CPU processor does?
Okay.
Most so I will skip that it does a source file inclusion, macro replacement,
conditional compilation and other stuff and that we will just move into problems.
Garnet's throw stroke described the pre-process as a constant problem to
probabilities, maintainers, people reporting code and tool builders.
And this indeed the case is faced by this thing from the compiler.
And therefore it's difficult to analyze when you see a syntax error in the compiler.
You don't know how the pre-processor changed the code and that made that error appear.
It's difficult to reason about.
Confuses the C grammar and the semantics you can have parts that are distinct from the C grammar.
The conditional compilation confuses testing and source associated with many traps and pitfalls.
Books are on the use of C programming language.
This is how to use the pre-processor.
So properly otherwise you will get the burnt and crash.
So what I will look at is how the pre-processor is used in the Linux kernel.
And specifically examine four things.
First of all the usage characteristics.
The extent it is used in the Linux kernel.
Second I will and I will most focus.
I will discuss the introduced technical depth.
We'll see how it has changed over time.
And finally we'll discuss the feasibility of this reducing this technical depth.
Things that make it difficult to switch the pre-processor makes our life difficult.
Especially the feasibility of using Rust as an alternative method for doing many of the things that
Microsoft do nowadays.
For this study I use the tool called the C scout.
This is a refactoring browser for C code.
So it ingest C code allows you to study it.
Taking to account the full semantics and tokens of the pre-processor.
So when you see the code and you click on a token it goes back to the token's definition in a
Macro for example.
Even if this has been defined in a way that there is uses the pre-processor.
So it performs both the semantics and that analysis of the code.
And I have extended this to collect a number of metrics.
What happens before the pre-processor and after the pre-processor.
Both at the end of each function and at the end of each file.
And I also added functionality to measure keywords and some other metrics
have to do with the complexity of the code.
I've analyzed the three kernels which you see here.
Paste about 10 years.
In the 10 years the distance the most recent one is 6.10 in July last year.
And as you see there, the number of lines has been released from
4,000 lines to 23,000 lines files.
C files nowadays.
And similarly the number of lines has been released from 5 million lines to 24 million lines of which I analyzed
20 billion lines because I analyzed only a single architecture.
And the one configuration the most complete configuration of all config.
As you can see on the bottom, this required considerable resources.
More than a week of processing time for the latest kernel and large amount of memory,
113 gigabytes.
The analysis was not easy for the two versions.
For the early versions it cannot be analyzed with a modern GCC.
I'm installing no GCC on a modern Linux was in practical.
And also the 32-bit RAM capacity was insufficient to run a C scout.
For this I used QMU and Hypervisor Accelerator.
I had to force the use of deprecated crypto in order to be able to access
a section to the hyper via into the MU later.
And used architect packages because could otherwise
could not install what was required.
And therefore I compiled it on the QMU and then I analyzed it on a powerful host.
For the 6.10 there isn't a version it required more than a week of processing
which by running it again again would take months.
And also a lot of RAM and for this I utilized the super computer.
I split the task into 32 tasks running in parallel and several 32 super computer nodes.
And then I developed a procedure to merge the results on a powerful
node number of different ways to do it
through SQL recursive queries.
Couldn't do it.
I could not merge graphs.
In the end I developed a command in C scout to merge the parts as you see here.
I performed a binary tournament merge 32 processes running in parallel.
These were reduced and hour and a half later and again in two hours
and the three hours the results were almost the merging results were almost ready.
So now we'll describe the findings for the most recent version 6.10.1.
And later I will give some examples of what happened before that time.
So how is the preprocessor used extensively?
33% of the defined functions are defined.
It looks like a function.
It's a macro.
72% of what is defined as an identifier is a macro identifier.
And when you look at the usage 44% of when you see a function call,
it's actually a macro behind it.
And if you see an identifier actually 44% again it is a macro identified.
Also interesting 94% of the macro identifiers are never used.
This is not that bad because most of these definitions have to do with the hardware constants
and I think it's good to define them for the sake of completion.
It's rather than leaving gaps in having people wonder whether we've forgotten something or not.
The distribution of preprocessor, the electives varies among various areas of the kernel.
So we see that in the main part of the cancer on the kernel directory
we see a large number of conditionals probably because the kernel has to serve many purposes,
many architectures and the configurations.
We see under drivers that conditionals are used very little,
probably because drivers target a very specific configuration.
And also on the architecture part arch, then we have a large number of filing clues.
I'm not sure why.
If we look at the expansion, what the expansion, the simply processor,
it does with the expansion, we see that the number of tokens used doubles
from 2,000 to 4,000 per file.
And there are some explosions to 3 million tokens post expansion.
The same number of statements or declarations
that the compiler sees, it rises from 170 to 300.
And the number of operators from 300 to 760.
Also the if statements increase from 23 to 36 per unit looked.
And also there's a huge number of increase in the number of go-to labels,
but this happens for a very specific purpose.
So I know why.
You 32 and you 16 also are part of labels.
So this conflates those things.
Why is this?
But let me give you some reasons.
Name space pollution at the beginning of its function.
We have 106 global namespace occupants.
Identifies that are visible there.
That's the median value.
Also each marker is used in 81 files, so it's used a lot.
And the 10 most used frequently defined macro names
are defined 30,000 times.
So the same macro name is defined again again in various functions.
30,000 times.
And these are used 152,000 times in 2000 files.
Another thing that happens is namespace confusion.
Look at this dream, but there are many of these.
For example, this defiles BCH.
Our log fills as a macro.
Doing something X with reads time and some value.
Later on this is redefined.
X is defined to create a name out of what happens before.
What of the name?
And creates new names.
And these are become part of an enumeration.
As you see here by invoking this macro.
And later on again, X is defined in a different way.
BCH log fills is called again,
again, invoked again as a macro.
And these accesses members of a structure.
So at the same time, the same identifier must be part of a structure
member and also part of the name here that is defined
in the generated dynamically through token pasting.
I've looked at all areas of confusion.
And you see here that the markers are become also
in time members of enumeration.
Parts of labels, parts of structure or union members,
or structure union tags, or ordinary identifiers.
So these are confused between things that the simple programming language
considers separator in theory separate namespaces.
But macros confused the two.
So if you change a structure or union tag,
you may also need to change the corresponding go to label.
And another thing is that in the coding style,
there are actually forbidden, but it actually happens.
So macros should not affect control for it.
You're not, it's not good to return from a macro.
And there should also access not access local variables
if defined outside of a function.
And yet here's an example of scoping confusion.
This macro here uses BCH, defined outside the function.
200 lines later, we have a definition of BCH.
21 lines later, this macro is involved using this BCH value.
Control flow confusion.
And this happens 3,000 to 7,700 times this happening.
Control flow confusion, you see here again this macro that returns something.
And later on it's called 77 lines later, it's called,
and this return happens automatically.
This doesn't happen a lot.
I found 12 instances of continue.
40 of break 80 go to which are but troubling
and 97 return statements in such macros defined outside functions.
When I gave this talk at ETH, can I develop it?
Yes, yes, yes, yes, but these are the people working on drivers.
And not with don't do it in the kernel directory.
Actually check after that.
And you see here what happens in the kernel, these violations.
And invariable scope actually happens more under the kernel directory.
Another thing are hybrid call paths.
So the case where we don't have C functions calling C functions,
which is the most common or C functions calling macros.
But more complicated stuff, we have instances of macros calling other macros.
And there are almost half a million like 3 chains of C functions calling
another C function via a macro.
If you try to look at this in the debugger, you will not find it.
If you create the call graph using the object file definitions,
you will not find this calls through the macro.
You will find them directly inexplicably so,
because this will not appear thus in the source code.
Another thing that this actually made me study this thing is expansion explosion.
So about 500 files expand to more than 1,000 per cent.
The median is 87%.
And there are found 30 outliers that take 14 seconds to compile,
whereas most files compile in less than 2 seconds.
Let me show you an example here.
This is a file set up dot C from x86 Zen.
It's about 1,000 lines, 26 kilobytes.
When I expand it becomes 50 megabytes, 88,000 lines.
It takes about 7 minutes to compile and 3 gigabytes of RAM.
And I will try to zoom here.
So what I like to see here is the file.
On the right we see where I am, it's very small dot.
And now I'm zooming, moving a bit up and zooming again.
And zooming again, you see the red square and larger.
Okay, we see some code here.
And actually, with a few weeks later after I found it,
it was actually fixed with this commit.
It does excessive expansion.
It was called to the main 3 macro.
There are also complexity metrics that computer scientists study
to see how difficult it is to understand the code.
Things called cyclomatic complexity.
Having to do with jumps around the core and the graph of the instructions.
Jumping from one place in the other.
And this increases for 4 to 7.
This is called a cyclomatic complexity.
And the hard set volume, having to do with the identifiers.
Visible at a given point.
Also in the medium volume increases for 85 to 180.
Which means that it's more difficult to reason about the code and test it.
Other things.
There are composite identifiers piece together through markers about 150,000.
Extensive include hierarchies.
So there are some outlier compilation units that include 1.5 million number of lines.
Each compilation unit.
So it thinks we compile, takes about 2,000 files, imports it.
And also 36 include file outliers, have a depth of 12 nesting.
So something includes something else, include something else 12 times.
And that also found several cyclical includes defect dependencies.
So in total 170,000, 7 per compilation unit.
The longest one consists of 10 elements.
So it's this cycle here.
Of course, this is not an instrument to the core.
Cursion because we protect include files from re-including themselves.
But nevertheless, when we fancy such things, it's difficult to break them.
It's difficult to reason what's happening here.
How has this evolved over time?
So here are the three kernels I looked at.
Two things are good.
Conditional directives are falling.
And include directives are also falling a bit.
Which means, especially in conditional directives.
It's difficult to test stuff.
It's good that they are being reduced.
But other things you see that they are still increasing names with confusion.
They use of the concatenation operator.
So how can we reduce this technical depth?
First of all, one practical thing.
I found that about 5 million object-like macros,
almost most of them, can simply be rewritten.
Either as a static const value.
And I've verified that juicy compiles it,
makes it doesn't take any memory at all.
It's not a problem.
It's a problem.
It doesn't take any memory at all.
It compiles the code as if it was defined as a macro.
If it's used as a macro.
So without taking it's address, for example,
or assigning to it.
Or they can also be defined as an emulation.
Remember, which makes it possible to use it as a compile-time constant.
For instance, for declaring the size,
define the size of an array with it.
And this is a possible for 77% of the macros.
For the rest, the values probably not a compile-time constant,
about 1 million of them.
Or the value is used as a token concatenation,
or a stingyization, about 90,000 of them.
Or the values used in a simply processor constant.
So it's appears in the nif, if death.
And so on.
And for 23,000 of them.
But for a large majority, we could actually do it.
Well, now let's move back to something more difficult.
The function-like macros, about 100,000 of them.
I've calculated by looking at cases that cannot be easily converted.
That about half of them could be converted into C.
And for the rest, we've heard it in a number of sessions through this conference so far.
Last could promise an answer because, as a more powerful type system,
it allows for typed, syntactic, correct, complete macros.
And torsive can process code declaratively by manipulating the syntax.
And that allows to do more complex things.
So as something that the Germans very elegantly call the Duncan experiment,
a thought experiment, let's think about what it would mean to use
rest to change existing function-like macros into a last code.
It's not really feasible because each change would have to happen together with the rest of the code.
But let's look at what it would involve.
32,000 function-like macros are not used as functions,
so they create data structures or code dynamically.
But they could be converted into rest macros.
9500 of them used talking concatenation for this.
We could use the last concatenance feature.
5,000 used non-object parameters, so they take a parameter that's not an object,
like a function name or a variable name, but for this,
we could use the rest macros meta variables.
1700 of them have some modifications, rest has a stringify,
so this could also work.
200 of them affect control flow.
For this, we could use rest macros or ideally we should
refactor them not use a not effect control flow,
so not return from inside the macro.
33 used the type of for this could use type traits or generic parameters.
Again, I suspect that more used generic types,
so this number may be larger, but rest gives a very good solution for this,
and this could also improve the code's quality.
And also 88 have incomplete syntax, so they have any dangling open bracket
or dangling close brace.
And for this, I think we should be refactor there, also very few.
So overall there are 24 to 43,000 macros about 44%
that could be handled by using the more powerful features of rest.
So to see the overall, these are all the object,
like are all the macros.
These are all C constants that could be
moved directly to C objects.
These are the rest of the objects,
like things that cannot be directly defined as C constants.
And from the function like macros,
some would require rest and another large part
can probably be converted into C directly.
So to conclude what have we seen here,
we have seen that they use of the C preprocessor in the Linux kernel
is extensive, introduces technical depth in all preprocessor dimensions,
so no matter how you use the preprocessor,
in many cases, something bad happens.
The usage is still growing in a number of areas,
and it can be quite expensive to address
there is no simple solution that can help us here.
So for the short term, what could we do,
fix macros explosions, and for example,
where this has already happened.
We can correct frequent cyclic,
frequently occurring cyclic dependencies.
I fixed one as an experiment over the summons
has already been merged.
I think it would be good to reduce other ones.
And also consider converting those 77% of the object-like macros
that can be converted into C constants,
doing this as a benefit they will appear in the debugger,
and it will be more easier to reason about it.
In the longer term, we can prioritize
refactoring a function-like macros,
either into C, or it is possible,
or into rest when modules are converted into rest
or created into rest from the beginning.
This brings me to the end.
I hope you find it useful. Thank you.
Thank you.
All right. Any questions?
All right.
I'm sorry.
So, I think you're all wondering what
why are people doing that, right?
If stuff can easily be written as a C function,
why do we write a macro?
Because they used it from 1980s, or what is your theory?
So, where are we using macros?
I looked, especially when I told that macros have a problem.
I looked back and I was saying why people
consider size of it to be equals to size of pointer,
when can I do it?
Can I do it?
You said that don't do it.
One answer was that can I do it?
You didn't have children at the time.
We told somebody don't do it.
So, in seriousness, now,
why are we doing it?
I think there's a historical precedent.
Early compilers didn't have the optimization
capabilities that modern compilers have.
So, for example, they could not in line functions
that were very small.
Whereas with a macro, this happens automatically.
So, you have the compiler.
The same with constants.
So, now that you see recognizes that something is not used.
It doesn't need to allocate memory, but all compilers were very primitive
and would allocate memory for that.
And constant wasn't even available in the first version of C.
So, a large part, I think, of macro usage has to do with helping
compilers that were not very, very sophisticated.
But also, there are other uses that are defined
so generic functions that can be used with multiple types,
such as minimum.
We saw explored before for conditional compilation
for which there is no alternative.
And also, the C doesn't have a powerful module system.
So, for this, we will use the include directive and header files.
Thank you.
Anything else?
Yeah.
In your sort experiment for a conditional rest,
what will you see as the unit of conversion?
Because obviously we are not going to go.
Sorry, a bit louder, please.
In your sort experiment, to convert into rest,
what will you see as the minimum unit for conversion to rest?
Because obviously we are not going to connect in digital Microsoft.
Exactly, this white was a thought experiment.
The other thing is, if I understood the question correctly,
what to do with the rest of the code, because the code will need to be converted into rest.
Is that a question?
Yes.
So, this is a very larger question where the cannot answer as part of this.
The study people are looking at ways to convert C into safe rest,
because in converting into rest is not difficult,
to safe and read the rest is difficult.
And there are a number of tools that help with that,
such as C to safe rest.
LLMs can help in small areas.
But that's a huge project,
and not sure even that the community is looking at something
that is universally good thing to do.
So, it's beyond the scope of where this study.
That's another question there.
Hello.
Thank you for the presentation.
One thing that I would like to find out from your research is that
the last year we're moving into rest.
The tenant is moving into rest gradually,
and there is a lot of funding there.
So, that's also a very good question.
If you're moving into the right direction,
it's difficult to say it before hand.
Rust has many advantages,
because clearly created as a systems programming.
LLMs and it offers us the ability to write safe code in many areas,
while still being near the hardware.
So, this is a very interesting question.
I would like to ask you a question.
In many areas, while still being near the hardware.
I think that C is becoming more and more difficult to use in advanced cases.
And there's also a matter of mind share.
So, it's difficult for younger generations to learn
because no longer taught in many universities.
And this makes it difficult to have a community of new developers
who will contribute in the care.
So, I agree maybe Rust has problems,
maybe more difficult to learn than C,
but we need to move forward and bring new people into our community.
And maybe Rust is a part of the solution space.
All right, thanks a lot.
Thank you.