linux-kernel - Re: Please pull IDR rewrite

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 for Android: free password hash cracker in your pocket

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

Date:   Tue, 28 Feb 2017 16:06:32 -0800
From:   Matthew Wilcox <willy@...radead.org>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: Please pull IDR rewrite

On Tue, Feb 28, 2017 at 03:38:09PM -0800, Linus Torvalds wrote:
> On Tue, Feb 28, 2017 at 1:11 PM, Matthew Wilcox <willy@...radead.org> wrote:
> >
> > The most significant part of the following is the patch to rewrite the
> > IDR & IDA to be clients of the radix tree.
> 
> Could you give a bit more details about what this rewrite brings with
> it, for the merge message and peoples edification?

Certainly!

The radix tree and the IDR use very similar data structures.  Merging the
two codebases lets us share the memory allocation pools, and results in
a net deletion of 500 lines of code.  It also opens up the possibility
of exposing more of the features of the radix tree to users of the IDR
(and I have some interesting patches along those lines waiting for 4.12).
It also shrinks the size of the 'struct idr' from 40 bytes to 24 which
will shrink a fair few data structures that embed an IDR.

 include/linux/idr.h        |  145 +++---
 include/linux/radix-tree.h |   49 +-
 lib/idr.c                  | 1175 +++++++++-----------------------------------
 lib/radix-tree.c           |  375 ++++++++++----
 4 files changed, 627 insertions(+), 1117 deletions(-)