Riot: RFC (build system): Define requirements for `module selection and configuration` stage

[leandrolanzieri]

Description

During some offline discussions regarding the next steps in the migration to Kconfig,
@aabadie and @fjmolinas pointed out that it can be useful to state requirements we want
from the build system, regarding module selection and configuration. Having
these clear will help us making design decisions.

Here I propose requirements both from the user and developer perspectives:

• Must provide the user with:
  
  
  
  • a clear view of the possible configurations for the target hardware
  
  
  • default configurations for the most common use-cases
  
  
• Must allow producing the leanest possible target for a given configuration
• Must allow producing only unambiguous and valid configurations
• Must not allow circular dependencies
• Must allow to model features provided by hardware or modules
• Must allow to define module dependencies to:
  
  
  
  • other modules
  
  
  • hardware features
  
  
  • software features (e.g. a feature that can have different backends)
  
  
• Available module configuration options should be clearly exposed, and accessible for parameterizing tests.

Some questions:

1. Do we agree on these requirements?
2. What else do we expect from the build system in this regard?

[kaspar030]

j> * a clear view of the possible configurations for the target hardware

I guess this means "configuration options". I don't think it is possible to actually show all configurations in a clear way.

Must not allow circular dependencies

Please elaborate. Module A might not work without Module B and vice versa.

What I think we also need:

Dependency types:

• "provides" (if selected, also satisfies dependency FOO)
• "conflicts" (cannot be selected together with BAR)
• "one of" (depend on A|B|C, if available, in that order)
• "if module A is available, depend on B"
• "if module A is not available, depend on B"

Scoped variables:

defines or options of a module should have different "visibility".
E.g., there's no need to compile ztimer with "-DCONFIG_FATFS_SUPPORT_UTF8", but every dependee that includes ztimer.h needs e.g., "-DCONFIG_ZTIMER_NOINLINE".
Any variables / defines for a module should be either global, local or "exported to all dependees".

External dependencies:

The build system should support external, versioned packages, and also show their configuration.

Nested configuration contexts:

It should be possible to express and configure nested configurations. E.g., there should be a RIOT context, on top of that a Cortex-M context, on top of that a sam0 context, ..., up to the board or application/board. It needs to be possible to configure each of these contexts.

Access to the data:
IMO json/yaml access to the build system (configuration) data is a must.

---

Other than that I'm missing a bit of a workflow idea.

Let's start with a fresh (empty, new) application. I guess a first step would be sth like make configure.

Which options are presented? Is selecting a board the first thing? How do we configure a portable application?

[maribu]

* Must not allow circular dependencies

I think this is hard to avoid. I know how much of an issue this is for Linux distribution when package A depends on B and B depends on A. In that case you have to e.g. build A first in a stripped down version that does not depend on B in order to build B. And often you have to loop rebuild them over and over until finally all features can be build.

But the difference here is: In RIOT the headers will just always be available. Thus, it should be no issue to build A without B already being build in the other way round. (If this is a concern: We could write this down that we expect that every module should be able to compile without any of its dependencies being compiled yet - so that only at the linking stage all dependencies need to be available. But as every module happened to comply with this already, I guess this either is just so natural or so obvious, that we could just rely on this not going to happen without a written rule.)

[maribu]

* Must allow producing only unambiguous and valid configurations

I would even prefer to be more stricter here: The build system should enforce this by not building anything at all until the configuration is valid and unambiguous.

[maribu]

Dependency types:

* "provides" (if selected, also satisfies dependency FOO)

* "conflicts" (cannot be selected together with BAR)

* "one of" (depend on A|B|C, if available, in that order)

* "if module A is available, depend on B"

* "if module A is not available, depend on B"

+1

but for the "one of" it should only pull in any dependency if none of the options is not yet pulled in. E.g. if it depends on A|B|C but C is already used anyway, it should not pull in A even if A is available. (Note: The FEATURES_REQUIRED_ANY currently in RIOT does this.) In addition, if Module M depends on A|B|C and N depends on D|B it would be super if the build system would pull in only B, rather than A and D. (Note: This is something that FEATURES_REQUIRED_ANY currently will not do.)

[kaspar030]

But the difference here is: In RIOT the headers will just always be available. Thus, it should be no issue to build A without B already being build in the other way round. (If this is a concern: We could write this down that we expect that every module should be able to compile without any of its dependencies being compiled yet - so that only at the linking stage all dependencies need to be available. But as every module happened to comply with this already, I guess this either is just so natural or so obvious, that we could just rely on this not going to happen without a written rule.)

Let's not forget Rust modules (which were difficult to support due to build order dependencies that RIOT's module system could not express), and maybe generated code. There are build order dependencies and logical dependencies between modules.

[leandrolanzieri]

• a clear view of the possible configurations for the target hardware

I guess this means "configuration options". I don't think it is possible to actually show all configurations in a clear way.

With this I mean that the user should be provided with the information of which modules are selectable and which configuration options are available given the target hardware and currently active modules.

Must not allow circular dependencies

Please elaborate. Module A might not work without Module B and vice versa.

AFAIK circular dependencies are in most cases not a good practice, and as such something we would like to move away from. This type of dependency makes modules harder to understand, test and it is not in line with our modular design.

A different thing is that, for a certain feature one needs Module A and Module B to be present. But if both modules need each other, are they actually well modeled? Usually on those cases it is possible to split modules into a finer granularity in order to get the correct dependencies.

Dependency types:

• "provides" (if selected, also satisfies dependency FOO)
• "conflicts" (cannot be selected together with BAR)
• "one of" (depend on A|B|C, if available, in that order)
• "if module A is available, depend on B"
• "if module A is not available, depend on B"

Ok. I think this is something like what I had in mind with:

Must allow to define module dependencies to:

• other modules
• hardware features
• software features (e.g. a feature that can have different backends)

But I guess we can list which relationships we want to be able to express. This means, among others, that modules should also be able to provide 'features'.

[cgundogan]

I think this is hard to avoid. I know how much of an issue this is for Linux distribution when package A depends on B and B depends on A. In that case you have to e.g. build A first in a stripped down version that does not depend on B in order to build B. And often you have to loop rebuild them over and over until finally all features can be build.

But the difference here is: In RIOT the headers will just always be available. Thus, it should be no issue to build A without B already being build in the other way round. (If this is a concern: We could write this down that we expect that every module should be able to compile without any of its dependencies being compiled yet - so that only at the linking stage all dependencies need to be available. But as every module happened to comply with this already, I guess this either is just so natural or so obvious, that we could just rely on this not going to happen without a written rule.)

I disagree here. IMO it is not hard to avoid circular dependencies. Nowadays, the typical programming 101 class teaches design patterns that avoid a strong coupling of modules .. Dependency hell is something that we want to must avoid, especially if we have a very nuanced dependency tree with a multitude of branches. Enforcing an acyclic dependency graph with a tool is IMO the correct way to go.

Let's not forget Rust modules (which were difficult to support due to build order dependencies that RIOT's module system could not express), and maybe generated code. There are build order dependencies and logical dependencies between modules.

I would argue that build order dependencies closely follow the logical order dependencies. Otherwise, that would be very strange .. why would I need to build a module first and then the dependencies (in most cases this wouldn't even compile? And we don't support dynamic linking ..)

[kaspar030]

I disagree here. IMO it is not hard to avoid circular dependencies. Nowadays, the typical programming 101 class teaches design patterns that avoid a strong coupling of modules .. Dependency hell is something that we ~want to~ must avoid, especially if we have a very nuanced dependency tree with a multitude of branches. Enforcing an acyclic dependency graph with a tool is IMO the correct way to go.

Spoken like coming out of programming 101. Good luck modeling RIOT's current dependencies with that.

There are quite some circular dependencies in RIOT atm. Out of my head, core depends on auto_init. auto_init depends on everything, everything depends on core. Or gnrc depends on gnrc_pktbuf, which depends on gnrc_pkt, which depends on gnrc.
There are different "kinds" of dependencies (A also selects B, A uses header of B, A uses symbols from B, ...). Some are naturally circular. I don't buy "programming 101 dictates that we have to do without".

And believe me, in practice, disallowing seemingly valid circular dependencies is a huge aspect of dependency hell.

[kaspar030]

I would argue that build order dependencies closely follow the logical order dependencies.

No, they are a completely different dimension. For almost all current RIOT modules, the build order is [compile all *.c of an application to *.o] before [ link all *.o of an application into application.elf ]. That doesn't quite match the logical dependency tree, which would require e.g., cimpile gnrc_pktbuf.c before compile gnrc_tcp.c.

[miri64]

Out of my head, core depends on auto_init. auto_init depends on everything, everything depends on core.

Why has auto_init dependencies? AFAIK all code in auto_init is more of the kind of

#if IS_USED(MODULE_FOOBAR)
init_foobar();
#endif 

One could call this an (optional) dependency, but this is transparent to the build system and thus not creating the cyclic dependency you claim must exist.

Or gnrc depends on gnrc_pktbuf, which depends on gnrc_pkt, which depends on gnrc.

The latter dependency seems unnecessary to me and AFAIK is not true. You don't need the whole stack to have a list of packets.

[cgundogan]

Spoken like coming out of programming 101. Good luck modeling RIOT's current dependencies with that.

well, better don't skip programming 101, hm?

There are quite some circular dependencies in RIOT atm. Out of my head, core depends on auto_init. auto_init depends on everything, everything depends on core. Or gnrc depends on gnrc_pktbuf, which depends on gnrc_pkt, which depends on gnrc.
There are different "kinds" of dependencies (A also selects B, A uses header of B, A uses symbols from B, ...). Some are naturally circular. I don't buy "programming 101 dictates that we have to do without".

Great. Identifying the problems is the first step. We should use this discourse to exchange proper arguments for or against the subject. I don't want a circular reasoning ..

Or gnrc depends on gnrc_pktbuf, which depends on gnrc_pkt, which depends on gnrc.

Not sure it is that simple. There are many modules within GNRC that, to my knowledge, follow an acyclic dependency resolution. @miri64 can probably say more on this topic ..

There are different "kinds" of dependencies (A also selects B, A uses header of B, A uses symbols from B, ...). Some are naturally circular.

But all these "kinds" of dependencies have nothing to do with cycle vs acycle, or am I not seeing something?

And believe me, in practice, disallowing seemingly valid circular dependencies is a huge aspect of dependency hell.

Sorry, I still have to disagree on this point. What would be a valid circular dependency? And what do we gain from that?

[kaspar030]

well, better don't skip programming 101, hm?

Sorry for my statement, it was quite rude.

[cgundogan]

For almost all current RIOT modules, the build order is [compile all *.c of an application to *.o] before [ link all *.o of an application into application.elf ]

yeah along the way from dependency resolution to linking the final binary, we lose the correct module order in $(BASELIBS) currently. That's why we also have to use --start-group ... --end-group in the linker call. The linker is basically doing a recursive lookup of symbols from all passed .a files (which are probably in alphabetical order by now). I think, if we can keep some information to the order of modules in $(BASELIBS) intact, then this could speed up the linking time?

[kaspar030]

Sorry, I still have to disagree on this point. What would be a valid circular dependency? And what do we gain from that?

Well, this is just how our code is laid out. For example, everything outputting something depends on stdio_X (usually stdio_uart). Even core ("Hello! this is RIOT."). But stdio_uart also depends on core (it uses isrpipe, which uses mutex, ...). So core does not link without stdio_X. But stdio_x does not link without core. That is a cyclic dependency. IMO, it is "valid".

Can that be modeled differently? Probably. But would that make sense? How would that look?

[fjmolinas]

Must allow to define module dependencies to:

• other modules
• hardware features
• software features (e.g. a feature that can have different backends)

I would add also configuration dependencies, e.g. some modules require some CFLAGS. These can probably modeled as another module though, but in our current system its not like that.

Dependency types:

• "provides" (if selected, also satisfies dependency FOO)
• "conflicts" (cannot be selected together with BAR)
• "one of" (depend on A|B|C, if available, in that order)
• "if module A is available, depend on B"
• "if module A is not available, depend on B"

I think having optional modules has come up a lot:

• "If Module A is available, depend on A"
• "If Module A is not available, and B is available depend on B"

I would also add that I would be nice for everything to be declarative.

[kaspar030]

I'd like to add another requirement:

• build each .C with the CFLAGS and and defines it needs, and no more.

This makes incremental builds possible even when configuration changes. The build system should only rebuild what needs rebuilding. (IMO, "let ccache sort that out" is a bad choice).

This rules out building e.g., core with "-DMODULE_FATFS" if there's no need. It rules out including a global "auto_config.h".

[kaspar030]

* "If Module B is not available, and B is available depend on B"

I think there's an A missing somewhere?

[maribu]

So core does not link without stdio_X. But stdio_x does not link without core. That is a cyclic dependency. IMO, it is "valid".

That's a perfect example of where avoiding cyclic dependency is not feasible.

But I agree that cyclic dependency should be avoided and an indicator of poor design. Except when not.

Let's not forget Rust modules (which were difficult to support due to build order dependencies that RIOT's module system could not express), and maybe generated code. There are build order dependencies and logical dependencies between modules.

Thanks for correcting me. (This reminds me that I really should get some Rust experience.) That requirement is going to be "fun" to properly address :-/

[leandrolanzieri]

This makes incremental builds possible even when configuration changes. The build system should only rebuild what needs rebuilding.

There are other ways to deal with incremental builds. For example Linux uses the fixdep.c script to change dependency files, in order to rebuild only the affected sources.

[leandrolanzieri]

For example, everything outputting something depends on stdio_X (usually stdio_uart). Even core ("Hello! this is RIOT."). But stdio_uart also depends on core (it uses isrpipe, which uses mutex, ...). So core does not link without stdio_X. But stdio_x does not link without core. That is a cyclic dependency. IMO, it is "valid".

Can that be modeled differently? Probably. But would that make sense? How would that look?

Regarding the message in core_init, couldn't the strong dependency be avoided if the message is only printed when an stdio_x is present? Similarly to the call to auto_init:
```C

ifdef MODULE_AUTO_INIT

auto_init();

endif

[MrKevinWeiss]

Regarding avoiding cyclic dependency, I think we all can agree that it would be great to avoid them. I also think it is technically possible. The question is about the magnitude of work to correct this. Maybe it is just a matter of using an #ifdef around all the places such as the Hello! this is RIOT print or breaking it down into finer granularity such as a core and core_with_hello, in which case I would say let's start the work now. I have usually found that it is not as easy as that, however, I still think that we get some great advantages for everyone that would make the struggle worth it.

A concern that I have is regarding integration with things outside RIOT.
If I have an application that uses RIOT and some third-party stack, and that third-party stack has some circular dependencies (or violating the other requirements for that matter), does this pose a problem, or is it only within RIOT that we would have this requirement?

Aside from that, I agree with this idea, not only does this improve the quality and design of RIOT but also allows for tools to take advantage of a defined structure (more projects, more work :smiley:)

[tcschmidt]

A concern that I have is regarding integration with things outside RIOT.
If I have an application that uses RIOT and some third-party stack, and that third-party stack has some circular dependencies (or violating the other requirements for that matter), does this pose a problem, or is it only within RIOT that we would have this requirement?

Does Zephyr experience this problem and how do they deal with it?
Would be good to check empirically rather than discussing hypothetically.

[maribu]

There seems to be an agreement that a dependency cycle like "A depends on B and B depends optionally on A" is not a dependency cycle. I assume this is based on the assumption that dependency cycles with at least one dependency of the cycle being optional is no problem to handle by the build system. On what is this based?

E.g. if use of stdio in core would be optional and the build system would first build core (without message) and then stdio. Wouldn't it now have to build core again (with messages) this time? Or would the build system just rely on the fact that dependency cycles in C (and C++) with the headers are being available at any point in time and just build core with messages in the first compilation step? If so, what is then the advantage of the "hard" dependency cycle being turned into a "weak" dependency cycle?

So: Is there any reason to believe that "weak" dependency cycles (with at least on dependency in the cycle being optional) has any any advantage in the context of C (or C++) code? It certainly has the disadvantage of many #ifdef MODULE_FOO...#endif pairs are added just to turn forbidden hard dependency cycles into allowed weak dependency cycles. And that in turn would not result easier to maintain code, but quite the opposite.

If everyone insists in outlawing dependency cycles, couldn't we at least have this less strict like e.g. this:

• C (and C++) modules having dependency cycles should provide sound reason why no better architecture avoid dependency cycles is feasible
• Modules written in a language in which build order matters (e.g. Rust) must not contain dependency cycles.

[jia200x]

A concern that I have is regarding integration with things outside RIOT.
If I have an application that uses RIOT and some third-party stack, and that third-party stack has some circular dependencies (or violating the other requirements for that matter), does this pose a problem, or is it only within RIOT that we would have this requirement?

Just a side note: I think we should distinguish between "cooking"/configuring the RIOT kernel and linking third parties libraries. AFAIS the requirements cover the former.

Some libraries (in shape of PKGs) are configured via the RIOT build system because there's some "kernel contrib code" that might require different configurations. For instance, the OpenThread integration exposes some configuration options that might be relevant to the contrib code. But the build system acts as an interface for the actual pkg configuration (e.g using the openthread-ftd module injects some CFLAGS and ./configure options to OpenThread's cmake).

But in general, third-parties will use their own build system. Thus, linking third party libraries is indeed in the scope of "RIOT Build System" but out of the scope of the having cyclic/acyclic graphs

[tcschmidt]

C (and C++) modules having dependency cycles should provide sound reason why no better architecture avoid dependency cycles is feasible

These requirements are meant for technical modeling and tooling, not as designer guideline. So "sound reasons" are a problem when presented to a tool.

[tcschmidt]

E.g. if use of stdio in core would be optional and the build system would first build core (without message) and then stdio. Wouldn't it now have to build core again (with messages) this time? Or would the build system just rely on the fact that dependency cycles in C (and C++) with the headers are being available at any point in time and just build core with messages in the first compilation step?

This problem is only present if the built system is not aware of the entire configuration graph (as it is today). You are actually describing one of the current key problems of the RIOT build system, namely that it cannot produce uniquely defined, optimized targets. Rather, the results depend on the order of execution.

Whenever the build system can work on the basis of an exposed configuration graph, this problem disappears, which is one of the main goals of this work.

[leandrolanzieri]

I think it is important to keep in mind that the initial points proposed here are requirements for the 'module selection and configuration' stage (a.k.a. "cooking" as @jia200x mentioned above). The output of this stage will contain a list of modules that the build system needs to compile.

Of course further optimizations of the other stages of the build process are possible, but it would be good to keep the scope of the discussion on this.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[aabadie]

Still a relevant topic.