directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <>
Subject Alias cycle detection
Date Mon, 13 Jun 2011 14:39:55 GMT
Alias cycle detection

There is an unsolved question about how we should detect Alias cycles. 
Right now, we check for cycles *before* they are created. The 
alternative would be to stop any search that could lead to an infinite loop.

A third - but unrealistic - solution would be to don't detect cycle, and 
process the search until we reach the time or size limit (in other 
words, it's up to the admin to avoid the creation of such cycle; Highly 

The problem with the first approach is that we can't anymore pass the 
VSLDAP tests. It's a major burden. Also most of the current servers 
support this feature.

So it seems that everything concurs to get the cycle be detected while 
searching, not before. Now, how can we do that efficiently ?

Detecting a cycle is a pretty obvious algorithm : every entry we went 
through should be memorized, and we should check that we aren't going 
through an entry we already returned.

This is easy, but highly memory consuming, as we have to keep track of 
*all* the entries during a search. Simply idealistic.

Hopefully, we can use a simplified algorithm : if we hit an Alias, we 
have to check that we don't come back to the original DN we came from, 
or one of its descendant. We should also memorize each indirection (each 
of them is like a new search)

initial search : A.B.C -~-> a(alias)  (A.B.C memorized)
a -~-> B.C… -~-> A.B.C : cycle detected (B.C memorized)


initial search : A.B.C -~-> a(alias)  (A.B.C memorized)
a -~-> D.E… -~-> b(alias) : (D.E memorized)
b -~-> B.C… -~-> A.B.C : cycle detected (B.C memorized)

This way we only have to memorize the roots for all searches, instead of 
memorize all he entries. As we are very unlikely to have many aliases 
and many indirection, it should be safe from the memory consumption POV.

One other aspect is that this should be only done if the user has 
required that we dereference aliases on the server.

Last, not least, if the user has sent the ManageDSAIt control, we should 
not have to memorize anything either, as we don't dereference aliases in 
this case.

The DN cache will be stored in the session, and removed as soon as we 
reached the end of the search. It will be associated with the message 
ID, so that a user can issue more than one search in parallel.

thoughts ?

Emmanuel Lécharny

View raw message