ext4_free_clusters.c

/*
 * Kirill Tkhai <ktkhai@virtuozzo.com>
 *
 * License: GPL v2.
 */

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define CLUSTER_SIZE	(1024*1024)

#define pr_err(fmt, ...) fprintf(stderr, "Error: " fmt ": %s:%d\n", ##__VA_ARGS__, __FILE__, __LINE__)

unsigned long block_size = 0;
unsigned long blocks_per_group = 0;

#define BITS_PER_LONG		64
#define BIT_MASK(nr)            (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
#define __round_mask(x, y) ((__typeof__(x))((y)-1))
#define round_down(x, y) ((x) & ~__round_mask(x, y))

#define min(a,b)		(a < b ? a : b)

static unsigned long __ffs(unsigned long word)
{
        int num = 0;

#if BITS_PER_LONG == 64
        if ((word & 0xffffffff) == 0) {
                num += 32;
                word >>= 32;
        }
#endif
        if ((word & 0xffff) == 0) {
                num += 16;
                word >>= 16;
        }
        if ((word & 0xff) == 0) {
                num += 8;
                word >>= 8;
        }
        if ((word & 0xf) == 0) {
                num += 4;
                word >>= 4;
        }
        if ((word & 0x3) == 0) {
                num += 2;
                word >>= 2;
        }
        if ((word & 0x1) == 0)
                num += 1;
        return num;
}

static inline void set_bit(int nr, volatile unsigned long *addr)
{
        unsigned long mask = BIT_MASK(nr);
        unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
        unsigned long flags;

        *p  |= mask;
}

static inline unsigned long _find_next_bit(const unsigned long *addr1,
                const unsigned long *addr2, unsigned long nbits,
                unsigned long start, unsigned long invert)
{
        unsigned long tmp;

        if (start >= nbits)
                return nbits;

        tmp = addr1[start / BITS_PER_LONG];
        if (addr2)
                tmp &= addr2[start / BITS_PER_LONG];
        tmp ^= invert;

        /* Handle 1st word. */
        tmp &= BITMAP_FIRST_WORD_MASK(start);
        start = round_down(start, BITS_PER_LONG);

        while (!tmp) {
                start += BITS_PER_LONG;
                if (start >= nbits)
                        return nbits;

                tmp = addr1[start / BITS_PER_LONG];
                if (addr2)
                        tmp &= addr2[start / BITS_PER_LONG];
                tmp ^= invert;
        }

        return min(start + __ffs(tmp), nbits);
}

unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                            unsigned long offset)
{
        return _find_next_bit(addr, NULL, size, offset, 0UL);
}

#define for_each_set_bit_from(bit, addr, size) \
        for ((bit) = find_next_bit((addr), (size), (bit));      \
             (bit) < (size);                                    \
             (bit) = find_next_bit((addr), (size), (bit) + 1))

static void usage(const char *prog_name)
{
	printf("Reading dumpe2fs output from stdin...\n");
}

static int count_free_clusters(const char *line, unsigned long *count, void *group_blocks, unsigned int group)
{
	unsigned long start, end;
	int i, ret = 0;
	int n = 0;

	*count = 0;

	assert(group_blocks);
	memset(group_blocks, 0, (blocks_per_group + 7) / 8);

	while (1) {
		if (line[0] == '\0' || line[0] == '\n')
			break;
		if (line[0] == ' ' || line[0] == ',') {
			line +=1;
			continue;
		}
		ret = sscanf(line, "%lu %n", &start, &n);
		if (ret != 1) {
			pr_err("sscanf");
			ret = -1;
			goto out;
		}
		line += n;

		if (line[0] != '-') {
			/* Single free block */
			set_bit(start - group * blocks_per_group, group_blocks);
			continue;
		}
		line += 1;

		ret = sscanf(line, "%lu %n", &end, &n);
		if (ret != 1) {
			pr_err("sscanf");
			ret = -1;
			goto out;
		}
		line += n;

		/* Range of free blocks */
		for (i = start - group * blocks_per_group; i <= end - group * blocks_per_group; i++)
			set_bit(i, group_blocks);

		start *= block_size;
		start = (start + CLUSTER_SIZE - 1) / CLUSTER_SIZE;

		end += 1;
		end = end * block_size / CLUSTER_SIZE;

		if (end > start)
			*count += (end - start);
	}

	ret = 0;
out:
	return ret;
}

void show_spare_clusters(void *group_blocks, int group)
{
	unsigned long clu, clu_abs;

	/* Iteration by clusters */
	for (clu = 0; clu < blocks_per_group * block_size / CLUSTER_SIZE; clu++) {
		unsigned long i, start, blk, free = 0;

		start = clu * CLUSTER_SIZE / block_size;
		i = start;
		for_each_set_bit_from(i, group_blocks, start + CLUSTER_SIZE / block_size) {
			free++;
		}

		clu_abs = group * blocks_per_group * block_size / CLUSTER_SIZE + clu;
		blk = clu_abs * CLUSTER_SIZE / block_size;
		printf("clu: %lu free: %lu [%lu-%lu]\n", clu_abs, free, blk, blk + CLUSTER_SIZE/block_size - 1);
	}
}

int main(int argc, const char *argv[])
{
	unsigned long count, free_cluster_count = 0;
	unsigned long block_count = 0;
	unsigned group = 0;
	void *group_blocks = NULL;
	char *line = NULL;
	size_t n = 0;
	int ret;

	usage(argv[0]);

	while (getline(&line, &n, stdin) != -1) {
		if (!block_count && strncmp(line, "Block count:", 12) == 0) {
			ret = sscanf(line + 12, "%lu", &block_count);
			if (ret != 1) {
				pr_err("sscanf");
				ret = -1;
				goto out;
			}
			printf("blocks_count=%lu\n", block_count);
			continue;
		}

		if (!block_size && strncmp(line, "Block size:", 11) == 0) {
			ret = sscanf(line + 11, "%lu", &block_size);
			if (ret != 1) {
				pr_err("sscanf");
				ret = -1;
				goto out;
			}
			printf("block_size=%lu\n", block_size);
			if (block_size > CLUSTER_SIZE) {
				pr_err("block_size not supported");
			}
			continue;
		}

		if (!blocks_per_group && strncmp(line, "Blocks per group:", 17) == 0) {
			ret = sscanf(line + 17, "%lu", &blocks_per_group);
			if (ret != 1) {
				pr_err("sscanf");
				ret = -1;
				goto out;
			}
			group_blocks = malloc((blocks_per_group + 7) / 8);
			if (!group_blocks) {
				pr_err("malloc");
				ret = -1;
				goto out;
			}
			printf("blocks_per_group=%lu\n", blocks_per_group);
			continue;
		}

		if (strncmp(line, "  Free blocks: ", 15) == 0) {
			printf("%s", line);
			if (count_free_clusters(line + 15, &count, group_blocks, group) < 0) {
				ret = -1;
				goto out;
			}

			show_spare_clusters(group_blocks, group);
			free_cluster_count += count;
			group++;
		}
	
	}

	printf("free_cluster_count=%lu\n", free_cluster_count);
	printf("occupied_cluster_count=%lu\n",
		(block_count * block_size + CLUSTER_SIZE - 1)/CLUSTER_SIZE - free_cluster_count);
	ret = 0;
out:
	free(line);
	return ret;
}