pkix_List_Destroy destroys by recursion, one level per list item

RESOLVED FIXED in 3.12.3

Status

P2
normal
RESOLVED FIXED
10 years ago
8 years ago

People

(Reporter: nelson, Assigned: alvolkov.bgs)

Tracking

(Blocks: 1 bug)

3.12
3.12.3

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:dos]PKIX SUN_MUST_HAVE)

Attachments

(1 attachment, 1 obsolete attachment)

The stack shown in bug 439123 comment 1 shows a crash that happened while
trying to destroy a list of 9 elements.  It shows that, for each element
in the list, except the last, pkix_List_Destroy called PKIX_PL_Object_DecRef 
which, in turn, called pkix_List_Destroy again.  The comment at line 120
in pkix_List_Destroy even claims that it destroys the list by recursion.
This means that large lists of objects have the potential to cause stack 
overflows.  That's unacceptable design.

Alexei, you said something about the first member of a list having a flag
that identifies it as the head of a list.  Perhaps pkix_list_destroy can
be modified to behave differently depending on the value of that flag.
It could return immediately after 
121         PKIX_DECREF(list->item);
if that first-in-list flag is not set, and if that flag is set, then
go down the list in a loop, decrefing each member.  That's just an idea,
and it depends on that first-in-list flag being set correctly at all times.
(Reporter)

Updated

10 years ago
Blocks: 436376
Priority: -- → P2
Whiteboard: PKIX
(In reply to comment #0)
> Alexei, you said something about the first member of a list having a flag
> that identifies it as the head of a list.  Perhaps pkix_list_destroy can
> be modified to behave differently depending on the value of that flag.
> It could return immediately after 
> 121         PKIX_DECREF(list->item);
> if that first-in-list flag is not set, and if that flag is set, then
> go down the list in a loop, decrefing each member.  That's just an idea,
> and it depends on that first-in-list flag being set correctly at all times.

You could avoid the need for the flag by unlinking each item from the list before destroying it.  In other words, assume that the head's destroy method will destroy each of the remaining items, but it does this by doing something like replacing the PKIX_DECREF(list->next) with:

  curitem = list->next;
  while (curitem) {
    nextitem = curitem->next;
    curitem->next = NULL;
    PKIX_DECREF(curitem);
    curitem = nextitem;
  }

(with the variables "curitem" and "nextitem" being additional PKIX_List*)
(Assignee)

Updated

10 years ago
Target Milestone: 3.12.1 → 3.12.2
(Assignee)

Updated

10 years ago
Whiteboard: PKIX → PKIX SUN_MUST_HAVE
(Assignee)

Comment 2

10 years ago
Created attachment 346165 [details] [diff] [review]
Patch v1. Remove recursive decref call on the members of a list 

Similar fix as to what was suggested in comment #1.
Attachment #346165 - Flags: review?(nelson)
(Reporter)

Updated

10 years ago
Attachment #346165 - Flags: review?(nelson) → review-
(Reporter)

Comment 3

10 years ago
Comment on attachment 346165 [details] [diff] [review]
Patch v1. Remove recursive decref call on the members of a list 

>@@ -119,7 +120,13 @@ pkix_List_Destroy(
> 
>         /* We have a valid list. DecRef its item and recurse on next */
>         PKIX_DECREF(list->item);
>-        PKIX_DECREF(list->next);
>+        nextItem = list->next;
>+        while (nextItem) {
>+            PKIX_List *delItem = nextItem;
>+            nextItem = nextItem->next;
>+            delItem->next = NULL;
>+            PKIX_DECREF(delItem);
>+        }

The new code never changes the value of list->next.  When this function 
returns, list->next will still point at an object that has been decref'ed.
Also, the decref call could change the contents of one or more objects in 
the list, so I think it is best not to remember information about the list
that was gathered before the decref was called.  
I suggest something like this:

>+        while (nextItem = list->next) {
>+            list->next = nextItem->next;
>+            nextItem->next = NULL;
>+            PKIX_DECREF(nextItem);
>+        }
(Assignee)

Comment 4

10 years ago
Created attachment 347371 [details] [diff] [review]
Patch v2 - implement Nelsons suggestion
Attachment #346165 - Attachment is obsolete: true
Attachment #347371 - Flags: review?(nelson)
(Reporter)

Updated

10 years ago
Attachment #347371 - Flags: superreview?(alexei.volkov.bugs)
Attachment #347371 - Flags: review?(nelson)
Attachment #347371 - Flags: review+
(Reporter)

Comment 5

10 years ago
Comment on attachment 347371 [details] [diff] [review]
Patch v2 - implement Nelsons suggestion

I feel like I'm giving r+ to my own patch.  So, I'll ask Alexei to review it also. :)
(Assignee)

Comment 6

10 years ago
Comment on attachment 347371 [details] [diff] [review]
Patch v2 - implement Nelsons suggestion

The main problem with the previous patch was that it was leaving list->next pointing into destroyed object. 

I agree with the solution in this patch. r+
Attachment #347371 - Flags: superreview?(alexei.volkov.bugs) → superreview+
(Assignee)

Comment 7

10 years ago
patch is integrated
Status: NEW → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED

Comment 8

9 years ago
Comment on attachment 347371 [details] [diff] [review]
Patch v2 - implement Nelsons suggestion

>         /* We have a valid list. DecRef its item and recurse on next */
>         PKIX_DECREF(list->item);
>-        PKIX_DECREF(list->next);
>+        while (nextItem = list->next) {
>+            list->next = nextItem->next;
>+            nextItem->next = NULL;
>+            PKIX_DECREF(nextItem);
>+        }      

Should we remove "recurse on next" from the comment?

Chromium just ran into this bug (because the system NSS libraries
in Ubuntu are version 3.12.0.3): http://codereview.chromium.org/113578

Chromium will work around this bug by increasing the thread stack
size from 64KB to 128KB (64KB is too small anyway).

Comment 9

9 years ago
This bug is fixed in NSS 3.12.3, not 3.12.2.
Target Milestone: 3.12.2 → 3.12.3
Whiteboard: PKIX SUN_MUST_HAVE → [sg:dos]PKIX SUN_MUST_HAVE
Group: core-security
You need to log in before you can comment on or make changes to this bug.