path: root/fs/logfs/gc.c

/*
 * fs/logfs/gc.c	- garbage collection code
 *
 * As should be obvious for Linux kernel code, license is GPLv2
 *
 * Copyright (c) 2005-2008 Joern Engel <joern@logfs.org>
 */
#include "logfs.h"
#include <linux/sched.h>
#include <linux/slab.h>

/*
 * Wear leveling needs to kick in when the difference between low erase
 * counts and high erase counts gets too big.  A good value for "too big"
 * may be somewhat below 10% of maximum erase count for the device.
 * Why not 397, to pick a nice round number with no specific meaning? :)
 *
 * WL_RATELIMIT is the minimum time between two wear level events.  A huge
 * number of segments may fulfil the requirements for wear leveling at the
 * same time.  If that happens we don't want to cause a latency from hell,
 * but just gently pick one segment every so often and minimize overhead.
 */
#define WL_DELTA 397
#define WL_RATELIMIT 100
#define MAX_OBJ_ALIASES	2600
#define SCAN_RATIO 512	/* number of scanned segments per gc'd segment */
#define LIST_SIZE 64	/* base size of candidate lists */
#define SCAN_ROUNDS 128	/* maximum number of complete medium scans */
#define SCAN_ROUNDS_HIGH 4 /* maximum number of higher-level scans */

static int no_free_segments(struct super_block *sb)
{
	struct logfs_super *super = logfs_super(sb);

	return super->s_free_list.count;
}

/* journal has distance -1, top-most ifile layer distance 0 */
static u8 root_distance(struct super_block *sb, gc_level_t __gc_level)
{
	struct logfs_super *super = logfs_super(sb);
	u8 gc_level = (__force u8)__gc_level;

	switch (gc_level) {
	case 0: /* fall through */
	case 1: /* fall through */
	case 2: /* fall through */
	case 3:
		/* file data or indirect blocks */
		return super->s_ifile_levels + super->s_iblock_levels - gc_level;
	case 6: /* fall through */
	case 7: /* fall through */
	case 8: /* fall through */
	case 9:
		/* inode file data or indirect blocks */
		return super->s_ifile_levels - (gc_level - 6);
	default:
		printk(KERN_ERR"LOGFS: segment of unknown level %x found\n",
				gc_level);
		WARN_ON(1);
		return super->s_ifile_levels + super->s_iblock_levels;
	}
}

static int segment_is_reserved(struct super_block *sb, u32 segno)
{
	struct logfs_super *super = logfs_super(sb);
	struct logfs_area *area;
	void *reserved;
	int i;

	/* Some segments are reserved.  Just pretend they were all valid */
	reserved = btree_lookup32(&super->s_reserved_segments, segno);
	if (reserved)
		return 1;

	/* Currently open segments */
	for_each_area(i) {
		area = super->s_area[i];
		if (area->a_is_open && area->a_segno == segno)
			return 1;
	}

	return 0;
}

static void logfs_mark_segment_bad(struct super_block *sb, u32 segno)
{
	BUG();
}

/*
 * Returns the bytes consumed by valid objects in this segment.  Object headers
 * are counted, the segment header is not.
 */
static u32 logfs_valid_bytes(struct super_block *sb, u32 segno, u32 *ec,
		gc_level_t *gc_level)
{
	struct logfs_segment_entry se;
	u32 ec_level;

	logfs_get_segment_entry(sb, segno, &se);
	if (se.ec_level == cpu_to_be32(BADSEG) ||
			se.valid == cpu_to_be32(RESERVED))
		return RESERVED;

	ec_level = be32_to_cpu(se.ec_level);
	*ec = ec_level >> 4;
	*gc_level = GC_LEVEL(ec_level & 0xf);
	return be32_to_cpu(se.valid);
}

static void logfs_cleanse_block(struct super_block *sb, u64 ofs, u64 ino,
		u64 bix, gc_level_t gc_level)
{
	struct inode *inode;
	int err, cookie;

	inode = logfs_safe_iget(sb, ino, &cookie);
	err = logfs_rewrite_block(inode, bix, ofs, gc_level, 0);
	BUG_ON(err);
	logfs_safe_iput(inode, cookie);
}

static u32 logfs_gc_segment(struct super_block *sb, u32 segno)
{
	struct logfs_super *super = logfs_super(sb);
	struct logfs_segment_header sh;
	struct logfs_object_header oh;
	u64 ofs, ino, bix;
	u32 seg_ofs, logical_segno, cleaned = 0;
	int err, len, valid;
	gc_level_t gc_level;

	LOGFS_BUG_ON(segment_is_reserved(sb, segno), sb);

	btree_insert32(&super->s_reserved_segments, segno, (void *)1, GFP_NOFS);
	err = wbuf_read(sb, dev_ofs(sb, segno, 0), sizeof(sh), &sh);
	BUG_ON(err);
	gc_level = GC_LEVEL(sh.level);
	logical_segno = be32_to_cpu(sh.segno);
	if (sh.crc != logfs_crc32(&sh, sizeof(sh), 4)) {
		logfs_mark_segment_bad(sb, segno);
		cleaned = -1;
		goto out;
	}

	for (seg_ofs = LOGFS_SEGMENT_HEADERSIZE;
			seg_ofs + sizeof(oh) < super->s_segsize; ) {
		ofs = dev_ofs(sb, logical_segno, seg_ofs);
		err = wbuf_read(sb, dev_ofs(sb, segno, seg_ofs), sizeof(oh),
				&oh);
		BUG_ON(err);

		if (!memchr_inv(&oh, 0xff, sizeof(oh)))
			break;

		if (oh.crc != logfs_crc32(&oh, sizeof(oh) - 4, 4)) {
			logfs_mark_segment_bad(sb, segno);
			cleaned = super->s_segsize - 1;
			goto out;
		}

		ino = be64_to_cpu(oh.ino);
		bix = be64_to_cpu(oh.bix);
		len = sizeof(oh) + be16_to_cpu(oh.len);
		valid = logfs_is_valid_block(sb, ofs, ino, bix, gc_level);
		if (valid == 1) {
			logfs_cleanse_block(sb, ofs, ino, bix, gc_level);
			cleaned += len;
		} else if (valid == 2) {
			/* Will be invalid upon journal commit */
			cleaned += len;
		}
		seg_ofs += len;
	}
out:
	btree_remove32(&super