Pseudobacklinks in samba4

[Matthieu Patou]

On 23/05/2011 12:35, Andrew Bartlett wrote:
> 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).
But isn't the removal just a loop around ldb_attr_list_copy ?
>
>>> 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)
it's  this:
+       for (a=msg->num_elements - 1; a != (unsigned int)-1; a--) {
+               const char *name = msg->elements[a].name;
+
+               if (name && name[0] == '@') {
+                       struct ldb_message_element *el = &msg->elements[a];
+                       ldb_msg_remove_element(msg, el);
+               }
+       }
+

Of course it could be better to mark as removed first, then purge it.
But this is O(n^2) (yeah I changed a bit the code this morning).
>>
>>> 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.
Why not ?
>
> Andrew Bartlett
>


-- 
Matthieu Patou
Samba Team        http://samba.org
Private repo      http://git.samba.org/?p=mat/samba.git;a=summary