histogram.c File Reference

Detailed Description

This data structure is used to analyze CPU performance.

Histogram is a data structure which simplifies CPU performance monitoring and trobleshooting by tracking the min, max and a couple of median values for a series of measurments.

Date

Dec 18, 2013

Author

Andrey Belomutskiy, (c) 2012-2020

Definition in file histogram.c.

Functions
void	initHistogramsModule (void)
int	histogramGetIndex (int64_t value)
	This internal method is only public so that we can test it. More...
void	initHistogram (histogram_s *h, const char *name)
	Reset histogram_s to orignal state. More...
void	hsAdd (histogram_s *h, int64_t value)
int	hsReport (histogram_s *h, int *report)
	Prepare histogram report. More...

Variables
static float	confidence_bounds [] = { 0.5 - H_CONFIDENCE * 0.5, 0.5, 0.5 + H_CONFIDENCE * 0.5 }
static int64_t bounds [BOUND_LENGTH]	CCM_OPTIONAL
static int	small_bounds_index [SBI_SIZE]
static int	initialized = FALSE

Function Documentation

histogramGetIndex()

int histogramGetIndex

(

int64_t

value

)

This internal method is only public so that we can test it.

Definition at line 65 of file histogram.c.

                                     {
    efiAssert(CUSTOM_ERR_ASSERT, initialized, "histo initialized", 0);
    if (value < 0)
        return 0;
    if (value < SBI_SIZE)
        return small_bounds_index[(int) value];
    int l = small_bounds_index[SBI_SIZE - 1];
    int r = BOUND_LENGTH - 1;
    while (l < r) {
        int m = (l + r) >> 1;
        if (bounds[m] > value)
            r = m - 1;
        else if (bounds[m + 1] <= value)
            l = m + 1;
        else
            return m;
    }
    return l;
}

Referenced by hsAdd().

hsAdd()

void hsAdd	(	histogram_s *	h,
		int64_t	value
	)

@breif Add a new value into histogram_s

Definition at line 101 of file histogram.c.

                                          {
    int index = histogramGetIndex(value);
    int count = 1;
    h->total_value += value;
    h->total_count += count;
    efiAssertVoid(CUSTOM_ERR_6670, index < BOUND_LENGTH, "histogram issue");

    h->values[index] += count;
}

Here is the call graph for this function:

hsReport()

int hsReport	(	histogram_s *	h,
		int *	report
	)

Prepare histogram report.

Note

This report should be displayed using 'printHistogram' method

Definition at line 115 of file histogram.c.

                                          {
    int index = 0;

    if (h->total_count <= 5) {
        for (int j = 0; j < BOUND_LENGTH; j++) {
            for (int k = 0; k < h->values[j]; k++) {
                report[index++] = (bounds[j] + bounds[j + 1]) / 2;
            }
        }
        return index;
    }

    int minIndex = 0;
    while (h->values[minIndex] == 0) {
        minIndex++;
    }
    report[index++] = h->values[minIndex];

    int64_t acc = 0;
    // 'acc' is accumulated number of samples in [0, min - 1].
    for (int j = 0; j < 3; j++) {
        int64_t k = confidence_bounds[j] * h->total_count;
        // Always drop at least 1 'non-confident' sample...
        if (k == 0) {
            k = 1;
        }
        if (k == h->total_count) {
            k = h->total_count - 1;
        }
        // 'k' is desired number of samples.
        while (acc + h->values[minIndex] < k)
            acc += h->values[minIndex++];
        if (k < h->total_count / 2) // Converge to median (from left).
            while (acc + h->values[minIndex] <= k)
                acc += h->values[minIndex++];
        // Now: acc <= k <= acc + st.histogram[min]
        // And desired number of samples is within [min, min + 1)
        float d = bounds[minIndex];
        if (acc != k)
            d += (bounds[minIndex + 1] - 1 - bounds[minIndex]) * (k - acc) / h->values[minIndex];
        report[index++] = (int) d;
    }

    int maxIndex = BOUND_LENGTH - 1;
    while (h->values[maxIndex] == 0)
        maxIndex--;
    int64_t maxValue = bounds[maxIndex + 1] - 1;
    report[index++] = maxValue;

    return index;
}

Referenced by printHistogram().

initHistogram()

void initHistogram	(	histogram_s *	h,
		const char *	name
	)

Reset histogram_s to orignal state.

Definition at line 88 of file histogram.c.

                                                     {
    if (efiStrlen(name) > sizeof(h->name) - 1) {
        firmwareError(ERROR_HISTO_NAME, "Histogram name [%s] too long", name);
    }
    strcpy(h->name, name);
    h->total_value = 0;
    h->total_count = 0;
    memset(h->values, 0, sizeof(h->values));
}

Referenced by initWaveChart().

Here is the call graph for this function:

initHistogramsModule()

void initHistogramsModule

(

void

)

@breif Internal histogram data structure

Definition at line 43 of file histogram.c.

                                {
    bounds[0] = 0;
    for (int i = 1; i < BOUND_LENGTH; i++) {
        int64_t prev = bounds[i - 1];
        int64_t next = prev + (int64_t) ((double) prev * H_ACCURACY);
        if (next == prev) // Ensure minimum step for small numbers.
            next = prev + 1;
        if (next < prev) // Overflow over Long.MAX_VALUE occurred.
            next = LONG_MAX_INT;
        bounds[i] = next;
    }
    bounds[BOUND_LENGTH - 1] = LONG_MAX_INT;

    for (int i = 0, j = 0; j < SBI_SIZE; i++)
        while (j < bounds[i + 1] && j < SBI_SIZE)
            small_bounds_index[j++] = i;
    initialized = TRUE;
}

Referenced by adc_callback_fast_internal().

Variable Documentation

CCM_OPTIONAL

int64_t bounds [BOUND_LENGTH] CCM_OPTIONAL

static

magic curve lookup table

Definition at line 32 of file histogram.c.

confidence_bounds

float confidence_bounds[] = { 0.5 - H_CONFIDENCE * 0.5, 0.5, 0.5 + H_CONFIDENCE * 0.5 }

static

Definition at line 27 of file histogram.c.

Referenced by hsReport().

initialized

int initialized = FALSE

static

Definition at line 38 of file histogram.c.

Referenced by histogramGetIndex(), and initHistogramsModule().

small_bounds_index

int small_bounds_index[SBI_SIZE]

static

just an optimization - faster lookup for small values

Definition at line 36 of file histogram.c.

Referenced by histogramGetIndex(), and initHistogramsModule().

Go to the source code of this file.