289558 - cert_CombineConstraintsLists doesn't always work

Status: RESOLVED INVALID

(NSS :: Libraries, defect, P2)

Description

[Hanfei Yu]

cert_CombineConstraintsLists in genname.c doesn't handle two lists of single
element well. It will returns list2 without merging them. Because the list has
single element, its l.prev and l.next are pointing to itself. When updating
end[12]->next, lists are merged. But then updating begin[12]->prev, lists are
reset back to what it were.

Following is my fix:

cert_CombineConstraintsLists(CERTNameConstraint *list1, CERTNameConstraint *list2)
{
    PRCList *begin1;
    PRCList *begin2;
    PRCList *end1;
    PRCList *end2;

    if (list1 == NULL){
	return list2;
    } else if (list2 == NULL) {
	return list1;
    } else {
	begin1 = &list1->l;
	begin2 = &list2->l;
	end1 = list1->l.prev;
	end2 = list2->l.prev;

	if (list1->l.prev == list1->l.next) {
		end1->next = begin2;
	} else {
		end1->next = begin2;
		begin1->prev = end2;
	}
	if (list2->l.prev == list2->l.next) {
		end2->next = begin1;
	} else {
		end2->next = begin1;
		begin2->prev = end1;
	}
	return list1;
    }
}

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

Suggesting P2 for 3.10

Comment 2

[Julien Pierre]

Retargetting for 3.12 .

Comment 3

[Julien Pierre]

This is a bugfix, suggesting for 3.11 .

Comment 4

[Julien Pierre]

Attachment: same fix as a patch

checked in to NSS_LIBPKIX_BRANCH .

Checking in genname.c;
/cvsroot/mozilla/security/nss/lib/certdb/genname.c,v  <--  genname.c
new revision: 1.28.10.1; previous revision: 1.28
done

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 189439 [details] [diff] [review]
same fix as a patch

I believe the original code is right, and the patch actually breaks it.  I
don't think there's really a bug here.	

These are doubly-linked, circular lists.  There really is no
first node or last node.  One cannot tell, by inspection of
the list, which node is the first and which is the last.

It is not the case that the list has two nodes, one at each
end, where the first node's prev pointer points at itself,
and the last node's next pointer points at itself.
You don't walk down a list until you find an entry whose
next pointer points to itself.	

They're circular.  Pick any node in the list.  Call it the "first" node. 
Traverse the list in either direction until you come to that node again.  Walk
the list until you find the
node from which you started.  

The combine function turns them into a single doubly-linked circular list.

Then node->prev is the "last" node, and last->next is the first node. When a
list has one element, its next and prev pointers point to itself.  When a list
has two nodes, each of those nodes' prev and next pointers points to the other
one.  That's correct behavior in a circular list. 

I walked through the behavior of the original code for the case
of two single-element lists, and it appears to me to be correct.

This patch would actually change the lists to no longer be
circular lists.  That's an undesirable change, IMO.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Imagine two nodes, a and b.
Initialiy
   a.prev == &a
   a.next == &a
   b.prev == &b
   b.next == &b

After merging these two single-node lists, 
it should be true that

   a.prev == &b
   a.next == &b
   b.prev == &a
   b.next == &a

If the code does that, it's correct.
I believe the existing NSS code does that.
If you can show me that it doesn't produce that
outcome, I'll reconsider my position on this bug.

The patch above produces a different outcome.
After merging a and b above (as list1 and list2),
with the patch code, we get:

   a.prev == &a  
   a.next == &b
   b.prev == &b
   b.next == &a

which is wrong; that is, not a circular list.

I suspect there is now code in the PKIX branch
that finds the end of a list with a method that 
doesn't work for circular lists.
I encourage you to back this patch out from the PKIX
branch, and change the list-traversal code in PKIX to
work with circular lists.

Marking invalid.

Comment 7

[Julien Pierre]

Nelson,

We are using bugzilla to track changes on the PKIX branch as well. Since changes
may be needed that are not committed, please don't close the bug.

Comment 8

[Julien Pierre]

Reassigning to Hanfei .

Comment 9

[Wan-Teh Chang]

PRCList is designed to be a doubly-linked circular list
that always contains a dummy code.  The purpose of the
dummy node is that the prev and next pointers can never
be NULL so the NULL tests can be omitted.  You are
supposed to manipulate a PRCList using the macros defined
in "prclist.h".

Some NSS code doesn't use PRCList
the way it is designed for.  The code in
lib/certdb/genname.c uses PRCList as a doubly-linked
circular list that has at least one node.  (An empty
list is represented by a NULL pointer to the containing
structure.)  The prev and next pointers can never be
NULL either just like the standard PRCList.

I looked at the use of PRCList quickly and it seems
that lib/certdb/genname.c is the only file that uses
PRCList in a nonstandard way (specifically, the
"PRCList l" member of struct CERTGeneralNameStr and
struct CERTNameConstraintStr).  The code is correct
though.

Comment 10

[Hanfei Yu]

Traced the algorithm by hand. It provides the expected result. You may close
this bug.

Comment 11

[Julien Pierre]

Hanfei,

Thanks. In this case, we need to back out your change from NSS_LIBPKIX_BRANCH .
Since several changes were checked in together last friday, please generate a
patch that removes only this change, and attach it to this bug. I can then check
it, or hopefully you'll be able to check it in once your CVS account is finally
active.

Comment 12

[Hanfei Yu]

Attachment: back out changes

Comment 13

[Julien Pierre]

Thanks, Hanfei. I have committed the changes to the NSS_LIBPKIX_BRANCH .

Checking in genname.c;
/cvsroot/mozilla/security/nss/lib/certdb/genname.c,v  <--  genname.c
new revision: 1.28.10.3; previous revision: 1.28.10.2
done

Marking the bug invalid.

Comment 14

[Robert Relyea]

Comment on attachment 189439 [details] [diff] [review]
same fix as a patch

clearing request on already rejected review