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

Message-Id: <2793AF96-98CE-4709-94EE-659D853267E4@code-trick.com>
Date:	Thu, 4 Oct 2012 22:28:33 +0800
From:	Zimilo <zimilo@...e-trick.com>
To:	Arne Jansen <sensille@....net>
Cc:	Zimilo <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

Detailed explanations for the patch:

     When the small inline cache is exhausted, created a new rbtree,

     and the new rbtree uses  original spaces the inline nodes placed for saving memory.

     By using the rbtree can gain a better performance when nnodes gets larger.

     
Sorry for I doest't did much more measurements, but the average lookup time increases slower then the original linear policy when nnodes goes larger.


For this is my first patch I submitted, I'm too excited to find something I can hack the kernel, however I didn't consider the whole thing.

I will continue to dive into the btrfs implementation, and work harder. 

:-)

- Rock

On 2012-10-4, at 下午5:44, Arne Jansen <sensille@....net> wrote:

> 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/







--
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/