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 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id EE89CC433EF for ; Mon, 18 Jul 2022 22:42:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9286E6B0071; Mon, 18 Jul 2022 18:42:14 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8D81F6B0078; Mon, 18 Jul 2022 18:42:14 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7C7346B007B; Mon, 18 Jul 2022 18:42:14 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 6E08E6B0071 for ; Mon, 18 Jul 2022 18:42:14 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay12.hostedemail.com (Postfix) with ESMTP id 409A8120F51 for ; Mon, 18 Jul 2022 22:42:14 +0000 (UTC) X-FDA: 79701695388.23.CCE5599 Received: from mail-qk1-f178.google.com (mail-qk1-f178.google.com [209.85.222.178]) by imf10.hostedemail.com (Postfix) with ESMTP id E2388C0079 for ; Mon, 18 Jul 2022 22:42:13 +0000 (UTC) Received: by mail-qk1-f178.google.com with SMTP id n2so8567952qkk.8 for ; Mon, 18 Jul 2022 15:42:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Srf+AYvhoPZ4SANiE5r//Mtt56L7Cxm65IjKMxEOpbM=; b=TMkZVh5cRXYdusuziYLkDihvUfczQKJGa6SnTrPUBD0CFe8rd9W6aypO13w8ZEgafs pM6ghhD2hz2uvswuYMl+l6dJraSgQni8sAMSwXil/QcZDiJJV3GR8Zq6it/MOH15BqJx kf6Y8333ko9fS2NkYgAhl/4TnOXX8hc+aukzYLv+C5tcKIHdNXZT30Kh8aDSOPhLrktt ewAUNoNIUE7335HUHBDfeZf8kgbDs6gwTakDK2/qNrC//Ci+0Zzd6BjoCl5d8Jvh8tvk hgwJIPqBdyM8DznRS7IV18v+gtcOrgy/5PN6Vq9wd7wDB5Zwdr5R/lyBeCIB62iIVtFs HdYQ== 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=Srf+AYvhoPZ4SANiE5r//Mtt56L7Cxm65IjKMxEOpbM=; b=6+YKtOXKoTzmhqa9O5oEFdHZRuQ9Rr5/poEZuA+fEVOGqygBRQxhE9992I4RenkXDT DGzRB2Qu9DVtH3Wy2bd9jizbTUKOPehnNKfujXC0qIuzVoVsFJqWTfOFckbx8P1mWJbP 6eHQ8Djfol9bnlMwxUp2XWNzXpLJmZjnUN9MKIlcyU72rwKe7RfP9Y0/U4eucrEftd8N GppTkYknOFu9PBaRigwbLP8ckcDUg2FgNjFT/AHkDp1Gq7gA1eC0K8OANHtvvFlNpx6r 4clTJWZ787QV9W9Qe1vx2fzXCUhwfjhSIcjYfDtpGRyIgzR7b93nsZQaVqwmmqA0y6FL RfdA== X-Gm-Message-State: AJIora9iU5s+v0oZF3VUTRjikHVxW4SJSD/LFN18TXCPb3CeWNGONLny jrW5NvztIrY9A13I7SJ4/7V80+i+EpgFe0f+ddM= X-Google-Smtp-Source: AGRyM1shEhBbf2LtPRjG9yy2NUNITEJg83Tr7CVIPIIgx41eBcNi+fxHZ9b/xdC38HxZjPel/BrbLMsgkVhbY91ic/E= X-Received: by 2002:a37:4644:0:b0:6af:271e:a510 with SMTP id t65-20020a374644000000b006af271ea510mr20013693qka.515.1658184133183; Mon, 18 Jul 2022 15:42:13 -0700 (PDT) MIME-Version: 1.0 References: <3cd76121903de13713581687ffa45e668ef1475a.1655150842.git.andreyknvl@google.com> In-Reply-To: From: Andrey Konovalov Date: Tue, 19 Jul 2022 00:42:02 +0200 Message-ID: Subject: Re: [PATCH 31/32] kasan: implement stack ring for tag-based modes To: Marco Elver Cc: andrey.konovalov@linux.dev, Alexander Potapenko , Dmitry Vyukov , Andrey Ryabinin , kasan-dev , Peter Collingbourne , Evgenii Stepanov , Florian Mayer , Andrew Morton , Linux Memory Management List , LKML , Andrey Konovalov Content-Type: text/plain; charset="UTF-8" ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=TMkZVh5c; spf=pass (imf10.hostedemail.com: domain of andreyknvl@gmail.com designates 209.85.222.178 as permitted sender) smtp.mailfrom=andreyknvl@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1658184133; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Srf+AYvhoPZ4SANiE5r//Mtt56L7Cxm65IjKMxEOpbM=; b=HJGnBI75hC2UCPzEHdgoryngGLWLqdynXv4cfQ5AoBur+0ed2nhv0yWYFal3AQF79GllvX kBAW/Sl8LW11gZmFXhin9N2auB3+yy4202Pq8tei6Iep3/5aUdO0N1JvkedsjC7avf9tAc WqLSaf68k1sL0V9aip4sgyFnBsbRe3U= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1658184133; a=rsa-sha256; cv=none; b=08CalMfTcX+0FZbVBz8Rq67iruv75Pe0OY5fr1IYi6DEB4PJSDBCyIraxD4l8kbbLtH4tQ UIpCCOeLBGagro4tZMjcirqarX2hzaxbfOd5QgIrcBSw1xkYfNZYjXPKu+uBCF4/OxmWrx EV8wwxv3idPZRqvdGbx9zCxiyKq2YK4= X-Rspam-User: X-Rspamd-Queue-Id: E2388C0079 Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=TMkZVh5c; spf=pass (imf10.hostedemail.com: domain of andreyknvl@gmail.com designates 209.85.222.178 as permitted sender) smtp.mailfrom=andreyknvl@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-Stat-Signature: skimgqmyjup8py4e4ymog6gsbyxjpucx X-Rspamd-Server: rspam07 X-HE-Tag: 1658184133-858841 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Mon, Jun 20, 2022 at 3:35 PM Marco Elver wrote: > > > The number of entries in the stack ring is fixed in this version of the > > patch. We could either implement it as a config option or a command-line > > argument. I tilt towards the latter option and will implement it in v2 > > unless there are objections. > > Yes, that'd be good, along with just not allocating if no stacktraces > are requested per kasan.stacktrace=. Sounds good, will do in v2. > > +struct kasan_stack_ring_entry { > > + atomic64_t ptr; /* void * */ > > + atomic64_t size; /* size_t */ > > + atomic_t pid; /* u32 */ > > + atomic_t stack; /* depot_stack_handle_t */ > > + atomic_t is_free; /* bool */ > > Per comments below, consider making these non-atomic. Will do in v2. > > void kasan_complete_mode_report_info(struct kasan_report_info *info) > > { > > + u64 pos; > > + struct kasan_stack_ring_entry *entry; > > + void *object; > > + u32 pid; > > + depot_stack_handle_t stack; > > + bool is_free; > > If you switch away from atomic for kasan_stack_ring_entry members, you > can just replace the above with a 'struct kasan_stack_ring_entry' and > READ_ONCE() each entry into it below. It would be a bit confusing to have two kasan_stack_ring_entry-based variable in the function. I'll keep the current code if you don't mind. > > + bool alloc_found = false, free_found = false; > > + > > info->bug_type = get_bug_type(info); > > + > > + if (!info->cache || !info->object) > > + return; > > + > > + pos = atomic64_read(&stack_ring.pos); > > + > > + for (u64 i = pos - 1; i != pos - 1 - KASAN_STACK_RING_ENTRIES; i--) { > > + if (alloc_found && free_found) > > + break; > > + > > + entry = &stack_ring.entries[i % KASAN_STACK_RING_ENTRIES]; > > + > > + /* Paired with atomic64_set_release() in save_stack_info(). */ > > + object = (void *)atomic64_read_acquire(&entry->ptr); > > + > > + if (kasan_reset_tag(object) != info->object || > > + get_tag(object) != get_tag(info->access_addr)) > > + continue; > > + > > + pid = atomic_read(&entry->pid); > > + stack = atomic_read(&entry->stack); > > + is_free = atomic_read(&entry->is_free); > > + > > + /* Try detecting if the entry was changed while being read. */ > > + smp_mb(); > > + if (object != (void *)atomic64_read(&entry->ptr)) > > + continue; > > What if the object was changed, but 'ptr' is the same? It might very > well be possible to then read half of the info of the previous object, > and half of the new object (e.g. pid is old, stack is new). > > Is the assumption that it is extremely unlikely that this will happen > where 1) address is the same, and 2) tags are the same? And if it does > happen, it is unlikely that there'll be a bug on that address? > > It might be worth stating this in comments. This part will be removed in v2 due to the addition of an rwlock, but I'll add a comment about the stack ring being best-effort anyway. > Another thing is, if there's a bug, but concurrently you have tons of > allocations/frees that change the ring's entries at a very high rate, > how likely is it that the entire ring will have been wiped before the > entry of interest is found again? > > One way to guard against this is to prevent modifications of the ring > while the ring is searched. This could be implemented with a > percpu-rwsem, which is almost free for read-lockers but very expensive > for write-lockers. Insertions only acquire a read-lock, but on a bug > when searching the ring, you have to acquire a write-lock. Although you > currently take the contention hit for incrementing 'pos', so a plain > rwlock might also be ok. Will add an rwlock in v2. > It would be good to understand the probabilities of these corner cases > with some average to worst case workloads, and optimize based on that. With the new synchronizations and checks added in v2, the only problematic issue is when the stack ring overflows. Please see my response to your cover letter comment wrt this. > > +struct kasan_stack_ring stack_ring; > > This is a very large struct. Can it be allocated by memblock_alloc() > very early on only if required (kasan.stacktrace= can still switch it > off, right?). Will do in v2. > > +void save_stack_info(struct kmem_cache *cache, void *object, > > + gfp_t flags, bool is_free) > > static void save_stack_info(...) Right, will do in v2. > > +{ > > + u64 pos; > > + struct kasan_stack_ring_entry *entry; > > + depot_stack_handle_t stack; > > + > > + stack = kasan_save_stack(flags, true); > > + > > + pos = atomic64_fetch_add(1, &stack_ring.pos); > > + entry = &stack_ring.entries[pos % KASAN_STACK_RING_ENTRIES]; > > + > > + atomic64_set(&entry->size, cache->object_size); > > + atomic_set(&entry->pid, current->pid); > > + atomic_set(&entry->stack, stack); > > + atomic_set(&entry->is_free, is_free); > > + > > I don't see the point of these being atomic. You can make them normal > variables with the proper types, and use READ_ONCE() / WRITE_ONCE(). > > The only one where you truly need the atomic type is 'pos'. Will do in v2. > > + /* > > + * Paired with atomic64_read_acquire() in > > + * kasan_complete_mode_report_info(). > > + */ > > + atomic64_set_release(&entry->ptr, (s64)object); > > This could be smp_store_release() and 'ptr' can be just a normal pointer. Will do in v2. > One thing that is not entirely impossible though (vs. re-reading same > pointer but inconsistent fields I mentioned above), is if something > wants to write to the ring, but stalls for a very long time before the > release of 'ptr', giving 'pos' the chance to wrap around and another > writer writing the same entry. Something like: > > T0 | T1 > --------------------------------------+-------------------------------- > WRITE_ONCE(entry->size, ..) | > WRITE_ONCE(entry->pid, ..) | > | WRITE_ONCE(entry->size, ..) > | WRITE_ONCE(entry->pid, ..) > | WRITE_ONCE(entry->stack, ..) > | WRITE_ONCE(entry->is_free, ..) > | smp_store_release(entry->ptr, ...) > WRITE_ONCE(entry->stack, ..) | > WRITE_ONCE(entry->is_free, ..) | > smp_store_release(entry->ptr, ...) | > > Which results in some mix of T0's and T1's data. > > The way to solve this is to implement a try-lock using 'ptr': > > #define BUSY_PTR ((void*)1) // non-zero because initial values are 0 > old_ptr = READ_ONCE(entry->ptr); > if (old_ptr == BUSY_PTR) > goto next; /* Busy slot. */ > if (!try_cmpxchg(&entry->ptr, &old_ptr, BUSY_PTR)) > goto next; /* Busy slot. */ > ... set fields as before ... > smp_store_release(&entry->ptr, object); Sounds good, will do in v2. Thank you, Marco!