Bug 472131 - dbverify: when a duplicate is large enough to have internal page(s), dbverify issues bogus out-of-order key errors
Summary: dbverify: when a duplicate is large enough to have internal page(s), dbverify...
Keywords:
Status: CLOSED CURRENTRELEASE
Alias: None
Product: 389
Classification: Retired
Component: Command Line Utilities
Version: 1.1.3
Hardware: All
OS: Linux
high
medium
Target Milestone: ---
Assignee: Noriko Hosoi
QA Contact: Viktor Ashirov
URL:
Whiteboard:
Depends On: 562941 562950 563607 563610 564448
Blocks: 389_1.2.7 639035
TreeView+ depends on / blocked
 
Reported: 2008-11-18 21:37 UTC by Noriko Hosoi
Modified: 2015-12-07 16:36 UTC (History)
3 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2015-12-07 16:36:39 UTC


Attachments (Terms of Use)
cvs diff btree/bt_verify.c (Berkeley DB 4.6.21) (1.60 KB, patch)
2008-11-18 21:41 UTC, Noriko Hosoi
no flags Details | Diff
diff ../../db-4.7.25/btree/bt_verify.c bt_verify.c (37.24 KB, patch)
2009-12-23 19:06 UTC, Noriko Hosoi
no flags Details | Diff
patch for btree/bt_verify.c (Berkeley DB 4.7.25) (6.51 KB, patch)
2010-01-14 01:22 UTC, Noriko Hosoi
no flags Details | Diff
patch for btree/bt_verify.c (Berkeley DB 4.3.29) (5.05 KB, patch)
2010-02-08 18:34 UTC, Noriko Hosoi
nhosoi: review?
rmeggins: review+
Details | Diff
patch for btree/bt_verify.c (Berkeley DB 4.7.25) (4.33 KB, patch)
2010-02-08 18:36 UTC, Noriko Hosoi
nhosoi: review?
rmeggins: review+
Details | Diff

Description Noriko Hosoi 2008-11-18 21:37:05 UTC
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.

Comment 1 Noriko Hosoi 2008-11-18 21:41:32 UTC
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
    [...]

Comment 2 Noriko Hosoi 2008-11-18 22:07:54 UTC
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

Comment 3 Noriko Hosoi 2009-01-16 20:08:15 UTC
Per bug council, reset the tracking bug to 8.2

Comment 4 Noriko Hosoi 2009-01-16 20:10:17 UTC
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)

Comment 5 Noriko Hosoi 2009-12-23 19:06:04 UTC
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.)

Comment 6 Noriko Hosoi 2010-01-14 01:22:45 UTC
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.

Comment 7 Noriko Hosoi 2010-02-08 18:34:03 UTC
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

Comment 8 Noriko Hosoi 2010-02-08 18:36:31 UTC
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

Comment 9 Noriko Hosoi 2010-02-08 19:02:16 UTC
(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

Comment 10 Noriko Hosoi 2010-02-08 19:06:29 UTC
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).

Comment 11 Noriko Hosoi 2010-06-09 16:00:30 UTC
The current status (06/09/2010):

563607   	medium  	high  	Linux  	 jnovy@redhat.com   	MODIFIED  	  	patch for btree/bt_verify.c (Berkeley DB 4.3.29)
589879 	medium 	high 	Linux 	jnovy@redhat.com 	ON_QA 		patch for btree/bt_verify.c (Berkeley DB 4.3.29)
589880 	medium 	high 	Linux 	jnovy@redhat.com 	ON_QA 		patch for btree/bt_verify.c (Berkeley DB 4.3.29)
563610 	medium 	low 	Linux 	jnovy@redhat.com 	ON_QA 		patch for btree/bt_verify.c (Berkeley DB 4.7.25)
232141 	medium 	medium 	Linux 	jnovy@redhat.com 	CLOSED 	ERRATA 	Need the btree/bt_rec.c patch for 4.2.52
564448 	medium 	low 	Linux 	jnovy@redhat.com 	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.

Comment 12 Noriko Hosoi 2010-09-30 21:22:27 UTC
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.

Comment 13 Amita Sharma 2011-05-18 11:57:01 UTC
Hi Noriko,

Request you to please guide with the VERIFICATION steps.

Thanks,
ami

Comment 14 Noriko Hosoi 2011-05-18 16:00:58 UTC
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.

Comment 15 Amita Sharma 2011-05-19 07:35:29 UTC
[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


Note You need to log in before you can comment on or make changes to this bug.