external-software/github_OpenIdentityPlatform_OpenDJ.git

			@@ -26,641 +26,38 @@
			*/
			package org.opends.server.backends.pluggable;

			import static org.forgerock.util.Reject.*;
			import static org.opends.messages.JebMessages.*;
			import static org.opends.server.backends.pluggable.EntryIDSet.*;
			import static org.opends.server.backends.pluggable.State.IndexFlag.*;

			import java.util.ArrayList;
			import java.util.EnumSet;
			import java.util.HashSet;
			import java.util.List;
			import java.util.Map;
			import java.util.Set;
			import java.util.TreeMap;

			import org.forgerock.i18n.slf4j.LocalizedLogger;
			import org.forgerock.opendj.ldap.ByteSequence;
			import org.forgerock.opendj.ldap.ByteString;
			import org.forgerock.opendj.ldap.ConditionResult;
			import org.forgerock.opendj.ldap.spi.IndexingOptions;
			import org.forgerock.util.promise.NeverThrowsException;
			import org.opends.server.backends.pluggable.CursorTransformer.ValueTransformer;
			import org.opends.server.backends.pluggable.EntryIDSet.EntryIDSetCodec;
			import org.opends.server.backends.pluggable.IndexBuffer.BufferedIndexValues;
			import org.opends.server.backends.pluggable.State.IndexFlag;
			import org.opends.server.backends.pluggable.spi.Cursor;
			import org.opends.server.backends.pluggable.spi.ReadableTransaction;
			import org.opends.server.backends.pluggable.spi.StorageRuntimeException;
			import org.opends.server.backends.pluggable.spi.TreeName;
			import org.opends.server.backends.pluggable.spi.UpdateFunction;
			import org.opends.server.backends.pluggable.spi.WriteableTransaction;
			import org.opends.server.types.Entry;
			import org.opends.server.types.Modification;
			import org.opends.server.util.StaticUtils;

			/**
			* Represents an index implemented by a tree in which each key maps to
			* a set of entry IDs. The key is a byte array, and is constructed from some
			* normalized form of an attribute value (or fragment of a value) appearing
			* in the entry.
			* Represents an index implemented by a tree in which each key maps to a set of entry IDs. The key
			* is a byte array, and is constructed from some normalized form of an attribute value (or fragment
			* of a value) appearing in the entry.
			*/
			class Index extends DatabaseContainer
			interface Index extends DatabaseContainer
			{
			private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();
			EntryIDSet get(ReadableTransaction txn, ByteSequence key);

			/** The indexer object to construct index keys from LDAP attribute values. */
			private Indexer indexer;
			int getIndexEntryLimit();

			/** The limit on the number of entry IDs that may be indexed by one key. */
			private int indexEntryLimit;
			/**
			* Limit on the number of entry IDs that may be retrieved by cursoring
			* through an index.
			*/
			private final int cursorEntryLimit;
			/**
			* Number of keys that have exceeded the entry limit since this
			* object was created.
			*/
			private int entryLimitExceededCount;
			boolean getMaintainCount();

			/**
			* Whether to maintain a count of IDs for a key once the entry limit
			* has exceeded.
			*/
			private final boolean maintainCount;
			// Ignores trusted state.
			void importPut(WriteableTransaction txn, ImportIDSet idsToBeAdded);

			private final State state;
			// Ignores trusted state.
			void importRemove(WriteableTransaction txn, ImportIDSet idsToBeRemoved);

			private final EntryIDSetCodec codec;
			boolean isTrusted();

			/**
			* A flag to indicate if this index should be trusted to be consistent
			* with the entries database. If not trusted, we assume that existing
			* entryIDSets for a key is still accurate. However, keys that do not
			* exist are undefined instead of an empty entryIDSet. The following
			* rules will be observed when the index is not trusted:
			*
			* - no entryIDs will be added to a non-existing key.
			* - undefined entryIdSet will be returned whenever a key is not found.
			*/
			private boolean trusted;
			Cursor<ByteString, EntryIDSet> openCursor(ReadableTransaction txn);

			/**
			* Create a new index object.
			* @param name The name of the index database within the entryContainer.
			* @param indexer The indexer object to construct index keys from LDAP
			* attribute values.
			* @param state The state database to persist index state info.
			* @param indexEntryLimit The configured limit on the number of entry IDs
			* that may be indexed by one key.
			* @param cursorEntryLimit The configured limit on the number of entry IDs
			* @param maintainCount Whether to maintain a count of IDs for a key once
			* the entry limit has exceeded.
			* @param txn a non null database transaction
			* @param entryContainer The database entryContainer holding this index.
			* @throws StorageRuntimeException If an error occurs in the database.
			*/
			Index(TreeName name, Indexer indexer, State state, int indexEntryLimit, int cursorEntryLimit, boolean maintainCount,
			WriteableTransaction txn, EntryContainer entryContainer) throws StorageRuntimeException
			{
			super(name);
			this.indexer = indexer;
			this.indexEntryLimit = indexEntryLimit;
			this.cursorEntryLimit = cursorEntryLimit;
			this.maintainCount = maintainCount;
			this.state = state;
			boolean setIndexEntryLimit(int indexEntryLimit);

			final EnumSet<IndexFlag> flags = state.getIndexFlags(txn, getName());
			this.codec = flags.contains(COMPACTED) ? CODEC_V2 : CODEC_V1;
			this.trusted = flags.contains(TRUSTED);
			if (!trusted && entryContainer.getHighestEntryID(txn).longValue() == 0)
			{
			// If there are no entries in the entry container then there
			// is no reason why this index can't be upgraded to trusted.
			setTrusted(txn, true);
			}
			}
			void setTrusted(WriteableTransaction txn, boolean trusted);

			void indexEntry(Entry entry, Set<ByteString> keys, IndexingOptions options)
			{
			indexer.indexEntry(entry, keys, options);
			}

			final void insertID(IndexBuffer buffer, ByteString keyBytes, EntryID entryID)
			{
			getBufferedIndexValues(buffer, keyBytes).addEntryID(keyBytes, entryID);
			}

			final Cursor<ByteString, EntryIDSet> openCursor(ReadableTransaction txn) {
			checkNotNull(txn, "txn must not be null");
			return CursorTransformer.transformValues(txn.openCursor(getName()),
			new ValueTransformer<ByteString, ByteString, EntryIDSet, NeverThrowsException>()
			{
			@Override
			public EntryIDSet transform(ByteString key, ByteString value) throws NeverThrowsException
			{
			return codec.decode(key, value);
			}
			});
			}

			/**
			* Delete the specified import ID set from the import ID set associated with the key.
			*
			* @param txn a non null database transaction
			* @param importIdSet The import ID set to delete.
			* @throws StorageRuntimeException If a database error occurs.
			*/
			final void delete(WriteableTransaction txn, ImportIDSet importIdSet) throws StorageRuntimeException
			{
			ByteSequence key = importIdSet.getKey();
			ByteString value = txn.read(getName(), key);
			if (value != null) {
			final ImportIDSet importIDSet = new ImportIDSet(key, codec.decode(key, value), indexEntryLimit, maintainCount);
			importIDSet.remove(importIdSet);
			if (importIDSet.isDefined() && importIDSet.size() == 0)
			{
			txn.delete(getName(), key);
			}
			else
			{
			value = importIDSet.valueToByteString(codec);
			txn.put(getName(), key, value);
			}
			} else {
			// Should never happen -- the keys should always be there.
			throw new RuntimeException();
			}
			}

			/**
			* Insert the specified import ID set into this index. Creates a DB cursor if needed.
			*
			* @param txn a non null database transaction
			* @param importIdSet The set of import IDs.
			* @throws StorageRuntimeException If a database error occurs.
			*/
			final void insert(WriteableTransaction txn, ImportIDSet importIdSet) throws StorageRuntimeException
			{
			ByteSequence key = importIdSet.getKey();
			ByteString value = txn.read(getName(), key);
			if(value != null) {
			final ImportIDSet importIDSet = new ImportIDSet(key, codec.decode(key, value), indexEntryLimit, maintainCount);
			if (importIDSet.merge(importIdSet)) {
			entryLimitExceededCount++;
			}
			value = importIDSet.valueToByteString(codec);
			} else {
			if(!importIdSet.isDefined()) {
			entryLimitExceededCount++;
			}
			value = importIdSet.valueToByteString(codec);
			}
			txn.put(getName(), key, value);
			}

			void updateKey(WriteableTransaction txn, ByteString key, EntryIDSet deletedIDs, EntryIDSet addedIDs)
			throws StorageRuntimeException
			{
			/*
			* Check the special condition where both deletedIDs and addedIDs are null. This is used when
			* deleting entries and corresponding id2children and id2subtree records must be completely
			* removed.
			*/
			if (deletedIDs == null && addedIDs == null)
			{
			boolean success = txn.delete(getName(), key);
			if (success && logger.isTraceEnabled())
			{
			StringBuilder builder = new StringBuilder();
			StaticUtils.byteArrayToHexPlusAscii(builder, key.toByteArray(), 4);
			logger.trace("The expected key does not exist in the index %s.\nKey:%s ", getName(), builder);
			}
			return;
			}

			// Handle cases where nothing is changed early to avoid DB access.
			if (isNullOrEmpty(deletedIDs) && isNullOrEmpty(addedIDs))
			{
			return;
			}

			if (maintainCount)
			{
			updateKeyWithRMW(txn, key, deletedIDs, addedIDs);
			}
			else
			{
			/*
			* Avoid taking a write lock on a record which has hit all IDs because it is likely to be a
			* point of contention.
			*/
			ByteString value = txn.read(getName(), key);
			if (value != null)
			{
			EntryIDSet entryIDSet = codec.decode(key, value);
			if (entryIDSet.isDefined())
			{
			updateKeyWithRMW(txn, key, deletedIDs, addedIDs);
			} // else the record exists but we've hit all IDs.
			}
			else if (trusted)
			{
			/*
			* The key was not present, but we cannot simply add it because another thread may have
			* added since.
			*/
			updateKeyWithRMW(txn, key, deletedIDs, addedIDs);
			}
			}
			}

			private boolean isNullOrEmpty(EntryIDSet entryIDSet)
			{
			return entryIDSet == null \|\| entryIDSet.size() == 0;
			}

			private boolean isNotEmpty(EntryIDSet entryIDSet)
			{
			return entryIDSet != null && entryIDSet.size() > 0;
			}

			private void updateKeyWithRMW(final WriteableTransaction txn, final ByteString key, final EntryIDSet deletedIDs,
			final EntryIDSet addedIDs) throws StorageRuntimeException
			{
			txn.update(getName(), key, new UpdateFunction()
			{
			@Override
			public ByteSequence computeNewValue(final ByteSequence oldValue)
			{
			if (oldValue != null)
			{
			EntryIDSet entryIDSet = computeEntryIDSet(key, oldValue.toByteString(), deletedIDs, addedIDs);
			ByteString after = codec.encode(entryIDSet);
			/*
			* If there are no more IDs then return null indicating that the record should be removed.
			* If index is not trusted then this will cause all subsequent reads for this key to
			* return undefined set.
			*/
			return after.isEmpty() ? null : after;
			}
			else if (trusted)
			{
			if (deletedIDs != null)
			{
			logIndexCorruptError(txn, key);
			}
			if (isNotEmpty(addedIDs))
			{
			return codec.encode(addedIDs);
			}
			}
			return null; // no change.
			}
			});
			}

			private EntryIDSet computeEntryIDSet(ByteString key, ByteString value, EntryIDSet deletedIDs, EntryIDSet addedIDs)
			{
			EntryIDSet entryIDSet = codec.decode(key, value);
			if(addedIDs != null)
			{
			if(entryIDSet.isDefined() && indexEntryLimit > 0)
			{
			long idCountDelta = addedIDs.size();
			if(deletedIDs != null)
			{
			idCountDelta -= deletedIDs.size();
			}
			if(idCountDelta + entryIDSet.size() >= indexEntryLimit)
			{
			if(maintainCount)
			{
			entryIDSet = newUndefinedSetWithSize(key, entryIDSet.size() + idCountDelta);
			}
			else
			{
			entryIDSet = newUndefinedSet();
			}
			entryLimitExceededCount++;

			if(logger.isTraceEnabled())
			{
			StringBuilder builder = new StringBuilder();
			StaticUtils.byteArrayToHexPlusAscii(builder, key.toByteArray(), 4);
			logger.trace("Index entry exceeded in index %s. " +
			"Limit: %d. ID list size: %d.\nKey:%s",
			getName(), indexEntryLimit, idCountDelta + addedIDs.size(), builder);

			}
			}
			else
			{
			entryIDSet.addAll(addedIDs);
			if(deletedIDs != null)
			{
			entryIDSet.removeAll(deletedIDs);
			}
			}
			}
			else
			{
			entryIDSet.addAll(addedIDs);
			if(deletedIDs != null)
			{
			entryIDSet.removeAll(deletedIDs);
			}
			}
			}
			else if(deletedIDs != null)
			{
			entryIDSet.removeAll(deletedIDs);
			}
			return entryIDSet;
			}

			final void removeID(IndexBuffer buffer, ByteString keyBytes, EntryID entryID)
			{
			getBufferedIndexValues(buffer, keyBytes).deleteEntryID(keyBytes, entryID);
			}

			private void logIndexCorruptError(WriteableTransaction txn, ByteString key)
			{
			if (logger.isTraceEnabled())
			{
			StringBuilder builder = new StringBuilder();
			StaticUtils.byteArrayToHexPlusAscii(builder, key.toByteArray(), 4);
			logger.trace("The expected key does not exist in the index %s.\nKey:%s", getName(), builder);
			}

			setTrusted(txn, false);
			logger.error(ERR_JEB_INDEX_CORRUPT_REQUIRES_REBUILD, getName());
			}

			void delete(IndexBuffer buffer, ByteString keyBytes)
			{
			getBufferedIndexValues(buffer, keyBytes);
			}

			private BufferedIndexValues getBufferedIndexValues(IndexBuffer buffer, ByteString keyBytes)
			{
			return buffer.getBufferedIndexValues(this, keyBytes);
			}

			/**
			* Check if an entry ID is in the set of IDs indexed by a given key.
			*
			* @param txn
			* A database transaction.
			* @param key
			* The index key.
			* @param entryID
			* The entry ID.
			* @return true if the entry ID is indexed by the given key, false if it is not indexed by the
			* given key, undefined if the key has exceeded the entry limit.
			* @throws StorageRuntimeException
			* If an error occurs in the database.
			*/
			ConditionResult containsID(ReadableTransaction txn, ByteString key, EntryID entryID)
			throws StorageRuntimeException
			{
			ByteString value = txn.read(getName(), key);
			if (value != null)
			{
			EntryIDSet entryIDSet = codec.decode(key, value);
			if (entryIDSet.isDefined())
			{
			return ConditionResult.valueOf(entryIDSet.contains(entryID));
			}
			return ConditionResult.UNDEFINED;
			}
			return trusted ? ConditionResult.FALSE : ConditionResult.UNDEFINED;
			}

			/**
			* Reads the value associated to a key.
			*
			* @param txn a non null database transaction
			* @param key The key to read
			* @return The non null set of entry IDs.
			*/
			EntryIDSet read(ReadableTransaction txn, ByteSequence key)
			{
			try
			{
			ByteString value = txn.read(getName(), key);
			if (value != null)
			{
			return codec.decode(key, value);
			}
			return trusted ? newDefinedSet() : newUndefinedSet();
			}
			catch (StorageRuntimeException e)
			{
			logger.traceException(e);
			return newUndefinedSet();
			}
			}

			/**
			* Reads a range of keys and collects all their entry IDs into a
			* single set.
			*
			* @param txn a non null database transaction
			* @param lower The lower bound of the range. A 0 length byte array indicates
			* no lower bound and the range will start from the
			* smallest key.
			* @param upper The upper bound of the range. A 0 length byte array indicates
			* no upper bound and the range will end at the largest
			* key.
			* @param lowerIncluded true if a key exactly matching the lower bound
			* is included in the range, false if only keys
			* strictly greater than the lower bound are included.
			* This value is ignored if the lower bound is not
			* specified.
			* @param upperIncluded true if a key exactly matching the upper bound
			* is included in the range, false if only keys
			* strictly less than the upper bound are included.
			* This value is ignored if the upper bound is not
			* specified.
			* @return The non null set of entry IDs.
			*/
			EntryIDSet readRange(ReadableTransaction txn,
			ByteSequence lower, ByteSequence upper, boolean lowerIncluded, boolean upperIncluded)
			{
			// If this index is not trusted, then just return an undefined id set.
			if (!trusted)
			{
			return newUndefinedSet();
			}

			try
			{
			// Total number of IDs found so far.
			int totalIDCount = 0;

			ArrayList<EntryIDSet> sets = new ArrayList<EntryIDSet>();

			Cursor<ByteString, ByteString> cursor = txn.openCursor(getName());
			try
			{
			boolean success;
			// Set the lower bound if necessary.
			if (lower.length() > 0)
			{
			// Initialize the cursor to the lower bound.
			success = cursor.positionToKeyOrNext(lower);

			// Advance past the lower bound if necessary.
			if (success && !lowerIncluded && cursor.getKey().equals(lower))
			{
			// Do not include the lower value.
			success = cursor.next();
			}
			}
			else
			{
			success = cursor.next();
			}

			if (!success)
			{
			// There are no values.
			return newDefinedSet();
			}

			// Step through the keys until we hit the upper bound or the last key.
			while (success)
			{
			// Check against the upper bound if necessary
			if (upper.length() > 0)
			{
			int cmp = cursor.getKey().compareTo(upper);
			if (cmp > 0 \|\| (cmp == 0 && !upperIncluded))
			{
			break;
			}
			}

			EntryIDSet set = codec.decode(cursor.getKey(), cursor.getValue());
			if (!set.isDefined())
			{
			// There is no point continuing.
			return set;
			}
			totalIDCount += set.size();
			if (cursorEntryLimit > 0 && totalIDCount > cursorEntryLimit)
			{
			// There are too many. Give up and return an undefined list.
			return newUndefinedSet();
			}
			sets.add(set);
			success = cursor.next();
			}

			return newSetFromUnion(sets);
			}
			finally
			{
			cursor.close();
			}
			}
			catch (StorageRuntimeException e)
			{
			logger.traceException(e);
			return newUndefinedSet();
			}
			}

			int getEntryLimitExceededCount()
			{
			return entryLimitExceededCount;
			}

			void addEntry(IndexBuffer buffer, EntryID entryID, Entry entry, IndexingOptions options)
			throws StorageRuntimeException
			{
			HashSet<ByteString> addKeys = new HashSet<ByteString>();
			indexer.indexEntry(entry, addKeys, options);

			for (ByteString keyBytes : addKeys)
			{
			insertID(buffer, keyBytes, entryID);
			}
			}

			void removeEntry(IndexBuffer buffer, EntryID entryID, Entry entry, IndexingOptions options)
			throws StorageRuntimeException
			{
			HashSet<ByteString> delKeys = new HashSet<ByteString>();
			indexer.indexEntry(entry, delKeys, options);

			for (ByteString keyBytes : delKeys)
			{
			removeID(buffer, keyBytes, entryID);
			}
			}

			void modifyEntry(IndexBuffer buffer, EntryID entryID, Entry oldEntry, Entry newEntry, List<Modification> mods,
			IndexingOptions options) throws StorageRuntimeException
			{
			TreeMap<ByteString, Boolean> modifiedKeys = new TreeMap<ByteString, Boolean>();
			indexer.modifyEntry(oldEntry, newEntry, mods, modifiedKeys, options);

			for (Map.Entry<ByteString, Boolean> modifiedKey : modifiedKeys.entrySet())
			{
			if(modifiedKey.getValue())
			{
			insertID(buffer, modifiedKey.getKey(), entryID);
			}
			else
			{
			removeID(buffer, modifiedKey.getKey(), entryID);
			}
			}
			}

			boolean setIndexEntryLimit(int indexEntryLimit)
			{
			final boolean rebuildRequired = this.indexEntryLimit < indexEntryLimit && entryLimitExceededCount > 0;
			this.indexEntryLimit = indexEntryLimit;
			return rebuildRequired;
			}

			final void setIndexer(Indexer indexer)
			{
			this.indexer = indexer;
			}

			int getIndexEntryLimit()
			{
			return indexEntryLimit;
			}

			synchronized void setTrusted(WriteableTransaction txn, boolean trusted) throws StorageRuntimeException
			{
			this.trusted = trusted;
			if (trusted) {
			state.addFlagsToIndex(txn, getName(), TRUSTED);
			} else {
			state.removeFlagsFromIndex(txn, getName(), TRUSTED);
			}
			}

			synchronized boolean isTrusted()
			{
			return trusted;
			}

			synchronized boolean isRebuildRunning()
			{
			return false; // FIXME inline?
			}

			boolean getMaintainCount()
			{
			return maintainCount;
			}
			void update(WriteableTransaction txn, ByteString key, EntryIDSet deletedIDs, EntryIDSet addedIDs);
			}