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
  46 ext4_bcache_lba_compare(struct ext4_buf *a,
  47                         struct ext4_buf *b)
  48 {
  49         return a->lba - b->lba;
  50 }
  51
  52 static int
  53 ext4_bcache_lru_compare(struct ext4_buf *a,
  54                         struct ext4_buf *b)
  55 {
  56         return a->lru_id - b->lru_id;
  57 }
  58
  59 RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
  60                      ext4_bcache_lba_compare, static inline)
  61 RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
  62                      ext4_bcache_lru_compare, static inline)
  63
  64 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
  65                              uint32_t itemsize)
  66 {
  67         ext4_assert(bc && cnt && itemsize);
  68
  69         memset(bc, 0, sizeof(struct ext4_bcache));
  70
  71         bc->cnt = cnt;
  72         bc->itemsize = itemsize;
  73         bc->ref_blocks = 0;
  74         bc->max_ref_blocks = 0;
  75
  76         return EOK;
  77 }
  78
  79 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
  80 {
  81         memset(bc, 0, sizeof(struct ext4_bcache));
  82         return EOK;
  83 }
  84
  85 static struct ext4_buf *
  86 ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
  87 {
  88         void *data;
  89         struct ext4_buf *buf;
  90         data = malloc(bc->itemsize);
  91         if (!data)
  92                 return NULL;
  93
  94         buf = malloc(sizeof(struct ext4_buf));
  95         if (!buf) {
  96                 free(data);
  97                 return NULL;
  98         }
  99
 100         buf->flags = 0;
 101         buf->lba = lba;
 102         buf->data = data;
 103         buf->lru_id = 0;
 104         buf->refctr = 0;
 105         memset(&buf->lba_node, 0, sizeof(buf->lba_node));
 106         memset(&buf->lru_node, 0, sizeof(buf->lru_node));
 107         memset(&buf->dirty_node, 0, sizeof(buf->dirty_node));
 108         return buf;
 109 }
 110
 111 static void ext4_buf_free(struct ext4_buf *buf)
 112 {
 113         free(buf->data);
 114         free(buf);
 115 }
 116
 117 static struct ext4_buf *
 118 ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
 119 {
 120         struct ext4_buf tmp = {
 121                 .lba = lba
 122         };
 123
 124         return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
 125 }
 126
 127 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
 128 {
 129         return RB_MIN(ext4_buf_lba, &bc->lba_root);
 130 }
 131
 132 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
 133 {
 134         /*Cannot drop any referenced buffers.*/
 135         ext4_assert(!buf->refctr);
 136
 137         RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
 138         RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
 139
 140         /*Forcibly drop dirty buffer.*/
 141         if (ext4_bcache_test_flag(buf, BC_DIRTY))
 142                 SLIST_REMOVE(&bc->dirty_list,
 143                              buf,
 144                              ext4_buf,
 145                              dirty_node);
 146
 147         ext4_buf_free(buf);
 148         bc->ref_blocks--;
 149 }
 150
 151 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
 152                       bool *is_new)
 153 {
 154         struct ext4_buf *buf = ext4_buf_lookup(bc, b->lb_id);
 155         if (buf) {
 156                 if (!buf->refctr) {
 157                         buf->lru_id = ++bc->lru_ctr;
 158                         RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
 159                         if (ext4_bcache_test_flag(buf, BC_DIRTY))
 160                                 SLIST_REMOVE(&bc->dirty_list,
 161                                              buf,
 162                                              ext4_buf,
 163                                              dirty_node);
 164
 165                 }
 166
 167                 buf->refctr++;
 168                 b->uptodate = ext4_bcache_test_flag(buf, BC_UPTODATE);
 169                 b->dirty = false;
 170                 b->buf = buf;
 171                 b->data = buf->data;
 172                 *is_new = false;
 173                 return EOK;
 174         }
 175         buf = ext4_buf_alloc(bc, b->lb_id);
 176         if (!buf)
 177                 return ENOMEM;
 178
 179         RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
 180         bc->ref_blocks++;
 181
 182         buf->refctr = 1;
 183         buf->lru_id = ++bc->lru_ctr;
 184         b->uptodate = false;
 185         b->dirty = false;
 186         b->buf = buf;
 187         b->data = buf->data;
 188         *is_new = true;
 189         return EOK;
 190 }
 191
 192 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b,
 193                      uint8_t free_delay)
 194 {
 195         struct ext4_buf *buf = b->buf;
 196
 197         ext4_assert(bc && b);
 198
 199         /*Check if valid.*/
 200         ext4_assert(b->lb_id);
 201
 202         /*Block should have a valid pointer to ext4_buf.*/
 203         ext4_assert(buf);
 204
 205         /*Check if someone don't try free unreferenced block cache.*/
 206         ext4_assert(buf->refctr);
 207
 208         /*Just decrease reference counter*/
 209         buf->refctr--;
 210
 211         if (free_delay)
 212                 bc->free_delay = free_delay;
 213
 214         if (b->dirty) {
 215                 ext4_bcache_set_flag(buf, BC_DIRTY);
 216                 ext4_bcache_set_flag(buf, BC_UPTODATE);
 217                 b->uptodate = true;
 218         }
 219         if (!b->uptodate)
 220                 ext4_bcache_clear_flag(buf, BC_UPTODATE);
 221
 222         if (!buf->refctr) {
 223                 RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
 224                 if (ext4_bcache_test_flag(buf, BC_DIRTY))
 225                         SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
 226
 227                 if (!ext4_bcache_test_flag(buf, BC_UPTODATE))
 228                         ext4_bcache_drop_buf(bc, buf);
 229
 230         }
 231
 232         b->lb_id = 0;
 233         b->data = 0;
 234         b->uptodate = false;
 235         b->dirty = false;
 236
 237         return EOK;
 238 }
 239
 240 bool ext4_bcache_is_full(struct ext4_bcache *bc)
 241 {
 242         return (bc->cnt <= bc->ref_blocks);
 243 }
 244
 245 /**
 246  * @}
 247  */