This task is automatically imported from the old Task Issue Board and it was originally created by Keziah Wesley. Original issue is here.

Some Rust libs are using pointers in ways that are incorrect when the underlying allocations are freed

At least 5 places in the codebase use pointers to create IDs that are intended to be unique and stable, e.g. Id(Rc::downgrade(&self.rc).as_ptr() as *const () as usize).

(The 5 usages can be found in these search results; note that that search also returns two false positives that are not instances of the pattern in question.)

In some runtime circumstances, an ID produced this way can end up identifying a different object than intended, which would cause logically incorrect behavior.

The IDs can be invalid due to weak reference semantics

In some cases, these pointers are obtained using Weak::as_ptr. The value returned by that function is unspecified if the strong count of the Rc is 0. I am not sure if this would cause problems in practice, except when it overlaps with the next issue:

IDs can collide when addresses are reused

Even an ID that is valid when it is generated can later refer to a different object, e.g. if a sequence of events like this occurs:

Some ObjectA is created; its ID is obtained and stored.
The last reference to the Rc holding ObjectA is dropped; its memory is reclaimed.
A new ObjectB is created. It happens to be allocated at the same address as ObjectB was.
Now the ID that originally referred to ObjectA refers to ObjectB!

Address reuse for objects of the same type is likely to occur in practice if there is some timeframe where many objects are being created and destroyed.

Possible solutions

Maybe some IDs could be replaced with (wrapped) weak references

Using pointers for IDs correctly would require ensuring the addresses are unique as long as the IDs are alive; this is exactly what Rc::weak exists to do. While this is a clean solution, the IDs are no longer plain data; they become more expensive to clone, can't be serialized, and would need wrappers to be compared by identity. I don't know if those are important considerations for how these IDs are used.

IDs can be assigned by incrementing a global

This requires adding a new field to references to remember the assigned ID, but this way the IDs would still be Copy types.

Comments:

Keziah Wesley reports a new STANDUP for today (2022-03-18):

Progress: I implemented a sound API for ID generation. It should be finished by 2022-03-18. (Enso Bot - Mar 18, 2022)

Keziah Wesley reports a new 🔴 DELAY for the last Friday (2022-04-01):

Summary: There is 16 days delay in implementation of the Logic bug in a pattern used to obtain IDs. (#181610155) task. It will cause 0 days delay for the delivery of this weekly plan.

Delay Cause: Latency caused by nullability design issue that came up. Started and finished other tasks before getting back to this.

Possible solutions: Should have reduced back-and-forth about the issue with a quick meeting. (Enso Bot - Apr 4, 2022)

Keziah Wesley reports a new STANDUP for the last Friday (2022-04-01):

Progress: Examined/measured performance characteristics of safe-ids; investigated a test crash that reveals a little problem with no obvious perfect solutions. Handed off 2nd GL optimization; measured its impact; had a quick look at my next potential target, Graph::new. It should be finished by 2022-04-03.

Next Day: Next day I will be working on the ##181610155 task. TBD after meeting. (Enso Bot - Apr 4, 2022)

Status: postponed until overlarge function that causes compilation problems is refactored. See discussion in PR. (Keziah Wesley - May 26, 2022)

enso-org / enso

Logic bug in a pattern used to obtain IDs. #5185