lwext4/ext4_bcache.h

   1 /*
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup lwext4
  30  * @{
  31  */
  32 /**
  33  * @file  ext4_bcache.h
  34  * @brief Block cache allocator.
  35  */
  36
  37 #ifndef EXT4_BCACHE_H_
  38 #define EXT4_BCACHE_H_
  39
  40 #ifdef __cplusplus
  41 extern "C" {
  42 #endif
  43
  44 #include "ext4_config.h"
  45
  46 #include <stdint.h>
  47 #include <stdbool.h>
  48 #include "tree.h"
  49 #include "queue.h"
  50
  51 #define EXT4_BLOCK_ZERO()       \
  52         {.uptodate = 0, .dirty = 0, .lb_id = 0, .data = 0}
  53
  54 /**@brief   Single block descriptor*/
  55 struct ext4_block {
  56         /**@brief   Uptodate flag*/
  57         bool uptodate;
  58
  59         /**@brief   Dirty flag*/
  60         bool dirty;
  61
  62         /**@brief   Logical block ID*/
  63         uint64_t lb_id;
  64
  65         /**@brief   Buffer */
  66         struct ext4_buf *buf;
  67
  68         /**@brief   Data buffer.*/
  69         uint8_t *data;
  70 };
  71
  72 /**@brief   Single block descriptor*/
  73 struct ext4_buf {
  74         /**@brief   Flags*/
  75         int flags;
  76
  77         /**@brief   Logical block address*/
  78         uint64_t lba;
  79
  80         /**@brief   Data buffer.*/
  81         uint8_t *data;
  82
  83         /**@brief   LRU priority. (unused) */
  84         uint32_t lru_prio;
  85
  86         /**@brief   LRU id.*/
  87         uint32_t lru_id;
  88
  89         /**@brief   Reference count table*/
  90         uint32_t refctr;
  91
  92         /**@brief   Whether or not buffer is on dirty list.*/
  93         bool on_dirty_list;
  94
  95         /**@brief   LBA tree node*/
  96         RB_ENTRY(ext4_buf) lba_node;
  97
  98         /**@brief   LRU tree node*/
  99         RB_ENTRY(ext4_buf) lru_node;
 100
 101         /**@brief   Dirty list node*/
 102         SLIST_ENTRY(ext4_buf) dirty_node;
 103 };
 104
 105 /**@brief   Block cache descriptor*/
 106 struct ext4_bcache {
 107
 108         /**@brief   Item count in block cache*/
 109         uint32_t cnt;
 110
 111         /**@brief   Item size in block cache*/
 112         uint32_t itemsize;
 113
 114         /**@brief   Last recently used counter*/
 115         uint32_t lru_ctr;
 116
 117         /**@brief   Currently referenced datablocks*/
 118         uint32_t ref_blocks;
 119
 120         /**@brief   Maximum referenced datablocks*/
 121         uint32_t max_ref_blocks;
 122
 123         /**@brief   The blockdev binded to this block cache*/
 124         struct ext4_blockdev *bdev;
 125
 126         /**@brief   A tree holding all bufs*/
 127         RB_HEAD(ext4_buf_lba, ext4_buf) lba_root;
 128
 129         /**@brief   A tree holding unreferenced bufs*/
 130         RB_HEAD(ext4_buf_lru, ext4_buf) lru_root;
 131
 132         /**@brief   A singly-linked list holding dirty buffers*/
 133         SLIST_HEAD(ext4_buf_dirty, ext4_buf) dirty_list;
 134 };
 135
 136 enum bcache_state_bits {
 137         BC_UPTODATE,
 138         BC_DIRTY
 139 };
 140
 141 #define ext4_bcache_set_flag(buf, b)    \
 142         (buf)->flags |= 1 << (b)
 143
 144 #define ext4_bcache_clear_flag(buf, b)    \
 145         (buf)->flags &= ~(1 << (b))
 146
 147 #define ext4_bcache_test_flag(buf, b)    \
 148         (((buf)->flags & (1 << (b))) >> (b))
 149
 150 /**@brief   Static initializer of block cache structure.*/
 151 #define EXT4_BCACHE_STATIC_INSTANCE(__name, __cnt, __itemsize)                 \
 152         static struct ext4_bcache __name = {                                   \
 153             .cnt = __cnt,                                                      \
 154             .itemsize = __itemsize,                                            \
 155             .lru_ctr = 0,                                                      \
 156         }
 157
 158 /**@brief   Insert buffer to dirty cache list
 159  * @param   bc block cache descriptor
 160  * @param   buf buffer descriptor */
 161 static inline void
 162 ext4_bcache_insert_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
 163         if (!buf->on_dirty_list) {
 164                 SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
 165                 buf->on_dirty_list = true;
 166         }
 167 }
 168
 169 /**@brief   Remove buffer to dirty cache list
 170  * @param   bc block cache descriptor
 171  * @param   buf buffer descriptor */
 172 static inline void
 173 ext4_bcache_remove_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
 174         if (buf->on_dirty_list) {
 175                 SLIST_REMOVE(&bc->dirty_list, buf, ext4_buf, dirty_node);
 176                 buf->on_dirty_list = false;
 177         }
 178 }
 179
 180
 181 /**@brief   Dynamic initialization of block cache.
 182  * @param   bc block cache descriptor
 183  * @param   cnt items count in block cache
 184  * @param   itemsize single item size (in bytes)
 185  * @return  standard error code*/
 186 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
 187                              uint32_t itemsize);
 188
 189 /**@brief   Dynamic de-initialization of block cache.
 190  * @param   bc block cache descriptor
 191  * @return  standard error code*/
 192 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc);
 193
 194 /**@brief   Get a buffer with the lowest LRU counter in bcache.
 195  * @param   bc block cache descriptor
 196  * @return  buffer with the lowest LRU counter*/
 197 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc);
 198
 199 /**@brief   Drop unreferenced buffer from bcache.
 200  * @param   bc block cache descriptor
 201  * @param   buf buffer*/
 202 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf);
 203
 204 /**@brief   Allocate block from block cache memory.
 205  *          Unreferenced block allocation is based on LRU
 206  *          (Last Recently Used) algorithm.
 207  * @param   bc block cache descriptor
 208  * @param   b block to alloc
 209  * @param   is_new block is new (needs to be read)
 210  * @return  standard error code*/
 211 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
 212                       bool *is_new);
 213
 214 /**@brief   Free block from cache memory (decrement reference counter).
 215  * @param   bc block cache descriptor
 216  * @param   b block to free
 217  * @return  standard error code*/
 218 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b);
 219
 220 /**@brief   Return a full status of block cache.
 221  * @param   bc block cache descriptor
 222  * @return  full status*/
 223 bool ext4_bcache_is_full(struct ext4_bcache *bc);
 224
 225 #ifdef __cplusplus
 226 }
 227 #endif
 228
 229 #endif /* EXT4_BCACHE_H_ */
 230
 231 /**
 232  * @}
 233  */