/*
    Copyright 2005-2010 Intel Corporation.  All Rights Reserved.

    This file is part of Threading Building Blocks.

    Threading Building Blocks is free software; you can redistribute it
    and/or modify it under the terms of the GNU General Public License
    version 2 as published by the Free Software Foundation.

    Threading Building Blocks 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 Threading Building Blocks; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    As a special exception, you may use this file as part of a free software
    library without restriction.  Specifically, if other files instantiate
    templates or use macros or inline functions from this file, or you compile
    this file and link it with other files to produce an executable, this
    file does not by itself cause the resulting executable to be covered by
    the GNU General Public License.  This exception does not however
    invalidate any other reasons why the executable file might be covered by
    the GNU General Public License.
*/

#include "tbb/reader_writer_lock.h"
#include "tbb/tbb_machine.h"
#include "tbb/tbb_exception.h"
#include "itt_notify.h"

namespace tbb {
namespace interface5 {

const unsigned WFLAG1 = 0x1;  // writer interested or active
const unsigned WFLAG2 = 0x2;  // writers interested, no entering readers
const unsigned RFLAG = 0x4;   // reader interested but not active
const unsigned RC_INCR = 0x8; // to adjust reader count


// Perform an atomic bitwise-OR on the operand with the addend, and return
// the previous value of the operand.
inline unsigned fetch_and_or(atomic<unsigned>& operand, unsigned addend) {
    tbb::internal::atomic_backoff backoff;
    for (;;) {
        unsigned old = operand;
        unsigned result = operand.compare_and_swap(old|addend, old);
        if (result==old) return old;
        backoff.pause();
    }
}

// Perform an atomic bitwise-AND on the operand with the addend, and return
// the previous value of the operand.
inline unsigned fetch_and_and(atomic<unsigned>& operand, unsigned addend) {
    tbb::internal::atomic_backoff backoff;
    for (;;) {
        unsigned old = operand;
        unsigned result = operand.compare_and_swap(old&addend, old);
        if (result==old) return old;
        backoff.pause();
    }
}

//! Spin WHILE the value at the location is greater than or equal to a given value
/** T and U should be comparable types. */
template<typename T, typename U>
void spin_wait_while_geq( const volatile T& location, U value ) {
    tbb::internal::atomic_backoff backoff;
    while( location>=value ) backoff.pause();
}

//! Spin UNTIL (location & value) is true.
/** T and U should be comparable types. */
template<typename T, typename U>
void spin_wait_until_and( const volatile T& location, U value ) {
    tbb::internal::atomic_backoff backoff;
    while( !(location & value) ) backoff.pause();
}


void reader_writer_lock::internal_construct() {
    reader_head = NULL;
    writer_head = NULL;
    writer_tail = NULL;
    rdr_count_and_flags = 0;
    my_current_writer = tbb_thread::id();
#if TBB_USE_THREADING_TOOLS
    ITT_SYNC_CREATE(this, _T("tbb::reader_writer_lock"), _T(""));
#endif /* TBB_USE_THREADING_TOOLS */
}

void reader_writer_lock::internal_destroy() {
    __TBB_ASSERT(rdr_count_and_flags==0, "reader_writer_lock destroyed with pending readers/writers.");
    __TBB_ASSERT(reader_head==NULL, "reader_writer_lock destroyed with pending readers.");
    __TBB_ASSERT(writer_tail==NULL, "reader_writer_lock destroyed with pending writers.");
    __TBB_ASSERT(writer_head==NULL, "reader_writer_lock destroyed with pending/active writers.");
}

// Acquires the reader_writer_lock for write.    If the lock is currently held in write 
// mode by another context, the writer will block by spinning on a local variable. 
// Throws exception improper_lock if the context tries to acquire a
// reader_writer_lock that it already has write ownership of.
void reader_writer_lock::lock() {
    if (is_current_writer()) { // recursive lock attempt
        // we don't support recursive writer locks; throw exception
        tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
    }
    else {
        scoped_lock *a_writer_lock = new scoped_lock();
        (void) start_write(a_writer_lock);
    }
}

// Tries to acquire the reader_writer_lock for write.    This function does not block.
// Return Value: True or false, depending on whether the lock is acquired or not.    
// If the lock is already held by this acquiring context, try_lock() returns false.
bool reader_writer_lock::try_lock() {
    if (is_current_writer()) { // recursive lock attempt
        return false;
    }
    else {
        scoped_lock *a_writer_lock = new scoped_lock();
        a_writer_lock->status = waiting_nonblocking;
        return start_write(a_writer_lock);
    }
}
    
bool reader_writer_lock::start_write(scoped_lock *I) {
    tbb_thread::id id = this_tbb_thread::get_id();
    scoped_lock *pred = NULL;
    if (I->status == waiting_nonblocking) {
        if ((pred = writer_tail.compare_and_swap(I, NULL)) != NULL) {
            delete I;
            return false;
        }
    }
    else {
        ITT_NOTIFY(sync_prepare, this);
        pred = writer_tail.fetch_and_store(I);
    }
    if (pred) 
        pred->next = I;
    else {
        set_next_writer(I);
        if (I->status == waiting_nonblocking) {
            if (I->next) { // potentially more writers
                set_next_writer(I->next);
            }
            else { // no more writers
                writer_head.fetch_and_store(NULL);
                if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
                    spin_wait_while_eq(I->next, (scoped_lock *)NULL);  // wait for new writer to be added
                    __TBB_ASSERT(I->next, "There should be a node following the last writer.");
                    set_next_writer(I->next);
                }
            }
            delete I;
            return false;
        }
    }
    spin_wait_while_eq(I->status, waiting);
    ITT_NOTIFY(sync_acquired, this);
    my_current_writer = id;
    return true;
}
    
void reader_writer_lock::set_next_writer(scoped_lock *W) {
    writer_head = W;
    if (W->status == waiting_nonblocking) {
        if (rdr_count_and_flags.compare_and_swap(WFLAG1+WFLAG2, 0) == 0) {
            W->status = active;
        }
    }
    else {
        if (fetch_and_or(rdr_count_and_flags, WFLAG1) & RFLAG) { // reader present
            spin_wait_until_and(rdr_count_and_flags, WFLAG2); // block until readers set WFLAG2
        }
        else { // no reader in timing window
            __TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
        } 
        spin_wait_while_geq(rdr_count_and_flags, RC_INCR); // block until readers finish
        W->status = active;
   }
}
    
// Acquires the reader_writer_lock for read.    If the lock is currently held by a writer,
// this reader will block and wait until the writers are done. 
// Throws exception improper_lock when the context tries to acquire a reader_writer_lock 
// that it already has write ownership of.
void reader_writer_lock::lock_read() {
    if (is_current_writer()) { // recursive lock attempt
        // we don't support writer->reader downgrade; throw exception
        tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
    }
    else {
        scoped_lock_read a_reader_lock;
        start_read(&a_reader_lock);
    }
}
    
// Tries to acquire the reader_writer_lock for read.    This function does not block.
// Return Value: True or false, depending on whether the lock is acquired or not.    
bool reader_writer_lock::try_lock_read() {
    if (is_current_writer()) { // recursive lock attempt
        return false;
    }
    else {
        if (rdr_count_and_flags.fetch_and_add(RC_INCR) & (WFLAG1+WFLAG2)) { // writers present
            rdr_count_and_flags -= RC_INCR;
            return false;
        }
        else { // no writers
            ITT_NOTIFY(sync_acquired, this);
            return true;
        }
    }
}

void reader_writer_lock::start_read(scoped_lock_read *I) {
    ITT_NOTIFY(sync_prepare, this);
    I->next = reader_head.fetch_and_store(I);
    if (!I->next) { // first arriving reader in my group; set RFLAG, test writer flags
        // unblock and/or update statuses of non-blocking readers
        if (!(fetch_and_or(rdr_count_and_flags, RFLAG) & (WFLAG1+WFLAG2))) { // no writers
            unblock_readers();
        }
    }
    __TBB_ASSERT(I->status == waiting || I->status == active, "Lock requests should be waiting or active before blocking.");
    spin_wait_while_eq(I->status, waiting); // block
    if (I->next) {
        __TBB_ASSERT(I->next->status == waiting, NULL);
        rdr_count_and_flags += RC_INCR;
        I->next->status = active; // wake successor
    }
    ITT_NOTIFY(sync_acquired, this);
}

void reader_writer_lock::unblock_readers() {
    // clear rdr interest flag, increment rdr count
    __TBB_ASSERT(rdr_count_and_flags&RFLAG, NULL);
    rdr_count_and_flags += RC_INCR-RFLAG;
    __TBB_ASSERT(rdr_count_and_flags >= RC_INCR, NULL);
    // indicate clear of window
    if (rdr_count_and_flags & WFLAG1 && !(rdr_count_and_flags & WFLAG2)) {
        __TBB_AtomicOR(&rdr_count_and_flags, WFLAG2);
    }
    // unblock waiting readers 
    scoped_lock_read *head = reader_head.fetch_and_store(NULL);
    __TBB_ASSERT(head, NULL);
    __TBB_ASSERT(head->status == waiting, NULL);
    head->status = active;
}
    
// Releases the reader_writer_lock
void reader_writer_lock::unlock() {
    if( my_current_writer!=tbb_thread::id() ) {
        // A writer owns the lock
        __TBB_ASSERT(is_current_writer(), "caller of reader_writer_lock::unlock() does not own the lock.");
        __TBB_ASSERT(writer_head, NULL);
        __TBB_ASSERT(writer_head->status==active, NULL);
        scoped_lock *a_writer_lock = writer_head;
        end_write(a_writer_lock);
        __TBB_ASSERT(a_writer_lock != writer_head, "Internal error: About to turn writer_head into dangling reference.");
        delete a_writer_lock;
    } else {
        end_read();
    }
}
    
void reader_writer_lock::end_write(scoped_lock *I) {
    __TBB_ASSERT(I==writer_head, "Internal error: can't unlock a thread that is not holding the lock.");
    my_current_writer = tbb_thread::id();
    ITT_NOTIFY(sync_releasing, this);
    if (I->next) { // potentially more writers
        writer_head = I->next;
        writer_head->status = active;
    }
    else { // No more writers; clear writer flag, test reader interest flag
        __TBB_ASSERT(writer_head, NULL);
        if (fetch_and_and(rdr_count_and_flags, ~(WFLAG1+WFLAG2)) & RFLAG) {
            unblock_readers();
        }
        writer_head.fetch_and_store(NULL);
        if (I != writer_tail.compare_and_swap(NULL, I)) { // an incoming writer is in the process of being added
            spin_wait_while_eq(I->next, (scoped_lock *)NULL);  // wait for new writer to be added
            __TBB_ASSERT(I->next, "There should be a node following the last writer.");
            set_next_writer(I->next);
        }
    }
}
    
void reader_writer_lock::end_read() {
    ITT_NOTIFY(sync_releasing, this);
    __TBB_ASSERT(rdr_count_and_flags >= RC_INCR, "unlock() called but no readers hold the lock.");
    rdr_count_and_flags -= RC_INCR;
}

inline bool reader_writer_lock::is_current_writer() {
    return my_current_writer==this_tbb_thread::get_id();
}

// Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock 
void reader_writer_lock::scoped_lock::internal_construct (reader_writer_lock& lock) {
    mutex = &lock;
    next = NULL;
    status = waiting;
    if (mutex->is_current_writer()) { // recursive lock attempt
        // we don't support recursive writer locks; throw exception
        tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
    }
    else { // this thread holds no locks
        (void) mutex->start_write(this);
    }
}

inline reader_writer_lock::scoped_lock::scoped_lock() : mutex(NULL), next(NULL) { 
    status = waiting;
}

// Construct with a blocking attempt to acquire a write lock on the passed reader_writer_lock 
void reader_writer_lock::scoped_lock_read::internal_construct (reader_writer_lock& lock) {
    mutex = &lock;
    next = NULL;
    status = waiting;
    if (mutex->is_current_writer()) { // recursive lock attempt
        // we don't support writer->reader downgrade; throw exception
        tbb::internal::throw_exception(tbb::internal::eid_improper_lock);
    }
    else { // this thread holds no locks
        mutex->start_read(this);
    }
}
  
inline reader_writer_lock::scoped_lock_read::scoped_lock_read() : mutex(NULL), next(NULL) {
    status = waiting;
}

void reader_writer_lock::scoped_lock::internal_destroy() {
    if (mutex) {
        __TBB_ASSERT(mutex->is_current_writer(), "~scoped_lock() destroyed by thread different than thread that holds lock.");
        mutex->end_write(this);
    }
    status = invalid;
}

void reader_writer_lock::scoped_lock_read::internal_destroy() { 
    if (mutex)  
        mutex->end_read(); 
    status = invalid;
}

} // namespace interface5
} // namespace tbb