Freelists

[Brian Geffon <br...@apache.org>]

Hi,
I was curious if anyone could shed some light on the following
question I've had. So if I understand this correctly the freelists use
the upper 16bits of the data ptr to be a "version," where this version
tries to solve several problems related to lockfree data structures
including the ABA problem and the delete after remove problem. So in
my quest to understand these more, I'm trying to figure why the macros
are so complex, for example:

#define FREELIST_POINTER(_x) ((void*)(((((intptr_t)(_x).data)<<16)>>16) | \
 (((~((((intptr_t)(_x).data)<<16>>63)-1))>>48)<<48)))

Since the pointer is just the lower 48 bits, isn't it enough to just
do something like:

(void*)(((intptr_t)(_x).data) & (intptr_t)(0x0000FFFFFFFFFFFFULL)))

It would seem like we should be able to pull this off with only a
single machine instruction? Which is surprising that we dont when the
freelist version macro is much simpler:

#define FREELIST_VERSION(_x) (((intptr_t)(_x).data)>>48)

I know some pretty smart people worked on this stuff so I'm sure there
is a very good reason for the complexity, but I just cant figure it
out. Anyone?

Brian

Re: Freelists

[Brian Geffon <br...@apache.org>]

Actually, please do not disregard this question, it appears James and
I cannot correctly do bitwise arithmetic :)

Brian

On Wed, Sep 5, 2012 at 9:34 PM, Brian Geffon <br...@apache.org> wrote:
> Disregard this question, it's not doing what I originally expected it
> was doing based on the name.
>
> Brian
>
> On Wed, Sep 5, 2012 at 8:45 PM, Brian Geffon <br...@apache.org> wrote:
>> Hi,
>> I was curious if anyone could shed some light on the following
>> question I've had. So if I understand this correctly the freelists use
>> the upper 16bits of the data ptr to be a "version," where this version
>> tries to solve several problems related to lockfree data structures
>> including the ABA problem and the delete after remove problem. So in
>> my quest to understand these more, I'm trying to figure why the macros
>> are so complex, for example:
>>
>> #define FREELIST_POINTER(_x) ((void*)(((((intptr_t)(_x).data)<<16)>>16) | \
>>  (((~((((intptr_t)(_x).data)<<16>>63)-1))>>48)<<48)))
>>
>> Since the pointer is just the lower 48 bits, isn't it enough to just
>> do something like:
>>
>> (void*)(((intptr_t)(_x).data) & (intptr_t)(0x0000FFFFFFFFFFFFULL)))
>>
>> It would seem like we should be able to pull this off with only a
>> single machine instruction? Which is surprising that we dont when the
>> freelist version macro is much simpler:
>>
>> #define FREELIST_VERSION(_x) (((intptr_t)(_x).data)>>48)
>>
>> I know some pretty smart people worked on this stuff so I'm sure there
>> is a very good reason for the complexity, but I just cant figure it
>> out. Anyone?
>>
>> Brian

Re: Freelists

[Brian Geffon <br...@apache.org>]

Disregard this question, it's not doing what I originally expected it
was doing based on the name.

Brian

On Wed, Sep 5, 2012 at 8:45 PM, Brian Geffon <br...@apache.org> wrote:
> Hi,
> I was curious if anyone could shed some light on the following
> question I've had. So if I understand this correctly the freelists use
> the upper 16bits of the data ptr to be a "version," where this version
> tries to solve several problems related to lockfree data structures
> including the ABA problem and the delete after remove problem. So in
> my quest to understand these more, I'm trying to figure why the macros
> are so complex, for example:
>
> #define FREELIST_POINTER(_x) ((void*)(((((intptr_t)(_x).data)<<16)>>16) | \
>  (((~((((intptr_t)(_x).data)<<16>>63)-1))>>48)<<48)))
>
> Since the pointer is just the lower 48 bits, isn't it enough to just
> do something like:
>
> (void*)(((intptr_t)(_x).data) & (intptr_t)(0x0000FFFFFFFFFFFFULL)))
>
> It would seem like we should be able to pull this off with only a
> single machine instruction? Which is surprising that we dont when the
> freelist version macro is much simpler:
>
> #define FREELIST_VERSION(_x) (((intptr_t)(_x).data)>>48)
>
> I know some pretty smart people worked on this stuff so I'm sure there
> is a very good reason for the complexity, but I just cant figure it
> out. Anyone?
>
> Brian