Use no-std-compat to transition to no-std

[setupminimal]

This would close #21 - allowing Shredder to be used in no-std environments.

This uses the no-std-compat crate to provide an easy transition. Mutexes and RwLocks are provided by the spin crate. A user can get the no-std version of shredder by disabling the std feature.

One caveat to be aware of: debug prints, and error prints are replaced with no-ops. This might cause errors to go un-reported. An item of future work might be to find a way to make those assertions useful in a no-std environment.

[setupminimal]

The clippy check appears to be failing because of the wildcard imports in this pull request. I'm happy to change them if needed, but I'd argue that wildcard-importing the prelude is more ergonomic.

Would you like the imports de-wildcarded or the clippy warning suppressed?

[Others]

Yeah you can disable the lint. How does this handle the background thread in no std environments?

[setupminimal]

I wasn't sure, so I went to go double-check what the implementation was. Turns out that the std::thread namespace isn't included in no-std-compat. I realized that I should have been running cargo test --no-default-features instead of cargo test --features "".

My original plan to handle that was to allow the library user to pass in a function that takes the place of spawn; I'm going to go implement that, turn off the clippy check, and update this pull request. It might have to wait until tomorrow, though, as it's getting pretty late where I am.

[Others]

The architectural changes to allow the user to pass in a spawn function make me nervous. I have an inkling that the correct choice is to implement a switch for the collector to run without the need for a background threads at all.

Is no-std a feature you want to personally use for some application?

[setupminimal]

Yes, it is. I'm writing an operating system kernel in the style of a Lisp Machine, and need to use some form of garbage collection to implement the language that the userspace is written in.

One of the reasons I thought shredder would be a good fit is because it supported concurrent collection; I have a cooperative multitasking system based on async implemented.

I'm not sure what would be needed/involved in re-writing shredder to not use threads at all - I assume that the work that the dropper thread does would need to be amortized across places that access Gc references? If you could provide a little bit of guidance about what you think that should look like, I'd be happy to give it a try.

Or if that's too complicated a change, maybe we could replace the current use of threading with async? That way, on no-std targets people could provide their own implementations, and on normal targets, people could delegate to tokio or some other common scheduler.

[setupminimal]

I've just pushed the changes that would be needed to allow a user to supply their own spawn function.

Note that this is not quite ready yet - the no-std-compat crate re-exports an old version of spin that isn't quite compatible with the API that shredder uses. I've already opened a pull request against no-std-compat to fix that.

And even if it were ready, it wouldn't quite meet my use case, because I would need to change things to use async queues instead of crossbeam queues so that it would work under cooperative multithreading.

But maybe this gives an idea of what letting the user supply their own spawn function could look like - I tried to write a version requiring minimal change.

Do let me know how you'd like to move forward - as I said, I'm perfectly willing to volunteer time to this, since it's something I need for my own project anyway.

[Others]

I think you may need to test this in an actually no-std environment. I think (off the top of my head) that some of our dependencies (in particular parking-lot) may not actually work without std.

I'll have a think tonight about how a no-background thread mode for shredder would work, and get back to you on what work would need done to go in that direction. (I'm not entirely opposed to the spawn function direction for now, but I don't think it's right long term.)

[Others]

Thought about this more, here are my concerns: a) I consider this blocked on having a CI step that runs the tests in a no-std environment so we continuously validate this work b) I think a no-thread version of shredder is workable, but I have concerns about how a naive implementation on top of spinlocks. See: https://matklad.github.io//2020/01/02/spinlocks-considered-harmful.html c) I want to put out a new release with AtomicGc and DerefGc, so that'll take priority over no-std support (but that work is just finishing my derive work and writing a blog post so it shouldn't be too slow)

All that being said, I'm happy to work with you to get this done. I think the first step is to create a CI step in the context of this PR, then we hack at it until it passes (ignoring concerns about spinlocks and threading). I can then merge that into an unstable feature branch, which we can then hack and iterate on.

[setupminimal]

That sounds perfectly reasonable; the tests need to be updated to use the new feature flag and compatibility library, but that's pretty straightforward.

The real blocker on actually getting the tests running is having a no-std equivalent of spawn. Dragging a whole operating system kernel into the test environment doesn't seem like a good idea. I'll have to do some research on what options are available, and then I can probably spend some time this weekend tweaking the tests.

[setupminimal]

Okay. I've done some research, and I have further thoughts:

It looks like pre-emptive multitasking isn't well supported for no-std. I assumed that there would be a package that implemented it based on underlying OS threads, for testing if nothing else. We can use std::thread::spawn for some tests, but the more complicated ones like the integration tests can't be made to work that way.

Other than writing a minimal OS kernel and using QEMU, I don't think there's a reasonable way to test this, which is maybe a sign to take a step back and re-consider.

Maybe the best way forward here is to first work on a no-threads version, and only then attempt to add no-std support; other than the threading, porting everything else is pretty easy.

For a no-threads version, the 'obvious' solution is just to have the thread that would send the drop request to the drop thread drop the value itself. But I have to assume there's some reason that you introduced a drop thread in the first place - probably to prevent latency spikes on the main thread that happens to be responsible for dropping the last reference to something?

Maybe it's as simple as making another feature that disables the use of the dropper thread. Then the no-std version of the library would just require that feature as well. That would work for my use case, I believe.

What was the original purpose behind the dropper thread? Would removing it the 'obvious' way have some impact on shredder's performance or design that I'm not seeing?

[Others]

There are two background threads--the collector thread and the dropper thread. Both exist as optimizations to prevent stopping compute--they shouldn't be necessary. I think that replacing the dropper thread should be easy (just create two versions of the module and switch between them based on a feature flag).

The collector thread probably needs rearchitected to be managed behind a module/struct as well, and then we can apply the same approach.

[setupminimal]

I've just pushed a commit that essentially does that - it reverts the change that allowed users to specify their own spawn, and instead performs the work in the thread that would have written to the channel.

The code can probably be cleaned up slightly, but it should be mostly functional.

This commit also adds a configuration to run the tests in a no-std environment in CircleCI. It breaks two of the tests for some reason - I'm not sure why. I intend to figure out what the tests are trying to tell us when I have some free time this weekend. But this should be a good test that the new CircleCI config does what I think it does.

[Others]

Your test is not doing what you think it is. Even if this crate is no-std, our dependencies may not be. You should add an additional step to build the library with no features on a platform without std, like wasm.

That will check that the no-std version actually doesn't pull in std transitively.

[Others]

rustup target install thumbv6m-none-eabi; cargo build --no-default-features --target thumbv6m-none-eabi

I think that's the command you want to ensure that we build on no-std targets :)

[Others]

@setupminimal I do like the work you have done here so far, but there is a ways to go. Do you want to keep iterating on this, or should I close this as inactive?