From dev-return-38317-apmail-directory-dev-archive=directory.apache.org@directory.apache.org Mon Jun 13 20:12:49 2011 Return-Path: X-Original-To: apmail-directory-dev-archive@www.apache.org Delivered-To: apmail-directory-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id A0A61619E for ; Mon, 13 Jun 2011 20:12:49 +0000 (UTC) Received: (qmail 53528 invoked by uid 500); 13 Jun 2011 20:12:49 -0000 Delivered-To: apmail-directory-dev-archive@directory.apache.org Received: (qmail 53474 invoked by uid 500); 13 Jun 2011 20:12:49 -0000 Mailing-List: contact dev-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Apache Directory Developers List" Delivered-To: mailing list dev@directory.apache.org Received: (qmail 53463 invoked by uid 99); 13 Jun 2011 20:12:49 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 13 Jun 2011 20:12:49 +0000 X-ASF-Spam-Status: No, hits=-0.0 required=5.0 tests=SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of hyc@symas.com designates 64.71.152.235 as permitted sender) Received: from [64.71.152.235] (HELO lirone.symas.net) (64.71.152.235) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 13 Jun 2011 20:12:43 +0000 Received: from cpe-76-94-188-8.socal.res.rr.com ([76.94.188.8] helo=[192.168.1.22]) by lirone.symas.net with esmtpsa (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.72) (envelope-from ) id 1QWDUj-00061n-LW; Mon, 13 Jun 2011 13:12:21 -0700 Message-ID: <4DF66F11.70801@symas.com> Date: Mon, 13 Jun 2011 13:12:01 -0700 From: Howard Chu User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:7.0a1) Gecko/20110612 Firefox/7.0a1 SeaMonkey/2.4a1 MIME-Version: 1.0 To: Apache Directory Developers List CC: Ludovic Poitou , elecharny@apache.org Subject: Re: Alias cycle detection References: <4DF6213B.8060705@gmail.com> In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit X-Virus-Checked: Checked by ClamAV on apache.org Ludovic Poitou wrote: > Sun Directory Server, OpenDS, OpenDJ, Port 389 (formerly known as Fedora > Directory) at least, do not support Alias dereferencing because the complexity > out-weights the benefits, and very few client applications make use of it anyway. > > My 2 cents. We had no alias support in back-bdb originally; I added it back in 2003. Indeed, you only need to track all of the alias entries that you hit, and that's typically a small number. Each new entry defines a new search scope. Any time a dereference leads to an entry that resides anywhere within your already-known search scopes that deref can be considered fully resolved, because the result was already part of the scope. It's actually quite simple and quite fast. Using the objectclass index it's trivial to obtain the list of all alias entries within the database, so from the outset you already know the maximum size of what you're dealing with. And just to remind, alias deref is a 2-bit option - deref base of the search, and deref (the rest of the search). They're selected independently. > Ludo > --- > Ludovic Poitou > http://ludopoitou.wordpress.com > > > On Mon, Jun 13, 2011 at 4:39 PM, Emmanuel Lecharny > wrote: > > 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 dangerous…). > > 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) > > or > > 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 ? > > -- > Regards, > Cordialement, > Emmanuel Lécharny > www.iktek.com > > -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/