Merge lp://qastaging/~mixxxdevelopers/mixxx/atomic-co into lp://qastaging/~mixxxdevelopers/mixxx/trunk

Sorry for taking so long to get you feedback :( better late than never?

I've skimmed the whole thing once but for now will just comment on controlobjectbase.h:

* static const int cReaderSlotCnt
  - Should not be static.. if multiple object files include controlobjectbase.h then we will get duplicate symbols during linking. This builds fine now because only controlobject.o includes it. You could just leave it as a const int.

* sizeof(T) <= sizeof(void*) is not enough to determine atomicity -- for example, if the pointer to a value is not memory-aligned then that breaks atomicity guarantees. I think to be sure we need to use a compiler directive in the ATOMIC=true template to request m_value is aligned.

* Need comments on all methods declarations in controlobjectbase.h. This is such a crucial file it needs plenty of documentation for future developers :).

* ControlObjectRingValue::tryGet()
  - why return an int when it's functionally a bool (i.e. was it successful)
  - bool originalSlots = m_readerSlots.fetchAndAddAcquire(-1);
  Should instead be:
    bool originalSlots = m_readerSlots.fetchAndAddAcquire(-1) <= 0;

The reason is this: m_readerSlots can go negative if too many concurrent reads occur simultaneously. It can even go negative if a write is happening and two reads happen right after the write has swapped m_readerSlots with the value 0 (the second read will see -1). So to detect whether a read should be successful, you should check if the value is <= 0.

  - Why is cReaderSlotCnt the number of concurrent readers allowed also the size of the ring buffer? I can't think of a reason why those 2 values need to be the same.
  - How did you choose 7?

* ControlObjectValue::getValue
  - Can you use ARRAYSIZE on m_ring instead of hard-coding cReaderSlotCnt+1 ? It should be compile-time.
  - When getValue() fails to read a slot, it goes backward one. This means we sacrifice consistency for speed. We need to make sure people understand this is a trade-off that is part of the control system. Under high load, the control system will possibly serve a stale result when you get().

Thank you for review!

> * static const int cReaderSlotCnt
OK

> * sizeof(T) <= sizeof(void*) is not enough to determine atomicity
OK, It should be save in any case, if we cast to an QAtomicPointer container
But that looks really ugly. But better ugly than a failure!

> * Need comments
OK

> * ControlObjectRingValue::tryGet()
Fixed.

> - Why is cReaderSlotCnt the number of concurrent readers allowed also the size of the ring buffer? I can't think of a reason why those 2 values need to be the same.

In worst case, each reader can consume a reader slot from a different ring element. In this case there is still one ring element available for writing.

> - How did you choose 7?
I want to have 8 ring element because it is a 2^x value.
To be sure we are lock free, we need on ring element for each accessing thread. I have not counted CO accessing threads but I think 8 should not be reached. We should verify this.
But It should also work with more tasks, because it is very unlikely that 8 threads are in the critical section at the same time. And when it relay happens, the additional threads are locked.

> - Can you use ARRAYSIZE
OK

> - When getValue() fails to read a slot, it goes backward one. This means we sacrifice consistency for speed. We need to make sure people understand this is a trade-off that is part of the control system. Under high load, the control system will possibly serve a stale result when you get().

If there are enough ring elements this should not happen. The value is not stale, because the more recent value is not entirely written.

There appear to be some issues with class ControlObjectValue<T, true>.

First, assuming sizeof(double) <= sizeof(void*) (which is the case on my machine), this class is used for ControlObjectValue<double>. This results in casts like reinterpret_case<void*>(x), where x is a double. These aren't legal casts (and as such, I can't actually compile the branch). To store a double in a QAtomicPointer<void*>, you have to do something like (assuming sizeof(void*)==sizeof(uint64_t) and sizeof(double)==sizeof(uint64_t)):

    QAtomicPointer<void*> qap;
    double x = 1.5;
    qap = reinterpret_cast<void**>(*reinterpret_cast<uint64_t*>(&x));

    void *qap_val = qap;
    double y = *reinterpret_cast<double*>(&qap_val);
    cout << y << endl; // prints 1.5

(some of the complexity exists because QAtomicPointer doesn't overload the deref (*) operator, it provides an implicit type conversion to T*, which means *qap here actually dereferences our stored "pointer", so we have to use void *p = gap which invokes the operator void*() without dereferencing anything)

But regardless, we're not really gaining anything from QAtomicPointer. It's storing a T* in a data member marked volatile (which doesn't even guarantee alignment afaik, which is something we need), and for store and retrieve operations it's not doing anything special (see src/corelib/thread/q{,basic}atomic.h in the qt source). We'd be better off just using a volatile void * in the class, just as a reduction in complexity.

Along these lines:
        return reinterpret_cast<T>(m_container);

As far as I can tell, this is actually trying to cast the QAtomicPointer<void*> to T (an illegal case). This is almost certainly not desirable, but we really want the thing we've stored in the QAP<void*>, cast to T (which requires some bit-fiddling like what I wrote above).

Happened to come across this:

Load a song.
Set a hotcue (if not already set).
Hold down the hotcue key (eg. z).
Press play/pause (either in the UI or on the keyboard).

In truck, it allows you to continue playing the track without holding the hotcue key; in the branch, it segfaults. It happens both with and without the QAtomicPointer code, so I guess it's another change. It seems easily repeatable, so I'm not attaching a backtrace, but I can if needed.

RE: My previous comment about atomicity.. I think we can actually get around it without QAtomicPointer, we just need to use compiler-specific alignment directives.

e.g. for GCC: __attribute__ ((aligned (__BIGGEST_ALIGNMENT__)))

Now for some comments on the broader changes in the branch outside of COBase:

I think COBase is a nice wait-free base for CO to be based on. Getting rid of the proxies (in this case, turning them into shims) is problematic though. The valueChanged() signal is dangerous and can cause infinite processing loops.

If you listen to valueChanged and some code path in your slot for valueChanged can set the control again then you can have an infinite loop. The proxies are an important part of preventing this because when they queue their change to the control system, they provide a pointer to themselves. CO::sync() then does not deliver the change to the proxy that changed the value.

We are also going to run into many logic errors as we track down the places in Mixxx that have encoded assumptions about the fact that there is an intermediary between setting a COT and the corresponding CO change taking effect.

I think a good solution is one where every control set()/get()s the actual CO value through a proxy that provides a pointer to the original changer. The COBase then emits this pointer in its valueChanged signal. Listening proxies can then check if they originated the set and not emit a valueChanged() in that case.

This brings me to valueChangedFromEngine(double). This signal exists in the first place to be able to differentiate between sets to a control from the current instance of a control or sets to a control from a proxy. What I described from the previous paragraph is just a generalization of valueChangedFromEngine().

> > - Why is cReaderSlotCnt the number of concurrent readers allowed also the size of the ring buffer? I can't think of a reason why those 2 values need to be the same.

> In worst case, each reader can consume a reader slot from a different ring element. In this case there is still one ring element available for writing.

If I understand this right, every slot in the ring buffer can support cReaderSlotCnt readers. (i.e. reads fail after cReaderSlotCnt readers are active). When reads fail, a reader moves backward one in the ring buffer to the previous value to read.

So, worst case scenario (for a write), cReaderSlotCnt*cReaderSlotCnt+1 concurrent reads are occurring and there are no available write slots. I don't see how anything related to cReaderSlotCnt preserves an extra slot for writing? We could just have more readers.

> I want to have 8 ring element because it is a 2^x value.
> To be sure we are lock free, we need on ring element for each accessing thread. I have not counted CO accessing threads but I think 8 should not be reached. We should verify this.
> But It should also work with more tasks, because it is very unlikely that 8 threads are in the critical section at the same time. And when it relay happens, the additional threads are locked.

So, to characterize the scenarios when a thread spin-locks:

When (cReaderCnt+1)*cReaderCnt concurrent reads are occurring, then a reader will be spin-locked.
When cReaderCnt+1 concurrent writes are occurring, then a reader will be spin-locked.

When cReaderCnt*cReaderCnt + 1 concurrent reads are occurring, then a writer will be spin-locked.
When cReaderCnt+1 concurrent writes are occurring, then a writer will be spin-locked.

(there is no actual locking, just busy-waiting).

> > - When getValue() fails to read a slot, it goes backward one. This means we sacrifice consistency for speed. We need to make sure people understand this is a trade-off that is part of the control system. Under high load, the control system will possibly serve a stale result when you get().

> If there are enough ring elements this should not happen. The value is not stale, because the more recent value is not entirely written.

This can happen under excessive read-pressure (> cReaderSlotCnt concurrent reads) alone so I don't think that's true... (unless I'm missing something about how this works).

I don't see why cReaderSlotCnt and the ring buffer size need to be related. You could just pick cReaderSlotCnt as INT_MAX and make the ring buffer size 8 and we would effectively never have inconsistent reads under read pressure alone. Isn't cReaderSlotCnt just an arbitrary value we count down to 0 from?

atomicity:

I think it should be really fine to simply revert #3355.
But RJ is right, the native alignment is not guarantied by the c++ standard but actually the compilers will align natively by default.
I have a look at the implementation of QtAtomicInt and they seems not care about alignment.

But it will not hurt to do something like this, just to be sure:

T m_value __attribute__ ((aligned(sizeof(void*)))); // GCC
T __declspec(align(sizeof(void*))) m_value; // MSVC

This is a nice thread:
http://stackoverflow.com/questions/5002046/atomicity-in-c-myth-or-reality

changes outside of COBase:

* Risk of infinite processing loops
Yes this is right. I have already fixed some of those conditions.
My Idea was to solve it in the calling code, to keep the CO core clean and performant.
The key benefit is to get rid of the sync thread.
Do you have a idea to solve it without it?

* intermediary between setting a COT and the corresponding CO change
This should be fixed in the calling code in any case, because this is was on of my goals.

>
> I think a good solution is one where every control set()/get()s the actual CO
> value through a proxy that provides a pointer to the original changer. The
> COBase then emits this pointer in its valueChanged signal. Listening proxies
> can then check if they originated the set and not emit a valueChanged() in
> that case.
>
> This brings me to valueChangedFromEngine(double). This signal exists in the
> first place to be able to differentiate between sets to a control from the
> current instance of a control or sets to a control from a proxy. What I
> described from the previous paragraph is just a generalization of
> valueChangedFromEngine().
>

We might introduce a
setFrom(double value, QObject* source)
function and emit the the source pointer along with the value change event.
Then the receiver can throw the event away if it is it's own.

But I would prefer not to introduce this overhead.
The current rule is very simple and easy to understand:
"If you change a CO you get the signal ... always"

But there is still work to do find all places where this causes issues.

Number of Reader slots:

RJ, you understand the concept correct. I am afraid better then me ;-)

You idea is a relay good workaround for the readers spin lock. I will change the cReaderSlots to Maximum.

But there is still a reader count limit:
Since a writer consumes all reader slots from a writer we have a writer spin-lock if one reader reads on every ring element (cRingSize).

I think this condition is really hard to achieve in real live. Do we have to deal with it?

Sometimes it's hard to tell that you're going to get an infinite loop. The loop could even span across multiple different CO changes. It's much easier to code and requires less of a "full view" of the system if the CO you set() does not emit a valueChanged for the set(). I have an idea for how to do this without sacrificing any performance. I'll hack it up in a branch based on this one and send you a merge request.

In my master_sync work, the infinite-CO loop is a humongous pain in the ass. Setting something to master will set other things to slave, and setting other things to slave might set something else to master... If I had a simple call to ask "did I initiate this chain of events?" then I could avoid a lot of ugly code I've had to create.

Also, I just noticed the change to ControlObjectThreadMain -- that needs to be reverted. When you use a COTM/COTW in Mixxx code you are declaring that valueChanged signals are expected to be delivered by the GUI/main thread so we need to save this behavior or we will run into trouble.

Without posting the event to the Qt event queue as it was implemented there's no guarantee that a valueChanged signal coming from the ControlObject will be received on the GUI thread.

I added COTM main-thread proxying back in lp:~rryan/mixxx/atomic-co.

Here some results:

* I think the CO is registered twice: In ControlObject::ControlObject() and in ControlDoublePrivate::getControl()
* it is not clear where the home of m_sqCOHash is, for me it should move to ControlDoublePrivate
* all static functions should have the leading comment // static
* control.cpp/h should be renamed to controldoubleprivate.cpp/h
* DRY violation in overloaded ControlObject::ControlObject()
* setMidiParameter needs a pSender
* gcc complains about the missing virtual destructors in the *Behaviour classes
* i do not like to distingish between valueChanged(v) and valueChangedByThis(v), because it is most likely that if an object wants to receive valueChangedByThis(v) it will also receive valueChanged(v).
For this propose we should implement a new proxy which sends out pSender, or allow to use ControlDoublePrivate directly

please not the merge request with additional changes

On May 16, 2013 7:46 PM, "Daniel Schürmann" <email address hidden> wrote:
>
> Review: Needs Fixing
>
> Here some results:
>
> * I think the CO is registered twice: In ControlObject::ControlObject()
and in ControlDoublePrivate::getControl()

On mobile - sorry for brevity.

We have to keep this until we get rid of CO::getControl

> * it is not clear where the home of m_sqCOHash is, for me it should move
to control double private

Agree but see above.

> * all static functions should have the leading comment // static

Thx will change

> * control.cpp/h should be renamed to controldoubleprivate.cpp/h

I think all control implementations should go in control.h so there's one
header to include. I could see this not being a public part of the control
system so maybe that makes sense.

> * DRY violation in overloaded ControlObject::ControlObject()

Will fix with a common init method

> * setMidiParameter needs a pSender

The sender in this case is the midi controller and the midi controller uses
raw COs instead of creating a COT so its not correct to do this how you did
... When MController gets changed to use COT then that should be the sender

> * gcc complains about the missing virtual destructors in the *Behaviour
classes

K can fix

> * i do not like to distingish between valueChanged(v) and
valueChangedByThis(v), because it is most likely that if an object wants to
receive valueChangedByThis(v) it will also receive valueChanged(v).

Yes but that's because by default code is not safe until carefully reviewed
for infinite loop prevention. Once it is reviewed it is natural we would
like to respond to both internal and external. There may be cases in the
future where you would only want to react to internally sourced changes.

> For this propose we should implement a new proxy which sends out pSender,
or allow to use ControlDoublePrivate directly

I've explained why we need this signal -- it's safer for writing code
because it avoids infinite feedback loops and it allows you to distinguish
between local and remote value changes (which is already used today in
mixxx).

Can you explain why you think we should not do this?

>
> please not the merge request with additional changes
> --
> https://code.launchpad.net/~mixxxdevelopers/mixxx/atomic-co/+merge/153696
> You are reviewing the proposed merge of
lp:~mixxxdevelopers/mixxx/atomic-co into lp:mixxx.

> > * i do not like to distingish between valueChanged(v) and
> valueChangedByThis(v), because it is most likely that if an object wants to
> receive valueChangedByThis(v) it will also receive valueChanged(v).
>
> Yes but that's because by default code is not safe until carefully reviewed
> for infinite loop prevention. Once it is reviewed it is natural we would
> like to respond to both internal and external. There may be cases in the
> future where you would only want to react to internally sourced changes.
>
> > For this propose we should implement a new proxy which sends out pSender,
> or allow to use ControlDoublePrivate directly
>
> I've explained why we need this signal -- it's safer for writing code
> because it avoids infinite feedback loops and it allows you to distinguish
> between local and remote value changes (which is already used today in
> mixxx).
>
> Can you explain why you think we should not do this?
>

I the meanwhile I am convinced that we don't need the loop back signal at all.
It is allays lower overhead to call the slot manually if required and it is
more easy to track when reading the code.