dsdb linked attributes: fix forward links faster
authorDouglas Bagnall <douglas.bagnall@catalyst.net.nz>
Wed, 9 Jan 2019 04:57:15 +0000 (17:57 +1300)
committerAndrew Bartlett <abartlet@samba.org>
Mon, 4 Mar 2019 21:41:18 +0000 (21:41 +0000)
commit8765ed2f1dd5b291f449a46a9e99b6ae810d3947
treeb8cd22c81a1536d86155c4c32494fb71b787a410
parent518320ae33ae6d77d67ec216cd4cd68d69036be1
dsdb linked attributes: fix forward links faster

Rename operations can be very slow in large database with many group
memberships, because the linked attributes need to be found and
rewritten for each moved object and the way we did that was naive.

For a while now Samba has kept forward links in sorted order, so
finding group memberships can be an O(log n) rather than O(n)
operation. This patch makes use of that.

The backlinks are not sorted, nor are forward links in old databases,
so we have to use a linear search in those cases.

There is a little bit of extra work to handle the few kinds of forward
links (e.g. msDS-RevealedUsers) that have DN+Binary values.

Tim and Garming came up with the basic idea and a prototype.

Pair-programmed-with: Tim Beale <timbeale@catalyst.net.nz>
Pair-programmed-with: Garming Sam <garming@catalyst.net.nz>
Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
source4/dsdb/samdb/ldb_modules/linked_attributes.c