-/*\r
- * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
- * All rights reserved.\r
- *\r
- * Redistribution and use in source and binary forms, with or without\r
- * modification, are permitted provided that the following conditions\r
- * are met:\r
- *\r
- * - Redistributions of source code must retain the above copyright\r
- * notice, this list of conditions and the following disclaimer.\r
- * - Redistributions in binary form must reproduce the above copyright\r
- * notice, this list of conditions and the following disclaimer in the\r
- * documentation and/or other materials provided with the distribution.\r
- * - The name of the author may not be used to endorse or promote products\r
- * derived from this software without specific prior written permission.\r
- *\r
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
- */\r
-\r
-/** @addtogroup lwext4\r
- * @{\r
- */\r
-/**\r
- * @file ext4_bcache.h\r
- * @brief Block cache allocator.\r
- */\r
-\r
-#ifndef EXT4_BCACHE_H_\r
-#define EXT4_BCACHE_H_\r
-\r
-#include <ext4_config.h>\r
-\r
-#include <stdint.h>\r
-#include <stdbool.h>\r
-\r
-/**@brief Single block descriptor.*/\r
-struct ext4_block {\r
- /**@brief Dirty flag.*/\r
- bool dirty;\r
-\r
- /**@brief Logical block ID*/\r
- uint64_t lb_id;\r
-\r
- /**@brief Cache id*/\r
- uint32_t cache_id;\r
-\r
- /**@brief Data buffer.*/\r
- uint8_t *data;\r
-};\r
-\r
-\r
-/**@brief Block cache descriptor.*/\r
-struct ext4_bcache {\r
-\r
- /**@brief Item count in block cache*/\r
- uint32_t cnt;\r
-\r
- /**@brief Item size in block cache*/\r
- uint32_t itemsize;\r
-\r
- /**@brief Last recently used counter.*/\r
- uint32_t lru_ctr;\r
-\r
- /**@brief Reference count table (cnt).*/\r
- uint32_t *refctr;\r
-\r
- /**@brief Last recently used ID table (cnt)*/\r
- uint32_t *lru_id;\r
-\r
- /**@brief Writeback free delay mode table (cnt)*/\r
- uint8_t *free_delay;\r
-\r
- /**@brief Logical block table (cnt).*/\r
- uint64_t *lba;\r
-\r
- /**@brief Dirty mark (cnt).*/\r
- bool *dirty;\r
-\r
- /**@brief Cache data buffers (cnt * itemsize)*/\r
- uint8_t *data;\r
-\r
- /**@brief Currently referenced datablocks*/\r
- uint32_t ref_blocks;\r
-\r
- /**@brief Maximum referenced datablocks*/\r
- uint32_t max_ref_blocks;\r
-\r
-};\r
-\r
-/**@brief Static initializer of block cache structure.*/\r
-#define EXT4_BCACHE_STATIC_INSTANCE(__name, __cnt, __itemsize) \\r
- static uint32_t __name##_refctr[(__cnt)]; \\r
- static uint32_t __name##_lru_id[(__cnt)]; \\r
- static uint8_t __name##_free_delay[(__cnt)]; \\r
- static uint64_t __name##_lba[(__cnt)]; \\r
- static bool __name##_dirty[(__cnt)]; \\r
- static uint8_t __name##_data[(__cnt) * (__itemsize)]; \\r
- static struct ext4_bcache __name = { \\r
- .cnt = __cnt, \\r
- .itemsize = __itemsize, \\r
- .lru_ctr = 0, \\r
- .refctr = __name##_refctr, \\r
- .lru_id = __name##_lru_id, \\r
- .lba = __name##_lba, \\r
- .dirty = __name##_dirty, \\r
- .free_delay= __name##_free_delay, \\r
- .data = __name##_data, \\r
- }\r
-\r
-\r
-/**@brief Dynamic initialization of block cache.\r
- * @param bc block cache descriptor\r
- * @param cnt items count in block cache\r
- * @param itemsize single item size (in bytes)\r
- * @return standard error code*/\r
-int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,\r
- uint32_t itemsize);\r
-\r
-/**@brief Dynamic de-initialization of block cache.\r
- * @param bc block cache descriptor\r
- * @return standard error code*/\r
-int ext4_bcache_fini_dynamic(struct ext4_bcache *bc);\r
-\r
-/**@brief Allocate block from block cache memory.\r
- * Unreferenced block allocation is based on LRU\r
- * (Last Recently Used) algorithm.\r
- * @param bc block cache descriptor\r
- * @param b block to alloc\r
- * @param is_new block is new (needs to be read)\r
- * @return standard error code*/\r
-int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,\r
- bool *is_new);\r
-\r
-/**@brief Free block from cache memory (decrement reference counter).\r
- * @param bc block cache descriptor\r
- * @param b block to free\r
- * @param cache writeback mode\r
- * @return standard error code*/\r
-int ext4_bcache_free (struct ext4_bcache *bc, struct ext4_block *b,\r
- uint8_t free_delay);\r
-\r
-\r
-/**@brief Return a full status of block cache.\r
- * @param bc block cache descriptor\r
- * @return full status*/\r
-bool ext4_bcache_is_full(struct ext4_bcache *bc);\r
-\r
-#endif /* EXT4_BCACHE_H_ */\r
-\r
-/**\r
- * @}\r
- */\r
+/*
+ * 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.h
+ * @brief Block cache allocator.
+ */
+
+#ifndef EXT4_BCACHE_H_
+#define EXT4_BCACHE_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "ext4_config.h"
+
+#include <stdint.h>
+#include <stdbool.h>
+#include "tree.h"
+#include "queue.h"
+
+#define EXT4_BLOCK_ZERO() \
+ {.lb_id = 0, .data = 0}
+
+/**@brief Single block descriptor*/
+struct ext4_block {
+ /**@brief Logical block ID*/
+ uint64_t lb_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*/
+struct ext4_bcache {
+
+ /**@brief Item count in block cache*/
+ uint32_t cnt;
+
+ /**@brief Item size in block cache*/
+ uint32_t itemsize;
+
+ /**@brief Last recently used counter*/
+ uint32_t lru_ctr;
+
+ /**@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_FLUSH
+};
+
+#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);
+}
+
+/**@brief Increment reference counter of buf by 1.*/
+#define ext4_bcache_inc_ref(buf) ((buf)->refctr++)
+
+/**@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 struct ext4_bcache __name = { \
+ .cnt = __cnt, \
+ .itemsize = __itemsize, \
+ .lru_ctr = 0, \
+ }
+
+/**@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
+ * @param itemsize single item size (in bytes)
+ * @return standard error code*/
+int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
+ uint32_t itemsize);
+
+/**@brief Dynamic de-initialization of block cache.
+ * @param bc block cache descriptor
+ * @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.
+ * @param bc block cache descriptor
+ * @param b block to alloc
+ * @param is_new block is new (needs to be read)
+ * @return standard error code*/
+int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
+ bool *is_new);
+
+/**@brief Free block from cache memory (decrement reference counter).
+ * @param bc block cache descriptor
+ * @param b block to free
+ * @return standard error code*/
+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
+ * @return full status*/
+bool ext4_bcache_is_full(struct ext4_bcache *bc);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* EXT4_BCACHE_H_ */
+
+/**
+ * @}
+ */