#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)
{
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);
}
/**
projects / lwext4.git / blobdiff