chfs_gc.c revision 1.1
1 /* $NetBSD: chfs_gc.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 * Copyright (c) 2010 Tamas Toth <ttoth (at) inf.u-szeged.hu> 7 * Copyright (c) 2010 Adam Hoka <ahoka (at) NetBSD.org> 8 * All rights reserved. 9 * 10 * This code is derived from software contributed to The NetBSD Foundation 11 * by the Department of Software Engineering, University of Szeged, Hungary 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include "chfs.h" 36 37 void chfs_gc_release_inode(struct chfs_mount *, 38 struct chfs_inode *); 39 struct chfs_inode *chfs_gc_fetch_inode(struct chfs_mount *, 40 ino_t, uint32_t); 41 int chfs_check(struct chfs_mount *, struct chfs_vnode_cache *); 42 void chfs_clear_inode(struct chfs_mount *, struct chfs_inode *); 43 44 45 struct chfs_eraseblock *find_gc_block(struct chfs_mount *); 46 int chfs_gcollect_pristine(struct chfs_mount *, 47 struct chfs_eraseblock *, 48 struct chfs_vnode_cache *, struct chfs_node_ref *); 49 int chfs_gcollect_live(struct chfs_mount *, 50 struct chfs_eraseblock *, struct chfs_node_ref *, 51 struct chfs_inode *); 52 int chfs_gcollect_vnode(struct chfs_mount *, struct chfs_inode *); 53 int chfs_gcollect_dirent(struct chfs_mount *, 54 struct chfs_eraseblock *, struct chfs_inode *, 55 struct chfs_dirent *); 56 int chfs_gcollect_deletion_dirent(struct chfs_mount *, 57 struct chfs_eraseblock *, struct chfs_inode *, 58 struct chfs_dirent *); 59 int chfs_gcollect_dnode(struct chfs_mount *, 60 struct chfs_eraseblock *, struct chfs_inode *, 61 struct chfs_full_dnode *, uint32_t, uint32_t); 62 63 /* must be called with chm_lock_mountfields held */ 64 void 65 chfs_gc_trigger(struct chfs_mount *chmp) 66 { 67 struct garbage_collector_thread *gc = &chmp->chm_gc_thread; 68 69 //mutex_enter(&chmp->chm_lock_sizes); 70 if (gc->gcth_running && 71 chfs_gc_thread_should_wake(chmp)) { 72 cv_signal(&gc->gcth_wakeup); 73 } 74 //mutex_exit(&chmp->chm_lock_sizes); 75 } 76 77 78 void 79 chfs_gc_thread(void *data) 80 { 81 struct chfs_mount *chmp = data; 82 struct garbage_collector_thread *gc = &chmp->chm_gc_thread; 83 84 dbg_gc("[GC THREAD] thread started\n"); 85 86 mutex_enter(&chmp->chm_lock_mountfields); 87 while (gc->gcth_running) { 88 /* we must call chfs_gc_thread_should_wake with chm_lock_mountfields 89 * held, which is a bit awkwardly done here, but we cant relly 90 * do it otherway with the current design... 91 */ 92 if (chfs_gc_thread_should_wake(chmp)) { 93 // mutex_exit(&chmp->chm_lock_mountfields); 94 if (chfs_gcollect_pass(chmp) == ENOSPC) { 95 dbg_gc("No space for garbage collection\n"); 96 panic("No space for garbage collection\n"); 97 /* XXX why break here? i have added a panic 98 * here to see if it gets triggered -ahoka 99 */ 100 break; 101 } 102 /* XXX gcollect_pass drops the mutex */ 103 mutex_enter(&chmp->chm_lock_mountfields); 104 } 105 106 cv_timedwait_sig(&gc->gcth_wakeup, 107 &chmp->chm_lock_mountfields, mstohz(100)); 108 } 109 mutex_exit(&chmp->chm_lock_mountfields); 110 111 dbg_gc("[GC THREAD] thread stopped\n"); 112 kthread_exit(0); 113 } 114 115 void 116 chfs_gc_thread_start(struct chfs_mount *chmp) 117 { 118 struct garbage_collector_thread *gc = &chmp->chm_gc_thread; 119 120 cv_init(&gc->gcth_wakeup, "chfsgccv"); 121 122 gc->gcth_running = true; 123 kthread_create(PRI_NONE, /*KTHREAD_MPSAFE |*/ KTHREAD_MUSTJOIN, 124 NULL, chfs_gc_thread, chmp, &gc->gcth_thread, 125 "chfsgcth"); 126 } 127 128 void 129 chfs_gc_thread_stop(struct chfs_mount *chmp) 130 { 131 struct garbage_collector_thread *gc = &chmp->chm_gc_thread; 132 133 /* check if it is actually running. if not, do nothing */ 134 if (gc->gcth_running) { 135 gc->gcth_running = false; 136 } else { 137 return; 138 } 139 cv_signal(&gc->gcth_wakeup); 140 dbg_gc("[GC THREAD] stop signal sent\n"); 141 142 kthread_join(gc->gcth_thread); 143 #ifdef BROKEN_KTH_JOIN 144 kpause("chfsthjoin", false, mstohz(1000), NULL); 145 #endif 146 147 cv_destroy(&gc->gcth_wakeup); 148 } 149 150 /* must be called with chm_lock_mountfields held */ 151 int 152 chfs_gc_thread_should_wake(struct chfs_mount *chmp) 153 { 154 int nr_very_dirty = 0; 155 struct chfs_eraseblock *cheb; 156 uint32_t dirty; 157 158 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 159 160 if (!TAILQ_EMPTY(&chmp->chm_erase_pending_queue)) { 161 dbg_gc("erase_pending\n"); 162 return 1; 163 } 164 165 if (chmp->chm_unchecked_size) { 166 dbg_gc("unchecked\n"); 167 return 1; 168 } 169 170 dirty = chmp->chm_dirty_size - chmp->chm_nr_erasable_blocks * 171 chmp->chm_ebh->eb_size; 172 173 if (chmp->chm_nr_free_blocks + chmp->chm_nr_erasable_blocks < 174 chmp->chm_resv_blocks_gctrigger && (dirty > chmp->chm_nospc_dirty)) { 175 dbg_gc("free: %d + erasable: %d < resv: %d\n", 176 chmp->chm_nr_free_blocks, chmp->chm_nr_erasable_blocks, 177 chmp->chm_resv_blocks_gctrigger); 178 dbg_gc("dirty: %d > nospc_dirty: %d\n", 179 dirty, chmp->chm_nospc_dirty); 180 181 return 1; 182 } 183 184 TAILQ_FOREACH(cheb, &chmp->chm_very_dirty_queue, queue) { 185 nr_very_dirty++; 186 if (nr_very_dirty == chmp->chm_vdirty_blocks_gctrigger) { 187 dbg_gc("nr_very_dirty\n"); 188 return 1; 189 } 190 } 191 192 return 0; 193 } 194 195 void 196 chfs_gc_release_inode(struct chfs_mount *chmp, 197 struct chfs_inode *ip) 198 { 199 dbg_gc("release inode\n"); 200 //mutex_exit(&ip->inode_lock); 201 //vput(ITOV(ip)); 202 } 203 204 struct chfs_inode * 205 chfs_gc_fetch_inode(struct chfs_mount *chmp, ino_t vno, 206 uint32_t unlinked) 207 { 208 struct vnode *vp = NULL; 209 struct chfs_vnode_cache *vc; 210 struct chfs_inode *ip; 211 dbg_gc("fetch inode %llu\n", vno); 212 213 if (unlinked) { 214 dbg_gc("unlinked\n"); 215 vp = chfs_vnode_lookup(chmp, vno); 216 if (!vp) { 217 mutex_enter(&chmp->chm_lock_vnocache); 218 vc = chfs_vnode_cache_get(chmp, vno); 219 if (!vc) { 220 mutex_exit(&chmp->chm_lock_vnocache); 221 return NULL; 222 } 223 if (vc->state != VNO_STATE_CHECKEDABSENT) { 224 //sleep_on_spinunlock(&chmp->chm_lock_vnocache); 225 mutex_exit(&chmp->chm_lock_vnocache); 226 /* XXX why do we need the delay here?! */ 227 // kpause("chvncabs", true, mstohz(50), NULL); 228 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 229 cv_timedwait_sig( 230 &chmp->chm_gc_thread.gcth_wakeup, 231 &chmp->chm_lock_mountfields, mstohz(50)); 232 233 // KASSERT(!mutex_owned(&chmp->chm_lock_vnocache)); 234 } else { 235 mutex_exit(&chmp->chm_lock_vnocache); 236 } 237 return NULL; 238 } 239 } else { 240 dbg_gc("vnode lookup\n"); 241 vp = chfs_vnode_lookup(chmp, vno); 242 //VFS_VGET(chmp->chm_fsmp, vno, &vp); 243 } 244 dbg_gc("vp to ip\n"); 245 ip = VTOI(vp); 246 KASSERT(ip); 247 //mutex_enter(&ip->inode_lock); 248 249 return ip; 250 } 251 252 extern rb_tree_ops_t frag_rbtree_ops; 253 254 int 255 chfs_check(struct chfs_mount *chmp, struct chfs_vnode_cache *chvc) 256 { 257 struct chfs_inode *ip; 258 struct vnode *vp; 259 int ret; 260 261 ip = pool_get(&chfs_inode_pool, PR_WAITOK); 262 if (!ip) { 263 return ENOMEM; 264 } 265 266 vp = kmem_zalloc(sizeof(struct vnode), KM_SLEEP); 267 268 ip->chvc = chvc; 269 ip->vp = vp; 270 271 vp->v_data = ip; 272 273 rb_tree_init(&ip->fragtree, &frag_rbtree_ops); 274 TAILQ_INIT(&ip->dents); 275 276 ret = chfs_read_inode_internal(chmp, ip); 277 if (!ret) { 278 chfs_clear_inode(chmp, ip); 279 } 280 281 pool_put(&chfs_inode_pool, ip); 282 283 return ret; 284 } 285 286 void 287 chfs_clear_inode(struct chfs_mount *chmp, struct chfs_inode *ip) 288 { 289 struct chfs_dirent *fd, *tmpfd; 290 struct chfs_vnode_cache *chvc; 291 292 293 /* XXX not sure if this is the correct locking */ 294 // mutex_enter(&chmp->chm_lock_vnocache); 295 chvc = ip->chvc; 296 /* shouldnt this be: */ 297 //bool deleted = (chvc && !(chvc->pvno || chvc->nlink)); 298 int deleted = (chvc && !(chvc->pvno | chvc->nlink)); 299 300 if (chvc && chvc->state != VNO_STATE_CHECKING) { 301 // chfs_vnode_cache_state_set(chmp, chvc, VNO_STATE_CLEARING); 302 chvc->state = VNO_STATE_CLEARING; 303 } 304 305 if (chvc->v && ((struct chfs_vnode_cache *)chvc->v != chvc)) { 306 if (deleted) 307 chfs_mark_node_obsolete(chmp, chvc->v); 308 //chfs_free_refblock(chvc->v); 309 } 310 // mutex_enter(&chmp->chm_lock_vnocache); 311 312 chfs_kill_fragtree(&ip->fragtree); 313 /* 314 fd = TAILQ_FIRST(&ip->dents); 315 while (fd) { 316 TAILQ_REMOVE(&ip->dents, fd, fds); 317 chfs_free_dirent(fd); 318 fd = TAILQ_FIRST(&ip->dents); 319 } 320 */ 321 322 TAILQ_FOREACH_SAFE(fd, &ip->dents, fds, tmpfd) { 323 chfs_free_dirent(fd); 324 } 325 326 if (chvc && chvc->state == VNO_STATE_CHECKING) { 327 chfs_vnode_cache_set_state(chmp, 328 chvc, VNO_STATE_CHECKEDABSENT); 329 if ((struct chfs_vnode_cache *)chvc->v == chvc && 330 (struct chfs_vnode_cache *)chvc->dirents == chvc && 331 (struct chfs_vnode_cache *)chvc->dnode == chvc) 332 chfs_vnode_cache_remove(chmp, chvc); 333 } 334 335 } 336 337 struct chfs_eraseblock * 338 find_gc_block(struct chfs_mount *chmp) 339 { 340 struct chfs_eraseblock *ret; 341 struct chfs_eraseblock_queue *nextqueue; 342 343 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 344 345 struct timespec now; 346 vfs_timestamp(&now); 347 348 int n = now.tv_nsec % 128; 349 350 //dbg_gc("n = %d\n", n); 351 again: 352 /* if (!TAILQ_EMPTY(&chmp->chm_bad_used_queue) && chmp->chm_nr_free_blocks > chmp->chm_nr_resv_blocks_gcbad) { 353 dbg_gc("Picking block from bad_used_queue to GC next\n"); 354 nextqueue = &chmp->chm_bad_used_queue; 355 } else */if (n<50 && !TAILQ_EMPTY(&chmp->chm_erase_pending_queue)) { 356 dbg_gc("Picking block from erase_pending_queue to GC next\n"); 357 nextqueue = &chmp->chm_erase_pending_queue; 358 } else if (n<110 && !TAILQ_EMPTY(&chmp->chm_very_dirty_queue) ) { 359 dbg_gc("Picking block from very_dirty_queue to GC next\n"); 360 nextqueue = &chmp->chm_very_dirty_queue; 361 } else if (n<126 && !TAILQ_EMPTY(&chmp->chm_dirty_queue) ) { 362 dbg_gc("Picking block from dirty_queue to GC next\n"); 363 nextqueue = &chmp->chm_dirty_queue; 364 } else if (!TAILQ_EMPTY(&chmp->chm_clean_queue)) { 365 dbg_gc("Picking block from clean_queue to GC next\n"); 366 nextqueue = &chmp->chm_clean_queue; 367 } else if (!TAILQ_EMPTY(&chmp->chm_dirty_queue)) { 368 dbg_gc("Picking block from dirty_queue to GC next" 369 " (clean_queue was empty)\n"); 370 nextqueue = &chmp->chm_dirty_queue; 371 } else if (!TAILQ_EMPTY(&chmp->chm_very_dirty_queue)) { 372 dbg_gc("Picking block from very_dirty_queue to GC next" 373 " (clean_queue and dirty_queue were empty)\n"); 374 nextqueue = &chmp->chm_very_dirty_queue; 375 } else if (!TAILQ_EMPTY(&chmp->chm_erase_pending_queue)) { 376 dbg_gc("Picking block from erase_pending_queue to GC next" 377 " (clean_queue and {very_,}dirty_queue were empty)\n"); 378 nextqueue = &chmp->chm_erase_pending_queue; 379 } else if (!TAILQ_EMPTY(&chmp->chm_erasable_pending_wbuf_queue)) { 380 dbg_gc("Synching wbuf in order to reuse " 381 "erasable_pendig_wbuf_queue blocks\n"); 382 rw_enter(&chmp->chm_lock_wbuf, RW_WRITER); 383 chfs_flush_pending_wbuf(chmp); 384 rw_exit(&chmp->chm_lock_wbuf); 385 goto again; 386 } else { 387 dbg_gc("CHFS: no clean, dirty _or_ erasable" 388 " blocks to GC from! Where are they all?\n"); 389 return NULL; 390 } 391 392 ret = TAILQ_FIRST(nextqueue); 393 if (chmp->chm_nextblock) { 394 dbg_gc("nextblock num: %u - gcblock num: %u\n", 395 chmp->chm_nextblock->lnr, ret->lnr); 396 if (ret == chmp->chm_nextblock) 397 goto again; 398 //KASSERT(ret != chmp->chm_nextblock); 399 //dbg_gc("first node lnr: %u ofs: %u\n", ret->first_node->lnr, ret->first_node->offset); 400 //dbg_gc("last node lnr: %u ofs: %u\n", ret->last_node->lnr, ret->last_node->offset); 401 } 402 TAILQ_REMOVE(nextqueue, ret, queue); 403 chmp->chm_gcblock = ret; 404 ret->gc_node = ret->first_node; 405 406 if (!ret->gc_node) { 407 dbg_gc("Oops! ret->gc_node at LEB: %u is NULL\n", ret->lnr); 408 panic("CHFS BUG - one LEB's gc_node is NULL\n"); 409 } 410 411 /* TODO wasted size? */ 412 return ret; 413 } 414 415 416 int 417 chfs_gcollect_pass(struct chfs_mount *chmp) 418 { 419 struct chfs_vnode_cache *vc; 420 struct chfs_eraseblock *eb; 421 struct chfs_node_ref *nref; 422 uint32_t gcblock_dirty; 423 struct chfs_inode *ip; 424 ino_t vno, pvno; 425 uint32_t nlink; 426 int ret = 0; 427 428 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 429 430 // mutex_enter(&chmp->chm_lock_mountfields); 431 for (;;) { 432 mutex_enter(&chmp->chm_lock_sizes); 433 434 dbg_gc("unchecked size == %u\n", chmp->chm_unchecked_size); 435 if (!chmp->chm_unchecked_size) 436 break; 437 438 if (chmp->chm_checked_vno > chmp->chm_max_vno) { 439 mutex_exit(&chmp->chm_lock_sizes); 440 mutex_exit(&chmp->chm_lock_mountfields); 441 dbg_gc("checked_vno (#%llu) > max_vno (#%llu)\n", 442 chmp->chm_checked_vno, chmp->chm_max_vno); 443 return ENOSPC; 444 } 445 446 mutex_exit(&chmp->chm_lock_sizes); 447 448 mutex_enter(&chmp->chm_lock_vnocache); 449 dbg_gc("checking vno #%llu\n", chmp->chm_checked_vno); 450 dbg_gc("get vnode cache\n"); 451 vc = chfs_vnode_cache_get(chmp, chmp->chm_checked_vno++); 452 453 if (!vc) { 454 dbg_gc("!vc\n"); 455 mutex_exit(&chmp->chm_lock_vnocache); 456 continue; 457 } 458 459 if ((vc->pvno | vc->nlink) == 0) { 460 dbg_gc("(pvno | nlink) == 0\n"); 461 mutex_exit(&chmp->chm_lock_vnocache); 462 continue; 463 } 464 465 dbg_gc("switch\n"); 466 switch (vc->state) { 467 case VNO_STATE_CHECKEDABSENT: 468 case VNO_STATE_PRESENT: 469 mutex_exit(&chmp->chm_lock_vnocache); 470 continue; 471 472 case VNO_STATE_GC: 473 case VNO_STATE_CHECKING: 474 mutex_exit(&chmp->chm_lock_vnocache); 475 mutex_exit(&chmp->chm_lock_mountfields); 476 dbg_gc("VNO_STATE GC or CHECKING\n"); 477 panic("CHFS BUG - vc state gc or checking\n"); 478 479 case VNO_STATE_READING: 480 chmp->chm_checked_vno--; 481 mutex_exit(&chmp->chm_lock_vnocache); 482 /* XXX why do we need the delay here?! */ 483 kpause("chvncrea", true, mstohz(50), NULL); 484 485 // sleep_on_spinunlock(&chmp->chm_lock_vnocache); 486 // KASSERT(!mutex_owned(&chmp->chm_lock_vnocache)); 487 mutex_exit(&chmp->chm_lock_mountfields); 488 return 0; 489 490 default: 491 mutex_exit(&chmp->chm_lock_vnocache); 492 mutex_exit(&chmp->chm_lock_mountfields); 493 dbg_gc("default\n"); 494 panic("CHFS BUG - vc state is other what we" 495 " checked\n"); 496 497 case VNO_STATE_UNCHECKED: 498 ; 499 } 500 501 chfs_vnode_cache_set_state(chmp, vc, VNO_STATE_CHECKING); 502 503 /* XXX check if this is too heavy to call under 504 * chm_lock_vnocache 505 */ 506 ret = chfs_check(chmp, vc); 507 dbg_gc("set state\n"); 508 chfs_vnode_cache_set_state(chmp, 509 vc, VNO_STATE_CHECKEDABSENT); 510 511 mutex_exit(&chmp->chm_lock_vnocache); 512 mutex_exit(&chmp->chm_lock_mountfields); 513 514 return ret; 515 } 516 517 518 eb = chmp->chm_gcblock; 519 520 if (!eb) { 521 eb = find_gc_block(chmp); 522 } 523 524 if (!eb) { 525 dbg_gc("!eb\n"); 526 if (!TAILQ_EMPTY(&chmp->chm_erase_pending_queue)) { 527 mutex_exit(&chmp->chm_lock_sizes); 528 mutex_exit(&chmp->chm_lock_mountfields); 529 return EAGAIN; 530 } 531 mutex_exit(&chmp->chm_lock_sizes); 532 mutex_exit(&chmp->chm_lock_mountfields); 533 return EIO; 534 } 535 536 if (!eb->used_size) { 537 dbg_gc("!eb->used_size\n"); 538 goto eraseit; 539 } 540 541 nref = eb->gc_node; 542 //dbg_gc("gc use: %u\n", chmp->chm_nextblock->lnr); 543 //dbg_gc("nref: %u %u\n", nref->nref_lnr, nref->nref_offset); 544 gcblock_dirty = eb->dirty_size; 545 546 while(CHFS_REF_OBSOLETE(nref)) { 547 //dbg_gc("obsoleted nref lnr: %u - offset: %u\n", nref->nref_lnr, nref->nref_offset); 548 #ifdef DBG_MSG_GC 549 if (nref == chmp->chm_blocks[nref->nref_lnr].last_node) { 550 dbg_gc("THIS NODE IS THE LAST NODE OF ITS EB\n"); 551 } 552 #endif 553 nref = node_next(nref); 554 if (!nref) { 555 //dbg_gc("!nref\n"); 556 eb->gc_node = nref; 557 mutex_exit(&chmp->chm_lock_sizes); 558 mutex_exit(&chmp->chm_lock_mountfields); 559 panic("CHFS BUG - nref is NULL)\n"); 560 } 561 } 562 eb->gc_node = nref; 563 //dbg_gc("nref the chosen one lnr: %u - offset: %u\n", nref->nref_lnr, nref->nref_offset); 564 KASSERT(nref->nref_lnr == chmp->chm_gcblock->lnr); 565 566 if (!nref->nref_next) { 567 //dbg_gc("!nref->nref_next\n"); 568 mutex_exit(&chmp->chm_lock_sizes); 569 if (CHFS_REF_FLAGS(nref) == CHFS_PRISTINE_NODE_MASK) { 570 chfs_gcollect_pristine(chmp, eb, NULL, nref); 571 } else { 572 chfs_mark_node_obsolete(chmp, nref); 573 } 574 goto lock_size; 575 } 576 577 dbg_gc("nref lnr: %u - offset: %u\n", nref->nref_lnr, nref->nref_offset); 578 vc = chfs_nref_to_vc(nref); 579 580 mutex_exit(&chmp->chm_lock_sizes); 581 582 //dbg_gc("enter vnocache lock on #%llu\n", vc->vno); 583 mutex_enter(&chmp->chm_lock_vnocache); 584 585 dbg_gc("switch\n"); 586 switch(vc->state) { 587 case VNO_STATE_CHECKEDABSENT: 588 if (CHFS_REF_FLAGS(nref) == CHFS_PRISTINE_NODE_MASK) { 589 chfs_vnode_cache_set_state(chmp, vc, VNO_STATE_GC); 590 } 591 break; 592 593 case VNO_STATE_PRESENT: 594 break; 595 596 case VNO_STATE_UNCHECKED: 597 case VNO_STATE_CHECKING: 598 case VNO_STATE_GC: 599 mutex_exit(&chmp->chm_lock_vnocache); 600 mutex_exit(&chmp->chm_lock_mountfields); 601 panic("CHFS BUG - vc state unchecked," 602 " checking or gc (vno #%llu, num #%d)\n", 603 vc->vno, vc->state); 604 605 case VNO_STATE_READING: 606 mutex_exit(&chmp->chm_lock_vnocache); 607 /* XXX why do we need the delay here?! */ 608 kpause("chvncrea", true, mstohz(50), NULL); 609 610 // sleep_on_spinunlock(&chmp->chm_lock_vnocache); 611 // KASSERT(!mutex_owned(&chmp->chm_lock_vnocache)); 612 mutex_exit(&chmp->chm_lock_mountfields); 613 return 0; 614 } 615 616 if (vc->state == VNO_STATE_GC) { 617 dbg_gc("vc->state == VNO_STATE_GC\n"); 618 mutex_exit(&chmp->chm_lock_vnocache); 619 ret = chfs_gcollect_pristine(chmp, eb, NULL, nref); 620 621 // chfs_vnode_cache_state_set(chmp, 622 // vc, VNO_STATE_CHECKEDABSENT); 623 /* XXX locking? */ 624 vc->state = VNO_STATE_CHECKEDABSENT; 625 //TODO wake_up(&chmp->chm_vnocache_wq); 626 if (ret != EBADF) 627 goto test_gcnode; 628 mutex_enter(&chmp->chm_lock_vnocache); 629 } 630 631 vno = vc->vno; 632 pvno = vc->pvno; 633 nlink = vc->nlink; 634 mutex_exit(&chmp->chm_lock_vnocache); 635 636 ip = chfs_gc_fetch_inode(chmp, vno, !(pvno | nlink)); 637 638 if (!ip) { 639 dbg_gc("!ip\n"); 640 ret = 0; 641 goto lock_size; 642 } 643 644 chfs_gcollect_live(chmp, eb, nref, ip); 645 646 chfs_gc_release_inode(chmp, ip); 647 648 test_gcnode: 649 if (eb->dirty_size == gcblock_dirty && 650 !CHFS_REF_OBSOLETE(eb->gc_node)) { 651 dbg_gc("ERROR collecting node at %u failed.\n", 652 CHFS_GET_OFS(eb->gc_node->nref_offset)); 653 654 ret = ENOSPC; 655 } 656 657 lock_size: 658 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 659 mutex_enter(&chmp->chm_lock_sizes); 660 eraseit: 661 dbg_gc("eraseit\n"); 662 663 if (chmp->chm_gcblock) { 664 dbg_gc("eb used size = %u\n", chmp->chm_gcblock->used_size); 665 dbg_gc("eb free size = %u\n", chmp->chm_gcblock->free_size); 666 dbg_gc("eb dirty size = %u\n", chmp->chm_gcblock->dirty_size); 667 dbg_gc("eb unchecked size = %u\n", 668 chmp->chm_gcblock->unchecked_size); 669 dbg_gc("eb wasted size = %u\n", chmp->chm_gcblock->wasted_size); 670 671 KASSERT(chmp->chm_gcblock->used_size + chmp->chm_gcblock->free_size + 672 chmp->chm_gcblock->dirty_size + 673 chmp->chm_gcblock->unchecked_size + 674 chmp->chm_gcblock->wasted_size == chmp->chm_ebh->eb_size); 675 676 } 677 678 if (chmp->chm_gcblock && chmp->chm_gcblock->dirty_size + 679 chmp->chm_gcblock->wasted_size == chmp->chm_ebh->eb_size) { 680 dbg_gc("Block at leb #%u completely obsoleted by GC, " 681 "Moving to erase_pending_queue\n", chmp->chm_gcblock->lnr); 682 TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue, 683 chmp->chm_gcblock, queue); 684 chmp->chm_gcblock = NULL; 685 chmp->chm_nr_erasable_blocks++; 686 if (!TAILQ_EMPTY(&chmp->chm_erase_pending_queue)) { 687 ret = chfs_remap_leb(chmp); 688 } 689 } 690 691 mutex_exit(&chmp->chm_lock_sizes); 692 mutex_exit(&chmp->chm_lock_mountfields); 693 dbg_gc("return\n"); 694 return ret; 695 } 696 697 698 int 699 chfs_gcollect_pristine(struct chfs_mount *chmp, struct chfs_eraseblock *cheb, 700 struct chfs_vnode_cache *chvc, struct chfs_node_ref *nref) 701 { 702 struct chfs_node_ref *newnref; 703 struct chfs_flash_node_hdr *nhdr; 704 struct chfs_flash_vnode *fvnode; 705 struct chfs_flash_dirent_node *fdirent; 706 struct chfs_flash_data_node *fdata; 707 int ret, retries = 0; 708 uint32_t ofs, crc; 709 size_t totlen = chfs_nref_len(chmp, cheb, nref); 710 char *data; 711 struct iovec vec; 712 size_t retlen; 713 714 dbg_gc("gcollect_pristine\n"); 715 716 data = kmem_alloc(totlen, KM_SLEEP); 717 if (!data) 718 return ENOMEM; 719 720 ofs = CHFS_GET_OFS(nref->nref_offset); 721 722 ret = chfs_read_leb(chmp, nref->nref_lnr, data, ofs, totlen, &retlen); 723 if (ret) { 724 dbg_gc("reading error\n"); 725 return ret; 726 } 727 if (retlen != totlen) { 728 dbg_gc("read size error\n"); 729 return EIO; 730 } 731 nhdr = (struct chfs_flash_node_hdr *)data; 732 /* check the header */ 733 if (le16toh(nhdr->magic) != CHFS_FS_MAGIC_BITMASK) { 734 dbg_gc("node header magic number error\n"); 735 return EBADF; 736 } 737 crc = crc32(0, (uint8_t *)nhdr, CHFS_NODE_HDR_SIZE - 4); 738 if (crc != le32toh(nhdr->hdr_crc)) { 739 dbg_gc("node header crc error\n"); 740 return EBADF; 741 } 742 743 switch(le16toh(nhdr->type)) { 744 case CHFS_NODETYPE_VNODE: 745 fvnode = (struct chfs_flash_vnode *)data; 746 crc = crc32(0, (uint8_t *)fvnode, sizeof(struct chfs_flash_vnode) - 4); 747 if (crc != le32toh(fvnode->node_crc)) { 748 dbg_gc("vnode crc error\n"); 749 return EBADF; 750 } 751 break; 752 case CHFS_NODETYPE_DIRENT: 753 fdirent = (struct chfs_flash_dirent_node *)data; 754 crc = crc32(0, (uint8_t *)fdirent, sizeof(struct chfs_flash_dirent_node) - 4); 755 if (crc != le32toh(fdirent->node_crc)) { 756 dbg_gc("dirent crc error\n"); 757 return EBADF; 758 } 759 crc = crc32(0, fdirent->name, fdirent->nsize); 760 if (crc != le32toh(fdirent->name_crc)) { 761 dbg_gc("dirent name crc error\n"); 762 return EBADF; 763 } 764 break; 765 case CHFS_NODETYPE_DATA: 766 fdata = (struct chfs_flash_data_node *)data; 767 crc = crc32(0, (uint8_t *)fdata, sizeof(struct chfs_flash_data_node) - 4); 768 if (crc != le32toh(fdata->node_crc)) { 769 dbg_gc("data node crc error\n"); 770 return EBADF; 771 } 772 break; 773 default: 774 if (chvc) { 775 dbg_gc("unknown node have vnode cache\n"); 776 return EBADF; 777 } 778 } 779 /* CRC's OK, write node to its new place */ 780 retry: 781 ret = chfs_reserve_space_gc(chmp, totlen); 782 if (ret) 783 return ret; 784 785 newnref = chfs_alloc_node_ref(chmp->chm_nextblock); 786 if (!newnref) 787 return ENOMEM; 788 789 ofs = chmp->chm_ebh->eb_size - chmp->chm_nextblock->free_size; 790 newnref->nref_offset = ofs; 791 792 vec.iov_base = (void *)data; 793 vec.iov_len = totlen; 794 mutex_enter(&chmp->chm_lock_sizes); 795 ret = chfs_write_wbuf(chmp, &vec, 1, ofs, &retlen); 796 797 if (ret || retlen != totlen) { 798 chfs_err("error while writing out to the media\n"); 799 chfs_err("err: %d | size: %zu | retlen : %zu\n", 800 ret, totlen, retlen); 801 802 chfs_change_size_dirty(chmp, chmp->chm_nextblock, totlen); 803 if (retries) { 804 mutex_exit(&chmp->chm_lock_sizes); 805 return EIO; 806 } 807 808 retries++; 809 mutex_exit(&chmp->chm_lock_sizes); 810 goto retry; 811 } 812 813 mutex_exit(&chmp->chm_lock_sizes); 814 //TODO should we set free_size? 815 chfs_mark_node_obsolete(chmp, nref); 816 chfs_add_vnode_ref_to_vc(chmp, chvc, newnref); 817 return 0; 818 } 819 820 821 int 822 chfs_gcollect_live(struct chfs_mount *chmp, 823 struct chfs_eraseblock *cheb, struct chfs_node_ref *nref, 824 struct chfs_inode *ip) 825 { 826 struct chfs_node_frag *frag; 827 struct chfs_full_dnode *fn = NULL; 828 int start = 0, end = 0, nrfrags = 0; 829 struct chfs_dirent *fd = NULL; 830 int ret = 0; 831 bool is_dirent; 832 833 dbg_gc("gcollect_live\n"); 834 835 if (chmp->chm_gcblock != cheb) { 836 dbg_gc("GC block is no longer gcblock. Restart.\n"); 837 goto upnout; 838 } 839 840 if (CHFS_REF_OBSOLETE(nref)) { 841 dbg_gc("node to be GC'd was obsoleted in the meantime.\n"); 842 goto upnout; 843 } 844 845 /* It's a vnode? */ 846 if (ip->chvc->v == nref) { 847 chfs_gcollect_vnode(chmp, ip); 848 goto upnout; 849 } 850 851 /* find fn */ 852 dbg_gc("find full dnode\n"); 853 for(frag = frag_first(&ip->fragtree); 854 frag; frag = frag_next(&ip->fragtree, frag)) { 855 if (frag->node && frag->node->nref == nref) { 856 fn = frag->node; 857 end = frag->ofs + frag->size; 858 if (!nrfrags++) 859 start = frag->ofs; 860 if (nrfrags == frag->node->frags) 861 break; 862 } 863 } 864 865 /* It's a pristine node, or dnode (or hole? XXX have we hole nodes?) */ 866 if (fn) { 867 if (CHFS_REF_FLAGS(nref) == CHFS_PRISTINE_NODE_MASK) { 868 ret = chfs_gcollect_pristine(chmp, 869 cheb, ip->chvc, nref); 870 if (!ret) { 871 frag->node->nref = ip->chvc->v; 872 } 873 if (ret != EBADF) 874 goto upnout; 875 } 876 //ret = chfs_gcollect_hole(chmp, cheb, ip, fn, start, end); 877 ret = chfs_gcollect_dnode(chmp, cheb, ip, fn, start, end); 878 goto upnout; 879 } 880 881 882 /* It's a dirent? */ 883 dbg_gc("find full dirent\n"); 884 is_dirent = false; 885 TAILQ_FOREACH(fd, &ip->dents, fds) { 886 if (fd->nref == nref) { 887 is_dirent = true; 888 break; 889 } 890 } 891 892 if (is_dirent && fd->vno) { 893 ret = chfs_gcollect_dirent(chmp, cheb, ip, fd); 894 } else if (is_dirent) { 895 ret = chfs_gcollect_deletion_dirent(chmp, cheb, ip, fd); 896 } else { 897 dbg_gc("Nref at leb #%u offset 0x%08x wasn't in node list" 898 " for ino #%llu\n", 899 nref->nref_lnr, CHFS_GET_OFS(nref->nref_offset), ip->ino); 900 if (CHFS_REF_OBSOLETE(nref)) { 901 dbg_gc("But it's obsolete so we don't mind" 902 " too much.\n"); 903 } 904 } 905 906 upnout: 907 return ret; 908 } 909 910 int 911 chfs_gcollect_vnode(struct chfs_mount *chmp, struct chfs_inode *ip) 912 { 913 int ret; 914 dbg_gc("gcollect_vnode\n"); 915 916 ret = chfs_write_flash_vnode(chmp, ip, ALLOC_GC); 917 918 return ret; 919 } 920 921 int 922 chfs_gcollect_dirent(struct chfs_mount *chmp, 923 struct chfs_eraseblock *cheb, struct chfs_inode *parent, 924 struct chfs_dirent *fd) 925 { 926 struct vnode *vnode = NULL; 927 struct chfs_inode *ip; 928 struct chfs_node_ref *prev; 929 dbg_gc("gcollect_dirent\n"); 930 931 vnode = chfs_vnode_lookup(chmp, fd->vno); 932 933 /* XXX maybe KASSERT or panic on this? */ 934 if (vnode == NULL) { 935 return ENOENT; 936 } 937 938 ip = VTOI(vnode); 939 940 prev = parent->chvc->dirents; 941 if (prev == fd->nref) { 942 parent->chvc->dirents = prev->nref_next; 943 dbg_gc("fd nref removed from dirents list\n"); 944 prev = NULL; 945 } 946 while (prev) { 947 if (prev->nref_next == fd->nref) { 948 prev->nref_next = fd->nref->nref_next; 949 dbg_gc("fd nref removed from dirents list\n"); 950 break; 951 } 952 prev = prev->nref_next; 953 } 954 955 prev = fd->nref; 956 chfs_mark_node_obsolete(chmp, fd->nref); 957 return chfs_write_flash_dirent(chmp, 958 parent, ip, fd, fd->vno, ALLOC_GC); 959 } 960 961 /* Check dirents what are marked as deleted. */ 962 int 963 chfs_gcollect_deletion_dirent(struct chfs_mount *chmp, 964 struct chfs_eraseblock *cheb, struct chfs_inode *parent, 965 struct chfs_dirent *fd) 966 { 967 struct chfs_flash_dirent_node chfdn; 968 struct chfs_node_ref *nref; 969 size_t retlen, name_len, nref_len; 970 uint32_t name_crc; 971 972 int ret; 973 974 struct vnode *vnode = NULL; 975 976 dbg_gc("gcollect_deletion_dirent\n"); 977 978 name_len = strlen(fd->name); 979 name_crc = crc32(0, fd->name, name_len); 980 981 nref_len = chfs_nref_len(chmp, cheb, fd->nref); 982 983 vnode = chfs_vnode_lookup(chmp, fd->vno); 984 985 //dbg_gc("ip from vnode\n"); 986 //VFS_VGET(chmp->chm_fsmp, fd->vno, &vnode); 987 //ip = VTOI(vnode); 988 //vput(vnode); 989 990 //dbg_gc("mutex enter erase_completion_lock\n"); 991 992 // dbg_gc("alloc chfdn\n"); 993 // chfdn = kmem_alloc(nref_len, KM_SLEEP); 994 // if (!chfdn) 995 // return ENOMEM; 996 997 for (nref = parent->chvc->dirents; 998 nref != (void*)parent->chvc; 999 nref = nref->nref_next) { 1000 1001 if (!CHFS_REF_OBSOLETE(nref)) 1002 continue; 1003 1004 /* if node refs have different length, skip */ 1005 if (chfs_nref_len(chmp, NULL, nref) != nref_len) 1006 continue; 1007 1008 if (CHFS_GET_OFS(nref->nref_offset) == 1009 CHFS_GET_OFS(fd->nref->nref_offset)) { 1010 continue; 1011 } 1012 1013 ret = chfs_read_leb(chmp, 1014 nref->nref_lnr, (void*)&chfdn, CHFS_GET_OFS(nref->nref_offset), 1015 nref_len, &retlen); 1016 1017 if (ret) { 1018 dbg_gc("Read error: %d\n", ret); 1019 continue; 1020 } 1021 1022 if (retlen != nref_len) { 1023 dbg_gc("Error reading node:" 1024 " read: %zu insted of: %zu\n", retlen, nref_len); 1025 continue; 1026 } 1027 1028 /* if node type doesn't match, skip */ 1029 if (le16toh(chfdn.type) != CHFS_NODETYPE_DIRENT) 1030 continue; 1031 1032 /* if crc doesn't match, skip */ 1033 if (le32toh(chfdn.name_crc) != name_crc) 1034 continue; 1035 1036 /* if length of name different, or this is an another deletion 1037 * dirent, skip 1038 */ 1039 if (chfdn.nsize != name_len || !le64toh(chfdn.vno)) 1040 continue; 1041 1042 /* check actual name */ 1043 if (memcmp(chfdn.name, fd->name, name_len)) 1044 continue; 1045 1046 // kmem_free(chfdn, nref_len); 1047 1048 chfs_mark_node_obsolete(chmp, fd->nref); 1049 return chfs_write_flash_dirent(chmp, 1050 parent, NULL, fd, fd->vno, ALLOC_GC); 1051 } 1052 1053 // kmem_free(chfdn, nref_len); 1054 1055 TAILQ_REMOVE(&parent->dents, fd, fds); 1056 chfs_free_dirent(fd); 1057 return 0; 1058 } 1059 1060 int 1061 chfs_gcollect_dnode(struct chfs_mount *chmp, 1062 struct chfs_eraseblock *orig_cheb, struct chfs_inode *ip, 1063 struct chfs_full_dnode *fn, uint32_t orig_start, uint32_t orig_end) 1064 { 1065 struct chfs_node_ref *nref, *prev; 1066 struct chfs_full_dnode *newfn; 1067 struct chfs_flash_data_node *fdnode; 1068 int ret = 0, retries = 0; 1069 uint32_t totlen; 1070 char *data = NULL; 1071 struct iovec vec; 1072 size_t retlen; 1073 dbg_gc("gcollect_dnode\n"); 1074 1075 //uint32_t used_size; 1076 1077 /* TODO GC merging frags, should we use it? 1078 1079 uint32_t start, end; 1080 1081 start = orig_start; 1082 end = orig_end; 1083 1084 if (chmp->chm_nr_free_blocks + chmp->chm_nr_erasable_blocks > chmp->chm_resv_blocks_gcmerge) { 1085 struct chfs_node_frag *frag; 1086 uint32_t min, max; 1087 1088 min = start & (PAGE_CACHE_SIZE-1); 1089 max = min + PAGE_CACHE_SIZE; 1090 1091 frag = (struct chfs_node_frag *)rb_tree_find_node_leq(&ip->i_chfs_ext.fragtree, &start); 1092 KASSERT(frag->ofs == start); 1093 1094 while ((frag = frag_prev(&ip->i_chfs_ext.fragtree, frag)) && frag->ofs >= min) { 1095 if (frag->ofs > min) { 1096 start = frag->ofs; 1097 continue; 1098 } 1099 1100 if (!frag->node || !frag->node->nref) { 1101 break; 1102 } else { 1103 struct chfs_node_ref *nref = frag->node->nref; 1104 struct chfs_eraseblock *cheb; 1105 1106 cheb = &chmp->chm_blocks[nref->nref_lnr]; 1107 1108 if (cheb == chmp->chm_gcblock) 1109 start = frag->ofs; 1110 1111 //TODO is this a clean block? 1112 1113 start = frag->ofs; 1114 break; 1115 } 1116 } 1117 1118 end--; 1119 frag = (struct chfs_node_frag *)rb_tree_find_node_leq(&ip->i_chfs_ext.fragtree, &(end)); 1120 1121 while ((frag = frag_next(&ip->i_chfs_ext.fragtree, frag)) && (frag->ofs + frag->size <= max)) { 1122 if (frag->ofs + frag->size < max) { 1123 end = frag->ofs + frag->size; 1124 continue; 1125 } 1126 1127 if (!frag->node || !frag->node->nref) { 1128 break; 1129 } else { 1130 struct chfs_node_ref *nref = frag->node->nref; 1131 struct chfs_eraseblock *cheb; 1132 1133 cheb = &chmp->chm_blocks[nref->nref_lnr]; 1134 1135 if (cheb == chmp->chm_gcblock) 1136 end = frag->ofs + frag->size; 1137 1138 //TODO is this a clean block? 1139 1140 end = frag->ofs + frag->size; 1141 break; 1142 } 1143 } 1144 1145 KASSERT(end <= 1146 frag_last(&ip->i_chfs_ext.fragtree)->ofs + 1147 frag_last(&ip->i_chfs_ext.fragtree)->size); 1148 KASSERT(end >= orig_end); 1149 KASSERT(start <= orig_start); 1150 } 1151 */ 1152 KASSERT(orig_cheb->lnr == fn->nref->nref_lnr); 1153 totlen = chfs_nref_len(chmp, orig_cheb, fn->nref); 1154 data = kmem_alloc(totlen, KM_SLEEP); 1155 1156 ret = chfs_read_leb(chmp, fn->nref->nref_lnr, data, fn->nref->nref_offset, 1157 totlen, &retlen); 1158 1159 fdnode = (struct chfs_flash_data_node *)data; 1160 fdnode->version = htole64(++ip->chvc->highest_version); 1161 fdnode->node_crc = htole32(crc32(0, (uint8_t *)fdnode, 1162 sizeof(*fdnode) - 4)); 1163 1164 vec.iov_base = (void *)data; 1165 vec.iov_len = totlen; 1166 1167 retry: 1168 ret = chfs_reserve_space_gc(chmp, totlen); 1169 if (ret) 1170 goto out; 1171 1172 nref = chfs_alloc_node_ref(chmp->chm_nextblock); 1173 if (!nref) { 1174 ret = ENOMEM; 1175 goto out; 1176 } 1177 1178 mutex_enter(&chmp->chm_lock_sizes); 1179 1180 nref->nref_offset = chmp->chm_ebh->eb_size - chmp->chm_nextblock->free_size; 1181 KASSERT(nref->nref_offset % 4 == 0); 1182 chfs_change_size_free(chmp, chmp->chm_nextblock, -totlen); 1183 1184 ret = chfs_write_wbuf(chmp, &vec, 1, nref->nref_offset, &retlen); 1185 if (ret || retlen != totlen) { 1186 chfs_err("error while writing out to the media\n"); 1187 chfs_err("err: %d | size: %d | retlen : %zu\n", 1188 ret, totlen, retlen); 1189 chfs_change_size_dirty(chmp, chmp->chm_nextblock, totlen); 1190 if (retries) { 1191 ret = EIO; 1192 mutex_exit(&chmp->chm_lock_sizes); 1193 goto out; 1194 } 1195 1196 retries++; 1197 mutex_exit(&chmp->chm_lock_sizes); 1198 goto retry; 1199 } 1200 1201 dbg_gc("new nref lnr: %u - offset: %u\n", nref->nref_lnr, nref->nref_offset); 1202 1203 chfs_change_size_used(chmp, &chmp->chm_blocks[nref->nref_lnr], totlen); 1204 mutex_exit(&chmp->chm_lock_sizes); 1205 KASSERT(chmp->chm_blocks[nref->nref_lnr].used_size <= chmp->chm_ebh->eb_size); 1206 1207 newfn = chfs_alloc_full_dnode(); 1208 newfn->nref = nref; 1209 newfn->ofs = fn->ofs; 1210 newfn->size = fn->size; 1211 newfn->frags = fn->frags; 1212 1213 //TODO should we remove fd from dnode list? 1214 1215 prev = ip->chvc->dnode; 1216 if (prev == fn->nref) { 1217 ip->chvc->dnode = prev->nref_next; 1218 prev = NULL; 1219 } 1220 while (prev) { 1221 if (prev->nref_next == fn->nref) { 1222 prev->nref_next = fn->nref->nref_next; 1223 break; 1224 } 1225 prev = prev->nref_next; 1226 } 1227 1228 chfs_add_full_dnode_to_inode(chmp, ip, newfn); 1229 chfs_add_node_to_list(chmp, 1230 ip->chvc, newfn->nref, &ip->chvc->dnode); 1231 1232 out: 1233 kmem_free(data, totlen); 1234 return ret; 1235 } 1236
Indexes created Mon Sep 29 21:09:56 GMT 2025