negating unsigned....

[Chris M. Thomasson]

Take a look at the code here:

https://pastebin.com/raw/p1E9WN5i

Well there is something stupid I did. The code still works for me, but
its still pissing me off. It involves negating an unsigned int.

Take a look at the following function:
_____________________
void prv_quiesce_begin()
{
// Try to begin the quiescence process.
if (! m_quiesce.exchange(true, std::memory_order_acquire))
{
// advance the current collector and grab the old one.
unsigned int old = m_current.load(std::memory_order_relaxed) &
0xFU;
old = m_current.exchange((old + 1) & 1, std::memory_order_acq_rel);
collector& c = m_collectors[old & 0xFU];

// decode reference count.
//unsigned int refs = old & 0xFFFFFFF0U; HOLY SHIT!!!
long refs = old & 0xFFFFFFF0U;

// verify reference count and previous collector index.
// RL_ASSERT(!(refs & 0x10U) && (old & 0xFU) == (&c -
m_collectors));

// increment and generate an odd reference count.
if (c.m_count.fetch_add(refs + 0x10U,
std::memory_order_release) == (unsigned int)-refs)
{
// odd reference count and drop-to-zero condition detected!
prv_quiesce_complete(c);
}
}
}
_____________________

Now, this makes me feel bad. I should have just wrote it the following
way to begin with... Adding UINT_MAX + 1 should negate the reference
count without any casts:

_____________________
void prv_quiesce_begin()
{
// Try to begin the quiescence process.
if (! m_quiesce.exchange(true, std::memory_order_acquire))
{
// advance the current collector and grab the old one.
unsigned int old = m_current.load(std::memory_order_relaxed) &
0xFU;
old = m_current.exchange((old + 1) & 1, std::memory_order_acq_rel);
collector& c = m_collectors[old & 0xFU];

// decode reference count.
unsigned int refs = old & 0xFFFFFFF0U;

// verify reference count and previous collector index.
// RL_ASSERT(!(refs & 0x10U) && (old & 0xFU) == (&c -
m_collectors));

// increment and generate an odd reference count.
if (c.m_count.fetch_add(refs + 0x10U,
std::memory_order_release) == refs + UINT_MAX + 1)
{
// odd reference count and drop-to-zero condition detected!
prv_quiesce_complete(c);
}
}
}
_____________________


Much better!


refs + UINT_MAX + 1 should equal -refs... ;^)

[Chris M. Thomasson]

On 2/7/2021 1:57 PM, Chris M. Thomasson wrote:
> Take a look at the code here:
>
> https://pastebin.com/raw/p1E9WN5i

[...]

> Much better!
>
>
> refs + UINT_MAX + 1 should equal -refs... ;^)

Also, I need to ensure that I am using actual 32-bit types here.
unsigned int can be less than 32-bits. My Bad!! I am correcting these
things before I finish creating my "Poor Mans RCU..." example in C++17.

The examples work for me, even negating an unsigned int. However, its
not portable.

[Richard Damon]

On 2/7/21 4:57 PM, Chris M. Thomasson wrote:
>
> refs + UINT_MAX + 1 should equal -refs... ;^)

UINT_MAX+1 as a unsigned int (which it should be) will be 0, remember
unsigned math is mod *_MAX+1

thus refs + UINT_MAX + 1 will be refs.

You don't need casts to deal with -refs, as an unsigned it just has the
value of UINT_MAX + 1 - refs

You only need the cast if you want -refs to be < 0, but I don't see any
comparisons in the code that would be affected by that.

[Chris M. Thomasson]

Ahhh shit. You are right. Self slap. In this particular proxy gc
implementation of mine, only a single thread can collect and its all
unsigned. Therefore I can just use:

if (old_refs == refs)

and that's it.
______________________________

void prv_quiesce_begin()
{
// Try to begin the quiescence process.
if (! m_quiesce.exchange(true, std::memory_order_acquire))
{
// advance the current collector and grab the old one.
unsigned int old = m_current.load(std::memory_order_relaxed) &
0xFU;
old = m_current.exchange((old + 1) & 1, std::memory_order_acq_rel);
collector& c = m_collectors[old & 0xFU];

// decode reference count.
unsigned int refs = old & 0xFFFFFFF0U;

// verify reference count and previous collector index.
// RL_ASSERT(!(refs & 0x10U) && (old & 0xFU) == (&c -
m_collectors));

// increment and generate an odd reference count.

unsigned int old_refs = c.m_count.fetch_add(refs + 0x10U,
std::memory_order_release);
if (old_refs == refs)

{
// odd reference count and drop-to-zero condition detected!
prv_quiesce_complete(c);
}
}
}

______________________________


I have some other proxy collectors that allow for multiple threads to
collect, and the reference count was not unsigned and can go negative.
My bad. Now I remember porting the quiescence process from the ones that
used signed integers instead of unsigned.

Thanks for your input Richard. Also, I should be using std::uint32_t
instead of unsigned int.

Well... Now that this issue is completed, I can finish my Poor Mans RCU
impl. Should be ready sometime tonight or tomorrow.

[Chris M. Thomasson]

On 2/7/2021 3:34 PM, Chris M. Thomasson wrote:
> On 2/7/2021 2:48 PM, Richard Damon wrote:
>> On 2/7/21 4:57 PM, Chris M. Thomasson wrote:
>>>
>>> refs + UINT_MAX + 1 should equal -refs... ;^)
>>
>> UINT_MAX+1 as a unsigned int (which it should be) will be 0, remember
>> unsigned math is mod  *_MAX+1
>>
>> thus refs + UINT_MAX + 1 will be refs.
>>
>> You don't need casts to deal with -refs, as an unsigned it just has the
>> value of UINT_MAX + 1 - refs
>>
>> You only need the cast if you want -refs to be < 0, but I don't see any
>> comparisons in the code that would be affected by that.
>>
>
> Ahhh shit. You are right. Self slap. In this particular proxy gc
> implementation of mine, only a single thread can collect and its all
> unsigned. Therefore I can just use:
>
> if (old_refs == refs)

Oh well, shit. I should be really doing this:

if (old_refs == 0 - refs)

The proxy collector does work without the subtraction, but it can miss
collections, and memory can start to grow a bit, when it does not have to.

Need to add this into the next version.