linux-kernel - [RFC][PATCH 00/12] tracing/filter: Remove 32 pred limit and add short circuits

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20110128042118.561146147@goodmis.org>
Date:	Thu, 27 Jan 2011 23:21:18 -0500
From:	Steven Rostedt <rostedt@...dmis.org>
To:	linux-kernel@...r.kernel.org
Cc:	Ingo Molnar <mingo@...e.hu>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Tom Zanussi <tzanussi@...il.com>,
	Frederic Weisbecker <fweisbec@...il.com>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Subject: [RFC][PATCH 00/12] tracing/filter: Remove 32 pred limit and add short circuits

While doing some intense tracing, I hit the 32 pred limit in the filters.
This annoyed me a little, so I decided to remove this constraint.
But as I saw that the current approach needs to store state in a stack,
the algorithm needed to be changed such that we could do any
arbitrary number of preds without needing to store state.

This patch series converts the stack version into a tree walk that can
use the direction of the walk to store the state.

An added bonus is that this also allows short circuit of AND and OR
logic when one value is found to be false or true respectively.
That is, if the left child is false and the operation is an AND, we
do not need to process the right child. We can just set the result
to false and pass it up to the parent.

For an optimization, the tree is also folded so that multiple ANDs
or ORs in a row are converted to a single pred that has all
the opperations in an array:

  a || b || c || d || e ...

  a && b && c && d && e ...

Either of the above does not need a tree walk. If any of the ORs
are found to be true, we can exit and move to the parent. If any
of the ANDs are found to be false we can do the same. Otherwise
we can use the result of the last compare.

I'm sending this out as an RFC first, but they are pretty much
set. I'll start running them through more vigorous tests and then
package them up for 2.6.39.

This email is to let people know what is happening.

The following patches are in:

  git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-2.6-trace.git

    branch: rfc/tracing/filter

Steven Rostedt (12):
      tracing/filter: Have no filter return a match
      tracing/filter: Move OR and AND logic out of fn() method
      tracing/filter: Dynamically allocate preds
      tracing/filter: Call synchronize_sched() just once for system filters
      tracing/filter: Allocate the preds in an array
      tracing/filter: Free pred array on disabling of filter
      tracing/filter: Use a tree instead of stack for filter_match_preds()
      tracing/filter: Optimize short ciruit check
      tracing/filter: Check the created pred tree
      tracing/filter: Optimize filter by folding the tree
      tracing/filter: Move MAX_FILTER_PRED to local tracing directory
      tracing/filter: Increase the max preds to 2^14

----
 include/linux/ftrace_event.h       |    1 -
 kernel/trace/trace.h               |   38 ++-
 kernel/trace/trace_events_filter.c |  751 ++++++++++++++++++++++++++++++-----
 3 files changed, 675 insertions(+), 115 deletions(-)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/