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 |