linux-kernel - Re: [PATCH] xarray: Document erasing entries during iteration

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

Date:   Wed, 13 Feb 2019 12:13:40 +1100
From:   "Tobin C. Harding" <me@...in.cc>
To:     "Tobin C. Harding" <tobin@...nel.org>
Cc:     Matthew Wilcox <willy@...radead.org>,
        linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] xarray: Document erasing entries during iteration

On Tue, Feb 12, 2019 at 06:29:58PM +1100, Tobin C. Harding wrote:
> The XArray is, in a way, a replacement data structure for linked lists,
> as such, on first use developers may wonder if it is safe to remove
> items while iterating over the array.
> 
> For example, this is fine:
> 
> 	DEFINE_XARRAY(things);
> 
> 	void cleanup()
> 	{
> 		struct thing *thing;
> 		unsigned long index;
> 
> 		xa_for_each(&things, index, thing)
> 			xa_erase(&things, index);
> 	}
> 
> Document this feature explicitly in the docs and also for the macro
> definition.
> 
> Signed-off-by: Tobin C. Harding <tobin@...nel.org>
> ---
> 
> Hi Willy,
> 
> I had my first go using the XArray today and during that I wondered if
> it was safe to remove items during iteration.  Conceptually it seems
> fine and it seemed to work just fine in code - is this something people
> should not be doing for any reason?  Is this the best way to traverse
> the tree and get every thing just to erase it?  Are we even supposed to
> be thinking this is a tree or should we just be thinking it is an array?
> 
> (As you might have guessed I _still_ don't know exactly how a radix tree
> works :)
> 
> Oh, and FTR the XArray is hot - good effort man.
> 
> thanks,
> Tobin.
> 
> 
>  Documentation/core-api/xarray.rst | 3 ++-
>  include/linux/xarray.h            | 2 ++
>  2 files changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
> index 5d54b27c6eba..2578e0bdaa17 100644
> --- a/Documentation/core-api/xarray.rst
> +++ b/Documentation/core-api/xarray.rst
> @@ -97,7 +97,8 @@ You can copy entries out of the XArray into a plain array by calling
>  :c:func:`xa_extract`.  Or you can iterate over the present entries in
>  the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
>  :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
> -entry in the XArray.
> +entry in the XArray.  It is safe to call :c:func:`xa_release` on entries
> +as you iterate over the array using :c:func:`xa_for_each`.

Re-reading documentation this line may be in the wrong place .

Perhaps it would be better added at the end of the 'Normal API' section?

	Finally, you can remove all entries from an XArray by calling
	:c:func:`xa_destroy`.  If the XArray entries are pointers, you may wish
	to free the entries first.  You can do this by iterating over all present
	entries in the XArray using the :c:func:`xa_for_each` iterator.  It is safe
	to call :c:func:`xa_erase` while iterating the array.

I'm a bit lazy when I read docs and soon as I find an answer I stop
reading (bad Tobin) so it might be nice to tie the first mention of
xa_for_each with the comment on xa_erase _and_ the section on
xa_destroy.  Man, writing docs is never as easy as it first appears.

Oh and I sent v2 already but it hasn't shown up in my inbox so replying
here on v1.

thanks,
Tobin.