From patchwork Mon Apr 29 16:56:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Siddharth Chintamaneni X-Patchwork-Id: 13647380 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-qv1-f54.google.com (mail-qv1-f54.google.com [209.85.219.54]) (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 A0E3533C7 for ; Mon, 29 Apr 2024 16:57:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714409837; cv=none; b=QK4mfo1nSpC1kURcwFWhCPZ5JcGLhwIHwHUT80TcK9Z9p9/5corVmckI5Tg6sKtkSnM/Wc0DPdZZCvXRHYD5FGf/rQsGUCQpeoTzaaWDxVj8TwwQT3cKzSS+4M1X+X1Tr3HNoDpv6KaYGbFF+kv97jEaj0IyjjCiA6XFwuRrJZc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714409837; c=relaxed/simple; bh=siK3kKrobvPnmziYFgX7k3QNzrUUA/glXT1ty22eN4U=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=QOM7wXaeHgJ1H11Y53sfoBsSEI8TcMZ0oVGi56cBm+to6MC7+phCly3DMrXl43S6UwSXQCzk8tVeVaYC1QIUFusbjlb6FeWD7qDumg/9wsY+G898Dl/5HBjTkd6bMuyRFntOFH+I0sRBGq5LdhDisutMRd2ln+Hhu2lbDhAkOv8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Ng5jPwRL; arc=none smtp.client-ip=209.85.219.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Ng5jPwRL" Received: by mail-qv1-f54.google.com with SMTP id 6a1803df08f44-69b59c10720so11340266d6.3 for ; Mon, 29 Apr 2024 09:57:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714409834; x=1715014634; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=aOZZTMrjSpiAuTui+v+CO8NJMpyQfa45AC/DO4tm6Hg=; b=Ng5jPwRLIQLzONaAmmw52q7sf9qjxzZEM+ob64oaq6OLZodyIQ+NsWJzP892oZnHKr cyu6UJesLhH3Gm6AJnMr+nS2g2WuBlZonUBFKhhkb+gZgTuoJ+USeKSWx321nHeouV8w AMKHLIhsW3xXzvtTP0KNUm/+YUCh9m8CfImeBAnwZt4k7mKtA1bSPHphWQORyCUZKCih n+SPEBZHzj6fJeeWrTOVHPAkqi/tlzaQ5XeRk5Q3Z1g3aXVX/7K1bnfsEKve0/DIcj1H 7Gkv5ERojKcrPCEqRc1KgB2ZVaWRN4SZSIa/NXuy1BJKjTUNG1PnXeIXOflWdNSXR441 lVxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714409834; x=1715014634; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=aOZZTMrjSpiAuTui+v+CO8NJMpyQfa45AC/DO4tm6Hg=; b=EyvQ0T5cIqyQPUqSAiRvtkDwfqftqgJGAGweSochJA1BHiBaed7S3ErNJFPuFJHUFC uN+zrOwo2QY72nUnTIOX4jiie1BPf+wztGPvh+KZB2y+37ttKgi3F1fzFobwxeZntI0N YaELeMSNnxI7TGb4p6iyYTpJcJ2aW7eOQc14Wd5rnpgr9+0OzIGlKCoGH/mY+QTTJ1pL ScgDuDmePn2LFVYfGyBWCE5fHAnUvkudYBOiRgc6FiIrij6kNIyOq3iPLJdpbKBesVOw 24Bu4qzr+XUtKDFLrSR3ZB967KgGC381TqdZE5FnbiOArFMhi8YJPnYsKSaHxvgKnW2v K/zw== X-Gm-Message-State: AOJu0YwowGcNDeGVrGt+YKCNZ6C1iJUm8W3m5HWihVPuDu3ZYmstcXP2 D5dzLh0dMMltruK0SOqQZ/IZORTPTLkRFkVH72Owd5K/L36eabuenPbFYg== X-Google-Smtp-Source: AGHT+IH9+uB0yVCB3y/ubdvkxPxo5aVEj/hIpTwdj6nZROVz1W008mXxXK1IsHTh15qe4mH5gdza6Q== X-Received: by 2002:a05:6214:cc6:b0:699:206c:2db1 with SMTP id 6-20020a0562140cc600b00699206c2db1mr14153561qvx.16.1714409834384; Mon, 29 Apr 2024 09:57:14 -0700 (PDT) Received: from fedora.. ([2607:b400:30:a100:6442:5b0e:54ab:110b]) by smtp.gmail.com with ESMTPSA id k17-20020a0cc791000000b0069b5672bab8sm3031988qvj.134.2024.04.29.09.57.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 29 Apr 2024 09:57:14 -0700 (PDT) From: Siddharth Chintamaneni To: bpf@vger.kernel.org Cc: alexei.starovoitov@gmail.com, daniel@iogearbox.net, olsajiri@gmail.com, andrii@kernel.org, yonghong.song@linux.dev, rjsu26@vt.edu, sairoop@vt.edu, Siddharth Chintamaneni , syzbot+8bdfc2c53fb2b63e1871@syzkaller.appspotmail.com Subject: [PATCH bpf-next 1/2] Patch to Fix deadlocks in queue and stack maps Date: Mon, 29 Apr 2024 12:56:57 -0400 Message-ID: <20240429165658.1305969-1-sidchintamaneni@gmail.com> X-Mailer: git-send-email 2.44.0 Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net From: Siddharth Chintamaneni This patch address a possible deadlock issue in queue and stack map types. Deadlock could happen when a nested BPF program acquires the same lock as the parent BPF program to perform a write operation on the same map as the first one. This bug is also reported by syzbot. Link: https://lore.kernel.org/lkml/0000000000004c3fc90615f37756@google.com/ Reported-by: syzbot+8bdfc2c53fb2b63e1871@syzkaller.appspotmail.com Fixes: f1a2e44a3aec ("bpf: add queue and stack maps") Signed-off-by: Siddharth Chintamaneni --- kernel/bpf/queue_stack_maps.c | 42 +++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/kernel/bpf/queue_stack_maps.c b/kernel/bpf/queue_stack_maps.c index d869f51ea93a..4b7df1a53cf2 100644 --- a/kernel/bpf/queue_stack_maps.c +++ b/kernel/bpf/queue_stack_maps.c @@ -18,6 +18,7 @@ struct bpf_queue_stack { raw_spinlock_t lock; u32 head, tail; u32 size; /* max_entries + 1 */ + int __percpu *map_locked; char elements[] __aligned(8); }; @@ -78,6 +79,16 @@ static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) qs->size = size; + qs->map_locked = bpf_map_alloc_percpu(&qs->map, + sizeof(int), + sizeof(int), + GFP_USER); + if (!qs->map_locked) { + bpf_map_area_free(qs); + return ERR_PTR(-ENOMEM); + } + + raw_spin_lock_init(&qs->lock); return &qs->map; @@ -98,6 +109,16 @@ static long __queue_map_get(struct bpf_map *map, void *value, bool delete) int err = 0; void *ptr; + preempt_disable(); + local_irq_save(flags); + if (unlikely(__this_cpu_inc_return(*(qs->map_locked)) != 1)) { + __this_cpu_dec(*(qs->map_locked)); + local_irq_restore(flags); + preempt_enable(); + return -EBUSY; + } + preempt_enable(); + if (in_nmi()) { if (!raw_spin_trylock_irqsave(&qs->lock, flags)) return -EBUSY; @@ -133,6 +154,17 @@ static long __stack_map_get(struct bpf_map *map, void *value, bool delete) void *ptr; u32 index; + preempt_disable(); + local_irq_save(flags); + if (unlikely(__this_cpu_inc_return(*(qs->map_locked)) != 1)) { + __this_cpu_dec(*(qs->map_locked)); + local_irq_restore(flags); + preempt_enable(); + return -EBUSY; + } + preempt_enable(); + + if (in_nmi()) { if (!raw_spin_trylock_irqsave(&qs->lock, flags)) return -EBUSY; @@ -194,6 +226,16 @@ static long queue_stack_map_push_elem(struct bpf_map *map, void *value, int err = 0; void *dst; + preempt_disable(); + local_irq_save(irq_flags); + if (unlikely(__this_cpu_inc_return(*(qs->map_locked)) != 1)) { + __this_cpu_dec(*(qs->map_locked)); + local_irq_restore(irq_flags); + preempt_enable(); + return -EBUSY; + } + preempt_enable(); + /* BPF_EXIST is used to force making room for a new element in case the * map is full */ From patchwork Mon Apr 29 16:56:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Siddharth Chintamaneni X-Patchwork-Id: 13647381 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-qk1-f171.google.com (mail-qk1-f171.google.com [209.85.222.171]) (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 0408F33C7 for ; Mon, 29 Apr 2024 16:57:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714409843; cv=none; b=ldaI0jGeGwL91Xx+MntnCT3EnMYoDrqySk7T83/UQcWQGm1PbB8WkfMIOfJdkSOcayJv75GcIF0agndrwDzK42+D9OoEU+S2Wo9ZGcQsC5jWQ4wlRiL50beeLOzcjPcTONQ69hpbUgIQVlKPfVRmHxLEpOkv/GGGZxeVxiauGTA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714409843; c=relaxed/simple; bh=0W9/C1hPgxxlARFFETzIJ2476MZg+pUaNpx7i5oBKAg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=trQw7M/f9mo5VbxaU4t3CGSa9WNlbVbg8CL4C+s5cwe84iOQc4Cu6QyPLOwgQL5YR7G9/uoOY/cs4Gsh8hcyYRyHkvBvvd3jcRiqlecMlfsGLyh38hTeAI/QVQqrmlq/bxVRai9Qp4WVNeAR8oII5RVcjpQMWnyMgU/iL5Gi90U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Yp07FNFo; arc=none smtp.client-ip=209.85.222.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Yp07FNFo" Received: by mail-qk1-f171.google.com with SMTP id af79cd13be357-78f05afc8d6so368860185a.3 for ; Mon, 29 Apr 2024 09:57:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714409841; x=1715014641; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=hf3sBEjssVoG0X9/iQmT36SkFRO7vV5Eo//ezrteqt4=; b=Yp07FNFoGmjUwfQWmeqe7XEYxW87Qzsg1FKr8b/P0xQ5SubbopGejc03rBeyaTxuN4 CG/8STcTHX4BLGibWrb/4CddOfAVuyU2J1pt0W0ZzO51e1ZwzRtazcP+M0Xy6zPe/AtZ xr04fyTf4+80sCs2XRgkF90qygOjBQOX1O8KGmeUMlr4Wfw2G8o5USNOYGDh7ZlTQIoC AD1lTok9LPBsVCKj68lqUBeibSDeZC4DxfIOIgukdKqsal5Zbj4RsdOMtROs7PLT1OB9 lc+z/hzkrfJwYHIam6pMx+KKxfqTXX7GIp9XyVsPSdiLlRocwJvWSul+Xg0QSsZkE/KN iEnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714409841; x=1715014641; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=hf3sBEjssVoG0X9/iQmT36SkFRO7vV5Eo//ezrteqt4=; b=LwTF9hFp7dL7NQf50sSnPiN661H00z2uZl+eczSKuwjzoPcI3mrG/qD7X2S2WxzIV1 vUVUAaMUP4cVOHaWvVqN5jLzxdY0RdN78MqfWemVC0RX0STIhXSwiRET7mtxBvs89Iio rnmh2u24NA3iBTOLmY3EUW8MjFV+VLTh5v5NlSI33QtTTi//5u8F7mELJIKKeNLm8fxj 2yBbg4Fm1ZF8okBW4ZCGuQQXLr4GXqRhB77hU8vtOqTVCArRtgCPM3cfgeEUEFCxyA+s HJkiOdqGqzhTCIbrOZWtP4f1iivTZ1dDJReghQZCO0epOhSot6D6dEKkemJAmd3cn/Pq 0Wqw== X-Gm-Message-State: AOJu0YyFZEYVQb0Bjh6wLzq9uhBU8gzpmEFR3Wj2k5ZO0+VX0jyr+eeE J3Pw0bLDP2yy+JuBwE/5TUr+HEyfHpAtDlYloob2EklE5m7ubNs6130teg== X-Google-Smtp-Source: AGHT+IE+3CAjFbhTBNCM8mB29I8h5oOi4hBoFCHRSb6c0QTIbL0TUiaqHNA9VqQBfHrEVJME0AENbg== X-Received: by 2002:a05:6214:194c:b0:6a0:d29d:a416 with SMTP id q12-20020a056214194c00b006a0d29da416mr3008066qvk.47.1714409840718; Mon, 29 Apr 2024 09:57:20 -0700 (PDT) Received: from fedora.. ([2607:b400:30:a100:6442:5b0e:54ab:110b]) by smtp.gmail.com with ESMTPSA id k17-20020a0cc791000000b0069b5672bab8sm3031988qvj.134.2024.04.29.09.57.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 29 Apr 2024 09:57:20 -0700 (PDT) From: Siddharth Chintamaneni To: bpf@vger.kernel.org Cc: alexei.starovoitov@gmail.com, daniel@iogearbox.net, olsajiri@gmail.com, andrii@kernel.org, yonghong.song@linux.dev, rjsu26@vt.edu, sairoop@vt.edu, Siddharth Chintamaneni Subject: [PATCH bpf-next 2/2] Added selftests to check deadlocks in queue and stack map Date: Mon, 29 Apr 2024 12:56:58 -0400 Message-ID: <20240429165658.1305969-2-sidchintamaneni@gmail.com> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240429165658.1305969-1-sidchintamaneni@gmail.com> References: <20240429165658.1305969-1-sidchintamaneni@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net From: Siddharth Chintamaneni Added selftests to check for nested deadlocks in queue and stack maps. Signed-off-by: Siddharth Chintamaneni --- .../prog_tests/test_queue_stack_nested_map.c | 48 ++++++++++++++ .../bpf/progs/test_queue_stack_nested_map.c | 62 +++++++++++++++++++ 2 files changed, 110 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c create mode 100644 tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c diff --git a/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c b/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file mode 100644 index 000000000000..731e958419eb --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c @@ -0,0 +1,48 @@ +// SPDX-License-Identifier: GPL-2.0 +#include +#include + +#include "test_queue_stack_nested_map.skel.h" + + +static void test_map_queue_stack_nesting_success(bool is_map_queue) +{ + struct test_queue_stack_nested_map *skel; + int err; + int prog_fd; + + LIBBPF_OPTS(bpf_test_run_opts, ropts); + + skel = test_queue_stack_nested_map__open_and_load(); + if (!ASSERT_OK_PTR(skel, "test_queue_stack_nested_map__open_and_load")) + goto out; + + err = test_queue_stack_nested_map__attach(skel); + if (!ASSERT_OK(err, "test_queue_stack_nested_map__attach")) + goto out; + + if (is_map_queue) { + prog_fd = bpf_program__fd(skel->progs.test_queue_nesting); + err = bpf_prog_test_run_opts(prog_fd, &ropts); + ASSERT_OK(err, "test_nested_queue_map_run"); + } else { + prog_fd = bpf_program__fd(skel->progs.test_stack_nesting); + err = bpf_prog_test_run_opts(prog_fd, &ropts); + ASSERT_OK(err, "test_nested_stack_map_run"); + } + + + +out: + test_queue_stack_nested_map__destroy(skel); +} + +void test_test_queue_stack_nested_map(void) +{ + if (test__start_subtest("map_queue_nesting")) + test_map_queue_stack_nesting_success(true); + if (test__start_subtest("map_stack_nesting")) + test_map_queue_stack_nesting_success(false); + +} + diff --git a/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c b/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c new file mode 100644 index 000000000000..6d22016b1709 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c @@ -0,0 +1,62 @@ +// SPDX-License-Identifier: GPL-2.0 +#include "vmlinux.h" +#include +#include + +struct { + __uint(type, BPF_MAP_TYPE_STACK); + __uint(max_entries, 32); + __uint(map_flags, 0); + __uint(key_size, 0); + __uint(value_size, sizeof(__u32)); +} map_stack SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_QUEUE); + __uint(max_entries, 32); + __uint(map_flags, 0); + __uint(key_size, 0); + __uint(value_size, sizeof(__u32)); +} map_queue SEC(".maps"); + +SEC("fentry/_raw_spin_unlock_irqrestore") +int BPF_PROG(test_stack_nesting2, raw_spinlock_t *lock, unsigned long flags) +{ + __u32 value = 1; + + bpf_map_push_elem(&map_stack, &value, 0); + + return 0; +} + +SEC("fentry/bpf_fentry_test1") +int BPF_PROG(test_stack_nesting, int a) +{ + __u32 value = 1; + + bpf_map_push_elem(&map_stack, &value, 0); + + return 0; +} + +SEC("fentry/_raw_spin_unlock_irqrestore") +int BPF_PROG(test_queue_nesting2, raw_spinlock_t *lock, unsigned long flags) +{ + __u32 value = 1; + + bpf_map_pop_elem(&map_queue, &value); + + return 0; +} + +SEC("fentry/bpf_fentry_test1") +int BPF_PROG(test_queue_nesting, int a) +{ + __u32 value = 1; + + bpf_map_push_elem(&map_queue, &value, 0); + + return 0; +} + +char _license[] SEC("license") = "GPL";