337896 - nsStyleChangeList::AppendChange uses memcpy with overlapping regions

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Jesse Ruderman]

http://lxr.mozilla.org/seamonkey/source/layout/base/nsStyleChangeList.cpp#89

102           if (index < mCount) { // move later changes down
103             memcpy(&mArray[index], &mArray[index + 1], 
104                    (mCount - index) * sizeof(nsStyleChangeData));
105           }

memcpy has undefined behavior when the regions overlap.  Code should use memmove instead if the regions might overlap (and, afaik, the only difference between the two functions is that memmove is more careful when the regions overlap).

I noticed this because Valgrind complained, saying "Source and destination overlap in memcpy" with nsStyleChangeList::AppendChange just below Valgrind's version of memcpy on the stack.

Comment 1

[Mats Palmgren (inactive)]

Jesse, I can't seem to trigger these lines of the code...
Which URL and RandomStyles params did you use?

Comment 2

[Mats Palmgren (inactive)]

...answering my own question: RandomStyles 0,0,1200,200 triggers it
for http://slashdot.org/ and http://news.google.com/ for example.

FWIW, I noted that the current algorithm would copy the same array
elements twice if the elements to remove are not consecutive.
e.g. mArray=a,b,c,X,d,e,X,f,g  and aContent=X would copy f,g twice.
This could be avoided if we compact the array from the beginning.

However, it seems it is extremely rare that this would occur (if ever).
Out of 244059 calls to nsStyleChangeList::AppendChange only 93
triggered a memcpy at all and they called memcpy just once.

FWIW, some of the statistics I collected:

mCount: Calls that trigger memcpy, Avg.memcpy, Avg.memcpy elms
2: 2 1.000000 1.000000
3: 4 1.000000 1.000000
4: 9 1.000000 1.333333
5: 4 1.000000 2.250000
6: 6 1.000000 2.000000
7: 7 1.000000 2.857143
8: 5 1.000000 3.000000
9: 2 1.000000 6.500000
10: 2 1.000000 5.000000
11: 2 1.000000 2.500000
12: 1 1.000000 8.000000
13: 2 1.000000 1.500000
14: 1 1.000000 10.000000
15: 1 1.000000 1.000000
16: 4 1.000000 7.250000
18: 2 1.000000 12.500000
19: 1 1.000000 1.000000
23: 1 1.000000 1.000000
28: 2 1.000000 14.000000
31: 1 1.000000 15.000000
34: 1 1.000000 3.000000
35: 2 1.000000 1.500000
36: 2 1.000000 4.000000
39: 1 1.000000 1.000000
41: 1 1.000000 2.000000
42: 1 1.000000 32.000000
44: 1 1.000000 1.000000
45: 1 1.000000 1.000000
48: 1 1.000000 44.000000
61: 1 1.000000 43.000000
63: 2 1.000000 28.500000
64: 1 1.000000 1.000000
65: 1 1.000000 1.000000
66: 2 1.000000 1.000000
67: 1 1.000000 1.000000
68: 1 1.000000 1.000000
69: 3 1.000000 3.000000
74: 1 1.000000 21.000000
84: 1 1.000000 1.000000
87: 1 1.000000 1.000000
105: 1 1.000000 103.000000
106: 1 1.000000 1.000000
110: 1 1.000000 1.000000
123: 1 1.000000 1.000000
124: 1 1.000000 1.000000
137: 1 1.000000 3.000000
139: 1 1.000000 1.000000
167: 1 1.000000 30.000000

memcpy length=1 calls=50
memcpy length=2 calls=9
memcpy length=3 calls=7
memcpy length=4 calls=3
memcpy length=5 calls=1
memcpy length=6 calls=4
memcpy length=7 calls=3
memcpy length=8 calls=2
memcpy length=9 calls=1
memcpy length=10 calls=1
memcpy length=12 calls=1
memcpy length=13 calls=1
memcpy length=15 calls=2
memcpy length=21 calls=1
memcpy length=27 calls=1
memcpy length=30 calls=1
memcpy length=32 calls=1
memcpy length=43 calls=1
memcpy length=44 calls=1
memcpy length=56 calls=1
memcpy length=103 calls=1

Total: Calls that trigger memcpy, Avg.memcpy, Avg.memcpy elms
93 1.000000 6.419355

Comment 3

[Mats Palmgren (inactive)]

Attachment: Patch rev. 1

Comment 4

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Comment on attachment 221982 [details] [diff] [review]
Patch rev. 1

Please land this on the 1.8 branch as well (if it's open, of course).

Comment 5

[Mats Palmgren (inactive)]

Checked in to trunk at 2006-06-03 07:19 PDT:

Checking in layout/base/nsStyleChangeList.cpp;
/cvsroot/mozilla/layout/base/nsStyleChangeList.cpp,v  <--  nsStyleChangeList.cpp
new revision: 1.19; previous revision: 1.18
done


Checked in to MOZILLA_1_8_BRANCH at 2006-06-03 07:44 PDT:

Checking in layout/base/nsStyleChangeList.cpp;
/cvsroot/mozilla/layout/base/nsStyleChangeList.cpp,v  <--  nsStyleChangeList.cpp
new revision: 1.16.28.1; previous revision: 1.16
done