include/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 "misc/tree.h"
  49 #include "misc/queue.h"
  50
  51 #define EXT4_BLOCK_ZERO()       \
  52         {.lb_id = 0, .data = 0}
  53
  54 /**@brief   Single block descriptor*/
  55 struct ext4_block {
  56         /**@brief   Logical block ID*/
  57         uint64_t lb_id;
  58
  59         /**@brief   Buffer */
  60         struct ext4_buf *buf;
  61
  62         /**@brief   Data buffer.*/
  63         uint8_t *data;
  64 };
  65
  66 struct ext4_bcache;
  67
  68 /**@brief   Single block descriptor*/
  69 struct ext4_buf {
  70         /**@brief   Flags*/
  71         int flags;
  72
  73         /**@brief   Logical block address*/
  74         uint64_t lba;
  75
  76         /**@brief   Data buffer.*/
  77         uint8_t *data;
  78
  79         /**@brief   LRU priority. (unused) */
  80         uint32_t lru_prio;
  81
  82         /**@brief   LRU id.*/
  83         uint32_t lru_id;
  84
  85         /**@brief   Reference count table*/
  86         uint32_t refctr;
  87
  88         /**@brief   The block cache this buffer belongs to. */
  89         struct ext4_bcache *bc;
  90
  91         /**@brief   Whether or not buffer is on dirty list.*/
  92         bool on_dirty_list;
  93
  94         /**@brief   LBA tree node*/
  95         RB_ENTRY(ext4_buf) lba_node;
  96
  97         /**@brief   LRU tree node*/
  98         RB_ENTRY(ext4_buf) lru_node;
  99
 100         /**@brief   Dirty list node*/
 101         SLIST_ENTRY(ext4_buf) dirty_node;
 102
 103         /**@brief   Callback routine after a disk-write operation.
 104          * @param   bc block cache descriptor
 105          * @param   buf buffer descriptor
 106          * @param   standard error code returned by bdev->bwrite()
 107          * @param   arg argument passed to this routine*/
 108         void (*end_write)(struct ext4_bcache *bc,
 109                           struct ext4_buf *buf,
 110                           int res,
 111                           void *arg);
 112
 113         /**@brief   argument passed to end_write() callback.*/
 114         void *end_write_arg;
 115 };
 116
 117 /**@brief   Block cache descriptor*/
 118 struct ext4_bcache {
 119
 120         /**@brief   Item count in block cache*/
 121         uint32_t cnt;
 122
 123         /**@brief   Item size in block cache*/
 124         uint32_t itemsize;
 125
 126         /**@brief   Last recently used counter*/
 127         uint32_t lru_ctr;
 128
 129         /**@brief   Currently referenced datablocks*/
 130         uint32_t ref_blocks;
 131
 132         /**@brief   Maximum referenced datablocks*/
 133         uint32_t max_ref_blocks;
 134
 135         /**@brief   The blockdev binded to this block cache*/
 136         struct ext4_blockdev *bdev;
 137
 138         /**@brief   The cache should not be shaked */
 139         bool dont_shake;
 140
 141         /**@brief   A tree holding all bufs*/
 142         RB_HEAD(ext4_buf_lba, ext4_buf) lba_root;
 143
 144         /**@brief   A tree holding unreferenced bufs*/
 145         RB_HEAD(ext4_buf_lru, ext4_buf) lru_root;
 146
 147         /**@brief   A singly-linked list holding dirty buffers*/
 148         SLIST_HEAD(ext4_buf_dirty, ext4_buf) dirty_list;
 149 };
 150
 151 /**@brief buffer state bits
 152  *
 153  *  - BC♡UPTODATE: Buffer contains valid data.
 154  *  - BC_DIRTY: Buffer is dirty.
 155  *  - BC_FLUSH: Buffer will be immediately flushed,
 156  *              when no one references it.
 157  *  - BC_TMP: Buffer will be dropped once its refctr
 158  *            reaches zero.
 159  */
 160 enum bcache_state_bits {
 161         BC_UPTODATE,
 162         BC_DIRTY,
 163         BC_FLUSH,
 164         BC_TMP
 165 };
 166
 167 #define ext4_bcache_set_flag(buf, b)    \
 168         (buf)->flags |= 1 << (b)
 169
 170 #define ext4_bcache_clear_flag(buf, b)    \
 171         (buf)->flags &= ~(1 << (b))
 172
 173 #define ext4_bcache_test_flag(buf, b)    \
 174         (((buf)->flags & (1 << (b))) >> (b))
 175
 176 static inline void ext4_bcache_set_dirty(struct ext4_buf *buf) {
 177         ext4_bcache_set_flag(buf, BC_UPTODATE);
 178         ext4_bcache_set_flag(buf, BC_DIRTY);
 179 }
 180
 181 static inline void ext4_bcache_clear_dirty(struct ext4_buf *buf) {
 182         ext4_bcache_clear_flag(buf, BC_UPTODATE);
 183         ext4_bcache_clear_flag(buf, BC_DIRTY);
 184 }
 185
 186 /**@brief   Increment reference counter of buf by 1.*/
 187 #define ext4_bcache_inc_ref(buf) ((buf)->refctr++)
 188
 189 /**@brief   Decrement reference counter of buf by 1.*/
 190 #define ext4_bcache_dec_ref(buf) ((buf)->refctr--)
 191
 192 /**@brief   Insert buffer to dirty cache list
 193  * @param   bc block cache descriptor
 194  * @param   buf buffer descriptor */
 195 static inline void
 196 ext4_bcache_insert_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
 197         if (!buf->on_dirty_list) {
 198                 SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
 199                 buf->on_dirty_list = true;
 200         }
 201 }
 202
 203 /**@brief   Remove buffer to dirty cache list
 204  * @param   bc block cache descriptor
 205  * @param   buf buffer descriptor */
 206 static inline void
 207 ext4_bcache_remove_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
 208         if (buf->on_dirty_list) {
 209                 SLIST_REMOVE(&bc->dirty_list, buf, ext4_buf, dirty_node);
 210                 buf->on_dirty_list = false;
 211         }
 212 }
 213
 214
 215 /**@brief   Dynamic initialization of block cache.
 216  * @param   bc block cache descriptor
 217  * @param   cnt items count in block cache
 218  * @param   itemsize single item size (in bytes)
 219  * @return  standard error code*/
 220 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
 221                              uint32_t itemsize);
 222
 223 /**@brief   Do cleanup works on block cache.
 224  * @param   bc block cache descriptor.*/
 225 void ext4_bcache_cleanup(struct ext4_bcache *bc);
 226
 227 /**@brief   Dynamic de-initialization of block cache.
 228  * @param   bc block cache descriptor
 229  * @return  standard error code*/
 230 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc);
 231
 232 /**@brief   Get a buffer with the lowest LRU counter in bcache.
 233  * @param   bc block cache descriptor
 234  * @return  buffer with the lowest LRU counter*/
 235 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc);
 236
 237 /**@brief   Drop unreferenced buffer from bcache.
 238  * @param   bc block cache descriptor
 239  * @param   buf buffer*/
 240 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf);
 241
 242 /**@brief   Invalidate a buffer.
 243  * @param   bc block cache descriptor
 244  * @param   buf buffer*/
 245 void ext4_bcache_invalidate_buf(struct ext4_bcache *bc,
 246                                 struct ext4_buf *buf);
 247
 248 /**@brief   Invalidate a range of buffers.
 249  * @param   bc block cache descriptor
 250  * @param   from starting lba
 251  * @param   cnt block counts
 252  * @param   buf buffer*/
 253 void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
 254                                 uint64_t from,
 255                                 uint32_t cnt);
 256
 257 /**@brief   Find existing buffer from block cache memory.
 258  *          Unreferenced block allocation is based on LRU
 259  *          (Last Recently Used) algorithm.
 260  * @param   bc block cache descriptor
 261  * @param   b block to alloc
 262  * @param   lba logical block address
 263  * @return  block cache buffer */
 264 struct ext4_buf *
 265 ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
 266                      uint64_t lba);
 267
 268 /**@brief   Allocate block from block cache memory.
 269  *          Unreferenced block allocation is based on LRU
 270  *          (Last Recently Used) algorithm.
 271  * @param   bc block cache descriptor
 272  * @param   b block to alloc
 273  * @param   is_new block is new (needs to be read)
 274  * @return  standard error code*/
 275 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
 276                       bool *is_new);
 277
 278 /**@brief   Free block from cache memory (decrement reference counter).
 279  * @param   bc block cache descriptor
 280  * @param   b block to free
 281  * @return  standard error code*/
 282 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b);
 283
 284 /**@brief   Return a full status of block cache.
 285  * @param   bc block cache descriptor
 286  * @return  full status*/
 287 bool ext4_bcache_is_full(struct ext4_bcache *bc);
 288
 289 #ifdef __cplusplus
 290 }
 291 #endif
 292
 293 #endif /* EXT4_BCACHE_H_ */
 294
 295 /**
 296  * @}
 297  */