[Date Prev][Date Next] [Chronological] [Thread] [Top]

RE: (ITS#6985) sssvlv / greaterThanOrEqual problem



--_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>&gt=3B &gt=3B &gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=
=3B &gt=3B &gt=3B I am running slapd built from HEAD on June 30th 2011=2C w=
ith back-sql<br>&gt=3B &gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B &gt=3B =
Can you confirm this issue with another backend=2C e.g. back-bdb? Bugs<br>&=
gt=3B &gt=3B &gt=3B &gt=3B specific to back-sql or to interaction with it c=
ould receive only marginal<br>&gt=3B &gt=3B &gt=3B &gt=3B attention.<br>&gt=
=3B &gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B &gt=3B p.<br>&gt=3B &gt=3B=
 &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B I've importe=
d my data into a server with a bdb backend=2C and I see the same problem.<b=
r>&gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B Looking at the code in sssvl=
v.c=2C it uses tavl_find3() to search the values=2C but the<br>&gt=3B &gt=
=3B &gt=3B code in tavl_find3() looks to me that it only works properly wit=
h an exact match<br>&gt=3B &gt=3B &gt=3B type of matching rule:<br>&gt=3B &=
gt=3B &gt=3B<br>&gt=3B &gt=3B &gt=3B Avlnode *<br>&gt=3B &gt=3B &gt=3B tavl=
_find3( Avlnode *root=2C const void *data=2C AVL_CMP fcmp=2C int *ret )<br>=
&gt=3B &gt=3B &gt=3B {<br>&gt=3B &gt=3B &gt=3B int cmp =3D -1=2C dir=3B<br>=
&gt=3B &gt=3B &gt=3B Avlnode *prev =3D root=3B<br>&gt=3B &gt=3B &gt=3B<br>&=
gt=3B &gt=3B &gt=3B while ( root !=3D 0 &amp=3B&amp=3B (cmp =3D (*fcmp)( da=
ta=2C root-&gt=3Bavl_data )) !=3D 0 ) {<br>&gt=3B &gt=3B &gt=3B prev =3D ro=
ot=3B<br>&gt=3B &gt=3B &gt=3B dir =3D cmp &gt=3B 0=3B<br>&gt=3B &gt=3B &gt=
=3B root =3D avl_child( root=2C dir )=3B<br>&gt=3B &gt=3B &gt=3B }<br>&gt=
=3B &gt=3B &gt=3B *ret =3D cmp=3B<br>&gt=3B &gt=3B &gt=3B return root ? roo=
t : prev=3B<br>&gt=3B &gt=3B &gt=3B }<br>&gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=
=3B &gt=3B since the while loop terminates when the fcmp function returns 0=
 (i.e. exact match).<br>&gt=3B &gt=3B &gt=3B<br>&gt=3B &gt=3B<br>&gt=3B &gt=
=3B I think I've worked out where the problem is.<br>&gt=3B &gt=3B Firstly=
=2C there's a comment before tavl_find3() saying<br>&gt=3B &gt=3B /*<br>&gt=
=3B &gt=3B * tavl_find2 - returns Avlnode instead of data pointer.<br>&gt=
=3B &gt=3B * tavl_find3 - as above=2C but returns Avlnode even if no match =
is found.<br>&gt=3B &gt=3B * also set *ret =3D last comparison result=2C or=
 -1 if root =3D=3D NULL.<br>&gt=3B &gt=3B */<br>&gt=3B &gt=3B<br>&gt=3B &gt=
=3B but the "or -1 if root =3D=3D NULL" is not done.<br>&gt=3B &gt=3B<br>&g=
t=3B &gt=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>&gt=3B &gt=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>&gt=3B &gt=3B the search node to =
be returned.<br>&gt=3B &gt=3B<br>&gt=3B &gt=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>&gt=3B &gt=3B<br>&gt=3B &gt=3B There is another bug =
in send_list() in sssvlv.c=2C at lines 535-544:<br>&gt=3B &gt=3B<br>&gt=3B =
&gt=3B if ( i &gt=3B 0 ) {<br>&gt=3B &gt=3B tmp_node =3D tavl_end(so-&gt=3B=
so_tree=2C TAVL_DIR_RIGHT)=3B<br>&gt=3B &gt=3B dir =3D TAVL_DIR_LEFT=3B<br>=
&gt=3B &gt=3B } else {<br>&gt=3B &gt=3B tmp_node =3D tavl_end(so-&gt=3Bso_t=
ree=2C TAVL_DIR_LEFT)=3B<br>&gt=3B &gt=3B dir =3D TAVL_DIR_RIGHT=3B<br>&gt=
=3B &gt=3B }<br>&gt=3B &gt=3B for (i=3D0=3B tmp_node !=3D cur_node=3B<br>&g=
t=3B &gt=3B tmp_node =3D tavl_next( tmp_node=2C dir )=2C i++)=3B<br>&gt=3B =
&gt=3B so-&gt=3Bso_vlv_target =3D i=3B<br>&gt=3B &gt=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>&gt=3B &gt=3B to an offset from the e=
nd of the list=2C rather than the beginning.<br>&gt=3B &gt=3B<br>&gt=3B<br>=
&gt=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>&gt=3B<br>&gt=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>&gt=3B<br>&gt=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>&gt=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_--