diff -r 6621df29d406 user/test/ileaf.c
--- a/user/test/ileaf.c	Mon Sep 01 21:18:45 2008 -0700
+++ b/user/test/ileaf.c	Mon Sep 01 23:54:23 2008 -0700
@@ -299,6 +299,24 @@
 	attrs = ileaf_resize(btree, inum, leaf, size - less);
 }
 
+int isinorder(BTREE, struct ileaf *leaf)
+{
+	int offset = 0;
+	u16 *dict = (void *)leaf + btree->sb->blocksize;
+	int correct = 1;
+	for (int i = 0; i > -leaf->count; i--)
+	{
+		int limit = dict[i];
+		if (limit < offset)
+		{
+			correct = 0;
+			break;
+		}
+		offset = limit;
+	}
+	return correct;
+}
+
 block_t balloc(SB)
 {
 	return sb->nextalloc++;
@@ -317,17 +335,22 @@
 	test_append(btree, leaf, 0x13, 2, 'a');
 	test_append(btree, leaf, 0x14, 4, 'b');
 	test_append(btree, leaf, 0x16, 6, 'c');
+	assert(isinorder(btree, leaf));
 	ileaf_dump(btree, leaf);
 	ileaf_split(btree, 0x10, leaf, dest);
+	assert(isinorder(btree, leaf));
 	ileaf_dump(btree, leaf);
 	ileaf_dump(btree, dest);
 	ileaf_merge(btree, leaf, dest);
 	ileaf_dump(btree, leaf);
 	test_append(btree, leaf, 0x13, 3, 'x');
+	assert(isinorder(btree, leaf));
 	ileaf_dump(btree, leaf);
 	test_append(btree, leaf, 0x18, 3, 'y');
+	assert(isinorder(btree, leaf));
 	ileaf_dump(btree, leaf);
 	test_remove(btree, leaf, 0x16, 5);
+	assert(isinorder(btree, leaf));
 	ileaf_dump(btree, leaf);
 return 0;
 	unsigned size = 0;



_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]

This diff adds deferred rename.  Unlike the patch iterations before it, 
this one actually shrinks the code, because the directory sync handler 
does linking and unlinking for rename just like it does for other 
namespace operations.  All we have to do is set the BACKED and STALE 
flags on the dentries involved appropriately.

The position vacated by the moved dentry has to be filled in with a 
negative dentry to prevent the vfs from discovering the dirent still on 
the filesystem.  If the source dentry was BACKED or STALE (that is, an 
entry exists on disk) then the clone is marked STALE.  The source 
dentry is going to be d_moved to take the place of the target dentry,  
so if the target dentry is BACKED or STALE then the source dentry is 
marked STALE so that the existing target dirent will be removed.

This works pretty well with non-directories as far as I have tested it.  
If a directory is being moved, then I fail to update the directory's 
dotdot dirent, which is pretty easy to fix.  A much harder problem is 
knowing when a directory is empty.  Scanning through all the dirent 
blocks to find out, as Ext2 has traditionally done, gives an incorrect 
answer if some unlinks have been deferred.  For some strange reason, 
directory link count only includes subdirectories, not regular files or 
other kinds of entries, so that cannot be relied on.  I am not sure 
what the right thing to do here is.  At worst, a flush could be forced 
before deleting a directory, then the traditional check will work.  Or 
we can do a dcache lookup for each dirent still found in the directory 
(the cached_lookup function in namei.c does this, and could just be 
exported).

Anyway, the deferred namespace operations patch now goes on the back 
burner.  The effort so far has basically proven the idea, I think, and 
opens up a path to a powerful optimization we can do later.  Of course 
I am interested in comments, bugs, criticism, test reports or whatever 
on this patch, regardless, and probably ...
[ message continues ]

Your negative for loop is stylish.  Let's try crunching down the loop
body a little:

int isinorder(BTREE, struct ileaf *leaf)
{
	u16 *dict = (void *)leaf + btree->sb->blocksize;
	for (int i = 0, offset = 0, limit; i > -leaf->count; i--, offset = limit)
		if ((limit = dict[i]) < offset)
			return 0;
	return 1;
}

Wow, it compresses nicely :-)

It is still your nice clear and correct algorithm, just poked a little.
You can integrate it with the existing (lame) check like this:

int ileaf_check(BTREE, struct ileaf *leaf)
{
	char *why;
	why = "not an inode table leaf";
	if (leaf->magic != 0x90de)
		goto eek;
	why = "dict out of order";
	if (!isinorder(btree, leaf))
		goto eek;
	return 0;
eek:
	printf("%s!\n", why);
	return -1;
}

_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]

--nextPart7140683.zDLOMV79lj
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline



Sorry, didn't notice ileaf_check earlier. New patch coming up in a minute o=
r=20
two.

Regards,
--=20
Conrad Meyer <konrad@tylerc.org>

--nextPart7140683.zDLOMV79lj
Content-Type: application/pgp-signature; name=signature.asc 
Content-Description: This is a digitally signed message part.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iEYEABECAAYFAki9QWAACgkQFZSH7vtOfpSNuQCbBKceJVtEfmQgcRL4yhKAyjJH
h3IAnjMOwCNevsbai2iSEoeEaWMD38Dh
=RBt7
-----END PGP SIGNATURE-----

--nextPart7140683.zDLOMV79lj--


[ message continues ]

The diff improves deferred directory rename support by linking the
directory to its parent when the parent directory is flushed.  The
two missing pieces to finish deferred directory support are:

  * Detect empty directory for unlink
  * Deferred mkdir support

And that will complete all the deferred link, unlink and move
operations, I think.  To make it actually usable, some locking issues
should be cleaned up and waiting on directory flush added in a few
strategic places, the latter being something of a challenge in Ext2.
So I do not think this patch will ever actually be used in Ext2, but
it is close to being able to run well enough to measure the effect on
buffer namespace operation latency.

Regards,

Daniel
[ message continues ]

The adds deferred mkdir.  After the mkdir, "." and ".." have not been
assigned yet, until the parent directory is flushed.  So in a full
implementation, opening a directory that is still deferred should wait
for the parent directory to be flushed, in addition to waiting for the
directory itself to be flushed.

Regards,

Daniel
[ message continues ]

That's because it's counting the '..' links in the subdirectories.

Maciej

_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]

Duh, thanks  And does anything actually rely on this count being equal
to the number of subdirectories as opposed to being > greater than two
for a non-empty directory?

It would be a lot more useful to Tux3 as a directory in-use counter
than as a subdirectory counter.

Regards,

Daniel

_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]

I believe '/usr/bin/find' does use the link count for some
optimization (it assumes a directory has nlink-2 subdirectories, -2
since 1 for the link from parent to itself, and 1 for the '.'), but
should fall back to a less optimized mode if it sees a mismatch...

I've definitely seen it complain about mismatched link counts many
times before...

_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]

It can speed up some find operations quite a lot, when find doesn't
have to stat(2) all the entries in the leaf directories to know if it
needs to recurse deeper or not.

And it is sometimes used by users of find(1) too, to find leaf directories.
'find . -links 2' is the easiest way I know of for that.


	/Bellman

_______________________________________________
Tux3 mailing list
Tux3@tux3.org
http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3
[ message continues ]