submission of new Windows rwlock code

["Marc M. Adkins" <mm...@Doorways.org>]

I've re-coded the Windows rwlock based on the OS/2 algorithm implemented by
Brian Havard.  My test program doesn't show starvation with this algorithm.
I'm assuming that the code is stable and works correctly on OS/2, and it's
essentially the same code here, plus it passes all the tests I know how to
do so I'm submitting the code for review.

Somewhat to my surprise the performance test program that comes with APR
seems to show an increase in speed of 30% - 50%.  Possibly because the old
code had two mutex waits for a read lock and the new code has one.

I was initially surprised because the new code has tests on return values
and an extra level of subroutine calling not present in the old code.  Not
to mention additional functionality:  tryrdlock and trywrlock are both
working now and starvation should be prevented.  When does more
functionality ever mean faster?

I'm attaching the two changed files, which were essentially rewritten.  So
far as I can tell, the 2.1 code is still the same in CVS, so just replacing
the files in their entirety should be sufficient.  I can do diffs if that is
better.  I don't personally have CVS write access.

mma

Re: submission of new Windows rwlock code

[Bill Stoddard <bi...@wstoddard.com>]

Marc M. Adkins wrote:

>I've re-coded the Windows rwlock based on the OS/2 algorithm implemented by
>Brian Havard.  My test program doesn't show starvation with this algorithm.
>I'm assuming that the code is stable and works correctly on OS/2, and it's
>essentially the same code here, plus it passes all the tests I know how to
>do so I'm submitting the code for review.
>
>Somewhat to my surprise the performance test program that comes with APR
>seems to show an increase in speed of 30% - 50%.  Possibly because the old
>code had two mutex waits for a read lock and the new code has one.
>
>I was initially surprised because the new code has tests on return values
>and an extra level of subroutine calling not present in the old code.  Not
>to mention additional functionality:  tryrdlock and trywrlock are both
>working now and starvation should be prevented.  When does more
>functionality ever mean faster?
>
>I'm attaching the two changed files, which were essentially rewritten.  So
>far as I can tell, the 2.1 code is still the same in CVS, so just replacing
>the files in their entirety should be sufficient.  I can do diffs if that is
>better.  I don't personally have CVS write access.
>
>mma
>  
>
This definitely looks better based on the part I have reviewed.  It 
doesn't appear to me that the old code will ever allow multiple readers.

+1 with some coding style cleanups (which I'll do if I commit this code 
tomorrow).

Bill

RE: submission of new Windows rwlock code

["Marc M. Adkins" <mm...@Doorways.org>]

> At 07:05 PM 6/17/2003, Marc M. Adkins wrote:
> >I've re-coded the Windows rwlock based on the OS/2 algorithm
> implemented by
> >Brian Havard.  My test program doesn't show starvation with this
> algorithm.
> >I'm assuming that the code is stable and works correctly on
> OS/2, and it's
> >essentially the same code here, plus it passes all the tests I
> know how to
> >do so I'm submitting the code for review.

>From an offline discussion with Brian Havard:

> >... in the unlock code...
> >you check the value of the readers flag outside of the critical  section.
> >So in theory the readers flag could be changed between the check and the
> >critical section in which it is decremented.
> >
> >In practice, this should never happen unless a read lock is unlocked
twice.
> >So arbitrarily bad code could result in questionable behavior.  I think
it's
> >a non-issue.
>
> Ok, true, that could happen. The critical section could be brought up a
> level to prevent that without any performance penalty (except for when
> attempting to unlock a lock that's not locked which shouldn't be done
> anyway).

But in my port of Brian's code I don't use a critical section, I use the
Windows equivalent of atomic variables.  So while Brian could fix his
implementation easily I would have to do some more rewrite, to bring it back
into line with his version by creating a critical section in the unlock
code.

Frankly, I still think this is a non-issue in both cases.  It can only
happen if the APR user writes code that unlocks more than it locks, which
indicates errors in the user code anyway.  But it is potentially a hole in
the algorithm, so I figured I had to at least write it up, in case the
consensus was that a fix was in fact required.

mma

Re: submission of new Windows rwlock code

["William A. Rowe, Jr." <wr...@apache.org>]

At 07:05 PM 6/17/2003, Marc M. Adkins wrote:
>I've re-coded the Windows rwlock based on the OS/2 algorithm implemented by
>Brian Havard.  My test program doesn't show starvation with this algorithm.
>I'm assuming that the code is stable and works correctly on OS/2, and it's
>essentially the same code here, plus it passes all the tests I know how to
>do so I'm submitting the code for review.

Great work!  Consider this reviewed+=1.

Mr. Stoddard was correct, the patch needed style updates (I'll discard my
edited copies and replace them with his :-)  Not that we don't like your own
preferred style, but as a coder working in a dozen different code bases over
the course of a week, strong style affinity within a project helps keep my
mind on the right page.

I have a few other small kibitzes.  OS2 is unique from Win32 in that it will
generally provide the return value from the function, not a separate error
lookup.  In general we've used apr_get_os_error() which does apr_status_t 
conversion + GetLastError().  Stoddard was guilty of the same this a.m. :-)

>Somewhat to my surprise the performance test program that comes with APR
>seems to show an increase in speed of 30% - 50%.  Possibly because the old
>code had two mutex waits for a read lock and the new code has one.
>
>I was initially surprised because the new code has tests on return values
>and an extra level of subroutine calling not present in the old code.  Not
>to mention additional functionality:  tryrdlock and trywrlock are both
>working now and starvation should be prevented.  When does more
>functionality ever mean faster?

The magic of well written locking logic on single CPU boxes :-)

>I'm attaching the two changed files, which were essentially rewritten.  So
>far as I can tell, the 2.1 code is still the same in CVS, so just replacing
>the files in their entirety should be sufficient.  I can do diffs if that is
>better.  




In general we prefer cvs diff -u3 as the format, even when a file will change
substantially.  Remember that folks a year from now will be trying to follow
the delta from one commit to another, between an older and newer release.
Please always try to minimize gratuitous whitespace and decorative changes,
so that the cvs diff's are as clean as possible.

>I don't personally have CVS write access.

At the rate you are going this may change sooner rather than later :-)  Please
try to observe the style guidelines, as that is a chief issue when considering
when to grant our consistent contributors their own cvs write access.

  http://httpd.apache.org/dev/patches.html
  http://httpd.apache.org/dev/styleguide.html

Thanks again for this rewrite, and thanks to Brian for the original logic!

Bill