Pseudobacklinks in samba4

[Andrew Bartlett]

On Mon, 2011-05-23 at 11:56 +0400, Matthieu Patou wrote:
> On 23/05/2011 09:13, Andrew Bartlett wrote:
> > On Mon, 2011-05-23 at 00:05 +0400, Matthieu Patou wrote:
> >> Hello,
> >>
> >> I just pushed in my repo at
> >> http://git.samba.org/?p=mat/samba.git;a=shortlog;h=refs/heads/pseudobacklinks.
> >>
> >> Pseudo backlinks are a way to do fake linked attributes on attribute
> >> with a DN like syntax but that are not linked attribute.
> >>
> >> The main interest of this is that if the DN pointed by this attribute
> >> change then thanks to the pseudobacklink we will be able to change the
> >> value in the attribute as well.
> >>
> >> This can be very useful when removing a DC or when changing the site of
> >> a DC and surely in other case that we don't envision yet.
> >>
> >> I tried to be very cautious on this patches (as usual) but a small
> >> review wouldn't hurt I think !
> > s4-dsdb: do not allow search on @ attributes and don't return them
> > http://git.samba.org/?p=mat/samba.git;a=commitdiff;h=23bf142dfde77429180f6cbd193b6faa2cbb05ec
> >
> > This is O(n^3) and not safe, as far as I can see it.
> As far as I can understand ldb_attr_list_copy is O(n) as we are 
> potentially calling it n times it should be O(n^2) no ?

I was referring to the removal, but yes the loop around
ldb_attr_list_copy() should be O(n^2). 

> >
> > If you used ldb_msg_remove_element() you could make it only O(n^2) and
> > potentially safe (knowing to repeat the index each time you remove it,
> > due to the internal memmove()).
> It seems to me that ldb_msg_remove_element is O(n^2) and as it could be 
> called n times it should be O(n^3) right ?
> 
> Of course this penalties will happen only if you try to search on 
> pseudobacklink which is not a use case at all.

How do you avoid the caller seeing the @ elements in the normal case?
(I'm worried that the removal is in the normal codepath - I can't see
how it is selective)

> Then can you point what you think is not safe ?

Because msg->num_elements shrinks each time you remove an element, you
have to account for that.  If you use ldb_msg_remove_element() at least
you know you are removing exactly one element, so can 'go back' one
index.

> >
> > We do need to move to a 'mark as deleted' scheme here, as this is one of
> > our nastiest little traps in the ldb API, but for now you have to work
> > around it.
> Right as I'm pretty sure we iterate more than once on attributes to 
> remove or add some, we should also move away from doing string 
> comparisons as it's very costly.
> > s4-dsdb: Add a warning about dsdb_module_rename that locks if olddn ==
> > newdn
> > http://git.samba.org/?p=mat/samba.git;a=commitdiff;h=933d74e64e9836e8597bcfa531d5347bec726182
> >
> > Is this bug new, or exposed by your tests, or?  We should not use FIXME
> > as a bug tracking system, but actually fix the code if at all possible,
> > otherwise error out early.
> We hit this metze, while working on the rootdse, we managed to avoid it, 
> but we agreed that we should mark it as, fix needed.
> 
> >
> > s4-dsdb: In rootdse module, catch rename on any DN that has an impact on
> > our NTDS Setting dn
> > http://git.samba.org/?p=mat/samba.git;a=commitdiff;h=e78335ce0184b5fdd6f313a6b95b00f242fab83f
> >
> > We should more dynamically determine this, I think, perhaps based on a
> > stored GUID (which should not change).  We have gradually moved from
> > having static strings in @ROOTDSE to dynamic lookup, and this is just
> > another step in that direction.
> So at first here I was keen on making it dynamic, but it didn't work, an 
> early search like '(guid=<myguid>)' didn't work. I show this to metze 
> and it turns out that it's because at the early moment the indexing 
> system is not the same as "as usual". So basically doing a search with a 
> guid at the very beginning don't work.

We need to fix that then, or find a way around it, I don't want us
changing the @ROOTDSE record.

Andrew Bartlett

-- 
Andrew Bartlett                                http://samba.org/~abartlet/
Authentication Developer, Samba Team           http://samba.org