[Ocfs2-devel] [PATCH 3/3] ocfs2/xattr: Proper hash collision handle in bucket division.v2

[Tao Ma]

Joel Becker wrote:
> On Fri, Oct 24, 2008 at 08:52:33AM +0800, Tao Ma wrote:
>> Joel Becker wrote:
>>> 	Do we really need such a complex function?  Some of your
>>> bailouts don't even help much.  I *think* what you are doing here is
>>> trying to find the hash value change closest to the middle.
>>> Also, you don't need to pass around u16s.  It just makes the code
>>> more complex.
>>> 	What about:
>>>
>>> /* In an ocfs2_xattr_header, are the hashes of entries n and n+1 equal?. */
>>> static inline int xe_cmp(struct ocfs2_xattr_entry *entres, int n)
>>> {
>>> 	return le32_to_cpu(entries[n].xe_name_hash) ==
>>> 		le32_to_cpu(entries[n + 1].xe_name_hash);
>>> }
> 
> <snip>
> 
>> Don't agree. Actually in most cases we won't be so lucky to hit this  
>> situation(I run the test scripts many times and hit one), so I think  
>> most times we will just return "middle" and my function go out  
>> immediately, it is O(1). You function suppose that the hash collision  
>> happens frequently and iterate the half of the xh_entries so it is O(n).
> 
> 	Are you saying that you usually have only one xattr per bucket,
> even with many xattrs?  Because if we have n xattrs per bucket, your
> function will walk down from middle to 0 (half the bucket) unless n is
> 1.
No. See ocfs2_xattr_find_divide_pos.
+	/*
+	 * Find a xe before middle which doesn't have the same hash alue
+	 * with the previous one.
+	 */
+	pos = middle;
+	while (pos > 0) {
+		xe = &xh->xh_entries[pos];
+		xe_low = &xh->xh_entries[pos - 1];
+		if (le32_to_cpu(xe_low->xe_name_hash) !=
+		    le32_to_cpu(xe->xe_name_hash))
+			return pos;
+
+		pos--;
+	}
In most cases, it will return 'pos' immediately since the hash value 
isn't the same.

> 	Your function would be much more understandable even if it just
> used my xe_cmp() function.  Then some comment about what you are trying
> to achieve (I guessed at that), and perhaps a mention of the common
> case.
OK, I will add some comments for it. As for xe_cmp, can I use "cmp_xe" 
which already exists in xattr.c?

Regards,
Tao