2
\$\begingroup\$

Can someone please review my rwlock implementation to see if there are any issues with correctness (hopefully not), give any feedback on how to write good C code etc, design patterns which could be useful.

struct rwlock{
        pthread_cond_t read_var;
        pthread_cond_t write_var;
        pthread_mutex_t mutex;
        int readers = 0; // no of readers
        int writers = 0; // no of writers
        int read_waiters = 0; // no of waiters for reading while writing
        int write_waiters = 0; // no of waiters for writing while reading
};

void rd_lock(struct rwlock * lock){
        // if we are not writing, simply get the lock
        // if we are writing, increase the number of read_waiters and wait for signal
        pthread_mutex_lock(&lock->mutex);
        if(lock->writers == 0){
                lock->readers++;
        } else if(lock->writers > 0){
                lock->read_waiters++;
                while(pthread_cond_wait(&read_var,&mutex) != 0 && lock->writers > 0 );
                // if we have returned
                lock->read_waiters--;
                lock->readers++;
        }
        pthread_mutex_unlock(&lock->mutex);

}
void wr_lock(struct rwlock * lock){
        // if we are not readers, simply get the lock
        pthread_mutex_lock(&lock->mutex);
        if(lock->readers == 0){
                lock->writers = 1;
        } else if(lock->readers > 0){
                // if we are readers, simply increase the number of write_waiters and wait for signal
                lock->write_waiters++;
                while(pthread_cond_wait(&write_var,&mutex) != 0 && lock->readers > 0);
                // we have the mutex and lock->readers = 0
                lock->write_waiters--;
                lock->writers = 1;
        } else {
                assert(false);
        }
        pthread_mutex_unlock(&lock->mutex);
}
void unlock(struct rwlock * lock){
        pthread_mutex_lock(&lock->mutex);
        // if we are reading, decrease the number of readers if the readers becomes zero then broadcast to writers
        if(lock->readers > 0){
                lock->readers--;
                if(lock->readers == 0){
                        assert(lock->read_waiters == 0);
                        // if we are releasing the readlock completely, at this point read_waiters should be zero
                        // broadcast to writers only if there are writers
                        if(lock->write_waiters > 0){
                                pthread_cond_broadcast(&lock->write_var);
                        }
                }
        } else if(lock->readers == 0) {
                // we were writing 
                lock->writers = 0;
                // we need to completely release the lcok now
                // either the readers are going to get it or the writers are going to get it
                // give priority to the writers
                // obviously readers should be zero
                if(lock->write_waiters > 0){
                        pthread_cond_broadcast(&lock->write_var);
                } else if(lock->read_waiters > 0){
                        pthread_cond_broadcast(&lock->read_var);
                }
        } else {
                assert(false);
        }
 
```
\$\endgroup\$
3
  • \$\begingroup\$ I imagine you probably wrote some code which calls these library routines. It's too bad you have not yet shared that code as part of the Review Context. \$\endgroup\$
    – J_H
    Feb 24 at 0:51
  • \$\begingroup\$ int readers = 0; // no of readers ==> Since when did this become Standard C? Are you compiling under a C++ compiler? \$\endgroup\$
    – Harith
    Feb 24 at 7:01
  • 1
    \$\begingroup\$ @G.Sliepen I was speaking of initializing members inside the structure declaration. See: Why can't we initialize members inside a structure? \$\endgroup\$
    – Harith
    Feb 24 at 8:50

3 Answers 3

1
\$\begingroup\$
  • Consider a scenario:

    • A thread t1 calls unlock, and passes the if (lock->readers == 0) test successfully.
    • t1 is preempted by a t2 thread, which calls rdlock. Now lock->readers becomes 1.
    • t2 is preempted by t3, which also calls rdlock. Now lock->read_waiters becomes 1.
    • t1 resumes, and fails on assertion.

    Looks like a race to me.

  • rd_lock increments lock->readers no matter what. Lift lock->readers++ out of the if/else clause.

    Ditto for lock->writers = 1;. Also, I am not convinced that else in wr_lock has a right to exist.

  • I am equally not convinced that else in unlock has a right to exist. I don't see a path resulting in lock->readers < 0. Consider changing ints into unsigned ints. Along the same line, writers feels more like a bool.

\$\endgroup\$
1
  • \$\begingroup\$ Every function is wrapped around a lock->mutex. I'm not sure how that's happen here. \$\endgroup\$ Feb 24 at 6:18
1
\$\begingroup\$

asserts

I see two of them, essentially saying that readers never goes negative.

        } else {
                assert(false);
        }

I would love to see a more systematic approach to assert'ing invariants.

invariants

For any distributed / parallel computation, a clear statement of guarantees made by the system is very important. We wish to verify that invariants on state variables hold upon initialization, and then that they continue to hold as we perform operations.

I see a few remarks to that effect, e.g.

                // obviously readers should be zero

At the top of the compilation unit I would love to see some clear statements about how the four {read,write}{ers,waiters} variables are related to one another.

And then back it up with assert's in the code.

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

Your lock implementation is completely wrong. You are acquiring the lock->mutex and then mistakenly releasing it in the same function. You should only release the lock->mutex in the unlock function

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Tell us about your analysis. Suggest an event trace, a sequence of calls, that produces undesired results. \$\endgroup\$
    – J_H
    Feb 24 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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