BTreeLockingPolicy


1   /*
2   
3      Derby - Class org.apache.derby.impl.store.access.btree.BTreeLockingPolicy
4   
5      Licensed to the Apache Software Foundation (ASF) under one or more
6      contributor license agreements.  See the NOTICE file distributed with
7      this work for additional information regarding copyright ownership.
8      The ASF licenses this file to you under the Apache License, Version 2.0
9      (the "License"); you may not use this file except in compliance with
10     the License.  You may obtain a copy of the License at
11  
12        http://www.apache.org/licenses/LICENSE-2.0
13  
14     Unless required by applicable law or agreed to in writing, software
15     distributed under the License is distributed on an "AS IS" BASIS,
16     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17     See the License for the specific language governing permissions and
18     limitations under the License.
19  
20   */
21  
22  package org.apache.derby.impl.store.access.btree;
23  
24  import org.apache.derby.iapi.error.StandardException; 
25  
26  import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
27  
28  import org.apache.derby.iapi.store.access.ConglomerateController;
29  
30  import org.apache.derby.iapi.store.raw.FetchDescriptor;
31  import org.apache.derby.iapi.store.raw.Page;
32  import org.apache.derby.iapi.store.raw.RecordHandle;
33  
34  import org.apache.derby.iapi.types.DataValueDescriptor;
35  
36  import org.apache.derby.iapi.types.RowLocation;
37  
38  /**
39  
40  The generic.BTree directory wants to know as little about locking as possible,
41  in order to make the code usuable by multiple implementations.  But the 
42  generic code will make calls to abstract lock calls implemented by concrete
43  btree implementations.  Concrete implementations like B2I understand locking,
44  and needs informatation specific to the implementation to make the lock calls.
45  <p>
46  This class is created and owned by the concrete application, but is passed
47  into and returned from the generic code when lock calls are made.
48  Concrete implementations which do not need lock calls can just pass a null
49  pointer where a BTreeLockingPolicy is requested.
50  <p>
51  There are 2 types of lock interfaces, lockScan*() and lockNonScan*().
52  <p>
53  The lockScan*() interfaces assume that the caller gets a "scan lock" on the
54  page before requesting any row locks on the page.  This is either done by
55  makeing a lockScan() call followed by row lock requests, or it can be done
56  in one operation by calling lockScanRow() and requesting the scan lock be
57  obtained before getting the row lock.  Upon return from these interfaces 
58  the row lock requested is guaranteed to have been obtained on the correct
59  key for the row requested.  These interfaces handle the special case of 
60  unique indexes where the RowLocation can change while waiting on the lock 
61  (see implementation for details), basically the lock is retryed after waiting
62  if the RowLocation has changed.
63  <p>
64  The lockNonScan*() interfaces assume that no "scan lock" exists.  If these
65  routines return that the latch was released while waiting to obtain the
66  lock, then the caller must requeue the lock request after taking appropriate
67  action.  This action usually involves researching the tree to make sure 
68  that the correct key is locked with latches held.  Because no scan lock is
69  held the original row could have disappeared from the table.  These interfaces
70  do not handle the special case of unique indexes where the RowLocation can 
71  change while waiting on the lock, as the row may disappear when the latch
72  is released to wait on the lock - thus it is necessary that the caller retry
73  the lock if the interface returns that the latch was released.
74  
75  
76  **/
77  
78  public interface BTreeLockingPolicy
79  {
80      /**************************************************************************
81       * Abstract Protected lockScan*() locking methods of BTree:
82       *     lockScan                 - lock the scan page
83       *     lockScanForReclaimSpace  - lock page for reclaiming deleted rows.
84       *     lockScanRow              - lock row and possibly the scan page
85       *     unlockScan               - unlock the scan page
86       *     unlockScanRecordAfterRead- unlock the scan record
87       **************************************************************************
88       */
89  
90      /**
91       * Lock the current leaf page.
92       * <p>
93       * Logically lock the record id's on a leaf page.  This protocol is used
94       * by splits/row purgers and scans to coordinate between themselves.
95       * <p>
96       * Anyone who wants to either move rows off of a btree page or, purge
97       * them from existence must first call this routine with "forUpdate" 
98       * true.  This will result in a lock request which will block on other
99       * processes which cannot work if rows move off the page or disappear.
100      * It is expected that the this routine will only be called for update
101      * by very short term internal transactions which will commit immediately
102      * after doing their work and give up the exclusive lock quickly.
103      * <p>
104      * Currently scans can position themselves in one of 2 ways, either by
105      * saving the record handle of a record when they give up the latch on 
106      * the page, or by saving the entire row.  If they save the record handle
107      * then they must call this routine with "forUpdate" false, to get a 
108      * lock which will protect the record handle they are using from moving
109      * off the page or disapearing.  This is also why aborts of inserts must
110      * be done by marking the rows deleted, rather than purging them.
111      * It is expected that scanner's will release this lock once they move
112      * off the page they are looking at.  They do this by calling 
113      * unlockScan().
114      * <p>
115      * This lock enforces the same lock/latch protocol as btree row locks.
116      * On return the lock has been obtained.  Return status indicates if the
117      * lock was waited for, which will mean a latch(s) were dropped while 
118      * waiting.
119      * In general a false status means that the caller will either have 
120      * to research the tree unless some protocol has been implemented that
121      * insures that the row will not have moved while the latch was dropped.
122      * <p>
123      * This routine requests a special row on the RECORD_ID_PROTECTION_HANDLE 
124      * row id.  If the lock is granted the routine will return true.
125      * If the lock cannot be granted NOWAIT, then the routine will release
126      * the latch on "current_leaf" and "aux_control_row" (if 
127      * aux_control_row is non-null), and then it will request a WAIT lock on 
128      * the row.  
129      *
130      * @param current_leaf      The lock is associated with this page in the
131      *                          btree.  This control row is unlatched if the
132      *                          routine has to wait on the lock.
133      * @param aux_control_row   If non-null, this control row is unlatched 
134      *                          if the routine has to wait on the lock.
135      * @param forUpdate         Whether to wait for lock.
136      * @param lock_operation    For what operation are we requesting the lock, 
137      *                          this should be one of the following 4 options:
138      *                          LOCK_READ [read lock], 
139      *                          (LOCK_INS | LOCK_UPD) [ lock for insert], 
140      *                          (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for 
141      *                          previous key to insert],
142      *                          (LOCK_UPD) [lock for delete or replace]
143      *
144      * @exception  StandardException  Standard exception policy.
145      **/
146     abstract public boolean lockScan(
147     LeafControlRow          current_leaf,
148     ControlRow              aux_control_row,
149     boolean                 forUpdate,
150     int                     lock_operation)
151         throws StandardException;
152 
153 
154     /**
155      * Lock a control row page for reclaiming deleted rows.
156      * <p>
157      * When reclaiming deleted rows during split need to get an exclusive
158      * scan lock on the page, which will mean there are no other scans 
159      * positioned on the page.  If there are other scans positioned, just
160      * give up on reclaiming space now.
161      *
162      * @return true if lock was granted nowait, else false and not lock was
163      *         granted.
164      *
165      * @exception  StandardException  Standard exception policy.
166      **/
167     abstract public boolean lockScanForReclaimSpace(
168     LeafControlRow          current_leaf)
169         throws StandardException;
170 
171     /**
172      * Lock a btree row to determine if it is a committed deleted row.
173      * <p>
174      * Request an exclusive lock on the row located at the given slot, NOWAIT.
175      * Return true if the lock is granted, otherwise false.
176      * <p>
177      *
178      * @param open_btree        The conglomerate we are locking.
179      * @param leaf              The leaf page with the row to lock.
180      * @param template          Empty full template row, to read row into.
181      * @param slot_no           The slot of row on "current_leaf" 
182      *
183      * @exception  StandardException  Standard exception policy.
184      **/
185     abstract public boolean lockScanCommittedDeletedRow(
186     OpenBTree               open_btree,
187     LeafControlRow          leaf,
188     DataValueDescriptor[]   template,
189     FetchDescriptor         lock_fetch_desc,
190     int                     slot_no)
191         throws StandardException;
192 
193     /**
194      * Lock a row as part of doing the scan.
195      * <p>
196      * Lock the row at the given slot (or the previous row if slot is 0).
197      * Get the scan lock on the page if "request_scan_lock" is true.
198      * <p>
199      * If this routine returns true all locks were acquired while maintaining
200      * the latch on leaf.  If this routine returns false, locks may or may
201      * not have been acquired, and the routine should be called again after
202      * the client has researched the tree to reget the latch on the 
203      * appropriate page.
204      * (p>
205      * As a side effect stores the value of the record handle of the current
206      * scan lock.
207      *
208      * @return Whether locks were acquired without releasing latch on leaf.
209      *
210      * @param open_btree        The open_btree to associate latches with - 
211      *                          used if routine has to scan backward.
212      * @param btree             the conglomerate info.
213      * @param pos               Description of position of row to lock.
214      * @param request_scan_lock Whether to request the page scan lock, should
215      *                          only be requested once per page in the scan.
216      * @param lock_template     A scratch area to use to read in rows.
217      * @param previous_key_lock Is this a previous key lock call?
218      * @param forUpdate         Is the scan for update or for read only.
219      * @param lock_operation    For what operation are we requesting the lock, 
220      *                          this should be one of the following 4 options:
221      *                          LOCK_READ [read lock], 
222      *                          (LOCK_INS | LOCK_UPD) [ lock for insert], 
223      *                          (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for 
224      *                          previous key to insert],
225      *                          (LOCK_UPD) [lock for delete or replace]
226      *
227      * @exception  StandardException  Standard exception policy.
228      **/
229     abstract public boolean lockScanRow(
230     OpenBTree               open_btree,
231     BTree                   btree,
232     BTreeRowPosition        pos,
233     boolean                 request_scan_lock,
234     FetchDescriptor         lock_fetch_desc,
235     DataValueDescriptor[]   lock_template,
236     RowLocation             lock_row_loc,
237     boolean                 previous_key_lock,
238     boolean                 forUpdate,
239     int                     lock_operation)
240         throws StandardException;
241 
242     /**
243      * Release read lock on a row.
244      *
245      * @param pos               Data structure that defines the current position
246      *                          in the scan to be unlocked.
247      *
248      * @param forUpdate         Is the scan for update or for read only.
249      *
250      * @exception  StandardException  Standard exception policy.
251      **/
252     abstract public void unlockScanRecordAfterRead(
253     BTreeRowPosition        pos,
254     boolean                 forUpdate)
255         throws StandardException;
256 
257     /**
258      * Release the lock gotten by calling lockScan.  This call can only be
259      * made to release read scan locks, write scan locks must be held until
260      * end of transaction.
261      * <p>
262      *
263      * @param page_number   page number of page that lockScan was called on.
264      *
265      **/
266     abstract public void unlockScan(long page_number);
267 
268 
269     /**************************************************************************
270      * Abstract Protected lockNonScan*() locking methods of BTree:
271      *
272      *     lockNonScanPreviousRow   - lock the row previous to the current
273      *     lockNonScanRow           - lock the input row
274      *     lockNonScanRowOnPage     - lock the given row on the page.
275      **************************************************************************
276      */
277 
278     /**
279      * Lock the previous key.
280      * <p>
281      * Given the current latched page and slot number, lock the logically
282      * previous key in the table.  There are 3 cases:
283      * <p>
284      * slotnumber > 1                       - just lock (slotnumber - 1)
285      * (slotnumber == 1) && (leftmost leaf) - this is the first key in the
286      *                                        table, so lock a "magic" FIRSTKEY.
287      * (slotnumber == 1) && !(leftmost leaf)- traverse left in the tree looking
288      *                                        for a previous key.
289      * <p>
290      * On successful return from this routine appropriate locking will have
291      * been done.  All locks and latches are requested nowait, if any 
292      * lock/latch cannot be granted this routine releases the current_leaf
293      * latch and any latches it may have acquired and returns "false."
294      * <p>
295      * All extra latches that may have been gotten will have been released.
296      * <p>
297      * This routine will find the "previous row" to the (current_leaf,
298      * current_slot), walking left in the tree as necessary, and first request
299      * the lock on that row NOWAIT.  If that lock can not be granted,
300      * then it will release all latches that it has acquired up to that point
301      * including the latched current_leaf passed into the routine, and request 
302      * the lock WAIT.  Once the lock has been granted the routine will return
303      * and it is up to the caller to research the tree to find where the 
304      * row may have ended up.
305      * <p>
306      * If routine returns true, lock was granted NOWAIT, current leaf
307      * remains latched, and was never unlatched.  If routine returns false,
308      * lock was granted WAIT, current leaf is not latched, row may have 
309      * moved in the btree so caller must research to find the row.
310      *
311      *
312      * @param btree             The conglomerate we are locking.
313      * @param current_leaf      Latched current leaf where "current" key is.
314      * @param current_slot      The slot of row on "current_leaf" 
315      * @param lock_template     Empty full template row, to read row into.
316      * @param open_btree        The open_btree to associate latches with - 
317      *                          used if routine has to scan backward.
318      * @param lock_operation    For what operation are we requesting the lock, 
319      *                          this should be one of the following 4 options:
320      *                          LOCK_READ [read lock], 
321      *                          (LOCK_INS | LOCK_UPD) [ lock for insert], 
322      *                          (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for 
323      *                          previous key to insert],
324      *                          (LOCK_UPD) [lock for delete or replace]
325      * @param lock_duration     For what duration should the lock be held,
326      *                          if INSTANT_DURATION, then the routine will
327      *                          guarantee that lock was acquired while holding
328      *                          the latch, but then immediately release the
329      *                          lock.  If COMMIT_DURATION or MANUAL_DURATION
330      *                          then the lock be held when routine returns
331      *                          successfully.
332      *
333      * @exception  StandardException  Standard exception policy.
334      **/
335     abstract public boolean lockNonScanPreviousRow(
336     BTree                   btree,
337     LeafControlRow          current_leaf,
338     int                     current_slot,
339     FetchDescriptor         lock_fetch_desc,
340     DataValueDescriptor[]   lock_template,
341     RowLocation             lock_row_loc,
342     OpenBTree               open_btree,
343     int                     lock_operation,
344     int                     lock_duration)
345         throws StandardException;
346 
347     /**
348      * Lock a btree row (row in memory).  Meant to be used if caller 
349      * has the entire row objectified.
350      * <p>
351      * Lock a btree row, enforcing the standard lock/latch protocol.  
352      * On return the row is locked.  Return status indicates if the lock
353      * was waited for, which will mean a latch was dropped while waiting.
354      * In general a false status means that the caller will either have 
355      * to research the tree unless some protocol has been implemented that
356      * insures that the row will not have moved while the latch was dropped.
357      * <p>
358      * This routine request a row lock NOWAIT on the in-memory row 
359      * "current_row.".  If the lock is granted the routine will return true.
360      * If the lock cannot be granted NOWAIT, then the routine will release
361      * the latch on "current_leaf" (if current_leaf is non-null) and 
362      * "aux_leaf" (if aux_leaf is non-null), and then it will request a WAIT 
363      * lock on the row.  
364      *
365      *
366      * @param btree             The conglomerate we are locking.
367      * @param current_leaf      If non-null, this leaf is unlatched if the 
368      *                          routine has to wait on the lock.
369      * @param aux_leaf          If non-null, this leaf is unlatched if the 
370      *                          routine has to wait on the lock.
371      * @param current_row       In memory, objectified "current" row.
372      * @param lock_operation    For what operation are we requesting the lock, 
373      *                          this should be one of the following 4 options:
374      *                          LOCK_READ [read lock], 
375      *                          (LOCK_INS | LOCK_UPD) [ lock for insert], 
376      *                          (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for 
377      *                          previous key to insert],
378      *                          (LOCK_UPD) [lock for delete or replace]
379      *
380      * @exception  StandardException  Standard exception policy.
381      **/
382     abstract public boolean lockNonScanRow(
383     BTree                   btree,
384     LeafControlRow          current_leaf,
385     LeafControlRow          aux_leaf,
386     DataValueDescriptor[]   current_row,
387     int                     lock_operation)
388         throws StandardException;
389 
390     /**
391      * Lock the row at the given slot.
392      * <p>
393      * If this routine returns true all locks were acquired while maintaining
394      * the latch on leaf.  If this routine returns false, locks may or may
395      * not have been acquired, and the routine should be called again after
396      * the client has researched the tree to reget the latch on the 
397      * appropriate page.
398      *
399      * @return Whether locks were acquired without releasing latch on leaf.
400      *
401      * @param btree             the conglomerate info.
402      * @param leaf              The control row of the current leaf to lock.
403      * @param slot              The slot position of the row to lock.
404      * @param lock_template     A scratch area to use to read in rows.
405      * @param lock_operation    For what operation are we requesting the lock, 
406      *                          this should be one of the following 4 options:
407      *                          LOCK_READ [read lock], 
408      *                          (LOCK_INS | LOCK_UPD) [ lock for insert], 
409      *                          (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for 
410      *                          previous key to insert],
411      *                          (LOCK_UPD) [lock for delete or replace]
412      *
413      * @exception  StandardException  Standard exception policy.
414      **/
415     abstract public boolean lockNonScanRowOnPage(
416     BTree                   btree,
417     LeafControlRow          leaf,
418     int                     slot,
419     FetchDescriptor         lock_fetch_desc,
420     DataValueDescriptor[]   lock_template,
421     RowLocation             lock_row_loc,
422     int                     lock_operation)
423         throws StandardException;
424 }
425
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags