You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by as...@apache.org on 2018/12/11 19:24:49 UTC
qpid-proton git commit: PROTON-1984: [c] Avoid O(n^2) complexity in
pn_data_inspect
Repository: qpid-proton
Updated Branches:
refs/heads/master 3b1edb510 -> 58ec2b1e5
PROTON-1984: [c] Avoid O(n^2) complexity in pn_data_inspect
Project: http://git-wip-us.apache.org/repos/asf/qpid-proton/repo
Commit: http://git-wip-us.apache.org/repos/asf/qpid-proton/commit/58ec2b1e
Tree: http://git-wip-us.apache.org/repos/asf/qpid-proton/tree/58ec2b1e
Diff: http://git-wip-us.apache.org/repos/asf/qpid-proton/diff/58ec2b1e
Branch: refs/heads/master
Commit: 58ec2b1e54d00fce4a07b7c3c6de2b504b2525ee
Parents: 3b1edb5
Author: Andrew Stitcher <as...@apache.org>
Authored: Tue Dec 11 14:17:52 2018 -0500
Committer: Andrew Stitcher <as...@apache.org>
Committed: Tue Dec 11 14:24:12 2018 -0500
----------------------------------------------------------------------
c/src/core/codec.c | 44 ++++++++-----------
c/src/core/data.h | 4 +-
c/src/core/encoder.c | 6 ++-
.../crash/5691758789263360 | Bin 0 -> 291 bytes
4 files changed, 24 insertions(+), 30 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/codec.c
----------------------------------------------------------------------
diff --git a/c/src/core/codec.c b/c/src/core/codec.c
index 37165f5..1a01bb2 100644
--- a/c/src/core/codec.c
+++ b/c/src/core/codec.c
@@ -111,16 +111,6 @@ static const pn_fields_t *pni_node_fields(pn_data_t *data, pni_node_t *node)
}
}
-static int pni_node_index(pn_data_t *data, pni_node_t *node)
-{
- int count = 0;
- while (node) {
- node = pn_data_node(data, node->prev);
- count++;
- }
- return count - 1;
-}
-
int pni_inspect_atom(pn_atom_t *atom, pn_string_t *str)
{
switch (atom->type) {
@@ -247,16 +237,16 @@ int pni_inspect_atom(pn_atom_t *atom, pn_string_t *str)
}
}
-int pni_inspect_enter(void *ctx, pn_data_t *data, pni_node_t *node)
+int pni_inspect_enter(void *ctx, pn_data_t *data, pni_nid_t index)
{
pn_string_t *str = (pn_string_t *) ctx;
+ pni_node_t *node = pn_data_node(data, index);
pn_atom_t *atom = (pn_atom_t *) &node->atom;
pni_node_t *parent = pn_data_node(data, node->parent);
const pn_fields_t *fields = pni_node_fields(data, parent);
pni_node_t *grandparent = parent ? pn_data_node(data, parent->parent) : NULL;
const pn_fields_t *grandfields = pni_node_fields(data, grandparent);
- int index = pni_node_index(data, node);
int err;
@@ -310,9 +300,10 @@ pni_node_t *pni_next_nonnull(pn_data_t *data, pni_node_t *node)
return NULL;
}
-int pni_inspect_exit(void *ctx, pn_data_t *data, pni_node_t *node)
+int pni_inspect_exit(void *ctx, pn_data_t *data, pni_nid_t index)
{
pn_string_t *str = (pn_string_t *) ctx;
+ pni_node_t *node = pn_data_node(data, index);
pni_node_t *parent = pn_data_node(data, node->parent);
pni_node_t *grandparent = parent ? pn_data_node(data, parent->parent) : NULL;
const pn_fields_t *grandfields = pni_node_fields(data, grandparent);
@@ -335,7 +326,6 @@ int pni_inspect_exit(void *ctx, pn_data_t *data, pni_node_t *node)
if (!grandfields || node->atom.type != PN_NULL) {
if (next) {
- int index = pni_node_index(data, node);
if (parent && parent->atom.type == PN_MAP && (index % 2) == 0) {
err = pn_string_addf(str, "=");
} else if (parent && parent->atom.type == PN_DESCRIBED && index == 0) {
@@ -1323,40 +1313,42 @@ bool pn_data_prev(pn_data_t *data)
}
int pni_data_traverse(pn_data_t *data,
- int (*enter)(void *ctx, pn_data_t *data, pni_node_t *node),
- int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
+ int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
+ int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
void *ctx)
{
- pni_node_t *node = data->size ? pn_data_node(data, 1) : NULL;
- while (node) {
- pni_node_t *parent = pn_data_node(data, node->parent);
+ pni_nid_t index = data->size ? 1 : 0;
+ while (index!=0) {
+ pni_node_t *node = pn_data_node(data, index);
- int err = enter(ctx, data, node);
+ int err = enter(ctx, data, index);
if (err) return err;
size_t next = 0;
if (node->down) {
next = node->down;
} else if (node->next) {
- err = exit(ctx, data, node);
+ err = exit(ctx, data, index);
if (err) return err;
next = node->next;
} else {
- err = exit(ctx, data, node);
+ err = exit(ctx, data, index);
if (err) return err;
- while (parent) {
- err = exit(ctx, data, parent);
+ pni_nid_t parenti = node->parent;
+ while (parenti) {
+ err = exit(ctx, data, parenti);
if (err) return err;
+ pni_node_t *parent = pn_data_node(data, parenti);
if (parent->next) {
next = parent->next;
break;
} else {
- parent = pn_data_node(data, parent->parent);
+ parenti = parent->parent;
}
}
}
- node = pn_data_node(data, next);
+ index = next;
}
return 0;
http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/data.h
----------------------------------------------------------------------
diff --git a/c/src/core/data.h b/c/src/core/data.h
index 94dc7d6..454ec55 100644
--- a/c/src/core/data.h
+++ b/c/src/core/data.h
@@ -68,8 +68,8 @@ static inline pni_node_t * pn_data_node(pn_data_t *data, pni_nid_t nd)
}
int pni_data_traverse(pn_data_t *data,
- int (*enter)(void *ctx, pn_data_t *data, pni_node_t *node),
- int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
+ int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
+ int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
void *ctx);
#endif /* data.h */
http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/encoder.c
----------------------------------------------------------------------
diff --git a/c/src/core/encoder.c b/c/src/core/encoder.c
index 505db47..43afe43 100644
--- a/c/src/core/encoder.c
+++ b/c/src/core/encoder.c
@@ -254,9 +254,10 @@ typedef union {
double d;
} conv_t;
-static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_node_t *node)
+static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_nid_t index)
{
pn_encoder_t *encoder = (pn_encoder_t *) ctx;
+ pni_node_t *node = pn_data_node(data, index);
pni_node_t *parent = pn_data_node(data, node->parent);
pn_atom_t *atom = &node->atom;
uint8_t code;
@@ -344,9 +345,10 @@ static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_node_t *node)
#include <stdio.h>
-static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_node_t *node)
+static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_nid_t index)
{
pn_encoder_t *encoder = (pn_encoder_t *) ctx;
+ pni_node_t *node = pn_data_node(data, index);
char *pos;
// Special case 0 length list
http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360
----------------------------------------------------------------------
diff --git a/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360 b/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360
new file mode 100644
index 0000000..df239f6
Binary files /dev/null and b/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360 differ
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org