1/* $NetBSD: chfs_build.c,v 1.6 2021/07/19 21:04:39 andvar Exp $ */ 2 3/*- 4 * Copyright (c) 2010 Department of Software Engineering, 5 * University of Szeged, Hungary 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to The NetBSD Foundation 9 * by the Department of Software Engineering, University of Szeged, Hungary 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 21 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 23 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 25 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 27 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 28 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33#include "chfs.h" 34 35 36/* 37 * chfs_calc_trigger_levels - setup filesystem parameters 38 * Setups filesystem parameters (reserved blocks and GC trigger level) 39 * for a specific flash. 40 */ 41void 42chfs_calc_trigger_levels(struct chfs_mount *chmp) 43{ 44 uint32_t size; 45 46 chmp->chm_resv_blocks_deletion = 2; 47 48 size = chmp->chm_ebh->flash_size / 50; /* 2% of flash size */ 49 size += chmp->chm_ebh->peb_nr * 100; 50 size += chmp->chm_ebh->eb_size - 1; 51 52 chmp->chm_resv_blocks_write = 53 chmp->chm_resv_blocks_deletion + (size / chmp->chm_ebh->eb_size); 54 chmp->chm_resv_blocks_gctrigger = chmp->chm_resv_blocks_write + 1; 55 chmp->chm_resv_blocks_gcmerge = chmp->chm_resv_blocks_deletion + 1; 56 chmp->chm_vdirty_blocks_gctrigger = chmp->chm_resv_blocks_gctrigger * 10; 57 58 chmp->chm_nospc_dirty = 59 chmp->chm_ebh->eb_size + (chmp->chm_ebh->flash_size / 100); 60} 61 62 63/* 64 * chfs_build_set_vnodecache_nlink - set pvno and nlink in vnodecaches 65 * Travels vc's directory entries and sets the pvno and nlink 66 * attribute of the vnode where the dirent's vno points. 67 */ 68void 69chfs_build_set_vnodecache_nlink(struct chfs_mount *chmp, 70 struct chfs_vnode_cache *vc) 71{ 72 struct chfs_dirent *fd, *tmpfd; 73 74 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 75 struct chfs_vnode_cache *child_vc; 76 77 if (!fd->vno) 78 continue; 79 80 mutex_enter(&chmp->chm_lock_vnocache); 81 child_vc = chfs_vnode_cache_get(chmp, fd->vno); 82 mutex_exit(&chmp->chm_lock_vnocache); 83 if (!child_vc) { 84 chfs_mark_node_obsolete(chmp, fd->nref); 85 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 86 continue; 87 } 88 if (fd->type == CHT_DIR) { 89 if (child_vc->nlink < 1) 90 child_vc->nlink = 1; 91 92 if (child_vc->pvno) { 93 chfs_err("found a hard link: child dir: %s" 94 ", (vno: %llu) of dir vno: %llu\n", 95 fd->name, (unsigned long long)fd->vno, 96 (unsigned long long)vc->vno); 97 } else { 98 child_vc->pvno = vc->vno; 99 } 100 } 101 child_vc->nlink++; 102 vc->nlink++; 103 } 104} 105 106/* 107 * chfs_build_remove_unlinked vnode 108 */ 109void 110chfs_build_remove_unlinked_vnode(struct chfs_mount *chmp, 111 struct chfs_vnode_cache *vc, 112 struct chfs_dirent_list *unlinked) 113{ 114 struct chfs_node_ref *nref; 115 struct chfs_dirent *fd, *tmpfd; 116 117 dbg("START\n"); 118 dbg("vno: %llu\n", (unsigned long long)vc->vno); 119 120 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 121 nref = vc->dnode; 122 /* The vnode cache is at the end of the data node's chain */ 123 while (nref != (struct chfs_node_ref *)vc) { 124 struct chfs_node_ref *next = nref->nref_next; 125 dbg("mark dnode\n"); 126 chfs_mark_node_obsolete(chmp, nref); 127 nref = next; 128 } 129 vc->dnode = (struct chfs_node_ref *)vc; 130 nref = vc->dirents; 131 /* The vnode cache is at the end of the dirent node's chain */ 132 while (nref != (struct chfs_node_ref *)vc) { 133 struct chfs_node_ref *next = nref->nref_next; 134 dbg("mark dirent\n"); 135 chfs_mark_node_obsolete(chmp, nref); 136 nref = next; 137 } 138 vc->dirents = (struct chfs_node_ref *)vc; 139 if (!TAILQ_EMPTY(&vc->scan_dirents)) { 140 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 141 struct chfs_vnode_cache *child_vc; 142 dbg("dirent dump:\n"); 143 dbg(" ->vno: %llu\n", (unsigned long long)fd->vno); 144 dbg(" ->version: %llu\n", (unsigned long long)fd->version); 145 dbg(" ->nhash: 0x%x\n", fd->nhash); 146 dbg(" ->nsize: %d\n", fd->nsize); 147 dbg(" ->name: %s\n", fd->name); 148 dbg(" ->type: %d\n", fd->type); 149 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 150 151 if (!fd->vno) { 152 chfs_free_dirent(fd); 153 continue; 154 } 155 mutex_enter(&chmp->chm_lock_vnocache); 156 child_vc = chfs_vnode_cache_get(chmp, fd->vno); 157 mutex_exit(&chmp->chm_lock_vnocache); 158 if (!child_vc) { 159 chfs_free_dirent(fd); 160 continue; 161 } 162 /* 163 * Decrease nlink in child. If it is 0, add to unlinked 164 * dirents or just free it otherwise. 165 */ 166 child_vc->nlink--; 167 168 if (!child_vc->nlink) { 169 // XXX HEAD or TAIL? 170 // original code did HEAD, but we could add 171 // it to the TAIL easily with TAILQ. 172 TAILQ_INSERT_TAIL(unlinked, fd, fds); 173 } else { 174 chfs_free_dirent(fd); 175 } 176 } 177 } else { 178 dbg("there are no scan dirents\n"); 179 } 180 181 nref = vc->v; 182 while ((struct chfs_vnode_cache *)nref != vc) { 183 chfs_mark_node_obsolete(chmp, nref); 184 nref = nref->nref_next; 185 } 186 vc->v = (struct chfs_node_ref *)vc; 187 188 mutex_enter(&chmp->chm_lock_vnocache); 189 if (vc->vno != CHFS_ROOTINO) 190 vc->state = VNO_STATE_UNCHECKED; 191 mutex_exit(&chmp->chm_lock_vnocache); 192 dbg("END\n"); 193} 194 195/* 196 * chfs_build_filesystem - build in-memory representation of filesystem 197 * 198 * Step 1: 199 * Scans through the eraseblocks mapped in EBH. 200 * During scan builds up the map of vnodes and directory entries and puts them 201 * into the vnode_cache. 202 * Step 2: 203 * Scans the directory tree and set the nlink in the vnode caches. 204 * Step 3: 205 * Scans vnode caches with nlink = 0 206 */ 207int 208chfs_build_filesystem(struct chfs_mount *chmp) 209{ 210 int i,err = 0; 211 struct chfs_vnode_cache *vc; 212 struct chfs_dirent *fd, *tmpfd; 213 struct chfs_node_ref **nref; 214 struct chfs_dirent_list unlinked; 215 struct chfs_vnode_cache *notregvc; 216 217 TAILQ_INIT(&unlinked); 218 219 mutex_enter(&chmp->chm_lock_mountfields); 220 221 /* Step 1 */ 222 chmp->chm_flags |= CHFS_MP_FLAG_SCANNING; 223 for (i = 0; i < chmp->chm_ebh->peb_nr; i++) { 224 chmp->chm_blocks[i].lnr = i; 225 chmp->chm_blocks[i].free_size = chmp->chm_ebh->eb_size; 226 /* If the LEB is add to free list skip it. */ 227 if (chmp->chm_ebh->lmap[i] < 0) { 228 TAILQ_INSERT_TAIL(&chmp->chm_free_queue, 229 &chmp->chm_blocks[i], queue); 230 chmp->chm_nr_free_blocks++; 231 continue; 232 } 233 234 err = chfs_scan_eraseblock(chmp, &chmp->chm_blocks[i]); 235 switch (err) { 236 case CHFS_BLK_STATE_FREE: 237 chmp->chm_nr_free_blocks++; 238 TAILQ_INSERT_TAIL(&chmp->chm_free_queue, 239 &chmp->chm_blocks[i], queue); 240 break; 241 case CHFS_BLK_STATE_CLEAN: 242 TAILQ_INSERT_TAIL(&chmp->chm_clean_queue, 243 &chmp->chm_blocks[i], queue); 244 break; 245 case CHFS_BLK_STATE_PARTDIRTY: 246 if (chmp->chm_blocks[i].free_size > chmp->chm_wbuf_pagesize && 247 (!chmp->chm_nextblock || 248 chmp->chm_blocks[i].free_size > 249 chmp->chm_nextblock->free_size)) { 250 /* convert the old nextblock's free size to 251 * dirty and put it on a list */ 252 if (chmp->chm_nextblock) { 253 err = chfs_close_eraseblock(chmp, 254 chmp->chm_nextblock); 255 if (err) { 256 mutex_exit(&chmp->chm_lock_mountfields); 257 return err; 258 } 259 } 260 chmp->chm_nextblock = &chmp->chm_blocks[i]; 261 } else { 262 /* convert the scanned block's free size to 263 * dirty and put it on a list */ 264 err = chfs_close_eraseblock(chmp, 265 &chmp->chm_blocks[i]); 266 if (err) { 267 mutex_exit(&chmp->chm_lock_mountfields); 268 return err; 269 } 270 } 271 break; 272 case CHFS_BLK_STATE_ALLDIRTY: 273 /* 274 * The block has a valid EBH header, but it doesn't 275 * contain any valid data. 276 */ 277 TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue, 278 &chmp->chm_blocks[i], queue); 279 chmp->chm_nr_erasable_blocks++; 280 break; 281 default: 282 /* It was an error, unknown state */ 283 break; 284 } 285 286 } 287 chmp->chm_flags &= ~CHFS_MP_FLAG_SCANNING; 288 289 290 //TODO need bad block check (and bad block handling in EBH too!!) 291 /* Now EBH only checks block is bad during its scan operation. 292 * Need check at erase + write + read... 293 */ 294 295 /* Step 2 */ 296 chmp->chm_flags |= CHFS_MP_FLAG_BUILDING; 297 for (i = 0; i < VNODECACHE_SIZE; i++) { 298 vc = chmp->chm_vnocache_hash[i]; 299 while (vc) { 300 dbg("vc->vno: %llu\n", (unsigned long long)vc->vno); 301 if (!TAILQ_EMPTY(&vc->scan_dirents)) 302 chfs_build_set_vnodecache_nlink(chmp, vc); 303 vc = vc->next; 304 } 305 } 306 307 /* Step 3 */ 308 for (i = 0; i < VNODECACHE_SIZE; i++) { 309 vc = chmp->chm_vnocache_hash[i]; 310 while (vc) { 311 if (vc->nlink) { 312 vc = vc->next; 313 continue; 314 } 315 316 chfs_build_remove_unlinked_vnode(chmp, 317 vc, &unlinked); 318 vc = vc->next; 319 } 320 } 321 /* Remove the newly unlinked vnodes. They are on the unlinked list */ 322 TAILQ_FOREACH_SAFE(fd, &unlinked, fds, tmpfd) { 323 TAILQ_REMOVE(&unlinked, fd, fds); 324 mutex_enter(&chmp->chm_lock_vnocache); 325 vc = chfs_vnode_cache_get(chmp, fd->vno); 326 mutex_exit(&chmp->chm_lock_vnocache); 327 if (vc) { 328 chfs_build_remove_unlinked_vnode(chmp, 329 vc, &unlinked); 330 } 331 chfs_free_dirent(fd); 332 } 333 334 chmp->chm_flags &= ~CHFS_MP_FLAG_BUILDING; 335 336 /* Free all dirents */ 337 for (i = 0; i < VNODECACHE_SIZE; i++) { 338 vc = chmp->chm_vnocache_hash[i]; 339 while (vc) { 340 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 341 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 342 if (fd->vno == 0) { 343 nref = &fd->nref; 344 *nref = fd->nref->nref_next; 345 } else if (fd->type == CHT_DIR) { 346 /* set state every non-VREG file's vc */ 347 mutex_enter(&chmp->chm_lock_vnocache); 348 notregvc = chfs_vnode_cache_get(chmp, fd->vno); 349 notregvc->state = VNO_STATE_PRESENT; 350 mutex_exit(&chmp->chm_lock_vnocache); 351 } 352 chfs_free_dirent(fd); 353 } 354 KASSERT(TAILQ_EMPTY(&vc->scan_dirents)); 355 vc = vc->next; 356 } 357 } 358 359 /* Set up chmp->chm_wbuf_ofs for the first write */ 360 if (chmp->chm_nextblock) { 361 dbg("free_size: %d\n", chmp->chm_nextblock->free_size); 362 chmp->chm_wbuf_ofs = chmp->chm_ebh->eb_size - 363 chmp->chm_nextblock->free_size; 364 } else { 365 chmp->chm_wbuf_ofs = 0xffffffff; 366 } 367 mutex_exit(&chmp->chm_lock_mountfields); 368 369 return 0; 370} 371 372