| 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
| ||
|
Message-Id: <1296234783-17491-2-git-send-email-acme@infradead.org>
Date: Fri, 28 Jan 2011 15:13:00 -0200
From: Arnaldo Carvalho de Melo <acme@...radead.org>
To: Ingo Molnar <mingo@...e.hu>
Cc: linux-kernel@...r.kernel.org,
Masami Hiramatsu <masami.hiramatsu.pt@...achi.com>,
2nddept-manager@....hitachi.co.jp,
Franck Bui-Huu <fbuihuu@...il.com>,
Ingo Molnar <mingo@...e.hu>, Paul Mackerras <paulus@...ba.org>,
Peter Zijlstra <a.p.zijlstra@...llo.nl>,
Srikar Dronamraju <srikar@...ux.vnet.ibm.com>,
Steven Rostedt <rostedt@...dmis.org>,
Arnaldo Carvalho de Melo <acme@...hat.com>
Subject: [PATCH 1/4] perf tools: Add strfilter for general purpose string filter
From: Masami Hiramatsu <masami.hiramatsu.pt@...achi.com>
Add strfilter for general purpose string filter.
Every filter rules are descrived by glob matching pattern and '!' prefix
which means Logical NOT.
A strfilter consists of those filter rules connected with '&' and '|'.
A set of rules can be folded by using '(' and ')'.
It also accepts spaces around rules and those operators.
Format:
<rule> ::= <glob-exp> | "!" <rule> | <rule> <op> <rule> | "(" <rule> ")"
<op> ::= "&" | "|"
e.g.:
"(add* | del*) & *timer" filter rules pass strings which start with add
or del and end with timer.
This will be used by perf probe --filter.
Changes in V2:
- Fix to check result of strdup() and strfilter__alloc().
- Encapsulate and simplify interfaces as like regex(3).
Cc: 2nddept-manager@....hitachi.co.jp
Cc: Franck Bui-Huu <fbuihuu@...il.com>
Cc: Ingo Molnar <mingo@...e.hu>
Cc: Paul Mackerras <paulus@...ba.org>
Cc: Peter Zijlstra <a.p.zijlstra@...llo.nl>
Cc: Srikar Dronamraju <srikar@...ux.vnet.ibm.com>
Cc: Steven Rostedt <rostedt@...dmis.org>
LKML-Reference: <20110120141530.25915.12673.stgit@...236.sdl.hitachi.co.jp>
Signed-off-by: Masami Hiramatsu <masami.hiramatsu.pt@...achi.com>
Signed-off-by: Arnaldo Carvalho de Melo <acme@...hat.com>
---
tools/perf/Makefile | 2 +
tools/perf/util/strfilter.c | 200 +++++++++++++++++++++++++++++++++++++++++++
tools/perf/util/strfilter.h | 48 ++++++++++
3 files changed, 250 insertions(+), 0 deletions(-)
create mode 100644 tools/perf/util/strfilter.c
create mode 100644 tools/perf/util/strfilter.h
diff --git a/tools/perf/Makefile b/tools/perf/Makefile
index 638e8e1..eedcf95 100644
--- a/tools/perf/Makefile
+++ b/tools/perf/Makefile
@@ -417,6 +417,7 @@ LIB_H += util/help.h
LIB_H += util/session.h
LIB_H += util/strbuf.h
LIB_H += util/strlist.h
+LIB_H += util/strfilter.h
LIB_H += util/svghelper.h
LIB_H += util/run-command.h
LIB_H += util/sigchain.h
@@ -458,6 +459,7 @@ LIB_OBJS += $(OUTPUT)util/quote.o
LIB_OBJS += $(OUTPUT)util/strbuf.o
LIB_OBJS += $(OUTPUT)util/string.o
LIB_OBJS += $(OUTPUT)util/strlist.o
+LIB_OBJS += $(OUTPUT)util/strfilter.o
LIB_OBJS += $(OUTPUT)util/usage.o
LIB_OBJS += $(OUTPUT)util/wrapper.o
LIB_OBJS += $(OUTPUT)util/sigchain.o
diff --git a/tools/perf/util/strfilter.c b/tools/perf/util/strfilter.c
new file mode 100644
index 0000000..4064b7d
--- /dev/null
+++ b/tools/perf/util/strfilter.c
@@ -0,0 +1,200 @@
+#include <ctype.h>
+#include "util.h"
+#include "string.h"
+#include "strfilter.h"
+
+/* Operators */
+static const char *OP_and = "&"; /* Logical AND */
+static const char *OP_or = "|"; /* Logical OR */
+static const char *OP_not = "!"; /* Logical NOT */
+
+#define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
+#define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
+
+static void strfilter_node__delete(struct strfilter_node *self)
+{
+ if (self) {
+ if (self->p && !is_operator(*self->p))
+ free((char *)self->p);
+ strfilter_node__delete(self->l);
+ strfilter_node__delete(self->r);
+ free(self);
+ }
+}
+
+void strfilter__delete(struct strfilter *self)
+{
+ if (self) {
+ strfilter_node__delete(self->root);
+ free(self);
+ }
+}
+
+static const char *get_token(const char *s, const char **e)
+{
+ const char *p;
+
+ while (isspace(*s)) /* Skip spaces */
+ s++;
+
+ if (*s == '\0') {
+ p = s;
+ goto end;
+ }
+
+ p = s + 1;
+ if (!is_separator(*s)) {
+ /* End search */
+retry:
+ while (*p && !is_separator(*p) && !isspace(*p))
+ p++;
+ /* Escape and special case: '!' is also used in glob pattern */
+ if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
+ p++;
+ goto retry;
+ }
+ }
+end:
+ *e = p;
+ return s;
+}
+
+static struct strfilter_node *strfilter_node__alloc(const char *op,
+ struct strfilter_node *l,
+ struct strfilter_node *r)
+{
+ struct strfilter_node *ret = zalloc(sizeof(struct strfilter_node));
+
+ if (ret) {
+ ret->p = op;
+ ret->l = l;
+ ret->r = r;
+ }
+
+ return ret;
+}
+
+static struct strfilter_node *strfilter_node__new(const char *s,
+ const char **ep)
+{
+ struct strfilter_node root, *cur, *last_op;
+ const char *e;
+
+ if (!s)
+ return NULL;
+
+ memset(&root, 0, sizeof(root));
+ last_op = cur = &root;
+
+ s = get_token(s, &e);
+ while (*s != '\0' && *s != ')') {
+ switch (*s) {
+ case '&': /* Exchg last OP->r with AND */
+ if (!cur->r || !last_op->r)
+ goto error;
+ cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
+ if (!cur)
+ goto nomem;
+ last_op->r = cur;
+ last_op = cur;
+ break;
+ case '|': /* Exchg the root with OR */
+ if (!cur->r || !root.r)
+ goto error;
+ cur = strfilter_node__alloc(OP_or, root.r, NULL);
+ if (!cur)
+ goto nomem;
+ root.r = cur;
+ last_op = cur;
+ break;
+ case '!': /* Add NOT as a leaf node */
+ if (cur->r)
+ goto error;
+ cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
+ if (!cur->r)
+ goto nomem;
+ cur = cur->r;
+ break;
+ case '(': /* Recursively parses inside the parenthesis */
+ if (cur->r)
+ goto error;
+ cur->r = strfilter_node__new(s + 1, &s);
+ if (!s)
+ goto nomem;
+ if (!cur->r || *s != ')')
+ goto error;
+ e = s + 1;
+ break;
+ default:
+ if (cur->r)
+ goto error;
+ cur->r = strfilter_node__alloc(NULL, NULL, NULL);
+ if (!cur->r)
+ goto nomem;
+ cur->r->p = strndup(s, e - s);
+ if (!cur->r->p)
+ goto nomem;
+ }
+ s = get_token(e, &e);
+ }
+ if (!cur->r)
+ goto error;
+ *ep = s;
+ return root.r;
+nomem:
+ s = NULL;
+error:
+ *ep = s;
+ strfilter_node__delete(root.r);
+ return NULL;
+}
+
+/*
+ * Parse filter rule and return new strfilter.
+ * Return NULL if fail, and *ep == NULL if memory allocation failed.
+ */
+struct strfilter *strfilter__new(const char *rules, const char **err)
+{
+ struct strfilter *ret = zalloc(sizeof(struct strfilter));
+ const char *ep = NULL;
+
+ if (ret)
+ ret->root = strfilter_node__new(rules, &ep);
+
+ if (!ret || !ret->root || *ep != '\0') {
+ if (err)
+ *err = ep;
+ strfilter__delete(ret);
+ ret = NULL;
+ }
+
+ return ret;
+}
+
+static bool strfilter_node__compare(struct strfilter_node *self,
+ const char *str)
+{
+ if (!self || !self->p)
+ return false;
+
+ switch (*self->p) {
+ case '|': /* OR */
+ return strfilter_node__compare(self->l, str) ||
+ strfilter_node__compare(self->r, str);
+ case '&': /* AND */
+ return strfilter_node__compare(self->l, str) &&
+ strfilter_node__compare(self->r, str);
+ case '!': /* NOT */
+ return !strfilter_node__compare(self->r, str);
+ default:
+ return strglobmatch(str, self->p);
+ }
+}
+
+/* Return true if STR matches the filter rules */
+bool strfilter__compare(struct strfilter *self, const char *str)
+{
+ if (!self)
+ return false;
+ return strfilter_node__compare(self->root, str);
+}
diff --git a/tools/perf/util/strfilter.h b/tools/perf/util/strfilter.h
new file mode 100644
index 0000000..00f58a7
--- /dev/null
+++ b/tools/perf/util/strfilter.h
@@ -0,0 +1,48 @@
+#ifndef __PERF_STRFILTER_H
+#define __PERF_STRFILTER_H
+/* General purpose glob matching filter */
+
+#include <linux/list.h>
+#include <stdbool.h>
+
+/* A node of string filter */
+struct strfilter_node {
+ struct strfilter_node *l; /* Tree left branche (for &,|) */
+ struct strfilter_node *r; /* Tree right branche (for !,&,|) */
+ const char *p; /* Operator or rule */
+};
+
+/* String filter */
+struct strfilter {
+ struct strfilter_node *root;
+};
+
+/**
+ * strfilter__new - Create a new string filter
+ * @rules: Filter rule, which is a combination of glob expressions.
+ * @err: Pointer which points an error detected on @rules
+ *
+ * Parse @rules and return new strfilter. Return NULL if an error detected.
+ * In that case, *@err will indicate where it is detected, and *@err is NULL
+ * if a memory allocation is failed.
+ */
+struct strfilter *strfilter__new(const char *rules, const char **err);
+
+/**
+ * strfilter__compare - compare given string and a string filter
+ * @self: String filter
+ * @str: target string
+ *
+ * Compare @str and @self. Return true if the str match the rule
+ */
+bool strfilter__compare(struct strfilter *self, const char *str);
+
+/**
+ * strfilter__delete - delete a string filter
+ * @self: String filter to delete
+ *
+ * Delete @self.
+ */
+void strfilter__delete(struct strfilter *self);
+
+#endif
--
1.6.2.5
--
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/
Powered by blists - more mailing lists