[Ocfs2-devel] [PATCH 3/3] ocfs2/xattr: Proper hash collision handle in bucket division.v2
Joel Becker
Joel.Becker at oracle.com
Fri Oct 24 02:15:59 PDT 2008
On Fri, Oct 24, 2008 at 05:02:28PM +0800, Tao Ma wrote:
>
>
> Joel Becker wrote:
>> On Fri, Oct 24, 2008 at 12:43:53AM -0700, Joel Becker wrote:
>>> On Fri, Oct 24, 2008 at 02:15:35PM +0800, Tao Ma wrote:
>>>> Joel Becker wrote:
>>>>> I have an idea to do what you're doing, but cleaner. I'll look
>>>>> at cmp_xe and try again in the morning.
>>>> cool, so waiting for your perfect code. ;)
>>> Zing! You got me :-)
>> How's this (untested)?
>> /*
>> * If this ocfs2_xattr_header covers more than one hash value, find a
>> * place where the hash value changes. Try to find the most even split.
>> * The most common case is that all entries have different hash values,
>> * and the first check we make will find a place to split.
>> */
>> static int ocfs2_xattr_find_divide_pos(struct ocfs2_xattr_header *xh)
>> {
>> struct ocfs2_xattr_entry *entries = &xh->xh_entries;
>> int count = le16_to_cpu(xh->xh_count);
>> int delta, middle = count / 2;
>> /* * We start at the middle. Each step gets farther away in both
>> * directions. We therefore hit the change in hash value
>> * nearest to the middle. Note that this loop does not execute for
>> * count < 2.
>> */
>> for (delta = 0; delta < middle; delta++) {
>> /* Let's check delta earlier than middle */
>> if (!cmp_ex(&entries[middle - delta - 1], &entries[middle -
>> delta]))
>> return middle - delta;
>> /* For even counts, don't walk off the end */
>> if ((middle + delta + 1) == count)
>> continue;
>> /* Now try delta past middle */
>> if (!cmp_ex(&entries[middle + delta],
>> &entries[middle + delta + 1]))
>> return middle + delta + 1;
>> }
>> /* Every entry had the same hash */
>> return count;
>> }
> yeah, this looks perfect and more efficient.
> I will modify my patch and then test it.
Haha, it has a bug! Those cmp_ex() calls should not have the
'!' in front of them. We're looking for differences, not matches. Take
out those '!'s.
Joel (sorry about the bug)
--
"Every new beginning comes from some other beginning's end."
Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
More information about the Ocfs2-devel
mailing list