3
\$\begingroup\$

So I introduced myself to templates in C++11 and I have to say it's really confusing, but also very fascinating. I just need to get my head around what happens at compile time so that I don't wind up making one line of driver code amount to a megabyte of asm...

Anyway, to teach myself I wrote a little container class. It's a container that locks and unlocks a mutex on each read/write operation on a group of data. There's still a few features I want to add to it, but that will take a lot of forced templating beyond compile-time recursion (more on this at the end).

Here is the code (updated 11/5):

#include <mutex>
#include <tuple>
#include <cstring>
#include "pack_size.hpp"
#include "pack_size_index.hpp"
#include "pod_test.hpp"

template <typename... item_t> class lockbox {
    static_assert(sizeof...(item_t) > 0, "empty lockboxes are not permitted.");
private:
    pod_test<item_t...> _test; //No data, tests to make sure item_t parameters are pod-only
    public: char _items[pack_size<item_t...>::value];
    std::mutex _mutex;

    template <size_t index, typename type_t, typename... args>
    static inline const void set_all(char* dest, const type_t& value, const args&... values) {
        type_t* align = (type_t*)&dest[pack_size_index<index, item_t...>::value];

        *align = value;

        set_all <index + 1, args...> (dest, values...);
    }

    template <size_t index, typename type_t>
    static inline const void set_all(char* dest, const type_t& value) {
        type_t* align = (type_t*)&dest[pack_size_index<index, item_t...>::value];

        *align = value;
    }

    template <size_t index, typename type_t, typename... args>
    static inline const void get_all(char* src, type_t& value, args&... values) {
        type_t* align = (type_t*)&src[pack_size_index<index, item_t...>::value];

        value = *align;

        get_all <index + 1, args...> (src, values...);
    }

    template <size_t index, typename type_t>
    static inline const void get_all(char* src, type_t& value) {
        type_t* align = (type_t*)&src[pack_size_index<index, item_t...>::value];

        value = *align;
    }

    template <size_t index, size_t... indices>
    static inline const void set_indices(char* dest,
                                         typename std::tuple_element<index, std::tuple<item_t...> >::type& value,
                                         typename std::tuple_element<indices, std::tuple<item_t...> >::type&... values) {
        typedef typename std::tuple_element<index, std::tuple<item_t...> >::type type_t;

        type_t* align = (type_t*)&dest[pack_size_index<index, item_t...>::value];

        *align = value;

        set_indices <indices...> (dest, values...);
    }

    template <size_t index>
    static inline const void set_indices(char* dest,
                                         typename std::tuple_element<index, std::tuple<item_t...> >::type& value) {
        typedef typename std::tuple_element<index, std::tuple<item_t...> >::type type_t;

        type_t* align = (type_t*)&dest[pack_size_index<index, item_t...>::value];

        *align = value;
    }

    template <size_t index, size_t... indices>
    static inline const void get_indices(char* src,
                                         typename std::tuple_element<index, std::tuple<item_t...> >::type& value,
                                         typename std::tuple_element<indices, std::tuple<item_t...> >::type&... values) {
        typedef typename std::tuple_element<index, std::tuple<item_t...> >::type type_t;

        type_t* align = (type_t*)&src[pack_size_index<index, item_t...>::value];

        value = *align;

        get_indices <indices...> (src, values...);
    }

    template <size_t index>
    static inline const void get_indices(char* src,
                                         typename std::tuple_element<index, std::tuple<item_t...> >::type& value) {
        typedef typename std::tuple_element<index, std::tuple<item_t...> >::type type_t;

        type_t* align = (type_t*)&src[pack_size_index<index, item_t...>::value];

        value = *align;
    }

public:
    lockbox(void) {
        _mutex.lock();

        memset(_items, 0, pack_size<item_t...>::value);

        _mutex.unlock();
    }

    inline lockbox(const lockbox<item_t...>& other) {
        operator=(other);
    }

    lockbox(item_t... items) {
        _mutex.lock();

        set_all <0, item_t...> (_items, items...);

        _mutex.unlock();
    }

    ~lockbox(void) {}

    lockbox<item_t...>& operator= (lockbox<item_t...>& rhs) {
        char buffer[pack_size<item_t...>::value];

        rhs._mutex.lock();

        memcpy(buffer, rhs._items, pack_size<item_t...>::value);

        rhs._mutex.unlock();

        _mutex.lock();

        memcpy(_items, buffer, pack_size<item_t...>::value);

        _mutex.unlock();

        return *this;
    }

    lockbox<item_t...>& set(item_t... items) {
        _mutex.lock();

        set_all <0, item_t...> (_items, items...);

        _mutex.unlock();

        return *this;
    }

    template <size_t... indices>
    lockbox<item_t...>& set(typename std::tuple_element<indices, std::tuple<item_t...> >::type... values) {
        _mutex.lock();

        set_indices <indices...> (_items, values...);

        _mutex.unlock();

        return *this;
    }

    inline lockbox<item_t...>& set(lockbox<item_t...>& other) {
        return operator=(other);
    }

    lockbox<item_t...>& get(item_t&... ref_items) {
        _mutex.lock();

        get_all <0, item_t...> (_items, ref_items...);

        _mutex.unlock();

        return *this;
    }

    template <size_t... indices>
    lockbox<item_t...>& get(typename std::tuple_element<indices, std::tuple<item_t...> >::type&... ref_values) {
        _mutex.lock();

        get_indices <indices...> (_items, ref_values...);

        _mutex.unlock();

        return *this;
    }

    inline lockbox<item_t...>& get(lockbox<item_t...>& other) {
        return other = *this;
    }

    static inline const size_t bytes(void) {
        return pack_size<item_t...>::value;
    }
};

pack_size:

template <typename... args> struct pack_size;

template <> struct pack_size <> {
    static const size_t value = 0;
};

template <typename type_t, typename... args> struct pack_size <type_t, args...> {
    static const size_t value = sizeof(type_t) + pack_size<args...>::value;
};

pack_size_index:

template <size_t index, typename... args> struct pack_size_index;

template <size_t index, typename type_t, typename... args> struct pack_size_index <index, type_t, args...> {
    static_assert(sizeof...(args) > 0, "index specified is out of bounds.");

    static constexpr size_t value = sizeof(type_t) + pack_size_index<index - 1, args...>::value;
};

template <typename type_t, typename... args> struct pack_size_index <0, type_t, args...> {
    static constexpr size_t value = 0;
};

pod_test:

#include <type_traits>

template <typename... args> struct pod_test;

template <typename type_t, typename... args> struct pod_test<type_t, args...> {
    static_assert(std::is_pod<type_t>::value, "parameter pack contains non-pod types.");

    static pod_test<args...> node;
};

template <typename type_t> struct pod_test<type_t> {
    static_assert(std::is_pod<type_t>::value, "parameter pack contains non-pod types.");
};

Usage:

#include "lockbox.hpp"

int main(int argc, char** argv) {
    lockbox<float, double> box(3.5f, 6.7777899);

    float a;
    double b;

    lockbox.get<0, 1>(a, b) //get the items at indices 0 and 1 and
                            //store them in the variables specified

    std::cout << a << ", " << b << std::endl; //output: 3.5, 6.7777899

    lockbox.set<1> (5.67); //set the item at index 1 to the value specified

    lockbox.get(a, b) //get all items and store them in the variables
                      //specified (works the same with set as well)

    std::cout << a << ", " << b << std::endl; //output: 3.5, 5.67

    return 0;
}

What inefficiencies are present here? I think set_all, get_all, set_indices, and get_indices might be creating an inordinate amount of functions, but that's all I can think of. Is my format readable, naming conventions and spacing considered?

\$\endgroup\$
2
\$\begingroup\$

I might be misreading things so correct me if I'm wrong but Ithink your assignment operator can deadlock. A lockbox only makes sense when accessed from multiple threads, doesn't it (otherwise what would be the point)?

  • Let's say we have two boxes box1 and box2 and two threads A and B.
  • Both threads get a reference to both boxes.
  • Each thread tries to copy the contents of one box into the other for some reason, so
    • Thread A executes: box1 = box2 in order to assign the contents of box2 to box1
    • Thread B executes: box2 = box1 in order to assign the contents of box1 to box2
  • Now if the timing is right the following could happen:
    • Thread A executes the assignment operator and locks the right hand side first so box2 is now locked.
    • Thread A gets interrupted or Thread B just manages to sneak in the next step on another CPU core
    • Thread B executes the assignment operator and locks the right hand side first so box1 is now locked.
    • Thread B tries to lock the left hand side which is box1 but that's already locked so it waits
    • Thread A picks up again and now tries to lock the left hand side which is box2 but that's locked so it waits
    • Kaputt
  • It's probably pretty rare but deadlocks often have the habit of being rare and non-determinsistic

Update: As mentioned by Loki in the comments you can use std::lock to obtain multiple locks. It's employing a deadlock avoidance algorithm (I guess effectively something like: "try to lock all objects, if one failed, unlock all obtained locks and try again until you succeed").

\$\endgroup\$
  • \$\begingroup\$ Actually you are right, I'm not sure how to efficiently avoid that though. Locking the this->_mutex and then rhs would do the same thing... I could make a copy of rhs._items in a local char array, but for large lockboxes this could be quite slow... \$\endgroup\$ – NmdMystery Nov 5 '13 at 3:11
  • \$\begingroup\$ Scratch that, that's my only choice. Code updated to reflect this change. \$\endgroup\$ – NmdMystery Nov 5 '13 at 20:09
  • \$\begingroup\$ @NmdMystery: Could you not change the code you originally posted? Otherwise the provided answers will become useless. Either include the revised code further down in your question or ask a new question with your revised code for further comments. \$\endgroup\$ – ChrisWue Nov 6 '13 at 2:13
  • 1
    \$\begingroup\$ @NmdMystery: This problem is solved by locking the resources in a specific order. If you use std::lock() and pass multiple objects it will always make sure that they are locked in a (unspecified but) specific order that avoids deadlock. \$\endgroup\$ – Martin York Nov 6 '13 at 12:47
  • \$\begingroup\$ @ChrisWue Woops, I was thinking the opposite in that the post would be too long and nobody would want to read it. The original code is lost now, though. \$\endgroup\$ – NmdMystery Nov 7 '13 at 0:44
1
\$\begingroup\$
  1. Your internal storage field char _items[pack_size<item_t...>::value]; may not be aligned properly, i.e. a double has an alignment of 8, but lockbox<double>::_items is only aligned by 4 (on 32-bit platforms).
  2. Using memset and memcpy means your class only works for POD types and has undefined behaviour for non-POD types.
  3. Since you're using C++11, why not just use std::tuple?
\$\endgroup\$
  • \$\begingroup\$ Actually I revised this to use tuple in a few places. I wasn't aware of how tuple worked, I thought it was just sort of a container but it has all these extra meta-programming features I had no idea were there. Will post an update in a moment. \$\endgroup\$ – NmdMystery Nov 5 '13 at 3:04
  • \$\begingroup\$ I decided that only pod types should be used, since by design the lockbox makes it impossible to call methods of a non-pod anyway. What should I do to fix the alignment problem, though? I only own 64-bit machines so I can't go and test this on a 32-bit. \$\endgroup\$ – NmdMystery Nov 5 '13 at 20:07
  • \$\begingroup\$ Also, testing sizeof(lockbox) gives me strange results - it seems to force an alignment of 8, is this just what sizeof does with non-pods or is this an issue I should be trying to fix? \$\endgroup\$ – NmdMystery Nov 5 '13 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.