Uploaded image for project: 'Traffic Server'
  1. Traffic Server
  2. TS-1742

Freelists to use 64bit version w/ Double Word Compare and Swap



    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 3.3.2
    • None
    • None


      So to those of you familiar with the freelists you know that it works this way the head pointer uses the upper 16 bits for a version to prevent the ABA problem. The big drawback to this is that it requires the following macros to get at the pointer or the version:

      #define FREELIST_POINTER(_x) ((void*)(((((intptr_t)(_x).data)<<16)>>16) | \
       (((~((((intptr_t)(_x).data)<<16>>63)-1))>>48)<<48)))  // sign extend
      #define FREELIST_VERSION(_x) (((intptr_t)(_x).data)>>48)
      #define SET_FREELIST_POINTER_VERSION(_x,_p,_v) \
        (_x).data = ((((intptr_t)(_p))&0x0000FFFFFFFFFFFFULL) | (((_v)&0xFFFFULL) << 48))

      Additionally, since this only leaves 16 bits it limits the number of versions you can have, well more and more x86_64 processors support DCAS (double word compare and swap / 128bit CAS). This means that we can use 64bits for a version which basically makes the versions unlimited but more importantly it takes those macros above and simplifies them to:

      #define FREELIST_POINTER(_x) (_x).s.pointer
      #define FREELIST_VERSION(_x) (_x).s.version
      #define SET_FREELIST_POINTER_VERSION(_x,_p,_v) \
      (_x).s.pointer = _p; (_x).s.version = _v

      As you can imagine this will have a performance improvement, in my simple tests I measured a performance improvement of around 6%. Unfortunately, I'm not an expert with this stuff and I would really appreciate more community feedback before I commit this patch.

      Note: this only applies if you're not using a reclaimable freelist.


        1. 128bit_cas.patch
          12 kB
          Brian Geffon
        2. 128bit_cas.patch.2
          11 kB
          Brian Geffon

        Issue Links



              briang Brian Geffon
              briang Brian Geffon
              0 Vote for this issue
              5 Start watching this issue