1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002, 2014 Oracle and/or its affiliates.  All rights reserved.
5  *
6  */
7 
8 package com.sleepycat.je.rep.vlsn;
9 
10 import static com.sleepycat.je.utilint.VLSN.NULL_VLSN;
11 
12 import com.sleepycat.bind.tuple.LongBinding;
13 import com.sleepycat.bind.tuple.TupleBinding;
14 import com.sleepycat.bind.tuple.TupleInput;
15 import com.sleepycat.bind.tuple.TupleOutput;
16 import com.sleepycat.je.Cursor;
17 import com.sleepycat.je.CursorConfig;
18 import com.sleepycat.je.DatabaseEntry;
19 import com.sleepycat.je.DbInternal;
20 import com.sleepycat.je.EnvironmentFailureException;
21 import com.sleepycat.je.OperationStatus;
22 import com.sleepycat.je.dbi.DatabaseImpl;
23 import com.sleepycat.je.dbi.EnvironmentImpl;
24 import com.sleepycat.je.log.LogEntryType;
25 import com.sleepycat.je.txn.Txn;
26 import com.sleepycat.je.utilint.VLSN;
27 
28 public class VLSNRange {
29 
30     /* On-disk version. */
31     private static final int VERSION = 1;
32     public static final long RANGE_KEY = -1L;
33     static final VLSNRange EMPTY = new VLSNRange(NULL_VLSN, NULL_VLSN,
34                                                  NULL_VLSN, NULL_VLSN);
35 
36     /*
37      * Information about the range of contiguous VLSN entries on this node.
38      * All the range values must be viewed together, to ensure a consistent set
39      * of values.
40      */
41     private final VLSN first;
42     private final VLSN last;
43     private final byte commitType = LogEntryType.LOG_TXN_COMMIT.getTypeNum();
44     private final byte abortType = LogEntryType.LOG_TXN_ABORT.getTypeNum();
45 
46     /*
47      * VLSN of the last log entry in our VLSN range that can serve as a sync
48      * matchpoint.
49      */
50     private final VLSN lastSync;
51     private final VLSN lastTxnEnd;
52 
VLSNRange(VLSN first, VLSN last, VLSN lastSync, VLSN lastTxnEnd)53     private VLSNRange(VLSN first,
54                       VLSN last,
55                       VLSN lastSync,
56                       VLSN lastTxnEnd) {
57         this.first = first;
58         this.last = last;
59         this.lastSync = lastSync;
60         this.lastTxnEnd = lastTxnEnd;
61     }
62 
63     /**
64      * When the range is written out by the VLSNTracker, we must always be sure
65      * to update the tracker's lastVSLNOnDisk field. Return the last VLSN in
66      * the range as part of this method, to help ensure that update.
67      * @param envImpl
68      * @param dbImpl
69      * @param txn
70      */
writeToDatabase(final EnvironmentImpl envImpl, final DatabaseImpl dbImpl, Txn txn)71     VLSN writeToDatabase(final EnvironmentImpl envImpl,
72                          final DatabaseImpl dbImpl,
73                          Txn txn) {
74 
75         VLSNRangeBinding binding = new VLSNRangeBinding();
76         DatabaseEntry key = new DatabaseEntry();
77         DatabaseEntry data = new DatabaseEntry();
78 
79         LongBinding.longToEntry(RANGE_KEY, key);
80         binding.objectToEntry(this, data);
81 
82         Cursor c = null;
83         try {
84             c = DbInternal.makeCursor(dbImpl,
85                                       txn,
86                                       CursorConfig.DEFAULT);
87             DbInternal.getCursorImpl(c).setAllowEviction(false);
88 
89             OperationStatus status = c.put(key, data);
90             if (status != OperationStatus.SUCCESS) {
91                 throw EnvironmentFailureException.unexpectedState
92                     (envImpl, "Unable to write VLSNRange, status = " + status);
93             }
94         } finally {
95             if (c != null) {
96                 c.close();
97             }
98         }
99         return last;
100     }
101 
readFromDatabase(DatabaseEntry data)102     public static VLSNRange readFromDatabase(DatabaseEntry data) {
103         VLSNRangeBinding binding = new VLSNRangeBinding();
104         VLSNRange range = binding.entryToObject(data);
105 
106         return range;
107     }
108 
getFirst()109     public VLSN getFirst() {
110         return first;
111     }
112 
getLast()113     public VLSN getLast() {
114         return last;
115     }
116 
getLastSync()117     public VLSN getLastSync() {
118         return lastSync;
119     }
120 
getLastTxnEnd()121     public VLSN getLastTxnEnd() {
122         return lastTxnEnd;
123     }
124 
125     /**
126      * Return the VLSN that should come after the lastVLSN.
127      */
getUpcomingVLSN()128     VLSN getUpcomingVLSN() {
129         return last.getNext();
130     }
131 
132     /**
133      * @return true if this VLSN is within the range described by this class.
134      */
contains(final VLSN vlsn)135     public boolean contains(final VLSN vlsn) {
136         if (first.equals(NULL_VLSN)) {
137             return false;
138         }
139 
140         if ((first.compareTo(vlsn) <= 0) && (last.compareTo(vlsn) >= 0)) {
141             return true;
142         }
143 
144         return false;
145     }
146 
147     /**
148      * A new VLSN->LSN mapping has been registered in a bucket. Update the
149      * range accordingly.
150      */
getUpdateForNewMapping(final VLSN newValue, final byte entryTypeNum)151     VLSNRange getUpdateForNewMapping(final VLSN newValue,
152                                      final byte entryTypeNum) {
153         VLSN newFirst = first;
154         VLSN newLast = last;
155         VLSN newLastSync = lastSync;
156         VLSN newLastTxnEnd = lastTxnEnd;
157 
158         if (first.equals(NULL_VLSN) || first.compareTo(newValue) > 0) {
159             newFirst = newValue;
160         }
161 
162         if (last.compareTo(newValue) < 0) {
163             newLast = newValue;
164         }
165 
166         if (LogEntryType.isSyncPoint(entryTypeNum)) {
167             if (lastSync.compareTo(newValue) < 0) {
168                 newLastSync = newValue;
169             }
170         }
171 
172         if ((entryTypeNum == commitType) || (entryTypeNum == abortType)) {
173             if (lastTxnEnd.compareTo(newValue) < 0) {
174                 newLastTxnEnd = newValue;
175             }
176         }
177 
178         return new VLSNRange(newFirst, newLast, newLastSync, newLastTxnEnd);
179     }
180 
181     /**
182      * Incorporate the information in "other" in this range.
183      */
getUpdate(final VLSNRange other)184     VLSNRange getUpdate(final VLSNRange other) {
185         VLSN newFirst = getComparison(first, other.first,
186                                       other.first.compareTo(first) < 0);
187         VLSN newLast = getComparison(last, other.last,
188                                      other.last.compareTo(last) > 0);
189         VLSN newLastSync =
190             getComparison(lastSync, other.lastSync,
191                           other.lastSync.compareTo(lastSync) > 0);
192         VLSN newLastTxnEnd =
193             getComparison(lastTxnEnd, other.lastTxnEnd,
194                           other.lastTxnEnd.compareTo(lastTxnEnd) > 0);
195         return new VLSNRange(newFirst, newLast, newLastSync, newLastTxnEnd);
196     }
197 
198     /**
199      * The "other" range is going to be appended to this range.
200      */
merge(final VLSNRange other)201     VLSNRange merge(final VLSNRange other) {
202         VLSN newLast = getComparison(last, other.last, true);
203         VLSN newLastSync = getComparison(lastSync, other.lastSync, true);
204         VLSN newLastTxnEnd = getComparison(lastTxnEnd, other.lastTxnEnd, true);
205         return new VLSNRange(first, newLast, newLastSync, newLastTxnEnd);
206     }
207 
208     /*
209      * We can assume that deleteStart.getPrev() is either NULL_VLSN or is
210      * on a sync-able boundary. We can also assume that lastTxnEnd has not
211      * been changed. And lastly, we can assume that this range is not empty,
212      * since that was checked earlier on.
213      */
shortenFromEnd(final VLSN deleteStart)214     VLSNRange shortenFromEnd(final VLSN deleteStart) {
215         VLSN newLast = deleteStart.getPrev();
216 
217         assert newLast.compareTo(lastTxnEnd) >= 0 :
218         "Can't truncate at " + newLast +
219             " because it overwrites a commit at " +  lastTxnEnd;
220 
221         if (newLast.equals(NULL_VLSN)) {
222             return new VLSNRange(NULL_VLSN, NULL_VLSN, NULL_VLSN, NULL_VLSN);
223         }
224         return new VLSNRange(first, newLast, newLast, lastTxnEnd);
225     }
226 
227     /*
228      * @return an new VLSNRange which starts at deleteEnd.getNext()
229      */
shortenFromHead(final VLSN deleteEnd)230     VLSNRange shortenFromHead(final VLSN deleteEnd) {
231         /* We shouldn't be truncating the last sync */
232 
233         VLSN newFirst = null;
234         VLSN newLast = last;
235         if (deleteEnd.compareTo(last) == 0) {
236             newFirst = NULL_VLSN;
237             newLast = NULL_VLSN;
238         } else {
239             newFirst = deleteEnd.getNext();
240         }
241 
242         assert (lastSync.equals(NULL_VLSN) ||
243                 lastSync.compareTo(newFirst) >= 0 ) :
244             "Can't truncate lastSync= " + lastSync + " deleteEnd=" + deleteEnd;
245 
246         VLSN newTxnEnd = lastTxnEnd.compareTo(newFirst) > 0 ?
247             lastTxnEnd : NULL_VLSN;
248 
249         return new VLSNRange(newFirst, newLast, lastSync, newTxnEnd);
250     }
251 
252     /**
253      * Compare two VLSNs, normalizing for NULL_VLSN. If one of them is
254      * NULL_VLSN, return the other one. If neither are NULL_VLSN, use the
255      * result of the comparison, expressed as the value of "better" to decide
256      * which one to return. If "better" is true, return "otherVLSN".
257      */
getComparison(final VLSN thisVLSN, final VLSN otherVLSN, final boolean better)258     private VLSN getComparison(final VLSN thisVLSN,
259                                final VLSN otherVLSN,
260                                final boolean better) {
261         if (thisVLSN.equals(NULL_VLSN)) {
262             return otherVLSN;
263         }
264 
265         if (otherVLSN.equals(NULL_VLSN)) {
266             return thisVLSN;
267         }
268 
269         if (better) {
270             return otherVLSN;
271         }
272 
273         return thisVLSN;
274     }
275 
isEmpty()276     boolean isEmpty() {
277         return first.equals(NULL_VLSN);
278     }
279 
280     @Override
toString()281     public String toString() {
282         StringBuilder sb = new StringBuilder();
283         sb.append("first=").append(first);
284         sb.append(" last=").append(last);
285         sb.append(" sync=").append(lastSync);
286         sb.append(" txnEnd=").append(lastTxnEnd);
287         return sb.toString();
288     }
289 
290     /**
291      * Marshals a VLSNRange to a byte buffer to store in the database.
292      */
293     static class VLSNRangeBinding extends TupleBinding<VLSNRange> {
294 
295         @Override
entryToObject(final TupleInput ti)296         public VLSNRange entryToObject(final TupleInput ti) {
297             int onDiskVersion = ti.readPackedInt();
298             if (onDiskVersion != VERSION) {
299                 throw EnvironmentFailureException.unexpectedState
300                     ("Don't expect version diff " +
301                      "on_disk=" + onDiskVersion +
302                      " source=" +
303                      VERSION);
304             }
305 
306             VLSNRange range =
307                 new VLSNRange(new VLSN(ti.readPackedLong()), // first
308                               new VLSN(ti.readPackedLong()), // last
309                               new VLSN(ti.readPackedLong()), // lastSync
310                               new VLSN(ti.readPackedLong())); // lastTxnEnd
311             return range;
312         }
313 
314         @Override
objectToEntry(final VLSNRange range, final TupleOutput to)315         public void objectToEntry(final VLSNRange range,
316                                   final TupleOutput to) {
317             /* No need to store the file number -- that's the key */
318             to.writePackedInt(VERSION);
319             to.writePackedLong(range.getFirst().getSequence());
320             to.writePackedLong(range.getLast().getSequence());
321             to.writePackedLong(range.getLastSync().getSequence());
322             to.writePackedLong(range.getLastTxnEnd().getSequence());
323         }
324     }
325 
verify(final boolean verbose)326     boolean verify(final boolean verbose) {
327         if (first.equals(NULL_VLSN)) {
328             if (!(last.equals(NULL_VLSN) &&
329                   (lastSync.equals(NULL_VLSN)) &&
330                   (lastTxnEnd.equals(NULL_VLSN)))) {
331                 if (verbose) {
332                     System.out.println("Range: All need to be NULL_VLSN " +
333                                        this);
334                 }
335                 return false;
336             }
337         } else {
338             if (first.compareTo(last) > 0) {
339                 if (verbose) {
340                     System.out.println("Range: first > last " + this);
341                 }
342                 return false;
343             }
344 
345             if (!lastSync.equals(NULL_VLSN)) {
346                 if (lastSync.compareTo(last) > 0) {
347                     if (verbose) {
348                         System.out.println("Range: lastSync > last " + this);
349                     }
350                     return false;
351                 }
352             }
353 
354             if (!lastTxnEnd.equals(NULL_VLSN)) {
355                 if (lastTxnEnd.compareTo(last) > 0) {
356                     if (verbose) {
357                         System.out.println("Range: lastTxnEnd > last " + this);
358                     }
359                     return false;
360                 }
361             }
362         }
363         return true;
364     }
365 
366     /**
367      * @return true if subsetRange is a subset of this range.
368      */
verifySubset(final boolean verbose, final VLSNRange subsetRange)369     boolean verifySubset(final boolean verbose, final VLSNRange subsetRange) {
370         if (subsetRange == null) {
371             return true;
372         }
373 
374         if ((subsetRange.getFirst().equals(NULL_VLSN)) &&
375             (subsetRange.getLast().equals(NULL_VLSN)) &&
376             (subsetRange.getLastSync().equals(NULL_VLSN)) &&
377             (subsetRange.getLastTxnEnd().equals(NULL_VLSN))) {
378             return true;
379         }
380 
381         if (first.compareTo(subsetRange.getFirst()) >  0) {
382             if (verbose) {
383                 System.out.println("Range: subset must be LTE: this=" + this +
384                                    " subset=" + subsetRange);
385             }
386             return false;
387         }
388 
389         if (first.equals(NULL_VLSN)) {
390             return true;
391         }
392 
393         if (last.compareTo(subsetRange.getLast()) < 0) {
394             if (verbose) {
395                 System.out.println("Range: last must be GTE: this=" + this +
396                                    " subsetRange=" + subsetRange);
397             }
398             return false;
399         }
400         return true;
401     }
402 }
403