chfs_build.c revision 1.1
1 /* $NetBSD: chfs_build.c,v 1.1 2011/11/24 15:51:31 ahoka 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 //#include </root/xipffs/netbsd.chfs/chfs.h> 35 36 37 void 38 chfs_calc_trigger_levels(struct chfs_mount *chmp) 39 { 40 uint32_t size; 41 42 chmp->chm_resv_blocks_deletion = 2; 43 44 size = chmp->chm_ebh->flash_size / 50; //2% of flash size 45 size += chmp->chm_ebh->peb_nr * 100; 46 size += chmp->chm_ebh->eb_size - 1; 47 48 chmp->chm_resv_blocks_write = 49 chmp->chm_resv_blocks_deletion + (size / chmp->chm_ebh->eb_size); 50 chmp->chm_resv_blocks_gctrigger = chmp->chm_resv_blocks_write + 1; 51 chmp->chm_resv_blocks_gcmerge = chmp->chm_resv_blocks_deletion + 1; 52 chmp->chm_vdirty_blocks_gctrigger = chmp->chm_resv_blocks_gctrigger * 10; 53 54 chmp->chm_nospc_dirty = 55 chmp->chm_ebh->eb_size + (chmp->chm_ebh->flash_size / 100); 56 } 57 58 59 /** 60 * chfs_build_set_vnodecache_nlink - set pvno and nlink in vnodecaches 61 * @chmp: CHFS main descriptor structure 62 * @vc: vnode cache 63 * This function travels @vc's directory entries and sets the pvno and nlink 64 * attribute of the vnode where the dirent's vno points. 65 */ 66 void 67 chfs_build_set_vnodecache_nlink(struct chfs_mount *chmp, 68 struct chfs_vnode_cache *vc) 69 { 70 struct chfs_dirent *fd; 71 //dbg("set nlink\n"); 72 73 // for (fd = vc->scan_dirents; fd; fd = fd->next) { 74 TAILQ_FOREACH(fd, &vc->scan_dirents, fds) { 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 continue; 86 } 87 if (fd->type == VDIR) { 88 if (child_vc->nlink < 1) 89 child_vc->nlink = 1; 90 91 if (child_vc->pvno) { 92 chfs_err("found a hard link: child dir: %s" 93 ", (vno: %llu) of dir vno: %llu\n", 94 fd->name, fd->vno, vc->vno); 95 } else { 96 //dbg("child_vc->pvno = 97 // vc->vno; pvno = %d\n", child_vc->pvno); 98 child_vc->pvno = vc->vno; 99 } 100 } 101 child_vc->nlink++; 102 //dbg("child_vc->nlink++;\n"); 103 //child_vc->nlink++; 104 vc->nlink++; 105 } 106 } 107 108 /** 109 * chfs_build_remove_unlinked vnode 110 */ 111 /* static */ 112 void 113 chfs_build_remove_unlinked_vnode(struct chfs_mount *chmp, 114 struct chfs_vnode_cache *vc, 115 // struct chfs_dirent **unlinked) 116 struct chfs_dirent_list *unlinked) 117 { 118 struct chfs_node_ref *nref; 119 struct chfs_dirent *fd, *tmpfd; 120 121 dbg("START\n"); 122 dbg("vno: %llu\n", vc->vno); 123 124 nref = vc->dnode; 125 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 126 // The vnode cache is at the end of the data node's chain 127 while (nref != (struct chfs_node_ref *)vc) { 128 struct chfs_node_ref *next = nref->nref_next; 129 dbg("mark dnode\n"); 130 chfs_mark_node_obsolete(chmp, nref); 131 nref = next; 132 } 133 nref = vc->dirents; 134 // The vnode cache is at the end of the dirent node's chain 135 while (nref != (struct chfs_node_ref *)vc) { 136 struct chfs_node_ref *next = nref->nref_next; 137 dbg("mark dirent\n"); 138 chfs_mark_node_obsolete(chmp, nref); 139 nref = next; 140 } 141 if (!TAILQ_EMPTY(&vc->scan_dirents)) { 142 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 143 // while (vc->scan_dirents) { 144 struct chfs_vnode_cache *child_vc; 145 // fd = vc->scan_dirents; 146 dbg("dirent dump:\n"); 147 dbg(" ->vno: %llu\n", fd->vno); 148 dbg(" ->version: %llu\n", fd->version); 149 dbg(" ->nhash: 0x%x\n", fd->nhash); 150 dbg(" ->nsize: %d\n", fd->nsize); 151 dbg(" ->name: %s\n", fd->name); 152 dbg(" ->type: %d\n", fd->type); 153 // vc->scan_dirents = fd->next; 154 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 155 156 if (!fd->vno) { 157 chfs_free_dirent(fd); 158 continue; 159 } 160 mutex_enter(&chmp->chm_lock_vnocache); 161 child_vc = chfs_vnode_cache_get(chmp, fd->vno); 162 mutex_exit(&chmp->chm_lock_vnocache); 163 if (!child_vc) { 164 chfs_free_dirent(fd); 165 continue; 166 } 167 /** 168 * Decrease nlink in child. If it is 0, add to unlinked 169 * dirents or just free it otherwise. 170 */ 171 child_vc->nlink--; 172 173 if (!child_vc->nlink) { 174 //dbg("nlink is 0\n"); 175 // fd->next = *unlinked; 176 // *unlinked = fd; 177 // XXX HEAD or TAIL? 178 // original code did HEAD, but we could add 179 // it to the TAIL easily with TAILQ. 180 TAILQ_INSERT_TAIL(unlinked, fd, fds); 181 } else { 182 chfs_free_dirent(fd); 183 } 184 } 185 } else { 186 dbg("there are no scan dirents\n"); 187 } 188 189 nref = vc->v; 190 while ((struct chfs_vnode_cache *)nref != vc) { 191 if (!CHFS_REF_OBSOLETE(nref)) 192 chfs_mark_node_obsolete(chmp, nref); 193 nref = nref->nref_next; 194 } 195 196 mutex_enter(&chmp->chm_lock_vnocache); 197 if (vc->vno != CHFS_ROOTINO) 198 chfs_vnode_cache_set_state(chmp, vc, VNO_STATE_UNCHECKED); 199 mutex_exit(&chmp->chm_lock_vnocache); 200 dbg("END\n"); 201 } 202 203 /** 204 * chfs_build_filesystem - build in-memory representation of filesystem 205 * @chmp: super block information 206 * 207 * Step 1: 208 * This function scans through the eraseblocks mapped in EBH. 209 * During scan builds up the map of vnodes and directory entries and puts them 210 * into the vnode_cache. 211 * Step 2: 212 * Scans the directory tree and set the nlink in the vnode caches. 213 * Step 3: 214 * Scans vnode caches with nlink = 0 215 */ 216 int 217 chfs_build_filesystem(struct chfs_mount *chmp) 218 { 219 int i,err = 0; 220 struct chfs_vnode_cache *vc; 221 struct chfs_dirent *fd, *tmpfd; 222 // struct chfs_dirent *unlinked = NULL; 223 struct chfs_node_ref **nref; 224 struct chfs_dirent_list unlinked; 225 struct chfs_vnode_cache *notregvc; 226 227 TAILQ_INIT(&unlinked); 228 229 mutex_enter(&chmp->chm_lock_mountfields); 230 231 /** 232 * Step 1 233 */ 234 chmp->chm_flags |= CHFS_MP_FLAG_SCANNING; 235 for (i = 0; i < chmp->chm_ebh->peb_nr; i++) { 236 //dbg("processing block: %d\n", i); 237 chmp->chm_blocks[i].lnr = i; 238 chmp->chm_blocks[i].free_size = chmp->chm_ebh->eb_size; 239 //If the LEB is add to free list skip it. 240 if (chmp->chm_ebh->lmap[i] < 0) { 241 //dbg("block %d is unmapped\n", i); 242 TAILQ_INSERT_TAIL(&chmp->chm_free_queue, 243 &chmp->chm_blocks[i], queue); 244 chmp->chm_nr_free_blocks++; 245 continue; 246 } 247 248 err = chfs_scan_eraseblock(chmp, &chmp->chm_blocks[i]); 249 switch (err) { 250 case CHFS_BLK_STATE_FREE: 251 chmp->chm_nr_free_blocks++; 252 TAILQ_INSERT_TAIL(&chmp->chm_free_queue, 253 &chmp->chm_blocks[i], queue); 254 break; 255 case CHFS_BLK_STATE_CLEAN: 256 TAILQ_INSERT_TAIL(&chmp->chm_clean_queue, 257 &chmp->chm_blocks[i], queue); 258 break; 259 case CHFS_BLK_STATE_PARTDIRTY: 260 //dbg("free size: %d\n", chmp->chm_blocks[i].free_size); 261 if (chmp->chm_blocks[i].free_size > chmp->chm_wbuf_pagesize && 262 (!chmp->chm_nextblock || 263 chmp->chm_blocks[i].free_size > 264 chmp->chm_nextblock->free_size)) { 265 /* convert the old nextblock's free size to 266 * dirty and put it on a list */ 267 if (chmp->chm_nextblock) { 268 err = chfs_close_eraseblock(chmp, 269 chmp->chm_nextblock); 270 if (err) 271 return err; 272 } 273 chmp->chm_nextblock = &chmp->chm_blocks[i]; 274 } else { 275 /* convert the scanned block's free size to 276 * dirty and put it on a list */ 277 err = chfs_close_eraseblock(chmp, 278 &chmp->chm_blocks[i]); 279 if (err) 280 return err; 281 } 282 break; 283 case CHFS_BLK_STATE_ALLDIRTY: 284 /* 285 * The block has a valid EBH header, but it doesn't 286 * contain any valid data. 287 */ 288 TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue, 289 &chmp->chm_blocks[i], queue); 290 chmp->chm_nr_erasable_blocks++; 291 break; 292 default: 293 /* It was an error, unknown state */ 294 break; 295 } 296 297 } 298 chmp->chm_flags &= ~CHFS_MP_FLAG_SCANNING; 299 300 301 //TODO need bad block check (and bad block handling in EBH too!!) 302 /* Now EBH only checks block is bad during its scan operation. 303 * Need check at erase + write + read... 304 */ 305 306 /** 307 * Step 2 308 */ 309 chmp->chm_flags |= CHFS_MP_FLAG_BUILDING; 310 for (i = 0; i < VNODECACHE_SIZE; i++) { 311 vc = chmp->chm_vnocache_hash[i]; 312 while (vc) { 313 dbg("vc->vno: %llu\n", vc->vno); 314 if (!TAILQ_EMPTY(&vc->scan_dirents)) 315 chfs_build_set_vnodecache_nlink(chmp, vc); 316 vc = vc->next; 317 } 318 } 319 320 /** 321 * Step 3 322 * Scan for vnodes with 0 nlink. 323 */ 324 for (i = 0; i < VNODECACHE_SIZE; i++) { 325 vc = chmp->chm_vnocache_hash[i]; 326 while (vc) { 327 if (vc->nlink) { 328 vc = vc->next; 329 continue; 330 } 331 332 //dbg("remove unlinked start i: %d\n", i); 333 chfs_build_remove_unlinked_vnode(chmp, 334 vc, &unlinked); 335 //dbg("remove unlinked end\n"); 336 vc = vc->next; 337 } 338 } 339 /* Remove the newly unlinked vnodes. They are on the unlinked list */ 340 TAILQ_FOREACH_SAFE(fd, &unlinked, fds, tmpfd) { 341 // while (unlinked) { 342 // fd = unlinked; 343 // unlinked = fd->next; 344 TAILQ_REMOVE(&unlinked, fd, fds); 345 mutex_enter(&chmp->chm_lock_vnocache); 346 vc = chfs_vnode_cache_get(chmp, fd->vno); 347 mutex_exit(&chmp->chm_lock_vnocache); 348 if (vc) { 349 chfs_build_remove_unlinked_vnode(chmp, 350 vc, &unlinked); 351 } 352 chfs_free_dirent(fd); 353 } 354 355 chmp->chm_flags &= ~CHFS_MP_FLAG_BUILDING; 356 357 /* Free all dirents */ 358 for (i = 0; i < VNODECACHE_SIZE; i++) { 359 vc = chmp->chm_vnocache_hash[i]; 360 while (vc) { 361 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) { 362 // while (vc->scan_dirents) { 363 // fd = vc->scan_dirents; 364 // vc->scan_dirents = fd->next; 365 TAILQ_REMOVE(&vc->scan_dirents, fd, fds); 366 if (fd->vno == 0) { 367 //for (nref = &vc->dirents; 368 // *nref != fd->nref; 369 // nref = &((*nref)->next)); 370 371 nref = &fd->nref; 372 *nref = fd->nref->nref_next; 373 //fd->nref->nref_next = NULL; 374 } else if (fd->type == VDIR) { 375 //set state every non-VREG file's vc 376 mutex_enter(&chmp->chm_lock_vnocache); 377 notregvc = 378 chfs_vnode_cache_get(chmp, 379 fd->vno); 380 chfs_vnode_cache_set_state(chmp, 381 notregvc, VNO_STATE_PRESENT); 382 mutex_exit(&chmp->chm_lock_vnocache); 383 } 384 chfs_free_dirent(fd); 385 } 386 // vc->scan_dirents = NULL; 387 KASSERT(TAILQ_EMPTY(&vc->scan_dirents)); 388 vc = vc->next; 389 } 390 } 391 392 //Set up chmp->chm_wbuf_ofs for the first write 393 if (chmp->chm_nextblock) { 394 dbg("free_size: %d\n", chmp->chm_nextblock->free_size); 395 chmp->chm_wbuf_ofs = chmp->chm_ebh->eb_size - 396 chmp->chm_nextblock->free_size; 397 } else { 398 chmp->chm_wbuf_ofs = 0xffffffff; 399 } 400 mutex_exit(&chmp->chm_lock_mountfields); 401 402 return 0; 403 } 404 405
Indexes created Sat Sep 27 14:09:57 GMT 2025