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 <astitc...@apache.org> Authored: Tue Dec 11 14:17:52 2018 -0500 Committer: Andrew Stitcher <astitc...@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-unsubscr...@qpid.apache.org For additional commands, e-mail: commits-h...@qpid.apache.org