Re: aliased bases

[Robert Streich <streich@austin.apc.slb.com>]

> > I took a slightly different approach. I didn't want to have to touch
> > every call to dn2entry() in order to propagate the deref option, I let
> > dn2entry() fail, then check to see if the "matched" string is an alias.
> > If it is, I resolve it (traversing a chain if necessary), then swap
> > out the DN of the target entry with the "matched" portion of the
> > original entry, then retrieve the original entry with the new DN.
> > This way I only have to change the parameter list of and calls to
> > base_candidates(), onelevel_candidates(), and subtree_candidates().
> > This also makdes it easier to apply the right logic with the deref
> > parameters. For example, in base_candidates(), you only need to test
> > for "finding" and "always" since "searching" doesn't apply here.
> 
> Perhaps I missed something in your description, but it seems to me this does not work
> for all cases.  The search method uses dn2id when there is a filter present, then
> id2entry.   It does not use dn2entry for parts other than the search root. If you
> search for an entry based on some filter and the alias object is returned, the alias
> will not be dereferenced.
>
> I think the parts we have done are complementary though.  What you describe seems to be
> the part that dereferences information from the base when the base fails, the part
> I have done dereferences when the alias is a candidate.

The problem here is that unless you add another search filter, the alias entries
will most likely not be among the candidates.

> > Anyway, the last step is traversing the aliases below the base. It
> > looks to me like the search routines fetch all entries that match the
> > filter and then sort out the ones that apply given the scoping parameters.
> > If this is the case, then it seems that the thing to do is to fetch
> > all of the aliases, sort through the paths to get only those that are
> > applicable, then test the scope of the returned candidates against a
> > list of paths rather than just the original base.
> 
> Yes, that is how they work.  I am unsure what you mean by "fetch all of the aliases".
> At the stage the candidates are being checked you will need to traverse up the DIT
> looking for aliases unless the entry itself is an alias.  Is that what you mean?

We only have this issue in one-level and subtree searches. I wrote the algorithms
below that should work.

One-level algorithm--here all we are concerned about are aliases that are children
of base:

    alias_list = fetch_aliases() /* Get all alias entries from the db */
    /* Collect all aliases that are children of base */
    foreach i in alias_list
	if dn_parent(alias_list[i]) == base
	    if alias_list[i].aliasedObjectName notin child_list
	    	insert(child_list, alias_list[i].aliasedObjectName)
	    fi
	    delete alias_list[i]
	fi
    done
    /* Then resolve any alias chains */
    do
    	found = false
    	foreach i in alias_list
	    foreach j in child_list
	    	if alias_list[i] == child_list[j]
	            if alias_list[i].aliasedObjectName notin child_list
	            	insert(child_list, alias_list[i].aliasedObjectName)
	            fi
	            delete child_list[j]
	            delete alias_list[i]
	            found = true
	    	fi
	    done
	done
    while found = true
    
I'd leave all the existing code in place and just fetch any entries in child_list,
test them against the filter, and either add them to the results or discard them.

Subtree algorithm ("vertex_list" is the list of all of the scoping vertices in the
tree that is initialized with the search "base")--here we have to convert the single
vertex base into a list of vertices:

    alias_list = fetch_aliases() /* Get all alias entries from the db */
    insert(vertex_list, base);
    do
    	found = false;
	foreach i in alias_list
	    foreach j in vertex_list
		if dn_issuffix(alias_list[i], vertex_list[j])
		    foreach k in vertex_list
		    	/* dn_issuffix() returns true if the two are equal also. */
		        if not dn_issuffix(alias_list[i].aliasedObjectName, vertex_list[j])
		    	    insert(vertex_list, alias_list[i].aliasedObjectName)
		    	fi
		    done
		    found = true;
		    remove element i from alias_list
		fi
	    done
	done
    while found = true
    
Then you have to test each candidate to see if it has a parent in the vertex_list.
The rest of the code is intact.

I can't use an array for the vertex_list as the algorithms imply. That would make
the time complexity exponential. I'll have to add the code for a more optimal
data structure.

I think these are right. If anyone sees any errors, please let me know. I didn't
spend all that much time on them for the first pass.

> > All this leaves out is cycle detection. However, I got a partial response
> > from Wahl to some questions on the issue that leads me to believe that
> > cycles are non-issues:
> 
> By cycles I assume you mean loops? They are discussed in
> http://www.ietf.org/internet-drafts/draft-byrne-ldap-alias-00.txt it states that
> 
>              During the dereferencing of aliases, a loop is detected if the
>              server visits the same alias entry more than once. In this
>              case a data integrity error has occurred and the server MUST
>              return an error of 'aliasProblem'

I know, but I think this is wrong. I've been going through X.511 and X.518
this morning and I can't find any prohibition against cycles. Given that
and Mark Wahl's response to the simple case of an alias that points to
itself, I don't believe that it is an error to have a cycle in your
DIT (DIG?). It becomes the responsibility of the search mechanism to remove
the cycles.

The algorithms above effectively remove any cycles in the graph, and since the
search routines don't return any duplicates, cycles are a non-issue and no
duplicate entries are returned.

> > > From Mark.Wahl@INNOSOFT.COM  Mon Oct 19 15:19:34 1998
> > >
> > > You should definitely look at X.501, X.511 and X.518 in addition to X.521.
> > > There is much more information on how aliases operate which we simply reference
> > > from LDAP.
> > >
> > > > Another question is how do you report an error? I'm assuming that the
> > > > case of an alias pointing to itself is an error. Is it an "alias
> > > > problem" or an "alias dereferencing problem?" Should it be an error to
> > > > create entries like this in the DIT in the first place?
> > >
> > > I don't think an alias to itself is an error, though it is not useful.
> > > The target object exists and is searchable.
> > >
> 
> Well, dereferencing an alias to itself seems to me a problem if loop detection is not
> in place and the error reported since aliases are supposed to dereference to the end
> point.  This means that if the dereferenced alias is itself the code is obliged to
> dereference that, ad infinitum.  The only time I can see this not being a problem is if
> the alias is either dereferenced once, there is a special case to itself (in whichcase
> you can still make loops), or you don't dereference.

My interpretation is that you dereference it and then return the alias itself
(if it matches the search criteria that is).

Interestingly enough, X.501 (93 anyway) specifically allows dangling aliases:

  9.5 ...Note--The name within the aliasedEntryName is said to be pointed
      to by the alias. It does not have to be the distinguished name of
      any entry.

bob

Robert Streich			streich@slb.com
Schlumberger			512-331-3318 (voice)
Austin Research			512-331-3760 (fax)