Use skiplist-based FastCallSet within trace::CallSet

The FastCallSet supports only ranges step of 1 and freq of
FREQUENCY_ALL, so store any such ranges there, and store all other
ranges in the existing, linear list of CallRange.

For manually entered call sets on the command line, the performance
hit of the linear lookup was not generally a problem. But when taking
the (potentially huge) output of "apitrace trim --print-callset" the
performance hit made things quite painful. This makes things usable
again.

Rename trim::CallSet to trace::FastCallSet

This is in preparation for being able to use this code to optimize the common
cases in trace::CallSet, (callsets without step or freq).

Extend trim::CallSet with a new range-based add method.

Previously, individual calls had to be added one-at-a-time. This was
adequate for trimming functionality where one call is examined at a
time.

But I'm now wanting to use this same CallSet code to dramatically
optimize the performance of callset specifications on the apitrace
command-line, (in particular large callsets resulting from "apitrace
trim --print-callset"). In this case, we really want to add entire
call ranges rather than just one call at a time.

trim: Use custom skiplist for required list (instead of std::set<unsigned>)

The std::set<unsigned>::insert method has been dominating profile
output for trimming large traces. Meanwhile, the access patterns of
TraceAnalyzer on the required list is extremely structured; it often
adds the next sequential integer. So we can optimize this data
structure dramatically with two additions:

  1. Store ranges rather than single elements, so that the addition of
     a new number can expand an existing range rather than inserting a
     new element.

  2. Remember the most recent element looked-up so that we can check
     it first and not do any new lookup for in-order accesses.

With these two changes we get O(1) behavior for the access pattern of
adding sequential integers. For other cases we can still get
logarithmic behavior, but we can keep N dramatically smaller.

Unfortunately, we can't implement either change (that I can see) with
STL. I don't see any way to support lookup with range-based elements
in any STL data structure.

So here, I implement a skip-list based callset data structure. It
provides optimization (1) above and affords an easy implementation of
(2) as well, (though that is postponed to a later commit).

The skip-list implementation is ported from a C version which Keith
Packard and I implemented for cairo, and with the identical license as
the license of apitrace. The reference I used is the commit named
c2509f8a721ec489e1b44fa8a68be165363787a7 in the cairo repository.

In addition to changing from C to C++, I implemented range-based
elements.

trim: Enable dependency analysis (--auto) by default.

The --exact mode of trimming can be useful, but only if the user has
somehow performed all the dependency analysis needed manually, (such
as by extracting a list of calls from a previous run by
--print-callset). Since --exact inherently requires more care to be
used, it makes sense to also require an extra command-line option, and
to thus prefer the easier-to-use --auto mode by default.

trim: Add --no-deps, --no-prune, and --exact options.

These allow for explicitly specifying the behavior desired. This
change anticipates some future change of the default trimming from
--exact to --auto. (That is, with these options in place, scripts can
be written today with either --exact or --auto and be immune to any
future change of the default.)

Fix sorting of callFlagTable

Commit 89681160639 inserted three entries in an unsorted position in
the list, tripping up an internal check and causing many apitrace
operations to abort. Fix this by restoring correct sorting.

trim: Fix early-bailout bug when accepting both --calls and --frames

The trim code was inappropriately bailing once either list was
exhausted, before also exhausting the user's other requested list.

This fixes the traces/trim-frames-and-calls test recently added to the
apitrace-tests repository.

Thanks to Eric Anholt for reporting this bug.

trim: Greatly expand the list of calls considered to have no side effects

The list of calls added here with the NO_SIDE_EFFECTS flag was
obtained from the existing specs/glapi.py file, (most[*] calls with
"sideeffects=False").

It's a bit unfortunate that we have this duplication of information in
the source tree, (two different lists of calls with no side
effects). But that duplication was already present before this
commit. This commit merely brings this list into sync with the other.

[*] The following calls are not added here in spite of having
sideeffects=False in glapi.py:

    glGetTextureImageEXT
    glGetnCompressedTexImageARB
    glGetnColorTableARB

José reports that the above calls can have side effects when PBOs are
on, (and he plans to update glapi.py).

Then, while the following calls may not affect traditional "GL state"
they do have side effects that can be observed by the user. And these
are debugging side effects that can be very important when
replaying/analyzing a trace. For example, debug message or string
markers are used to decorate different portions of the graphics
command stream with user-supplied data that exists nowhere else. So
these calls are not considered as having no side effects:

    glDebugMessageControl
    glDebugMessageControlARB
    glDebugMessageEnableAMD
    glDebugMessageInsert
    glDebugMessageInsertAMD
    glDebugMessageInsertARB
    glPopDebugGroup
    glPushDebugGroup
    glStringMarkerGREMEDY

trim: Don't consider a SwapBuffers call has having no side effects

I can't justify why I ever added this code. I can only guess that I was
trying to get qapitrace to not show frame markers for frames that had
largely been trimmed.

Anyway, the code is wrong. SwapBuffers call obviously have significant
side effects. And the effect I was trying to achieve is already well
satisified by the change in 2f0d1a3244c8953a4468759ac466b80c4965d38f
that will trim a SwapBuffers call when --trim-spec=drawing is in
force.

trim --prune: Look at FLAG_NO_SIDE_EFFECTS rather than FLAG_VERBOSE

The --prune option is documented precisely to prune calls with no side
effects, so that's the flag it should examine.

Previously, the trim --prune code was keying off of the VERBOSE
flag. This hasn't made a substantial difference in the past, (the
NO_SIDE_EFFECTS calls have historically all been VERBOSE as well). But
NO_SIDE_EFFECTS has the advantage that it can objectively determined,
so the set of calls that should have this flag should be
unambiguous. (Meanwhile, whether any particular call should be
classified as VERBOSE is inherently subjective.)

gltrace,glretrace: Properly handle PBOs with GL_EXT_direct_state_access.

- glCompressed*Tex*ImageEXT receive intptr instead of blobs when PBO is used

- glGet*Tex*ImageEXT have side effects when PBO is used

replay: Add a --loop option to repeatedly loop over the final frame

This can be useful for repeatedly exercising the driver with the
operations of a single frame.

glretrace: Flush outstanding requests when waiting for user input.

This helps make "apitrace replay -sb" work in cases where the driver
really only exposes double-buffered rendering, (so a flush is required
to make anything appear if the trace doesn't include a final
SwapBuffers).

Cleanup README formatting.

gui: Fix includes.

stdio.h doesn't seem necessary. stdlib.h might be though, for exit().

qapitrace: Support executing glretrace on a remote target host.

This is supported with a new command-line argument:

qapitrace --remote-target <HOST> <trace-file>

See README.markdown for documentation on usage and current limitations
of this feature.

cmake: Update android.toolchain.cmake from upstream (issue #115).

From https://github.com/taka-no-me/android-cmake/commit/62bcf2b40e8b8a943dd4923dfcf614e661af0678

Rename Android.markdown to Dalvik.markdown.

As README still contains Android information.

Minor tweaks.

Improve Android tracing instructions

Tracing of Java applications on Android is quite different from tracing native
executables, so move it to a separate file.

Add instructions on using wrapping support that appeared in Android 4.0, which
simplifies usage of apitrace on Android.

Add a reference to adjust-child-env tool that allows to inject tracing library
on Android without rebuilding and reflashing recovery image.

Signed-off-by: José Fonseca <jose.r.fonseca@gmail.com>

gui: Handle calls stranded between frames gracefully (issue #117).

Still a bit hackish (those calls will disappear), but at least the gui
doesn't crash now.

cli: Fix script search for out of source build.

Only for debug builds.  Release must be installed.

gltrace: Handle negative lengths in glShaderSource* (issue #116).

Add per-directory synopsis.

Add a high-level overview of apitrace source tree.

common: Add more comments.

cmake: Check for libproc library name

libprocps can be replaced with libprocps-ng, so check for the proper library name.
This fix building with ArchLinux.

Reviewed-by: Arthur Huillet <arthur.huillet@free.fr>
Signed-off-by: José Fonseca <jfonseca@vmware.com>

common: Set flags for D3D11.1 calls too.

d3dretrace: Add state dumping support for ID3D11DeviceContext1

Signed-off-by: José Fonseca <jfonseca@vmware.com>

glretrace: Fix cpu timings when not measuring gpu times.

Add some missing DXGI and D3D11.1 api

Signed-off-by: José Fonseca <jfonseca@vmware.com>

dispatch: Compensate for broken GL headers in Visual Studio 2012

cmake: Fix D2D include path w/ Visual Studio 2012.

gui: Link against pthread.

/usr/bin/ld: CMakeFiles/qapitrace.dir/apitracecall.cpp.o: undefined
reference to symbol '__pthread_key_create@@GLIBC_2.2.5'
/usr/bin/ld: note: '__pthread_key_create@@GLIBC_2.2.5' is defined in DSO
/lib64/libpthread.so.0 so try adding it to the linker command line
/lib64/libpthread.so.0: could not read symbols: Invalid operation

Signed-off-by: José Fonseca <jfonseca@vmware.com>

glretrace: Fix several problems with the earlier commit.

retrace: Add single thread option.

Allow to replay trace using only one thread, helpful when debugging
driver.

Signed-off-by: Jerome Glisse <jglisse@redhat.com>
Signed-off-by: José Fonseca <jfonseca@vmware.com>

glretrace: Fix dumping of cube map FBO attachements.

directxtex: Fix MinGW64 build.

d3dretrace: Use DirectXTex for d3d10 state too.

Merge branch 'directxtex'

Extend profiling tool to support Vsize and Rss memory usage profile per call

Add one new option -pmem for retrace tool to track Visze and Rss usage during every call

Signed-off-by: Shuang He <shuang.he@intel.com>
Signed-off-by: José Fonseca <jfonseca@vmware.com>

Update news for new nomenclature.

cli: Add an alias mechanism and alias "retrace" to "replay"

This allows any existing scripts calling "apitrace retrace" to
continue to work.

cli: Rename "apitrace retrace" to "apitrace replay".

After some debate on the mailing list, the consensus favors the name
"replay" for this operation. Update the documentation in
README.markdown to match.

dxgitrace: Generalize the swapchain size for the entry functions too.

d3dretrace: Force DWM traces to run on a window.

Fullscreen is hard to debug.

Serialize swapchain dimensions.

trace: Unwrap all args before serializing them.

trace: Remove unused Trace::unwrapRet method.

inject: Always output warning messages to debug output.

inject: Add define to use environment var instead of shared memory.

d3dretrace: Cope with _MAP_FLAG_DO_NOT_WAIT flags.

If the map succeeded in the original trace, then we must wait.

d3dretrace: Replay IUnknown::AddRef/Release methods faithfully.

Several D3D APIs (especially recent ones) keep track of reference counts
and will ensure errors if reference counting is not properly done.

For example, IDXGISwapChain::ResizeBuffers will fail if there are
outstanding references to its buffers.

trace_parser: More comprehensive debug output.

It was useful to diagnose issue #110.

replay: Support applications mixing glCreateProgramObjectARB and glUseProgram

As is known to happen with OpenGL, there are many more than one ways
to do the same thing. In this case, one can create a program
(glCreateProgram) or a program object (glCreateProgramObjectARB) along
with many similar pairs of functions.

In fact, a single application might even mix these two approaches,
(for example, calling glCreateProgramObjectARB and then calling
glUseProgram rather than glUseProgramObjectARB).

Historically, glretrace could fail with such mixed usage. The calls
into the ObjectARB function would go through _handleARB_map while the
other calls would go through _program_map, so after mixed calls the
desired object would not be found in the referenced map.

Making mixed usage work requires merging both _program_map and
_shader_map together with _handleARB map. This is correct for any
OpenGL implementation which supports the GL_ARB_shader_objects
extension, since there is no way to implement this extension correctly
without having shaders and programs in the same namespace.

However, we carefully maintain separate _shader_map and _program_map
for an OpenGL implementation not supporting GL_ARB_shader_objects. In
this case, it's not possible for an application to mix usage (since
none of the ObjectARB functions are guaranteed to exist). And it's
also possible for the implementation to provide separate namespaces
for shaders and programs, so they each need their own map.

Get DWM traces working.

Sort-of -- shared resources still don't work correctly.

specs/dxva: Try to define DXVA2_PVP_SETKEY.

trim: Trim swapbuffers calls when --trim-spec=drawing

Previously, the SwapBuffers calls were only getting trimmed if
--trim-spec included "no-side-effects". It was counter-intuitive that
a trim-spec of "drawing" alone would leave all the SwapBuffers calls
in place. So catch them under this trim-spec as well.

trim: Add a new --trim-spec option for fine-grained trimming

This has two benefits:

1. In cases where the dependency analysis goes wrong, using the --trim-spec
   option can help identify which portion of the code is misbehaving, (and
   allows the user to still get some trim benefit by avoiding the broken
   code).

2. The implementation of this change breaks the analysis code up into several
   more fine-grained functions, so it should be easier to review and maintain.

d3dtrace: Fix DXVA2_DecodeExecuteParams::pCompressedBuffers spec.

d3dtrace: Recognize YV12 format.

Update Android instructions.

Not really based from personal experience, but rather on what others wrote,
namely

  https://github.com/kanru/apitrace/commit/5948e72a25b1d2df07299db0d49f91677827478b

glstate: Cleanup the read buffer selection code slightly.

We were calling glReadBuffer(draw_buffer) before reading the GL_READ_BUFFER.

image: make getDrawBufferImage() work for ES or !ARB_draw_buffers

Without this 'apitrace dump-images' was failing for me (GLES, freedreno
gallium driver) because attachment would be GL_NONE.

Signed-off-by: Rob Clark <robdclark@gmail.com>
Reviewed-by: Carl Worth <cworth@cworth.org>
Signed-off-by: José Fonseca <jfonseca@vmware.com>

d3dretrace: Recognize IDirect3DDevice9Ex::PresentEx as frame terminator.

trim: Fix short command-line option -a for "apitrace trim"

This was documented as being equivalent to --auto, but one piece of
the plumbing was not in place.

glretrace: Fix snapshots on GL 3.2 core contexts (issue #106).

glPush/PopClientAttrib() are not available in core contexts. Simply
save/restore the state via glGet and pack API.

glretrace: Ignore a few more CGL calls.

os: Cast pthread_create's arg parameter.

cli: Inject DLL on windows by default.

cli: Update description of windows trace apis.

gltrace: Prevent use of uninitialised variable.

gltrace: Recognize more ES parameters.

We now always use our bundled headers so no need to be conservative any
more.

gltrace: Support GL_(NUM_)PROGRAM_BINARY_FORMATS (issue #104).

gltrace/retrace: Full support for variable length parameters.

Such as GL_COMPRESSED_TEXTURE_FORMATS.

retrace: Split ScopedAllocator into its own header.

It will be useful outside of retrace.

Update downloads link.

cli: Fix MSVC build.

d3dretrace: presents may flip so set CALL_FLAG_SWAP_RENDERTARGET flag.

d3dretrace: Dump D3D8 images too.

scripts: Add some missing code.

scripts: New script to convert to PIX.

d3dretrace: Follow --driver option for d3d8/d3d9 too

d3d9state: Upack D3DFMT_R5G6B5 too.

Quite common.

scripts: Don't install bogus sample.py

scripts: Install all of them.

Install all thirdparty licenses.

Merge branch 'trim-auto'

Conflicts:
cli/CMakeLists.txt

Merge remote-tracking branch 'github/timestamp'

glretrace: Remove the gpu/cpu time syncing code.

No longer necessary now that we use the same clock (GL_TIMESTAMP) for
both GPU and CPU time measurements.

cmake: Move the binary/installs definitions to CLI.

As that's the only place they are used.

qapitrace: Determine binary dir in run-time.

qapitrace: Adjust PATH only once and for all.

qapitrace: Fix histogram tooltip for profiles with small number of calls.

gui/tracedialog: Don't show warning when user cancel to browse.

And add three dots to browse button's label to indicate dialog.

gui/mainwindow: Add functions that toggle actions enables and use it.

Added enabling/disabling of few more actions.
Cleanup .ui file (set actions to default state).

gui: Fix crash on trigger actions without loaded trace-file.
gui/apitrace: findFrameStart(), findFrameEnd(): Do nothing, when passed frame is null-pointer.

gui: Small style/usability fixes.

Add accelerator (F) to Edit->Find.
Add accelerator (N) and shortcut (Ctrl+N) to File->New.
Rename "File->New" to "File->New..." to indicate, that dialog will be showed.

glretrace: Use GL_TIMESTAMP (if available) for CPU profiling.

The prior scheme of trying to continuously re-synchronize separate CPU
and GPU counters is doomed to always be unreliable. Instead, simply prefer
to use the GL_TIMESTAMP values for both GPU and for CPU profiling.

v2: José Fonseca: use glGet(GL_TIMESTAMP)

d3d11state: Use DirectXTex for format conversion.