Tux3 command interpreter

Tux3 now has a command interpreter to aid in debugging, with commands
like:

   tux3 make foodev

that makes a filesystem on device foodev, which can also be a file.  It
normally is a file for me and I make it sparse like this:

   dd if=/dev/zero of=foodev bs=1 count=1 seek=100K

I can see how many blocks tux3 actually used in it by:

   du foodev

less the few blocks that the sparse file has for metatdata and the
little blob of data at the end that dd puts there.  (I don't know how
to make dd truncate without writing, I am not sure it is possible.)

Then:

   echo "hello world!" | tux3 write foodev foo

creates and writes to file foo in foodev.  A subsequent write will
fail with EEXIST, which is maybe not quite what we want.

Finally:

  tux3 read foodev foo

outputs "hello world!".

Time to truncate

The last burst of checkins has brought Tux3 to the pointer where it
undeniably acts like a filesystem: one can write files, go away,
come back later and read those files by name.  We can see some of the
hoped for attractiveness starting to emerge: Tux3 clearly does scale
from the very small to the very big at the same time.  We have our
Exabyte file with 4K blocksize and we can also create 64 Petabyte
files using 256 byte blocks.  How cool is that?  Not much chance for
internal fragmentation with 256 byte blocks.

   http://en.wikipedia.org/wiki/Fragmentation_(computer)

I wonder how well Tux3 will perform with 256 byte blocks.  Actually,
I don't really see big problems.  We should probably be working mostly
with tiny blocks in initial development, because little blocks generate
bushy trees, and bushy trees expose boundary conditions much faster
than big blocks.  Which is exactly what we need now if we want to get
stable early.  Plus it helps focus on allocation strategy: more little
blocks means more chances for things to go wrong by fragmentation.
Let's keep that issue front and center throughout the entire course of
Tux3 development.

(When we get closer to the kernel port I will switch to working mainly
with 512 byte blocks, which is the finest granularity supported by
Linux block devices at present.)

Anyway, the question naturally arises: what next?  There are so many
issues remaining, big and small.  Some of the big ones:

  * Atomic Commit - we want to know if Tux3's new forward logging
    strategy is as good as I have boasted, and indeed, does it work

Time to truncate

The last burst of checkins has brought Tux3 to the point where it
undeniably acts like a filesystem: one can write files, go away,
come back later and read those files by name.  We can see some of the
hoped for attractiveness starting to emerge: Tux3 clearly does scale
from the very small to the very big at the same time.  We have our
Exabyte file with 4K blocksize and we can also create 64 Petabyte
files using 256 byte blocks.  How cool is that?  Not much chance for
internal fragmentation with 256 byte blocks.

   http://en.wikipedia.org/wiki/Fragmentation_(computer)

I wonder how well Tux3 will perform with 256 byte blocks.  Actually,
I don't really see big problems.  We should probably be working mostly
with tiny blocks in initial development, because little blocks generate
bushy trees, and bushy trees expose boundary conditions much faster
than big blocks.  Which is exactly what we need now if we want to get
stable early.  Plus it helps focus on allocation strategy: more little
blocks means more chances for things to go wrong by fragmentation.
Let's keep that issue front and center throughout the entire course of
Tux3 development.

(When we get closer to the kernel port I will switch to working mainly
with 512 byte blocks, which is the finest granularity supported by
Linux block devices at present.)

Anyway, the question naturally arises: what next?  There are so many
issues remaining, big and small.  Some of the big ones:

  * Atomic Commit - we want to know if Tux3's new forward logging
    strategy is as good as I have boasted, and indeed, does it work

[PATCH] More 64 bit format string cleanups (again)

diff -r dc0f4243e276 user/test/inode.c
--- a/user/test/inode.c	Mon Sep 01 12:51:37 2008 -0700
+++ b/user/test/inode.c	Mon Sep 01 16:56:37 2008 -0700
@@ -418,7 +418,7 @@
 	/* Always 8K regardless of blocksize */
 	int reserve = 1 << (sb->blockbits > 13 ? 0 : 13 - sb->blockbits);
 	for (int i = 0; i < reserve; i++)
-		printf("reserve %Lx\n", balloc_from_range(sb->bitmap, i, 1));
+		printf("reserve %Lx\n", (L)balloc_from_range(sb->bitmap, i, 1));

 	printf("---- create inode table ----\n");
 	sb->itree = new_btree(sb, &itree_ops);
diff -r dc0f4243e276 user/test/tux3.c
--- a/user/test/tux3.c	Mon Sep 01 12:51:37 2008 -0700
+++ b/user/test/tux3.c	Mon Sep 01 16:56:37 2008 -0700
@@ -136,7 +136,7 @@
 #endif
 		if (seekarg) {
 			u64 seek = strtoull(seekarg, NULL, 0);
-			printf("seek to %Li\n", seek);
+			printf("seek to %Li\n", (L)seek);
 			tuxseek(file, seek);
 		}
 		char text[2 << 16];
@@ -172,7 +172,7 @@
 		//tuxseek(file, (1LL << 60) - 12);
 		if (seekarg) {
 			u64 seek = strtoull(seekarg, NULL, 0);
-			printf("seek to %Li\n", seek);
+			printf("seek to %Li\n", (L)seek);

[PATCH] Make sure ileaf offsets are in non-descending order

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');

Re: [PATCH] Make sure ileaf offsets are in non-descending order

On Monday 01 September 2008 23:56, Conrad Meyer wrote:
> +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;
> +}

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;
}

Re: [PATCH] Make sure ileaf offsets are in non-descending order

Quoth Daniel Phillips:
> 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 

Heh, yes it does, doesn't it.

> 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;

[PATCH] Add check for ileaf dict ordering

diff -r fd5ca07f03dd user/test/ileaf.c
--- a/user/test/ileaf.c	Tue Sep 02 00:06:45 2008 -0700
+++ b/user/test/ileaf.c	Tue Sep 02 06:47:17 2008 -0700
@@ -124,11 +124,23 @@
 	return attrs;
 }

+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;
+}
+
 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:

Re: [PATCH] Add check for ileaf dict ordering

Applied, thanks.

Daniel

Re: [PATCH] Add check for ileaf dict ordering

On Tuesday 02 September 2008 09:36:55 am you wrote:
> On Tue, Sep 2, 2008 at 6:47 AM, Conrad Meyer <konrad <at> tylerc.org> wrote:
> 
> > diff -r fd5ca07f03dd user/test/ileaf.c
> > --- a/user/test/ileaf.c Tue Sep 02 00:06:45 2008 -0700
> > +++ b/user/test/ileaf.c Tue Sep 02 06:47:17 2008 -0700
> > @@ -124,11 +124,23 @@
> >        return attrs;
> >  }
> >
> > +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)
> 
> 
> My memory might be failing me. Is this correct C standard?

It's C99 IIRC.

Regards,
--

-- 
Conrad Meyer <konrad <at> tylerc.org>

_______________________________________________
Tux3 mailing list
Tux3 <at> tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3