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 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
  46                              uint32_t itemsize)
  47 {
  48         ext4_assert(bc && cnt && itemsize);
  49
  50         memset(bc, 0, sizeof(struct ext4_bcache));
  51
  52         bc->data = malloc(cnt * itemsize);
  53         if (!bc->data)
  54                 goto error;
  55
  56         bc->cnt = cnt;
  57         bc->itemsize = itemsize;
  58         bc->ref_blocks = 0;
  59         bc->max_ref_blocks = 0;
  60
  61         return EOK;
  62
  63 error:
  64
  65         if (bc->data)
  66                 free(bc->data);
  67
  68         memset(bc, 0, sizeof(struct ext4_bcache));
  69
  70         return ENOMEM;
  71 }
  72
  73 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
  74 {
  75         if (bc->data)
  76                 free(bc->data);
  77
  78         memset(bc, 0, sizeof(struct ext4_bcache));
  79
  80         return EOK;
  81 }
  82
  83 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
  84                       bool *is_new)
  85 {
  86         uint32_t i;
  87         ext4_assert(bc && b && is_new);
  88
  89         /*Check if valid.*/
  90         ext4_assert(b->lb_id);
  91         if (!b->lb_id) {
  92                 ext4_assert(b->lb_id);
  93         }
  94
  95         uint32_t cache_id = bc->cnt;
  96         uint32_t alloc_id = 0;
  97
  98         *is_new = false;
  99
 100         /*Find in free blocks (Last Recently Used).*/
 101         for (i = 0; i < bc->cnt; ++i) {
 102
 103                 /*Check if block is already in cache*/
 104                 if (b->lb_id == bc->lba[i]) {
 105
 106                         if (!bc->refctr[i] && !bc->free_delay[i])
 107                                 bc->ref_blocks++;
 108
 109                         /*Update reference counter*/
 110                         bc->refctr[i]++;
 111
 112                         /*Update usage marker*/
 113                         bc->lru_id[i] = ++bc->lru_ctr;
 114
 115                         /*Set valid cache data and id*/
 116                         b->data = bc->data + i * bc->itemsize;
 117                         b->cache_id = i;
 118
 119                         return EOK;
 120                 }
 121
 122                 /*Best fit calculations.*/
 123                 if (bc->refctr[i])
 124                         continue;
 125
 126                 if (bc->free_delay[i])
 127                         continue;
 128
 129                 /*Block is unreferenced, but it may exist block with
 130                  * lower usage marker*/
 131
 132                 /*First find.*/
 133                 if (cache_id == bc->cnt) {
 134                         cache_id = i;
 135                         alloc_id = bc->lru_id[i];
 136                         continue;
 137                 }
 138
 139                 /*Next find*/
 140                 if (alloc_id <= bc->lru_id[i])
 141                         continue;
 142
 143                 /*This block has lower alloc id marker*/
 144                 cache_id = i;
 145                 alloc_id = bc->lru_id[i];
 146         }
 147
 148         if (cache_id != bc->cnt) {
 149                 /*There was unreferenced block*/
 150                 bc->lba[cache_id] = b->lb_id;
 151                 bc->refctr[cache_id] = 1;
 152                 bc->lru_id[cache_id] = ++bc->lru_ctr;
 153
 154                 /*Set valid cache data and id*/
 155                 b->data = bc->data + cache_id * bc->itemsize;
 156                 b->cache_id = cache_id;
 157
 158                 /*Statistics*/
 159                 bc->ref_blocks++;
 160                 if (bc->ref_blocks > bc->max_ref_blocks)
 161                         bc->max_ref_blocks = bc->ref_blocks;
 162
 163                 /*Block needs to be read.*/
 164                 *is_new = true;
 165
 166                 return EOK;
 167         }
 168
 169         ext4_dprintf(EXT4_DEBUG_BCACHE,
 170                      "ext4_bcache_alloc: FAIL, unable to alloc block cache!\n");
 171         return ENOMEM;
 172 }
 173
 174 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b,
 175                      uint8_t free_delay)
 176 {
 177         ext4_assert(bc && b);
 178
 179         /*Check if valid.*/
 180         ext4_assert(b->lb_id);
 181
 182         /*Block should be in cache.*/
 183         ext4_assert(b->cache_id < bc->cnt);
 184
 185         /*Check if someone don't try free unreferenced block cache.*/
 186         ext4_assert(bc->refctr[b->cache_id]);
 187
 188         /*Just decrease reference counter*/
 189         if (bc->refctr[b->cache_id])
 190                 bc->refctr[b->cache_id]--;
 191
 192         if (free_delay)
 193                 bc->free_delay[b->cache_id] = free_delay;
 194
 195         /*Update statistics*/
 196         if (!bc->refctr[b->cache_id] && !bc->free_delay[b->cache_id])
 197                 bc->ref_blocks--;
 198
 199         b->lb_id = 0;
 200         b->data = 0;
 201         b->cache_id = 0;
 202
 203         return EOK;
 204 }
 205
 206 bool ext4_bcache_is_full(struct ext4_bcache *bc)
 207 {
 208         return (bc->cnt == bc->ref_blocks);
 209 }
 210
 211 /**
 212  * @}
 213  */