My 2 cents.

Ludo
---
Ludovic Poitou
http://ludopoitou.wordpress.com

On Mon, Jun 13, 2011 at 4:39 PM, Emmanue= l Lecharny wrote:
Alias cycle detection
---------------------

There is an unsolved question about how we should detect Alias cycles. Righ= t 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, an= d 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 dange= rous=E2=80=A6).

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

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

Detecting a cycle is a pretty obvious algorithm : every entry we went throu= gh should be memorized, and we should check that we aren't going throug= h 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 on= e of its descendant. We should also memorize each indirection (each of them= is like a new search)

initial search : A.B.C -~-> a(alias) =C2=A0(A.B.C memorized)
a -~-> B.C=E2=80=A6 -~-> A.B.C : cycle detected (B.C memorized)

or

initial search : A.B.C -~-> a(alias) =C2=A0(A.B.C memorized)
a -~-> D.E=E2=80=A6 -~-> b(alias) : (D.E memorized)
b -~-> B.C=E2=80=A6 -~-> A.B.C : cycle detected (B.C memorized)

This way we only have to memorize the roots for all searches, instead of me= morize all he entries. As we are very unlikely to have many aliases and man= y 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 no= t 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 reach= ed the end of the search. It will be associated with the message ID, so tha= t a user can issue more than one search in parallel.

thoughts ?

--
Regards,
Cordialement,
Emmanuel L=C3=A9charny
www.iktek.com

--000e0cd47c427cc01404a599fc67--