--_3d71bf45-bf8f-4026-9c30-d39291bf9f56_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
[I thought I'd send this to the ITS list=2C but I only sent it to myself :-= ( ]
I am running slapd built from HEAD on June 30th 2011=2C with back=
-sql
Can you confirm this issue with another backend=2C e.g. back-bdb? B=
ugs
specific to back-sql or to interaction with it could receive only m=
arginal
attention.
p.
I've imported my data into a server with a bdb backend=2C and I see t=
he same problem.
Looking at the code in sssvlv.c=2C it uses tavl_find3() to search the=
values=2C but the
code in tavl_find3() looks to me that it only works properly with an =
exact match
type of matching rule:
Avlnode * tavl_find3( Avlnode *root=2C const void *data=2C AVL_CMP fcmp=2C int =
*ret )
{ int cmp =3D -1=2C dir=3B Avlnode *prev =3D root=3B
while ( root !=3D 0 && (cmp =3D (*fcmp)( data=2C root->avl_data )) !=
=3D 0 ) {
prev =3D root=3B dir =3D cmp > 0=3B root =3D avl_child( root=2C dir )=3B } *ret =3D cmp=3B return root ? root : prev=3B }
since the while loop terminates when the fcmp function returns 0 (i.e=
. exact match).
I think I've worked out where the problem is. Firstly=2C there's a comment before tavl_find3() saying /*
- tavl_find2 - returns Avlnode instead of data pointer.
- tavl_find3 - as above=2C but returns Avlnode even if no match is foun=
d.
- also set *ret =3D last comparison result=2C or -1 if root =3D=3D NULL=
.
*/
but the "or -1 if root =3D=3D NULL" is not done.
Secondly=2C if no exact match is found=2C prev is returned which may po=
int to a node which is less than the search
node=2C depending on what the tree looks like=2C but we really want a p=
ointer to the last node which was greater than
the search node to be returned.
Once these fixes are done=2C the correct node is returned by tavl_find3=
to the call in send_list() in sssvlv.c (line 523).
There is another bug in send_list() in sssvlv.c=2C at lines 535-544:
if ( i > 0 ) { tmp_node =3D tavl_end(so->so_tree=2C TAVL_DIR_RIGHT)=3B dir =3D TAVL_DIR_LEFT=3B } else { tmp_node =3D tavl_end(so->so_tree=2C TAVL_DIR_LEFT)=3B dir =3D TAVL_DIR_RIGHT=3B } for (i=3D0=3B tmp_node !=3D cur_node=3B tmp_node =3D tavl_next( tmp_node=2C dir )=2C i++)=3B so->so_vlv_target =3D i=3B This code is ok if the cur_node is in the left hand side of the tree=2C=
but if it is in the rhs of the tree so_vlv_target is set
to an offset from the end of the list=2C rather than the beginning.
One more issue: the most recent draft spec for vlv (http://tools.ietf.org=
/html/draft-ietf-ldapext-ldapv3-vlv-09) states that the offset field in the= vlv request has range 1..maxInt whereas the targetPosition in the vlv resp= onse has range 0..maxInt.
However=2C my interpretation of the spec is that offset and targetPositio=
n represent the same thing=2C i.e. the position of the target entry in the = list=2C with the first entry having offset/targetPosition =3D 1.
If that interpretation is correct=2C the assignment of so_vlv_target in t=
he code above is off by one=2C since i will be zero if cur_node is at the b= eginning of the list.
I've uploaded a patch to ftp.openldap.org=2C incoming/Chris-Card-110708.ITS= -6985-fix.patch
Chris
=
--_3d71bf45-bf8f-4026-9c30-d39291bf9f56_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
<html> <head> <style><!-- .hmmessage P { margin:0px=3B padding:0px } body.hmmessage { font-size: 10pt=3B font-family:Tahoma } --></style> </head> <body class=3D'hmmessage'><div dir=3D'ltr'> [I thought I'd send this to the ITS list=2C but I only sent it to myself :-= ( ]<br><br><div><br>>=3B >=3B >=3B >=3B >=3B<br>>=3B >=3B >= =3B >=3B >=3B I am running slapd built from HEAD on June 30th 2011=2C w= ith back-sql<br>>=3B >=3B >=3B >=3B<br>>=3B >=3B >=3B >=3B = Can you confirm this issue with another backend=2C e.g. back-bdb? Bugs<br>&= gt=3B >=3B >=3B >=3B specific to back-sql or to interaction with it c= ould receive only marginal<br>>=3B >=3B >=3B >=3B attention.<br>>= =3B >=3B >=3B >=3B<br>>=3B >=3B >=3B >=3B p.<br>>=3B >=3B= >=3B >=3B<br>>=3B >=3B >=3B<br>>=3B >=3B >=3B I've importe= d my data into a server with a bdb backend=2C and I see the same problem.<b= r>>=3B >=3B >=3B<br>>=3B >=3B >=3B Looking at the code in sssvl= v.c=2C it uses tavl_find3() to search the values=2C but the<br>>=3B >= =3B >=3B code in tavl_find3() looks to me that it only works properly wit= h an exact match<br>>=3B >=3B >=3B type of matching rule:<br>>=3B &= gt=3B >=3B<br>>=3B >=3B >=3B Avlnode *<br>>=3B >=3B >=3B tavl= _find3( Avlnode *root=2C const void *data=2C AVL_CMP fcmp=2C int *ret )<br>= >=3B >=3B >=3B {<br>>=3B >=3B >=3B int cmp =3D -1=2C dir=3B<br>= >=3B >=3B >=3B Avlnode *prev =3D root=3B<br>>=3B >=3B >=3B<br>&= gt=3B >=3B >=3B while ( root !=3D 0 &=3B&=3B (cmp =3D (*fcmp)( da= ta=2C root->=3Bavl_data )) !=3D 0 ) {<br>>=3B >=3B >=3B prev =3D ro= ot=3B<br>>=3B >=3B >=3B dir =3D cmp >=3B 0=3B<br>>=3B >=3B >= =3B root =3D avl_child( root=2C dir )=3B<br>>=3B >=3B >=3B }<br>>= =3B >=3B >=3B *ret =3D cmp=3B<br>>=3B >=3B >=3B return root ? roo= t : prev=3B<br>>=3B >=3B >=3B }<br>>=3B >=3B >=3B<br>>=3B >= =3B >=3B since the while loop terminates when the fcmp function returns 0= (i.e. exact match).<br>>=3B >=3B >=3B<br>>=3B >=3B<br>>=3B >= =3B I think I've worked out where the problem is.<br>>=3B >=3B Firstly= =2C there's a comment before tavl_find3() saying<br>>=3B >=3B /*<br>>= =3B >=3B * tavl_find2 - returns Avlnode instead of data pointer.<br>>= =3B >=3B * tavl_find3 - as above=2C but returns Avlnode even if no match = is found.<br>>=3B >=3B * also set *ret =3D last comparison result=2C or= -1 if root =3D=3D NULL.<br>>=3B >=3B */<br>>=3B >=3B<br>>=3B >= =3B but the "or -1 if root =3D=3D NULL" is not done.<br>>=3B >=3B<br>&g= t=3B >=3B Secondly=2C if no exact match is found=2C prev is returned whic= h may point to a node which is less than the search<br>>=3B >=3B node= =2C depending on what the tree looks like=2C but we really want a pointer t= o the last node which was greater than<br>>=3B >=3B the search node to = be returned.<br>>=3B >=3B<br>>=3B >=3B Once these fixes are done=2C= the correct node is returned by tavl_find3 to the call in send_list() in s= ssvlv.c (line 523).<br>>=3B >=3B<br>>=3B >=3B There is another bug = in send_list() in sssvlv.c=2C at lines 535-544:<br>>=3B >=3B<br>>=3B = >=3B if ( i >=3B 0 ) {<br>>=3B >=3B tmp_node =3D tavl_end(so->=3B= so_tree=2C TAVL_DIR_RIGHT)=3B<br>>=3B >=3B dir =3D TAVL_DIR_LEFT=3B<br>= >=3B >=3B } else {<br>>=3B >=3B tmp_node =3D tavl_end(so->=3Bso_t= ree=2C TAVL_DIR_LEFT)=3B<br>>=3B >=3B dir =3D TAVL_DIR_RIGHT=3B<br>>= =3B >=3B }<br>>=3B >=3B for (i=3D0=3B tmp_node !=3D cur_node=3B<br>&g= t=3B >=3B tmp_node =3D tavl_next( tmp_node=2C dir )=2C i++)=3B<br>>=3B = >=3B so->=3Bso_vlv_target =3D i=3B<br>>=3B >=3B This code is ok if = the cur_node is in the left hand side of the tree=2C but if it is in the rh= s of the tree so_vlv_target is set<br>>=3B >=3B to an offset from the e= nd of the list=2C rather than the beginning.<br>>=3B >=3B<br>>=3B<br>= >=3B One more issue: the most recent draft spec for vlv (http://tools.iet= f.org/html/draft-ietf-ldapext-ldapv3-vlv-09) states that the offset field i= n the vlv request has range 1..maxInt whereas the targetPosition in the vlv= response has range 0..maxInt.<br>>=3B<br>>=3B However=2C my interpreta= tion of the spec is that offset and targetPosition represent the same thing= =2C i.e. the position of the target entry in the list=2C with the first ent= ry having offset/targetPosition =3D 1.<br>>=3B<br>>=3B If that interpre= tation is correct=2C the assignment of so_vlv_target in the code above is o= ff by one=2C since i will be zero if cur_node is at the beginning of the li= st.<br>>=3B<br><br>I've uploaded a patch to ftp.openldap.org=2C incoming/= Chris-Card-110708.ITS-6985-fix.patch<br><br></div><div>Chris<br><br></div> = </div></body> </html>=
--_3d71bf45-bf8f-4026-9c30-d39291bf9f56_--
-
ctcard＠hotmail.com