xfs errors while unlinking filenames with hash collisions

* xfs errors while unlinking filenames with hash collisions
@ 2014-03-27  7:41 Hannes Frederic Sowa
  2014-03-27 13:14 ` Mark Tinguely
  2014-04-01 18:49 ` [PATCH xfstests] tests for file hash collisions on xfs filesystems Hannes Frederic Sowa
  0 siblings, 2 replies; 16+ messages in thread
From: Hannes Frederic Sowa @ 2014-03-27  7:41 UTC (permalink / raw)
  To: xfs

Hello!

I wanted to break some network stack hashing, but while running the test
against my local xfs filesystem I got corruptions in rmdir:

[ 3856.245843] XFS (vda1): Internal error xfs_trans_cancel at line 966 of file fs/xfs/xfs_trans.c.  Caller 0xffffffffa01186bc
[ 3856.249049] CPU: 1 PID: 866 Comm: rm Not tainted 3.13.6-200.fc20.x86_64 #1
[ 3856.250966] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011
[ 3856.252615]  000000000000000c ffff8800d23a7d68 ffffffff8168730c ffff8800cf5462b8
[ 3856.254823]  ffff8800d23a7d80 ffffffffa00d00cb ffffffffa01186bc ffff8800d23a7da8
[ 3856.257241]  ffffffffa00e5459 ffff8800d9ac3400 ffff8800d23a7e30 ffff8800371b6800
[ 3856.259420] Call Trace:
[ 3856.260172]  [<ffffffff8168730c>] dump_stack+0x45/0x56
[ 3856.261717]  [<ffffffffa00d00cb>] xfs_error_report+0x3b/0x40 [xfs]
[ 3856.263472]  [<ffffffffa01186bc>] ? xfs_remove+0x1ac/0x370 [xfs]
[ 3856.270838]  [<ffffffffa00e5459>] xfs_trans_cancel+0xd9/0x100 [xfs]
[ 3856.272783]  [<ffffffffa01186bc>] xfs_remove+0x1ac/0x370 [xfs]
[ 3856.274531]  [<ffffffffa00db40b>] xfs_vn_unlink+0x4b/0x90 [xfs]
[ 3856.276286]  [<ffffffff811c61b8>] vfs_rmdir+0xa8/0x100
[ 3856.277821]  [<ffffffff811c638d>] do_rmdir+0x17d/0x1d0
[ 3856.281021]  [<ffffffff811ba7fe>] ? ____fput+0xe/0x10
[ 3856.285261]  [<ffffffff8108c11c>] ? task_work_run+0xac/0xe0
[ 3856.286952]  [<ffffffff81013a31>] ? do_notify_resume+0x61/0xa0
[ 3856.288693]  [<ffffffff811c9a65>] SyS_unlinkat+0x25/0x40
[ 3856.290407]  [<ffffffff816962e9>] system_call_fastpath+0x16/0x1b
[ 3856.292685] XFS (vda1): xfs_do_force_shutdown(0x8) called from line 967 of file fs/xfs/xfs_trans.c.  Return address = 0xffffffffa00e5472
[ 3856.627330] XFS (vda1): Corruption of in-memory data detected.  Shutting down filesystem
[ 3856.627332] XFS (vda1): Please umount the filesystem and rectify the problem(s)

I also tested this on a current linux net-next kernel, which is 3.14.0-rc6.

If I run the test code below in an directory for a while and after that
try to unlink the files in it (rm -rf testdir), I get above splat. Even
after running xfs_repair I cannot remove the directory. The system is
pretty unusable after that if this is done on a root filesystem.

I quickly extracted this simple test case below. It does not generate
perfect collisions, but they are enough to trigger the above described
problem.

Thanks,

  Hannes

---- >8 ----
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdbool.h>
#include <unistd.h>
#include <err.h>
#include <string.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

static inline uint32_t rol32(uint32_t word, unsigned int shift)
{
	return (word << shift) | (word >> (32 - shift));
}

static uint32_t xfs_hash(const uint8_t *name, int namelen)
{
	uint32_t hash = 0;

	for (; namelen >= 4; namelen -= 4, name += 4)
		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^ (name[3] << 0) ^ rol32(hash, 7 * 4);

	if (namelen)
		abort();

	return hash;
}

static uint8_t gen_rand(void)
{
	uint8_t r;
	while (!(r = rand()));
	return r;
}

static uint8_t *round_one(uint8_t (*generator)())
{
	int idx;
	static uint8_t buffer[300] = {0};

	for (idx = 0; idx < 252-4; idx+=4) {
		buffer[idx + 0] = gen_rand();
		buffer[idx + 1] = gen_rand();
		buffer[idx + 2] = gen_rand();
		buffer[idx + 3] = gen_rand();
	}
	return buffer;
}

static uint8_t *round_two(uint8_t *buffer)
{
	static uint8_t a = 0, b = 0, c = 0;

	static const uint32_t target = ~0U;

	uint32_t hash = rol32(xfs_hash(buffer, 248), 7 * 4);

	a++, b++, c++;

	uint32_t last = hash ^ target;

	buffer[248] = (last >> 21) & 0xff;
	buffer[249] = (last >> 14) & 0xff;
	buffer[250] = (last >> 7) & 0xff;
	buffer[251] = last & 0xff;

	return buffer;
}

int main(int argc, char **argv)
{
	unsigned int cnt = 0;

	while (true)
		mkdir(round_two(round_one(gen_rand)), S_IRWXU);

	exploit();
}
--- >8 ----

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

^ permalink raw reply	[flat|nested] 16+ messages in thread