Re: Overloaded function lookup with const/volatile

Joshua Maurice wrote:


Well, any real existing compiler will have some points where it is
non-standard. Sometime these are called bugs, sometimes features. :-)

It is IBM Visual Age C++ (icc). A quite old one. It does not support all
of the new features, but I found only few bugs so far. Guess I found one
now.

It turned out that gcc compiles the code as expected. And furthermore
gcc also compiles it when I remove the methods that take non-const
references. Now I am really surprised. Obviously gcc prefers the
conversion to const X& over const volatile X& for some reason.


Yes you are right. The default constructor was missing.

Unfortunately the whole code is a bit large and non-portable because of
the threading stuff. There is no need to be portable in my case.
However, I added the code used for testing on x86 below. The interlocked
functions should be hopefully the same as with MSVC.


Hmm, same with gcc.


The volatile keyword is not used for anything special in my code. In
fact only a few atomic operations are applied to the pointers to
volatile storage so the compiler will most probably ignore it. The
thread safety of the code is not directly related to the volatile
keyword at all.


Volatile is used to mark shared pointer instances that may change
asynchronously. All access to these instances has to be done logically
atomic. The latter is achieved by invoking different functions for
volatile objects.

The alternative to using volatile here has significant drawbacks too. In
fact I would need a different type for shared pointer instances. No
problem so far, but think about structures of smart pointers:
   struct S
   { int_ptr<my_type> P1;
     int_ptr<my_type> P2;
     // ...
   };
Now you need a different type for shared instances of S too. And the
conversion between them is plenty much of work.

I have many of such structures to hold properties of objects. If I want
to display them e.g. in a GUI I either have to lock each object while I
access the properties - with all further drawbacks like priority
inversion, slow access and so on - or I read them atomically. Of course
I prefer the latter. And for this purpose the objects provide a public
method that returns a const volatile references to the structure S. Once
the object is locked, read access to S has no longer to be atomic. So
another method returns a const reference to S and checks whether the
corresponding mutex is hold by the current thread (assertion).

Marcel

------------
#define INCL_DOS
#include <os2.h>

#include <process.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <time.h>
#include <malloc.h>

#define Sleep DosSleep

//#define DEBUGLOG(x)
#define DEBUGLOG(x) debuglog x

#define WORD_WIDTH 32
#define INT_PTR_STOLEN_BITS 2U
#define INT_PTR_ALIGNMENT (1U << INT_PTR_STOLEN_BITS)
#define INT_PTR_POINTER_MASK (~INT_PTR_ALIGNMENT+1U)
#define INT_PTR_COUNTER_MASK (INT_PTR_ALIGNMENT-1U)
#define CLIB_ALIGNMENT 4U // Intrinsic alignment of C runtime

// get thread id
static long get_tid()
{ PTIB ptib;
   DosGetInfoBlocks( &ptib, NULL );
   return ptib->tib_ptib2->tib2_ultid;
}

// log to stderr
static void debuglog( const char* fmt, ... )
{ va_list va;
   char buffer[1024];
   ULONG dummy;

   va_start(va, fmt);
   // 8+ 1+4+ 1 = 14
   sprintf(buffer, "%08ld %04ld ", clock(), get_tid());
   vsprintf(buffer+14, fmt, va);
   va_end(va);
   //fputs( buffer, stderr );
   DosWrite(2, buffer, 14 + strlen(buffer+14), &dummy); // much faster

   //Sleep(0);
}

static void do_assert(const char* msg, const char* file, int line)
{ DosResetBuffer(2); // Flush stderr before we die.
   fprintf(stderr, "Assertion failed in thread %ld at %s line %i: %s\n",
get_tid(), file, line, msg);
   abort();
}

#define ASSERT(cond) \
   if (!(cond)) \
     do_assert(#cond, __FILE__, __LINE__);

#if defined(__GNUC__)
   // Intrinsics for gcc/x86
   static __inline__ void _InterlockedIncrement(__volatile__ long *pu)
   { __asm__ __volatile__("lock; incl %0"
                          : "+m" (*pu)
                          :
                          : "cc");
   }
   static __inline__ void _InterlockedDecrement(__volatile__ long *pu)
   { __asm__ __volatile__("lock; decl %0"
                          : "+m" (*pu)
                          :
                          : "cc");
   }
   static __inline__ long _InterlockedExchange(__volatile__ long *pu,
long u)
   { __asm__ __volatile__("xchgl %1, %0"
                          : "+m" (*pu)
                          , "+r" (u));
     return u;
   }
   static __inline__ void _InterlockedAdd(__volatile__ long *pu, const
long uAdd)
   { __asm__ __volatile__("lock; addl %1, %0"
                          : "+m" (*pu)
                          : "nr" (uAdd)
                          : "cc");
   }
   static __inline__ void _InterlockedSubtract(__volatile__ long *pu,
const long uSub)
   { __asm__ __volatile__("lock; subl %1, %0"
                          : "+m" (*pu)
                          : "nr" (uSub)
                          : "cc");
   }
   static __inline__ long _InterlockedExchangeAdd(__volatile__ long *pu,
long uAdd)
   { __asm__ __volatile__("lock; xaddl %1, %0"
                          : "+m" (*pu)
                          , "+r" (uAdd)
                          :
                          : "cc");
     return uAdd;
   }
   static __inline__ long _InterlockedCompareExchange(__volatile__ long
*pu, const long uNew, long uOld)
   { __asm__ __volatile__("lock; cmpxchgl %2, %0"
                          : "+m" (*pu)
                          , "+a" (uOld)
                          : "r" (uNew)
                          : "cc");
     return uOld;
   }
   #define THREAD_FUNC
#elif defined(__IBMC__) || defined(__IBMCPP__)
   // ICC does not support inline assembler.
   const unsigned char InterlockedXchCode[] =
   { 0x87, 0x10 // xchg [eax], edx
   , 0x89, 0xd0 // mov eax, edx
   , 0xC3 // ret
   };
   const unsigned char InterlockedCxcCode[] =
   { 0x91 // xchg eax, ecx
   , 0xF0, 0x0F, 0xB1, 0x11 // lock cmpxchg [ecx], edx
   , 0xC3 // ret
   };
   const unsigned char InterlockedIncCode[] =
   { 0xF0, 0xFF, 0x00 // lock inc dword [eax]
   , 0xC3 // ret
   };
   const unsigned char InterlockedDecCode[] =
   { 0xF0, 0xFF, 0x08 // lock dec dword [eax]
   , 0x0F, 0x95, 0xC0 // setnz al
   , 0xC3 // ret
   };
   const unsigned char InterlockedAddCode[] =
   { 0xF0, 0x01, 0x10 // lock add [eax], edx
   , 0xC3 // ret
   };
   const unsigned char InterlockedSubCode[] =
   { 0xF0, 0x29, 0x10 // lock sub [eax], edx
   , 0x0F, 0x95, 0xC0 // setnz al
   , 0xC3 // ret
   };
   const unsigned char InterlockedXadCode[] =
   { 0xF0, 0x0F, 0xC1, 0x10 // lock xadd [eax], edx
   , 0x89, 0xD0 // mov eax, edx
   , 0xC3 // ret
   };
   #define _InterlockedExchange(x,n) (*(long(_Optlink*)(volatile
long*,long))InterlockedXchCode)((x),(n))
   #define _InterlockedCompareExchange(x,n,c)(*(long(_Optlink*)(volatile
long*,long,long))InterlockedCxcCode)((x),(n),(c))
   #define _InterlockedIncrement(x) (*(void(_Optlink*)(volatile
long*))InterlockedIncCode)((x))
   #define _InterlockedDecrement(x) (*(char(_Optlink*)(volatile
long*))InterlockedDecCode)((x))
   #define _InterlockedAdd(x,n) (*(void(_Optlink*)(volatile
long*,long))InterlockedAddCode)((x),(n))
   #define _InterlockedSubtract(x,n) (*(char(_Optlink*)(volatile
long*,long))InterlockedSubCode)((x),(n))
   #define _InterlockedExchangeAdd(x,n) (*(long(_Optlink*)(volatile
long*,long))InterlockedXadCode)((x),(n))
   // Well, icc
   #define bool unsigned char
   #define explicit
   #define THREAD_FUNC _Optlink
#else
   #error Unsupported compiler. Interlocked functions need to be ported.
#endif

template <class T> class int_ptr;
/* Base class to make a class reference countable. */
class Iref_count
{ template <class T> friend class int_ptr;
  private:
   volatile long Count;
   // This function is the interface to int_ptr<T>
   volatile long& access_counter()
   { return Count; }
  private: // non-copyable
   Iref_count(const Iref_count&);
   void operator=(const Iref_count&);
  protected:
   Iref_count() : Count(0) {}
   ~Iref_count() {} // You must not call the non-virtual destructor
directly.
  public:
   // Checks whether the object is currently unique.
   // Only the return value true is reliable.
   bool RefCountIsUnique() const
   { return (Count & ~INT_PTR_ALIGNMENT) == 0; }
   // Checks whether the object is not under control of a int_ptr.
   // This is the case when the object is just constructed and not yet
   // assigned to an int_ptr instance or if the method is called from the
   // destructor. Only the return value true is reliable.
   bool RefCountIsUnmanaged() const
   { return Count == 0; }

#if INT_PTR_ALIGNMENT > CLIB_ALIGNMENT
  private:
   typedef unsigned char offset; // must be able to hold ALIGNMENT
  public:
   // alignment
   void* operator new( unsigned int len )
   { char* p = (char*)::operator new(len + sizeof(offset) +
INT_PTR_ALIGNMENT - CLIB_ALIGNMENT);
     offset off = ((-(int)p-sizeof(offset)) & INT_PTR_COUNTER_MASK) +
sizeof(offset);
     p += off;
     ((offset*)p)[-1] = off;
     return p;
   }
   void operator delete( void* ptr )
   { char* p = (char*)ptr;
     offset off = ((offset*)p)[-1];
     ::operator delete(p - off);
   }
#endif
};

/* This is a simple and highly efficient reference counted smart pointer
  * implementation for objects of type T. The class is similar to
  * boost::intrusive_ptr but works on old C++ compilers too.
  * Furthermore the implementation is strongly thread-safe on volatile
  * instances and wait-free.
  * All objects of type T must implement a function called
  * acess_counter() that provides access to the reference counter.
  * The easiest way to do so is to derive from Iref_count.
  * Note that all objects of type T MUST be aligned to INT_PTR_ALIGNMENT
  * in memory! Iref_count ensures this.
  */
template <class T>
class int_ptr
{private:
   long Data;
  private:
   // Strongly thread safe read
   long acquire() volatile const;
   // Destructor core
   static void release(long data);
   // Transfer hold count to the main counter and return data pointer.
   static long transfer(long data);

   // Raw initialization
   explicit int_ptr(long data)
   : Data(data) {}
  public:
   // Initialize a NULL pointer.
               int_ptr() : Data(0) {}
   // Store a new object under reference count control.
               int_ptr(T* ptr);
   // Copy constructor
               int_ptr(const int_ptr<T>& r);
   // Copy constructor, strongly thread-safe.
               int_ptr(volatile const int_ptr<T>& r);
   // Destructor, frees the stored object if this is the last reference.
               ~int_ptr();
   // swap instances (not thread safe)
   void swap(int_ptr<T>& r);
   // Strongly thread safe swap
   void swap(volatile int_ptr<T>& r);
   // Strongly thread safe swap
   void swap(int_ptr<T>& r) volatile;
   // reset the current instance to NULL
   void reset();
   void reset() volatile;
   // Basic operators
   T* get() const { return (T*)Data; }
               operator T*() const { return (T*)Data; }
   T& operator*() const { ASSERT(Data); return *(T*)Data; }
   T* operator->() const { ASSERT(Data); return (T*)Data; }
   // assignment
   int_ptr<T>& operator=(T* ptr);
   int_ptr<T>& operator=(const int_ptr<T>& r);
   int_ptr<T>& operator=(volatile const int_ptr<T>& r);
   void operator=(T* ptr) volatile;
   void operator=(const int_ptr<T>& r) volatile;
   void operator=(volatile const int_ptr<T>& r) volatile;
};

// diagnostic value
volatile long max_outer_count = 0;

template <class T>
long int_ptr<T>::acquire() volatile const
{ if (!Data)
     return 0; // fast path
   const long old_outer = _InterlockedExchangeAdd(&(long&)Data, 1) + 1;
   const long outer_count = old_outer & INT_PTR_COUNTER_MASK;
   ASSERT(outer_count != 0); // overflow condition
   const long new_outer = old_outer & INT_PTR_POINTER_MASK;
   if (new_outer)
     // Transfer counter to obj->count.
     _InterlockedAdd(&((T*)new_outer)->access_counter(),
INT_PTR_ALIGNMENT - outer_count + 1);
   // And reset it in *this.
   const long old_2 = _InterlockedCompareExchange(&(long&)Data,
new_outer, old_outer);
   if (old_2 != old_outer && new_outer)
     // Someone else does the job already => undo.
     _InterlockedAdd(&((T*)new_outer)->access_counter(), outer_count);
     // The global count cannot return to zero here,
     // because we have an active reference.
   // Diagnostics
   long max_outer = max_outer_count;
   while (max_outer < outer_count)
     max_outer = _InterlockedCompareExchange(&max_outer_count,
outer_count, max_outer);
   return new_outer;
}

template <class T>
void int_ptr<T>::release(long data)
{ T* obj = (T*)(data & INT_PTR_POINTER_MASK);
   if (obj)
   { long adjust = -((data & INT_PTR_COUNTER_MASK) + INT_PTR_ALIGNMENT);
     adjust += _InterlockedExchangeAdd(&obj->access_counter(), adjust);
     if (adjust == 0)
       delete obj;
   }
}

template <class T>
long int_ptr<T>::transfer(long data)
{ const long outer = data & INT_PTR_COUNTER_MASK;
   if (outer)
   { data &= INT_PTR_POINTER_MASK;
     if (data)
       _InterlockedSubtract(&((T*)data)->access_counter(), outer);
   }
   return data;
}

template <class T>
inline int_ptr<T>::int_ptr(T* ptr)
: Data((long)ptr)
{ if (Data)
     _InterlockedAdd(&((T*)Data)->access_counter(), INT_PTR_ALIGNMENT);
}
template <class T>
inline int_ptr<T>::int_ptr(const int_ptr<T>& r)
: Data(r.Data)
{ if (Data)
     _InterlockedAdd(&((T*)Data)->access_counter(), INT_PTR_ALIGNMENT);
}
template <class T>
inline int_ptr<T>::int_ptr(volatile const int_ptr<T>& r)
: Data(r.acquire())
{}

template <class T>
inline int_ptr<T>::~int_ptr()
{ release(Data);
}

template <class T>
void int_ptr<T>::swap(int_ptr<T>& r)
{ const long temp = r.Data;
   r.Data = Data;
   Data = temp;
}
template <class T>
inline void int_ptr<T>::swap(volatile int_ptr<T>& r)
{ Data = transfer(_InterlockedExchange(&r.Data, Data));
}
template <class T>
inline void int_ptr<T>::swap(int_ptr<T>& r) volatile
{ r.swap(*this);
}

template <class T>
inline void int_ptr<T>::reset()
{ release(Data);
   Data = 0;
}
template <class T>
inline void int_ptr<T>::reset() volatile
{ release(_InterlockedExchange(&Data, 0));
}

template <class T>
inline int_ptr<T>& int_ptr<T>::operator=(T* ptr)
{ int_ptr<T>(ptr).swap(*this);
   return *this;
}
template <class T>
inline int_ptr<T>& int_ptr<T>::operator=(const int_ptr<T>& r)
{ int_ptr<T>(r).swap(*this);
   return *this;
}
template <class T>
inline int_ptr<T>& int_ptr<T>::operator=(volatile const int_ptr<T>& r)
{ int_ptr<T>(r).swap(*this);
   return *this;
}
template <class T>
inline void int_ptr<T>::operator=(T* ptr) volatile
{ int_ptr<T>(ptr).swap(*this);
}
template <class T>
inline void int_ptr<T>::operator=(const int_ptr<T>& r) volatile
{ int_ptr<T>(r).swap(*this);
}
template <class T>
inline void int_ptr<T>::operator=(volatile const int_ptr<T>& r) volatile
{ int_ptr<T>(r).swap(*this);
}

// test tracer - used as user data
long inst_counter = 0;
long id_counter = 0;

struct my_data : public Iref_count
{
   const int i;
   const int j;

   my_data(int i) : i(i), j(_InterlockedExchangeAdd(&id_counter, 1))
   { _InterlockedIncrement(&inst_counter);
     DEBUGLOG(("ctor %p %d %d %d\r\n", this, i, j, inst_counter));
   }

   ~my_data()
   { DEBUGLOG(("dtor %p %d %d %d\r\n", this, i, j, inst_counter));
     _InterlockedDecrement(&inst_counter);
   }

};

// And here is the test:

long thread_counter = 0;

static void THREAD_FUNC reader_thread(void* p)
{ volatile int_ptr<my_data>& s = *(volatile int_ptr<my_data>*)p;
   for (int i = 0; i <= 100000; ++i)
   { // here is our object
     int_ptr<my_data> h(s);
     // work with it
     if (h)
     { DEBUGLOG(("read %p %d %d\r\n", h.get(), h->i, h->j));
     } else
     { DEBUGLOG(("read NULL\r\n"));
     }
     //Sleep(0);
     // get one more ref but now with normal thread safety
     int_ptr<my_data> h2(h);
     // ...
   }
   _InterlockedDecrement(&thread_counter);
}

static void THREAD_FUNC writer_thread(void* p)
{ volatile int_ptr<my_data>& s = *(volatile int_ptr<my_data>*)p;
   const long tid = get_tid() + 10;
   for (int i = 1; i <= 100000; ++i)
   { if (i % tid)
     { my_data* data = i % tid ? new my_data(i) : NULL;
       DEBUGLOG(("repl %p %d %d\r\n", data, i, data->j));
       s = data;
     } else
     { DEBUGLOG(("repl NULL\r\n"));
       s.reset();
     }
     //Sleep(0);
   }
   _InterlockedDecrement(&thread_counter);
}

static void starter(void (THREAD_FUNC *fn)(void*), volatile void* p)
{ _InterlockedIncrement(&thread_counter);
   int tid = _beginthread(fn, NULL, 65536, (void*)p);
   ASSERT(tid != -1);
}

int_ptr<my_data> foo(my_data* ptr)
{ return ptr;
}

int main()
{ // syntax checks
   { int_ptr<my_data> a;
     int_ptr<my_data> b(new my_data(1));
     int_ptr<my_data> c(b);
     int_ptr<my_data> d(foo(c));
     volatile int_ptr<my_data> A(a);
     volatile int_ptr<my_data> B(c);
     a = b;
     A = b;
     a = B;
     A = B;
   }

   // race condition checks
   { volatile int_ptr<my_data> s(new my_data(0));

     starter(&reader_thread, &s);
     starter(&writer_thread, &s);
     starter(&reader_thread, &s);
     starter(&writer_thread, &s);
     starter(&reader_thread, &s);
     starter(&reader_thread, &s);
     starter(&writer_thread, &s);
     starter(&reader_thread, &s);
     starter(&reader_thread, &s);
     starter(&reader_thread, &s);
     starter(&writer_thread, &s);
     starter(&reader_thread, &s);
     starter(&reader_thread, &s);
     starter(&reader_thread, &s);
     // join threads
     do {Sleep(100);} while (thread_counter != 0);
   }

   debuglog("done - %li instances, max outer count = %li\r\n",
inst_counter, max_outer_count);
   ASSERT(inst_counter == 0);
   putchar('\7');
}