Received: by 2002:a25:683:0:0:0:0:0 with SMTP id 125csp1322275ybg; Thu, 11 Jun 2020 07:00:39 -0700 (PDT) X-Google-Smtp-Source: ABdhPJydvTCcvSF/t3LnBoA7kF4zhxA3dy6YlscT+lJMU6y7vDNglKPOJYsZXNPqJkcL2QpozDQU X-Received: by 2002:a17:907:1118:: with SMTP id qu24mr8204319ejb.287.1591884038463; Thu, 11 Jun 2020 07:00:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1591884038; cv=none; d=google.com; s=arc-20160816; b=zZT2MbGyj1F5OB93nCJ0JOAfcImsg+oenmUzEKh0RR0s20NcFhbGkMKJT2PkebrTB9 TYHi/D0IOuJyvrmccvglkNS4UwlZisdTvzgCVCZl5+erQhn6/rbaQrN0jGZycmDgVtWA xoBYBZrX/Pyasmk3zW4BbEUFBxyF/PDi4ga+D2cWf+iWXs0h08ya8ajN2WjalLL4xg05 RWaytU9tBbccrufOhoShRzx31GtnN2uVC9/Aj96v9wpSl8PleKhb4U3hRZ4Ev5pKkoMB BOpPAtFMrm/7MZdI6eVYm+TVgjSZoeA19bn5RWBWYjeZsmAb9ebpluotY8OCl9FPz93t oDGw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:user-agent:in-reply-to :content-disposition:mime-version:references:message-id:subject:cc :to:from:date; bh=Dqta6kkZ2F+4NTcoq1d0c+CulHhtTTXWUXSaqBMpau8=; b=ACkfPvh7vyqe9xsVamTehIcyf4ErJeqbAblOQ97BazMlZBAmIjsXRZqNMruaH4u2J7 SsI/jTD5uVqhsWOaNRDITUQooTycp3mF/2dpB7Qy6KrCxSm3gj2ifUzo6lNTY9h96mHH 1v3XOqFKu+XRGZVXVNXGoYdMJTCTqi3aoWmChLUDTSIuzp3eWs74MkDjmQVoueIuyKZe aIy0Gpg46CDAg7+BxU5FQFwjyYKrKMJyb9Lu7AOqi8yiMWEIbMicAtNXUcGl6E50DCLi i+8bGuYYw/QAwYuL0I0pja3OKQD9oFo9/rAl0iaafiAsKxc4RRWL8rTcmiitHnIrjWyS 0SMA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id n19si2012685ejl.25.2020.06.11.07.00.14; Thu, 11 Jun 2020 07:00:38 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727814AbgFKNzO (ORCPT + 99 others); Thu, 11 Jun 2020 09:55:14 -0400 Received: from mx2.suse.de ([195.135.220.15]:33668 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726109AbgFKNzN (ORCPT ); Thu, 11 Jun 2020 09:55:13 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 64D29AE53; Thu, 11 Jun 2020 13:55:14 +0000 (UTC) Date: Thu, 11 Jun 2020 15:55:09 +0200 From: Petr Mladek To: John Ogness Cc: Peter Zijlstra , Sergey Senozhatsky , Sergey Senozhatsky , Steven Rostedt , Linus Torvalds , Greg Kroah-Hartman , Andrea Parri , Thomas Gleixner , kexec@lists.infradead.org, linux-kernel@vger.kernel.org, Paul McKenney Subject: Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer Message-ID: <20200611135509.GE6581@linux-b0ei> References: <20200501094010.17694-1-john.ogness@linutronix.de> <20200501094010.17694-3-john.ogness@linutronix.de> <20200609093103.GB23752@linux-b0ei> <87lfkwuwg1.fsf@vostro.fn.ogness.net> <20200610093835.GB4311@linux-b0ei> <87o8prp6bi.fsf@vostro.fn.ogness.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <87o8prp6bi.fsf@vostro.fn.ogness.net> User-Agent: Mutt/1.10.1 (2018-07-13) Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed 2020-06-10 12:24:01, John Ogness wrote: > On 2020-06-10, Petr Mladek wrote: > >> >> --- /dev/null > >> >> +++ b/kernel/printk/printk_ringbuffer.c > >> >> +/* > >> >> + * Given a data ring (text or dict), put the associated descriptor of each > >> >> + * data block from @lpos_begin until @lpos_end into the reusable state. > >> >> + * > >>>> + * If there is any problem making the associated descriptor reusable, either > >>>> + * the descriptor has not yet been committed or another writer task has > >>>> + * already pushed the tail lpos past the problematic data block. Regardless, > >>>> + * on error the caller can re-load the tail lpos to determine the situation. > >>>> + */ > >>>> +static bool data_make_reusable(struct printk_ringbuffer *rb, > >>>> + struct prb_data_ring *data_ring, > >>>> + unsigned long lpos_begin, > >>>> + unsigned long lpos_end, > >>>> + unsigned long *lpos_out) > >>>> +{ > >>>> + struct prb_desc_ring *desc_ring = &rb->desc_ring; > >>>> + struct prb_data_blk_lpos *blk_lpos; > >>>> + struct prb_data_block *blk; > >>>> + unsigned long tail_lpos; > >>>> + enum desc_state d_state; > >>>> + struct prb_desc desc; > >>>> + unsigned long id; > >>>> + > >>>> + /* > >>>> + * Using the provided @data_ring, point @blk_lpos to the correct > >>>> + * blk_lpos within the local copy of the descriptor. > >>>> + */ > >>>> + if (data_ring == &rb->text_data_ring) > >>>> + blk_lpos = &desc.text_blk_lpos; > >>>> + else > >>>> + blk_lpos = &desc.dict_blk_lpos; > >>>> + > >>>> + /* Loop until @lpos_begin has advanced to or beyond @lpos_end. */ > >>>> + while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) { > >>>> + blk = to_block(data_ring, lpos_begin); > >>>> + id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */ > >>>> + > >>>> + /* > >>>> + * Guarantee the block ID is loaded before checking the tail > >>>> + * lpos. The loaded block ID can only be considered valid if > >>>> + * the tail lpos has not overtaken @lpos_begin. This pairs > >>>> + * with data_alloc:A. > >>>> + * > >>>> + * Memory barrier involvement: > >>>> + * > >>>> + * If data_make_reusable:A reads from data_alloc:B, then > >>>> + * data_make_reusable:C reads from data_push_tail:D. > >>>> + * > >>>> + * Relies on: > >>>> + * > >>>> + * MB from data_push_tail:D to data_alloc:B > >>>> + * matching > >>>> + * RMB from data_make_reusable:A to data_make_reusable:C > >>>> + * > >>>> + * Note: data_push_tail:D and data_alloc:B can be different > >>>> + * CPUs. However, the data_alloc:B CPU (which performs > >>>> + * the full memory barrier) must have previously seen > >>>> + * data_push_tail:D. > >>>> + */ > >>>> + smp_rmb(); /* LMM(data_make_reusable:B) */ > >>>> + > >>>> + tail_lpos = atomic_long_read(&data_ring->tail_lpos > >>>> + ); /* LMM(data_make_reusable:C) */ > >>>> + > >>>> + /* > >>>> + * If @lpos_begin has fallen behind the tail lpos, the read > >>>> + * block ID cannot be trusted. Fast forward @lpos_begin to the > >>>> + * tail lpos and try again. > >>>> + */ > >>>> + if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) { > >>>> + lpos_begin = tail_lpos; > >>>> + continue; > >>>> + } > >>> > >>> I am sorry if we have had this discussion already in past. > >> > >> We have [0]. (Search for "Ouch.") > > > > I see. Thanks a lot for the pointer. > > > >>> Well, it would just prove that it really needs a comment why this > >>> check is necessary. > >> > >> The comment says why it is necessary. The previous read of the block ID > >> cannot be trusted if the the tail has been pushed beyond it. > > > > Not really. The comment describes what the check does. But it does not > > explain why it is needed. The reason might be described be something like: > > > > * Make sure that the id read from tail_lpos is really > > * pointing to this lpos. The block might have been > > * reused in the meantime. Make sure to do not make > > * the new owner reusable. > > That is _not_ what this check is doing. I recommend looking closely at > the example you posted. This is not about whether or not a descriptor is > pointing to this lpos. In your example you showed that ID, state, and > lpos values could all look good, but it is for the _new_ record and we > should _not_ invalidate that one. OK, let's make sure that we are talking about the same example. I was talking about this one from https://lore.kernel.org/lkml/87ftecy343.fsf@linutronix.de/ % [*] Another problem would be when data_make_reusable() see the new % data already in the committed state. It would make fresh new % data reusable. % % I mean the following: % % CPU0 CPU1 % % data_alloc() % begin_lpos = dr->head_lpos % data_push_tail() % lpos = dr->tail_lpos % prb_reserve() % # reserve the location of current % # dr->tail_lpos % prb_commit() % % id = blk->id % # read id for the freshly written data on CPU1 % # and happily make them reusable % data_make_reusable() Sigh, sigh, sigh, there is a hugely misleading comment in the example: % # reserve the location of current % # dr->tail_lpos It is true that it reserves part of this location. But it will use data_ring->head_lpos for the related desc->text_blk_lpos.begin !!! See below: > We can detect the scenario you pointed out by verifying the tail has not > moved beyond the data block that the ID was read from. The comment for > this check says: > > If @lpos_begin has fallen behind the tail lpos, > the read block ID cannot be trusted. > > This is exactly the why. It is only about whether we can trust that a > non-garbage block ID was read. Or do you want me to add: > > ... because data read that is behind the tail lpos must be > considered garbage. > > > But wait! This situation should get caught by the two existing descriptor > > checks: > > > >> case desc_committed: > >> /* > >> * This data block is invalid if the descriptor > >> * does not point back to it. > >> */ > >> if (blk_lpos->begin != lpos_begin) > >> return false; > >> desc_make_reusable(desc_ring, id); > >> break; > >> case desc_reusable: > >> /* > >> * This data block is invalid if the descriptor > >> * does not point back to it. > >> */ > >> if (blk_lpos->begin != lpos_begin) > >> return false; > >> break; > > No. Your example showed that it is not caught here. I am afraid that my example was wrong: If blk->id comes from the new descriptor written by CPU1 then blk_lpos->begin is based on the old data_ring->head_lpos. Then it is different from lpos_begin. Let's put it another way. The state of the descriptor defines validity of the data. Descriptor in committed state _must not_ point to invalid data block!!! If a descriptor in committed state point to lpos that was in invalid range before reading the descriptor then we have a huge hole in the design. This is why I believe that the check of the descriptor must be enough. Best Regards, Petr PS: I am sorry if I create too much confusion. It is easy to get lost :-(