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.
19 #include <sys/ioctl.h>
22 #include "send-utils.h"
26 char *path_for_root(int fd
, u64 root
);
28 static struct rb_node
*tree_insert(struct rb_root
*root
,
29 struct subvol_info
*si
,
30 enum subvol_search_type type
)
32 struct rb_node
** p
= &root
->rb_node
;
33 struct rb_node
* parent
= NULL
;
34 struct subvol_info
*entry
;
39 if (type
== subvol_search_by_received_uuid
) {
40 entry
= rb_entry(parent
, struct subvol_info
,
43 comp
= memcmp(entry
->received_uuid
, si
->received_uuid
,
46 if (entry
->stransid
< si
->stransid
)
48 else if (entry
->stransid
> si
->stransid
)
53 } else if (type
== subvol_search_by_uuid
) {
54 entry
= rb_entry(parent
, struct subvol_info
,
56 comp
= memcmp(entry
->uuid
, si
->uuid
, BTRFS_UUID_SIZE
);
57 } else if (type
== subvol_search_by_root_id
) {
58 entry
= rb_entry(parent
, struct subvol_info
,
60 comp
= entry
->root_id
- si
->root_id
;
61 } else if (type
== subvol_search_by_path
) {
62 entry
= rb_entry(parent
, struct subvol_info
,
64 comp
= strcmp(entry
->path
, si
->path
);
75 if (type
== subvol_search_by_received_uuid
) {
76 rb_link_node(&si
->rb_received_node
, parent
, p
);
77 rb_insert_color(&si
->rb_received_node
, root
);
78 } else if (type
== subvol_search_by_uuid
) {
79 rb_link_node(&si
->rb_local_node
, parent
, p
);
80 rb_insert_color(&si
->rb_local_node
, root
);
81 } else if (type
== subvol_search_by_root_id
) {
82 rb_link_node(&si
->rb_root_id_node
, parent
, p
);
83 rb_insert_color(&si
->rb_root_id_node
, root
);
84 } else if (type
== subvol_search_by_path
) {
85 rb_link_node(&si
->rb_path_node
, parent
, p
);
86 rb_insert_color(&si
->rb_path_node
, root
);
91 static struct subvol_info
*tree_search(struct rb_root
*root
,
92 u64 root_id
, const u8
*uuid
,
93 u64 stransid
, const char *path
,
94 enum subvol_search_type type
)
96 struct rb_node
* n
= root
->rb_node
;
97 struct subvol_info
*entry
;
101 if (type
== subvol_search_by_received_uuid
) {
102 entry
= rb_entry(n
, struct subvol_info
,
104 comp
= memcmp(entry
->received_uuid
, uuid
,
107 if (entry
->stransid
< stransid
)
109 else if (entry
->stransid
> stransid
)
114 } else if (type
== subvol_search_by_uuid
) {
115 entry
= rb_entry(n
, struct subvol_info
, rb_local_node
);
116 comp
= memcmp(entry
->uuid
, uuid
, BTRFS_UUID_SIZE
);
117 } else if (type
== subvol_search_by_root_id
) {
118 entry
= rb_entry(n
, struct subvol_info
, rb_root_id_node
);
119 comp
= entry
->root_id
- root_id
;
120 } else if (type
== subvol_search_by_path
) {
121 entry
= rb_entry(n
, struct subvol_info
, rb_path_node
);
122 comp
= strcmp(entry
->path
, path
);
134 static int count_bytes(void *buf
, int len
, char b
)
138 for (i
= 0; i
< len
; i
++) {
139 if (((char*)buf
)[i
] == b
)
145 void subvol_uuid_search_add(struct subvol_uuid_search
*s
,
146 struct subvol_info
*si
)
150 tree_insert(&s
->root_id_subvols
, si
, subvol_search_by_root_id
);
151 tree_insert(&s
->path_subvols
, si
, subvol_search_by_path
);
153 cnt
= count_bytes(si
->uuid
, BTRFS_UUID_SIZE
, 0);
154 if (cnt
!= BTRFS_UUID_SIZE
)
155 tree_insert(&s
->local_subvols
, si
, subvol_search_by_uuid
);
156 cnt
= count_bytes(si
->received_uuid
, BTRFS_UUID_SIZE
, 0);
157 if (cnt
!= BTRFS_UUID_SIZE
)
158 tree_insert(&s
->received_subvols
, si
,
159 subvol_search_by_received_uuid
);
162 struct subvol_info
*subvol_uuid_search(struct subvol_uuid_search
*s
,
163 u64 root_id
, const u8
*uuid
, u64 transid
,
165 enum subvol_search_type type
)
167 struct rb_root
*root
;
168 if (type
== subvol_search_by_received_uuid
)
169 root
= &s
->received_subvols
;
170 else if (type
== subvol_search_by_uuid
)
171 root
= &s
->local_subvols
;
172 else if (type
== subvol_search_by_root_id
)
173 root
= &s
->root_id_subvols
;
174 else if (type
== subvol_search_by_path
)
175 root
= &s
->path_subvols
;
178 return tree_search(root
, root_id
, uuid
, transid
, path
, type
);
181 int subvol_uuid_search_init(int mnt_fd
, struct subvol_uuid_search
*s
)
184 struct btrfs_ioctl_search_args args
;
185 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
186 struct btrfs_ioctl_search_header
*sh
;
187 struct btrfs_root_item
*root_item_ptr
;
188 struct btrfs_root_item root_item
;
189 struct subvol_info
*si
= NULL
;
190 int root_item_valid
= 0;
191 unsigned long off
= 0;
196 memset(&args
, 0, sizeof(args
));
198 sk
->tree_id
= BTRFS_ROOT_TREE_OBJECTID
;
200 sk
->max_objectid
= (u64
)-1;
201 sk
->max_offset
= (u64
)-1;
202 sk
->max_transid
= (u64
)-1;
203 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
204 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
208 ret
= ioctl(mnt_fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
211 fprintf(stderr
, "ERROR: can't perform the search- %s\n",
215 if (sk
->nr_items
== 0)
220 for (i
= 0; i
< sk
->nr_items
; i
++) {
221 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
225 if ((sh
->objectid
!= 5 &&
226 sh
->objectid
< BTRFS_FIRST_FREE_OBJECTID
) ||
227 sh
->objectid
== BTRFS_FREE_INO_OBJECTID
)
230 if (sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
231 /* older kernels don't have uuids+times */
232 if (sh
->len
< sizeof(root_item
)) {
236 root_item_ptr
= (struct btrfs_root_item
*)
238 memcpy(&root_item
, root_item_ptr
,
241 } else if (sh
->type
== BTRFS_ROOT_BACKREF_KEY
) {
242 if (!root_item_valid
)
245 path
= path_for_root(mnt_fd
, sh
->objectid
);
250 fprintf(stderr
, "ERROR: unable to "
257 si
= calloc(1, sizeof(*si
));
258 si
->root_id
= sh
->objectid
;
259 memcpy(si
->uuid
, root_item
.uuid
,
261 memcpy(si
->parent_uuid
, root_item
.parent_uuid
,
263 memcpy(si
->received_uuid
,
264 root_item
.received_uuid
,
266 si
->ctransid
= btrfs_root_ctransid(&root_item
);
267 si
->otransid
= btrfs_root_otransid(&root_item
);
268 si
->stransid
= btrfs_root_stransid(&root_item
);
269 si
->rtransid
= btrfs_root_rtransid(&root_item
);
271 subvol_uuid_search_add(s
, si
);
282 * record the mins in sk so we can make sure the
283 * next search doesn't repeat this root
285 sk
->min_objectid
= sh
->objectid
;
286 sk
->min_offset
= sh
->offset
;
287 sk
->min_type
= sh
->type
;
290 if (sk
->min_offset
< (u64
)-1)
292 else if (sk
->min_objectid
< (u64
)-1) {
305 char *path_cat(const char *p1
, const char *p2
)
307 int p1_len
= strlen(p1
);
308 int p2_len
= strlen(p2
);
309 char *new = malloc(p1_len
+ p2_len
+ 3);
311 if (p1_len
&& p1
[p1_len
- 1] == '/')
313 if (p2_len
&& p2
[p2_len
- 1] == '/')
315 sprintf(new, "%.*s/%.*s", p1_len
, p1
, p2_len
, p2
);
320 char *path_cat3(const char *p1
, const char *p2
, const char *p3
)
322 int p1_len
= strlen(p1
);
323 int p2_len
= strlen(p2
);
324 int p3_len
= strlen(p3
);
325 char *new = malloc(p1_len
+ p2_len
+ p3_len
+ 4);
327 if (p1_len
&& p1
[p1_len
- 1] == '/')
329 if (p2_len
&& p2
[p2_len
- 1] == '/')
331 if (p3_len
&& p3
[p3_len
- 1] == '/')
333 sprintf(new, "%.*s/%.*s/%.*s", p1_len
, p1
, p2_len
, p2
, p3_len
, p3
);