packaging: Enable LTO and set visibility to hidden
[platform/upstream/btrfs-progs.git] / libbtrfsutil / subvolume.c
1 /*
2  * Copyright (C) 2018 Facebook
3  *
4  * This file is part of libbtrfsutil.
5  *
6  * libbtrfsutil is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * libbtrfsutil is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with libbtrfsutil.  If not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #include <errno.h>
21 #include <fcntl.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <sys/ioctl.h>
26 #include <sys/stat.h>
27 #include <sys/types.h>
28 #include <sys/vfs.h>
29 #include <linux/magic.h>
30 #include "stubs.h"
31
32 #include "btrfsutil_internal.h"
33
34 /*
35  * This intentionally duplicates btrfs_util_is_subvolume_fd() instead of opening
36  * a file descriptor and calling it, because fstat() and fstatfs() don't accept
37  * file descriptors opened with O_PATH on old kernels (before v3.6 and before
38  * v3.12, respectively), but stat() and statfs() can be called on a path that
39  * the user doesn't have read or write permissions to.
40  */
41 PUBLIC enum btrfs_util_error btrfs_util_is_subvolume(const char *path)
42 {
43         struct statfs sfs;
44         struct stat st;
45         int ret;
46
47         ret = statfs(path, &sfs);
48         if (ret == -1)
49                 return BTRFS_UTIL_ERROR_STATFS_FAILED;
50
51         if (sfs.f_type != BTRFS_SUPER_MAGIC) {
52                 errno = EINVAL;
53                 return BTRFS_UTIL_ERROR_NOT_BTRFS;
54         }
55
56         ret = stat(path, &st);
57         if (ret == -1)
58                 return BTRFS_UTIL_ERROR_STAT_FAILED;
59
60         if (st.st_ino != BTRFS_FIRST_FREE_OBJECTID || !S_ISDIR(st.st_mode)) {
61                 errno = EINVAL;
62                 return BTRFS_UTIL_ERROR_NOT_SUBVOLUME;
63         }
64
65         return BTRFS_UTIL_OK;
66 }
67
68 PUBLIC enum btrfs_util_error btrfs_util_is_subvolume_fd(int fd)
69 {
70         struct statfs sfs;
71         struct stat st;
72         int ret;
73
74         ret = fstatfs(fd, &sfs);
75         if (ret == -1)
76                 return BTRFS_UTIL_ERROR_STATFS_FAILED;
77
78         if (sfs.f_type != BTRFS_SUPER_MAGIC) {
79                 errno = EINVAL;
80                 return BTRFS_UTIL_ERROR_NOT_BTRFS;
81         }
82
83         ret = fstat(fd, &st);
84         if (ret == -1)
85                 return BTRFS_UTIL_ERROR_STAT_FAILED;
86
87         if (st.st_ino != BTRFS_FIRST_FREE_OBJECTID || !S_ISDIR(st.st_mode)) {
88                 errno = EINVAL;
89                 return BTRFS_UTIL_ERROR_NOT_SUBVOLUME;
90         }
91
92         return BTRFS_UTIL_OK;
93 }
94
95 PUBLIC enum btrfs_util_error btrfs_util_subvolume_id(const char *path,
96                                                      uint64_t *id_ret)
97 {
98         enum btrfs_util_error err;
99         int fd;
100
101         fd = open(path, O_RDONLY);
102         if (fd == -1)
103                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
104
105         err = btrfs_util_subvolume_id_fd(fd, id_ret);
106         SAVE_ERRNO_AND_CLOSE(fd);
107         return err;
108 }
109
110 PUBLIC enum btrfs_util_error btrfs_util_subvolume_id_fd(int fd,
111                                                         uint64_t *id_ret)
112 {
113         struct btrfs_ioctl_ino_lookup_args args = {
114                 .treeid = 0,
115                 .objectid = BTRFS_FIRST_FREE_OBJECTID,
116         };
117         int ret;
118
119         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
120         if (ret == -1) {
121                 close(fd);
122                 return BTRFS_UTIL_ERROR_INO_LOOKUP_FAILED;
123         }
124
125         *id_ret = args.treeid;
126
127         return BTRFS_UTIL_OK;
128 }
129
130 PUBLIC enum btrfs_util_error btrfs_util_subvolume_path(const char *path,
131                                                        uint64_t id,
132                                                        char **path_ret)
133 {
134         enum btrfs_util_error err;
135         int fd;
136
137         fd = open(path, O_RDONLY);
138         if (fd == -1)
139                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
140
141         err = btrfs_util_subvolume_path_fd(fd, id, path_ret);
142         SAVE_ERRNO_AND_CLOSE(fd);
143         return err;
144 }
145
146 PUBLIC enum btrfs_util_error btrfs_util_subvolume_path_fd(int fd, uint64_t id,
147                                                           char **path_ret)
148 {
149         char *path, *p;
150         size_t capacity = 4096;
151
152         if (id == 0) {
153                 enum btrfs_util_error err;
154
155                 err = btrfs_util_is_subvolume_fd(fd);
156                 if (err)
157                         return err;
158
159                 err = btrfs_util_subvolume_id_fd(fd, &id);
160                 if (err)
161                         return err;
162         }
163
164         path = malloc(capacity);
165         if (!path)
166                 return BTRFS_UTIL_ERROR_NO_MEMORY;
167         p = path + capacity - 1;
168         p[0] = '\0';
169
170         while (id != BTRFS_FS_TREE_OBJECTID) {
171                 struct btrfs_ioctl_search_args search = {
172                         .key = {
173                                 .tree_id = BTRFS_ROOT_TREE_OBJECTID,
174                                 .min_objectid = id,
175                                 .max_objectid = id,
176                                 .min_type = BTRFS_ROOT_BACKREF_KEY,
177                                 .max_type = BTRFS_ROOT_BACKREF_KEY,
178                                 .min_offset = 0,
179                                 .max_offset = UINT64_MAX,
180                                 .min_transid = 0,
181                                 .max_transid = UINT64_MAX,
182                                 .nr_items = 1,
183                         },
184                 };
185                 struct btrfs_ioctl_ino_lookup_args lookup;
186                 const struct btrfs_ioctl_search_header *header;
187                 const struct btrfs_root_ref *ref;
188                 const char *name;
189                 uint16_t name_len;
190                 size_t lookup_len;
191                 size_t total_len;
192                 int ret;
193
194                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search);
195                 if (ret == -1) {
196                         free(path);
197                         return BTRFS_UTIL_ERROR_SEARCH_FAILED;
198                 }
199
200                 if (search.key.nr_items == 0) {
201                         free(path);
202                         errno = ENOENT;
203                         return BTRFS_UTIL_ERROR_SUBVOLUME_NOT_FOUND;
204                 }
205
206                 header = (struct btrfs_ioctl_search_header *)search.buf;
207                 ref = (struct btrfs_root_ref *)(header + 1);
208                 name = (char *)(ref + 1);
209                 name_len = le16_to_cpu(ref->name_len);
210
211                 id = header->offset;
212
213                 lookup.treeid = id;
214                 lookup.objectid = le64_to_cpu(ref->dirid);
215                 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &lookup);
216                 if (ret == -1) {
217                         free(path);
218                         return BTRFS_UTIL_ERROR_SEARCH_FAILED;
219                 }
220                 lookup_len = strlen(lookup.name);
221
222                 total_len = name_len + lookup_len + (id != BTRFS_FS_TREE_OBJECTID);
223                 if (p - total_len < path) {
224                         char *new_path, *new_p;
225                         size_t new_capacity = capacity * 2;
226
227                         new_path = malloc(new_capacity);
228                         if (!new_path) {
229                                 free(path);
230                                 return BTRFS_UTIL_ERROR_NO_MEMORY;
231                         }
232                         new_p = new_path + new_capacity - (path + capacity - p);
233                         memcpy(new_p, p, path + capacity - p);
234                         free(path);
235                         path = new_path;
236                         p = new_p;
237                         capacity = new_capacity;
238                 }
239                 p -= name_len;
240                 memcpy(p, name, name_len);
241                 p -= lookup_len;
242                 memcpy(p, lookup.name, lookup_len);
243                 if (id != BTRFS_FS_TREE_OBJECTID)
244                         *--p = '/';
245         }
246
247         if (p != path)
248                 memmove(path, p, path + capacity - p);
249
250         *path_ret = path;
251
252         return BTRFS_UTIL_OK;
253 }
254
255 static void copy_timespec(struct timespec *timespec,
256                           const struct btrfs_timespec *btrfs_timespec)
257 {
258         timespec->tv_sec = le64_to_cpu(btrfs_timespec->sec);
259         timespec->tv_nsec = le32_to_cpu(btrfs_timespec->nsec);
260 }
261
262 static void copy_root_item(struct btrfs_util_subvolume_info *subvol,
263                            const struct btrfs_root_item *root)
264 {
265         subvol->flags = le64_to_cpu(root->flags);
266         memcpy(subvol->uuid, root->uuid, sizeof(subvol->uuid));
267         memcpy(subvol->parent_uuid, root->parent_uuid,
268                sizeof(subvol->parent_uuid));
269         memcpy(subvol->received_uuid, root->received_uuid,
270                sizeof(subvol->received_uuid));
271         subvol->generation = le64_to_cpu(root->generation);
272         subvol->ctransid = le64_to_cpu(root->ctransid);
273         subvol->otransid = le64_to_cpu(root->otransid);
274         subvol->stransid = le64_to_cpu(root->stransid);
275         subvol->rtransid = le64_to_cpu(root->rtransid);
276         copy_timespec(&subvol->ctime, &root->ctime);
277         copy_timespec(&subvol->otime, &root->otime);
278         copy_timespec(&subvol->stime, &root->stime);
279         copy_timespec(&subvol->rtime, &root->rtime);
280 }
281
282 PUBLIC enum btrfs_util_error btrfs_util_subvolume_info(const char *path,
283                                                        uint64_t id,
284                                                        struct btrfs_util_subvolume_info *subvol)
285 {
286         enum btrfs_util_error err;
287         int fd;
288
289         fd = open(path, O_RDONLY);
290         if (fd == -1)
291                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
292
293         err = btrfs_util_subvolume_info_fd(fd, id, subvol);
294         SAVE_ERRNO_AND_CLOSE(fd);
295         return err;
296 }
297
298 PUBLIC enum btrfs_util_error btrfs_util_subvolume_info_fd(int fd, uint64_t id,
299                                                           struct btrfs_util_subvolume_info *subvol)
300 {
301         struct btrfs_ioctl_search_args search = {
302                 .key = {
303                         .tree_id = BTRFS_ROOT_TREE_OBJECTID,
304                         .min_type = BTRFS_ROOT_ITEM_KEY,
305                         .max_type = BTRFS_ROOT_BACKREF_KEY,
306                         .min_offset = 0,
307                         .max_offset = UINT64_MAX,
308                         .min_transid = 0,
309                         .max_transid = UINT64_MAX,
310                         .nr_items = 0,
311                 },
312         };
313         enum btrfs_util_error err;
314         size_t items_pos = 0, buf_off = 0;
315         bool need_root_item = true, need_root_backref = true;
316         int ret;
317
318         if (id == 0) {
319                 err = btrfs_util_is_subvolume_fd(fd);
320                 if (err)
321                         return err;
322
323                 err = btrfs_util_subvolume_id_fd(fd, &id);
324                 if (err)
325                         return err;
326         }
327
328         if ((id < BTRFS_FIRST_FREE_OBJECTID && id != BTRFS_FS_TREE_OBJECTID) ||
329             id > BTRFS_LAST_FREE_OBJECTID) {
330                 errno = ENOENT;
331                 return BTRFS_UTIL_ERROR_SUBVOLUME_NOT_FOUND;
332         }
333
334         search.key.min_objectid = search.key.max_objectid = id;
335
336         if (subvol) {
337                 subvol->id = id;
338                 subvol->parent_id = 0;
339                 subvol->dir_id = 0;
340                 if (id == BTRFS_FS_TREE_OBJECTID)
341                         need_root_backref = false;
342         } else {
343                 /*
344                  * We only need the backref for filling in the subvolume info.
345                  */
346                 need_root_backref = false;
347         }
348
349         /* Don't bother searching for the backref if we don't need it. */
350         if (!need_root_backref)
351                 search.key.max_type = BTRFS_ROOT_ITEM_KEY;
352
353         while (need_root_item || need_root_backref) {
354                 const struct btrfs_ioctl_search_header *header;
355
356                 if (items_pos >= search.key.nr_items) {
357                         search.key.nr_items = 4096;
358                         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search);
359                         if (ret == -1)
360                                 return BTRFS_UTIL_ERROR_SEARCH_FAILED;
361                         items_pos = 0;
362                         buf_off = 0;
363
364                         if (search.key.nr_items == 0) {
365                                 if (need_root_item) {
366                                         errno = ENOENT;
367                                         return BTRFS_UTIL_ERROR_SUBVOLUME_NOT_FOUND;
368                                 } else {
369                                         break;
370                                 }
371                         }
372                 }
373
374                 header = (struct btrfs_ioctl_search_header *)(search.buf + buf_off);
375                 if (header->type == BTRFS_ROOT_ITEM_KEY) {
376                         if (subvol) {
377                                 const struct btrfs_root_item *root;
378
379                                 root = (const struct btrfs_root_item *)(header + 1);
380                                 copy_root_item(subvol, root);
381                         }
382                         need_root_item = false;
383                         search.key.min_type = BTRFS_ROOT_BACKREF_KEY;
384                 } else if (header->type == BTRFS_ROOT_BACKREF_KEY) {
385                         if (subvol) {
386                                 const struct btrfs_root_ref *ref;
387
388                                 ref = (const struct btrfs_root_ref *)(header + 1);
389                                 subvol->parent_id = header->offset;
390                                 subvol->dir_id = le64_to_cpu(ref->dirid);
391                         }
392                         need_root_backref = false;
393                         search.key.min_type = UINT32_MAX;
394                 }
395
396                 items_pos++;
397                 buf_off += sizeof(*header) + header->len;
398         }
399
400         return BTRFS_UTIL_OK;
401 }
402
403 PUBLIC enum btrfs_util_error btrfs_util_get_subvolume_read_only_fd(int fd,
404                                                                    bool *read_only_ret)
405 {
406         uint64_t flags;
407         int ret;
408
409         ret = ioctl(fd, BTRFS_IOC_SUBVOL_GETFLAGS, &flags);
410         if (ret == -1)
411                 return BTRFS_UTIL_ERROR_SUBVOL_GETFLAGS_FAILED;
412
413         *read_only_ret = flags & BTRFS_SUBVOL_RDONLY;
414         return BTRFS_UTIL_OK;
415 }
416
417 PUBLIC enum btrfs_util_error btrfs_util_get_subvolume_read_only(const char *path,
418                                                                 bool *ret)
419 {
420         enum btrfs_util_error err;
421         int fd;
422
423         fd = open(path, O_RDONLY);
424         if (fd == -1)
425                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
426
427         err = btrfs_util_get_subvolume_read_only_fd(fd, ret);
428         SAVE_ERRNO_AND_CLOSE(fd);
429         return err;
430 }
431
432 PUBLIC enum btrfs_util_error btrfs_util_set_subvolume_read_only(const char *path,
433                                                                 bool read_only)
434 {
435         enum btrfs_util_error err;
436         int fd;
437
438         fd = open(path, O_RDONLY);
439         if (fd == -1)
440                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
441
442         err = btrfs_util_set_subvolume_read_only_fd(fd, read_only);
443         SAVE_ERRNO_AND_CLOSE(fd);
444         return err;
445 }
446
447 PUBLIC enum btrfs_util_error btrfs_util_set_subvolume_read_only_fd(int fd,
448                                                                    bool read_only)
449 {
450         uint64_t flags;
451         int ret;
452
453         ret = ioctl(fd, BTRFS_IOC_SUBVOL_GETFLAGS, &flags);
454         if (ret == -1)
455                 return BTRFS_UTIL_ERROR_SUBVOL_GETFLAGS_FAILED;
456
457         if (read_only)
458                 flags |= BTRFS_SUBVOL_RDONLY;
459         else
460                 flags &= ~BTRFS_SUBVOL_RDONLY;
461
462         ret = ioctl(fd, BTRFS_IOC_SUBVOL_SETFLAGS, &flags);
463         if (ret == -1)
464                 return BTRFS_UTIL_ERROR_SUBVOL_SETFLAGS_FAILED;
465
466         return BTRFS_UTIL_OK;
467 }
468
469 PUBLIC enum btrfs_util_error btrfs_util_get_default_subvolume(const char *path,
470                                                               uint64_t *id_ret)
471 {
472         enum btrfs_util_error err;
473         int fd;
474
475         fd = open(path, O_RDONLY);
476         if (fd == -1)
477                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
478
479         err = btrfs_util_get_default_subvolume_fd(fd, id_ret);
480         SAVE_ERRNO_AND_CLOSE(fd);
481         return err;
482 }
483
484 PUBLIC enum btrfs_util_error btrfs_util_get_default_subvolume_fd(int fd,
485                                                                  uint64_t *id_ret)
486 {
487         struct btrfs_ioctl_search_args search = {
488                 .key = {
489                         .tree_id = BTRFS_ROOT_TREE_OBJECTID,
490                         .min_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID,
491                         .max_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID,
492                         .min_type = BTRFS_DIR_ITEM_KEY,
493                         .max_type = BTRFS_DIR_ITEM_KEY,
494                         .min_offset = 0,
495                         .max_offset = UINT64_MAX,
496                         .min_transid = 0,
497                         .max_transid = UINT64_MAX,
498                         .nr_items = 0,
499                 },
500         };
501         size_t items_pos = 0, buf_off = 0;
502         int ret;
503
504         for (;;) {
505                 const struct btrfs_ioctl_search_header *header;
506
507                 if (items_pos >= search.key.nr_items) {
508                         search.key.nr_items = 4096;
509                         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search);
510                         if (ret == -1)
511                                 return BTRFS_UTIL_ERROR_SEARCH_FAILED;
512                         items_pos = 0;
513                         buf_off = 0;
514
515                         if (search.key.nr_items == 0) {
516                                 errno = ENOENT;
517                                 return BTRFS_UTIL_ERROR_SUBVOLUME_NOT_FOUND;
518                         }
519                 }
520
521                 header = (struct btrfs_ioctl_search_header *)(search.buf + buf_off);
522                 if (header->type == BTRFS_DIR_ITEM_KEY) {
523                         const struct btrfs_dir_item *dir;
524                         const char *name;
525                         uint16_t name_len;
526
527                         dir = (struct btrfs_dir_item *)(header + 1);
528                         name = (const char *)(dir + 1);
529                         name_len = le16_to_cpu(dir->name_len);
530                         if (strncmp(name, "default", name_len) == 0) {
531                                 *id_ret = le64_to_cpu(dir->location.objectid);
532                                 break;
533                         }
534                 }
535
536                 items_pos++;
537                 buf_off += sizeof(*header) + header->len;
538                 search.key.min_offset = header->offset + 1;
539         }
540
541         return BTRFS_UTIL_OK;
542 }
543
544 PUBLIC enum btrfs_util_error btrfs_util_set_default_subvolume(const char *path,
545                                                               uint64_t id)
546 {
547         enum btrfs_util_error err;
548         int fd;
549
550         fd = open(path, O_RDONLY);
551         if (fd == -1)
552                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
553
554         err = btrfs_util_set_default_subvolume_fd(fd, id);
555         SAVE_ERRNO_AND_CLOSE(fd);
556         return err;
557 }
558
559 PUBLIC enum btrfs_util_error btrfs_util_set_default_subvolume_fd(int fd,
560                                                                  uint64_t id)
561 {
562         enum btrfs_util_error err;
563         int ret;
564
565         if (id == 0) {
566                 err = btrfs_util_is_subvolume_fd(fd);
567                 if (err)
568                         return err;
569
570                 err = btrfs_util_subvolume_id_fd(fd, &id);
571                 if (err)
572                         return err;
573         }
574
575         ret = ioctl(fd, BTRFS_IOC_DEFAULT_SUBVOL, &id);
576         if (ret == -1)
577                 return BTRFS_UTIL_ERROR_DEFAULT_SUBVOL_FAILED;
578
579         return BTRFS_UTIL_OK;
580 }
581
582 static enum btrfs_util_error openat_parent_and_name(int dirfd, const char *path,
583                                                     char *name, size_t name_len,
584                                                     int *fd)
585 {
586         char *tmp_path, *slash, *dirname, *basename;
587         size_t len;
588
589         /* Ignore trailing slashes. */
590         len = strlen(path);
591         while (len > 1 && path[len - 1] == '/')
592                 len--;
593
594         tmp_path = malloc(len + 1);
595         if (!tmp_path)
596                 return BTRFS_UTIL_ERROR_NO_MEMORY;
597         memcpy(tmp_path, path, len);
598         tmp_path[len] = '\0';
599
600         slash = memrchr(tmp_path, '/', len);
601         if (slash == tmp_path) {
602                 dirname = "/";
603                 basename = tmp_path + 1;
604         } else if (slash) {
605                 *slash = '\0';
606                 dirname = tmp_path;
607                 basename = slash + 1;
608         } else {
609                 dirname = ".";
610                 basename = tmp_path;
611         }
612
613         len = strlen(basename);
614         if (len >= name_len) {
615                 free(tmp_path);
616                 errno = ENAMETOOLONG;
617                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
618         }
619         memcpy(name, basename, len);
620         name[len] = '\0';
621
622         *fd = openat(dirfd, dirname, O_RDONLY | O_DIRECTORY);
623         if (*fd == -1) {
624                 free(tmp_path);
625                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
626         }
627
628         free(tmp_path);
629         return BTRFS_UTIL_OK;
630 }
631
632 PUBLIC enum btrfs_util_error btrfs_util_create_subvolume(const char *path,
633                                                          int flags,
634                                                          uint64_t *async_transid,
635                                                          struct btrfs_util_qgroup_inherit *qgroup_inherit)
636 {
637         char name[BTRFS_SUBVOL_NAME_MAX + 1];
638         enum btrfs_util_error err;
639         int parent_fd;
640
641         err = openat_parent_and_name(AT_FDCWD, path, name, sizeof(name),
642                                      &parent_fd);
643         if (err)
644                 return err;
645
646         err = btrfs_util_create_subvolume_fd(parent_fd, name, flags,
647                                             async_transid, qgroup_inherit);
648         SAVE_ERRNO_AND_CLOSE(parent_fd);
649         return err;
650 }
651
652 PUBLIC enum btrfs_util_error btrfs_util_create_subvolume_fd(int parent_fd,
653                                                             const char *name,
654                                                             int flags,
655                                                             uint64_t *async_transid,
656                                                             struct btrfs_util_qgroup_inherit *qgroup_inherit)
657 {
658         struct btrfs_ioctl_vol_args_v2 args = {};
659         size_t len;
660         int ret;
661
662         if (flags) {
663                 errno = EINVAL;
664                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
665         }
666
667         if (async_transid)
668                 args.flags |= BTRFS_SUBVOL_CREATE_ASYNC;
669         if (qgroup_inherit) {
670                 args.flags |= BTRFS_SUBVOL_QGROUP_INHERIT;
671                 args.qgroup_inherit = (struct btrfs_qgroup_inherit *)qgroup_inherit;
672                 args.size = (sizeof(*args.qgroup_inherit) +
673                              args.qgroup_inherit->num_qgroups *
674                              sizeof(args.qgroup_inherit->qgroups[0]));
675         }
676
677         len = strlen(name);
678         if (len >= sizeof(args.name)) {
679                 errno = ENAMETOOLONG;
680                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
681         }
682         memcpy(args.name, name, len);
683         args.name[len] = '\0';
684
685         ret = ioctl(parent_fd, BTRFS_IOC_SUBVOL_CREATE_V2, &args);
686         if (ret == -1)
687                 return BTRFS_UTIL_ERROR_SUBVOL_CREATE_FAILED;
688
689         if (async_transid)
690                 *async_transid = args.transid;
691
692         return BTRFS_UTIL_OK;
693 }
694
695 #define BTRFS_UTIL_SUBVOLUME_ITERATOR_CLOSE_FD (1 << 30)
696
697 struct search_stack_entry {
698         struct btrfs_ioctl_search_args search;
699         size_t items_pos, buf_off;
700         size_t path_len;
701 };
702
703 struct btrfs_util_subvolume_iterator {
704         int fd;
705         int flags;
706
707         struct search_stack_entry *search_stack;
708         size_t search_stack_len;
709         size_t search_stack_capacity;
710
711         char *cur_path;
712         size_t cur_path_capacity;
713 };
714
715 static enum btrfs_util_error append_to_search_stack(struct btrfs_util_subvolume_iterator *iter,
716                                                     uint64_t tree_id,
717                                                     size_t path_len)
718 {
719         struct search_stack_entry *entry;
720
721         if (iter->search_stack_len >= iter->search_stack_capacity) {
722                 size_t new_capacity = iter->search_stack_capacity * 2;
723                 struct search_stack_entry *new_search_stack;
724
725                 new_search_stack = reallocarray(iter->search_stack,
726                                                 new_capacity,
727                                                 sizeof(*iter->search_stack));
728                 if (!new_search_stack)
729                         return BTRFS_UTIL_ERROR_NO_MEMORY;
730
731                 iter->search_stack_capacity = new_capacity;
732                 iter->search_stack = new_search_stack;
733         }
734
735         entry = &iter->search_stack[iter->search_stack_len++];
736
737         memset(&entry->search, 0, sizeof(entry->search));
738         entry->search.key.tree_id = BTRFS_ROOT_TREE_OBJECTID;
739         entry->search.key.min_objectid = tree_id;
740         entry->search.key.max_objectid = tree_id;
741         entry->search.key.min_type = BTRFS_ROOT_REF_KEY;
742         entry->search.key.max_type = BTRFS_ROOT_REF_KEY;
743         entry->search.key.min_offset = 0;
744         entry->search.key.max_offset = UINT64_MAX;
745         entry->search.key.min_transid = 0;
746         entry->search.key.max_transid = UINT64_MAX;
747         entry->search.key.nr_items = 0;
748
749         entry->items_pos = 0;
750         entry->buf_off = 0;
751
752         entry->path_len = path_len;
753
754         return BTRFS_UTIL_OK;
755 }
756
757 PUBLIC enum btrfs_util_error btrfs_util_create_subvolume_iterator(const char *path,
758                                                                   uint64_t top,
759                                                                   int flags,
760                                                                   struct btrfs_util_subvolume_iterator **ret)
761 {
762         enum btrfs_util_error err;
763         int fd;
764
765         fd = open(path, O_RDONLY);
766         if (fd == -1)
767                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
768
769         err = btrfs_util_create_subvolume_iterator_fd(fd, top, flags, ret);
770         if (err)
771                 SAVE_ERRNO_AND_CLOSE(fd);
772         else
773                 (*ret)->flags |= BTRFS_UTIL_SUBVOLUME_ITERATOR_CLOSE_FD;
774
775         return err;
776 }
777
778 PUBLIC enum btrfs_util_error btrfs_util_create_subvolume_iterator_fd(int fd,
779                                                                      uint64_t top,
780                                                                      int flags,
781                                                                      struct btrfs_util_subvolume_iterator **ret)
782 {
783         struct btrfs_util_subvolume_iterator *iter;
784         enum btrfs_util_error err;
785
786         if (flags & ~BTRFS_UTIL_SUBVOLUME_ITERATOR_MASK) {
787                 errno = EINVAL;
788                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
789         }
790
791         if (top == 0) {
792                 err = btrfs_util_is_subvolume_fd(fd);
793                 if (err)
794                         return err;
795
796                 err = btrfs_util_subvolume_id_fd(fd, &top);
797                 if (err)
798                         return err;
799         }
800
801         iter = malloc(sizeof(*iter));
802         if (!iter)
803                 return BTRFS_UTIL_ERROR_NO_MEMORY;
804
805         iter->fd = fd;
806         iter->flags = flags;
807
808         iter->search_stack_len = 0;
809         iter->search_stack_capacity = 4;
810         iter->search_stack = malloc(sizeof(*iter->search_stack) *
811                                     iter->search_stack_capacity);
812         if (!iter->search_stack) {
813                 err = BTRFS_UTIL_ERROR_NO_MEMORY;
814                 goto out_iter;
815         }
816
817         iter->cur_path_capacity = 256;
818         iter->cur_path = malloc(iter->cur_path_capacity);
819         if (!iter->cur_path) {
820                 err = BTRFS_UTIL_ERROR_NO_MEMORY;
821                 goto out_search_stack;
822         }
823
824         err = append_to_search_stack(iter, top, 0);
825         if (err)
826                 goto out_cur_path;
827
828         *ret = iter;
829
830         return BTRFS_UTIL_OK;
831
832 out_cur_path:
833         free(iter->cur_path);
834 out_search_stack:
835         free(iter->search_stack);
836 out_iter:
837         free(iter);
838         return err;
839 }
840
841 static enum btrfs_util_error snapshot_subvolume_children(int fd, int parent_fd,
842                                                          const char *name,
843                                                          uint64_t *async_transid)
844 {
845         struct btrfs_util_subvolume_iterator *iter;
846         enum btrfs_util_error err;
847         int dstfd;
848
849         dstfd = openat(parent_fd, name, O_RDONLY);
850         if (dstfd == -1)
851                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
852
853         err = btrfs_util_create_subvolume_iterator_fd(fd, 0, 0, &iter);
854         if (err)
855                 goto out;
856
857         for (;;) {
858                 char child_name[BTRFS_SUBVOL_NAME_MAX + 1];
859                 char *child_path;
860                 int child_fd, new_parent_fd;
861                 uint64_t tmp_transid;
862
863                 err = btrfs_util_subvolume_iterator_next(iter, &child_path,
864                                                          NULL);
865                 if (err) {
866                         if (err == BTRFS_UTIL_ERROR_STOP_ITERATION)
867                                 err = BTRFS_UTIL_OK;
868                         break;
869                 }
870
871                 /* Remove the placeholder directory. */
872                 if (unlinkat(dstfd, child_path, AT_REMOVEDIR) == -1) {
873                         free(child_path);
874                         err = BTRFS_UTIL_ERROR_RMDIR_FAILED;
875                         break;
876                 }
877
878                 child_fd = openat(fd, child_path, O_RDONLY);
879                 if (child_fd == -1) {
880                         free(child_path);
881                         err = BTRFS_UTIL_ERROR_OPEN_FAILED;
882                         break;
883                 }
884
885                 err = openat_parent_and_name(dstfd, child_path, child_name,
886                                              sizeof(child_name),
887                                              &new_parent_fd);
888                 free(child_path);
889                 if (err) {
890                         SAVE_ERRNO_AND_CLOSE(child_fd);
891                         break;
892                 }
893
894                 err = btrfs_util_create_snapshot_fd2(child_fd, new_parent_fd,
895                                                      child_name, 0,
896                                                      async_transid ? &tmp_transid : NULL,
897                                                      NULL);
898                 SAVE_ERRNO_AND_CLOSE(child_fd);
899                 SAVE_ERRNO_AND_CLOSE(new_parent_fd);
900                 if (err)
901                         break;
902                 if (async_transid && tmp_transid > *async_transid)
903                         *async_transid = tmp_transid;
904         }
905
906         btrfs_util_destroy_subvolume_iterator(iter);
907 out:
908         SAVE_ERRNO_AND_CLOSE(dstfd);
909         return err;
910 }
911
912 PUBLIC enum btrfs_util_error btrfs_util_create_snapshot(const char *source,
913                                                         const char *path,
914                                                         int flags,
915                                                         uint64_t *async_transid,
916                                                         struct btrfs_util_qgroup_inherit *qgroup_inherit)
917 {
918         enum btrfs_util_error err;
919         int fd;
920
921         fd = open(source, O_RDONLY);
922         if (fd == -1)
923                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
924
925         err = btrfs_util_create_snapshot_fd(fd, path, flags, async_transid,
926                                             qgroup_inherit);
927         SAVE_ERRNO_AND_CLOSE(fd);
928         return err;
929 }
930
931 PUBLIC enum btrfs_util_error btrfs_util_create_snapshot_fd(int fd,
932                                                            const char *path,
933                                                            int flags,
934                                                            uint64_t *async_transid,
935                                                            struct btrfs_util_qgroup_inherit *qgroup_inherit)
936 {
937         char name[BTRFS_SUBVOL_NAME_MAX + 1];
938         enum btrfs_util_error err;
939         int parent_fd;
940
941         err = openat_parent_and_name(AT_FDCWD, path, name, sizeof(name),
942                                      &parent_fd);
943         if (err)
944                 return err;
945
946         err = btrfs_util_create_snapshot_fd2(fd, parent_fd, name, flags,
947                                              async_transid, qgroup_inherit);
948         SAVE_ERRNO_AND_CLOSE(parent_fd);
949         return err;
950 }
951
952 PUBLIC enum btrfs_util_error btrfs_util_create_snapshot_fd2(int fd,
953                                                             int parent_fd,
954                                                             const char *name,
955                                                             int flags,
956                                                             uint64_t *async_transid,
957                                                             struct btrfs_util_qgroup_inherit *qgroup_inherit)
958 {
959         struct btrfs_ioctl_vol_args_v2 args = {.fd = fd};
960         enum btrfs_util_error err;
961         size_t len;
962         int ret;
963
964         if ((flags & ~BTRFS_UTIL_CREATE_SNAPSHOT_MASK) ||
965             ((flags & BTRFS_UTIL_CREATE_SNAPSHOT_READ_ONLY) &&
966              (flags & BTRFS_UTIL_CREATE_SNAPSHOT_RECURSIVE))) {
967                 errno = EINVAL;
968                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
969         }
970
971         if (flags & BTRFS_UTIL_CREATE_SNAPSHOT_READ_ONLY)
972                 args.flags |= BTRFS_SUBVOL_RDONLY;
973         if (async_transid)
974                 args.flags |= BTRFS_SUBVOL_CREATE_ASYNC;
975         if (qgroup_inherit) {
976                 args.flags |= BTRFS_SUBVOL_QGROUP_INHERIT;
977                 args.qgroup_inherit = (struct btrfs_qgroup_inherit *)qgroup_inherit;
978                 args.size = (sizeof(*args.qgroup_inherit) +
979                              args.qgroup_inherit->num_qgroups *
980                              sizeof(args.qgroup_inherit->qgroups[0]));
981         }
982
983         len = strlen(name);
984         if (len >= sizeof(args.name)) {
985                 errno = ENAMETOOLONG;
986                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
987         }
988         memcpy(args.name, name, len);
989         args.name[len] = '\0';
990
991         ret = ioctl(parent_fd, BTRFS_IOC_SNAP_CREATE_V2, &args);
992         if (ret == -1)
993                 return BTRFS_UTIL_ERROR_SUBVOL_CREATE_FAILED;
994
995         if (async_transid)
996                 *async_transid = args.transid;
997
998         if (flags & BTRFS_UTIL_CREATE_SNAPSHOT_RECURSIVE) {
999                 err = snapshot_subvolume_children(fd, parent_fd, name,
1000                                                   async_transid);
1001                 if (err)
1002                         return err;
1003         }
1004
1005         return BTRFS_UTIL_OK;
1006 }
1007
1008 static enum btrfs_util_error delete_subvolume_children(int parent_fd,
1009                                                        const char *name)
1010 {
1011         struct btrfs_util_subvolume_iterator *iter;
1012         enum btrfs_util_error err;
1013         int fd;
1014
1015         fd = openat(parent_fd, name, O_RDONLY);
1016         if (fd == -1)
1017                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
1018
1019         err = btrfs_util_create_subvolume_iterator_fd(fd, 0,
1020                                                       BTRFS_UTIL_SUBVOLUME_ITERATOR_POST_ORDER,
1021                                                       &iter);
1022         if (err)
1023                 goto out;
1024
1025         for (;;) {
1026                 char child_name[BTRFS_PATH_NAME_MAX + 1];
1027                 char *child_path;
1028                 int child_parent_fd;
1029
1030                 err = btrfs_util_subvolume_iterator_next(iter, &child_path,
1031                                                          NULL);
1032                 if (err) {
1033                         if (err == BTRFS_UTIL_ERROR_STOP_ITERATION)
1034                                 err = BTRFS_UTIL_OK;
1035                         break;
1036                 }
1037
1038                 err = openat_parent_and_name(fd, child_path, child_name,
1039                                              sizeof(child_name),
1040                                              &child_parent_fd);
1041                 free(child_path);
1042                 if (err)
1043                         break;
1044
1045                 err = btrfs_util_delete_subvolume_fd(child_parent_fd,
1046                                                      child_name, 0);
1047                 SAVE_ERRNO_AND_CLOSE(child_parent_fd);
1048                 if (err)
1049                         break;
1050         }
1051
1052         btrfs_util_destroy_subvolume_iterator(iter);
1053 out:
1054         SAVE_ERRNO_AND_CLOSE(fd);
1055         return err;
1056 }
1057
1058 PUBLIC enum btrfs_util_error btrfs_util_delete_subvolume(const char *path,
1059                                                          int flags)
1060 {
1061         char name[BTRFS_PATH_NAME_MAX + 1];
1062         enum btrfs_util_error err;
1063         int parent_fd;
1064
1065         err = openat_parent_and_name(AT_FDCWD, path, name, sizeof(name),
1066                                      &parent_fd);
1067         if (err)
1068                 return err;
1069
1070         err = btrfs_util_delete_subvolume_fd(parent_fd, name, flags);
1071         SAVE_ERRNO_AND_CLOSE(parent_fd);
1072         return err;
1073 }
1074
1075 PUBLIC enum btrfs_util_error btrfs_util_delete_subvolume_fd(int parent_fd,
1076                                                             const char *name,
1077                                                             int flags)
1078 {
1079         struct btrfs_ioctl_vol_args args = {};
1080         enum btrfs_util_error err;
1081         size_t len;
1082         int ret;
1083
1084         if (flags & ~BTRFS_UTIL_DELETE_SUBVOLUME_MASK) {
1085                 errno = EINVAL;
1086                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
1087         }
1088
1089         if (flags & BTRFS_UTIL_DELETE_SUBVOLUME_RECURSIVE) {
1090                 err = delete_subvolume_children(parent_fd, name);
1091                 if (err)
1092                         return err;
1093         }
1094
1095         len = strlen(name);
1096         if (len >= sizeof(args.name)) {
1097                 errno = ENAMETOOLONG;
1098                 return BTRFS_UTIL_ERROR_INVALID_ARGUMENT;
1099         }
1100         memcpy(args.name, name, len);
1101         args.name[len] = '\0';
1102
1103         ret = ioctl(parent_fd, BTRFS_IOC_SNAP_DESTROY, &args);
1104         if (ret == -1)
1105                 return BTRFS_UTIL_ERROR_SNAP_DESTROY_FAILED;
1106
1107         return BTRFS_UTIL_OK;
1108 }
1109
1110 PUBLIC void btrfs_util_destroy_subvolume_iterator(struct btrfs_util_subvolume_iterator *iter)
1111 {
1112         if (iter) {
1113                 free(iter->cur_path);
1114                 free(iter->search_stack);
1115                 if (iter->flags & BTRFS_UTIL_SUBVOLUME_ITERATOR_CLOSE_FD)
1116                         SAVE_ERRNO_AND_CLOSE(iter->fd);
1117                 free(iter);
1118         }
1119 }
1120
1121 PUBLIC int btrfs_util_subvolume_iterator_fd(const struct btrfs_util_subvolume_iterator *iter)
1122 {
1123         return iter->fd;
1124 }
1125
1126 static struct search_stack_entry *top_search_stack_entry(struct btrfs_util_subvolume_iterator *iter)
1127 {
1128         return &iter->search_stack[iter->search_stack_len - 1];
1129 }
1130
1131 static enum btrfs_util_error build_subvol_path(struct btrfs_util_subvolume_iterator *iter,
1132                                                const struct btrfs_ioctl_search_header *header,
1133                                                const struct btrfs_root_ref *ref,
1134                                                const char *name,
1135                                                size_t *path_len_ret)
1136 {
1137         struct btrfs_ioctl_ino_lookup_args lookup = {
1138                 .treeid = header->objectid,
1139                 .objectid = le64_to_cpu(ref->dirid),
1140         };
1141         struct search_stack_entry *top = top_search_stack_entry(iter);
1142         size_t dir_len, name_len, path_len;
1143         char *p;
1144         int ret;
1145
1146         ret = ioctl(iter->fd, BTRFS_IOC_INO_LOOKUP, &lookup);
1147         if (ret == -1)
1148                 return BTRFS_UTIL_ERROR_INO_LOOKUP_FAILED;
1149
1150         dir_len = strlen(lookup.name);
1151         name_len = le16_to_cpu(ref->name_len);
1152
1153         path_len = top->path_len;
1154         /*
1155          * We need a joining slash if we have a current path and a subdirectory.
1156          */
1157         if (top->path_len && dir_len)
1158                 path_len++;
1159         path_len += dir_len;
1160         /*
1161          * We need another joining slash if we have a current path and a name,
1162          * but not if we have a subdirectory, because the lookup ioctl includes
1163          * a trailing slash.
1164          */
1165         if (top->path_len && !dir_len && name_len)
1166                 path_len++;
1167         path_len += name_len;
1168
1169         if (path_len > iter->cur_path_capacity) {
1170                 char *tmp = realloc(iter->cur_path, path_len);
1171
1172                 if (!tmp)
1173                         return BTRFS_UTIL_ERROR_NO_MEMORY;
1174                 iter->cur_path = tmp;
1175                 iter->cur_path_capacity = path_len;
1176         }
1177
1178         p = iter->cur_path + top->path_len;
1179         if (top->path_len && dir_len)
1180                 *p++ = '/';
1181         memcpy(p, lookup.name, dir_len);
1182         p += dir_len;
1183         if (top->path_len && !dir_len && name_len)
1184                 *p++ = '/';
1185         memcpy(p, name, name_len);
1186         p += name_len;
1187
1188         *path_len_ret = path_len;
1189
1190         return BTRFS_UTIL_OK;
1191 }
1192
1193 PUBLIC enum btrfs_util_error btrfs_util_subvolume_iterator_next(struct btrfs_util_subvolume_iterator *iter,
1194                                                                 char **path_ret,
1195                                                                 uint64_t *id_ret)
1196 {
1197         struct search_stack_entry *top;
1198         const struct btrfs_ioctl_search_header *header;
1199         const struct btrfs_root_ref *ref;
1200         const char *name;
1201         enum btrfs_util_error err;
1202         size_t path_len;
1203         int ret;
1204
1205         for (;;) {
1206                 for (;;) {
1207                         if (iter->search_stack_len == 0)
1208                                 return BTRFS_UTIL_ERROR_STOP_ITERATION;
1209
1210                         top = top_search_stack_entry(iter);
1211                         if (top->items_pos < top->search.key.nr_items) {
1212                                 break;
1213                         } else {
1214                                 top->search.key.nr_items = 4096;
1215                                 ret = ioctl(iter->fd, BTRFS_IOC_TREE_SEARCH, &top->search);
1216                                 if (ret == -1)
1217                                         return BTRFS_UTIL_ERROR_SEARCH_FAILED;
1218                                 top->items_pos = 0;
1219                                 top->buf_off = 0;
1220
1221                                 if (top->search.key.nr_items == 0) {
1222                                         iter->search_stack_len--;
1223                                         if ((iter->flags & BTRFS_UTIL_SUBVOLUME_ITERATOR_POST_ORDER) &&
1224                                             iter->search_stack_len)
1225                                                 goto out;
1226                                 }
1227                         }
1228                 }
1229
1230                 header = (struct btrfs_ioctl_search_header *)(top->search.buf + top->buf_off);
1231
1232                 top->items_pos++;
1233                 top->buf_off += sizeof(*header) + header->len;
1234                 top->search.key.min_offset = header->offset + 1;
1235
1236                 /* This shouldn't happen, but handle it just in case. */
1237                 if (header->type != BTRFS_ROOT_REF_KEY)
1238                         continue;
1239
1240                 ref = (struct btrfs_root_ref *)(header + 1);
1241                 name = (const char *)(ref + 1);
1242                 err = build_subvol_path(iter, header, ref, name, &path_len);
1243                 if (err)
1244                         return err;
1245
1246                 err = append_to_search_stack(iter, header->offset, path_len);
1247                 if (err)
1248                         return err;
1249
1250                 if (!(iter->flags & BTRFS_UTIL_SUBVOLUME_ITERATOR_POST_ORDER)) {
1251                         top = top_search_stack_entry(iter);
1252                         goto out;
1253                 }
1254         }
1255
1256 out:
1257         if (path_ret) {
1258                 *path_ret = malloc(top->path_len + 1);
1259                 if (!*path_ret)
1260                         return BTRFS_UTIL_ERROR_NO_MEMORY;
1261                 memcpy(*path_ret, iter->cur_path, top->path_len);
1262                 (*path_ret)[top->path_len] = '\0';
1263         }
1264         if (id_ret)
1265                 *id_ret = top->search.key.min_objectid;
1266         return BTRFS_UTIL_OK;
1267 }
1268
1269 PUBLIC enum btrfs_util_error btrfs_util_subvolume_iterator_next_info(struct btrfs_util_subvolume_iterator *iter,
1270                                                                      char **path_ret,
1271                                                                      struct btrfs_util_subvolume_info *subvol)
1272 {
1273         enum btrfs_util_error err;
1274         uint64_t id;
1275
1276         err = btrfs_util_subvolume_iterator_next(iter, path_ret, &id);
1277         if (err)
1278                 return err;
1279
1280         return btrfs_util_subvolume_info_fd(iter->fd, id, subvol);
1281 }
1282
1283 PUBLIC enum btrfs_util_error btrfs_util_deleted_subvolumes(const char *path,
1284                                                            uint64_t **ids,
1285                                                            size_t *n)
1286 {
1287         enum btrfs_util_error err;
1288         int fd;
1289
1290         fd = open(path, O_RDONLY);
1291         if (fd == -1)
1292                 return BTRFS_UTIL_ERROR_OPEN_FAILED;
1293
1294         err = btrfs_util_deleted_subvolumes_fd(fd, ids, n);
1295         SAVE_ERRNO_AND_CLOSE(fd);
1296         return err;
1297 }
1298
1299 PUBLIC enum btrfs_util_error btrfs_util_deleted_subvolumes_fd(int fd,
1300                                                               uint64_t **ids,
1301                                                               size_t *n)
1302 {
1303         size_t capacity = 0;
1304         struct btrfs_ioctl_search_args search = {
1305                 .key = {
1306                         .tree_id = BTRFS_ROOT_TREE_OBJECTID,
1307                         .min_objectid = BTRFS_ORPHAN_OBJECTID,
1308                         .max_objectid = BTRFS_ORPHAN_OBJECTID,
1309                         .min_type = BTRFS_ORPHAN_ITEM_KEY,
1310                         .max_type = BTRFS_ORPHAN_ITEM_KEY,
1311                         .min_offset = 0,
1312                         .max_offset = UINT64_MAX,
1313                         .min_transid = 0,
1314                         .max_transid = UINT64_MAX,
1315                         .nr_items = 0,
1316                 },
1317         };
1318         enum btrfs_util_error err;
1319         size_t items_pos = 0, buf_off = 0;
1320         int ret;
1321
1322         *ids = NULL;
1323         *n = 0;
1324         for (;;) {
1325                 const struct btrfs_ioctl_search_header *header;
1326
1327                 if (items_pos >= search.key.nr_items) {
1328                         search.key.nr_items = 4096;
1329                         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &search);
1330                         if (ret == -1) {
1331                                 err = BTRFS_UTIL_ERROR_SEARCH_FAILED;
1332                                 goto out;
1333                         }
1334                         items_pos = 0;
1335                         buf_off = 0;
1336
1337                         if (search.key.nr_items == 0)
1338                                 break;
1339                 }
1340
1341                 header = (struct btrfs_ioctl_search_header *)(search.buf + buf_off);
1342
1343                 /*
1344                  * The orphan item might be for a free space cache inode, so
1345                  * check if there's a matching root item.
1346                  */
1347                 err = btrfs_util_subvolume_info_fd(fd, header->offset, NULL);
1348                 if (!err) {
1349                         if (*n >= capacity) {
1350                                 size_t new_capacity;
1351                                 uint64_t *new_ids;
1352
1353                                 new_capacity = capacity ? capacity * 2 : 1;
1354                                 new_ids = reallocarray(*ids, new_capacity,
1355                                                        sizeof(**ids));
1356                                 if (!new_ids) {
1357                                         err = BTRFS_UTIL_ERROR_NO_MEMORY;
1358                                         goto out;
1359                                 }
1360
1361                                 *ids = new_ids;
1362                                 capacity = new_capacity;
1363                         }
1364                         (*ids)[(*n)++] = header->offset;
1365                 } else if (err != BTRFS_UTIL_ERROR_SUBVOLUME_NOT_FOUND) {
1366                         goto out;
1367                 }
1368
1369                 items_pos++;
1370                 buf_off += sizeof(*header) + header->len;
1371                 search.key.min_offset = header->offset + 1;
1372         }
1373
1374         err = BTRFS_UTIL_OK;
1375 out:
1376         if (err) {
1377                 free(*ids);
1378                 *ids = NULL;
1379                 *n = 0;
1380         }
1381         return err;
1382 }