3
\$\begingroup\$

I have written a typetoken library in C++11 and I want to know if it is indeed typesafe, threadsafe and complete.

The purpose of this library is to give an unique ID to every requested typename during runtime.

The code I used is the following:

/*
 * typetoken.hpp
 *  Created on: 27.11.2014
 *      Author: WorldSEnder
 */

#pragma once
#ifndef TYPETOKEN_HPP_
#define TYPETOKEN_HPP_

#include <atomic>

namespace typetoken
{

using token_t = std::size_t;
template<typename T> token_t getToken(void);

class tokenbase {
private:
    tokenbase(void) = delete;
    static volatile std::atomic<token_t> counter;

    template<typename Q>
    friend token_t getToken(void);
};

template<typename T>
struct typetoken : tokenbase {
private:
    typetoken(void) = delete;
    static token_t ID;

    template<typename Q>
    friend token_t getToken(void);
};

template<typename T>
token_t typetoken<T>::ID = 0;

template<typename T>
token_t getToken(void) {
    typedef typetoken<T> token;
    if(!token::ID) {
        token::ID = ++token::counter;
    }
    return token::ID;
}
} // namespace typetoken

#endif /* TYPETOKEN_HPP_ */

/*
 * typetoken.cpp
 *  Created on: 27.11.2014
 *      Author: WorldSEnder
 */
#include "typetoken.hpp"

namespace typetoken
{

volatile std::atomic<token_t> tokenbase::counter = ATOMIC_VAR_INIT(1);
volatile std::atomic<impl_token_t> impltokenbase::counter = ATOMIC_VAR_INIT(1);

}

You can use this to map a typename to any other object during runtime, for example:

#include <map>
#include <iostream>
#include "typetoken.hpp"

class Mapper {
    std::map<typetoken::token_t, float> mapObj;
public:
    template<typename T>
    void setFor(float object) {
        mapObj.insert(std::make_pair(typetoken::getToken<T>(), object));
    }
    template<typename T>
    float getFor(void) {
        return (*mapObj.find(typetoken::getToken<T>())).second;
    }
};

int main(void) {
    Mapper map;
    map.setFor<int>(2.5f);
    map.setFor<char>(3.5f);
    std::cout << map.getFor<char>() << std::endl;
    std::cout << map.getFor<int>() << std::endl;
}
// Outputs: "3.5\n2.5"

I have the following doubts about this implementation:

  • When two threads create a token for the same type at the same time, it could be set simultaneously to two different values, can't it?
  • Is it possible that the same ID is given to two different types?
  • Can I code this better in general, reducing overhead, runtime and such?
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview! It looks like your question is appropriate for this forum, but it might help reviewers if you edit the post to describe the purpose and show example use of your code. \$\endgroup\$ – Edward Nov 28 '14 at 15:33
  • \$\begingroup\$ Looks like you never define typetoken::tokenbase::counter. \$\endgroup\$ – nwp Nov 28 '14 at 15:41
  • \$\begingroup\$ I updated the question to include an example usage and the (small) .cpp file so that the linker can find typetoken::tokenbase::counter, etc. \$\endgroup\$ – WorldSEnder Nov 28 '14 at 16:50
  • \$\begingroup\$ The purpose of this library is to give an unique ID to every requested typename during runtime. WHY? \$\endgroup\$ – Martin York Nov 28 '14 at 18:29
5
\$\begingroup\$

I used your code with the following driver to test it out.

#include <iostream>
#include <thread>
#include <vector>
#include "typetoken.h"

#define SHOW(x) std::cout << i << " says " # x " = " << x << '\n'
std::atomic<typetoken::token_t> typetoken::tokenbase::counter{100};

void f(int i) { 
    SHOW(typetoken::getToken<float>());
    SHOW(typetoken::getToken<unsigned long>());
    SHOW(typetoken::getToken<double>());
}
void g(int i) { 
    SHOW(typetoken::getToken<unsigned long>());
    SHOW(typetoken::getToken<float>());
    SHOW(typetoken::getToken<double>());
}

int main() {
    std::vector<std::thread> v;
    const int threadcount = 4;
    for (int i=0; i < threadcount; ++i) {
        v.push_back(std::move(std::thread{f, i}));
        v.push_back(std::move(std::thread{g, ++i}));
    }
    for (auto &thr : v) 
        thr.join();
}

The output varies from run to run, as we should expect. In some runs float gets assigned a value of 101, and in others 102, but after a value is assigned, it does not change and there is no possibility (that I can detect) that a value will be duplicated.

With that said, there are a few minor things that I think could be improved.

Don't use volatile unless hardware can change the value

The C++ keyword volatile only means that something outside of the program may alter the underlying value during the program's run. That does not appear to be the case here, and so counter should not be declared volatile. As Stroustrup writes:

Do not assume that volatile has special meaning in the memory model. It does not. It is not -- as in some later languages -- a synchronization mechanism.

Delete all constructors that are not desired

You have wisely deleted default constructors for tokenbase and typetoken which will help to prevent casual misuse, but what about more dedicated attempts at misuse? This example is admittedly perverse, but still possible:

typetoken::tokenbase tb(*reinterpret_cast<typetoken::tokenbase *>(77));

We now have a tokenbase object although it's almost guaranteed to be malformed. We could delete the automatically generated copy constructor, move constructor, etc. but there's a better way. The way to prevent these kinds of abuse is by adding these two lines to the declaration of tokenbase:

~tokenbase() = delete;
void *operator new(size_t) = delete;

The first makes it impossible to have a local variable of type tokenbase and the latter prevents one from being created on the free store.

Prevent other abuses

If we want to further subvert the use of this mechanism, we could define this:

namespace typetoken{
    template<>
    token_t getToken<void>(void) { return typetoken<void>::counter = 42; }
}

And then use it:

typetoken::getToken<void>();
typetoken::getToken<double>();
typetoken::getToken<void>();
typetoken::getToken<int>();

It has the effect of resetting the counter so that in this case, both int and double will be assigned the value of 43.

Perhaps the users of your class are not as destructively creative, so it may well be reasonable to simply expect that users of the class won't do this, but it can also be actively prevented. Instead of having getToken() be a friend of tokenbase you could omit that friend declaration from within tokenbase and then change typetoken and getToken to these:

template<typename T>
struct typetoken : tokenbase {
private:
    static token_t ID;
    static token_t getToken(void) {
        return ID ? ID : ID = ++typetoken::counter;
    }
    template<typename Q>
    friend token_t getToken(void);
};

template<typename T>
token_t getToken(void) {
    return typetoken<T>::getToken();
}

Now the "abusive" function simply won't compile, preventing the problem. The problem is simplified still further if we can accept the elmination of the "syntactic sugar" of the friend function. That is, if we can accept this:

typetoken::typetoken<double>::getToken();

instead of this:

typetoken::getToken<double>();

We can eliminate the friend, and make member function getToken public.

\$\endgroup\$
1
\$\begingroup\$

This review focuses more on thread safety.

  • Your version is not thread safe. If two threads call typetoken::getToken<int>(); at the same time you get a data race on typetoken<T>::ID. Unfortunately it is not enough to change the type from token_t to std::atomic<token_t>, because between checking the value and setting the value the value may have changed, leading to getToken returning different ids for the same type.

  • Using both #include guards and #pragma once seems weird. You get the disadvantages of both worlds: Global namespace pollution by the #include guard and non-portability by #pragma once. I would stick to only one.

  • volatile atomic is somewhere between redundant and inefficient. atomic gives you all guarantees of volatile and then some additional ones.

  • I dislike using void for an empty parameter list. It is useless in C++ and just adds visual noise but makes sense in C, so the code looks like it was written by a C programmer just learning C++.

  • tokenbase just holds a static variable and no functionality. There is no reason to have a class for that and even less reason to inherit from that class it since there is nothing that can be inherited, not even counter because it is private. Just use a regular atomic<token_t> counter;.

  • Do not reinvent the wheel, use typeid and std::typeinfo.

Since you specifically asked for thread safety here is my take on the problem:

TypeID.h

#ifndef TYPE_ID
#define TYPE_ID

#include <atomic>

namespace TypeID{
    using ID_t = int;

    namespace Implementation{
        template<class T>
        struct ID{
            static std::atomic<ID_t> id;
        };

        template<class T>
        std::atomic<ID_t> ID<T>::id;

        extern std::atomic<ID_t> newID;
    }

    template<class T>
    ID_t getID(){
        ID_t id = Implementation::ID<T>::id;
        if (!id){
            ID_t newID = ++Implementation::newID;
            std::atomic_compare_exchange_strong(&Implementation::ID<T>::id, &id, newID);
            id = Implementation::ID<T>::id;
        }
        return id;
    }
}

#endif

TypeID.cpp

#include "TypeID.h"
std::atomic<TypeID::ID_t> TypeID::Implementation::newID;

Note that I am less concerned with malicious misuse of my code since I cannot prevent it anyways. I stay with trying to prevent accidental misuse.

The only interesting part is the function getID. First I make a copy of the atomic variable so that in case the ID is already set I only pay for one atomic read, not two. In case the ID is not set I increment the atomic newID to get a newID and then atomically set Implementation::ID<T>::id to newID. In case I am the first to set the ID the compare exchange will succeed and Implementation::ID<T>::id will have the correct ID set which I then read and return. In case another thread managed to update Implementation::ID<T>::id before me I read the value the other thread set and return that ID. Interestingly I do not care if the compare exchange succeeds or not.

Reasoning about this kind of code is difficult. I had to revise this answer many times and was convinced every time that I got it right this time and then found another problem. My code would require another review, so just stick with this:

template<class T>
std::size_t getID(){
    return typeid(T).hash_code();
}
\$\endgroup\$
  • \$\begingroup\$ I really like your review and just want to point out that I DO want to reinvent the wheel (just for the sake of it). I want to develop a mindset for fast, secure code, not easy solutions because a day will come where there is no stdlib-version of some problem. I really like problem #1, didn't think about that. #2: Is it really bad to do this? I see how that polutes the namespace but it also leads to more compatibility, doesn't it? #4: you are right ^^ but imo it shows anyone reading the code that the empty parameter list is explicitly wanted. #5: It does enable access to ::counter. \$\endgroup\$ – WorldSEnder Nov 29 '14 at 15:20
  • \$\begingroup\$ according to this typeid().hash_code() is not guaranteed to be unique at all \$\endgroup\$ – WorldSEnder Nov 29 '14 at 16:54

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.