OPENDJ-1710: NPE performing deletes and potentially other indexed updates a...

Matthew Swift

22.03.2014 38f4dd121d6aa3baa0c06bbe7f3c7cb6cb861131

OPENDJ-1710: NPE performing deletes and potentially other indexed updates against Persistit backend

* inline and simplify ID list encoding avoiding potential NPEs
* fix usage of stale key in EntryContainer.deleteEntry().

It is now possible to do single entry deletes. Subtree deletes fail when attempting to delete the final top level entry.

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/jeb/VerifyJob.java

@@ -592,7 +592,6 @@

        try
        {
          JebFormat.entryIDListFromDatabase(data.getData());
          entryIDList = new EntryIDSet(key.getData(), data.getData());
        }
        catch (Exception e)
@@ -723,7 +722,6 @@
        EntryIDSet entryIDList;
        try
        {
          JebFormat.entryIDListFromDatabase(data.getData());
          entryIDList = new EntryIDSet(key.getData(), data.getData());
        }
        catch (Exception e)
@@ -1009,7 +1007,6 @@
        EntryIDSet entryIDList;
        try
        {
          JebFormat.entryIDListFromDatabase(data.getData());
          entryIDList = new EntryIDSet(key.getData(), data.getData());
        }
        catch (Exception e)

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/EntryContainer.java

@@ -1783,7 +1783,7 @@
                  }
                }

                deleteEntry(txn, indexBuffer, true, entryDN, startKey, entryID);
                deleteEntry(txn, indexBuffer, true, entryDN, cursor.getKey(), entryID);
                subordinateEntriesDeleted++;

                if (deleteOperation != null)
@@ -1877,7 +1877,7 @@
      ByteString value = dn2id.read(txn, leafDNKey, true);
      if (value == null)
      {
        LocalizableMessage message = ERR_JEB_DELETE_NO_SUCH_OBJECT.get(leafDNKey);
        LocalizableMessage message = ERR_JEB_DELETE_NO_SUCH_OBJECT.get(targetDN);
        DN matchedDN = getMatchedDN(baseDN);
        throw new DirectoryException(ResultCode.NO_SUCH_OBJECT, message, matchedDN, null);
      }

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/EntryIDSet.java

@@ -31,7 +31,9 @@
import java.util.Iterator;

import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;

/**
 * Represents a set of Entry IDs.  It can represent a set where the IDs are
@@ -90,10 +92,8 @@
    if (bytes == null)
    {
      values = new long[0];
      return;
    }

    if (bytes.length() == 0)
    else if (bytes.length() == 0)
    {
      // Entry limit has exceeded and there is no encoded undefined set size.
      undefinedSize = Long.MAX_VALUE;
@@ -101,17 +101,30 @@
    else if ((bytes.byteAt(0) & 0x80) == 0x80)
    {
      // Entry limit has exceeded and there is an encoded undefined set size.
      undefinedSize =
          JebFormat.entryIDUndefinedSizeFromDatabase(bytes.toByteArray());
      undefinedSize = bytes.length() == 8
              ? bytes.toLong() & Long.MAX_VALUE // remove top bit
              : Long.MAX_VALUE;
    }
    else
    {
      // Seems like entry limit has not been exceeded and the bytes is a
      // list of entry IDs.
      values = JebFormat.entryIDListFromDatabase(bytes);
      values = decodeEntryIDList(bytes);
    }
  }

  private long[] decodeEntryIDList(ByteString bytes)
  {
    final ByteSequenceReader reader = bytes.asReader();
    final int count = bytes.length() / 8;
    final long[] entryIDList = new long[count];
    for (int i = 0; i < count; i++)
    {
      entryIDList[i] = reader.getLong();
    }
    return entryIDList;
  }

  /**
   * Construct an EntryIDSet from an array of longs.
   *
@@ -285,13 +298,19 @@
   */
  public ByteString toByteString()
  {
    if(isDefined())
    if (isDefined())
    {
      return ByteString.wrap(JebFormat.entryIDListToDatabase(values));
      final ByteStringBuilder builder = new ByteStringBuilder(8 * values.length);
      for (int i = 0; i < values.length; i++)
      {
        builder.append(values[i]);
      }
      return builder.toByteString();
    }
    else
    {
      return ByteString.wrap(JebFormat.entryIDUndefinedSizeToDatabase(undefinedSize));
      // Set top bit.
      return ByteString.valueOf(undefinedSize | Long.MIN_VALUE);
    }
  }


 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/Index.java

@@ -241,7 +241,7 @@
    {
      EntryIDSet entryIDList = computeEntryIDList(key, value, deletedIDs, addedIDs);
      ByteString after = entryIDList.toByteString();
      if (after != null)
      if (!after.isEmpty())
      {
        put(txn, key, after);
      }
@@ -455,7 +455,7 @@
       throws StorageRuntimeException
  {
    ByteString value = entryIDList.toByteString();
    if (value != null)
    if (!value.isEmpty())
    {
      if (!entryIDList.isDefined())
      {

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/JebFormat.java

@@ -30,7 +30,6 @@
import java.util.TreeSet;

import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.opends.server.types.DN;
@@ -52,159 +51,6 @@
  public static final byte TAG_DIRECTORY_SERVER_ENTRY = 0x61;

  /**
   * Decode a long from a byte array, starting at start index and ending at end
   * index.
   *
   * @param bytes
   *          The bytes value of the long.
   * @param start
   *          the array index where to start computing the long
   * @param end
   *          the array index exclusive where to end computing the long
   * @return the long representation of the read bytes.
   * @throws ArrayIndexOutOfBoundsException
   *           if the bytes array length is less than end.
   */
  public static long toLong(byte[] bytes, int start, int end)
      throws ArrayIndexOutOfBoundsException
  {
    long v = 0;
    for (int i = start; i < end; i++)
    {
      v <<= 8;
      v |= (bytes[i] & 0xFF);
    }
    return v;
  }

  /**
   * Decode an entry ID count from its database representation.
   *
   * @param bytes The database value of the entry ID count.
   * @return The entry ID count.
   *  Cannot be negative if encoded with #entryIDUndefinedSizeToDatabase(long)
   * @see #entryIDUndefinedSizeToDatabase(long)
   */
  public static long entryIDUndefinedSizeFromDatabase(byte[] bytes)
  {
    if(bytes == null)
    {
      return 0;
    }

    if(bytes.length == 8)
    {
      long v = 0;
      v |= (bytes[0] & 0x7F);
      for (int i = 1; i < 8; i++)
      {
        v <<= 8;
        v |= (bytes[i] & 0xFF);
      }
      return v;
    }
    return Long.MAX_VALUE;
  }

  /**
   * Decode an array of entry ID values from its database representation.
   *
   * @param bytes The raw database value, null if there is no value and
   *              hence no entry IDs. Note that this method will throw an
   *              ArrayIndexOutOfBoundsException if the bytes array length is
   *              not a multiple of 8.
   * @return An array of entry ID values.
   * @see #entryIDListToDatabase(long[])
   */
  public static long[] entryIDListFromDatabase(ByteSequence bytes)
  {
    final ByteSequenceReader r = bytes.asReader();

    final int count = bytes.length() / 8;
    final long[] entryIDList = new long[count];
    for (int i = 0; i < count; i++)
    {
      entryIDList[i] = r.getLong();
    }
    return entryIDList;
  }

  /**
   * Decode a integer array using the specified byte array read from DB.
   *
   * @param bytes The byte array.
   * @return An integer array.
   */
  public static int[] intArrayFromDatabaseBytes(byte[] bytes) {
    byte[] decodedBytes = bytes;

    int count = decodedBytes.length / 8;
    int[] entryIDList = new int[count];
    for (int pos = 0, i = 0; i < count; i++) {
      int v = 0;
      pos +=4;
      v |= (decodedBytes[pos++] & 0xFFL) << 24;
      v |= (decodedBytes[pos++] & 0xFFL) << 16;
      v |= (decodedBytes[pos++] & 0xFFL) << 8;
      v |= (decodedBytes[pos++] & 0xFFL);
      entryIDList[i] = v;
    }

    return entryIDList;
  }

  /**
   * Encode an entry ID set count to its database representation.
   *
   * @param count The entry ID set count to be encoded.
   * @return The encoded database value of the entry ID set count.
   * @see #entryIDUndefinedSizeFromDatabase(byte[])
   */
  public static byte[] entryIDUndefinedSizeToDatabase(long count)
  {
    byte[] bytes = new byte[8];
    long v = count;
    for (int i = 7; i >= 1; i--)
    {
      bytes[i] = (byte) (v & 0xFF);
      v >>>= 8;
    }
    bytes[0] = (byte) ((v | 0x80) & 0xFF);
    return bytes;
  }

  /**
   * Encode an array of entry ID values to its database representation.
   *
   * @param entryIDArray An array of entry ID values.
   * @return The encoded database value.
   */
  public static byte[] entryIDListToDatabase(long[] entryIDArray)
  {
    if (entryIDArray.length == 0)
    {
      // Zero values
      return null;
    }

    byte[] bytes = new byte[8*entryIDArray.length];
    for (int pos = 0, i = 0; i < entryIDArray.length; i++)
    {
      long v = entryIDArray[i];
      bytes[pos++] = (byte) ((v >>> 56) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 48) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 40) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 32) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 24) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 16) & 0xFF);
      bytes[pos++] = (byte) ((v >>> 8) & 0xFF);
      bytes[pos++] = (byte) (v & 0xFF);
    }

    return bytes;
  }

  /**
   * Decode a DN value from its database key representation.
   *
   * @param dnKey The database key value of the DN.
@@ -258,35 +104,6 @@
    return dn;
  }

  /**
   * Find the length of bytes that represents the superior DN of the given
   * DN key. The superior DN is represented by the initial bytes of the DN key.
   *
   * @param dnKey The database key value of the DN.
   * @param offset Starting position in the database key data.
   * @param length The length of the database key data.
   * @return The length of the superior DN or -1 if the given dn is the
   *         root DN or 0 if the superior DN is removed.
   */
  public static int findDNKeyParent(byte[] dnKey, int offset, int length)
  {
    if(length == 0)
    {
      // This is the root or base DN
      return -1;
    }

    // We will walk backwards through the buffer and find the first unescaped comma
    for(int i = offset+length - 1; i >= offset; i--)
    {
      if(dnKey[i] == 0x00 && i-1 >= offset && dnKey[i-1] != 0x5C)
      {
        return i;
      }
    }
    return offset;
  }

  public static int findDNKeyParent(ByteSequence dnKey)
  {
    if (dnKey.length() == 0)

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/SortValuesSet.java

@@ -26,6 +26,7 @@
 */
package org.opends.server.backends.pluggable;

import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.forgerock.opendj.ldap.DecodeException;
@@ -350,39 +351,15 @@
    {
      return null;
    }

    byte[] entryIDBytes = JebFormat.entryIDListToDatabase(entryIDs);
    byte[] concatBytes = new byte[entryIDBytes.length + valuesBytes.length + 4];
    int v = entryIDs.length;

    for (int j = 3; j >= 0; j--)
    final ByteStringBuilder builder = new ByteStringBuilder(4 + entryIDs.length
        * 8 + valuesBytes.length);
    builder.append(entryIDs.length);
    for (int i = 0; i < entryIDs.length; i++)
    {
      concatBytes[j] = (byte) (v & 0xFF);
      v >>>= 8;
      builder.append(entryIDs[i]);
    }

    System.arraycopy(entryIDBytes, 0, concatBytes, 4, entryIDBytes.length);
    System.arraycopy(valuesBytes, 0, concatBytes, entryIDBytes.length+4,
                     valuesBytes.length);

    return ByteString.valueOf(concatBytes);
  }

  /**
   * Get the size of the provided encoded set.
   *
   * @param bytes The encoded bytes of a SortValuesSet to decode the size from.
   * @return The size of the provided encoded set.
   */
  public static int getEncodedSize(ByteString bytes)
  {
    int v = 0;
    for (int i = 0; i < 4; i++)
    {
      v <<= 8;
      v |= (bytes.byteAt(i) & 0xFF);
    }
    return v;
    builder.append(valuesBytes);
    return builder.toByteString();
  }

  /**
@@ -393,9 +370,14 @@
   */
  public static long[] getEncodedIDs(ByteString bytes)
  {
    int length = getEncodedSize(bytes) * 8;
    ByteString entryIDBytes = bytes.subSequence(4, 4 + length);
    return JebFormat.entryIDListFromDatabase(entryIDBytes);
    final ByteSequenceReader reader = bytes.asReader();
    final int length = reader.getInt();
    final long[] entryIDList = new long[length];
    for (int i = 0; i < length; i++)
    {
      entryIDList[i] = reader.getLong();
    }
    return entryIDList;
  }

  /**

 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/VLVIndex.java

@@ -230,7 +230,7 @@
    {
      while (cursor.next())
      {
        count.getAndAdd(SortValuesSet.getEncodedSize(cursor.getValue()));
        count.getAndAdd(getEncodedSize(cursor.getValue()));
      }
    }
    finally
@@ -239,6 +239,12 @@
    }
  }

  // Matches encoding from SortValuesSet.
  private int getEncodedSize(ByteString bytes)
  {
    return bytes.toInt();
  }

  /**
   * Close the VLV index.
   *
@@ -826,7 +832,7 @@
              }
              else
              {
                targetOffset += SortValuesSet.getEncodedSize(cursor.getValue());
                targetOffset += getEncodedSize(cursor.getValue());
              }
            }

@@ -1090,15 +1096,13 @@
      }
      else
      {
        byte[] valueBytes = new byte[valueLength];
        System.arraycopy(keyBytes, vBytesPos, valueBytes, 0, valueLength);
        attributeValues[i] = ByteString.wrap(valueBytes);
        attributeValues[i] = keyBytes.subSequence(vBytesPos, vBytesPos + valueLength);
      }

      vBytesPos += valueLength;
    }

    final long id = JebFormat.toLong(keyBytes.toByteArray(), vBytesPos, keyBytes.length());
    final long id = keyBytes.subSequence(vBytesPos, keyBytes.length()).toLong();
    return new SortValues(new EntryID(id), attributeValues, sortOrder);
  }


 opendj-sdk/opendj3-server-dev/src/server/org/opends/server/backends/pluggable/VerifyJob.java

@@ -615,7 +615,6 @@

        try
        {
          JebFormat.entryIDListFromDatabase(value);
          entryIDList = new EntryIDSet(key, value);
        }
        catch (Exception e)
@@ -741,7 +740,6 @@
        EntryIDSet entryIDList;
        try
        {
          JebFormat.entryIDListFromDatabase(value);
          entryIDList = new EntryIDSet(key, value);
        }
        catch (Exception e)
@@ -1013,7 +1011,6 @@
        EntryIDSet entryIDList;
        try
        {
          JebFormat.entryIDListFromDatabase(value);
          entryIDList = new EntryIDSet(key, value);
        }
        catch (Exception e)