2 * Copyright (C) 2012 Alexander Block. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
21 #include <sys/ioctl.h>
22 #include <uuid/uuid.h>
25 #include "send-utils.h"
27 #include "btrfs-list.h"
29 static int btrfs_subvolid_resolve_sub(int fd
, char *path
, size_t *path_len
,
32 static int btrfs_get_root_id_by_sub_path(int mnt_fd
, const char *sub_path
,
38 subvol_fd
= openat(mnt_fd
, sub_path
, O_RDONLY
);
41 fprintf(stderr
, "ERROR: open %s failed. %s\n", sub_path
,
46 ret
= btrfs_list_get_path_rootid(subvol_fd
, root_id
);
51 static int btrfs_read_root_item_raw(int mnt_fd
, u64 root_id
, size_t buf_len
,
52 u32
*read_len
, void *buf
)
55 struct btrfs_ioctl_search_args args
;
56 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
57 struct btrfs_ioctl_search_header
*sh
;
58 unsigned long off
= 0;
63 memset(&args
, 0, sizeof(args
));
65 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
68 * there may be more than one ROOT_ITEM key if there are
69 * snapshots pending deletion, we have to loop through
72 sk
->min_objectid
= root_id
;
73 sk
->max_objectid
= root_id
;
74 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
75 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
76 sk
->max_offset
= (u64
)-1;
77 sk
->max_transid
= (u64
)-1;
81 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
84 "ERROR: can't perform the search - %s\n",
88 /* the ioctl returns the number of item it found in nr_items */
89 if (sk
->nr_items
== 0)
93 for (i
= 0; i
< sk
->nr_items
; i
++) {
94 struct btrfs_root_item
*item
;
95 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
99 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
102 sk
->min_objectid
= sh
->objectid
;
103 sk
->min_type
= sh
->type
;
104 sk
->min_offset
= sh
->offset
;
106 if (sh
->objectid
> root_id
)
109 if (sh
->objectid
== root_id
&&
110 sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
111 if (sh
->len
> buf_len
) {
112 /* btrfs-progs is too old for kernel */
114 "ERROR: buf for read_root_item_raw() is too small, get newer btrfs tools!\n");
117 memcpy(buf
, item
, sh
->len
);
122 if (sk
->min_offset
< (u64
)-1)
127 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
||
128 sk
->min_objectid
!= root_id
)
132 return found
? 0 : -ENOENT
;
136 * Read a root item from the tree. In case we detect a root item smaller then
137 * sizeof(root_item), we know it's an old version of the root structure and
138 * initialize all new fields to zero. The same happens if we detect mismatching
139 * generation numbers as then we know the root was once mounted with an older
140 * kernel that was not aware of the root item structure change.
142 static int btrfs_read_root_item(int mnt_fd
, u64 root_id
,
143 struct btrfs_root_item
*item
)
148 ret
= btrfs_read_root_item_raw(mnt_fd
, root_id
, sizeof(*item
),
153 if (read_len
< sizeof(*item
) ||
154 btrfs_root_generation(item
) != btrfs_root_generation_v2(item
))
155 memset(&item
->generation_v2
, 0,
156 sizeof(*item
) - offsetof(struct btrfs_root_item
,
162 static struct rb_node
*tree_insert(struct rb_root
*root
,
163 struct subvol_info
*si
,
164 enum subvol_search_type type
)
166 struct rb_node
**p
= &root
->rb_node
;
167 struct rb_node
*parent
= NULL
;
168 struct subvol_info
*entry
;
173 if (type
== subvol_search_by_received_uuid
) {
174 entry
= rb_entry(parent
, struct subvol_info
,
177 comp
= memcmp(entry
->received_uuid
, si
->received_uuid
,
180 if (entry
->stransid
< si
->stransid
)
182 else if (entry
->stransid
> si
->stransid
)
187 } else if (type
== subvol_search_by_uuid
) {
188 entry
= rb_entry(parent
, struct subvol_info
,
190 comp
= memcmp(entry
->uuid
, si
->uuid
, BTRFS_UUID_SIZE
);
191 } else if (type
== subvol_search_by_root_id
) {
192 entry
= rb_entry(parent
, struct subvol_info
,
194 comp
= entry
->root_id
- si
->root_id
;
195 } else if (type
== subvol_search_by_path
) {
196 entry
= rb_entry(parent
, struct subvol_info
,
198 comp
= strcmp(entry
->path
, si
->path
);
211 if (type
== subvol_search_by_received_uuid
) {
212 rb_link_node(&si
->rb_received_node
, parent
, p
);
213 rb_insert_color(&si
->rb_received_node
, root
);
214 } else if (type
== subvol_search_by_uuid
) {
215 rb_link_node(&si
->rb_local_node
, parent
, p
);
216 rb_insert_color(&si
->rb_local_node
, root
);
217 } else if (type
== subvol_search_by_root_id
) {
218 rb_link_node(&si
->rb_root_id_node
, parent
, p
);
219 rb_insert_color(&si
->rb_root_id_node
, root
);
220 } else if (type
== subvol_search_by_path
) {
221 rb_link_node(&si
->rb_path_node
, parent
, p
);
222 rb_insert_color(&si
->rb_path_node
, root
);
227 int btrfs_subvolid_resolve(int fd
, char *path
, size_t path_len
, u64 subvol_id
)
233 path
[path_len
] = '\0';
234 return btrfs_subvolid_resolve_sub(fd
, path
, &path_len
, subvol_id
);
237 static int btrfs_subvolid_resolve_sub(int fd
, char *path
, size_t *path_len
,
241 struct btrfs_ioctl_search_args search_arg
;
242 struct btrfs_ioctl_ino_lookup_args ino_lookup_arg
;
243 struct btrfs_ioctl_search_header
*search_header
;
244 struct btrfs_root_ref
*backref_item
;
246 if (subvol_id
== BTRFS_FS_TREE_OBJECTID
) {
254 memset(&search_arg
, 0, sizeof(search_arg
));
255 search_arg
.key
.tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
256 search_arg
.key
.min_objectid
= subvol_id
;
257 search_arg
.key
.max_objectid
= subvol_id
;
258 search_arg
.key
.min_type
= BTRFS_ROOT_BACKREF_KEY
;
259 search_arg
.key
.max_type
= BTRFS_ROOT_BACKREF_KEY
;
260 search_arg
.key
.max_offset
= (u64
)-1;
261 search_arg
.key
.max_transid
= (u64
)-1;
262 search_arg
.key
.nr_items
= 1;
263 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &search_arg
);
266 "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
267 (unsigned long long)subvol_id
, ret
, strerror(errno
));
271 if (search_arg
.key
.nr_items
< 1) {
273 "failed to lookup subvol_id %llu!\n",
274 (unsigned long long)subvol_id
);
277 search_header
= (struct btrfs_ioctl_search_header
*)search_arg
.buf
;
278 backref_item
= (struct btrfs_root_ref
*)(search_header
+ 1);
279 if (search_header
->offset
!= BTRFS_FS_TREE_OBJECTID
) {
282 sub_ret
= btrfs_subvolid_resolve_sub(fd
, path
, path_len
,
283 search_header
->offset
);
292 if (btrfs_stack_root_ref_dirid(backref_item
) !=
293 BTRFS_FIRST_FREE_OBJECTID
) {
296 memset(&ino_lookup_arg
, 0, sizeof(ino_lookup_arg
));
297 ino_lookup_arg
.treeid
= search_header
->offset
;
298 ino_lookup_arg
.objectid
=
299 btrfs_stack_root_ref_dirid(backref_item
);
300 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_lookup_arg
);
303 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
304 ret
, strerror(errno
));
308 len
= strlen(ino_lookup_arg
.name
);
311 strcat(path
, ino_lookup_arg
.name
);
315 if (*path_len
< btrfs_stack_root_ref_name_len(backref_item
))
317 strncat(path
, (char *)(backref_item
+ 1),
318 btrfs_stack_root_ref_name_len(backref_item
));
319 (*path_len
) -= btrfs_stack_root_ref_name_len(backref_item
);
323 static int count_bytes(void *buf
, int len
, char b
)
328 for (i
= 0; i
< len
; i
++) {
329 if (((char *)buf
)[i
] == b
)
335 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
336 struct subvol_info
*si
)
340 tree_insert(&s
->root_id_subvols
, si
, subvol_search_by_root_id
);
341 tree_insert(&s
->path_subvols
, si
, subvol_search_by_path
);
343 cnt
= count_bytes(si
->uuid
, BTRFS_UUID_SIZE
, 0);
344 if (cnt
!= BTRFS_UUID_SIZE
)
345 tree_insert(&s
->local_subvols
, si
, subvol_search_by_uuid
);
346 cnt
= count_bytes(si
->received_uuid
, BTRFS_UUID_SIZE
, 0);
347 if (cnt
!= BTRFS_UUID_SIZE
)
348 tree_insert(&s
->received_subvols
, si
,
349 subvol_search_by_received_uuid
);
352 static struct subvol_info
*tree_search(struct rb_root
*root
,
353 u64 root_id
, const u8
*uuid
,
354 u64 stransid
, const char *path
,
355 enum subvol_search_type type
)
357 struct rb_node
*n
= root
->rb_node
;
358 struct subvol_info
*entry
;
362 if (type
== subvol_search_by_received_uuid
) {
363 entry
= rb_entry(n
, struct subvol_info
,
365 comp
= memcmp(entry
->received_uuid
, uuid
,
368 if (entry
->stransid
< stransid
)
370 else if (entry
->stransid
> stransid
)
375 } else if (type
== subvol_search_by_uuid
) {
376 entry
= rb_entry(n
, struct subvol_info
, rb_local_node
);
377 comp
= memcmp(entry
->uuid
, uuid
, BTRFS_UUID_SIZE
);
378 } else if (type
== subvol_search_by_root_id
) {
379 entry
= rb_entry(n
, struct subvol_info
,
381 comp
= entry
->root_id
- root_id
;
382 } else if (type
== subvol_search_by_path
) {
383 entry
= rb_entry(n
, struct subvol_info
, rb_path_node
);
384 comp
= strcmp(entry
->path
, path
);
399 * this function will be only called if kernel dosen't support uuid tree.
401 static struct subvol_info
*subvol_uuid_search_old(struct subvol_uuid_search
*s
,
402 u64 root_id
, const u8
*uuid
, u64 transid
,
404 enum subvol_search_type type
)
406 struct rb_root
*root
;
407 if (type
== subvol_search_by_received_uuid
)
408 root
= &s
->received_subvols
;
409 else if (type
== subvol_search_by_uuid
)
410 root
= &s
->local_subvols
;
411 else if (type
== subvol_search_by_root_id
)
412 root
= &s
->root_id_subvols
;
413 else if (type
== subvol_search_by_path
)
414 root
= &s
->path_subvols
;
417 return tree_search(root
, root_id
, uuid
, transid
, path
, type
);
420 struct subvol_info
*subvol_uuid_search(struct subvol_uuid_search
*s
,
421 u64 root_id
, const u8
*uuid
, u64 transid
,
423 enum subvol_search_type type
)
426 struct btrfs_root_item root_item
;
427 struct subvol_info
*info
= NULL
;
429 if (!s
->uuid_tree_existed
)
430 return subvol_uuid_search_old(s
, root_id
, uuid
, transid
,
433 case subvol_search_by_received_uuid
:
434 ret
= btrfs_lookup_uuid_received_subvol_item(s
->mnt_fd
, uuid
,
437 case subvol_search_by_uuid
:
438 ret
= btrfs_lookup_uuid_subvol_item(s
->mnt_fd
, uuid
, &root_id
);
440 case subvol_search_by_root_id
:
442 case subvol_search_by_path
:
443 ret
= btrfs_get_root_id_by_sub_path(s
->mnt_fd
, path
, &root_id
);
453 ret
= btrfs_read_root_item(s
->mnt_fd
, root_id
, &root_item
);
457 info
= calloc(1, sizeof(*info
));
458 info
->root_id
= root_id
;
459 memcpy(info
->uuid
, root_item
.uuid
, BTRFS_UUID_SIZE
);
460 memcpy(info
->received_uuid
, root_item
.received_uuid
, BTRFS_UUID_SIZE
);
461 memcpy(info
->parent_uuid
, root_item
.parent_uuid
, BTRFS_UUID_SIZE
);
462 info
->ctransid
= btrfs_root_ctransid(&root_item
);
463 info
->otransid
= btrfs_root_otransid(&root_item
);
464 info
->stransid
= btrfs_root_stransid(&root_item
);
465 info
->rtransid
= btrfs_root_rtransid(&root_item
);
466 if (type
== subvol_search_by_path
) {
467 info
->path
= strdup(path
);
469 info
->path
= malloc(BTRFS_PATH_NAME_MAX
);
470 ret
= btrfs_subvolid_resolve(s
->mnt_fd
, info
->path
,
471 BTRFS_PATH_NAME_MAX
, root_id
);
484 static int is_uuid_tree_supported(int fd
)
487 struct btrfs_ioctl_search_args args
;
488 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
490 memset(&args
, 0, sizeof(args
));
492 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
494 sk
->min_objectid
= BTRFS_UUID_TREE_OBJECTID
;
495 sk
->max_objectid
= BTRFS_UUID_TREE_OBJECTID
;
496 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
497 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
498 sk
->max_offset
= (u64
)-1;
499 sk
->max_transid
= (u64
)-1;
502 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
506 /* the ioctl returns the number of item it found in nr_items */
507 if (sk
->nr_items
== 0)
514 * this function is mainly used to read all root items
515 * it will be only used when we use older kernel which uuid
516 * tree is not supported yet
518 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
521 struct btrfs_ioctl_search_args args
;
522 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
523 struct btrfs_ioctl_search_header
*sh
;
524 struct btrfs_root_item
*root_item_ptr
;
525 struct btrfs_root_item root_item
;
526 struct subvol_info
*si
= NULL
;
527 int root_item_valid
= 0;
528 unsigned long off
= 0;
535 s
->root_id_subvols
= RB_ROOT
;
536 s
->local_subvols
= RB_ROOT
;
537 s
->received_subvols
= RB_ROOT
;
538 s
->path_subvols
= RB_ROOT
;
540 ret
= is_uuid_tree_supported(mnt_fd
);
543 "ERROR: check if we support uuid tree fails- %s\n",
547 /* uuid tree is supported */
548 s
->uuid_tree_existed
= 1;
551 memset(&args
, 0, sizeof(args
));
553 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
555 sk
->max_objectid
= (u64
)-1;
556 sk
->max_offset
= (u64
)-1;
557 sk
->max_transid
= (u64
)-1;
558 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
559 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
563 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
566 fprintf(stderr
, "ERROR: can't perform the search- %s\n",
570 if (sk
->nr_items
== 0)
575 for (i
= 0; i
< sk
->nr_items
; i
++) {
576 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
580 if ((sh
->objectid
!= 5 &&
581 sh
->objectid
< BTRFS_FIRST_FREE_OBJECTID
) ||
582 sh
->objectid
> BTRFS_LAST_FREE_OBJECTID
)
585 if (sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
586 /* older kernels don't have uuids+times */
587 if (sh
->len
< sizeof(root_item
)) {
591 root_item_ptr
= (struct btrfs_root_item
*)
593 memcpy(&root_item
, root_item_ptr
,
596 } else if (sh
->type
== BTRFS_ROOT_BACKREF_KEY
||
598 if (!root_item_valid
)
601 path
= btrfs_list_path_for_root(mnt_fd
,
607 fprintf(stderr
, "ERROR: unable to "
614 si
= calloc(1, sizeof(*si
));
615 si
->root_id
= sh
->objectid
;
616 memcpy(si
->uuid
, root_item
.uuid
,
618 memcpy(si
->parent_uuid
, root_item
.parent_uuid
,
620 memcpy(si
->received_uuid
,
621 root_item
.received_uuid
,
623 si
->ctransid
= btrfs_root_ctransid(&root_item
);
624 si
->otransid
= btrfs_root_otransid(&root_item
);
625 si
->stransid
= btrfs_root_stransid(&root_item
);
626 si
->rtransid
= btrfs_root_rtransid(&root_item
);
628 subvol_uuid_search_add(s
, si
);
638 * record the mins in sk so we can make sure the
639 * next search doesn't repeat this root
641 sk
->min_objectid
= sh
->objectid
;
642 sk
->min_offset
= sh
->offset
;
643 sk
->min_type
= sh
->type
;
646 if (sk
->min_offset
< (u64
)-1)
648 else if (sk
->min_objectid
< (u64
)-1) {
660 void subvol_uuid_search_finit(struct subvol_uuid_search
*s
)
662 struct rb_root
*root
= &s
->root_id_subvols
;
663 struct rb_node
*node
;
665 if (!s
->uuid_tree_existed
)
668 while ((node
= rb_first(root
))) {
669 struct subvol_info
*entry
=
670 rb_entry(node
, struct subvol_info
, rb_root_id_node
);
673 rb_erase(node
, root
);
677 s
->root_id_subvols
= RB_ROOT
;
678 s
->local_subvols
= RB_ROOT
;
679 s
->received_subvols
= RB_ROOT
;
680 s
->path_subvols
= RB_ROOT
;
683 char *path_cat(const char *p1
, const char *p2
)
685 int p1_len
= strlen(p1
);
686 int p2_len
= strlen(p2
);
687 char *new = malloc(p1_len
+ p2_len
+ 2);
689 if (p1_len
&& p1
[p1_len
- 1] == '/')
691 if (p2_len
&& p2
[p2_len
- 1] == '/')
693 sprintf(new, "%.*s/%.*s", p1_len
, p1
, p2_len
, p2
);
697 char *path_cat3(const char *p1
, const char *p2
, const char *p3
)
699 int p1_len
= strlen(p1
);
700 int p2_len
= strlen(p2
);
701 int p3_len
= strlen(p3
);
702 char *new = malloc(p1_len
+ p2_len
+ p3_len
+ 3);
704 if (p1_len
&& p1
[p1_len
- 1] == '/')
706 if (p2_len
&& p2
[p2_len
- 1] == '/')
708 if (p3_len
&& p3
[p3_len
- 1] == '/')
710 sprintf(new, "%.*s/%.*s/%.*s", p1_len
, p1
, p2_len
, p2
, p3_len
, p3
);