HTRACE-209. Make span ID 128 bit to avoid collisions (cmccabe)
Project: http://git-wip-us.apache.org/repos/asf/incubator-htrace/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-htrace/commit/a06159b2 Tree: http://git-wip-us.apache.org/repos/asf/incubator-htrace/tree/a06159b2 Diff: http://git-wip-us.apache.org/repos/asf/incubator-htrace/diff/a06159b2 Branch: refs/heads/master Commit: a06159b278259f0d4a39f92737c460ed217efcf0 Parents: 33f71ec Author: Colin Patrick Mccabe <[email protected]> Authored: Thu Jul 30 11:40:24 2015 -0700 Committer: Colin Patrick Mccabe <[email protected]> Committed: Fri Jul 31 12:50:01 2015 -0700 ---------------------------------------------------------------------- htrace-c/src/CMakeLists.txt | 5 +- htrace-c/src/core/htrace.h | 10 - htrace-c/src/core/htrace.hpp | 4 - htrace-c/src/core/scope.c | 31 ++- htrace-c/src/core/scope.h | 13 ++ htrace-c/src/core/span.c | 66 +++--- htrace-c/src/core/span.h | 10 +- htrace-c/src/core/span_id.c | 221 +++++++++++++++++++ htrace-c/src/core/span_id.h | 149 +++++++++++++ htrace-c/src/test/cmp_util-unit.c | 20 +- htrace-c/src/test/linkage-unit.c | 1 - htrace-c/src/test/rtest.c | 22 +- htrace-c/src/test/rtestpp.cc | 15 +- htrace-c/src/test/span-unit.c | 160 +++----------- htrace-c/src/test/span_id-unit.c | 104 +++++++++ htrace-c/src/test/span_table.c | 3 +- htrace-c/src/test/span_util-unit.c | 74 ------- htrace-c/src/test/span_util.c | 99 +++------ .../src/main/java/org/apache/htrace/Span.java | 23 +- .../src/main/java/org/apache/htrace/SpanId.java | 149 +++++++++++++ .../src/main/java/org/apache/htrace/Trace.java | 11 +- .../main/java/org/apache/htrace/TraceInfo.java | 38 ---- .../main/java/org/apache/htrace/TraceTree.java | 191 ---------------- .../src/main/java/org/apache/htrace/Tracer.java | 6 +- .../java/org/apache/htrace/impl/MilliSpan.java | 75 ++----- .../java/org/apache/htrace/TestBadClient.java | 2 - .../test/java/org/apache/htrace/TestHTrace.java | 15 +- .../test/java/org/apache/htrace/TestSpanId.java | 72 ++++++ .../test/java/org/apache/htrace/TraceGraph.java | 179 +++++++++++++++ .../org/apache/htrace/impl/TestMilliSpan.java | 33 ++- .../apache/htrace/impl/FlumeSpanReceiver.java | 5 +- .../htrace/impl/TestFlumeSpanReceiver.java | 4 +- .../apache/htrace/impl/HBaseSpanReceiver.java | 10 +- .../htrace/impl/TestHBaseSpanReceiver.java | 28 +-- .../go/src/org/apache/htrace/client/client.go | 10 +- .../go/src/org/apache/htrace/common/span.go | 101 ++++++++- .../src/org/apache/htrace/common/span_test.go | 62 +++++- .../src/org/apache/htrace/common/test_util.go | 9 + .../go/src/org/apache/htrace/htrace/cmd.go | 14 +- .../src/org/apache/htrace/htrace/file_test.go | 15 +- .../go/src/org/apache/htrace/htrace/graph.go | 18 +- .../src/org/apache/htrace/htrace/graph_test.go | 24 +- .../org/apache/htrace/htraced/client_test.go | 2 +- .../src/org/apache/htrace/htraced/datastore.go | 218 +++++++----------- .../org/apache/htrace/htraced/datastore_test.go | 33 ++- .../go/src/org/apache/htrace/htraced/hrpc.go | 4 + .../go/src/org/apache/htrace/htraced/rest.go | 7 +- .../go/src/org/apache/htrace/test/random.go | 12 +- .../go/src/org/apache/htrace/test/util.go | 33 --- .../htrace/impl/TestHTracedRESTReceiver.java | 11 +- htrace-webapp/src/main/web/app/span.js | 10 +- htrace-webapp/src/main/web/app/string.js | 12 +- .../htrace/zipkin/HTraceToZipkinConverter.java | 6 +- .../htrace/TestHTraceSpanToZipkinSpan.java | 35 +-- src/main/site/markdown/index.md | 17 +- 55 files changed, 1475 insertions(+), 1026 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/htrace-c/src/CMakeLists.txt b/htrace-c/src/CMakeLists.txt index c34a7c2..20a0d51 100644 --- a/htrace-c/src/CMakeLists.txt +++ b/htrace-c/src/CMakeLists.txt @@ -75,6 +75,7 @@ set(SRC_ALL core/htracer.c core/scope.c core/span.c + core/span_id.c receiver/hrpc.c receiver/htraced.c receiver/local_file.c @@ -198,8 +199,8 @@ add_utest(span-unit test/span-unit.c ) -add_utest(span_util-unit - test/span_util-unit.c +add_utest(span_id-unit + test/span_id-unit.c ) add_utest(string-unit http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/htrace.h ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/htrace.h b/htrace-c/src/core/htrace.h index e7dc93b..03c02bb 100644 --- a/htrace-c/src/core/htrace.h +++ b/htrace-c/src/core/htrace.h @@ -329,16 +329,6 @@ extern "C" { struct htrace_span *span); /** - * Get the span id of an HTrace scope. - * - * @param scope The trace scope, or NULL. - * - * @return The span ID of the trace span, or 0 if there is no trace - * span inside the scope, or if NULL was passed. - */ - uint64_t htrace_scope_get_span_id(const struct htrace_scope *scope); - - /** * Close a trace scope. * * This must be called from the same thread that the trace scope was created http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/htrace.hpp ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/htrace.hpp b/htrace-c/src/core/htrace.hpp index e4a87cb..0378c57 100644 --- a/htrace-c/src/core/htrace.hpp +++ b/htrace-c/src/core/htrace.hpp @@ -221,10 +221,6 @@ namespace htrace { scope_ = NULL; } - uint64_t GetSpanId() { - return htrace_scope_get_span_id(scope_); - } - private: friend class Tracer; Scope(htrace::Scope &other); // Can't copy http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/scope.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/scope.c b/htrace-c/src/core/scope.c index 93008cb..442bf52 100644 --- a/htrace-c/src/core/scope.c +++ b/htrace-c/src/core/scope.c @@ -43,7 +43,7 @@ struct htrace_scope* htrace_start_span(struct htracer *tracer, { struct htrace_scope *cur_scope, *scope = NULL, *pscope; struct htrace_span *span = NULL; - uint64_t span_id; + struct htrace_span_id span_id; // Validate the description string. This ensures that it doesn't have // anything silly in it like embedded double quotes, backslashes, or control @@ -54,15 +54,16 @@ struct htrace_scope* htrace_start_span(struct htracer *tracer, return NULL; } cur_scope = htracer_cur_scope(tracer); - if (!cur_scope) { + if ((!cur_scope) || (!cur_scope->span)) { if (!sampler->ty->next(sampler)) { return NULL; } + htrace_span_id_generate(&span_id, tracer->rnd, NULL); + } else { + htrace_span_id_generate(&span_id, tracer->rnd, + &cur_scope->span->span_id); } - do { - span_id = random_u64(tracer->rnd); - } while (span_id == 0); - span = htrace_span_alloc(desc, now_ms(tracer->lg), span_id); + span = htrace_span_alloc(desc, now_ms(tracer->lg), &span_id); if (!span) { htrace_log(tracer->lg, "htrace_span_alloc(desc=%s): OOM\n", desc); return NULL; @@ -112,12 +113,14 @@ struct htrace_scope* htrace_restart_span(struct htracer *tracer, struct htrace_span *span) { struct htrace_scope *cur_scope, *scope = NULL; + char buf[HTRACE_SPAN_ID_STRING_LENGTH + 1]; scope = malloc(sizeof(*scope)); if (!scope) { + htrace_span_id_to_str(&span->span_id, buf, sizeof(buf)); + htrace_log(tracer->lg, "htrace_start_span(desc=%s, parent_id=%s" + "): OOM\n", span->desc, buf); htrace_span_free(span); - htrace_log(tracer->lg, "htrace_start_span(desc=%s, parent_id=%016"PRIx64 - "): OOM\n", span->desc, span->span_id); return NULL; } scope->tracer = tracer; @@ -132,15 +135,21 @@ struct htrace_scope* htrace_restart_span(struct htracer *tracer, return scope; } -uint64_t htrace_scope_get_span_id(const struct htrace_scope *scope) +void htrace_scope_get_span_id(const struct htrace_scope *scope, + struct htrace_span_id *id) { struct htrace_span *span; if (!scope) { - return 0; + htrace_span_id_clear(id); + return; } span = scope->span; - return span ? span->span_id : 0; + if (!span) { + htrace_span_id_clear(id); + return; + } + htrace_span_id_copy(id, &span->span_id); } void htrace_scope_close(struct htrace_scope *scope) http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/scope.h ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/scope.h b/htrace-c/src/core/scope.h index f76cd42..9f00b13 100644 --- a/htrace-c/src/core/scope.h +++ b/htrace-c/src/core/scope.h @@ -27,6 +27,8 @@ * This is an internal header, not intended for external use. */ +struct htrace_span_id; + #include <stdint.h> /** @@ -53,6 +55,17 @@ struct htrace_scope { struct htrace_span *span; }; +/** + * Get the span id of an HTrace scope. + * + * @param scope The trace scope, or NULL. + * @param id (out param) The htrace span ID object to modify. + * It will be set to the invalid span ID if the scope + * is null or has no span. + */ +void htrace_scope_get_span_id(const struct htrace_scope *scope, + struct htrace_span_id *id); + #endif // vim: ts=4:sw=4:et http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/span.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/span.c b/htrace-c/src/core/span.c index b82f4f1..44f4e6c 100644 --- a/htrace-c/src/core/span.c +++ b/htrace-c/src/core/span.c @@ -38,7 +38,7 @@ */ struct htrace_span *htrace_span_alloc(const char *desc, - uint64_t begin_ms, uint64_t span_id) + uint64_t begin_ms, struct htrace_span_id *span_id) { struct htrace_span *span; @@ -53,10 +53,10 @@ struct htrace_span *htrace_span_alloc(const char *desc, } span->begin_ms = begin_ms; span->end_ms = 0; - span->span_id = span_id; + htrace_span_id_copy(&span->span_id, span_id); span->trid = NULL; span->num_parents = 0; - span->parent.single = 0; + htrace_span_id_clear(&span->parent.single); span->parent.list = NULL; return span; } @@ -74,35 +74,26 @@ void htrace_span_free(struct htrace_span *span) free(span); } -static int compare_spanids(const void *va, const void *vb) -{ - uint64_t a = *((uint64_t*)va); - uint64_t b = *((uint64_t*)vb); - if (a < b) { - return -1; - } else if (a > b) { - return 1; - } else { - return 0; - } -} +typedef int (*qsort_fn_t)(const void *, const void *); void htrace_span_sort_and_dedupe_parents(struct htrace_span *span) { int i, j, num_parents = span->num_parents; - uint64_t prev; + struct htrace_span_id prev; if (num_parents <= 1) { return; } - qsort(span->parent.list, num_parents, sizeof(uint64_t), compare_spanids); + qsort(span->parent.list, num_parents, sizeof(struct htrace_span_id), + (qsort_fn_t)htrace_span_id_compare); prev = span->parent.list[0]; + htrace_span_id_copy(&prev, &span->parent.list[0]); j = 1; for (i = 1; i < num_parents; i++) { - uint64_t id = span->parent.list[i]; - if (id != prev) { - span->parent.list[j++] = span->parent.list[i]; - prev = id; + if (htrace_span_id_compare(&prev, span->parent.list + i) != 0) { + htrace_span_id_copy(&prev, span->parent.list + i); + htrace_span_id_copy(span->parent.list + j, span->parent.list + i); + j++; } } span->num_parents = j; @@ -114,7 +105,8 @@ void htrace_span_sort_and_dedupe_parents(struct htrace_span *span) } else if (j != num_parents) { // After deduplication, there are now fewer entries. Use realloc to // shrink the size of our dynamic allocation if possible. - uint64_t *nlist = realloc(span->parent.list, sizeof(uint64_t) * j); + struct htrace_span_id *nlist = + realloc(span->parent.list, sizeof(struct htrace_span_id) * j); if (nlist) { span->parent.list = nlist; } @@ -141,13 +133,15 @@ static int span_json_sprintf_impl(const struct htrace_span *span, { int num_parents, i, ret = 0; const char *prefix = ""; + char sbuf[HTRACE_SPAN_ID_STRING_LENGTH + 1]; // Note that we have validated the description and process ID strings to // make sure they don't contain anything evil. So we don't need to escape // them here. - ret += fwdprintf(&buf, &max, "{\"s\":\"%016" PRIx64 "\",\"b\":%" PRId64 - ",\"e\":%" PRId64",", span->span_id, span->begin_ms, + htrace_span_id_to_str(&span->span_id, sbuf, sizeof(sbuf)); + ret += fwdprintf(&buf, &max, "{\"a\":\"%s\",\"b\":%" PRId64 + ",\"e\":%" PRId64",", sbuf, span->begin_ms, span->end_ms); if (span->desc[0]) { ret += fwdprintf(&buf, &max, "\"d\":\"%s\",", span->desc); @@ -159,13 +153,13 @@ static int span_json_sprintf_impl(const struct htrace_span *span, if (num_parents == 0) { ret += fwdprintf(&buf, &max, "\"p\":[]"); } else if (num_parents == 1) { - ret += fwdprintf(&buf, &max, "\"p\":[\"%016"PRIx64"\"]", - span->parent.single); + htrace_span_id_to_str(&span->parent.single, sbuf, sizeof(sbuf)); + ret += fwdprintf(&buf, &max, "\"p\":[\"%s\"]", sbuf); } else if (num_parents > 1) { ret += fwdprintf(&buf, &max, "\"p\":["); for (i = 0; i < num_parents; i++) { - ret += fwdprintf(&buf, &max, "%s\"%016" PRIx64 "\"", prefix, - span->parent.list[i]); + htrace_span_id_to_str(span->parent.list + i, sbuf, sizeof(sbuf)); + ret += fwdprintf(&buf, &max, "%s\"%s\"", prefix, sbuf); prefix = ","; } ret += fwdprintf(&buf, &max, "]"); @@ -205,6 +199,12 @@ int span_write_msgpack(const struct htrace_span *span, cmp_ctx_t *ctx) if (!cmp_write_map16(ctx, map_size)) { return 0; } + if (!cmp_write_fixstr(ctx, "a", 1)) { + return 0; + } + if (!htrace_span_id_write_msgpack(&span->span_id, ctx)) { + return 0; + } if (!cmp_write_fixstr(ctx, "d", 1)) { return 0; } @@ -223,12 +223,6 @@ int span_write_msgpack(const struct htrace_span *span, cmp_ctx_t *ctx) if (!cmp_write_u64(ctx, span->end_ms)) { return 0; } - if (!cmp_write_fixstr(ctx, "s", 1)) { - return 0; - } - if (!cmp_write_u64(ctx, span->span_id)) { - return 0; - } if (span->trid) { if (!cmp_write_fixstr(ctx, "r", 1)) { return 0; @@ -245,12 +239,12 @@ int span_write_msgpack(const struct htrace_span *span, cmp_ctx_t *ctx) return 0; } if (num_parents == 1) { - if (!cmp_write_u64(ctx, span->parent.single)) { + if (!htrace_span_id_write_msgpack(&span->parent.single, ctx)) { return 0; } } else { for (i = 0; i < num_parents; i++) { - if (!cmp_write_u64(ctx, span->parent.list[i])) { + if (!htrace_span_id_write_msgpack(span->parent.list + i, ctx)) { return 0; } } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/span.h ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/span.h b/htrace-c/src/core/span.h index 4d28e75..d6fbeb5 100644 --- a/htrace-c/src/core/span.h +++ b/htrace-c/src/core/span.h @@ -27,6 +27,8 @@ * This is an internal header, not intended for external use. */ +#include "core/span_id.h" + #include <stdint.h> struct cmp_ctx_s; @@ -52,7 +54,7 @@ struct htrace_span { /** * The span id. */ - uint64_t span_id; + struct htrace_span_id span_id; /** * The tracer ID of this trace scope. @@ -69,13 +71,13 @@ struct htrace_span { /** * If there is 1 parent, this is the parent ID. */ - uint64_t single; + struct htrace_span_id single; /** * If there are multiple parents, this is a pointer to a dynamically * allocated array of parent IDs. */ - uint64_t *list; + struct htrace_span_id *list; } parent; }; @@ -89,7 +91,7 @@ struct htrace_span { * @return NULL on OOM; the span otherwise. */ struct htrace_span *htrace_span_alloc(const char *desc, - uint64_t begin_ms, uint64_t span_id); + uint64_t begin_ms, struct htrace_span_id *span_id); /** * Free the memory associated with an htrace span. http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/span_id.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/span_id.c b/htrace-c/src/core/span_id.c new file mode 100644 index 0000000..7ea23eb --- /dev/null +++ b/htrace-c/src/core/span_id.c @@ -0,0 +1,221 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "core/span_id.h" +#include "util/cmp.h" +#include "util/log.h" +#include "util/rand.h" +#include "util/string.h" +#include "util/time.h" + +#include <errno.h> +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/** + * @file span_id.c + * + * Implementation of HTrace span IDs. + * + * Span IDs are 128 bits in total. The upper 64 bits of a span ID is the same + * as the upper 64 bits of the first parent span, if there is one. The lower 64 + * bits are always random. + */ + +const struct htrace_span_id INVALID_SPAN_ID; + +static uint64_t parse_hex_range(const char *str, int start, int end, + char *err, size_t err_len) +{ + char *endptr = NULL; + uint64_t ret; + char substr[HTRACE_SPAN_ID_STRING_LENGTH + 1]; + + err[0] = '\0'; + if (end - start >= HTRACE_SPAN_ID_STRING_LENGTH) { + snprintf(err, err_len, "parse_hex_range buffer too short."); + return 0; + } + memcpy(substr, str + start, end - start); + substr[end - start] = '\0'; + errno = 0; + ret = strtoull(substr, &endptr, 16); + if (errno) { + int e = errno; + snprintf(err, err_len, "parse_hex_range error: %s", terror(e)); + return 0; + } + while (1) { + char c = *endptr; + if (c == '\0') { + break; + } + if ((c != ' ') || (c != '\t')) { + snprintf(err, err_len, "parse_hex_range error: garbage at end " + "of string."); + return 0; + } + endptr++; + } + return ret; +} + +void htrace_span_id_parse(struct htrace_span_id *id, const char *str, + char *err, size_t err_len) +{ + size_t len; + + err[0] = '\0'; + len = strlen(str); + if (len < HTRACE_SPAN_ID_STRING_LENGTH) { + snprintf(err, err_len, "too short: must be %d characters.", + HTRACE_SPAN_ID_STRING_LENGTH); + return; + } + id->high = (parse_hex_range(str, 0, 8, err, err_len) << 32); + if (err[0]) { + return; + } + id->high |= (parse_hex_range(str, 8, 16, err, err_len)); + if (err[0]) { + return; + } + id->low = (parse_hex_range(str, 16, 24, err, err_len) << 32); + if (err[0]) { + return; + } + id->low |= (parse_hex_range(str, 24, 32, err, err_len)); + if (err[0]) { + return; + } +} + +int htrace_span_id_to_str(const struct htrace_span_id *id, + char *str, size_t len) +{ + int res = snprintf(str, len, + "%08"PRIx32"%08"PRIx32"%08"PRIx32"%08"PRIx32, + (uint32_t)(0xffffffffUL & (id->high >> 32)), + (uint32_t)(0xffffffffUL & id->high), + (uint32_t)(0xffffffffUL & (id->low >> 32)), + (uint32_t)(0xffffffffUL & id->low)); + return (res == HTRACE_SPAN_ID_STRING_LENGTH); +} + +void htrace_span_id_copy(struct htrace_span_id *dst, + const struct htrace_span_id *src) +{ + memmove(dst, src, sizeof(*dst)); +} + +int htrace_span_id_write_msgpack(const struct htrace_span_id *id, + struct cmp_ctx_s *ctx) +{ + uint8_t buf[HTRACE_SPAN_ID_NUM_BYTES]; + buf[0] = (id->high >> 56) & 0xff; + buf[1] = (id->high >> 48) & 0xff; + buf[2] = (id->high >> 40) & 0xff; + buf[3] = (id->high >> 32) & 0xff; + buf[4] = (id->high >> 24) & 0xff; + buf[5] = (id->high >> 16) & 0xff; + buf[6] = (id->high >> 8) & 0xff; + buf[7] = (id->high >> 0) & 0xff; + buf[8] = (id->low >> 56) & 0xff; + buf[9] = (id->low >> 48) & 0xff; + buf[10] = (id->low >> 40) & 0xff; + buf[11] = (id->low >> 32) & 0xff; + buf[12] = (id->low >> 24) & 0xff; + buf[13] = (id->low >> 16) & 0xff; + buf[14] = (id->low >> 8) & 0xff; + buf[15] = (id->low >> 0) & 0xff; + return cmp_write_bin(ctx, buf, HTRACE_SPAN_ID_NUM_BYTES); +} + +int htrace_span_id_read_msgpack(struct htrace_span_id *id, + struct cmp_ctx_s *ctx) +{ + uint8_t buf[HTRACE_SPAN_ID_NUM_BYTES]; + uint32_t size = HTRACE_SPAN_ID_NUM_BYTES; + + if (!cmp_read_bin(ctx, buf, &size)) { + return 0; + } + if (size != HTRACE_SPAN_ID_NUM_BYTES) { + return 0; + } + id->high = + (((uint64_t)buf[0]) << 56) | + (((uint64_t)buf[1]) << 48) | + (((uint64_t)buf[2]) << 40) | + (((uint64_t)buf[3]) << 32) | + (((uint64_t)buf[4]) << 24) | + (((uint64_t)buf[5]) << 16) | + (((uint64_t)buf[6]) << 8) | + (((uint64_t)buf[7]) << 0); + id->low = + (((uint64_t)buf[8]) << 56) | + (((uint64_t)buf[9]) << 48) | + (((uint64_t)buf[10]) << 40) | + (((uint64_t)buf[11]) << 32) | + (((uint64_t)buf[12]) << 24) | + (((uint64_t)buf[13]) << 16) | + (((uint64_t)buf[14]) << 8) | + (((uint64_t)buf[15]) << 0); + return 1; +} + +void htrace_span_id_generate(struct htrace_span_id *id, struct random_src *rnd, + const struct htrace_span_id *parent) +{ + if (parent) { + id->high = parent->high; + } else { + do { + id->high = random_u64(rnd); + } while (id->high == 0); + } + do { + id->low = random_u64(rnd); + } while (id->low == 0); +} + +void htrace_span_id_clear(struct htrace_span_id *id) +{ + memset(id, 0, sizeof(*id)); +} + +int htrace_span_id_compare(const struct htrace_span_id *a, + const struct htrace_span_id *b) +{ + if (a->high < b->high) { + return -1; + } else if (a->high > b->high) { + return 1; + } else if (a->low < b->low) { + return -1; + } else if (a->low > b->low) { + return 1; + } else { + return 0; + } +} + +// vim:ts=4:sw=4:et http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/core/span_id.h ---------------------------------------------------------------------- diff --git a/htrace-c/src/core/span_id.h b/htrace-c/src/core/span_id.h new file mode 100644 index 0000000..af2e725 --- /dev/null +++ b/htrace-c/src/core/span_id.h @@ -0,0 +1,149 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef APACHE_HTRACE_SPAN_ID_H +#define APACHE_HTRACE_SPAN_ID_H + +/** + * @file span_id.h + * + * Functions related to HTrace span IDs. + * + * This is an internal header, not intended for external use. + */ + +#include <stdint.h> // for uint64_t +#include <unistd.h> // for size_t + +struct cmp_ctx_s; +struct random_src; + +/** + * Length of an HTrace span ID in hexadecimal string form. + */ +#define HTRACE_SPAN_ID_STRING_LENGTH 32 + +/** + * The number of bytes in the HTrace span ID + */ +#define HTRACE_SPAN_ID_NUM_BYTES 16 + +/** + * The invalid span ID, which is all zeroes. + */ +extern const struct htrace_span_id INVALID_SPAN_ID; + +/** + * The HTrace span id. + */ +struct htrace_span_id { + uint64_t high; + uint64_t low; +}; + +/** + * Parse a string containing an HTrace span ID. + * + * @param id The HTrace span ID to fill in. + * @param str The string to parse. + * + */ +void htrace_span_id_parse(struct htrace_span_id *id, const char *str, + char *err, size_t err_len); + +/** + * Write an HTrace span ID to a string. + * + * @param id The HTrace span ID. + * @param str Where to put the string. + * @param len The length of the string buffer. + * @param err The error buffer to be set on failure. + * @param err_len Length of the error buffer. + * + * @return 1 on success; 0 if the length was not long enough, or + * there was an internal snprintf error. + */ +int htrace_span_id_to_str(const struct htrace_span_id *id, + char *str, size_t len); + +/** + * Copy an htrace span ID. + * + * dst and src can be the same. + * + * @param dst The destination span ID. + * @param src The source span ID. + */ +void htrace_span_id_copy(struct htrace_span_id *dst, + const struct htrace_span_id *src); + +/** + * Write this span ID to the provided CMP context. + * + * @param span The span. + * @param ctx The CMP context. + * + * @return 0 on failure; 1 on success. + */ +int htrace_span_id_write_msgpack(const struct htrace_span_id *id, + struct cmp_ctx_s *ctx); + +/** + * Read this span ID from the provided CMP context. + * + * @param span The span. + * @param ctx The CMP context. + * + * @return 0 on failure; 1 on success. + */ +int htrace_span_id_read_msgpack(struct htrace_span_id *id, + struct cmp_ctx_s *ctx); + +/** + * Generate a new span ID. + * + * @param id The span ID to alter. + * @param rnd The random source. + * @param parent The parent span ID, or null if there is none. + */ +void htrace_span_id_generate(struct htrace_span_id *id, struct random_src *rnd, + const struct htrace_span_id *parent); + +/** + * Set a span ID to the invalid span ID by clearing it. + * + * @param id The span ID to clear. + */ +void htrace_span_id_clear(struct htrace_span_id *id); + +/** + * Compare two span IDs. + * + * @param a The first span ID. + * @param b The second span ID. + * + * @return A number less than 0 if the first span ID is less; + * A number greater than 0 if the first span ID is greater; + * 0 if the span IDs are equal. + */ +int htrace_span_id_compare(const struct htrace_span_id *a, + const struct htrace_span_id *b); + +#endif + +// vim: ts=4:sw=4:et http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/cmp_util-unit.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/cmp_util-unit.c b/htrace-c/src/test/cmp_util-unit.c index 4675ca8..d272cae 100644 --- a/htrace-c/src/test/cmp_util-unit.c +++ b/htrace-c/src/test/cmp_util-unit.c @@ -39,27 +39,33 @@ static struct htrace_span **setup_test_spans(void) spans[0]->desc = xstrdup("FirstSpan"); spans[0]->begin_ms = 1927; spans[0]->end_ms = 2000; - spans[0]->span_id = 1; + spans[0]->span_id.high = 0xface; + spans[0]->span_id.low = 1; spans[1] = xcalloc(sizeof(struct htrace_span)); spans[1]->desc = xstrdup("SecondSpan"); spans[1]->begin_ms = 1950; spans[1]->end_ms = 2000; - spans[1]->span_id = 0xffffffffffffffffULL; + spans[1]->span_id.high = 0xface; + spans[1]->span_id.low = 2; spans[1]->trid = xstrdup("SecondSpanProc"); spans[1]->num_parents = 1; - spans[1]->parent.single = 1; + spans[1]->parent.single.high = 0xface; + spans[1]->parent.single.low = 1; spans[2] = xcalloc(sizeof(struct htrace_span)); spans[2]->desc = xstrdup("ThirdSpan"); spans[2]->begin_ms = 1969; spans[2]->end_ms = 1997; - spans[2]->span_id = 0xcfcfcfcfcfcfcfcfULL; + spans[1]->span_id.high = 0xface; + spans[1]->span_id.low = 0xcfcfcfcfcfcfcfcfULL; spans[2]->trid = xstrdup("ThirdSpanProc"); spans[2]->num_parents = 2; - spans[2]->parent.list = xcalloc(sizeof(uint64_t) * 2); - spans[2]->parent.list[0] = 1; - spans[2]->parent.list[1] = 0xffffffffffffffffULL; + spans[2]->parent.list = xcalloc(sizeof(struct htrace_span_id) * 2); + spans[2]->parent.list[0].high = 0xface; + spans[2]->parent.list[0].low = 1; + spans[2]->parent.list[1].high = 0xface; + spans[2]->parent.list[1].low = 2; return spans; } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/linkage-unit.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/linkage-unit.c b/htrace-c/src/test/linkage-unit.c index f3c5eba..bba73e1 100644 --- a/htrace-c/src/test/linkage-unit.c +++ b/htrace-c/src/test/linkage-unit.c @@ -45,7 +45,6 @@ static const char * const PUBLIC_SYMS[] = { "htrace_sampler_to_str", "htrace_scope_close", "htrace_scope_detach", - "htrace_scope_get_span_id", "htrace_start_span", "htracer_create", "htracer_free", http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/rtest.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/rtest.c b/htrace-c/src/test/rtest.c index ccae241..933315d 100644 --- a/htrace-c/src/test/rtest.c +++ b/htrace-c/src/test/rtest.c @@ -18,6 +18,7 @@ #include "core/conf.h" #include "core/htrace.h" +#include "core/scope.h" #include "core/span.h" #include "test/rtest.h" #include "test/span_table.h" @@ -92,12 +93,17 @@ static int rtest_verify_table_size(struct rtest *rt, struct span_table *st) static int doit(struct rtest_data *rdata) { struct htrace_scope *scope1, *scope2, *scope2_5; + struct htrace_span_id span_id; scope1 = htrace_start_span(rdata->tracer, NULL, "part1"); - EXPECT_UINT64_GT(0L, htrace_scope_get_span_id(scope1)); + htrace_scope_get_span_id(scope1, &span_id); + EXPECT_TRUE(0 != + htrace_span_id_compare(&INVALID_SPAN_ID, &span_id)); htrace_scope_close(scope1); scope2 = htrace_start_span(rdata->tracer, NULL, "part2"); - EXPECT_UINT64_GT(0L, htrace_scope_get_span_id(scope2)); + htrace_scope_get_span_id(scope2, &span_id); + EXPECT_TRUE(0 != + htrace_span_id_compare(&INVALID_SPAN_ID, &span_id)); scope2_5 = htrace_start_span(rdata->tracer, NULL, "part2.5"); htrace_scope_close(scope2_5); htrace_scope_close(scope2); @@ -122,27 +128,27 @@ int rtest_simple_run(struct rtest *rt, const char *conf_str) int rtest_simple_verify(struct rtest *rt, struct span_table *st) { struct htrace_span *span; - uint64_t doit_id, part2_id; + struct htrace_span_id doit_id, part2_id; char trid[128]; EXPECT_INT_ZERO(rtest_verify_table_size(rt, st)); get_receiver_test_trid(trid, sizeof(trid)); EXPECT_INT_ZERO(span_table_get(st, &span, "doit", trid)); - doit_id = span->span_id; + htrace_span_id_copy(&doit_id, &span->span_id); EXPECT_INT_ZERO(span->num_parents); EXPECT_INT_ZERO(span_table_get(st, &span, "part1", trid)); EXPECT_INT_EQ(1, span->num_parents); - EXPECT_UINT64_EQ(doit_id, span->parent.single); + EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single)); EXPECT_INT_ZERO(span_table_get(st, &span, "part2", trid)); EXPECT_INT_EQ(1, span->num_parents); - part2_id = span->span_id; - EXPECT_UINT64_EQ(doit_id, span->parent.single); + htrace_span_id_copy(&part2_id, &span->span_id); + EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single)); EXPECT_INT_ZERO(span_table_get(st, &span, "part2.5", trid)); EXPECT_INT_EQ(1, span->num_parents); - EXPECT_UINT64_EQ(part2_id, span->parent.single); + EXPECT_TRUE(0 == htrace_span_id_compare(&part2_id, &span->parent.single)); return EXIT_SUCCESS; } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/rtestpp.cc ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/rtestpp.cc b/htrace-c/src/test/rtestpp.cc index 0cd7120..a5c2ac8 100644 --- a/htrace-c/src/test/rtestpp.cc +++ b/htrace-c/src/test/rtestpp.cc @@ -88,14 +88,11 @@ static int doit(RTestData &tdata, struct rtest *rt) { { htrace::Scope scope1(tdata.tracer_, "part1"); - EXPECT_UINT64_GT(0L, scope1.GetSpanId()); } { htrace::Scope scope2(tdata.tracer_, "part2"); - EXPECT_UINT64_GT(0L, scope2.GetSpanId()); { htrace::Scope scope2_5(tdata.tracer_, "part2.5"); - EXPECT_UINT64_GT(0L, scope2_5.GetSpanId()); } } return EXIT_SUCCESS; @@ -115,27 +112,27 @@ int rtestpp_simple_run(struct rtest *rt, const char *conf_str) int rtestpp_simple_verify(struct rtest *rt, struct span_table *st) { struct htrace_span *span; - uint64_t doit_id, part2_id; + struct htrace_span_id doit_id, part2_id; char trid[128]; EXPECT_INT_ZERO(rtest_generic_verify(rt, st)); get_receiver_test_trid(trid, sizeof(trid)); EXPECT_INT_ZERO(span_table_get(st, &span, "doit", trid)); - doit_id = span->span_id; + htrace_span_id_copy(&doit_id, &span->span_id); EXPECT_INT_ZERO(span->num_parents); EXPECT_INT_ZERO(span_table_get(st, &span, "part1", trid)); EXPECT_INT_EQ(1, span->num_parents); - EXPECT_UINT64_EQ(doit_id, span->parent.single); + EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single)); EXPECT_INT_ZERO(span_table_get(st, &span, "part2", trid)); EXPECT_INT_EQ(1, span->num_parents); - part2_id = span->span_id; - EXPECT_UINT64_EQ(doit_id, span->parent.single); + htrace_span_id_copy(&part2_id, &span->span_id); + EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single)); EXPECT_INT_ZERO(span_table_get(st, &span, "part2.5", trid)); EXPECT_INT_EQ(1, span->num_parents); - EXPECT_UINT64_EQ(part2_id, span->parent.single); + EXPECT_TRUE(0 == htrace_span_id_compare(&part2_id, &span->parent.single)); return EXIT_SUCCESS; } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/span-unit.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/span-unit.c b/htrace-c/src/test/span-unit.c index 5482b8d..652c9a7 100644 --- a/htrace-c/src/test/span-unit.c +++ b/htrace-c/src/test/span-unit.c @@ -20,153 +20,51 @@ #include "core/htrace.h" #include "core/htracer.h" #include "core/span.h" -#include "sampler/sampler.h" #include "test/span_util.h" #include "test/test.h" -#include "util/htable.h" -#include "util/log.h" -#include <errno.h> #include <inttypes.h> -#include <stdarg.h> #include <stdio.h> #include <stdlib.h> #include <string.h> -#define MAX_SPAN_JSON_LEN 100000 - -static struct htrace_conf *g_test_conf; - -static struct htrace_log *g_test_lg; - -static struct htracer *g_test_tracer; - -static struct htrace_span *create_span(const char *desc, - uint64_t begin_ms, uint64_t end_ms, uint64_t span_id, - const char *trid, ...) __attribute__((sentinel)); - -static int test_span_to_json(const char *expected, - struct htrace_span *span) +static int test_span_round_trip(const char *str) { - int buf_len; - char *buf; - struct htrace_span *rspan = NULL; - char err[128]; + char err[512], *json = NULL; size_t err_len = sizeof(err); - - htrace_span_sort_and_dedupe_parents(span); - buf_len = span_json_size(span); - if ((0 > buf_len) || (buf_len > MAX_SPAN_JSON_LEN)) { - fprintf(stderr, "invalid span_json_size %d.\n", buf_len); - return EXIT_FAILURE; - } - buf = malloc(buf_len); - EXPECT_NONNULL(buf); - span_json_sprintf(span, buf_len, buf); - EXPECT_STR_EQ(expected, buf); - span_json_parse(buf, &rspan, err, err_len); - if (err[0]) { - fprintf(stderr, "Failed to parse span json %s: %s\n", buf, err); - return EXIT_FAILURE; - } - EXPECT_NONNULL(rspan); - if (span_compare(span, rspan) != 0) { - htrace_span_free(rspan); - fprintf(stderr, "Failed to parse the span json back into a span " - "which was identical to the input. JSON: %s\n", buf); - return EXIT_FAILURE; - } - free(buf); - htrace_span_free(rspan); - return EXIT_SUCCESS; -} - -static struct htrace_span *create_span(const char *desc, - uint64_t begin_ms, uint64_t end_ms, uint64_t span_id, - const char *trid, ...) -{ - struct htrace_span* span = NULL; - uint64_t *parents, parent; - int i, num_parents = 0; - va_list ap, ap2; - - va_start(ap, trid); - va_copy(ap2, ap); - while (1) { - parent = va_arg(ap2, uint64_t); - if (!parent) { - break; - } - num_parents++; - } while (parent); - va_end(ap2); - if (num_parents > 0) { - parents = xcalloc(sizeof(uint64_t) * num_parents); - for (i = 0; i < num_parents; i++) { - parents[i] = va_arg(ap, uint64_t); - } - } - va_end(ap); - span = htrace_span_alloc(desc, begin_ms, span_id); - span->end_ms = end_ms; - span->span_id = span_id; - span->trid = xstrdup(trid); - span->num_parents = num_parents; - if (num_parents == 1) { - span->parent.single = parents[0]; - free(parents); - } else if (num_parents > 1) { - span->parent.list = parents; - } - return span; -} - -static int test_spans_to_str(void) -{ - struct htrace_span *span; - - span = create_span("foo", 123LLU, 456LLU, 789LLU, "span-unit", - NULL); - EXPECT_INT_ZERO(test_span_to_json( - "{\"s\":\"0000000000000315\",\"b\":123,\"e\":456," - "\"d\":\"foo\",\"r\":\"span-unit\"" - ",\"p\":[]}", span)); - htrace_span_free(span); - - span = create_span("myspan", 34359738368LLU, - 34359739368LLU, 68719476736LLU, "span-unit2", - 1LLU, 2LLU, 3LLU, NULL); - EXPECT_INT_ZERO(test_span_to_json( - "{\"s\":\"0000001000000000\",\"b\":34359738368,\"e\":34359739368," - "\"d\":\"myspan\",\"r\":\"span-unit2\"," "\"p\":[\"0000000000000001\"," - "\"0000000000000002\",\"0000000000000003\"]}", span)); + struct htrace_span *span = NULL; + int json_size; + + err[0] = '\0'; + span_json_parse(str, &span, err, err_len); + EXPECT_STR_EQ("", err); + json_size = span_json_size(span); + json = malloc(json_size); + EXPECT_NONNULL(json); + span_json_sprintf(span, json_size, json); + EXPECT_STR_EQ(str, json); + free(json); htrace_span_free(span); - span = create_span("nextSpan", 14359739368LLU, 18719476736LLU, - 0x8000001000000000LLU, "span-unit3", - 1LLU, 1LLU, 1LLU, NULL); - EXPECT_INT_ZERO(test_span_to_json( - "{\"s\":\"8000001000000000\",\"b\":14359739368,\"e\":18719476736," - "\"d\":\"nextSpan\",\"r\":\"span-unit3\"," "\"p\":[\"0000000000000001\"]" - "}", span)); - htrace_span_free(span); - return EXIT_SUCCESS; + return 0; } int main(void) { - g_test_conf = htrace_conf_from_strs("", HTRACE_TRACER_ID"=span-unit"); - EXPECT_NONNULL(g_test_conf); - g_test_lg = htrace_log_alloc(g_test_conf); - EXPECT_NONNULL(g_test_lg); - g_test_tracer = htracer_create("span-unit", g_test_conf); - EXPECT_NONNULL(g_test_tracer); - - EXPECT_INT_ZERO(test_spans_to_str()); - - htracer_free(g_test_tracer); - htrace_log_free(g_test_lg); - htrace_conf_free(g_test_conf); + EXPECT_INT_ZERO(test_span_round_trip( + "{\"a\":\"ba85631c2ce111e5b345feff819cdc9f\",\"b\":34359738368," + "\"e\":34359739368,\"d\":\"myspan\",\"r\":\"span-unit2\"," + "\"p\":[\"1549e8d42ce411e5b345feff819cdc9f\"," + "\"1b6a1d242ce411e5b345feff819cdc9f\"," + "\"25ab73822ce411e5b345feff819cdc9f\"]}")); + EXPECT_INT_ZERO(test_span_round_trip( + "{\"a\":\"000000002ce111e5b345feff819cdc9f\",\"b\":0," + "\"e\":0,\"d\":\"secondSpan\",\"r\":\"other-tracerid\"," + "\"p\":[]}")); + EXPECT_INT_ZERO(test_span_round_trip( + "{\"a\":\"6baba3842ce411e5b345feff819cdc9f\",\"b\":999," + "\"e\":1000,\"d\":\"thirdSpan\",\"r\":\"other-tracerid\"," + "\"p\":[\"000000002ce111e5b345feff819cdc9f\"]}")); return EXIT_SUCCESS; } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/span_id-unit.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/span_id-unit.c b/htrace-c/src/test/span_id-unit.c new file mode 100644 index 0000000..06c0320 --- /dev/null +++ b/htrace-c/src/test/span_id-unit.c @@ -0,0 +1,104 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "core/span_id.h" +#include "test/span_util.h" +#include "test/test.h" + +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +static int test_span_id_round_trip(const char *str) +{ + struct htrace_span_id id; + char err[512], str2[HTRACE_SPAN_ID_STRING_LENGTH + 1]; + size_t err_len = sizeof(err); + + err[0] = '\0'; + htrace_span_id_parse(&id, str, err, err_len); + EXPECT_STR_EQ("", err); + EXPECT_INT_EQ(1, htrace_span_id_to_str(&id, str2, sizeof(str2))); + EXPECT_STR_EQ(str, str2); + return 0; +} + +static int test_span_id_compare(int isLess, + const char *sa, const char *sb) +{ + struct htrace_span_id a, b; + char err[512]; + size_t err_len = sizeof(err); + int cmp; + + err[0] = '\0'; + + htrace_span_id_parse(&a, sa, err, err_len); + EXPECT_STR_EQ("", err); + + htrace_span_id_parse(&b, sb, err, err_len); + EXPECT_STR_EQ("", err); + + cmp = htrace_span_id_compare(&a, &b); + if (isLess) { + EXPECT_INT_GT(cmp, 0); + } else { + EXPECT_INT_ZERO(cmp); + } + cmp = htrace_span_id_compare(&b, &a); + if (isLess) { + EXPECT_INT_GT(0, cmp); + } else { + EXPECT_INT_ZERO(cmp); + } + return 0; +} + +static int test_span_id_less(const char *sa, const char *sb) +{ + return test_span_id_compare(1, sa, sb); +} + +static int test_span_id_eq(const char *sa, const char *sb) +{ + return test_span_id_compare(0, sa, sb); +} + +int main(void) +{ + EXPECT_INT_ZERO(test_span_id_round_trip("0123456789abcdef0011223344556677")); + EXPECT_INT_ZERO(test_span_id_round_trip("a919f3d62ce111e5b345feff819cdc9f")); + EXPECT_INT_ZERO(test_span_id_round_trip("00000000000000000000000000000000")); + EXPECT_INT_ZERO(test_span_id_round_trip("ba85631c2ce111e5b345feff819cdc9f")); + EXPECT_INT_ZERO(test_span_id_round_trip("ffffffffffffffffffffffffffffffff")); + EXPECT_INT_ZERO(test_span_id_round_trip("ba85631c2ce111e5b345feff819cdc9f")); + + EXPECT_INT_ZERO(test_span_id_less("a919f3d62ce111e5b345feff819cdc9e", + "a919f3d62ce111e5b345feff819cdc9f")); + EXPECT_INT_ZERO(test_span_id_eq("a919f3d62ce111e5b345feff819cdc9f", + "a919f3d62ce111e5b345feff819cdc9f")); + EXPECT_INT_ZERO(test_span_id_eq("ffffffff2ce111e5b345feff819cdc9f", + "ffffffff2ce111e5b345feff819cdc9f")); + EXPECT_INT_ZERO(test_span_id_less("1919f3d62ce111e5b345feff819cdc9f", + "f919f3d62ce111e5b345feff81900000")); + return EXIT_SUCCESS; +} + +// vim: ts=4:sw=4:tw=79:et http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/span_table.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/span_table.c b/htrace-c/src/test/span_table.c index 42ed5f6..b2b23fd 100644 --- a/htrace-c/src/test/span_table.c +++ b/htrace-c/src/test/span_table.c @@ -50,7 +50,8 @@ int span_table_get(struct span_table *st, struct htrace_span **out, EXPECT_NONNULL(span); EXPECT_STR_EQ(desc, span->desc); EXPECT_UINT64_GE(span->begin_ms, span->end_ms); - EXPECT_UINT64_GT(0L, span->span_id); + EXPECT_TRUE(0 != + htrace_span_id_compare(&INVALID_SPAN_ID, &span->span_id)); EXPECT_NONNULL(span->trid); EXPECT_STR_EQ(trid, span->trid); *out = span; http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/span_util-unit.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/span_util-unit.c b/htrace-c/src/test/span_util-unit.c deleted file mode 100644 index fc2a56c..0000000 --- a/htrace-c/src/test/span_util-unit.c +++ /dev/null @@ -1,74 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "test/span_util.h" -#include "test/test.h" - -#include <inttypes.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -static int test_parse_hex_id_error(const char *in) -{ - char err[128]; - - err[0] = '\0'; - parse_hex_id(in, err, sizeof(err)); - if (!err[0]) { - fprintf(stderr, "test_parse_hex_id_error(%s): expected error, but " - "was successful.\n", in); - return EXIT_FAILURE; - } - return EXIT_SUCCESS; -} - -static int test_parse_hex_id(uint64_t expected, const char *in) -{ - char err[128]; - size_t err_len = sizeof(err); - uint64_t val; - - err[0] = '\0'; - val = parse_hex_id(in, err, err_len); - if (err[0]) { - fprintf(stderr, "test_parse_hex_id(%s): got error %s\n", - in, err); - return EXIT_FAILURE; - } - EXPECT_UINT64_EQ(expected, val); - return EXIT_SUCCESS; -} - -int main(void) -{ - EXPECT_INT_ZERO(test_parse_hex_id_error("")); - EXPECT_INT_ZERO(test_parse_hex_id_error("z")); - EXPECT_INT_ZERO(test_parse_hex_id_error("achoo")); - EXPECT_INT_ZERO(test_parse_hex_id(1LLU, "00000000000000001")); - EXPECT_INT_ZERO(test_parse_hex_id(0xffffffffffffffffLLU, - "ffffffffffffffff")); - EXPECT_INT_ZERO(test_parse_hex_id(0x8000000000000000LLU, - "8000000000000000")); - EXPECT_INT_ZERO(test_parse_hex_id(0x6297421fe159345fLLU, - "6297421fe159345f")); - EXPECT_INT_ZERO(test_parse_hex_id_error("6297421fe159345fzoo")); - return EXIT_SUCCESS; -} - -// vim: ts=4:sw=4:tw=79:et http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-c/src/test/span_util.c ---------------------------------------------------------------------- diff --git a/htrace-c/src/test/span_util.c b/htrace-c/src/test/span_util.c index 625ba86..04490a9 100644 --- a/htrace-c/src/test/span_util.c +++ b/htrace-c/src/test/span_util.c @@ -29,46 +29,15 @@ #include <stdlib.h> #include <string.h> -uint64_t parse_hex_id(const char *in, char *err, size_t err_len) -{ - char *endptr; - unsigned long long int ret; - - err[0] = '\0'; - errno = 0; - ret = strtoull(in, &endptr, 16); - if (errno) { - int e = errno; - snprintf(err, err_len, "parse_hex_id(%s) failed: error %s", - in, terror(e)); - return 0; - } - if (endptr == in) { - snprintf(err, err_len, "parse_hex_id(%s) failed: empty string " - "found.", in); - return 0; - } - while (1) { - char c = *endptr++; - if (c == '\0') { - break; - } - if ((c != ' ') || (c != '\t')) { - snprintf(err, err_len, "parse_hex_id(%s) failed: garbage at end " - "of string.", in); - return 0; - } - } - return ret; -} - static void span_json_parse_parents(struct json_object *root, struct htrace_span *span, char *err, size_t err_len) { char err2[128]; + size_t err2_len = sizeof(err2); struct json_object *p = NULL, *e = NULL; int i, np; + err2[0] = '\0'; if (!json_object_object_get_ex(root, "p", &p)) { return; // no parents } @@ -80,14 +49,14 @@ static void span_json_parse_parents(struct json_object *root, if (np == 1) { span->num_parents = 1; e = json_object_array_get_idx(p, 0); - span->parent.single = parse_hex_id(json_object_get_string(e), - err2, sizeof(err2)); + htrace_span_id_parse(&span->parent.single, + json_object_get_string(e), err2, err2_len); if (err2[0]) { snprintf(err, err_len, "failed to parse parent ID 1/1: %s.", err2); return; } } else if (np > 1) { - span->parent.list = malloc(sizeof(uint64_t) * np); + span->parent.list = malloc(sizeof(struct htrace_span_id) * np); if (!span->parent.list) { snprintf(err, err_len, "failed to allocate parent ID array of " "%d elements", np); @@ -96,8 +65,8 @@ static void span_json_parse_parents(struct json_object *root, span->num_parents = np; for (i = 0; i < np; i++) { e = json_object_array_get_idx(p, i); - span->parent.list[i] = parse_hex_id(json_object_get_string(e), - err2, sizeof(err2)); + htrace_span_id_parse(span->parent.list + i, + json_object_get_string(e), err2, err2_len); if (err2[0]) { snprintf(err, err_len, "failed to parse parent ID %d/%d: %s", i + 1, np, err2); @@ -115,6 +84,7 @@ static void span_json_parse_impl(struct json_object *root, int res; err[0] = '\0'; + err2[0] = '\0'; if (!json_object_object_get_ex(root, "d", &d)) { d = NULL; } @@ -141,8 +111,8 @@ static void span_json_parse_impl(struct json_object *root, return; } } - if (json_object_object_get_ex(root, "s", &s)) { - span->span_id = parse_hex_id(json_object_get_string(s), + if (json_object_object_get_ex(root, "a", &s)) { + htrace_span_id_parse(&span->span_id, json_object_get_string(s), err2, sizeof(err2)); if (err2[0]) { snprintf(err, err_len, "error parsing span_id: %s", err2); @@ -226,7 +196,7 @@ static int strcmp_handle_null(const char *a, const char *b) static int compare_parents(struct htrace_span *a, struct htrace_span *b) { - int na, nb, i; + int na, nb, i, cmp; htrace_span_sort_and_dedupe_parents(a); na = a->num_parents; @@ -234,7 +204,7 @@ static int compare_parents(struct htrace_span *a, struct htrace_span *b) nb = b->num_parents; for (i = 0; ; i++) { - uint64_t sa, sb; + struct htrace_span_id sa, sb; if (i >= na) { if (i >= nb) { @@ -246,21 +216,18 @@ static int compare_parents(struct htrace_span *a, struct htrace_span *b) return 1; } if ((i == 0) && (na == 1)) { - sa = a->parent.single; + htrace_span_id_copy(&sa, &a->parent.single); } else { - sa = a->parent.list[i]; + htrace_span_id_copy(&sa, a->parent.list + i); } if ((i == 0) && (nb == 1)) { - sb = b->parent.single; + htrace_span_id_copy(&sb, &b->parent.single); } else { - sb = b->parent.list[i]; + htrace_span_id_copy(&sb, b->parent.list + i); } - // Use explicit comparison rather than subtraction to avoid numeric - // overflow issues. - if (sa < sb) { - return -1; - } else if (sa > sb) { - return 1; + cmp = htrace_span_id_compare(&sa, &sb); + if (cmp) { + return cmp; } } } @@ -269,7 +236,7 @@ int span_compare(struct htrace_span *a, struct htrace_span *b) { int c; - c = uint64_cmp(a->span_id, b->span_id); + c = htrace_span_id_compare(&a->span_id, &b->span_id); if (c) { return c; } @@ -355,7 +322,7 @@ static void span_parse_msgpack_parents(struct cmp_ctx_s *ctx, free(span->parent.list); span->parent.list = NULL; } - span->parent.single = 0; + htrace_span_id_clear(&span->parent.single); span->num_parents = 0; if (!cmp_read_array(ctx, &size)) { snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_array " @@ -363,22 +330,22 @@ static void span_parse_msgpack_parents(struct cmp_ctx_s *ctx, return; } if (size == 1) { - if (!cmp_read_u64(ctx, &span->parent.single)) { + if (!htrace_span_id_read_msgpack(&span->parent.single, ctx)) { snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_u64 " "for single child ID failed"); return; } } else if (size > 1) { - span->parent.list = malloc(sizeof(uint64_t) * size); + span->parent.list = malloc(sizeof(struct htrace_span_id) * size); if (!span->parent.list) { snprintf(err, err_len, "span_parse_msgpack_parents: failed to " "malloc %"PRId32"-entry parent array.", size); return; } for (i = 0; i < size; i++) { - if (!cmp_read_u64(ctx, &span->parent.list[i])) { - snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_u64 " - "for child %d ID failed", i); + if (!htrace_span_id_read_msgpack(span->parent.list + i, ctx)) { + snprintf(err, err_len, "span_parse_msgpack_parents: " + "htrace_span_id_read_msgpack for child %d ID failed", i); free(span->parent.list); span->parent.list = NULL; return; @@ -412,6 +379,13 @@ struct htrace_span *span_read_msgpack(struct cmp_ctx_s *ctx, goto error; } switch (key[0]) { + case 'a': + if (!htrace_span_id_read_msgpack(&span->span_id, ctx)) { + snprintf(err, err_len, "span_read_msgpack: " + "htrace_span_id_read_msgpack failed for span->span_id"); + goto error; + } + break; case 'd': if (span->desc) { free(span->desc); @@ -436,13 +410,6 @@ struct htrace_span *span_read_msgpack(struct cmp_ctx_s *ctx, goto error; } break; - case 's': - if (!cmp_read_u64(ctx, &span->span_id)) { - snprintf(err, err_len, "span_read_msgpack: cmp_read_u64 " - "failed for span->span_id"); - goto error; - } - break; case 'r': if (span->trid) { free(span->trid); http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/Span.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/Span.java b/htrace-core/src/main/java/org/apache/htrace/Span.java index f41da30..0897ee9 100644 --- a/htrace-core/src/main/java/org/apache/htrace/Span.java +++ b/htrace-core/src/main/java/org/apache/htrace/Span.java @@ -75,13 +75,7 @@ public interface Span { * The spanId is immutable and cannot be changed. It is safe to access this * from multiple threads. */ - long getSpanId(); - - /** - * A pseudo-unique (random) number assigned to the trace associated with this - * span - */ - long getTraceId(); + SpanId getSpanId(); /** * Create a child span of this span with the given description @@ -96,14 +90,14 @@ public interface Span { * * The array will be empty if there are no parents. */ - long[] getParents(); + SpanId[] getParents(); /** * Set the parents of this span.<p/> * * Any existing parents will be cleared by this call. */ - void setParents(long[] parents); + void setParents(SpanId[] parents); /** * Add a data annotation associated with this span @@ -151,11 +145,8 @@ public interface Span { public void serialize(Span span, JsonGenerator jgen, SerializerProvider provider) throws IOException { jgen.writeStartObject(); - if (span.getTraceId() != 0) { - jgen.writeStringField("i", String.format("%016x", span.getTraceId())); - } - if (span.getSpanId() != 0) { - jgen.writeStringField("s", String.format("%016x", span.getSpanId())); + if (span.getSpanId().isValid()) { + jgen.writeStringField("a", span.getSpanId().toString()); } if (span.getStartTimeMillis() != 0) { jgen.writeNumberField("b", span.getStartTimeMillis()); @@ -171,8 +162,8 @@ public interface Span { jgen.writeStringField("r", tracerId); } jgen.writeArrayFieldStart("p"); - for (long parent : span.getParents()) { - jgen.writeString(String.format("%016x", parent)); + for (SpanId parent : span.getParents()) { + jgen.writeString(parent.toString()); } jgen.writeEndArray(); Map<String, String> traceInfoMap = span.getKVAnnotations(); http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/SpanId.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/SpanId.java b/htrace-core/src/main/java/org/apache/htrace/SpanId.java new file mode 100644 index 0000000..25dc108 --- /dev/null +++ b/htrace-core/src/main/java/org/apache/htrace/SpanId.java @@ -0,0 +1,149 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.htrace; + +import java.math.BigInteger; +import java.lang.Void; +import java.util.concurrent.ThreadLocalRandom; +import java.util.Random; + +/** + * Uniquely identifies an HTrace span. + * + * Span IDs are 128 bits in total. The upper 64 bits of a span ID is the same + * as the upper 64 bits of the parent span, if there is one. The lower 64 bits + * are always random. + */ +public final class SpanId implements Comparable<SpanId> { + private static final int SPAN_ID_STRING_LENGTH = 32; + private final long high; + private final long low; + + /** + * The invalid span ID, which is all zeroes. + * + * It is also the "least" span ID in the sense that it is considered + * smaller than any other span ID. + */ + public static SpanId INVALID = new SpanId(0, 0); + + private static long nonZeroRand64() { + while (true) { + long r = ThreadLocalRandom.current().nextLong(); + if (r != 0) { + return r; + } + } + } + + public static SpanId fromRandom() { + return new SpanId(nonZeroRand64(), nonZeroRand64()); + } + + public static SpanId fromString(String str) { + if (str.length() != SPAN_ID_STRING_LENGTH) { + throw new RuntimeException("Invalid SpanID string: length was not " + + SPAN_ID_STRING_LENGTH); + } + long high = + ((Long.parseLong(str.substring(0, 8), 16)) << 32) | + (Long.parseLong(str.substring(8, 16), 16)); + long low = + ((Long.parseLong(str.substring(16, 24), 16)) << 32) | + (Long.parseLong(str.substring(24, 32), 16)); + return new SpanId(high, low); + } + + public SpanId(long high, long low) { + this.high = high; + this.low = low; + } + + public long getHigh() { + return high; + } + + public long getLow() { + return low; + } + + @Override + public boolean equals(Object o) { + if (!(o instanceof SpanId)) { + return false; + } + SpanId other = (SpanId)o; + return ((other.high == high) && (other.low == low)); + } + + @Override + public int compareTo(SpanId other) { + int cmp = compareAsUnsigned(high, other.high); + if (cmp != 0) { + return cmp; + } + return compareAsUnsigned(low, other.low); + } + + private static int compareAsUnsigned(long a, long b) { + boolean aSign = a < 0; + boolean bSign = b < 0; + if (aSign != bSign) { + if (aSign) { + return 1; + } else { + return -1; + } + } + if (aSign) { + a = -a; + b = -b; + } + if (a < b) { + return -1; + } else if (a > b) { + return 1; + } else { + return 0; + } + } + + @Override + public int hashCode() { + return (int)((0xffffffff & (high >> 32))) ^ + (int)((0xffffffff & (high >> 0))) ^ + (int)((0xffffffff & (low >> 32))) ^ + (int)((0xffffffff & (low >> 0))); + } + + @Override + public String toString() { + return String.format("%08x%08x%08x%08x", + (0x00000000ffffffffL & (high >> 32)), + (0x00000000ffffffffL & high), + (0x00000000ffffffffL & (low >> 32)), + (0x00000000ffffffffL & low)); + } + + public boolean isValid() { + return (high != 0) || (low != 0); + } + + public SpanId newChildId() { + return new SpanId(high, nonZeroRand64()); + } +} http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/Trace.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/Trace.java b/htrace-core/src/main/java/org/apache/htrace/Trace.java index b9def45..e782309 100644 --- a/htrace-core/src/main/java/org/apache/htrace/Trace.java +++ b/htrace-core/src/main/java/org/apache/htrace/Trace.java @@ -75,15 +75,16 @@ public class Trace { return startSpan(description, NeverSampler.INSTANCE); } - public static TraceScope startSpan(String description, TraceInfo tinfo) { - if (tinfo == null) return continueSpan(null); + public static TraceScope startSpan(String description, SpanId parentId) { + if (parentId == null) { + return continueSpan(null); + } Span newSpan = new MilliSpan.Builder(). begin(System.currentTimeMillis()). end(0). description(description). - traceId(tinfo.traceId). - spanId(Tracer.nonZeroRandom64()). - parents(new long[] { tinfo.spanId }). + spanId(parentId.newChildId()). + parents(new SpanId[] { parentId }). build(); return continueSpan(newSpan); } http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java b/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java deleted file mode 100644 index 9e7d74a..0000000 --- a/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java +++ /dev/null @@ -1,38 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.htrace; - - -public class TraceInfo { - public final long traceId; - public final long spanId; - - public TraceInfo(long traceId, long spanId) { - this.traceId = traceId; - this.spanId = spanId; - } - - @Override - public String toString() { - return "TraceInfo(traceId=" + traceId + ", spanId=" + spanId + ")"; - } - - public static TraceInfo fromSpan(Span s) { - if (s == null) return null; - return new TraceInfo(s.getTraceId(), s.getSpanId()); - } -} http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/TraceTree.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/TraceTree.java b/htrace-core/src/main/java/org/apache/htrace/TraceTree.java deleted file mode 100644 index db781cb..0000000 --- a/htrace-core/src/main/java/org/apache/htrace/TraceTree.java +++ /dev/null @@ -1,191 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.htrace; - -import org.apache.htrace.impl.MilliSpan; - -import org.apache.commons.logging.Log; -import org.apache.commons.logging.LogFactory; - -import java.util.Arrays; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashMap; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.TreeSet; - -/** - * Used to create the graph formed by spans. - */ -public class TraceTree { - private static final Log LOG = LogFactory.getLog(Tracer.class); - - - public static class SpansByParent { - /** - * Compare two spans by span ID. - */ - private static Comparator<Span> COMPARATOR = - new Comparator<Span>() { - @Override - public int compare(Span a, Span b) { - if (a.getSpanId() < b.getSpanId()) { - return -1; - } else if (a.getSpanId() > b.getSpanId()) { - return 1; - } else { - return 0; - } - } - }; - - private final TreeSet<Span> treeSet; - - private final HashMap<Long, LinkedList<Span>> parentToSpans; - - SpansByParent(Collection<Span> spans) { - TreeSet<Span> treeSet = new TreeSet<Span>(COMPARATOR); - parentToSpans = new HashMap<Long, LinkedList<Span>>(); - for (Span span : spans) { - treeSet.add(span); - for (long parent : span.getParents()) { - LinkedList<Span> list = parentToSpans.get(Long.valueOf(parent)); - if (list == null) { - list = new LinkedList<Span>(); - parentToSpans.put(Long.valueOf(parent), list); - } - list.add(span); - } - if (span.getParents().length == 0) { - LinkedList<Span> list = parentToSpans.get(Long.valueOf(0L)); - if (list == null) { - list = new LinkedList<Span>(); - parentToSpans.put(Long.valueOf(0L), list); - } - list.add(span); - } - } - this.treeSet = treeSet; - } - - public List<Span> find(long parentId) { - LinkedList<Span> spans = parentToSpans.get(parentId); - if (spans == null) { - return new LinkedList<Span>(); - } - return spans; - } - - public Iterator<Span> iterator() { - return Collections.unmodifiableSortedSet(treeSet).iterator(); - } - } - - public static class SpansByTracerId { - /** - * Compare two spans by process ID, and then by span ID. - */ - private static Comparator<Span> COMPARATOR = - new Comparator<Span>() { - @Override - public int compare(Span a, Span b) { - int cmp = a.getTracerId().compareTo(b.getTracerId()); - if (cmp != 0) { - return cmp; - } else if (a.getSpanId() < b.getSpanId()) { - return -1; - } else if (a.getSpanId() > b.getSpanId()) { - return 1; - } else { - return 0; - } - } - }; - - private final TreeSet<Span> treeSet; - - SpansByTracerId(Collection<Span> spans) { - TreeSet<Span> treeSet = new TreeSet<Span>(COMPARATOR); - for (Span span : spans) { - treeSet.add(span); - } - this.treeSet = treeSet; - } - - public List<Span> find(String tracerId) { - List<Span> spans = new ArrayList<Span>(); - Span span = new MilliSpan.Builder(). - traceId(Long.MIN_VALUE). - spanId(Long.MIN_VALUE). - tracerId(tracerId). - build(); - while (true) { - span = treeSet.higher(span); - if (span == null) { - break; - } - if (span.getTracerId().equals(tracerId)) { - break; - } - spans.add(span); - } - return spans; - } - - public Iterator<Span> iterator() { - return Collections.unmodifiableSortedSet(treeSet).iterator(); - } - } - - private final SpansByParent spansByParent; - private final SpansByTracerId spansByTracerId; - - /** - * Create a new TraceTree - * - * @param spans The collection of spans to use to create this TraceTree. Should - * have at least one root span. - */ - public TraceTree(Collection<Span> spans) { - this.spansByParent = new SpansByParent(spans); - this.spansByTracerId = new SpansByTracerId(spans); - } - - public SpansByParent getSpansByParent() { - return spansByParent; - } - - public SpansByTracerId getSpansByTracerId() { - return spansByTracerId; - } - - @Override - public String toString() { - StringBuilder bld = new StringBuilder(); - String prefix = ""; - for (Iterator<Span> iter = spansByParent.iterator(); iter.hasNext();) { - Span span = iter.next(); - bld.append(prefix).append(span.toString()); - prefix = "\n"; - } - return bld.toString(); - } -} http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/Tracer.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/Tracer.java b/htrace-core/src/main/java/org/apache/htrace/Tracer.java index b0ed451..d07e1a8 100644 --- a/htrace-core/src/main/java/org/apache/htrace/Tracer.java +++ b/htrace-core/src/main/java/org/apache/htrace/Tracer.java @@ -48,8 +48,7 @@ public class Tracer { return null; } }; - public static final TraceInfo DONT_TRACE = new TraceInfo(-1, -1); - private static final long EMPTY_PARENT_ARRAY[] = new long[0]; + private static final SpanId EMPTY_PARENT_ARRAY[] = new SpanId[0]; /** * Log a client error, and throw an exception. @@ -81,9 +80,8 @@ public class Tracer { begin(System.currentTimeMillis()). end(0). description(description). - traceId(nonZeroRandom64()). parents(EMPTY_PARENT_ARRAY). - spanId(nonZeroRandom64()). + spanId(SpanId.fromRandom()). build(); } else { return parent.child(description); http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java index 3f6e700..9d49cf9 100644 --- a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java +++ b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java @@ -26,6 +26,7 @@ import com.fasterxml.jackson.databind.ObjectReader; import com.fasterxml.jackson.databind.ObjectWriter; import com.fasterxml.jackson.databind.annotation.JsonDeserialize; import org.apache.htrace.Span; +import org.apache.htrace.SpanId; import org.apache.htrace.TimelineAnnotation; import org.apache.htrace.Tracer; @@ -40,8 +41,6 @@ import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; -import java.util.Random; -import java.util.concurrent.ThreadLocalRandom; /** * A Span implementation that stores its information in milliseconds since the @@ -52,37 +51,26 @@ public class MilliSpan implements Span { private static ObjectMapper OBJECT_MAPPER = new ObjectMapper(); private static ObjectReader JSON_READER = OBJECT_MAPPER.reader(MilliSpan.class); private static ObjectWriter JSON_WRITER = OBJECT_MAPPER.writer(); - private static final long EMPTY_PARENT_ARRAY[] = new long[0]; + private static final SpanId EMPTY_PARENT_ARRAY[] = new SpanId[0]; private static final String EMPTY_STRING = ""; private long begin; private long end; private final String description; - private final long traceId; - private long parents[]; - private final long spanId; + private SpanId parents[]; + private final SpanId spanId; private Map<String, String> traceInfo = null; private String tracerId; private List<TimelineAnnotation> timeline = null; - private static long nonZeroRandom64() { - long id; - Random random = ThreadLocalRandom.current(); - do { - id = random.nextLong(); - } while (id == 0); - return id; - } - @Override public Span child(String childDescription) { return new MilliSpan.Builder(). begin(System.currentTimeMillis()). end(0). description(childDescription). - traceId(traceId). - parents(new long[] {spanId}). - spanId(nonZeroRandom64()). + parents(new SpanId[] {spanId}). + spanId(spanId.newChildId()). tracerId(tracerId). build(); } @@ -94,9 +82,8 @@ public class MilliSpan implements Span { private long begin; private long end; private String description = EMPTY_STRING; - private long traceId; - private long parents[] = EMPTY_PARENT_ARRAY; - private long spanId; + private SpanId parents[] = EMPTY_PARENT_ARRAY; + private SpanId spanId = SpanId.INVALID; private Map<String, String> traceInfo = null; private String tracerId = EMPTY_STRING; private List<TimelineAnnotation> timeline = null; @@ -119,26 +106,21 @@ public class MilliSpan implements Span { return this; } - public Builder traceId(long traceId) { - this.traceId = traceId; - return this; - } - - public Builder parents(long parents[]) { + public Builder parents(SpanId parents[]) { this.parents = parents; return this; } - public Builder parents(List<Long> parentList) { - long[] parents = new long[parentList.size()]; + public Builder parents(List<SpanId> parentList) { + SpanId[] parents = new SpanId[parentList.size()]; for (int i = 0; i < parentList.size(); i++) { - parents[i] = parentList.get(i).longValue(); + parents[i] = parentList.get(i); } this.parents = parents; return this; } - public Builder spanId(long spanId) { + public Builder spanId(SpanId spanId) { this.spanId = spanId; return this; } @@ -167,9 +149,8 @@ public class MilliSpan implements Span { this.begin = 0; this.end = 0; this.description = EMPTY_STRING; - this.traceId = 0; this.parents = EMPTY_PARENT_ARRAY; - this.spanId = 0; + this.spanId = SpanId.INVALID; this.traceInfo = null; this.tracerId = EMPTY_STRING; this.timeline = null; @@ -179,7 +160,6 @@ public class MilliSpan implements Span { this.begin = builder.begin; this.end = builder.end; this.description = builder.description; - this.traceId = builder.traceId; this.parents = builder.parents; this.spanId = builder.spanId; this.traceInfo = builder.traceInfo; @@ -227,26 +207,21 @@ public class MilliSpan implements Span { } @Override - public long getSpanId() { + public SpanId getSpanId() { return spanId; } @Override - public long[] getParents() { + public SpanId[] getParents() { return parents; } @Override - public void setParents(long[] parents) { + public void setParents(SpanId[] parents) { this.parents = parents; } @Override - public long getTraceId() { - return traceId; - } - - @Override public long getStartTimeMillis() { return begin; } @@ -308,10 +283,6 @@ public class MilliSpan implements Span { return writer.toString(); } - private static long parseUnsignedHexLong(String s) { - return new BigInteger(s, 16).longValue(); - } - public static class MilliSpanDeserializer extends JsonDeserializer<MilliSpan> { @Override @@ -331,25 +302,21 @@ public class MilliSpan implements Span { if (dNode != null) { builder.description(dNode.asText()); } - JsonNode iNode = root.get("i"); - if (iNode != null) { - builder.traceId(parseUnsignedHexLong(iNode.asText())); - } - JsonNode sNode = root.get("s"); + JsonNode sNode = root.get("a"); if (sNode != null) { - builder.spanId(parseUnsignedHexLong(sNode.asText())); + builder.spanId(SpanId.fromString(sNode.asText())); } JsonNode rNode = root.get("r"); if (rNode != null) { builder.tracerId(rNode.asText()); } JsonNode parentsNode = root.get("p"); - LinkedList<Long> parents = new LinkedList<Long>(); + LinkedList<SpanId> parents = new LinkedList<SpanId>(); if (parentsNode != null) { for (Iterator<JsonNode> iter = parentsNode.elements(); iter.hasNext(); ) { JsonNode parentIdNode = iter.next(); - parents.add(parseUnsignedHexLong(parentIdNode.asText())); + parents.add(SpanId.fromString(parentIdNode.asText())); } } builder.parents(parents); http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java b/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java index e13a0f8..868c0d0 100644 --- a/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java +++ b/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java @@ -24,8 +24,6 @@ import org.apache.htrace.HTraceConfiguration; import org.apache.htrace.Span; import org.apache.htrace.SpanReceiver; import org.apache.htrace.Tracer; -import org.apache.htrace.TraceTree.SpansByParent; -import org.apache.htrace.TraceTree; import org.apache.htrace.impl.AlwaysSampler; import org.apache.htrace.impl.LocalFileSpanReceiver; import org.apache.htrace.impl.POJOSpanReceiver; http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/a06159b2/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java ---------------------------------------------------------------------- diff --git a/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java b/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java index 13338e9..92f96c8 100644 --- a/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java +++ b/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java @@ -16,7 +16,7 @@ */ package org.apache.htrace; -import org.apache.htrace.TraceTree.SpansByParent; +import org.apache.htrace.TraceGraph.SpansByParent; import org.apache.htrace.impl.LocalFileSpanReceiver; import org.apache.htrace.impl.POJOSpanReceiver; import org.apache.htrace.impl.StandardOutSpanReceiver; @@ -67,8 +67,8 @@ public class TestHTrace { traceCreator.addReceiver(new POJOSpanReceiver(HTraceConfiguration.EMPTY){ @Override public void close() { - TraceTree traceTree = new TraceTree(getSpans()); - Collection<Span> roots = traceTree.getSpansByParent().find(0); + TraceGraph traceGraph = new TraceGraph(getSpans()); + Collection<Span> roots = traceGraph.getSpansByParent().find(SpanId.INVALID); Assert.assertTrue("Trace tree must have roots", !roots.isEmpty()); Assert.assertEquals(numTraces, roots.size()); @@ -84,7 +84,7 @@ public class TestHTrace { Assert.assertTrue(descriptionToRootSpan.keySet().contains( TraceCreator.THREADED_TRACE_ROOT)); - SpansByParent spansByParentId = traceTree.getSpansByParent(); + SpansByParent spansByParentId = traceGraph.getSpansByParent(); Span rpcTraceRoot = descriptionToRootSpan.get(TraceCreator.RPC_TRACE_ROOT); Assert.assertEquals(1, spansByParentId.find(rpcTraceRoot.getSpanId()).size()); @@ -109,11 +109,10 @@ public class TestHTrace { @Test(timeout=60000) public void testRootSpansHaveNonZeroSpanId() throws Exception { - TraceInfo traceInfo = new TraceInfo(100L, 200L); - TraceScope scope = Trace.startSpan("myRootSpan", traceInfo); + TraceScope scope = Trace.startSpan("myRootSpan", new SpanId(100L, 200L)); Assert.assertNotNull(scope); Assert.assertEquals("myRootSpan", scope.getSpan().getDescription()); - Assert.assertEquals(100L, scope.getSpan().getTraceId()); - Assert.assertTrue(0 != scope.getSpan().getSpanId()); + Assert.assertEquals(100L, scope.getSpan().getSpanId().getHigh()); + Assert.assertTrue(scope.getSpan().getSpanId().isValid()); } }
