Make AciList reads lock-free with true copy-on-write (#674)

Valery Kharseko

3 days ago a5caf29be545e56b13ccd67e45e56bff6c05366f

Make AciList reads lock-free with true copy-on-write (#674)

 opendj-server-legacy/src/main/java/org/opends/server/authorization/dseecompat/AciList.java

@@ -13,6 +13,7 @@
 *
 * Copyright 2008-2010 Sun Microsystems, Inc.
 * Portions Copyright 2013-2016 ForgeRock AS.
 * Portions Copyright 2026 3A Systems, LLC
 */
package org.opends.server.authorization.dseecompat;

@@ -26,7 +27,7 @@
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.slf4j.LocalizedLogger;
@@ -48,15 +49,21 @@

  /**
   * A map containing all the ACIs.
   * We use the copy-on-write technique to avoid locking when reading.
   * We use the copy-on-write technique to avoid locking when reading:
   * mutators build a copy of the map (with copied value lists), modify the
   * copy and publish it through this volatile reference. A published map is
   * never modified in place, so getCandidateAcis() can read it lock-free —
   * it runs for every access-controlled operation, and even a read lock
   * becomes a cross-core hotspot under load. Aci instances themselves are
   * treated as immutable once published: the map and its value lists are
   * the only mutable containers.
   */
  private volatile DITCacheMap<List<Aci>> aciList = new DITCacheMap<>();

  /**
   * Lock to protect internal data structures.
   * Lock serializing mutators (ACI additions, removals and renames are rare).
   */
  private final ReentrantReadWriteLock lock =
          new ReentrantReadWriteLock();
  private final ReentrantLock lock = new ReentrantLock();

  /** The configuration DN used to compare against the global ACI entry DN. */
  private final DN configDN;
@@ -87,46 +94,56 @@
      return candidates;
    }

    lock.readLock().lock();
    try
    {
      //Save the baseDN in case we need to evaluate a global ACI.
      DN entryDN=baseDN;
      while (baseDN != null) {
        List<Aci> acis = aciList.get(baseDN);
        if (acis != null) {
          //Check if there are global ACIs. Global ACI has a NULL DN.
          if (baseDN.isRootDN()) {
            for (Aci aci : acis) {
              AciTargets targets = aci.getTargets();
              //If there is a target, evaluate it to see if this ACI should
              //be included in the candidate set.
              if (targets != null
                  && AciTargets.isTargetApplicable(aci, targets, entryDN))
              {
                  candidates.add(aci);  //Add this ACI to the candidates.
              }
    // Lock-free read of the copy-on-write map: mutators never modify a
    // published map or its value lists in place.
    final DITCacheMap<List<Aci>> aciList = this.aciList;
    //Save the baseDN in case we need to evaluate a global ACI.
    DN entryDN=baseDN;
    while (baseDN != null) {
      List<Aci> acis = aciList.get(baseDN);
      if (acis != null) {
        //Check if there are global ACIs. Global ACI has a NULL DN.
        if (baseDN.isRootDN()) {
          for (Aci aci : acis) {
            AciTargets targets = aci.getTargets();
            //If there is a target, evaluate it to see if this ACI should
            //be included in the candidate set.
            if (targets != null
                && AciTargets.isTargetApplicable(aci, targets, entryDN))
            {
                candidates.add(aci);  //Add this ACI to the candidates.
            }
          } else {
            candidates.addAll(acis);
          }
        }
        if(baseDN.isRootDN()) {
          break;
        }
        DN parentDN=baseDN.parent();
        if(parentDN == null) {
          baseDN=DN.rootDN();
        } else {
          baseDN=parentDN;
          candidates.addAll(acis);
        }
      }
      return candidates;
      if(baseDN.isRootDN()) {
        break;
      }
      DN parentDN=baseDN.parent();
      if(parentDN == null) {
        baseDN=DN.rootDN();
      } else {
        baseDN=parentDN;
      }
    }
    finally
    return candidates;
  }

  /**
   * Returns a copy of the current ACI map with copied value lists, suitable
   * for mutation and subsequent publication through the volatile reference.
   * Must be called while holding the write lock.
   */
  private DITCacheMap<List<Aci>> copyAciList()
  {
    DITCacheMap<List<Aci>> copy = new DITCacheMap<>();
    for (Map.Entry<DN, List<Aci>> entry : aciList.entrySet())
    {
      lock.readLock().unlock();
      copy.put(entry.getKey(), new LinkedList<>(entry.getValue()));
    }
    return copy;
  }

  /**
@@ -141,22 +158,24 @@
  public int addAci(List<? extends Entry> entries,
                                 LinkedList<LocalizableMessage> failedACIMsgs)
  {
    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      int validAcis = 0;
      for (Entry entry : entries) {
        DN dn=entry.getName();
        List<Attribute> attributeList =
             entry.getOperationalAttribute(AciHandler.aciType);
        validAcis += addAciAttributeList(aciList, dn, configDN,
        validAcis += addAciAttributeList(copy, dn, configDN,
                                         attributeList, failedACIMsgs);
      }
      aciList = copy;
      return validAcis;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -170,14 +189,16 @@
   *
   */
  public void addAci(DN dn, SortedSet<Aci> acis) {
    lock.writeLock().lock();
    lock.lock();
    try
    {
      aciList.put(dn, new LinkedList<>(acis));
      DITCacheMap<List<Aci>> copy = copyAciList();
      copy.put(dn, new LinkedList<>(acis));
      aciList = copy;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -195,29 +216,31 @@
  public int addAci(Entry entry, boolean hasAci,
                                 boolean hasGlobalAci,
                                 List<LocalizableMessage> failedACIMsgs) {
    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      int validAcis = 0;
      //Process global "ds-cfg-global-aci" attribute type. The oldentry
      //DN is checked to verify it is equal to the config DN. If not those
      //attributes are skipped.
      if(hasGlobalAci && entry.getName().equals(configDN)) {
          List<Attribute> attributeList = entry.getAllAttributes(globalAciType);
          validAcis = addAciAttributeList(aciList, DN.rootDN(), configDN,
          validAcis = addAciAttributeList(copy, DN.rootDN(), configDN,
                                          attributeList, failedACIMsgs);
      }

      if(hasAci) {
          List<Attribute> attributeList = entry.getAllAttributes(aciType);
          validAcis += addAciAttributeList(aciList, entry.getName(), configDN,
          validAcis += addAciAttributeList(copy, entry.getName(), configDN,
                                           attributeList, failedACIMsgs);
      }
      aciList = copy;
      return validAcis;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -282,31 +305,33 @@
                                             boolean hasAci,
                                             boolean hasGlobalAci) {

    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      List<LocalizableMessage> failedACIMsgs=new LinkedList<>();
      //Process "aci" attribute types.
      if(hasAci) {
          aciList.remove(oldEntry.getName());
          copy.remove(oldEntry.getName());
          List<Attribute> attributeList =
                  newEntry.getOperationalAttribute(aciType);
          addAciAttributeList(aciList,newEntry.getName(), configDN,
          addAciAttributeList(copy,newEntry.getName(), configDN,
                              attributeList, failedACIMsgs);
      }
      //Process global "ds-cfg-global-aci" attribute type. The oldentry
      //DN is checked to verify it is equal to the config DN. If not those
      //attributes are skipped.
      if(hasGlobalAci && oldEntry.getName().equals(configDN)) {
          aciList.remove(DN.rootDN());
          copy.remove(DN.rootDN());
          List<Attribute> attributeList = newEntry.getAllAttributes(globalAciType);
          addAciAttributeList(aciList, DN.rootDN(), configDN,
          addAciAttributeList(copy, DN.rootDN(), configDN,
                              attributeList, failedACIMsgs);
      }
      aciList = copy;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -343,24 +368,28 @@
   */
  public boolean removeAci(Entry entry,  boolean hasAci,
                                                      boolean hasGlobalAci) {
    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      DN entryDN = entry.getName();
      if (hasGlobalAci && entryDN.equals(configDN) &&
          aciList.remove(DN.rootDN()) == null)
          copy.remove(DN.rootDN()) == null)
      {
        aciList = copy;
        return false;
      }
      boolean result = true;
      if (hasAci || !hasGlobalAci)
      {
        return aciList.removeSubtree(entryDN, null);
        result = copy.removeSubtree(entryDN, null);
      }
      return true;
      aciList = copy;
      return result;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -371,11 +400,12 @@
   */
  public void removeAci(LocalBackend<?> backend) {

    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      Iterator<Map.Entry<DN,List<Aci>>> iterator =
              aciList.entrySet().iterator();
              copy.entrySet().iterator();
      while (iterator.hasNext())
      {
        Map.Entry<DN,List<Aci>> mapEntry = iterator.next();
@@ -384,10 +414,11 @@
          iterator.remove();
        }
      }
      aciList = copy;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }

@@ -399,12 +430,13 @@
   */
  public void renameAci(DN oldDN, DN newDN ) {

    lock.writeLock().lock();
    lock.lock();
    try
    {
      DITCacheMap<List<Aci>> copy = copyAciList();
      Map<DN,List<Aci>> tempAciList = new HashMap<>();
      Iterator<Map.Entry<DN,List<Aci>>> iterator =
              aciList.entrySet().iterator();
              copy.entrySet().iterator();
      while (iterator.hasNext()) {
        Map.Entry<DN,List<Aci>> hashEntry = iterator.next();
        DN keyDn = hashEntry.getKey();
@@ -427,11 +459,12 @@
          iterator.remove();
        }
      }
      aciList.putAll(tempAciList);
      copy.putAll(tempAciList);
      aciList = copy;
    }
    finally
    {
      lock.writeLock().unlock();
      lock.unlock();
    }
  }
}

 opendj-server-legacy/src/test/java/org/opends/server/authorization/dseecompat/AciListTests.java

New file
@@ -0,0 +1,161 @@
/*
 * The contents of this file are subject to the terms of the Common Development and
 * Distribution License (the License). You may not use this file except in compliance with the
 * License.
 *
 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
 * specific language governing permission and limitations under the License.
 *
 * When distributing Covered Software, include this CDDL Header Notice in each file and include
 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
 * Header, with the fields enclosed by brackets [] replaced by your own identifying
 * information: "Portions Copyright [year] [name of copyright owner]".
 *
 * Copyright 2026 3A Systems, LLC
 */
package org.opends.server.authorization.dseecompat;

import static org.testng.Assert.*;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.DN;
import org.opends.server.DirectoryServerTestCase;
import org.opends.server.TestCaseUtils;
import org.opends.server.types.Entry;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * Locks in the copy-on-write contract of {@link AciList}: readers snapshot
 * the map through the volatile reference without locking, so mutators must
 * never modify a published map or its value lists in place.
 */
@SuppressWarnings("javadoc")
public class AciListTests extends DirectoryServerTestCase
{
  @BeforeClass
  public void setUp() throws Exception
  {
    // The full server schema is needed for "aci" to be an operational
    // attribute, which the Entry-based append path relies on.
    TestCaseUtils.startServer();
  }

  @Test(timeOut = 60000)
  public void testCandidateSnapshotsUnderConcurrentMutation() throws Exception
  {
    final DN aciDN = DN.valueOf("dc=example,dc=com");
    final DN queryDN = DN.valueOf("uid=user.0,ou=People,dc=example,dc=com");
    // Off the query path: churned to force structural map changes.
    final DN movingDnA = DN.valueOf("ou=A,dc=example,dc=com");
    final DN movingDnB = DN.valueOf("ou=B,dc=example,dc=com");
    final AciList aciList = new AciList(DN.valueOf("cn=Access Control Handler,cn=config"));

    final Aci aci1 = Aci.decode(ByteString.valueOfUtf8(
        "(version 3.0; acl \"cow test 1\"; allow(all) userdn=\"ldap:///anyone\";)"), aciDN);
    final Aci aci2 = Aci.decode(ByteString.valueOfUtf8(
        "(version 3.0; acl \"cow test 2\"; allow(read) userdn=\"ldap:///all\";)"), aciDN);
    final SortedSet<Aci> oneAci = new TreeSet<>();
    oneAci.add(aci1);
    final SortedSet<Aci> twoAcis = new TreeSet<>();
    twoAcis.add(aci1);
    twoAcis.add(aci2);

    // Entry whose "aci" attribute is APPENDED to the existing list under
    // aciDN by addAci(List<Entry>, ...): with copy-on-write the append goes
    // to a fresh copy; an in-place append would mutate the published list
    // under the readers' fail-fast iterators.
    final Entry appendEntry = TestCaseUtils.makeEntry(
        "dn: " + aciDN,
        "objectClass: top",
        "objectClass: domain",
        "dc: example",
        "aci: (version 3.0; acl \"cow test 2\"; allow(read) userdn=\"ldap:///all\";)");

    aciList.addAci(aciDN, oneAci);
    aciList.addAci(movingDnA, oneAci);

    // Sanity-check the append channel before relying on it for churn.
    final LinkedList<LocalizableMessage> failedACIMsgs = new LinkedList<>();
    aciList.addAci(Collections.singletonList(appendEntry), failedACIMsgs);
    assertTrue(failedACIMsgs.isEmpty(), String.valueOf(failedACIMsgs));
    assertEquals(aciList.getCandidateAcis(queryDN).size(), 2,
        "addAci(List<Entry>) must append to the list under aciDN");
    aciList.addAci(aciDN, oneAci);

    final AtomicBoolean done = new AtomicBoolean();
    final AtomicReference<Throwable> failure = new AtomicReference<>();
    Thread[] readers = new Thread[3];
    for (int i = 0; i < readers.length; i++)
    {
      readers[i] = new Thread("AciList COW reader " + i)
      {
        @Override
        public void run()
        {
          try
          {
            while (!done.get())
            {
              // Iterates the published value lists: an in-place mutator
              // would make this throw or return a torn snapshot.
              List<Aci> candidates = aciList.getCandidateAcis(queryDN);
              int size = candidates.size();
              if (size != 1 && size != 2)
              {
                throw new AssertionError("Torn candidate snapshot: " + candidates);
              }
            }
          }
          catch (Throwable t)
          {
            failure.compareAndSet(null, t);
          }
        }
      };
      readers[i].start();
    }

    try
    {
      for (int i = 0; i < 50000 && failure.get() == null; i++)
      {
        // Append a second ACI to the list under aciDN, then reset to one.
        aciList.addAci(Collections.singletonList(appendEntry), failedACIMsgs);
        aciList.addAci(aciDN, oneAci);
        // Structural churn off the query path: rename moves the key
        // through iterator.remove() and putAll() on every iteration.
        if (i % 2 == 0)
        {
          aciList.renameAci(movingDnA, movingDnB);
        }
        else
        {
          aciList.renameAci(movingDnB, movingDnA);
        }
        assertTrue(failedACIMsgs.isEmpty(), String.valueOf(failedACIMsgs));
      }
    }
    finally
    {
      done.set(true);
      for (Thread reader : readers)
      {
        reader.join(10000);
      }
    }
    if (failure.get() != null)
    {
      fail("Reader failed under concurrent ACI mutation", failure.get());
    }
  }
}