GCC Code Coverage Report


Directory: ./
File: firmware/util/histogram.cpp
Date: 2025-10-03 00:57:22
Warnings: 1 unchecked decisions!
Coverage Exec Excl Total
Lines: 93.8% 75 0 80
Functions: 100.0% 5 0 5
Branches: 84.6% 44 0 52
Decisions: 82.6% 38 - 46

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