we have got hash function screwed up

we have got hash function screwed up

[Gabor HALASZ]

Hi!

I got the next message:

Sep  5 17:48:32 sk8n kernel: ReiserFS: dm-10: warning: 
reiserfs_add_entry: Congratulations! we have got hash function screwed up

Caused by:

17:47:43 Getting file 
'main/x/xorg-x11/xserver-xorg-dbg_6.8.2.dfsg.1-6_i386.deb' size = 21256772
17:48:32 Transfer rate:   423.79 kb/sec lastfile,    293.55 kb/sec overall
17:48:32 -- ERROR -- Creating temp file 
'main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb' : Device or 
resource busy
17:48:32 Retrieving file failed. Exiting.

The strange magic:

root@sk8n:~# touch 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dea
root@sk8n:~# touch 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
touch: cannot touch 
`/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb': 
Device or resource busy
root@sk8n:~# touch 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dec
root@sk8n:~# touch 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.ded
root@sk8n:~# touch 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dee

root@sk8n:~# ls -la /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.*
-rw-r--r--  1 root root 0 2005-09-05 18:26 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dea
-rw-r--r--  1 root root 0 2005-09-05 18:26 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dec
-rw-r--r--  1 root root 0 2005-09-05 18:26 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.ded
-rw-r--r--  1 root root 0 2005-09-05 18:26 
/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dee

and I found same message in the kernel log:

Sep  5 18:26:38 sk8n kernel: ReiserFS: dm-10: warning: 
reiserfs_add_entry: Congratulations! we have got hash function screwed up

The filsystem was clear at the last mount:

Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: found reiserfs format 
"3.6" with standard journal
Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: using ordered data mode
Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: journal params: device 
dm-10, size 8192, journal first block 18, max trans len 1024, max batch 
900, max commit age 30, max trans age 30
Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: checking transaction log 
(dm-10)
Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: Using rupasov hash to sort 
names


The system is x86-64 (Opteron), Debian Sid from amd64.debian.net, 2.6.13 
kernel, but same with 2.6.12.5.

What can I do?!

-- 
Gabor HALASZ <halasz.g@freemail.hu>

Re: we have got hash function screwed up

[michael chang]

On 9/5/05, Gabor HALASZ <halasz.g@freemail.hu> wrote:

> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
> touch: cannot touch
> `/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
> Device or resource busy

> What can I do?!

What happens when you try again after rebooting?

Also, how much disk space free?

Check output of "mount" or "/proc/mtab" also maybe...

-- 
~Mike
 - Just my two cents
 - No man is an island, and no man is unable.

Re: we have got hash function screwed up

[Konstantin Münning]

Hi!

Gabor HALASZ wrote:

> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
> 
> touch: cannot touch
> `/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
> Device or resource busy

Errors like these I've seen mostly with corrupted FS. Umount the
partition (reboot from some live-CD if it's your root partition) and do
an fsck.reiserfs /dev/xxx. I'm quite sure it will find something.

Before trying repairs check if your disk is operational (at least
badblocks -s /dev/xxx) as otherwise things can get worse. And don't
forget to backup as much of your important data as possible - it is very
likely but there's no guarantee that it will survive a repair.

If fsck don't show anything then someone better informed should help you.

Have luck,
Konstantin

Re: we have got hash function screwed up

[Vladimir V. Saveliev]

Hello

michael chang wrote:
> On 9/5/05, Gabor HALASZ <halasz.g@freemail.hu> wrote:
> 
>>root@sk8n:~# touch
>>/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
>>touch: cannot touch
>>`/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
>>Device or resource busy
> 
>>What can I do?!
> 

Can you send output of ls /home/ftpd/pub/debian/pool/main/x/xorg-x11/ ?
You should be able to create this file in other directory. Or create file with other name in that directory.

Re: we have got hash function screwed up

[Nikita Danilov]

[-- Attachment #1: message body text --]
[-- Type: text/plain, Size: 1812 bytes --]

Gabor HALASZ writes:
 > Hi!
 > 
 > I got the next message:
 > 
 > Sep  5 17:48:32 sk8n kernel: ReiserFS: dm-10: warning: 
 > reiserfs_add_entry: Congratulations! we have got hash function screwed up

reiserfs v3 uses a hash of the file name as a part of a tree key to
store directory entry for that name. To handle "hash collisions" i.e.,
situations when different names have the same hash "generation counter"
is appended to the hash to make the key unique. As generation counter is
8 bits, reiserfs handles up to 255 file names with the same hash value
in the same directory.

When generation counter "overflows" there is no way to generate unique
key and reiserfs refuses to create new file with (somewhat arbitrary)
-EBUSY error. This is usually rather hard to trigger (hence
"congratulations" bit): with the default r5 hash it takes about 1.5M
random file names to start getting generation counter overflowing.

It seems that in your case ".in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb"
file name falls into already full hash bin. Depending on what you are
doing you might try one of the following:

 - find other files in that bin and remove or rename some of them. That
 would allow ".in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb" to be created,
 but the problem might recur in the future;

 - re-create file system with the tea hash. That hash permutes bits
 thoroughly and it's much harder (albeit still possible) to get -EBUSY
 with it. Note however, that due to that randomization, directory
 operations are usually slower with the tea hash.

I am attaching simple program to calculate hashes. Build it and use as

ls -A /home/ftpd/pub/debian/pool/main/x/xorg-x11/ |\
        /path-to/r5 r5 | <...some uniq/awk/perl/sh glue to find duplicates...>

 > 
 > -- 
 > Gabor HALASZ <halasz.g@freemail.hu>
 > 

Nikita.

[-- Attachment #2: r5.c --]
[-- Type: text/plain, Size: 4793 bytes --]

#include <stdio.h>
#include <stdlib.h>

unsigned long r5e_hash (const char *s)
{
  unsigned int h=0;
  while (*s) {
    h += *s++ + h<<3 + h<<1;
    h <<= 3;
  }
  return h;
}

unsigned long r5l_hash( const char *msg )
{
    unsigned long a = 0;

    for( ; *msg ; ++msg ) 
	  { 
		a *= 11;
		a += *msg << 4;
		a += *msg >> 4;
	  }
    return a;
}

unsigned long r5_hash (const char *msg)
{
  unsigned long a = 0;

  for( ; *msg ; ++msg ) {
    a += *msg << 4;
    a += *msg >> 4;
    a *= 11;
   } 
  return a;
}

unsigned long r5mod_hash( const char *msg )
{
    unsigned long a = 0;

    for( ; *msg ; ++msg ) 
	  { 
		a *= 11;
		if( a == 0 )
		  {
			a += 0xacc01ade;
		  }
		a += *msg << 4;
		a += *msg >> 4;
	  }
    return a;
}

unsigned long r5ul_hash( const char *smsg )
{
  const unsigned char *msg = ( const unsigned char * )smsg;
  unsigned long a = 0;

  for( ; *msg ; ++msg ) {
    a += ( ( unsigned long )*msg ) << 4;
	a += ( ( unsigned long )*msg ) >> 4;
    a *= 11;
   } 
  return a;
}

unsigned short swab( unsigned short word )
{
  return ( word << 8 ) | ( word >> 8 );
}

unsigned long r5xxx_hash( const char *msg )
{
  unsigned long a;

  for( a = 0 ; *msg ; ++msg ) 
	{
	  a *= 11;
	  a += a % 0x7ffffff;
	  a += ( *msg << 4 ) + ( *msg >> 4 );
	}
  return a;
}

unsigned long fnv_1_hash( const char *smsg )
{
  unsigned long a = 0x811c9dc5;
  const unsigned long fnv_32_prime = 0x01000193;
  unsigned char *msg = ( unsigned char * )smsg;

  /*
   * FNV-1 hash each octet in the buffer
   */
  for( ; *msg ; ++msg ) 
	{

	  /* multiply by the 32 bit FNV magic prime mod 2^64 */
	  a *= fnv_32_prime;

	  /* xor the bottom with the current octet */
	  a ^= ( unsigned long ) ( *msg );
    }

    /* return our new hash value */
    return a;
}

unsigned long fnv_1_64_hash( const char *mes )
{
	unsigned long long a = 0xcbf29ce484222325ull;
	const unsigned long long fnv_64_prime = 0x100000001b3ull;
	const unsigned char *name;

	name = mes;
	/* FNV-1 hash each octet in the buffer */
	for( ; *name ; ++name ) {
		/* multiply by the 32 bit FNV magic prime mod 2^64 */
		a *= fnv_64_prime;
		/* xor the bottom with the current octet */
		a ^= ( unsigned long long ) ( *name );
	}
	/* return our new hash value */
	return a;
}

/*
 * XFS hash: fs/xfs/xfs_da_btree.c:xfs_da_hashname()
 *
 * Implement a simple hash on a character string.
 * Rotate the hash value by 7 bits, then XOR each character in.
 * This is implemented with some source-level loop unrolling.
 */
unsigned long xfs_da_hash( const char *mes )
{
  const unsigned char *name;
  int namelen;
  unsigned long hash;

  name = ( const unsigned char * ) mes;
  namelen = strlen( mes );

#define ROTL(x,y)	(((x) << (y)) | ((x) >> (32 - (y))))
#ifdef SLOWVERSION
	/*
	 * This is the old one-byte-at-a-time version.
	 */
	for (hash = 0; namelen > 0; namelen--) {
		hash = *name++ ^ ROTL(hash, 7);
	}
	return(hash);
#else
	/*
	 * Do four characters at a time as long as we can.
	 */
	for (hash = 0; namelen >= 4; namelen -= 4, name += 4) {
		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
		       (name[3] << 0) ^ ROTL(hash, 7 * 4);
	}
	/*
	 * Now do the rest of the characters.
	 */
	switch (namelen) {
	case 3:
		return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
		       ROTL(hash, 7 * 3);
	case 2:
		return (name[0] << 7) ^ (name[1] << 0) ^ ROTL(hash, 7 * 2);
	case 1:
		return (name[0] << 0) ^ ROTL(hash, 7 * 1);
	case 0:
		return hash;
	}
	/* NOTREACHED */
#endif
#undef ROTL
	return 0; /* keep gcc happy */
}

#define HASH( h ) { .name = #h, .hash = h ## _hash }
struct 
{
  const char *name;
  unsigned long ( *hash )( const char * );
} hashes [] = {
  HASH( r5 ),
  HASH( r5l ),
  HASH( r5mod ),
  HASH( r5xxx ),
  HASH( r5ul ),
  HASH( r5e ),
  HASH( fnv_1 ),
  HASH( fnv_1_64 ),
  HASH( xfs_da ),
  { .name = NULL, .hash = NULL }
};

static void usage( const char *pname )
{
  int i;

  fprintf( stderr, "%s %s", pname, hashes[ 0 ].name );
  for( i = 1 ; hashes[ i ].name != NULL ; ++ i ) 
	{
	  fprintf( stderr, "|%s", hashes[ i ].name );
	}
  fprintf( stderr, "\n" );
}

int main( int argc, char **argv )
{
  unsigned long ( *hash )( const char *name );
  int i;
  char fname[ 10000 ];

  if( argc > 1 )
	{
	  hash = NULL;
	  for( i = 0 ; hashes[ i ].name != NULL ; ++ i ) 
		{
		  if( !strcmp( argv[ 1 ], hashes[ i ].name ) )
			{
			  hash = hashes[ i ].hash;
			}
		}
	  if( hash == NULL )
		{
		  fprintf( stderr, "unknown hash: %s", argv[ 1 ] );
		  usage( argv[ 0 ] );
		}
	  else if( argc > 2 )
		{
		  for( i = 2 ; i < argc ; ++i )
			{
			  printf( "%lx\t%s\n", hash( argv[ i ] ), argv[ i ] );
			}
		}
	  else
		{
		  while( gets( fname ) )
			{
			  printf( "%lx\t%s\n", hash( fname ), fname );
			}
		}
	}
  else
	{
	  usage( argv[ 0 ] );
	}
  return EXIT_SUCCESS;
}

Re: we have got hash function screwed up

[Vladimir V. Saveliev]

[-- Attachment #1: Type: text/plain, Size: 1642 bytes --]

Hello

Gabor HALASZ wrote:
> Vladimir V. Saveliev wrote:
>> Hello
>>
>> michael chang wrote:
>>
>>> On 9/5/05, Gabor HALASZ <halasz.g@freemail.hu> wrote:
>>>
>>>
>>>> root@sk8n:~# touch
>>>> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
>>>>
>>>> touch: cannot touch
>>>> `/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
>>>>
>>>> Device or resource busy
>>>
>>>> What can I do?!
>>>
>>
>> Can you send output of ls /home/ftpd/pub/debian/pool/main/x/xorg-x11/ ?
> 
> It's really required?! Contains only 156 .deb files, mirrored from
> de.debian.org.
> 

Yes. It looks like something is wrong in that directory. Would you please run the attached program:
readdir /home/ftpd/pub/debian/pool/main/x/xorg-x11/ and send the output?


>> You should be able to create this file in other directory.
> 
> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
> 
> touch: cannot touch
> `/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
> Device or resource busy
> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
> 
> 
>> Or create file with other name in that directory.
> 
> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb
> 
> touch: cannot touch
> `/home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.deb':
> Device or resource busy
> root@sk8n:~# touch
> /home/ftpd/pub/debian/pool/main/x/xorg-x11/.in.xserver-xorg_6.8.2.dfsg.1-6_i386.dec
> 
> 
> 


[-- Attachment #2: readdir.c --]
[-- Type: text/x-c, Size: 476 bytes --]

#include <stdio.h>
#include <dirent.h>

int main(int argc, char **argv)
{
	DIR *dp;
	struct dirent *ep;
	int nr;

	if (argc != 2) {
		printf("usage: %s dirname\n", argv[0]);
		return 0;
	}
	dp = opendir (argv[1]);
	if (dp == NULL) {
		perror("openfailed");
		return 0;
	}
	nr = 0;
	while ((ep = readdir(dp))) {
		printf("\"%s\", len %d, off %ld\n",
		       ep->d_name, ep->d_reclen, ep->d_off);
		nr ++;
	}
	closedir(dp);

	printf("%d entried are read\n", nr);
	return 0;
}

Re: we have got hash function screwed up

[evilninja]

Gabor HALASZ schrieb:
> Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: checking transaction log
> (dm-10)
> Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: Using rupasov hash to sort
> names

why did you choose the rupasov hash?
http://www.namesys.com/mount-options.html knows:

rupasov: [...] Never use it, as it has high probability of hash
         collisions.

-- 
BOFH excuse #234:

Someone is broadcasting pygmy packets and the router doesn't know how to
deal with them.

Re: we have got hash function screwed up

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 868 bytes --]

On Sat, 10 Sep 2005 17:36:49 +0200, evilninja said:
> Gabor HALASZ schrieb:
> > Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: checking transaction log (dm-10)
> > Sep  5 12:30:24 sk8n kernel: ReiserFS: dm-10: Using rupasov hash to sort names
> 
> why did you choose the rupasov hash?
> http://www.namesys.com/mount-options.html knows:
> 
> rupasov: [...] Never use it, as it has high probability of hash
>          collisions.

Why is it selectable then?

Yes, I know there's needs to support borked legacy filesystems that were mkfs'ed
before the problem was recognized.  That means fsck.reiserfs needs to know about
it - but mkfs.reiserfs??  Seen in the Fedora Core devel tree as of tonight:

% rpm -q reiserfs-utils
reiserfs-utils-3.6.19-2
% strings /sbin/mkfs.reiserfs  | grep -i rupasov
rupasov
  -h | --hash rupasov|tea|r5       hash function to use by default


[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: we have got hash function screwed up

[evilninja]

Valdis.Kletnieks@vt.edu schrieb:
> Yes, I know there's needs to support borked legacy filesystems that were mkfs'ed
> before the problem was recognized.  That means fsck.reiserfs needs to know about
> it - but mkfs.reiserfs??  Seen in the Fedora Core devel tree as of tonight:

yeah, this "feature" of mkfs.reiserfs could be removed, but since reiserfs
is in bugfixes-only-mode i don't see it happen.

i am really curious though, why the OP used rupasov hash at all. r5 is the
default algorithm for years now.

-- 
BOFH excuse #80:

That's a great computer you have there; have you considered how it would
work as a BSD machine?

Re: we have got hash function screwed up

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 541 bytes --]

On Mon, 12 Sep 2005 00:49:54 +0200, evilninja said:
> Valdis.Kletnieks@vt.edu schrieb:
> > Yes, I know there's needs to support borked legacy filesystems that were mkfs'ed
> > before the problem was recognized.  That means fsck.reiserfs needs to know about
> > it - but mkfs.reiserfs??  Seen in the Fedora Core devel tree as of tonight:
> 
> yeah, this "feature" of mkfs.reiserfs could be removed, but since reiserfs
> is in bugfixes-only-mode i don't see it happen.

I'd consider a #if 0/#endif to remove known busticated code a bugfix. ;)

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]