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     bc->lru_ctr= 0;\r
  52 \r
  53     bc->refctr          = 0;\r
  54     bc->lru_id          = 0;\r
  55     bc->free_delay  = 0;\r
  56     bc->lba                     = 0;\r
  57     bc->data            = 0;\r
  58 \r
  59     bc->refctr   = malloc(cnt * sizeof(uint32_t));\r
  60     if(!bc->refctr)\r
  61         goto error;\r
  62 \r
  63     bc->lru_id = malloc(cnt * sizeof(uint32_t));\r
  64     if(!bc->lru_id)\r
  65         goto error;\r
  66 \r
  67     bc->free_delay = malloc(cnt * sizeof(uint8_t));\r
  68     if(!bc->free_delay)\r
  69         goto error;\r
  70 \r
  71     bc->lba      = malloc(cnt * sizeof(uint64_t));\r
  72     if(!bc->lba)\r
  73         goto error;\r
  74 \r
  75     bc->data     = malloc(cnt * itemsize);\r
  76     if(!bc->data)\r
  77         goto error;\r
  78 \r
  79     memset(bc->refctr, 0, cnt * sizeof(uint32_t));\r
  80     memset(bc->lru_id, 0, cnt * sizeof(uint32_t));\r
  81     memset(bc->free_delay, 0, cnt * sizeof(uint8_t));\r
  82     memset(bc->lba, 0, cnt * sizeof(uint64_t));\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->data)\r
 106         free(bc->data);\r
 107 \r
 108     return ENOMEM;\r
 109 }\r
 110 \r
 111 int ext4_bcache_fini_dynamic(struct     ext4_bcache *bc)\r
 112 {\r
 113     if(bc->refctr)\r
 114         free(bc->refctr);\r
 115 \r
 116     if(bc->lru_id)\r
 117         free(bc->lru_id);\r
 118 \r
 119     if(bc->free_delay)\r
 120         free(bc->free_delay);\r
 121 \r
 122     if(bc->lba)\r
 123         free(bc->lba);\r
 124 \r
 125     if(bc->data)\r
 126         free(bc->data);\r
 127 \r
 128     bc->lru_ctr= 0;\r
 129 \r
 130     bc->refctr          = 0;\r
 131     bc->lru_id          = 0;\r
 132     bc->free_delay  = 0;\r
 133     bc->lba                     = 0;\r
 134     bc->data            = 0;\r
 135 \r
 136     return EOK;\r
 137 }\r
 138 \r
 139 \r
 140 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,\r
 141     bool *is_new)\r
 142 {\r
 143     uint32_t i;\r
 144     ext4_assert(bc && b && is_new);\r
 145 \r
 146     /*Check if valid.*/\r
 147     ext4_assert(b->lb_id);\r
 148     if(!b->lb_id){\r
 149         ext4_assert(b->lb_id);\r
 150     }\r
 151 \r
 152     uint32_t cache_id = bc->cnt;\r
 153     uint32_t alloc_id;\r
 154 \r
 155     *is_new = false;\r
 156 \r
 157     /*Find in free blocks (Last Recently Used).*/\r
 158     for (i = 0; i < bc->cnt; ++i) {\r
 159 \r
 160         /*Check if block is already in cache*/\r
 161         if(b->lb_id == bc->lba[i]){\r
 162 \r
 163             if(!bc->refctr[i] && !bc->free_delay[i])\r
 164                 bc->ref_blocks++;\r
 165 \r
 166             /*Update reference counter*/\r
 167             bc->refctr[i]++;\r
 168 \r
 169             /*Update usage marker*/\r
 170             bc->lru_id[i] = ++bc->lru_ctr;\r
 171 \r
 172             /*Set valid cache data and id*/\r
 173             b->data = bc->data + i * bc->itemsize;\r
 174             b->cache_id = i;\r
 175 \r
 176             return EOK;\r
 177         }\r
 178 \r
 179         /*Best fit calculations.*/\r
 180         if(bc->refctr[i])\r
 181             continue;\r
 182 \r
 183         if(bc->free_delay[i])\r
 184             continue;\r
 185 \r
 186         /*Block is unreferenced, but it may exist block with\r
 187          * lower usage marker*/\r
 188 \r
 189         /*First find.*/\r
 190         if(cache_id == bc->cnt){\r
 191             cache_id = i;\r
 192             alloc_id = bc->lru_id[i];\r
 193             continue;\r
 194         }\r
 195 \r
 196         /*Next find*/\r
 197         if(alloc_id <= bc->lru_id[i])\r
 198             continue;\r
 199 \r
 200         /*This block has lower alloc id marker*/\r
 201         cache_id = i;\r
 202         alloc_id = bc->lru_id[i];\r
 203     }\r
 204 \r
 205 \r
 206     if(cache_id != bc->cnt){\r
 207         /*There was unreferenced block*/\r
 208         bc->lba[cache_id]          = b->lb_id;\r
 209         bc->refctr[cache_id]   = 1;\r
 210         bc->lru_id[cache_id] = ++bc->lru_ctr;\r
 211 \r
 212         /*Set valid cache data and id*/\r
 213         b->data = bc->data + cache_id * bc->itemsize;\r
 214         b->cache_id = cache_id;\r
 215 \r
 216         /*Statistics*/\r
 217         bc->ref_blocks++;\r
 218         if(bc->ref_blocks > bc->max_ref_blocks)\r
 219             bc->max_ref_blocks = bc->ref_blocks;\r
 220 \r
 221 \r
 222         /*Block needs to be read.*/\r
 223         *is_new = true;\r
 224 \r
 225         return EOK;\r
 226     }\r
 227 \r
 228     ext4_dprintf(EXT4_DEBUG_BCACHE,\r
 229         "ext4_bcache_alloc: FAIL, unable to alloc block cache!\n");\r
 230     return ENOMEM;\r
 231 }\r
 232 \r
 233 int ext4_bcache_free (struct ext4_bcache *bc, struct ext4_block *b,\r
 234     uint8_t free_delay)\r
 235 {\r
 236     ext4_assert(bc && b);\r
 237 \r
 238     /*Check if valid.*/\r
 239     ext4_assert(b->lb_id);\r
 240 \r
 241     /*Block should be in cache.*/\r
 242     ext4_assert(b->cache_id < bc->cnt);\r
 243 \r
 244     /*Check if someone don't try free unreferenced block cache.*/\r
 245     ext4_assert(bc->refctr[b->cache_id]);\r
 246 \r
 247     /*Just decrease reference counter*/\r
 248     if(bc->refctr[b->cache_id])\r
 249         bc->refctr[b->cache_id]--;\r
 250 \r
 251     if(free_delay)\r
 252         bc->free_delay[b->cache_id] = free_delay;\r
 253 \r
 254     /*Update statistics*/\r
 255     if(!bc->refctr[b->cache_id] && !bc->free_delay[b->cache_id])\r
 256         bc->ref_blocks--;\r
 257 \r
 258     b->lb_id    = 0;\r
 259     b->data     = 0;\r
 260     b->cache_id = 0;\r
 261 \r
 262     return EOK;\r
 263 }\r
 264 \r
 265 \r
 266 \r
 267 bool ext4_bcache_is_full(struct ext4_bcache *bc)\r
 268 {\r
 269     return (bc->cnt == bc->ref_blocks);\r
 270 }\r
 271 \r
 272 /**\r
 273  * @}\r
 274  */\r
 275 \r
 276 \r