Creating an alias from a child entry to the ancestor causes an error (return code 36)

• Key: DIRSERVER-803
• Type: Bug
• Status: Open
• Priority: Major
• Assignee: Alex Karasulu
• Reporter: Stefan Zoerner
• Component/s: core
• Affects Version/s: 1.5.1, 1.5.0, 1.0.2, 1.0.1, 1.0
• Fix Version/s: 2.0.0-RC1

Environment

* ApacheDS 1.0.0
* Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-b03)
* Windows XP Professional SP2

Description

It fails to import the following two entries into ApacheDS 1.0 (default server.xml).
The second entry is an alias to the first one, and is directly located below the first entry:

dn: ou=Singers,dc=example,dc=com
ou: Singers
objectclass: top
objectclass: organizationalUnit

dn: ou=Songwriters,ou=Singers,dc=example,dc=com
ou: Songwriters
objectclass: top
objectclass: organizationalUnit
objectclass: alias
aliasedobjectname: ou=Singers,dc=example,dc=com

Here is the result I got from an ldapmodify attempt:

$ ldapmodify -h localhost -p 10389 -D "uid=admin,ou=system" -w ****** -q -c -a -f aliasSingers.ldif
ldap_add: Unknown error
ldap_add: additional info: failed to add entry ou=Songwriters,ou=Singers,dc=example,dc=com: [36] aliasDereferencingProblem - attempt to create alias with cycle to relative ou=Singers,dc=example,dc=com not allowed from descendent alias 2.5.4.11=songwriters,2.5.4.11=singers,0.9.2342.19200300.100.1.25=example,0.9.2342.19200300.100.1.25=com

It seems that ApacheDS does not allow to create an alias from a descendant. I tried the same with Tivoli Directory Server 6.0 and Sun Java System Directory Server 5.2, both allowed this constellation.

Find attached a JNDI JUnit test which is able to cause the error by adding two entries programmatically.

Comments

[Stefan Zoerner]

Test case to demonstrate DIRSERVER-803. Uses JNDI and its LDAP provider to connect to ApacheDS and perform the two add operations described in the original issue description.

[Emmanuel Lecharny]

Oh...

The error message is pretty clear : there is a cycle. If you do a search starting at the top level and with a Whole Subtree scope, you will have an infinite loop.

The question is : do we detect such cycle when inserting data, or do we stop to search further as soon as we found an entry which is already in the result set ?

I don't know if adding such a ldif is valid :

dn: ou=A, dc=example, dc=com
ou: A
objectclass: top
objectclass: organizationalUnit

dn: ou=B, dc=example, dc=com
ou: B
objectclass: top
objectclass: organizationalUnit

dn: ou=A->B, ou=A, dc=example, dc=com
ou: A->B
objectclass: top
objectclass: organizationalUnit
objectclass: alias
aliasedobjectname: ou=B, dc=example, dc=com

dn: ou=B->A, ou=B, dc=example, dc=com
ou: B->A
objectclass: top
objectclass: organizationalUnit
objectclass: alias
aliasedobjectname: ou=A, dc=example, dc=com

There is a cycle, but it will be difficult to find it when being added.

On the other side, if we try to detect a cycle during a search, we may have to store a hashmap of seen DN to check that a DN has not been already seen, which myth be very memory consumming (especially if we have a big search ...)

Not a simple question, no simple solutions ...

From my point of view, we should favor the second solution (detection while searching) but with a check test when adding, and an optionnal setting of the server to allow a check/denial when adding, modifying or modifyRDNing entries.

wdyt ?

[Emmanuel Lecharny]

There is no simple way to have this problem fixed for 1.0.1. Even for 1.5.0, it will be clearly a challenge : we have chosen a strategy to deal with aliases which forbid direct cycles. Do we have to change this ?

[Emmanuel Lecharny]

This is a problematic issue : if we don't fix it, we can't reach the STANDARD certification. However, this is not easy to fix, if only we can fix it.

Postponed to 1.5.1

[Emmanuel Lecharny]

Postponed to 1.5.2, but it will soon become a must-have feature !

[Alex Karasulu]

Yep you guys are right the server's alias handling code presumes cycles do
not exist from descendant entries to any one of their ancestors. The algorithm
could be modified to handle these cycles but that's not a quick endeavor so
I will put it off as E suggested.

[Alex Karasulu]

Ooops I forgot to delay it.

[Emmanuel Lecharny]

Still has to be fixed... Postponed.

[Alex Karasulu]

Can't postpone this anymore must be fixed next time.

[Kiran Ayyagari]

From the 2nd comment
"On the other side, if we try to detect a cycle during a search, we may have to store a hashmap of seen DN to check that a DN has not been already seen, which myth be very memory consumming (especially if we have a big search ...)"

How about using UUID instead of DN?

[Emmanuel Lecharny]

As soon as we have UUID, that's the one to use.

However, I don't know if it's a good idea to allow cycle to be created when injecting aliases on an ancestor.

[Stefan Seelmann]

I'm working on alias issues, see DIRSERVER-1355 and DIRSERVER-1349.

I think the detection of cycles during search isn't that hard, the algorithm is described here: http://cwiki.apache.org/confluence/display/DIRxSRVx11/Structure+and+Organization#StructureandOrganization-HandlingDereferencingwithSubtreeLevelScope.

I already implemented it for the SubtreeScopeCursor: The idea is to collect a list of all search bases that are relevant for a subtree search, create a cursor for each base and switch between these cursors. Therefore I use the ID of the provided search base and recursively get all dereferenced aliases using the subtree alias index. Only if the dereferenced alias extends the search scope it is added to the list. Additional descendants of the added search scope are removed from the list. The cycle detection is simple because we only need to check if a dereferenced alias is already contained in this list. In that case we could just quit the current recursion.

I would voluneer for this issue. The SubtreeScopeCursor implementation seems to work, I just add some more test cases and check the behaviour of other LDAP servers. Atm I don't understand what the SubtreeScopeEvaluator is used for...

[Emmanuel Lecharny]

Postponed to 2.0.0-RC1