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