1/*
2 * e2freefrag - report filesystem free-space fragmentation
3 *
4 * Copyright (C) 2009 Sun Microsystems, Inc.
5 *
6 * Author: Rupesh Thakare <rupesh@sun.com>
7 *         Andreas Dilger <adilger@sun.com>
8 *
9 * %Begin-Header%
10 * This file may be redistributed under the terms of the GNU Public
11 * License version 2.
12 * %End-Header%
13 */
14#include <stdio.h>
15#ifdef HAVE_UNISTD_H
16#include <unistd.h>
17#endif
18#ifdef HAVE_STDLIB_H
19#include <stdlib.h>
20#endif
21#ifdef HAVE_GETOPT_H
22#include <getopt.h>
23#else
24extern char *optarg;
25extern int optind;
26#endif
27
28#include "ext2fs/ext2_fs.h"
29#include "ext2fs/ext2fs.h"
30#include "e2freefrag.h"
31
32static void usage(const char *prog)
33{
34	fprintf(stderr, "usage: %s [-c chunksize in kb] [-h] "
35		"device_name\n", prog);
36#ifndef DEBUGFS
37	exit(1);
38#endif
39}
40
41static int ul_log2(unsigned long arg)
42{
43        int     l = 0;
44
45        arg >>= 1;
46        while (arg) {
47                l++;
48                arg >>= 1;
49        }
50        return l;
51}
52
53static void init_chunk_info(ext2_filsys fs, struct chunk_info *info)
54{
55	int i;
56
57	info->blocksize_bits = ul_log2((unsigned long)fs->blocksize);
58	if (info->chunkbytes) {
59		info->chunkbits = ul_log2(info->chunkbytes);
60		info->blks_in_chunk = info->chunkbytes >> info->blocksize_bits;
61	} else {
62		info->chunkbits = ul_log2(DEFAULT_CHUNKSIZE);
63		info->blks_in_chunk = DEFAULT_CHUNKSIZE >> info->blocksize_bits;
64	}
65
66	info->min = ~0UL;
67	info->max = info->avg = 0;
68	info->real_free_chunks = 0;
69
70	for (i = 0; i < MAX_HIST; i++) {
71		info->histogram.fc_chunks[i] = 0;
72		info->histogram.fc_blocks[i] = 0;
73	}
74}
75
76static void update_chunk_stats(struct chunk_info *info,
77			       unsigned long chunk_size)
78{
79	unsigned long idx;
80
81	idx = ul_log2(chunk_size) + 1;
82	if (idx >= MAX_HIST)
83		idx = MAX_HIST-1;
84	info->histogram.fc_chunks[idx]++;
85	info->histogram.fc_blocks[idx] += chunk_size;
86
87	if (chunk_size > info->max)
88		info->max = chunk_size;
89	if (chunk_size < info->min)
90		info->min = chunk_size;
91	info->avg += chunk_size;
92	info->real_free_chunks++;
93}
94
95static void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
96{
97	unsigned long long blocks_count = ext2fs_blocks_count(fs->super);
98	unsigned long long chunks = (blocks_count + info->blks_in_chunk) >>
99				(info->chunkbits - info->blocksize_bits);
100	unsigned long long chunk_num;
101	unsigned long last_chunk_size = 0;
102	unsigned long long chunk_start_blk = 0;
103	int used;
104
105	for (chunk_num = 0; chunk_num < chunks; chunk_num++) {
106		unsigned long long blk, num_blks;
107		int chunk_free;
108
109		/* Last chunk may be smaller */
110		if (chunk_start_blk + info->blks_in_chunk > blocks_count)
111			num_blks = blocks_count - chunk_start_blk;
112		else
113			num_blks = info->blks_in_chunk;
114
115		chunk_free = 0;
116
117		/* Initialize starting block for first chunk correctly else
118		 * there is a segfault when blocksize = 1024 in which case
119		 * block_map->start = 1 */
120		for (blk = 0; blk < num_blks; blk++, chunk_start_blk++) {
121			if (chunk_num == 0 && blk == 0) {
122				blk = fs->super->s_first_data_block;
123				chunk_start_blk = blk;
124			}
125			used = ext2fs_fast_test_block_bitmap2(fs->block_map,
126				chunk_start_blk >> fs->cluster_ratio_bits);
127			if (!used) {
128				last_chunk_size++;
129				chunk_free++;
130			}
131
132			if (used && last_chunk_size != 0) {
133				update_chunk_stats(info, last_chunk_size);
134				last_chunk_size = 0;
135			}
136		}
137
138		if (chunk_free == info->blks_in_chunk)
139			info->free_chunks++;
140	}
141	if (last_chunk_size != 0)
142		update_chunk_stats(info, last_chunk_size);
143}
144
145static errcode_t get_chunk_info(ext2_filsys fs, struct chunk_info *info,
146				FILE *f)
147{
148	unsigned long total_chunks;
149	const char *unitp = "KMGTPEZY";
150	int units = 10;
151	unsigned long start = 0, end;
152	int i, retval = 0;
153
154	scan_block_bitmap(fs, info);
155
156	fprintf(f, "Total blocks: %llu\nFree blocks: %u (%0.1f%%)\n",
157		ext2fs_blocks_count(fs->super), fs->super->s_free_blocks_count,
158		(double)fs->super->s_free_blocks_count * 100 /
159		ext2fs_blocks_count(fs->super));
160
161	if (info->chunkbytes) {
162		fprintf(f, "\nChunksize: %lu bytes (%u blocks)\n",
163			info->chunkbytes, info->blks_in_chunk);
164		total_chunks = (ext2fs_blocks_count(fs->super) +
165				info->blks_in_chunk) >>
166			(info->chunkbits - info->blocksize_bits);
167		fprintf(f, "Total chunks: %lu\nFree chunks: %lu (%0.1f%%)\n",
168			total_chunks, info->free_chunks,
169			(double)info->free_chunks * 100 / total_chunks);
170	}
171
172	/* Display chunk information in KB */
173	if (info->real_free_chunks) {
174		unsigned int scale = fs->blocksize >> 10;
175		info->min = info->min * scale;
176		info->max = info->max * scale;
177		info->avg = info->avg / info->real_free_chunks * scale;
178	} else {
179		info->min = 0;
180	}
181
182	fprintf(f, "\nMin. free extent: %lu KB \nMax. free extent: %lu KB\n"
183		"Avg. free extent: %lu KB\n", info->min, info->max, info->avg);
184	fprintf(f, "Num. free extent: %lu\n", info->real_free_chunks);
185
186	fprintf(f, "\nHISTOGRAM OF FREE EXTENT SIZES:\n");
187	fprintf(f, "%s :  %12s  %12s  %7s\n", "Extent Size Range",
188		"Free extents", "Free Blocks", "Percent");
189	for (i = 0; i < MAX_HIST; i++) {
190		end = 1 << (i + info->blocksize_bits - units);
191		if (info->histogram.fc_chunks[i] != 0) {
192			char end_str[32];
193
194			sprintf(end_str, "%5lu%c-", end, *unitp);
195			if (i == MAX_HIST-1)
196				strcpy(end_str, "max ");
197			fprintf(f, "%5lu%c...%7s  :  %12lu  %12lu  %6.2f%%\n",
198				start, *unitp, end_str,
199				info->histogram.fc_chunks[i],
200				info->histogram.fc_blocks[i],
201				(double)info->histogram.fc_blocks[i] * 100 /
202				fs->super->s_free_blocks_count);
203		}
204		start = end;
205		if (start == 1<<10) {
206			start = 1;
207			units += 10;
208			unitp++;
209		}
210	}
211
212	return retval;
213}
214
215static void close_device(char *device_name, ext2_filsys fs)
216{
217	int retval = ext2fs_close(fs);
218
219	if (retval)
220		com_err(device_name, retval, "while closing the filesystem.\n");
221}
222
223static void collect_info(ext2_filsys fs, struct chunk_info *chunk_info, FILE *f)
224{
225	unsigned int retval = 0;
226
227	fprintf(f, "Device: %s\n", fs->device_name);
228	fprintf(f, "Blocksize: %u bytes\n", fs->blocksize);
229
230	retval = ext2fs_read_block_bitmap(fs);
231	if (retval) {
232		com_err(fs->device_name, retval, "while reading block bitmap");
233		close_device(fs->device_name, fs);
234		exit(1);
235	}
236
237	init_chunk_info(fs, chunk_info);
238
239	retval = get_chunk_info(fs, chunk_info, f);
240	if (retval) {
241		com_err(fs->device_name, retval, "while collecting chunk info");
242                close_device(fs->device_name, fs);
243		exit(1);
244	}
245}
246
247#ifndef DEBUGFS
248static void open_device(char *device_name, ext2_filsys *fs)
249{
250	int retval;
251	int flag = EXT2_FLAG_FORCE | EXT2_FLAG_64BITS;
252
253	retval = ext2fs_open(device_name, flag, 0, 0, unix_io_manager, fs);
254	if (retval) {
255		com_err(device_name, retval, "while opening filesystem");
256		exit(1);
257	}
258	(*fs)->default_bitmap_type = EXT2FS_BMAP64_RBTREE;
259}
260#endif
261
262#ifdef DEBUGFS
263#include "debugfs.h"
264
265void do_freefrag(int argc, char **argv)
266#else
267int main(int argc, char *argv[])
268#endif
269{
270	struct chunk_info chunk_info;
271	ext2_filsys fs = NULL;
272	char *progname;
273	char *end;
274	int c;
275
276#ifdef DEBUGFS
277	if (check_fs_open(argv[0]))
278		return;
279#else
280	char *device_name;
281
282	add_error_table(&et_ext2_error_table);
283#endif
284	progname = argv[0];
285	memset(&chunk_info, 0, sizeof(chunk_info));
286
287	while ((c = getopt(argc, argv, "c:h")) != EOF) {
288		switch (c) {
289		case 'c':
290			chunk_info.chunkbytes = strtoull(optarg, &end, 0);
291			if (*end != '\0') {
292				fprintf(stderr, "%s: bad chunk size '%s'\n",
293					progname, optarg);
294				usage(progname);
295			}
296			if (chunk_info.chunkbytes &
297			    (chunk_info.chunkbytes - 1)) {
298				fprintf(stderr, "%s: chunk size must be a "
299					"power of 2.\n", argv[0]);
300				usage(progname);
301			}
302			chunk_info.chunkbytes *= 1024;
303			break;
304		case 'h':
305		default:
306			usage(progname);
307			break;
308		}
309	}
310
311#ifndef DEBUGFS
312	if (optind == argc) {
313		fprintf(stderr, "%s: missing device name.\n", progname);
314		usage(progname);
315	}
316
317	device_name = argv[optind];
318
319	open_device(device_name, &fs);
320#else
321	fs = current_fs;
322#endif
323
324	if (chunk_info.chunkbytes && (chunk_info.chunkbytes < fs->blocksize)) {
325		fprintf(stderr, "%s: chunksize must be greater than or equal "
326			"to filesystem blocksize.\n", progname);
327		exit(1);
328	}
329	collect_info(fs, &chunk_info, stdout);
330#ifndef DEBUGFS
331	close_device(device_name, fs);
332
333	return 0;
334#endif
335}
336