Reconstruct source directory tree.

1 files changed, 317 insertions, 0 deletions

diff --git a/src/ext4_bcache.c b/src/ext4_bcache.c
new file mode 100644
index 0000000..1a1766a
--- /dev/null
+++ b/src/ext4_bcache.c
@@ -0,0 +1,317 @@
+/*
+ * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** @addtogroup lwext4
+ * @{
+ */
+/**
+ * @file  ext4_bcache.c
+ * @brief Block cache allocator.
+ */
+
+#include "ext4_config.h"
+#include "ext4_bcache.h"
+#include "ext4_blockdev.h"
+#include "ext4_debug.h"
+#include "ext4_errno.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+static int ext4_bcache_lba_compare(struct ext4_buf *a, struct ext4_buf *b)
+{
+	 if (a->lba > b->lba)
+		 return 1;
+	 else if (a->lba < b->lba)
+		 return -1;
+	 return 0;
+}
+
+static int ext4_bcache_lru_compare(struct ext4_buf *a, struct ext4_buf *b)
+{
+	if (a->lru_id > b->lru_id)
+		return 1;
+	else if (a->lru_id < b->lru_id)
+		return -1;
+	return 0;
+}
+
+RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
+		     ext4_bcache_lba_compare, static inline)
+RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
+		     ext4_bcache_lru_compare, static inline)
+
+int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
+			     uint32_t itemsize)
+{
+	ext4_assert(bc && cnt && itemsize);
+
+	memset(bc, 0, sizeof(struct ext4_bcache));
+
+	bc->cnt = cnt;
+	bc->itemsize = itemsize;
+	bc->ref_blocks = 0;
+	bc->max_ref_blocks = 0;
+
+	return EOK;
+}
+
+void ext4_bcache_cleanup(struct ext4_bcache *bc)
+{
+	struct ext4_buf *buf, *tmp;
+	RB_FOREACH_SAFE(buf, ext4_buf_lba, &bc->lba_root, tmp) {
+		ext4_block_flush_buf(bc->bdev, buf);
+		ext4_bcache_drop_buf(bc, buf);
+	}
+}
+
+int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
+{
+	memset(bc, 0, sizeof(struct ext4_bcache));
+	return EOK;
+}
+
+/**@brief:
+ *
+ *  This is ext4_bcache, the module handling basic buffer-cache stuff.
+ *
+ *  Buffers in a bcache are sorted by their LBA and stored in a
+ *  RB-Tree(lba_root).
+ *
+ *  Bcache also maintains another RB-Tree(lru_root) right now, where
+ *  buffers are sorted by their LRU id.
+ *
+ *  A singly-linked list is used to track those dirty buffers which are
+ *  ready to be flushed. (Those buffers which are dirty but also referenced
+ *  are not considered ready to be flushed.)
+ *
+ *  When a buffer is not referenced, it will be stored in both lba_root
+ *  and lru_root, while it will only be stored in lba_root when it is
+ *  referenced.
+ */
+
+static struct ext4_buf *
+ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
+{
+	void *data;
+	struct ext4_buf *buf;
+	data = malloc(bc->itemsize);
+	if (!data)
+		return NULL;
+
+	buf = calloc(1, sizeof(struct ext4_buf));
+	if (!buf) {
+		free(data);
+		return NULL;
+	}
+
+	buf->lba = lba;
+	buf->data = data;
+	buf->bc = bc;
+	return buf;
+}
+
+static void ext4_buf_free(struct ext4_buf *buf)
+{
+	free(buf->data);
+	free(buf);
+}
+
+static struct ext4_buf *
+ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
+{
+	struct ext4_buf tmp = {
+		.lba = lba
+	};
+
+	return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
+}
+
+struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
+{
+	return RB_MIN(ext4_buf_lru, &bc->lru_root);
+}
+
+void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
+{
+	/* Warn on dropping any referenced buffers.*/
+	if (buf->refctr) {
+		ext4_dbg(DEBUG_BCACHE, DBG_WARN "Buffer is still referenced. "
+				"lba: %" PRIu64 ", refctr: %" PRIu32 "\n",
+				buf->lba, buf->refctr);
+	} else
+		RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
+
+	RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
+
+	/*Forcibly drop dirty buffer.*/
+	if (ext4_bcache_test_flag(buf, BC_DIRTY))
+		ext4_bcache_remove_dirty_node(bc, buf);
+
+	ext4_buf_free(buf);
+	bc->ref_blocks--;
+}
+
+void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
+				uint64_t from,
+				uint32_t cnt)
+{
+	uint64_t end = from + cnt - 1;
+	struct ext4_buf *tmp = ext4_buf_lookup(bc, from), *buf;
+	RB_FOREACH_FROM(buf, ext4_buf_lba, tmp) {
+		if (buf->lba > end)
+			break;
+
+		/* Clear both dirty and up-to-date flags. */
+		if (ext4_bcache_test_flag(buf, BC_DIRTY))
+			ext4_bcache_remove_dirty_node(bc, buf);
+
+		buf->end_write = NULL;
+		buf->end_write_arg = NULL;
+		ext4_bcache_clear_dirty(buf);
+	}
+}
+
+struct ext4_buf *
+ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
+		     uint64_t lba)
+{
+	struct ext4_buf *buf = ext4_buf_lookup(bc, lba);
+	if (buf) {
+		/* If buffer is not referenced. */
+		if (!buf->refctr) {
+			/* Assign new value to LRU id and increment LRU counter
+			 * by 1*/
+			buf->lru_id = ++bc->lru_ctr;
+			RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
+			if (ext4_bcache_test_flag(buf, BC_DIRTY))
+				ext4_bcache_remove_dirty_node(bc, buf);
+
+		}
+
+		ext4_bcache_inc_ref(buf);
+
+		b->lb_id = lba;
+		b->buf = buf;
+		b->data = buf->data;
+	}
+	return buf;
+}
+
+int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
+		      bool *is_new)
+{
+	/* Try to search the buffer with exaxt LBA. */
+	struct ext4_buf *buf = ext4_bcache_find_get(bc, b, b->lb_id);
+	if (buf) {
+		*is_new = false;
+		return EOK;
+	}
+
+	/* We need to allocate one buffer.*/
+	buf = ext4_buf_alloc(bc, b->lb_id);
+	if (!buf)
+		return ENOMEM;
+
+	RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
+	/* One more buffer in bcache now. :-) */
+	bc->ref_blocks++;
+
+	/*Calc ref blocks max depth*/
+	if (bc->max_ref_blocks < bc->ref_blocks)
+		bc->max_ref_blocks = bc->ref_blocks;
+
+
+	ext4_bcache_inc_ref(buf);
+	/* Assign new value to LRU id and increment LRU counter
+	 * by 1*/
+	buf->lru_id = ++bc->lru_ctr;
+
+	b->buf = buf;
+	b->data = buf->data;
+
+	*is_new = true;
+	return EOK;
+}
+
+int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b)
+{
+	struct ext4_buf *buf = b->buf;
+
+	ext4_assert(bc && b);
+
+	/*Check if valid.*/
+	ext4_assert(b->lb_id);
+
+	/*Block should have a valid pointer to ext4_buf.*/
+	ext4_assert(buf);
+
+	/*Check if someone don't try free unreferenced block cache.*/
+	ext4_assert(buf->refctr);
+
+	/*Just decrease reference counter*/
+	ext4_bcache_dec_ref(buf);
+
+	/* We are the last one touching this buffer, do the cleanups. */
+	if (!buf->refctr) {
+		RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
+		/* This buffer is ready to be flushed. */
+		if (ext4_bcache_test_flag(buf, BC_DIRTY) &&
+		    ext4_bcache_test_flag(buf, BC_UPTODATE)) {
+			if (bc->bdev->cache_write_back &&
+			    !ext4_bcache_test_flag(buf, BC_FLUSH) &&
+			    !ext4_bcache_test_flag(buf, BC_TMP))
+				ext4_bcache_insert_dirty_node(bc, buf);
+			else {
+				ext4_block_flush_buf(bc->bdev, buf);
+				ext4_bcache_clear_flag(buf, BC_FLUSH);
+			}
+		}
+
+		/* The buffer is invalidated...drop it. */
+		if (!ext4_bcache_test_flag(buf, BC_UPTODATE) ||
+		    ext4_bcache_test_flag(buf, BC_TMP))
+			ext4_bcache_drop_buf(bc, buf);
+
+	}
+
+	b->lb_id = 0;
+	b->data = 0;
+
+	return EOK;
+}
+
+bool ext4_bcache_is_full(struct ext4_bcache *bc)
+{
+	return (bc->cnt <= bc->ref_blocks);
+}
+
+
+/**
+ * @}
+ */