{"id":314,"date":"2016-03-11T12:08:49","date_gmt":"2016-03-11T12:08:49","guid":{"rendered":"http:\/\/www.crazygaze.com\/blog\/?p=314"},"modified":"2016-08-24T15:46:01","modified_gmt":"2016-08-24T15:46:01","slug":"callstack-markers-boostasiodetailcall_stack","status":"publish","type":"post","link":"https:\/\/www.crazygaze.com\/blog\/2016\/03\/11\/callstack-markers-boostasiodetailcall_stack\/","title":{"rendered":"Callstack markers (boost::asio::detail::call_stack)"},"content":{"rendered":"

<\/p>\n

Like I mentioned a few days ago in my previous post<\/a>, I’ve been working on a new network library for my pet project. The interface turned out very similar to Boost Asio. I eventually spent a while studying how Boost Asio solves some of the problems, so it influenced my interface and some of the inner workings.<\/p>\n

Here, I’m going to dissect a little helper class that I needed on my way to implement the equivalent to boost::asio::io_service::strand<\/a>. Now, I know I can just use Boost instead of reinventing the wheel, but I already elaborated on that in the previous post.<\/p>\n

So, let’s meet our little friend boost::asio::detail::call_stack<\/a> (or my version of it), and see why you need it.<\/p>\n

In some situations, your code needs to know if it is executing in the context of a particular function so it can make the right decisions. You can try to solve this in a couple of different ways.<\/p>\n

First, consider we have the following imaginary class to helps us out with the sample code:<\/p>\n

\n\/\/ Thread safe queue (Multi-producer\/Multi-consumer)\ntemplate <typename T>\nstruct ThreadSafeQueue {\npublic:\n    \/\/ Add a new element\n    void push(T v);\n\n    \/\/ Retrieves an element from the queue, optionally blocking to wait for new\n    \/\/ elements if the queue is empty\n    \/\/ \\return True if an element was retrieved, false if 'cancel' was called\n    bool pop(T& v, bool wait);\n\n    \/\/ Causes any current or future calls to 'pop' to finish with false\n    void cancel();\n};\n<\/pre>\n
The problem<\/h4>\n
Suppose we have this class that allows us to enqueue work to be done at a later time.<\/p>\n
\nclass WorkQueue {\npublic:\n    void post(std::function<void()> w) {\n        m_work.push(w);\n    }\n    \/\/ Run enqueued handlers. "wait" causes it to keep processing work until\n    \/\/ "stop" is called\n    void run(bool wait) {\n        std::function<void()> w;\n        while (m_work.pop(w, wait)) {\n            w();\n        }\n    }\n\n    \/\/ Stops processing new work (causing "run" to return)\n    void stop() {\n        m_work.cancel();\n    }\n\n    \/\/ Some method that let us know if we are currently executing our run\n    \/\/ method\n    bool isInRun();\n\nprivate:\n    \/\/ Some thread safe queue...\n    ThreadSafeQueue<std::function<void()>> m_work;\n};\n\n<\/pre>\n
And then we have this work item, whose behavior depends if the current thread is currently executing isInRun<\/em> or not.<\/p>\n
\n\/\/ Some global work queue\nWorkQueue globalWork;\n\nvoid func1() {\n    \/\/ Code needs to behave differently if executing "run" on the globalWork\n    \/\/ instance at the moment\n    if (globalWork.isInRun()) {\n        \/\/ ...\n    } else {\n        \/\/ ..\n    }\n}\n\nint main() {\n    globalWork.post([]() { func1(); });\n    globalWork.run(false); \/\/ Execute any currently enqueued handlers\n    return 0;\n}\n<\/pre>\n
How do we implement the WorkQueue::isInRun()<\/em> method ?<\/p>\n
The naive way<\/h4>\n
Maybe have a member variable tell us if we are currently inside WorkQueue::run<\/em> ?  Like this…<\/p>\n
\nclass WorkQueue {\npublic:\n    void run(bool wait) {\n        m_running++;\n        \/\/ ...\n        m_running--;\n    }\n\n    bool isInRun() const { return m_running > 0; }\nprivate:\n    int m_running = 0;\n};\n<\/pre>\n
Why not use bool m_running<\/em> instead? So we can deal with recursion. And why would run<\/em> be recursive? It calls unknown code (the handlers), and that code might do all kind of things the library didn’t account for. That’s also the reason why you should never hold locks while calling unknown code<\/strong>. It’s all too easy to end up with deadlocks.<\/p>\n
So, is this solution usable? Not really. The only case where it would work (that I can think off), is if you only use a WorkQueue<\/em> instance from one single thread. The problem is not even because m_running<\/em> is unprotected.<\/p>\n
Examples:<\/p>\n
\n\/\/ This works correctly\nvoid test1() {\n    globalWork.post([] {        \n        func1(); \/\/ isInRun() returns true here\n    });\n\n    \/\/ isInRun() returns false here\n    func1();\n\n    \/\/ Explicitly run any handlers\n    globalWork.run(false);\n}\n\n\/\/ This doesn't work correctly\nvoid test2() {\n    \/\/ Create worker thread to process work\n    auto th = std::thread([] { globalWork.run(true); });\n\n    globalWork.post([] {\n        \/\/ isInRun() returns true here\n        func1();\n    });\n\n    \/\/ WRONG behaviour: isInRun() returns true here.\n    \/\/ Even worse, it might return true or false depending if the worker thread\n    \/\/ is already running or not\n    func1();\n\n    \/\/ shutdown worker thread\n    globalWork.stop();\n    th.join();\n}\n<\/pre>\n
The one size fits all way<\/h4>\n
To fix this, our idea of “currently executing” needs to be tied to the thread’s callstack itself.<\/p>\n
How? By placing markers in the callstack as we go, with each marker linking to the previous one. By making the most recently placed marker accessible through thread local storage (TLS), we can then iterate through all the markers in the current thread:<\/p>\n
<\/p>\n
This is the implementation, extremely similar to Boost’s version. Main differences are the use of the now standard thread_local<\/a> , and the possibility to iterate the callstack with a range based for loop<\/a> .<\/p>\n
\ntemplate <typename Key, typename Value = unsigned char>\nclass Callstack {\npublic:\n    class Iterator;\n\n    class Context {\n    public:\n        Context(const Context&) = delete;\n        Context& operator=(const Context&) = delete;\n        explicit Context(Key* k)\n            : m_key(k), m_next(Callstack<Key, Value>::ms_top) {\n            m_val = reinterpret_cast<unsigned char*>(this);\n            Callstack<Key, Value>::ms_top = this;\n        }\n\n        Context(Key* k, Value& v)\n            : m_key(k), m_val(&v), m_next(Callstack<Key, Value>::ms_top) {\n            Callstack<Key, Value>::ms_top = this;\n        }\n\n        ~Context() {\n            Callstack<Key, Value>::ms_top = m_next;\n        }\n\n        Key* getKey() {\n            return m_key;\n        }\n\n        Value* getValue() {\n            return m_val;\n        }\n\n    private:\n        friend class Callstack<Key, Value>;\n        friend class Callstack<Key, Value>::Iterator;\n        Key* m_key;\n        Value* m_val;\n        Context* m_next;\n    };\n\n    class Iterator {\n    public:\n        Iterator(Context* ctx) : m_ctx(ctx) {}\n        Iterator& operator++() {\n            if (m_ctx)\n                m_ctx = m_ctx->m_next;\n            return *this;\n        }\n\n        bool operator!=(const Iterator& other) {\n            return m_ctx != other.m_ctx;\n        }\n\n        Context* operator*() {\n            return m_ctx;\n        }\n\n    private:\n        Context* m_ctx;\n    };\n\n    \/\/ Determine if the specified owner is on the stack\n    \/\/ \\return\n    \/\/  The address of the value if present, nullptr if not present\n    static Value* contains(const Key* k) {\n        Context* elem = ms_top;\n        while (elem) {\n            if (elem->m_key == k)\n                return elem->m_val;\n            elem = elem->m_next;\n        }\n        return nullptr;\n    }\n\n    static Iterator begin() {\n        return Iterator(ms_top);\n    }\n\n    static Iterator end() {\n        return Iterator(nullptr);\n    }\n\nprivate:\n    static thread_local Context* ms_top;\n};\n\ntemplate <typename Key, typename Value>\ntypename thread_local Callstack<Key, Value>::Context*\n    Callstack<Key, Value>::ms_top = nullptr;\n<\/pre>\n
Note that it's a templated class, which means that the following types are all distinct, and have their own linked list:<\/p>\n
\nCallstack<Foo>\nCallstack<Foo, int>\nCallstack<Bar>\nCallstack<Bar,SomeData>\n<\/pre>\n
Advantages of this solution:<\/p>\n