183230 – [ext2fs] ext2fs hash function incompatible with linux

Bug 183230 - [ext2fs] ext2fs hash function incompatible with linux

Summary: [ext2fs] ext2fs hash function incompatible with linux

Status:	Closed FIXED

Alias:	None

Product:	Base System
Classification:	Unclassified
Component:	kern (show other bugs)
Version:	Unspecified
Hardware:	Any Any

Importance:	Normal Affects Only Me
Assignee:	Pedro F. Giffuni

URL:
Keywords:

Depends on:
Blocks:

Reported:	2013-10-23 10:40 UTC by Grzegorz
Modified:	2013-12-26 01:20 UTC (History)
CC List:	0 users

See Also:

Attachments
patch-halfmd4.txt (355 bytes, patch) 2013-10-28 20:27 UTC, Pedro F. Giffuni	no flags	Details \| Diff
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.

Description Grzegorz 2013-10-23 10:40:05 UTC

Hi,


probably I found a bug. Half md4 hash output value is assigned to hash and hash_minor. Linux fsck reports problems (HTREE max value is wrong) on ext partition with a lot directory entries.

FreeBSD implementation:
http://fxr.watson.org/fxr/source/fs/ext2fs/ext2_hash.c?v=FREEBSD9#L242

Linux implementation:
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/fs/ext3/hash.c

Look EXT2_HTREE_HALF_MD4:

FreeBSD:
major = hash[0];
minor = hash[1];

Linux:
minor_hash = buf[2];
hash = buf[1];

Comment 1 Mark Linimon freebsd_committer

2013-10-27 22:11:01 UTC

Responsible Changed
From-To: freebsd-bugs->freebsd-fs

Over to maintainer(s).

Comment 2 Pedro F. Giffuni freebsd_committer

2013-10-28 18:34:51 UTC

Responsible Changed
From-To: freebsd-fs->pfg

I will take this one.

Comment 3 dfilter service freebsd_committer

2013-10-28 19:46:09 UTC

Author: pfg
Date: Mon Oct 28 19:46:01 2013
New Revision: 257267
URL: http://svnweb.freebsd.org/changeset/base/257267

Log:
  MFC	r255338:
  
  ext2fs: temporarily disable htree directory index.
  
  In addition to our implementation not having workarounds for hash
  collisions, it appears we also have a compatibility problem.
  
  For now disable the htree code until we are able to re-examine
  both issues.
  
  PR:	kern/183230

Modified:
  stable/9/sys/fs/ext2fs/ext2_htree.c
  stable/9/sys/fs/ext2fs/ext2_lookup.c
Directory Properties:
  stable/9/sys/   (props changed)
  stable/9/sys/fs/   (props changed)

Modified: stable/9/sys/fs/ext2fs/ext2_htree.c
==============================================================================
--- stable/9/sys/fs/ext2fs/ext2_htree.c	Mon Oct 28 19:30:09 2013	(r257266)
+++ stable/9/sys/fs/ext2fs/ext2_htree.c	Mon Oct 28 19:46:01 2013	(r257267)
@@ -89,10 +89,12 @@ static int	ext2_htree_writebuf(struct ex
 int
 ext2_htree_has_idx(struct inode *ip)
 {
+#ifdef EXT2FS_HTREE
 	if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
 	    ip->i_flags & EXT4_INDEX)
 		return (1);
 	else
+#endif
 		return (0);
 }
 

Modified: stable/9/sys/fs/ext2fs/ext2_lookup.c
==============================================================================
--- stable/9/sys/fs/ext2fs/ext2_lookup.c	Mon Oct 28 19:30:09 2013	(r257266)
+++ stable/9/sys/fs/ext2fs/ext2_lookup.c	Mon Oct 28 19:46:01 2013	(r257267)
@@ -884,6 +884,7 @@ ext2_direnter(struct inode *ip, struct v
 	bcopy(cnp->cn_nameptr, newdir.e2d_name, (unsigned)cnp->cn_namelen + 1);
 	newentrysize = EXT2_DIR_REC_LEN(newdir.e2d_namlen);
 
+#ifdef EXT2FS_HTREE
 	if (ext2_htree_has_idx(dp)) {
 		error = ext2_htree_add_entry(dvp, &newdir, cnp);
 		if (error) {
@@ -904,6 +905,7 @@ ext2_direnter(struct inode *ip, struct v
 			return ext2_htree_create_index(dvp, cnp, &newdir);
 		}
 	}
+#endif	/* EXT2FS_HTREE */
 
 	if (dp->i_count == 0) {
 		/*
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscribe@freebsd.org"

Comment 4 Pedro F. Giffuni freebsd_committer

2013-10-28 20:27:35 UTC

Oops, I meant this.

Comment 5 dfilter service freebsd_committer

2013-12-23 19:47:42 UTC

Author: pfg
Date: Mon Dec 23 19:47:34 2013
New Revision: 259780
URL: http://svnweb.freebsd.org/changeset/base/259780

Log:
  ext2fs: make the hashing algorithm match the linux code.
  
  There appears to be a hash function compatibility issue.
  The code is currently disabled but fix it nevertheless.
  
  PR:		kern/183230
  MFC after:	3 days

Modified:
  head/sys/fs/ext2fs/ext2_hash.c

Modified: head/sys/fs/ext2fs/ext2_hash.c
==============================================================================
--- head/sys/fs/ext2fs/ext2_hash.c	Mon Dec 23 19:29:07 2013	(r259779)
+++ head/sys/fs/ext2fs/ext2_hash.c	Mon Dec 23 19:47:34 2013	(r259780)
@@ -289,8 +289,8 @@ ext2_htree_hash(const char *name, int le
 			len -= 32;
 			name += 32;
 		}
-		major = hash[0];
-		minor = hash[1];
+		major = hash[1];
+		minor = hash[2];
 		break;
 	default:
 		goto error;
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscribe@freebsd.org"

Comment 6 dfilter service freebsd_committer

2013-12-26 01:11:59 UTC

Author: pfg
Date: Thu Dec 26 01:11:51 2013
New Revision: 259903
URL: http://svnweb.freebsd.org/changeset/base/259903

Log:
  MFC	r252397, r258904, r259780:
  Small ext2fs updates.
  
  Use the unsigned random() range in i_gen.
  Add two new reserved inodes.
  Make the hashing algorithm match the linux code.
  
  PR:		kern/183230

Modified:
  stable/9/sys/fs/ext2fs/ext2_dinode.h
  stable/9/sys/fs/ext2fs/ext2_hash.c
  stable/9/sys/fs/ext2fs/ext2_vfsops.c
Directory Properties:
  stable/9/sys/   (props changed)
  stable/9/sys/fs/   (props changed)

Modified: stable/9/sys/fs/ext2fs/ext2_dinode.h
==============================================================================
--- stable/9/sys/fs/ext2fs/ext2_dinode.h	Thu Dec 26 00:11:19 2013	(r259902)
+++ stable/9/sys/fs/ext2fs/ext2_dinode.h	Thu Dec 26 01:11:51 2013	(r259903)
@@ -44,6 +44,8 @@
 #define	EXT2_UNDELDIRINO	((ino_t)6)
 #define	EXT2_RESIZEINO		((ino_t)7)
 #define	EXT2_JOURNALINO		((ino_t)8)
+#define	EXT2_EXCLUDEINO		((ino_t)9)
+#define	EXT2_REPLICAINO		((ino_t)10)
 #define	EXT2_FIRSTINO		((ino_t)11)
 
 /*

Modified: stable/9/sys/fs/ext2fs/ext2_hash.c
==============================================================================
--- stable/9/sys/fs/ext2fs/ext2_hash.c	Thu Dec 26 00:11:19 2013	(r259902)
+++ stable/9/sys/fs/ext2fs/ext2_hash.c	Thu Dec 26 01:11:51 2013	(r259903)
@@ -289,8 +289,8 @@ ext2_htree_hash(const char *name, int le
 			len -= 32;
 			name += 32;
 		}
-		major = hash[0];
-		minor = hash[1];
+		major = hash[1];
+		minor = hash[2];
 		break;
 	default:
 		goto error;

Modified: stable/9/sys/fs/ext2fs/ext2_vfsops.c
==============================================================================
--- stable/9/sys/fs/ext2fs/ext2_vfsops.c	Thu Dec 26 00:11:19 2013	(r259902)
+++ stable/9/sys/fs/ext2fs/ext2_vfsops.c	Thu Dec 26 01:11:51 2013	(r259903)
@@ -1006,7 +1006,7 @@ ext2_vget(struct mount *mp, ino_t ino, i
 	 * already have one. This should only happen on old filesystems.
 	 */
 	if (ip->i_gen == 0) {
-		ip->i_gen = random() / 2 + 1;
+		ip->i_gen = random() + 1;
 		if ((vp->v_mount->mnt_flag & MNT_RDONLY) == 0)
 			ip->i_flag |= IN_MODIFIED;
 	}
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscribe@freebsd.org"

Comment 7 dfilter service freebsd_committer

2013-12-26 01:12:43 UTC

Author: pfg
Date: Thu Dec 26 01:12:35 2013
New Revision: 259904
URL: http://svnweb.freebsd.org/changeset/base/259904

Log:
  MFC	r258904, r259780:
  Small ext2fs updates.
  
  Add two new reserved inodes.
  Make the hashing algorithm match the linux code.
  
  PR:		kern/183230

Modified:
  stable/10/sys/fs/ext2fs/ext2_dinode.h
  stable/10/sys/fs/ext2fs/ext2_hash.c

Modified: stable/10/sys/fs/ext2fs/ext2_dinode.h
==============================================================================
--- stable/10/sys/fs/ext2fs/ext2_dinode.h	Thu Dec 26 01:11:51 2013	(r259903)
+++ stable/10/sys/fs/ext2fs/ext2_dinode.h	Thu Dec 26 01:12:35 2013	(r259904)
@@ -44,6 +44,8 @@
 #define	EXT2_UNDELDIRINO	((ino_t)6)
 #define	EXT2_RESIZEINO		((ino_t)7)
 #define	EXT2_JOURNALINO		((ino_t)8)
+#define	EXT2_EXCLUDEINO		((ino_t)9)
+#define	EXT2_REPLICAINO		((ino_t)10)
 #define	EXT2_FIRSTINO		((ino_t)11)
 
 /*

Modified: stable/10/sys/fs/ext2fs/ext2_hash.c
==============================================================================
--- stable/10/sys/fs/ext2fs/ext2_hash.c	Thu Dec 26 01:11:51 2013	(r259903)
+++ stable/10/sys/fs/ext2fs/ext2_hash.c	Thu Dec 26 01:12:35 2013	(r259904)
@@ -289,8 +289,8 @@ ext2_htree_hash(const char *name, int le
 			len -= 32;
 			name += 32;
 		}
-		major = hash[0];
-		minor = hash[1];
+		major = hash[1];
+		minor = hash[2];
 		break;
 	default:
 		goto error;
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscribe@freebsd.org"

Comment 8 Pedro F. Giffuni freebsd_committer

2013-12-26 01:15:01 UTC

State Changed
From-To: open->closed

Fix commited and MFC. 
Thank you for taking a look at the code!