DTrace: qsort use in Firefox, part 2
Earlier, I wrote about some silly qsort behavior in Firefox. I couldn’t help but dig a bit deeper.
Before, we concluded that there were a lot of 8-element, 4-byte element sorts. What are these used for? What part of Firefox is causing these? DTrace to the rescue.
First, let’s change the last DTrace command from last time a bit. First of all, let’s look at 4-byte element invocations only (arg2 equals 4) and let’s aggregate on the caller function name:
# dtrace -n 'pid1120:libc:qsort:entry/arg2==4/{@[ufunc(ucaller)]=llquantize(arg1, 10,0,6,20)} tick-60sec{printa(@)}'
...
1 75455 :tick-60sec
libnss3.so`DPCache_GetUpToDate
value ------------- Distribution ------------- count
< 1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 14
1 | 0
libglib-2.0.so.0.2501.0`g_array_sort
value ------------- Distribution ------------- count
700 | 0
750 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 1
800 | 0
libfontconfig.so.1`FcFontSetSort
value ------------- Distribution ------------- count
55 | 0
60 |@ 4
65 | 2
70 | 0
75 |@@@@ 20
80 |@@@@@ 24
85 |@@@@@@@ 36
90 |@@@@@ 26
95 | 0
100 |@@@@@@@@@@@@@@ 76
150 |@@@@ 22
200 | 0
libcairo.so.2.10800.10`_cairo_bentley_ottmann_tessellate_bo_edges
value ------------- Distribution ------------- count
3 | 0
4 |@ 59
5 | 0
6 | 32
7 | 0
8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 2357
9 | 0
10 |@@ 137
15 |@@@ 215
20 |@ 52
25 | 12
30 |@ 58
35 |@@ 200
40 |@ 67
45 | 3
50 | 2
55 | 2
60 | 7
65 | 0
70 |@ 67
75 | 0
80 | 0
85 | 0
90 | 0
95 | 16
100 | 0
We see four unique functions that call qsort. It doesn’t take long to spot the one we were looking for: _cairo_bentley_ottmann_tessellate_bo_edges in libcairo.so. Interesting, so it turns out that it wasn’t Firefox itself doing all these sorts (8-element, 4-byte element) but rather the Cairo graphics library. It would also seem that it is the only place that does these sorts. Let’s see how Firefox is involved in this.
# dtrace -n 'pid1120:libc:qsort:entry/arg2==4 && arg1==8/{@[ustack()]=count()} tick-60sec{printa(@)}'
...
0 75455 :tick-60sec
libc.so.1`qsort
libcairo.so.2.10800.10`_cairo_bentley_ottmann_tessellate_bo_edges+0x172
libcairo.so.2.10800.10`_cairo_bentley_ottmann_tessellate_polygon+0x41f
libcairo.so.2.10800.10`_cairo_path_fixed_fill_to_traps+0x150
libcairo.so.2.10800.10`_cairo_clip_clip+0xe3
libcairo.so.2.10800.10`_cairo_gstate_clip+0x44
libcairo.so.2.10800.10`cairo_clip_preserve+0x31
libxul.so`__1cKgfxContextEClip6M_v_+0x24
libxul.so`__1cInsWindowNOnExposeEvent6MpnK_GtkWidget_pnP_GdkEventExpose__i_+0x56e
libxul.so`__1cPexpose_event_cb6FpnK_GtkWidget_pnP_GdkEventExpose__i_+0x72
libgtk-x11-2.0.so.0.2000.0`_gtk_marshal_BOOLEAN__BOXED+0x7b
libgobject-2.0.so.0.2501.0`g_closure_invoke+0xdf
libgobject-2.0.so.0.2501.0`signal_emit_unlocked_R+0x9f2
libgobject-2.0.so.0.2501.0`g_signal_emit_valist+0x6d2
libgobject-2.0.so.0.2501.0`g_signal_emit+0x28
libgtk-x11-2.0.so.0.2000.0`gtk_widget_event_internal+0x24d
libgtk-x11-2.0.so.0.2000.0`gtk_widget_send_expose+0x98
libgtk-x11-2.0.so.0.2000.0`gtk_main_do_event+0x46f
libgdk-x11-2.0.so.0.2000.0`_gdk_window_process_updates_recurse+0x291
libgdk-x11-2.0.so.0.2000.0`_gdk_windowing_window_process_updates_recurse+0x24
184
This counts the number of 4-byte element, 8-element arrays qsort aggregated on the stack trace. We get to use ustack() here because we are in userspace (stack() would give us the kernel stack trace). Where is Firefox in this mess? libxul.so. This is the limit of my knowledge of Firefox internals and someone more knowledgeable could tell you more.
Your Turn
Do you use DTrace? Do you have some interesting war stories? Let me know in the comments!