Do I need a reentrant locks?

[atd...@gmail.com]

Hi,

I have a tree datastructure where mutating some nodes may trigger a mutation on some other tree nodes.

This tree should be accessible by multiple goroutines but mutated by only one at a time.

As such, I wanted to have a global lock on the tree such that mutatiing node methods should acquire this lock beforehand.

But it seems to require for the mutex to be reentrant? 

I have tried to create a very simplified* model to illustrate https://go.dev/play/p/v37cbYQ1jSY

(*) I know people might want to suggest for the Set method to use a lockless variant when iterating over the linked nodes but in the real code, it iterates over user created callbacks instead and I don't think I can expect callbacks writers to juggle between the two kind of methods to avoid deadlocks.

Any suggestion?

[Brian Candler]

Have a public Set() that does the lock and then calls a private internal function, which assumes it's already running under the lock.

https://go.dev/play/p/M1XuC8bxCxL

[atd...@gmail.com]

:) That's what the asterisked note was for in the original question. I don't think I can do that in the real code because the real code is much more complex. Each node actually triggers a callback that may modify another node. That callback is user-created, not framework created so I have no way of knowing if the lock has already been taken.

And I wouldn't want for library users to have to make that distinction themselves.

[Marvin Renich]

* Brian Candler <b.ca...@pobox.com> [220705 09:48]:

> Have a public Set() that does the lock and then calls a private internal
> function, which assumes it's already running under the lock.
> https://go.dev/play/p/M1XuC8bxCxL
>
> On Tuesday, 5 July 2022 at 13:32:26 UTC+1 atd...@gmail.com wrote:
>
> > Hi,
> >

> > I have a tree datastructure where mutating some nodes *may *trigger a

> > mutation on some other tree nodes.
> >
> > This tree should be accessible by multiple goroutines but mutated by only
> > one at a time.
> >
> > As such, I wanted to have a global lock on the tree such that mutatiing
> > node methods should acquire this lock beforehand.
> >
> > But it seems to require for the mutex to be reentrant?
> >

> > I have tried to create a very simplified*** model to illustrate
> > https://go.dev/play/p/v37cbYQ1jSY
> >
> > (***) I know people might want to suggest for the Set method to use a

> > lockless variant when iterating over the linked nodes but in the real code,
> > it iterates over user created callbacks instead and I don't think I can
> > expect callbacks writers to juggle between the two kind of methods to avoid
> > deadlocks.
> >
> > Any suggestion?
> >
> >

Note also that for referencing a Node to be safe, you must do one of two
things: either use sync/atomic for all reads and writes of Num
(assuming the data in the tree is of a type that can be handled by
sync/atomic), or use sync.RWMutex instead of sync.Mutex, and use RLock
on reads and Lock on writes.

If Node has more than one data field, e.g. {Name string; Age int; ...},
you will have to go with the RWMutex option.

...Marvin

[Marvin Renich]

* atd...@gmail.com <atd...@gmail.com> [220705 10:03]:

> :) That's what the asterisked note was for in the original question. I
> don't think I can do that in the real code because the real code is much
> more complex. Each node actually triggers a callback that may modify
> another node. That callback is user-created, not framework created so I
> have no way of knowing if the lock has already been taken.
>
> And I wouldn't want for library users to have to make that distinction
> themselves.

Have the Set method always take some type of context, which is a pointer
type. If the context is nil, assume a top-level call to Set, otherwise
use the context to decide what to do. All the callbacks will be
required to accept a context and pass it to the Set method.

If you have multiple goroutines that can be making top-level Set calls,
I see no way around using something to distinguish top-level calls from
Set within callbacks.

...Marvin

> On Tuesday, July 5, 2022 at 3:48:16 PM UTC+2 Brian Candler wrote:
>
> > Have a public Set() that does the lock and then calls a private internal
> > function, which assumes it's already running under the lock.
> > https://go.dev/play/p/M1XuC8bxCxL
> >
> > On Tuesday, 5 July 2022 at 13:32:26 UTC+1 atd...@gmail.com wrote:
> >
> >> Hi,
> >>

> >> I have a tree datastructure where mutating some nodes *may *trigger a

> >> mutation on some other tree nodes.
> >>
> >> This tree should be accessible by multiple goroutines but mutated by only
> >> one at a time.
> >>
> >> As such, I wanted to have a global lock on the tree such that mutatiing
> >> node methods should acquire this lock beforehand.
> >>
> >> But it seems to require for the mutex to be reentrant?
> >>

> >> I have tried to create a very simplified*** model to illustrate
> >> https://go.dev/play/p/v37cbYQ1jSY
> >>
> >> (***) I know people might want to suggest for the Set method to use a

[atd...@gmail.com]

You're absolutely right. (I wrote the simplified example a bit too fast and missed that in a few places https://go.dev/play/p/9fk_yt0vkHD) 

To add the general motivation, I have a reactive UI tree and need to introduce concurrency (for when async data fetching is done and the data is reintroduced,, essentially mutating the tree).

[robert engels]

This is a recipe for bad bugs. Use defensive programming - grab the lock in the top-level functions, have private functions like ‘doXXXXWithLock()’ as a signal to the developer that they must be holding the lock.

Allowing callbacks to call back into a concurrent safe structure is very difficult - because the callbacks can easily be made async as well.

I would just re-entrant locks. And ensure that no locks are held when the callback is made - or if it is - it needs to be heavily documented on what the callee can do.

Still, in your case without detailing api design available I am guessing you are going to run in deadlocks very quickly.

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/YsRLSsBPXIbN0Nob%40basil.wdw.

[robert engels]

I would put all of the mutations on a queue so they are single threaded.

[atd...@gmail.com]

Yes, while I'm grateful for Marvin's suggestion, I also don't think that I can put the onus on the developper to pass the right info about how framework methods are called. Even in terms of API, that would be too heavy. And this is essentially trying to have re-entrant lock behavior without reentrant locks.

The goal of using a top level mutex was actually  to serialize mutations to the tree. Only one potential cascade of mutations would be seen at a time regardless of which goroutine it is initiated from.

I'm afraid the real API is already too large to be duplicated for lock-awareness, anyway.

I don't really see a way without lock reentrancy :/

[Brian Candler]

But a bigger problem was raised: how are you going to deal with *readers* of the tree, who may be reading it concurrently with updates?

[Robert Engels]

I would use re-entrant read/write locks. 

If that lags due to concurrency contention you’ll probably need to use various lock free techniques - copy on write being the easiest but may not work if the data structures are large. Look at Java ConcurrentMap for other ideas (locks per “partition”)

Check out github/robaho/go-concurrency-test for ideas. 

On Jul 5, 2022, at 11:50 AM, Brian Candler <b.ca...@pobox.com> wrote:

But a bigger problem was raised: how are you going to deal with *readers* of the tree, who may be reading it concurrently with updates?

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/9f2a1604-96fe-46ee-885d-08e307fd1c3cn%40googlegroups.com.

[atd...@gmail.com]

Hmmh, as I'm thinking about it some more, although a reentrant lock may help, it does not completely solve the issue.

Basically, I need a mutating goroutine to be guaranteed to have sole ownership of the datastructure as long as it isn't done modifying it.

A reentrant lock doesn't help if a critical section where all the mutations happen has not been established in each new goroutine.

Basically 

go func(){

    data := http.Client.Get(...);

    node.Set("data",converted(data))

} 

would be fine but 

go func(){

    data,err := http.Client.Get(ctx,...); if err!= nil{};

    node.SetData("tickers", convert(data))

    // not locked inbetween statements

    node.Set("event","fetch", String("done"))

}

could be incorrect as the goroutine could be preempted while the lock is not taken. At which point the structure may encounter simulatenous mutations by multiple goroutines.

It's a bit annoying. Seems like I need to expect discipline from the library user to make all mutations in a critical section (in spawned goroutines).

At best, to alleviate the problem a little, I can handle data fetching at the framework level.

But in that case, I probably don't need a re-entrant lock in my specific use-case.

[Robert Engels]

As I said, make the mutating op simply record the desired op on a queue and process the serially on another thread.  You are essentially implementing transactions. 

On Jul 5, 2022, at 9:57 PM, atd...@gmail.com <atd...@gmail.com> wrote:

Hmmh, as I'm thinking about it some more, although a reentrant lock may help, it does not completely solve the issue.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/9451bc1f-e527-414a-bf6a-73da4bb06b49n%40googlegroups.com.

[Brian Candler]

On Wednesday, 6 July 2022 at 11:33:29 UTC+1 ren...@ix.netcom.com wrote:

As I said, make the mutating op simply record the desired op on a queue and process the serially on another thread.  You are essentially implementing transactions. 

But how do you protect tree *readers* from having mutations take place under their feet? You could serialize all reads as well, and copy the results. But I don't think that's what the OP was intending.

You could have aRWMutex, but then it's up to the API caller to obtain that mutex *for as long as necessary* (e.g. while traversing part of the tree).

Depending on the use case, a "functional" approach might be worth considering:

- nodes are strictly immutable

- if you need to modify a node, create a new node instead

- recursively repeat for every other node that holds a pointer to this node.

- atomically update the "tree root" pointer

Then each reader sees a snapshot of the tree at a point in time, and garbage collection should take care of the rest.

[Robert Engels]

Depends on if you “concurrent” readers or serialized interlaced ones. 

It depends on you transaction semantics - eg dirty reads, etc. 

It is fairly easy for readers to grab the read lock and the writer thread (since they were added to a queue) to grab the write lock when it has work to do. 

Like I said, a copy on write - partitioned - can be highly effective. 

Review the ConcurrentHashMap source for an efficient implementation of a complex data structure that is highly concurrent for both reading and writing. 

If you have a tree, you would most likely partition by branches. 

The idea is to mutate only a portion of the structure and efficiently swap it it when ready. 

On Jul 6, 2022, at 5:59 AM, Brian Candler <b.ca...@pobox.com> wrote:



--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/888413c1-d4ff-4752-a607-2a3f2196e1dfn%40googlegroups.com.

[atd...@gmail.com]

Well, in my case, only the writing goroutine should be able to have access to the datastructure (to keep the invariants). So I think a mutex should do the trick.

Indeed, it looks like transactions or a reimplementation of a UI thread/event loop.

A concurrent hash=array mapped trie might indeed help if reads had to happen concurrently with writes.

In my experience though, this is allocation heavy and for one of my current targets, it might be impractical: wasm in the browser is highly sensitive to allocations and those concurrent datastructures rely heavily on copy-on-write.

For now, my main idea is to deal with establishing critical sections in the main goroutine (which is framework handled so should be fine)

and unfortunately, document that framework users spawning their own goroutine should establish a critical section where all tree access/mutation should happen, by taking the global lock.

One alternative would be storing operations into a queue as suggested and then passing it to a tree modifying goroutine. Might be better although it might add some API surface. Need to think about it.

[atd...@gmail.com]

So it seems that reentrant locks are a hard requirement after all.

The reason being that an event handler can itself trigger an event which will be handled by a similar callback synchronously. (basically, callback composition)

If the first event handler locks the UI tree, the next synchronous callback will also attempt to take the lock. If no lock reentrancy, it's a deadlock.

This is the same scenario as described here (which doesn't seem to have any satisfying answer)  https://stackoverflow.com/questions/30469808/recursive-critical-sections-in-go

For now, I'm going to take advantage of the fact that there is no goroutine preemption in wasm  to make locking in event handling callbacks optional (using trylock).

That's a ugly hack, but there is no way around it for now.

***and yes, I have thouhgt about sending mutating functions to a goroutine dedicated to call them via a channel (basically a UI thread) but that would make the API too cumbersome to use by the end users as they  would now have to remember to create closures and put them on a channel. A tedious DX only because we need to be concurrent-aware. Not even that concurrency is required all the time.****