Can you think of anything wrong with this code.

[PredicateNormative]

As a bit of background, I'll be leaving my current company soon - this is posing as a slight problem to my company because very few software engineers at my company know how to write or maintain template code - those that do are busy on other projects. Although all the code has been checked by a static analysis tool, I still feel it would be prudent to manually review my own code. So, I've been going through the templates that I have written in the following order or priority

1) The most complex and most widely used
2) The most widely used non-complex templates
3) Complex but rarely used templates (there is a good argument that I should have put these at the top of my priority list)
4) Non-complex rarely used templates.

I've been through a large number from category 1, and started looking at category 2 when I came across a piece of code that concerns me a little. I can't put my finger on why it could be a problem, but I have an uneasy feeling about it. So, I thought I'd post the code here for comment.

So, to add some context for the code that I'm about to post, the code that I am concerned about is the node class for a templated circular buffer. The idea is that the circular buffer capacity is set to the correct size and subsequent nodes are created at construction to get expensive dynamic memory allocations out of the way before the buffer is used in anger. The reason for this is that the circular buffer class is used in a real-time system where the amount of processing time is so limited on the thread supplying the data, that if there are calls to expression new in circular_buffer::push_back(), then the expression new call stalls the thread long enough that some of the data that the source thread is meant to be reading from shared memory is lost (the shared memory is written to by a hardware device).

Anyway, here is the circular_buffer class, so that you can see how the node class is used (the circular_buffer class is pasted here more here for reference than detailed reading - the important thing to review is the node class).

  template<typename T>
  class circular_buffer
  {
  public:
    typedef T value_type;
    typedef unsigned int size_type;

    typedef otl::detail::node::iterator<T> iterator;
    typedef otl::detail::node::iterator<const T> const_iterator;
    
    circular_buffer(size_type capacity)
      :size_(0)
      ,capacity_(capacity)
      ,begin_(new node_type()) //Allocate end node
      ,end_(begin_)
    {
      if(capacity == 0)
      {
        delete begin_;
        throw std::runtime_error("circular_buffer: capacity must be greater than 0");
      }

      try
      {
        allocate_and_link_nodes();
      }
      catch(...)
      {
        delete_nodes();
        throw;
      }
    }

    circular_buffer(const circular_buffer<T>& other)
      :size_(0)
      ,capacity_(other.capacity_)
      ,begin_(new node_type()) //Allocate end node
      ,end_(begin_)
    {
      try
      {
        allocate_and_link_nodes();

        const_iterator first(other.begin());
        const_iterator last(other.end());

        //Copy the data from the other buffer
        while(first != last)
        {
          push_back(*first++);
        }
      }
      catch(...)
      {
        delete_nodes();
        throw;
      }
    }

    circular_buffer& operator=(const circular_buffer<T>& rhs)
    {
      circular_buffer<T>(rhs).swap(*this);
      return *this;
    }

    void push_front(const T& value)
    {
      if(size_ == capacity_)
      {
        end_ = end_->previous();
      }
      else
      {
        ++size_;
      }
      
      begin_->previous()->value(value);
      begin_ = begin_->previous();
    }

    void push_back(const T& value)
    {
      if(size_ == capacity_)
      {
        begin_ = begin_->next();
      }
      else
      {
        ++size_;
      }
      
      end_->value(value);
      end_ = end_->next();
    }

    void pop_back()
    {
      end_ = end_->previous();
      
      if(size_ > 0)
      {
        --size_;
      }
    }

    void pop_front()
    {
      begin_ = begin_->next();
      
      if(size_ > 0) 
      {
        --size_;
      }
    }

    const T& back() const 
    {
      return end_->previous()->value();
    }

    bool empty() const
    {
      return size_ == 0;
    }

    void clear()
    {
      size_ = 0;
      end_ = begin_;
    }

    T& back()
    {
      return end_->previous()->value();
    }

    const T& front() const 
    {
      return begin_->value();
    }

    T& front()
    {
      return begin_->value();
    }

    iterator begin() { return otl::detail::node::assignable_iterator<T>(begin_); }
    iterator end()   { return otl::detail::node::assignable_iterator<T>(end_); }

    const_iterator begin() const { return otl::detail::node::assignable_iterator<const T>(begin_); }
    const_iterator end()   const { return otl::detail::node::assignable_iterator<const T>(end_); }

    size_type size()       const { return size_; }
    size_type capacity() const { return capacity_; }

    void swap(circular_buffer& other)
    {
      std::swap(size_,     other.size_);
      std::swap(capacity_, other.capacity_);
      std::swap(begin_,    other.begin_);
      std::swap(end_,      other.end_);
    }

    ~circular_buffer()
    {
      delete_nodes();
    }

  private:
    typedef otl::detail::node::node<T> node_type;
    typedef node_type* pointer;

    void allocate_and_link_nodes()
    {
      size_type nodes_remaining(capacity_);

      while(nodes_remaining > 0)
      {
        //Allocate node
        pointer new_node = new node_type();

        //Link node
        pointer last_valid = end_->previous();
        last_valid->next(new_node);
        end_->previous(new_node);

        --nodes_remaining;
      }
    }

    void delete_nodes()
    {
      while(begin_ != end_)
      {
        pointer node_to_kill = begin_;

        //get the node previous to begin
        pointer node_prior_to_begin = begin_->previous();

        //move the begin pointer on one
        begin_ = begin_->next();

        //Link the new begin position with the node prior to the previous begin position
        begin_->previous(node_prior_to_begin);

        delete node_to_kill;
      }

      //Now begin_ and end_ point to the same last remaining node
      //Delete the last remaining node
      delete begin_;
    }

    volatile size_type size_;
    size_type capacity_;
    volatile pointer begin_;
    volatile pointer end_;
  };

So, from the above code there are two things to which I'd like to draw your attention.

1) Node objects are created in the constructor - usually I would have allocated the nodes as and when they are required up to a maximum capacity, but as already explained, we can't do that for performance reasons - the nodes all need to be allocated up front.
2) There is no guarantee that T has a default constructor - therefore the node class cannot default construct a T object in its constructor.

Put those two things together, and that creates an interesting problem for the node class. The way that I have "solved" the problem is to specify a byte array of size sizeof(T)*2, and then used placement new to copy construct an object of type T at the appropriate point (assignment otherwise). The reason why I have picked sizeof(T)*2 is to take in account of potential byte alignment of the constructed T object. Anyway, here is the code for the node class.

  template <typename T>
  struct node
  {
    typedef T value_type;

    node()
      :value_(0)
      ,previous_(0)
      ,next_(0)
      ,is_valid_(false)
    {
      previous_ = this;
      next_     = this;
    }

    node(const value_type& value)
      :value_(0)
      ,previous_(0)
      ,next_(0)
      ,is_valid_(true)
    {
      previous_ = this;
      next_     = this;

      //Use placement new to construct a copy of value
      value_ = new(object_memory_) value_type(value);
    }

    template <typename U>
    node(const node<U>& other)
      :value_(other.value_)
      ,previous_(other.previous_)
      ,next_(other.next_)
      ,is_valid_(other.is_valid_)
    {
      if(is_valid_)
      {
        value_ = new(object_memory_) value_type(other.value_);
      }
    }

    ~node()
    {
      if(is_valid_)
      {
        value_->~value_type();
      }
    }

    value_type&       value()          { return *value_;   }
    const value_type& value()    const { return *value_;   }
    node*             previous() const { return previous_; }
    node*             next()     const { return next_;     }
    bool              is_valid() const { return is_valid_; }

    void value(const value_type& val) 
    {
      if(!is_valid_)
      {
        value_ = new(object_memory_) value_type(val);
        is_valid_ = true;
      }
      else
      {
        *value_ = val;
      }
    }

    void previous(node* previous_node) 
    {
      if(previous_node != 0)
      {
        previous_node->next_ = this;
        previous_ = previous_node;
      }
      else
      {
        previous_ = 0;
      }
    }

    void next(node* next_node) 
    {
      if(next_node != 0)
      {
        next_node->previous_ = this;
        next_ = next_node;
      }
      else
      {
        next_ = 0;
      }
    }

    void is_valid(bool state)
    {
      is_valid_ = state;
    }

  private:
    node(const node&);
    node operator=(const node&);

    unsigned char object_memory_[sizeof(value_type)*2]; //Allocate enough space to allow for byte alignment
    value_type* value_;
    node* previous_;
    node* next_;
    bool is_valid_;
  };

Aside from the obvious drawback of memory wastage, is there anything that you can see that is bad or even dangerous? The thing that concerns me is that I am assuming that the maximum alignment requirement is sizeof(T). Although it "works" on the various platforms on which I've tested it, I'm not comfortable with that assumption.

EDIT:
According to the 2003 C++ standard

The alignment of a complete object type is an implementation defined integer value representing a number of bytes; an object is allocated at an address that meets the alignment requirements of its object type.

I cannot find anything that states the maximum alignment requirement of type T is sizeof(T). Therefore I'm really not convinced the code is portable, although it might work ok all of the compilers and platforms on which I've tried it.

[PredicateNormative]

Just noticed, under the sizeof section, the C++ standard states:

When applied to a class, the result [of sizeof] is the number of bytes in an object of that class including any padding required for placing objects of that type in an array... When applied to an array, the result is the total number of bytes in the array. This implies that the size of an array of n elements is n times the size of an element

This in turn implies that the maximum alignment requirement of T is no greater than sizeof(T). This would make sense since if I allocate an object of type T using expression new, then the underlying call to operator new knows nothing about T, but is simply required to allocate sizeof(T) bytes to some alignment boundary. Since the only thing operator new knows about T is the number of allocation bytes required (i.e. sizeof(T)), the implication is that the maximum alignment requirement that can be applied to the allocation is sizeof(T).

However, the standard uses the word "implies" and not "means" and therefore it does not seem to absolutely guarantee that the size of an array allocation in bytes is n*sizeof(T). Therefore there does not really seem to be any guarantee that the maximum alignment requirement for T is sizeof(T).

[PredicateNormative]

Finally locked it down. Under Allocator Members, the Standard states:

pointer allocate ( size_type n , allocator <void >:: const_pointer hint =0);
3 Remarks: Uses ::operator new(std::size_t) (18.4.1).
4 Requires: hint either 0 or previously obtained from member allocate and not yet passed to member deallocate.
The value hint may be used by an implementation to help improve performance225).
5 Returns: a pointer to the initial element of an array of storage of size n * sizeof(T), aligned appropriately for
objects of type T.

The line in bold clearly prohibits additional padding between array elements (else the storage size would not be n*sizeof(T) ), therefore the only type of padding allowed is that already accounted for by sizeof(T). This therefore means that the maximum alignment requirement cannot be greater than sizeof(T) else padding would be required between array elements, breaking the n*sizeof(T) requirement of the allocator.

So, at least my node class is safe as far as byte alignment goes.

[superbonzo]

you're right about sizeof(T) being the max alignment, but, unless I'm missing something, I fail to see how object_memory_ is guaranteed to respect T's alignment ( it just implies that there is a correctly aligned address in [object_memory_,object_memory_+2*sizeof(T)] ). In order to do so, you should either use the c++11 std::aligned_storage or use a union of char[sizeof(T)] and an object with the same alignment of T ( this is how boost optional do it BTW ). Indeed, you could use boost optional directly to avoid any headache ... ( it's also due for standardization ).

[PredicateNormative]

but, unless I'm missing something, I fail to see how object_memory_ is guaranteed to respect T's alignment

You haven't missed anything, I've just been a muppet, thanks for pointing out that rather critical error.

Anyway, your comment has got me wondering why it has worked so far without any issues. I'm thinking that the reason is this... each node<T> object is dynamically allocated using expression new, which in turn calls operator new to return an allocation with correct alignment for the node<T> object. object_memory_ is the first member in the node<T> object and therefore (on every platform I've just checked it on) shares the same address as the node<T> object (not guaranteed behaviour?). Since C++ needs to deal with the case of runtime poly-morphism (where alignment of the smaller base class object address must be satisfied by the alignment of the derived class object), it makes sense that the alignment rules must in effect mean that if an allocation is made for a larger class it's alignment by implication satifies the alignment requirements of classes that are of the same or smaller size. Therefore, the fact that the node<T> alignment has been satisfied by expression new, the alignment for T must also be satisfied since they share the same address. Basically, in short, it seems that it is blind luck, since as far as I am aware, there is no guarantee that the node<T> object and its first member share the same address.

Anyway, since I'm stuck with VS2008 on my project and we are not meant to use third party libraries any more than is necessary, I think I'll use a union of char[sizeof(T)] and an object with the same alignment. I haven't checked the boost implementation but I'm guessing something like the following should work ok...

template <unsigned int Size>
class class_storage_size
{
  char data[Size];
};

template <typename T>
union aligned_storage
{
  char data[sizeof(T)];
private:
  class_storage_size<sizeof(T)> class_storage_;
};

replacing

unsigned char object_memory_[sizeof(value_type)*2];

with

aligned_storage<value_type> object_memory_;

and

value_ = new(object_memory_) value_type(val);

with

value_ = new(object_memory_.data) value_type(val);

[Codeplug]

You should read this: http://www.gotw.ca/gotw/028.htm

And what is up with those volatile qualifiers? I hope it has nothing to do with threading....

I would also recommend this to avoid dynamic memory at all - http://www.boost.org/doc/libs/1_56_0...ar_buffer.html

gg

[OReubens]

if you allocate with new. Then those objects will typically be 8byte aligned, some compilers have 16byte alignment guarantee on new.
This is essentially part of how the underlying API's work.
This happens REGARDLESS of the alignment imposed at the object level so even though your object may impose a higher alignment, it will be honored for static allocation, but won't be for dynamic allocation.

if you need a larger dynamic alignment, you'll need to take care of that yourself by overallocating and sub-aligninig yourself. (there are helper classes to achieve this).



Also, if templates is this critical for your company... your company needs to put more effort in educating their programmers to be able to write templates.

[PredicateNormative]

You should read this: http://www.gotw.ca/gotw/028.htm

Yeah, I read that before I posted my code... in fact, it was that gotw (well, technically it was Item 30 in Exceptional C++ which is pretty much identical) that prompted my post. I realised that in my particular circumstance that a lot of the gotw didn't apply, but some parts clearly did, which worried me and got me thinking about the code.

And what is up with those volatile qualifiers? I hope it has nothing to do with threading....

No, cough, cough. I know that using volatile is almost useless for multi-threaded code and does not do what most people think it does. I know that it does not guarantee an atomic read/write of the variable - I'm making use of system dependent implementation for that, which lets be honest is bad and not portable (I generally apply mutexes, but haven't in this case). The reason why the keyword is there in the circular_buffer is to take advantage of the fact that volatile prevents caching, instead forcing read/writes from/to main memory, which means (as far as I understand) that as long as the system guarantees atomic reads/writes of variables of pointer size or less, then I can guarantee that the threads will see atomic changes to the data as and when it happens. The bad part is that what I have written isn't portable and also prevents the compiler from doing its job with optimisation in that area of the code, meaning that the circular buffer will be slower, than it otherwise would be.

I must admit though, I don't know the correct way to ensure that a change to a variable in one thread is immediately visible in the other thread without using volatile... So, I'll put my learning cap on and await your response.

I would also recommend this to avoid dynamic memory at all - http://www.boost.org/doc/libs/1_56_0...ar_buffer.html
gg

I'll take a proper look at that soon. Thanks for your comments.

[PredicateNormative]

if you allocate with new. Then those objects will typically be 8byte aligned, some compilers have 16byte alignment guarantee on new.
This is essentially part of how the underlying API's work.
This happens REGARDLESS of the alignment imposed at the object level so even though your object may impose a higher alignment, it will be honored for static allocation, but won't be for dynamic allocation.

if you need a larger dynamic alignment, you'll need to take care of that yourself by overallocating and sub-aligninig yourself. (there are helper classes to achieve this).

Although I find your post helpful, please can you expand upon the part of your quote in bold? I'm not sure that I am correctly understanding what you are saying. It would seem that you are suggesting that operator new does not guarantee that the returned pointer for the requested memory (sizeof(T) ) is guaranteed to be correctly aligned for an object of type T.

However, I'm not sure if that is what you mean. If it is though, then I would point out that the C++ standard states:

A new-expression passes the amount of space requested to the allocation function as the first argument of type std::
size_t. That argument shall be no less than the size of the object being created; it may be greater than the size of the
object being created only if the object is an array. For arrays of char and unsigned char, the difference between the
result of the new-expression and the address returned by the allocation function shall be an integral multiple of the most
stringent alignment requirement (3.9) of any object type whose size is no greater than the size of the array being created.

The section in bold infers that the allocation returned by the allocator must be appropriately aligned for an object of type T since no room for extra allocation is allowed. In fact the following section of the standard would seem to support that:

3.7.3.1 Allocation functions [basic.stc.dynamic.allocation]
1 An allocation function shall be a class member function or a global function; a program is ill-formed if an allocation
function is declared in a namespace scope other than global scope or declared static in global scope. The return type shall
be void*. The first parameter shall have type std::size_t (18.1). The first parameter shall not have an associated
default argument (8.3.6). The value of the first parameter shall be interpreted as the requested size of the allocation.
An allocation function can be a function template. Such a template shall declare its return type and first parameter as
specified above (that is, template parameter types shall not be used in the return type and first parameter type). Template
allocation functions shall have two or more parameters.
2 The allocation function attempts to allocate the requested amount of storage. If it is successful, it shall return the
address of the start of a block of storage whose length in bytes shall be at least as large as the requested size. There are
no constraints on the contents of the allocated storage on return from the allocation function. The order, contiguity, and
initial value of storage allocated by successive calls to an allocation function is unspecified. The pointer returned shall
be suitably aligned so that it can be converted to a pointer of any complete object type and then used to access the object
or array in the storage allocated (until the storage is explicitly deallocated by a call to a corresponding deallocation
function). Even if the size of the space requested is zero, the request can fail. If the request succeeds, the value returned
shall be a non-null pointer value (4.10) p0 different from any previously returned value p1, unless that value p1 was
subsequently passed to an operator delete. The effect of dereferencing a pointer returned as a request for zero size
is undefined.37)
3 An allocation function that fails to allocate storage can invoke the currently installed new-handler function (18.4.2.2),
if any. [ Note: A program-supplied allocation function can obtain the address of the currently installed new_handler
using the std::set_new_handler function (18.4.2.3). —end note ] If an allocation function declared with an empty
exception-specification (15.4), throw(), fails to allocate storage, it shall return a null pointer. Any other allocation
function that fails to allocate storage shall only indicate failure by throwing an exception of class std::bad_alloc
(18.4.2.1) or a class derived from std::bad_alloc.

37) The intent is to have operator new() implementable by calling std::malloc() or std::calloc(), so the rules are substantially the same.
C++ differs from C in requiring a zero request to return a non-null pointer.

Also, if templates is this critical for your company... your company needs to put more effort in educating their programmers to be able to write templates.

Absolutely agree I think my company does now too.

[PredicateNormative]

I'm wondering if the solution to my problem is to make the following changes to my node class?

  template <typename T>
  struct node
  {
    typedef T value_type;

    node()
      :object_memory_(operator new(sizeof(T)))
      ,value_(0)
      ,previous_(0)
      ,next_(0)
      ,is_valid_(false)
    {
      previous_ = this;
      next_     = this;
    }

    node(const value_type& value)
      :object_memory_(operator new(sizeof(T)))
      ,value_(0)
      ,previous_(0)
      ,next_(0)
      ,is_valid_(true)
    {
      previous_ = this;
      next_     = this;

      //Use placement new to construct a copy of value
      value_ = new(object_memory_) value_type(value);
    }

    template <typename U>
    node(const node<U>& other)
      :object_memory_(operator new(sizeof(T)))
      ,value_(other.value_)
      ,previous_(other.previous_)
      ,next_(other.next_)
      ,is_valid_(other.is_valid_)
    {
      if(is_valid_)
      {
        value_ = new(object_memory_) value_type(other.value_);
      }
    }

    ~node()
    {
      if(is_valid_)
      {
        value_->~value_type();
      }

      operator delete(object_memory_);
    }

    value_type&       value()          { return *value_;   }
    const value_type& value()    const { return *value_;   }
    node*             previous() const { return previous_; }
    node*             next()     const { return next_;     }
    bool              is_valid() const { return is_valid_; }

    void value(const value_type& val) 
    {
      if(!is_valid_)
      {
        value_ = new(object_memory_) value_type(val);
        is_valid_ = true;
      }
      else
      {
        *value_ = val;
      }
    }

    void previous(node* previous_node) 
    {
      if(previous_node != 0)
      {
        previous_node->next_ = this;
        previous_ = previous_node;
      }
      else
      {
        previous_ = 0;
      }
    }

    void next(node* next_node) 
    {
      if(next_node != 0)
      {
        next_node->previous_ = this;
        next_ = next_node;
      }
      else
      {
        next_ = 0;
      }
    }

    void is_valid(bool state)
    {
      is_valid_ = state;
    }

  private:
    node(const node&);
    node operator=(const node&);

    void* object_memory_;
    value_type* value_;
    node* previous_;
    node* next_;
    bool is_valid_;
  };

[Codeplug]

Even though you are using the MS implementation of volatile, there are still plenty of data races that may be present depending your you how your threads access the object.

The conclusion that I take away from gotw #28 is that if you need fast dynamic allocation, then it is better to implement a memory pool instead of doing the union trick to ensure proper alignment.

Whether you use pre-allocated dynamic memory or static memory, you still need to know the maximum size you'll need to prevent further allocations. That being the case, I would just use a boost::circular_buffer<> of that size. (And the contiguous memory may give you favorable cache-locality performance.) I demonstrate an inter-thread usage of boost::circular_buffer<> in this post: http://forums.codeguru.com/showthrea...81#post2057581

>> There is no guarantee that T has a default constructor ...
Then you may have no choice but to use a memory pool. You could still use a boost::circular_buffer<>, but of pointers instead of objects.

gg

[superbonzo]

I'm wondering if the solution to my problem is to make the following changes to my node class?

yes, it is, as long as T is not overaligned ( ie, it has stricter alignment than the strictest scalar type ). Note that even in c++11 allocation functions are not required to support overaligned types, so it's safe to ignore them ( in the sense that it's safe to assume that users of your class cannot give such a support for granted ).

[Codeplug]

>> template <typename U>
>> node(const node<U>& other)
>> :object_memory_(operator new(sizeof(T)))
Should that be sizeof(U)?

gg

[PredicateNormative]

Even though you are using the MS implementation of volatile, there are still plenty of data races that may be present depending your you how your threads access the object.

Yeah, this is bad, but I believe that both Windows and Linux have atomic read/writes for objects that are of the same size or smaller than a pointer. I really should just mutex protect the variables.

The conclusion that I take away from gotw #28 is that if you need fast dynamic allocation, then it is better to implement a memory pool instead of doing the union trick to ensure proper alignment.

Agreed, but in my case, it doesn't matter if the circular_buffer doesn't construct that fast (the place where all of the nodes are allocated), because the data feed hasn't started at that point. What matters is that there is not a dynamic allocation in the push_back or push_front calls, because the dynamic memory requests take too long.

Whether you use pre-allocated dynamic memory or static memory, you still need to know the maximum size you'll need to prevent further allocations.

That is the non-modifiable capacity parameter on the circular_buffers constructor.

That being the case, I would just use a boost::circular_buffer<> of that size. (And the contiguous memory may give you favorable cache-locality performance.) I demonstrate an inter-thread usage of boost::circular_buffer<> in this post: http://forums.codeguru.com/showthrea...81#post2057581

Thanks for this, it looks very similar to the way I usually code threads, but I have found that I still need to use the volatile keyword at times, since otherwise it seems that certain values get cached (e.g. the is_ready flag) for each thread and therefore the changes made by one thread are not seen by the other fast enough - perhaps it's an error in how I have coded a class in the past.

>> There is no guarantee that T has a default constructor ...
Then you may have no choice but to use a memory pool. You could still use a boost::circular_buffer<>, but of pointers instead of objects.
gg

Yes, but in this case the object memory can be allocated using operator new in the Node constructor, and then the T object construction can be delayed until the push_back/push_front using operator new when required. So, it probably works out OK.

[PredicateNormative]

yes, it is, as long as T is not overaligned ( ie, it has stricter alignment than the strictest scalar type ). Note that even in c++11 allocation functions are not required to support overaligned types, so it's safe to ignore them ( in the sense that it's safe to assume that users of your class cannot give such a support for granted ).

I'd never heard of an over-aligned data until today... looks like I haven't read enough of the C++11 Standard!

That's interesting... so if the C++11 allocation functions are not required to support over-aligned types, then what does that mean with respect to types that require over-alignment? I guess extra user code that makes use of provided helper types?

I must admit, I've kind of put off learning all of the language extensions in C++11 due to lack of compiler compliance with the C++11 Standard meaning that certain features are not currently portable... it looks like GCC is pretty close though. Come on Microsoft!