1/*
2 * filefrag.c -- report if a particular file is fragmented
3 *
4 * Copyright 2003 by Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 */
11
12#include "config.h"
13#ifndef __linux__
14#include <stdio.h>
15#include <stdlib.h>
16#include <unistd.h>
17
18int main(void) {
19	fputs("This program is only supported on Linux!\n", stderr);
20	exit(EXIT_FAILURE);
21}
22#else
23#ifndef _LARGEFILE_SOURCE
24#define _LARGEFILE_SOURCE
25#endif
26#ifndef _LARGEFILE64_SOURCE
27#define _LARGEFILE64_SOURCE
28#endif
29
30
31#include <stdio.h>
32#include <stdlib.h>
33#include <unistd.h>
34#include <string.h>
35#include <time.h>
36#include <fcntl.h>
37#include <errno.h>
38#ifdef HAVE_GETOPT_H
39#include <getopt.h>
40#else
41extern char *optarg;
42extern int optind;
43#endif
44#include <sys/types.h>
45#include <sys/stat.h>
46#include <sys/vfs.h>
47#include <sys/ioctl.h>
48#include <linux/fd.h>
49#include <ext2fs/ext2fs.h>
50#include <ext2fs/ext2_types.h>
51#include <ext2fs/fiemap.h>
52
53int verbose = 0;
54int blocksize;		/* Use specified blocksize (default 1kB) */
55int sync_file = 0;	/* fsync file before getting the mapping */
56int xattr_map = 0;	/* get xattr mapping */
57int force_bmap;	/* force use of FIBMAP instead of FIEMAP */
58int force_extent;	/* print output in extent format always */
59int logical_width = 8;
60int physical_width = 10;
61const char *ext_fmt = "%4d: %*llu..%*llu: %*llu..%*llu: %6llu: %s\n";
62const char *hex_fmt = "%4d: %*llx..%*llx: %*llx..%*llx: %6llx: %s\n";
63
64#define FILEFRAG_FIEMAP_FLAGS_COMPAT (FIEMAP_FLAG_SYNC | FIEMAP_FLAG_XATTR)
65
66#define FIBMAP		_IO(0x00, 1)	/* bmap access */
67#define FIGETBSZ	_IO(0x00, 2)	/* get the block size used for bmap */
68
69#define LUSTRE_SUPER_MAGIC 0x0BD00BD0
70
71#define	EXT4_EXTENTS_FL			0x00080000 /* Inode uses extents */
72#define	EXT3_IOC_GETFLAGS		_IOR('f', 1, long)
73
74static int int_log2(int arg)
75{
76	int     l = 0;
77
78	arg >>= 1;
79	while (arg) {
80		l++;
81		arg >>= 1;
82	}
83	return l;
84}
85
86static int int_log10(unsigned long long arg)
87{
88	int     l = 0;
89
90	arg = arg / 10;
91	while (arg) {
92		l++;
93		arg = arg / 10;
94	}
95	return l;
96}
97
98static unsigned int div_ceil(unsigned int a, unsigned int b)
99{
100	if (!a)
101		return 0;
102	return ((a - 1) / b) + 1;
103}
104
105static int get_bmap(int fd, unsigned long block, unsigned long *phy_blk)
106{
107	int	ret;
108	unsigned int b;
109
110	b = block;
111	ret = ioctl(fd, FIBMAP, &b); /* FIBMAP takes pointer to integer */
112	if (ret < 0)
113		return -errno;
114	*phy_blk = b;
115
116	return ret;
117}
118
119static void print_extent_header(void)
120{
121	printf(" ext: %*s %*s length: %*s flags:\n",
122	       logical_width * 2 + 3,
123	       "logical_offset:",
124	       physical_width * 2 + 3, "physical_offset:",
125	       physical_width + 1,
126	       "expected:");
127}
128
129static void print_flag(__u32 *flags, __u32 mask, char *buf, const char *name)
130{
131	if ((*flags & mask) == 0)
132		return;
133
134	strcat(buf, name);
135	*flags &= ~mask;
136}
137
138static void print_extent_info(struct fiemap_extent *fm_extent, int cur_ex,
139			      unsigned long long expected, int blk_shift,
140			      ext2fs_struct_stat *st)
141{
142	unsigned long long physical_blk;
143	unsigned long long logical_blk;
144	unsigned long long ext_len;
145	unsigned long long ext_blks;
146	__u32 fe_flags, mask;
147	char flags[256] = "";
148
149	/* For inline data all offsets should be in bytes, not blocks */
150	if (fm_extent->fe_flags & FIEMAP_EXTENT_DATA_INLINE)
151		blk_shift = 0;
152
153	ext_len = fm_extent->fe_length >> blk_shift;
154	ext_blks = (fm_extent->fe_length - 1) >> blk_shift;
155	logical_blk = fm_extent->fe_logical >> blk_shift;
156	if (fm_extent->fe_flags & FIEMAP_EXTENT_UNKNOWN) {
157		physical_blk = 0;
158	} else {
159		physical_blk = fm_extent->fe_physical >> blk_shift;
160	}
161
162	if (expected)
163		sprintf(flags, ext_fmt == hex_fmt ? "%*llx: " : "%*llu: ",
164			physical_width, expected >> blk_shift);
165	else
166		sprintf(flags, "%.*s  ", physical_width, "                   ");
167
168	fe_flags = fm_extent->fe_flags;
169	print_flag(&fe_flags, FIEMAP_EXTENT_LAST, flags, "last,");
170	print_flag(&fe_flags, FIEMAP_EXTENT_UNKNOWN, flags, "unknown_loc,");
171	print_flag(&fe_flags, FIEMAP_EXTENT_DELALLOC, flags, "delalloc,");
172	print_flag(&fe_flags, FIEMAP_EXTENT_ENCODED, flags, "encoded,");
173	print_flag(&fe_flags, FIEMAP_EXTENT_DATA_ENCRYPTED, flags,"encrypted,");
174	print_flag(&fe_flags, FIEMAP_EXTENT_NOT_ALIGNED, flags, "not_aligned,");
175	print_flag(&fe_flags, FIEMAP_EXTENT_DATA_INLINE, flags, "inline,");
176	print_flag(&fe_flags, FIEMAP_EXTENT_DATA_TAIL, flags, "tail_packed,");
177	print_flag(&fe_flags, FIEMAP_EXTENT_UNWRITTEN, flags, "unwritten,");
178	print_flag(&fe_flags, FIEMAP_EXTENT_MERGED, flags, "merged,");
179	print_flag(&fe_flags, FIEMAP_EXTENT_SHARED, flags, "shared,");
180	/* print any unknown flags as hex values */
181	for (mask = 1; fe_flags != 0 && mask != 0; mask <<= 1) {
182		char hex[6];
183
184		if ((fe_flags & mask) == 0)
185			continue;
186		sprintf(hex, "%#04x,", mask);
187		print_flag(&fe_flags, mask, flags, hex);
188	}
189
190	if (fm_extent->fe_logical + fm_extent->fe_length >=
191	    (unsigned long long) st->st_size)
192		strcat(flags, "eof,");
193
194	/* Remove trailing comma, if any */
195	if (flags[0] != '\0')
196		flags[strnlen(flags, sizeof(flags)) - 1] = '\0';
197
198	printf(ext_fmt, cur_ex, logical_width, logical_blk,
199	       logical_width, logical_blk + ext_blks,
200	       physical_width, physical_blk,
201	       physical_width, physical_blk + ext_blks,
202	       ext_len, flags);
203}
204
205static int filefrag_fiemap(int fd, int blk_shift, int *num_extents,
206			   ext2fs_struct_stat *st)
207{
208	__u64 buf[2048];	/* __u64 for proper field alignment */
209	struct fiemap *fiemap = (struct fiemap *)buf;
210	struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
211	struct fiemap_extent fm_last = {0};
212	int count = (sizeof(buf) - sizeof(*fiemap)) /
213			sizeof(struct fiemap_extent);
214	unsigned long long expected = 0;
215	unsigned long long expected_dense = 0;
216	unsigned long flags = 0;
217	unsigned int i;
218	int fiemap_header_printed = 0;
219	int tot_extents = 0, n = 0;
220	int last = 0;
221	int rc;
222
223	memset(fiemap, 0, sizeof(struct fiemap));
224
225	if (sync_file)
226		flags |= FIEMAP_FLAG_SYNC;
227
228	if (xattr_map)
229		flags |= FIEMAP_FLAG_XATTR;
230
231	do {
232		fiemap->fm_length = ~0ULL;
233		fiemap->fm_flags = flags;
234		fiemap->fm_extent_count = count;
235		rc = ioctl(fd, FS_IOC_FIEMAP, (unsigned long) fiemap);
236		if (rc < 0) {
237			static int fiemap_incompat_printed;
238
239			rc = -errno;
240			if (rc == -EBADR && !fiemap_incompat_printed) {
241				fprintf(stderr, "FIEMAP failed with unknown "
242						"flags %x\n",
243				       fiemap->fm_flags);
244				fiemap_incompat_printed = 1;
245			}
246			return rc;
247		}
248
249		/* If 0 extents are returned, then more ioctls are not needed */
250		if (fiemap->fm_mapped_extents == 0)
251			break;
252
253		if (verbose && !fiemap_header_printed) {
254			print_extent_header();
255			fiemap_header_printed = 1;
256		}
257
258		for (i = 0; i < fiemap->fm_mapped_extents; i++) {
259			expected_dense = fm_last.fe_physical +
260					 fm_last.fe_length;
261			expected = fm_last.fe_physical +
262				   fm_ext[i].fe_logical - fm_last.fe_logical;
263			if (fm_ext[i].fe_logical != 0 &&
264			    fm_ext[i].fe_physical != expected &&
265			    fm_ext[i].fe_physical != expected_dense) {
266				tot_extents++;
267			} else {
268				expected = 0;
269				if (!tot_extents)
270					tot_extents = 1;
271			}
272			if (verbose)
273				print_extent_info(&fm_ext[i], n, expected,
274						  blk_shift, st);
275			if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
276				last = 1;
277			fm_last = fm_ext[i];
278			n++;
279		}
280
281		fiemap->fm_start = (fm_ext[i - 1].fe_logical +
282				    fm_ext[i - 1].fe_length);
283	} while (last == 0);
284
285	*num_extents = tot_extents;
286
287	return 0;
288}
289
290#define EXT2_DIRECT	12
291
292static int filefrag_fibmap(int fd, int blk_shift, int *num_extents,
293			   ext2fs_struct_stat *st,
294			   unsigned long numblocks, int is_ext2)
295{
296	struct fiemap_extent	fm_ext, fm_last;
297	unsigned long		i, last_block;
298	unsigned long long	logical, expected = 0;
299				/* Blocks per indirect block */
300	const long		bpib = st->st_blksize / 4;
301	int			count;
302
303	memset(&fm_ext, 0, sizeof(fm_ext));
304	memset(&fm_last, 0, sizeof(fm_last));
305	if (force_extent) {
306		fm_ext.fe_flags = FIEMAP_EXTENT_MERGED;
307	}
308
309	if (sync_file)
310		fsync(fd);
311
312	for (i = 0, logical = 0, *num_extents = 0, count = last_block = 0;
313	     i < numblocks;
314	     i++, logical += st->st_blksize) {
315		unsigned long block = 0;
316		int rc;
317
318		if (is_ext2 && last_block) {
319			if (((i - EXT2_DIRECT) % bpib) == 0)
320				last_block++;
321			if (((i - EXT2_DIRECT - bpib) % (bpib * bpib)) == 0)
322				last_block++;
323			if (((i - EXT2_DIRECT - bpib - bpib * bpib) %
324			     (((unsigned long long)bpib) * bpib * bpib)) == 0)
325				last_block++;
326		}
327		rc = get_bmap(fd, i, &block);
328		if (rc < 0)
329			return rc;
330		if (block == 0)
331			continue;
332
333		if (*num_extents == 0 || block != last_block + 1 ||
334		    fm_ext.fe_logical + fm_ext.fe_length != logical) {
335			/*
336			 * This is the start of a new extent; figure out where
337			 * we expected it to be and report the extent.
338			 */
339			if (*num_extents != 0 && fm_last.fe_length) {
340				expected = fm_last.fe_physical +
341					(fm_ext.fe_logical - fm_last.fe_logical);
342				if (expected == fm_ext.fe_physical)
343					expected = 0;
344			}
345			if (force_extent && *num_extents == 0)
346				print_extent_header();
347			if (force_extent && *num_extents != 0) {
348				print_extent_info(&fm_ext, *num_extents - 1,
349						  expected, blk_shift, st);
350			}
351			if (verbose && expected != 0) {
352				printf("Discontinuity: Block %llu is at %llu "
353				       "(was %llu)\n",
354					fm_ext.fe_logical / st->st_blksize,
355					fm_ext.fe_physical / st->st_blksize,
356					expected / st->st_blksize);
357			}
358			/* create the new extent */
359			fm_last = fm_ext;
360			(*num_extents)++;
361			fm_ext.fe_physical = block * st->st_blksize;
362			fm_ext.fe_logical = logical;
363			fm_ext.fe_length = 0;
364		}
365		fm_ext.fe_length += st->st_blksize;
366		last_block = block;
367	}
368	if (force_extent && *num_extents != 0) {
369		if (fm_last.fe_length) {
370			expected = fm_last.fe_physical +
371				   (fm_ext.fe_logical - fm_last.fe_logical);
372			if (expected == fm_ext.fe_physical)
373				expected = 0;
374		}
375		print_extent_info(&fm_ext, *num_extents - 1, expected,
376				  blk_shift, st);
377	}
378
379	return count;
380}
381
382static int frag_report(const char *filename)
383{
384	static struct statfs fsinfo;
385	static unsigned int blksize;
386	ext2fs_struct_stat st;
387	int		blk_shift;
388	long		fd;
389	unsigned long long	numblocks;
390	int		data_blocks_per_cyl = 1;
391	int		num_extents = 1, expected = ~0;
392	int		is_ext2 = 0;
393	static dev_t	last_device;
394	int		width;
395	int		rc = 0;
396
397#if defined(HAVE_OPEN64) && !defined(__OSX_AVAILABLE_BUT_DEPRECATED)
398	fd = open64(filename, O_RDONLY);
399#else
400	fd = open(filename, O_RDONLY);
401#endif
402	if (fd < 0) {
403		rc = -errno;
404		perror("open");
405		return rc;
406	}
407
408#if defined(HAVE_FSTAT64) && !defined(__OSX_AVAILABLE_BUT_DEPRECATED)
409	if (fstat64(fd, &st) < 0) {
410#else
411	if (fstat(fd, &st) < 0) {
412#endif
413		rc = -errno;
414		perror("stat");
415		goto out_close;
416	}
417
418	if (last_device != st.st_dev) {
419		if (fstatfs(fd, &fsinfo) < 0) {
420			rc = -errno;
421			perror("fstatfs");
422			goto out_close;
423		}
424		if (ioctl(fd, FIGETBSZ, &blksize) < 0)
425			blksize = fsinfo.f_bsize;
426		if (verbose)
427			printf("Filesystem type is: %lx\n",
428			       (unsigned long)fsinfo.f_type);
429	}
430	st.st_blksize = blksize;
431	if (fsinfo.f_type == 0xef51 || fsinfo.f_type == 0xef52 ||
432	    fsinfo.f_type == 0xef53) {
433		unsigned int	flags;
434
435		if (ioctl(fd, EXT3_IOC_GETFLAGS, &flags) == 0 &&
436		    !(flags & EXT4_EXTENTS_FL))
437			is_ext2 = 1;
438	}
439
440	if (is_ext2) {
441		long cylgroups = div_ceil(fsinfo.f_blocks, blksize * 8);
442
443		if (verbose && last_device != st.st_dev)
444			printf("Filesystem cylinder groups approximately %ld\n",
445			       cylgroups);
446
447		data_blocks_per_cyl = blksize * 8 -
448					(fsinfo.f_files / 8 / cylgroups) - 3;
449	}
450	last_device = st.st_dev;
451
452	width = int_log10(fsinfo.f_blocks);
453	if (width > physical_width)
454		physical_width = width;
455
456	numblocks = (st.st_size + blksize - 1) / blksize;
457	if (blocksize != 0)
458		blk_shift = int_log2(blocksize);
459	else
460		blk_shift = int_log2(blksize);
461
462	width = int_log10(numblocks);
463	if (width > logical_width)
464		logical_width = width;
465	if (verbose)
466		printf("File size of %s is %llu (%llu block%s of %d bytes)\n",
467		       filename, (unsigned long long)st.st_size,
468		       numblocks * blksize >> blk_shift,
469		       numblocks == 1 ? "" : "s", 1 << blk_shift);
470
471	if (!force_bmap) {
472		rc = filefrag_fiemap(fd, blk_shift, &num_extents, &st);
473		expected = 0;
474	}
475
476	if (force_bmap || rc < 0) { /* FIEMAP failed, try FIBMAP instead */
477		expected = filefrag_fibmap(fd, blk_shift, &num_extents,
478					   &st, numblocks, is_ext2);
479		if (expected < 0) {
480			if (expected == -EINVAL || expected == -ENOTTY) {
481				fprintf(stderr, "%s: FIBMAP unsupported\n",
482					filename);
483			} else if (expected == -EPERM) {
484				fprintf(stderr,
485					"%s: FIBMAP requires root privileges\n",
486					filename);
487			} else {
488				fprintf(stderr, "%s: FIBMAP error: %s",
489					filename, strerror(expected));
490			}
491			rc = expected;
492			goto out_close;
493		} else {
494			rc = 0;
495		}
496		expected = expected / data_blocks_per_cyl + 1;
497	}
498
499	if (num_extents == 1)
500		printf("%s: 1 extent found", filename);
501	else
502		printf("%s: %d extents found", filename, num_extents);
503	/* count, and thus expected, only set for indirect FIBMAP'd files */
504	if (is_ext2 && expected && expected < num_extents)
505		printf(", perfection would be %d extent%s\n", expected,
506			(expected > 1) ? "s" : "");
507	else
508		fputc('\n', stdout);
509out_close:
510	close(fd);
511
512	return rc;
513}
514
515static void usage(const char *progname)
516{
517	fprintf(stderr, "Usage: %s [-b{blocksize}] [-BeksvxX] file ...\n",
518		progname);
519	exit(1);
520}
521
522int main(int argc, char**argv)
523{
524	char **cpp;
525	int rc = 0, c;
526
527	while ((c = getopt(argc, argv, "Bb::eksvxX")) != EOF) {
528		switch (c) {
529		case 'B':
530			force_bmap++;
531			break;
532		case 'b':
533			if (optarg) {
534				char *end;
535				blocksize = strtoul(optarg, &end, 0);
536				if (end) {
537					switch (end[0]) {
538					case 'g':
539					case 'G':
540						blocksize *= 1024;
541						/* no break */
542					case 'm':
543					case 'M':
544						blocksize *= 1024;
545						/* no break */
546					case 'k':
547					case 'K':
548						blocksize *= 1024;
549						break;
550					default:
551						break;
552					}
553				}
554			} else { /* Allow -b without argument for compat. Remove
555				  * this eventually so "-b {blocksize}" works */
556				fprintf(stderr, "%s: -b needs a blocksize "
557					"option, assuming 1024-byte blocks.\n",
558					argv[0]);
559				blocksize = 1024;
560			}
561			break;
562		case 'e':
563			force_extent++;
564			if (!verbose)
565				verbose++;
566			break;
567		case 'k':
568			blocksize = 1024;
569			break;
570		case 's':
571			sync_file++;
572			break;
573		case 'v':
574			verbose++;
575			break;
576		case 'x':
577			xattr_map++;
578			break;
579		case 'X':
580			ext_fmt = hex_fmt;
581			break;
582		default:
583			usage(argv[0]);
584			break;
585		}
586	}
587
588	if (optind == argc)
589		usage(argv[0]);
590
591	for (cpp = argv + optind; *cpp != '\0'; cpp++) {
592		int rc2 = frag_report(*cpp);
593
594		if (rc2 < 0 && rc == 0)
595			rc = rc2;
596	}
597
598	return -rc;
599}
600#endif
601