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>
27 #include "send-utils.h"
29 #include "btrfs-list.h"
31 static int btrfs_subvolid_resolve_sub(int fd
, char *path
, size_t *path_len
,
34 static int btrfs_get_root_id_by_sub_path(int mnt_fd
, const char *sub_path
,
40 subvol_fd
= openat(mnt_fd
, sub_path
, O_RDONLY
);
43 fprintf(stderr
, "ERROR: open %s failed. %s\n", sub_path
,
48 ret
= btrfs_list_get_path_rootid(subvol_fd
, root_id
);
53 static int btrfs_read_root_item_raw(int mnt_fd
, u64 root_id
, size_t buf_len
,
54 u32
*read_len
, void *buf
)
57 struct btrfs_ioctl_search_args args
;
58 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
59 struct btrfs_ioctl_search_header
*sh
;
60 unsigned long off
= 0;
65 memset(&args
, 0, sizeof(args
));
67 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
70 * there may be more than one ROOT_ITEM key if there are
71 * snapshots pending deletion, we have to loop through
74 sk
->min_objectid
= root_id
;
75 sk
->max_objectid
= root_id
;
76 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
77 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
78 sk
->max_offset
= (u64
)-1;
79 sk
->max_transid
= (u64
)-1;
83 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
86 "ERROR: can't perform the search - %s\n",
90 /* the ioctl returns the number of item it found in nr_items */
91 if (sk
->nr_items
== 0)
95 for (i
= 0; i
< sk
->nr_items
; i
++) {
96 struct btrfs_root_item
*item
;
97 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
101 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
102 off
+= btrfs_search_header_len(sh
);
104 sk
->min_objectid
= btrfs_search_header_objectid(sh
);
105 sk
->min_type
= btrfs_search_header_type(sh
);
106 sk
->min_offset
= btrfs_search_header_offset(sh
);
108 if (btrfs_search_header_objectid(sh
) > root_id
)
111 if (btrfs_search_header_objectid(sh
) == root_id
&&
112 btrfs_search_header_type(sh
) == BTRFS_ROOT_ITEM_KEY
) {
113 if (btrfs_search_header_len(sh
) > buf_len
) {
114 /* btrfs-progs is too old for kernel */
116 "ERROR: buf for read_root_item_raw() is too small, get newer btrfs tools!\n");
119 memcpy(buf
, item
, btrfs_search_header_len(sh
));
120 *read_len
= btrfs_search_header_len(sh
);
124 if (sk
->min_offset
< (u64
)-1)
129 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
||
130 sk
->min_objectid
!= root_id
)
134 return found
? 0 : -ENOENT
;
138 * Read a root item from the tree. In case we detect a root item smaller then
139 * sizeof(root_item), we know it's an old version of the root structure and
140 * initialize all new fields to zero. The same happens if we detect mismatching
141 * generation numbers as then we know the root was once mounted with an older
142 * kernel that was not aware of the root item structure change.
144 static int btrfs_read_root_item(int mnt_fd
, u64 root_id
,
145 struct btrfs_root_item
*item
)
150 ret
= btrfs_read_root_item_raw(mnt_fd
, root_id
, sizeof(*item
),
155 if (read_len
< sizeof(*item
) ||
156 btrfs_root_generation(item
) != btrfs_root_generation_v2(item
))
157 memset(&item
->generation_v2
, 0,
158 sizeof(*item
) - offsetof(struct btrfs_root_item
,
164 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
165 static struct rb_node
*tree_insert(struct rb_root
*root
,
166 struct subvol_info
*si
,
167 enum subvol_search_type type
)
169 struct rb_node
**p
= &root
->rb_node
;
170 struct rb_node
*parent
= NULL
;
171 struct subvol_info
*entry
;
176 if (type
== subvol_search_by_received_uuid
) {
177 entry
= rb_entry(parent
, struct subvol_info
,
180 comp
= memcmp(entry
->received_uuid
, si
->received_uuid
,
183 if (entry
->stransid
< si
->stransid
)
185 else if (entry
->stransid
> si
->stransid
)
190 } else if (type
== subvol_search_by_uuid
) {
191 entry
= rb_entry(parent
, struct subvol_info
,
193 comp
= memcmp(entry
->uuid
, si
->uuid
, BTRFS_UUID_SIZE
);
194 } else if (type
== subvol_search_by_root_id
) {
195 entry
= rb_entry(parent
, struct subvol_info
,
197 comp
= entry
->root_id
- si
->root_id
;
198 } else if (type
== subvol_search_by_path
) {
199 entry
= rb_entry(parent
, struct subvol_info
,
201 comp
= strcmp(entry
->path
, si
->path
);
214 if (type
== subvol_search_by_received_uuid
) {
215 rb_link_node(&si
->rb_received_node
, parent
, p
);
216 rb_insert_color(&si
->rb_received_node
, root
);
217 } else if (type
== subvol_search_by_uuid
) {
218 rb_link_node(&si
->rb_local_node
, parent
, p
);
219 rb_insert_color(&si
->rb_local_node
, root
);
220 } else if (type
== subvol_search_by_root_id
) {
221 rb_link_node(&si
->rb_root_id_node
, parent
, p
);
222 rb_insert_color(&si
->rb_root_id_node
, root
);
223 } else if (type
== subvol_search_by_path
) {
224 rb_link_node(&si
->rb_path_node
, parent
, p
);
225 rb_insert_color(&si
->rb_path_node
, root
);
231 int btrfs_subvolid_resolve(int fd
, char *path
, size_t path_len
, u64 subvol_id
)
237 path
[path_len
] = '\0';
238 return btrfs_subvolid_resolve_sub(fd
, path
, &path_len
, subvol_id
);
241 static int btrfs_subvolid_resolve_sub(int fd
, char *path
, size_t *path_len
,
245 struct btrfs_ioctl_search_args search_arg
;
246 struct btrfs_ioctl_ino_lookup_args ino_lookup_arg
;
247 struct btrfs_ioctl_search_header
*search_header
;
248 struct btrfs_root_ref
*backref_item
;
250 if (subvol_id
== BTRFS_FS_TREE_OBJECTID
) {
258 memset(&search_arg
, 0, sizeof(search_arg
));
259 search_arg
.key
.tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
260 search_arg
.key
.min_objectid
= subvol_id
;
261 search_arg
.key
.max_objectid
= subvol_id
;
262 search_arg
.key
.min_type
= BTRFS_ROOT_BACKREF_KEY
;
263 search_arg
.key
.max_type
= BTRFS_ROOT_BACKREF_KEY
;
264 search_arg
.key
.max_offset
= (u64
)-1;
265 search_arg
.key
.max_transid
= (u64
)-1;
266 search_arg
.key
.nr_items
= 1;
267 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &search_arg
);
270 "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
271 (unsigned long long)subvol_id
, ret
, strerror(errno
));
275 if (search_arg
.key
.nr_items
< 1) {
277 "failed to lookup subvol_id %llu!\n",
278 (unsigned long long)subvol_id
);
281 search_header
= (struct btrfs_ioctl_search_header
*)search_arg
.buf
;
282 backref_item
= (struct btrfs_root_ref
*)(search_header
+ 1);
283 if (btrfs_search_header_offset(search_header
)
284 != BTRFS_FS_TREE_OBJECTID
) {
287 sub_ret
= btrfs_subvolid_resolve_sub(fd
, path
, path_len
,
288 btrfs_search_header_offset(search_header
));
297 if (btrfs_stack_root_ref_dirid(backref_item
) !=
298 BTRFS_FIRST_FREE_OBJECTID
) {
301 memset(&ino_lookup_arg
, 0, sizeof(ino_lookup_arg
));
302 ino_lookup_arg
.treeid
=
303 btrfs_search_header_offset(search_header
);
304 ino_lookup_arg
.objectid
=
305 btrfs_stack_root_ref_dirid(backref_item
);
306 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_lookup_arg
);
309 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
310 ret
, strerror(errno
));
314 len
= strlen(ino_lookup_arg
.name
);
317 strcat(path
, ino_lookup_arg
.name
);
321 if (*path_len
< btrfs_stack_root_ref_name_len(backref_item
))
323 strncat(path
, (char *)(backref_item
+ 1),
324 btrfs_stack_root_ref_name_len(backref_item
));
325 (*path_len
) -= btrfs_stack_root_ref_name_len(backref_item
);
329 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
330 static int count_bytes(void *buf
, int len
, char b
)
335 for (i
= 0; i
< len
; i
++) {
336 if (((char *)buf
)[i
] == b
)
342 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
343 struct subvol_info
*si
)
347 tree_insert(&s
->root_id_subvols
, si
, subvol_search_by_root_id
);
348 tree_insert(&s
->path_subvols
, si
, subvol_search_by_path
);
350 cnt
= count_bytes(si
->uuid
, BTRFS_UUID_SIZE
, 0);
351 if (cnt
!= BTRFS_UUID_SIZE
)
352 tree_insert(&s
->local_subvols
, si
, subvol_search_by_uuid
);
353 cnt
= count_bytes(si
->received_uuid
, BTRFS_UUID_SIZE
, 0);
354 if (cnt
!= BTRFS_UUID_SIZE
)
355 tree_insert(&s
->received_subvols
, si
,
356 subvol_search_by_received_uuid
);
359 static struct subvol_info
*tree_search(struct rb_root
*root
,
360 u64 root_id
, const u8
*uuid
,
361 u64 stransid
, const char *path
,
362 enum subvol_search_type type
)
364 struct rb_node
*n
= root
->rb_node
;
365 struct subvol_info
*entry
;
369 if (type
== subvol_search_by_received_uuid
) {
370 entry
= rb_entry(n
, struct subvol_info
,
372 comp
= memcmp(entry
->received_uuid
, uuid
,
375 if (entry
->stransid
< stransid
)
377 else if (entry
->stransid
> stransid
)
382 } else if (type
== subvol_search_by_uuid
) {
383 entry
= rb_entry(n
, struct subvol_info
, rb_local_node
);
384 comp
= memcmp(entry
->uuid
, uuid
, BTRFS_UUID_SIZE
);
385 } else if (type
== subvol_search_by_root_id
) {
386 entry
= rb_entry(n
, struct subvol_info
,
388 comp
= entry
->root_id
- root_id
;
389 } else if (type
== subvol_search_by_path
) {
390 entry
= rb_entry(n
, struct subvol_info
, rb_path_node
);
391 comp
= strcmp(entry
->path
, path
);
406 * this function will be only called if kernel doesn't support uuid tree.
408 static struct subvol_info
*subvol_uuid_search_old(struct subvol_uuid_search
*s
,
409 u64 root_id
, const u8
*uuid
, u64 transid
,
411 enum subvol_search_type type
)
413 struct rb_root
*root
;
414 if (type
== subvol_search_by_received_uuid
)
415 root
= &s
->received_subvols
;
416 else if (type
== subvol_search_by_uuid
)
417 root
= &s
->local_subvols
;
418 else if (type
== subvol_search_by_root_id
)
419 root
= &s
->root_id_subvols
;
420 else if (type
== subvol_search_by_path
)
421 root
= &s
->path_subvols
;
424 return tree_search(root
, root_id
, uuid
, transid
, path
, type
);
427 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
428 struct subvol_info
*si
)
437 struct subvol_info
*subvol_uuid_search(struct subvol_uuid_search
*s
,
438 u64 root_id
, const u8
*uuid
, u64 transid
,
440 enum subvol_search_type type
)
443 struct btrfs_root_item root_item
;
444 struct subvol_info
*info
= NULL
;
446 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
447 if (!s
->uuid_tree_existed
)
448 return subvol_uuid_search_old(s
, root_id
, uuid
, transid
,
452 case subvol_search_by_received_uuid
:
453 ret
= btrfs_lookup_uuid_received_subvol_item(s
->mnt_fd
, uuid
,
456 case subvol_search_by_uuid
:
457 ret
= btrfs_lookup_uuid_subvol_item(s
->mnt_fd
, uuid
, &root_id
);
459 case subvol_search_by_root_id
:
461 case subvol_search_by_path
:
462 ret
= btrfs_get_root_id_by_sub_path(s
->mnt_fd
, path
, &root_id
);
472 ret
= btrfs_read_root_item(s
->mnt_fd
, root_id
, &root_item
);
476 info
= calloc(1, sizeof(*info
));
477 info
->root_id
= root_id
;
478 memcpy(info
->uuid
, root_item
.uuid
, BTRFS_UUID_SIZE
);
479 memcpy(info
->received_uuid
, root_item
.received_uuid
, BTRFS_UUID_SIZE
);
480 memcpy(info
->parent_uuid
, root_item
.parent_uuid
, BTRFS_UUID_SIZE
);
481 info
->ctransid
= btrfs_root_ctransid(&root_item
);
482 info
->otransid
= btrfs_root_otransid(&root_item
);
483 info
->stransid
= btrfs_root_stransid(&root_item
);
484 info
->rtransid
= btrfs_root_rtransid(&root_item
);
485 if (type
== subvol_search_by_path
) {
486 info
->path
= strdup(path
);
488 info
->path
= malloc(PATH_MAX
);
489 ret
= btrfs_subvolid_resolve(s
->mnt_fd
, info
->path
,
503 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
504 static int is_uuid_tree_supported(int fd
)
507 struct btrfs_ioctl_search_args args
;
508 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
510 memset(&args
, 0, sizeof(args
));
512 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
514 sk
->min_objectid
= BTRFS_UUID_TREE_OBJECTID
;
515 sk
->max_objectid
= BTRFS_UUID_TREE_OBJECTID
;
516 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
517 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
518 sk
->max_offset
= (u64
)-1;
519 sk
->max_transid
= (u64
)-1;
522 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
526 /* the ioctl returns the number of item it found in nr_items */
527 if (sk
->nr_items
== 0)
534 * this function is mainly used to read all root items
535 * it will be only used when we use older kernel which uuid
536 * tree is not supported yet
538 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
541 struct btrfs_ioctl_search_args args
;
542 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
543 struct btrfs_ioctl_search_header
*sh
;
544 struct btrfs_root_item
*root_item_ptr
;
545 struct btrfs_root_item root_item
= {};
546 struct subvol_info
*si
= NULL
;
547 int root_item_valid
= 0;
548 unsigned long off
= 0;
554 s
->root_id_subvols
= RB_ROOT
;
555 s
->local_subvols
= RB_ROOT
;
556 s
->received_subvols
= RB_ROOT
;
557 s
->path_subvols
= RB_ROOT
;
559 ret
= is_uuid_tree_supported(mnt_fd
);
562 "ERROR: check if we support uuid tree fails - %s\n",
566 /* uuid tree is supported */
567 s
->uuid_tree_existed
= 1;
570 memset(&args
, 0, sizeof(args
));
572 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
574 sk
->max_objectid
= (u64
)-1;
575 sk
->max_offset
= (u64
)-1;
576 sk
->max_transid
= (u64
)-1;
577 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
578 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
582 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
584 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
588 if (sk
->nr_items
== 0)
593 for (i
= 0; i
< sk
->nr_items
; i
++) {
594 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
598 if ((btrfs_search_header_objectid(sh
) != 5 &&
599 btrfs_search_header_objectid(sh
)
600 < BTRFS_FIRST_FREE_OBJECTID
) ||
601 btrfs_search_header_objectid(sh
)
602 > BTRFS_LAST_FREE_OBJECTID
) {
606 if (btrfs_search_header_type(sh
)
607 == BTRFS_ROOT_ITEM_KEY
) {
608 /* older kernels don't have uuids+times */
609 if (btrfs_search_header_len(sh
)
610 < sizeof(root_item
)) {
614 root_item_ptr
= (struct btrfs_root_item
*)
616 memcpy(&root_item
, root_item_ptr
,
619 } else if (btrfs_search_header_type(sh
)
620 == BTRFS_ROOT_BACKREF_KEY
||
622 if (!root_item_valid
)
625 path
= btrfs_list_path_for_root(mnt_fd
,
626 btrfs_search_header_objectid(sh
));
631 fprintf(stderr
, "ERROR: unable to "
634 btrfs_search_header_objectid(sh
));
638 si
= calloc(1, sizeof(*si
));
639 si
->root_id
= btrfs_search_header_objectid(sh
);
640 memcpy(si
->uuid
, root_item
.uuid
,
642 memcpy(si
->parent_uuid
, root_item
.parent_uuid
,
644 memcpy(si
->received_uuid
,
645 root_item
.received_uuid
,
647 si
->ctransid
= btrfs_root_ctransid(&root_item
);
648 si
->otransid
= btrfs_root_otransid(&root_item
);
649 si
->stransid
= btrfs_root_stransid(&root_item
);
650 si
->rtransid
= btrfs_root_rtransid(&root_item
);
652 subvol_uuid_search_add(s
, si
);
659 off
+= btrfs_search_header_len(sh
);
662 * record the mins in sk so we can make sure the
663 * next search doesn't repeat this root
665 sk
->min_objectid
= btrfs_search_header_objectid(sh
);
666 sk
->min_offset
= btrfs_search_header_offset(sh
);
667 sk
->min_type
= btrfs_search_header_type(sh
);
670 if (sk
->min_offset
< (u64
)-1)
672 else if (sk
->min_objectid
< (u64
)-1) {
684 void subvol_uuid_search_finit(struct subvol_uuid_search
*s
)
686 struct rb_root
*root
= &s
->root_id_subvols
;
687 struct rb_node
*node
;
689 if (!s
->uuid_tree_existed
)
692 while ((node
= rb_first(root
))) {
693 struct subvol_info
*entry
=
694 rb_entry(node
, struct subvol_info
, rb_root_id_node
);
697 rb_erase(node
, root
);
701 s
->root_id_subvols
= RB_ROOT
;
702 s
->local_subvols
= RB_ROOT
;
703 s
->received_subvols
= RB_ROOT
;
704 s
->path_subvols
= RB_ROOT
;
707 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
714 void subvol_uuid_search_finit(struct subvol_uuid_search
*s
)
719 int path_cat_out(char *out
, const char *p1
, const char *p2
)
721 int p1_len
= strlen(p1
);
722 int p2_len
= strlen(p2
);
724 if (p1_len
+ p2_len
+ 2 >= PATH_MAX
)
725 return -ENAMETOOLONG
;
727 if (p1_len
&& p1
[p1_len
- 1] == '/')
729 if (p2_len
&& p2
[p2_len
- 1] == '/')
731 sprintf(out
, "%.*s/%.*s", p1_len
, p1
, p2_len
, p2
);
736 __attribute__((deprecated
))
737 char *path_cat(const char *p1
, const char *p2
)
739 int p1_len
= strlen(p1
);
740 int p2_len
= strlen(p2
);
741 char *new = malloc(p1_len
+ p2_len
+ 2);
743 path_cat_out(new, p1
, p2
);
748 int path_cat3_out(char *out
, const char *p1
, const char *p2
, const char *p3
)
750 int p1_len
= strlen(p1
);
751 int p2_len
= strlen(p2
);
752 int p3_len
= strlen(p3
);
754 if (p1_len
+ p2_len
+ p3_len
+ 3 >= PATH_MAX
)
755 return -ENAMETOOLONG
;
757 if (p1_len
&& p1
[p1_len
- 1] == '/')
759 if (p2_len
&& p2
[p2_len
- 1] == '/')
761 if (p3_len
&& p3
[p3_len
- 1] == '/')
763 sprintf(out
, "%.*s/%.*s/%.*s", p1_len
, p1
, p2_len
, p2
, p3_len
, p3
);
768 __attribute__((deprecated
))
769 char *path_cat3(const char *p1
, const char *p2
, const char *p3
)
771 int p1_len
= strlen(p1
);
772 int p2_len
= strlen(p2
);
773 int p3_len
= strlen(p3
);
774 char *new = malloc(p1_len
+ p2_len
+ p3_len
+ 3);
776 path_cat3_out(new, p1
, p2
, p3
);