linux-kernel - Re: [PATCH] btrfs ulist use rbtree instead

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

Date:	Thu, 04 Oct 2012 11:44:00 +0200
From:	Arne Jansen <sensille@....net>
To:	Rock Lee <zimilo@...e-trick.com>, chris.mason@...ionio.com,
	linux-btrfs@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] btrfs ulist use rbtree instead

On 04.10.2012 11:26, David Sterba wrote:
>> @@ -207,16 +266,23 @@ EXPORT_SYMBOL(ulist_add);
>>   * end is reached. No guarantee is made with respect to the order in which
>>   * the elements are returned. They might neither be returned in order of
>>   * addition nor in ascending order.
>> - * It is allowed to call ulist_add during an enumeration. Newly added items
>> - * are guaranteed to show up in the running enumeration.
>>   */
>>  struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
> 
> Quick observation:
> 
> If there's code relying on the behaviour stated in the removed part of
> the comment, it will break. Have you verified this is not the case?

It's a good thing to use rb-trees when the small inline cache is exhausted,
but of course it should keep the semantics. We heavily rely on the removed
part.
It should be possible to keep the semantics if the elements are also kept
in a linked list. As it inflates the size of struct ulist_node even more,
it might make sense to use a smaller struct for the inline cache to keep
the footprint low.

Also, a commit message might be good that explains the motivation for the
change. Have you done any measurements?

Thanks for working on this.

-Arne

> 
> 
> david
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@...r.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/