Make AciList (the ACI cache) a copy-on-write class, such that there is no l...

coulbeck

01.30.2007 196ca99c14ab4aeee0c76c90fce0b72ab4e102f4

Make AciList (the ACI cache) a copy-on-write class, such that there is no locking when reading the ACI cache.
Remove the linked list field from the Aci class and use the standard LinkedList instead.

 opends/src/server/org/opends/server/authorization/dseecompat/Aci.java

@@ -32,6 +32,7 @@
import static org.opends.server.messages.MessageHandler.*;
import static org.opends.server.authorization.dseecompat.AciMessages.*;
import java.util.regex.Pattern;

/**
 * The Aci class represents ACI strings.
 */
@@ -41,28 +42,24 @@
     * pairs.
     */
    private AciBody body;

    /*
     * The ACI targets.
     */
    private AciTargets targets=null;
    /**
     * The ACIs are on a linked list hashed by the ACI entry DN.
     * Next points to the next Aci object in the list.
     */
    /*
     * TODO Remove this linked list an replace with an array
     * of ACIs.
     */
    Aci next = null;

    /**
     * Version that we support.
     */
    public static final String supportedVersion="3.0";

    private String aciString;

    /*
     * The DN of the entry containing this ACI.
     */
    private DN dn;

    /*
     * This regular expression is used to do a quick syntax check
     * when an ACI is being decoded.
@@ -97,7 +94,7 @@
    public static Aci decode (ByteString byteString, DN dn)
    throws AciException {
        String input=byteString.stringValue();
        //Perform an quick pattern check against the string to catch any
        //Perform a quick pattern check against the string to catch any
        //obvious syntax errors.
        if (!Pattern.matches(aciRegex, input)) {
            int msgID = MSGID_ACI_SYNTAX_GENERAL_PARSE_FAILED;

 opends/src/server/org/opends/server/authorization/dseecompat/AciList.java

@@ -34,8 +34,8 @@
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.ArrayList;

import org.opends.server.types.Attribute;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.DN;
@@ -49,203 +49,230 @@
 * using the entry DN as the key.
 */
public class AciList {
    /*
     * TODO Change linked list implementation as suggested below.
     *  I would strongly recommend that you change aciList to be
     *  LinkedHashMap<DN,List<Aci>> or LinkedHashMap<DN,Aci[]> rather than
     *  LinkedHashMap<String,Aci>.  It looks like there are some costly
     *  string->DN and even string->DN->string conversions.  Further, the very
     *  hackish way that the linked-list is currently maintained is very
     *  ugly and potentially error-prone.
     */
    private LinkedHashMap<DN, Aci> aciList =
            new LinkedHashMap<DN, Aci>();
    /*
     * TODO Evaluate making this class lock-free.
     *  I would definitely try to make this a lock-free class if at all
     *  possible. Read locks aren't free to acquire, since they still require
     *  an exclusive lock at some point.  If possible, you should use a
     *  copy-on-write structure so that you only incur penalties for changing
     *  the ACI list (which should be a rare event) and there is no need for
     *  any kind of locking at all for read operations.
     */
    private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
    private final Lock aciReadLock  = rwl.readLock();
    private final Lock aciWriteLock = rwl.writeLock();
  /**
   * A map containing all the ACIs.
   * We use the copy-on-write technique to avoid locking when reading.
   */
  private volatile LinkedHashMap<DN, List<Aci>> aciList =
       new LinkedHashMap<DN, List<Aci>>();

    /*
     * TODO Add support global ACIs in config.ldif.
     *
     */
    /**
     * Using the base DN, return a list of ACIs that are candidates for
     * evaluation by walking up from the base DN towards the root of the
     * DIT gathering ACIs on parents.
     *
     * @param baseDN  The DN to check.
     * @return A list of candidate ACIs that might be applicable.
     */
    public LinkedList<Aci> getCandidateAcis(DN baseDN) {
        LinkedList<Aci> candidates = new LinkedList<Aci>();
        if(baseDN == null)
            return candidates;
  /**
   * Accessor to the ACI list intended to be called from within unsynchronized
   * read-only methods.
   */
  private LinkedHashMap<DN, List<Aci>> getList() {
    return aciList;
  }

  /**
   * Used by synchronized write methods to make a copy of the ACI list.
   * @return A copy of the ACI list.
   */
  private LinkedHashMap<DN,List<Aci>> copyList() {
    return new LinkedHashMap<DN, List<Aci>>(aciList);
  }

  /*
  * TODO Add support for global ACIs in config.ldif.
  *
  */
  /**
   * Using the base DN, return a list of ACIs that are candidates for
   * evaluation by walking up from the base DN towards the root of the
   * DIT gathering ACIs on parents.
   *
   * @param baseDN  The DN to check.
   * @return A list of candidate ACIs that might be applicable.
   */
  public LinkedList<Aci> getCandidateAcis(DN baseDN) {
    LinkedList<Aci> candidates = new LinkedList<Aci>();
    if(baseDN == null)
      return candidates;

    // Save a reference to the current ACI list, in case it gets changed.
    LinkedHashMap<DN, List<Aci>> aciList = getList();

    while(baseDN != null) {
      List<Aci> acis = aciList.get(baseDN);
      if (acis != null)
      {
        candidates.addAll(acis);
      }
      if(baseDN.isNullDN())
        break;
      DN parentDN=baseDN.getParent();
      if(parentDN == null)
        baseDN=DN.nullDN();
      else
        baseDN=parentDN;
    }
    return candidates;
  }

  /**
   * Add all the ACI from a set of entries to the ACI list.
   * @param entries The set of entries containing the "aci" attribute values.
   * @return The number of valid ACI attribute values added to the ACI list.
   */
  public synchronized int addAci(List<? extends Entry> entries)
  {
    // Copy the ACI list.
    LinkedHashMap<DN,List<Aci>> aciCopy = copyList();

    int validAcis=0;
    for (Entry entry : entries) {
      DN dn=entry.getDN();
      List<Attribute> attributeList =
           entry.getOperationalAttribute(AciHandler.aciType);
      validAcis += addAciAttributeList(aciCopy, dn, attributeList);
    }

    // Replace the ACI list with the copy.
    aciList = aciCopy;
    return validAcis;
  }

  /**
   * Add all of an entry's ACI attribute values to the ACI list.
   * @param entry The entry containing the "aci" attribute values.
   * @return The number of valid ACI attribute values added to the ACI list.
   */
  public synchronized int addAci(Entry entry) {
    int validAcis;
    DN dn=entry.getDN();
    List<Attribute> attributeList =
         entry.getOperationalAttribute(AciHandler.aciType);

    // Copy the ACI list.
    LinkedHashMap<DN,List<Aci>> aciCopy = copyList();

    validAcis=addAciAttributeList(aciCopy, dn, attributeList);

    // Replace the ACI list with the copy.
    aciList = aciCopy;
    return validAcis;
  }

  /**
   * Add "aci" attribute type values to the ACI list. There is a chance
   * that an ACI will throw an exception if it has an invalid syntax.
   * If that happens a message will be logged and the ACI skipped.
   * @param aciList The ACI list to which the ACI is to be added.
   * @param dn The DN to use as the key in the ACI list.
   * @param attributeList List of attributes containing the "aci" attribute
   * values.
   * @return The number of valid "aci" attribute values added to the ACI list.
   */
  private static int addAciAttributeList(
       LinkedHashMap<DN,List<Aci>> aciList, DN dn,
       List<Attribute> attributeList) {
    int validAcis=0;
    ArrayList<Aci> acis = new ArrayList<Aci>();
    for (Attribute attribute : attributeList) {
      for (AttributeValue value : attribute.getValues()) {
        try {
            aciReadLock.lock();
            while(baseDN != null) {
                Aci aci = aciList.get(baseDN);
                if (aci != null)
                {
                    while (aci != null)
                    {
                        candidates.add(aci);
                        aci = aci.next;
                    }
                }
                if(baseDN.isNullDN())
                    break;
               DN parentDN=baseDN.getParent();
               if(parentDN == null)
                    baseDN=DN.nullDN();
                else
                    baseDN=parentDN;
            }
        } finally {
            aciReadLock.unlock();
          Aci aci= Aci.decode(value.getValue(),dn);
          acis.add(aci);
          validAcis++;
        } catch (AciException ex) {
          /* An illegal ACI might have been loaded
           * during import and is failing at ACI handler
           * initialization time. Log a message and continue
           * processing. ACIs added via LDAP add have their
           * syntax checked before adding and should never
           * hit this code.
           */
          int    msgID  = MSGID_ACI_ADD_LIST_FAILED_DECODE;
          String message = getMessage(msgID,
                                      ex.getMessage());
          logError(ErrorLogCategory.ACCESS_CONTROL,
                   ErrorLogSeverity.SEVERE_WARNING,
                   message, msgID);
        }
        return candidates;
      }
    }
    addAci(aciList, dn, acis);
    return validAcis;
  }

  /**
   * Remove all of the ACIs related to the old entry and then add all of the
   * ACIs related to the new entry. This method locks/unlocks the list.
   * @param oldEntry The old entry possibly containing old "aci" attribute
   * values.
   * @param newEntry The new entry possibly containing new "aci" attribute
   * values.
   */
  public synchronized void modAciOldNewEntry(Entry oldEntry, Entry newEntry) {
    if((oldEntry.hasOperationalAttribute(AciHandler.aciType)) ||
         (newEntry.hasOperationalAttribute(AciHandler.aciType))) {

      // Copy the ACI list.
      LinkedHashMap<DN,List<Aci>> aciCopy = copyList();

      aciCopy.remove(oldEntry.getDN());
      List<Attribute> attributeList =
           newEntry.getOperationalAttribute(AciHandler.aciType, null);
      addAciAttributeList(aciCopy,newEntry.getDN(),attributeList);

      // Replace the ACI list with the copy.
      aciList = aciCopy;
    }
  }

  /**
   * Add ACI using the DN as a key. If the DN already
   * has ACI(s) on the list, then the new ACI is added to the
   * end of the array.
   * @param aciList The set of ACIs to which ACI is to be added.
   * @param dn The DN to use as the key.
   * @param acis The ACI to be added.
   */
  private static void addAci(LinkedHashMap<DN,List<Aci>> aciList, DN dn,
                             List<Aci> acis)
  {
    if(aciList.containsKey(dn)) {
      List<Aci> tmpAci = aciList.get(dn);
      tmpAci.addAll(acis);
    } else {
      aciList.put(dn, acis);
    }
  }

  /**
   * Remove ACIs related to an entry.
   * @param entry The entry to be removed.
   * @return True if the ACI set was deleted.
   */
  public synchronized boolean removeAci(Entry entry) {
    // Copy the ACI list.
    LinkedHashMap<DN,List<Aci>> aciCopy = copyList();

    boolean deleted = false;
    if (aciCopy.remove(entry.getDN()) != null)
      deleted = true;

    // Replace the ACI list with the copy.
    aciList = aciCopy;
    return deleted;
  }

  /**
   * Remove all ACIs related to a backend.
   * @param backend  The backend to check if each DN is handled by that
   * backend.
   */
  public synchronized void removeAci(Backend backend) {
    // Copy the ACI list.
    LinkedHashMap<DN,List<Aci>> aciCopy = copyList();

    Set<DN> keys=aciCopy.keySet();
    for(DN dn : keys) {
      if (backend.handlesEntry(dn))
        aciCopy.remove(dn);
    }


    /**
     * Add all of an entries ACI attribute values to the ACI list. This
     * method locks/unlocks the list.
     * @param entry The entry containing the "aci" attribute values.\
     * @return The number of valid ACI attribute values added to the ACI list.
     */
    public int addAci(Entry entry) {
        int validAcis=0;
        DN dn=entry.getDN();
        List<Attribute> attributeList =
                entry.getOperationalAttribute(AciHandler.aciType);
        try {
            aciWriteLock.lock();
            validAcis=addAciAttributeListNoLock(dn, attributeList);
        } finally {
            aciWriteLock.unlock();
        }
        return validAcis;
    }

    /**
     * Add "aci" attribute type values to the ACI list. There is a chance
     * that an ACI will throw an exception if it has an invalid syntax.
     * If that happens a message will be logged and the ACI skipped.
     * @param dn The DN to use a the key in the ACI list.
     * @param attributeList List of attributes contain the "aci" attribute
     * values.
     * @return The number of valid "aci" attribute types added to the ACI list.
     */
    private int addAciAttributeListNoLock(DN dn,
                                    List<Attribute> attributeList) {
        int validAcis=0;
        for (Attribute attribute : attributeList) {
            for (AttributeValue value : attribute.getValues()) {
                try {
                    Aci aci= Aci.decode(value.getValue(),dn);
                    addAci(dn, aci);
                    validAcis++;
                } catch (AciException ex) {
                    /* An illegal ACI might have been loaded
                     * during import and is failing at ACI handler
                     * initialization time. Log a message and continue
                     * processing. ACIs added via LDAP add have their
                     * syntax checked before adding and should never
                     * hit this code.
                     */
                    int    msgID  = MSGID_ACI_ADD_LIST_FAILED_DECODE;
                    String message = getMessage(msgID,
                            ex.getMessage());
                    logError(ErrorLogCategory.ACCESS_CONTROL,
                             ErrorLogSeverity.SEVERE_WARNING,
                             message, msgID);
                }
            }
        }
        return validAcis;
    }

    /**
     * Remove all of the ACIs related to the old entry and then add all of the
     * ACIs related to the new entry. This method locks/unlocks the list.
     * @param oldEntry The old entry maybe containing old "aci" attribute
     * values.
     * @param newEntry The new entry maybe containing new "aci" attribute
     * values.
     */
    public void modAciOldNewEntry(Entry oldEntry, Entry newEntry) {
         if((oldEntry.hasOperationalAttribute(AciHandler.aciType)) ||
                 (newEntry.hasOperationalAttribute(AciHandler.aciType))) {
             try {
                 aciWriteLock.lock();
                 aciList.remove(oldEntry.getDN());
                 List<Attribute> attributeList =
                     newEntry.getOperationalAttribute(AciHandler.aciType, null);
                 addAciAttributeListNoLock(newEntry.getDN(),attributeList);
             } finally {
                 aciWriteLock.unlock();
             }
         }
     }

    /**
     * Add an ACI using the DN as a key. If the DN already
     * has ACI(s) on the list, then the new ACI is added to the
     * end of the linked list.
     * @param dn The DN to use as the key.
     * @param aci  The ACI to add to the list.
     */
    public void addAci(DN dn, Aci aci)  {
        if(aciList.containsKey(dn)) {
            Aci tmpAci = aciList.get(dn);
            while(tmpAci.next != null)
                tmpAci=tmpAci.next;
            tmpAci.next=aci;
        } else
            aciList.put(dn, aci);
    }

    /**
     * Remove ACIs related to an entry.
     * @param entry The entry to be removed.
     * @return True if the ACI set was deleted.
     */
    public boolean removeAci(Entry entry) {
        boolean deleted = false;
        try {
            aciWriteLock.lock();
            if (aciList.remove(entry.getDN()) != null)
                deleted = true;
        } finally {
            aciWriteLock.unlock();
        }
        return deleted;
    }

    /**
     * Remove all ACIs related to a backend.
     * @param backend  The backend to check if each DN is handled by that
     * backend.
     */
    public void removeAci (Backend backend) {
        try {
            aciWriteLock.lock();
            Set<DN> keys=aciList.keySet();
            for(DN dn : keys) {
                if (backend.handlesEntry(dn))
                    aciList.remove(dn);
            }
        } finally {
            aciWriteLock.unlock();
        }
    }
    // Replace the ACI list with the copy.
    aciList = aciCopy;
  }
}

 opends/src/server/org/opends/server/authorization/dseecompat/AciListenerManager.java

@@ -39,20 +39,12 @@
import static org.opends.server.loggers.debug.DebugLogger.debugCought;
import static org.opends.server.loggers.debug.DebugLogger.debugEnabled;
import static org.opends.server.loggers.Error.logError;
import org.opends.server.types.DebugLogLevel;
import org.opends.server.types.DN;
import org.opends.server.types.DereferencePolicy;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.ErrorLogCategory;
import org.opends.server.types.ErrorLogSeverity;
import org.opends.server.types.SearchFilter;
import org.opends.server.types.SearchResultEntry;
import org.opends.server.types.SearchScope;
import org.opends.server.types.*;
import static org.opends.server.authorization.dseecompat.AciMessages.*;
import static org.opends.server.messages.MessageHandler.getMessage;

import java.util.LinkedHashSet;
import java.util.List;

/**
 * The AciListenerManager updates an ACI list after each
@@ -113,7 +105,7 @@
     * @param entry   The entry being added.
     */
    public void handleAddOperation(PostResponseAddOperation addOperation,
            Entry entry) {
                                   Entry entry) {
        if(entry.hasOperationalAttribute(AciHandler.aciType))
        {
            aciList.addAci(entry);
@@ -129,9 +121,25 @@
     * @param newEntry  The new entry to examine.
     */
    public void handleModifyOperation(PostResponseModifyOperation modOperation,
            Entry oldEntry, Entry newEntry)
                                      Entry oldEntry, Entry newEntry)
    {
      // A change to the ACI list is expensive so let's first make sure that
      // the modification included changes to the ACI.
      boolean hasAciMod = false;
      List<Modification> mods = modOperation.getModifications();
      for (Modification mod : mods)
      {
        if (mod.getAttribute().getAttributeType().equals(AciHandler.aciType))
        {
          hasAciMod = true;
          break;
        }
      }

      if (hasAciMod)
      {
        aciList.modAciOldNewEntry(oldEntry, newEntry);
      }
    }

    /**
@@ -155,58 +163,56 @@
     * ACI list.
     */
    public void performBackendInitializationProcessing(Backend backend) {
        InternalClientConnection conn =
                InternalClientConnection.getRootConnection();
        for (DN baseDN : backend.getBaseDNs()) {
            try {
                if (! backend.entryExists(baseDN))  {
                    continue;
                }
            } catch (Exception e) {
              if (debugEnabled())
              {
                debugCought(DebugLogLevel.ERROR, e);
              }
                //TODO log message
                continue;
            }
            InternalSearchOperation internalSearch =
                    new InternalSearchOperation(conn,
                            InternalClientConnection.nextOperationID(),
                            InternalClientConnection.nextMessageID(),
                            null, baseDN, SearchScope.WHOLE_SUBTREE,
                            DereferencePolicy.NEVER_DEREF_ALIASES,
                            0, 0, false, aciFilter, attrs, null);
            try
            {
                backend.search(internalSearch);
            } catch (Exception e) {
              if (debugEnabled())
              {
                debugCought(DebugLogLevel.ERROR, e);
              }
                //TODO log message
                continue;
            }
            if(internalSearch.getSearchEntries().isEmpty()) {
                int    msgID  = MSGID_ACI_ADD_LIST_NO_ACIS;
                String message = getMessage(msgID, String.valueOf(baseDN));
                logError(ErrorLogCategory.ACCESS_CONTROL,
                        ErrorLogSeverity.NOTICE, message, msgID);
            } else {
                int validAcis=0;
                for (SearchResultEntry entry :
                        internalSearch.getSearchEntries()) {
                    validAcis += aciList.addAci(entry);
                }
                int    msgID  = MSGID_ACI_ADD_LIST_ACIS;
                String message = getMessage(msgID, Integer.toString(validAcis),
                        String.valueOf(baseDN));
                logError(ErrorLogCategory.ACCESS_CONTROL,
                        ErrorLogSeverity.NOTICE,
                        message, msgID);
            }
      InternalClientConnection conn =
           InternalClientConnection.getRootConnection();
      for (DN baseDN : backend.getBaseDNs()) {
        try {
          if (! backend.entryExists(baseDN))  {
            continue;
          }
        } catch (Exception e) {
          if (debugEnabled())
          {
            debugCought(DebugLogLevel.ERROR, e);
          }
          //TODO log message
          continue;
        }
        InternalSearchOperation internalSearch =
             new InternalSearchOperation(
                  conn,
                  InternalClientConnection.nextOperationID(),
                  InternalClientConnection.nextMessageID(),
                  null, baseDN, SearchScope.WHOLE_SUBTREE,
                  DereferencePolicy.NEVER_DEREF_ALIASES,
                  0, 0, false, aciFilter, attrs, null);
        try
        {
          backend.search(internalSearch);
        } catch (Exception e) {
          if (debugEnabled())
          {
            debugCought(DebugLogLevel.ERROR, e);
          }
          //TODO log message
          continue;
        }
        if(internalSearch.getSearchEntries().isEmpty()) {
          int    msgID  = MSGID_ACI_ADD_LIST_NO_ACIS;
          String message = getMessage(msgID, String.valueOf(baseDN));
          logError(ErrorLogCategory.ACCESS_CONTROL,
                   ErrorLogSeverity.NOTICE, message, msgID);
        } else {
          int validAcis = aciList.addAci(
               internalSearch.getSearchEntries());
          int    msgID  = MSGID_ACI_ADD_LIST_ACIS;
          String message = getMessage(msgID, Integer.toString(validAcis),
                                      String.valueOf(baseDN));
          logError(ErrorLogCategory.ACCESS_CONTROL,
                   ErrorLogSeverity.NOTICE,
                   message, msgID);
        }
      }
    }

    /**