00001 /* -*- mode:C++; c-basic-offset:4 -*- 00002 Shore-MT -- Multi-threaded port of the SHORE storage manager 00003 00004 Copyright (c) 2007-2009 00005 Data Intensive Applications and Systems Labaratory (DIAS) 00006 Ecole Polytechnique Federale de Lausanne 00007 00008 All Rights Reserved. 00009 00010 Permission to use, copy, modify and distribute this software and 00011 its documentation is hereby granted, provided that both the 00012 copyright notice and this permission notice appear in all copies of 00013 the software, derivative works or modified versions, and any 00014 portions thereof, and that both notices appear in supporting 00015 documentation. 00016 00017 This code is distributed in the hope that it will be useful, but 00018 WITHOUT ANY WARRANTY; without even the implied warranty of 00019 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS 00020 DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER 00021 RESULTING FROM THE USE OF THIS SOFTWARE. 00022 */ 00023 00024 // -*- mode:c++; c-basic-offset:4 -*- 00025 /*<std-header orig-src='shore'> 00026 00027 $Id: srwlock.cpp,v 1.2 2010/05/26 01:21:33 nhall Exp $ 00028 00029 SHORE -- Scalable Heterogeneous Object REpository 00030 00031 Copyright (c) 1994-99 Computer Sciences Department, University of 00032 Wisconsin -- Madison 00033 All Rights Reserved. 00034 00035 Permission to use, copy, modify and distribute this software and its 00036 documentation is hereby granted, provided that both the copyright 00037 notice and this permission notice appear in all copies of the 00038 software, derivative works or modified versions, and any portions 00039 thereof, and that both notices appear in supporting documentation. 00040 00041 THE AUTHORS AND THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY 00042 OF WISCONSIN - MADISON ALLOW FREE USE OF THIS SOFTWARE IN ITS 00043 "AS IS" CONDITION, AND THEY DISCLAIM ANY LIABILITY OF ANY KIND 00044 FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 00045 00046 This software was developed with support by the Advanced Research 00047 Project Agency, ARPA order number 018 (formerly 8230), monitored by 00048 the U.S. Army Research Laboratory under contract DAAB07-91-C-Q518. 00049 Further funding for this work was provided by DARPA through 00050 Rome Research Laboratory Contract No. F30602-97-2-0247. 00051 00052 */ 00053 00054 #include "w_defines.h" 00055 00056 /* -- do not edit anything above this line -- </std-header>*/ 00057 00058 #include <w.h> 00059 #include <w_debug.h> 00060 #include <sthread.h> 00061 00062 /************************************************************************************ 00063 * mcs_rwlock implementation; cheaper but problematic when we get os preemptions 00064 */ 00065 00066 // CC mangles this as __1cKmcs_rwlockOspin_on_writer6M_v_ 00067 // private 00068 void mcs_rwlock::_spin_on_writer() 00069 { 00070 while(has_writer()) ; 00071 // callers do membar_enter 00072 } 00073 // CC mangles this as __1cKmcs_rwlockPspin_on_readers6M_v_ 00074 // private 00075 void mcs_rwlock::_spin_on_readers() 00076 { 00077 while(has_reader()) ; 00078 // callers do membar_enter 00079 } 00080 00081 // private 00082 void mcs_rwlock::_add_when_writer_leaves(int delta) 00083 { 00084 // we always have the parent lock to do this 00085 _spin_on_writer(); 00086 atomic_add_32(&_holders, delta); 00087 // callers do membar_enter 00088 } 00089 00090 bool mcs_rwlock::attempt_read() 00091 { 00092 unsigned int old_value = *&_holders; 00093 if(old_value & WRITER || 00094 old_value != atomic_cas_32(&_holders, old_value, old_value+READER)) 00095 return false; 00096 00097 membar_enter(); 00098 return true; 00099 } 00100 00101 void mcs_rwlock::acquire_read() 00102 { 00103 /* attempt to CAS first. If no writers around, or no intervening 00104 * add'l readers, we're done 00105 */ 00106 if(!attempt_read()) { 00107 /* There seem to be writers around, or other readers intervened in our 00108 * attempt_read() above. 00109 * Join the queue and wait for them to leave 00110 */ 00111 { 00112 CRITICAL_SECTION(cs, (parent_lock*) this); 00113 _add_when_writer_leaves(READER); 00114 } 00115 membar_enter(); 00116 } 00117 } 00118 00119 void mcs_rwlock::release_read() 00120 { 00121 w_assert2(has_reader()); 00122 membar_exit(); // flush protected modified data before releasing lock; 00123 // update and complete any loads by others before I do this write 00124 atomic_add_32(&_holders, -READER); 00125 } 00126 00127 bool mcs_rwlock::_attempt_write(unsigned int expected) 00128 { 00129 /* succeeds iff we are the only reader (if expected==READER) 00130 * or if there are no readers or writers (if expected==0) 00131 * 00132 * How do we know there's the only reader is us? 00133 * A: we rely on these facts: this is called with expected==READER only 00134 * from attempt_upgrade(), which is called from latch only in the case 00135 * in which we hold the latch in LATCH_SH mode and are requesting it in LATCH_EX mode. 00136 00137 If there is a writer waiting we have to get in line like everyone else. 00138 No need for a membar because we already hold the latch 00139 */ 00140 ext_qnode me = EXT_QNODE_INITIALIZER; 00141 if(*&_holders != expected || !attempt(&me)) 00142 return false; 00143 // at this point, we've called mcs_lock::attempt(&me), and 00144 // have acquired the parent/mcs lock 00145 // The following line replaces our reader bit with a writer bit. 00146 bool result = (expected == atomic_cas_32(&_holders, expected, WRITER)); 00147 release(me); // parent/mcs lock 00148 membar_enter(); 00149 return result; 00150 } 00151 00152 bool mcs_rwlock::attempt_write() 00153 { 00154 if(!_attempt_write(0)) 00155 return false; 00156 00157 // moved to end of _attempt_write() membar_enter(); 00158 return true; 00159 } 00160 00161 void mcs_rwlock::acquire_write() 00162 { 00163 /* always join the queue first. 00164 * 00165 * 1. We don't want to race with other writers 00166 * 00167 * 2. We don't want to make readers deal with the gap between 00168 * us updating _holders and actually acquiring the MCS lock. 00169 */ 00170 CRITICAL_SECTION(cs, (parent_lock*) this); 00171 _add_when_writer_leaves(WRITER); 00172 w_assert1(has_writer()); // me! 00173 00174 // now wait for existing readers to clear out 00175 if(has_reader()) _spin_on_readers(); 00176 00177 // done! 00178 membar_enter(); 00179 } 00180 00181 void mcs_rwlock::release_write() { 00182 membar_exit(); // flush protected modified data before releasing lock; 00183 w_assert1(*&_holders == WRITER); 00184 *&_holders = 0; 00185 } 00186 00187 bool mcs_rwlock::attempt_upgrade() 00188 { 00189 w_assert1(has_reader()); 00190 return _attempt_write(READER); 00191 } 00192 00193 void mcs_rwlock::downgrade() 00194 { 00195 membar_exit(); // this is for all intents and purposes, a release 00196 w_assert1(*&_holders == WRITER); 00197 *&_holders = READER; 00198 membar_enter(); // but it's also an acquire 00199 }