Description of problem: It's not a Directory Server's problem, but a Berkeley DB API's issue (dbp->verify) The Directory Server uses the "duplicate (nested btree)" to store the IDs (ID list). To sort them in the duplicate, we set a comparison function idl_new_compare_dups to dbp->set_dup_compare. To make dbp->verify use the comparison function, we wrote our own dbverify (slapd/back-ldbm/dbverify.c). If the ID list is not very long -- the duplicate storing the IDs can be put in one page, BDB verify reports the correct result. Once the duplicate splits and has an internal page, it reports errors like these: db_verify: Page 7: out-of-order key at entry 6 db_verify: Page 7: out-of-order key at entry 11 db_verify: Page 7: out-of-order key at entry 17 db_verify: Page 7: out-of-order key at entry 22 [...] The cause of this problem is Berkeley DB does not distinguish the internal pages (nodes) of the duplicate from the ones of the main btree. Both has the type P_IBTREE. In the verify process, __bam_vrfy_itemorder (btree/bt_verify.c) sets the default comparison function __bam_defcmp for the both internal pages even though the user defined comparison function should have been set for the duplicate internal page.
Created attachment 323966 [details] cvs diff btree/bt_verify.c (Berkeley DB 4.6.21) Description: The attached patch checks the leaf type and if it is an ordinary btree (P_LBTREE), it uses the bt_compare or the default comparison function __bam_defcmp. If it is a duplicate (P_LDUP), it uses the user defined comparison function, if any. Note: this operation makes the verify slower since the check needs to be done for every internal page. But it reports the right result. # ./dbverify -V DB verify - /var/lib/dirsrv/slapd-ID/db/userRoot/uid.db4: ok DB verify - /var/lib/dirsrv/slapd-ID/db/userRoot/cn.db4: ok [...]
Posted to the Oracle/Berkeley DB forum: http://forums.oracle.com/forums/thread.jspa?threadID=828256&stqc=true verify reports bogus out-of-order key messages
Per bug council, reset the tracking bug to 8.2
corresponding doc bug for 8.1: Bug 474952 - Relnotes: dbverify: when a duplicate is large enough to have internal page(s), dbverify issues bogus out-of-order key errors (472131)
Created attachment 380082 [details] diff ../../db-4.7.25/btree/bt_verify.c bt_verify.c Verified the bug was fixed in Berkeley DB 4.8.26. Diff of btree/bt_verify.c between 4.7.25 and 4.8.26 is attached. (Note: It includes not-needed changes such as HAVE_COMPRESSION.)
Created attachment 383587 [details] patch for btree/bt_verify.c (Berkeley DB 4.7.25) Description: back ported the db_verify fix from Berkeley DB 4.8.26.
Created attachment 389588 [details] patch for btree/bt_verify.c (Berkeley DB 4.3.29) $ cat /etc/redhat-release Red Hat Enterprise Linux Server release 5.4 (Tikanga) $ rpm -q db4 db4-4.3.29-10.el5
Created attachment 389590 [details] patch for btree/bt_verify.c (Berkeley DB 4.7.25) $ cat /etc/redhat-release Fedora release 11 (Leonidas) $ rpm -q db4 db4-4.7.25-11.fc11.x86_64 $ cat /etc/redhat-release Fedora release 12 (Constantine) # rpm -q db4 db4-4.7.25-13.fc12.i686
(In reply to comment #8) > Created an attachment (id=389590) [details] > patch for btree/bt_verify.c (Berkeley DB 4.7.25) > > $ cat /etc/redhat-release > Fedora release 11 (Leonidas) > $ rpm -q db4 > db4-4.7.25-11.fc11.x86_64 > > $ cat /etc/redhat-release > Fedora release 12 (Constantine) > # rpm -q db4 > db4-4.7.25-13.fc12.i686 RHEL6 also includes db4-4.7.25... Package detail Package Name: db4 Product Version: RHEL-6.0 Maintainer: jnovy QE owner: BaseOS QE - Daemons SRPMs and reviews db4-4.7.25-13.1.el6 Latest review db4-4.7.25-13.el6 Latest review
Thanks to Rich for reviewing the back ported patches. I'm going to file 4 bugs (for component db4 on RHEL5, 6 and Fedora-11 and 12).
The current status (06/09/2010): 563607 medium high Linux jnovy MODIFIED patch for btree/bt_verify.c (Berkeley DB 4.3.29) 589879 medium high Linux jnovy ON_QA patch for btree/bt_verify.c (Berkeley DB 4.3.29) 589880 medium high Linux jnovy ON_QA patch for btree/bt_verify.c (Berkeley DB 4.3.29) 563610 medium low Linux jnovy ON_QA patch for btree/bt_verify.c (Berkeley DB 4.7.25) 232141 medium medium Linux jnovy CLOSED ERRATA Need the btree/bt_rec.c patch for 4.2.52 564448 medium low Linux jnovy CLOSED WONTFIX patch for btree/bt_verify.c (Berkeley DB 4.2.52) Fedora-13: The system db4 version is 4.8.30, which includes the fix for bt_verify.c: $ rpm -q db4 db4-4.8.30-1.fc13.x86_64 I verified dbverify/verify-db.pl works on Fedora-13.
Changing the status to MODIFIED since ... 1) RHEL5.5 and 6.0 have db4 including the patch we provided. RHEL5.5: db4-4.3.29-10.el5_5.2 RHEL6.0: db4-4.7.25-15.el6 2) Fedora-13 and newer has db4-4.8.30-# (# >= 1) on which this bug had been fixed.
Hi Noriko, Request you to please guide with the VERIFICATION steps. Thanks, ami
Steps: dbgen.pl -s <suffix> -o <ldiffile> -n 100000 cd /usr/lib[64]/dirsrv/slapd-ID ./ldif2db -n <backend> -i <ldiffile> ./dbverify If you don't see an error "db_verify: Page #: out-of-order key at entry #", the bug is verified.
[root@testvm bin]# dbgen.pl -s dc=example,dc=com -o /home/abc.ldif -n 100000 Generating 100000 entries, please wait Progress: .................................................................................................... Generated 100000 entries [root@testvm slapd-testvm]# service dirsrv stop Shutting down dirsrv: testvm... [ OK ] [root@testvm slapd-testvm]# ./ldif2db -n userRoot -i /home/abc.ldif importing data ... [19/May/2011:13:00:40 +051800] - WARNING: Import is running with nsslapd-db-private-import-mem on; No other process is allowed to access the database [19/May/2011:13:00:40 +051800] - check_and_set_import_cache: pagesize: 4096, pages: 249236, procpages: 49966 [19/May/2011:13:00:40 +051800] - WARNING: After allocating import cache 398776KB, the available memory is 598168KB, which is less than the soft limit 1048576KB. You may want to decrease the import cache size and rerun import. [19/May/2011:13:00:40 +051800] - Import allocates 398776KB import cache. [19/May/2011:13:00:40 +051800] - import userRoot: Beginning import job... [19/May/2011:13:00:40 +051800] - import userRoot: Index buffering enabled with bucket size 100 [19/May/2011:13:00:40 +051800] - import userRoot: Processing file "/home/abc.ldif" [19/May/2011:13:01:00 +051800] - import userRoot: Processed 27462 entries -- average rate 1373.1/sec, recent rate 1373.0/sec, hit ratio 0% [19/May/2011:13:01:20 +051800] - import userRoot: Processed 53434 entries -- average rate 1335.8/sec, recent rate 1335.8/sec, hit ratio 100% [19/May/2011:13:01:40 +051800] - import userRoot: Processed 80430 entries -- average rate 1340.5/sec, recent rate 1324.2/sec, hit ratio 100% [19/May/2011:13:01:55 +051800] - import userRoot: Finished scanning file "/home/abc.ldif" (100006 entries) [19/May/2011:13:01:55 +051800] - import userRoot: Workers finished; cleaning up... [19/May/2011:13:01:55 +051800] - import userRoot: Workers cleaned up. [19/May/2011:13:01:55 +051800] - import userRoot: Cleaning up producer thread... [19/May/2011:13:01:55 +051800] - import userRoot: Indexing complete. Post-processing... [19/May/2011:13:01:56 +051800] - import userRoot: Flushing caches... [19/May/2011:13:01:56 +051800] - import userRoot: Closing files... [19/May/2011:13:02:03 +051800] - All database threads now stopped [19/May/2011:13:02:03 +051800] - import userRoot: Import complete. Processed 100006 entries in 83 seconds. (1204.89 entries/sec) [root@testvm slapd-testvm]# ./dbverify DB verify: Passed