Skip to contentSkip to conversation

Btrfs: Really return keys within specified range

PATCH In review Li Zefan 3 participants 15 messages Dec 13, 2010 – Dec 16, 2010 Btrfs file system

lore
Share & tools
lore

Li Zefan

author
#0 lore raw

PATCH 1/3 Btrfs: Really return keys within specified range

The keys returned by tree search ioctl should be restricted to:

	key.objectid = [min_objectid, max_objectid] &&
	key.offset   = [min_offset, max_offset] &&
	key.type     = [min_type, max_type]

But actually it returns those keys:

[(min_objectid, min_type, min_offset),
(max_objectid, max_type, max_offset)].

And the bug can result in missing subvolumes in the output of "btrfs subvolume list"

---
 fs/btrfs/ioctl.c |   20 ++++----------------
 1 files changed, 4 insertions(+), 16 deletions(-)
fs/btrfs/ioctl.c +4 -16
index f1c9bb4..785f713 100644
@@ -1028,23 +1028,11 @@ out:
 static noinline int key_in_sk(struct btrfs_key *key,
 			      struct btrfs_ioctl_search_key *sk)
 {
-	struct btrfs_key test;
-	int ret;
-
-	test.objectid = sk->min_objectid;
-	test.type = sk->min_type;
-	test.offset = sk->min_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret < 0)
+	if (key->type < sk->min_type || key->type > sk->max_type)
 		return 0;
-
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret > 0)
+	if (key->offset < sk->min_offset || key->offset > sk->max_offset)
+		return 0;
+	if (key->objectid < sk->min_objectid || key->objectid > sk->max_objectid)
 		return 0;
 	return 1;
 }
Signature · 1 line
1.6.3
author
#1 lore raw

PATCH 2/3 Btrfs: Don't return items more than user specified

We check if num_found >= sk->nr_items every time we find an expected item, but num_found is not incremented, so we may return items more than the user asked.

Also return -EINVAL if the user specified 0 nr_items.

---
 fs/btrfs/ioctl.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
fs/btrfs/ioctl.c +4 -3
index 785f713..08174e2 100644
@@ -1053,7 +1053,6 @@ static noinline int copy_to_sk(struct btrfs_root *root,
 	int nritems;
 	int i;
 	int slot;
-	int found = 0;
 	int ret = 0;
 
 	leaf = path->nodes[0];
@@ -1100,8 +1099,8 @@ static noinline int copy_to_sk(struct btrfs_root *root,
 					   item_off, item_len);
 			*sk_offset += item_len;
 		}
-		found++;
 
+		(*num_found)++;
 		if (*num_found >= sk->nr_items)
 			break;
 	}
@@ -1119,7 +1118,6 @@ advance_key:
 	} else
 		ret = 1;
 overflow:
-	*num_found += found;
 	return ret;
 }
 
@@ -1136,6 +1134,9 @@ static noinline int search_ioctl(struct inode *inode,
 	int num_found = 0;
 	unsigned long sk_offset = 0;
 
+	if (sk->nr_items == 0)
+		return -EINVAL;
+
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
Signature · 1 line
1.6.3
author
#2 lore raw

PATCH 3/3 Btrfs: Clean up tree search ioctl code

In reply to Li Zefan

- Check if the key is within specified range before checking the item length.
- Advance to the next key a bit more efficiently.
- Remove redundant code.

---
 fs/btrfs/ioctl.c |   30 ++++++++++++------------------
 1 files changed, 12 insertions(+), 18 deletions(-)
fs/btrfs/ioctl.c +12 -18
index 08174e2..477affb 100644
@@ -1059,28 +1059,24 @@ static noinline int copy_to_sk(struct btrfs_root *root,
 	slot = path->slots[0];
 	nritems = btrfs_header_nritems(leaf);
 
-	if (btrfs_header_generation(leaf) > sk->max_transid) {
-		i = nritems;
+	if (btrfs_header_generation(leaf) > sk->max_transid)
 		goto advance_key;
-	}
 	found_transid = btrfs_header_generation(leaf);
 
 	for (i = slot; i < nritems; i++) {
 		item_off = btrfs_item_ptr_offset(leaf, i);
 		item_len = btrfs_item_size_nr(leaf, i);
 
+		btrfs_item_key_to_cpu(leaf, key, i);
+		if (!key_in_sk(key, sk))
+			continue;
+
 		if (item_len > BTRFS_SEARCH_ARGS_BUFSIZE)
 			item_len = 0;
 
 		if (sizeof(sh) + item_len + *sk_offset >
-		    BTRFS_SEARCH_ARGS_BUFSIZE) {
-			ret = 1;
-			goto overflow;
-		}
-
-		btrfs_item_key_to_cpu(leaf, key, i);
-		if (!key_in_sk(key, sk))
-			continue;
+		    BTRFS_SEARCH_ARGS_BUFSIZE)
+			return 1;
 
 		sh.objectid = key->objectid;
 		sh.offset = key->offset;
@@ -1102,22 +1098,21 @@ static noinline int copy_to_sk(struct btrfs_root *root,
 
 		(*num_found)++;
 		if (*num_found >= sk->nr_items)
-			break;
+			return 1;
 	}
 advance_key:
 	ret = 0;
 	if (key->offset < (u64)-1 && key->offset < sk->max_offset)
 		key->offset++;
 	else if (key->type < (u8)-1 && key->type < sk->max_type) {
-		key->offset = 0;
+		key->offset = sk->min_offset;
 		key->type++;
 	} else if (key->objectid < (u64)-1 && key->objectid < sk->max_objectid) {
-		key->offset = 0;
-		key->type = 0;
+		key->offset = sk->min_offset;
+		key->type = sk->min_type;
 		key->objectid++;
 	} else
 		ret = 1;
-overflow:
 	return ret;
 }
 
@@ -1178,9 +1173,8 @@ static noinline int search_ioctl(struct inode *inode,
 		ret = copy_to_sk(root, path, &key, sk, args->buf,
 				 &sk_offset, &num_found);
 		btrfs_release_path(root, path);
-		if (ret || num_found >= sk->nr_items)
+		if (ret)
 			break;
-
 	}
 	ret = 0;
 err:
Signature · 1 line
1.6.3
#3 lore raw

Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

In reply to Li Zefan

Hi Li,

Quoted 11 lines · Li Zefan

The keys returned by tree search ioctl should be restricted to:

	key.objectid = [min_objectid, max_objectid] &&
	key.offset   = [min_offset, max_offset] &&
	key.type     = [min_type, max_type]

But actually it returns those keys:

[(min_objectid, min_type, min_offset),
(max_objectid, max_type, max_offset)].

I have to admit that I had need several minutes to understand what you wrote :). Then I came to conclusion that the tree search ioctl is basically wrong.

IMHO, the error in this API is to use the lower bound of the acceptance criteria (the min_objectid, min_offset, min_type fields) also as starting point for the search.

Let me explain with an example.

Suppose to want to search all the keys in the range

key.objectid = 10..20
key.offset = 100..200
key.type = 2..5

Suppose to set sk->nr_items to 1 for simplicity, and the keys available which fit in the range are

1) [15,150,3]
2) [16,160,4]
3) [17,180,3]

All these key satisfy the "acceptance criteria", but because we have to restart the search from the last key found, the code should resemble

	sk = &args.key

	sk->min_objectid=10; sk->max_objectid=20
	sk->min_offset=100; sk->max_offset=200
	sk->min_type=2; sk->max_type=5
	sk->nr_items = 1;

	while(1){
		ioctl(fd,  BTRFS_IOC_TREE_SEARCH, &args);
		if( !sk->nr_items )
			break

		for(off = 0, i=0 ; i < sk->nr_items ; i   ){
			sh = (struct btrfs_ioctl_search_header *)(args.buf  
                                                                 off);

			[...]
	                sk->min_objectid = sh->objectid;
        	        sk->min_offset = sh->offset;
	                sk->min_type = sh->type;
		}

		<increase the sk->min_* key of 1>
				
	}

But in this case, the code after found the key #2, sets the minimum acceptance criteria to [16,160,4], which exclude the key #3 because min_type is too high.

Ideally, we should add three new field to the search key structure:

	sk->start_objectid
	sk->start_offset
	sk->start_type

And after every iteration the code (even the kernel code) should set these fields as "last key found 1", leaving the min_* fields as they are.

My analysis is correct or I miss something ?

Regards
G.Baroncelli

Quoted 50 lines

And the bug can result in missing subvolumes in the output of "btrfs subvolume list"

---
 fs/btrfs/ioctl.c |   20 ++++----------------
 1 files changed, 4 insertions(+), 16 deletions(-)
fs/btrfs/ioctl.c +4 -16
index f1c9bb4..785f713 100644
@@ -1028,23 +1028,11 @@ out:
 static noinline int key_in_sk(struct btrfs_key *key,
 			      struct btrfs_ioctl_search_key *sk)
 {
-	struct btrfs_key test;
-	int ret;
-
-	test.objectid = sk->min_objectid;
-	test.type = sk->min_type;
-	test.offset = sk->min_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret < 0)
+	if (key->type < sk->min_type || key->type > sk->max_type)
 		return 0;
-
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret > 0)
+	if (key->offset < sk->min_offset || key->offset > sk->max_offset)
+		return 0;
+	if (key->objectid < sk->min_objectid || key->objectid > sk-
 max_objectid)
 		return 0;
 	return 1;

}

Signature · 6 lines
1.6.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512
author
#4 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 72 lines · Goffredo Baroncelli

Hi Li,

Quoted 11 lines · Li Zefan

The keys returned by tree search ioctl should be restricted to:

	key.objectid = [min_objectid, max_objectid] &&
	key.offset   = [min_offset, max_offset] &&
	key.type     = [min_type, max_type]

But actually it returns those keys:

[(min_objectid, min_type, min_offset),
(max_objectid, max_type, max_offset)].

I have to admit that I had need several minutes to understand what you wrote :). Then I came to conclusion that the tree search ioctl is basically wrong.

IMHO, the error in this API is to use the lower bound of the acceptance criteria (the min_objectid, min_offset, min_type fields) also as starting point for the search.

Let me explain with an example.

Suppose to want to search all the keys in the range

(quoted diff) +0 -0
 	key.objectid = 10..20
 	key.offset   = 100..200
 	key.type     = 2..5

Suppose to set sk->nr_items to 1 for simplicity, and the keys available which fit in the range are

1) [15,150,3]
2) [16,160,4]
3) [17,180,3]

All these key satisfy the "acceptance criteria", but because we have to restart the search from the last key found, the code should resemble

	sk = &args.key

	sk->min_objectid=10; sk->max_objectid=20
	sk->min_offset=100; sk->max_offset=200
	sk->min_type=2; sk->max_type=5
	sk->nr_items = 1;

	while(1){
		ioctl(fd,  BTRFS_IOC_TREE_SEARCH, &args);
		if( !sk->nr_items )
			break

		for(off = 0, i=0 ; i < sk->nr_items ; i   ){
			sh = (struct btrfs_ioctl_search_header *)(args.buf  
                                                                 off);

			[...]
	                sk->min_objectid = sh->objectid;
        	        sk->min_offset = sh->offset;
	                sk->min_type = sh->type;
		}

		<increase the sk->min_* key of 1>
				
	}

But in this case, the code after found the key #2, sets the minimum acceptance criteria to [16,160,4], which exclude the key #3 because min_type is too high.

Ideally, we should add three new field to the search key structure:

Quoted 9 lines
	sk->start_objectid
	sk->start_offset
	sk->start_type

And after every iteration the code (even the kernel code) should set these fields as "last key found 1", leaving the min_* fields as they are.

My analysis is correct or I miss something ?

After looking more deeply, I found the ioctl was changed in this way on purpose, to support "btrfs subvolume find-new" specifically.

See this commit:

commit abc6e1341bda974e2d0eddb75f57a20ac18e9b33

Author: Chris Mason <[email protected]>
Date:   Thu Mar 18 12:10:08 2010 -0400

Btrfs: fix key checks and advance in the search ioctl

The search ioctl was working well for finding tree roots, but using it for generic searches requires a few changes to how the keys are advanced. This treats the search control min fields for objectid, type and offset more like a key, where we drop the offset to zero once we bump the type, etc.

The downside of this is that we are changing the min_type and min_offset fields during the search, and so the ioctl caller needs extra checks to make the keys in the result are the ones it wanted.

This also changes key_in_sk to use btrfs_comp_cpu_keys, just to make things more readable.

So I think we can just fix the btrfs tool. Though adding sk->start_xxx should also be able to meet the needs for "btrfs subvolume find-new".

#5 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 10 lines · Li Zefan
Quoted 9 lines · Goffredo Baroncelli

Hi Li,

Quoted 6 lines · Li Zefan

The keys returned by tree search ioctl should be restricted to:

	key.objectid = [min_objectid, max_objectid] &&
	key.offset   = [min_offset, max_offset] &&
	key.type     = [min_type, max_type]
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines

But actually it returns those keys:

[(min_objectid, min_type, min_offset),
(max_objectid, max_type, max_offset)].

I have to admit that I had need several minutes to understand what you

wrote

Quoted 1 line
Quoted 1 line

:). Then I came to conclusion that the tree search ioctl is basically

wrong.

Quoted 7 lines
Quoted 7 lines

IMHO, the error in this API is to use the lower bound of the acceptance criteria (the min_objectid, min_offset, min_type fields) also as starting point for the search.

Let me explain with an example.

Quoted 8 lines
Quoted 8 lines

Suppose to want to search all the keys in the range

(quoted diff) +0 -0
 	key.objectid = 10..20
 	key.offset   = 100..200
 	key.type     = 2..5

Suppose to set sk->nr_items to 1 for simplicity, and the keys available

which

Quoted 31 lines
Quoted 31 lines

fit in the range are

1) [15,150,3]
2) [16,160,4]
3) [17,180,3]

All these key satisfy the "acceptance criteria", but because we have to restart the search from the last key found, the code should resemble

	sk = &args.key

	sk->min_objectid=10; sk->max_objectid=20
	sk->min_offset=100; sk->max_offset=200
	sk->min_type=2; sk->max_type=5
	sk->nr_items = 1;

	while(1){
		ioctl(fd,  BTRFS_IOC_TREE_SEARCH, &args);
		if( !sk->nr_items )
			break

		for(off = 0, i=0 ; i < sk->nr_items ; i   ){
			sh = (struct btrfs_ioctl_search_header *)(args.buf  
                                                                 off);

			[...]
	                sk->min_objectid = sh->objectid;
        	        sk->min_offset = sh->offset;
	                sk->min_type = sh->type;
		}
Quoted 5 lines
Quoted 5 lines
		<increase the sk->min_* key of 1>
				
	}

But in this case, the code after found the key #2, sets the minimum

acceptance

Quoted 1 line
Quoted 1 line

criteria to [16,160,4], which exclude the key #3 because min_type is too

high.

Quoted 18 lines
Quoted 12 lines

Ideally, we should add three new field to the search key structure:

	sk->start_objectid
	sk->start_offset
	sk->start_type

And after every iteration the code (even the kernel code) should set these fields as "last key found 1", leaving the min_* fields as they are.

My analysis is correct or I miss something ?

After looking more deeply, I found the ioctl was changed in this way on purpose, to support "btrfs subvolume find-new" specifically.

See this commit:

Quoted 7 lines

commit abc6e1341bda974e2d0eddb75f57a20ac18e9b33

Author: Chris Mason <[email protected]>
Date:   Thu Mar 18 12:10:08 2010 -0400

Btrfs: fix key checks and advance in the search ioctl

The search ioctl was working well for finding tree roots, but using it

for

Quoted 7 lines

generic searches requires a few changes to how the keys are advanced. This treats the search control min fields for objectid, type and offset more like a key, where we drop the offset to zero once we bump the type, etc.

The downside of this is that we are changing the min_type and min_offset fields during the search, and so the ioctl caller needs extra checks to

make

Quoted 6 lines

the keys in the result are the ones it wanted.

This also changes key_in_sk to use btrfs_comp_cpu_keys, just to make things more readable.

So I think we can just fix the btrfs tool. Though adding sk->start_xxx

should

Quoted 1 line

also be able to meet the needs for "btrfs subvolume find-new".

Sorry, but I have to disagree. This API seems to me simply bugged. The example above (which is quite generic) highlights this fact. But I can provide a more real case: suppose to use the BTRFS_IOC_TREE_SEARCH ioctl to find the new files. We are interested to the following items:

- BTRFS_EXTENT_DATA_KEY (type = 1)
- BTRFS_INODE_ITEM_KEY (type = 24)
- BTRFS_XATTR_ITEM_KEY (type = 108)

Acceptance criteria:

min_type = 1
max_type = 108
min_offset = 0
max_offset = ~0
min_objectid = 0
max_objectid = ~0
min_transid = <the base generation number>

Pay attention that we aren't interested in the offset.

Suppose to have the following sequence keys [objectid, type, offset]:

[...]
1) [300, BTRFS_EXTENT_DATA_KEY, xx]
2) [300, BTRFS_INODE_ITEM_KEY, xx]
3) [300, BTRFS_XATTR_ITEM_KEY, xx]
4) [301, BTRFS_EXTENT_DATA_KEY, xx]
5) [301, BTRFS_INODE_ITEM_KEY, xx]
7) [30200, BTRFS_EXTENT_DATA_KEY, xx]
8) [30200, BTRFS_INODE_ITEM_KEY, xx]
9) [30200, BTRFS_XATTR_ITEM_KEY, xx]
[...]

Suppose that the buffer is filled between the item 2 and 3. We should restart the search, but how set the min_* key ? Try the following hypothesis

h1) objectid++, type = 0 -> In the next search the key 3 would be skipped h2) objectid asis, type ++, -> in the next search the key 4 would be skipped h3) objectid asis, type = 0 -> in the next search the key 1,2,3 would be returned a second time...

Pay attention that every inode may have more key type BTRFS_XATTR_ITEM_KEY or type BTRFS_EXTENT_DATA_KEY, so it is not possible to know in advance when the buffer is filled.

Only as theoretical exercise, we can improve the search logic in userspace so when an item is returned, in the next search we set the minimum type as previous type+1, and the *maximum* objectid as the latest ofound bject id. When we are sure that there are not more key with this objectid we can reuse the old max_objectid and min_type... But to me it seems very fragile.

Chris what do you think ? Otherwise I missed something this seems a severe bug in the api ?

In another email I will propose a patch which may address this problem.

Regards
G.Baroncelli

Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512
author
#6 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 150 lines · Goffredo Baroncelli
Quoted 10 lines · Li Zefan
Quoted 9 lines · Goffredo Baroncelli

Hi Li,

Quoted 6 lines · Li Zefan

The keys returned by tree search ioctl should be restricted to:

	key.objectid = [min_objectid, max_objectid] &&
	key.offset   = [min_offset, max_offset] &&
	key.type     = [min_type, max_type]
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

But actually it returns those keys:

[(min_objectid, min_type, min_offset),
(max_objectid, max_type, max_offset)].

I have to admit that I had need several minutes to understand what you

wrote

Quoted 1 line
Quoted 1 line

:). Then I came to conclusion that the tree search ioctl is basically

wrong.

Quoted 6 lines
Quoted 6 lines

IMHO, the error in this API is to use the lower bound of the acceptance criteria (the min_objectid, min_offset, min_type fields) also as starting point for the search.

Let me explain with an example.

Quoted 8 lines
Quoted 8 lines

Suppose to want to search all the keys in the range

(quoted diff) +0 -0
 	key.objectid = 10..20
 	key.offset   = 100..200
 	key.type     = 2..5

Suppose to set sk->nr_items to 1 for simplicity, and the keys available

which

Quoted 31 lines
Quoted 31 lines

fit in the range are

1) [15,150,3]
2) [16,160,4]
3) [17,180,3]

All these key satisfy the "acceptance criteria", but because we have to restart the search from the last key found, the code should resemble

	sk = &args.key

	sk->min_objectid=10; sk->max_objectid=20
	sk->min_offset=100; sk->max_offset=200
	sk->min_type=2; sk->max_type=5
	sk->nr_items = 1;

	while(1){
		ioctl(fd,  BTRFS_IOC_TREE_SEARCH, &args);
		if( !sk->nr_items )
			break

		for(off = 0, i=0 ; i < sk->nr_items ; i   ){
			sh = (struct btrfs_ioctl_search_header *)(args.buf  
                                                                 off);

			[...]
	                sk->min_objectid = sh->objectid;
        	        sk->min_offset = sh->offset;
	                sk->min_type = sh->type;
		}
Quoted 5 lines
Quoted 5 lines
		<increase the sk->min_* key of 1>
				
	}

But in this case, the code after found the key #2, sets the minimum

acceptance

Quoted 1 line
Quoted 1 line

criteria to [16,160,4], which exclude the key #3 because min_type is too

high.

Quoted 16 lines
Quoted 11 lines

Ideally, we should add three new field to the search key structure:

	sk->start_objectid
	sk->start_offset
	sk->start_type

And after every iteration the code (even the kernel code) should set these fields as "last key found 1", leaving the min_* fields as they are.

My analysis is correct or I miss something ?

After looking more deeply, I found the ioctl was changed in this way on purpose, to support "btrfs subvolume find-new" specifically.

See this commit:

Quoted 7 lines

commit abc6e1341bda974e2d0eddb75f57a20ac18e9b33

Author: Chris Mason <[email protected]>
Date:   Thu Mar 18 12:10:08 2010 -0400

Btrfs: fix key checks and advance in the search ioctl

The search ioctl was working well for finding tree roots, but using it

for

Quoted 7 lines

generic searches requires a few changes to how the keys are advanced. This treats the search control min fields for objectid, type and offset more like a key, where we drop the offset to zero once we bump the type, etc.

The downside of this is that we are changing the min_type and min_offset fields during the search, and so the ioctl caller needs extra checks to

make

Quoted 6 lines

the keys in the result are the ones it wanted.

This also changes key_in_sk to use btrfs_comp_cpu_keys, just to make things more readable.

So I think we can just fix the btrfs tool. Though adding sk->start_xxx

should

Quoted 1 line

also be able to meet the needs for "btrfs subvolume find-new".

Sorry, but I have to disagree. This API seems to me simply bugged. The example above (which is quite generic) highlights this fact. But I can provide a more real case: suppose to use the BTRFS_IOC_TREE_SEARCH ioctl to find the new files. We are interested to the following items:

- BTRFS_EXTENT_DATA_KEY (type = 1)
- BTRFS_INODE_ITEM_KEY (type = 24)
- BTRFS_XATTR_ITEM_KEY (type = 108)

Acceptance criteria:

min_type = 1
max_type = 108
min_offset = 0
max_offset = ~0
min_objectid = 0
max_objectid = ~0
min_transid = <the base generation number>

Pay attention that we aren't interested in the offset.

Suppose to have the following sequence keys [objectid, type, offset]:

[...]
1) [300, BTRFS_EXTENT_DATA_KEY, xx]
2) [300, BTRFS_INODE_ITEM_KEY, xx]
3) [300, BTRFS_XATTR_ITEM_KEY, xx]
4) [301, BTRFS_EXTENT_DATA_KEY, xx]
5) [301, BTRFS_INODE_ITEM_KEY, xx]
7) [30200, BTRFS_EXTENT_DATA_KEY, xx]
8) [30200, BTRFS_INODE_ITEM_KEY, xx]
9) [30200, BTRFS_XATTR_ITEM_KEY, xx]
[...]

Quoted 6 lines

Suppose that the buffer is filled between the item 2 and 3. We should restart the search, but how set the min_* key ? Try the following hypothesis

h1) objectid++, type = 0 -> In the next search the key 3 would be skipped h2) objectid asis, type ++, -> in the next search the key 4 would be skipped h3) objectid asis, type = 0 -> in the next search the key 1,2,3 would be

h4) objectid asis, type asis, offset++ -> we should get the correct result.

because the current ioctl uses min_{x,y,z} and max_{x,y,z} as start_key and end_key, and it returns all keys that falls in [start_key, end_key].

So this btrfs-progs patch should fix missing subvolumes in the output of "subvolume list":

btrfs-list.c +4 -1
index 93766a8..1b9ea45 100644
@@ -620,7 +620,10 @@ int list_subvols(int fd)
 		/* this iteration is done, step forward one root for the next
 		 * ioctl
 		 */
-		if (sk->min_objectid < (u64)-1) {
+		if (sk->min_type < BTRFS_ROOT_BACKREF_KEY) {
+			sk->min_type = BTRFS_ROOT_BACKREF_KEY;
+			sk->min_offset = 0;
+		} else  if (sk->min_objectid < (u64)-1) {
 			sk->min_objectid++;
 			sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 			sk->min_offset = 0;
Quoted 17 lines

returned a second time...

Pay attention that every inode may have more key type BTRFS_XATTR_ITEM_KEY or type BTRFS_EXTENT_DATA_KEY, so it is not possible to know in advance when the buffer is filled.

Only as theoretical exercise, we can improve the search logic in userspace so when an item is returned, in the next search we set the minimum type as previous type+1, and the *maximum* objectid as the latest ofound bject id. When we are sure that there are not more key with this objectid we can reuse the old max_objectid and min_type... But to me it seems very fragile.

Chris what do you think ? Otherwise I missed something this seems a severe bug in the api ?

In another email I will propose a patch which may address this problem.

#7 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 1 line · Li Zefan

h4) objectid asis, type asis, offset++ -> we should get the correct result.

This fix the problem of the "missing subvolume". But for the other case (searching for more than one type) the problem still here.

btrfs-list.c int list_subvols(int fd) · line 620

Quoted 12 lines

because the current ioctl uses min_{x,y,z} and max_{x,y,z} as start_key and end_key, and it returns all keys that falls in [start_key, end_key].

So this btrfs-progs patch should fix missing subvolumes in the output of "subvolume list":

btrfs-list.c +0 -0
index 93766a8..1b9ea45 100644
@@ -620,7 +620,10 @@ int list_subvols(int fd)
                /* this iteration is done, step forward one root for the 

next

Quoted 11 lines
btrfs-list.c +4 -1
                 * ioctl
                 */
-               if (sk->min_objectid < (u64)-1) {
+               if (sk->min_type < BTRFS_ROOT_BACKREF_KEY) {
+                       sk->min_type = BTRFS_ROOT_BACKREF_KEY;
+                       sk->min_offset = 0;
+               } else  if (sk->min_objectid < (u64)-1) {
                        sk->min_objectid++;
                        sk->min_type = BTRFS_ROOT_BACKREF_KEY;
                        sk->min_offset = 0;
Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512
author
#8 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 6 lines · Goffredo Baroncelli
Quoted 1 line · Li Zefan

h4) objectid asis, type asis, offset++ -> we should get the correct result.

This fix the problem of the "missing subvolume". But for the other case (searching for more than one type) the problem still here.

I don't think so. And the above "h4" has showed how we search for more than one type.

The generic userland code for next search is:

/* this is in essence the same as how we advance key in kernel code */ if (sk->min_offset < (u64)-1 && sk->min_offset < sk->max_offset)

	sk->min_offset++;
else if (sk->min_type < (u8)-1 && sk->min_type < sk->max_type) {
	sk->min_offset = 0;
	sk->min_type++;
} else if (sk->min_objectid < (u64)-1 && sk->min_objectid < sk->max_objectid){
	sk->min_offset = 0;
	sk->min_type = 0;
	sk->min_objectid++;
} else
	break;

ioctl(...);

for (i = 0; i < nr_items; i++) {
	if (!filter(items[i]))
		continue;
	/* process this item */
	...
}
Quoted 26 lines

btrfs-list.c int list_subvols(int fd) · line 620

Quoted 12 lines

because the current ioctl uses min_{x,y,z} and max_{x,y,z} as start_key and end_key, and it returns all keys that falls in [start_key, end_key].

So this btrfs-progs patch should fix missing subvolumes in the output of "subvolume list":

btrfs-list.c +0 -0
index 93766a8..1b9ea45 100644
@@ -620,7 +620,10 @@ int list_subvols(int fd)
                /* this iteration is done, step forward one root for the 

next

Quoted 11 lines
btrfs-list.c +4 -1
                 * ioctl
                 */
-               if (sk->min_objectid < (u64)-1) {
+               if (sk->min_type < BTRFS_ROOT_BACKREF_KEY) {
+                       sk->min_type = BTRFS_ROOT_BACKREF_KEY;
+                       sk->min_offset = 0;
+               } else  if (sk->min_objectid < (u64)-1) {
                        sk->min_objectid++;
                        sk->min_type = BTRFS_ROOT_BACKREF_KEY;
                        sk->min_offset = 0;
#9 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 3 lines · Li Zefan
Quoted 2 lines · Goffredo Baroncelli
Quoted 1 line · Li Zefan

h4) objectid asis, type asis, offset++ -> we should get the correct

result.

Quoted 12 lines
Quoted 4 lines

This fix the problem of the "missing subvolume". But for the other case (searching for more than one type) the problem still here.

I don't think so. And the above "h4" has showed how we search for more than one type.

The generic userland code for next search is:

/* this is in essence the same as how we advance key in kernel code */ if (sk->min_offset < (u64)-1 && sk->min_offset < sk->max_offset)

Quoted 8 lines
	sk->min_offset++;
else if (sk->min_type < (u8)-1 && sk->min_type < sk->max_type) {
	sk->min_offset = 0;
	sk->min_type++;
} else if (sk->min_objectid < (u64)-1 && sk->min_objectid < sk-
max_objectid){
	sk->min_offset = 0;
	sk->min_type = 0;

Sorry but if you reset the sk->min_type to 0, this means that the min_type lost its purpose (act as lover bound of the acceptance criteria).

Quoted 9 lines
	sk->min_objectid++;
} else
	break;

ioctl(...);

for (i = 0; i < nr_items; i++) {
	if (!filter(items[i]))
		continue;

So you are suggesting: "Move all tree items from kernel to user space and filter it in userspace ?". This mean a lot of un-needed kernel-space <-> userspace transition...

Sorry I don't understand if we are talking about a workaround or a solution.

Quoted 5 lines
	/* process this item */
	...
}
Quoted 1 line
Quoted 1 line

because the current ioctl uses min_{x,y,z} and max_{x,y,z} as start_key

and

Quoted 30 lines
Quoted 5 lines
Quoted 5 lines

end_key, and it returns all keys that falls in [start_key, end_key].

So this btrfs-progs patch should fix missing subvolumes in the output of "subvolume list":

Quoted 20 lines

btrfs-list.c int list_subvols(int fd) · line 620

Quoted 6 lines
btrfs-list.c +0 -0
index 93766a8..1b9ea45 100644
@@ -620,7 +620,10 @@ int list_subvols(int fd)
                /* this iteration is done, step forward one root for the 

next

Quoted 11 lines
btrfs-list.c +4 -1
                 * ioctl
                 */
-               if (sk->min_objectid < (u64)-1) {
+               if (sk->min_type < BTRFS_ROOT_BACKREF_KEY) {
+                       sk->min_type = BTRFS_ROOT_BACKREF_KEY;
+                       sk->min_offset = 0;
+               } else  if (sk->min_objectid < (u64)-1) {
                        sk->min_objectid++;
                        sk->min_type = BTRFS_ROOT_BACKREF_KEY;
                        sk->min_offset = 0;

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512
author
#10 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 24 lines · Goffredo Baroncelli
Quoted 3 lines · Li Zefan
Quoted 2 lines · Goffredo Baroncelli
Quoted 1 line · Li Zefan

h4) objectid asis, type asis, offset++ -> we should get the correct

result.

Quoted 10 lines
Quoted 3 lines

This fix the problem of the "missing subvolume". But for the other case (searching for more than one type) the problem still here.

I don't think so. And the above "h4" has showed how we search for more than one type.

The generic userland code for next search is:

/* this is in essence the same as how we advance key in kernel code */ if (sk->min_offset < (u64)-1 && sk->min_offset < sk->max_offset)

Quoted 8 lines
	sk->min_offset++;
else if (sk->min_type < (u8)-1 && sk->min_type < sk->max_type) {
	sk->min_offset = 0;
	sk->min_type++;
} else if (sk->min_objectid < (u64)-1 && sk->min_objectid < sk-
max_objectid){
	sk->min_offset = 0;
	sk->min_type = 0;
Quoted 3 lines

Sorry but if you reset the sk->min_type to 0, this means that the min_type lost its purpose (act as lover bound of the acceptance criteria).

Yep, the changelog of Chris' commit has said that userland has to do this.

Quoted 6 lines
Quoted 6 lines
	sk->min_objectid++;
} else
	break;

ioctl(...);

Quoted 8 lines
Quoted 3 lines
for (i = 0; i < nr_items; i++) {
	if (!filter(items[i]))
		continue;

So you are suggesting: "Move all tree items from kernel to user space and filter it in userspace ?". This mean a lot of un-needed kernel-space <-> userspace transition...

Right, but it's fine so far. I'm not suggesting anything, but explaining how the ioctl is working.

Quoted 2 lines

Sorry I don't understand if we are talking about a workaround or a solution.

As Chris said, it's not perfect but we can just live along with it, until we find some killer app that requests us to improve/expand this ioctl.

#11 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

In reply to Li Zefan

Excerpts from Li Zefan's message of 2010-12-14 22:33:33 -0500:

Quoted 14 lines
Quoted 14 lines

Suppose to have the following sequence keys [objectid, type, offset]:

[...]

1)    [300, BTRFS_EXTENT_DATA_KEY, xx]
2)    [300, BTRFS_INODE_ITEM_KEY, xx]
3)    [300, BTRFS_XATTR_ITEM_KEY, xx]
4)    [301, BTRFS_EXTENT_DATA_KEY, xx]
5)    [301, BTRFS_INODE_ITEM_KEY, xx]
7)    [30200, BTRFS_EXTENT_DATA_KEY, xx]
8)    [30200, BTRFS_INODE_ITEM_KEY, xx]
9)    [30200, BTRFS_XATTR_ITEM_KEY, xx]

[...]

Quoted 8 lines
Quoted 6 lines

Suppose that the buffer is filled between the item 2 and 3. We should restart the search, but how set the min_* key ? Try the following hypothesis

h1) objectid++, type = 0 -> In the next search the key 3 would be skipped h2) objectid asis, type ++, -> in the next search the key 4 would be skipped h3) objectid asis, type = 0 -> in the next search the key 1,2,3 would be

h4) objectid asis, type asis, offset++ -> we should get the correct result.

This is the right answer ;). The problem is that even though our key has 3 distinct parts, and the API makes it look like you have very fine grained control over those three parts, you have to remember to reset them as you iterate between objectids. It isn't a obvious as it should be.

The current API is a very raw export of how we do the searches in the kernel too. You can do pretty much anything with it, but we pay with complexity.

-chris

#12 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Quoted 16 lines · Chris Mason

Excerpts from Li Zefan's message of 2010-12-14 22:33:33 -0500:

Quoted 15 lines
Quoted 15 lines

Suppose to have the following sequence keys [objectid, type, offset]:

[...]

1)    [300, BTRFS_EXTENT_DATA_KEY, xx]
2)    [300, BTRFS_INODE_ITEM_KEY, xx]
3)    [300, BTRFS_XATTR_ITEM_KEY, xx]
4)    [301, BTRFS_EXTENT_DATA_KEY, xx]
5)    [301, BTRFS_INODE_ITEM_KEY, xx]
7)    [30200, BTRFS_EXTENT_DATA_KEY, xx]
8)    [30200, BTRFS_INODE_ITEM_KEY, xx]
9)    [30200, BTRFS_XATTR_ITEM_KEY, xx]

[...]

Suppose that the buffer is filled between the item 2 and 3. We should

restart

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

the search, but how set the min_* key ? Try the following hypothesis

h1) objectid++, type = 0 -> In the next search the key 3 would be

skipped

Quoted 1 line
Quoted 1 line
Quoted 1 line

h2) objectid asis, type ++, -> in the next search the key 4 would be

skipped

Quoted 3 lines
Quoted 3 lines
Quoted 1 line

h3) objectid asis, type = 0 -> in the next search the key 1,2,3 would be

h4) objectid asis, type asis, offset++ -> we should get the correct

result.

Quoted 10 lines

This is the right answer ;). The problem is that even though our key has 3 distinct parts, and the API makes it look like you have very fine grained control over those three parts, you have to remember to reset them as you iterate between objectids. It isn't a obvious as it should be.

The current API is a very raw export of how we do the searches in the kernel too. You can do pretty much anything with it, but we pay with complexity.

Hi Chris,

I am a bit confused about your answer.

The actual API is a bit confused (or almost not "obvious"). An application in order to work properly has to make some adjustment to the min_* fields AND filter the results (because if we tweak with the min_* field, not useful data is returned). Moreover this means that we move between user-space<->kernel- space a lot of unused data (un-necessary context switch).

On the basis of your answer, it seems that this is ok (please don't consider only the case of listing the subvolumes which is a very simple cases). And nothing have to do.

Instead I suggest to (see my email [PATCH] BTRFS_IOC_TREE_SEARCH: store and use the last key found):
- leave the min_* and max_* fields to act only as filter
- add three more fields start_* as start point for the search
- make some small modification to the kernel code to track in the start_* fields the last key found

pro:
- we pass to userspace only useful data
- we simplify a lot the userspace application, because they don't have to update the min_* fields (they will work in a obvious way :-) )
- we can use the ordered property of a btree structure to perform efficient data lookup (if we reset to zero the min_* fields we lookup un-necessary data)
- we have the same functionality of the old API

cons:
- we need a modification ( :-) )

May be that I missed some point, but I don't see any advantage to continue to support the actual API. Of course, that doesn't means that we can remove the old API ignoring the backward compatibility.
But I think that there are sufficient pros to develop a new API

Please be patient: my english is very bad; I am not trying to blame anybody; I want only a "perfect fs" (TM) :-)

Quoted 4 lines

-chris

Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512
#13 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

Excerpts from Goffredo Baroncelli's message of 2010-12-15 13:42:23 -0500:

Quoted 49 lines · Chris Mason
Quoted 16 lines

Excerpts from Li Zefan's message of 2010-12-14 22:33:33 -0500:

Quoted 15 lines
Quoted 15 lines

Suppose to have the following sequence keys [objectid, type, offset]:

[...]

1)    [300, BTRFS_EXTENT_DATA_KEY, xx]
2)    [300, BTRFS_INODE_ITEM_KEY, xx]
3)    [300, BTRFS_XATTR_ITEM_KEY, xx]
4)    [301, BTRFS_EXTENT_DATA_KEY, xx]
5)    [301, BTRFS_INODE_ITEM_KEY, xx]
7)    [30200, BTRFS_EXTENT_DATA_KEY, xx]
8)    [30200, BTRFS_INODE_ITEM_KEY, xx]
9)    [30200, BTRFS_XATTR_ITEM_KEY, xx]

[...]

Suppose that the buffer is filled between the item 2 and 3. We should

restart

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

the search, but how set the min_* key ? Try the following hypothesis

h1) objectid++, type = 0 -> In the next search the key 3 would be

skipped

Quoted 1 line
Quoted 1 line
Quoted 1 line

h2) objectid asis, type ++, -> in the next search the key 4 would be

skipped

Quoted 3 lines
Quoted 3 lines
Quoted 1 line

h3) objectid asis, type = 0 -> in the next search the key 1,2,3 would be

h4) objectid asis, type asis, offset++ -> we should get the correct

result.

Quoted 10 lines

This is the right answer ;). The problem is that even though our key has 3 distinct parts, and the API makes it look like you have very fine grained control over those three parts, you have to remember to reset them as you iterate between objectids. It isn't a obvious as it should be.

The current API is a very raw export of how we do the searches in the kernel too. You can do pretty much anything with it, but we pay with complexity.

Hi Chris,

I am a bit confused about your answer.

The actual API is a bit confused (or almost not "obvious"). An application in order to work properly has to make some adjustment to the min_* fields AND filter the results (because if we tweak with the min_* field, not useful data is returned). Moreover this means that we move between user-space<->kernel- space a lot of unused data (un-necessary context switch).

Quoted 3 lines

On the basis of your answer, it seems that this is ok (please don't consider only the case of listing the subvolumes which is a very simple cases). And nothing have to do.

Well, it's ok in that I wanted the API to be very close to the way searches are done in the kernel. I'll definitely agree it isn't perfect, especially as we hop between objectids or types.

But I don't want to extend it just yet, mostly because we don't have new applications making use of it. I'd rather couple any new apis with new applications that we haven't yet thought of.

Thanks a lot for the time you're spending on review and looking at this. If you have killer apps that can really make use of new APIs, I'm happy to start reworking things.

-chris

#14 lore raw

Re: Bug in the design of the tree search ioctl API ? [was Re: [PATCH 1/3] Btrfs: Really return keys within specified range]

On Wednesday, 15 December, 2010, Chris Mason wrote:
[...]

Quoted 6 lines
Quoted 6 lines

Hi Chris,

I am a bit confused about your answer.

The actual API is a bit confused (or almost not "obvious"). An application

in

Quoted 2 lines
Quoted 2 lines

order to work properly has to make some adjustment to the min_* fields AND filter the results (because if we tweak with the min_* field, not useful

data

Quoted 5 lines
Quoted 1 line

is returned). Moreover this means that we move between user-space<-

kernel-

Quoted 3 lines

space a lot of unused data (un-necessary context switch).

On the basis of your answer, it seems that this is ok (please don't

consider

Quoted 7 lines
Quoted 2 lines

only the case of listing the subvolumes which is a very simple cases). And nothing have to do.

Well, it's ok in that I wanted the API to be very close to the way searches are done in the kernel. I'll definitely agree it isn't perfect, especially as we hop between objectids or types.

Quoted 7 lines

But I don't want to extend it just yet, mostly because we don't have new applications making use of it. I'd rather couple any new apis with new applications that we haven't yet thought of.

Thanks a lot for the time you're spending on review and looking at this. If you have killer apps that can really make use of new APIs, I'm happy to start reworking things.

Look at a my previous email about an enhancement of the find-new command ([RFC] Improve btrfs subvolume find-new command - 11/12/2010).
It would be sufficient ? (of course now on the basis of the last news of this API I know that this command is bugged :-( )

I can live with the current API ( tweaking the increasing of the min_* fields).. but think about another side of the question: now the only client of this API is the btrfs command (btrfs subvol list, which actually is broken) , and we can update this api with the minimum effort. Instead if we leave the current behavior in the future may appears an application which depends on it. So we may be obligated to maintain it ..

Goffredo

Quoted 7 lines

-chris
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 2 lines
gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <[email protected]>
Key fingerprint = 4769 7E51 5293 D36C 814E  C054 BF04 F161 3DC5 0512