#include <stdint.h>
#include <stdbool.h>
+#include "tree.h"
+#include "queue.h"
#define EXT4_BLOCK_ZERO() \
- {.uptodate = 0, .dirty = 0, .lb_id = 0, .cache_id = 0, .data = 0}
+ {.lb_id = 0, .data = 0}
/**@brief Single block descriptor*/
struct ext4_block {
- /**@brief Uptodate flag*/
- bool uptodate;
-
- /**@brief Dirty flag*/
- bool dirty;
-
/**@brief Logical block ID*/
uint64_t lb_id;
- /**@brief Cache id*/
- uint32_t cache_id;
+ /**@brief Buffer */
+ struct ext4_buf *buf;
+
+ /**@brief Data buffer.*/
+ uint8_t *data;
+};
+
+struct ext4_bcache;
+
+/**@brief Single block descriptor*/
+struct ext4_buf {
+ /**@brief Flags*/
+ int flags;
+
+ /**@brief Logical block address*/
+ uint64_t lba;
/**@brief Data buffer.*/
uint8_t *data;
+
+ /**@brief LRU priority. (unused) */
+ uint32_t lru_prio;
+
+ /**@brief LRU id.*/
+ uint32_t lru_id;
+
+ /**@brief Reference count table*/
+ uint32_t refctr;
+
+ /**@brief Whether or not buffer is on dirty list.*/
+ bool on_dirty_list;
+
+ /**@brief LBA tree node*/
+ RB_ENTRY(ext4_buf) lba_node;
+
+ /**@brief LRU tree node*/
+ RB_ENTRY(ext4_buf) lru_node;
+
+ /**@brief Dirty list node*/
+ SLIST_ENTRY(ext4_buf) dirty_node;
+
+ /**@brief Callback routine after a disk-write operation.
+ * @param bc block cache descriptor
+ * @param buf buffer descriptor
+ * @param standard error code returned by bdev->bwrite()
+ * @param arg argument passed to this routine*/
+ void (*end_write)(struct ext4_bcache *bc,
+ struct ext4_buf *buf,
+ int res,
+ void *arg);
+
+ /**@brief argument passed to end_write() callback.*/
+ void *end_write_arg;
};
/**@brief Block cache descriptor*/
/**@brief Last recently used counter*/
uint32_t lru_ctr;
- /**@brief Reference count table*/
- uint32_t refctr[CONFIG_BLOCK_DEV_CACHE_SIZE];
-
- /**@brief Last recently used ID table*/
- uint32_t lru_id[CONFIG_BLOCK_DEV_CACHE_SIZE];
-
- /**@brief Writeback free delay mode table*/
- uint8_t free_delay[CONFIG_BLOCK_DEV_CACHE_SIZE];
-
- /**@brief Logical block table*/
- uint64_t lba[CONFIG_BLOCK_DEV_CACHE_SIZE];
-
- /**@brief Flags*/
- int flags[CONFIG_BLOCK_DEV_CACHE_SIZE];
-
- /**@brief Cache data buffers*/
- uint8_t *data;
-
/**@brief Currently referenced datablocks*/
uint32_t ref_blocks;
/**@brief Maximum referenced datablocks*/
uint32_t max_ref_blocks;
+
+ /**@brief The blockdev binded to this block cache*/
+ struct ext4_blockdev *bdev;
+
+ /**@brief A tree holding all bufs*/
+ RB_HEAD(ext4_buf_lba, ext4_buf) lba_root;
+
+ /**@brief A tree holding unreferenced bufs*/
+ RB_HEAD(ext4_buf_lru, ext4_buf) lru_root;
+
+ /**@brief A singly-linked list holding dirty buffers*/
+ SLIST_HEAD(ext4_buf_dirty, ext4_buf) dirty_list;
};
+/**@brief buffer state bits
+ *
+ * - BC♡UPTODATE: Buffer contains valid data.
+ * - BC_DIRTY: Buffer is dirty.
+ * - BC_FLUSH: Buffer will be immediately flushed,
+ * when no one references it.
+ */
enum bcache_state_bits {
BC_UPTODATE,
- BC_DIRTY
+ BC_DIRTY,
+ BC_FLUSH
};
-#define ext4_bcache_set_flag(bc, id, b) \
- (bc)->flags[id] |= 1 << (b)
+#define ext4_bcache_set_flag(buf, b) \
+ (buf)->flags |= 1 << (b)
+
+#define ext4_bcache_clear_flag(buf, b) \
+ (buf)->flags &= ~(1 << (b))
+
+#define ext4_bcache_test_flag(buf, b) \
+ (((buf)->flags & (1 << (b))) >> (b))
+
+static inline void ext4_bcache_set_dirty(struct ext4_buf *buf) {
+ ext4_bcache_set_flag(buf, BC_UPTODATE);
+ ext4_bcache_set_flag(buf, BC_DIRTY);
+}
+
+static inline void ext4_bcache_clear_dirty(struct ext4_buf *buf) {
+ ext4_bcache_clear_flag(buf, BC_UPTODATE);
+ ext4_bcache_clear_flag(buf, BC_DIRTY);
+}
-#define ext4_bcache_clear_flag(bc, id, b) \
- (bc)->flags[id] &= ~(1 << (b))
+/**@brief Increment reference counter of buf by 1.*/
+#define ext4_bcache_inc_ref(buf) ((buf)->refctr++)
-#define ext4_bcache_test_flag(bc, id, b) \
- (((bc)->flags[id] & (1 << (b))) >> (b))
+/**@brief Decrement reference counter of buf by 1.*/
+#define ext4_bcache_dec_ref(buf) ((buf)->refctr--)
/**@brief Static initializer of block cache structure.*/
#define EXT4_BCACHE_STATIC_INSTANCE(__name, __cnt, __itemsize) \
- static uint8_t __name##_data[(__cnt) * (__itemsize)]; \
static struct ext4_bcache __name = { \
.cnt = __cnt, \
.itemsize = __itemsize, \
.lru_ctr = 0, \
- .data = __name##_data, \
}
+/**@brief Insert buffer to dirty cache list
+ * @param bc block cache descriptor
+ * @param buf buffer descriptor */
+static inline void
+ext4_bcache_insert_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
+ if (!buf->on_dirty_list) {
+ SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
+ buf->on_dirty_list = true;
+ }
+}
+
+/**@brief Remove buffer to dirty cache list
+ * @param bc block cache descriptor
+ * @param buf buffer descriptor */
+static inline void
+ext4_bcache_remove_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
+ if (buf->on_dirty_list) {
+ SLIST_REMOVE(&bc->dirty_list, buf, ext4_buf, dirty_node);
+ buf->on_dirty_list = false;
+ }
+}
+
+
/**@brief Dynamic initialization of block cache.
* @param bc block cache descriptor
* @param cnt items count in block cache
* @return standard error code*/
int ext4_bcache_fini_dynamic(struct ext4_bcache *bc);
+/**@brief Get a buffer with the lowest LRU counter in bcache.
+ * @param bc block cache descriptor
+ * @return buffer with the lowest LRU counter*/
+struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc);
+
+/**@brief Drop unreferenced buffer from bcache.
+ * @param bc block cache descriptor
+ * @param buf buffer*/
+void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf);
+
/**@brief Allocate block from block cache memory.
* Unreferenced block allocation is based on LRU
* (Last Recently Used) algorithm.
/**@brief Free block from cache memory (decrement reference counter).
* @param bc block cache descriptor
* @param b block to free
- * @param cache writeback mode
* @return standard error code*/
-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);
/**@brief Return a full status of block cache.
* @param bc block cache descriptor