Subject: Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning
To: Daniel Borkmann <daniel@iogearbox.net>,
        Edward Cree <ecree@solarflare.com>, <davem@davemloft.net>,
        Alexei Starovoitov <alexei.starovoitov@gmail.com>
References: <f40d3d54-c88a-7348-99ca-66db8075a8d5@solarflare.com>
 <89ff34f7-84ee-0e0a-3766-5b4d046189bf@fb.com>
 <b8a46388-74ea-81f9-df08-3b6b88042229@solarflare.com>
 <5d4e12aa-6861-a176-a8cf-a766bbca0a7a@fb.com>
 <b39b4a6f-907e-c684-b9e4-285ff9c7ca9a@solarflare.com>
 <599B4231.3080405@iogearbox.net>
 <128a84cd-234d-f505-95e2-7561db974981@solarflare.com>
 <599B49DB.6010008@iogearbox.net>
CC: <netdev@vger.kernel.org>, <linux-kernel@vger.kernel.org>,
        iovisor-dev <iovisor-dev@lists.iovisor.org>
From: Alexei Starovoitov <ast@fb.com>
Message-ID: <2c636ee7-ba60-b506-9d37-1fe405c31076@fb.com>
Date: Mon, 21 Aug 2017 14:23:29 -0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0)
 Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <599B49DB.6010008@iogearbox.net>
Content-Type: text/plain; charset="utf-8"; format=flowed
Content-Transfer-Encoding: 7bit
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Aug 2017 21:23:32.4728 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL2PR15MB0962
X-OriginatorOrg: fb.com
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-08-21_14:,,
 signatures=0
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 2856
Lines: 62

On 8/21/17 2:00 PM, Daniel Borkmann wrote:
> On 08/21/2017 10:44 PM, Edward Cree wrote:
>> On 21/08/17 21:27, Daniel Borkmann wrote:
>>> On 08/21/2017 08:36 PM, Edward Cree wrote:
>>>> On 19/08/17 00:37, Alexei Starovoitov wrote:
>>> [...]
>>>> I'm tempted to just rip out env->varlen_map_value_access and always
>>>> check
>>>>    the whole thing, because honestly I don't know what it was meant
>>>> to do
>>>>    originally or how it can ever do any useful pruning.  While
>>>> drastic, it
>>>>    does cause your test case to pass.
>>>
>>> Original intention from 484611357c19 ("bpf: allow access into map
>>> value arrays") was that it wouldn't potentially make pruning worse
>>> if PTR_TO_MAP_VALUE_ADJ was not used, meaning that we wouldn't need
>>> to take reg state's min_value and max_value into account for state
>>> checking; this was basically due to min_value / max_value is being
>>> adjusted/tracked on every alu/jmp ops for involved regs (e.g.
>>> adjust_reg_min_max_vals() and others that mangle them) even if we
>>> have the case that no actual dynamic map access is used throughout
>>> the program. To give an example on net tree, the bpf_lxc.o prog's
>>> section increases from 36,386 to 68,226 when
>>> env->varlen_map_value_access
>>> is always true, so it does have an effect. Did you do some checks
>>> on this on net-next?
>> I tested with the cilium progs and saw no change in insn count.  I
>>   suspect that for the normal case I already killed this optimisation
>>   when I did my unification patch, it was previously about ignoring
>>   min/max values on all regs (including scalars), whereas on net-next
>>   it only ignores them on map_value pointers; in practice this is
>>   useless because we tend to still have the offset scalar sitting in
>>   a register somewhere.  (Come to think of it, this may have been
>>   behind a large chunk of the #insn increase that my patches caused.)
>
> Yeah, this would seem plausible.
>
>> Since we use umax_value in find_good_pkt_pointers() now (to check
>>   against MAX_PACKET_OFF and ensure our reg->range is really ok), we
>>   can't just stop caring about all min/max values just because we
>>   haven't done any variable map accesses.
>> I don't see a way around this.
>
> Agree, was thinking the same. If there's not really a regression in
> terms of complexity, then lets kill the flag.

+1

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2489e67b65f6..908d13b2a2aa 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3582,7 +3582,7 @@ static int do_check(struct bpf_verifier_env *env)
         init_reg_state(regs);
         state->parent = NULL;
         insn_idx = 0;
-       env->varlen_map_value_access = false;
+       env->varlen_map_value_access = true;

makes _zero_ difference on cilium*.o tests, so let's just kill
that workaround.