5:07 p.m.
There appears to be a long-standing problem with back-bdb and entries with
more than BDB_IDL_DB_MAX immediate children. If the entryIDs of the children
are non-contiguous, then attempts to delete the subtree of the entry will
fail, because the IDL range for the OneLevel index in the dn2id DB will never
zero out.
back-hdb doesn't have this problem.
Not sure what an appropriate fix is. Ideally, when deleting an entry whose ID
corresponds to either the lower or upper bound of the range, we should update
the range with the ID of the next remaining sibling. But there's no easy way
to search for that ID, so we just increment/decrement the range by 1. The
OneLevel index is the only structure that can quickly tell us what the
siblings are, and it's obviously useless when this situation arises.
The only way to search would be to [inc/dec]rement the ID and retrieve the
corresponding entry's DN to see if it is a sibling of the deleted entry, and
loop until a sibling is found or we run into the opposite range boundary. On a
large DB this will be extremely slow.
Seems like the best fix is to deprecate back-bdb and only use back-hdb from
now on.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
1:22 p.m.
Michael Ströder wrote:
Howard Chu wrote:
> Seems like the best fix is to deprecate back-bdb and only use back-hdb
> from now on.
But I vaguely remember that back-hdb has higher memory consumption.
Eh? back-hdb has a smaller memory footprint, as well as a smaller on-disk
footprint.
Maybe you're thinking of the original design in 2.1
http://www.openldap.org/lists/openldap-devel/200303/msg00055.html
which changed quite a bit since then.
Thinking about it some more, we can still salvage back-bdb, but it will
require a change in the dn2id index format. The only thing that bothers me
about this is that once you start down the path of making "sensible" changes
to back-bdb's dn2id format, you eventually arrive at back-hdb anyway, so
again, is it really worth the effort...
Anyway, the solution I'm thinking of is to reverse the RDN order in the dn2id
index keys. (I.e., use X.500 order.) This way we can use BDB range lookups to
find children/siblings of entries. That will give us a quick method of
validating the OneLevel index. (The next logical step is of course to
eliminate the OneLevel index because it's superfluous once you organize the
RDNs this way. But we can stop short of that, no point in repeating the
development of back-hdb yet again.)
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
1:33 p.m.
--On Tuesday, July 22, 2008 1:22 PM -0700 Howard Chu <hyc(a)symas.com> wrote:
Thinking about it some more, we can still salvage back-bdb, but it
will
require a change in the dn2id index format. The only thing that bothers
me about this is that once you start down the path of making "sensible"
changes to back-bdb's dn2id format, you eventually arrive at back-hdb
anyway, so again, is it really worth the effort...
Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at the
same time, and rework back-hdb to work with BDB 4.7's new locking stuff.
Honestly it seems like a bit of work to go to, to save a backend that's
already been obsoleted.
--Quanah
--
Quanah Gibson-Mount
Principal Software Engineer
Zimbra, Inc
--------------------
Zimbra :: the leader in open source messaging and collaboration
2:31 p.m.
Quanah Gibson-Mount wrote:
--On Tuesday, July 22, 2008 1:22 PM -0700 Howard
Chu<hyc(a)symas.com> wrote:
> Thinking about it some more, we can still salvage back-bdb, but it will
> require a change in the dn2id index format. The only thing that bothers
> me about this is that once you start down the path of making "sensible"
> changes to back-bdb's dn2id format, you eventually arrive at back-hdb
> anyway, so again, is it really worth the effort...
Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at the
same time, and rework back-hdb to work with BDB 4.7's new locking stuff.
Honestly it seems like a bit of work to go to, to save a backend that's
already been obsoleted.
Sounds about right to me. Of course, we knew that back-bdb's dn2id index was a
problem 'way back in the beginning...
http://www.openldap.org/lists/openldap-devel/200112/msg00118.html
and we knew that back-hdb didn't have these problems. And we've talked about
dropping back-bdb in favor of back-hdb several times through the years. It
seems now is the time.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
3:55 p.m.
<quote who="Howard Chu">
Quanah Gibson-Mount wrote:
> --On Tuesday, July 22, 2008 1:22 PM -0700 Howard Chu<hyc(a)symas.com>
> wrote:
>> Thinking about it some more, we can still salvage back-bdb, but it will
>> require a change in the dn2id index format. The only thing that bothers
>> me about this is that once you start down the path of making
"sensible"
>> changes to back-bdb's dn2id format, you eventually arrive at back-hdb
>> anyway, so again, is it really worth the effort...
>
> Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at
> the
> same time, and rework back-hdb to work with BDB 4.7's new locking stuff.
> Honestly it seems like a bit of work to go to, to save a backend that's
> already been obsoleted.
Sounds about right to me. Of course, we knew that back-bdb's dn2id index
was a
problem 'way back in the beginning...
http://www.openldap.org/lists/openldap-devel/200112/msg00118.html
and we knew that back-hdb didn't have these problems. And we've talked
about
dropping back-bdb in favor of back-hdb several times through the years. It
seems now is the time.
What's the overall impact to everything else code wise? "make test" will
take half the time now though.
--
Kind Regards,
Gavin Henry.
T +44 (0) 1224 279484
M +44 (0) 7930 323266
F +44 (0) 1224 824887
E ghenry(a)suretecsystems.com
Open Source. Open Solutions(tm).
http://www.suretecsystems.com/
Suretec Systems is a limited company registered in Scotland. Registered
number: SC258005. Registered office: 13 Whiteley Well Place, Inverurie,
Aberdeenshire, AB51 4FP.
4:41 p.m.
Gavin Henry wrote:
<quote who="Howard Chu">
> and we knew that back-hdb didn't have these problems. And we've talked
> about
> dropping back-bdb in favor of back-hdb several times through the years. It
> seems now is the time.
What's the overall impact to everything else code wise? "make test" will
take half the time now though.
Considering that back-hdb and back-bdb share 90% of their code, I don't see
any immediate impact from this decision. Even going thru and deleting/moving
the files in CVS is more trouble than it's worth. I guess we can disable it by
default in the configure script, and drop it from the default tests.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
5:05 a.m.
Howard Chu writes:
Considering that back-hdb and back-bdb share 90% of their code, I
don't see any immediate impact from this decision. Even going thru
and deleting/moving the files in CVS is more trouble than it's worth.
If so, the version (RE25?) which removes back-bdb can rename the "hdb"
backend to "bdb", maybe leaving "hdb" as an alias to be removed
later.
They are similar enough that this should not cause confusion. slapcat -
slapadd will be required to upgrade, but that's required anyway between
release branches.
What advantages do bdb still have over hdb today? Only that it's more
used and thus somewhat better tested?
--
Hallvard
5:12 a.m.
Howard Chu wrote:
And we've talked
about dropping back-bdb in favor of back-hdb several times through the
years. It seems now is the time.
If back-hdb has no disadvantages (like higher memory footprint) I'm for
deprecating back-bdb. back-hdb offers more features anyway.
Ciao, Michael.
5:22 a.m.
Howard Chu wrote:
Michael Ströder wrote:
> Howard Chu wrote:
>> Seems like the best fix is to deprecate back-bdb and only use back-hdb
>> from now on.
>
> But I vaguely remember that back-hdb has higher memory consumption.
Eh? back-hdb has a smaller memory footprint, as well as a smaller
on-disk footprint.
Glad to stand corrected regarding this. ;-)
Ciao, Michael.
12:24 a.m.
Howard Chu writes:
There appears to be a long-standing problem with back-bdb and
entries
with more than BDB_IDL_DB_MAX immediate children. If the entryIDs of
the children are non-contiguous, then attempts to delete the subtree
of the entry will fail, because the IDL range for the OneLevel index
in the dn2id DB will never zero out.
I'm not aware of a recursive delete LDAP control - do you mean "attempts
to delete the entry after having deleted the subtree"? If so:
Is the problem only to (make it feasible to) detect this situation, or
also to act on it? To detect it, I assume Delete before returning
notAllowedOnNonLeaf could search with scope onelevel/children, and see
if it finds any entires.
--
Hallvard
1:28 a.m.
Hallvard B Furuseth wrote:
Howard Chu writes:
> There appears to be a long-standing problem with back-bdb and entries
> with more than BDB_IDL_DB_MAX immediate children. If the entryIDs of
> the children are non-contiguous, then attempts to delete the subtree
> of the entry will fail, because the IDL range for the OneLevel index
> in the dn2id DB will never zero out.
I'm not aware of a recursive delete LDAP control - do you mean "attempts
to delete the entry after having deleted the subtree"? If so:
Pretty much. E.g. using ldapdelete -r, but it would apply to any situation
where an entry had many children, and eventually they were all deleted, and
then eventually someone attempts to delete the entry itself.
Is the problem only to (make it feasible to) detect this situation,
or
also to act on it? To detect it, I assume Delete before returning
notAllowedOnNonLeaf could search with scope onelevel/children, and see
if it finds any entires.
Yes... back-bdb would also need to check this for modrdn as well. Seems like
quite a lot of extra expense to perform this check each time.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
1:58 a.m.
Howard Chu writes:
Hallvard B Furuseth wrote:
> Is the problem only to (make it feasible to) detect this situation, or
> also to act on it? To detect it, I assume Delete before returning
> notAllowedOnNonLeaf could search with scope onelevel/children, and see
> if it finds any entires.
Yes... back-bdb would also need to check this for modrdn as well. Seems
like quite a lot of extra expense to perform this check each time.
Only at failure. Maybe it's more work than I imagine - it's an index
after all. But IIRC we already have similar slowdowns in situations I'd
assume are more common. When deleting multiple attribute values in an
entry have the same hash, or something.
--
Hallvard
3:05 a.m.
Hallvard B Furuseth wrote:
Howard Chu writes:
> Hallvard B Furuseth wrote:
>> Is the problem only to (make it feasible to) detect this situation, or
>> also to act on it? To detect it, I assume Delete before returning
>> notAllowedOnNonLeaf could search with scope onelevel/children, and see
>> if it finds any entires.
> Yes... back-bdb would also need to check this for modrdn as well. Seems
> like quite a lot of extra expense to perform this check each time.
Only at failure.
We need to do this check whenever deleting an entry whose parent's onelevel
index is an IDL range.
Maybe it's more work than I imagine - it's an index after
all.
Yes, it's an index. But there's no efficient way to determine this info
without the index. (Which again is why back-hdb doesn't do things this way...)
The checks we're considering here could also seriously impair concurrency,
since the Delete transaction could end up taking read locks on many entries
before finding the next sibling.
But IIRC we already have similar slowdowns in situations I'd
assume are more common. When deleting multiple attribute values in an
entry have the same hash, or something.
No, not a comparable situation. In that case, we compute all of the hashes in
memory but we cancel out the duplicates and only push the true changes into
the DB. Computing the hashes is cheap, DB operations are not.
Seems like it's time to revisit this thread...
http://www.openldap.org/lists/openldap-devel/200503/msg00012.html
The notion of bit-vectors for IDLs is looking good again. The whole reason
this problem exists is because range IDLs lose so much information.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
2:08 a.m.
Hallvard B Furuseth wrote:
Does this bug produce incorrect hasSubordinates: TRUE values too?
Yes.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
5609
days inactive
5610
days old
15 comments
5 participants
participants (5)
-
Gavin Henry -
Hallvard B Furuseth -
Howard Chu -
Michael Ströder -
Quanah Gibson-Mount