Subj : Re: Problem in jsscope.c?
To   : MA
From : Brendan Eich
Date : Mon Sep 20 2004 05:02 pm

MA wrote:
> Hello,
> 
>     We just ran Klocwork software on our Spidermonkey embedding. 
> It pointed out that its possible for array index to be 
> out of bounds at jsscope.c, line 677 
> (http://lxr.mozilla.org/mozilla/source/js/src/jsscope.c#677).
> 
> 675                         --j;
> 676                         if (chunk != lastChunk || j > i)
> 677                             chunk->kids[i] = lastChunk->kids[j];
> 
> 
>    It seems that if the kids[0] of a chunk 
> can be NULL, then  it's possible for j to be -1 and hence 
> be out of range of 'kids' array.

Is Klocwork's static analysis correct here?

The minimal amount code to analyze here is:

                 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
                     if (chunk->kids[i] == child) {
                         lastChunk = chunk;
662                     if (!lastChunk->next) {
                             j = i + 1;
                         } else {
                             j = 0;
                             do {
                                 chunkp = &lastChunk->next;
                                 lastChunk = *chunkp;
                             } while (lastChunk->next);
                         }
                         for (; j < MAX_KIDS_PER_CHUNK; j++) {
672                         if (!lastChunk->kids[j])
                                 break;
                         }
                         --j;
                         if (chunk != lastChunk || j > i)
677                         chunk->kids[i] = lastChunk->kids[j];
                         lastChunk->kids[j] = NULL;
                         if (j == 0) {
                             *chunkp = NULL;
                             if (!list)
                                 parent->kids = NULL;
683                         DestroyPropTreeKidsChunk(rt, lastChunk);
                         }
                         return;
                     }
                 }

Notice that if (j == 0) when control reaches the --j, then indeed we may 
have an ABR on the lastChunk->kids[j], but only if chunk != lastChunk. 
But if chunk != lastChunk, then (lastChunk->next != NULL) at 662, which 
is the only way j could be 0 (i and j are unsigned).

In that case, for j to remain 0 until the --j; is reached, 
lastChunk->kids[0] must be NULL and the then for the if statement at 672 
breaks from the for loop without any j++ executing.

So altogether, we must have a kid in a non-final chunk, and the final 
chunk (lastChunk) must have a NULL kids[0].  But that "can't happen" 
because we always swap the last kid pointer in the last chunk with the 
kid pointer being removed (677), and free any last entire-empty (all 
null kid pointers) chunk (683).


>    What I want to know is this : should I worry about this and fix
> it, or just ignore it? If i were to fix this, what should I do?


It may be that Klocwork's static analysis is not up to reasoning 
completely about the code, and my analysis (and intent and design and 
review when writing this code) is correct.  Otherwise, you'd have to 
point out how the invariant that the last chunk is never empty is violated.

/be

.