Goffredo Baroncelli wrote:
> Hi Li,
>
> On Monday, 13 December, 2010, Li Zefan wrote:
>> 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 ?
>
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 <chris.mason@xxxxxxxxxx>
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".
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
