| Line | Branch | Decision | Exec | Source |
|---|---|---|---|---|
| 1 | /** | |||
| 2 | * @file histogram.c | |||
| 3 | * @brief This data structure is used to analyze CPU performance | |||
| 4 | * | |||
| 5 | * Histogram is a data structure which simplifies CPU performance monitoring and trobleshooting by tracking the min, max | |||
| 6 | * and a couple of median values for a series of measurments. | |||
| 7 | * | |||
| 8 | * @date Dec 18, 2013 | |||
| 9 | * @author Andrey Belomutskiy, (c) 2012-2020 | |||
| 10 | */ | |||
| 11 | ||||
| 12 | #include "pch.h" | |||
| 13 | ||||
| 14 | #include <string.h> | |||
| 15 | #include "histogram.h" | |||
| 16 | ||||
| 17 | #if defined(HAS_OS_ACCESS) | |||
| 18 | #error "Unexpected OS ACCESS HERE" | |||
| 19 | #endif | |||
| 20 | ||||
| 21 | #if EFI_HISTOGRAMS || EFI_UNIT_TEST | |||
| 22 | ||||
| 23 | #define H_ACCURACY 0.05 | |||
| 24 | #define H_CONFIDENCE 0.8 | |||
| 25 | #define LONG_MAX_INT 0x7fffffffffffffffL | |||
| 26 | #define SBI_SIZE 1000 | |||
| 27 | ||||
| 28 | static float confidence_bounds[] = { 0.5 - H_CONFIDENCE * 0.5, 0.5, 0.5 + H_CONFIDENCE * 0.5 }; | |||
| 29 | ||||
| 30 | /** | |||
| 31 | * magic curve lookup table | |||
| 32 | */ | |||
| 33 | static int64_t bounds[BOUND_LENGTH] CCM_OPTIONAL; | |||
| 34 | /** | |||
| 35 | * just an optimization - faster lookup for small values | |||
| 36 | */ | |||
| 37 | static int small_bounds_index[SBI_SIZE]; | |||
| 38 | ||||
| 39 | static int initialized = FALSE; | |||
| 40 | ||||
| 41 | /** | |||
| 42 | * @breif Internal histogram data structure | |||
| 43 | */ | |||
| 44 | 1 | void initHistogramsModule(void) { | ||
| 45 | 1 | bounds[0] = 0; | ||
| 46 |
2/2✓ Branch 0 taken 894 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 894 times.
✓ Decision 'false' taken 1 time.
|
895 | for (int i = 1; i < BOUND_LENGTH; i++) { |
| 47 | 894 | int64_t prev = bounds[i - 1]; | ||
| 48 | 894 | int64_t next = prev + (int64_t) ((double) prev * H_ACCURACY); | ||
| 49 |
2/2✓ Branch 0 taken 20 times.
✓ Branch 1 taken 874 times.
|
2/2✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 874 times.
|
894 | if (next == prev) // Ensure minimum step for small numbers. |
| 50 | 20 | next = prev + 1; | ||
| 51 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 864 times.
|
2/2✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 864 times.
|
894 | if (next < prev) // Overflow over Long.MAX_VALUE occurred. |
| 52 | 30 | next = LONG_MAX_INT; | ||
| 53 | 894 | bounds[i] = next; | ||
| 54 | } | |||
| 55 | 1 | bounds[BOUND_LENGTH - 1] = LONG_MAX_INT; | ||
| 56 | ||||
| 57 |
2/2✓ Branch 0 taken 111 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 111 times.
✓ Decision 'false' taken 1 time.
|
112 | for (int i = 0, j = 0; j < SBI_SIZE; i++) |
| 58 |
4/4✓ Branch 1 taken 1001 times.
✓ Branch 2 taken 110 times.
✓ Branch 3 taken 1000 times.
✓ Branch 4 taken 1 time.
|
0/1? Decision couldn't be analyzed.
|
1111 | while (j < bounds[i + 1] && j < SBI_SIZE) |
| 59 | 1000 | small_bounds_index[j++] = i; | ||
| 60 | 1 | initialized = TRUE; | ||
| 61 | 1 | } | ||
| 62 | ||||
| 63 | /** | |||
| 64 | * @brief This internal method is only public so that we can test it. | |||
| 65 | */ | |||
| 66 | 10 | int histogramGetIndex(int64_t value) { | ||
| 67 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
|
10 | efiAssert(ObdCode::CUSTOM_ERR_ASSERT, initialized, "histo initialized", 0); | |
| 68 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 10 times.
|
10 | if (value < 0) |
| 69 | ✗ | return 0; | ||
| 70 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 3 times.
|
2/2✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 3 times.
|
10 | if (value < SBI_SIZE) |
| 71 | 7 | return small_bounds_index[(int) value]; | ||
| 72 | 3 | int l = small_bounds_index[SBI_SIZE - 1]; | ||
| 73 | 3 | int r = BOUND_LENGTH - 1; | ||
| 74 |
1/2✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 27 times.
✗ Decision 'false' not taken.
|
27 | while (l < r) { |
| 75 | 27 | int m = (l + r) >> 1; | ||
| 76 |
2/2✓ Branch 1 taken 17 times.
✓ Branch 2 taken 10 times.
|
2/2✓ Decision 'true' taken 17 times.
✓ Decision 'false' taken 10 times.
|
27 | if (bounds[m] > value) |
| 77 | 17 | r = m - 1; | ||
| 78 |
2/2✓ Branch 1 taken 7 times.
✓ Branch 2 taken 3 times.
|
2/2✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 3 times.
|
10 | else if (bounds[m + 1] <= value) |
| 79 | 7 | l = m + 1; | ||
| 80 | else | |||
| 81 | 3 | return m; | ||
| 82 | } | |||
| 83 | ✗ | return l; | ||
| 84 | } | |||
| 85 | ||||
| 86 | /** | |||
| 87 | * @brief Reset histogram_s to orignal state | |||
| 88 | */ | |||
| 89 | 1 | void initHistogram(histogram_s *h, const char *name) { | ||
| 90 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 time.
|
1 | if (std::strlen(name) > sizeof(h->name) - 1) { |
| 91 | ✗ | firmwareError(ObdCode::ERROR_HISTO_NAME, "Histogram name [%s] too long", name); | ||
| 92 | } | |||
| 93 | 1 | strcpy(h->name, name); | ||
| 94 | 1 | h->total_value = 0; | ||
| 95 | 1 | h->total_count = 0; | ||
| 96 | 1 | memset(h->values, 0, sizeof(h->values)); | ||
| 97 | 1 | } | ||
| 98 | ||||
| 99 | /** | |||
| 100 | * @breif Add a new value into histogram_s | |||
| 101 | */ | |||
| 102 | 7 | void hsAdd(histogram_s *h, int64_t value) { | ||
| 103 | 7 | int index = histogramGetIndex(value); | ||
| 104 | 7 | int count = 1; | ||
| 105 | 7 | h->total_value += value; | ||
| 106 | 7 | h->total_count += count; | ||
| 107 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
|
7 | efiAssertVoid(ObdCode::CUSTOM_ERR_6670, index < BOUND_LENGTH, "histogram issue"); | |
| 108 | ||||
| 109 | 7 | h->values[index] += count; | ||
| 110 | } | |||
| 111 | ||||
| 112 | /** | |||
| 113 | * @brief Prepare histogram report | |||
| 114 | * @note This report should be displayed using 'printHistogram' method | |||
| 115 | */ | |||
| 116 | 4 | int hsReport(histogram_s *h, int* report) { | ||
| 117 | 4 | int index = 0; | ||
| 118 | ||||
| 119 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 time.
|
4 | if (h->total_count <= 5) { |
| 120 |
2/2✓ Branch 0 taken 2685 times.
✓ Branch 1 taken 3 times.
|
2/2✓ Decision 'true' taken 2685 times.
✓ Decision 'false' taken 3 times.
|
2688 | for (int j = 0; j < BOUND_LENGTH; j++) { |
| 121 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2685 times.
|
2/2✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 2685 times.
|
2688 | for (int k = 0; k < h->values[j]; k++) { |
| 122 | 3 | report[index++] = (bounds[j] + bounds[j + 1]) / 2; | ||
| 123 | } | |||
| 124 | } | |||
| 125 | 3 | return index; | ||
| 126 | } | |||
| 127 | ||||
| 128 | 1 | int minIndex = 0; | ||
| 129 |
2/2✓ Branch 0 taken 10 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 1 time.
|
11 | while (h->values[minIndex] == 0) { |
| 130 | 10 | minIndex++; | ||
| 131 | } | |||
| 132 | 1 | report[index++] = h->values[minIndex]; | ||
| 133 | ||||
| 134 | 1 | int64_t acc = 0; | ||
| 135 | // 'acc' is accumulated number of samples in [0, min - 1]. | |||
| 136 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 time.
|
4 | for (int j = 0; j < 3; j++) { |
| 137 | 3 | int64_t k = confidence_bounds[j] * h->total_count; | ||
| 138 | // Always drop at least 1 'non-confident' sample... | |||
| 139 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 2 times.
|
2/2✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 2 times.
|
3 | if (k == 0) { |
| 140 | 1 | k = 1; | ||
| 141 | } | |||
| 142 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 3 times.
|
3 | if (k == h->total_count) { |
| 143 | ✗ | k = h->total_count - 1; | ||
| 144 | } | |||
| 145 | // 'k' is desired number of samples. | |||
| 146 |
2/2✓ Branch 0 taken 51 times.
✓ Branch 1 taken 3 times.
|
2/2✓ Decision 'true' taken 51 times.
✓ Decision 'false' taken 3 times.
|
54 | while (acc + h->values[minIndex] < k) |
| 147 | 51 | acc += h->values[minIndex++]; | ||
| 148 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 2 times.
|
2/2✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 2 times.
|
3 | if (k < h->total_count / 2) // Converge to median (from left). |
| 149 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 time.
|
1 | while (acc + h->values[minIndex] <= k) |
| 150 | ✗ | acc += h->values[minIndex++]; | ||
| 151 | // Now: acc <= k <= acc + st.histogram[min] | |||
| 152 | // And desired number of samples is within [min, min + 1) | |||
| 153 | 3 | float d = bounds[minIndex]; | ||
| 154 |
1/2✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 3 times.
✗ Decision 'false' not taken.
|
3 | if (acc != k) |
| 155 | 3 | d += (bounds[minIndex + 1] - 1 - bounds[minIndex]) * (k - acc) / h->values[minIndex]; | ||
| 156 | 3 | report[index++] = (int) d; | ||
| 157 | } | |||
| 158 | ||||
| 159 | 1 | int maxIndex = BOUND_LENGTH - 1; | ||
| 160 |
2/2✓ Branch 0 taken 784 times.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 784 times.
✓ Decision 'false' taken 1 time.
|
785 | while (h->values[maxIndex] == 0) |
| 161 | 784 | maxIndex--; | ||
| 162 | 1 | int64_t maxValue = bounds[maxIndex + 1] - 1; | ||
| 163 | 1 | report[index++] = maxValue; | ||
| 164 | ||||
| 165 | 1 | return index; | ||
| 166 | } | |||
| 167 | ||||
| 168 | #endif /* EFI_HISTOGRAMS */ | |||
| 169 |