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