12845504567

Committed 18 Jan 2025 04:08PM UTC coverage: 88.169% (-1.5%) from 89.646%

Build # 12845504567

Build Type

push

github

Committed by

web-flow

Commit Message

Handle upgrade from LCOV 1.15 to LCOV 2.0 (#826)

* Testing code coverage with a comment only change
* Workaround for failing code coverage
* Testing code coverage fix

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

Coverage Stats

8481 of 9619 relevant lines covered (88.17%)

7430805.79 hits per line

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

85.51

/src/asm_syntax.hpp

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

#include <optional>
#include <ostream>
#include <string>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>

#include "crab/label.hpp"
#include "crab/type_encoding.hpp"
#include "crab_utils/num_safety.hpp"
#include "spec_type_descriptors.hpp"

using crab::label_t;

// Assembly syntax.
namespace asm_syntax {

/// Immediate argument.
struct Imm {
    uint64_t v{};
    constexpr bool operator==(const Imm&) const = default;
};

/// Register argument.
struct Reg {
    uint8_t v{};
    constexpr bool operator==(const Reg&) const = default;
};

using Value = std::variant<Imm, Reg>;

/// Binary operation.
struct Bin {
    enum class Op {
        MOV,
        ADD,
        SUB,
        MUL,
        UDIV,
        UMOD,
        OR,
        AND,
        LSH,
        RSH,
        ARSH,
        XOR,
        SDIV,
        SMOD,
        MOVSX8,
        MOVSX16,
        MOVSX32,
    };

    Op op;
    Reg dst; ///< Destination.
    Value v;
    bool is64{};
    bool lddw{};
    constexpr bool operator==(const Bin&) const = default;
};

/// Unary operation.
struct Un {
    enum class Op {
        BE16,   // dst = htobe16(dst)
        BE32,   // dst = htobe32(dst)
        BE64,   // dst = htobe64(dst)
        LE16,   // dst = htole16(dst)
        LE32,   // dst = htole32(dst)
        LE64,   // dst = htole64(dst)
        SWAP16, // dst = bswap16(dst)
        SWAP32, // dst = bswap32(dst)
        SWAP64, // dst = bswap64(dst)
        NEG,    // dst = -dst
    };

    Op op{};
    Reg dst;
    bool is64{};
    constexpr bool operator==(const Un&) const = default;
};

/// This instruction is encoded similarly to LDDW.
/// See comment in makeLddw() at asm_unmarshal.cpp
struct LoadMapFd {
    Reg dst;
    int32_t mapfd{};
    constexpr bool operator==(const LoadMapFd&) const = default;
};

struct Condition {
    enum class Op {
        EQ,
        NE,
        SET,
        NSET, // NSET does not exist in ebpf
        LT,
        LE,
        GT,
        GE,
        SLT,
        SLE,
        SGT,
        SGE,
    };

    Op op;
    Reg left;
    Value right;
    bool is64{};
    constexpr bool operator==(const Condition&) const = default;
};

struct Jmp {
    std::optional<Condition> cond;
    label_t target;
    bool operator==(const Jmp&) const = default;
};

struct ArgSingle {
    // see comments in spec_prototypes.hpp
    enum class Kind {
        MAP_FD,
        MAP_FD_PROGRAMS,
        PTR_TO_MAP_KEY,
        PTR_TO_MAP_VALUE,
        PTR_TO_CTX,
        ANYTHING,
    } kind{};
    Reg reg;
    constexpr bool operator==(const ArgSingle&) const = default;
};

/// Pair of arguments to a function for pointer and size.
struct ArgPair {
    enum class Kind {
        PTR_TO_READABLE_MEM,
        PTR_TO_READABLE_MEM_OR_NULL,
        PTR_TO_WRITABLE_MEM,
    } kind{};
    Reg mem;  ///< Pointer.
    Reg size; ///< Size of space pointed to.
    bool can_be_zero{};
    constexpr bool operator==(const ArgPair&) const = default;
};

struct Call {
    int32_t func{};
    constexpr bool operator==(const Call& other) const { return func == other.func; }

    // TODO: move name and signature information somewhere else
    std::string name;
    bool is_map_lookup{};
    bool reallocate_packet{};
    std::vector<ArgSingle> singles;
    std::vector<ArgPair> pairs;
    std::string stack_frame_prefix; ///< Variable prefix at point of call.
};

/// Call a "function" (macro) within the same program.
struct CallLocal {
    label_t target;
    std::string stack_frame_prefix; ///< Variable prefix to be used within the call.
    bool operator==(const CallLocal& other) const noexcept = default;
};

struct Exit {
    std::string stack_frame_prefix; ///< Variable prefix to clean up when exiting.
    bool operator==(const Exit& other) const noexcept = default;
};

/// Experimental callx instruction.
struct Callx {
    Reg func;
    constexpr bool operator==(const Callx&) const = default;
};

struct Deref {
    int32_t width{};
    Reg basereg;
    int32_t offset{};
    constexpr bool operator==(const Deref&) const = default;
};

/// Load/store instruction.
struct Mem {
    Deref access;
    Value value;
    bool is_load{};
    constexpr bool operator==(const Mem&) const = default;
};

/// A deprecated instruction for checked access to packets; it is actually a
/// function call, and analyzed as one, e.g., by scratching caller-saved
/// registers after it is performed.
struct Packet {
    int32_t width{};
    int32_t offset{};
    std::optional<Reg> regoffset;
    constexpr bool operator==(const Packet&) const = default;
};

/// Special instruction for atomically updating values inside shared memory.
/// The analysis just treats an atomic operation as a series of consecutive
/// operations, and the atomicity itself is not significant.
struct Atomic {
    enum class Op {
        ADD = 0x00,
        OR = 0x40,
        AND = 0x50,
        XOR = 0xa0,
        XCHG = 0xe0,    // Only valid with fetch=true.
        CMPXCHG = 0xf0, // Only valid with fetch=true.
    };

    Op op{};
    bool fetch{};
    Deref access;
    Reg valreg;
    constexpr bool operator==(const Atomic&) const = default;
};

/// Not an instruction, just used for failure cases.
struct Undefined {
    int opcode{};
    constexpr bool operator==(const Undefined&) const = default;
};

/// When a CFG is translated to its nondeterministic form, Conditional Jump
/// instructions are replaced by two Assume instructions, immediately after
/// the branch and before each jump target.
struct Assume {
    Condition cond;

    // True if the condition is implicitly written in the program (False for tests).
    bool is_implicit{true};

    constexpr bool operator==(const Assume&) const = default;
};

struct IncrementLoopCounter {
    label_t name;
    bool operator==(const IncrementLoopCounter&) const = default;
};

using Instruction = std::variant<Undefined, Bin, Un, LoadMapFd, Call, CallLocal, Callx, Exit, Jmp, Mem, Packet, Atomic,
                                 Assume, IncrementLoopCounter>;

using LabeledInstruction = std::tuple<label_t, Instruction, std::optional<btf_line_info_t>>;
using InstructionSeq = std::vector<LabeledInstruction>;

/// Condition check whether something is a valid size.
struct ValidSize {
    Reg reg;
    bool can_be_zero{};
    constexpr bool operator==(const ValidSize&) const = default;
};

/// Condition check whether two registers can be compared with each other.
/// For example, one is not allowed to compare a number with a pointer,
/// or compare pointers to different memory regions.
struct Comparable {
    Reg r1;
    Reg r2;
    bool or_r2_is_number{}; ///< true for subtraction, false for comparison
    constexpr bool operator==(const Comparable&) const = default;
};

// ptr: ptr -> num : num
struct Addable {
    Reg ptr;
    Reg num;
    constexpr bool operator==(const Addable&) const = default;
};

// Condition check whether a register contains a non-zero number.
struct ValidDivisor {
    Reg reg;
    bool is_signed{};
    constexpr bool operator==(const ValidDivisor&) const = default;
};

enum class AccessType {
    compare,
    read,  // Memory pointed to must be initialized.
    write, // Memory pointed to must be writable.
};

struct ValidAccess {
    int call_stack_depth{};
    Reg reg;
    int32_t offset{};
    Value width{Imm{0}};
    bool or_null{};
    AccessType access_type{};
    constexpr bool operator==(const ValidAccess&) const = default;
};

/// Condition check whether something is a valid key value.
struct ValidMapKeyValue {
    Reg access_reg;
    Reg map_fd_reg;
    bool key{};
    constexpr bool operator==(const ValidMapKeyValue&) const = default;
};

/// Condition check whether a call is valid in the current context.
struct ValidCall {
    int32_t func{};
    std::string stack_frame_prefix; ///< Variable prefix at point of call.
    bool operator==(const ValidCall&) const = default;
};

// "if mem is not stack, val is num"
struct ValidStore {
    Reg mem;
    Reg val;
    constexpr bool operator==(const ValidStore&) const = default;
};

using crab::TypeGroup;
struct TypeConstraint {
    Reg reg;
    TypeGroup types;
    constexpr bool operator==(const TypeConstraint&) const = default;
};

struct FuncConstraint {
    Reg reg;
    constexpr bool operator==(const FuncConstraint&) const = default;
};

/// Condition check whether something is a valid size.
struct ZeroCtxOffset {
    Reg reg;
    constexpr bool operator==(const ZeroCtxOffset&) const = default;
};

struct BoundedLoopCount {
    label_t name;
    bool operator==(const BoundedLoopCount&) const = default;
    // Maximum number of loop iterations allowed during verification.
    // This prevents infinite loops while allowing reasonable bounded loops.
    // When exceeded, verification fails as the loop might not terminate.
    static constexpr int limit = 100000;
};

using Assertion = std::variant<Comparable, Addable, ValidDivisor, ValidAccess, ValidStore, ValidSize, ValidMapKeyValue,
                               ValidCall, TypeConstraint, FuncConstraint, ZeroCtxOffset, BoundedLoopCount>;

std::ostream& operator<<(std::ostream& os, Instruction const& ins);
std::string to_string(Instruction const& ins);

std::ostream& operator<<(std::ostream& os, Bin::Op op);
std::ostream& operator<<(std::ostream& os, Condition::Op op);

inline std::ostream& operator<<(std::ostream& os, const Imm imm) { return os << crab::to_signed(imm.v); }
inline std::ostream& operator<<(std::ostream& os, Reg const& a) { return os << "r" << gsl::narrow<int>(a.v); }
inline std::ostream& operator<<(std::ostream& os, Value const& a) {
    if (const auto pa = std::get_if<Imm>(&a)) {
        return os << *pa;
    }
    return os << std::get<Reg>(a);
}

std::ostream& operator<<(std::ostream& os, const Assertion& a);
std::string to_string(const Assertion& constraint);

void print(const InstructionSeq& insts, std::ostream& out, const std::optional<const label_t>& label_to_print,
           bool print_line_info = false);

} // namespace asm_syntax

using namespace asm_syntax;
using crab::pc_t;

template <class... Ts>
struct overloaded : Ts... {
    using Ts::operator()...;
};

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3	#pragma once
4
5	#include <optional>
6	#include <ostream>
7	#include <string>
8	#include <tuple>
9	#include <utility>
10	#include <variant>
11	#include <vector>
12
13	#include "crab/label.hpp"
14	#include "crab/type_encoding.hpp"
15	#include "crab_utils/num_safety.hpp"
16	#include "spec_type_descriptors.hpp"
17
18	using crab::label_t;
19
20	// Assembly syntax.
21	namespace asm_syntax {
22
23	/// Immediate argument.
24	struct Imm {
25	uint64_t v{};	75,282✔
26	constexpr bool operator==(const Imm&) const = default;	75,282✔
27	};
28
29	/// Register argument.
30	struct Reg {
31	uint8_t v{};	14,618✔
32	constexpr bool operator==(const Reg&) const = default;	7,365✔
33	};
34
35	using Value = std::variant<Imm, Reg>;
36
37	/// Binary operation.
38	struct Bin {
39	enum class Op {
40	MOV,
41	ADD,
42	SUB,
43	MUL,
44	UDIV,
45	UMOD,
46	OR,
47	AND,
48	LSH,
49	RSH,
50	ARSH,
51	XOR,
52	SDIV,
53	SMOD,
54	MOVSX8,
55	MOVSX16,
56	MOVSX32,
57	};
58
59	Op op;	156,832✔
60	Reg dst; ///< Destination.	14,332✔
61	Value v;	14,332✔
62	bool is64{};	9,754✔
63	bool lddw{};	9,754✔
64	constexpr bool operator==(const Bin&) const = default;	156,832✔
65	};
66
67	/// Unary operation.
68	struct Un {
69	enum class Op {
70	BE16, // dst = htobe16(dst)
71	BE32, // dst = htobe32(dst)
72	BE64, // dst = htobe64(dst)
73	LE16, // dst = htole16(dst)
74	LE32, // dst = htole32(dst)
75	LE64, // dst = htole64(dst)
76	SWAP16, // dst = bswap16(dst)
77	SWAP32, // dst = bswap32(dst)
78	SWAP64, // dst = bswap64(dst)
79	NEG, // dst = -dst
80	};
81
82	Op op{};	22✔
83	Reg dst;	22✔
84	bool is64{};	22✔
85	constexpr bool operator==(const Un&) const = default;	22✔
86	};
87
88	/// This instruction is encoded similarly to LDDW.
89	/// See comment in makeLddw() at asm_unmarshal.cpp
90	struct LoadMapFd {
91	Reg dst;	2✔
92	int32_t mapfd{};	2✔
93	constexpr bool operator==(const LoadMapFd&) const = default;	2✔
94	};
95
96	struct Condition {
97	enum class Op {
98	EQ,
99	NE,
100	SET,
101	NSET, // NSET does not exist in ebpf
102	LT,
103	LE,
104	GT,
105	GE,
106	SLT,
107	SLE,
108	SGT,
109	SGE,
110	};
111
112	Op op;	44✔
113	Reg left;	44✔
114	Value right;	44✔
115	bool is64{};	44✔
116	constexpr bool operator==(const Condition&) const = default;	44✔
117	};
118
119	struct Jmp {	255,478✔
120	std::optional<Condition> cond;	44✔
121	label_t target;	44✔
122	bool operator==(const Jmp&) const = default;	44✔
123	};
124
125	struct ArgSingle {
126	// see comments in spec_prototypes.hpp
127	enum class Kind {
128	MAP_FD,
129	MAP_FD_PROGRAMS,
130	PTR_TO_MAP_KEY,
131	PTR_TO_MAP_VALUE,
132	PTR_TO_CTX,
133	ANYTHING,
134	} kind{};
135	Reg reg;
136	constexpr bool operator==(const ArgSingle&) const = default;
137	};
138
139	/// Pair of arguments to a function for pointer and size.
140	struct ArgPair {
141	enum class Kind {
142	PTR_TO_READABLE_MEM,
143	PTR_TO_READABLE_MEM_OR_NULL,
144	PTR_TO_WRITABLE_MEM,
145	} kind{};
146	Reg mem; ///< Pointer.
147	Reg size; ///< Size of space pointed to.
148	bool can_be_zero{};
149	constexpr bool operator==(const ArgPair&) const = default;
150	};
151
152	struct Call {	10,052✔
153	int32_t func{};
154	constexpr bool operator==(const Call& other) const { return func == other.func; }	4✔
155
156	// TODO: move name and signature information somewhere else
157	std::string name;
158	bool is_map_lookup{};
159	bool reallocate_packet{};
160	std::vector<ArgSingle> singles;
161	std::vector<ArgPair> pairs;
162	std::string stack_frame_prefix; ///< Variable prefix at point of call.
163	};
164
165	/// Call a "function" (macro) within the same program.
166	struct CallLocal {
167	label_t target;	×
168	std::string stack_frame_prefix; ///< Variable prefix to be used within the call.	×
169	bool operator==(const CallLocal& other) const noexcept = default;	×
170	};
171
172	struct Exit {	12,039✔
173	std::string stack_frame_prefix; ///< Variable prefix to clean up when exiting.	2✔
174	bool operator==(const Exit& other) const noexcept = default;	2✔
175	};
176
177	/// Experimental callx instruction.
178	struct Callx {
179	Reg func;	2✔
180	constexpr bool operator==(const Callx&) const = default;	2✔
181	};
182
183	struct Deref {
184	int32_t width{};	64✔
185	Reg basereg;	64✔
186	int32_t offset{};	64✔
187	constexpr bool operator==(const Deref&) const = default;	64✔
188	};
189
190	/// Load/store instruction.
191	struct Mem {
192	Deref access;	24✔
193	Value value;	24✔
194	bool is_load{};	24✔
195	constexpr bool operator==(const Mem&) const = default;	36✔
196	};
197
198	/// A deprecated instruction for checked access to packets; it is actually a
199	/// function call, and analyzed as one, e.g., by scratching caller-saved
200	/// registers after it is performed.
201	struct Packet {
202	int32_t width{};	12✔
203	int32_t offset{};	12✔
204	std::optional<Reg> regoffset;	12✔
205	constexpr bool operator==(const Packet&) const = default;	12✔
206	};
207
208	/// Special instruction for atomically updating values inside shared memory.
209	/// The analysis just treats an atomic operation as a series of consecutive
210	/// operations, and the atomicity itself is not significant.
211	struct Atomic {
212	enum class Op {
213	ADD = 0x00,
214	OR = 0x40,
215	AND = 0x50,
216	XOR = 0xa0,
217	XCHG = 0xe0, // Only valid with fetch=true.
218	CMPXCHG = 0xf0, // Only valid with fetch=true.
219	};
220
221	Op op{};	40✔
222	bool fetch{};	40✔
223	Deref access;	40✔
224	Reg valreg;	40✔
225	constexpr bool operator==(const Atomic&) const = default;	60✔
226	};
227
228	/// Not an instruction, just used for failure cases.
229	struct Undefined {
230	int opcode{};	×
231	constexpr bool operator==(const Undefined&) const = default;	×
232	};
233
234	/// When a CFG is translated to its nondeterministic form, Conditional Jump
235	/// instructions are replaced by two Assume instructions, immediately after
236	/// the branch and before each jump target.
237	struct Assume {
238	Condition cond;	×
239
240	// True if the condition is implicitly written in the program (False for tests).
241	bool is_implicit{true};	×
242
243	constexpr bool operator==(const Assume&) const = default;	×
244	};
245
246	struct IncrementLoopCounter {	160✔
247	label_t name;	×
248	bool operator==(const IncrementLoopCounter&) const = default;	×
249	};
250
251	using Instruction = std::variant<Undefined, Bin, Un, LoadMapFd, Call, CallLocal, Callx, Exit, Jmp, Mem, Packet, Atomic,
252	Assume, IncrementLoopCounter>;
253
254	using LabeledInstruction = std::tuple<label_t, Instruction, std::optional<btf_line_info_t>>;
255	using InstructionSeq = std::vector<LabeledInstruction>;
256
257	/// Condition check whether something is a valid size.
258	struct ValidSize {
259	Reg reg;
260	bool can_be_zero{};
261	constexpr bool operator==(const ValidSize&) const = default;
262	};
263
264	/// Condition check whether two registers can be compared with each other.
265	/// For example, one is not allowed to compare a number with a pointer,
266	/// or compare pointers to different memory regions.
267	struct Comparable {
268	Reg r1;
269	Reg r2;
270	bool or_r2_is_number{}; ///< true for subtraction, false for comparison
271	constexpr bool operator==(const Comparable&) const = default;
272	};
273
274	// ptr: ptr -> num : num
275	struct Addable {
276	Reg ptr;
277	Reg num;
278	constexpr bool operator==(const Addable&) const = default;
279	};
280
281	// Condition check whether a register contains a non-zero number.
282	struct ValidDivisor {
283	Reg reg;
284	bool is_signed{};
285	constexpr bool operator==(const ValidDivisor&) const = default;
286	};
287
288	enum class AccessType {
289	compare,
290	read, // Memory pointed to must be initialized.
291	write, // Memory pointed to must be writable.
292	};
293
294	struct ValidAccess {
295	int call_stack_depth{};
296	Reg reg;
297	int32_t offset{};
298	Value width{Imm{0}};
299	bool or_null{};
300	AccessType access_type{};
301	constexpr bool operator==(const ValidAccess&) const = default;
302	};
303
304	/// Condition check whether something is a valid key value.
305	struct ValidMapKeyValue {
306	Reg access_reg;
307	Reg map_fd_reg;
308	bool key{};
309	constexpr bool operator==(const ValidMapKeyValue&) const = default;
310	};
311
312	/// Condition check whether a call is valid in the current context.
313	struct ValidCall {	129,639✔
314	int32_t func{};
315	std::string stack_frame_prefix; ///< Variable prefix at point of call.
316	bool operator==(const ValidCall&) const = default;
317	};
318
319	// "if mem is not stack, val is num"
320	struct ValidStore {
321	Reg mem;
322	Reg val;
323	constexpr bool operator==(const ValidStore&) const = default;
324	};
325
326	using crab::TypeGroup;
327	struct TypeConstraint {
328	Reg reg;
329	TypeGroup types;
330	constexpr bool operator==(const TypeConstraint&) const = default;
331	};
332
333	struct FuncConstraint {
334	Reg reg;
335	constexpr bool operator==(const FuncConstraint&) const = default;
336	};
337
338	/// Condition check whether something is a valid size.
339	struct ZeroCtxOffset {
340	Reg reg;
341	constexpr bool operator==(const ZeroCtxOffset&) const = default;
342	};
343
344	struct BoundedLoopCount {	224✔
345	label_t name;
346	bool operator==(const BoundedLoopCount&) const = default;
347	// Maximum number of loop iterations allowed during verification.
348	// This prevents infinite loops while allowing reasonable bounded loops.
349	// When exceeded, verification fails as the loop might not terminate.
350	static constexpr int limit = 100000;
351	};
352
353	using Assertion = std::variant<Comparable, Addable, ValidDivisor, ValidAccess, ValidStore, ValidSize, ValidMapKeyValue,
354	ValidCall, TypeConstraint, FuncConstraint, ZeroCtxOffset, BoundedLoopCount>;
355
356	std::ostream& operator<<(std::ostream& os, Instruction const& ins);
357	std::string to_string(Instruction const& ins);
358
359	std::ostream& operator<<(std::ostream& os, Bin::Op op);
360	std::ostream& operator<<(std::ostream& os, Condition::Op op);
361
362	inline std::ostream& operator<<(std::ostream& os, const Imm imm) { return os << crab::to_signed(imm.v); }	30,244✔
363	inline std::ostream& operator<<(std::ostream& os, Reg const& a) { return os << "r" << gsl::narrow<int>(a.v); }	53,334✔
364	inline std::ostream& operator<<(std::ostream& os, Value const& a) {	37,472✔
365	if (const auto pa = std::get_if<Imm>(&a)) {	37,472✔
366	return os << *pa;	30,244✔
367	}
368	return os << std::get<Reg>(a);	7,228✔
369	}
370
371	std::ostream& operator<<(std::ostream& os, const Assertion& a);
372	std::string to_string(const Assertion& constraint);
373
374	void print(const InstructionSeq& insts, std::ostream& out, const std::optional<const label_t>& label_to_print,
375	bool print_line_info = false);
376
377	} // namespace asm_syntax
378
379	using namespace asm_syntax;
380	using crab::pc_t;
381
382	template <class... Ts>
383	struct overloaded : Ts... {
384	using Ts::operator()...;
385	};

vbpf / ebpf-verifier / 12845504567

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