Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752248AbcLFUpw (ORCPT ); Tue, 6 Dec 2016 15:45:52 -0500 Received: from mail.linuxfoundation.org ([140.211.169.12]:36090 "EHLO mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751427AbcLFUpT (ORCPT ); Tue, 6 Dec 2016 15:45:19 -0500 Date: Tue, 6 Dec 2016 12:44:53 -0800 From: Andrew Morton To: Matthew Wilcox Cc: linux-kernel@vger.kernel.org, Konstantin Khlebnikov , Ross Zwisler , Matthew Wilcox , linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, "Kirill A . Shutemov" , Matthew Wilcox Subject: Re: [PATCH v3 33/33] Reimplement IDR and IDA using the radix tree Message-Id: <20161206124453.3d3ce26a1526fedd70988ab8@linux-foundation.org> In-Reply-To: <1480369871-5271-34-git-send-email-mawilcox@linuxonhyperv.com> References: <1480369871-5271-1-git-send-email-mawilcox@linuxonhyperv.com> <1480369871-5271-34-git-send-email-mawilcox@linuxonhyperv.com> X-Mailer: Sylpheed 3.4.1 (GTK+ 2.24.23; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1463 Lines: 39 On Mon, 28 Nov 2016 13:50:37 -0800 Matthew Wilcox wrote: > The IDR is very similar to the radix tree. It has some functionality > that the radix tree did not have (alloc next free, cyclic allocation, > a callback-based for_each, destroy tree), which is readily implementable > on top of the radix tree. A few small changes were needed in order to > use a tag to represent nodes with free space below them. > > The IDA is reimplemented as a client of the newly enhanced radix tree. > As in the current implementation, it uses a bitmap at the last level of > the tree. > > Signed-off-by: Matthew Wilcox > --- > include/linux/idr.h | 132 ++-- > include/linux/radix-tree.h | 5 +- > init/main.c | 3 +- > lib/idr.c | 1078 ------------------------------- > lib/radix-tree.c | 632 ++++++++++++++++-- hm. It's just a cosmetic issue, but perhaps the idr wrappers-around-radix-tree code should be in a different .c file. Before: akpm3:/usr/src/25> size lib/idr.o lib/radix-tree.o text data bss dec hex filename 6566 89 16 6671 1a0f lib/idr.o 11811 117 8 11936 2ea0 lib/radix-tree.o After: text data bss dec hex filename 14151 118 8 14277 37c5 lib/radix-tree.o So 4500 bytes saved. Decent.