From 196ca99c14ab4aeee0c76c90fce0b72ab4e102f4 Mon Sep 17 00:00:00 2001
From: coulbeck <coulbeck@localhost>
Date: Thu, 01 Mar 2007 19:30:17 +0000
Subject: [PATCH] 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/AciList.java | 419 +++++++++++++++++++++++++++++++----------------------------
1 files changed, 223 insertions(+), 196 deletions(-)
diff --git a/opends/src/server/org/opends/server/authorization/dseecompat/AciList.java b/opends/src/server/org/opends/server/authorization/dseecompat/AciList.java
index 62f81e5..f9d2b24 100644
--- a/opends/src/server/org/opends/server/authorization/dseecompat/AciList.java
+++ b/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;
+ }
}
--
Gitblit v1.10.0