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
010     * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011     * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012     * See the License for the specific language governing permissions
013     * and limitations under the License.
014     *
015     * When distributing Covered Code, include this CDDL HEADER in each
016     * file and include the License file at
017     * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
018     * add the following below this CDDL HEADER, with the fields enclosed
019     * by brackets "[]" replaced with your own identifying information:
020     *      Portions Copyright [yyyy] [name of copyright owner]
021     *
022     * CDDL HEADER END
023     *
024     *
025     *      Copyright 2006-2008 Sun Microsystems, Inc.
026     */
027    package org.opends.server.backends.jeb;
028    import org.opends.messages.Message;
029    
030    import static org.opends.server.loggers.ErrorLogger.logError;
031    import static org.opends.server.loggers.debug.DebugLogger.*;
032    import org.opends.server.loggers.debug.DebugTracer;
033    
034    import com.sleepycat.je.Cursor;
035    import com.sleepycat.je.CursorConfig;
036    import com.sleepycat.je.DatabaseEntry;
037    import com.sleepycat.je.DatabaseException;
038    import com.sleepycat.je.EnvironmentStats;
039    import com.sleepycat.je.LockMode;
040    import com.sleepycat.je.OperationStatus;
041    import com.sleepycat.je.StatsConfig;
042    import com.sleepycat.je.Transaction;
043    
044    import org.opends.server.api.OrderingMatchingRule;
045    import org.opends.server.api.ApproximateMatchingRule;
046    import org.opends.server.core.DirectoryServer;
047    import org.opends.server.protocols.asn1.ASN1OctetString;
048    import org.opends.server.util.StaticUtils;
049    import org.opends.server.util.ServerConstants;
050    
051    import org.opends.server.types.*;
052    import static org.opends.messages.JebMessages.*;
053    import java.util.ArrayList;
054    import java.util.Arrays;
055    import java.util.HashMap;
056    import java.util.IdentityHashMap;
057    import java.util.LinkedHashSet;
058    import java.util.List;
059    import java.util.Map;
060    import java.util.Set;
061    import java.util.Timer;
062    import java.util.TimerTask;
063    
064    /**
065     * This class is used to run an index verification process on the backend.
066     */
067    public class VerifyJob
068    {
069      /**
070       * The tracer object for the debug logger.
071       */
072      private static final DebugTracer TRACER = getTracer();
073    
074    
075      /**
076       * The verify configuration.
077       */
078      private VerifyConfig verifyConfig;
079    
080      /**
081       * The root container used for the verify job.
082       */
083      RootContainer rootContainer;
084    
085      /**
086       * The number of milliseconds between job progress reports.
087       */
088      private long progressInterval = 10000;
089    
090      /**
091       * The number of index keys processed.
092       */
093      private long keyCount = 0;
094    
095      /**
096       * The number of errors found.
097       */
098      private long errorCount = 0;
099    
100      /**
101       * The number of records that have exceeded the entry limit.
102       */
103      long entryLimitExceededCount = 0;
104    
105      /**
106       * The number of records that reference more than one entry.
107       */
108      long multiReferenceCount = 0;
109    
110      /**
111       * The total number of entry references.
112       */
113      long entryReferencesCount = 0;
114    
115      /**
116       * The maximum number of references per record.
117       */
118      long maxEntryPerValue = 0;
119    
120      /**
121       * This map is used to gather some statistics about values that have
122       * exceeded the entry limit.
123       */
124      IdentityHashMap<Index,HashMap<ByteString,Long>> entryLimitMap =
125           new IdentityHashMap<Index, HashMap<ByteString, Long>>();
126    
127      /**
128       * Indicates whether the DN database is to be verified.
129       */
130      private boolean verifyDN2ID = false;
131    
132      /**
133       * Indicates whether the children database is to be verified.
134       */
135      private boolean verifyID2Children = false;
136    
137      /**
138       * Indicates whether the subtree database is to be verified.
139       */
140      private boolean verifyID2Subtree = false;
141    
142      /**
143       * The entry database.
144       */
145      ID2Entry id2entry = null;
146    
147      /**
148       * The DN database.
149       */
150      DN2ID dn2id = null;
151    
152      /**
153       * The children database.
154       */
155      Index id2c = null;
156    
157      /**
158       * The subtree database.
159       */
160      Index id2s = null;
161    
162      /**
163       * A list of the attribute indexes to be verified.
164       */
165      ArrayList<AttributeIndex> attrIndexList = new ArrayList<AttributeIndex>();
166    
167      /**
168       * A list of the VLV indexes to be verified.
169       */
170      ArrayList<VLVIndex> vlvIndexList = new ArrayList<VLVIndex>();
171    
172    /**
173     * The types of indexes that are verifiable.
174     */
175      enum IndexType
176      {
177          PRES, EQ, SUBSTRING, ORDERING, APPROXIMATE
178      }
179    
180      /**
181       * Construct a VerifyJob.
182       *
183       * @param verifyConfig The verify configuration.
184       */
185      public VerifyJob(VerifyConfig verifyConfig)
186      {
187        this.verifyConfig = verifyConfig;
188      }
189    
190      /**
191       * Verify the backend.
192       *
193       * @param rootContainer The root container that holds the entries to verify.
194       * @param statEntry Optional statistics entry.
195       * @return The error count.
196       * @throws DatabaseException If an error occurs in the JE database.
197       * @throws JebException If an error occurs in the JE backend.
198       * @throws DirectoryException If an error occurs while verifying the backend.
199       */
200      public long verifyBackend(RootContainer rootContainer, Entry statEntry) throws
201          DatabaseException, JebException, DirectoryException
202      {
203        this.rootContainer = rootContainer;
204        EntryContainer entryContainer =
205            rootContainer.getEntryContainer(verifyConfig.getBaseDN());
206    
207        entryContainer.sharedLock.lock();
208        try
209        {
210          ArrayList<String> completeList = verifyConfig.getCompleteList();
211          ArrayList<String> cleanList = verifyConfig.getCleanList();
212    
213          boolean cleanMode = false;
214          if (completeList.isEmpty() && cleanList.isEmpty())
215          {
216            verifyDN2ID = true;
217            verifyID2Children = true;
218            verifyID2Subtree = true;
219            attrIndexList.addAll(entryContainer.getAttributeIndexes());
220          }
221          else
222          {
223            ArrayList<String> list;
224            if (!completeList.isEmpty())
225            {
226              list = completeList;
227            }
228            else
229            {
230              list = cleanList;
231              cleanMode = true;
232            }
233    
234            for (String index : list)
235            {
236              String lowerName = index.toLowerCase();
237              if (lowerName.equals("dn2id"))
238              {
239                verifyDN2ID = true;
240              }
241              else if (lowerName.equals("id2children"))
242              {
243                verifyID2Children = true;
244              }
245              else if (lowerName.equals("id2subtree"))
246              {
247                verifyID2Subtree = true;
248              }
249              else if(lowerName.startsWith("vlv."))
250              {
251                if(lowerName.length() < 5)
252                {
253                  Message msg = ERR_JEB_VLV_INDEX_NOT_CONFIGURED.get(lowerName);
254                  throw new JebException(msg);
255                }
256    
257                VLVIndex vlvIndex =
258                    entryContainer.getVLVIndex(lowerName.substring(4));
259                if(vlvIndex == null)
260                {
261                  Message msg =
262                      ERR_JEB_VLV_INDEX_NOT_CONFIGURED.get(lowerName.substring(4));
263                  throw new JebException(msg);
264                }
265    
266                vlvIndexList.add(vlvIndex);
267              }
268              else
269              {
270                AttributeType attrType =
271                    DirectoryServer.getAttributeType(lowerName);
272                if (attrType == null)
273                {
274                  Message msg = ERR_JEB_ATTRIBUTE_INDEX_NOT_CONFIGURED.get(index);
275                  throw new JebException(msg);
276                }
277                AttributeIndex attrIndex =
278                    entryContainer.getAttributeIndex(attrType);
279                if (attrIndex == null)
280                {
281                  Message msg = ERR_JEB_ATTRIBUTE_INDEX_NOT_CONFIGURED.get(index);
282                  throw new JebException(msg);
283                }
284                attrIndexList.add(attrIndex);
285              }
286            }
287          }
288    
289          entryLimitMap =
290              new IdentityHashMap<Index,HashMap<ByteString,Long>>(
291                  attrIndexList.size());
292    
293          // We will be updating these files independently of the indexes
294          // so we need direct access to them rather than going through
295          // the entry entryContainer methods.
296          id2entry = entryContainer.getID2Entry();
297          dn2id = entryContainer.getDN2ID();
298          id2c = entryContainer.getID2Children();
299          id2s = entryContainer.getID2Subtree();
300    
301          // Make a note of the time we started.
302          long startTime = System.currentTimeMillis();
303    
304          // Start a timer for the progress report.
305          Timer timer = new Timer();
306          TimerTask progressTask = new ProgressTask();
307          timer.scheduleAtFixedRate(progressTask, progressInterval,
308                                    progressInterval);
309    
310          // Iterate through the index keys.
311          try
312          {
313            if (cleanMode)
314            {
315              iterateIndex();
316            }
317            else
318            {
319              iterateID2Entry();
320    
321              // Make sure the vlv indexes are in correct order.
322              for(VLVIndex vlvIndex : vlvIndexList)
323              {
324                iterateVLVIndex(vlvIndex, false);
325              }
326            }
327          }
328          finally
329          {
330            timer.cancel();
331          }
332    
333          long finishTime = System.currentTimeMillis();
334          long totalTime = (finishTime - startTime);
335    
336          float rate = 0;
337          if (totalTime > 0)
338          {
339            rate = 1000f*keyCount / totalTime;
340          }
341    
342          addStatEntry(statEntry, "verify-error-count",
343                       String.valueOf(errorCount));
344          addStatEntry(statEntry, "verify-key-count",
345                       String.valueOf(keyCount));
346          if (cleanMode)
347          {
348            Message message = NOTE_JEB_VERIFY_CLEAN_FINAL_STATUS.get(
349                keyCount, errorCount, totalTime/1000, rate);
350            logError(message);
351    
352            if (multiReferenceCount > 0)
353            {
354              float averageEntryReferences = 0;
355              if (keyCount > 0)
356              {
357                averageEntryReferences = (float)entryReferencesCount/keyCount;
358              }
359    
360              message =
361                  INFO_JEB_VERIFY_MULTIPLE_REFERENCE_COUNT.get(multiReferenceCount);
362              logError(message);
363              addStatEntry(statEntry, "verify-multiple-reference-count",
364                           String.valueOf(multiReferenceCount));
365    
366              message = INFO_JEB_VERIFY_ENTRY_LIMIT_EXCEEDED_COUNT.get(
367                  entryLimitExceededCount);
368              logError(message);
369              addStatEntry(statEntry, "verify-entry-limit-exceeded-count",
370                           String.valueOf(entryLimitExceededCount));
371    
372              message = INFO_JEB_VERIFY_AVERAGE_REFERENCE_COUNT.get(
373                  averageEntryReferences);
374              logError(message);
375              addStatEntry(statEntry, "verify-average-reference-count",
376                           String.valueOf(averageEntryReferences));
377    
378              message =
379                  INFO_JEB_VERIFY_MAX_REFERENCE_COUNT.get(maxEntryPerValue);
380              logError(message);
381              addStatEntry(statEntry, "verify-max-reference-count",
382                           String.valueOf(maxEntryPerValue));
383            }
384          }
385          else
386          {
387            Message message = NOTE_JEB_VERIFY_FINAL_STATUS.get(
388                keyCount, errorCount, totalTime/1000, rate);
389            logError(message);
390            //TODO add entry-limit-stats to the statEntry
391            if (entryLimitMap.size() > 0)
392            {
393              message = INFO_JEB_VERIFY_ENTRY_LIMIT_STATS_HEADER.get();
394              logError(message);
395    
396              for (Map.Entry<Index,HashMap<ByteString,Long>> mapEntry :
397                  entryLimitMap.entrySet())
398              {
399                Index index = mapEntry.getKey();
400                Long[] values = mapEntry.getValue().values().toArray(new Long[0]);
401    
402                // Calculate the median value for entry limit exceeded.
403                Arrays.sort(values);
404                long medianValue;
405                int x = values.length / 2;
406                if (values.length % 2 == 0)
407                {
408                  medianValue = (values[x] + values[x-1]) / 2;
409                }
410                else
411                {
412                  medianValue = values[x];
413                }
414    
415                message = INFO_JEB_VERIFY_ENTRY_LIMIT_STATS_ROW.
416                    get(index.toString(), values.length, values[0],
417                        values[values.length-1], medianValue);
418                logError(message);
419              }
420            }
421          }
422        }
423        finally
424        {
425          entryContainer.sharedLock.unlock();
426        }
427        return errorCount;
428      }
429    
430      /**
431       * Iterate through the entries in id2entry to perform a check for
432       * index completeness. We check that the ID for the entry is indeed
433       * present in the indexes for the appropriate values.
434       *
435       * @throws DatabaseException If an error occurs in the JE database.
436       */
437      private void iterateID2Entry() throws DatabaseException
438      {
439        Cursor cursor = id2entry.openCursor(null, new CursorConfig());
440        try
441        {
442          DatabaseEntry key = new DatabaseEntry();
443          DatabaseEntry data = new DatabaseEntry();
444    
445          Long storedEntryCount = id2entry.getRecordCount();
446    
447          OperationStatus status;
448          for (status = cursor.getFirst(key, data, LockMode.DEFAULT);
449               status == OperationStatus.SUCCESS;
450               status = cursor.getNext(key, data, LockMode.DEFAULT))
451          {
452            EntryID entryID;
453            try
454            {
455              entryID = new EntryID(key);
456            }
457            catch (Exception e)
458            {
459              errorCount++;
460              if (debugEnabled())
461              {
462                TRACER.debugCaught(DebugLogLevel.ERROR, e);
463    
464                TRACER.debugError("Malformed id2entry ID %s.%n",
465                           StaticUtils.bytesToHex(key.getData()));
466              }
467              continue;
468            }
469    
470            keyCount++;
471    
472            Entry entry;
473            try
474            {
475              entry = JebFormat.entryFromDatabase(data.getData(),
476                                     rootContainer.getCompressedSchema());
477            }
478            catch (Exception e)
479            {
480              errorCount++;
481              if (debugEnabled())
482              {
483                TRACER.debugCaught(DebugLogLevel.ERROR, e);
484    
485                TRACER.debugError("Malformed id2entry record for ID %d:%n%s%n",
486                           entryID.longValue(),
487                           StaticUtils.bytesToHex(data.getData()));
488              }
489              continue;
490            }
491    
492            verifyEntry(entryID, entry);
493          }
494          if (keyCount != storedEntryCount)
495          {
496            errorCount++;
497            if (debugEnabled())
498            {
499              TRACER.debugError("The stored entry count in id2entry (%d) does " +
500                  "not agree with the actual number of entry " +
501                  "records found (%d).%n", storedEntryCount, keyCount);
502            }
503          }
504        }
505        finally
506        {
507          cursor.close();
508        }
509      }
510    
511      /**
512       * Iterate through the entries in an index to perform a check for
513       * index cleanliness. For each ID in the index we check that the
514       * entry it refers to does indeed contain the expected value.
515       *
516       * @throws JebException If an error occurs in the JE backend.
517       * @throws DatabaseException If an error occurs in the JE database.
518       * @throws DirectoryException If an error occurs reading values in the index.
519       */
520      private void iterateIndex()
521          throws JebException, DatabaseException, DirectoryException
522      {
523        if (verifyDN2ID)
524        {
525          iterateDN2ID();
526        }
527        else if (verifyID2Children)
528        {
529          iterateID2Children();
530        }
531        else if (verifyID2Subtree)
532        {
533          iterateID2Subtree();
534        }
535        else
536        {
537          if(attrIndexList.size() > 0)
538          {
539            AttributeIndex attrIndex = attrIndexList.get(0);
540            iterateAttrIndex(attrIndex.getAttributeType(),
541                             attrIndex.equalityIndex, IndexType.EQ );
542            iterateAttrIndex(attrIndex.getAttributeType(),
543                             attrIndex.presenceIndex, IndexType.PRES);
544            iterateAttrIndex(attrIndex.getAttributeType(),
545                             attrIndex.substringIndex, IndexType.SUBSTRING);
546            iterateAttrIndex(attrIndex.getAttributeType(),
547                             attrIndex.orderingIndex, IndexType.ORDERING);
548            iterateAttrIndex(attrIndex.getAttributeType(),
549                             attrIndex.approximateIndex, IndexType.APPROXIMATE);
550          } else if(vlvIndexList.size() > 0)
551          {
552            iterateVLVIndex(vlvIndexList.get(0), true);
553          }
554        }
555      }
556    
557      /**
558       * Iterate through the entries in DN2ID to perform a check for
559       * index cleanliness.
560       *
561       * @throws DatabaseException If an error occurs in the JE database.
562       */
563      private void iterateDN2ID() throws DatabaseException
564      {
565        Cursor cursor = dn2id.openCursor(null, new CursorConfig());
566        try
567        {
568          DatabaseEntry key = new DatabaseEntry();
569          DatabaseEntry data = new DatabaseEntry();
570    
571          OperationStatus status;
572          for (status = cursor.getFirst(key, data, LockMode.DEFAULT);
573               status == OperationStatus.SUCCESS;
574               status = cursor.getNext(key, data, LockMode.DEFAULT))
575          {
576            keyCount++;
577    
578            DN dn;
579            try
580            {
581              dn = DN.decode(new ASN1OctetString(key.getData()));
582            }
583            catch (DirectoryException e)
584            {
585              errorCount++;
586              if (debugEnabled())
587              {
588                TRACER.debugCaught(DebugLogLevel.ERROR, e);
589    
590                TRACER.debugError("File dn2id has malformed key %s.%n",
591                           StaticUtils.bytesToHex(key.getData()));
592              }
593              continue;
594            }
595    
596            EntryID entryID;
597            try
598            {
599              entryID = new EntryID(data);
600            }
601            catch (Exception e)
602            {
603              errorCount++;
604              if (debugEnabled())
605              {
606                TRACER.debugCaught(DebugLogLevel.ERROR, e);
607    
608                TRACER.debugError("File dn2id has malformed ID for DN <%s>:%n%s%n",
609                           dn.toNormalizedString(),
610                           StaticUtils.bytesToHex(data.getData()));
611              }
612              continue;
613            }
614    
615            Entry entry;
616            try
617            {
618              entry = id2entry.get(null, entryID, LockMode.DEFAULT);
619            }
620            catch (Exception e)
621            {
622              errorCount++;
623              if (debugEnabled())
624              {
625                TRACER.debugCaught(DebugLogLevel.ERROR, e);
626              }
627              continue;
628            }
629    
630            if (entry == null)
631            {
632              errorCount++;
633              if (debugEnabled())
634              {
635                TRACER.debugError("File dn2id has DN <%s> referencing unknown " +
636                    "ID %d%n", dn.toNormalizedString(), entryID.longValue());
637              }
638            }
639            else
640            {
641              if (!entry.getDN().equals(dn))
642              {
643                errorCount++;
644                if (debugEnabled())
645                {
646                  TRACER.debugError("File dn2id has DN <%s> referencing entry " +
647                      "with wrong DN <%s>%n", dn.toNormalizedString(),
648                                              entry.getDN().toNormalizedString());
649                }
650              }
651            }
652          }
653        }
654        finally
655        {
656          cursor.close();
657        }
658      }
659    
660      /**
661       * Iterate through the entries in ID2Children to perform a check for
662       * index cleanliness.
663       *
664       * @throws JebException If an error occurs in the JE backend.
665       * @throws DatabaseException If an error occurs in the JE database.
666       */
667      private void iterateID2Children() throws JebException, DatabaseException
668      {
669        Cursor cursor = id2c.openCursor(null, new CursorConfig());
670        try
671        {
672          DatabaseEntry key = new DatabaseEntry();
673          DatabaseEntry data = new DatabaseEntry();
674    
675          OperationStatus status;
676          for (status = cursor.getFirst(key, data, LockMode.DEFAULT);
677               status == OperationStatus.SUCCESS;
678               status = cursor.getNext(key, data, LockMode.DEFAULT))
679          {
680            keyCount++;
681    
682            EntryID entryID;
683            try
684            {
685              entryID = new EntryID(key);
686            }
687            catch (Exception e)
688            {
689              errorCount++;
690              if (debugEnabled())
691              {
692                TRACER.debugCaught(DebugLogLevel.ERROR, e);
693    
694                TRACER.debugError("File id2children has malformed ID %s%n",
695                           StaticUtils.bytesToHex(key.getData()));
696              }
697              continue;
698            }
699    
700            EntryIDSet entryIDList;
701    
702            try
703            {
704              JebFormat.entryIDListFromDatabase(data.getData());
705              entryIDList = new EntryIDSet(key.getData(), data.getData());
706            }
707            catch (Exception e)
708            {
709              errorCount++;
710              if (debugEnabled())
711              {
712                TRACER.debugCaught(DebugLogLevel.ERROR, e);
713    
714                TRACER.debugError("File id2children has malformed ID list " +
715                    "for ID %s:%n%s%n", entryID,
716                                        StaticUtils.bytesToHex(data.getData()));
717              }
718              continue;
719            }
720    
721            updateIndexStats(entryIDList);
722    
723            if (entryIDList.isDefined())
724            {
725              Entry entry;
726              try
727              {
728                entry = id2entry.get(null, entryID, LockMode.DEFAULT);
729              }
730              catch (Exception e)
731              {
732                if (debugEnabled())
733                {
734                  TRACER.debugCaught(DebugLogLevel.ERROR, e);
735                }
736                errorCount++;
737                continue;
738              }
739    
740              if (entry == null)
741              {
742                errorCount++;
743                if (debugEnabled())
744                {
745                  TRACER.debugError("File id2children has unknown ID %d%n",
746                             entryID.longValue());
747                }
748                continue;
749              }
750    
751              for (EntryID id : entryIDList)
752              {
753                Entry childEntry;
754                try
755                {
756                  childEntry = id2entry.get(null, id, LockMode.DEFAULT);
757                }
758                catch (Exception e)
759                {
760                  if (debugEnabled())
761                  {
762                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
763                  }
764                  errorCount++;
765                  continue;
766                }
767    
768                if (childEntry == null)
769                {
770                  errorCount++;
771                  if (debugEnabled())
772                  {
773                    TRACER.debugError("File id2children has ID %d referencing " +
774                        "unknown ID %d%n", entryID.longValue(), id.longValue());
775                  }
776                  continue;
777                }
778    
779                if (!childEntry.getDN().isDescendantOf(entry.getDN()) ||
780                     childEntry.getDN().getNumComponents() !=
781                     entry.getDN().getNumComponents() + 1)
782                {
783                  errorCount++;
784                  if (debugEnabled())
785                  {
786                    TRACER.debugError("File id2children has ID %d with DN <%s> " +
787                        "referencing ID %d with non-child DN <%s>%n",
788                               entryID.longValue(), entry.getDN().toString(),
789                               id.longValue(), childEntry.getDN().toString());
790                  }
791                }
792              }
793            }
794          }
795        }
796        finally
797        {
798          cursor.close();
799        }
800      }
801    
802      /**
803       * Iterate through the entries in ID2Subtree to perform a check for
804       * index cleanliness.
805       *
806       * @throws JebException If an error occurs in the JE backend.
807       * @throws DatabaseException If an error occurs in the JE database.
808       */
809      private void iterateID2Subtree() throws JebException, DatabaseException
810      {
811        Cursor cursor = id2s.openCursor(null, new CursorConfig());
812        try
813        {
814          DatabaseEntry key = new DatabaseEntry();
815          DatabaseEntry data = new DatabaseEntry();
816    
817          OperationStatus status;
818          for (status = cursor.getFirst(key, data, LockMode.DEFAULT);
819               status == OperationStatus.SUCCESS;
820               status = cursor.getNext(key, data, LockMode.DEFAULT))
821          {
822            keyCount++;
823    
824            EntryID entryID;
825            try
826            {
827              entryID = new EntryID(key);
828            }
829            catch (Exception e)
830            {
831              errorCount++;
832              if (debugEnabled())
833              {
834                TRACER.debugCaught(DebugLogLevel.ERROR, e);
835    
836                TRACER.debugError("File id2subtree has malformed ID %s%n",
837                           StaticUtils.bytesToHex(key.getData()));
838              }
839              continue;
840            }
841    
842            EntryIDSet entryIDList;
843            try
844            {
845              JebFormat.entryIDListFromDatabase(data.getData());
846              entryIDList = new EntryIDSet(key.getData(), data.getData());
847            }
848            catch (Exception e)
849            {
850              errorCount++;
851              if (debugEnabled())
852              {
853                TRACER.debugCaught(DebugLogLevel.ERROR, e);
854    
855                TRACER.debugError("File id2subtree has malformed ID list " +
856                    "for ID %s:%n%s%n", entryID,
857                                        StaticUtils.bytesToHex(data.getData()));
858              }
859              continue;
860            }
861    
862            updateIndexStats(entryIDList);
863    
864            if (entryIDList.isDefined())
865            {
866              Entry entry;
867              try
868              {
869                entry = id2entry.get(null, entryID, LockMode.DEFAULT);
870              }
871              catch (Exception e)
872              {
873                if (debugEnabled())
874                {
875                  TRACER.debugCaught(DebugLogLevel.ERROR, e);
876                }
877                errorCount++;
878                continue;
879              }
880    
881              if (entry == null)
882              {
883                errorCount++;
884                if (debugEnabled())
885                {
886                  TRACER.debugError("File id2subtree has unknown ID %d%n",
887                             entryID.longValue());
888                }
889                continue;
890              }
891    
892              for (EntryID id : entryIDList)
893              {
894                Entry subordEntry;
895                try
896                {
897                  subordEntry = id2entry.get(null, id, LockMode.DEFAULT);
898                }
899                catch (Exception e)
900                {
901                  if (debugEnabled())
902                  {
903                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
904                  }
905                  errorCount++;
906                  continue;
907                }
908    
909                if (subordEntry == null)
910                {
911                  errorCount++;
912                  if (debugEnabled())
913                  {
914                    TRACER.debugError("File id2subtree has ID %d referencing " +
915                        "unknown ID %d%n", entryID.longValue(), id.longValue());
916                  }
917                  continue;
918                }
919    
920                if (!subordEntry.getDN().isDescendantOf(entry.getDN()))
921                {
922                  errorCount++;
923                  if (debugEnabled())
924                  {
925                    TRACER.debugError("File id2subtree has ID %d with DN <%s> " +
926                        "referencing ID %d with non-subordinate " +
927                        "DN <%s>%n",
928                               entryID.longValue(), entry.getDN().toString(),
929                               id.longValue(), subordEntry.getDN().toString());
930                  }
931                }
932              }
933            }
934          }
935        }
936        finally
937        {
938          cursor.close();
939        }
940      }
941    
942      /**
943       * Increment the counter for a key that has exceeded the
944       * entry limit. The counter gives the number of entries that have
945       * referenced the key.
946       *
947       * @param index The index containing the key.
948       * @param key A key that has exceeded the entry limit.
949       */
950      private void incrEntryLimitStats(Index index, byte[] key)
951      {
952        HashMap<ByteString,Long> hashMap = entryLimitMap.get(index);
953        if (hashMap == null)
954        {
955          hashMap = new HashMap<ByteString, Long>();
956          entryLimitMap.put(index, hashMap);
957        }
958        ByteString octetString = new ASN1OctetString(key);
959        Long counter = hashMap.get(octetString);
960        if (counter == null)
961        {
962          counter = 1L;
963        }
964        else
965        {
966          counter++;
967        }
968        hashMap.put(octetString, counter);
969      }
970    
971      /**
972       * Update the statistical information for an index record.
973       *
974       * @param entryIDSet The set of entry IDs for the index record.
975       */
976      private void updateIndexStats(EntryIDSet entryIDSet)
977      {
978        if (!entryIDSet.isDefined())
979        {
980          entryLimitExceededCount++;
981          multiReferenceCount++;
982        }
983        else
984        {
985          if (entryIDSet.size() > 1)
986          {
987            multiReferenceCount++;
988          }
989          entryReferencesCount += entryIDSet.size();
990          maxEntryPerValue = Math.max(maxEntryPerValue, entryIDSet.size());
991        }
992      }
993    
994      /**
995       * Iterate through the entries in a VLV index to perform a check for index
996       * cleanliness.
997       *
998       * @param vlvIndex The VLV index to perform the check against.
999       * @param verifyID True to verify the IDs against id2entry.
1000       * @throws JebException If an error occurs in the JE backend.
1001       * @throws DatabaseException If an error occurs in the JE database.
1002       * @throws DirectoryException If an error occurs reading values in the index.
1003       */
1004      private void iterateVLVIndex(VLVIndex vlvIndex, boolean verifyID)
1005          throws JebException, DatabaseException, DirectoryException
1006      {
1007        if(vlvIndex == null)
1008        {
1009          return;
1010        }
1011    
1012        Cursor cursor = vlvIndex.openCursor(null, new CursorConfig());
1013        try
1014        {
1015          DatabaseEntry key = new DatabaseEntry();
1016          OperationStatus status;
1017          LockMode lockMode = LockMode.DEFAULT;
1018          DatabaseEntry data = new DatabaseEntry();
1019    
1020          status = cursor.getFirst(key, data, lockMode);
1021          SortValues lastValues = null;
1022          while(status == OperationStatus.SUCCESS)
1023          {
1024            SortValuesSet sortValuesSet =
1025                new SortValuesSet(key.getData(), data.getData(), vlvIndex);
1026            for(int i = 0; i < sortValuesSet.getEntryIDs().length; i++)
1027            {
1028              keyCount++;
1029              SortValues values = sortValuesSet.getSortValues(i);
1030              if(lastValues != null && lastValues.compareTo(values) >= 1)
1031              {
1032                // Make sure the values is larger then the previous one.
1033                if(debugEnabled())
1034                {
1035                  TRACER.debugError("Values %s and %s are incorrectly ordered",
1036                                    lastValues, values, keyDump(vlvIndex,
1037                                              sortValuesSet.getKeySortValues()));
1038                }
1039                errorCount++;
1040              }
1041              if(i == sortValuesSet.getEntryIDs().length - 1 &&
1042                  key.getData().length != 0)
1043              {
1044                // If this is the last one in a bounded set, make sure it is the
1045                // same as the database key.
1046                byte[] encodedKey = vlvIndex.encodeKey(values.getEntryID(),
1047                                                       values.getValues());
1048                if(!Arrays.equals(key.getData(), encodedKey))
1049                {
1050                  if(debugEnabled())
1051                  {
1052                    TRACER.debugError("Incorrect key for SortValuesSet in VLV " +
1053                        "index %s. Last values bytes %s, Key bytes %s",
1054                                      vlvIndex.getName(), encodedKey, key);
1055                  }
1056                  errorCount++;
1057                }
1058              }
1059              lastValues = values;
1060    
1061              if(verifyID)
1062              {
1063                Entry entry;
1064                EntryID id = new EntryID(values.getEntryID());
1065                try
1066                {
1067                  entry = id2entry.get(null, id, LockMode.DEFAULT);
1068                }
1069                catch (Exception e)
1070                {
1071                  if (debugEnabled())
1072                  {
1073                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
1074                  }
1075                  errorCount++;
1076                  continue;
1077                }
1078    
1079                if (entry == null)
1080                {
1081                  errorCount++;
1082                  if (debugEnabled())
1083                  {
1084                    TRACER.debugError("Reference to unknown ID %d%n%s",
1085                                      id.longValue(),
1086                                      keyDump(vlvIndex,
1087                                              sortValuesSet.getKeySortValues()));
1088                  }
1089                  continue;
1090                }
1091    
1092                SortValues entryValues =
1093                    new SortValues(id, entry, vlvIndex.sortOrder);
1094                if(entryValues.compareTo(values) != 0)
1095                {
1096                  errorCount++;
1097                  if(debugEnabled())
1098                  {
1099                    TRACER.debugError("Reference to entry ID %d " +
1100                        "which does not match the values%n%s",
1101                                      id.longValue(),
1102                                      keyDump(vlvIndex,
1103                                              sortValuesSet.getKeySortValues()));
1104                  }
1105                }
1106              }
1107            }
1108            status = cursor.getNext(key, data, lockMode);
1109          }
1110        }
1111        finally
1112        {
1113          cursor.close();
1114        }
1115      }
1116    
1117      /**
1118       * Iterate through the entries in an attribute index to perform a check for
1119       * index cleanliness.
1120       * @param attrType The attribute type of the index to be checked.
1121       * @param index The index database to be checked.
1122       * @param indexType Type of the index (ie, SUBSTRING, ORDERING)
1123       * @throws JebException If an error occurs in the JE backend.
1124       * @throws DatabaseException If an error occurs in the JE database.
1125       */
1126      private void iterateAttrIndex(AttributeType attrType,
1127              Index index, IndexType indexType)
1128           throws JebException, DatabaseException
1129      {
1130        if (index == null)
1131        {
1132          return;
1133        }
1134    
1135        Cursor cursor = index.openCursor(null, new CursorConfig());
1136        try
1137        {
1138          DatabaseEntry key = new DatabaseEntry();
1139          DatabaseEntry data = new DatabaseEntry();
1140    
1141          OrderingMatchingRule orderingMatchingRule =
1142              attrType.getOrderingMatchingRule();
1143          ApproximateMatchingRule approximateMatchingRule =
1144              attrType.getApproximateMatchingRule();
1145          ASN1OctetString previousValue = null;
1146    
1147          OperationStatus status;
1148          for (status = cursor.getFirst(key, data, LockMode.DEFAULT);
1149               status == OperationStatus.SUCCESS;
1150               status = cursor.getNext(key, data, LockMode.DEFAULT))
1151          {
1152            keyCount++;
1153    
1154            EntryIDSet entryIDList;
1155            try
1156            {
1157              JebFormat.entryIDListFromDatabase(data.getData());
1158              entryIDList = new EntryIDSet(key.getData(), data.getData());
1159            }
1160            catch (Exception e)
1161            {
1162              errorCount++;
1163              if (debugEnabled())
1164              {
1165                TRACER.debugCaught(DebugLogLevel.ERROR, e);
1166    
1167                TRACER.debugError("Malformed ID list: %s%n%s",
1168                           StaticUtils.bytesToHex(data.getData()),
1169                           keyDump(index, key.getData()));
1170              }
1171              continue;
1172            }
1173    
1174            updateIndexStats(entryIDList);
1175    
1176            if (entryIDList.isDefined())
1177            {
1178              byte[] value = key.getData();
1179              SearchFilter sf;
1180              AttributeValue assertionValue;
1181    
1182              switch (indexType)
1183              {
1184                case SUBSTRING:
1185                  ArrayList<ByteString> subAnyElements =
1186                       new ArrayList<ByteString>(1);
1187                  subAnyElements.add(new ASN1OctetString(value));
1188    
1189                  sf = SearchFilter.createSubstringFilter(attrType,null,
1190                                                          subAnyElements,null);
1191                  break;
1192                case ORDERING:
1193                  // Ordering index checking is two fold:
1194                  // 1. Make sure the entry has an attribute value that is the same
1195                  //    as the key. This is done by falling through to the next
1196                  //    case and create an equality filter.
1197                  // 2. Make sure the key value is greater then the previous key
1198                  //    value.
1199                  assertionValue =
1200                      new AttributeValue(attrType, new ASN1OctetString(value));
1201    
1202                  sf = SearchFilter.createEqualityFilter(attrType,assertionValue);
1203    
1204                  if(orderingMatchingRule != null && previousValue != null)
1205                  {
1206                    ASN1OctetString thisValue = new ASN1OctetString(value);
1207                    int order = orderingMatchingRule.compareValues(thisValue,
1208                                                                   previousValue);
1209                    if(order > 0)
1210                    {
1211                      errorCount++;
1212                      if(debugEnabled())
1213                      {
1214                        TRACER.debugError("Reversed ordering of index keys " +
1215                            "(keys dumped in the order found in database)%n" +
1216                            "Key 1:%n%s%nKey 2:%n%s",
1217                                   keyDump(index, thisValue.value()),
1218                                   keyDump(index,previousValue.value()));
1219                      }
1220                      continue;
1221                    }
1222                    else if(order == 0)
1223                    {
1224                      errorCount++;
1225                      if(debugEnabled())
1226                      {
1227                        TRACER.debugError("Duplicate index keys%nKey 1:%n%s%n" +
1228                            "Key2:%n%s", keyDump(index, thisValue.value()),
1229                                         keyDump(index,previousValue.value()));
1230                      }
1231                      continue;
1232                    }
1233                    else
1234                    {
1235                      previousValue = thisValue;
1236                    }
1237                  }
1238                  break;
1239                case EQ:
1240                  assertionValue =
1241                       new AttributeValue(attrType, new ASN1OctetString(value));
1242    
1243                  sf = SearchFilter.createEqualityFilter(attrType,assertionValue);
1244                  break;
1245    
1246                case PRES:
1247                  sf = SearchFilter.createPresenceFilter(attrType);
1248                  break;
1249    
1250                case APPROXIMATE:
1251                  // This must be handled differently since we can't use a search
1252                  // filter to see if the key matches.
1253                  sf = null;
1254                  break;
1255    
1256                default:
1257                  errorCount++;
1258                  if (debugEnabled())
1259                  {
1260                    TRACER.debugError("Malformed value%n%s", keyDump(index, value));
1261                  }
1262                  continue;
1263              }
1264    
1265              EntryID prevID = null;
1266              for (EntryID id : entryIDList)
1267              {
1268                if (prevID != null && id.equals(prevID))
1269                {
1270                  if (debugEnabled())
1271                  {
1272                    TRACER.debugError("Duplicate reference to ID %d%n%s",
1273                               id.longValue(), keyDump(index, key.getData()));
1274                  }
1275                }
1276                prevID = id;
1277    
1278                Entry entry;
1279                try
1280                {
1281                  entry = id2entry.get(null, id, LockMode.DEFAULT);
1282                }
1283                catch (Exception e)
1284                {
1285                  if (debugEnabled())
1286                  {
1287                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
1288                  }
1289                  errorCount++;
1290                  continue;
1291                }
1292    
1293                if (entry == null)
1294                {
1295                  errorCount++;
1296                  if (debugEnabled())
1297                  {
1298                    TRACER.debugError("Reference to unknown ID %d%n%s",
1299                               id.longValue(), keyDump(index, key.getData()));
1300                  }
1301                  continue;
1302                }
1303    
1304                try
1305                {
1306                  boolean match = false;
1307                  if(indexType != IndexType.APPROXIMATE)
1308                  {
1309                    match = sf.matchesEntry(entry);
1310                  }
1311                  else
1312                  {
1313                    ByteString normalizedValue = new ASN1OctetString(value);
1314                    List<Attribute> attrs = entry.getAttribute(attrType);
1315                    if ((attrs != null) && (!attrs.isEmpty()))
1316                    {
1317                      for (Attribute a : attrs)
1318                      {
1319                        for (AttributeValue v : a.getValues())
1320                        {
1321                          ByteString nv =
1322                              approximateMatchingRule.normalizeValue(v.getValue());
1323                          match = approximateMatchingRule.
1324                              approximatelyMatch(nv, normalizedValue);
1325                          if(match)
1326                          {
1327                            break;
1328                          }
1329                        }
1330                        if(match)
1331                        {
1332                          break;
1333                        }
1334                      }
1335                    }
1336                  }
1337    
1338                  if (!match)
1339                  {
1340                    errorCount++;
1341                    if (debugEnabled())
1342                    {
1343                      TRACER.debugError("Reference to entry " +
1344                          "<%s> which does not match the value%n%s",
1345                                 entry.getDN(), keyDump(index, value));
1346                    }
1347                  }
1348                }
1349                catch (DirectoryException e)
1350                {
1351                  if (debugEnabled())
1352                  {
1353                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
1354                  }
1355                }
1356              }
1357            }
1358          }
1359        }
1360        finally
1361        {
1362          cursor.close();
1363        }
1364      }
1365    
1366      /**
1367       * Check that an index is complete for a given entry.
1368       *
1369       * @param entryID The entry ID.
1370       * @param entry The entry to be checked.
1371       */
1372      private void verifyEntry(EntryID entryID, Entry entry)
1373      {
1374        if (verifyDN2ID)
1375        {
1376          verifyDN2ID(entryID, entry);
1377        }
1378        if (verifyID2Children)
1379        {
1380          verifyID2Children(entryID, entry);
1381        }
1382        if (verifyID2Subtree)
1383        {
1384          verifyID2Subtree(entryID, entry);
1385        }
1386        verifyIndex(entryID, entry);
1387      }
1388    
1389      /**
1390       * Check that the DN2ID index is complete for a given entry.
1391       *
1392       * @param entryID The entry ID.
1393       * @param entry The entry to be checked.
1394       */
1395      private void verifyDN2ID(EntryID entryID, Entry entry)
1396      {
1397        DN dn = entry.getDN();
1398    
1399        // Check the ID is in dn2id with the correct DN.
1400        try
1401        {
1402          EntryID id = dn2id.get(null, dn, LockMode.DEFAULT);
1403          if (id == null)
1404          {
1405            if (debugEnabled())
1406            {
1407              TRACER.debugError("File dn2id is missing key %s.%n",
1408                         dn.toNormalizedString());
1409            }
1410            errorCount++;
1411          }
1412          else if (!id.equals(entryID))
1413          {
1414            if (debugEnabled())
1415            {
1416              TRACER.debugError("File dn2id has ID %d instead of %d for key %s.%n",
1417                         id.longValue(),
1418                         entryID.longValue(),
1419                         dn.toNormalizedString());
1420            }
1421            errorCount++;
1422          }
1423        }
1424        catch (Exception e)
1425        {
1426          if (debugEnabled())
1427          {
1428            TRACER.debugCaught(DebugLogLevel.ERROR, e);
1429    
1430            TRACER.debugError("File dn2id has error reading key %s: %s.%n",
1431                       dn.toNormalizedString(),
1432                       e.getMessage());
1433          }
1434          errorCount++;
1435        }
1436    
1437        // Check the parent DN is in dn2id.
1438        DN parentDN = getParent(dn);
1439        if (parentDN != null)
1440        {
1441          try
1442          {
1443            EntryID id = dn2id.get(null, parentDN, LockMode.DEFAULT);
1444            if (id == null)
1445            {
1446              if (debugEnabled())
1447              {
1448                TRACER.debugError("File dn2id is missing key %s.%n",
1449                           parentDN.toNormalizedString());
1450              }
1451              errorCount++;
1452            }
1453          }
1454          catch (Exception e)
1455          {
1456            if (debugEnabled())
1457            {
1458              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1459    
1460              TRACER.debugError("File dn2id has error reading key %s: %s.%n",
1461                         parentDN.toNormalizedString(),
1462                         e.getMessage());
1463            }
1464            errorCount++;
1465          }
1466        }
1467      }
1468    
1469      /**
1470       * Check that the ID2Children index is complete for a given entry.
1471       *
1472       * @param entryID The entry ID.
1473       * @param entry The entry to be checked.
1474       */
1475      private void verifyID2Children(EntryID entryID, Entry entry)
1476      {
1477        DN dn = entry.getDN();
1478    
1479        DN parentDN = getParent(dn);
1480        if (parentDN != null)
1481        {
1482          EntryID parentID = null;
1483          try
1484          {
1485            parentID = dn2id.get(null, parentDN, LockMode.DEFAULT);
1486            if (parentID == null)
1487            {
1488              if (debugEnabled())
1489              {
1490                TRACER.debugError("File dn2id is missing key %s.%n",
1491                           parentDN.toNormalizedString());
1492              }
1493              errorCount++;
1494            }
1495          }
1496          catch (Exception e)
1497          {
1498            if (debugEnabled())
1499            {
1500              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1501    
1502              TRACER.debugError("File dn2id has error reading key %s: %s.",
1503                         parentDN.toNormalizedString(),
1504                         e.getMessage());
1505            }
1506            errorCount++;
1507          }
1508          if (parentID != null)
1509          {
1510            try
1511            {
1512              ConditionResult cr;
1513              cr = id2c.containsID(null, parentID.getDatabaseEntry(), entryID);
1514              if (cr == ConditionResult.FALSE)
1515              {
1516                if (debugEnabled())
1517                {
1518                  TRACER.debugError("File id2children is missing ID %d " +
1519                      "for key %d.%n",
1520                             entryID.longValue(), parentID.longValue());
1521                }
1522                errorCount++;
1523              }
1524              else if (cr == ConditionResult.UNDEFINED)
1525              {
1526                incrEntryLimitStats(id2c, parentID.getDatabaseEntry().getData());
1527              }
1528            }
1529            catch (DatabaseException e)
1530            {
1531              if (debugEnabled())
1532              {
1533                TRACER.debugCaught(DebugLogLevel.ERROR, e);
1534    
1535                TRACER.debugError("File id2children has error reading key %d: %s.",
1536                           parentID.longValue(), e.getMessage());
1537              }
1538              errorCount++;
1539            }
1540          }
1541        }
1542      }
1543    
1544      /**
1545       * Check that the ID2Subtree index is complete for a given entry.
1546       *
1547       * @param entryID The entry ID.
1548       * @param entry The entry to be checked.
1549       */
1550      private void verifyID2Subtree(EntryID entryID, Entry entry)
1551      {
1552        for (DN dn = getParent(entry.getDN()); dn != null; dn = getParent(dn))
1553        {
1554          EntryID id = null;
1555          try
1556          {
1557            id = dn2id.get(null, dn, LockMode.DEFAULT);
1558            if (id == null)
1559            {
1560              if (debugEnabled())
1561              {
1562                TRACER.debugError("File dn2id is missing key %s.%n",
1563                           dn.toNormalizedString());
1564              }
1565              errorCount++;
1566            }
1567          }
1568          catch (Exception e)
1569          {
1570            if (debugEnabled())
1571            {
1572              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1573    
1574              TRACER.debugError("File dn2id has error reading key %s: %s.%n",
1575                         dn.toNormalizedString(),
1576                         e.getMessage());
1577            }
1578            errorCount++;
1579          }
1580          if (id != null)
1581          {
1582            try
1583            {
1584              ConditionResult cr;
1585              cr = id2s.containsID(null, id.getDatabaseEntry(), entryID);
1586              if (cr == ConditionResult.FALSE)
1587              {
1588                if (debugEnabled())
1589                {
1590                  TRACER.debugError("File id2subtree is missing ID %d " +
1591                      "for key %d.%n",
1592                             entryID.longValue(), id.longValue());
1593                }
1594                errorCount++;
1595              }
1596              else if (cr == ConditionResult.UNDEFINED)
1597              {
1598                incrEntryLimitStats(id2s, id.getDatabaseEntry().getData());
1599              }
1600            }
1601            catch (DatabaseException e)
1602            {
1603              if (debugEnabled())
1604              {
1605                TRACER.debugCaught(DebugLogLevel.ERROR, e);
1606    
1607                TRACER.debugError("File id2subtree has error reading key %d: %s.%n",
1608                           id.longValue(), e.getMessage());
1609              }
1610              errorCount++;
1611            }
1612          }
1613        }
1614      }
1615    
1616      /**
1617       * Construct a printable string from a raw key value.
1618       *
1619       * @param index The index database containing the key value.
1620       * @param keyBytes The bytes of the key.
1621       * @return A string that may be logged or printed.
1622       */
1623      private String keyDump(Index index, byte[] keyBytes)
1624      {
1625    /*
1626        String str;
1627        try
1628        {
1629          str = new String(keyBytes, "UTF-8");
1630        }
1631        catch (UnsupportedEncodingException e)
1632        {
1633          str = StaticUtils.bytesToHex(keyBytes);
1634        }
1635        return str;
1636    */
1637        StringBuilder buffer = new StringBuilder(128);
1638        buffer.append("File: ");
1639        buffer.append(index.toString());
1640        buffer.append(ServerConstants.EOL);
1641        buffer.append("Key:");
1642        buffer.append(ServerConstants.EOL);
1643        StaticUtils.byteArrayToHexPlusAscii(buffer, keyBytes, 6);
1644        return buffer.toString();
1645      }
1646    
1647      /**
1648       * Construct a printable string from a raw key value.
1649       *
1650       * @param vlvIndex The vlvIndex database containing the key value.
1651       * @param keySortValues THe sort values that is being used as the key.
1652       * @return A string that may be logged or printed.
1653       */
1654      private String keyDump(VLVIndex vlvIndex, SortValues keySortValues)
1655      {
1656    /*
1657        String str;
1658        try
1659        {
1660          str = new String(keyBytes, "UTF-8");
1661        }
1662        catch (UnsupportedEncodingException e)
1663        {
1664          str = StaticUtils.bytesToHex(keyBytes);
1665        }
1666        return str;
1667    */
1668        StringBuilder buffer = new StringBuilder(128);
1669        buffer.append("File: ");
1670        buffer.append(vlvIndex.toString());
1671        buffer.append(ServerConstants.EOL);
1672        buffer.append("Key (last sort values):");
1673        if(keySortValues == null)
1674        {
1675          buffer.append("UNBOUNDED (0x00)");
1676        }
1677        else
1678        {
1679          buffer.append(keySortValues.toString());
1680        }
1681        return buffer.toString();
1682      }
1683    
1684      /**
1685       * Check that an attribute index is complete for a given entry.
1686       *
1687       * @param entryID The entry ID.
1688       * @param entry The entry to be checked.
1689       */
1690      private void verifyIndex(EntryID entryID, Entry entry)
1691      {
1692        for (AttributeIndex attrIndex : attrIndexList)
1693        {
1694          try
1695          {
1696            List<Attribute> attrList =
1697                 entry.getAttribute(attrIndex.getAttributeType());
1698            if (attrList != null)
1699            {
1700              verifyAttribute(attrIndex, entryID, attrList);
1701            }
1702          }
1703          catch (DirectoryException e)
1704          {
1705            if (debugEnabled())
1706            {
1707              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1708    
1709              TRACER.debugError("Error normalizing values of attribute %s in " +
1710                  "entry <%s>: %s.%n",
1711                         attrIndex.getAttributeType().toString(),
1712                         entry.getDN().toString(),
1713                         String.valueOf(e.getMessageObject()));
1714            }
1715          }
1716        }
1717    
1718        for (VLVIndex vlvIndex : vlvIndexList)
1719        {
1720          try
1721          {
1722            if(vlvIndex.shouldInclude(entry))
1723            {
1724              if(!vlvIndex.containsValues(null, entryID.longValue(),
1725                                      vlvIndex.getSortValues(entry)))
1726              {
1727                if(debugEnabled())
1728                {
1729                  TRACER.debugError("Missing entry %s in VLV index %s",
1730                                    entry.getDN().toString(),
1731                                    vlvIndex.getName());
1732                }
1733                errorCount++;
1734              }
1735            }
1736          }
1737          catch (DirectoryException e)
1738          {
1739            if (debugEnabled())
1740            {
1741              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1742    
1743              TRACER.debugError("Error checking entry %s against filter or " +
1744                  "base DN for VLV index %s: %s",
1745                         entry.getDN().toString(),
1746                         vlvIndex.getName(),
1747                         String.valueOf(e.getMessageObject()));
1748            }
1749            errorCount++;
1750          }
1751          catch (DatabaseException e)
1752          {
1753            if (debugEnabled())
1754            {
1755              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1756    
1757              TRACER.debugError("Error reading VLV index %s for entry %s: %s",
1758                         vlvIndex.getName(),
1759                         entry.getDN().toString(),
1760                         StaticUtils.getBacktrace(e));
1761            }
1762            errorCount++;
1763          }
1764          catch (JebException e)
1765          {
1766            if (debugEnabled())
1767            {
1768              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1769    
1770              TRACER.debugError("Error reading VLV index %s for entry %s: %s",
1771                         vlvIndex.getName(),
1772                         entry.getDN().toString(),
1773                         StaticUtils.getBacktrace(e));
1774            }
1775            errorCount++;
1776          }
1777        }
1778      }
1779    
1780      /**
1781       * Check that an attribute index is complete for a given attribute.
1782       *
1783       * @param attrIndex The attribute index to be checked.
1784       * @param entryID The entry ID.
1785       * @param attrList The attribute to be checked.
1786       * @throws DirectoryException If a Directory Server error occurs.
1787       */
1788      private void verifyAttribute(AttributeIndex attrIndex, EntryID entryID,
1789                                  List<Attribute> attrList)
1790           throws DirectoryException
1791      {
1792        Transaction txn = null;
1793        Index equalityIndex = attrIndex.equalityIndex;
1794        Index presenceIndex = attrIndex.presenceIndex;
1795        Index substringIndex = attrIndex.substringIndex;
1796        Index orderingIndex = attrIndex.orderingIndex;
1797        Index approximateIndex = attrIndex.approximateIndex;
1798        DatabaseEntry presenceKey = AttributeIndex.presenceKey;
1799    
1800        // Presence index.
1801        if (!attrList.isEmpty() && presenceIndex != null)
1802        {
1803          try
1804          {
1805            ConditionResult cr;
1806            cr = presenceIndex.containsID(txn, presenceKey, entryID);
1807            if (cr == ConditionResult.FALSE)
1808            {
1809              if (debugEnabled())
1810              {
1811                TRACER.debugError("Missing ID %d%n%s",
1812                           entryID.longValue(),
1813                           keyDump(presenceIndex, presenceKey.getData()));
1814              }
1815              errorCount++;
1816            }
1817            else if (cr == ConditionResult.UNDEFINED)
1818            {
1819              incrEntryLimitStats(presenceIndex, presenceKey.getData());
1820            }
1821          }
1822          catch (DatabaseException e)
1823          {
1824            if (debugEnabled())
1825            {
1826              TRACER.debugCaught(DebugLogLevel.ERROR, e);
1827    
1828              TRACER.debugError("Error reading database: %s%n%s",
1829                         e.getMessage(),
1830                         keyDump(presenceIndex, presenceKey.getData()));
1831            }
1832            errorCount++;
1833          }
1834        }
1835    
1836        if (attrList != null)
1837        {
1838          for (Attribute attr : attrList)
1839          {
1840            LinkedHashSet<AttributeValue> values = attr.getValues();
1841            for (AttributeValue value : values)
1842            {
1843              byte[] normalizedBytes = value.getNormalizedValue().value();
1844    
1845              // Equality index.
1846              if (equalityIndex != null)
1847              {
1848                DatabaseEntry key = new DatabaseEntry(normalizedBytes);
1849                try
1850                {
1851                  ConditionResult cr;
1852                  cr = equalityIndex.containsID(txn, key, entryID);
1853                  if (cr == ConditionResult.FALSE)
1854                  {
1855                    if (debugEnabled())
1856                    {
1857                      TRACER.debugError("Missing ID %d%n%s",
1858                                 entryID.longValue(),
1859                                 keyDump(equalityIndex, normalizedBytes));
1860                    }
1861                    errorCount++;
1862                  }
1863                  else if (cr == ConditionResult.UNDEFINED)
1864                  {
1865                    incrEntryLimitStats(equalityIndex, normalizedBytes);
1866                  }
1867                }
1868                catch (DatabaseException e)
1869                {
1870                  if (debugEnabled())
1871                  {
1872                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
1873    
1874                    TRACER.debugError("Error reading database: %s%n%s",
1875                               e.getMessage(),
1876                               keyDump(equalityIndex, normalizedBytes));
1877                  }
1878                  errorCount++;
1879                }
1880              }
1881    
1882              // Substring index.
1883              if (substringIndex != null)
1884              {
1885                Set<ByteString> keyBytesSet =
1886                     attrIndex.substringKeys(normalizedBytes);
1887                DatabaseEntry key = new DatabaseEntry();
1888                for (ByteString keyBytes : keyBytesSet)
1889                {
1890                  key.setData(keyBytes.value());
1891                  try
1892                  {
1893                    ConditionResult cr;
1894                    cr = substringIndex.containsID(txn, key, entryID);
1895                    if (cr == ConditionResult.FALSE)
1896                    {
1897                      if (debugEnabled())
1898                      {
1899                        TRACER.debugError("Missing ID %d%n%s",
1900                                   entryID.longValue(),
1901                                   keyDump(substringIndex, key.getData()));
1902                      }
1903                      errorCount++;
1904                    }
1905                    else if (cr == ConditionResult.UNDEFINED)
1906                    {
1907                      incrEntryLimitStats(substringIndex, key.getData());
1908                    }
1909                  }
1910                  catch (DatabaseException e)
1911                  {
1912                    if (debugEnabled())
1913                    {
1914                      TRACER.debugCaught(DebugLogLevel.ERROR, e);
1915    
1916                      TRACER.debugError("Error reading database: %s%n%s",
1917                                 e.getMessage(),
1918                                 keyDump(substringIndex, key.getData()));
1919                    }
1920                    errorCount++;
1921                  }
1922                }
1923              }
1924    
1925              // Ordering index.
1926              if (orderingIndex != null)
1927              {
1928                // Use the ordering matching rule to normalize the value.
1929                OrderingMatchingRule orderingRule =
1930                     attr.getAttributeType().getOrderingMatchingRule();
1931    
1932                normalizedBytes =
1933                     orderingRule.normalizeValue(value.getValue()).value();
1934    
1935                DatabaseEntry key = new DatabaseEntry(normalizedBytes);
1936                try
1937                {
1938                  ConditionResult cr;
1939                  cr = orderingIndex.containsID(txn, key, entryID);
1940                  if (cr == ConditionResult.FALSE)
1941                  {
1942                    if (debugEnabled())
1943                    {
1944                      TRACER.debugError("Missing ID %d%n%s",
1945                                 entryID.longValue(),
1946                                 keyDump(orderingIndex, normalizedBytes));
1947                    }
1948                    errorCount++;
1949                  }
1950                  else if (cr == ConditionResult.UNDEFINED)
1951                  {
1952                    incrEntryLimitStats(orderingIndex, normalizedBytes);
1953                  }
1954                }
1955                catch (DatabaseException e)
1956                {
1957                  if (debugEnabled())
1958                  {
1959                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
1960    
1961                    TRACER.debugError("Error reading database: %s%n%s",
1962                               e.getMessage(),
1963                               keyDump(orderingIndex, normalizedBytes));
1964                  }
1965                  errorCount++;
1966                }
1967              }
1968              // Approximate index.
1969              if (approximateIndex != null)
1970              {
1971                // Use the approximate matching rule to normalize the value.
1972                ApproximateMatchingRule approximateRule =
1973                    attr.getAttributeType().getApproximateMatchingRule();
1974    
1975                normalizedBytes =
1976                    approximateRule.normalizeValue(value.getValue()).value();
1977    
1978                DatabaseEntry key = new DatabaseEntry(normalizedBytes);
1979                try
1980                {
1981                  ConditionResult cr;
1982                  cr = approximateIndex.containsID(txn, key, entryID);
1983                  if (cr == ConditionResult.FALSE)
1984                  {
1985                    if (debugEnabled())
1986                    {
1987                      TRACER.debugError("Missing ID %d%n%s",
1988                                 entryID.longValue(),
1989                                 keyDump(orderingIndex, normalizedBytes));
1990                    }
1991                    errorCount++;
1992                  }
1993                  else if (cr == ConditionResult.UNDEFINED)
1994                  {
1995                    incrEntryLimitStats(orderingIndex, normalizedBytes);
1996                  }
1997                }
1998                catch (DatabaseException e)
1999                {
2000                  if (debugEnabled())
2001                  {
2002                    TRACER.debugCaught(DebugLogLevel.ERROR, e);
2003    
2004                    TRACER.debugError("Error reading database: %s%n%s",
2005                               e.getMessage(),
2006                               keyDump(approximateIndex, normalizedBytes));
2007                  }
2008                  errorCount++;
2009                }
2010              }
2011            }
2012          }
2013        }
2014      }
2015    
2016      /**
2017       * Get the parent DN of a given DN.
2018       *
2019       * @param dn The DN.
2020       * @return The parent DN or null if the given DN is a base DN.
2021       */
2022      private DN getParent(DN dn)
2023      {
2024        if (dn.equals(verifyConfig.getBaseDN()))
2025        {
2026          return null;
2027        }
2028        return dn.getParentDNInSuffix();
2029      }
2030    
2031      /**
2032       * This class reports progress of the verify job at fixed intervals.
2033       */
2034      class ProgressTask extends TimerTask
2035      {
2036        /**
2037         * The total number of records to process.
2038         */
2039        private long totalCount;
2040    
2041        /**
2042         * The number of records that had been processed at the time of the
2043         * previous progress report.
2044         */
2045        private long previousCount = 0;
2046    
2047        /**
2048         * The time in milliseconds of the previous progress report.
2049         */
2050        private long previousTime;
2051    
2052        /**
2053         * The environment statistics at the time of the previous report.
2054         */
2055        private EnvironmentStats prevEnvStats;
2056    
2057        /**
2058         * The number of bytes in a megabyte.
2059         * Note that 1024*1024 bytes may eventually become known as a mebibyte(MiB).
2060         */
2061        private static final int bytesPerMegabyte = 1024*1024;
2062    
2063        /**
2064         * Create a new verify progress task.
2065         * @throws DatabaseException An error occurred while accessing the JE
2066         * database.
2067         */
2068        public ProgressTask() throws DatabaseException
2069        {
2070          previousTime = System.currentTimeMillis();
2071          prevEnvStats =
2072              rootContainer.getEnvironmentStats(new StatsConfig());
2073          totalCount = rootContainer.getEntryContainer(
2074            verifyConfig.getBaseDN()).getEntryCount();
2075        }
2076    
2077        /**
2078         * The action to be performed by this timer task.
2079         */
2080        public void run()
2081        {
2082          long latestCount = keyCount;
2083          long deltaCount = (latestCount - previousCount);
2084          long latestTime = System.currentTimeMillis();
2085          long deltaTime = latestTime - previousTime;
2086    
2087          if (deltaTime == 0)
2088          {
2089            return;
2090          }
2091    
2092          float rate = 1000f*deltaCount / deltaTime;
2093    
2094          Message message = NOTE_JEB_VERIFY_PROGRESS_REPORT.get(
2095            latestCount, totalCount, errorCount, rate);
2096          logError(message);
2097    
2098          try
2099          {
2100            Runtime runtime = Runtime.getRuntime();
2101            long freeMemory = runtime.freeMemory() / bytesPerMegabyte;
2102    
2103            EnvironmentStats envStats =
2104                rootContainer.getEnvironmentStats(new StatsConfig());
2105            long nCacheMiss =
2106                 envStats.getNCacheMiss() - prevEnvStats.getNCacheMiss();
2107    
2108            float cacheMissRate = 0;
2109            if (deltaCount > 0)
2110            {
2111              cacheMissRate = nCacheMiss/(float)deltaCount;
2112            }
2113    
2114            message = INFO_JEB_VERIFY_CACHE_AND_MEMORY_REPORT.get(
2115                freeMemory, cacheMissRate);
2116            logError(message);
2117    
2118            prevEnvStats = envStats;
2119          }
2120          catch (DatabaseException e)
2121          {
2122            if (debugEnabled())
2123            {
2124              TRACER.debugCaught(DebugLogLevel.ERROR, e);
2125            }
2126          }
2127    
2128    
2129          previousCount = latestCount;
2130          previousTime = latestTime;
2131        }
2132      }
2133    
2134        /**
2135         * Adds an attribute of type t and value v to the statEntry, only if the
2136         * statEntry is not null.
2137         * @param statEntry passed in from backentryImpl.verifyBackend.
2138         * @param t String to be used as the attribute type.
2139         * @param v String to be used as the attribute value.
2140         */
2141        private void addStatEntry(Entry statEntry, String t, String v)
2142        {
2143            if (statEntry != null)
2144            {
2145                Attribute a = new Attribute(t, v);
2146                statEntry.addAttribute(a, null);
2147            }
2148        }
2149    }