[linux-2.6-block.git] / tools / testing / selftests / bpf / verifier / loops1.c

{
	"bounded loop, count to 4",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	.retval = 4,
},
{
	"bounded loop, count to 20",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 3),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 20, -2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"bounded loop, count from positive unknown to 4",
	.insns = {
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
	BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, 2),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	.retval = 4,
},
{
	"bounded loop, count from totally unknown to 4",
	.insns = {
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"bounded loop, count to 4 with equality",
	.insns = {
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
		BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 4, -2),
		BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"bounded loop, start in the middle",
	.insns = {
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_JMP_A(1),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
		BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
		BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "back-edge",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	.retval = 4,
},
{
	"bounded loop containing a forward jump",
	.insns = {
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
		BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_0, 0),
		BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -3),
		BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	.retval = 4,
},
{
	"bounded loop that jumps out rather than in",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_6, 0),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 1),
	BPF_JMP_IMM(BPF_JGT, BPF_REG_6, 10000, 2),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
	BPF_JMP_A(-4),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"infinite loop after a conditional jump",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 5),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, 2),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_JMP_A(-2),
	BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "program is too large",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"bounded recursion",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_1, 0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
	BPF_EXIT_INSN(),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1),
	BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 4, 1),
	BPF_EXIT_INSN(),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -5),
	BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "back-edge",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"infinite loop in two jumps",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_JMP_A(0),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "loop detected",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"infinite loop: three-jump trick",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1),
	BPF_EXIT_INSN(),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1),
	BPF_EXIT_INSN(),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, -11),
	BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "loop detected",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"not-taken loop with back jump to 1st insn",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_0, 123),
	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 4, -2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_XDP,
	.retval = 123,
},
{
	"taken loop with back jump to 1st insn",
	.insns = {
	BPF_MOV64_IMM(BPF_REG_1, 10),
	BPF_MOV64_IMM(BPF_REG_2, 0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
	BPF_EXIT_INSN(),
	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_1),
	BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 1),
	BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, -3),
	BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
	BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.prog_type = BPF_PROG_TYPE_XDP,
	.retval = 55,
},
Commit	Line	Data
0d3679e9 AS	1	{
	2	"bounded loop, count to 4",
	3	.insns = {
	4	BPF_MOV64_IMM(BPF_REG_0, 0),
	5	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	6	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	7	BPF_EXIT_INSN(),
	8	},
	9	.result = ACCEPT,
	10	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	11	.retval = 4,
	12	},
	13	{
	14	"bounded loop, count to 20",
	15	.insns = {
	16	BPF_MOV64_IMM(BPF_REG_0, 0),
	17	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 3),
	18	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 20, -2),
	19	BPF_EXIT_INSN(),
	20	},
	21	.result = ACCEPT,
	22	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	23	},
	24	{
	25	"bounded loop, count from positive unknown to 4",
	26	.insns = {
	27	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
	28	BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, 2),
	29	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	30	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	31	BPF_EXIT_INSN(),
	32	},
	33	.result = ACCEPT,
	34	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	35	.retval = 4,
	36	},
	37	{
	38	"bounded loop, count from totally unknown to 4",
	39	.insns = {
	40	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
	41	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	42	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
	43	BPF_EXIT_INSN(),
	44	},
	45	.result = ACCEPT,
	46	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	47	},
	48	{
	49	"bounded loop, count to 4 with equality",
	50	.insns = {
	51	BPF_MOV64_IMM(BPF_REG_0, 0),
	52	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
	53	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 4, -2),
	54	BPF_EXIT_INSN(),
	55	},
	56	.result = ACCEPT,
	57	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
	58	},
	59	{
	60	"bounded loop, start in the middle",
	61	.insns = {
	62	BPF_MOV64_IMM(BPF_REG_0, 0),
	63	BPF_JMP_A(1),
	64	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
65	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
66	BPF_EXIT_INSN(),
67	},
68	.result = REJECT,
69	.errstr = "back-edge",
70	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
71	.retval = 4,
72	},
73	{
74	"bounded loop containing a forward jump",
75	.insns = {
76	BPF_MOV64_IMM(BPF_REG_0, 0),
77	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
78	BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_0, 0),
79	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -3),
80	BPF_EXIT_INSN(),
81	},
82	.result = ACCEPT,
83	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
84	.retval = 4,
85	},
86	{
87	"bounded loop that jumps out rather than in",
88	.insns = {
89	BPF_MOV64_IMM(BPF_REG_6, 0),
90	BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 1),
91	BPF_JMP_IMM(BPF_JGT, BPF_REG_6, 10000, 2),
92	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
93	BPF_JMP_A(-4),
94	BPF_EXIT_INSN(),
95	},
96	.result = ACCEPT,
97	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
98	},
99	{
100	"infinite loop after a conditional jump",
101	.insns = {
102	BPF_MOV64_IMM(BPF_REG_0, 5),
103	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, 2),
104	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
105	BPF_JMP_A(-2),
106	BPF_EXIT_INSN(),
107	},
108	.result = REJECT,
109	.errstr = "program is too large",
110	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
111	},
112	{
113	"bounded recursion",
114	.insns = {
115	BPF_MOV64_IMM(BPF_REG_1, 0),
116	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 1, 0, 1),
117	BPF_EXIT_INSN(),
118	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1),
119	BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
120	BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 4, 1),
121	BPF_EXIT_INSN(),
122	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 1, 0, -5),
123	BPF_EXIT_INSN(),
124	},
125	.result = REJECT,
126	.errstr = "back-edge",
127	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
128	},
129	{
130	"infinite loop in two jumps",
131	.insns = {
132	BPF_MOV64_IMM(BPF_REG_0, 0),
133	BPF_JMP_A(0),
134	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2),
135	BPF_EXIT_INSN(),
136	},
137	.result = REJECT,
138	.errstr = "loop detected",
139	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
140	},
141	{
142	"infinite loop: three-jump trick",
143	.insns = {
144	BPF_MOV64_IMM(BPF_REG_0, 0),
145	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
146	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
147	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1),
148	BPF_EXIT_INSN(),
149	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
150	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
151	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1),
152	BPF_EXIT_INSN(),
153	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
154	BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1),
155	BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, -11),
156	BPF_EXIT_INSN(),
157	},
158	.result = REJECT,
159	.errstr = "loop detected",
160	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
161	},
f1fc7249 AS	162	{
	163	"not-taken loop with back jump to 1st insn",
	164	.insns = {
	165	BPF_MOV64_IMM(BPF_REG_0, 123),
	166	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 4, -2),
	167	BPF_EXIT_INSN(),
	168	},
	169	.result = ACCEPT,
	170	.prog_type = BPF_PROG_TYPE_XDP,
	171	.retval = 123,
	172	},
	173	{
	174	"taken loop with back jump to 1st insn",
	175	.insns = {
	176	BPF_MOV64_IMM(BPF_REG_1, 10),
	177	BPF_MOV64_IMM(BPF_REG_2, 0),
	178	BPF_RAW_INSN(BPF_JMP \| BPF_CALL, 0, 1, 0, 1),
	179	BPF_EXIT_INSN(),
	180	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_1),
	181	BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 1),
	182	BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, -3),
	183	BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
	184	BPF_EXIT_INSN(),
	185	},
	186	.result = ACCEPT,
	187	.prog_type = BPF_PROG_TYPE_XDP,
	188	.retval = 55,
	189	},