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 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
163 static struct rb_node
*tree_insert(struct rb_root
*root
,
164 struct subvol_info
*si
,
165 enum subvol_search_type type
)
167 struct rb_node
**p
= &root
->rb_node
;
168 struct rb_node
*parent
= NULL
;
169 struct subvol_info
*entry
;
174 if (type
== subvol_search_by_received_uuid
) {
175 entry
= rb_entry(parent
, struct subvol_info
,
178 comp
= memcmp(entry
->received_uuid
, si
->received_uuid
,
181 if (entry
->stransid
< si
->stransid
)
183 else if (entry
->stransid
> si
->stransid
)
188 } else if (type
== subvol_search_by_uuid
) {
189 entry
= rb_entry(parent
, struct subvol_info
,
191 comp
= memcmp(entry
->uuid
, si
->uuid
, BTRFS_UUID_SIZE
);
192 } else if (type
== subvol_search_by_root_id
) {
193 entry
= rb_entry(parent
, struct subvol_info
,
195 comp
= entry
->root_id
- si
->root_id
;
196 } else if (type
== subvol_search_by_path
) {
197 entry
= rb_entry(parent
, struct subvol_info
,
199 comp
= strcmp(entry
->path
, si
->path
);
212 if (type
== subvol_search_by_received_uuid
) {
213 rb_link_node(&si
->rb_received_node
, parent
, p
);
214 rb_insert_color(&si
->rb_received_node
, root
);
215 } else if (type
== subvol_search_by_uuid
) {
216 rb_link_node(&si
->rb_local_node
, parent
, p
);
217 rb_insert_color(&si
->rb_local_node
, root
);
218 } else if (type
== subvol_search_by_root_id
) {
219 rb_link_node(&si
->rb_root_id_node
, parent
, p
);
220 rb_insert_color(&si
->rb_root_id_node
, root
);
221 } else if (type
== subvol_search_by_path
) {
222 rb_link_node(&si
->rb_path_node
, parent
, p
);
223 rb_insert_color(&si
->rb_path_node
, root
);
229 int btrfs_subvolid_resolve(int fd
, char *path
, size_t path_len
, u64 subvol_id
)
235 path
[path_len
] = '\0';
236 return btrfs_subvolid_resolve_sub(fd
, path
, &path_len
, subvol_id
);
239 static int btrfs_subvolid_resolve_sub(int fd
, char *path
, size_t *path_len
,
243 struct btrfs_ioctl_search_args search_arg
;
244 struct btrfs_ioctl_ino_lookup_args ino_lookup_arg
;
245 struct btrfs_ioctl_search_header
*search_header
;
246 struct btrfs_root_ref
*backref_item
;
248 if (subvol_id
== BTRFS_FS_TREE_OBJECTID
) {
256 memset(&search_arg
, 0, sizeof(search_arg
));
257 search_arg
.key
.tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
258 search_arg
.key
.min_objectid
= subvol_id
;
259 search_arg
.key
.max_objectid
= subvol_id
;
260 search_arg
.key
.min_type
= BTRFS_ROOT_BACKREF_KEY
;
261 search_arg
.key
.max_type
= BTRFS_ROOT_BACKREF_KEY
;
262 search_arg
.key
.max_offset
= (u64
)-1;
263 search_arg
.key
.max_transid
= (u64
)-1;
264 search_arg
.key
.nr_items
= 1;
265 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &search_arg
);
268 "ioctl(BTRFS_IOC_TREE_SEARCH, subvol_id %llu) ret=%d, error: %s\n",
269 (unsigned long long)subvol_id
, ret
, strerror(errno
));
273 if (search_arg
.key
.nr_items
< 1) {
275 "failed to lookup subvol_id %llu!\n",
276 (unsigned long long)subvol_id
);
279 search_header
= (struct btrfs_ioctl_search_header
*)search_arg
.buf
;
280 backref_item
= (struct btrfs_root_ref
*)(search_header
+ 1);
281 if (search_header
->offset
!= BTRFS_FS_TREE_OBJECTID
) {
284 sub_ret
= btrfs_subvolid_resolve_sub(fd
, path
, path_len
,
285 search_header
->offset
);
294 if (btrfs_stack_root_ref_dirid(backref_item
) !=
295 BTRFS_FIRST_FREE_OBJECTID
) {
298 memset(&ino_lookup_arg
, 0, sizeof(ino_lookup_arg
));
299 ino_lookup_arg
.treeid
= search_header
->offset
;
300 ino_lookup_arg
.objectid
=
301 btrfs_stack_root_ref_dirid(backref_item
);
302 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_lookup_arg
);
305 "ioctl(BTRFS_IOC_INO_LOOKUP) ret=%d, error: %s\n",
306 ret
, strerror(errno
));
310 len
= strlen(ino_lookup_arg
.name
);
313 strcat(path
, ino_lookup_arg
.name
);
317 if (*path_len
< btrfs_stack_root_ref_name_len(backref_item
))
319 strncat(path
, (char *)(backref_item
+ 1),
320 btrfs_stack_root_ref_name_len(backref_item
));
321 (*path_len
) -= btrfs_stack_root_ref_name_len(backref_item
);
325 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
326 static int count_bytes(void *buf
, int len
, char b
)
331 for (i
= 0; i
< len
; i
++) {
332 if (((char *)buf
)[i
] == b
)
338 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
339 struct subvol_info
*si
)
343 tree_insert(&s
->root_id_subvols
, si
, subvol_search_by_root_id
);
344 tree_insert(&s
->path_subvols
, si
, subvol_search_by_path
);
346 cnt
= count_bytes(si
->uuid
, BTRFS_UUID_SIZE
, 0);
347 if (cnt
!= BTRFS_UUID_SIZE
)
348 tree_insert(&s
->local_subvols
, si
, subvol_search_by_uuid
);
349 cnt
= count_bytes(si
->received_uuid
, BTRFS_UUID_SIZE
, 0);
350 if (cnt
!= BTRFS_UUID_SIZE
)
351 tree_insert(&s
->received_subvols
, si
,
352 subvol_search_by_received_uuid
);
355 static struct subvol_info
*tree_search(struct rb_root
*root
,
356 u64 root_id
, const u8
*uuid
,
357 u64 stransid
, const char *path
,
358 enum subvol_search_type type
)
360 struct rb_node
*n
= root
->rb_node
;
361 struct subvol_info
*entry
;
365 if (type
== subvol_search_by_received_uuid
) {
366 entry
= rb_entry(n
, struct subvol_info
,
368 comp
= memcmp(entry
->received_uuid
, uuid
,
371 if (entry
->stransid
< stransid
)
373 else if (entry
->stransid
> stransid
)
378 } else if (type
== subvol_search_by_uuid
) {
379 entry
= rb_entry(n
, struct subvol_info
, rb_local_node
);
380 comp
= memcmp(entry
->uuid
, uuid
, BTRFS_UUID_SIZE
);
381 } else if (type
== subvol_search_by_root_id
) {
382 entry
= rb_entry(n
, struct subvol_info
,
384 comp
= entry
->root_id
- root_id
;
385 } else if (type
== subvol_search_by_path
) {
386 entry
= rb_entry(n
, struct subvol_info
, rb_path_node
);
387 comp
= strcmp(entry
->path
, path
);
402 * this function will be only called if kernel dosen't support uuid tree.
404 static struct subvol_info
*subvol_uuid_search_old(struct subvol_uuid_search
*s
,
405 u64 root_id
, const u8
*uuid
, u64 transid
,
407 enum subvol_search_type type
)
409 struct rb_root
*root
;
410 if (type
== subvol_search_by_received_uuid
)
411 root
= &s
->received_subvols
;
412 else if (type
== subvol_search_by_uuid
)
413 root
= &s
->local_subvols
;
414 else if (type
== subvol_search_by_root_id
)
415 root
= &s
->root_id_subvols
;
416 else if (type
== subvol_search_by_path
)
417 root
= &s
->path_subvols
;
420 return tree_search(root
, root_id
, uuid
, transid
, path
, type
);
423 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
424 struct subvol_info
*si
)
433 struct subvol_info
*subvol_uuid_search(struct subvol_uuid_search
*s
,
434 u64 root_id
, const u8
*uuid
, u64 transid
,
436 enum subvol_search_type type
)
439 struct btrfs_root_item root_item
;
440 struct subvol_info
*info
= NULL
;
442 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
443 if (!s
->uuid_tree_existed
)
444 return subvol_uuid_search_old(s
, root_id
, uuid
, transid
,
448 case subvol_search_by_received_uuid
:
449 ret
= btrfs_lookup_uuid_received_subvol_item(s
->mnt_fd
, uuid
,
452 case subvol_search_by_uuid
:
453 ret
= btrfs_lookup_uuid_subvol_item(s
->mnt_fd
, uuid
, &root_id
);
455 case subvol_search_by_root_id
:
457 case subvol_search_by_path
:
458 ret
= btrfs_get_root_id_by_sub_path(s
->mnt_fd
, path
, &root_id
);
468 ret
= btrfs_read_root_item(s
->mnt_fd
, root_id
, &root_item
);
472 info
= calloc(1, sizeof(*info
));
473 info
->root_id
= root_id
;
474 memcpy(info
->uuid
, root_item
.uuid
, BTRFS_UUID_SIZE
);
475 memcpy(info
->received_uuid
, root_item
.received_uuid
, BTRFS_UUID_SIZE
);
476 memcpy(info
->parent_uuid
, root_item
.parent_uuid
, BTRFS_UUID_SIZE
);
477 info
->ctransid
= btrfs_root_ctransid(&root_item
);
478 info
->otransid
= btrfs_root_otransid(&root_item
);
479 info
->stransid
= btrfs_root_stransid(&root_item
);
480 info
->rtransid
= btrfs_root_rtransid(&root_item
);
481 if (type
== subvol_search_by_path
) {
482 info
->path
= strdup(path
);
484 info
->path
= malloc(BTRFS_PATH_NAME_MAX
);
485 ret
= btrfs_subvolid_resolve(s
->mnt_fd
, info
->path
,
486 BTRFS_PATH_NAME_MAX
, root_id
);
499 #ifdef BTRFS_COMPAT_SEND_NO_UUID_TREE
500 static int is_uuid_tree_supported(int fd
)
503 struct btrfs_ioctl_search_args args
;
504 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
506 memset(&args
, 0, sizeof(args
));
508 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
510 sk
->min_objectid
= BTRFS_UUID_TREE_OBJECTID
;
511 sk
->max_objectid
= BTRFS_UUID_TREE_OBJECTID
;
512 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
513 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
514 sk
->max_offset
= (u64
)-1;
515 sk
->max_transid
= (u64
)-1;
518 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
522 /* the ioctl returns the number of item it found in nr_items */
523 if (sk
->nr_items
== 0)
530 * this function is mainly used to read all root items
531 * it will be only used when we use older kernel which uuid
532 * tree is not supported yet
534 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
537 struct btrfs_ioctl_search_args args
;
538 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
539 struct btrfs_ioctl_search_header
*sh
;
540 struct btrfs_root_item
*root_item_ptr
;
541 struct btrfs_root_item root_item
= {};
542 struct subvol_info
*si
= NULL
;
543 int root_item_valid
= 0;
544 unsigned long off
= 0;
551 s
->root_id_subvols
= RB_ROOT
;
552 s
->local_subvols
= RB_ROOT
;
553 s
->received_subvols
= RB_ROOT
;
554 s
->path_subvols
= RB_ROOT
;
556 ret
= is_uuid_tree_supported(mnt_fd
);
559 "ERROR: check if we support uuid tree fails - %s\n",
563 /* uuid tree is supported */
564 s
->uuid_tree_existed
= 1;
567 memset(&args
, 0, sizeof(args
));
569 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
571 sk
->max_objectid
= (u64
)-1;
572 sk
->max_offset
= (u64
)-1;
573 sk
->max_transid
= (u64
)-1;
574 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
575 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
579 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
582 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
586 if (sk
->nr_items
== 0)
591 for (i
= 0; i
< sk
->nr_items
; i
++) {
592 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
596 if ((sh
->objectid
!= 5 &&
597 sh
->objectid
< BTRFS_FIRST_FREE_OBJECTID
) ||
598 sh
->objectid
> BTRFS_LAST_FREE_OBJECTID
)
601 if (sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
602 /* older kernels don't have uuids+times */
603 if (sh
->len
< sizeof(root_item
)) {
607 root_item_ptr
= (struct btrfs_root_item
*)
609 memcpy(&root_item
, root_item_ptr
,
612 } else if (sh
->type
== BTRFS_ROOT_BACKREF_KEY
||
614 if (!root_item_valid
)
617 path
= btrfs_list_path_for_root(mnt_fd
,
623 fprintf(stderr
, "ERROR: unable to "
630 si
= calloc(1, sizeof(*si
));
631 si
->root_id
= sh
->objectid
;
632 memcpy(si
->uuid
, root_item
.uuid
,
634 memcpy(si
->parent_uuid
, root_item
.parent_uuid
,
636 memcpy(si
->received_uuid
,
637 root_item
.received_uuid
,
639 si
->ctransid
= btrfs_root_ctransid(&root_item
);
640 si
->otransid
= btrfs_root_otransid(&root_item
);
641 si
->stransid
= btrfs_root_stransid(&root_item
);
642 si
->rtransid
= btrfs_root_rtransid(&root_item
);
644 subvol_uuid_search_add(s
, si
);
654 * record the mins in sk so we can make sure the
655 * next search doesn't repeat this root
657 sk
->min_objectid
= sh
->objectid
;
658 sk
->min_offset
= sh
->offset
;
659 sk
->min_type
= sh
->type
;
662 if (sk
->min_offset
< (u64
)-1)
664 else if (sk
->min_objectid
< (u64
)-1) {
676 void subvol_uuid_search_finit(struct subvol_uuid_search
*s
)
678 struct rb_root
*root
= &s
->root_id_subvols
;
679 struct rb_node
*node
;
681 if (!s
->uuid_tree_existed
)
684 while ((node
= rb_first(root
))) {
685 struct subvol_info
*entry
=
686 rb_entry(node
, struct subvol_info
, rb_root_id_node
);
689 rb_erase(node
, root
);
693 s
->root_id_subvols
= RB_ROOT
;
694 s
->local_subvols
= RB_ROOT
;
695 s
->received_subvols
= RB_ROOT
;
696 s
->path_subvols
= RB_ROOT
;
699 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
706 void subvol_uuid_search_finit(struct subvol_uuid_search
*s
)
711 char *path_cat(const char *p1
, const char *p2
)
713 int p1_len
= strlen(p1
);
714 int p2_len
= strlen(p2
);
715 char *new = malloc(p1_len
+ p2_len
+ 2);
717 if (p1_len
&& p1
[p1_len
- 1] == '/')
719 if (p2_len
&& p2
[p2_len
- 1] == '/')
721 sprintf(new, "%.*s/%.*s", p1_len
, p1
, p2_len
, p2
);
725 char *path_cat3(const char *p1
, const char *p2
, const char *p3
)
727 int p1_len
= strlen(p1
);
728 int p2_len
= strlen(p2
);
729 int p3_len
= strlen(p3
);
730 char *new = malloc(p1_len
+ p2_len
+ p3_len
+ 3);
732 if (p1_len
&& p1
[p1_len
- 1] == '/')
734 if (p2_len
&& p2
[p2_len
- 1] == '/')
736 if (p3_len
&& p3
[p3_len
- 1] == '/')
738 sprintf(new, "%.*s/%.*s/%.*s", p1_len
, p1
, p2_len
, p2
, p3_len
, p3
);