Repository navigation
Description
The requirement that dtor is called when no threads hold the lock can be enforced by the token/given_token and is orthogonal. We are experimenting with two approaches:
-
The mutex constructor returns
used_threads \empty, the ablility to allocate an exclusiveuser thghost state for each thread (with). This is bad with a mutex client: consider the main thread initializing some mutex, and then spawns some threadsbrick-libcpp/rocq-brick-libstdcpp/proof/lib/lock_ghost.v
Lines 80 to 83 in be863c8
Lemma login th g s : th ∉ s -> used_threads g s |-- (|==> used_threads g (s ∪ {[ th ]}) ** user g th). t2,t3(which may also spawn threads dynamically and try to grab the mutex). Sinceused_threadsis exclusive, how the threadsloginbecomes a problem -- 2 problems, actually: a). how to distributeused_threads, and b). When a threadthlog in, how does it know thatthis not logged in yet? I sketch 3 attempts here; each is flawed:- The main thread allocates all
usertokens and then distributes them; there must exist a way to distribute them, but for the main thread to distribute a set ofusertot2, it must know the set of threads thatt2will allocate in the future. - We put
userin some invariantuser_inv; then the set of threads already allocated is existentially quantified, and we need some other way to know whatuserhas not been allocated. This might be mitigated by includinguser_invin the thread constructor spec and using the fact that thread spawn always gets a fresh thread ID, but there the mutex can be created after threads are spawned. So the postcondition for thread ctor should probably include the ability to acquire a mutex later, even when the mutex is not created yet (which will be approach 2). - We make
logindepend only on a version ofused_threadswhereused_threadscan be fragmented and distributed to threads, but I don't know if such a model exists whileuser this still exclusive. If we haveused_threads (q1+q2) \empty |-- used_threads q1 \empty ** used_threads q2 \emptythen threadthcan allocateusertwice, which is probably not what we want.
- The main thread allocates all
-
Don't use
user, and a thread keeps track of invariant gnames that it has locked so far (the MUTEX_SET module). Thread constructor returnsmy_mutexes th sa sfwheresa, sf : gset gnames :=\emptyfor threadth, andsais the auth piece thatthkeeps,sfis the frag that is used likeuser(traded into inv for resource); to get resources frommutex_inv := inv \gamma P,thfirst doesmy_mutexes th sa sf |-- |==> my_mutexes th (sa \union {[\gamma]} (sf \union {[\gamma]}), then split the tokenmy_mutexes th (sa \union {[\gamma]} (sf \union {[\gamma]}) |-- |==> my_mutexes th (sa \union {[\gamma]} sf ** my_mutexes_frag th {[ \gamma ]}, and puts the singletonmy_mutexes_fragin inv.
With 2, it does not have the problems that user has, but it does have a new one: since inv gnames are introduced under an \exists, we need a way to know that the gname is not in sa in my_mutexes th sa sf. Can we do this with namespaces/non_atomic invaraints?
Activity
pgiarrusso-sl commentedon Oct 1, 2026
Related/duplicate of #153 ?