15194704016

Committed 22 May 2025 08:53AM UTC coverage: 88.11% (-0.07%) from 88.177%

Build # 15194704016

Build Type

push

github

Committed by

elazarg

Commit Message

uniform class names and explicit constructors for adapt_sgraph.hpp

Signed-off-by: Elazar Gershuni <elazarg@gmail.com>

Run Details

27 of 30 new or added lines in 1 file covered. (90.0%)

481 existing lines in 33 files now uncovered.

8552 of 9706 relevant lines covered (88.11%)

9089054.61 hits per line

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

89.13

/src/crab/type_domain.cpp

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

// This file is eBPF-specific, not derived from CRAB.
#include <functional>
#include <map>
#include <optional>

#include "crab/array_domain.hpp"
#include "crab/dsl_syntax.hpp"
#include "crab/split_dbm.hpp"
#include "crab/type_domain.hpp"
#include "crab/type_encoding.hpp"
#include "crab/variable.hpp"
#include "crab_utils/debug.hpp"

namespace prevail {

template <is_enum T>
static void operator++(T& t) {
    t = static_cast<T>(1 + static_cast<std::underlying_type_t<T>>(t));
}

std::vector<DataKind> iterate_kinds(const DataKind lb, const DataKind ub) {
    if (lb > ub) {
        CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);
    }
    if (lb < KIND_MIN || ub > KIND_MAX) {
        CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");
    }
    std::vector<DataKind> res;
    for (DataKind i = lb; i <= ub; ++i) {
        res.push_back(i);
    }
    return res;
}

std::vector<TypeEncoding> iterate_types(const TypeEncoding lb, const TypeEncoding ub) {
    if (lb > ub) {
        CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);
    }
    if (lb < T_MIN || ub > T_MAX) {
        CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");
    }
    std::vector<TypeEncoding> res;
    for (TypeEncoding i = lb; i <= ub; ++i) {
        res.push_back(i);
    }
    return res;
}

static constexpr auto S_UNINIT = "uninit";
static constexpr auto S_STACK = "stack";
static constexpr auto S_PACKET = "packet";
static constexpr auto S_CTX = "ctx";
static constexpr auto S_MAP_PROGRAMS = "map_fd_programs";
static constexpr auto S_MAP = "map_fd";
static constexpr auto S_NUM = "number";
static constexpr auto S_SHARED = "shared";

std::string name_of(const DataKind kind) {
    switch (kind) {
    case DataKind::ctx_offsets: return "ctx_offset";
    case DataKind::map_fds: return "map_fd";
    case DataKind::packet_offsets: return "packet_offset";
    case DataKind::shared_offsets: return "shared_offset";
    case DataKind::shared_region_sizes: return "shared_region_size";
    case DataKind::stack_numeric_sizes: return "stack_numeric_size";
    case DataKind::stack_offsets: return "stack_offset";
    case DataKind::svalues: return "svalue";
    case DataKind::types: return "type";
    case DataKind::uvalues: return "uvalue";
    }
    return {};
}

DataKind regkind(const std::string& s) {
    static const std::map<std::string, DataKind> string_to_kind{
        {"type", DataKind::types},
        {"ctx_offset", DataKind::ctx_offsets},
        {"map_fd", DataKind::map_fds},
        {"packet_offset", DataKind::packet_offsets},
        {"shared_offset", DataKind::shared_offsets},
        {"stack_offset", DataKind::stack_offsets},
        {"shared_region_size", DataKind::shared_region_sizes},
        {"stack_numeric_size", DataKind::stack_numeric_sizes},
        {"svalue", DataKind::svalues},
        {"uvalue", DataKind::uvalues},
    };
    if (string_to_kind.contains(s)) {
        return string_to_kind.at(s);
    }
    throw std::runtime_error(std::string() + "Bad kind: " + s);
}

std::ostream& operator<<(std::ostream& os, const TypeEncoding s) {
    switch (s) {
    case T_SHARED: return os << S_SHARED;
    case T_STACK: return os << S_STACK;
    case T_PACKET: return os << S_PACKET;
    case T_CTX: return os << S_CTX;
    case T_NUM: return os << S_NUM;
    case T_MAP: return os << S_MAP;
    case T_MAP_PROGRAMS: return os << S_MAP_PROGRAMS;
    case T_UNINIT: return os << S_UNINIT;
    default: CRAB_ERROR("Unsupported type encoding", s);
    }
}

TypeEncoding string_to_type_encoding(const std::string& s) {
    static std::map<std::string, TypeEncoding> string_to_type{
        {S_UNINIT, T_UNINIT}, {S_MAP_PROGRAMS, T_MAP_PROGRAMS},
        {S_MAP, T_MAP},       {S_NUM, T_NUM},
        {S_CTX, T_CTX},       {S_STACK, T_STACK},
        {S_PACKET, T_PACKET}, {S_SHARED, T_SHARED},
    };
    if (string_to_type.contains(s)) {
        return string_to_type[s];
    }
    throw std::runtime_error(std::string("Unsupported type name: ") + s);
}
RegPack reg_pack(const int i) {
    return {
        Variable::reg(DataKind::svalues, i),
        Variable::reg(DataKind::uvalues, i),
        Variable::reg(DataKind::ctx_offsets, i),
        Variable::reg(DataKind::map_fds, i),
        Variable::reg(DataKind::packet_offsets, i),
        Variable::reg(DataKind::shared_offsets, i),
        Variable::reg(DataKind::stack_offsets, i),
        Variable::reg(DataKind::types, i),
        Variable::reg(DataKind::shared_region_sizes, i),
        Variable::reg(DataKind::stack_numeric_sizes, i),
    };
}

void TypeDomain::add_extra_invariant(const NumAbsDomain& dst, std::map<Variable, Interval>& extra_invariants,
                                     const Variable type_variable, const TypeEncoding type, const DataKind kind,
                                     const NumAbsDomain& src) const {
    const bool dst_has_type = has_type(dst, type_variable, type);
    const bool src_has_type = has_type(src, type_variable, type);
    Variable v = Variable::kind_var(kind, type_variable);

    // If type is contained in exactly one of dst or src,
    // we need to remember the value.
    if (dst_has_type && !src_has_type) {
        extra_invariants.emplace(v, dst.eval_interval(v));
    } else if (!dst_has_type && src_has_type) {
        extra_invariants.emplace(v, src.eval_interval(v));
    }
}

void TypeDomain::selectively_join_based_on_type(NumAbsDomain& dst, NumAbsDomain&& src) const {
    // Some variables are type-specific.  Type-specific variables
    // for a register can exist in the domain whenever the associated
    // type value is present in the register's types interval (and the
    // value is not Top), and are absent otherwise.  That is, we want
    // to keep track of implications of the form
    // "if register R has type=T then R.T_offset has value ...".
    //
    // If a type value is legal in exactly one of the two domains, a
    // normal join operation would remove any type-specific variables
    // from the resulting merged domain since absence from the other
    // would be interpreted to mean Top.
    //
    // However, when the type value is not present in one domain,
    // any type-specific variables for that type are instead to be
    // interpreted as Bottom, so we want to preserve the values of any
    // type-specific variables from the other domain where the type
    // value is legal.
    //
    // Example input:
    //   r1.type=stack, r1.stack_offset=100
    //   r1.type=packet, r1.packet_offset=4
    // Output:
    //   r1.type={stack,packet}, r1.stack_offset=100, r1.packet_offset=4

    std::map<Variable, Interval> extra_invariants;
    if (!dst.is_bottom()) {
        for (const Variable v : Variable::get_type_variables()) {
            add_extra_invariant(dst, extra_invariants, v, T_CTX, DataKind::ctx_offsets, src);
            add_extra_invariant(dst, extra_invariants, v, T_MAP, DataKind::map_fds, src);
            add_extra_invariant(dst, extra_invariants, v, T_MAP_PROGRAMS, DataKind::map_fds, src);
            add_extra_invariant(dst, extra_invariants, v, T_PACKET, DataKind::packet_offsets, src);
            add_extra_invariant(dst, extra_invariants, v, T_SHARED, DataKind::shared_offsets, src);
            add_extra_invariant(dst, extra_invariants, v, T_STACK, DataKind::stack_offsets, src);
            add_extra_invariant(dst, extra_invariants, v, T_SHARED, DataKind::shared_region_sizes, src);
            add_extra_invariant(dst, extra_invariants, v, T_STACK, DataKind::stack_numeric_sizes, src);
        }
    }

    // Do a normal join operation on the domain.
    dst |= std::move(src);

    // Now add in the extra invariants saved above.
    for (const auto& [variable, interval] : extra_invariants) {
        dst.set(variable, interval);
    }
}

void TypeDomain::assign_type(NumAbsDomain& inv, const Reg& lhs, const Reg& rhs) {
    inv.assign(reg_pack(lhs).type, reg_pack(rhs).type);
}

void TypeDomain::assign_type(NumAbsDomain& inv, const std::optional<Variable> lhs, const LinearExpression& t) {
    inv.assign(lhs, t);
}

void TypeDomain::assign_type(NumAbsDomain& inv, const Reg& lhs, const std::optional<LinearExpression>& rhs) {
    inv.assign(reg_pack(lhs).type, rhs);
}

void TypeDomain::havoc_type(NumAbsDomain& inv, const Reg& r) { inv.havoc(reg_pack(r).type); }

TypeEncoding TypeDomain::get_type(const NumAbsDomain& inv, const LinearExpression& v) const {
    const auto res = inv.eval_interval(v).singleton();
    if (!res) {
        return T_UNINIT;
    }
    return res->narrow<TypeEncoding>();
}

TypeEncoding TypeDomain::get_type(const NumAbsDomain& inv, const Reg& r) const {
    const auto res = inv.eval_interval(reg_pack(r).type).singleton();
    if (!res) {
        return T_UNINIT;
    }
    return res->narrow<TypeEncoding>();
}

// Check whether a given type value is within the range of a given type variable's value.
bool TypeDomain::has_type(const NumAbsDomain& inv, const Reg& r, const TypeEncoding type) const {
    const Interval interval = inv.eval_interval(reg_pack(r).type);
    return interval.contains(type);
}

bool TypeDomain::has_type(const NumAbsDomain& inv, const LinearExpression& v, const TypeEncoding type) const {
    const Interval interval = inv.eval_interval(v);
    return interval.contains(type);
}

NumAbsDomain TypeDomain::join_over_types(const NumAbsDomain& inv, const Reg& reg,
                                         const std::function<void(NumAbsDomain&, TypeEncoding)>& transition) const {
    Interval types = inv.eval_interval(reg_pack(reg).type);
    if (types.is_bottom()) {
        return NumAbsDomain::bottom();
    }
    if (types.contains(T_UNINIT)) {
        NumAbsDomain res(inv);
        transition(res, T_UNINIT);
        return res;
    }
    NumAbsDomain res = NumAbsDomain::bottom();
    auto [lb, ub] = types.bound(T_MIN, T_MAX);
    for (TypeEncoding type : iterate_types(lb, ub)) {
        NumAbsDomain tmp(inv);
        transition(tmp, type);
        selectively_join_based_on_type(res, std::move(tmp)); // res |= tmp;
    }
    return res;
}

NumAbsDomain TypeDomain::join_by_if_else(const NumAbsDomain& inv, const LinearConstraint& condition,
                                         const std::function<void(NumAbsDomain&)>& if_true,
                                         const std::function<void(NumAbsDomain&)>& if_false) const {
    NumAbsDomain true_case(inv.when(condition));
    if_true(true_case);

    NumAbsDomain false_case(inv.when(condition.negate()));
    if_false(false_case);

    return true_case | false_case;
}

static LinearConstraint eq_types(const Reg& a, const Reg& b) {
    using namespace dsl_syntax;
    return eq(reg_pack(a).type, reg_pack(b).type);
}

bool TypeDomain::same_type(const NumAbsDomain& inv, const Reg& a, const Reg& b) const {
    return inv.entail(eq_types(a, b));
}

bool TypeDomain::implies_type(const NumAbsDomain& inv, const LinearConstraint& a, const LinearConstraint& b) const {
    return inv.when(a).entail(b);
}

bool TypeDomain::is_in_group(const NumAbsDomain& inv, const Reg& r, const TypeGroup group) const {
    using namespace dsl_syntax;
    const Variable t = reg_pack(r).type;
    switch (group) {
    case TypeGroup::number: return inv.entail(t == T_NUM);
    case TypeGroup::map_fd: return inv.entail(t == T_MAP);
    case TypeGroup::map_fd_programs: return inv.entail(t == T_MAP_PROGRAMS);
    case TypeGroup::ctx: return inv.entail(t == T_CTX);
    case TypeGroup::packet: return inv.entail(t == T_PACKET);
    case TypeGroup::stack: return inv.entail(t == T_STACK);
    case TypeGroup::shared: return inv.entail(t == T_SHARED);
    case TypeGroup::mem: return inv.entail(t >= T_PACKET);
    case TypeGroup::mem_or_num: return inv.entail(t >= T_NUM) && inv.entail(t != T_CTX);
    case TypeGroup::pointer: return inv.entail(t >= T_CTX);
    case TypeGroup::ptr_or_num: return inv.entail(t >= T_NUM);
    case TypeGroup::stack_or_packet: return inv.entail(t >= T_PACKET) && inv.entail(t <= T_STACK);
    case TypeGroup::singleton_ptr: return inv.entail(t >= T_CTX) && inv.entail(t <= T_STACK);
    default: CRAB_ERROR("Unsupported type group", group);
    }
}

std::string typeset_to_string(const std::vector<TypeEncoding>& items) {
    std::stringstream ss;
    ss << "{";
    for (auto it = items.begin(); it != items.end(); ++it) {
        ss << *it;
        if (std::next(it) != items.end()) {
            ss << ", ";
        }
    }
    ss << "}";
    return ss.str();
}

bool is_singleton_type(const TypeGroup t) {
    switch (t) {
    case TypeGroup::number:
    case TypeGroup::map_fd:
    case TypeGroup::map_fd_programs:
    case TypeGroup::ctx:
    case TypeGroup::packet:
    case TypeGroup::stack:
    case TypeGroup::shared: return true;
    default: return false;
    }
}

std::ostream& operator<<(std::ostream& os, const TypeGroup ts) {
    using namespace prevail;
    static const std::map<TypeGroup, std::string> string_to_type{
        {TypeGroup::number, S_NUM},
        {TypeGroup::map_fd, S_MAP},
        {TypeGroup::map_fd_programs, S_MAP_PROGRAMS},
        {TypeGroup::ctx, S_CTX},
        {TypeGroup::packet, S_PACKET},
        {TypeGroup::stack, S_STACK},
        {TypeGroup::shared, S_SHARED},
        {TypeGroup::mem, typeset_to_string({T_STACK, T_PACKET, T_SHARED})},
        {TypeGroup::pointer, typeset_to_string({T_CTX, T_STACK, T_PACKET, T_SHARED})},
        {TypeGroup::ptr_or_num, typeset_to_string({T_NUM, T_CTX, T_STACK, T_PACKET, T_SHARED})},
        {TypeGroup::stack_or_packet, typeset_to_string({T_STACK, T_PACKET})},
        {TypeGroup::singleton_ptr, typeset_to_string({T_CTX, T_STACK, T_PACKET})},
        {TypeGroup::mem_or_num, typeset_to_string({T_NUM, T_STACK, T_PACKET, T_SHARED})},
    };
    if (string_to_type.contains(ts)) {
        return os << string_to_type.at(ts);
    }
    CRAB_ERROR("Unsupported type group", ts);
}

} // namespace prevail

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3	// ReSharper disable CppMemberFunctionMayBeStatic
4
5	// This file is eBPF-specific, not derived from CRAB.
6	#include <functional>
7	#include <map>
8	#include <optional>
9
10	#include "crab/array_domain.hpp"
11	#include "crab/dsl_syntax.hpp"
12	#include "crab/split_dbm.hpp"
13	#include "crab/type_domain.hpp"
14	#include "crab/type_encoding.hpp"
15	#include "crab/variable.hpp"
16	#include "crab_utils/debug.hpp"
17
18	namespace prevail {
19
20	template <is_enum T>
21	static void operator++(T& t) {	124,732✔
22	t = static_cast<T>(1 + static_cast<std::underlying_type_t<T>>(t));	124,732✔
23	}	124,732✔
24
25	std::vector<DataKind> iterate_kinds(const DataKind lb, const DataKind ub) {	486✔
26	if (lb > ub) {	486✔
27	CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);	×
28	}
29	if (lb < KIND_MIN \|\| ub > KIND_MAX) {	486✔
30	CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");	×
31	}
32	std::vector<DataKind> res;	486✔
33	for (DataKind i = lb; i <= ub; ++i) {	5,346✔
34	res.push_back(i);	4,860✔
35	}
36	return res;	486✔
37	}	×
38
39	std::vector<TypeEncoding> iterate_types(const TypeEncoding lb, const TypeEncoding ub) {	119,558✔
40	if (lb > ub) {	119,558✔
41	CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);	×
42	}
43	if (lb < T_MIN \|\| ub > T_MAX) {	119,558✔
44	CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");	×
45	}
46	std::vector<TypeEncoding> res;	119,558✔
47	for (TypeEncoding i = lb; i <= ub; ++i) {	239,430✔
48	res.push_back(i);	119,872✔
49	}
50	return res;	119,558✔
51	}	×
52
53	static constexpr auto S_UNINIT = "uninit";
54	static constexpr auto S_STACK = "stack";
55	static constexpr auto S_PACKET = "packet";
56	static constexpr auto S_CTX = "ctx";
57	static constexpr auto S_MAP_PROGRAMS = "map_fd_programs";
58	static constexpr auto S_MAP = "map_fd";
59	static constexpr auto S_NUM = "number";
60	static constexpr auto S_SHARED = "shared";
61
62	std::string name_of(const DataKind kind) {	33,598,578✔
63	switch (kind) {	33,598,578✔
64	case DataKind::ctx_offsets: return "ctx_offset";	6,575,982✔
65	case DataKind::map_fds: return "map_fd";	9,401,230✔
66	case DataKind::packet_offsets: return "packet_offset";	6,563,818✔
67	case DataKind::shared_offsets: return "shared_offset";	6,563,926✔
68	case DataKind::shared_region_sizes: return "shared_region_size";	6,563,926✔
69	case DataKind::stack_numeric_sizes: return "stack_numeric_size";	9,985,960✔
70	case DataKind::stack_offsets: return "stack_offset";	9,984,532✔
71	case DataKind::svalues: return "svalue";	3,892,358✔
72	case DataKind::types: return "type";	3,822,450✔
73	case DataKind::uvalues: return "uvalue";	3,842,990✔
74	}
75	return {};	×
76	}
77
78	DataKind regkind(const std::string& s) {	4,560✔
79	static const std::map<std::string, DataKind> string_to_kind{	2,280✔
80	{"type", DataKind::types},	39✔
81	{"ctx_offset", DataKind::ctx_offsets},	39✔
82	{"map_fd", DataKind::map_fds},	39✔
83	{"packet_offset", DataKind::packet_offsets},	39✔
84	{"shared_offset", DataKind::shared_offsets},	39✔
85	{"stack_offset", DataKind::stack_offsets},	39✔
86	{"shared_region_size", DataKind::shared_region_sizes},	39✔
87	{"stack_numeric_size", DataKind::stack_numeric_sizes},	39✔
88	{"svalue", DataKind::svalues},	39✔
89	{"uvalue", DataKind::uvalues},	39✔
90	};	5,457✔
91	if (string_to_kind.contains(s)) {	4,560✔
92	return string_to_kind.at(s);	4,560✔
93	}
94	throw std::runtime_error(std::string() + "Bad kind: " + s);	×
95	}	78✔
96
97	std::ostream& operator<<(std::ostream& os, const TypeEncoding s) {	2,012✔
98	switch (s) {	2,012✔
99	case T_SHARED: return os << S_SHARED;	102✔
100	case T_STACK: return os << S_STACK;	248✔
101	case T_PACKET: return os << S_PACKET;	114✔
102	case T_CTX: return os << S_CTX;	98✔
103	case T_NUM: return os << S_NUM;	1,426✔
104	case T_MAP: return os << S_MAP;	18✔
105	case T_MAP_PROGRAMS: return os << S_MAP_PROGRAMS;	6✔
106	case T_UNINIT: return os << S_UNINIT;	×
107	default: CRAB_ERROR("Unsupported type encoding", s);	×
108	}
109	}
110
111	TypeEncoding string_to_type_encoding(const std::string& s) {	2,532✔
112	static std::map<std::string, TypeEncoding> string_to_type{	1,266✔
113	{S_UNINIT, T_UNINIT}, {S_MAP_PROGRAMS, T_MAP_PROGRAMS},	39✔
114	{S_MAP, T_MAP}, {S_NUM, T_NUM},	78✔
115	{S_CTX, T_CTX}, {S_STACK, T_STACK},	78✔
116	{S_PACKET, T_PACKET}, {S_SHARED, T_SHARED},	78✔
117	};	3,273✔
118	if (string_to_type.contains(s)) {	2,532✔
119	return string_to_type[s];	2,532✔
120	}
121	throw std::runtime_error(std::string("Unsupported type name: ") + s);	×
122	}	78✔
123	RegPack reg_pack(const int i) {	1,860,532✔
124	return {	930,265✔
125	Variable::reg(DataKind::svalues, i),	1,860,532✔
126	Variable::reg(DataKind::uvalues, i),	1,860,532✔
127	Variable::reg(DataKind::ctx_offsets, i),	1,860,532✔
128	Variable::reg(DataKind::map_fds, i),	1,860,532✔
129	Variable::reg(DataKind::packet_offsets, i),	1,860,532✔
130	Variable::reg(DataKind::shared_offsets, i),	1,860,532✔
131	Variable::reg(DataKind::stack_offsets, i),	1,860,532✔
132	Variable::reg(DataKind::types, i),	1,860,532✔
133	Variable::reg(DataKind::shared_region_sizes, i),	1,860,532✔
134	Variable::reg(DataKind::stack_numeric_sizes, i),	1,860,532✔
135	};	1,860,532✔
136	}
137
138	void TypeDomain::add_extra_invariant(const NumAbsDomain& dst, std::map<Variable, Interval>& extra_invariants,	11,355,664✔
139	const Variable type_variable, const TypeEncoding type, const DataKind kind,
140	const NumAbsDomain& src) const {
141	const bool dst_has_type = has_type(dst, type_variable, type);	11,355,664✔
142	const bool src_has_type = has_type(src, type_variable, type);	11,355,664✔
143	Variable v = Variable::kind_var(kind, type_variable);	11,355,664✔
144
145	// If type is contained in exactly one of dst or src,
146	// we need to remember the value.
147	if (dst_has_type && !src_has_type) {	11,355,664✔
148	extra_invariants.emplace(v, dst.eval_interval(v));	850,710✔
149	} else if (!dst_has_type && src_has_type) {	10,788,524✔
150	extra_invariants.emplace(v, src.eval_interval(v));	108,243✔
151	}
152	}	11,355,664✔
153
154	void TypeDomain::selectively_join_based_on_type(NumAbsDomain& dst, NumAbsDomain&& src) const {	144,052✔
155	// Some variables are type-specific. Type-specific variables
156	// for a register can exist in the domain whenever the associated
157	// type value is present in the register's types interval (and the
158	// value is not Top), and are absent otherwise. That is, we want
159	// to keep track of implications of the form
160	// "if register R has type=T then R.T_offset has value ...".
161	//
162	// If a type value is legal in exactly one of the two domains, a
163	// normal join operation would remove any type-specific variables
164	// from the resulting merged domain since absence from the other
165	// would be interpreted to mean Top.
166	//
167	// However, when the type value is not present in one domain,
168	// any type-specific variables for that type are instead to be
169	// interpreted as Bottom, so we want to preserve the values of any
170	// type-specific variables from the other domain where the type
171	// value is legal.
172	//
173	// Example input:
174	// r1.type=stack, r1.stack_offset=100
175	// r1.type=packet, r1.packet_offset=4
176	// Output:
177	// r1.type={stack,packet}, r1.stack_offset=100, r1.packet_offset=4
178
179	std::map<Variable, Interval> extra_invariants;	144,052✔
180	if (!dst.is_bottom()) {	144,052✔
181	for (const Variable v : Variable::get_type_variables()) {	1,443,976✔
182	add_extra_invariant(dst, extra_invariants, v, T_CTX, DataKind::ctx_offsets, src);	1,419,458✔
183	add_extra_invariant(dst, extra_invariants, v, T_MAP, DataKind::map_fds, src);	1,419,458✔
184	add_extra_invariant(dst, extra_invariants, v, T_MAP_PROGRAMS, DataKind::map_fds, src);	1,419,458✔
185	add_extra_invariant(dst, extra_invariants, v, T_PACKET, DataKind::packet_offsets, src);	1,419,458✔
186	add_extra_invariant(dst, extra_invariants, v, T_SHARED, DataKind::shared_offsets, src);	1,419,458✔
187	add_extra_invariant(dst, extra_invariants, v, T_STACK, DataKind::stack_offsets, src);	1,419,458✔
188	add_extra_invariant(dst, extra_invariants, v, T_SHARED, DataKind::shared_region_sizes, src);	1,419,458✔
189	add_extra_invariant(dst, extra_invariants, v, T_STACK, DataKind::stack_numeric_sizes, src);	1,419,458✔
190	}	24,518✔
191	}
192
193	// Do a normal join operation on the domain.
194	dst \|= std::move(src);	144,052✔
195
196	// Now add in the extra invariants saved above.
197	for (const auto& [variable, interval] : extra_invariants) {	709,226✔
198	dst.set(variable, interval);	565,174✔
199	}
200	}	144,052✔
201
202	void TypeDomain::assign_type(NumAbsDomain& inv, const Reg& lhs, const Reg& rhs) {	36,520✔
203	inv.assign(reg_pack(lhs).type, reg_pack(rhs).type);	36,520✔
204	}	36,520✔
205
206	void TypeDomain::assign_type(NumAbsDomain& inv, const std::optional<Variable> lhs, const LinearExpression& t) {	31,670✔
207	inv.assign(lhs, t);	31,670✔
208	}	31,670✔
209
210	void TypeDomain::assign_type(NumAbsDomain& inv, const Reg& lhs, const std::optional<LinearExpression>& rhs) {	108,523✔
211	inv.assign(reg_pack(lhs).type, rhs);	108,523✔
212	}	108,523✔
213
214	void TypeDomain::havoc_type(NumAbsDomain& inv, const Reg& r) { inv.havoc(reg_pack(r).type); }	103,014✔
215
216	TypeEncoding TypeDomain::get_type(const NumAbsDomain& inv, const LinearExpression& v) const {	44,770✔
217	const auto res = inv.eval_interval(v).singleton();	44,770✔
218	if (!res) {	44,770✔
219	return T_UNINIT;	145✔
220	}
221	return res->narrow<TypeEncoding>();	44,480✔
222	}	44,770✔
223
224	TypeEncoding TypeDomain::get_type(const NumAbsDomain& inv, const Reg& r) const {	8✔
225	const auto res = inv.eval_interval(reg_pack(r).type).singleton();	12✔
226	if (!res) {	8✔
227	return T_UNINIT;	2✔
228	}
229	return res->narrow<TypeEncoding>();	4✔
230	}	8✔
231
232	// Check whether a given type value is within the range of a given type variable's value.
233	bool TypeDomain::has_type(const NumAbsDomain& inv, const Reg& r, const TypeEncoding type) const {	239,496✔
234	const Interval interval = inv.eval_interval(reg_pack(r).type);	239,496✔
235	return interval.contains(type);	359,244✔
236	}	239,496✔
237
238	bool TypeDomain::has_type(const NumAbsDomain& inv, const LinearExpression& v, const TypeEncoding type) const {	25,512,367✔
239	const Interval interval = inv.eval_interval(v);	25,512,367✔
240	return interval.contains(type);	38,268,550✔
241	}	25,512,367✔
242
243	NumAbsDomain TypeDomain::join_over_types(const NumAbsDomain& inv, const Reg& reg,	120,646✔
244	const std::function<void(NumAbsDomain&, TypeEncoding)>& transition) const {
245	Interval types = inv.eval_interval(reg_pack(reg).type);	120,646✔
246	if (types.is_bottom()) {	120,646✔
247	return NumAbsDomain::bottom();	×
248	}
249	if (types.contains(T_UNINIT)) {	120,646✔
250	NumAbsDomain res(inv);	1,114✔
251	transition(res, T_UNINIT);	1,114✔
252	return res;	1,114✔
253	}	1,114✔
254	NumAbsDomain res = NumAbsDomain::bottom();	119,532✔
255	auto [lb, ub] = types.bound(T_MIN, T_MAX);	119,532✔
256	for (TypeEncoding type : iterate_types(lb, ub)) {	239,352✔
257	NumAbsDomain tmp(inv);	119,820✔
258	transition(tmp, type);	119,820✔
259	selectively_join_based_on_type(res, std::move(tmp)); // res \|= tmp;	119,820✔
260	}	239,352✔
261	return res;	119,532✔
262	}	180,412✔
263
264	NumAbsDomain TypeDomain::join_by_if_else(const NumAbsDomain& inv, const LinearConstraint& condition,	×
265	const std::function<void(NumAbsDomain&)>& if_true,
266	const std::function<void(NumAbsDomain&)>& if_false) const {
267	NumAbsDomain true_case(inv.when(condition));	×
268	if_true(true_case);	×
269
270	NumAbsDomain false_case(inv.when(condition.negate()));	×
271	if_false(false_case);	×
272
273	return true_case \| false_case;	×
274	}	×
275
276	static LinearConstraint eq_types(const Reg& a, const Reg& b) {	18,860✔
277	using namespace dsl_syntax;	9,430✔
278	return eq(reg_pack(a).type, reg_pack(b).type);	18,860✔
279	}
280
281	bool TypeDomain::same_type(const NumAbsDomain& inv, const Reg& a, const Reg& b) const {	18,860✔
282	return inv.entail(eq_types(a, b));	28,290✔
283	}
284
285	bool TypeDomain::implies_type(const NumAbsDomain& inv, const LinearConstraint& a, const LinearConstraint& b) const {	2,768✔
286	return inv.when(a).entail(b);	4,152✔
287	}
288
289	bool TypeDomain::is_in_group(const NumAbsDomain& inv, const Reg& r, const TypeGroup group) const {	93,484✔
290	using namespace dsl_syntax;	46,742✔
291	const Variable t = reg_pack(r).type;	93,484✔
292	switch (group) {	93,484✔
293	case TypeGroup::number: return inv.entail(t == T_NUM);	70,827✔
294	case TypeGroup::map_fd: return inv.entail(t == T_MAP);	4,482✔
295	case TypeGroup::map_fd_programs: return inv.entail(t == T_MAP_PROGRAMS);	414✔
296	case TypeGroup::ctx: return inv.entail(t == T_CTX);	7,854✔
UNCOV 297	case TypeGroup::packet: return inv.entail(t == T_PACKET);	×
298	case TypeGroup::stack: return inv.entail(t == T_STACK);	×
299	case TypeGroup::shared: return inv.entail(t == T_SHARED);	×
300	case TypeGroup::mem: return inv.entail(t >= T_PACKET);	11,252✔
301	case TypeGroup::mem_or_num: return inv.entail(t >= T_NUM) && inv.entail(t != T_CTX);	2,380✔
302	case TypeGroup::pointer: return inv.entail(t >= T_CTX);	28,680✔
303	case TypeGroup::ptr_or_num: return inv.entail(t >= T_NUM);	26,260✔
UNCOV 304	case TypeGroup::stack_or_packet: return inv.entail(t >= T_PACKET) && inv.entail(t <= T_STACK);	×
305	case TypeGroup::singleton_ptr: return inv.entail(t >= T_CTX) && inv.entail(t <= T_STACK);	6,122✔
UNCOV 306	default: CRAB_ERROR("Unsupported type group", group);	×
307	}
308	}
309
310	std::string typeset_to_string(const std::vector<TypeEncoding>& items) {	50✔
311	std::stringstream ss;	50✔
312	ss << "{";	50✔
313	for (auto it = items.begin(); it != items.end(); ++it) {	186✔
314	ss << *it;	136✔
315	if (std::next(it) != items.end()) {	204✔
316	ss << ", ";	86✔
317	}
318	}
319	ss << "}";	50✔
320	return ss.str();	100✔
321	}	50✔
322
323	bool is_singleton_type(const TypeGroup t) {	2,164✔
324	switch (t) {	2,164✔
325	case TypeGroup::number:	1,056✔
326	case TypeGroup::map_fd:
327	case TypeGroup::map_fd_programs:
328	case TypeGroup::ctx:
329	case TypeGroup::packet:
330	case TypeGroup::stack:
331	case TypeGroup::shared: return true;	1,056✔
332	default: return false;	52✔
333	}
334	}
335
336	std::ostream& operator<<(std::ostream& os, const TypeGroup ts) {	4,368✔
337	using namespace prevail;	2,184✔
338	static const std::map<TypeGroup, std::string> string_to_type{	2,184✔
339	{TypeGroup::number, S_NUM},	2✔
340	{TypeGroup::map_fd, S_MAP},	2✔
341	{TypeGroup::map_fd_programs, S_MAP_PROGRAMS},	2✔
342	{TypeGroup::ctx, S_CTX},	2✔
343	{TypeGroup::packet, S_PACKET},	2✔
344	{TypeGroup::stack, S_STACK},	2✔
345	{TypeGroup::shared, S_SHARED},	2✔
346	{TypeGroup::mem, typeset_to_string({T_STACK, T_PACKET, T_SHARED})},	8✔
347	{TypeGroup::pointer, typeset_to_string({T_CTX, T_STACK, T_PACKET, T_SHARED})},	8✔
348	{TypeGroup::ptr_or_num, typeset_to_string({T_NUM, T_CTX, T_STACK, T_PACKET, T_SHARED})},	8✔
349	{TypeGroup::stack_or_packet, typeset_to_string({T_STACK, T_PACKET})},	8✔
350	{TypeGroup::singleton_ptr, typeset_to_string({T_CTX, T_STACK, T_PACKET})},	8✔
351	{TypeGroup::mem_or_num, typeset_to_string({T_NUM, T_STACK, T_PACKET, T_SHARED})},	8✔
352	};	4,430✔
353	if (string_to_type.contains(ts)) {	4,368✔
354	return os << string_to_type.at(ts);	4,368✔
355	}
UNCOV 356	CRAB_ERROR("Unsupported type group", ts);	×
357	}	28✔
358
359	} // namespace prevail

Alan-Jowett / ebpf-verifier / 15194704016

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