18689846106

Committed 21 Oct 2025 03:54PM UTC coverage: 95.996% (+0.7%) from 95.331%

Build # 18689846106

Build Type

Pull #173

github

Committed by

web-flow

Commit Message

Merge 765c6cca4 into 643757eaf

Pull Request Pull Request #173: Add support for correctly handling BTF data with cycles

Run Details

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

88.7

/libbtf/btf_type_data.cpp

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

#include "btf_type_data.h"

#include "btf.h"
#include "btf_json.h"
#include "btf_parse.h"
#include "btf_write.h"
#include "cycle_detector.h"

#include <algorithm>
#include <iomanip>
#include <sstream>
#include <stdexcept>

namespace libbtf {

btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data) {
  auto visitor = [&, this](btf_type_id id,
                           const std::optional<std::string> &name,
                           const btf_kind &kind) {
    this->id_to_kind.insert({id, kind});
    if (name.has_value()) {
      this->name_to_id.insert({name.value(), id});
    }
  };
  btf_parse_types(btf_data, visitor);
}

btf_type_id btf_type_data::get_id(const std::string &name) const {
  auto it = name_to_id.find(name);
  if (it == name_to_id.end()) {
    return 0;
  }
  return it->second;
}

btf_kind btf_type_data::get_kind(btf_type_id id) const {
  auto it = id_to_kind.find(id);
  if (it == id_to_kind.end()) {
    throw std::runtime_error("BTF type id not found: " + std::to_string(id));
  }
  return it->second;
}

btf_type_id btf_type_data::dereference_pointer(btf_type_id id) const {
  return get_kind_type<btf_kind_ptr>(id).type;
}

uint32_t btf_type_data::get_size(btf_type_id id) const {
  cycle_detector detector;
  return get_size_with_detector(id, detector);
}

uint32_t btf_type_data::get_size_with_detector(btf_type_id id,
                                               cycle_detector &detector) const {
  return detector.with_cycle_detection<uint32_t>(
      id,
      [this, id, &detector]() -> uint32_t {
        // Main processing logic - same as original but using detector
        return std::visit(
            [this, id, &detector](auto kind) -> uint32_t {
              if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
                return sizeof(void *);
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return get_size_with_detector(kind.type, detector);
              } else if constexpr (btf_kind_traits<
                                       decltype(kind)>::has_size_in_bytes) {
                return kind.size_in_bytes;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_array>) {
                return kind.count_of_elements *
                       get_size_with_detector(kind.element_type, detector);
              } else {
                return 0;
              }
            },
            get_kind(id));
      },
      []() -> uint32_t {
        // Cycle detected - return 0 to avoid infinite recursion
        return 0;
      });
}

void btf_type_data::to_json(
    std::ostream &out,
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  btf_type_to_json(id_to_kind, out, filter);
}

std::vector<std::byte> btf_type_data::to_bytes() const {
  std::vector<btf_kind> kinds;
  for (const auto &[id, kind] : id_to_kind) {
    kinds.push_back(kind);
  }
  return btf_write_types(kinds);
}

void btf_type_data::replace(btf_type_id id, const btf_kind &kind) {
  if (id_to_kind.find(id) == id_to_kind.end()) {
    throw std::runtime_error("BTF type not found: " + std::to_string(id));
  }

  id_to_kind[id] = kind;
  update_name_to_id(id);
}

btf_type_id btf_type_data::append(const btf_kind &kind) {
  if (id_to_kind.size() > UINT32_MAX) {
    throw std::runtime_error("Too many BTF types");
  }
  btf_type_id next_id = static_cast<btf_type_id>(id_to_kind.size());
  id_to_kind.insert({next_id, kind});
  update_name_to_id(next_id);
  return next_id;
}

void btf_type_data::update_name_to_id(btf_type_id id) {

  auto name = get_type_name(id);
  if (!name.empty()) {
    name_to_id.insert({name, id});
  }
}

std::vector<btf_type_id> btf_type_data::dependency_order(
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  std::map<btf_type_id, std::set<btf_type_id>> children;
  std::map<btf_type_id, std::set<btf_type_id>> parents;
  std::set<btf_type_id> filtered_types;
  std::vector<btf_type_id> result;

  // Build list of dependencies manually to avoid infinite recursion with
  // cycles. This approach directly extracts immediate
  // dependencies without recursive traversal.
  for (const auto &[id, kind] : id_to_kind) {
    // Copy id to a local variable to workaround a bug in Apple's clang.
    // See: https://github.com/llvm/llvm-project/issues/48582
    auto local_id = id;
    bool match = false;
    if (!filter || (*filter)(local_id)) {
      match = true;
      filtered_types.insert(local_id);
    }

    // Initialize entries for this type
    if (parents.find(local_id) == parents.end()) {
      parents[local_id] = std::set<btf_type_id>();
    }
    if (children.find(local_id) == children.end()) {
      children[local_id] = std::set<btf_type_id>();
    }

    // Directly extract dependencies from the kind without recursive traversal
    std::visit(
        [&](auto k) {
          if constexpr (btf_kind_traits<decltype(k)>::has_type) {
            btf_type_id dep_id = k.type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_index_type) {
            btf_type_id dep_id = k.index_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_element_type) {
            btf_type_id dep_id = k.element_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_return_type) {
            btf_type_id dep_id = k.return_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_members) {
            for (auto member : k.members) {
              if constexpr (btf_kind_traits<decltype(member)>::has_type) {
                btf_type_id dep_id = member.type;
                if (dep_id != local_id &&
                    id_to_kind.find(dep_id) != id_to_kind.end()) {
                  children[local_id].insert(dep_id);
                  if (parents.find(dep_id) == parents.end()) {
                    parents[dep_id] = std::set<btf_type_id>();
                  }
                  parents[dep_id].insert(local_id);
                }
              }
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_parameters) {
            for (auto param : k.parameters) {
              if constexpr (btf_kind_traits<decltype(param)>::has_type) {
                btf_type_id dep_id = param.type;
                if (dep_id != local_id &&
                    id_to_kind.find(dep_id) != id_to_kind.end()) {
                  children[local_id].insert(dep_id);
                  if (parents.find(dep_id) == parents.end()) {
                    parents[dep_id] = std::set<btf_type_id>();
                  }
                  parents[dep_id].insert(local_id);
                }
              }
            }
          }
        },
        kind);
  }

  // Perform topological sort with cycle breaking
  // Add safety limit to prevent infinite loops in case of bugs in
  // cycle-breaking logic
  size_t previous_size = 0;
  size_t iteration_count = 0;
  // The multiplier '3' is chosen as a conservative upper bound for the number
  // of iterations required to remove all nodes, even in the presence of cycles.
  // In the worst-case scenario, each iteration removes at least one node, and
  // the factor of 3 ensures that the loop will terminate even if cycles require
  // multiple passes to break. Adjust if future analysis shows a different bound
  // is needed.
  const size_t max_iterations =
      id_to_kind.size() * 3; // Safety limit to prevent infinite loops in cycles

  while (!parents.empty() && iteration_count < max_iterations) {
    iteration_count++;
    std::vector<btf_type_id> types_to_remove;

    // Find all types with no parents.
    for (auto &[id, child_set] : parents) {
      if (child_set.empty()) {
        types_to_remove.push_back(id);
      }
    }

    // If we can't make progress (no types with empty parents),
    // we have cycles. Break them by selecting arbitrary types.
    if (types_to_remove.empty()) {
      // Pick the first type with the fewest dependencies to break the cycle
      btf_type_id min_id = parents.begin()->first;
      size_t min_deps = parents.begin()->second.size();
      for (const auto &[id, deps] : parents) {
        if (deps.size() < min_deps) {
          min_id = id;
          min_deps = deps.size();
        }
      }
      types_to_remove.push_back(min_id);
    }

    if (types_to_remove.empty()) {
      // Safety: force progress if we're still stuck
      types_to_remove.push_back(parents.begin()->first);
    }

    previous_size = parents.size();

    // Remove these parents from all children.
    for (auto id : types_to_remove) {
      for (auto child : children[id]) {
        parents[child].erase(id);
      }
      parents.erase(id);
    }
    // Append these types to the result.
    result.insert(result.end(), types_to_remove.begin(), types_to_remove.end());
  }

  // Remove types that are not children of the filtered type.
  std::vector<btf_type_id> filtered_result;
  for (auto id : result) {
    if (filtered_types.find(id) != filtered_types.end()) {
      filtered_result.push_back(id);
    }
  }

  std::reverse(filtered_result.begin(), filtered_result.end());
  return filtered_result;
}

void btf_type_data::to_c_header(
    std::ostream &out,
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  std::set<btf_type_id> declared_types;

  size_t indent = 0;
  out << "#pragma once\n\n";

  // Print each type in dependency order.
  for (auto id : dependency_order(filter)) {
    if (get_type_name(id).empty()) {
      continue;
    }
    std::visit(
        [&, this](auto kind) {
          if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
            out << "typedef ";
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind),
                                              btf_kind_struct>) {
            out << get_type_declaration(id, "", indent) << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
            out << get_type_declaration(id, "", indent) << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_fwd>) {
            out << (kind.is_struct ? "union " : "struct ") << kind.name
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_var>) {
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind),
                                              btf_kind_function>) {
            if (kind.linkage == BTF_LINKAGE_STATIC) {
              out << "static ";
            } else if (kind.linkage == BTF_LINKAGE_EXTERN) {
              out << "extern ";
            }
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          }
        },
        get_kind(id));
  }
}

std::string btf_type_data::get_type_name(btf_type_id id) const {
  // Use visit to return the name if the type has it.
  auto kind = get_kind(id);
  return std::visit(
      [](auto kind) -> std::string {
        if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
          return kind.name.value_or("");
        } else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
          return kind.name;
        } else {
          return "";
        }
      },
      get_kind(id));
}

std::string btf_type_data::get_qualified_type_name_with_detector(
    btf_type_id id, cycle_detector &detector) const {
  return detector.with_cycle_detection<std::string>(
      id,
      [this, id, &detector]() -> std::string {
        // Main processing logic - adapted from original but using detector
        auto kind = get_kind(id);
        return std::visit(
            [this, &detector](auto kind) -> std::string {
              // Add possible qualifiers.
              std::string qualifier;
              if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
                qualifier = "const ";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_volatile>) {
                qualifier = "volatile ";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_restrict>) {
                qualifier = "restrict ";
              }

              std::string suffix;
              if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
                suffix = "*";
              }

              if constexpr (btf_kind_traits<
                                decltype(kind)>::has_optional_name) {
                return qualifier + kind.name.value_or("") + suffix;
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
                return kind.name + suffix;
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return qualifier +
                       this->get_qualified_type_name_with_detector(kind.type,
                                                                   detector) +
                       suffix;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_void>) {
                return qualifier + "void" + suffix;
              } else {
                return "";
              }
            },
            kind);
      },
      [id]() -> std::string {
        // Cycle detected - return placeholder
        return "/* cyclic type " + std::to_string(id) + " */";
      });
}

btf_type_id btf_type_data::get_descendant_type_id_with_detector(
    btf_type_id id, cycle_detector &detector) const {
  return detector.with_cycle_detection<btf_type_id>(
      id,
      [this, id, &detector]() -> btf_type_id {
        // Main processing logic - same as original but using detector
        return std::visit(
            [id, this, &detector](auto kind) -> btf_type_id {
              if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return this->get_descendant_type_id_with_detector(kind.type,
                                                                  detector);
              } else {
                return id;
              }
            },
            get_kind(id));
      },
      [id]() -> btf_type_id {
        // Cycle detected - return current id to break the cycle
        return id;
      });
}

std::string btf_type_data::get_type_declaration(btf_type_id id,
                                                const std::string &name,
                                                size_t indent) const {
  cycle_detector detector;
  return get_type_declaration_with_detector(id, name, indent, detector);
}

std::string btf_type_data::get_type_declaration_with_detector(
    btf_type_id id, const std::string &name, size_t indent,
    cycle_detector &detector) const {
  return detector.with_cycle_detection<std::string>(
      id,
      [this, id, &name, indent, &detector]() -> std::string {
        // Build a string of type qualifiers.
        std::string result = std::string(indent, ' ');
        auto kind = get_kind(id);
        std::visit(
            [&](auto kind) {
              if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
                result += get_type_name(id) + " " + name;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_array>) {
                auto local_name = name;
                if (!local_name.empty() && local_name[0] == '*') {
                  local_name = "(" + local_name + ")";
                }
                auto local_type = get_type_name(kind.element_type);
                if (local_type.empty()) {
                  local_type = get_type_declaration_with_detector(
                      kind.element_type, "", indent, detector);
                }
                result += local_type + " " + local_name + "[" +
                          std::to_string(kind.count_of_elements) + "]";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_const>) {
                result += "const " + get_type_declaration_with_detector(
                                         kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_volatile>) {
                result += "volatile " + get_type_declaration_with_detector(
                                            kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_restrict>) {
                result += "restrict " + get_type_declaration_with_detector(
                                            kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_ptr>) {
                result = get_type_declaration_with_detector(
                    kind.type, "*" + name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_struct>) {
                if (kind.name.has_value()) {
                  result = "struct " + kind.name.value_or("") + " {\n";
                } else {
                  result = "struct {\n";
                }
                for (auto member : kind.members) {
                  std::string type_name = get_type_name(member.type);
                  if (type_name.empty()) {
                    result += get_type_declaration_with_detector(
                                  member.type, member.name.value_or(""),
                                  indent + 2, detector) +
                              ";\n";
                  } else {
                    result += std::string(indent + 2, ' ') + type_name + " " +
                              member.name.value_or("") + ";\n";
                  }
                }
                result += std::string(indent, ' ') + "}";
                if (!name.empty()) {
                  result += " " + name;
                }
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_union>) {
                if (kind.name.has_value()) {
                  result += "union " + kind.name.value_or("") + " {\n";
                } else {
                  result += "union {\n";
                }
                for (auto member : kind.members) {
                  std::string type_name = get_type_name(member.type);
                  if (type_name.empty()) {
                    result += get_type_declaration_with_detector(
                                  member.type, member.name.value_or(""),
                                  indent + 2, detector) +
                              ";\n";
                  } else {
                    result += std::string(indent + 2, ' ') + type_name + " " +
                              member.name.value_or("") + ";\n";
                  }
                }
                result += std::string(indent, ' ') + "}";
                if (!name.empty()) {
                  result += " " + name;
                }
              } else if constexpr (std::is_same_v<
                                       decltype(kind),
                                       btf_kind_function_prototype>) {
                result += get_qualified_type_name_with_detector(
                              kind.return_type, detector) +
                          " " + name + "(";
                for (auto param : kind.parameters) {
                  result += get_qualified_type_name_with_detector(param.type,
                                                                  detector);
                  if (!param.name.empty()) {
                    result += " " + param.name;
                  }
                  result += ", ";
                }
                if (kind.parameters.size() > 0) {
                  result.pop_back();
                  result.pop_back();
                }
                result += ")";
              } else if constexpr (!btf_kind_traits<decltype(kind)>::has_type) {
                result += get_type_name(id) + " " + name;
              }
            },
            kind);

        return result;
      },
      [this, id, &name, indent]() -> std::string {
        // Cycle detected - return just the type name if available, or a
        // placeholder
        auto type_name = get_type_name(id);
        if (!type_name.empty()) {
          return std::string(indent, ' ') + type_name + " " + name;
        } else {
          return std::string(indent, ' ') + "/* cyclic type " +
                 std::to_string(id) + " */ " + name;
        }
      });
}

} // namespace libbtf

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3
4	#include "btf_type_data.h"
5
6	#include "btf.h"
7	#include "btf_json.h"
8	#include "btf_parse.h"
9	#include "btf_write.h"
10	#include "cycle_detector.h"
11
12	#include <algorithm>
13	#include <iomanip>
14	#include <sstream>
15	#include <stdexcept>
16
17	namespace libbtf {
18
19	btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data) {	170✔
20	auto visitor = [&, this](btf_type_id id,	2,374✔
21	const std::optional<std::string> &name,
22	const btf_kind &kind) {	3,664✔
23	this->id_to_kind.insert({id, kind});	2,374✔
24	if (name.has_value()) {	2,374✔
25	this->name_to_id.insert({name.value(), id});	1,290✔
26	}
27	};	2,374✔
28	btf_parse_types(btf_data, visitor);	180✔
29	}	170✔
30
31	btf_type_id btf_type_data::get_id(const std::string &name) const {	398✔
32	auto it = name_to_id.find(name);	199✔
33	if (it == name_to_id.end()) {	398✔
34	return 0;	40✔
35	}
36	return it->second;	318✔
37	}
38
39	btf_kind btf_type_data::get_kind(btf_type_id id) const {	56,388✔
40	auto it = id_to_kind.find(id);	28,194✔
41	if (it == id_to_kind.end()) {	56,388✔
42	throw std::runtime_error("BTF type id not found: " + std::to_string(id));	3✔
43	}
44	return it->second;	84,579✔
45	}
46
47	btf_type_id btf_type_data::dereference_pointer(btf_type_id id) const {	314✔
48	return get_kind_type<btf_kind_ptr>(id).type;	314✔
49	}
50
51	uint32_t btf_type_data::get_size(btf_type_id id) const {	748✔
52	cycle_detector detector;	374✔
53	return get_size_with_detector(id, detector);	1,496✔
54	}	374✔
55
56	uint32_t btf_type_data::get_size_with_detector(btf_type_id id,	1,010✔
57	cycle_detector &detector) const {
58	return detector.with_cycle_detection<uint32_t>(	2,020✔
59	id,
60	[this, id, &detector]() -> uint32_t {	2,016✔
61	// Main processing logic - same as original but using detector
62	return std::visit(	1,008✔
63	[this, id, &detector](auto kind) -> uint32_t {	635✔
64	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
65	return sizeof(void *);	103✔
66	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
67	return get_size_with_detector(kind.type, detector);	190✔
68	} else if constexpr (btf_kind_traits<
69	decltype(kind)>::has_size_in_bytes) {
70	return kind.size_in_bytes;	203✔
71	} else if constexpr (std::is_same_v<decltype(kind),
72	btf_kind_array>) {
73	return kind.count_of_elements *	36✔
74	get_size_with_detector(kind.element_type, detector);	72✔
75	} else {
76	return 0;	67✔
77	}
78	},
79	get_kind(id));	2,016✔
80	},
81	[]() -> uint32_t {	1✔
82	// Cycle detected - return 0 to avoid infinite recursion
83	return 0;	1✔
84	});	1,515✔
85	}
86
87	void btf_type_data::to_json(	108✔
88	std::ostream &out,
89	std::optional<std::function<bool(btf_type_id)>> filter) const {
90	btf_type_to_json(id_to_kind, out, filter);	108✔
91	}	108✔
92
93	std::vector<std::byte> btf_type_data::to_bytes() const {	70✔
94	std::vector<btf_kind> kinds;	35✔
95	for (const auto &[id, kind] : id_to_kind) {	918✔
96	kinds.push_back(kind);	848✔
97	}
98	return btf_write_types(kinds);	140✔
99	}	70✔
100
101	void btf_type_data::replace(btf_type_id id, const btf_kind &kind) {	4✔
102	if (id_to_kind.find(id) == id_to_kind.end()) {	4✔
103	throw std::runtime_error("BTF type not found: " + std::to_string(id));	×
104	}
105
106	id_to_kind[id] = kind;	4✔
107	update_name_to_id(id);	4✔
108	}	4✔
109
110	btf_type_id btf_type_data::append(const btf_kind &kind) {	22,884✔
111	if (id_to_kind.size() > UINT32_MAX) {	22,884✔
112	throw std::runtime_error("Too many BTF types");	×
113	}
114	btf_type_id next_id = static_cast<btf_type_id>(id_to_kind.size());	22,884✔
115	id_to_kind.insert({next_id, kind});	22,884✔
116	update_name_to_id(next_id);	22,884✔
117	return next_id;	22,884✔
118	}
119
120	void btf_type_data::update_name_to_id(btf_type_id id) {	22,888✔
121
122	auto name = get_type_name(id);	22,888✔
123	if (!name.empty()) {	22,888✔
124	name_to_id.insert({name, id});	2,466✔
125	}
126	}	22,888✔
127
128	std::vector<btf_type_id> btf_type_data::dependency_order(	52✔
129	std::optional<std::function<bool(btf_type_id)>> filter) const {
130	std::map<btf_type_id, std::set<btf_type_id>> children;	26✔
131	std::map<btf_type_id, std::set<btf_type_id>> parents;	26✔
132	std::set<btf_type_id> filtered_types;	26✔
133	std::vector<btf_type_id> result;	26✔
134
135	// Build list of dependencies manually to avoid infinite recursion with
136	// cycles. This approach directly extracts immediate
137	// dependencies without recursive traversal.
138	for (const auto &[id, kind] : id_to_kind) {	730✔
139	// Copy id to a local variable to workaround a bug in Apple's clang.
140	// See: https://github.com/llvm/llvm-project/issues/48582
141	auto local_id = id;	678✔
142	bool match = false;	339✔
143	if (!filter \|\| (*filter)(local_id)) {	678✔
144	match = true;	339✔
145	filtered_types.insert(local_id);	339✔
146	}
147
148	// Initialize entries for this type
149	if (parents.find(local_id) == parents.end()) {	678✔
150	parents[local_id] = std::set<btf_type_id>();	642✔
151	}
152	if (children.find(local_id) == children.end()) {	678✔
153	children[local_id] = std::set<btf_type_id>();	1,017✔
154	}
155
156	// Directly extract dependencies from the kind without recursive traversal
157	std::visit(	678✔
158	[&](auto k) {	585✔
159	if constexpr (btf_kind_traits<decltype(k)>::has_type) {
160	btf_type_id dep_id = k.type;	302✔
161	if (dep_id != local_id &&	1,787✔
162	id_to_kind.find(dep_id) != id_to_kind.end()) {	1,227✔
163	children[local_id].insert(dep_id);	818✔
164	if (parents.find(dep_id) == parents.end()) {	1,520✔
165	parents[dep_id] = std::set<btf_type_id>();	270✔
166	}
167	parents[dep_id].insert(local_id);	302✔
168	}
169	}
170	if constexpr (btf_kind_traits<decltype(k)>::has_index_type) {
171	btf_type_id dep_id = k.index_type;	68✔
172	if (dep_id != local_id &&	136✔
173	id_to_kind.find(dep_id) != id_to_kind.end()) {	68✔
174	children[local_id].insert(dep_id);	68✔
175	if (parents.find(dep_id) == parents.end()) {	68✔
176	parents[dep_id] = std::set<btf_type_id>();	42✔
177	}
178	parents[dep_id].insert(local_id);	68✔
179	}
180	}
181	if constexpr (btf_kind_traits<decltype(k)>::has_element_type) {
182	btf_type_id dep_id = k.element_type;	68✔
183	if (dep_id != local_id &&	136✔
184	id_to_kind.find(dep_id) != id_to_kind.end()) {	68✔
185	children[local_id].insert(dep_id);	68✔
186	if (parents.find(dep_id) == parents.end()) {	68✔
NEW 187	parents[dep_id] = std::set<btf_type_id>();	×
188	}
189	parents[dep_id].insert(local_id);	68✔
190	}
191	}
192	if constexpr (btf_kind_traits<decltype(k)>::has_return_type) {
193	btf_type_id dep_id = k.return_type;	48✔
194	if (dep_id != local_id &&	96✔
195	id_to_kind.find(dep_id) != id_to_kind.end()) {	48✔
196	children[local_id].insert(dep_id);	48✔
197	if (parents.find(dep_id) == parents.end()) {	48✔
198	parents[dep_id] = std::set<btf_type_id>();	21✔
199	}
200	parents[dep_id].insert(local_id);	48✔
201	}
202	}
203	if constexpr (btf_kind_traits<decltype(k)>::has_members) {
204	for (auto member : k.members) {	360✔
205	if constexpr (btf_kind_traits<decltype(member)>::has_type) {
206	btf_type_id dep_id = member.type;	286✔
207	if (dep_id != local_id &&	572✔
208	id_to_kind.find(dep_id) != id_to_kind.end()) {	286✔
209	children[local_id].insert(dep_id);	286✔
210	if (parents.find(dep_id) == parents.end()) {	286✔
211	parents[dep_id] = std::set<btf_type_id>();	28✔
212	}
213	parents[dep_id].insert(local_id);	286✔
214	}
215	}
216	}
217	}
218	if constexpr (btf_kind_traits<decltype(k)>::has_parameters) {
219	for (auto param : k.parameters) {	94✔
220	if constexpr (btf_kind_traits<decltype(param)>::has_type) {
221	btf_type_id dep_id = param.type;	46✔
222	if (dep_id != local_id &&	92✔
223	id_to_kind.find(dep_id) != id_to_kind.end()) {	46✔
224	children[local_id].insert(dep_id);	46✔
225	if (parents.find(dep_id) == parents.end()) {	46✔
NEW 226	parents[dep_id] = std::set<btf_type_id>();	×
227	}
228	parents[dep_id].insert(local_id);	46✔
229	}
230	}
231	}
232	}
233	},	585✔
234	kind);
235	}
236
237	// Perform topological sort with cycle breaking
238	// Add safety limit to prevent infinite loops in case of bugs in
239	// cycle-breaking logic
240	size_t previous_size = 0;	26✔
241	size_t iteration_count = 0;	26✔
242	// The multiplier '3' is chosen as a conservative upper bound for the number
243	// of iterations required to remove all nodes, even in the presence of cycles.
244	// In the worst-case scenario, each iteration removes at least one node, and
245	// the factor of 3 ensures that the loop will terminate even if cycles require
246	// multiple passes to break. Adjust if future analysis shows a different bound
247	// is needed.
248	const size_t max_iterations =
249	id_to_kind.size() * 3; // Safety limit to prevent infinite loops in cycles	52✔
250
251	while (!parents.empty() && iteration_count < max_iterations) {	362✔
252	iteration_count++;	310✔
253	std::vector<btf_type_id> types_to_remove;	155✔
254
255	// Find all types with no parents.
256	for (auto &[id, child_set] : parents) {	2,910✔
257	if (child_set.empty()) {	2,600✔
258	types_to_remove.push_back(id);	688✔
259	}
260	}
261
262	// If we can't make progress (no types with empty parents),
263	// we have cycles. Break them by selecting arbitrary types.
264	if (types_to_remove.empty()) {	310✔
265	// Pick the first type with the fewest dependencies to break the cycle
266	btf_type_id min_id = parents.begin()->first;	2✔
267	size_t min_deps = parents.begin()->second.size();	1✔
268	for (const auto &[id, deps] : parents) {	6✔
269	if (deps.size() < min_deps) {	4✔
NEW 270	min_id = id;	×
271	min_deps = deps.size();
272	}
273	}
274	types_to_remove.push_back(min_id);	2✔
275	}
276
277	if (types_to_remove.empty()) {	310✔
278	// Safety: force progress if we're still stuck
NEW 279	types_to_remove.push_back(parents.begin()->first);	×
280	}
281
282	previous_size = parents.size();	155✔
283
284	// Remove these parents from all children.
285	for (auto id : types_to_remove) {	1,000✔
286	for (auto child : children[id]) {	1,400✔
287	parents[child].erase(id);	710✔
288	}
289	parents.erase(id);	345✔
290	}
291	// Append these types to the result.
292	result.insert(result.end(), types_to_remove.begin(), types_to_remove.end());	310✔
293	}	155✔
294
295	// Remove types that are not children of the filtered type.
296	std::vector<btf_type_id> filtered_result;	26✔
297	for (auto id : result) {	742✔
298	if (filtered_types.find(id) != filtered_types.end()) {	690✔
299	filtered_result.push_back(id);	690✔
300	}
301	}
302
303	std::reverse(filtered_result.begin(), filtered_result.end());	26✔
304	return filtered_result;	78✔
305	}	26✔
306
307	void btf_type_data::to_c_header(	48✔
308	std::ostream &out,
309	std::optional<std::function<bool(btf_type_id)>> filter) const {
310	std::set<btf_type_id> declared_types;	24✔
311
312	size_t indent = 0;	48✔
313	out << "#pragma once\n\n";	48✔
314
315	// Print each type in dependency order.
316	for (auto id : dependency_order(filter)) {	738✔
317	if (get_type_name(id).empty()) {	999✔
318	continue;	350✔
319	}
320	std::visit(	316✔
321	[&, this](auto kind) {	363✔
322	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
323	out << "typedef ";	182✔
324	out << get_type_declaration(kind.type, kind.name, indent)	158✔
325	<< ";\n\n";	102✔
326	} else if constexpr (std::is_same_v<decltype(kind),
327	btf_kind_struct>) {
328	out << get_type_declaration(id, "", indent) << ";\n\n";	24✔
329	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
330	out << get_type_declaration(id, "", indent) << ";\n\n";	×
331	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_fwd>) {
332	out << (kind.is_struct ? "union " : "struct ") << kind.name	30✔
333	<< ";\n\n";	40✔
334	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_var>) {
335	out << get_type_declaration(kind.type, kind.name, indent)	30✔
336	<< ";\n\n";	45✔
337	} else if constexpr (std::is_same_v<decltype(kind),
338	btf_kind_function>) {
339	if (kind.linkage == BTF_LINKAGE_STATIC) {	48✔
340	out << "static ";	4✔
341	} else if (kind.linkage == BTF_LINKAGE_EXTERN) {	44✔
342	out << "extern ";	×
343	}
344	out << get_type_declaration(kind.type, kind.name, indent)	48✔
345	<< ";\n\n";	72✔
346	}
347	},	247✔
348	get_kind(id));	632✔
349	}	24✔
350	}	48✔
351
352	std::string btf_type_data::get_type_name(btf_type_id id) const {	24,032✔
353	// Use visit to return the name if the type has it.
354	auto kind = get_kind(id);	24,032✔
355	return std::visit(
356	[](auto kind) -> std::string {	12,016✔
357	if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
358	return kind.name.value_or("");	396✔
359	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
360	return kind.name;	2,762✔
361	} else {
362	return "";	20,874✔
363	}
364	},
365	get_kind(id));	60,080✔
366	}	12,016✔
367
368	std::string btf_type_data::get_qualified_type_name_with_detector(	138✔
369	btf_type_id id, cycle_detector &detector) const {
370	return detector.with_cycle_detection<std::string>(
371	id,
372	[this, id, &detector]() -> std::string {	276✔
373	// Main processing logic - adapted from original but using detector
374	auto kind = get_kind(id);	138✔
375	return std::visit(
376	[this, &detector](auto kind) -> std::string {	160✔
377	// Add possible qualifiers.
378	std::string qualifier;	69✔
379	if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
380	qualifier = "const ";
381	} else if constexpr (std::is_same_v<decltype(kind),
382	btf_kind_volatile>) {
383	qualifier = "volatile ";
384	} else if constexpr (std::is_same_v<decltype(kind),
385	btf_kind_restrict>) {
386	qualifier = "restrict ";
387	}
388
389	std::string suffix;	69✔
390	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
391	suffix = "*";	22✔
392	}
393
394	if constexpr (btf_kind_traits<
395	decltype(kind)>::has_optional_name) {
396	return qualifier + kind.name.value_or("") + suffix;	40✔
397	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
398	return kind.name + suffix;	132✔
399	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
400	return qualifier +
401	this->get_qualified_type_name_with_detector(kind.type,
402	detector) +
403	suffix;	110✔
404	} else if constexpr (std::is_same_v<decltype(kind),
405	btf_kind_void>) {
406	return qualifier + "void" + suffix;	30✔
407	} else {
NEW 408	return "";	×
409	}
410	},	69✔
411	kind);	276✔
412	},	69✔
NEW 413	[id]() -> std::string {	×
414	// Cycle detected - return placeholder
NEW 415	return "/* cyclic type " + std::to_string(id) + " */";	×
416	});	276✔
417	}
418
NEW 419	btf_type_id btf_type_data::get_descendant_type_id_with_detector(	×
420	btf_type_id id, cycle_detector &detector) const {
NEW 421	return detector.with_cycle_detection<btf_type_id>(	×
422	id,
NEW 423	[this, id, &detector]() -> btf_type_id {	×
424	// Main processing logic - same as original but using detector
NEW 425	return std::visit(	×
NEW 426	[id, this, &detector](auto kind) -> btf_type_id {	×
427	if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
NEW 428	return this->get_descendant_type_id_with_detector(kind.type,	×
429	detector);
430	} else {
NEW 431	return id;	×
432	}
433	},
NEW 434	get_kind(id));	×
435	},
436	[id]() -> btf_type_id {
437	// Cycle detected - return current id to break the cycle
NEW 438	return id;	×
NEW 439	});	×
440	}
441
442	std::string btf_type_data::get_type_declaration(btf_type_id id,	158✔
443	const std::string &name,
444	size_t indent) const {
445	cycle_detector detector;	79✔
446	return get_type_declaration_with_detector(id, name, indent, detector);	316✔
447	}	79✔
448
449	std::string btf_type_data::get_type_declaration_with_detector(	452✔
450	btf_type_id id, const std::string &name, size_t indent,
451	cycle_detector &detector) const {
452	return detector.with_cycle_detection<std::string>(
453	id,
454	[this, id, &name, indent, &detector]() -> std::string {	1,130✔
455	// Build a string of type qualifiers.
456	std::string result = std::string(indent, ' ');	226✔
457	auto kind = get_kind(id);	452✔
458	std::visit(	452✔
459	[&](auto kind) {	452✔
460	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
461	result += get_type_name(id) + " " + name;	1,678✔
462	} else if constexpr (std::is_same_v<decltype(kind),
463	btf_kind_array>) {
464	auto local_name = name;	42✔
465	if (!local_name.empty() && local_name[0] == '*') {	84✔
466	local_name = "(" + local_name + ")";	111✔
467	}
468	auto local_type = get_type_name(kind.element_type);	84✔
469	if (local_type.empty()) {	84✔
470	local_type = get_type_declaration_with_detector(	6✔
471	kind.element_type, "", indent, detector);	552✔
472	}
473	result += local_type + " " + local_name + "[" +	126✔
474	std::to_string(kind.count_of_elements) + "]";
475	} else if constexpr (std::is_same_v<decltype(kind),	42✔
476	btf_kind_const>) {
NEW 477	result += "const " + get_type_declaration_with_detector(	×
478	kind.type, name, indent, detector);
479	} else if constexpr (std::is_same_v<decltype(kind),
480	btf_kind_volatile>) {
NEW 481	result += "volatile " + get_type_declaration_with_detector(	×
482	kind.type, name, indent, detector);
483	} else if constexpr (std::is_same_v<decltype(kind),
484	btf_kind_restrict>) {
NEW 485	result += "restrict " + get_type_declaration_with_detector(	×
486	kind.type, name, indent, detector);
487	} else if constexpr (std::is_same_v<decltype(kind),
488	btf_kind_ptr>) {
489	result = get_type_declaration_with_detector(	210✔
490	kind.type, "*" + name, indent, detector);
491	} else if constexpr (std::is_same_v<decltype(kind),
492	btf_kind_struct>) {
493	if (kind.name.has_value()) {	46✔
494	result = "struct " + kind.name.value_or("") + " {\n";	18✔
495	} else {
496	result = "struct {\n";	17✔
497	}
498	for (auto member : kind.members) {	306✔
499	std::string type_name = get_type_name(member.type);	260✔
500	if (type_name.empty()) {	260✔
501	result += get_type_declaration_with_detector(	219✔
502	member.type, member.name.value_or(""),
503	indent + 2, detector) +
504	";\n";
505	} else {
506	result += std::string(indent + 2, ' ') + type_name + " " +	171✔
507	member.name.value_or("") + ";\n";
508	}
509	}
510	result += std::string(indent, ' ') + "}";	69✔
511	if (!name.empty()) {	46✔
512	result += " " + name;	51✔
513	}
514	} else if constexpr (std::is_same_v<decltype(kind),
515	btf_kind_union>) {
516	if (kind.name.has_value()) {	4✔
NEW 517	result += "union " + kind.name.value_or("") + " {\n";	×
518	} else {
519	result += "union {\n";	2✔
520	}
521	for (auto member : kind.members) {	8✔
522	std::string type_name = get_type_name(member.type);	4✔
523	if (type_name.empty()) {	4✔
524	result += get_type_declaration_with_detector(	6✔
525	member.type, member.name.value_or(""),
526	indent + 2, detector) +
527	";\n";
528	} else {
NEW 529	result += std::string(indent + 2, ' ') + type_name + " " +	×
530	member.name.value_or("") + ";\n";
531	}
532	}
533	result += std::string(indent, ' ') + "}";	6✔
534	if (!name.empty()) {	4✔
NEW 535	result += " " + name;	×
536	}
537	} else if constexpr (std::is_same_v<
538	decltype(kind),
539	btf_kind_function_prototype>) {
540	result += get_qualified_type_name_with_detector(	72✔
541	kind.return_type, detector) +
542	" " + name + "(";
543	for (auto param : kind.parameters) {	94✔
544	result += get_qualified_type_name_with_detector(param.type,	69✔
545	detector);
546	if (!param.name.empty()) {	46✔
547	result += " " + param.name;	69✔
548	}
549	result += ", ";	23✔
550	}
551	if (kind.parameters.size() > 0) {	48✔
552	result.pop_back();	23✔
553	result.pop_back();	23✔
554	}
555	result += ")";	24✔
556	} else if constexpr (!btf_kind_traits<decltype(kind)>::has_type) {
557	result += get_type_name(id) + " " + name;	93✔
558	}
559	},	452✔
560	kind);
561
562	return result;	678✔
563	},	226✔
NEW 564	[this, id, &name, indent]() -> std::string {	×
565	// Cycle detected - return just the type name if available, or a
566	// placeholder
NEW 567	auto type_name = get_type_name(id);	×
NEW 568	if (!type_name.empty()) {	×
NEW 569	return std::string(indent, ' ') + type_name + " " + name;	×
570	} else {
NEW 571	return std::string(indent, ' ') + "/* cyclic type " +	×
NEW 572	std::to_string(id) + " */ " + name;	×
573	}
574	});	904✔
575	}
576
577	} // namespace libbtf

Alan-Jowett / libbtf / 18689846106

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