Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <d027cb6b-e32c-36ad-3aba-9a7b1177f89f@meta.com>
Date:   Mon, 22 May 2023 21:33:41 -0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0)
 Gecko/20100101 Thunderbird/102.11.0
Subject: Re: [bug] kernel: bpf: syscall: a possible sleep-in-atomic bug in
 __bpf_prog_put()
Content-Language: en-US
To:     Teng Qi <starmiku1207184332@gmail.com>
Cc:     ast@kernel.org, daniel@iogearbox.net, john.fastabend@gmail.com,
        andrii@kernel.org, martin.lau@linux.dev, song@kernel.org,
        yhs@fb.com, kpsingh@kernel.org, sdf@google.com, haoluo@google.com,
        jolsa@kernel.org, davem@davemloft.net, kuba@kernel.org,
        hawk@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org,
        netdev@vger.kernel.org
References: <20230516111823.2103536-1-starmiku1207184332@gmail.com>
 <e37c0a65-a3f6-e2e6-c2ad-367db20253a0@meta.com>
 <CALyQVax8X63qekZVhvRTmZFFs+ucPKRkBB7UnRZk6Hu3ggi7Og@mail.gmail.com>
 <57dc6a0e-6ba9-e77c-80ac-6bb0a6e2650a@meta.com>
 <CALyQVazb=D1ejapiFdTnan6JbjFJA2q9ifhSsmF4OC9MDz3oAw@mail.gmail.com>
From:   Yonghong Song <yhs@meta.com>
In-Reply-To: <CALyQVazb=D1ejapiFdTnan6JbjFJA2q9ifhSsmF4OC9MDz3oAw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?ODBSU3dPZ094RmFhUnE5VDgybTRrWXdtREFYWnFXcXA5a1pJK1FMeUdtMmJ1?=
 =?utf-8?B?NGJBUzVESy9FQXh5NFhrSTBDMFArcjM2L2JrQjcvZ1RMSXhhaTN2OFZWRkxQ?=
 =?utf-8?B?RGZ0SE95bVNUMUpLZ2lPUU9ZQ2dSTTFBcHZpV3E2Vk42emUvK2QrTUEraHZS?=
 =?utf-8?B?TGpIaTBld0xkRnpleXErM09rMHZQOWNyc0lMcGFOaW9YaUJUZ05qT0VVMk1p?=
 =?utf-8?B?RjZGdnNPRlpKaDZJOVg4NHNQNGNYQjVFSHROelIxSUI4TlVoUENtR2hITHZE?=
 =?utf-8?B?aHF3VURNR0hkWVJSOGZQZ28yNHVHMFp6akpnYzgxOUN5dlFaSjl6dWV0Mlls?=
 =?utf-8?B?ZkNyOVczT0J2MWxpRkxsS3ZIbVh6U0ZKNkR1VnM4UkVlY1pkUW1OVXh1a2xW?=
 =?utf-8?B?ZG5VQ2tRM0haQ0F5SmJ3SC8zMzNiaHlGdUIxU1NkaDdzanIxMC8rS3FmU0JO?=
 =?utf-8?B?Uk5FK0hVeFZ2WXZEL1FDTlYrNFlyVUk2c0Q4RkpKdmVFZXg3NHZJTWJ2ZDJk?=
 =?utf-8?B?Ukc5S2lMeEQwU2xWWktKbHNVZjNHNTJRL25IWDlteVh0YXJyL1NueHdHUmY2?=
 =?utf-8?B?YkZYZ3pYN1M4SHZnc3VxMm16OEc4SjU0SkJDc05zKzd6WndoUlE5bzF2Q25X?=
 =?utf-8?B?dFZ5TFU4NXUvdU5YTjRPaFBqRkp1YmQrU0VlQ2VmYnJOdS85OVlYSytDWUli?=
 =?utf-8?B?MHZVeE90ZGpmWlhVY3gyUUhXU3dxSFc1RnQzNmErN2tRdHZuaThIbWkvQnM0?=
 =?utf-8?B?KzhpM1Mwb2U0cStuNGY1Rk91M2JEZyt6OG1CVXZqaWVpNnV0NEk1YWtZcWFj?=
 =?utf-8?B?L1l2SnhPaUZ1N21McmwwSmFTaDZWV3pXeWtOdzdFRkJmdjZvcUZ1alJBMXJt?=
 =?utf-8?B?RkhpUzVmbTRkbTYrczd4Z0dBcmJpeFQ2alZOY3pWd0kva1o0aU9mNGpsaWhI?=
 =?utf-8?B?SVFuTjJKOFN1cmdFZjA3UTZmU1FZMEJjQTBOc0psQTFQRnQydDhkcDFHM2to?=
 =?utf-8?B?OTJQMTdNY3NPL0x0OHEyNzFOMEZZK0Zkb2R3b3RLUFE2MTNwVTNZMEVLSGNz?=
 =?utf-8?B?aWkwWkRMMzR1enhYSWxxY1pmbm1QbkNLaXl1ejBKN1E2R2ZNRWN4Mjdick9k?=
 =?utf-8?B?WVd4a3ByOGVYdGFMRGswMzRtNzhycDFncWdwVWt4a0xHNXF3NnRRMWlGajhj?=
 =?utf-8?B?WGU1TThjM0l3NUFaTEtzbE02QThlQWhoZC9xS3NoTVU2Vld4U3FrQ3hSZENn?=
 =?utf-8?B?NWRPaFlHSmhUQTJZQ05ReDBuYVgwOVMrZkFhTmg1Y1I1c1dKdU9aVytnTFNi?=
 =?utf-8?B?YXo4TU1TZGcyOHd2ZStzSzRMb0I0SVNpNVhhaEFpeEVSYUVYbmg0WGxuUy9E?=
 =?utf-8?B?YUk3R2VCL2VEOUtFOHlDOXJFNldxK3pnbFR5TG5MOUJDUTBZRDNtQS9nZElU?=
 =?utf-8?B?T2tHZGlXOFBrbnFROERhWTRSbVVmSXdBSVZsUDc1RjhYM1IwNzFvaFNKQXI2?=
 =?utf-8?B?SlNBc2hZUStGVlExazk2QkpTZHZIWUFmZkRVOHoraGNZdVBOaXExVFdRYVg2?=
 =?utf-8?B?d1VHUlV2N3FXVlBia1ZNb1FCR2pTUnFkeURTRTAydUJ5Y2E4NXdCaFpGcngz?=
 =?utf-8?B?OW96YjFTbnJwbWl0L2hnbW11bTdPV0taOGlHbWNVYUpON2UwcXg4N1hvc2pp?=
 =?utf-8?B?V1VES0h0YTFXMmMwOHpEV2t0UGI1MDRmWXZqWUNON1ZzdjFZd1BFTXg3T21a?=
 =?utf-8?B?Y0luYzZGcmxPR0hiVnl5eFN6dU5TajJuZTIrUkt3L1F6LzBGZC9zTzNUdHNH?=
 =?utf-8?B?U2hWeXdwTmNsUTg5cmdrWlhIdVZtQUI5bmt1Q0xNdUZiZ1lRK2psMk9uMXZJ?=
 =?utf-8?B?aFJnanJPaS9ubTF1ZTNEZzhZMzZHSy9iSFRKTDlieGhGTGI5QkxYZyttRUFV?=
 =?utf-8?B?MUVLcm9iT09kazFvN0hLRGkvNC8ybjdNTitwYzF1VVd3eHNHbnIrNHZpR0Iy?=
 =?utf-8?B?TGZMMHB0Yk9Qbk1yaWhjZTFhUURCYldacjJIQXkyWmhTVzdXMEdZcWFzaTZT?=
 =?utf-8?B?ZDBDMWU2VVJBTmFtUUVGOVdDOE1KSmdlRkxJVkNOS1ZtS1VpOW1FQ3VCbElR?=
 =?utf-8?B?Zzd1YkZyaUtsL3dzL3JwQ0dmZGl4elhYdEhzQ1l0bFVqT0svMFcvajB6eDAr?=
 =?utf-8?B?TVE9PQ==?=
X-OriginatorOrg: meta.com
X-MS-Exchange-CrossTenant-Network-Message-Id: f53bb2cb-32a3-4af1-ce66-08db5b46e5c3
X-MS-Exchange-CrossTenant-AuthSource: SN6PR1501MB2064.namprd15.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 May 2023 04:33:46.5913
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: RHYiJqEVwhkCPlTRBzMZp8TSrBifQt1dAhiAhlsBueR44sqIznSVsSNuAbrIF2Gs
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW3PR15MB3787
X-Proofpoint-GUID: Uueothdam9oXZJmqrAQiriyd917ObfPE
X-Proofpoint-ORIG-GUID: Uueothdam9oXZJmqrAQiriyd917ObfPE
Content-Transfer-Encoding: 8bit
X-Proofpoint-UnRewURL: 0 URL was un-rewritten
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26
 definitions=2023-05-23_02,2023-05-22_03,2023-05-22_02
X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS,
        T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED autolearn=ham autolearn_force=no
        version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org


On 5/21/23 6:39 AM, Teng Qi wrote:
> Thank you.
> 
>  > Your above analysis makes sense if indeed that kvfree cannot appear
>  > inside a spin lock region or RCU read lock region. But is it true?
>  > I checked a few code paths in kvfree/kfree. It is either guarded
>  > with local_irq_save/restore or by
>  > spin_lock_irqsave/spin_unlock_
>  > irqrestore, etc. Did I miss
>  > anything? Are you talking about RT kernel here?
> 
> To see the sleepable possibility of kvfree, it is important to analyze the
> following calling stack:
> mm/util.c: 645 kvfree()
> mm/vmalloc.c: 2763 vfree()
> 
> In kvfree(), to call vfree, if the pointer addr points to memory 
> allocated by
> vmalloc(), it calls vfree().
> void kvfree(const void *addr)
> {
>          if (is_vmalloc_addr(addr))
>                  vfree(addr);
>          else
>                  kfree(addr);
> }
> 
> In vfree(), in_interrupt() and might_sleep() need to be considered.
> void vfree(const void *addr)
> {
>          // ...
>          if (unlikely(in_interrupt()))
>          {
>                  vfree_atomic(addr);
>                  return;
>          }
>          // ...
>          might_sleep();
>          // ...
> }

Sorry. I didn't check vfree path. So it does look like that
we need to pay special attention to non interrupt part.

> 
> The vfree() may sleep if in_interrupt() == false. The RCU read lock region
> could have in_interrupt() == false and spin lock region which only disables
> preemption also has in_interrupt() == false. So the kvfree() cannot appear
> inside a spin lock region or RCU read lock region if the pointer addr points
> to memory allocated by vmalloc().
> 
>  > > Therefore, we propose modifying the condition to include
>  > > in_atomic(). Could we
>  > > update the condition as follows: "in_irq() || irqs_disabled() ||
>  > > in_atomic()"?
>  > Thank you! We look forward to your feedback.
> 
> We now think that ‘irqs_disabled() || in_atomic() || 
> rcu_read_lock_held()’ is
> more proper. irqs_disabled() is for irq flag reg, in_atomic() is for
> preempt count and rcu_read_lock_held() is for RCU read lock region.

We cannot use rcu_read_lock_held() in the 'if' statement. The return
value rcu_read_lock_held() could be 1 for some configuraitons regardless
whether rcu_read_lock() is really held or not. In most cases,
rcu_read_lock_held() is used in issuing potential warnings.
Maybe there are other ways to record whether rcu_read_lock() is held or not?

I agree with your that 'irqs_disabled() || in_atomic()' makes sense
since it covers process context local_irq_save() and spin_lock() cases.

If we cannot resolve rcu_read_lock() presence issue, maybe the condition
can be !in_interrupt(), so any process-context will go to a workqueue.

Alternatively, we could have another solution. We could add another
function e.g., bpf_prog_put_rcu(), which indicates that bpf_prog_put()
will be done in rcu context. So if in_interrupt(), do kvfree, otherwise,
put into a workqueue.


> 
> -- Teng Qi
> 
> On Sun, May 21, 2023 at 11:45 AM Yonghong Song <yhs@meta.com 
> <mailto:yhs@meta.com>> wrote:
> 
> 
> 
>     On 5/19/23 7:18 AM, Teng Qi wrote:
>      > Thank you for your response.
>      >  > Looks like you only have suspicion here. Could you find a real
>     violation
>      >  > here where __bpf_prog_put() is called with !in_irq() &&
>      >  > !irqs_disabled(), but inside spin_lock or rcu read lock? I
>     have not seen
>      >  > things like that.
>      >
>      > For the complex conditions to call bpf_prog_put() with 1 refcnt,
>     we have
>      > been
>      > unable to really trigger this atomic violation after trying to
>     construct
>      > test cases manually. But we found that it is possible to show
>     cases with
>      > !in_irq() && !irqs_disabled(), but inside spin_lock or rcu read lock.
>      > For example, even a failed case, one of selftest cases of bpf,
>     netns_cookie,
>      > calls bpf_sock_map_update() and may indirectly call bpf_prog_put()
>      > only inside rcu read lock: The possible call stack is:
>      > net/core/sock_map.c: 615 bpf_sock_map_update()
>      > net/core/sock_map.c: 468 sock_map_update_common()
>      > net/core/sock_map.c:  217 sock_map_link()
>      > kernel/bpf/syscall.c: 2111 bpf_prog_put()
>      >
>      > The files about netns_cookie include
>      > tools/testing/selftests/bpf/progs/netns_cookie_prog.c and
>      > tools/testing/selftests/bpf/prog_tests/netns_cookie.c. We
>     inserted the
>      > following code in
>      > ‘net/core/sock_map.c: 468 sock_map_update_common()’:
>      > static int sock_map_update_common(..)
>      > {
>      >          int inIrq = in_irq();
>      >          int irqsDisabled = irqs_disabled();
>      >          int preemptBits = preempt_count();
>      >          int inAtomic = in_atomic();
>      >          int rcuHeld = rcu_read_lock_held();
>      >          printk("in_irq() %d, irqs_disabled() %d, preempt_count() %d,
>      >            in_atomic() %d, rcu_read_lock_held() %d", inIrq,
>     irqsDisabled,
>      >            preemptBits, inAtomic, rcuHeld);
>      > }
>      >
>      > The output message is as follows:
>      > root@(none):/root/bpf# ./test_progs -t netns_cookie
>      > [  137.639188] in_irq() 0, irqs_disabled() 0, preempt_count() 0,
>      > in_atomic() 0,
>      >          rcu_read_lock_held() 1
>      > #113     netns_cookie:OK
>      > Summary: 1/0 PASSED, 0 SKIPPED, 0 FAILED
>      >
>      > We notice that there are numerous callers in kernel/, net/ and
>     drivers/,
>      > so we
>      > highly suggest modifying __bpf_prog_put() to address this gap.
>     The gap
>      > exists
>      > because __bpf_prog_put() is only safe under in_irq() ||
>     irqs_disabled()
>      > but not in_atomic() || rcu_read_lock_held(). The following code
>     snippet may
>      > mislead developers into thinking that bpf_prog_put() is safe in all
>      > contexts.
>      > if (in_irq() || irqs_disabled()) {
>      >          INIT_WORK(&aux->work, bpf_prog_put_deferred);
>      >          schedule_work(&aux->work);
>      > } else {
>      >          bpf_prog_put_deferred(&aux->work);
>      > }
>      >
>      > Implicit dependency may lead to issues.
>      >
>      >  > Any problem here?
>      > We mentioned it to demonstrate the possibility of kvfree() being
>      > called by __bpf_prog_put_noref().
>      >
>      > Thanks.
>      > -- Teng Qi
>      >
>      > On Wed, May 17, 2023 at 1:08 AM Yonghong Song <yhs@meta.com
>     <mailto:yhs@meta.com>
>      > <mailto:yhs@meta.com <mailto:yhs@meta.com>>> wrote:
>      >
>      >
>      >
>      >     On 5/16/23 4:18 AM, starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>
>      >     <mailto:starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>> wrote:
>      >      > From: Teng Qi <starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>
>      >     <mailto:starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>>>
>      >      >
>      >      > Hi, bpf developers,
>      >      >
>      >      > We are developing a static tool to check the matching between
>      >     helpers and the
>      >      > context of hooks. During our analysis, we have discovered some
>      >     important
>      >      > findings that we would like to report.
>      >      >
>      >      > ‘kernel/bpf/syscall.c: 2097 __bpf_prog_put()’ shows that
>     function
>      >      > bpf_prog_put_deferred() won`t be called in the condition of
>      >      > ‘in_irq() || irqs_disabled()’.
>      >      > if (in_irq() || irqs_disabled()) {
>      >      >      INIT_WORK(&aux->work, bpf_prog_put_deferred);
>      >      >      schedule_work(&aux->work);
>      >      > } else {
>      >      >
>      >      >      bpf_prog_put_deferred(&aux->work);
>      >      > }
>      >      >
>      >      > We suspect this condition exists because there might be
>     sleepable
>      >     operations
>      >      > in the callees of the bpf_prog_put_deferred() function:
>      >      > kernel/bpf/syscall.c: 2097 __bpf_prog_put()
>      >      > kernel/bpf/syscall.c: 2084 bpf_prog_put_deferred()
>      >      > kernel/bpf/syscall.c: 2063 __bpf_prog_put_noref()
>      >      > kvfree(prog->aux->jited_linfo);
>      >      > kvfree(prog->aux->linfo);
>      >
>      >     Looks like you only have suspicion here. Could you find a real
>      >     violation
>      >     here where __bpf_prog_put() is called with !in_irq() &&
>      >     !irqs_disabled(), but inside spin_lock or rcu read lock? I
>     have not seen
>      >     things like that.
>      >
>      >      >
>      >      > Additionally, we found that array prog->aux->jited_linfo is
>      >     initialized in
>      >      > ‘kernel/bpf/core.c: 157 bpf_prog_alloc_jited_linfo()’:
>      >      > prog->aux->jited_linfo = kvcalloc(prog->aux->nr_linfo,
>      >      >    sizeof(*prog->aux->jited_linfo),
>     bpf_memcg_flags(GFP_KERNEL |
>      >     __GFP_NOWARN));
>      >
>      >     Any problem here?
>      >
>      >      >
>      >      > Our question is whether the condition 'in_irq() ||
>      >     irqs_disabled() == false' is
>      >      > sufficient for calling 'kvfree'. We are aware that calling
>      >     'kvfree' within the
>      >      > context of a spin lock or an RCU lock is unsafe.
> 
>     Your above analysis makes sense if indeed that kvfree cannot appear
>     inside a spin lock region or RCU read lock region. But is it true?
>     I checked a few code paths in kvfree/kfree. It is either guarded
>     with local_irq_save/restore or by
>     spin_lock_irqsave/spin_unlock_irqrestore, etc. Did I miss
>     anything? Are you talking about RT kernel here?
> 
> 
>      >      >
>      >      > Therefore, we propose modifying the condition to include
>      >     in_atomic(). Could we
>      >      > update the condition as follows: "in_irq() ||
>     irqs_disabled() ||
>      >     in_atomic()"?
>      >      >
>      >      > Thank you! We look forward to your feedback.
>      >      >
>      >      > Signed-off-by: Teng Qi <starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>
>      >     <mailto:starmiku1207184332@gmail.com
>     <mailto:starmiku1207184332@gmail.com>>>
>      >
>