no_std support

[uazu]

It should be possible to support large parts of the functionality in a no_std environment. So add a default "std" feature, and allow the crate user to disable it if they want no_std.

[geeklint]

After looking into this a little, here's some commentary:

LCell will work as-is.

TLCell is basically completely off the table, at least with the current state of Rust, as thread local anything required std.

TCell; I don't really see a way to make it work. Maybe with an external support library that supports an atomic map, but that's going to come with a lot of compromises vs the current Mutex.

QCell should mostly work, the hold is on the Mutex used by ::new(). My crossbeam_queue PR could address this; the other option is just to feature gate the safe new on std, and only support the unsafe fast_new on no_std.

The main question I would then have is how you feel tests should work when compiling different feature sets. For example, what should the behavior of cargo test --no-default-features be? One option is to have it fail (basically, "we don't support testing anything but the full feature set") another would be to exclude the tests that require std (so the command would succeed, but not all tests would have been run).

[uazu]

I think ideally the tests should test whatever parts of the crate are supported with that feature set. However whether both the doctests and trybuild will support doing that is another question. It would need trying. (Note that trybuild is more for the crate maintainers to check that things are failing for the right reasons in terms of use of the API, so if the trybuild tests have to be excluded for no_std that is fine.)

If only QCell and LCell work to start with for no_std, that is still useful.

Regarding TCell: I had a look to see if it was possible to create a global per monomorphisation of the owner creation, but it seems not. There are various solutions, e.g. spinning instead of using a mutex, and maybe using BTreeMap instead of HashMap, but I'm not sure what is best. I wonder what other no_std crates do in this situation? TCell could be left for later.

[geeklint]

One thing maybe worth mentioning is it's relatively easy to make a global collection without std - if it's fixed size. So we could say, for example, "on no_std, TCell is limited to a maximum of 20 owner types at a time"

[uazu]

I don't know enough about typical no_std deployments to know what would be expected or acceptable in those scenarios. It would be handy to know what other projects do. I wonder, are there any practical uses for TCell without alloc? I can kind of see a use if someone has their own smart pointer type, and is allocating objects out of fixed tables. (I've seen a low-resource network stack that works like that in C). So maybe there is a use for it there. So maybe a fixed table is viable, but what happens if it is not big enough? Is it viable to ask the caller to give us some memory to put our table in, so the caller statically allocates the memory and chooses the size? I think the number 20 is reasonable for how I see TCell being used, but who knows really what people might try.

[SoniEx2]

Is this still relevant? Looks like we have #24 now.

[uazu]

It's mostly done -- i.e. QCell and LCell are done. TCell could still be supported on no_std using a fixed-sized table of atomics instead of a hashmap. I think that would be worth doing at some point, as TCell does have some advantages compared to the other two types. So I'll keep this issue open for now.

[geeklint]

I've been experimenting with something which is a possible solution to no_std TCell.

https://github.com/geeklint/typeid-set is a data structure which could be used in place of the current Mutex + CondVar, and is no_std¹ and const-constructible². I've been playing around with it in a separate repo so I could test and document the implementation stand-alone.

There are three possible drawbacks I see with the implementation:

1. Additional unsafe. I feel reasonably confident in the implementation, all of my local tests and all of qcell's tests pass under MIRI and have reasonable coverage, but I know this could always be a concern and welcome any soundness audit.
2. Explicitly does not reclaim memory. The current implementation actually doesn't reclaim memory either (std's HashSet never shrinks automatically, and there are no calls to trigger such), but it theoretically could, whereas this implementation relies on memory persisting for soundness reasons. I also don't think this is likely a concern since the number of distinct TypeIds is a compile-type constant.
3. Changes to performance characteristics. It's hard to speculate on performance without knowing where, if any, TCell is used that's performance-critical code section, but traversing a linked list is likely slower if the number of distinct TypeIds is very large.

Footnotes

1. Requires alloc, and the wait_to_insert method is std-only. ↩

2. I think this would remove the need for the once_cell dependency. ↩

[uazu]

I needed some clear early-morning time to try and understand this. I'm not worried about not reclaiming memory, for the same reasons you state. The O(N) performance is also not a concern, since this is only checked at owner-creation time, and we expect owners to be relatively long-lived, and to be based on relatively few types, which in any case is bounded. But this is pretty involved and complicated unsafe, with orderings and races to protect against and so on, and so it's a risk in terms of overlooked situations or pathways. I trust the work you've done on this, i.e. I trust that you've done all you can to check that it is fully sound, but I can't realistically maintain this code if it is put in qcell. With my current post-Covid brain, I cannot rapidly see and check all the possible failure modes -- maybe after some more recovery. But anyway there are other concerns:

I want to keep qcell as easy as possible to review, for people who are not necessary skilled at reviewing unsafe. That is to encourage adoption, especially in environments that insist on checking their unsafe dependencies or are otherwise risk-averse. So I think putting it in qcell is out, and using this code for the std case is also out.

If you create this as a separate crate, maybe qcell could use it as a dependency for the no_std TCell case, e.g. with a "no_std_tcell" feature or something like that. It has a cost in terms of needing a high level of skill to review, but it opens up possibilities that are not available right now. Each no_std use-case is different, but if a project is happy to use it based on their own testing or their own review, then there is a clear benefit of using this code.

What do you think?

[geeklint]

That totally makes sense to me, I think I will work on deploying this as its own crate, and may submit a PR here with the optional dependency at some point in the future once I do, since it sounds like you would be open to that.

[uazu]

Great! Yes, I'd be open to having it as an optional dependency. Thanks.

[geeklint]

Getting around to working on this, I've published the data structure as exclusion-set, and I'm working on a PR for the optional dep. One thing I've noticed is it might take fewer cfg guards if we make TCell and TCellOwner available regardless of feature set, and just cfg-guard the constructor(s) of TCellOwner. But I'd look to your opinion if you think this is more confusing than having the types guarded.

[uazu]

Thanks for the update. Right now tcell is just protected by #[cfg(feature = "std")]. I'd need to see what cfg-guards you'll be adding, but putting them on the constructors sounds okay if that works out better. It makes no difference to the std case, but for no_std I guess a crate user would only find a constructor available if your crate is configured via a feature. That sounds okay.