On Mon, 18 Dec 2023, Crystal Wood wrote:
> The new code is also intended to be used by cyclicdeadline, and possibly
> oslat and other tests.
>
> Signed-off-by: Crystal Wood <crwood@xxxxxxxxxx>
> ---
> v2: Fix some checkpatch warnings
>
> Makefile | 3 +-
> src/cyclictest/cyclictest.c | 82 +++++------------
> src/include/histogram.h | 42 +++++++++
> src/lib/histogram.c | 172 ++++++++++++++++++++++++++++++++++++
> 4 files changed, 239 insertions(+), 60 deletions(-)
> create mode 100644 src/include/histogram.h
> create mode 100644 src/lib/histogram.c
>
> diff --git a/Makefile b/Makefile
> index ad481a73cf93..9502adea49cf 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -178,7 +178,8 @@ oslat: $(OBJDIR)/oslat.o $(OBJDIR)/librttest.a $(OBJDIR)/librttestnuma.a
> %.8.bz2: %.8
> bzip2 -c $< > $@
>
> -LIBOBJS =$(addprefix $(OBJDIR)/,rt-error.o rt-get_cpu.o rt-sched.o rt-utils.o)
> +LIBOBJS =$(addprefix $(OBJDIR)/,rt-error.o rt-get_cpu.o rt-sched.o rt-utils.o \
> + histogram.o)
> $(OBJDIR)/librttest.a: $(LIBOBJS)
> $(AR) rcs $@ $^
>
> diff --git a/src/cyclictest/cyclictest.c b/src/cyclictest/cyclictest.c
> index 93ce201e9fca..6169170fc66d 100644
> --- a/src/cyclictest/cyclictest.c
> +++ b/src/cyclictest/cyclictest.c
> @@ -35,6 +35,7 @@
> #include "rt-utils.h"
> #include "rt-numa.h"
> #include "rt-error.h"
> +#include "histogram.h"
>
> #include <bionic.h>
>
> @@ -133,16 +134,13 @@ struct thread_stat {
> double avg;
> long *values;
> long *smis;
> - long *hist_array;
> - long *outliers;
> + struct histogram *hist;
> pthread_t thread;
> int threadstarted;
> int tid;
> long reduce;
> long redmax;
> long cycleofmax;
> - long hist_overflow;
> - long num_outliers;
> unsigned long smi_count;
> };
>
> @@ -216,6 +214,7 @@ static char jsonfile[MAX_PATH];
>
> static struct thread_param **parameters;
> static struct thread_stat **statistics;
> +static struct histoset hset;
>
> static void print_stat(FILE *fp, struct thread_param *par, int index, int verbose, int quiet);
> static void rstat_print_stat(struct thread_param *par, int index, int verbose, int quiet);
> @@ -777,15 +776,8 @@ static void *timerthread(void *param)
> }
>
> /* Update the histogram */
> - if (histogram) {
> - if (diff >= histogram) {
> - stat->hist_overflow++;
> - if (stat->num_outliers < histogram)
> - stat->outliers[stat->num_outliers++] = stat->cycles;
> - } else {
> - stat->hist_array[diff]++;
> - }
> - }
> + if (histogram)
> + hist_sample(stat->hist, diff);
>
> stat->cycles++;
>
> @@ -1422,19 +1414,13 @@ static void print_hist(struct thread_param *par[], int nthreads)
>
> fprintf(fd, "# Histogram\n");
> for (i = 0; i < histogram; i++) {
> - unsigned long long int allthreads = 0;
> + unsigned long flags = 0;
>
> fprintf(fd, "%06d ", i);
>
> - for (j = 0; j < nthreads; j++) {
> - unsigned long curr_latency=par[j]->stats->hist_array[i];
> - fprintf(fd, "%06lu", curr_latency);
> - if (j < nthreads - 1)
> - fprintf(fd, "\t");
> - allthreads += curr_latency;
> - }
> - if (histofall && nthreads > 1)
> - fprintf(fd, "\t%06llu", allthreads);
> + if (histofall)
> + flags |= HSET_PRINT_SUM;
> + hset_print_bucket(&hset, fd, i, flags);
> fprintf(fd, "\n");
> }
> fprintf(fd, "# Min Latencies:");
> @@ -1459,8 +1445,8 @@ static void print_hist(struct thread_param *par[], int nthreads)
> fprintf(fd, "# Histogram Overflows:");
> alloverflows = 0;
> for (j = 0; j < nthreads; j++) {
> - fprintf(fd, " %05lu", par[j]->stats->hist_overflow);
> - alloverflows += par[j]->stats->hist_overflow;
> + fprintf(fd, " %05lu", par[j]->stats->hist->oflow_count);
> + alloverflows += par[j]->stats->hist->oflow_count;
> }
> if (histofall && nthreads > 1)
> fprintf(fd, " %05lu", alloverflows);
> @@ -1468,11 +1454,8 @@ static void print_hist(struct thread_param *par[], int nthreads)
>
> fprintf(fd, "# Histogram Overflow at cycle number:\n");
> for (i = 0; i < nthreads; i++) {
> - fprintf(fd, "# Thread %d:", i);
> - for (j = 0; j < par[i]->stats->num_outliers; j++)
> - fprintf(fd, " %05lu", par[i]->stats->outliers[j]);
> - if (par[i]->stats->num_outliers < par[i]->stats->hist_overflow)
> - fprintf(fd, " # %05lu others", par[i]->stats->hist_overflow - par[i]->stats->num_outliers);
> + fprintf(fd, "# Thread %d: ", i);
> + hist_print_oflows(par[i]->stats->hist, fd);
> fprintf(fd, "\n");
> }
> if (smi) {
> @@ -1788,8 +1771,7 @@ rstat_err:
> static void write_stats(FILE *f, void *data __attribute__ ((unused)))
> {
> struct thread_param **par = parameters;
> - int i, j;
> - unsigned comma;
> + int i;
> struct thread_stat *s;
>
> fprintf(f, " \"num_threads\": %d,\n", num_threads);
> @@ -1800,15 +1782,7 @@ static void write_stats(FILE *f, void *data __attribute__ ((unused)))
>
> fprintf(f, " \"histogram\": {");
> s = par[i]->stats;
> - for (j = 0, comma = 0; j < histogram; j++) {
> - if (s->hist_array[j] == 0)
> - continue;
> - fprintf(f, "%s", comma ? ",\n" : "\n");
> - fprintf(f, " \"%u\": %ld", j, s->hist_array[j]);
> - comma = 1;
> - }
> - if (comma)
> - fprintf(f, "\n");
> + hist_print_json(par[i]->stats->hist, f);
> fprintf(f, " },\n");
> fprintf(f, " \"cycles\": %ld,\n", s->cycles);
> fprintf(f, " \"min\": %ld,\n", s->min);
> @@ -1991,6 +1965,10 @@ int main(int argc, char **argv)
> /* Set-up shm */
> rstat_setup();
>
> + if (histogram && hset_init(&hset, num_threads, 1, histogram, histogram))
> + fatal("failed to allocate histogram of size %d for %d threads\n",
> + histogram, num_threads);
> +
> parameters = calloc(num_threads, sizeof(struct thread_param *));
> if (!parameters)
> goto out;
> @@ -2066,18 +2044,8 @@ int main(int argc, char **argv)
> fatal("error allocating thread status struct for thread %d\n", i);
> memset(stat, 0, sizeof(struct thread_stat));
>
> - /* allocate the histogram if requested */
> - if (histogram) {
> - int bufsize = histogram * sizeof(long);
> -
> - stat->hist_array = threadalloc(bufsize, node);
> - stat->outliers = threadalloc(bufsize, node);
> - if (stat->hist_array == NULL || stat->outliers == NULL)
> - fatal("failed to allocate histogram of size %d on node %d\n",
> - histogram, i);
> - memset(stat->hist_array, 0, bufsize);
> - memset(stat->outliers, 0, bufsize);
> - }
> + if (histogram)
> + stat->hist = &hset.histos[i];
>
> if (verbose) {
> int bufsize = VALBUF_SIZE * sizeof(long);
> @@ -2215,13 +2183,8 @@ int main(int argc, char **argv)
> if (trigger)
> trigger_print();
>
> - if (histogram) {
> + if (histogram)
> print_hist(parameters, num_threads);
> - for (i = 0; i < num_threads; i++) {
> - threadfree(statistics[i]->hist_array, histogram*sizeof(long), parameters[i]->node);
> - threadfree(statistics[i]->outliers, histogram*sizeof(long), parameters[i]->node);
> - }
> - }
>
> if (tracelimit) {
> print_tids(parameters, num_threads);
> @@ -2263,5 +2226,6 @@ int main(int argc, char **argv)
> if (rstat_fd >= 0)
> shm_unlink(shm_name);
>
> + hset_destroy(&hset);
> exit(ret);
> }
> diff --git a/src/include/histogram.h b/src/include/histogram.h
> new file mode 100644
> index 000000000000..c7aba68ffb99
> --- /dev/null
> +++ b/src/include/histogram.h
> @@ -0,0 +1,42 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +#include <stdint.h>
> +#include <stdio.h>
> +
> +struct histogram {
> + unsigned long *buckets;
> + unsigned long width; // interval covered by one bucket
> + unsigned long num; // number of buckets
> + unsigned long events; // number of events logged
> +
> + unsigned long *oflows; // events when overflow happened
> + unsigned long oflow_bufsize; // number of overflows that can be logged
> + unsigned long oflow_count; // number of events that overflowed
> + uint64_t oflow_magnitude; // sum of how many buckets overflowed by
> +};
> +
> +struct histoset {
> + struct histogram *histos; // Group of related histograms (e.g. per cpu)
> + struct histogram *sum; // Accumulates events from all histos
> + unsigned long num_histos; // Not including sum
> + unsigned long num_buckets;
> +};
> +
> +#define HIST_OVERFLOW 1
> +#define HIST_OVERFLOW_MAG 2
> +#define HIST_OVERFLOW_LOG 4
> +
> +int hist_init(struct histogram *h, unsigned long width, unsigned long num);
> +int hist_init_oflow(struct histogram *h, unsigned long num);
> +void hist_destroy(struct histogram *h);
> +int hist_sample(struct histogram *h, uint64_t sample);
> +
> +#define HSET_PRINT_SUM 1
> +#define HSET_PRINT_JSON 2
> +
> +int hset_init(struct histoset *hs, unsigned long histos, unsigned long bucket_width,
> + unsigned long num_buckets, unsigned long overflow);
> +void hset_destroy(struct histoset *hs);
> +void hset_print_bucket(struct histoset *hs, FILE *f, unsigned long bucket,
> + unsigned long flags);
> +void hist_print_json(struct histogram *h, FILE *f);
> +void hist_print_oflows(struct histogram *h, FILE *f);
> diff --git a/src/lib/histogram.c b/src/lib/histogram.c
> new file mode 100644
> index 000000000000..35a9d604da86
> --- /dev/null
> +++ b/src/lib/histogram.c
> @@ -0,0 +1,172 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/*
> + * Latency histograms
> + *
> + * Copyright 2023 Red Hat Inc.
> + */
> +
> +#include <errno.h>
> +#include <stdbool.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include "histogram.h"
> +
> +int hist_init(struct histogram *h, unsigned long width, unsigned long num)
> +{
> + memset(h, 0, sizeof(*h));
> + h->width = width;
> + h->num = num;
> +
> + h->buckets = calloc(num, sizeof(unsigned long));
> + if (!h->buckets)
> + return -ENOMEM;
> +
> + return 0;
> +}
> +
> +int hist_init_oflow(struct histogram *h, unsigned long num)
> +{
> + h->oflow_bufsize = num;
> + h->oflows = calloc(num, sizeof(unsigned long));
> + if (!h->oflows)
> + return -ENOMEM;
> +
> + return 0;
> +}
> +
> +void hist_destroy(struct histogram *h)
> +{
> + free(h->oflows);
> + h->oflows = NULL;
> + free(h->buckets);
> + h->buckets = NULL;
> +}
> +
> +int hist_sample(struct histogram *h, uint64_t sample)
> +{
> + unsigned long bucket = sample / h->width;
> + unsigned long extra;
> + unsigned long event = h->events++;
> + int ret;
> +
> + if (bucket < h->num) {
> + h->buckets[bucket]++;
> + return 0;
> + }
> +
> + ret = HIST_OVERFLOW;
> + extra = bucket - h->num;
> + if (h->oflow_magnitude + extra > h->oflow_magnitude)
> + h->oflow_magnitude += extra;
> + else
> + ret |= HIST_OVERFLOW_MAG;
> +
> + if (h->oflows) {
> + if (h->oflow_count < h->oflow_bufsize)
> + h->oflows[h->oflow_count] = event;
> + else
> + ret |= HIST_OVERFLOW_LOG;
> + }
> +
> + h->oflow_count++;
> + return ret;
> +}
> +
> +int hset_init(struct histoset *hs, unsigned long num_histos,
> + unsigned long bucket_width, unsigned long num_buckets,
> + unsigned long overflow)
> +{
> + unsigned long i;
> +
> + if (num_histos == 0)
> + return -EINVAL;
> +
> + hs->num_histos = num_histos;
> + hs->num_buckets = num_buckets;
> + hs->histos = calloc(num_histos, sizeof(struct histogram));
> + if (!hs->histos)
> + return -ENOMEM;
> +
> + for (i = 0; i < num_histos; i++) {
> + if (hist_init(&hs->histos[i], bucket_width, num_buckets))
> + goto fail;
> + if (overflow && hist_init_oflow(&hs->histos[i], overflow))
> + goto fail;
> + }
> +
> + return 0;
> +
> +fail:
> + hset_destroy(hs);
> + return -ENOMEM;
> +}
> +
> +void hset_destroy(struct histoset *hs)
> +{
> + unsigned long i;
> +
> + if (hs->histos) {
> + for (i = 0; i < hs->num_histos; i++)
> + hist_destroy(&hs->histos[i]);
> + }
> +
> + free(hs->histos);
> + hs->histos = NULL;
> +}
> +
> +void hset_print_bucket(struct histoset *hs, FILE *f, unsigned long bucket,
> + unsigned long flags)
> +{
> + unsigned long long sum = 0;
> + unsigned long i;
> +
> + if (bucket >= hs->num_buckets)
> + return;
> +
> + for (i = 0; i < hs->num_histos; i++) {
> + unsigned long val = hs->histos[i].buckets[bucket];
> +
> + sum += val;
> + if (i != 0)
> + fprintf(f, "\t");
> + fprintf(f, "%06lu", val);
> + }
> +
> + if (flags & HSET_PRINT_SUM)
> + fprintf(f, "\t%06llu", sum);
> +}
> +
> +void hist_print_json(struct histogram *h, FILE *f)
> +{
> + unsigned long i;
> + bool comma = false;
> +
> + for (i = 0; i < h->num; i++) {
> + unsigned long val = h->buckets[i];
> +
> + if (val != 0) {
> + if (comma)
> + fprintf(f, ",");
> + fprintf(f, "\n \"%lu\": %lu", i, val);
> + comma = true;
> + }
> + }
> +
> + fprintf(f, "\n");
> +}
> +
> +void hist_print_oflows(struct histogram *h, FILE *f)
> +{
> + unsigned long i;
> +
> + for (i = 0; i < h->oflow_count; i++) {
> + if (i >= h->oflow_bufsize)
> + break;
> + if (i != 0)
> + fprintf(f, " ");
> + fprintf(f, "%05lu", h->oflows[i]);
> + }
> +
> + if (i >= h->oflow_bufsize)
> + fprintf(f, " # %05lu others", h->oflow_count - h->oflow_bufsize);
> +}
> --
> 2.43.0
>
>
>
Signed-off-by: John Kacur <jkacur@xxxxxxxxxx>
