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

diff --git a/lwext4/ext4_bcache.c b/lwext4/ext4_bcache.c
index bab156b..ab19c17 100644
--- a/lwext4/ext4_bcache.c
+++ b/lwext4/ext4_bcache.c
@@ -1,266 +1,261 @@
-/*
- * 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_debug.h>
-#include <ext4_errno.h>
-
-#include <string.h>
-#include <stdlib.h>
-
-
-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->refctr = malloc(cnt * sizeof(uint32_t));
-    if(!bc->refctr)
-        goto error;
-
-    bc->lru_id = malloc(cnt * sizeof(uint32_t));
-    if(!bc->lru_id)
-        goto error;
-
-    bc->free_delay = malloc(cnt * sizeof(uint8_t));
-    if(!bc->free_delay)
-        goto error;
-
-    bc->lba = malloc(cnt * sizeof(uint64_t));
-    if(!bc->lba)
-        goto error;
-
-    bc->data = malloc(cnt * itemsize);
-    if(!bc->data)
-        goto error;
-
-    memset(bc->refctr, 0, cnt * sizeof(uint32_t));
-    memset(bc->lru_id, 0, cnt * sizeof(uint32_t));
-    memset(bc->free_delay, 0, cnt * sizeof(uint8_t));
-    memset(bc->lba, 0, cnt * sizeof(uint64_t));
-
-    bc->cnt = cnt;
-    bc->itemsize = itemsize;
-    bc->ref_blocks = 0;
-    bc->max_ref_blocks = 0;
-
-    return EOK;
-
-    error:
-
-    if(bc->refctr)
-        free(bc->refctr);
-
-    if(bc->lru_id)
-        free(bc->lru_id);
-
-    if(bc->free_delay)
-        free(bc->free_delay);
-
-    if(bc->lba)
-        free(bc->lba);
-
-    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->refctr)
-        free(bc->refctr);
-
-    if(bc->lru_id)
-        free(bc->lru_id);
-
-    if(bc->free_delay)
-        free(bc->free_delay);
-
-    if(bc->lba)
-        free(bc->lba);
-
-    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);
-
-    /*Check if valid.*/
-    ext4_assert(b->lb_id);
-    if(!b->lb_id){
-        ext4_assert(b->lb_id);
-    }
-
-    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) {
-
-        /*Check if block is already in cache*/
-        if(b->lb_id == bc->lba[i]){
-
-            if(!bc->refctr[i] && !bc->free_delay[i])
-                bc->ref_blocks++;
-
-            /*Update reference counter*/
-            bc->refctr[i]++;
-
-            /*Update usage marker*/
-            bc->lru_id[i] = ++bc->lru_ctr;
-
-            /*Set valid cache data and id*/
-            b->data = bc->data + i * bc->itemsize;
-            b->cache_id = i;
-
-            return EOK;
-        }
-
-        /*Best fit calculations.*/
-        if(bc->refctr[i])
-            continue;
-
-        if(bc->free_delay[i])
-            continue;
-
-        /*Block is unreferenced, but it may exist block with
-         * lower usage marker*/
-
-        /*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;
-
-        /*This block has lower alloc id marker*/
-        cache_id = i;
-        alloc_id = bc->lru_id[i];
-    }
-
-
-    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;
-
-        /*Set valid cache data and id*/
-        b->data = bc->data + cache_id * bc->itemsize;
-        b->cache_id = cache_id;
-
-        /*Statistics*/
-        bc->ref_blocks++;
-        if(bc->ref_blocks > bc->max_ref_blocks)
-            bc->max_ref_blocks = bc->ref_blocks;
-
-
-        /*Block needs to be read.*/
-        *is_new = true;
-
-        return EOK;
-    }
-
-    ext4_dprintf(EXT4_DEBUG_BCACHE,
-        "ext4_bcache_alloc: FAIL, unable to alloc block cache!\n");
-    return ENOMEM;
-}
-
-int ext4_bcache_free (struct ext4_bcache *bc, struct ext4_block *b,
-    uint8_t free_delay)
-{
-    ext4_assert(bc && b);
-
-    /*Check if valid.*/
-    ext4_assert(b->lb_id);
-
-    /*Block should be in cache.*/
-    ext4_assert(b->cache_id < bc->cnt);
-
-    /*Check if someone don't try free unreferenced block cache.*/
-    ext4_assert(bc->refctr[b->cache_id]);
-
-    /*Just decrease reference counter*/
-    if(bc->refctr[b->cache_id])
-        bc->refctr[b->cache_id]--;
-
-    if(free_delay)
-        bc->free_delay[b->cache_id] = free_delay;
-
-    /*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;
-
-    return EOK;
-}
-
-
-
-bool ext4_bcache_is_full(struct ext4_bcache *bc)
-{
-    return (bc->cnt == bc->ref_blocks);
-}
-
-/**
- * @}
- */
-
-
+/*
+ * 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;
+}
+
+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;
+	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)
+{
+	/*Cannot drop any referenced buffers.*/
+	ext4_assert(!buf->refctr);
+
+	RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
+	RB_REMOVE(ext4_buf_lru, &bc->lru_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--;
+}
+
+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);
+
+		}
+
+		ext4_bcache_inc_ref(buf);
+
+		b->buf = buf;
+		b->data = buf->data;
+
+		*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++;
+
+	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)) {
+			if (bc->bdev->cache_write_back)
+				ext4_bcache_insert_dirty_node(bc, buf);
+			else
+				ext4_block_flush_buf(bc->bdev, buf);
+		}
+
+		/* The buffer is invalidated...drop it. */
+		if (!ext4_bcache_test_flag(buf, BC_UPTODATE))
+			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);
+}
+
+/**
+ * @}
+ */