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