libera/#sicl - IRC Chatlog
Search
23:58:23
Bike
obsolete instance is detected by mutating all relevant generic functions to hit the updater on objects with the old stamp
23:59:46
Bike
but i think a change-class concurrent with a dispatch isn't the problem, so much as doing two change-classes concurrently
1:07:59
hayley
I get that CHANGE-CLASS has to be safe, but is it expected that it will succeed with concurrent accesses and/or other CHANGE-CLASSes, instead of signalling if it detects concurrent modification (something like Java collections)?
1:08:30
Bike
i think signaling an error would be fine. the problem is a silent failure leaving objects in an inconsistent state
1:09:56
Bike
you know, like your usual thread 1 alters class -> thread 2 alters class -> thread 2 alters rack -> thread 1 alters rack thing
1:10:55
hayley
Hm, but then to be safe, we require some kind of safety test when getting the rack for an object in any normal accessor or STANDARD-INSTANCE-ACCESS or whatever else.
1:12:10
Bike
easiest thing would probably be to cheap out and e.g. have a couple global locks selected by a hash and grab them during change-class
1:12:25
hayley
Concurrent CHANGE-CLASS can be sort of handled though; either thread 2 notices that it failed the class update and either waits or updates the rack itself, or it signals.
1:14:53
hayley
Well, thread 2 would spin (possibly helping, to make it wait-free) until it sees the object in a consistent state, then reads the class....no, it can't atomically read both class and rack pointers, so it can't test for consistency.
1:17:39
hayley
If the object is updated between reading the class and rack, then later updates would fail and the process would start over (or signal).
1:36:56
hayley
"System checks that Alice has enough money. $1,000 is deducted from her account. Eve smashes in the server with a baseball bat. Bob never receives the money. $1,000 has completely disappeared from the system. The SEC shuts you down for fraud."
1:59:06
hayley
That said, I haven't figured out how to assert that the object is consistent in the end, but I was a bit more confident in that to start with.
2:08:15
hayley
If I remove the part where we help with updating the rack if we notice it is inconsistent w.r.t the class, then my invariant (either some thread is in CHANGE-CLASS or the object is consistent) holds though.
2:14:02
hayley
I guess I can see why trying to help updating wouldn't really help, so we can't really be wait-free without double-word-CAS. Here is the model I wrote: <https://gist.github.com/no-defun-allowed/7ea1c77521cf160c562da201f28e3ed8>
2:16:18
Bike
the other thing that could work is changing the representation of objects so that rather than a class and a rack, they just have a rack, and the rack includes the class. so all that needs to be swapped out is the rack
2:17:21
hayley
(I probably could use an infinite while loop instead of a goto but I couldn't figure how to break out of a loop.
2:25:27
hayley
Well, the SICL GC is designed to work with two-word object headers to some extent. Object headers are allocated from the same dyad free-list that cons cells do, and the mark-compact nursery algorithm requires objects to be at least two words (so single-word allocations would need padding). But that might not be the biggest problem.
2:27:25
hayley
Though from what I know now, putting the class pointer in the rack sounds preferable for platforms without double-word CAS (so everything but x86-64)?
2:29:33
hayley
Another free list for single word allocations could be maintained like the dyad list, as I think only a singly-linked list is made.
5:02:52
hayley
beach: Is there a reason the class is not stored in the rack, other than paying an additional indirection for CLASS-OF and the forementioned simplification of the GC?
5:07:22
hayley
"other than" makes it sound like those are insignificant, which we don't know admittedly.
5:12:13
beach
I don't know. I haven't thought about the consequences of storing the class in the rack.
5:13:46
beach
The class is rarely accessed this way, so I don't think there is any performance penalty involved.
5:15:53
beach
And if it turns out that the class should be in the rack, the second word of the header could be used for the hash value.
5:24:16
heisig
beach: Yes, I am still in the hospital. But there is hope that I'll be released today.
5:26:46
heisig
I thought storing the class in the header is a requirement for the thread-safe CHANGE-CLASS, and that we need a fast class access because we like generic functions so much.
5:31:28
hayley
Well, even with my hack to make dyads work, retrieving the rack is also not wait-free as we wait to get a consistent class and rack.
5:31:55
heisig
Maybe we should have an appendix in the SICL specification, where the discussion about each design decision is written down. Like the X3J13 Issues section of the CLHS.
5:34:11
hayley
The hack is to make concurrent calls to CHANGE-CLASS not leave the object in an inconsistent state, which I got TLA+ to verify.
5:49:53
heisig
So if we do store the class in the rack, we suddenly got one spare slot in a prominent location. Interesting.