From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.1 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS,USER_AGENT_NEOMUTT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 323A4C43387 for ; Fri, 18 Jan 2019 05:51:35 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id E987220855 for ; Fri, 18 Jan 2019 05:51:34 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="sbkAXBAz" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727005AbfARFvd (ORCPT ); Fri, 18 Jan 2019 00:51:33 -0500 Received: from mail-pg1-f195.google.com ([209.85.215.195]:40906 "EHLO mail-pg1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726461AbfARFvd (ORCPT ); Fri, 18 Jan 2019 00:51:33 -0500 Received: by mail-pg1-f195.google.com with SMTP id z10so5523675pgp.7 for ; Thu, 17 Jan 2019 21:51:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=1zjWnbcLRwRJALSXuBQXXCxcMspzQo9BJUHXCVzunwg=; b=sbkAXBAz7YBJS4Tq6NYbZao4w9c4A32ZAtQ3hD0iA4/SjL9o+xamujcPVjC1StYMNC 0jxT0JRKgHLgvxs2xpkuVJvGbQxUz/VWMJ4yuphPDtaS4RZeGN0Uy9iv8770TJAVzb4+ t0L18pLZXTxGiYY3AaKG0qXwreQGOxKcSdjuIU6Sp8nknkPqnRLhA1ugbadr1ZN8MXtN 1kKtxLIvJpk3H+MXUefaAg6z407F84lmuZwPzHbxqCAH+yBdpFoOIiwu/uUPrZx3yJT0 +S7tp/n/f0WJsxvMU3g13EoZf3/6t6QIjnjQCt2J+vHK80zV5s1ALNNkkNhY9scPSTiF aP1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=1zjWnbcLRwRJALSXuBQXXCxcMspzQo9BJUHXCVzunwg=; b=JRlip8iNTyY4y7eGLp88VB4mYrauA9cohi2SzJpVvsgRaRgZ34NqPKYh3xoeoiRCCy t4W4vsFN0IJpgQydsHWqy57tqsE6nxE67yZxfi1nnppotV/r1vjvxqcqgZZ1LFDZo7XQ vTjV6GlvurviqDAgGXrMdr2xwjiuhx1cuBudLNwnozehRv52nsSgbncFw3US03llj2Fw n8EkJiLXD1NsO1Kr7G6ApDVvCU/35MkuNXabuyeYSGBUC3Ib1Dfsji6Si6HxDnPcFl1M 4leZ7K/RqFKxiYv5fIZEcOXyZvwiwBX0XeNRT4pJ3i5D5uzZqeygtPHZ6ovHueF4d2Hy lI/A== X-Gm-Message-State: AJcUukc7sKqOljn+XPWu6WDOX12cZ1TVSFUZTdebeDQj9UXfgV8PpNJy Y/TKLlZwZxKiIj8pyHvde7Y= X-Google-Smtp-Source: ALg8bN5MHb8IytmkYe6jRi8dcdUbRtU0tJaZ3yrtgwO83TDaT2qryg8ln9Gztjop2ynL1/MEDtH3hg== X-Received: by 2002:a62:5c41:: with SMTP id q62mr18311380pfb.171.1547790692393; Thu, 17 Jan 2019 21:51:32 -0800 (PST) Received: from ast-mbp ([2620:10d:c090:200::6:35b7]) by smtp.gmail.com with ESMTPSA id m9sm6060901pgd.32.2019.01.17.21.51.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 17 Jan 2019 21:51:31 -0800 (PST) Date: Thu, 17 Jan 2019 21:51:29 -0800 From: Alexei Starovoitov To: Daniel Borkmann Cc: Alexei Starovoitov , davem@davemloft.net, jakub.kicinski@netronome.com, netdev@vger.kernel.org, kernel-team@fb.com Subject: Re: [PATCH bpf-next 1/9] bpf: introduce bpf_spin_lock Message-ID: <20190118055127.6esmbegpobostha2@ast-mbp> References: <20190116050830.1881316-1-ast@kernel.org> <20190116050830.1881316-2-ast@kernel.org> <20190116233029.xdaddrfehfjk4hrx@ast-mbp> <3367abf6-c6a3-2c2e-9fde-7de923f898d2@iogearbox.net> <20190117011629.efxp7abj4bpf5yco@ast-mbp> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20180223 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On Thu, Jan 17, 2019 at 12:27:55PM +0100, Daniel Borkmann wrote: > > Was thinking something like this, in very rough pseudo code: > > Prog A (normal spin lock use of mapA): > > val = bpf_map_lookup_elem(&mapA, &key); > if (val) { > bpf_spin_lock(&val->lock); > [...] > bpf_spin_unlock(&val->lock); > } > > Prog B: > > if (non_const_condition_A) { > map_ptr = &mapB; // mapB is normal array map with same > // properties as mapA, but no BTF and > // thus no spinlock use. > } else { > map_ptr = &mapA; > } > val = bpf_map_lookup_elem(&map_ptr, &key); > map_ptr = 0; // clear map reg to match for > // both verification paths > if (val) { > // turning val into PTR_TO_MAP_VALUE > if (non_const_condition_B) { > // write into memory area of spin_lock; > // first path with mapB is considered > // safe (since map with no spin_lock so > // write into this area allowed); > // now when verifier is checking the > // non_const_condition_A's else path > // with mapA, then non_const_condition_B > // has pruning checkpoint and is going > // to compare reg with PTR_TO_MAP_VALUE; > // since id is not considered I /think/ > // verifier would find it (wrongly) safe > // as well. > } > } > > Wdyt? I've implemented it and it was rejected. regsafe() is doing: memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)); 'map_ptr' is before 'id' in bpf_reg_state. lookups from different maps will have different register states as expected. I still felt that we need to compare id, so I tried if (random) val = bpf_map_lookup_elem(&hash_map, &key1); else val = bpf_map_lookup_elem(&hash_map, &key2); to force pruning of two states that point to the same map. The val->spin_lock addresses will be different and intuitively it may feel that we need to compare id, but it's unnecessary. If the rest of the program is valid with val for key1 it's a good thing to prune verification for key2 to avoid spending more cycles in the verifier. All map elements have spin_locks. If bpf code is valid for one element it's valid for all elements. Then I tried to trick the verifier with the following: int flag = 0; if (random) { val = bpf_map_lookup_elem(&hash_map, &key1); } else { flag = 1; val = bpf_map_lookup_elem(&hash_map, &key2); } if (!val) goto err; bpf_spin_lock(&val->lock); bpf_spin_unlock(&val->lock); if (flag == 1) // access spin_lock with ld/st the first pass of the verifier will correctly avoid exploring 'flag == 1' condition (because the verifier is smart enough to know that the flag is 0 there), but the second pass with different reg->id for 'val' will not be pruned, since the register (or stack) where 'flag' is stored is different and the verifier will proceed and will catch ld/st into spin_lock field and the prog will be rejected. So I believe the verifier should not compare 'id' in regsafe() for PTR_TO_MAP_VALUE to have better pruning. I'll add a comment there explaining this.