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