From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-lj1-f175.google.com (mail-lj1-f175.google.com [209.85.208.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2DDBF2C80 for ; Wed, 10 Nov 2021 11:41:22 +0000 (UTC) Received: by mail-lj1-f175.google.com with SMTP id e9so4688616ljl.5 for ; Wed, 10 Nov 2021 03:41:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=csmTgtaZMnyvU7jhPmCPCXw06UF8KdqBzZmK1KMCI6o=; b=QhmY5KuYe0XdpWl7mKeMIy/WVvxYHv/BXvIrQukvJNN+zYtG7FaI9dc6ohVUtjEqyX XoSQB1OuxL8X/onouOs9GEENzOYrok3YqfvL/NZ/uf8imt/TO+A7OQoDt7tEIljikIgc 6pXdy1pwSlazlj3uAQ4yk7ZrbqknDC6UK9Hsw= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=csmTgtaZMnyvU7jhPmCPCXw06UF8KdqBzZmK1KMCI6o=; b=ZP8A7dD1+4En5+UQfsfgtTyWbC7X72eMwEsb3CvcKfHWtEcaGGy+U1eE2HRZo0NTIW 926HsFysBXtGfR6E5cnXOLccYZe+vV+l1Vudd0z6ntJ/ixl8eznTauy17UCok/lR51VE +V+XIJ4FzsZVY1Y9dLwIHoUGw3uWMQG3zk/Bc65DP+7ZFF8cVFFvFF780NFKY2/JGq3/ 7V/61wVOivE/mkmoEIu7D74udBaJITkrkBa5WV+51bGmsPx4y41ty6Gwx6TOMgOvJuPH EZEJYv8/r2yqCv1PXkgX4iYIZan2E7UjzONjwERMGr6vYY6rVVrg4HZPmraoaHOXrUfd zRuw== X-Gm-Message-State: AOAM533ulIq6NSf5joJkIpxtmQkjtdq9LJTC16OFvXDE/9PrzMOP2TVL 7Ob+osfg8+CCilklXYapi0hQJQ+hp5/sNnOuuczNSw== X-Google-Smtp-Source: ABdhPJwg3ODydwUYEKknDDnRtSuPDjfEhEAzaBDjNvT4+ZA3qibPjvBsZvquxzyGi6U0EeSCcvuLWnZdwf8Dxs4QE68= X-Received: by 2002:a2e:9c02:: with SMTP id s2mr15129322lji.121.1636544480017; Wed, 10 Nov 2021 03:41:20 -0800 (PST) Precedence: bulk X-Mailing-List: regressions@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 References: <20211105194952.xve6u6lgh2oy46dy@ast-mbp.dhcp.thefacebook.com> <20211110042530.6ye65mpspre7au5f@ast-mbp.dhcp.thefacebook.com> In-Reply-To: <20211110042530.6ye65mpspre7au5f@ast-mbp.dhcp.thefacebook.com> From: Lorenz Bauer Date: Wed, 10 Nov 2021 11:41:09 +0000 Message-ID: Subject: Re: Verifier rejects previously accepted program To: Alexei Starovoitov Cc: Alexei Starovoitov , kernel-team , bpf , regressions@lists.linux.dev, Andrii Nakryiko , Daniel Borkmann Content-Type: text/plain; charset="UTF-8" On Wed, 10 Nov 2021 at 04:25, Alexei Starovoitov wrote: > > but it goes into R2 from non-inner map which ruins all my theories. The trace does contain modifications from inner maps, but they aren't at the start of the block at 1077. Your suggested hack makes this clear: 1033: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=invP0 R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1033: (16) if w1 == 0x0 goto pc+43 1077: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=invP0 R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1077: (79) r2 = *(u64 *)(r10 -128) 1078: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=invP0 R2_w=map_value(id=0,off=0,ks=4,vs=32,uid=0,imm=0) R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value r2 is the per-CPU array. r0, r3 are from an inner map. There are accesses to r3 a couple instructions later: 1081: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=inv(id=0) R2_w=map_value(id=0,off=0,ks=4,vs=32,uid=0,imm=0) R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1081: (71) r1 = *(u8 *)(r3 +32) R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=inv(id=0) R2_w=map_value(id=0,off=0,ks=4,vs=32,uid=0,imm=0) R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value > The verbose() part will help to confirm that R2 in the above should be uid=0. Yes, uid=0, see above. > After that please try only with: > - if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id))) > + if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, map_uid))) > > It should resolve the regression, but will break timer safety check and makes > the map_uid logic not quite right (though no existing test will show it). This doesn't help. > > If offsetof(map_uid) doesn't help another guess would be: > @@ -10496,7 +10497,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > * it's valid for all map elements regardless of the key > * used in bpf_map_lookup() > */ > - return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && > + return memcmp(rold, rcur, offsetof(struct bpf_reg_state, map_uid)) == 0 && > range_within(rold, rcur) && > tnum_in(rold->var_off, rcur->var_off); > that's for PTR_TO_MAP_VALUE and that would be a different theory which makes even less sense. This change resolves the regression. The first five occurrences of insn 1077 in the trace, with your logging applied: 1077: R0=map_value(id=0,off=0,ks=4,vs=36,uid=13,imm=0) R1=invP0 R3=map_value(id=0,off=0,ks=4,vs=36,uid=13,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=00000000 fp-32=0000mmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1077: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6875,imm=0) R1_w=invP0 R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6875,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=00000000 fp-32=0000mmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1077: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R1_w=invP0 R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6900,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1077: R0=map_value(id=0,off=0,ks=4,vs=36,uid=6908,imm=0) R1_w=invP0 R3_w=map_value(id=0,off=0,ks=4,vs=36,uid=6908,imm=0) R6=ctx(id=0,off=0,imm=0) R7=inv(id=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value 1077: R0=map_value(id=0,off=0,ks=16,vs=36,uid=0,imm=0) R1=invP0 R2=map_value(id=0,off=0,ks=4,vs=368,uid=0,imm=0) R3=map_value(id=0,off=0,ks=16,vs=36,uid=0,imm=0) R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=368,uid=0,imm=0) R8=pkt(id=0,off=18,r=38,imm=0) R9=inv0 R10=fp0 fp-24=mmmmmmmm fp-32=mmmmmmmm fp-40=mmmm00m0 fp-48=mmmm0000 fp-56=00000000 fp-64=00000000 fp-72=0000mmmm fp-80=mmmmmmmm fp-88=map_value fp-96=pkt_end fp-104=map_value fp-112=pkt fp-120=fp fp-128=map_value uid changes on every invocation, and therefore regsafe() returns false? -- Lorenz Bauer | Systems Engineer 6th Floor, County Hall/The Riverside Building, SE1 7PB, UK www.cloudflare.com