lwext4/ext4_bcache.c

   1 /*\r
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
   3  * All rights reserved.\r
   4  *\r
   5  * Redistribution and use in source and binary forms, with or without\r
   6  * modification, are permitted provided that the following conditions\r
   7  * are met:\r
   8  *\r
   9  * - Redistributions of source code must retain the above copyright\r
  10  *   notice, this list of conditions and the following disclaimer.\r
  11  * - Redistributions in binary form must reproduce the above copyright\r
  12  *   notice, this list of conditions and the following disclaimer in the\r
  13  *   documentation and/or other materials provided with the distribution.\r
  14  * - The name of the author may not be used to endorse or promote products\r
  15  *   derived from this software without specific prior written permission.\r
  16  *\r
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  27  */\r
  28 \r
  29 /** @addtogroup lwext4\r
  30  * @{\r
  31  */\r
  32 /**\r
  33  * @file  ext4_bcache.c\r
  34  * @brief Block cache allocator.\r
  35  */\r
  36 \r
  37 #include <ext4_config.h>\r
  38 #include <ext4_bcache.h>\r
  39 #include <ext4_debug.h>\r
  40 #include <ext4_errno.h>\r
  41 \r
  42 #include <string.h>\r
  43 #include <stdlib.h>\r
  44 \r
  45 \r
  46 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,\r
  47     uint32_t itemsize)\r
  48 {\r
  49     ext4_assert(bc && cnt && itemsize);\r
  50 \r
  51     memset(bc, 0, sizeof(struct ext4_bcache));\r
  52 \r
  53     bc->refctr = malloc(cnt * sizeof(uint32_t));\r
  54     if(!bc->refctr)\r
  55         goto error;\r
  56 \r
  57     bc->lru_id = malloc(cnt * sizeof(uint32_t));\r
  58     if(!bc->lru_id)\r
  59         goto error;\r
  60 \r
  61     bc->free_delay = malloc(cnt * sizeof(uint8_t));\r
  62     if(!bc->free_delay)\r
  63         goto error;\r
  64 \r
  65     bc->lba = malloc(cnt * sizeof(uint64_t));\r
  66     if(!bc->lba)\r
  67         goto error;\r
  68 \r
  69     bc->dirty = malloc(cnt * sizeof(bool));\r
  70     if(!bc->dirty)\r
  71         goto error;\r
  72 \r
  73 \r
  74     bc->data = malloc(cnt * itemsize);\r
  75     if(!bc->data)\r
  76         goto error;\r
  77 \r
  78     memset(bc->refctr, 0, cnt * sizeof(uint32_t));\r
  79     memset(bc->lru_id, 0, cnt * sizeof(uint32_t));\r
  80     memset(bc->free_delay, 0, cnt * sizeof(uint8_t));\r
  81     memset(bc->lba, 0, cnt * sizeof(uint64_t));\r
  82     memset(bc->dirty, 0, cnt * sizeof(bool));\r
  83 \r
  84     bc->cnt = cnt;\r
  85     bc->itemsize = itemsize;\r
  86     bc->ref_blocks = 0;\r
  87     bc->max_ref_blocks = 0;\r
  88 \r
  89     return EOK;\r
  90 \r
  91     error:\r
  92 \r
  93     if(bc->refctr)\r
  94         free(bc->refctr);\r
  95 \r
  96     if(bc->lru_id)\r
  97         free(bc->lru_id);\r
  98 \r
  99     if(bc->free_delay)\r
 100         free(bc->free_delay);\r
 101 \r
 102     if(bc->lba)\r
 103         free(bc->lba);\r
 104 \r
 105     if(bc->dirty)\r
 106        free(bc->dirty);\r
 107 \r
 108     if(bc->data)\r
 109         free(bc->data);\r
 110 \r
 111     memset(bc, 0, sizeof(struct ext4_bcache));\r
 112 \r
 113     return ENOMEM;\r
 114 }\r
 115 \r
 116 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)\r
 117 {\r
 118     if(bc->refctr)\r
 119         free(bc->refctr);\r
 120 \r
 121     if(bc->lru_id)\r
 122         free(bc->lru_id);\r
 123 \r
 124     if(bc->free_delay)\r
 125         free(bc->free_delay);\r
 126 \r
 127     if(bc->lba)\r
 128         free(bc->lba);\r
 129 \r
 130     if(bc->dirty)\r
 131        free(bc->dirty);\r
 132 \r
 133     if(bc->data)\r
 134         free(bc->data);\r
 135 \r
 136     memset(bc, 0, sizeof(struct ext4_bcache));\r
 137 \r
 138     return EOK;\r
 139 }\r
 140 \r
 141 \r
 142 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,\r
 143     bool *is_new)\r
 144 {\r
 145     uint32_t i;\r
 146     ext4_assert(bc && b && is_new);\r
 147 \r
 148     /*Check if valid.*/\r
 149     ext4_assert(b->lb_id);\r
 150     if(!b->lb_id){\r
 151         ext4_assert(b->lb_id);\r
 152     }\r
 153 \r
 154     uint32_t cache_id = bc->cnt;\r
 155     uint32_t alloc_id = 0;\r
 156 \r
 157     *is_new = false;\r
 158 \r
 159     /*Find in free blocks (Last Recently Used).*/\r
 160     for (i = 0; i < bc->cnt; ++i) {\r
 161 \r
 162         /*Check if block is already in cache*/\r
 163         if(b->lb_id == bc->lba[i]){\r
 164 \r
 165             if(!bc->refctr[i] && !bc->free_delay[i])\r
 166                 bc->ref_blocks++;\r
 167 \r
 168             /*Update reference counter*/\r
 169             bc->refctr[i]++;\r
 170 \r
 171             /*Update usage marker*/\r
 172             bc->lru_id[i] = ++bc->lru_ctr;\r
 173 \r
 174             /*Set valid cache data and id*/\r
 175             b->data = bc->data + i * bc->itemsize;\r
 176             b->cache_id = i;\r
 177 \r
 178             return EOK;\r
 179         }\r
 180 \r
 181         /*Best fit calculations.*/\r
 182         if(bc->refctr[i])\r
 183             continue;\r
 184 \r
 185         if(bc->free_delay[i])\r
 186             continue;\r
 187 \r
 188         /*Block is unreferenced, but it may exist block with\r
 189          * lower usage marker*/\r
 190 \r
 191         /*First find.*/\r
 192         if(cache_id == bc->cnt){\r
 193             cache_id = i;\r
 194             alloc_id = bc->lru_id[i];\r
 195             continue;\r
 196         }\r
 197 \r
 198         /*Next find*/\r
 199         if(alloc_id <= bc->lru_id[i])\r
 200             continue;\r
 201 \r
 202         /*This block has lower alloc id marker*/\r
 203         cache_id = i;\r
 204         alloc_id = bc->lru_id[i];\r
 205     }\r
 206 \r
 207 \r
 208     if(cache_id != bc->cnt){\r
 209         /*There was unreferenced block*/\r
 210         bc->lba[cache_id] = b->lb_id;\r
 211         bc->refctr[cache_id] = 1;\r
 212         bc->lru_id[cache_id] = ++bc->lru_ctr;\r
 213 \r
 214         /*Set valid cache data and id*/\r
 215         b->data = bc->data + cache_id * bc->itemsize;\r
 216         b->cache_id = cache_id;\r
 217 \r
 218         /*Statistics*/\r
 219         bc->ref_blocks++;\r
 220         if(bc->ref_blocks > bc->max_ref_blocks)\r
 221             bc->max_ref_blocks = bc->ref_blocks;\r
 222 \r
 223 \r
 224         /*Block needs to be read.*/\r
 225         *is_new = true;\r
 226 \r
 227         return EOK;\r
 228     }\r
 229 \r
 230     ext4_dprintf(EXT4_DEBUG_BCACHE,\r
 231         "ext4_bcache_alloc: FAIL, unable to alloc block cache!\n");\r
 232     return ENOMEM;\r
 233 }\r
 234 \r
 235 int ext4_bcache_free (struct ext4_bcache *bc, struct ext4_block *b,\r
 236     uint8_t free_delay)\r
 237 {\r
 238     ext4_assert(bc && b);\r
 239 \r
 240     /*Check if valid.*/\r
 241     ext4_assert(b->lb_id);\r
 242 \r
 243     /*Block should be in cache.*/\r
 244     ext4_assert(b->cache_id < bc->cnt);\r
 245 \r
 246     /*Check if someone don't try free unreferenced block cache.*/\r
 247     ext4_assert(bc->refctr[b->cache_id]);\r
 248 \r
 249     /*Just decrease reference counter*/\r
 250     if(bc->refctr[b->cache_id])\r
 251         bc->refctr[b->cache_id]--;\r
 252 \r
 253     if(free_delay)\r
 254         bc->free_delay[b->cache_id] = free_delay;\r
 255 \r
 256     /*Update statistics*/\r
 257     if(!bc->refctr[b->cache_id] && !bc->free_delay[b->cache_id])\r
 258         bc->ref_blocks--;\r
 259 \r
 260     b->lb_id = 0;\r
 261     b->data = 0;\r
 262     b->cache_id = 0;\r
 263 \r
 264     return EOK;\r
 265 }\r
 266 \r
 267 \r
 268 \r
 269 bool ext4_bcache_is_full(struct ext4_bcache *bc)\r
 270 {\r
 271     return (bc->cnt == bc->ref_blocks);\r
 272 }\r
 273 \r
 274 /**\r
 275  * @}\r
 276  */\r
 277 \r
 278 \r