CAS is broken

[Tomash Brechko]

Hi there,

>From the description of the protocol:

  - <cas unique> is a unique 64-bit value of an existing entry.
    Clients should use the value returned from the "gets" command
    when issuing "cas" updates.

If I understood the corresponding thread right, the idea is to provide
some sort of atomicity: if multiple clients 'gets' CAS value, only one
would be able to update the entry with 'cas', and everyone else will
get EXISTS.

However internally (and this was mentioned in the thread) CAS value is
actually a pointer (cast to uint32_t for some reason).  So I thought,
how we know the pointer won't be reused?

I spend some time trying to compose the test case, but indeed, no CAS
value for which you did 'gets' was ever reused.  This made me to
conclude that gets simply leaks some data (what's called item
internally).

Next two patches show that CAS is broken: first is a test case that
runs indefinite loop and does 'set', 'gets'.  See how memory usage
grows.

Second patch fixes the leak, and adds a test that shows that without
this leak item addresses are really reused, and so can't be used for
CAS.

I think this might be fixed with proper generation counters wide
enough to never wraparound (64-bit).  Besides, such generation
counters will enable a fast path in the client:

  # set the value
  set ...

  # get CAS
  CAS = gets ...

  # update the value
  cas ... CAS

  # update the value.  If we are lucky, no need to call gets again.
  cas ... CAS+1


What do you think?


-- 
   Tomash Brechko