Java > Open Source Codes > com > sleepycat > je > cleaner > FileProcessor


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: FileProcessor.java,v 1.17 2006/10/30 21:14:13 bostic Exp $
7  */
8
9 package com.sleepycat.je.cleaner;
10
11 import java.io.IOException ;
12 import java.util.HashMap ;
13 import java.util.HashSet ;
14 import java.util.Iterator ;
15 import java.util.Map ;
16 import java.util.Set ;
17 import java.util.SortedMap ;
18 import java.util.TreeMap ;
19 import java.util.logging.Level ;
20
21 import com.sleepycat.je.DatabaseException;
22 import com.sleepycat.je.dbi.DatabaseId;
23 import com.sleepycat.je.dbi.DatabaseImpl;
24 import com.sleepycat.je.dbi.DbTree;
25 import com.sleepycat.je.dbi.EnvironmentImpl;
26 import com.sleepycat.je.dbi.MemoryBudget;
27 import com.sleepycat.je.log.CleanerFileReader;
28 import com.sleepycat.je.tree.BIN;
29 import com.sleepycat.je.tree.ChildReference;
30 import com.sleepycat.je.tree.DIN;
31 import com.sleepycat.je.tree.IN;
32 import com.sleepycat.je.tree.LN;
33 import com.sleepycat.je.tree.SearchResult;
34 import com.sleepycat.je.tree.Tree;
35 import com.sleepycat.je.tree.TreeLocation;
36 import com.sleepycat.je.tree.WithRootLatched;
37 import com.sleepycat.je.txn.BasicLocker;
38 import com.sleepycat.je.txn.LockGrantType;
39 import com.sleepycat.je.txn.LockResult;
40 import com.sleepycat.je.txn.LockType;
41 import com.sleepycat.je.utilint.DaemonThread;
42 import com.sleepycat.je.utilint.DbLsn;
43 import com.sleepycat.je.utilint.Tracer;
44
45 /**
46  * Reads all entries in a log file and either determines them to be obsolete or
47  * marks them for migration. LNs are marked for migration by setting the BIN
48  * entry MIGRATE flag. INs are marked for migration by setting the dirty flag.
49  *
50  * May be invoked explicitly by calling doClean, or woken up if used as a
51  * daemon thread.
52  */
53 class FileProcessor extends DaemonThread {
54
55     /**
56      * The number of LN log entries after we process pending LNs. If we do
57      * this too seldom, the pending LN queue may grow large, and it isn't
58      * budgeted memory. If we process it too often, we will repeatedly request
59      * a non-blocking lock for the same locked node.
60      */
61     private static final int PROCESS_PENDING_EVERY_N_LNS = 100;
62
63     /**
64      * Whether to prohibit BINDeltas for a BIN that is fetched by the cleaner.
65      * The theory is that when fetching a BIN during cleaning we normally
66      * expect that the BIN will be evicted soon, and a delta during checkpoint
67      * would be wasted. However, this does not take into account use of the
68      * BIN by the application after fetching; the BIN could become hot and then
69      * deltas may be profitable. To be safe we currently allow deltas when
70      * fetching.
71      */
72     private static final boolean PROHIBIT_DELTAS_WHEN_FETCHING = false;
73
74     private static final boolean DEBUG_TRACING = false;
75
76     private EnvironmentImpl env;
77     private Cleaner cleaner;
78     private FileSelector fileSelector;
79     private UtilizationProfile profile;
80
81     /* Log version for the target file. */
82     private int fileLogVersion;
83
84     /* Per Run counters. Reset before each file is processed. */
85     private int nINsObsoleteThisRun = 0;
86     private int nINsCleanedThisRun = 0;
87     private int nINsDeadThisRun = 0;
88     private int nINsMigratedThisRun = 0;
89     private int nLNsObsoleteThisRun = 0;
90     private int nLNsCleanedThisRun = 0;
91     private int nLNsDeadThisRun = 0;
92     private int nLNsLockedThisRun = 0;
93     private int nLNsMigratedThisRun = 0;
94     private int nLNsMarkedThisRun = 0;
95     private int nLNQueueHitsThisRun = 0;
96     private int nEntriesReadThisRun;
97     private long nRepeatIteratorReadsThisRun;
98
99     FileProcessor(String name,
100                   EnvironmentImpl env,
101                   Cleaner cleaner,
102                   UtilizationProfile profile,
103                   FileSelector fileSelector) {
104         super(0, name, env);
105         this.env = env;
106         this.cleaner = cleaner;
107         this.fileSelector = fileSelector;
108         this.profile = profile;
109     }
110
111     public void clearEnv() {
112         env = null;
113         cleaner = null;
114         fileSelector = null;
115         profile = null;
116     }
117
118     /**
119      * Adds a sentinal object to the work queue to force onWakeup to be
120      * called immediately after setting je.env.runCleaner=true. We want to
121      * process any backlog immediately.
122      */
123     void addSentinalWorkObject() {
124         try {
125             workQueueLatch.acquire();
126             workQueue.add(new Object ());
127             workQueueLatch.release();
128         } catch (DatabaseException e) {
129             throw new IllegalStateException (e);
130         }
131     }
132
133     /**
134      * Return the number of retries when a deadlock exception occurs.
135      */
136     protected int nDeadlockRetries()
137         throws DatabaseException {
138
139         return cleaner.nDeadlockRetries;
140     }
141
142     /**
143      * Cleaner doesn't have a work queue so just throw an exception if it's
144      * ever called.
145      */
146     public void addToQueue(Object o)
147         throws DatabaseException {
148
149         throw new DatabaseException
150             ("Cleaner.addToQueue should never be called.");
151     }
152
153     /**
154      * Activates the cleaner. Is normally called when je.cleaner.byteInterval
155      * bytes are written to the log.
156      */
157     public void onWakeup()
158         throws DatabaseException {
159
160         doClean(true, // invokedFromDaemon
161 true, // cleanMultipleFiles
162 false); // forceCleaning
163
164         /* Remove the sentinal -- see addSentinalWorkObject. */
165         workQueueLatch.acquire();
166         workQueue.clear();
167         workQueueLatch.release();
168     }
169
170     /**
171      * Cleans selected files and returns the number of files cleaned. May be
172      * called by the daemon thread or programatically.
173      *
174      * @param invokedFromDaemon currently has no effect.
175      *
176      * @param cleanMultipleFiles is true to clean until we're under budget,
177      * or false to clean at most one file.
178      *
179      * @param forceCleaning is true to clean even if we're not under the
180      * utilization threshold.
181      *
182      * @return the number of files cleaned, not including files cleaned
183      * unsuccessfully.
184      */
185     public synchronized int doClean(boolean invokedFromDaemon,
186                                     boolean cleanMultipleFiles,
187                                     boolean forceCleaning)
188         throws DatabaseException {
189
190         if (env.isClosed()) {
191             return 0;
192         }
193
194         /* Clean until no more files are selected. */
195         int nOriginalLogFiles = profile.getNumberOfFiles();
196         int nFilesCleaned = 0;
197         while (true) {
198
199             /* Don't clean forever. */
200             if (nFilesCleaned >= nOriginalLogFiles) {
201                 break;
202             }
203
204             /* Stop if the daemon is paused or the environment is closing. */
205             if ((invokedFromDaemon && isPaused()) || env.isClosing()) {
206                 break;
207             }
208
209             /*
210              * Process pending LNs and then attempt to delete all cleaned files
211              * that are safe to delete. Pending LNs can prevent file deletion.
212              */
213             cleaner.processPending();
214             cleaner.deleteSafeToDeleteFiles();
215
216             /*
217              * Select the next file for cleaning and update the Cleaner's
218              * read-only file collections.
219              */
220             boolean needLowUtilizationSet =
221                 cleaner.clusterResident || cleaner.clusterAll;
222
223             Long fileNum = fileSelector.selectFileForCleaning
224                 (profile, forceCleaning, needLowUtilizationSet,
225                  cleaner.maxBatchFiles);
226
227             cleaner.updateReadOnlyFileCollections();
228
229             /*
230              * If no file was selected, the total utilization is under the
231              * threshold and we can stop cleaning.
232              */
233             if (fileNum == null) {
234                 break;
235             }
236
237             /*
238              * Clean the selected file.
239              */
240             resetPerRunCounters();
241             boolean finished = false;
242             long fileNumValue = fileNum.longValue();
243             int runId = ++cleaner.nCleanerRuns;
244             try {
245
246                 String traceMsg =
247                     "CleanerRun " + runId +
248                     " on file 0x" + Long.toHexString(fileNumValue) +
249                     " begins backlog=" + cleaner.nBacklogFiles;
250                 Tracer.trace(Level.INFO, env, traceMsg);
251                 if (DEBUG_TRACING) {
252                     System.out.println("\n" + traceMsg);
253                 }
254
255                 /* Clean all log entries in the file. */
256                 Set deferredWriteDbs = new HashSet ();
257                 if (processFile(fileNum, deferredWriteDbs)) {
258                     /* File is fully processed, update status information. */
259                     fileSelector.addCleanedFile(fileNum, deferredWriteDbs);
260                     nFilesCleaned += 1;
261                     accumulatePerRunCounters();
262                     finished = true;
263                 }
264             } catch (IOException IOE) {
265                 Tracer.trace(env, "Cleaner", "doClean", "", IOE);
266                 throw new DatabaseException(IOE);
267             } finally {
268                 if (!finished) {
269                     fileSelector.putBackFileForCleaning(fileNum);
270                 }
271                 String traceMsg =
272                     "CleanerRun " + runId +
273                     " on file 0x" + Long.toHexString(fileNumValue) +
274                     " invokedFromDaemon=" + invokedFromDaemon +
275                     " finished=" + finished +
276                     " nEntriesRead=" + nEntriesReadThisRun +
277                     " nINsObsolete=" + nINsObsoleteThisRun +
278                     " nINsCleaned=" + nINsCleanedThisRun +
279                     " nINsDead=" + nINsDeadThisRun +
280                     " nINsMigrated=" + nINsMigratedThisRun +
281                     " nLNsObsolete=" + nLNsObsoleteThisRun +
282                     " nLNsCleaned=" + nLNsCleanedThisRun +
283                     " nLNsDead=" + nLNsDeadThisRun +
284                     " nLNsMigrated=" + nLNsMigratedThisRun +
285                     " nLNsMarked=" + nLNsMarkedThisRun +
286                     " nLNQueueHits=" + nLNQueueHitsThisRun +
287                     " nLNsLocked=" + nLNsLockedThisRun;
288                 Tracer.trace(Level.SEVERE, env, traceMsg);
289                 if (DEBUG_TRACING) {
290                     System.out.println("\n" + traceMsg);
291                 }
292             }
293
294             /* If we should only clean one file, stop now. */
295             if (!cleanMultipleFiles) {
296                 break;
297             }
298         }
299
300         return nFilesCleaned;
301     }
302
303     /**
304      * Process all log entries in the given file.
305      *
306      * Note that we check for obsolete entries using the active TFS
307      * (TrackedFileSummary) for a file while it is being processed, and we
308      * prohibit flushing (eviction) of that offset information until file
309      * processing is complete. An entry could become obsolete because: 1-
310      * normal application activity deletes or updates the entry, 2- proactive
311      * migration migrates the entry before we process it, or 3- if trackDetail
312      * is false. However, checking the TFS is expensive if it has many
313      * entries, because we perform a linear search. There is a tradeoff
314      * between the cost of the TFS lookup and its benefit, which is to avoid a
315      * tree search if the entry is obsolete. Note that many more lookups for
316      * non-obsolete entries than obsolete entries will typically be done. In
317      * spite of that we check the tracked summary to avoid the situation where
318      * eviction does proactive migration, and evicts a BIN that is very soon
319      * afterward fetched during cleaning.
320      *
321      * @param fileNum the file being cleaned.
322      * @param deferredWriteDbs the set of databaseIds for deferredWrite
323      * databases which need a sync before a cleaned file can be safely deleted.
324      * @return false if we aborted file processing because the environment is
325      * being closed.
326      */
327     private boolean processFile(Long fileNum, Set deferredWriteDbs)
328         throws DatabaseException, IOException {
329
330         /* Get the current obsolete offsets for this file. */
331         PackedOffsets obsoleteOffsets = new PackedOffsets();
332         TrackedFileSummary tfs =
333             profile.getObsoleteDetail(fileNum,
334                                       obsoleteOffsets,
335                                       true /* logUpdate */);
336         PackedOffsets.Iterator obsoleteIter = obsoleteOffsets.iterator();
337         long nextObsolete = -1;
338
339         /* Keep in local variables because they are mutable properties. */
340         final int readBufferSize = cleaner.readBufferSize;
341         int lookAheadCacheSize = cleaner.lookAheadCacheSize;
342
343         /*
344          * Add the overhead of this method to the budget. Two read buffers are
345          * allocated by the file reader. The log size of the offsets happens to
346          * be the same as the memory overhead.
347          */
348         int adjustMem = (2 * readBufferSize) +
349                         obsoleteOffsets.getLogSize() +
350                         lookAheadCacheSize;
351         MemoryBudget budget = env.getMemoryBudget();
352         budget.updateMiscMemoryUsage(adjustMem);
353
354         /* Evict after updating the budget. */
355         if (Cleaner.DO_CRITICAL_EVICTION) {
356             env.getEvictor().doCriticalEviction(true); // backgroundIO
357 }
358
359         /*
360          * We keep a look ahead cache of non-obsolete LNs. When we lookup a
361          * BIN in processLN, we also process any other LNs in that BIN that are
362          * in the cache. This can reduce the number of tree lookups.
363          */
364         LookAheadCache lookAheadCache = new LookAheadCache(lookAheadCacheSize);
365
366         /*
367          * For obsolete entries we must check for pending deleted DBs. To
368          * avoid the overhead of DbTree.getDb on every entry we keep a set of
369          * all DB IDs encountered and do the check once per DB at the end.
370          */
371         Set checkPendingDbSet = new HashSet ();
372
373         /* Use local caching to reduce DbTree.getDb overhead. */
374         Map dbCache = new HashMap ();
375
376         try {
377             /* Create the file reader. */
378             CleanerFileReader reader = new CleanerFileReader
379                 (env, readBufferSize, DbLsn.NULL_LSN, fileNum);
380             /* Validate all entries before ever deleting a file. */
381             reader.setAlwaysValidateChecksum(true);
382
383             DbTree dbMapTree = env.getDbMapTree();
384             TreeLocation location = new TreeLocation();
385
386             int nProcessedLNs = 0;
387             while (reader.readNextEntry()) {
388                 cleaner.nEntriesRead += 1;
389                 long logLsn = reader.getLastLsn();
390                 long fileOffset = DbLsn.getFileOffset(logLsn);
391                 boolean isLN = reader.isLN();
392                 boolean isIN = reader.isIN();
393                 boolean isRoot = reader.isRoot();
394                 boolean isFileHeader = reader.isFileHeader();
395                 boolean isObsolete = false;
396
397                 if (reader.isFileHeader()) {
398                     fileLogVersion = reader.getFileHeader().getLogVersion();
399                 }
400
401                 /* Stop if the daemon is shut down. */
402                 if (env.isClosing()) {
403                     return false;
404                 }
405
406                 /* Update background reads. */
407                 int nReads = reader.getAndResetNReads();
408                 if (nReads > 0) {
409                     env.updateBackgroundReads(nReads);
410                 }
411
412                 /* Sleep if background read/write limit was exceeded. */
413                 env.sleepAfterBackgroundIO();
414
415                 /* Check for a known obsolete node. */
416                 while (nextObsolete < fileOffset && obsoleteIter.hasNext()) {
417                     nextObsolete = obsoleteIter.next();
418                 }
419                 if (nextObsolete == fileOffset) {
420                     isObsolete = true;
421                 }
422                 
423                 /* Check for the entry type next because it is very cheap. */
424                 if (!isObsolete &&
425                     !isLN &&
426                     !isIN &&
427                     !isRoot) {
428                     /* Consider all entries we do not process as obsolete. */
429                     isObsolete = true;
430                 }
431
432                 /*
433                  * SR 14583: In JE 2.0 and later we can assume that all
434                  * deleted LNs are obsolete. Either the delete committed and
435                  * the BIN parent is marked with a pending deleted bit, or the
436                  * delete rolled back, in which case there is no reference
437                  * to this entry. JE 1.7.1 and earlier require a tree lookup
438                  * because deleted LNs may still be reachable through their BIN
439                  * parents.
440                  */
441                 if (!isObsolete &&
442                     isLN &&
443                     reader.getLN().isDeleted() &&
444                     fileLogVersion > 2) {
445                     /* Deleted LNs are always obsolete. */
446                     isObsolete = true;
447                 }
448
449                 /* Check the current tracker last, as it is more expensive. */
450                 if (!isObsolete &&
451                     tfs != null &&
452                     tfs.containsObsoleteOffset(fileOffset)) {
453                     isObsolete = true;
454                 }
455
456                 /* Skip known obsolete nodes. */
457                 if (isObsolete) {
458                     /* Count obsolete stats. */
459                     if (isLN) {
460                         nLNsObsoleteThisRun++;
461                     } else if (isIN) {
462                         nINsObsoleteThisRun++;
463                     }
464                     /* Must update the pending DB set for obsolete entries. */
465                     DatabaseId dbId = reader.getDatabaseId();
466                     if (dbId != null) {
467                         checkPendingDbSet.add(dbId);
468                     }
469                     continue;
470                 }
471
472                 /* Evict before processing each entry. */
473                 if (Cleaner.DO_CRITICAL_EVICTION) {
474                     env.getEvictor().doCriticalEviction(true); // backgroundIO
475 }
476
477                 /* The entry is not known to be obsolete -- process it now. */
478                 if (isLN) {
479
480                     LN targetLN = reader.getLN();
481                     DatabaseId dbId = reader.getDatabaseId();
482                     byte[] key = reader.getKey();
483                     byte[] dupKey = reader.getDupTreeKey();
484
485                     lookAheadCache.add
486                         (new Long (DbLsn.getFileOffset(logLsn)),
487                          new LNInfo(targetLN, dbId, key, dupKey));
488
489                     if (lookAheadCache.isFull()) {
490                         processLN(fileNum, location, lookAheadCache,
491                                   dbCache, deferredWriteDbs);
492                     }
493
494                     /*
495                      * Process pending LNs before proceeding in order to
496                      * prevent the pending list from growing too large.
497                      */
498                     nProcessedLNs += 1;
499                     if (nProcessedLNs % PROCESS_PENDING_EVERY_N_LNS == 0) {
500                         cleaner.processPending();
501                     }
502
503                 } else if (isIN) {
504
505                     IN targetIN = reader.getIN();
506                     DatabaseId dbId = reader.getDatabaseId();
507                     DatabaseImpl db = dbMapTree.getDb
508                         (dbId, cleaner.lockTimeout, dbCache);
509                     targetIN.setDatabase(db);
510                     
511                     processIN(targetIN, db, logLsn, deferredWriteDbs);
512                     
513                 } else if (isRoot) {
514                     
515                     env.rewriteMapTreeRoot(logLsn);
516                 } else {
517                     assert false;
518                 }
519             }
520
521             /* Process remaining queued LNs. */
522             while (!lookAheadCache.isEmpty()) {
523                 if (Cleaner.DO_CRITICAL_EVICTION) {
524                     env.getEvictor().doCriticalEviction(true); // backgroundIO
525 }
526                 processLN(fileNum, location, lookAheadCache, dbCache,
527                           deferredWriteDbs);
528                 /* Sleep if background read/write limit was exceeded. */
529                 env.sleepAfterBackgroundIO();
530             }
531
532             /* Update the pending DB set. */
533             for (Iterator i = checkPendingDbSet.iterator(); i.hasNext();) {
534                 DatabaseId dbId = (DatabaseId) i.next();
535                 DatabaseImpl db = dbMapTree.getDb
536                     (dbId, cleaner.lockTimeout, dbCache);
537                 cleaner.addPendingDB(db);
538             }
539
540             /* Update reader stats. */
541             nEntriesReadThisRun = reader.getNumRead();
542             nRepeatIteratorReadsThisRun = reader.getNRepeatIteratorReads();
543
544         } finally {
545             /* Subtract the overhead of this method from the budget. */
546             budget.updateMiscMemoryUsage(0 - adjustMem);
547
548             /* Allow flushing of TFS when cleaning is complete. */
549             if (tfs != null) {
550                 tfs.setAllowFlush(true);
551             }
552         }
553
554         return true;
555     }
556
557     /**
558      * Processes the first LN in the look ahead cache and removes it from the
559      * cache. While the BIN is latched, look through the BIN for other LNs in
560      * the cache; if any match, process them to avoid a tree search later.
561      */
562     private void processLN(Long fileNum,
563                            TreeLocation location,
564                            LookAheadCache lookAheadCache,
565                            Map dbCache,
566                            Set deferredWriteDbs)
567         throws DatabaseException {
568
569         nLNsCleanedThisRun++;
570
571         /* Get the first LN from the queue. */
572         Long offset = lookAheadCache.nextOffset();
573         LNInfo info = lookAheadCache.remove(offset);
574
575         LN ln = info.getLN();
576         byte[] key = info.getKey();
577         byte[] dupKey = info.getDupKey();
578
579         long logLsn = DbLsn.makeLsn
580             (fileNum.longValue(), offset.longValue());
581
582         DatabaseImpl db = env.getDbMapTree().getDb
583             (info.getDbId(), cleaner.lockTimeout, dbCache);
584
585         /* Status variables are used to generate debug tracing info. */
586         boolean processedHere = true; // The LN was cleaned here.
587 boolean obsolete = false; // The LN is no longer in use.
588 boolean completed = false; // This method completed.
589
590         BIN bin = null;
591         DIN parentDIN = null; // for DupCountLNs
592 try {
593
594             /*
595              * If the DB is gone, this LN is obsolete. If delete cleanup is in
596              * progress, put the DB into the DB pending set; this LN will be
597              * declared deleted after the delete cleanup is finished.
598              */
599             if (db == null || db.isDeleted()) {
600                 cleaner.addPendingDB(db);
601                 nLNsDeadThisRun++;
602                 obsolete = true;
603                 completed = true;
604                 return;
605             }
606
607             Tree tree = db.getTree();
608             assert tree != null;
609
610             /*
611          * Search down to the bottom most level for the parent of this LN.
612          */
613             boolean parentFound = tree.getParentBINForChildLN
614                 (location, key, dupKey, ln,
615                  false, // splitsAllowed
616 true, // findDeletedEntries
617 false, // searchDupTree
618 Cleaner.UPDATE_GENERATION);
619             bin = location.bin;
620             int index = location.index;
621
622             if (!parentFound) {
623                 nLNsDeadThisRun++;
624         obsolete = true;
625                 completed = true;
626         return;
627             }
628
629             /*
630          * Now we're at the parent for this LN, whether BIN, DBIN or DIN.
631          * If knownDeleted, LN is deleted and can be purged.
632          */
633         if (bin.isEntryKnownDeleted(index)) {
634         nLNsDeadThisRun++;
635         obsolete = true;
636         completed = true;
637                 return;
638         }
639
640             /*
641              * Determine whether the parent is the current BIN, or in the case
642              * of a DupCountLN, a DIN. Get the tree LSN in either case.
643              */
644             boolean isDupCountLN = ln.containsDuplicates();
645             long treeLsn;
646         if (isDupCountLN) {
647         parentDIN = (DIN) bin.fetchTarget(index);
648         parentDIN.latch(Cleaner.UPDATE_GENERATION);
649                 ChildReference dclRef = parentDIN.getDupCountLNRef();
650                 treeLsn = dclRef.getLsn();
651         } else {
652                 treeLsn = bin.getLsn(index);
653         }
654
655             /* Process this LN that was found in the tree. */
656             processedHere = false;
657             processFoundLN(info, logLsn, treeLsn, bin, index, parentDIN);
658             completed = true;
659
660             /*
661              * For all other non-deleted LNs in this BIN, lookup their LSN
662              * in the LN queue and process any matches.
663              */
664             if (!isDupCountLN) {
665                 for (int i = 0; i < bin.getNEntries(); i += 1) {
666                     long binLsn = bin.getLsn(i);
667                     if (i != index &&
668                         !bin.isEntryKnownDeleted(i) &&
669                         !bin.isEntryPendingDeleted(i) &&
670                         DbLsn.getFileNumber(binLsn) == fileNum.longValue()) {
671
672                         Long myOffset = new Long (DbLsn.getFileOffset(binLsn));
673                         LNInfo myInfo = lookAheadCache.remove(myOffset);
674
675                         if (myInfo != null) {
676                             nLNQueueHitsThisRun++;
677                             nLNsCleanedThisRun++;
678                             processFoundLN
679                                 (myInfo, binLsn, binLsn, bin, i, null);
680                         }
681                     }
682                 }
683             }
684             return;
685
686         } finally {
687             noteDbsRequiringSync(db, deferredWriteDbs);
688
689             if (parentDIN != null) {
690                 parentDIN.releaseLatchIfOwner();
691             }
692
693             if (bin != null) {
694                 bin.releaseLatchIfOwner();
695             }
696
697             if (processedHere) {
698                 cleaner.trace
699                     (cleaner.detailedTraceLevel, Cleaner.CLEAN_LN, ln, logLsn,
700                      completed, obsolete, false /*migrated*/);
701             }
702         }
703     }
704
705     /**
706      * Processes an LN that was found in the tree. Lock the LN's node ID and
707      * then set the entry's MIGRATE flag if the LSN of the LN log entry is the
708      * active LSN in the tree.
709      *
710      * @param info identifies the LN log entry.
711      *
712      * @param logLsn is the LSN of the log entry.
713      *
714      * @param treeLsn is the LSN found in the tree.
715      *
716      * @param bin is the BIN found in the tree; is latched on method entry and
717      * exit.
718      *
719      * @param index is the BIN index found in the tree.
720      *
721      * @param parentDIN is non-null for a DupCountLN only; if non-null, is
722      * latched on method entry and exit.
723      */
724     private void processFoundLN(LNInfo info,
725                                 long logLsn,
726                                 long treeLsn,
727                                 BIN bin,
728                                 int index,
729                                 DIN parentDIN)
730         throws DatabaseException {
731
732         LN ln = info.getLN();
733         byte[] key = info.getKey();
734         byte[] dupKey = info.getDupKey();
735
736         DatabaseImpl db = bin.getDatabase();
737         boolean isDupCountLN = parentDIN != null;
738
739         /* Status variables are used to generate debug tracing info. */
740         boolean obsolete = false; // The LN is no longer in use.
741 boolean migrated = false; // The LN was in use and is migrated.
742 boolean lockDenied = false;// The LN lock was denied.
743 boolean completed = false; // This method completed.
744
745         long nodeId = ln.getNodeId();
746         BasicLocker locker = null;
747         try {
748             Tree tree = db.getTree();
749             assert tree != null;
750
751             /*
752              * If the tree and log LSNs are equal, then we can be fairly
753              * certain that the log entry is current; in that case, it is
754              * wasteful to lock the LN here -- it is better to lock only once
755              * during lazy migration. But if the tree and log LSNs differ, it
756              * is likely that another thread has updated or deleted the LN and
757              * the log LSN is now obsolete; in this case we can avoid dirtying
758              * the BIN by checking for obsoleteness here, which requires
759              * locking. The latter case can occur frequently if trackDetail is
760              * false.
761              *
762              * 1. If the LSN in the tree and in the log are the same, we will
763              * attempt to migrate it.
764              *
765              * 2. If the LSN in the tree is < the LSN in the log, the log entry
766              * is obsolete, because this LN has been rolled back to a previous
767              * version by a txn that aborted.
768              *
769              * 3. If the LSN in the tree is > the LSN in the log, the log entry
770              * is obsolete, because the LN was advanced forward by some
771              * now-committed txn.
772              *
773              * 4. If the LSN in the tree is a null LSN, the log entry is
774              * obsolete. A slot can only have a null LSN if the record has
775              * never been written to disk in a deferred write database, and
776              * in that case the log entry must be for a past, deleted version
777              * of that record.
778              */
779             if (ln.isDeleted() &&
780                 (treeLsn == logLsn) &&
781                 fileLogVersion <= 2) {
782
783                 /*
784                  * SR 14583: After JE 2.0, deleted LNs are never found in the
785                  * tree, since we can assume they're obsolete and correctly
786                  * marked as such in the obsolete offset tracking. JE 1.7.1 and
787                  * earlier did not use the pending deleted bit, so deleted LNs
788                  * may still be reachable through their BIN parents.
789                  */
790                 obsolete = true;
791                 nLNsDeadThisRun++;
792                 bin.setPendingDeleted(index);
793             } else if (treeLsn == DbLsn.NULL_LSN) {
794
795                 /*
796                  * Case 4: The LN in the tree is a never-written LN for a
797                  * deferred-write db, so the LN in the file is obsolete.
798                  */
799                 obsolete = true;
800             } else if (treeLsn != logLsn) {
801
802                 /*
803                  * Check to see whether the LN being migrated is locked
804                  * elsewhere. Do that by attempting to lock it. We can hold
805                  * the latch on the BIN (and DIN) since we always attempt to
806                  * acquire a non-blocking read lock. Holding the latch ensures
807                  * that the INs won't change underneath us because of splits or
808                  * eviction.
809                  */
810                 locker = new BasicLocker(env);
811                 LockResult lockRet = locker.nonBlockingLock
812                     (nodeId, LockType.READ, db);
813                 if (lockRet.getLockGrant() == LockGrantType.DENIED) {
814
815                     /*
816                      * LN is currently locked by another Locker, so we can't
817                      * assume anything about the value of the LSN in the bin.
818                      */
819                     nLNsLockedThisRun++;
820                     lockDenied = true;
821                 } else {
822                     /* The LN is obsolete and can be purged. */
823                     nLNsDeadThisRun++;
824                     obsolete = true;
825                 }
826             }
827
828             if (!obsolete && !lockDenied) {
829
830                 /*
831                  * Set the migrate flag and dirty the parent IN. The evictor
832                  * or checkpointer will migrate the LN later.
833                  *
834                  * Then set the target node so it does not have to be fetched
835                  * when it is migrated, if the tree and log LSNs are equal and
836                  * the target is not resident. We must call postFetchInit to
837                  * initialize MapLNs that have not been fully initialized yet
838                  * [#13191].
839                  */
840                 if (isDupCountLN) {
841                     ChildReference dclRef = parentDIN.getDupCountLNRef();
842                     dclRef.setMigrate(true);
843                     parentDIN.setDirty(true);
844
845                     if (treeLsn == logLsn && dclRef.getTarget() == null) {
846                         ln.postFetchInit(db, logLsn);
847                         parentDIN.updateDupCountLN(ln);
848                     }
849                 } else {
850                     bin.setMigrate(index, true);
851                     bin.setDirty(true);
852
853                     if (treeLsn == logLsn && bin.getTarget(index) == null) {
854                         ln.postFetchInit(db, logLsn);
855                         bin.updateEntry(index, ln);
856                     }
857
858                     /*
859                      * If the generation is zero, we fetched this BIN just for
860                      * cleaning.
861                      */
862                     if (PROHIBIT_DELTAS_WHEN_FETCHING &&
863                         bin.getGeneration() == 0) {
864                         bin.setProhibitNextDelta();
865                     }
866
867                     /*
868                      * Update the generation so that the BIN is not evicted
869                      * immediately. This allows the cleaner to fill in as many
870                      * entries as possible before eviction, as to-be-cleaned
871                      * files are processed.
872                      */
873                     bin.setGeneration();
874                 }
875
876                 nLNsMarkedThisRun++;
877                 migrated = true;
878             }
879             completed = true;
880         } finally {
881             if (locker != null) {
882                 locker.operationEnd();
883             }
884
885             /*
886              * If a write lock is held, it is likely that the log LSN will
887              * become obsolete. It is more efficient to process this via the
888              * pending list than to set the MIGRATE flag, dirty the BIN, and
889              * cause the BIN to be logged unnecessarily.
890              */
891             if (completed && lockDenied) {
892                 fileSelector.addPendingLN(ln, db.getId(), key, dupKey);
893             }
894
895             cleaner.trace
896                 (cleaner.detailedTraceLevel, Cleaner.CLEAN_LN, ln, logLsn,
897                  completed, obsolete, migrated);
898         }
899     }
900
901     /**
902      * If an IN is still in use in the in-memory tree, dirty it. The checkpoint
903      * invoked at the end of the cleaning run will end up rewriting it.
904      */
905     private void processIN(IN inClone,
906                            DatabaseImpl db,
907                            long logLsn,
908                            Set deferredWriteDbs)
909         throws DatabaseException {
910
911         boolean obsolete = false;
912         boolean dirtied = false;
913         boolean completed = false;
914
915         try {
916             nINsCleanedThisRun++;
917
918             /*
919              * If the DB is gone, this LN is obsolete. If delete cleanup is in
920              * progress, put the DB into the DB pending set; this LN will be
921              * declared deleted after the delete cleanup is finished.
922              */
923             if (db == null || db.isDeleted()) {
924                 cleaner.addPendingDB(db);
925                 nINsDeadThisRun++;
926                 obsolete = true;
927                 completed = true;
928                 return;
929             }
930
931             Tree tree = db.getTree();
932             assert tree != null;
933
934             IN inInTree = findINInTree(tree, db, inClone, logLsn);
935
936             if (inInTree == null) {
937                 /* IN is no longer in the tree. Do nothing. */
938                 nINsDeadThisRun++;
939                 obsolete = true;
940             } else {
941
942                 /*
943                  * IN is still in the tree. Dirty it. Checkpoint or eviction
944                  * will write it out. Prohibit the next delta, since the
945                  * original version must be made obsolete.
946                  */
947                 nINsMigratedThisRun++;
948                 inInTree.setDirty(true);
949                 inInTree.setProhibitNextDelta();
950                 inInTree.releaseLatch();
951                 dirtied = true;
952             }
953             
954             completed = true;
955         } finally {
956             noteDbsRequiringSync(db, deferredWriteDbs);
957
958             cleaner.trace
959                 (cleaner.detailedTraceLevel, Cleaner.CLEAN_IN, inClone, logLsn,
960                  completed, obsolete, dirtied);
961         }
962     }
963
964     /**
965      * Given a clone of an IN that has been taken out of the log, try to find
966      * it in the tree and verify that it is the current one in the log.
967      * Returns the node in the tree if it is found and it is current re: LSN's.
968      * Otherwise returns null if the clone is not found in the tree or it's not
969      * the latest version. Caller is responsible for unlatching the returned
970      * IN.
971      */
972     private IN findINInTree(Tree tree,
973                             DatabaseImpl db,
974                             IN inClone,
975                             long logLsn)
976         throws DatabaseException {
977
978         /* Check if inClone is the root. */
979         if (inClone.isDbRoot()) {
980             IN rootIN = isRoot(tree, db, inClone, logLsn);
981             if (rootIN == null) {
982
983                 /*
984                  * inClone is a root, but no longer in use. Return now, because
985                  * a call to tree.getParentNode will return something
986                  * unexpected since it will try to find a parent.
987                  */
988                 return null;
989             } else {
990                 return rootIN;
991             }
992         }
993
994         /* It's not the root. Can we find it, and if so, is it current? */
995         inClone.latch(Cleaner.UPDATE_GENERATION);
996         SearchResult result = null;
997         try {
998
999             result = tree.getParentINForChildIN
1000                (inClone,
1001                 true, // requireExactMatch
1002 Cleaner.UPDATE_GENERATION,
1003                 inClone.getLevel(),
1004                 null); // trackingList
1005
1006            if (!result.exactParentFound) {
1007                return null;
1008            }
1009        
1010            long treeLsn = result.parent.getLsn(result.index);
1011
1012            /*
1013             * Any entry that is in the log should not have a NULL_LSN in the
1014             * in-memory tree, even for a deferred write database. The
1015             * in-memory tree should always have a lsn that shows the last
1016             * on-disk version.
1017             */
1018            if (treeLsn == DbLsn.NULL_LSN) {
1019                throw new DatabaseException
1020                    ("Deferred Write IN should not have a NULL_LSN " +
1021                     " logLsn=" + DbLsn.getNoFormatString(logLsn));
1022            }
1023 
1024            int compareVal = DbLsn.compareTo(treeLsn, logLsn);
1025            
1026            if (compareVal > 0) {
1027                /* Log entry is obsolete. */
1028                return null;
1029            } else {
1030
1031                /*
1032                 * Log entry is same or newer than what's in the tree. Dirty
1033                 * the IN and let checkpoint write it out.
1034                 */
1035                IN in;
1036                if (compareVal == 0) {
1037                    /* We can reuse the log entry if the LSNs are equal. */
1038                    in = (IN) result.parent.getTarget(result.index);
1039                    if (in == null) {
1040                        in = inClone;
1041                        in.postFetchInit(db, logLsn);
1042                        result.parent.updateEntry(result.index, in);
1043                    }
1044                } else {
1045                    in = (IN) result.parent.fetchTarget(result.index);
1046                }
1047                in.latch(Cleaner.UPDATE_GENERATION);
1048                return in;
1049            }
1050        } finally {
1051            if ((result != null) && (result.exactParentFound)) {
1052                result.parent.releaseLatch();
1053            }
1054        }
1055    }
1056
1057    /*
1058     * When we process a target log entry for a deferred write db, we may
1059     * need to sync the db at the next checkpoint.
1060     * Cases are:
1061     * IN found in the tree:
1062     * The IN is dirtied and must be written out at the next ckpt.
1063     * IN not found in the tree:
1064     * This log entry is not in use by the in-memory tree, but a later
1065     * recovery has the possibility of reverting to the last synced
1066     * version. To prevent that, we have to sync the database before
1067     * deleting the file.
1068     * LN found in tree:
1069     * It will be migrated, need to be synced.
1070     * LN not found in tree:
1071     * Like not-found IN, need to be sure that the database is
1072     * sufficiently synced.
1073     * Note that if nothing in the db is actually dirty (LN and IN are not
1074     * found) there's no harm done, there will be no sync and no extra
1075     * processing.
1076     */
1077    private void noteDbsRequiringSync(DatabaseImpl db,
1078                                          Set deferredWriteDbs) {
1079        if ((db != null) && (!db.isDeleted()) && db.isDeferredWrite()) {
1080            deferredWriteDbs.add(db.getId());
1081        }
1082    }
1083
1084    /**
1085     * Get the current root in the tree, or null if the inClone
1086     * is the current root.
1087     */
1088    private static class RootDoWork implements WithRootLatched {
1089        private DatabaseImpl db;
1090        private IN inClone;
1091        private long logLsn;
1092
1093        RootDoWork(DatabaseImpl db, IN inClone, long logLsn) {
1094            this.db = db;
1095            this.inClone = inClone;
1096            this.logLsn = logLsn;
1097        }
1098
1099        public IN doWork(ChildReference root)
1100            throws DatabaseException {
1101
1102            if (root == null ||
1103                (root.getLsn() == DbLsn.NULL_LSN) || // deferred write root
1104 (root.fetchTarget(db, null).getNodeId() !=
1105                 inClone.getNodeId())) {
1106                return null;
1107            }
1108
1109            /* bozo, how can the root's lsn be less that the logLsn?
1110               This may have been an artifact of when we didn't properly
1111               propagate the logging of the rootIN up to the root
1112               ChildReference. Remove? */
1113            if (DbLsn.compareTo(root.getLsn(), logLsn) <= 0) {
1114                IN rootIN = (IN) root.fetchTarget(db, null);
1115                rootIN.latch(Cleaner.UPDATE_GENERATION);
1116                return rootIN;
1117            } else {
1118                return null;
1119            }
1120        }
1121    }
1122
1123    /**
1124     * Check if the cloned IN is the same node as the root in tree. Return the
1125     * real root if it is, null otherwise. If non-null is returned, the
1126     * returned IN (the root) is latched -- caller is responsible for
1127     * unlatching it.
1128     */
1129    private IN isRoot(Tree tree, DatabaseImpl db, IN inClone, long lsn)
1130        throws DatabaseException {
1131
1132        RootDoWork rdw = new RootDoWork(db, inClone, lsn);
1133        return tree.withRootLatchedShared(rdw);
1134    }
1135
1136    /**
1137     * Reset per-run counters.
1138     */
1139    private void resetPerRunCounters() {
1140        nINsObsoleteThisRun = 0;
1141        nINsCleanedThisRun = 0;
1142        nINsDeadThisRun = 0;
1143        nINsMigratedThisRun = 0;
1144        nLNsObsoleteThisRun = 0;
1145        nLNsCleanedThisRun = 0;
1146        nLNsDeadThisRun = 0;
1147        nLNsMigratedThisRun = 0;
1148        nLNsMarkedThisRun = 0;
1149        nLNQueueHitsThisRun = 0;
1150        nLNsLockedThisRun = 0;
1151        nEntriesReadThisRun = 0;
1152        nRepeatIteratorReadsThisRun = 0;
1153    }
1154
1155    /**
1156     * Add per-run counters to total counters.
1157     */
1158    private void accumulatePerRunCounters() {
1159        cleaner.nINsObsolete += nINsObsoleteThisRun;
1160        cleaner.nINsCleaned += nINsCleanedThisRun;
1161        cleaner.nINsDead += nINsDeadThisRun;
1162        cleaner.nINsMigrated += nINsMigratedThisRun;
1163        cleaner.nLNsObsolete += nLNsObsoleteThisRun;
1164        cleaner.nLNsCleaned += nLNsCleanedThisRun;
1165        cleaner.nLNsDead += nLNsDeadThisRun;
1166        cleaner.nLNsMigrated += nLNsMigratedThisRun;
1167        cleaner.nLNsMarked += nLNsMarkedThisRun;
1168        cleaner.nLNQueueHits += nLNQueueHitsThisRun;
1169        cleaner.nLNsLocked += nLNsLockedThisRun;
1170        cleaner.nRepeatIteratorReads += nRepeatIteratorReadsThisRun;
1171    }
1172
1173    /**
1174     * XXX: Was this intended to override Thread.toString()? If so it no
1175     * longer does, because we separated Thread from DaemonThread.
1176     */
1177    public String toString() {
1178        StringBuffer sb = new StringBuffer ();
1179        sb.append("<Cleaner name=\"").append(name).append("\"/>");
1180        return sb.toString();
1181    }
1182
1183    /**
1184     * A cache of LNInfo by LSN offset. Used to hold a set of LNs that are
1185     * to be processed. Keeps track of memory used, and when full (over
1186     * budget) the next offset should be queried and removed.
1187     */
1188    private static class LookAheadCache {
1189
1190        private SortedMap map;
1191        private int maxMem;
1192        private int usedMem;
1193
1194        LookAheadCache(int lookAheadCacheSize) {
1195            map = new TreeMap ();
1196            maxMem = lookAheadCacheSize;
1197            usedMem = MemoryBudget.TREEMAP_OVERHEAD;
1198        }
1199
1200        boolean isEmpty() {
1201            return map.isEmpty();
1202        }
1203
1204        boolean isFull() {
1205            return usedMem >= maxMem;
1206        }
1207
1208        Long nextOffset() {
1209            return (Long ) map.firstKey();
1210        }
1211
1212        void add(Long lsnOffset, LNInfo info) {
1213            map.put(lsnOffset, info);
1214            usedMem += info.getMemorySize();
1215            usedMem += MemoryBudget.TREEMAP_ENTRY_OVERHEAD;
1216        }
1217
1218        LNInfo remove(Long offset) {
1219            LNInfo info = (LNInfo) map.remove(offset);
1220            if (info != null) {
1221                usedMem -= info.getMemorySize();
1222                usedMem -= MemoryBudget.TREEMAP_ENTRY_OVERHEAD;
1223            }
1224            return info;
1225        }
1226    }
1227}
1228

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags