2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public
4 * License v2 as published by the Free Software Foundation.
6 * This program is distributed in the hope that it will be useful,
7 * but WITHOUT ANY WARRANTY; without even the implied warranty of
8 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9 * General Public License for more details.
11 * You should have received a copy of the GNU General Public
12 * License along with this program; if not, write to the
13 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
14 * Boston, MA 021110-1307, USA.
17 #include <sys/types.h>
28 #include <sys/ioctl.h>
30 #include <linux/fiemap.h>
34 #include "kerncompat.h"
37 #include "interval_tree_generic.h"
39 static int summarize
= 0;
40 static unsigned unit_mode
= UNITS_RAW
;
41 static char path
[PATH_MAX
] = { 0, };
42 static char *pathp
= path
;
43 static char *path_max
= &path
[PATH_MAX
- 1];
45 struct shared_extent
{
47 u64 start
; /* Start of interval */
48 u64 last
; /* Last location _in_ interval */
53 * extent_tree_* functions are defined in the massive interval tree
54 * macro below. This serves to illustrate the api in human-readable
58 extent_tree_insert(struct shared_extent
*node
, struct rb_root
*root
);
61 extent_tree_remove(struct shared_extent
*node
, struct rb_root
*root
);
63 static struct shared_extent
*
64 extent_tree_iter_first(struct rb_root
*root
,
67 static struct shared_extent
*
68 extent_tree_iter_next(struct shared_extent
*node
,
71 #define START(node) ((node)->start)
72 #define LAST(node) ((node)->last)
74 INTERVAL_TREE_DEFINE(struct shared_extent
, rb
,
76 START
, LAST
, static, extent_tree
)
78 static int add_shared_extent(u64 start
, u64 len
, struct rb_root
*root
)
80 struct shared_extent
*sh
;
84 sh
= calloc(1, sizeof(*sh
));
89 sh
->last
= (start
+ len
- 1);
91 extent_tree_insert(sh
, root
);
96 static void cleanup_shared_extents(struct rb_root
*root
)
98 struct shared_extent
*s
;
99 struct shared_extent
*tmp
;
104 s
= extent_tree_iter_first(root
, 0, -1ULL);
106 tmp
= extent_tree_iter_next(s
, 0, -1ULL);
107 extent_tree_remove(s
, root
);
117 * Find all extents which overlap 'n', calculate the space
118 * covered by them and remove those nodes from the tree.
120 static u64
count_unique_bytes(struct rb_root
*root
, struct shared_extent
*n
)
122 struct shared_extent
*tmp
;
123 u64 wstart
= n
->start
;
126 dprintf("Count overlaps:");
130 * Expand our search window based on the lastest
131 * overlapping extent. Doing this will allow us to
132 * find all possible overlaps
134 if (wstart
> n
->start
)
139 dprintf(" (%llu, %llu)", n
->start
, n
->last
);
142 n
= extent_tree_iter_next(n
, wstart
, wlast
);
144 extent_tree_remove(tmp
, root
);
148 dprintf("; wstart: %llu wlast: %llu total: %llu\n", wstart
,
149 wlast
, wlast
- wstart
+ 1);
151 return wlast
- wstart
+ 1;
155 * What we want to do here is get a count of shared bytes within the
156 * set of extents we have collected. Specifically, we don't want to
157 * count any byte more than once, so just adding them up doesn't
160 * For each set of overlapping extents we find the lowest start and
161 * highest end. From there we have the actual number of bytes which is
162 * shared across all of the extents in our set. A sum of each sets
163 * extent length is returned.
165 static void count_shared_bytes(struct rb_root
*root
, u64
*ret_cnt
)
168 struct shared_extent
*s
= extent_tree_iter_first(root
,
176 * Find all extents which overlap 's', calculate the space
177 * covered by them and remove those nodes from the tree.
179 count
+= count_unique_bytes(root
, s
);
182 * Since count_unique_bytes will be emptying the tree,
183 * we can grab the first node here
185 s
= extent_tree_iter_first(root
, 0, -1ULL);
188 BUG_ON(!RB_EMPTY_ROOT(root
));
193 /* Track which inodes we've seen for the purposes of hardlink detection. */
195 struct rb_node i_node
;
199 static struct rb_root seen_inodes
= RB_ROOT
;
201 static int cmp_si(struct seen_inode
*si
, u64 ino
, u64 subvol
)
205 else if (ino
> si
->i_ino
)
207 if (subvol
< si
->i_subvol
)
209 else if (subvol
> si
->i_subvol
)
214 static int mark_inode_seen(u64 ino
, u64 subvol
)
217 struct rb_node
**p
= &seen_inodes
.rb_node
;
218 struct rb_node
*parent
= NULL
;
219 struct seen_inode
*si
;
224 si
= rb_entry(parent
, struct seen_inode
, i_node
);
225 cmp
= cmp_si(si
, ino
, subvol
);
234 si
= calloc(1, sizeof(*si
));
239 si
->i_subvol
= subvol
;
241 rb_link_node(&si
->i_node
, parent
, p
);
242 rb_insert_color(&si
->i_node
, &seen_inodes
);
247 static int inode_seen(u64 ino
, u64 subvol
)
250 struct rb_node
*n
= seen_inodes
.rb_node
;
251 struct seen_inode
*si
;
254 si
= rb_entry(n
, struct seen_inode
, i_node
);
256 cmp
= cmp_si(si
, ino
, subvol
);
267 static void clear_seen_inodes(void)
269 struct rb_node
*n
= rb_first(&seen_inodes
);
270 struct seen_inode
*si
;
273 si
= rb_entry(n
, struct seen_inode
, i_node
);
275 rb_erase(&si
->i_node
, &seen_inodes
);
278 n
= rb_first(&seen_inodes
);
283 * Inline extents are skipped because they do not take data space,
284 * delalloc and unknown are skipped because we do not know how much
285 * space they will use yet.
287 #define SKIP_FLAGS (FIEMAP_EXTENT_UNKNOWN|FIEMAP_EXTENT_DELALLOC|FIEMAP_EXTENT_DATA_INLINE)
288 static int du_calc_file_space(int fd
, struct rb_root
*shared_extents
,
289 u64
*ret_total
, u64
*ret_shared
)
292 struct fiemap
*fiemap
= (struct fiemap
*)buf
;
293 struct fiemap_extent
*fm_ext
= &fiemap
->fm_extents
[0];
294 int count
= (sizeof(buf
) - sizeof(*fiemap
)) /
295 sizeof(struct fiemap_extent
);
304 memset(fiemap
, 0, sizeof(struct fiemap
));
307 fiemap
->fm_length
= ~0ULL;
308 fiemap
->fm_extent_count
= count
;
309 rc
= ioctl(fd
, FS_IOC_FIEMAP
, (unsigned long) fiemap
);
315 /* If 0 extents are returned, then more ioctls are not needed */
316 if (fiemap
->fm_mapped_extents
== 0)
319 for (i
= 0; i
< fiemap
->fm_mapped_extents
; i
++) {
320 ext_len
= fm_ext
[i
].fe_length
;
321 flags
= fm_ext
[i
].fe_flags
;
323 if (flags
& FIEMAP_EXTENT_LAST
)
326 if (flags
& SKIP_FLAGS
)
329 file_total
+= ext_len
;
330 if (flags
& FIEMAP_EXTENT_SHARED
) {
331 file_shared
+= ext_len
;
333 if (shared_extents
) {
334 ret
= add_shared_extent(fm_ext
[i
].fe_physical
,
343 fiemap
->fm_start
= (fm_ext
[i
- 1].fe_logical
+
344 fm_ext
[i
- 1].fe_length
);
347 *ret_total
= file_total
;
348 *ret_shared
= file_shared
;
359 struct rb_root shared_extents
;
361 #define INIT_DU_DIR_CTXT (struct du_dir_ctxt) { 0ULL, 0ULL, NULL, RB_ROOT }
363 static int du_add_file(const char *filename
, int dirfd
,
364 struct rb_root
*shared_extents
, u64
*ret_total
,
365 u64
*ret_shared
, int top_level
);
367 static int du_walk_dir(struct du_dir_ctxt
*ctxt
, struct rb_root
*shared_extents
)
370 struct dirent
*entry
;
371 DIR *dirstream
= ctxt
->dirstream
;
378 entry
= readdir(dirstream
);
380 if (strcmp(entry
->d_name
, ".") == 0
381 || strcmp(entry
->d_name
, "..") == 0)
384 type
= entry
->d_type
;
385 if (type
== DT_REG
|| type
== DT_DIR
) {
388 ret
= du_add_file(entry
->d_name
,
390 shared_extents
, &tot
, &shr
,
395 ctxt
->bytes_total
+= tot
;
396 ctxt
->bytes_shared
+= shr
;
399 } while (entry
!= NULL
);
404 static int du_add_file(const char *filename
, int dirfd
,
405 struct rb_root
*shared_extents
, u64
*ret_total
,
406 u64
*ret_shared
, int top_level
)
408 int ret
, len
= strlen(filename
);
411 struct du_dir_ctxt dir
= INIT_DU_DIR_CTXT
;
415 u64 dir_set_shared
= 0;
418 DIR *dirstream
= NULL
;
420 ret
= fstatat(dirfd
, filename
, &st
, 0);
424 if (!S_ISREG(st
.st_mode
) && !S_ISDIR(st
.st_mode
))
427 if (len
> (path_max
- pathp
)) {
428 error("path too long: %s %s", path
, filename
);
429 return -ENAMETOOLONG
;
434 ret
= sprintf(pathp
, "%s", filename
);
436 ret
= sprintf(pathp
, "/%s", filename
);
439 fd
= open_file_or_dir3(path
, &dirstream
, O_RDONLY
);
445 ret
= lookup_ino_rootid(fd
, &subvol
);
449 if (inode_seen(st
.st_ino
, subvol
))
452 ret
= mark_inode_seen(st
.st_ino
, subvol
);
456 if (S_ISREG(st
.st_mode
)) {
457 ret
= du_calc_file_space(fd
, shared_extents
, &file_total
,
461 } else if (S_ISDIR(st
.st_mode
)) {
462 struct rb_root
*root
= shared_extents
;
465 * We collect shared extents in an rb_root, the top
466 * level caller will not pass a root down, so use the
467 * one on our dir context.
470 root
= &dir
.shared_extents
;
474 dir
.dirstream
= dirstream
;
475 ret
= du_walk_dir(&dir
, root
);
479 cleanup_shared_extents(root
);
483 file_total
= dir
.bytes_total
;
484 file_shared
= dir
.bytes_shared
;
486 count_shared_bytes(root
, &dir_set_shared
);
489 if (!summarize
|| top_level
) {
490 u64 excl
= file_total
- file_shared
;
493 u64 set_shared
= file_shared
;
496 set_shared
= dir_set_shared
;
498 printf("%10s %10s %10s %s\n",
499 pretty_size_mode(file_total
, unit_mode
),
500 pretty_size_mode(excl
, unit_mode
),
501 pretty_size_mode(set_shared
, unit_mode
),
504 printf("%10s %10s %10s %s\n",
505 pretty_size_mode(file_total
, unit_mode
),
506 pretty_size_mode(excl
, unit_mode
),
512 *ret_total
= file_total
;
514 *ret_shared
= file_shared
;
517 close_file_or_dir(fd
, dirstream
);
519 /* reset path to just before this element */
525 const char * const cmd_filesystem_du_usage
[] = {
526 "btrfs filesystem du [options] <path> [<path>..]",
527 "Summarize disk usage of each file.",
528 "-s|--summarize display only a total for each argument",
533 int cmd_filesystem_du(int argc
, char **argv
)
535 int ret
= 0, err
= 0;
538 unit_mode
= get_unit_mode_from_arg(&argc
, argv
, 1);
542 static const struct option long_options
[] = {
543 { "summarize", no_argument
, NULL
, 's'},
546 int c
= getopt_long(argc
, argv
, "s", long_options
, NULL
);
555 usage(cmd_filesystem_du_usage
);
559 if (check_argc_min(argc
- optind
, 1))
560 usage(cmd_filesystem_du_usage
);
562 printf("%10s %10s %10s %s\n", "Total", "Exclusive", "Set shared",
565 for (i
= optind
; i
< argc
; i
++) {
566 ret
= du_add_file(argv
[i
], AT_FDCWD
, NULL
, NULL
, NULL
, 1);
568 error("cannot check space of '%s': %s", argv
[i
],
573 /* reset hard-link detection for each argument */