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