linux-kernel - Re: [PATCH] Add next, prev pointer in xa

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] [day] [month] [year] [list]

Date:   Wed, 18 Mar 2020 09:49:30 +0900
From:   JaeJoon Jung <rgbi3307@...il.com>
To:     Matthew Wilcox <willy@...radead.org>
Cc:     maple-tree@...ts.infradead.org, linux-kernel@...r.kernel.org,
        linux-riscv <linux-riscv@...ts.infradead.org>, koct9i@...il.com
Subject: Re: [PATCH] Add next, prev pointer in xa_node at the lib/xarray.c

Hi Matthew,
Thank you for your deep response.

I think XArray is a very well-made structure that requires no further
improvement if the indexes are dense in a 64-bit system.

Since xa_node is 576 bytes and is set to fit 7 per 4kB page,
adding a data type to xa_node is rather a memory waste problem.

#define XA_CHUNK_SHIFT          (CONFIG_BASE_SMALL ? 4 : 6)
XA_CHUNK_SIZE is 32 or 64

XA_CHUNK_SIZE is 32 or 64, and currently XAarray is 64 optimized,
so modifying it may have a counterproductive effect.

There is a downside to the well-designed XArray, but if the indexes
are not dense or deleted a lot, the memory of the slots in the xa_node
is increased and the search cost for logn increases at f (n) = O
(nlogn)

My worries are here and I hope you understand my efforts to solve it.

My attempts described below are meaningful when XA_CHUNK_SHIFT is 4 or
2, and can solve the slowdown in search speed when indexes are deleted
and not concentrated.

When XA_CHUNK_SHIFT is 2(XA_CHUNK_SIZE is 4), the XArray configuration
is as follows.
(It is difficult to express the picture in text.)

xarray->head : xa_node : index: 0  16  32  48
                +---+---+---+
                                |   |   |   |
        +-----------------------+   |   |   +------------+
        |              +------------+   |                |
        |              |                |                |
    0  4  8  12    16  20  24  28   32  36  40  44   48  52  56  60
    +--+--+---+    +---+---+---+    +---+---+---+    +---+---+---+
        |              |                |                |
  +-----+              |                +-------+        +---------------+
  |                    |                        |                        |
  0 1 2 3 <==>... <==> 16 17 18 19 <==>... <==> 32 33 34 35 <==>...
<==> 48 49 ..

In the above, if xa_node is connected to next and prev, it does not
search the parent node, so the logn disappears from f (n) = O (nlogn),
which improves search efficiency with f (n) = O (n). In fact, this is
already well-known in traditional algorithms, but I hope you can
understand it with the effort applied to XArray.

Best Regards,
JaeJoon Jung.

On Tue, 17 Mar 2020 at 22:40, Matthew Wilcox <willy@...radead.org> wrote:
>
> On Tue, Mar 17, 2020 at 04:32:34PM +0900, JaeJoon Jung wrote:
> > Hi Matthew,
> > I add next, prev pointer in the xa_node to improve search performance.
> > XArray currently has the following search capabilities:
> >
> > Search algorithm performance is O(n) = n x log(n)
>
> That's not how "big-O" notation is used.
> https://en.wikipedia.org/wiki/Big_O_notation
>
> What you mean to say here is O(n.log(n)).
>
> > For example,
> > XA_CHUNK_SHIFT 2
> > XA_CHUNK_SIZE 4
>
> I'm not really interested in the performance of a cut-down radix tree.
> You can re-run the numbers with a SHIFT of 6 and SIZE of 64 to get a
> more useful set of performance numbers.
>
> > If you connect the leaf node with the next and prev pointers as follows,
> > the search performance is improved to O (n) = n.
>
> But that's not free.  Right now, the xa_node is finely tuned in
> size to 576 bytes on 64-bit systems (32-bit systems are a secondary
> consideration).  That gets us 7 nodes per page.  Increasing the size any
> further reduces the number per page to 6, which is a pretty meaningful
> increase in memory usage.
>
> > @@ -1125,6 +1125,8 @@ struct xa_node {
> >         unsigned char   count;          /* Total entry count */
> >         unsigned char   nr_values;      /* Value entry count */
> >         struct xa_node __rcu *parent;   /* NULL at top of tree */
> > +        struct xa_node __rcu *prev;     /* previous node pointer */
> > +        struct xa_node __rcu *next;     /* next node pointer */
>
> You should be indenting with tabs, not spaces.  Or your mail system is
> messing with your patches.
>