20179964478

Committed 28 Oct 2025 07:58PM UTC coverage: 95.996% (+0.7%) from 95.331%

Build # 20179964478

Build Type

push

github

Committed by

web-flow

Commit Message

Add support for correctly handling BTF data with cycles (#173)

* Add support for handling loops in BTF data

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Additional tests

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Fix infinite loop in dependency_order

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Refactoring for code reuse

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Remove dead code

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Remove warning

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Add more test cases

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Remove warnings

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* PR feedback

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Debugging CI/CD failure

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* Fix ubsan failure

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

* PR feedback

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>

---------

Signed-off-by: Alan Jowett <alan.jowett@microsoft.com>
Co-authored-by: Alan Jowett <alan.jowett@microsoft.com>

Coverage Stats

890 of 935 new or added lines in 6 files covered. (95.19%)

1 existing line in 1 file now uncovered.

2182 of 2273 relevant lines covered (96.0%)

1576.27 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.8

/libbtf/cycle_detector.h

// Copyright (c) Prevail Verifier contributors.
// SPDX-License-Identifier: MIT

#pragma once

#include "btf.h"
#include <functional>
#include <set>
#include <stdexcept>

namespace libbtf {

/**
 * @brief A generic cycle detection utility for BTF type traversal.
 *
 * This class provides a reusable way to detect cycles when traversing
 * BTF type graphs, eliminating code duplication across the codebase.
 */
class cycle_detector {
public:
  using type_id = btf_type_id;

  /**
   * @brief Construct a new cycle detector object
   */
  cycle_detector() = default;

  /**
   * @brief Check if a type ID would create a cycle
   *
   * @param id The type ID to check
   * @return true if adding this ID would create a cycle, false otherwise
   */
  bool would_create_cycle(type_id id) const {
    return visited_.find(id) != visited_.end();
  }

  /**
   * @brief Add a type ID to the visited set
   *
   * @param id The type ID to mark as visited
   * @return true if the ID was newly added, false if it was already visited
   * (cycle detected)
   */
  bool mark_visited(type_id id) {
    if (would_create_cycle(id)) {
      return false;
    }
    visited_.insert(id);
    return true;
  }

  /**
   * @brief Remove a type ID from the visited set (for backtracking)
   *
   * @param id The type ID to unmark
   */
  void unmark_visited(type_id id) { visited_.erase(id); }

  /**
   * @brief Get the current visited set (for debugging or advanced usage)
   *
   * @return const reference to the visited set
   */
  const std::set<type_id> &get_visited() const { return visited_; }

  /**
   * @brief Clear all visited markers
   */
  void clear() { visited_.clear(); }

  /**
   * @brief Execute a function with automatic cycle detection and cleanup
   *
   * This RAII-style method automatically handles marking/unmarking the type ID
   * and provides cycle detection. If a cycle is detected, the on_cycle handler
   * is called instead of the main function.
   *
   * @tparam T Return type of the functions
   * @param id The type ID to process
   * @param func The main function to execute if no cycle is detected
   * @param on_cycle The function to execute if a cycle is detected
   * @param backtrack Whether to automatically unmark the ID after processing
   * (default: true)
   * @return The result of either func or on_cycle
   */
  template <typename T>
  T with_cycle_detection(type_id id, std::function<T()> func,
                         std::function<T()> on_cycle, bool backtrack = true) {
    if (would_create_cycle(id)) {
      return on_cycle();
    }

    visited_.insert(id);
    T result;
    try {
      result = func();
    } catch (...) {
      if (backtrack) {
        visited_.erase(id);
      }
      throw;
    }

    if (backtrack) {
      visited_.erase(id);
    }

    return result;
  }

private:
  std::set<type_id> visited_;
};

/**
 * @brief RAII helper for automatic visited tracking
 *
 * This class automatically marks a type as visited in its constructor
 * and unmarks it in its destructor, ensuring proper cleanup even
 * in the presence of exceptions.
 */
class scoped_visit {
public:
  /**
   * @brief Construct and mark a type as visited
   *
   * @param detector The cycle detector to use
   * @param id The type ID to mark as visited
   * @throws std::runtime_error if a cycle would be created
   */
  scoped_visit(cycle_detector &detector, btf_type_id id)
      : detector_(detector), id_(id), marked_(false) {
    if (!detector_.mark_visited(id)) {
      throw std::runtime_error("Cycle detected for type ID " +
                               std::to_string(id));
    }
    marked_ = true;
  }

  /**
   * @brief Construct without throwing on cycle detection
   *
   * @param detector The cycle detector to use
   * @param id The type ID to mark as visited
   * @param no_throw Tag to indicate no exception should be thrown
   * @return true if successfully marked, false if cycle detected
   */
  scoped_visit(cycle_detector &detector, btf_type_id id, std::nothrow_t)
      : detector_(detector), id_(id) {
    marked_ = detector_.mark_visited(id);
  }

  /**
   * @brief Destructor automatically unmarks the type
   */
  ~scoped_visit() {
    if (marked_) {
      detector_.unmark_visited(id_);
    }
  }

  /**
   * @brief Check if the type was successfully marked as visited
   *
   * @return true if marked (no cycle), false if cycle was detected
   */
  bool is_marked() const { return marked_; }

  // Non-copyable, non-movable to prevent issues with RAII
  scoped_visit(const scoped_visit &) = delete;
  scoped_visit &operator=(const scoped_visit &) = delete;
  scoped_visit(scoped_visit &&) = delete;
  scoped_visit &operator=(scoped_visit &&) = delete;

private:
  cycle_detector &detector_;
  btf_type_id id_;
  bool marked_;
};

} // namespace libbtf

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3
4	#pragma once
5
6	#include "btf.h"
7	#include <functional>
8	#include <set>
9	#include <stdexcept>
10
11	namespace libbtf {
12
13	/**
14	* @brief A generic cycle detection utility for BTF type traversal.
15	*
16	* This class provides a reusable way to detect cycles when traversing
17	* BTF type graphs, eliminating code duplication across the codebase.
18	*/
19	class cycle_detector {	545✔
20	public:
21	using type_id = btf_type_id;
22
23	/**
24	* @brief Construct a new cycle detector object
25	*/
26	cycle_detector() = default;	568✔
27
28	/**
29	* @brief Check if a type ID would create a cycle
30	*
31	* @param id The type ID to check
32	* @return true if adding this ID would create a cycle, false otherwise
33	*/
34	bool would_create_cycle(type_id id) const {	22,032✔
35	return visited_.find(id) != visited_.end();	32,046✔
36	}
37
38	/**
39	* @brief Add a type ID to the visited set
40	*
41	* @param id The type ID to mark as visited
42	* @return true if the ID was newly added, false if it was already visited
43	* (cycle detected)
44	*/
45	bool mark_visited(type_id id) {	22,414✔
46	if (would_create_cycle(id)) {	33,621✔
47	return false;	5✔
48	}
49	visited_.insert(id);	11,202✔
50	return true;	22,404✔
51	}
52
53	/**
54	* @brief Remove a type ID from the visited set (for backtracking)
55	*
56	* @param id The type ID to unmark
57	*/
58	void unmark_visited(type_id id) { visited_.erase(id); }	11,167✔
59
60	/**
61	* @brief Get the current visited set (for debugging or advanced usage)
62	*
63	* @return const reference to the visited set
64	*/
65	const std::set<type_id> &get_visited() const { return visited_; }	11✔
66
67	/**
68	* @brief Clear all visited markers
69	*/
70	void clear() { visited_.clear(); }	1✔
71
72	/**
73	* @brief Execute a function with automatic cycle detection and cleanup
74	*
75	* This RAII-style method automatically handles marking/unmarking the type ID
76	* and provides cycle detection. If a cycle is detected, the on_cycle handler
77	* is called instead of the main function.
78	*
79	* @tparam T Return type of the functions
80	* @param id The type ID to process
81	* @param func The main function to execute if no cycle is detected
82	* @param on_cycle The function to execute if a cycle is detected
83	* @param backtrack Whether to automatically unmark the ID after processing
84	* (default: true)
85	* @return The result of either func or on_cycle
86	*/
87	template <typename T>
88	T with_cycle_detection(type_id id, std::function<T()> func,	1,622✔
89	std::function<T()> on_cycle, bool backtrack = true) {
90	if (would_create_cycle(id)) {	2,433✔
91	return on_cycle();	6✔
92	}
93
94	visited_.insert(id);	808✔
95	T result;	295✔
96	try {
97	result = func();	1,103✔
NEW 98	} catch (...) {	×
NEW 99	if (backtrack) {	×
100	visited_.erase(id);
101	}
NEW 102	throw;	×
103	}
104
105	if (backtrack) {	1,616✔
106	visited_.erase(id);	807✔
107	}
108
109	return result;	808✔
110	}	295✔
111
112	private:
113	std::set<type_id> visited_;
114	};
115
116	/**
117	* @brief RAII helper for automatic visited tracking
118	*
119	* This class automatically marks a type as visited in its constructor
120	* and unmarks it in its destructor, ensuring proper cleanup even
121	* in the presence of exceptions.
122	*/
123	class scoped_visit {
124	public:
125	/**
126	* @brief Construct and mark a type as visited
127	*
128	* @param detector The cycle detector to use
129	* @param id The type ID to mark as visited
130	* @throws std::runtime_error if a cycle would be created
131	*/
132	scoped_visit(cycle_detector &detector, btf_type_id id)	2✔
133	: detector_(detector), id_(id), marked_(false) {	2✔
134	if (!detector_.mark_visited(id)) {	2✔
135	throw std::runtime_error("Cycle detected for type ID " +	3✔
136	std::to_string(id));	4✔
137	}
NEW 138	marked_ = true;	×
NEW 139	}	×
140
141	/**
142	* @brief Construct without throwing on cycle detection
143	*
144	* @param detector The cycle detector to use
145	* @param id The type ID to mark as visited
146	* @param no_throw Tag to indicate no exception should be thrown
147	* @return true if successfully marked, false if cycle detected
148	*/
149	scoped_visit(cycle_detector &detector, btf_type_id id, std::nothrow_t)	1,169✔
150	: detector_(detector), id_(id) {	1,169✔
151	marked_ = detector_.mark_visited(id);	2,338✔
152	}	1,169✔
153
154	/**
155	* @brief Destructor automatically unmarks the type
156	*/
157	~scoped_visit() {	1,169✔
158	if (marked_) {	1,180✔
159	detector_.unmark_visited(id_);	2,332✔
160	}
161	}	1,169✔
162
163	/**
164	* @brief Check if the type was successfully marked as visited
165	*
166	* @return true if marked (no cycle), false if cycle was detected
167	*/
168	bool is_marked() const { return marked_; }	1,169✔
169
170	// Non-copyable, non-movable to prevent issues with RAII
171	scoped_visit(const scoped_visit &) = delete;
172	scoped_visit &operator=(const scoped_visit &) = delete;
173	scoped_visit(scoped_visit &&) = delete;
174	scoped_visit &operator=(scoped_visit &&) = delete;
175
176	private:
177	cycle_detector &detector_;
178	btf_type_id id_;
179	bool marked_;
180	};
181
182	} // namespace libbtf

Alan-Jowett / libbtf / 20179964478

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous