BlockingSync.h

/*******************************************************************************
 *     Copyright © 2015, 2016 Saman Barghi
 *
 *     This program is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU General Public License as published by
 *     the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     This program is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU General Public License for more details.
 *
 *     You should have received a copy of the GNU General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *******************************************************************************/

#ifndef UTHREADS_BLOKING_SYNC_H
#define UTHREADS_BLOKING_SYNC_H

#include "../generic/IntrusiveContainers.h"
#include <cassert>
#include <mutex>
#include <iostream>

//TODO: implement timeouts for all synchronization and mutual exclusion variables
class Mutex;
class uThread;
class BlockingQueue {
    friend class uThread;
    friend class Mutex;
    friend class OwnerLock;
    friend class ConditionVariable;
    friend class Semaphore;

    IntrusiveList<uThread> queue;

    //temporary fix to avoid including uThread.h
    uThread* getCurrentUThread();
public:
    BlockingQueue() = default;
    ~BlockingQueue() {
        assert(empty());
    }
    BlockingQueue(const BlockingQueue&) = delete;
    const BlockingQueue& operator=(const BlockingQueue&) = delete;

    bool empty() const {
        return queue.empty();
    }

    bool suspend(std::mutex& lock);

    bool suspend(Mutex&);
//  bool suspend(mutex& lock, mword timeout);

    bool signal(std::mutex& lock, uThread*& owner); //Used along with Mutex

    bool signal(std::mutex& lock) {
        uThread* dummy = nullptr;
        return signal(lock, dummy);
    }

    bool signal(Mutex&);

    void signalAll(Mutex&);

    template<typename T>
    static void postSwitchFunc(void* ut, void* args){
        assert(args != nullptr);
        assert(ut != nullptr);
        uThread* utt = (uThread*)ut;

        auto bqp = (std::pair<T*, BlockingQueue*>*)args;
        bqp->second->queue.push_back(*utt);
        bqp->first->unlock();
    }
};

class Mutex {
    friend class ConditionVariable;
    friend class Semaphore;
    friend class BlockingQueue;
protected:
    /*
     * std::mutex acting as the base lock. Usually this is implemented as a
     * spinlock, but since we are interested in blocking in user level and this
     * lock is only held for a small amount of time the possibilities that it
     * blocks the kThread for a long time is minute, and hence it is safe
     * to use a mutex as the base lock for now. This might change in the future.
     */
    std::mutex lock;
    /* The blocking queue used for this Mutex to block and unblock uThreads */
    BlockingQueue bq;
    /* Owner of the Mutex */
    uThread* owner;

    template<bool OL> // OL: owner lock
    bool internalAcquire(mword timeout) {

        lock.lock();
        //TODO: since assert is disabled during production, find another way
        //to make sure the following is happening
        //Mutex cannot have recursive locking
        assert(OL || owner != bq.getCurrentUThread());
        if(fastpath(owner != nullptr && (!OL || owner != bq.getCurrentUThread()))) {
            return bq.suspend(lock); // release lock, false: timeout
        } else {
            /*
             * End up here if:
             *  - No one is holding the lock
             *  - Someone is holding the lock and:
             *      + The type is OwnlerLock and the calling thread is holding the lock
             * Otherwise, block and wait for the lock
             */
            owner = bq.getCurrentUThread();
            lock.unlock();
            return true;
        }
    }

    void internalRelease() {
        // try baton-passing, if yes: 'signal' releases lock
        if (fastpath(bq.signal(lock, owner))) return;
        owner = nullptr;
        lock.unlock();
    }

public:
    Mutex() : owner(nullptr) {}

    template<bool OL=false>
    bool acquire() {return internalAcquire<OL>(0);}

    //TODO: implement tryAcquire after timeouts are implemented
//  template<bool OL=false>
//  bool tryAcquire(mword t = 0) { return internalAcquire<true,OL>(t); }

    void release() {
        lock.lock();
        assert(owner == bq.getCurrentUThread()); //Attempt to release lock by non-owner
        internalRelease();
    }
    //temporary solution for the postSwitchFunc
    void unlock(){release();}
};

class OwnerLock: protected Mutex {
    /*
     * Counter to keep track of how many time this has been acquired
     * by the owner.
     */
    mword counter;
public:
    OwnerLock() :
            counter(0) {
    }
    mword acquire() {
        if (internalAcquire<true>(0))
            return ++counter;
        else
            return 0;
    }
//  mword tryAcquire(mword t = 0) {
//    if (internalAcquire<true,true>(t)) return ++counter;
//    else return 0;
//  }
    mword release() {
        lock.lock();
        assert(owner == bq.getCurrentUThread());
        if (--counter == 0)
            internalRelease();
        else
            lock.unlock();
        return counter;
    }
};

class ConditionVariable {
    BlockingQueue bq;

public:
    void wait(Mutex& mutex) {
        bq.suspend(mutex);
        mutex.acquire();
    }

    void signal(Mutex& mutex) {
        if(slowpath(!bq.signal(mutex))) mutex.release();}

    void signalAll(Mutex& mutex) {bq.signalAll(mutex);}

    bool empty(){ return bq.empty(); }
};

class Semaphore {
    Mutex mutex;
    BlockingQueue bq;
    mword counter;

    template<bool TO>
    bool internalP(mword timeout) {
        if(fastpath(counter < 1)) {
            return bq.suspend(mutex); // release lock, false: timeout
        } else {
            counter -= 1;
            mutex.release();
            return true;
        }
    }

public:
    explicit Semaphore(mword c = 0) : counter(c) {}

    bool P() {
        mutex.acquire();
        return internalP<false>(0);
    }

//  bool tryP(mword t = 0, SpinLock* l = nullptr) {
//      if (l) lock.acquire(*l); else lock.acquire();
//      return internalP<true>(t);
//  }

    void V() {
        mutex.acquire();
        // try baton-passing, if yes: 'signal' releases lock
        if (fastpath(bq.signal(mutex))) return;
        counter += 1;
        mutex.release();
    }
};

#endif /* UTHREADS_BLOKING_SYNC_H */