linux-kernel - Re: [PATCH -next] lib: disable KCSAN for XArray

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 3 Mar 2020 20:33:56 -0800
From:   Matthew Wilcox <willy@...radead.org>
To:     "Paul E. McKenney" <paulmck@...nel.org>
Cc:     Qian Cai <cai@....pw>, elver@...gle.com,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH -next] lib: disable KCSAN for XArray

On Tue, Mar 03, 2020 at 08:05:15PM -0800, Paul E. McKenney wrote:
> On Tue, Mar 03, 2020 at 07:33:29PM -0800, Matthew Wilcox wrote:
> > On Tue, Mar 03, 2020 at 10:15:51PM -0500, Qian Cai wrote:
> > > Functions like xas_find_marked(), xas_set_mark(), and xas_clear_mark()
> > > could happen concurrently result in data races, but those operate only
> > > on a single bit that are pretty much harmless. For example,
> > 
> > Those aren't data races.  The writes are protected by a spinlock and the
> > reads by the RCU read lock.  If the tool can't handle RCU protection,
> > it's not going to be much use.
> 
> Would KCSAN's ASSERT_EXCLUSIVE_BITS() help here?

I'm quite lost in the sea of new macros that have been added to help
with KCSAN.  It doesn't help that they're in -next somewhere that I
can't find, and not in mainline yet.  Is there documentation somewhere?

> RCU readers -do- exclude pre-insertion initialization on the one hand,
> and those post-removal accesses that follow a grace period, but only
> if that grace period starts after the removal.  In addition, the
> accesses due to rcu_dereference(), rcu_assign_pointer(), and similar
> are guaranteed to work even if they are concurrent.
> 
> Or am I missing something subtle here?

I probably am.  An XArray is composed of a tree of xa_nodes:

struct xa_node {
        unsigned char   shift;          /* Bits remaining in each slot */
        unsigned char   offset;         /* Slot offset in parent */
        unsigned char   count;          /* Total entry count */
        unsigned char   nr_values;      /* Value entry count */
        struct xa_node __rcu *parent;   /* NULL at top of tree */
        struct xarray   *array;         /* The array we belong to */
        union {
                struct list_head private_list;  /* For tree user */
                struct rcu_head rcu_head;       /* Used when freeing node */
        };
        void __rcu      *slots[XA_CHUNK_SIZE];
        union {
                unsigned long   tags[XA_MAX_MARKS][XA_MARK_LONGS];
                unsigned long   marks[XA_MAX_MARKS][XA_MARK_LONGS];
        };
};

'shift' is initialised before the node is inserted into the tree.
Ditto 'offset'.  'count' and 'nr_values' should only be touched with the
xa_lock held.  'parent' might be modified with the lock held and an RCU
reader expecting to see either the previous or new value.  'array' should
not change once the node is inserted.  private_list is, I believe, only
modified with the lock held.  'slots' may be modified with the xa_lock
held, and simultaneously read by an RCU reader.  Ditto 'tags'/'marks'.

The RCU readers are prepared for what they see to be inconsistent --
a fact of life when dealing with RCU!  So in a sense, yes, there is a
race there.  But it's a known, accepted race, and that acceptance is
indicated by the fact that the RCU lock is held.  Does there need to be
more annotation here?  Or is there an un-noticed bug that the tool is
legitimately pointing out?