From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753654AbdKXTsy (ORCPT ); Fri, 24 Nov 2017 14:48:54 -0500 Received: from mail-wr0-f180.google.com ([209.85.128.180]:40981 "EHLO mail-wr0-f180.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751024AbdKXTsw (ORCPT ); Fri, 24 Nov 2017 14:48:52 -0500 X-Google-Smtp-Source: AGs4zMa2VHPLNkOPU/RT2jeM+Mxq2BKhM7hL0v2kIAUTGsWRZFGVkx8Tq+fmNan9jvhlLS6gb+bv8lmqIb8jPqcJnM4= MIME-Version: 1.0 In-Reply-To: <2627399.jpLCoM7KBo@merkaba> References: <20171122210739.29916-1-willy@infradead.org> <3543098.x2GeNdvaH7@merkaba> <20171124170307.GA681@bombadil.infradead.org> <2627399.jpLCoM7KBo@merkaba> From: Shakeel Butt Date: Fri, 24 Nov 2017 11:48:49 -0800 Message-ID: Subject: Re: XArray documentation To: Martin Steigerwald Cc: Matthew Wilcox , linux-fsdevel@vger.kernel.org, Linux MM , LKML , Matthew Wilcox Content-Type: text/plain; charset="UTF-8" Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by nfs id vAOJmxXB009457 On Fri, Nov 24, 2017 at 10:01 AM, Martin Steigerwald wrote: > Hi Matthew. > > Matthew Wilcox - 24.11.17, 18:03: >> On Fri, Nov 24, 2017 at 05:50:41PM +0100, Martin Steigerwald wrote: >> > Matthew Wilcox - 24.11.17, 02:16: >> > > ====== >> > > XArray >> > > ====== >> > > >> > > Overview >> > > ======== >> > > >> > > The XArray is an array of ULONG_MAX entries. Each entry can be either >> > > a pointer, or an encoded value between 0 and LONG_MAX. It is efficient >> > > when the indices used are densely clustered; hashing the object and >> > > using the hash as the index will not perform well. A >> > > freshly-initialised >> > > XArray contains a NULL pointer at every index. There is no difference >> > > between an entry which has never been stored to and an entry which has >> > > most >> > > recently had NULL stored to it. >> > >> > I am no kernel developer (just provided a tiny bit of documentation a long >> > time ago)… but on reading into this, I missed: >> > >> > What is it about? And what is it used for? >> > >> > "Overview" appears to be already a description of the actual >> > implementation >> > specifics, instead of… well an overview. >> > >> > Of course, I am sure you all know what it is for… but someone who wants to >> > learn about the kernel is likely to be confused by such a start. > […] >> Thank you for your comment. I'm clearly too close to it because even >> after reading your useful critique, I'm not sure what to change. Please >> help me! > > And likely I am too far away to and do not understand enough of it to provide > more concrete suggestions, but let me try. (I do understand some programming > stuff like what an array is, what a pointer what an linked list or a tree is > or… so I am not completely novice here. I think the documentation should not > cover any of these basics.) > >> Maybe it's that I've described the abstraction as if it's the >> implementation and put too much detail into the overview. This might >> be clearer? >> >> The XArray is an abstract data type which behaves like an infinitely >> large array of pointers. The index into the array is an unsigned long. >> A freshly-initialised XArray contains a NULL pointer at every index. > > Yes, I think this is clearer already. > > Maybe with a few sentences on "Why does the kernel provide this?", "Where is > it used?" (if already known), "What use case is it suitable for – if I want to > implement something into the kernel (or in user space?) ?" and probably "How > does it differ from user data structures the kernel provides?" > Adding on to Martin's questions. Basically what is the motivation behind it? It seems like a replacement for radix tree, so, it would be good to write why radix tree was not good enough or which use cases radix tree could not solve. Also how XArray solves those issues/use-cases? And if you know which scenarios or use-cases where XArray will not be an optimal solution.