Bug 506786 - Index maintenance mechanism causes wrong search results when modifying attributes with subtypes [NEEDINFO]
Summary: Index maintenance mechanism causes wrong search results when modifying attrib...
Keywords:
Status: CLOSED CURRENTRELEASE
Alias: None
Product: 389
Classification: Retired
Component: Database - Indexes/Searches
Version: 1.2.1
Hardware: x86_64
OS: Linux
high
high
Target Milestone: ---
Assignee: Noriko Hosoi
QA Contact: Viktor Ashirov
URL:
Whiteboard:
Depends On:
Blocks: 434914 389_1.2.1
TreeView+ depends on / blocked
 
Reported: 2009-06-18 16:42 UTC by Andrey Ivanov
Modified: 2015-12-07 17:15 UTC (History)
3 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2015-12-07 17:15:11 UTC
andrey.ivanov: needinfo? (andrey.ivanov)


Attachments (Terms of Use)
Initial database contents (2.02 KB, application/octet-stream)
2009-06-18 16:43 UTC, Andrey Ivanov
no flags Details
LDIF that adds the "cn;fr" attribute (105 bytes, application/octet-stream)
2009-06-18 16:44 UTC, Andrey Ivanov
no flags Details
LDIF that deletes the "cn;fr" attribute (108 bytes, application/octet-stream)
2009-06-18 16:44 UTC, Andrey Ivanov
no flags Details
git patch file (index.c) (1.57 KB, patch)
2009-08-07 18:51 UTC, Noriko Hosoi
no flags Details | Diff
git patch file (index.c) (4.27 KB, patch)
2009-08-11 00:50 UTC, Noriko Hosoi
no flags Details | Diff
git patch file (index.c) (1.50 KB, patch)
2009-08-12 00:45 UTC, Noriko Hosoi
no flags Details | Diff

Description Andrey Ivanov 2009-06-18 16:42:37 UTC
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.11) Gecko/2009060215 Firefox/3.0.11 (.NET CLR 3.5.30729)

When adding a value to an attribute with subtype indexed on equality and then deleting this attribute subtype the index is not maintained correctly which results in wrong search results afterwards. After stopping the server and reindexing with db2index everything works correctly again. The unindexed and substring searches do not seem to be concerned.

Reproducible: Always

Steps to Reproduce:
1. Import the example.ldif attached  (there is only one entry):
service dirsrv stop
/usr/lib64/dirsrv/slapd-ldap-model/ldif2db -n userRoot -i /root/example.ldif 
service dirsrv start

2. Verify that the search of the entry filtered by cn is OK  (the attribute cn is by default indexed be equality) :
[root@ldap-model ~]# ldapsearch -x -D "cn=Directory Manager" -w 'password' -b "dc=example,dc=com" cn="Teena Vradmin" cn
# extended LDIF
#
# LDAPv3
# base <dc=example,dc=com> with scope subtree
# filter: cn=Teena Vradmin
# requesting: cn 
#

# TVradmin0, Accounting, example.com
dn: uid=TVradmin0, ou=Accounting, dc=example,dc=com
cn: Teena Vradmin

# search result
search: 2
result: 0 Success

# numResponses: 2
# numEntries: 1

3. Add the attribute "cn;fr" (cn with the subtype "fr") with the same value that is present in "cn" :
[root@ldap-model ~]# ldapmodify -x -D "cn=Directory Manager" -w 'manager!' -f add.ldif 
modifying entry "uid=TVradmin0, ou=Accounting, dc=example,dc=com"

The contents of add.ldif:
---------------------------------
dn: uid=TVradmin0, ou=Accounting, dc=example,dc=com
changetype: modify
add: cn;fr
cn;fr: Teena Vradmin
-
---------------------------------

4. Delete the attribute "cn;fr":
root@ldap-model ~]# ldapmodify -x -D "cn=Directory Manager" -w 'password' -f delete.ldif
modifying entry "uid=TVradmin0, ou=Accounting, dc=example,dc=com"

The contents of the file "delete.ldif"
---------------------------------
dn: uid=TVradmin0, ou=Accounting, dc=example,dc=com
changetype: modify
delete: cn;fr
cn;fr: Teena Vradmin
-
---------------------------------

5. The index is maintained in such a way that now LDAP thinks that the attribute "cn" is no more present (because of the same initial values of "cn" and "cn;fr") :

root@ldap-model ~]# ldapsearch -x -D "cn=Directory Manager" -w 'manager!' -b "dc=example,dc=com" cn="Teena Vradmin"
# extended LDIF
#
# LDAPv3
# base <dc=example,dc=com> with scope subtree
# filter: cn=Teena Vradmin
# requesting: ALL
#

# search result
search: 2
result: 0 Success

# numResponses: 1

6. If i stop the server and reindex the database the same search works correctly, so it is definitely  a problem in index maintenance engine:
[root@ldap-model ~]# ldapsearch -x -D "cn=Directory Manager" -w 'password' -b "dc=example,dc=com" cn="Teena Vradmin" cn
# extended LDIF
#
# LDAPv3
# base <dc=example,dc=com> with scope subtree
# filter: cn=Teena Vradmin
# requesting: cn 
#

# TVradmin0, Accounting, example.com
dn: uid=TVradmin0, ou=Accounting, dc=example,dc=com
cn: Teena Vradmin

# search result
search: 2
result: 0 Success

# numResponses: 2
# numEntries: 1

Actual Results:  
The server does not do the search correctly because of the index maintenance problems.

Expected Results:  
The server should return the correct search result.

The workaround is to add "*" to the filter to make it a substring filter (cn="Teena Vradmin*") or to delete the indexing on equality. But it's a significant performance loss.

Comment 1 Andrey Ivanov 2009-06-18 16:43:39 UTC
Created attachment 348521 [details]
Initial database contents

Comment 2 Andrey Ivanov 2009-06-18 16:44:15 UTC
Created attachment 348522 [details]
LDIF that adds the "cn;fr" attribute

Comment 3 Andrey Ivanov 2009-06-18 16:44:42 UTC
Created attachment 348524 [details]
LDIF that deletes the "cn;fr" attribute

Comment 4 Andrey Ivanov 2009-07-18 14:06:54 UTC
I've just encountered the problem in Outlook address book name search. So the same bug holds for VLV indexes, too. And the same workaround is valid - reindexing (db2index.pl -v -D "cn=Directory Manager" -w - -n userRoot).

Comment 5 Noriko Hosoi 2009-08-07 18:51:14 UTC
Created attachment 356696 [details]
git patch file (index.c)

Thanks to Nathan for his idea to fix this problem.  I verified your suggestion worked on the case that Andrey reported.  I also tested with the VLV index as follows:
dn: cn=Accounting cn, cn=userRoot, cn=ldbm database, cn=plugins, cn=config
objectClass: top
objectClass: vlvSearch
cn: Accounting cn
vlvBase: ou=Accounting, dc=example,dc=com
vlvScope: 1
vlvFilter: (|(cn=*)(objectclass=ldapsubentry))
numSubordinates: 1

dn: cn=Accounting cn vlv,cn=Accounting cn, cn=userRoot, cn=ldbm database, cn=p
 lugins, cn=config
objectClass: top
objectClass: vlvIndex
cn: Accounting cn vlv
vlvSort: cn

I could retrieve the entry with the following command line after removing "cn;fr" Teena Vradmin":
/usr/lib64/mozldap/ldapsearch -b "ou=accounting,dc=example,dc=com" -s onelevel -G 0:0:3:4 -S "cn" -x "(|(cn=*)(objectclass=ldapsubentry))" cn
version: 1
dn: uid=TVradmin0, ou=Accounting, dc=example,dc=com
cn: Teena Vradmin

[Fix Description]
When checking the same value exists in the entry, instead of using the
type to be modified, pass the basetype.  It covers the both cases removing
the attribute with subtype as well as with no subtype (basetype).

Comment 6 Andrey Ivanov 2009-08-07 19:26:58 UTC
That's exactly the place in the code where I have pinpointed the problem but i was not sure how to change the code and fix it, so i think it's a good fix. 

As for the VLV index, does the VLV code use the same index.c file? There is really nothing special about vlv*.c source files in the same directory? My Outlook index that went wrong is like this (by default, anonymous users can't use VLV Request Control, so the acis are here to authorize it) :

dn: oid=2.16.840.1.113730.3.4.9,cn=features,cn=config
changetype: modify
replace: aci
aci: (targetattr != "aci")(version 3.0; acl "VLV Request Control"; allow(read,search,compare) userdn = "ldap:///anyone";)

dn: cn=Outlook Browse,cn=userRoot,cn=ldbm database,cn=plugins,cn=config
changetype: add
cn: Outlook Browse
objectClass: top
objectClass: vlvsearch
aci: (targetattr != "aci")(version 3.0; acl "VLV Request Control"; allow(read,search,compare) userdn = "ldap:///anyone";)
vlvBase: ou=Users,dc=example,dc=com
vlvFilter: (&(mail=*)(cn=*))
vlvScope: 2

dn: cn=Outlook Browse Index,cn=Outlook Browse,cn=userRoot,cn=ldbm database,cn=plugins,cn=config
changetype: add
cn: Outlook Browse Index
objectClass: top
objectClass: vlvindex
aci: (targetattr != "aci")(version 3.0; acl "VLV Request Control"; allow(read,search,compare) userdn = "ldap:///anyone";)
vlvEnabled: 1
vlvSort: cn
vlvUses: 0

Comment 7 Noriko Hosoi 2009-08-07 22:15:54 UTC
Hold on...  I found the proposed fix had a problem removing "cn=Teena Vradmin" instead of "cn;fr=Teena Vradmin"... :(  I back off the proposal..

Comment 8 Noriko Hosoi 2009-08-11 00:50:58 UTC
Created attachment 356965 [details]
git patch file (index.c)

Found a problem in the previous proposed fix.  Revised...

Comment 9 Noriko Hosoi 2009-08-11 05:10:00 UTC
Thanks to Nathan for reviewing the change!

Pushed to master.

$ git merge work
Updating a26ba73..abff3fe
Fast forward
 ldap/servers/slapd/back-ldbm/index.c |   42 ++++++++++++++++++---------------
 1 files changed, 23 insertions(+), 19 deletions(-)
$ git push
Counting objects: 13, done.
Delta compression using 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 1.46 KiB, done.
Total 7 (delta 5), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/389/ds.git
   a26ba73..abff3fe  master -> master

Comment 10 Noriko Hosoi 2009-08-11 05:11:53 UTC
(In reply to comment #6) 
> As for the VLV index, does the VLV code use the same index.c file? There is
> really nothing special about vlv*.c source files in the same directory? My
> Outlook index that went wrong is like this (by default, anonymous users can't
> use VLV Request Control, so the acis are here to authorize it) :

Hi Andrey,

You are right.  VLV does not use the index code.  So, I might have just missed your issue.  Let me look into it some more...

--noriko

Comment 11 Andrey Ivanov 2009-08-11 08:20:47 UTC
I think the VLV  problem may have the same origin, so your patch will fix it. Since my VLV filter is (&(mail=*)(cn=*)) it actually uses the presence index (i think) to make the searches. The problem with vlv was like this : all the entries were present in the presented by Outlook list but when i made the search with the name (or part of the name) it returned the part of the list with the wrong name in the beginning. Maybe the sort code uses the presence indexes also, it could be an explanation. Anyway, right now i cannot reproduce the VLV problem to give you more details. So if it reappears i will open another bug or re-open this one... 

Here are the typical logs while doing the VLV searches by Outlook (and the operation that was causing the problems was like the "op=61") :

[11/Aug/2009:10:10:45 +0200] conn=3386 op=61 SRCH base="ou=Utilisateurs,dc=id,dc=polytechnique,dc=edu" scope=2 filter="(&(mail=*)(cn=*))" attrs="cn cn mail roleOccupant display-name displayName sn sn 
co o o givenName legacyexchangedn objectClass uid mailnickname title company physicalDeliveryOfficeName telephoneNumber"
[11/Aug/2009:10:10:45 +0200] conn=3386 op=61 SORT cn 
[11/Aug/2009:10:10:45 +0200] conn=3386 op=61 VLV 0:0:tir 6721:7263 (0)
[11/Aug/2009:10:10:45 +0200] conn=3386 op=61 RESULT err=0 tag=101 nentries=1 etime=0.986000
[11/Aug/2009:10:10:45 +0200] conn=3386 op=62 SRCH base="ou=Utilisateurs,dc=id,dc=polytechnique,dc=edu" scope=2 filter="(&(mail=*)(cn=*))" attrs="cn cn mail roleOccupant display-name displayName sn sn 
co o o givenName legacyexchangedn objectClass uid mailnickname title company physicalDeliveryOfficeName telephoneNumber"
[11/Aug/2009:10:10:45 +0200] conn=3386 op=62 SORT cn 
[11/Aug/2009:10:10:45 +0200] conn=3386 op=62 VLV 0:28:6720:7263 6721:7263 (0)
[11/Aug/2009:10:10:45 +0200] conn=3386 op=62 RESULT err=0 tag=101 nentries=29 etime=0.005000

Comment 12 Andrey Ivanov 2009-08-11 11:28:25 UTC
Hi, Noriko

Concerning your (second) patch. Is there a reason why you don't add a "break" into the "for" loop over mods_valueArray[j]? You could just stop parsing this array as soon as you have "found=1" :

...
for (j = 0; mods_valueArray[j] != NULL; j++ ) {
    if ( valuearray_find(curr_attr, evals, mods_valueArray[j]) > -1 ) {
        found = 1;
+       break;
    }
}
...

Comment 13 Noriko Hosoi 2009-08-11 14:48:12 UTC
(In reply to comment #12)
> Hi, Noriko
> 
> Concerning your (second) patch. Is there a reason why you don't add a "break"
> into the "for" loop over mods_valueArray[j]? You could just stop parsing this
> array as soon as you have "found=1" :
> 
> ...
> for (j = 0; mods_valueArray[j] != NULL; j++ ) {
>     if ( valuearray_find(curr_attr, evals, mods_valueArray[j]) > -1 ) {
>         found = 1;
> +       break;
>     }
> }
> ...  

Hi Andrey,

Oops.  I thought I should do it.  What I want to do is curr_attr is not in evals, set "flags |= BE_INDEX_EQUALITY".  I was somehow thinking I should check through all the values in evals, but it's not needed.  As soon as one is found, we can stop checking. :p  You are right.  I'm going to fix it.  Thanks for your review and comments!

Comment 14 Noriko Hosoi 2009-08-12 00:45:17 UTC
Created attachment 357101 [details]
git patch file (index.c)

Thanks to Andrey for his reviews.  The attached patch contains the fix as Andrey suggested.

Comment 15 Noriko Hosoi 2009-08-12 15:39:54 UTC
Thanks to Nathan and Rich for the reviews.

Pushed to master.

$ git merge work
Updating 65fef7e..20d6a63
Fast forward
 ldap/servers/slapd/back-ldbm/index.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)
$ git push
Counting objects: 13, done.
Delta compression using 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 946 bytes, done.
Total 7 (delta 5), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/389/ds.git
   65fef7e..20d6a63  master -> master

Comment 16 Noriko Hosoi 2009-08-12 15:41:46 UTC
(In reply to comment #11)
> I think the VLV  problem may have the same origin, so your patch will fix it.
> Since my VLV filter is (&(mail=*)(cn=*)) it actually uses the presence index (i
> think) to make the searches. The problem with vlv was like this : all the
> entries were present in the presented by Outlook list but when i made the
> search with the name (or part of the name) it returned the part of the list
> with the wrong name in the beginning. Maybe the sort code uses the presence
> indexes also, it could be an explanation. Anyway, right now i cannot reproduce
> the VLV problem to give you more details. So if it reappears i will open
> another bug or re-open this one... 

Thanks, Andrey!  For now, I'm changing the status of this bug to MODIFIED.  Please open a bug when you run into the VLV problem again...

Comment 17 Jenny Severance 2010-05-14 19:12:37 UTC
verified - RHEL 4

version:
redhat-ds-base-8.2.0-2010051204.el4dsrv

search after adding cn;fr:

# TVradmin0, Accounting, example.com
dn: uid=TVradmin0,ou=Accounting,dc=example,dc=com
objectClass: top
objectClass: person
objectClass: organizationalPerson
objectClass: inetOrgPerson
cn: Teena Vradmin
sn: Vradmin
uid: TVradmin0
givenName: Teena
description: 2;649;CN=Red Hat CS 71GA Demo,O=Red Hat CS 71GA Demo,C=US;CN=RHCS
  Agent - admin01,UID=admin01,O=redhat,C=US [1] This is Teena Vradmin's descri
 ption.
departmentNumber: 2220
employeeType: Manager
homePhone: +1 510 551-9687
initials: T. V.
telephoneNumber: +1 303 703-2147
facsimileTelephoneNumber: +1 206 682-3534
mobile: +1 213 151-5816
pager: +1 804 769-1685
manager: cn=Olga Lake
secretary: cn=Silva Giamatteo
roomNumber: 7730
carLicense: ZSN6DM3
l: Milpitas
ou: Accounting
mail: Teena_Vradmin@example.com
postalAddress: 796,  Dept #58, Room#Accounting
title: Senior Accounting Visionary
userCertificate;binary:: MIIBvjCCASegAwIBAgIBAjANBgkqhkiG9w0BAQQFADAnMQ8wDQYDV
 QQDEwZjb25maWcxFDASBgNVBAMTC01NUiBDQSBDZXJ0MB4XDTAxMDQwNTE1NTEwNloXDTExMDcwNT
 E1NTEwNlowIzELMAkGA1UEChMCZnIxFDASBgNVBAMTC01NUiBTMSBDZXJ0MIGfMA0GCSqGSIb3DQE
 BAQUAA4GNADCBiQKBgQDNlmsKEaPD+o3mAUwmW4E40MPs7aiui1YhorST3KzVngMqe5PbObUHMeJN
 7CLbq9SjXvdB3y2AoVl/s5UkgGz8krmJ8ELfUCU95AQls321RwBdLRjioiQ3MGJiFjxwYRIVj1CUT
 uX1y8dC7BWvZ1/EB0yv0QDtp2oVMUeoK9/9sQIDAQABMA0GCSqGSIb3DQEBBAUAA4GBADevhxY6Qy
 DMK3Mnr7vLGe/HWEZCObF+qEo2zWScGH0Q+dAmhkCCkNeHJoqGN4NWjTdnBcGaAr5Y85k1o/vOAMB
 sZePbYx4SrywL0b/OkOmQX+mQwieC2IQzvaBRyaNMh309vrF4w5kExReKfjR/gXpHiWQzGSxC5LeQ
 G4k3IP34
userPassword:: e1NTSEF9anp3SzMrUktTZFNNSWpjVWFvQlN1L0NzaWU4Ly8rbUJzRWFFMFE9PQ=
 =
cn;fr: Teena Vradmin

# search result
search: 2
result: 0 Success

search after deleting cn;fr:

# TVradmin0, Accounting, example.com
dn: uid=TVradmin0,ou=Accounting,dc=example,dc=com
objectClass: top
objectClass: person
objectClass: organizationalPerson
objectClass: inetOrgPerson
cn: Teena Vradmin
sn: Vradmin
uid: TVradmin0
givenName: Teena
description: 2;649;CN=Red Hat CS 71GA Demo,O=Red Hat CS 71GA Demo,C=US;CN=RHCS
  Agent - admin01,UID=admin01,O=redhat,C=US [1] This is Teena Vradmin's descri
 ption.
departmentNumber: 2220
employeeType: Manager
homePhone: +1 510 551-9687
initials: T. V.
telephoneNumber: +1 303 703-2147
facsimileTelephoneNumber: +1 206 682-3534
mobile: +1 213 151-5816
pager: +1 804 769-1685
manager: cn=Olga Lake
secretary: cn=Silva Giamatteo
roomNumber: 7730
carLicense: ZSN6DM3
l: Milpitas
ou: Accounting
mail: Teena_Vradmin@example.com
postalAddress: 796,  Dept #58, Room#Accounting
title: Senior Accounting Visionary
userCertificate;binary:: MIIBvjCCASegAwIBAgIBAjANBgkqhkiG9w0BAQQFADAnMQ8wDQYDV
 QQDEwZjb25maWcxFDASBgNVBAMTC01NUiBDQSBDZXJ0MB4XDTAxMDQwNTE1NTEwNloXDTExMDcwNT
 E1NTEwNlowIzELMAkGA1UEChMCZnIxFDASBgNVBAMTC01NUiBTMSBDZXJ0MIGfMA0GCSqGSIb3DQE
 BAQUAA4GNADCBiQKBgQDNlmsKEaPD+o3mAUwmW4E40MPs7aiui1YhorST3KzVngMqe5PbObUHMeJN
 7CLbq9SjXvdB3y2AoVl/s5UkgGz8krmJ8ELfUCU95AQls321RwBdLRjioiQ3MGJiFjxwYRIVj1CUT
 uX1y8dC7BWvZ1/EB0yv0QDtp2oVMUeoK9/9sQIDAQABMA0GCSqGSIb3DQEBBAUAA4GBADevhxY6Qy
 DMK3Mnr7vLGe/HWEZCObF+qEo2zWScGH0Q+dAmhkCCkNeHJoqGN4NWjTdnBcGaAr5Y85k1o/vOAMB
 sZePbYx4SrywL0b/OkOmQX+mQwieC2IQzvaBRyaNMh309vrF4w5kExReKfjR/gXpHiWQzGSxC5LeQ
 G4k3IP34
userPassword:: e1NTSEF9anp3SzMrUktTZFNNSWpjVWFvQlN1L0NzaWU4Ly8rbUJzRWFFMFE9PQ=
 =

# search result
search: 2
result: 0 Success

# numResponses: 2
# numEntries: 1


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