Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2026 Huawei Technologies Co., Ltd
3 : : */
4 : :
5 : : #include "bpf_value_set.h"
6 : :
7 : : #include <rte_debug.h>
8 : :
9 : : /* Helper interval operations and checks. */
10 : :
11 : : /* One of many possible full intervals. */
12 : : static const struct value_set_interval canonical_full_interval = {
13 : : .first = 0,
14 : : .last = UINT64_MAX,
15 : : };
16 : :
17 : : /* Translate ("shift") interval by `offset`. */
18 : : static void
19 : : interval_translate(struct value_set_interval *interval, uint64_t offset)
20 : : {
21 : 18344 : interval->first += offset;
22 : 18344 : interval->last += offset;
23 : : }
24 : :
25 : : /* Return true if the interval includes all possible values. */
26 : : static bool
27 : : interval_is_full(struct value_set_interval interval)
28 : : {
29 : 2164 : return interval.last + 1 == interval.first;
30 : : }
31 : :
32 : : /* Return true if the interval includes `value`. */
33 : : static bool
34 : : interval_contains(struct value_set_interval interval, uint64_t value)
35 : : {
36 : 7304 : return value - interval.first <= interval.last - interval.first;
37 : : }
38 : :
39 : : /* Return true if the interval `lhs` includes all values from `rhs`. */
40 : : static bool
41 : : interval_covers(struct value_set_interval lhs, struct value_set_interval rhs)
42 : : {
43 : : const uint64_t offset = -lhs.first;
44 : : interval_translate(&lhs, offset);
45 : : interval_translate(&rhs, offset);
46 : : RTE_ASSERT(lhs.first == 0);
47 : :
48 [ + - + + ]: 96 : return lhs.last == UINT64_MAX ||
49 [ + + ]: 68 : (lhs.last >= rhs.last && rhs.last >= rhs.first);
50 : : }
51 : :
52 : : /* Return true if the interval includes step from UINT64_MAX to 0. */
53 : : static bool
54 : : interval_crosses_zero(struct value_set_interval interval)
55 : : {
56 : : return interval.last < interval.first;
57 : : }
58 : :
59 : : /* Return number of elements in a non-full elements, 0 for full interval. */
60 : : static uint64_t
61 : : interval_size(struct value_set_interval interval)
62 : : {
63 : 96 : return interval.last - interval.first + 1;
64 : : }
65 : :
66 : : /* Return true if two intervals represent same sets of values. */
67 : : static bool
68 : : intervals_equal(struct value_set_interval lhs, struct value_set_interval rhs)
69 : : {
70 [ - + - - : 1972 : return (interval_is_full(lhs) && interval_is_full(rhs)) ||
+ - ]
71 [ + - ]: 1972 : (lhs.first == rhs.first && lhs.last == rhs.last);
72 : : }
73 : :
74 : : /* Return true if two intervals have common elements. */
75 : : static bool
76 : : intervals_intersect(struct value_set_interval lhs, struct value_set_interval rhs)
77 : : {
78 [ - + - - ]: 7304 : return interval_contains(lhs, rhs.first) || interval_contains(rhs, lhs.first);
79 : : }
80 : :
81 : : /* Return true if `rhs.first` follows `lhs.last` with some gap. Does not check other ends! */
82 : : static bool
83 : : intervals_follow_with_gap(struct value_set_interval lhs, struct value_set_interval rhs)
84 : : {
85 [ + - + + : 26416 : return lhs.last != UINT64_MAX && rhs.first > lhs.last + 1;
- + ]
86 : : }
87 : :
88 : : /* Return true if `(l - o) < (r - o)` for all `(o in origin, l in lhs, r in rhs)`. */
89 : : static bool
90 : : intervals_based_less(struct value_set_interval origin, struct value_set_interval lhs,
91 : : struct value_set_interval rhs)
92 : : {
93 : : /* Translate all intervals for the origin to start at 0. */
94 : : const uint64_t offset = -origin.first;
95 : : interval_translate(&origin, offset);
96 : : interval_translate(&lhs, offset);
97 : : interval_translate(&rhs, offset);
98 : : RTE_ASSERT(origin.first == 0);
99 : :
100 [ + + ]: 7304 : return origin.last <= lhs.first &&
101 [ - + ]: 7220 : lhs.first <= lhs.last &&
102 [ + - - - ]: 7304 : lhs.last < rhs.first &&
103 : : rhs.first <= rhs.last;
104 : : }
105 : :
106 : : /* Return true if `(l - o) <= (r - o)` for all `(o in origin, l in lhs, r in rhs)`. */
107 : : static bool
108 : 7304 : intervals_based_less_or_equal(struct value_set_interval origin, struct value_set_interval lhs,
109 : : struct value_set_interval rhs)
110 : : {
111 : : /* Translate all intervals for the origin to start at 0. */
112 : : const uint64_t offset = -origin.first;
113 : : interval_translate(&origin, offset);
114 : : interval_translate(&lhs, offset);
115 : : interval_translate(&rhs, offset);
116 : : RTE_ASSERT(origin.first == 0);
117 : :
118 : : /* Special cases. */
119 [ + + + + : 7304 : if (origin.last == 0 && lhs.first == 0 && lhs.last == 0)
+ + ]
120 : : return true;
121 [ + + + + : 7013 : if (origin.last == 0 && rhs.first == UINT64_MAX && rhs.last == UINT64_MAX)
- + ]
122 : : return true;
123 [ + + + - : 6834 : if (lhs.first == lhs.last && lhs.last == rhs.first && rhs.first == rhs.last)
+ + ]
124 : : return true;
125 : :
126 [ + - ]: 5036 : return origin.last <= lhs.first &&
127 [ + - ]: 5036 : lhs.first <= lhs.last &&
128 [ + - - + ]: 10072 : lhs.last <= rhs.first &&
129 : : rhs.first <= rhs.last;
130 : : }
131 : :
132 : : /* Append interval rhs to list of intervals in lhs. */
133 : : static void
134 : 28648 : value_set_append(struct value_set *lhs, struct value_set_interval rhs)
135 : : {
136 [ - + ]: 28648 : RTE_VERIFY(lhs->nb_interval < VALUE_SET_NB_INTERVAL_MAX);
137 [ + + + - : 28824 : RTE_VERIFY(lhs->nb_interval == 0 ||
- + ]
138 : : intervals_follow_with_gap(lhs->interval[lhs->nb_interval - 1], rhs));
139 : 28648 : lhs->interval[lhs->nb_interval++] = rhs;
140 : 28648 : }
141 : :
142 : : /*
143 : : * Helper operations on noncyclic value set and intervals.
144 : : * Noncyclic means no interval crosses zero,
145 : : * but in return last value set interval may touch first.
146 : : */
147 : :
148 : : static struct value_set
149 : 13448 : noncyclic_value_set_union_interval(const struct value_set *lhs, const struct value_set_interval rhs)
150 : : {
151 : 13448 : struct value_set result = {};
152 : : uint32_t index = 0;
153 : :
154 : : RTE_ASSERT(lhs->nb_interval == 0 ||
155 : : !interval_crosses_zero(lhs->interval[lhs->nb_interval - 1]));
156 : : RTE_ASSERT(!interval_crosses_zero(rhs));
157 : :
158 : : /* Append to result all lhs intervals preceding rhs. */
159 [ + - ]: 13448 : for (; index != lhs->nb_interval; ++index) {
160 [ + + ]: 13448 : const struct value_set_interval lhs_interval = lhs->interval[index];
161 [ - + ]: 13448 : if (!intervals_follow_with_gap(lhs_interval, rhs))
162 : : break;
163 : :
164 : 0 : value_set_append(&result, lhs_interval);
165 : : }
166 : :
167 : : /* Appendinterval joined from rhs and all lhs intervals intersecting or touching it. */
168 : 13448 : struct value_set_interval joint_interval = rhs;
169 [ + + ]: 26720 : for (; index != lhs->nb_interval; ++index) {
170 [ + + ]: 13448 : const struct value_set_interval lhs_interval = lhs->interval[index];
171 [ + + ]: 13448 : if (intervals_follow_with_gap(rhs, lhs_interval))
172 : : break;
173 : :
174 : 13272 : joint_interval.first = RTE_MIN(joint_interval.first, lhs_interval.first);
175 : 13272 : joint_interval.last = RTE_MAX(joint_interval.last, lhs_interval.last);
176 : : }
177 : 13448 : value_set_append(&result, joint_interval);
178 : :
179 : : /* Append to result all lhs intervals following rhs. */
180 [ + + ]: 13624 : for (; index != lhs->nb_interval; ++index)
181 : 176 : value_set_append(&result, lhs->interval[index]);
182 : :
183 : 13448 : return result;
184 : : }
185 : :
186 : : /* Make "normal" maximal disjoint interval value set out of noncyclic one. */
187 : : static struct value_set
188 : 13448 : value_set_from_noncyclic(const struct value_set *set)
189 : : {
190 : 13448 : struct value_set result = {};
191 : : uint32_t index = 0;
192 : :
193 [ + + ]: 13448 : if (set->nb_interval <= 1)
194 : 13272 : return *set;
195 : :
196 : 176 : struct value_set_interval last_interval = set->interval[set->nb_interval - 1];
197 [ + - + - ]: 176 : if (last_interval.last == UINT64_MAX && set->interval[0].first == 0) {
198 : : /* Join first interval with the last one instead of copying it. */
199 : 176 : last_interval.last = set->interval[0].last;
200 : : ++index;
201 : : }
202 : :
203 [ - + ]: 176 : for (; index != set->nb_interval - 1; ++index)
204 : 0 : value_set_append(&result, set->interval[index]);
205 : :
206 : 176 : value_set_append(&result, last_interval);
207 : :
208 : 176 : return result;
209 : : }
210 : :
211 : : /* Make lhs a union of lhs and rhs. */
212 : : static void
213 : 28296 : value_set_union_interval(struct value_set *lhs, const struct value_set_interval rhs)
214 : : {
215 : : struct value_set temp;
216 : :
217 [ + + ]: 28296 : if (value_set_is_empty(lhs)) {
218 : 14848 : value_set_append(lhs, rhs);
219 : 14848 : return;
220 : : }
221 : :
222 : 13448 : struct value_set_interval *const last_interval = &lhs->interval[lhs->nb_interval - 1];
223 : : const bool last_interval_crossed_zero = interval_crosses_zero(*last_interval);
224 : : const uint64_t wrapping_last = last_interval->last;
225 : :
226 [ - + ]: 13448 : if (last_interval_crossed_zero)
227 : : /* Make value set noncyclic by removing crossing part of last interval. */
228 : 0 : last_interval->last = UINT64_MAX;
229 : :
230 [ - + ]: 13448 : if (interval_crosses_zero(rhs)) {
231 : : /* Add parts before and after zero separately. */
232 : 0 : temp = noncyclic_value_set_union_interval(lhs,
233 : 0 : (struct value_set_interval){
234 : : .first = rhs.first,
235 : : .last = UINT64_MAX,
236 : : });
237 : 0 : temp = noncyclic_value_set_union_interval(lhs,
238 : 0 : (struct value_set_interval){
239 : : .first = 0,
240 : : .last = rhs.last,
241 : : });
242 : : } else
243 : 13448 : temp = noncyclic_value_set_union_interval(lhs, rhs);
244 : :
245 [ - + ]: 13448 : if (last_interval_crossed_zero)
246 : : /* Restore previously removed part. */
247 : 0 : temp = noncyclic_value_set_union_interval(&temp,
248 : 0 : (struct value_set_interval){
249 : : .first = 0,
250 : : .last = wrapping_last,
251 : : });
252 : :
253 : 13448 : *lhs = value_set_from_noncyclic(&temp);
254 : : }
255 : :
256 : : /* Set `lhs` to the set of possible sums between values from `lhs` and `rhs`. */
257 : : static void
258 : 96 : value_set_add_interval(struct value_set *lhs, struct value_set_interval rhs)
259 : : {
260 : 96 : const struct value_set temp = *lhs;
261 : 96 : lhs->nb_interval = 0;
262 : :
263 [ + + ]: 192 : for (uint32_t index = 0; index != temp.nb_interval; ++index) {
264 : 96 : const struct value_set_interval interval = temp.interval[index];
265 [ + - + - ]: 96 : if (interval_is_full(rhs) || interval_is_full(interval) ||
266 [ - + ]: 96 : interval_size(interval) > UINT64_MAX - interval_size(rhs)) {
267 : 0 : value_set_append(lhs, canonical_full_interval);
268 : : return;
269 : : }
270 : : }
271 : :
272 [ + + ]: 192 : for (uint32_t index = 0; index != temp.nb_interval; ++index)
273 : 96 : value_set_union_interval(lhs, (struct value_set_interval){
274 : : /* Checked sizes above, so these interval expansions won't overflow. */
275 : 96 : .first = temp.interval[index].first + rhs.first,
276 : 96 : .last = temp.interval[index].last + rhs.last,
277 : : });
278 : : }
279 : :
280 : : struct value_set
281 : 29120 : value_set_singleton(uint64_t value)
282 : : {
283 : 29120 : return value_set_contiguous(value, value);
284 : : }
285 : :
286 : : struct value_set
287 : 29168 : value_set_contiguous(uint64_t first, uint64_t last)
288 : : {
289 : 29168 : return (struct value_set){
290 : : .nb_interval = 1,
291 : : .interval = {
292 : : { .first = first, .last = last },
293 : : },
294 : : };
295 : : }
296 : :
297 : : struct value_set
298 : 14752 : value_set_from_pair(uint64_t first1, uint64_t last1, uint64_t first2, uint64_t last2)
299 : : {
300 : 14752 : struct value_set result = {};
301 : :
302 [ + + ]: 14752 : if (first1 - first2 <= last2 - first2)
303 : : /* Interval 1 starts within interval 2. */
304 : 14096 : value_set_union_interval(&result, (struct value_set_interval){
305 : : .first = first1,
306 : 14096 : .last = first1 + RTE_MIN(last1 - first1, last2 - first1),
307 : : });
308 : :
309 [ + + ]: 14752 : if (first2 - first1 <= last1 - first1)
310 : : /* Interval 2 starts within interval 1. */
311 : 14104 : value_set_union_interval(&result, (struct value_set_interval){
312 : : .first = first2,
313 : 14104 : .last = first2 + RTE_MIN(last2 - first2, last1 - first2),
314 : : });
315 : :
316 : 14752 : return result;
317 : : }
318 : :
319 : : bool
320 : 28296 : value_set_is_empty(const struct value_set *set)
321 : : {
322 : 28296 : return set->nb_interval == 0;
323 : : }
324 : :
325 : : bool
326 : 7304 : value_set_is_singleton(const struct value_set *set)
327 : : {
328 [ + - + + ]: 7304 : return set->nb_interval == 1 && interval_size(set->interval[0]) == 1;
329 : : }
330 : :
331 : : bool
332 : 1972 : value_sets_equal(const struct value_set *lhs, const struct value_set *rhs)
333 : : {
334 [ + - ]: 1972 : if (lhs->nb_interval != rhs->nb_interval)
335 : : return false;
336 : :
337 [ + + ]: 3944 : for (uint32_t index = 0; index != lhs->nb_interval; ++index)
338 [ + - ]: 1972 : if (!intervals_equal(lhs->interval[index], rhs->interval[index]))
339 : : return false;
340 : :
341 : : return true;
342 : : }
343 : :
344 : : bool
345 : 7304 : value_sets_intersect(const struct value_set *lhs, const struct value_set *rhs)
346 : : {
347 [ + - ]: 7304 : for (uint32_t lhs_index = 0; lhs_index != lhs->nb_interval; ++lhs_index)
348 [ + - ]: 7304 : for (uint32_t rhs_index = 0; rhs_index != rhs->nb_interval; ++rhs_index)
349 [ - + ]: 7304 : if (intervals_intersect(lhs->interval[lhs_index], rhs->interval[rhs_index]))
350 : : return true;
351 : :
352 : : return false;
353 : : }
354 : :
355 : : bool
356 : 96 : value_set_is_covered_by_contiguous(const struct value_set *lhs, uint64_t first, uint64_t last)
357 : : {
358 : : const struct value_set_interval rhs = { .first = first, .last = last };
359 [ + + ]: 144 : for (uint32_t lhs_index = 0; lhs_index != lhs->nb_interval; ++lhs_index)
360 [ + + ]: 96 : if (!interval_covers(rhs, lhs->interval[lhs_index]))
361 : : return false;
362 : :
363 : : return true;
364 : : }
365 : :
366 : : bool
367 : 7304 : value_sets_based_less(const struct value_set *origin, const struct value_set *lhs,
368 : : const struct value_set *rhs)
369 : : {
370 [ + - ]: 7304 : for (uint32_t origin_index = 0; origin_index != origin->nb_interval; ++origin_index)
371 [ + - ]: 7304 : for (uint32_t lhs_index = 0; lhs_index != lhs->nb_interval; ++lhs_index)
372 [ + - ]: 7304 : for (uint32_t rhs_index = 0; rhs_index != rhs->nb_interval; ++rhs_index)
373 [ - + ]: 7304 : if (!intervals_based_less(origin->interval[origin_index],
374 : : lhs->interval[lhs_index], rhs->interval[rhs_index]))
375 : : return false;
376 : : return true;
377 : : }
378 : :
379 : : bool
380 : 7304 : value_sets_based_less_or_equal(const struct value_set *origin, const struct value_set *lhs,
381 : : const struct value_set *rhs)
382 : : {
383 [ + + ]: 14608 : for (uint32_t origin_index = 0; origin_index != origin->nb_interval; ++origin_index)
384 [ + + ]: 14608 : for (uint32_t lhs_index = 0; lhs_index != lhs->nb_interval; ++lhs_index)
385 [ + + ]: 14608 : for (uint32_t rhs_index = 0; rhs_index != rhs->nb_interval; ++rhs_index)
386 [ + - ]: 7304 : if (!intervals_based_less_or_equal(origin->interval[origin_index],
387 : : lhs->interval[lhs_index], rhs->interval[rhs_index]))
388 : : return false;
389 : : return true;
390 : : }
391 : :
392 : : void
393 : 18344 : value_set_translate(struct value_set *set, uint64_t offset)
394 : : {
395 [ + + ]: 36688 : for (uint32_t index = 0; index != set->nb_interval; ++index)
396 : : interval_translate(&set->interval[index], offset);
397 : 18344 : }
398 : :
399 : : void
400 : 96 : value_set_add_contiguous(struct value_set *lhs, uint64_t first, uint64_t last)
401 : : {
402 : 96 : value_set_add_interval(lhs, (struct value_set_interval){ .first = first, .last = last });
403 : 96 : }
|
