From 61ca8fd927ae7770deb7f1032a55afccaf957a0b Mon Sep 17 00:00:00 2001 From: Eugene Loh Date: Thu, 7 Sep 2017 01:29:26 -0700 Subject: [PATCH] dtrace: implement llquantize log/linear aggregation DTrace offers a histogram aggregation, quantize(), whose bins are base-2 logarithmic. It also has a linear function lquantize(). Linux DTrace should also implement a log-linear function llquantize(). Such functionality is supported by Solaris DTrace and other tracing tools. Motivations for such a function include: - a logarithmic aggregation with base other than 2 (e.g. base 10) - finer control than simply logarithmic - greater dynamic range than simply linear Orabug: 26675659 Signed-off-by: Eugene Loh Reviewed-by: Tomas Jedlicka --- dtrace/dtrace_ecb.c | 35 +++++++ dtrace/dtrace_probe_ctx.c | 105 ++++++++++++++++++-- include/dtrace/dtrace_impl.h | 1 + include/uapi/linux/dtrace/actions_defines.h | 26 +++++ 4 files changed, 161 insertions(+), 6 deletions(-) diff --git a/dtrace/dtrace_ecb.c b/dtrace/dtrace_ecb.c index 7b2bd735da6d..68e2e54bb5ab 100644 --- a/dtrace/dtrace_ecb.c +++ b/dtrace/dtrace_ecb.c @@ -77,6 +77,41 @@ static dtrace_action_t *dtrace_ecb_aggregation_create(dtrace_ecb_t *ecb, break; } + case DTRACEAGG_LLQUANTIZE: { + uint16_t factor = DTRACE_LLQUANTIZE_FACTOR(desc->dtad_arg); + uint16_t lmag = DTRACE_LLQUANTIZE_LMAG(desc->dtad_arg); + uint16_t hmag = DTRACE_LLQUANTIZE_HMAG(desc->dtad_arg); + uint16_t steps = DTRACE_LLQUANTIZE_STEPS(desc->dtad_arg); + + agg->dtag_initial = desc->dtad_arg; + agg->dtag_aggregate = dtrace_aggregate_llquantize; + + /* + * 64 is the largest hmag can practically be (for the smallest + * possible value of factor, 2). libdtrace has already checked + * for overflow, so if hmag > 64, we have corrupted DOF. + */ + if (factor < 2 || steps == 0 || hmag > 64) + goto err; + + /* + * The size of the buffer for an llquantize() is given by: + * (hmag-lmag+1) logarithmic ranges + * x + * (steps - steps/factor) bins per range + * x + * 2 signs + * + + * two overflow bins + * + + * one underflow bin + * + + * beginning word to encode factor,lmag,hmag,steps + */ + size = ((hmag-lmag+1)*(steps-steps/factor)*2+4) * sizeof (uint64_t); + break; + } + case DTRACEAGG_AVG: agg->dtag_aggregate = dtrace_aggregate_avg; size = sizeof(uint64_t) * 2; diff --git a/dtrace/dtrace_probe_ctx.c b/dtrace/dtrace_probe_ctx.c index 40e8f5c1d529..5a539a18243f 100644 --- a/dtrace/dtrace_probe_ctx.c +++ b/dtrace/dtrace_probe_ctx.c @@ -188,6 +188,99 @@ void dtrace_aggregate_lquantize(uint64_t *lquanta, uint64_t nval, lquanta[levels + 1] += incr; } +static uint64_t dtrace_pow(uint64_t base, uint64_t exp) +{ + uint64_t p, r; + + p = base; + r = 1; + while (exp > 0) { + if (exp & 1) + r *= p; + + p *= p; + exp >>= 1; + } + + return (r); +} + +void dtrace_aggregate_llquantize(uint64_t *llquanta, uint64_t nval, uint64_t incr) +{ + uint64_t arg = *llquanta++; + int factor = DTRACE_LLQUANTIZE_FACTOR(arg); + int lmag = DTRACE_LLQUANTIZE_LMAG(arg); + int hmag = DTRACE_LLQUANTIZE_HMAG(arg); + int steps = DTRACE_LLQUANTIZE_STEPS(arg); + int i, signbit, steps_factor, mag, underflow_bin; + uint64_t val, bucket_max; + + ASSERT(steps != 0); + ASSERT(factor > 1); + + if (nval >> (64 - 1)) { + signbit = -1; + val = 1 + ~nval; + } else { + signbit = +1; + val = nval; + } + + /* + * Compute steps/factor. + * Notice that while we say there are "steps" bins per logarithmic range, + * steps/factor of them actually overlap with lower ranges. + * E.g., if factor=10 and steps=20, for mag=2 we have the 20 bins + * 0 50 100 150 200 250 300 350 ... 800 850 900 950 + * but the first two actually belong to lower ranges. + */ + steps_factor = steps/factor; + + /* the underflow bin is in the middle */ + underflow_bin = 1 + (hmag-lmag+1) * (steps-steps_factor); + + bucket_max = dtrace_pow(factor, lmag); + + /* check for "underflow" (smaller than the smallest bin) */ + if ( val < bucket_max ) { + llquanta[underflow_bin] += incr; + return; + } + + /* loop over the logarithmic ranges */ + i = 0; + for (mag = lmag; mag <= hmag; mag++) { + bucket_max *= factor; + if (val >= bucket_max) continue; + + /* + * We want + * i = val * steps / bucket_max; + * but val*steps could overflow. An alternative is + * i = val / ( bucket_max/steps ) + * but bucket_max/steps might not divide evenly. + * (Plus, we end up with an extra divide.) + * + * From Solaris, we inherit constraints on factor and steps + * that mean bucket_max/steps divides evenly when mag>0. + * Meanwhile, if mag==0, val*steps cannot overflow. + * So between our two expressions for i, at least one + * will work and we just have to pick which one to use. + */ + if (mag == 0) { + i = val * steps / bucket_max; + } else { + i = val / ( bucket_max/steps ); + } + + // shift for low indices that can never happen + i -= steps_factor; + break; + } + i = underflow_bin+signbit*((steps-steps_factor)*(mag-lmag)+i+1); + llquanta[i] += incr; +} + void dtrace_aggregate_avg(uint64_t *data, uint64_t nval, uint64_t arg) { data[0]++; @@ -321,12 +414,12 @@ void dtrace_aggregate(dtrace_aggregation_t *agg, dtrace_buffer_t *dbuf, if (!agg->dtag_hasarg) /* - * Currently, only quantize() and lquantize() take additional - * arguments, and they have the same semantics: an increment - * value that defaults to 1 when not present. If additional - * aggregating actions take arguments, the setting of the - * default argument value will presumably have to become more - * sophisticated... + * Currently, only quantize(), lquantize() and llquantize() + * take additional arguments, and they have the same semantics: + * an increment value that defaults to 1 when not present. If + * additional aggregating actions take arguments, the setting + * of the default argument value will presumably have to + * become more sophisticated... */ arg = 1; diff --git a/include/dtrace/dtrace_impl.h b/include/dtrace/dtrace_impl.h index 6df1220fc731..c0091acf0a2d 100644 --- a/include/dtrace/dtrace_impl.h +++ b/include/dtrace/dtrace_impl.h @@ -432,6 +432,7 @@ extern void dtrace_aggregate_min(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_max(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_quantize(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_lquantize(uint64_t *, uint64_t, uint64_t); +extern void dtrace_aggregate_llquantize(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_avg(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_stddev(uint64_t *, uint64_t, uint64_t); extern void dtrace_aggregate_count(uint64_t *, uint64_t, uint64_t); diff --git a/include/uapi/linux/dtrace/actions_defines.h b/include/uapi/linux/dtrace/actions_defines.h index 8a943bfcb7c2..57306f8f16aa 100644 --- a/include/uapi/linux/dtrace/actions_defines.h +++ b/include/uapi/linux/dtrace/actions_defines.h @@ -103,6 +103,7 @@ #define DTRACEAGG_STDDEV (DTRACEACT_AGGREGATION + 6) #define DTRACEAGG_QUANTIZE (DTRACEACT_AGGREGATION + 7) #define DTRACEAGG_LQUANTIZE (DTRACEACT_AGGREGATION + 8) +#define DTRACEAGG_LLQUANTIZE (DTRACEACT_AGGREGATION + 9) #define DTRACE_QUANTIZE_NBUCKETS \ (((sizeof (uint64_t) * NBBY) - 1) * 2 + 1) @@ -134,6 +135,31 @@ (int32_t)(((x) & DTRACE_LQUANTIZE_BASEMASK) >> \ DTRACE_LQUANTIZE_BASESHIFT) +#define DTRACE_LLQUANTIZE_STEPSSHIFT 48 +#define DTRACE_LLQUANTIZE_STEPSMASK ((uint64_t)UINT16_MAX << 48) +#define DTRACE_LLQUANTIZE_HMAGSHIFT 32 +#define DTRACE_LLQUANTIZE_HMAGMASK ((uint64_t)UINT16_MAX << 32) +#define DTRACE_LLQUANTIZE_LMAGSHIFT 16 +#define DTRACE_LLQUANTIZE_LMAGMASK ((uint64_t)UINT16_MAX << 16) +#define DTRACE_LLQUANTIZE_FACTORSHIFT 0 +#define DTRACE_LLQUANTIZE_FACTORMASK UINT16_MAX + +#define DTRACE_LLQUANTIZE_STEPS(x) \ + (uint16_t)(((x) & DTRACE_LLQUANTIZE_STEPSMASK) >> \ + DTRACE_LLQUANTIZE_STEPSSHIFT) + +#define DTRACE_LLQUANTIZE_HMAG(x) \ + (uint16_t)(((x) & DTRACE_LLQUANTIZE_HMAGMASK) >> \ + DTRACE_LLQUANTIZE_HMAGSHIFT) + +#define DTRACE_LLQUANTIZE_LMAG(x) \ + (uint16_t)(((x) & DTRACE_LLQUANTIZE_LMAGMASK) >> \ + DTRACE_LLQUANTIZE_LMAGSHIFT) + +#define DTRACE_LLQUANTIZE_FACTOR(x) \ + (uint16_t)(((x) & DTRACE_LLQUANTIZE_FACTORMASK) >> \ + DTRACE_LLQUANTIZE_FACTORSHIFT) + #define DTRACE_USTACK_NFRAMES(x) (uint32_t)((x) & UINT32_MAX) #define DTRACE_USTACK_STRSIZE(x) (uint32_t)((x) >> 32) #define DTRACE_USTACK_ARG(x, y) \ -- 2.50.1