Fix Descriptions:
- The key format of entryrdn index has been modified to allow traversing
tombstoned node entries.
old key format:
[PC]entryID: <rdn> (nsuniqueid=<UNIQUEID>,<rdn>)
new key format:
[PC]entryID:
To traverse the DIT on entryrdn, rdn's are not needed. Just using
entryID should work. Also, the rdn strings are stored in the entryrdn
value. Thus, this key format change eliminates the redundancy.
The main motivation of the change: a tombstone entry has a DN format
"nsuniqueid=<UNIQUEID>,<original_dn>". If any of the ancestor entries
of the tombstone entry were trying to get the full DN using entryrdn,
there was no way to figure out the node's nsuniqueid from the leaf DN.
That is, once an entire subtree was deleted, the leaf entries lost the
ability to get the full DN using the entryrdn index. This fix makes
entryrdn to regain it.

• Once an entry has become a tombstone entry, ordinary operation such
  as search does not expect the entry is returned. But it is needed
  when reaping the tombstone entries. To support the 2 conflicting
  requirements, a flag TOMBSTONE_INCLUDED is added. Passing the flag
  to dn2entry_ext, it returns the tombstoned entry.

• Introduced a system attribute tombstoneNumSubordinates to hold the
  subordinate count of the tombstone'd node. Once a normal entry is
  turned to be a tombstone entry, it loses the numSubordinates attribute.
  The attribute value is used to determine the normal entry is a leaf
  or a node. The analogous knowledge is necessary to determine if the
  tomb stone entry can be reaped or not. TombstoneNumSubordinates has
  been introduced to fulfill the goal. As long as the tombstoneNum-
  subordinates value is not 0, the tombstone entry won't be reaped.
  The tombstoneNumsubordinates attribute value pair is added/modified
  when the child entries are deleted (note: child entries never be
  added since we don't allow to add a subordinate entry to a tombstone
  entry). Also, when an ldif file which contains tombstone entries
  is imported, the tombstoneNumSubordinates value is added to a tomb-
  stone node entry in the same way as the numSubordinates is to a normal
  node entry. To support the new behavior, parentid index is now main-
  tained for the tombstone entries, as well.

• Added an upgrade script: 91subtreereindex.pl to reformat entryrdn
  index file.

• To check the upgrade is needed or not, introduced BDB_RDNFORMAT_VERSION:
  The current version is 1.
  bdb/4.8/libback-ldbm/newidl/rdn-format-1/dn-4514

• Modified an upgrade script 81changelog.pl to check target files (__db.,
  log., guardina) exist or not.

Test scenario
Trac-Ticket2-test-scenario.txt

{{{
--- a/ldap/admin/src/scripts/81changelog.pl
+++ b/ldap/admin/src/scripts/81changelog.pl
@@ -21,9 +21,15 @@ sub runinst {
# Remove old db region files and transaction logs
- system("rm $changelogdir/__db.");
- system("rm $changelogdir/log.");
- system("rm $changelogdir/guardian");
+ if (-f "$changelogdir/__db.") {
+ system("rm $changelogdir/__db.");
+ }
+ if (-f "$changelogdir/log.") {
+ system("rm $changelogdir/log.");
+ }
+ if (-f "$changelogdir/guardian") {
+ system("rm $changelogdir/guardian");
+ }

This won't work - the if -f doesn't do wildcard globbing - so -f "$changelogdir/__db." will always fail (unless there is a single file with the name $changelogdir/__db.). If the problem is that the rm command spews out information you don't want to see, just use rm -f instead.

In process_reap_entry - if the entry does not have tombstonenumsubordinates, it will be reaped? And if the entry has tombstonenumsubordinates, and the value is less than 1, it will be reaped?
I think you could just use slapi_entry_attr_get_long() here (or ulong, or longlong etc. depending on what kind of integer this value represents) - this will return 0 if there is no such attribute (in which case the tombstone will be reaped), or it will return the value (which if less than 1 the tombstone will be reaped).

slapi_dn_find_parent() - this is problematic if someone wants to use nsuniqueid=value,...dnvalue... as a "real" DN and not a tombstone DN - seems like whoever is calling slapi_dn_find_parent() needs to somehow know if the DN is the DN of a "real" tombstone entry or not

diff --git a/ldap/servers/slapd/util.c b/ldap/servers/slapd/util.c
index fd5ebcb..9ee3fbe 100644
--- a/ldap/servers/slapd/util.c
+++ b/ldap/servers/slapd/util.c
@@ -349,7 +349,6 @@ int slapi_entry2mods (const Slapi_Entry e, char dn, LDAPMod attrs)
}

*attrs = slapi_mods_get_ldapmods_passout (&smods);

• slapi_mods_done (&smods);

  return 0;
  }

Even though in the current code, after calling slapi_mods_get_ldapmods_passout(), slapi_mods_done() just does a memset of the &smods to 0, unless doing the memset is a significant performance hit, I would rather leave the slapi_mods_done() in the code. In the future, we may change the implementation of slapi_mods which would require a slapi_mods_done(), which could cause a memory leak if we omit it in this case.

--- a/ldap/servers/slapd/back-ldbm/import.h
+++ b/ldap/servers/slapd/back-ldbm/import.h
@@ -66,6 +66,7 @@ static const int import_sleep_time = 200; / in millisecs /

extern char numsubordinates;
extern char hassubordinates;
+extern tombstone_numsubordinates;

should specify the data type here (char *? int? long?) rather than the compiler default.

in the new entryrdn index - do we still need the trailing ":" after the ID?
}}}

looks good

revised git patch file (master)
0001-Trac-Ticket-2-If-node-entries-are-tombstone-d.patch

Reviewed by Rich. (Thanks a lot!!)

Pushed to master.

$ git merge trac2
Updating 91fa21f..681b22b
Fast-forward
Makefile.am | 3 +-
Makefile.in | 10 +-
aclocal.m4 | 40 +-
config.h.in | 6 +
configure |18949 +++++++++-------------
ldap/admin/src/scripts/81changelog.pl | 6 +-
ldap/admin/src/scripts/setup-ds.res.in | 2 +
ldap/servers/plugins/replication/repl5_replica.c | 33 +-
ldap/servers/slapd/back-ldbm/back-ldbm.h | 14 +
ldap/servers/slapd/back-ldbm/dbversion.c | 3 +-
ldap/servers/slapd/back-ldbm/dn2entry.c | 26 +-
ldap/servers/slapd/back-ldbm/findentry.c | 46 +-
ldap/servers/slapd/back-ldbm/id2entry.c | 7 +-
ldap/servers/slapd/back-ldbm/import-threads.c | 9 +-
ldap/servers/slapd/back-ldbm/import.c | 3 +-
ldap/servers/slapd/back-ldbm/import.h | 1 +
ldap/servers/slapd/back-ldbm/index.c | 21 +-
ldap/servers/slapd/back-ldbm/ldbm_add.c | 5 +-
ldap/servers/slapd/back-ldbm/ldbm_config.h | 2 +-
ldap/servers/slapd/back-ldbm/ldbm_delete.c | 122 +-
ldap/servers/slapd/back-ldbm/ldbm_entryrdn.c | 353 +-
ldap/servers/slapd/back-ldbm/ldbm_modrdn.c | 8 +-
ldap/servers/slapd/back-ldbm/ldif2ldbm.c | 41 +-
ldap/servers/slapd/back-ldbm/misc.c | 1 +
ldap/servers/slapd/back-ldbm/parents.c | 141 +-
ldap/servers/slapd/back-ldbm/proto-back-ldbm.h | 4 +
ldap/servers/slapd/dn.c | 69 +-
ldap/servers/slapd/modutil.c | 6 +-
ldap/servers/slapd/slapi-plugin.h | 48 +
ldap/servers/slapd/tools/dbscan.c | 6 +-
lib/libaccess/lasip.cpp | 4 +-
ltmain.sh | 3968 +++--
32 files changed, 10861 insertions(+), 13096 deletions(-)

$ git push
Counting objects: 90, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (45/45), done.
Writing objects: 100% (46/46), 85.53 KiB, done.
Total 46 (delta 41), reused 1 (delta 0)
To ssh://git.fedorahosted.org/git/389/ds.git
91fa21f..681b22b master -> master

commit changeset:681b22b/389-ds-base

Looks like 91subtreereindex.pl is missing

Thanks for finding it out, Rich!

Added the file:
$ git merge work
Updating 0070a45..aa28a59
Fast-forward
ldap/admin/src/scripts/91subtreereindex.pl | 141 ++++++++++++++++++++++++++++
1 files changed, 141 insertions(+), 0 deletions(-)
create mode 100644 ldap/admin/src/scripts/91subtreereindex.pl

$ git push
Counting objects: 12, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (6/6), done.
Writing objects: 100% (7/7), 1.79 KiB, done.
Total 7 (delta 4), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/389/ds.git
0070a45..aa28a59 master -> master

commit changeset:aa28a59/389-ds-base

Added initial screened field value.

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/2

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.