How to resolve cyclic dependency

help
#1

I'm writing an OS and I want my drivers to be able to call into my kernel by linking to it. However, my kernel requires at least a disk IO driver, and so I've included that in the cargo.toml. But there's a dependency on the kernel library in the disk IO driver's crate as well, creating a dependency loop. As Cargo puts it:
```error: cyclic package dependency: package kernel v0.1.0 (C:\Users\ethin\source\kernel) depends on itself. Cycle:
package kernel v0.1.0 (C:\Users\ethin\source\kernel)
... which is depended on by nvme v0.1.0 (C:\Users\ethin\source\kernel\drivers\storage\nvme)
... which is depended on by kernel v0.1.0 (C:\Users\ethin\source\kernel)

A resolution to this could be me to incorporate the driver directly into the kernel itself, but I want it to be possible to trivially swap out the driver for another. (I'm not quite sure how I could actually enforce this requirement -- build scripts, maybe?) What are other alternatives to resolving this cycle?
#2

Maybe you could move the kernel interface to a separate crate that only defines traits/types that are necessary for calling it, without the rest of the kernel.

Similarly like there's https://lib.rs/http crate that defines API of requests and responses, without any network code in it.

1 Like
#3

In general you want to avoid having cyclic dependencies, both for philosophical and practical reasons.

The philosophical reason is mostly that if you have a cyclic dependency, then conceptually the N things (especially if it's at the module level) pointing to each other are one and the same, since they can't exist without each other.

In the practical reason column is that you're likely to meet resistance from tooling, in this case cargo.
Cyclic dependencies are nasty to properly handle, and often involves undesirable calculations such as fixed point analyses, which can run for indefinite amounts of time. This in turn raises compile times.

The solution at a high level is to factor out as much as you can without having to turn to cyclic dependencies, because as long as you have one of those it will be painful for you.

At a deep conceptual level, code is always tree-shaped. Fighting that truth makes life harder for everyone involved in that code base.

1 Like
#4

I'm just not sure how to solve this. I don't want cyclic dependencies. But I do want a library that my kernel drivers can use without pulling in the entire kernel binary. So that's what I've done: I've extracted and made independent the kernel library. The problem is that the main kernel binary depends on the kernel library, and all the drivers that we build must also depend on this library as well.
The problem comes in when I want to actually pull in a driver. Say I have a network driver. The network driver would depend on libk because libk holds the memory manager for paging and such. So I can't make the binary depend on libk and then each driver depend on libk too, because Cargo won't like that. I can pull in drivers into the binary itself, but I don't know if that will actually resolve the problem, because I still need libk.

#5

If components like the memory manager have an interface based on traits, you can extract the traits (and any kernel-defined types that those traits depend on) to a new, much smaller crate, e.g. libk-mm. Both the kernel and the driver then depend on that instead of on each other.

If the components don't have such a trait-based API, then what may help you most is first refactoring the code so that it does have such an API, and then split it up like above.

#6

That won't work. If I abstract memory management functions into
libk-mm, libk will still require libk-mm, and so will the drivers. So
would that not keep the cyclic dep? (And either way, I'm not even
really sure how I'd refactor my code to fit that model right now,
because I use three functions -- allocate_paged_range,
allocate_phys_range, and free_range -- to allocate virtual and
physical memory and to free it.)

#7

It turns the cyclic dependency into a tree structure instead, so that any of these combinations are valid:

  • libk-mm only
  • libk-mm + libk
  • libk-mm + drivers
  • libk-mm + libk + drivers
1 Like
#8

Note that the libk-mm crate doesn't necessarily have to have the implementations of the memory management code, it merely needs to contain the trait definitions and any types used in those trait definitions.
The libk kernel crate can then define impls for those traits for types that are defined in that same libk crate.

1 Like