001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *
024 *      Copyright 2006-2010 Sun Microsystems, Inc.
025 *      Portions Copyright 2011-2015 ForgeRock AS
026 */
027package org.opends.server.backends.jeb;
028
029import static org.opends.messages.BackendMessages.*;
030
031import java.util.*;
032import java.util.concurrent.atomic.AtomicBoolean;
033
034import org.forgerock.i18n.LocalizableMessage;
035import org.forgerock.i18n.slf4j.LocalizedLogger;
036import org.forgerock.opendj.ldap.ByteString;
037import org.forgerock.opendj.ldap.ConditionResult;
038import org.forgerock.opendj.ldap.DecodeException;
039import org.forgerock.opendj.ldap.ResultCode;
040import org.forgerock.opendj.ldap.schema.MatchingRule;
041import org.opends.server.backends.VerifyConfig;
042import org.opends.server.core.DirectoryServer;
043import org.opends.server.types.*;
044import org.opends.server.util.ServerConstants;
045import org.opends.server.util.StaticUtils;
046
047import com.sleepycat.je.*;
048
049/** This class is used to run an index verification process on the backend. */
050public class VerifyJob
051{
052  private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();
053
054  /** The verify configuration. */
055  private final VerifyConfig verifyConfig;
056  /** The root container used for the verify job. */
057  private RootContainer rootContainer;
058
059  /** The number of milliseconds between job progress reports. */
060  private final long progressInterval = 10000;
061  /** The number of index keys processed. */
062  private long keyCount;
063  /** The number of errors found. */
064  private long errorCount;
065  /** The number of records that have exceeded the entry limit. */
066  private long entryLimitExceededCount;
067  /** The number of records that reference more than one entry. */
068  private long multiReferenceCount;
069  /** The total number of entry references. */
070  private long entryReferencesCount;
071  /** The maximum number of references per record. */
072  private long maxEntryPerValue;
073
074  /**
075   * This map is used to gather some statistics about values that have
076   * exceeded the entry limit.
077   */
078  private IdentityHashMap<Index, HashMap<ByteString, Long>> entryLimitMap = new IdentityHashMap<>();
079
080  /** Indicates whether the DN database is to be verified. */
081  private boolean verifyDN2ID;
082  /** Indicates whether the children database is to be verified. */
083  private boolean verifyID2Children;
084  /** Indicates whether the subtree database is to be verified. */
085  private boolean verifyID2Subtree;
086
087  /** The entry database. */
088  private ID2Entry id2entry;
089  /** The DN database. */
090  private DN2ID dn2id;
091  /** The children database. */
092  private Index id2c;
093  /** The subtree database. */
094  private Index id2s;
095
096  /** A list of the attribute indexes to be verified. */
097  private final ArrayList<AttributeIndex> attrIndexList = new ArrayList<>();
098  /** A list of the VLV indexes to be verified. */
099  private final ArrayList<VLVIndex> vlvIndexList = new ArrayList<>();
100
101  /**
102   * Construct a VerifyJob.
103   *
104   * @param verifyConfig The verify configuration.
105   */
106  public VerifyJob(VerifyConfig verifyConfig)
107  {
108    this.verifyConfig = verifyConfig;
109  }
110
111  /**
112   * Verify the backend.
113   *
114   * @param rootContainer The root container that holds the entries to verify.
115   * @return The error count.
116   * @throws DatabaseException If an error occurs in the JE database.
117   * @throws JebException If an error occurs in the JE backend.
118   * @throws DirectoryException If an error occurs while verifying the backend.
119   */
120  public long verifyBackend(RootContainer rootContainer) throws DatabaseException, JebException, DirectoryException
121  {
122    this.rootContainer = rootContainer;
123    EntryContainer entryContainer =
124        rootContainer.getEntryContainer(verifyConfig.getBaseDN());
125
126    entryContainer.sharedLock.lock();
127    try
128    {
129      final List<String> completeList = verifyConfig.getCompleteList();
130      final List<String> cleanList = verifyConfig.getCleanList();
131
132      boolean cleanMode = false;
133      if (completeList.isEmpty() && cleanList.isEmpty())
134      {
135        verifyDN2ID = true;
136        if (rootContainer.getConfiguration().isSubordinateIndexesEnabled())
137        {
138          verifyID2Children = true;
139          verifyID2Subtree = true;
140        }
141        for (AttributeIndex index : entryContainer.getAttributeIndexes())
142        {
143          if (index.isTrusted())
144          {
145            attrIndexList.add(index);
146          }
147        }
148      }
149      else
150      {
151        final List<String> list;
152        if (!completeList.isEmpty())
153        {
154          list = completeList;
155        }
156        else
157        {
158          list = cleanList;
159          cleanMode = true;
160        }
161
162        for (String index : list)
163        {
164          String lowerName = index.toLowerCase();
165          if ("dn2id".equals(lowerName))
166          {
167            verifyDN2ID = true;
168          }
169          else if ("id2children".equals(lowerName))
170          {
171            if (rootContainer.getConfiguration().isSubordinateIndexesEnabled())
172            {
173              verifyID2Children = true;
174            }
175            else
176            {
177              LocalizableMessage msg = NOTE_JEB_SUBORDINATE_INDEXES_DISABLED
178                  .get(rootContainer.getConfiguration().getBackendId());
179              throw new JebException(msg);
180            }
181          }
182          else if ("id2subtree".equals(lowerName))
183          {
184            if (rootContainer.getConfiguration().isSubordinateIndexesEnabled())
185            {
186              verifyID2Subtree = true;
187            }
188            else
189            {
190              LocalizableMessage msg = NOTE_JEB_SUBORDINATE_INDEXES_DISABLED
191                  .get(rootContainer.getConfiguration().getBackendId());
192              throw new JebException(msg);
193            }
194          }
195          else if(lowerName.startsWith("vlv."))
196          {
197            if(lowerName.length() < 5)
198            {
199              throw new JebException(ERR_VLV_INDEX_NOT_CONFIGURED.get(lowerName));
200            }
201
202            VLVIndex vlvIndex =
203                entryContainer.getVLVIndex(lowerName.substring(4));
204            if(vlvIndex == null)
205            {
206              throw new JebException(ERR_VLV_INDEX_NOT_CONFIGURED.get(lowerName.substring(4)));
207            }
208
209            vlvIndexList.add(vlvIndex);
210          }
211          else
212          {
213            AttributeType attrType = DirectoryServer.getAttributeType(lowerName);
214            if (attrType == null)
215            {
216              throw new JebException(ERR_ATTRIBUTE_INDEX_NOT_CONFIGURED.get(index));
217            }
218            AttributeIndex attrIndex = entryContainer.getAttributeIndex(attrType);
219            if (attrIndex == null)
220            {
221              throw new JebException(ERR_ATTRIBUTE_INDEX_NOT_CONFIGURED.get(index));
222            }
223            attrIndexList.add(attrIndex);
224          }
225        }
226      }
227
228      entryLimitMap = new IdentityHashMap<>(attrIndexList.size());
229
230      // We will be updating these files independently of the indexes
231      // so we need direct access to them rather than going through
232      // the entry entryContainer methods.
233      id2entry = entryContainer.getID2Entry();
234      dn2id = entryContainer.getDN2ID();
235      id2c = entryContainer.getID2Children();
236      id2s = entryContainer.getID2Subtree();
237
238      // Make a note of the time we started.
239      long startTime = System.currentTimeMillis();
240
241      // Start a timer for the progress report.
242      Timer timer = new Timer();
243      // Create a new progressTask based on the index count.
244      TimerTask progressTask = new ProgressTask(cleanMode);
245      timer.scheduleAtFixedRate(progressTask, progressInterval, progressInterval);
246
247      // Iterate through the index keys.
248      try
249      {
250        if (cleanMode)
251        {
252          iterateIndex();
253        }
254        else
255        {
256          iterateID2Entry();
257
258          // Make sure the vlv indexes are in correct order.
259          for(VLVIndex vlvIndex : vlvIndexList)
260          {
261            iterateVLVIndex(vlvIndex, false);
262          }
263        }
264      }
265      finally
266      {
267        timer.cancel();
268      }
269
270      long finishTime = System.currentTimeMillis();
271      long totalTime = finishTime - startTime;
272
273      float rate = 0;
274      if (totalTime > 0)
275      {
276        rate = 1000f*keyCount / totalTime;
277      }
278
279      if (cleanMode)
280      {
281        logger.info(NOTE_VERIFY_CLEAN_FINAL_STATUS, keyCount, errorCount, totalTime / 1000, rate);
282
283        if (multiReferenceCount > 0)
284        {
285          float averageEntryReferences = 0;
286          if (keyCount > 0)
287          {
288            averageEntryReferences = entryReferencesCount/keyCount;
289          }
290
291          if (logger.isDebugEnabled())
292          {
293            logger.debug(INFO_VERIFY_MULTIPLE_REFERENCE_COUNT, multiReferenceCount);
294            logger.debug(INFO_VERIFY_ENTRY_LIMIT_EXCEEDED_COUNT, entryLimitExceededCount);
295            logger.debug(INFO_VERIFY_AVERAGE_REFERENCE_COUNT, averageEntryReferences);
296            logger.debug(INFO_VERIFY_MAX_REFERENCE_COUNT, maxEntryPerValue);
297          }
298        }
299      }
300      else
301      {
302        logger.info(NOTE_VERIFY_FINAL_STATUS, keyCount, errorCount, totalTime/1000, rate);
303        if (!entryLimitMap.isEmpty())
304        {
305          logger.debug(INFO_VERIFY_ENTRY_LIMIT_STATS_HEADER);
306
307          for (Map.Entry<Index,HashMap<ByteString,Long>> mapEntry :
308              entryLimitMap.entrySet())
309          {
310            Index index = mapEntry.getKey();
311            Long[] values = mapEntry.getValue().values().toArray(new Long[0]);
312
313            // Calculate the median value for entry limit exceeded.
314            Arrays.sort(values);
315            long medianValue;
316            int x = values.length / 2;
317            if (values.length % 2 == 0)
318            {
319              medianValue = (values[x] + values[x-1]) / 2;
320            }
321            else
322            {
323              medianValue = values[x];
324            }
325
326            logger.debug(INFO_VERIFY_ENTRY_LIMIT_STATS_ROW, index, values.length, values[0],
327                    values[values.length-1], medianValue);
328          }
329        }
330      }
331    }
332    finally
333    {
334      entryContainer.sharedLock.unlock();
335    }
336    return errorCount;
337  }
338
339  /**
340   * Iterate through the entries in id2entry to perform a check for
341   * index completeness. We check that the ID for the entry is indeed
342   * present in the indexes for the appropriate values.
343   *
344   * @throws DatabaseException If an error occurs in the JE database.
345   */
346  private void iterateID2Entry() throws DatabaseException
347  {
348    DiskOrderedCursor cursor =
349        id2entry.openCursor(new DiskOrderedCursorConfig());
350    long storedEntryCount = id2entry.getRecordCount();
351    try
352    {
353      DatabaseEntry key = new DatabaseEntry();
354      DatabaseEntry data = new DatabaseEntry();
355      while (cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
356      {
357        EntryID entryID;
358        try
359        {
360          entryID = new EntryID(key);
361        }
362        catch (Exception e)
363        {
364          errorCount++;
365          if (logger.isTraceEnabled())
366          {
367            logger.traceException(e);
368
369            logger.trace("Malformed id2entry ID %s.%n",
370                       StaticUtils.bytesToHex(key.getData()));
371          }
372          continue;
373        }
374
375        keyCount++;
376
377        Entry entry;
378        try
379        {
380          entry = ID2Entry.entryFromDatabase(
381              ByteString.wrap(data.getData()),
382              rootContainer.getCompressedSchema());
383        }
384        catch (Exception e)
385        {
386          errorCount++;
387          if (logger.isTraceEnabled())
388          {
389            logger.traceException(e);
390
391            logger.trace("Malformed id2entry record for ID %d:%n%s%n",
392                       entryID.longValue(),
393                       StaticUtils.bytesToHex(data.getData()));
394          }
395          continue;
396        }
397
398        verifyEntry(entryID, entry);
399      }
400      if (keyCount != storedEntryCount)
401      {
402        errorCount++;
403        if (logger.isTraceEnabled())
404        {
405          logger.trace("The stored entry count in id2entry (%d) does " +
406              "not agree with the actual number of entry " +
407              "records found (%d).%n", storedEntryCount, keyCount);
408        }
409      }
410    }
411    finally
412    {
413      cursor.close();
414    }
415  }
416
417  /**
418   * Iterate through the entries in an index to perform a check for
419   * index cleanliness. For each ID in the index we check that the
420   * entry it refers to does indeed contain the expected value.
421   *
422   * @throws JebException If an error occurs in the JE backend.
423   * @throws DatabaseException If an error occurs in the JE database.
424   * @throws DirectoryException If an error occurs reading values in the index.
425   */
426  private void iterateIndex()
427      throws JebException, DatabaseException, DirectoryException
428  {
429    if (verifyDN2ID)
430    {
431      iterateDN2ID();
432    }
433    else if (verifyID2Children)
434    {
435      iterateID2Children();
436    }
437    else if (verifyID2Subtree)
438    {
439      iterateID2Subtree();
440    }
441    else if (!attrIndexList.isEmpty())
442    {
443      for (Index index : attrIndexList.get(0).getAllIndexes())
444      {
445        iterateAttrIndex(index);
446      }
447    }
448    else if (!vlvIndexList.isEmpty())
449    {
450      iterateVLVIndex(vlvIndexList.get(0), true);
451    }
452  }
453
454  /**
455   * Iterate through the entries in DN2ID to perform a check for
456   * index cleanliness.
457   *
458   * @throws DatabaseException If an error occurs in the JE database.
459   */
460  private void iterateDN2ID() throws DatabaseException
461  {
462    DiskOrderedCursor cursor = dn2id.openCursor(new DiskOrderedCursorConfig());
463    try
464    {
465      DatabaseEntry key = new DatabaseEntry();
466      DatabaseEntry data = new DatabaseEntry();
467
468      while (cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
469      {
470        keyCount++;
471
472        EntryID entryID;
473        try
474        {
475          entryID = new EntryID(data);
476        }
477        catch (Exception e)
478        {
479          errorCount++;
480          if (logger.isTraceEnabled())
481          {
482            logger.traceException(e);
483
484            logger.trace("File dn2id has malformed ID for DN <%s>:%n%s%n",
485                       new String(key.getData()),
486                       StaticUtils.bytesToHex(data.getData()));
487          }
488          continue;
489        }
490
491        Entry entry;
492        try
493        {
494          entry = id2entry.get(null, entryID, LockMode.DEFAULT);
495        }
496        catch (Exception e)
497        {
498          errorCount++;
499          logger.traceException(e);
500          continue;
501        }
502
503        if (entry == null)
504        {
505          errorCount++;
506          if (logger.isTraceEnabled())
507          {
508            logger.trace("File dn2id has DN <%s> referencing unknown " +
509                "ID %d%n", new String(key.getData()), entryID.longValue());
510          }
511        }
512        else if (!Arrays.equals(JebFormat.dnToDNKey(
513            entry.getName(), verifyConfig.getBaseDN().size()), key.getData()))
514        {
515          errorCount++;
516          if (logger.isTraceEnabled())
517          {
518            logger.trace("File dn2id has DN <%s> referencing entry with wrong DN <%s>%n",
519                new String(key.getData()), entry.getName());
520          }
521        }
522      }
523    }
524    finally
525    {
526      cursor.close();
527    }
528  }
529
530  /**
531   * Iterate through the entries in ID2Children to perform a check for
532   * index cleanliness.
533   *
534   * @throws JebException If an error occurs in the JE backend.
535   * @throws DatabaseException If an error occurs in the JE database.
536   */
537  private void iterateID2Children() throws JebException, DatabaseException
538  {
539    DiskOrderedCursor cursor = id2c.openCursor(new DiskOrderedCursorConfig());
540    try
541    {
542      DatabaseEntry key = new DatabaseEntry();
543      DatabaseEntry data = new DatabaseEntry();
544
545      while (cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
546      {
547        keyCount++;
548
549        EntryID entryID;
550        try
551        {
552          entryID = new EntryID(key);
553        }
554        catch (Exception e)
555        {
556          errorCount++;
557          if (logger.isTraceEnabled())
558          {
559            logger.traceException(e);
560
561            logger.trace("File id2children has malformed ID %s%n",
562                       StaticUtils.bytesToHex(key.getData()));
563          }
564          continue;
565        }
566
567        EntryIDSet entryIDList;
568
569        try
570        {
571          entryIDList = new EntryIDSet(key.getData(), data.getData());
572        }
573        catch (Exception e)
574        {
575          errorCount++;
576          if (logger.isTraceEnabled())
577          {
578            logger.traceException(e);
579
580            logger.trace("File id2children has malformed ID list " +
581                "for ID %s:%n%s%n", entryID,
582                                    StaticUtils.bytesToHex(data.getData()));
583          }
584          continue;
585        }
586
587        updateIndexStats(entryIDList);
588
589        if (entryIDList.isDefined())
590        {
591          Entry entry;
592          try
593          {
594            entry = id2entry.get(null, entryID, LockMode.DEFAULT);
595          }
596          catch (Exception e)
597          {
598            logger.traceException(e);
599            errorCount++;
600            continue;
601          }
602
603          if (entry == null)
604          {
605            errorCount++;
606            if (logger.isTraceEnabled())
607            {
608              logger.trace("File id2children has unknown ID %d%n",
609                         entryID.longValue());
610            }
611            continue;
612          }
613
614          for (EntryID id : entryIDList)
615          {
616            Entry childEntry;
617            try
618            {
619              childEntry = id2entry.get(null, id, LockMode.DEFAULT);
620            }
621            catch (Exception e)
622            {
623              logger.traceException(e);
624              errorCount++;
625              continue;
626            }
627
628            if (childEntry == null)
629            {
630              errorCount++;
631              if (logger.isTraceEnabled())
632              {
633                logger.trace("File id2children has ID %d referencing " +
634                    "unknown ID %d%n", entryID.longValue(), id.longValue());
635              }
636              continue;
637            }
638
639            if (!childEntry.getName().isDescendantOf(entry.getName()) ||
640                 childEntry.getName().size() !=
641                 entry.getName().size() + 1)
642            {
643              errorCount++;
644              if (logger.isTraceEnabled())
645              {
646                logger.trace("File id2children has ID %d with DN <%s> " +
647                    "referencing ID %d with non-child DN <%s>%n",
648                    entryID.longValue(), entry.getName(), id.longValue(), childEntry.getName());
649              }
650            }
651          }
652        }
653      }
654    }
655    finally
656    {
657      cursor.close();
658    }
659  }
660
661  /**
662   * Iterate through the entries in ID2Subtree to perform a check for
663   * index cleanliness.
664   *
665   * @throws JebException If an error occurs in the JE backend.
666   * @throws DatabaseException If an error occurs in the JE database.
667   */
668  private void iterateID2Subtree() throws JebException, DatabaseException
669  {
670    DiskOrderedCursor cursor = id2s.openCursor(new DiskOrderedCursorConfig());
671    try
672    {
673      DatabaseEntry key = new DatabaseEntry();
674      DatabaseEntry data = new DatabaseEntry();
675
676      while (cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
677      {
678        keyCount++;
679
680        EntryID entryID;
681        try
682        {
683          entryID = new EntryID(key);
684        }
685        catch (Exception e)
686        {
687          errorCount++;
688          if (logger.isTraceEnabled())
689          {
690            logger.traceException(e);
691
692            logger.trace("File id2subtree has malformed ID %s%n",
693                       StaticUtils.bytesToHex(key.getData()));
694          }
695          continue;
696        }
697
698        EntryIDSet entryIDList;
699        try
700        {
701          entryIDList = new EntryIDSet(key.getData(), data.getData());
702        }
703        catch (Exception e)
704        {
705          errorCount++;
706          if (logger.isTraceEnabled())
707          {
708            logger.traceException(e);
709
710            logger.trace("File id2subtree has malformed ID list " +
711                "for ID %s:%n%s%n", entryID,
712                                    StaticUtils.bytesToHex(data.getData()));
713          }
714          continue;
715        }
716
717        updateIndexStats(entryIDList);
718
719        if (entryIDList.isDefined())
720        {
721          Entry entry;
722          try
723          {
724            entry = id2entry.get(null, entryID, LockMode.DEFAULT);
725          }
726          catch (Exception e)
727          {
728            logger.traceException(e);
729            errorCount++;
730            continue;
731          }
732
733          if (entry == null)
734          {
735            errorCount++;
736            if (logger.isTraceEnabled())
737            {
738              logger.trace("File id2subtree has unknown ID %d%n",
739                         entryID.longValue());
740            }
741            continue;
742          }
743
744          for (EntryID id : entryIDList)
745          {
746            Entry subordEntry;
747            try
748            {
749              subordEntry = id2entry.get(null, id, LockMode.DEFAULT);
750            }
751            catch (Exception e)
752            {
753              logger.traceException(e);
754              errorCount++;
755              continue;
756            }
757
758            if (subordEntry == null)
759            {
760              errorCount++;
761              if (logger.isTraceEnabled())
762              {
763                logger.trace("File id2subtree has ID %d referencing " +
764                    "unknown ID %d%n", entryID.longValue(), id.longValue());
765              }
766              continue;
767            }
768
769            if (!subordEntry.getName().isDescendantOf(entry.getName()))
770            {
771              errorCount++;
772              if (logger.isTraceEnabled())
773              {
774                logger.trace("File id2subtree has ID %d with DN <%s> " +
775                    "referencing ID %d with non-subordinate DN <%s>%n",
776                    entryID.longValue(), entry.getName(), id.longValue(), subordEntry.getName());
777              }
778            }
779          }
780        }
781      }
782    }
783    finally
784    {
785      cursor.close();
786    }
787  }
788
789  /**
790   * Increment the counter for a key that has exceeded the
791   * entry limit. The counter gives the number of entries that have
792   * referenced the key.
793   *
794   * @param index The index containing the key.
795   * @param key A key that has exceeded the entry limit.
796   */
797  private void incrEntryLimitStats(Index index, byte[] key)
798  {
799    HashMap<ByteString,Long> hashMap = entryLimitMap.get(index);
800    if (hashMap == null)
801    {
802      hashMap = new HashMap<>();
803      entryLimitMap.put(index, hashMap);
804    }
805    ByteString octetString = ByteString.wrap(key);
806    Long counter = hashMap.get(octetString);
807    if (counter != null)
808    {
809      counter++;
810    }
811    else
812    {
813      counter = 1L;
814    }
815    hashMap.put(octetString, counter);
816  }
817
818  /**
819   * Update the statistical information for an index record.
820   *
821   * @param entryIDSet The set of entry IDs for the index record.
822   */
823  private void updateIndexStats(EntryIDSet entryIDSet)
824  {
825    if (!entryIDSet.isDefined())
826    {
827      entryLimitExceededCount++;
828      multiReferenceCount++;
829    }
830    else
831    {
832      if (entryIDSet.size() > 1)
833      {
834        multiReferenceCount++;
835      }
836      entryReferencesCount += entryIDSet.size();
837      maxEntryPerValue = Math.max(maxEntryPerValue, entryIDSet.size());
838    }
839  }
840
841  /**
842   * Iterate through the entries in a VLV index to perform a check for index
843   * cleanliness.
844   *
845   * @param vlvIndex The VLV index to perform the check against.
846   * @param verifyID True to verify the IDs against id2entry.
847   * @throws JebException If an error occurs in the JE backend.
848   * @throws DatabaseException If an error occurs in the JE database.
849   * @throws DirectoryException If an error occurs reading values in the index.
850   */
851  private void iterateVLVIndex(VLVIndex vlvIndex, boolean verifyID)
852      throws JebException, DatabaseException, DirectoryException
853  {
854    if(vlvIndex == null)
855    {
856      return;
857    }
858
859    DiskOrderedCursor cursor =
860        vlvIndex.openCursor(new DiskOrderedCursorConfig());
861    try
862    {
863      DatabaseEntry key = new DatabaseEntry();
864      DatabaseEntry data = new DatabaseEntry();
865
866      SortValues lastValues = null;
867      while(cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
868      {
869        SortValuesSet sortValuesSet =
870            new SortValuesSet(key.getData(), data.getData(), vlvIndex);
871        for(int i = 0; i < sortValuesSet.getEntryIDs().length; i++)
872        {
873          keyCount++;
874          SortValues values = sortValuesSet.getSortValues(i);
875          if(lastValues != null && lastValues.compareTo(values) >= 1)
876          {
877            // Make sure the values is larger then the previous one.
878            if(logger.isTraceEnabled())
879            {
880              logger.trace("Values %s and %s are incorrectly ordered",
881                                lastValues, values, keyDump(vlvIndex,
882                                          sortValuesSet.getKeySortValues()));
883            }
884            errorCount++;
885          }
886          if(i == sortValuesSet.getEntryIDs().length - 1 &&
887              key.getData().length != 0)
888          {
889            // If this is the last one in a bounded set, make sure it is the
890            // same as the database key.
891            byte[] encodedKey = vlvIndex.encodeKey(
892                values.getEntryID(), values.getValues(), values.getTypes());
893            if(!Arrays.equals(key.getData(), encodedKey))
894            {
895              if(logger.isTraceEnabled())
896              {
897                logger.trace("Incorrect key for SortValuesSet in VLV " +
898                    "index %s. Last values bytes %s, Key bytes %s",
899                                  vlvIndex.getName(), encodedKey, key);
900              }
901              errorCount++;
902            }
903          }
904          lastValues = values;
905
906          if(verifyID)
907          {
908            Entry entry;
909            EntryID id = new EntryID(values.getEntryID());
910            try
911            {
912              entry = id2entry.get(null, id, LockMode.DEFAULT);
913            }
914            catch (Exception e)
915            {
916              logger.traceException(e);
917              errorCount++;
918              continue;
919            }
920
921            if (entry == null)
922            {
923              errorCount++;
924              if (logger.isTraceEnabled())
925              {
926                logger.trace("Reference to unknown ID %d%n%s",
927                                  id.longValue(),
928                                  keyDump(vlvIndex,
929                                          sortValuesSet.getKeySortValues()));
930              }
931              continue;
932            }
933
934            SortValues entryValues =
935                new SortValues(id, entry, vlvIndex.sortOrder);
936            if(entryValues.compareTo(values) != 0)
937            {
938              errorCount++;
939              if(logger.isTraceEnabled())
940              {
941                logger.trace("Reference to entry ID %d " +
942                    "which does not match the values%n%s",
943                                  id.longValue(),
944                                  keyDump(vlvIndex,
945                                          sortValuesSet.getKeySortValues()));
946              }
947            }
948          }
949        }
950      }
951    }
952    finally
953    {
954      cursor.close();
955    }
956  }
957
958  /**
959   * Iterate through the entries in an attribute index to perform a check for
960   * index cleanliness.
961   * @param index The index database to be checked.
962   * @throws JebException If an error occurs in the JE backend.
963   * @throws DatabaseException If an error occurs in the JE database.
964   */
965  private void iterateAttrIndex(Index index) throws JebException, DatabaseException
966  {
967    if (index == null)
968    {
969      return;
970    }
971
972    DiskOrderedCursor cursor = index.openCursor(new DiskOrderedCursorConfig());
973    try
974    {
975      DatabaseEntry key = new DatabaseEntry();
976      DatabaseEntry data = new DatabaseEntry();
977
978      while (cursor.getNext(key, data, null) == OperationStatus.SUCCESS)
979      {
980        keyCount++;
981
982        EntryIDSet entryIDList;
983        try
984        {
985          entryIDList = new EntryIDSet(key.getData(), data.getData());
986        }
987        catch (Exception e)
988        {
989          errorCount++;
990          if (logger.isTraceEnabled())
991          {
992            logger.traceException(e);
993
994            logger.trace("Malformed ID list: %s%n%s",
995                       StaticUtils.bytesToHex(data.getData()),
996                       keyDump(index, key.getData()));
997          }
998          continue;
999        }
1000
1001        updateIndexStats(entryIDList);
1002
1003        if (entryIDList.isDefined())
1004        {
1005          final ByteString value = ByteString.wrap(key.getData());
1006          EntryID prevID = null;
1007
1008          for (EntryID id : entryIDList)
1009          {
1010            if (prevID != null && id.equals(prevID) && logger.isTraceEnabled())
1011            {
1012              logger.trace("Duplicate reference to ID %d%n%s",
1013                         id.longValue(), keyDump(index, key.getData()));
1014            }
1015            prevID = id;
1016
1017            Entry entry;
1018            try
1019            {
1020              entry = id2entry.get(null, id, LockMode.DEFAULT);
1021            }
1022            catch (Exception e)
1023            {
1024              logger.traceException(e);
1025              errorCount++;
1026              continue;
1027            }
1028
1029            if (entry == null)
1030            {
1031              errorCount++;
1032              if (logger.isTraceEnabled())
1033              {
1034                logger.trace("Reference to unknown ID %d%n%s",
1035                           id.longValue(), keyDump(index, key.getData()));
1036              }
1037              continue;
1038            }
1039
1040            // As an optimization avoid passing in a real set and wasting time
1041            // hashing and comparing a potentially large set of values, as well
1042            // as using up memory. Instead just intercept the add() method and
1043            // detect when an equivalent value has been added.
1044
1045            // We need to use an AtomicBoolean here since anonymous classes
1046            // require referenced external variables to be final.
1047            final AtomicBoolean foundMatchingKey = new AtomicBoolean(false);
1048
1049            Set<ByteString> dummySet = new AbstractSet<ByteString>()
1050            {
1051              @Override
1052              public Iterator<ByteString> iterator()
1053              {
1054                // The set is always empty.
1055                return Collections.<ByteString> emptySet().iterator();
1056              }
1057
1058              @Override
1059              public int size()
1060              {
1061                // The set is always empty.
1062                return 0;
1063              }
1064
1065              @Override
1066              public boolean add(ByteString e)
1067              {
1068                if (value.equals(e))
1069                {
1070                  // We could terminate processing at this point by throwing an
1071                  // UnsupportedOperationException, but this optimization is
1072                  // already ugly enough.
1073                  foundMatchingKey.set(true);
1074                }
1075                return true;
1076              }
1077
1078            };
1079
1080            index.indexEntry(entry, dummySet);
1081
1082            if (!foundMatchingKey.get())
1083            {
1084              errorCount++;
1085              if (logger.isTraceEnabled())
1086              {
1087                logger.trace("Reference to entry "
1088                    + "<%s> which does not match the value%n%s",
1089                    entry.getName(),
1090                    keyDump(index, value.toByteArray()));
1091              }
1092            }
1093          }
1094        }
1095      }
1096    }
1097    finally
1098    {
1099      cursor.close();
1100    }
1101  }
1102
1103  /**
1104   * Check that an index is complete for a given entry.
1105   *
1106   * @param entryID The entry ID.
1107   * @param entry The entry to be checked.
1108   */
1109  private void verifyEntry(EntryID entryID, Entry entry)
1110  {
1111    if (verifyDN2ID)
1112    {
1113      verifyDN2ID(entryID, entry);
1114    }
1115    if (verifyID2Children)
1116    {
1117      verifyID2Children(entryID, entry);
1118    }
1119    if (verifyID2Subtree)
1120    {
1121      verifyID2Subtree(entryID, entry);
1122    }
1123    verifyIndex(entryID, entry);
1124  }
1125
1126  /**
1127   * Check that the DN2ID index is complete for a given entry.
1128   *
1129   * @param entryID The entry ID.
1130   * @param entry The entry to be checked.
1131   */
1132  private void verifyDN2ID(EntryID entryID, Entry entry)
1133  {
1134    DN dn = entry.getName();
1135
1136    // Check the ID is in dn2id with the correct DN.
1137    try
1138    {
1139      EntryID id = dn2id.get(null, dn, LockMode.DEFAULT);
1140      if (id == null)
1141      {
1142        if (logger.isTraceEnabled())
1143        {
1144          logger.trace("File dn2id is missing key %s.%n", dn);
1145        }
1146        errorCount++;
1147      }
1148      else if (!id.equals(entryID))
1149      {
1150        if (logger.isTraceEnabled())
1151        {
1152          logger.trace("File dn2id has ID %d instead of %d for key %s.%n", id.longValue(), entryID.longValue(), dn);
1153        }
1154        errorCount++;
1155      }
1156    }
1157    catch (Exception e)
1158    {
1159      if (logger.isTraceEnabled())
1160      {
1161        logger.traceException(e);
1162        logger.trace("File dn2id has error reading key %s: %s.%n", dn, e.getMessage());
1163      }
1164      errorCount++;
1165    }
1166
1167    // Check the parent DN is in dn2id.
1168    DN parentDN = getParent(dn);
1169    if (parentDN != null)
1170    {
1171      try
1172      {
1173        EntryID id = dn2id.get(null, parentDN, LockMode.DEFAULT);
1174        if (id == null)
1175        {
1176          if (logger.isTraceEnabled())
1177          {
1178            logger.trace("File dn2id is missing key %s.%n", parentDN);
1179          }
1180          errorCount++;
1181        }
1182      }
1183      catch (Exception e)
1184      {
1185        if (logger.isTraceEnabled())
1186        {
1187          logger.traceException(e);
1188          logger.trace("File dn2id has error reading key %s: %s.%n", parentDN, e.getMessage());
1189        }
1190        errorCount++;
1191      }
1192    }
1193  }
1194
1195  /**
1196   * Check that the ID2Children index is complete for a given entry.
1197   *
1198   * @param entryID The entry ID.
1199   * @param entry The entry to be checked.
1200   */
1201  private void verifyID2Children(EntryID entryID, Entry entry)
1202  {
1203    DN dn = entry.getName();
1204
1205    DN parentDN = getParent(dn);
1206    if (parentDN != null)
1207    {
1208      EntryID parentID = null;
1209      try
1210      {
1211        parentID = dn2id.get(null, parentDN, LockMode.DEFAULT);
1212        if (parentID == null)
1213        {
1214          if (logger.isTraceEnabled())
1215          {
1216            logger.trace("File dn2id is missing key %s.%n", parentDN);
1217          }
1218          errorCount++;
1219        }
1220      }
1221      catch (Exception e)
1222      {
1223        if (logger.isTraceEnabled())
1224        {
1225          logger.traceException(e);
1226          logger.trace("File dn2id has error reading key %s: %s.", parentDN, e.getMessage());
1227        }
1228        errorCount++;
1229      }
1230      if (parentID != null)
1231      {
1232        try
1233        {
1234          ConditionResult cr = id2c.containsID(null, parentID.getDatabaseEntry(), entryID);
1235          if (cr == ConditionResult.FALSE)
1236          {
1237            if (logger.isTraceEnabled())
1238            {
1239              logger.trace("File id2children is missing ID %d for key %d.%n",
1240                  entryID.longValue(), parentID.longValue());
1241            }
1242            errorCount++;
1243          }
1244          else if (cr == ConditionResult.UNDEFINED)
1245          {
1246            incrEntryLimitStats(id2c, parentID.getDatabaseEntry().getData());
1247          }
1248        }
1249        catch (DatabaseException e)
1250        {
1251          if (logger.isTraceEnabled())
1252          {
1253            logger.traceException(e);
1254
1255            logger.trace("File id2children has error reading key %d: %s.",
1256                       parentID.longValue(), e.getMessage());
1257          }
1258          errorCount++;
1259        }
1260      }
1261    }
1262  }
1263
1264  /**
1265   * Check that the ID2Subtree index is complete for a given entry.
1266   *
1267   * @param entryID The entry ID.
1268   * @param entry The entry to be checked.
1269   */
1270  private void verifyID2Subtree(EntryID entryID, Entry entry)
1271  {
1272    for (DN dn = getParent(entry.getName()); dn != null; dn = getParent(dn))
1273    {
1274      EntryID id = null;
1275      try
1276      {
1277        id = dn2id.get(null, dn, LockMode.DEFAULT);
1278        if (id == null)
1279        {
1280          if (logger.isTraceEnabled())
1281          {
1282            logger.trace("File dn2id is missing key %s.%n", dn);
1283          }
1284          errorCount++;
1285        }
1286      }
1287      catch (Exception e)
1288      {
1289        if (logger.isTraceEnabled())
1290        {
1291          logger.traceException(e);
1292          logger.trace("File dn2id has error reading key %s: %s.%n", dn, e.getMessage());
1293        }
1294        errorCount++;
1295      }
1296      if (id != null)
1297      {
1298        try
1299        {
1300          ConditionResult cr;
1301          cr = id2s.containsID(null, id.getDatabaseEntry(), entryID);
1302          if (cr == ConditionResult.FALSE)
1303          {
1304            if (logger.isTraceEnabled())
1305            {
1306              logger.trace("File id2subtree is missing ID %d " +
1307                  "for key %d.%n",
1308                         entryID.longValue(), id.longValue());
1309            }
1310            errorCount++;
1311          }
1312          else if (cr == ConditionResult.UNDEFINED)
1313          {
1314            incrEntryLimitStats(id2s, id.getDatabaseEntry().getData());
1315          }
1316        }
1317        catch (DatabaseException e)
1318        {
1319          if (logger.isTraceEnabled())
1320          {
1321            logger.traceException(e);
1322
1323            logger.trace("File id2subtree has error reading key %d: %s.%n",
1324                       id.longValue(), e.getMessage());
1325          }
1326          errorCount++;
1327        }
1328      }
1329    }
1330  }
1331
1332  /**
1333   * Construct a printable string from a raw key value.
1334   *
1335   * @param index The index database containing the key value.
1336   * @param keyBytes The bytes of the key.
1337   * @return A string that may be logged or printed.
1338   */
1339  private String keyDump(Index index, byte[] keyBytes)
1340  {
1341    StringBuilder buffer = new StringBuilder(128);
1342    buffer.append("File: ");
1343    buffer.append(index);
1344    buffer.append(ServerConstants.EOL);
1345    buffer.append("Key:");
1346    buffer.append(ServerConstants.EOL);
1347    StaticUtils.byteArrayToHexPlusAscii(buffer, keyBytes, 6);
1348    return buffer.toString();
1349  }
1350
1351  /**
1352   * Construct a printable string from a raw key value.
1353   *
1354   * @param vlvIndex The vlvIndex database containing the key value.
1355   * @param keySortValues THe sort values that is being used as the key.
1356   * @return A string that may be logged or printed.
1357   */
1358  private String keyDump(VLVIndex vlvIndex, SortValues keySortValues)
1359  {
1360    StringBuilder buffer = new StringBuilder(128);
1361    buffer.append("File: ");
1362    buffer.append(vlvIndex);
1363    buffer.append(ServerConstants.EOL);
1364    buffer.append("Key (last sort values):");
1365    if(keySortValues != null)
1366    {
1367      buffer.append(keySortValues);
1368    }
1369    else
1370    {
1371      buffer.append("UNBOUNDED (0x00)");
1372    }
1373    return buffer.toString();
1374  }
1375
1376  /**
1377   * Check that an attribute index is complete for a given entry.
1378   *
1379   * @param entryID The entry ID.
1380   * @param entry The entry to be checked.
1381   */
1382  private void verifyIndex(EntryID entryID, Entry entry)
1383  {
1384    for (AttributeIndex attrIndex : attrIndexList)
1385    {
1386      try
1387      {
1388        verifyAttribute(attrIndex, entryID, entry);
1389      }
1390      catch (DirectoryException e)
1391      {
1392        if (logger.isTraceEnabled())
1393        {
1394          logger.traceException(e);
1395
1396          logger.trace("Error normalizing values of attribute %s in " +
1397              "entry <%s>: %s.%n",
1398                     attrIndex.getAttributeType(), entry.getName(), e.getMessageObject());
1399        }
1400      }
1401    }
1402
1403    for (VLVIndex vlvIndex : vlvIndexList)
1404    {
1405      try
1406      {
1407        if (vlvIndex.shouldInclude(entry)
1408            && !vlvIndex.containsValues(null, entryID.longValue(),
1409                    vlvIndex.getSortValues(entry), vlvIndex.getSortTypes()))
1410        {
1411          if(logger.isTraceEnabled())
1412          {
1413            logger.trace("Missing entry %s in VLV index %s", entry.getName(), vlvIndex.getName());
1414          }
1415          errorCount++;
1416        }
1417      }
1418      catch (DirectoryException e)
1419      {
1420        if (logger.isTraceEnabled())
1421        {
1422          logger.traceException(e);
1423          logger.trace("Error checking entry %s against filter or base DN for VLV index %s: %s",
1424                     entry.getName(), vlvIndex.getName(), e.getMessageObject());
1425        }
1426        errorCount++;
1427      }
1428      catch (DatabaseException | JebException e)
1429      {
1430        if (logger.isTraceEnabled())
1431        {
1432          logger.traceException(e);
1433          logger.trace("Error reading VLV index %s for entry %s: %s",
1434              vlvIndex.getName(), entry.getName(), StaticUtils.getBacktrace(e));
1435        }
1436        errorCount++;
1437      }
1438    }
1439  }
1440
1441  /**
1442   * Check that an attribute index is complete for a given attribute.
1443   *
1444   * @param attrIndex The attribute index to be checked.
1445   * @param entryID The entry ID.
1446   * @param attrList The attribute to be checked.
1447   * @throws DirectoryException If a Directory Server error occurs.
1448   */
1449  private void verifyAttribute(AttributeIndex attrIndex, EntryID entryID, Entry entry) throws DirectoryException
1450  {
1451    for (Index index : attrIndex.getAllIndexes())
1452    {
1453      final Set<ByteString> keys = new HashSet<>();
1454      index.indexEntry(entry, keys);
1455      for (ByteString key : keys)
1456      {
1457        verifyAttributeInIndex(index, null, key, entryID);
1458      }
1459    }
1460  }
1461
1462  private void verifyAttributeInIndex(Index index, Transaction txn, ByteString key, EntryID entryID)
1463  {
1464    try
1465    {
1466      final ConditionResult cr = index.containsID(txn, new DatabaseEntry(key.toByteArray()), entryID);
1467      if (cr == ConditionResult.FALSE)
1468      {
1469        if (logger.isTraceEnabled())
1470        {
1471          logger.trace("Missing ID %d%n%s",
1472                     entryID.longValue(),
1473                     keyDump(index, key.toByteArray()));
1474        }
1475        errorCount++;
1476      }
1477      else if (cr == ConditionResult.UNDEFINED)
1478      {
1479        incrEntryLimitStats(index, key.toByteArray());
1480      }
1481    }
1482    catch (DatabaseException e)
1483    {
1484      if (logger.isTraceEnabled())
1485      {
1486        logger.traceException(e);
1487
1488        logger.trace("Error reading database: %s%n%s",
1489                   e.getMessage(),
1490                   keyDump(index, key.toByteArray()));
1491      }
1492      errorCount++;
1493    }
1494  }
1495
1496  private byte[] normalize(MatchingRule matchingRule,
1497      ByteString value) throws DirectoryException
1498  {
1499    try
1500    {
1501      return matchingRule.normalizeAttributeValue(value).toByteArray();
1502    }
1503    catch (DecodeException e)
1504    {
1505      throw new DirectoryException(ResultCode.INVALID_ATTRIBUTE_SYNTAX,
1506          e.getMessageObject(), e);
1507    }
1508  }
1509
1510  /**
1511   * Get the parent DN of a given DN.
1512   *
1513   * @param dn The DN.
1514   * @return The parent DN or null if the given DN is a base DN.
1515   */
1516  private DN getParent(DN dn)
1517  {
1518    if (dn.equals(verifyConfig.getBaseDN()))
1519    {
1520      return null;
1521    }
1522    return dn.getParentDNInSuffix();
1523  }
1524
1525  /** This class reports progress of the verify job at fixed intervals. */
1526  private final class ProgressTask extends TimerTask
1527  {
1528    /** The total number of records to process. */
1529    private long totalCount;
1530
1531    /**
1532     * The number of records that had been processed at the time of the
1533     * previous progress report.
1534     */
1535    private long previousCount;
1536
1537    /** The time in milliseconds of the previous progress report. */
1538    private long previousTime;
1539    /** The environment statistics at the time of the previous report. */
1540    private EnvironmentStats prevEnvStats;
1541
1542    /**
1543     * The number of bytes in a megabyte.
1544     * Note that 1024*1024 bytes may eventually become known as a mebibyte(MiB).
1545     */
1546    private static final int bytesPerMegabyte = 1024*1024;
1547
1548    /**
1549     * Create a new verify progress task.
1550     * @param indexIterator boolean, indicates if the task is iterating
1551     * through indexes or the entries.
1552     * @throws DatabaseException An error occurred while accessing the JE
1553     * database.
1554     */
1555    private ProgressTask(boolean indexIterator) throws DatabaseException
1556    {
1557      previousTime = System.currentTimeMillis();
1558      prevEnvStats = rootContainer.getEnvironmentStats(new StatsConfig());
1559
1560      if (indexIterator)
1561      {
1562        if (verifyDN2ID)
1563        {
1564          totalCount = dn2id.getRecordCount();
1565        }
1566        else if (verifyID2Children)
1567        {
1568          totalCount = id2c.getRecordCount();
1569        }
1570        else if (verifyID2Subtree)
1571        {
1572          totalCount = id2s.getRecordCount();
1573        }
1574        else if(!attrIndexList.isEmpty())
1575        {
1576          AttributeIndex attrIndex = attrIndexList.get(0);
1577          totalCount = 0;
1578          for (Index index : attrIndex.getAllIndexes())
1579          {
1580            totalCount += getRecordCount(index);
1581          }
1582        }
1583        else if (!vlvIndexList.isEmpty())
1584        {
1585          totalCount = vlvIndexList.get(0).getRecordCount();
1586        }
1587      }
1588      else
1589      {
1590        totalCount = rootContainer.getEntryContainer(
1591          verifyConfig.getBaseDN()).getEntryCount();
1592      }
1593    }
1594
1595    private long getRecordCount(Index index)
1596    {
1597      return index != null ? index.getRecordCount() : 0;
1598    }
1599
1600    /** The action to be performed by this timer task. */
1601    @Override
1602    public void run()
1603    {
1604      long latestCount = keyCount;
1605      long deltaCount = latestCount - previousCount;
1606      long latestTime = System.currentTimeMillis();
1607      long deltaTime = latestTime - previousTime;
1608
1609      if (deltaTime == 0)
1610      {
1611        return;
1612      }
1613
1614      float rate = 1000f*deltaCount / deltaTime;
1615
1616      logger.info(NOTE_VERIFY_PROGRESS_REPORT, latestCount, totalCount, errorCount, rate);
1617
1618      try
1619      {
1620        Runtime runtime = Runtime.getRuntime();
1621        long freeMemory = runtime.freeMemory() / bytesPerMegabyte;
1622
1623        EnvironmentStats envStats =
1624            rootContainer.getEnvironmentStats(new StatsConfig());
1625        long nCacheMiss =
1626             envStats.getNCacheMiss() - prevEnvStats.getNCacheMiss();
1627
1628        float cacheMissRate = 0;
1629        if (deltaCount > 0)
1630        {
1631          cacheMissRate = nCacheMiss/(float)deltaCount;
1632        }
1633
1634        logger.debug(INFO_CACHE_AND_MEMORY_REPORT, freeMemory, cacheMissRate);
1635
1636        prevEnvStats = envStats;
1637      }
1638      catch (DatabaseException e)
1639      {
1640        logger.traceException(e);
1641      }
1642
1643
1644      previousCount = latestCount;
1645      previousTime = latestTime;
1646    }
1647  }
1648}