1 /* $NetBSD: chfs_build.c,v 1.5 2012/10/19 12:44:39 ttoth 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 */ 41 void 42 chfs_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 */ 68 void 69 chfs_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 */ 109 void 110 chfs_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 */ 207 int 208 chfs_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 return err; 257 } 258 chmp->chm_nextblock = &chmp->chm_blocks[i]; 259 } else { 260 /* convert the scanned block's free size to 261 * dirty and put it on a list */ 262 err = chfs_close_eraseblock(chmp, 263 &chmp->chm_blocks[i]); 264 if (err) 265 return err; 266 } 267 break; 268 case CHFS_BLK_STATE_ALLDIRTY: 269 /* 270 * The block has a valid EBH header, but it doesn't 271 * contain any valid data. 272 */ 273 TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue, 274 &chmp->chm_blocks[i], queue); 275 chmp->chm_nr_erasable_blocks++; 276 break; 277 default: 278 /* It was an error, unknown state */ 279 break; 280 } 281 282 } 283 chmp->chm_flags &= ~CHFS_MP_FLAG_SCANNING; 284 285 286 //TODO need bad block check (and bad block handling in EBH too!!) 287 /* Now EBH only checks block is bad during its scan operation. 288 * Need check at erase + write + read... 289 */ 290 291 /* Step 2 */ 292 chmp->chm_flags |= CHFS_MP_FLAG_BUILDING; 293 for (i = 0; i < VNODECACHE_SIZE; i++) { 294 vc = chmp->chm_vnocache_hash[i]; 295 while (vc) { 296 dbg("vc->vno: %llu\n", (unsigned long long)vc->vno); 297 if (!TAILQ_EMPTY(&vc->scan_dirents)) 298 chfs_build_set_vnodecache_nlink(chmp, vc); 299 vc = vc->next; 300 } 301 } 302 303 /* Step 3 */ 304 for (i = 0; i < VNODECACHE_SIZE; i++) { 305 vc = chmp->chm_vnocache_hash[i]; 306 while (vc) { 307 if (vc->nlink) { 308 vc = vc->next; 309 continue; 310 } 311 312 chfs_build_remove_unlinked_vnode(chmp, 313 vc, &unlinked); 314 vc = vc->next; 315 } 316 } 317 /* Remove the newly unlinked vnodes. They are on the unlinked list */ 318 TAILQ_FOREACH_SAFE(fd, &unlinked, fds, tmpfd) { 319 TAILQ_REMOVE(&unlinked, fd, fds); 320 mutex_enter(&chmp->chm_lock_vnocache); 321 vc = chfs_vnode_cache_get(chmp, fd->vno); 322 mutex_exit(&chmp->chm_lock_vnocache); 323 if (vc) { 324 chfs_build_remove_unlinked_vnode(chmp, 325 vc, &unlinked); 326 } 327 chfs_free_dirent(fd); 328 } 329 330 chmp->chm_flags &= ~CHFS_MP_FLAG_BUILDING; 331 332 /* Free all dirents */ 333 for (i = 0; i < VNODECACHE_SIZE; i++) { 334 vc = chmp->chm_vnocache_hash[i]; 335 while (vc) { 336 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 337 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 338 if (fd->vno == 0) { 339 nref = &fd->nref; 340 *nref = fd->nref->nref_next; 341 } else if (fd->type == CHT_DIR) { 342 /* set state every non-VREG file's vc */ 343 mutex_enter(&chmp->chm_lock_vnocache); 344 notregvc = chfs_vnode_cache_get(chmp, fd->vno); 345 notregvc->state = VNO_STATE_PRESENT; 346 mutex_exit(&chmp->chm_lock_vnocache); 347 } 348 chfs_free_dirent(fd); 349 } 350 KASSERT(TAILQ_EMPTY(&vc->scan_dirents)); 351 vc = vc->next; 352 } 353 } 354 355 /* Set up chmp->chm_wbuf_ofs for the first write */ 356 if (chmp->chm_nextblock) { 357 dbg("free_size: %d\n", chmp->chm_nextblock->free_size); 358 chmp->chm_wbuf_ofs = chmp->chm_ebh->eb_size - 359 chmp->chm_nextblock->free_size; 360 } else { 361 chmp->chm_wbuf_ofs = 0xffffffff; 362 } 363 mutex_exit(&chmp->chm_lock_mountfields); 364 365 return 0; 366 } 367 368