Introduction

Subentries are used for managing the administration of different aspects of the directory. LDAP has just recently formalized the notion of subentires in RFC 3672. Subentries have existed within X.500 Directories for years with clear specifications for administering collective attributes, schema, and access controls. Although LDAP has no equivalent yet for administering these aspects it is well on its way with RFC 3672 towards adopting and adapting these mechanisms from X.500 Directories. It is only a matter of time.

For this reason we intend to remain ahead of the curve by implementing these aspects of administration using Subentries and Administrative Areas similar to X.500 Directories.

This page describes how Subentries are implemented within ApacheDS according to RFC 3672. An understanding of this RFC and our implementation is critical for implementing administration mechanisms for the various mentioned aspects.

SubtreeSpecificationParser Class

Within the org.apache.ldap.common.subtree package there resides a SubtreeSpecificationParser which parses the value of a subtreeSpecification attribute as defined by RFC 3672. It generates a bean representation of the subtreeSpecification, a SubtreeSpecification instance. This parser is used by the subentry management subsystem of ApacheDS to create these objects to track and manage subtrees representing collections of entries.

SubtreeEvaluator Class

Within the org.apache.ldap.server.subtree package there resides a SubtreeEvaluator class. An evaluate() method in this class determines whether or not an entry is included by the entry collection described by a subtreeSpecification attribute present within a subentry.

The SubtreeEvaluator uses the SubtreeSpecification objects generated by SubtreeSpecificationParser instances. The evaluator is a critical component as we'll see later.

Tracking Entry Incusion in Subtrees

ApacheDS will need to rapidly determine which subentries an entry is contained in. This will be required for schema checking, access controls, and collective attribute handling. Eventually trigger handling and replication will also depend on this mechanism.

To determine the set of subentries including an entry we must use the SubtreeEvaluator on each subentry within a naming context. Searching for these subentries, then parsing their subtreeSpecification attribute values every time would be an extremely expensive task to perform for each operation. For this reason the subentry subsystem must load all subentry specifications at startup. The parsing of the subtreeSpecification attribute to generate instances of SubtreeSpecifcation beans would happen upon initialization of the subsystem. Furthermore the subsystem must track the addition, deletion and modification of subentry subtreeSpecifications to update this cache. Checking for inclusion with this cache eliminates the need to search for subentries and parse their subtreeSpecification attributes.

There still remains a considerable effort to evaluate all the subentry SubtreeSpecifications for each operation on an entry. When done once this information can be cached as well, however it can be permanantly stored with the entry using operational attributes. For this reason we use subentry operational attributes within entries to reference the subentries whose subtreeSpecification includes them. Such operational attributes can have a value or multiple values containing the DN of the subentry. A different subentry operational attribute is used for each type of administrativeRole associated with the Administrative Point corresponding to the subentry. Hence a subentry operational attribute for accessControlSpecificAreas for example can contain zero or more values pointing to subentries responsible for Directory Acces Control Domains (DACD). Partitioning the operational attributes according to the administrativeRoles further reduces the processing overhead for locating including subentries for an entry based on functional needs. These subentry operational attributes are injected automatically into entries by the subentry subsystem on add operations. They are modified whenever the subtreeSpecification value on subentries are altered or the name of and entry is changed via a modifyRdn operation. Note that these operational attributes also make it easier to search for entries included within a subentry's subtree.

Subentry Subsystem Implementation

The subentry subsystem must search for all subentries corresponding to a naming context and parse their subtreeSpecifications on startup. The SubtreeSpecification objects are cached in memory using a hash. The normalized DN of the subentry is used as the key into this hash.

The subsystem uses an interceptor to detect the addition, deletion and modification of subentries to update this cache with new information. This way a restart will not be required to update the cache when administrative changes are made via subentry modifications.

Whenever an entry is added or its name is changed via a modifyRdn operation, the interceptor traps these calls and evaluates or re-evaluates the subentry operational attributes for that entry. The cache of SubtreeSpecifications is accessed to test for inclusion of that entry within a subentry's subtree.

The subsystem may partition the SubtreeSpecification cache based on the naming context under which its subentry is located. Partitioning the space this way reduces the overall search for including subtrees.

Actions to take on operations

Operations on Subentries

• Add Subentry
  • Parse and add SubtreeSpecification of the Subentry to cache
  • Find and update the subentry operational attributes of all entries included by the new subtreeSpecification
• Delete Subentry
  • Remove the SubtreeSpecification of the Subentry from the cache
  • Find all entries that were included in the subtree and remove references to the subentry
• Modify Subentry's subtreeSpecification Attribute
  • Remove all entry references to the subentry's according to the old subtree
  • Remove the old SubtreeSpecification from the SS cache
  • Parse and add the new SubtreeSpecification to the SS cache
  • Find all entries selected by the new SubtreeSpecification and update their operational attributes to point to the subentry
• ModifyRdn on Subentry
  • Lookup all entries that reference the old name of the subentry and replace those operational attributes with the new name

Operations on Entries

• Add Entry
  • Check to see if the entry is included by any SubtreeSpecifications
  • If it is add the appropriate subentry operational attributes to the entry to reference the subentry
• ModifyRdn
  • Some specific exclusions may cause Rdn name changes to affect inclusion so we have to remove all subentry operational attributes within the entry and recompute then once again.
  • Operations that change the names of administrative points directly via a modifyRdn on the AP or via one of the AP's ancestors cannot be permitted. The reason is these changes would change the name of subentries referenced by entries in scope below the AP. To move an AP the user must make it a normal entry first.

Subentry Operational Attributes in Entries

Our approach here is justified in part by the use of subschemaSubentry operational attributes which point to subentries managing schema information for an entry. We will expand on this concept for the other aspects of administration, namely for access control and collective attribute management. RFC 3672 defines the following administrativeRole values for an administrative point:

We propose the following subentry operational attribute types to be used to correspond to these administrativeRoles:

Collective Attributes: a good simple usecase

Collective attributes use subentries and are perhaps the simplest mechanism by which we can demonstrate the use of subentries. Here is an RFC for LDAP that describes how: RFC 3671

Looking Ahead

It's a safe bet to partition the SubtreeSpecification cache based on the naming context of a subentry. However better results may be achieved by partitioning the cache based on administrative areas and their roles. An approach here is yet to be determined.

Grammar used to implement SubtreeSpecification

Take a look at the subtree specification grammar here SubtreeSpecificationGrammar.