Lock slice before reading and modifying it

Question

My experience working with Go is recent and in reviewing some code, I have seen that while it is write-protected, there is a problem with reading the data. Not with the reading itself, but with possible modifications that can occur between the reading and the modification of the slice.

type ConcurrentSlice struct {
    sync.RWMutex
    items []Item
}

type Item struct {
    Index int
    Value Info
}

type Info struct {
    Name        string 
    Labels      map[string]string
    Failure     bool

}

As mentioned, the writing is protected in this way:

func (cs *ConcurrentSlice) UpdateOrAppend(item ScalingInfo) {
    found := false
    i := 0
    for inList := range cs.Iter() {
        if item.Name == inList.Value.Name{
            cs.items[i] = item
            found = true
        }
        i++
    }
    if !found {
        cs.Lock()
        defer cs.Unlock()

        cs.items = append(cs.items, item)
    }
}

func (cs *ConcurrentSlice) Iter() <-chan ConcurrentSliceItem {
    c := make(chan ConcurrentSliceItem)

    f := func() {
        cs.Lock()
        defer cs.Unlock()
        for index, value := range cs.items {
            c <- ConcurrentSliceItem{index, value}
        }
        close(c)
    }
    go f()

    return c
}

But between collecting the content of the slice and modifying it, modifications can occur.It may be that another routine modifies the same slice and when it is time to assign a value, it no longer exists: slice[i] = item

What would be the right way to deal with this?

I have implemented this method:

func GetList() *ConcurrentSlice {
    if list == nil {
        denylist = NewConcurrentSlice()
        return denylist
    }
    return denylist
}

And I use it like this:

concurrentSlice := GetList()
concurrentSlice.UpdateOrAppend(item)

But I understand that between the get and the modification, even if it is practically immediate, another routine may have modified the slice. What would be the correct way to perform the two operations atomically? That the slice I read is 100% the one I modify. Because if I try to assign an item to a index that no longer exists, it will break the execution.

Thank you in advance!

Answer 1

The way you are doing the blocking is incorrect, because it does not ensure that the items you return have not been removed. In case of an update, the array would still be at least the same length.

A simpler solution that works could be the following:

func (cs *ConcurrentSlice) UpdateOrAppend(item ScalingInfo) {
    found := false
    i := 0
    cs.Lock()
    defer cs.Unlock()

    for _, it := range cs.items {
        if item.Name == it.Name{
            cs.items[i] = it
            found = true
        }
        i++
    }
    if !found {
        cs.items = append(cs.items, item)
    }
}

Answer 2

Data structures 101: always pick the best data structure for your use case. If you’re going to be looking up objects by name, that’s EXACTLY what map is for. If you still need to maintain the order of the items, you use a treemap

Concurrency 101: like transactions, your mutex should be atomic, consistent, and isolated. You’re failing isolation here because the data structure read does not fall inside your mutex lock.

Your code should look something like this:

func {
 mutex.lock
 defer mutex.unlock
 check map or treemap for name
 if exists update
 else add
}

Answer 3

Use a sync.Map if the order of the values is not important.

type Items struct {
    m sync.Map
}

func (items *Items) Update(item Info) {
    items.m.Store(item.Name, item)
}

func (items *Items) Range(f func(Info) bool) {
    items.m.Range(func(key, value any) bool {
        return f(value.(Info))
    })
}

Answer 4

After some tests, I can say that the situation you fear can indeed happen with sync.RWMutex. I think it could happen with sync.Mutex too, but I can't reproduce that. Maybe I'm missing some informations, or maybe the calls are in order because they all are blocked and the order they redeem the right to lock is ordered in some way.

One way to keep your two calls safe without other routines getting in 'conflict' would be to use an other mutex, for every task on that object. You would lock that mutex before your read and write, and release it when you're done. You would also have to use that mutex on any other call that write (or read) to that object. You can find an implementation of what I'm talking about here in the main.go file. In order to reproduce the issue with RWMutex, you can simply comment the startTask and the endTask calls and the issue is visible in the terminal output.

EDIT : my first answer was wrong as I misinterpreted a test result, and fell in the situation described by OP.

Answer 5

tl;dr;

If ConcurrentSlice is to be used from a single goroutine, the locks are unnecessary, because the way algorithm written there is not going to be any concurrent read/writes to slice elements, or the slice.

If ConcurrentSlice is to be used from multiple goroutines, existings locks are not sufficient. This is because UpdateOrAppend may modify slice elements concurrently.

A safe version woule need two versions of Iter:

This can be called by users of ConcurrentSlice, but it cannot be called from `UpdateOrAppend:

func (cs *ConcurrentSlice) Iter() <-chan ConcurrentSliceItem {
    c := make(chan ConcurrentSliceItem)

    f := func() {
        cs.RLock()
        defer cs.RUnlock()
        for index, value := range cs.items {
            c <- ConcurrentSliceItem{index, value}
        }
        close(c)
    }
    go f()

    return c
}

and this is only to be called from UpdateOrAppend:

func (cs *ConcurrentSlice) internalIter() <-chan ConcurrentSliceItem {
    c := make(chan ConcurrentSliceItem)

    f := func() {
        // No locking
        for index, value := range cs.items {
            c <- ConcurrentSliceItem{index, value}
        }
        close(c)
    }
    go f()

    return c
}

And UpdateOrAppend should be synchronized at the top level:

func (cs *ConcurrentSlice) UpdateOrAppend(item ScalingInfo) {
cs.Lock()
defer cs.Unlock()
....
}

Here's the long version:

This is an interesting piece of code. Based on my understanding of the go memory model, the mutex lock in Iter() is only necessary if there is another goroutine working on this code, and even with that, there is a possible race in the code. However, UpdateOrAppend only modifies elements of the slice with lower indexes than what Iter is working on, so that race never manifests itself.

The race can happen as follows:

1. The for-loop in iter reads element 0 of the slice
2. The element is sent through the channel. Thus, the slice receive happens after the first step.
3. The receiving end potentially updates element 0 of the slice. There is no problem up to here.
4. Then the sending goroutine reads element 1 of the slice. This is when a race can happen. If step 3 updated index 1 of the slice, the read at step 4 is a race. That is: if step 3 reads the update done by step 4, it is a race. You can see this if you start with i:=1 in UpdateOrAppend, and running it with the -race flag.

But UpdateOrAppend always modifies slice elements that are already seen by Iter when i=0, so this code is safe, even without the lock.

If there will be other goroutines accessing and modifying the structure, you need the Mutex, but you need it to protect the complete UpdateOrAppend method, because only one goroutine should be allowed to run that. You need the mutex to protect the potential updates in the first for-loop, and that mutex has to also include the slice append case, because that may actually modify the slice of the underlying object.

If Iter is only called from UpdateOrAppend, then this single mutex should be sufficient. If however Iter can be called from multiple goroutines, then there is another race possibility. If one UpdateOrAppend is running concurrently with multiple Iter instances, then some of those Iter instances will read from the modified slice elements concurrently, causing a race. So, it should be such that multiple Iters can only run if there are no UpdateOrAppend calls. That is a RWMutex.

But Iter can be called from UpdateOrAppend with a lock, so it cannot really call RLock, otherwise it is a deadlock.

Thus, you need two versions of Iter: one that can be called outside UpdateOrAppend, and that issues RLock in the goroutine, and another that can only be called from UpdateOrAppend and does not call RLock.