18660514157

Committed 20 Oct 2025 05:56PM UTC coverage: 95.257% (-0.07%) from 95.331%

Build # 18660514157

Build Type

Pull #172

github

Committed by

web-flow

Commit Message

Merge 4b49a0e0c into b6741487e

Pull Request Pull Request #172: Fix infinite recursion in BTF type processing when cycles are present

Run Details

89 of 101 new or added lines in 2 files covered. (88.12%)

2 existing lines in 2 files now uncovered.

1466 of 1539 relevant lines covered (95.26%)

1925.38 hits per line

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

91.1

/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 <algorithm>
#include <iomanip>
#include <sstream>
#include <stdexcept>

namespace libbtf {

btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data, bool reject_cycles) {
  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);
  // If reject_cycles is true, validate the type graph.
  // This will throw an exception if there are cycles.
  if (reject_cycles) {
    // Validate that the type graph is valid.
    for (const auto &[id, kind] : id_to_kind) {
      std::set<btf_type_id> visited;
      validate_type_graph(id, visited);
    }
  }
}

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 {
  std::set<btf_type_id> visited;
  return get_size(id, visited);
}

uint32_t btf_type_data::get_size(btf_type_id id,
                                  std::set<btf_type_id> &visited) const {
  // Check for cycle
  if (visited.find(id) != visited.end()) {
    // Cycle detected, return 0 as a safe default
    return 0;
  }
  visited.insert(id);

  // Compute the effective size of a BTF type.
  auto result = std::visit(
      [this, id, &visited](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(kind.type, visited);
        } 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(kind.element_type, visited);
        } else
          return 0;
      },
      get_kind(id));

  visited.erase(id);
  return result;
}

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);
}

void btf_type_data::validate_type_graph(btf_type_id id,
                                        std::set<btf_type_id> &visited) const {
  auto before = [&](btf_type_id id) -> bool {
    if (visited.find(id) != visited.end()) {
      throw std::runtime_error("BTF type cycle detected: " +
                               std::to_string(id));
    } else {
      visited.insert(id);
    }
    return true;
  };

  auto after = [&](btf_type_id id) { visited.erase(id); };

  visit_depth_first(before, after, id);
}

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});
  }
}

void btf_type_data::visit_depth_first(
    std::optional<std::function<bool(btf_type_id)>> before,
    std::optional<std::function<void(btf_type_id)>> after,
    btf_type_id id) const {
  if (before) {
    if (!(*before)(id)) {
      return;
    }
  }

  std::visit(
      [&, this](auto kind) {
        if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
          visit_depth_first(before, after, kind.type);
        }
        if constexpr (btf_kind_traits<decltype(kind)>::has_index_type) {
          visit_depth_first(before, after, kind.index_type);
        }
        if constexpr (btf_kind_traits<decltype(kind)>::has_element_type) {
          visit_depth_first(before, after, kind.element_type);
        }
        if constexpr (btf_kind_traits<decltype(kind)>::has_members) {
          for (auto member : kind.members) {
            if constexpr (btf_kind_traits<decltype(member)>::has_type) {
              visit_depth_first(before, after, member.type);
            }
          }
        }
        if constexpr (btf_kind_traits<decltype(kind)>::has_return_type) {
          visit_depth_first(before, after, kind.return_type);
        }
        if constexpr (btf_kind_traits<decltype(kind)>::has_parameters) {
          for (auto param : kind.parameters) {
            if constexpr (btf_kind_traits<decltype(param)>::has_type) {
              visit_depth_first(before, after, param.type);
            }
          }
        }
      },
      get_kind(id));

  if (after) {
    (*after)(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.
  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;
    }
    std::set<btf_type_id> visited_in_traversal;
    auto pre = [&](btf_type_id visit_id) -> bool {
      // Detect cycles - if we've already visited this node in the current
      // traversal, stop to prevent infinite recursion
      if (visited_in_traversal.find(visit_id) != visited_in_traversal.end()) {
        return false;
      }
      visited_in_traversal.insert(visit_id);

      if (match) {
        filtered_types.insert(visit_id);
      }
      if (visit_id != local_id) {
        children[local_id].insert(visit_id);
        parents[visit_id].insert(local_id);
      } else {
        parents.insert({local_id, {}});
        children.insert({local_id, {}});
      }
      return true;
    };

    auto post = [&](btf_type_id visit_id) {
      visited_in_traversal.erase(visit_id);
    };

    visit_depth_first(pre, post, local_id);
  }

  while (!parents.empty()) {
    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 remove any types, we have a cycle
    // Break to avoid infinite loop
    if (types_to_remove.empty()) {
      // Add remaining types (which are in a cycle) to the result
      for (auto &[id, _] : parents) {
        result.push_back(id);
      }
      break;
    }

    // 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(btf_type_id id) const {
  std::set<btf_type_id> visited;
  return get_qualified_type_name(id, visited);
}

std::string btf_type_data::get_qualified_type_name(
    btf_type_id id, std::set<btf_type_id> &visited) const {
  // Check for cycle
  if (visited.find(id) != visited.end()) {
    // Cycle detected, return a placeholder
    return "<cycle>";
  }
  visited.insert(id);

  // Use visit to return the name if the type has it.
  auto kind = get_kind(id);
  auto result = std::visit(
      [this, &visited](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(kind.type, visited) +
                 suffix;
        } else if constexpr (std::is_same_v<decltype(kind), btf_kind_void>) {
          return qualifier + "void" + suffix;
        } else {
          return "";
        }
      },
      get_kind(id));

  visited.erase(id);
  return result;
}

btf_type_id btf_type_data::get_descendant_type_id(btf_type_id id) const {
  std::set<btf_type_id> visited;
  return get_descendant_type_id(id, visited);
}

btf_type_id btf_type_data::get_descendant_type_id(
    btf_type_id id, std::set<btf_type_id> &visited) const {
  // Check for cycle
  if (visited.find(id) != visited.end()) {
    // Cycle detected, return the current id
    return id;
  }
  visited.insert(id);

  // Get the type id lowest in the tree.
  auto kind = get_kind(id);
  auto result = std::visit(
      [id, this, &visited](auto kind) -> btf_type_id {
        if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
          return this->get_descendant_type_id(kind.type, visited);
        } else {
          return id;
        }
      },
      kind);

  visited.erase(id);
  return result;
}

std::string btf_type_data::get_type_declaration(btf_type_id id,
                                                const std::string &name,
                                                size_t indent) const {
  std::set<btf_type_id> visited;
  return get_type_declaration(id, name, indent, visited);
}

std::string btf_type_data::get_type_declaration(
    btf_type_id id, const std::string &name, size_t indent,
    std::set<btf_type_id> &visited) const {
  // Check for cycle
  if (visited.find(id) != visited.end()) {
    // Cycle detected, return a placeholder
    return "<cycle> " + name;
  }
  visited.insert(id);

  // 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(kind.element_type, "", indent, visited);
          }
          result += local_type + " " + local_name + "[" +
                    std::to_string(kind.count_of_elements) + "]";
        } else
            // If kind is btf_kind_const, add const
            if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
          result +=
              "const " + get_type_declaration(kind.type, name, indent, visited);
        } else
            // If kind is btf_kind_volatile, add volatile
            if constexpr (std::is_same_v<decltype(kind), btf_kind_volatile>) {
          result += "volatile " +
                    get_type_declaration(kind.type, name, indent, visited);
        } else
            // If kind is btf_kind_restrict, add restrict
            if constexpr (std::is_same_v<decltype(kind), btf_kind_restrict>) {
          result += "restrict " +
                    get_type_declaration(kind.type, name, indent, visited);
        } else
            // If kind is btf_kind_ptr, add *
            if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
          result = get_type_declaration(kind.type, "*" + name, indent, visited);
        } 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(member.type,
                                              member.name.value_or(""),
                                              indent + 2, visited) +
                        ";\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(member.type,
                                              member.name.value_or(""),
                                              indent + 2, visited) +
                        ";\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(kind.return_type, visited) + " " +
                    name + "(";
          for (auto param : kind.parameters) {
            result += get_qualified_type_name(param.type, visited);
            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);

  visited.erase(id);
  return result;
}
} // 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
11	#include <algorithm>
12	#include <iomanip>
13	#include <sstream>
14	#include <stdexcept>
15
16	namespace libbtf {
17
18	btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data, bool reject_cycles) {	146✔
19	auto visitor = [&, this](btf_type_id id,	2,236✔
20	const std::optional<std::string> &name,
21	const btf_kind &kind) {	3,404✔
22	this->id_to_kind.insert({id, kind});	2,236✔
23	if (name.has_value()) {	2,236✔
24	this->name_to_id.insert({name.value(), id});	1,168✔
25	}
26	};	2,236✔
27	btf_parse_types(btf_data, visitor);	148✔
28	// If reject_cycles is true, validate the type graph.
29	// This will throw an exception if there are cycles.
30	if (reject_cycles) {	146✔
31	// Validate that the type graph is valid.
32	for (const auto &[id, kind] : id_to_kind) {	2,358✔
33	std::set<btf_type_id> visited;	1,108✔
34	validate_type_graph(id, visited);	2,216✔
35	}	1,108✔
36	}
37	}	146✔
38
39	btf_type_id btf_type_data::get_id(const std::string &name) const {	110✔
40	auto it = name_to_id.find(name);	55✔
41	if (it == name_to_id.end()) {	110✔
42	return 0;	22✔
43	}
44	return it->second;	66✔
45	}
46
47	btf_kind btf_type_data::get_kind(btf_type_id id) const {	25,632✔
48	auto it = id_to_kind.find(id);	12,816✔
49	if (it == id_to_kind.end()) {	25,632✔
50	throw std::runtime_error("BTF type id not found: " + std::to_string(id));	3✔
51	}
52	return it->second;	38,445✔
53	}
54
55	btf_type_id btf_type_data::dereference_pointer(btf_type_id id) const {	82✔
56	return get_kind_type<btf_kind_ptr>(id).type;	82✔
57	}
58
59	uint32_t btf_type_data::get_size(btf_type_id id) const {	720✔
60	std::set<btf_type_id> visited;	360✔
61	return get_size(id, visited);	1,440✔
62	}	360✔
63
64	uint32_t btf_type_data::get_size(btf_type_id id,	996✔
65	std::set<btf_type_id> &visited) const {
66	// Check for cycle
67	if (visited.find(id) != visited.end()) {	996✔
68	// Cycle detected, return 0 as a safe default
69	return 0;	4✔
70	}
71	visited.insert(id);	494✔
72
73	// Compute the effective size of a BTF type.
74	auto result = std::visit(	988✔
75	[this, id, &visited](auto kind) -> uint32_t {	632✔
76	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
77	return sizeof(void *);	88✔
78	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
79	return get_size(kind.type, visited);	206✔
80	} else if constexpr (btf_kind_traits<decltype(
81	kind)>::has_size_in_bytes) {
82	return kind.size_in_bytes;	201✔
83	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_array>) {
84	return kind.count_of_elements * get_size(kind.element_type, visited);	70✔
85	} else
86	return 0;	67✔
87	},
88	get_kind(id));	1,976✔
89
90	visited.erase(id);	494✔
91	return result;	988✔
92	}
93
94	void btf_type_data::to_json(	104✔
95	std::ostream &out,
96	std::optional<std::function<bool(btf_type_id)>> filter) const {
97	btf_type_to_json(id_to_kind, out, filter);	104✔
98	}	104✔
99
100	void btf_type_data::validate_type_graph(btf_type_id id,	2,216✔
101	std::set<btf_type_id> &visited) const {
102	auto before = [&](btf_type_id id) -> bool {	15,444✔
103	if (visited.find(id) != visited.end()) {	23,166✔
104	throw std::runtime_error("BTF type cycle detected: " +	6✔
105	std::to_string(id));	8✔
106	} else {
107	visited.insert(id);	7,720✔
108	}
109	return true;	15,440✔
110	};	1,108✔
111
112	auto after = [&](btf_type_id id) { visited.erase(id); };	15,436✔
113
114	visit_depth_first(before, after, id);	3,328✔
115	}	2,212✔
116
117	std::vector<std::byte> btf_type_data::to_bytes() const {	54✔
118	std::vector<btf_kind> kinds;	27✔
119	for (const auto &[id, kind] : id_to_kind) {	754✔
120	kinds.push_back(kind);	700✔
121	}
122	return btf_write_types(kinds);	108✔
123	}	54✔
124
125	void btf_type_data::replace(btf_type_id id, const btf_kind &kind) {	2✔
126	if (id_to_kind.find(id) == id_to_kind.end()) {	2✔
127	throw std::runtime_error("BTF type not found: " + std::to_string(id));	×
128	}
129
130	id_to_kind[id] = kind;	2✔
131	update_name_to_id(id);	2✔
132	}	2✔
133
134	btf_type_id btf_type_data::append(const btf_kind &kind) {	114✔
135	if (id_to_kind.size() > UINT32_MAX) {	114✔
136	throw std::runtime_error("Too many BTF types");	×
137	}
138	btf_type_id next_id = static_cast<btf_type_id>(id_to_kind.size());	114✔
139	id_to_kind.insert({next_id, kind});	114✔
140	update_name_to_id(next_id);	114✔
141	return next_id;	114✔
142	}
143
144	void btf_type_data::update_name_to_id(btf_type_id id) {	116✔
145
146	auto name = get_type_name(id);	116✔
147	if (!name.empty()) {	116✔
148	name_to_id.insert({name, id});	34✔
149	}
150	}	116✔
151
152	void btf_type_data::visit_depth_first(	19,856✔
153	std::optional<std::function<bool(btf_type_id)>> before,
154	std::optional<std::function<void(btf_type_id)>> after,
155	btf_type_id id) const {
156	if (before) {	19,856✔
157	if (!(*before)(id)) {	19,854✔
158	return;	4✔
159	}
160	}
161
162	std::visit(	19,844✔
163	[&, this](auto kind) {	20,080✔
164	if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
165	visit_depth_first(before, after, kind.type);	35,660✔
166	}
167	if constexpr (btf_kind_traits<decltype(kind)>::has_index_type) {
168	visit_depth_first(before, after, kind.index_type);	3,872✔
169	}
170	if constexpr (btf_kind_traits<decltype(kind)>::has_element_type) {
171	visit_depth_first(before, after, kind.element_type);	3,872✔
172	}
173	if constexpr (btf_kind_traits<decltype(kind)>::has_members) {
174	for (auto member : kind.members) {	5,556✔
175	if constexpr (btf_kind_traits<decltype(member)>::has_type) {
176	visit_depth_first(before, after, member.type);	9,128✔
177	}
178	}
179	}
180	if constexpr (btf_kind_traits<decltype(kind)>::has_return_type) {
181	visit_depth_first(before, after, kind.return_type);	1,010✔
182	}
183	if constexpr (btf_kind_traits<decltype(kind)>::has_parameters) {
184	for (auto param : kind.parameters) {	808✔
185	if constexpr (btf_kind_traits<decltype(param)>::has_type) {
186	visit_depth_first(before, after, param.type);	808✔
187	}
188	}
189	}
190	},	15,454✔
191	get_kind(id));	39,686✔
192
193	if (after) {	19,840✔
194	(*after)(id);	19,840✔
195	}
196	}
197
198	std::vector<btf_type_id> btf_type_data::dependency_order(	44✔
199	std::optional<std::function<bool(btf_type_id)>> filter) const {
200	std::map<btf_type_id, std::set<btf_type_id>> children;	22✔
201	std::map<btf_type_id, std::set<btf_type_id>> parents;	22✔
202	std::set<btf_type_id> filtered_types;	22✔
203	std::vector<btf_type_id> result;	22✔
204
205	// Build list of dependencies.
206	for (const auto &[id, kind] : id_to_kind) {	688✔
207	// Copy id to a local variable to workaround a bug in Apple's clang.
208	// See: https://github.com/llvm/llvm-project/issues/48582
209	auto local_id = id;	644✔
210	bool match = false;	644✔
211	if (!filter \|\| (*filter)(local_id)) {	644✔
212	match = true;	644✔
213	}
214	std::set<btf_type_id> visited_in_traversal;	322✔
215	auto pre = [&](btf_type_id visit_id) -> bool {	4,412✔
216	// Detect cycles - if we've already visited this node in the current
217	// traversal, stop to prevent infinite recursion
218	if (visited_in_traversal.find(visit_id) != visited_in_traversal.end()) {	6,618✔
219	return false;	4✔
220	}
221	visited_in_traversal.insert(visit_id);	2,202✔
222
223	if (match) {	4,404✔
224	filtered_types.insert(visit_id);	4,404✔
225	}
226	if (visit_id != local_id) {	6,284✔
227	children[local_id].insert(visit_id);	3,760✔
228	parents[visit_id].insert(local_id);	4,082✔
229	} else {
230	parents.insert({local_id, {}});	644✔
231	children.insert({local_id, {}});	644✔
232	}
233	return true;	2,202✔
234	};	644✔
235
236	auto post = [&](btf_type_id visit_id) {	2,202✔
237	visited_in_traversal.erase(visit_id);	4,404✔
238	};	2,524✔
239
240	visit_depth_first(pre, post, local_id);	1,288✔
241	}	322✔
242
243	while (!parents.empty()) {	310✔
244	std::vector<btf_type_id> types_to_remove;	135✔
245	// Find all types with no parents.
246	for (auto &[id, child_set] : parents) {	2,792✔
247	if (child_set.empty()) {	2,522✔
248	types_to_remove.push_back(id);	636✔
249	}
250	}
251
252	// If we can't remove any types, we have a cycle
253	// Break to avoid infinite loop
254	if (types_to_remove.empty()) {	270✔
255	// Add remaining types (which are in a cycle) to the result
256	for (auto &[id, _] : parents) {	12✔
257	result.push_back(id);	8✔
258	}
259	break;	2✔
260	}
261
262	// Remove these parents from all children.
263	for (auto id : types_to_remove) {	902✔
264	for (auto child : children[id]) {	2,808✔
265	parents[child].erase(id);	2,172✔
266	}
267	parents.erase(id);	318✔
268	}
269	// Append these types to the result.
270	result.insert(result.end(), types_to_remove.begin(), types_to_remove.end());	266✔
271	}	135✔
272
273	// Remove types that are not children of the filtered type.
274	std::vector<btf_type_id> filtered_result;	22✔
275	for (auto id : result) {	688✔
276	if (filtered_types.find(id) != filtered_types.end()) {	644✔
277	filtered_result.push_back(id);	644✔
278	}
279	}
280
281	std::reverse(filtered_result.begin(), filtered_result.end());	22✔
282	return filtered_result;	66✔
283	}	22✔
284
285	void btf_type_data::to_c_header(	44✔
286	std::ostream &out,
287	std::optional<std::function<bool(btf_type_id)>> filter) const {
288	std::set<btf_type_id> declared_types;	22✔
289
290	size_t indent = 0;	44✔
291	out << "#pragma once\n\n";	44✔
292
293	// Print each type in dependency order.
294	for (auto id : dependency_order(filter)) {	710✔
295	if (get_type_name(id).empty()) {	966✔
296	continue;	340✔
297	}
298	std::visit(	304✔
299	[&, this](auto kind) {	349✔
300	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
301	out << "typedef ";	174✔
302	out << get_type_declaration(kind.type, kind.name, indent)	154✔
303	<< ";\n\n";	99✔
304	} else if constexpr (std::is_same_v<decltype(kind),
305	btf_kind_struct>) {
306	out << get_type_declaration(id, "", indent) << ";\n\n";	28✔
307	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
308	out << get_type_declaration(id, "", indent) << ";\n\n";	×
309	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_fwd>) {
310	out << (kind.is_struct ? "union" : "struct ") << kind.name	30✔
311	<< ";\n\n";	40✔
312	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_var>) {
313	out << get_type_declaration(kind.type, kind.name, indent)	30✔
314	<< ";\n\n";	45✔
315	} else if constexpr (std::is_same_v<decltype(kind),
316	btf_kind_function>) {
317	if (kind.linkage == BTF_LINKAGE_STATIC) {	44✔
318	out << "static ";	×
319	} else if (kind.linkage == BTF_LINKAGE_EXTERN) {	44✔
320	out << "extern ";	×
321	}
322	out << get_type_declaration(kind.type, kind.name, indent)	44✔
323	<< ";\n\n";	66✔
324	}
325	},	239✔
326	get_kind(id));	608✔
327	}	22✔
328	}	44✔
329
330	std::string btf_type_data::get_type_name(btf_type_id id) const {	1,238✔
331	// Use visit to return the name if the type has it.
332	auto kind = get_kind(id);	1,238✔
333	return std::visit(
334	[](auto kind) -> std::string {	619✔
335	if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
336	return kind.name.value_or("");	64✔
337	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
338	return kind.name;	640✔
339	} else {
340	return "";	534✔
341	}
342	},
343	get_kind(id));	3,095✔
344	}	619✔
345
UNCOV 346	std::string btf_type_data::get_qualified_type_name(btf_type_id id) const {	×
347	std::set<btf_type_id> visited;
NEW 348	return get_qualified_type_name(id, visited);	×
349	}
350
351	std::string btf_type_data::get_qualified_type_name(	132✔
352	btf_type_id id, std::set<btf_type_id> &visited) const {
353	// Check for cycle
354	if (visited.find(id) != visited.end()) {	132✔
355	// Cycle detected, return a placeholder
NEW 356	return "<cycle>";	×
357	}
358	visited.insert(id);	66✔
359
360	// Use visit to return the name if the type has it.
361	auto kind = get_kind(id);	132✔
362	auto result = std::visit(
363	[this, &visited](auto kind) -> std::string {	154✔
364	// Add possible qualifiers.
365	std::string qualifier;	66✔
366	if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
367	qualifier = "const ";
368	} else if constexpr (std::is_same_v<decltype(kind),
369	btf_kind_volatile>) {
370	qualifier = "volatile ";
371	} else if constexpr (std::is_same_v<decltype(kind),
372	btf_kind_restrict>) {
373	qualifier = "restrict ";
374	}
375
376	std::string suffix;	66✔
377	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
378	suffix = "*";	22✔
379	}
380
381	if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
382	return qualifier + kind.name.value_or("") + suffix;	40✔
383	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
384	return kind.name + suffix;	120✔
385	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
386	return qualifier + this->get_qualified_type_name(kind.type, visited) +
387	suffix;	110✔
388	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_void>) {
389	return qualifier + "void" + suffix;	30✔
390	} else {
391	return "";	×
392	}
393	},	66✔
394	get_kind(id));	198✔
395
396	visited.erase(id);	66✔
397	return result;	66✔
398	}	66✔
399
400	btf_type_id btf_type_data::get_descendant_type_id(btf_type_id id) const {	×
401	std::set<btf_type_id> visited;
NEW 402	return get_descendant_type_id(id, visited);	×
403	}
404
NEW 405	btf_type_id btf_type_data::get_descendant_type_id(	×
406	btf_type_id id, std::set<btf_type_id> &visited) const {
407	// Check for cycle
NEW 408	if (visited.find(id) != visited.end()) {	×
409	// Cycle detected, return the current id
NEW 410	return id;	×
411	}
412	visited.insert(id);
413
414	// Get the type id lowest in the tree.
415	auto kind = get_kind(id);	×
NEW 416	auto result = std::visit(	×
NEW 417	[id, this, &visited](auto kind) -> btf_type_id {	×
418	if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
NEW 419	return this->get_descendant_type_id(kind.type, visited);	×
420	} else {
421	return id;	×
422	}
423	},
424	kind);
425
426	visited.erase(id);
427	return result;
428	}
429
430	std::string btf_type_data::get_type_declaration(btf_type_id id,	154✔
431	const std::string &name,
432	size_t indent) const {
433	std::set<btf_type_id> visited;	77✔
434	return get_type_declaration(id, name, indent, visited);	308✔
435	}	77✔
436
437	std::string btf_type_data::get_type_declaration(	452✔
438	btf_type_id id, const std::string &name, size_t indent,
439	std::set<btf_type_id> &visited) const {
440	// Check for cycle
441	if (visited.find(id) != visited.end()) {	452✔
442	// Cycle detected, return a placeholder
443	return "<cycle> " + name;	2✔
444	}
445	visited.insert(id);	225✔
446
447	// Build a string of type qualifiers.
448	std::string result = std::string(indent, ' ');	450✔
449	auto kind = get_kind(id);	450✔
450	std::visit(	450✔
451	[&](auto kind) {	450✔
452	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
453	result += get_type_name(id) + " " + name;	1,667✔
454	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_array>) {
455	auto local_name = name;	42✔
456	if (!local_name.empty() && local_name[0] == '*') {	84✔
457	local_name = "(" + local_name + ")";	111✔
458	}
459	auto local_type = get_type_name(kind.element_type);	84✔
460	if (local_type.empty()) {	84✔
461	local_type =	6✔
462	get_type_declaration(kind.element_type, "", indent, visited);	552✔
463	}
464	result += local_type + " " + local_name + "[" +	126✔
465	std::to_string(kind.count_of_elements) + "]";
466	} else	42✔
467	// If kind is btf_kind_const, add const
468	if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
NEW 469	result +=	×
470	"const " + get_type_declaration(kind.type, name, indent, visited);
471	} else
472	// If kind is btf_kind_volatile, add volatile
473	if constexpr (std::is_same_v<decltype(kind), btf_kind_volatile>) {
NEW 474	result += "volatile " +	×
475	get_type_declaration(kind.type, name, indent, visited);
476	} else
477	// If kind is btf_kind_restrict, add restrict
478	if constexpr (std::is_same_v<decltype(kind), btf_kind_restrict>) {
NEW 479	result += "restrict " +	×
480	get_type_declaration(kind.type, name, indent, visited);
481	} else
482	// If kind is btf_kind_ptr, add *
483	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
484	result = get_type_declaration(kind.type, "*" + name, indent, visited);	213✔
485	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_struct>) {
486	if (kind.name.has_value()) {	48✔
487	result = "struct " + kind.name.value_or("") + " {\n";	21✔
488	} else {
489	result = "struct {\n";	17✔
490	}
491	for (auto member : kind.members) {	310✔
492	std::string type_name = get_type_name(member.type);	262✔
493	if (type_name.empty()) {	262✔
494	result += get_type_declaration(member.type,	222✔
495	member.name.value_or(""),
496	indent + 2, visited) +
497	";\n";
498	} else {
499	result += std::string(indent + 2, ' ') + type_name + " " +	171✔
500	member.name.value_or("") + ";\n";
501	}
502	}
503	result += std::string(indent, ' ') + "}";	72✔
504	if (!name.empty()) {	48✔
505	result += " " + name;	51✔
506	}
507	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
508	if (kind.name.has_value()) {	4✔
509	result += "union " + kind.name.value_or("") + " {\n";	×
510	} else {
511	result += "union {\n";	2✔
512	}
513	for (auto member : kind.members) {	8✔
514	std::string type_name = get_type_name(member.type);	4✔
515	if (type_name.empty()) {	4✔
516	result += get_type_declaration(member.type,	6✔
517	member.name.value_or(""),
518	indent + 2, visited) +
519	";\n";
520	} else {
521	result += std::string(indent + 2, ' ') + type_name + " " +	×
522	member.name.value_or("") + ";\n";
523	}
524	}
525	result += std::string(indent, ' ') + "}";	6✔
526	if (!name.empty()) {	4✔
527	result += " " + name;	×
528	}
529	} else if constexpr (std::is_same_v<decltype(kind),
530	btf_kind_function_prototype>) {
531	result += get_qualified_type_name(kind.return_type, visited) + " " +	66✔
532	name + "(";
533	for (auto param : kind.parameters) {	88✔
534	result += get_qualified_type_name(param.type, visited);	66✔
535	if (!param.name.empty()) {	44✔
536	result += " " + param.name;	66✔
537	}
538	result += ", ";	22✔
539	}
540	if (kind.parameters.size() > 0) {	44✔
541	result.pop_back();	22✔
542	result.pop_back();	22✔
543	}
544	result += ")";	22✔
545	} else if constexpr (!btf_kind_traits<decltype(kind)>::has_type) {
546	result += get_type_name(id) + " " + name;	84✔
547	}
548	},	450✔
549	kind);
550
551	visited.erase(id);	225✔
552	return result;	225✔
553	}	225✔
554	} // namespace libbtf

Alan-Jowett / libbtf / 18660514157

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