X-Git-Url: https://git.carlh.net/gitweb/?a=blobdiff_plain;f=lwext4%2Fext4_bcache.c;h=ab19c177c619a66dc45c48e4da572a8d5eb866ac;hb=9195095bf35d65118fe69fd26906840bd5fcfc9f;hp=165cd8ad8ce81e91166e2edac804b23a058f02f1;hpb=23644a4048b147390df8bef84b1e9cf4dbea2b8e;p=lwext4.git

diff --git a/lwext4/ext4_bcache.c b/lwext4/ext4_bcache.c
index 165cd8a..ab19c17 100644
--- a/lwext4/ext4_bcache.c
+++ b/lwext4/ext4_bcache.c
@@ -36,12 +36,36 @@
 
 #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)
 {
@@ -49,167 +73,187 @@ int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
 
 	memset(bc, 0, sizeof(struct ext4_bcache));
 
-	bc->data = malloc(cnt * itemsize);
-	if (!bc->data)
-		goto error;
-
 	bc->cnt = cnt;
 	bc->itemsize = itemsize;
 	bc->ref_blocks = 0;
 	bc->max_ref_blocks = 0;
 
 	return EOK;
-
-error:
-
-	if (bc->data)
-		free(bc->data);
-
-	memset(bc, 0, sizeof(struct ext4_bcache));
-
-	return ENOMEM;
 }
 
 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
 {
-	if (bc->data)
-		free(bc->data);
-
 	memset(bc, 0, sizeof(struct ext4_bcache));
-
 	return EOK;
 }
 
-int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
-		      bool *is_new)
-{
-	uint32_t i;
-	ext4_assert(bc && b && is_new);
+/**@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.
+ */
 
-	/*Check if valid.*/
-	ext4_assert(b->lb_id);
-	if (!b->lb_id) {
-		ext4_assert(b->lb_id);
+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;
 	}
 
-	uint32_t cache_id = bc->cnt;
-	uint32_t alloc_id = 0;
-
-	*is_new = false;
-
-	/*Find in free blocks (Last Recently Used).*/
-	for (i = 0; i < bc->cnt; ++i) {
+	buf->lba = lba;
+	buf->data = data;
+	return buf;
+}
 
-		/*Check if block is already in cache*/
-		if (b->lb_id == bc->lba[i]) {
+static void ext4_buf_free(struct ext4_buf *buf)
+{
+	free(buf->data);
+	free(buf);
+}
 
-			if (!bc->refctr[i] && !bc->free_delay[i])
-				bc->ref_blocks++;
+static struct ext4_buf *
+ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
+{
+	struct ext4_buf tmp = {
+		.lba = lba
+	};
 
-			/*Update reference counter*/
-			bc->refctr[i]++;
+	return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
+}
 
-			/*Update usage marker*/
-			bc->lru_id[i] = ++bc->lru_ctr;
+struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
+{
+	return RB_MIN(ext4_buf_lru, &bc->lru_root);
+}
 
-			/*Set valid cache data and id*/
-			b->data = bc->data + i * bc->itemsize;
-			b->cache_id = i;
-			b->uptodate = ext4_bcache_test_flag(bc, i, BC_UPTODATE);
+void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
+{
+	/*Cannot drop any referenced buffers.*/
+	ext4_assert(!buf->refctr);
 
-			return EOK;
-		}
+	RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
+	RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
 
-		/*Best fit calculations.*/
-		if (bc->refctr[i])
-			continue;
+	/*Forcibly drop dirty buffer.*/
+	if (ext4_bcache_test_flag(buf, BC_DIRTY))
+		ext4_bcache_remove_dirty_node(bc, buf);
 
-		if (bc->free_delay[i])
-			continue;
+	ext4_buf_free(buf);
+	bc->ref_blocks--;
+}
 
-		/*Block is unreferenced, but it may exist block with
-		 * lower usage marker*/
+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_buf_lookup(bc, b->lb_id);
+	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);
 
-		/*First find.*/
-		if (cache_id == bc->cnt) {
-			cache_id = i;
-			alloc_id = bc->lru_id[i];
-			continue;
 		}
 
-		/*Next find*/
-		if (alloc_id <= bc->lru_id[i])
-			continue;
+		ext4_bcache_inc_ref(buf);
 
-		/*This block has lower alloc id marker*/
-		cache_id = i;
-		alloc_id = bc->lru_id[i];
-	}
+		b->buf = buf;
+		b->data = buf->data;
 
-	if (cache_id != bc->cnt) {
-		/*There was unreferenced block*/
-		bc->lba[cache_id] = b->lb_id;
-		bc->refctr[cache_id] = 1;
-		bc->lru_id[cache_id] = ++bc->lru_ctr;
+		*is_new = false;
+		return EOK;
+	}
 
-		/*Set valid cache data and id*/
-		b->data = bc->data + cache_id * bc->itemsize;
-		b->cache_id = cache_id;
-		ext4_bcache_clear_flag(bc, cache_id, BC_UPTODATE);
-		b->uptodate = false;
+	/* We need to allocate one buffer.*/
+	buf = ext4_buf_alloc(bc, b->lb_id);
+	if (!buf)
+		return ENOMEM;
 
-		/*Statistics*/
-		bc->ref_blocks++;
-		if (bc->ref_blocks > bc->max_ref_blocks)
-			bc->max_ref_blocks = bc->ref_blocks;
+	RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
+	/* One more buffer in bcache now. :-) */
+	bc->ref_blocks++;
 
-		/*Block needs to be read.*/
-		*is_new = true;
+	ext4_bcache_inc_ref(buf);
+	/* Assign new value to LRU id and increment LRU counter
+	 * by 1*/
+	buf->lru_id = ++bc->lru_ctr;
 
-		return EOK;
-	}
+	b->buf = buf;
+	b->data = buf->data;
 
-	ext4_dbg(DEBUG_BCACHE, DBG_ERROR
-		     "unable to alloc block cache!\n");
-	return ENOMEM;
+	*is_new = true;
+	return EOK;
 }
 
-int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b,
-		     uint8_t free_delay)
+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 be in cache.*/
-	ext4_assert(b->cache_id < bc->cnt);
+	/*Block should have a valid pointer to ext4_buf.*/
+	ext4_assert(buf);
 
 	/*Check if someone don't try free unreferenced block cache.*/
-	ext4_assert(bc->refctr[b->cache_id]);
+	ext4_assert(buf->refctr);
 
 	/*Just decrease reference counter*/
-	if (bc->refctr[b->cache_id])
-		bc->refctr[b->cache_id]--;
+	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)) {
+			if (bc->bdev->cache_write_back)
+				ext4_bcache_insert_dirty_node(bc, buf);
+			else
+				ext4_block_flush_buf(bc->bdev, buf);
+		}
 
-	if (free_delay)
-		bc->free_delay[b->cache_id] = free_delay;
+		/* The buffer is invalidated...drop it. */
+		if (!ext4_bcache_test_flag(buf, BC_UPTODATE))
+			ext4_bcache_drop_buf(bc, buf);
 
-	/*Update statistics*/
-	if (!bc->refctr[b->cache_id] && !bc->free_delay[b->cache_id])
-		bc->ref_blocks--;
+	}
 
 	b->lb_id = 0;
 	b->data = 0;
-	b->cache_id = 0;
-	b->uptodate = false;
 
 	return EOK;
 }
 
 bool ext4_bcache_is_full(struct ext4_bcache *bc)
 {
-	return (bc->cnt == bc->ref_blocks);
+	return (bc->cnt <= bc->ref_blocks);
 }
 
 /**