[jcalvinowens]

The Level<> abstraction is a really neat way to have your cake and eat it too: you only need a consistent arbitrary order to avoid deadlocks, but the order can have performance consequences when some locks are more coarse than others.

But the example seems backwards to me: unless every callsite that locks any item always locks the big global lock first (probably not true, because if you serialize all item access on a global lock then a per-item lock serves no purpose...), aren't you begging for priority inversions by acquiring the big global lock before you acquire the item lock?

My only gripe is missing the obvious opportunity for Ferengi memes ("rules of acquisition") :D :D

[vlovich123]

There’s no global lock. There’s a linear MutexKey<N> that a lock of Level >= N has to be acquired with. Aquiring it consumes MutexKey<N> and hands you back MutexKey<Level+1> where Level is the N of the level you’re locking.

There’s no priority inversion possible because locks can only ever be held in decreasing orders of priority - you can’t acquire a low priority lock and then a high priority lock since your remaining MutexKey won’t have the right level.

[jcalvinowens]

In the example it seems pretty clear to me that:

    Mutex::new(AppConfig::default());

...is meant to be acquiring a mutex protecting some global config object, yes? That's what I'm calling a "global lock".

> There’s no priority inversion possible because locks can only ever be held in decreasing orders of priority

    T1               T2
    --               --
    small_lock();
                     big_lock();
                     small_lock(); <--- Spins waiting for T1
                 

...and now any other thread that needs big_lock() spins waiting for T2 to release it, but T2 is spinning waiting for T1 to release the (presumably less critical) small lock.

If small_lock is never ever acquired without acquiring big_lock first, small_lock serves no purpose and should be deleted from the program.

[vlovich123]

Mutex::new creates a lock, it doesn’t acquire one.

Look at the API - if big_lock and small_lock are at the same level, you would need to acquire the lock simultaneously for both locks which is accomplished within the library by sorting* the locks and then acquiring. If you fail to acquire small_lock, big lock isn’t held (it’s an all or nothing situation). This exact scenario is explained in the link by the way. You can’t bypass the “acquire simultaneously” api because you only have a key for one level

Your terminology is also off. A lock around a configuration is typically called a fine grained lock unless you’re holding that lock for large swathes of program. Global as it refers to locking doesn’t refer to visibility of the lock or that it does mutual exclusion. For example, a lock on a database that only allows one thread into a hot path operation at a time is a global lock.

* sorting is done based on global construction order grabbed at construction - there’s a singleton atomic that hands out IDs for each mutex.

[jcalvinowens]

No, the entire point of what I was saying is that big_lock and little_lock are at two different levels.

[vlovich123]

If big lock and little lock are at different levels you won’t have a key at the appropriate level to create an inversion by trying to acquire in the first place.

T2 might “spin” waiting for small lock but assuming small lock is released at some point you’ve not got a deadlock (and by construction it’s impossible for small lock to have it’s release blocked on the acquisition of a lock that depends on big_lock).

That’s the whole point of having a level to the locks and to the key that you have to give up to acquire that lock.

Your terminology is also off. Mutexes are not implemented through spin locks. It’s an atomic operation and when lock acquisition fails you call futex_lock (or whatever your OS api is) to have the thread be put to sleep until the lock is acquired.

[yencabulator]

I think what they're trying to say is that sure it's deadlock-free but it might be sacrificing performance.

T2 sits there waiting for small_lock to be available while holding big_lock for a long time.

This bit:

> ...and now any other thread that needs big_lock() spins waiting for T2 to release it, but T2 is spinning waiting for T1 to release the (presumably less critical) small lock.

Which of course leads to conversations like can big_lock be an RWLock, ArcSwap or such.

[jcalvinowens]

This reply is word salad that completely fails to engage with anything I've actually said to you... please don't waste my time with more LLM generated comments.

[bonzini]

Usually a global lock is a lock that is taken outside all others and is taken for large parts of the runtime (or even, everywhere the thread isn't waiting on a condition variable, file descriptor and the like).

Mutex::new(AppConfig::default()) might very well be a small, leaf mutex.

[cryptonector]

> In the example it seems pretty clear to me that:

> Mutex::new(AppConfig::default());

> ...is meant to be acquiring a mutex protecting some global config object, yes? That's what I'm calling a "global lock".

You could certainly have a global lock at the top-most level, but you're not required to. The example is just an example.

[gpm]

> unless every callsite that locks any item always locks the big global lock first (probably not true, because if you serialize all item access on a global lock then a per-item lock serves no purpose...)

A pattern I've definitely both seen and used is

    let guard1 = datastructure_containing_the_whole_world.lock();
    let guard2 = guard1.subset_of_that_datastructure.lock();
    guard1.unlock();
    // Do expensive work
    guard2.unlock();

Which works to parallelize work so long as guard2 isn't contended... and at least ensures correctness and forward progress the rest of the time.

[jcalvinowens]

Agreed! But if you can reverse the acquire order, you can structure the function scopes such that you don't need the explicit unlock() calls, which is a bit nicer IMHO.