src/ext4_bcache.c

   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.c
  34  * @brief Block cache allocator.
  35  */
  36
  37 #include <ext4_config.h>
  38 #include <ext4_types.h>
  39 #include <ext4_bcache.h>
  40 #include <ext4_blockdev.h>
  41 #include <ext4_debug.h>
  42 #include <ext4_errno.h>
  43
  44 #include <string.h>
  45 #include <stdlib.h>
  46
  47 static int ext4_bcache_lba_compare(struct ext4_buf *a, struct ext4_buf *b)
  48 {
  49          if (a->lba > b->lba)
  50                  return 1;
  51          else if (a->lba < b->lba)
  52                  return -1;
  53          return 0;
  54 }
  55
  56 static int ext4_bcache_lru_compare(struct ext4_buf *a, struct ext4_buf *b)
  57 {
  58         if (a->lru_id > b->lru_id)
  59                 return 1;
  60         else if (a->lru_id < b->lru_id)
  61                 return -1;
  62         return 0;
  63 }
  64
  65 RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
  66                      ext4_bcache_lba_compare, static inline)
  67 RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
  68                      ext4_bcache_lru_compare, static inline)
  69
  70 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
  71                              uint32_t itemsize)
  72 {
  73         ext4_assert(bc && cnt && itemsize);
  74
  75         memset(bc, 0, sizeof(struct ext4_bcache));
  76
  77         bc->cnt = cnt;
  78         bc->itemsize = itemsize;
  79         bc->ref_blocks = 0;
  80         bc->max_ref_blocks = 0;
  81
  82         return EOK;
  83 }
  84
  85 void ext4_bcache_cleanup(struct ext4_bcache *bc)
  86 {
  87         struct ext4_buf *buf, *tmp;
  88         RB_FOREACH_SAFE(buf, ext4_buf_lba, &bc->lba_root, tmp) {
  89                 ext4_block_flush_buf(bc->bdev, buf);
  90                 ext4_bcache_drop_buf(bc, buf);
  91         }
  92 }
  93
  94 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
  95 {
  96         memset(bc, 0, sizeof(struct ext4_bcache));
  97         return EOK;
  98 }
  99
 100 /**@brief:
 101  *
 102  *  This is ext4_bcache, the module handling basic buffer-cache stuff.
 103  *
 104  *  Buffers in a bcache are sorted by their LBA and stored in a
 105  *  RB-Tree(lba_root).
 106  *
 107  *  Bcache also maintains another RB-Tree(lru_root) right now, where
 108  *  buffers are sorted by their LRU id.
 109  *
 110  *  A singly-linked list is used to track those dirty buffers which are
 111  *  ready to be flushed. (Those buffers which are dirty but also referenced
 112  *  are not considered ready to be flushed.)
 113  *
 114  *  When a buffer is not referenced, it will be stored in both lba_root
 115  *  and lru_root, while it will only be stored in lba_root when it is
 116  *  referenced.
 117  */
 118
 119 static struct ext4_buf *
 120 ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
 121 {
 122         void *data;
 123         struct ext4_buf *buf;
 124         data = ext4_malloc(bc->itemsize);
 125         if (!data)
 126                 return NULL;
 127
 128         buf = ext4_calloc(1, sizeof(struct ext4_buf));
 129         if (!buf) {
 130                 ext4_free(data);
 131                 return NULL;
 132         }
 133
 134         buf->lba = lba;
 135         buf->data = data;
 136         buf->bc = bc;
 137         return buf;
 138 }
 139
 140 static void ext4_buf_free(struct ext4_buf *buf)
 141 {
 142         ext4_free(buf->data);
 143         ext4_free(buf);
 144 }
 145
 146 static struct ext4_buf *
 147 ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
 148 {
 149         struct ext4_buf tmp = {
 150                 .lba = lba
 151         };
 152
 153         return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
 154 }
 155
 156 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
 157 {
 158         return RB_MIN(ext4_buf_lru, &bc->lru_root);
 159 }
 160
 161 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
 162 {
 163         /* Warn on dropping any referenced buffers.*/
 164         if (buf->refctr) {
 165                 ext4_dbg(DEBUG_BCACHE, DBG_WARN "Buffer is still referenced. "
 166                                 "lba: %" PRIu64 ", refctr: %" PRIu32 "\n",
 167                                 buf->lba, buf->refctr);
 168         } else
 169                 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
 170
 171         RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
 172
 173         /*Forcibly drop dirty buffer.*/
 174         if (ext4_bcache_test_flag(buf, BC_DIRTY))
 175                 ext4_bcache_remove_dirty_node(bc, buf);
 176
 177         ext4_buf_free(buf);
 178         bc->ref_blocks--;
 179 }
 180
 181 void ext4_bcache_invalidate_buf(struct ext4_bcache *bc,
 182                                 struct ext4_buf *buf)
 183 {
 184         buf->end_write = NULL;
 185         buf->end_write_arg = NULL;
 186
 187         /* Clear both dirty and up-to-date flags. */
 188         if (ext4_bcache_test_flag(buf, BC_DIRTY))
 189                 ext4_bcache_remove_dirty_node(bc, buf);
 190
 191         ext4_bcache_clear_dirty(buf);
 192 }
 193
 194 void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
 195                                 uint64_t from,
 196                                 uint32_t cnt)
 197 {
 198         uint64_t end = from + cnt - 1;
 199         struct ext4_buf *tmp = ext4_buf_lookup(bc, from), *buf;
 200         RB_FOREACH_FROM(buf, ext4_buf_lba, tmp) {
 201                 if (buf->lba > end)
 202                         break;
 203
 204                 ext4_bcache_invalidate_buf(bc, buf);
 205         }
 206 }
 207
 208 struct ext4_buf *
 209 ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
 210                      uint64_t lba)
 211 {
 212         struct ext4_buf *buf = ext4_buf_lookup(bc, lba);
 213         if (buf) {
 214                 /* If buffer is not referenced. */
 215                 if (!buf->refctr) {
 216                         /* Assign new value to LRU id and increment LRU counter
 217                          * by 1*/
 218                         buf->lru_id = ++bc->lru_ctr;
 219                         RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
 220                         if (ext4_bcache_test_flag(buf, BC_DIRTY))
 221                                 ext4_bcache_remove_dirty_node(bc, buf);
 222
 223                 }
 224
 225                 ext4_bcache_inc_ref(buf);
 226
 227                 b->lb_id = lba;
 228                 b->buf = buf;
 229                 b->data = buf->data;
 230         }
 231         return buf;
 232 }
 233
 234 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
 235                       bool *is_new)
 236 {
 237         /* Try to search the buffer with exaxt LBA. */
 238         struct ext4_buf *buf = ext4_bcache_find_get(bc, b, b->lb_id);
 239         if (buf) {
 240                 *is_new = false;
 241                 return EOK;
 242         }
 243
 244         /* We need to allocate one buffer.*/
 245         buf = ext4_buf_alloc(bc, b->lb_id);
 246         if (!buf)
 247                 return ENOMEM;
 248
 249         RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
 250         /* One more buffer in bcache now. :-) */
 251         bc->ref_blocks++;
 252
 253         /*Calc ref blocks max depth*/
 254         if (bc->max_ref_blocks < bc->ref_blocks)
 255                 bc->max_ref_blocks = bc->ref_blocks;
 256
 257
 258         ext4_bcache_inc_ref(buf);
 259         /* Assign new value to LRU id and increment LRU counter
 260          * by 1*/
 261         buf->lru_id = ++bc->lru_ctr;
 262
 263         b->buf = buf;
 264         b->data = buf->data;
 265
 266         *is_new = true;
 267         return EOK;
 268 }
 269
 270 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b)
 271 {
 272         struct ext4_buf *buf = b->buf;
 273
 274         ext4_assert(bc && b);
 275
 276         /*Check if valid.*/
 277         ext4_assert(b->lb_id);
 278
 279         /*Block should have a valid pointer to ext4_buf.*/
 280         ext4_assert(buf);
 281
 282         /*Check if someone don't try free unreferenced block cache.*/
 283         ext4_assert(buf->refctr);
 284
 285         /*Just decrease reference counter*/
 286         ext4_bcache_dec_ref(buf);
 287
 288         /* We are the last one touching this buffer, do the cleanups. */
 289         if (!buf->refctr) {
 290                 RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
 291                 /* This buffer is ready to be flushed. */
 292                 if (ext4_bcache_test_flag(buf, BC_DIRTY) &&
 293                     ext4_bcache_test_flag(buf, BC_UPTODATE)) {
 294                         if (bc->bdev->cache_write_back &&
 295                             !ext4_bcache_test_flag(buf, BC_FLUSH) &&
 296                             !ext4_bcache_test_flag(buf, BC_TMP))
 297                                 ext4_bcache_insert_dirty_node(bc, buf);
 298                         else {
 299                                 ext4_block_flush_buf(bc->bdev, buf);
 300                                 ext4_bcache_clear_flag(buf, BC_FLUSH);
 301                         }
 302                 }
 303
 304                 /* The buffer is invalidated...drop it. */
 305                 if (!ext4_bcache_test_flag(buf, BC_UPTODATE) ||
 306                     ext4_bcache_test_flag(buf, BC_TMP))
 307                         ext4_bcache_drop_buf(bc, buf);
 308
 309         }
 310
 311         b->lb_id = 0;
 312         b->data = 0;
 313
 314         return EOK;
 315 }
 316
 317 bool ext4_bcache_is_full(struct ext4_bcache *bc)
 318 {
 319         return (bc->cnt <= bc->ref_blocks);
 320 }
 321
 322
 323 /**
 324  * @}
 325  */