1 /* $NetBSD: chfs_readinode.c,v 1.2 2011/11/24 21:09:37 agc Exp $ */ 2 3 /*- 4 * Copyright (c) 2010 Department of Software Engineering, 5 * University of Szeged, Hungary 6 * Copyright (C) 2010 David Tengeri <dtengeri@inf.u-szeged.hu> 7 * Copyright (C) 2010 Tamas Toth <ttoth@inf.u-szeged.hu> 8 * Copyright (C) 2010 Adam Hoka <ahoka@NetBSD.org> 9 * All rights reserved. 10 * 11 * This code is derived from software contributed to The NetBSD Foundation 12 * by the Department of Software Engineering, University of Szeged, Hungary 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 1. Redistributions of source code must retain the above copyright 18 * notice, this list of conditions and the following disclaimer. 19 * 2. Redistributions in binary form must reproduce the above copyright 20 * notice, this list of conditions and the following disclaimer in the 21 * documentation and/or other materials provided with the distribution. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 26 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 31 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 /* 37 * chfs_readinode.c 38 * 39 * Created on: 2010.05.31. 40 * Author: dtengeri 41 */ 42 43 #include <sys/buf.h> 44 45 #include "chfs.h" 46 47 /* tmp node operations */ 48 int chfs_check_td_data(struct chfs_mount *, 49 struct chfs_tmp_dnode *); 50 int chfs_check_td_node(struct chfs_mount *, 51 struct chfs_tmp_dnode *); 52 struct chfs_node_ref *chfs_first_valid_data_ref(struct chfs_node_ref *); 53 int chfs_add_tmp_dnode_to_tree(struct chfs_mount *, 54 struct chfs_readinode_info *, 55 struct chfs_tmp_dnode *); 56 void chfs_add_tmp_dnode_to_tdi(struct chfs_tmp_dnode_info *, 57 struct chfs_tmp_dnode *); 58 void chfs_remove_tmp_dnode_from_tdi(struct chfs_tmp_dnode_info *, 59 struct chfs_tmp_dnode *); 60 static void chfs_kill_td(struct chfs_mount *, 61 struct chfs_tmp_dnode *); 62 static void chfs_kill_tdi(struct chfs_mount *, 63 struct chfs_tmp_dnode_info *); 64 /* frag node operations */ 65 struct chfs_node_frag *new_fragment(struct chfs_full_dnode *, 66 uint32_t, 67 uint32_t); 68 int no_overlapping_node(struct rb_tree *, struct chfs_node_frag *, 69 struct chfs_node_frag *, uint32_t); 70 int chfs_add_frag_to_fragtree(struct chfs_mount *, 71 struct rb_tree *, 72 struct chfs_node_frag *); 73 void chfs_obsolete_node_frag(struct chfs_mount *, 74 struct chfs_node_frag *); 75 /* general node operations */ 76 int chfs_get_data_nodes(struct chfs_mount *, 77 struct chfs_inode *, 78 struct chfs_readinode_info *); 79 int chfs_build_fragtree(struct chfs_mount *, 80 struct chfs_inode *, 81 struct chfs_readinode_info *); 82 83 84 85 /* 86 * -------------------------- 87 * tmp node rbtree operations 88 * -------------------------- 89 */ 90 static signed int 91 tmp_node_compare_nodes(void *ctx, const void *n1, const void *n2) 92 { 93 const struct chfs_tmp_dnode_info *tdi1 = n1; 94 const struct chfs_tmp_dnode_info *tdi2 = n2; 95 96 return (tdi1->tmpnode->node->ofs - tdi2->tmpnode->node->ofs); 97 } 98 99 static signed int 100 tmp_node_compare_key(void *ctx, const void *n, const void *key) 101 { 102 const struct chfs_tmp_dnode_info *tdi = n; 103 uint64_t ofs = *(const uint64_t *)key; 104 105 return (tdi->tmpnode->node->ofs - ofs); 106 } 107 108 const rb_tree_ops_t tmp_node_rbtree_ops = { 109 .rbto_compare_nodes = tmp_node_compare_nodes, 110 .rbto_compare_key = tmp_node_compare_key, 111 .rbto_node_offset = offsetof(struct chfs_tmp_dnode_info, rb_node), 112 .rbto_context = NULL 113 }; 114 115 116 /* 117 * --------------------------- 118 * frag node rbtree operations 119 * --------------------------- 120 */ 121 static signed int 122 frag_compare_nodes(void *ctx, const void *n1, const void *n2) 123 { 124 const struct chfs_node_frag *frag1 = n1; 125 const struct chfs_node_frag *frag2 = n2; 126 127 return (frag1->ofs - frag2->ofs); 128 } 129 130 static signed int 131 frag_compare_key(void *ctx, const void *n, const void *key) 132 { 133 const struct chfs_node_frag *frag = n; 134 uint64_t ofs = *(const uint64_t *)key; 135 136 return (frag->ofs - ofs); 137 } 138 139 const rb_tree_ops_t frag_rbtree_ops = { 140 .rbto_compare_nodes = frag_compare_nodes, 141 .rbto_compare_key = frag_compare_key, 142 .rbto_node_offset = offsetof(struct chfs_node_frag, rb_node), 143 .rbto_context = NULL 144 }; 145 146 147 /* 148 * ------------------- 149 * tmp node operations 150 * ------------------- 151 */ 152 /* 153 * Check the data CRC of the node. 154 * 155 * Returns: 0 - if everything OK; 156 * 1 - if CRC is incorrect; 157 * 2 - else; 158 * error code if an error occured. 159 */ 160 int 161 chfs_check_td_data(struct chfs_mount *chmp, 162 struct chfs_tmp_dnode *td) 163 { 164 int err; 165 size_t retlen, len, totlen; 166 uint32_t crc; 167 uint64_t ofs; 168 char *buf; 169 struct chfs_node_ref *nref = td->node->nref; 170 171 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 172 KASSERT(!mutex_owned(&chmp->chm_lock_sizes)); 173 174 ofs = CHFS_GET_OFS(nref->nref_offset) + sizeof(struct chfs_flash_data_node); 175 len = td->node->size; 176 if (!len) 177 return 0; 178 179 buf = kmem_alloc(len, KM_SLEEP); 180 if (!buf) { 181 dbg("allocating error\n"); 182 return 2; 183 } 184 err = chfs_read_leb(chmp, nref->nref_lnr, buf, ofs, len, &retlen); 185 if (err) { 186 dbg("error wile reading: %d\n", err); 187 err = 2; 188 goto out; 189 } 190 191 if (len != retlen) { 192 dbg("len:%zu, retlen:%zu\n", len, retlen); 193 err = 2; 194 goto out; 195 } 196 crc = crc32(0, (uint8_t *)buf, len); 197 198 if (crc != td->data_crc) { 199 dbg("crc failed, calculated: 0x%x, orig: 0x%x\n", crc, td->data_crc); 200 kmem_free(buf, len); 201 return 1; 202 } 203 204 nref->nref_offset = CHFS_GET_OFS(nref->nref_offset) | CHFS_NORMAL_NODE_MASK; 205 totlen = CHFS_PAD(sizeof(struct chfs_flash_data_node) + len); 206 207 mutex_enter(&chmp->chm_lock_sizes); 208 chfs_change_size_unchecked(chmp, &chmp->chm_blocks[nref->nref_lnr], -totlen); 209 chfs_change_size_used(chmp, &chmp->chm_blocks[nref->nref_lnr], totlen); 210 mutex_exit(&chmp->chm_lock_sizes); 211 KASSERT(chmp->chm_blocks[nref->nref_lnr].used_size <= chmp->chm_ebh->eb_size); 212 213 err = 0; 214 out: 215 kmem_free(buf, len); 216 return err; 217 } 218 219 int 220 chfs_check_td_node(struct chfs_mount *chmp, struct chfs_tmp_dnode *td) 221 { 222 int ret; 223 224 if (CHFS_REF_FLAGS(td->node->nref) != CHFS_UNCHECKED_NODE_MASK) 225 return 0; 226 227 ret = chfs_check_td_data(chmp, td); 228 if (ret == 1) { 229 chfs_mark_node_obsolete(chmp, td->node->nref); 230 } 231 return ret; 232 } 233 234 235 struct chfs_node_ref * 236 chfs_first_valid_data_ref(struct chfs_node_ref *nref) 237 { 238 while (nref) { 239 if (!CHFS_REF_OBSOLETE(nref)) { 240 #ifdef DGB_MSG_GC 241 if (nref->nref_lnr == REF_EMPTY_NODE) { 242 dbg("FIRST VALID IS EMPTY!\n"); 243 } 244 #endif 245 return nref; 246 } 247 248 if (nref->nref_next) { 249 nref = nref->nref_next; 250 } else 251 break; 252 } 253 return NULL; 254 } 255 256 void 257 chfs_add_tmp_dnode_to_tdi(struct chfs_tmp_dnode_info *tdi, 258 struct chfs_tmp_dnode *td) 259 { 260 if (!tdi->tmpnode) { 261 tdi->tmpnode = td; 262 } else { 263 struct chfs_tmp_dnode *tmp = tdi->tmpnode; 264 while (tmp->next) { 265 tmp = tmp->next; 266 } 267 tmp->next = td; 268 } 269 } 270 271 void 272 chfs_remove_tmp_dnode_from_tdi(struct chfs_tmp_dnode_info *tdi, 273 struct chfs_tmp_dnode *td) 274 { 275 if (tdi->tmpnode == td) { 276 tdi->tmpnode = tdi->tmpnode->next; 277 } else { 278 struct chfs_tmp_dnode *tmp = tdi->tmpnode->next; 279 while (tmp->next && tmp->next != td) { 280 tmp = tmp->next; 281 } 282 if (tmp->next) { 283 tmp->next = td->next; 284 } 285 } 286 } 287 288 static void 289 chfs_kill_td(struct chfs_mount *chmp, 290 struct chfs_tmp_dnode *td) 291 { 292 /* check if we need to mark as obsolete, to avoid double mark */ 293 if (!CHFS_REF_OBSOLETE(td->node->nref)) { 294 chfs_mark_node_obsolete(chmp, td->node->nref); 295 } 296 297 chfs_free_tmp_dnode(td); 298 } 299 300 static void 301 chfs_kill_tdi(struct chfs_mount *chmp, 302 struct chfs_tmp_dnode_info *tdi) 303 { 304 struct chfs_tmp_dnode *next, *tmp = tdi->tmpnode; 305 306 while (tmp) { 307 next = tmp->next; 308 chfs_kill_td(chmp, tmp); 309 tmp = next; 310 } 311 312 chfs_free_tmp_dnode_info(tdi); 313 } 314 315 int 316 chfs_add_tmp_dnode_to_tree(struct chfs_mount *chmp, 317 struct chfs_readinode_info *rii, 318 struct chfs_tmp_dnode *newtd) 319 { 320 uint64_t end_ofs = newtd->node->ofs + newtd->node->size; 321 struct chfs_tmp_dnode_info *this; 322 struct rb_node *node, *prev_node; 323 struct chfs_tmp_dnode_info *newtdi; 324 325 node = rb_tree_find_node(&rii->tdi_root, &newtd->node->ofs); 326 if (node) { 327 this = (struct chfs_tmp_dnode_info *)node; 328 while (this->tmpnode->overlapped) { 329 prev_node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT); 330 if (!prev_node) { 331 this->tmpnode->overlapped = 0; 332 break; 333 } 334 node = prev_node; 335 this = (struct chfs_tmp_dnode_info *)node; 336 } 337 } 338 while (node) { 339 this = (struct chfs_tmp_dnode_info *)node; 340 if (this->tmpnode->node->ofs > end_ofs) 341 break; 342 343 struct chfs_tmp_dnode *tmp_td = this->tmpnode; 344 while (tmp_td) { 345 if (tmp_td->version == newtd->version) { 346 if (!chfs_check_td_node(chmp, tmp_td)) { 347 dbg("calling kill td 0\n"); 348 chfs_kill_td(chmp, newtd); 349 return 0; 350 } else { 351 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 352 chfs_kill_td(chmp, tmp_td); 353 chfs_add_tmp_dnode_to_tdi(this, newtd); 354 return 0; 355 } 356 } 357 if (tmp_td->version < newtd->version && 358 tmp_td->node->ofs >= newtd->node->ofs && 359 tmp_td->node->ofs + tmp_td->node->size <= end_ofs) { 360 /* New node entirely overlaps 'this' */ 361 if (chfs_check_td_node(chmp, newtd)) { 362 dbg("calling kill td 2\n"); 363 chfs_kill_td(chmp, newtd); 364 return 0; 365 } 366 /* ... and is good. Kill 'this' and any subsequent nodes which are also overlapped */ 367 while (tmp_td && tmp_td->node->ofs + tmp_td->node->size <= end_ofs) { 368 struct rb_node *next = rb_tree_iterate(&rii->tdi_root, this, RB_DIR_RIGHT); 369 struct chfs_tmp_dnode_info *next_tdi = (struct chfs_tmp_dnode_info *)next; 370 struct chfs_tmp_dnode *next_td = NULL; 371 if (tmp_td->next) { 372 next_td = tmp_td->next; 373 } else if (next_tdi) { 374 next_td = next_tdi->tmpnode; 375 } 376 if (tmp_td->version < newtd->version) { 377 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 378 chfs_kill_td(chmp, tmp_td); 379 if (!this->tmpnode) { 380 rb_tree_remove_node(&rii->tdi_root, this); 381 chfs_kill_tdi(chmp, this); 382 this = next_tdi; 383 } 384 } 385 tmp_td = next_td; 386 } 387 continue; 388 } 389 if (tmp_td->version > newtd->version && 390 tmp_td->node->ofs <= newtd->node->ofs && 391 tmp_td->node->ofs + tmp_td->node->size >= end_ofs) { 392 /* New node entirely overlapped by 'this' */ 393 if (!chfs_check_td_node(chmp, tmp_td)) { 394 dbg("this version: %llu\n", 395 (unsigned long long)tmp_td->version); 396 dbg("this ofs: %llu, size: %u\n", 397 (unsigned long long)tmp_td->node->ofs, 398 tmp_td->node->size); 399 dbg("calling kill td 4\n"); 400 chfs_kill_td(chmp, newtd); 401 return 0; 402 } 403 /* ... but 'this' was bad. Replace it... */ 404 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 405 chfs_kill_td(chmp, tmp_td); 406 if (!this->tmpnode) { 407 rb_tree_remove_node(&rii->tdi_root, this); 408 chfs_kill_tdi(chmp, this); 409 } 410 dbg("calling kill td 5\n"); 411 chfs_kill_td(chmp, newtd); 412 break; 413 } 414 tmp_td = tmp_td->next; 415 } 416 node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT); 417 } 418 419 newtdi = chfs_alloc_tmp_dnode_info(); 420 chfs_add_tmp_dnode_to_tdi(newtdi, newtd); 421 /* We neither completely obsoleted nor were completely 422 obsoleted by an earlier node. Insert into the tree */ 423 struct chfs_tmp_dnode_info *tmp_tdi = rb_tree_insert_node(&rii->tdi_root, newtdi); 424 if (tmp_tdi != newtdi) { 425 chfs_add_tmp_dnode_to_tdi(tmp_tdi, newtd); 426 newtdi->tmpnode = NULL; 427 chfs_kill_tdi(chmp, newtdi); 428 } 429 430 /* If there's anything behind that overlaps us, note it */ 431 node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT); 432 if (node) { 433 while (1) { 434 this = (struct chfs_tmp_dnode_info *)node; 435 if (this->tmpnode->node->ofs + this->tmpnode->node->size > newtd->node->ofs) { 436 newtd->overlapped = 1; 437 } 438 if (!this->tmpnode->overlapped) 439 break; 440 441 prev_node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT); 442 if (!prev_node) { 443 this->tmpnode->overlapped = 0; 444 break; 445 } 446 node = prev_node; 447 } 448 } 449 450 /* If the new node overlaps anything ahead, note it */ 451 node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT); 452 this = (struct chfs_tmp_dnode_info *)node; 453 while (this && this->tmpnode->node->ofs < end_ofs) { 454 this->tmpnode->overlapped = 1; 455 node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT); 456 this = (struct chfs_tmp_dnode_info *)node; 457 } 458 return 0; 459 } 460 461 462 /* 463 * -------------------- 464 * frag node operations 465 * -------------------- 466 */ 467 struct chfs_node_frag * 468 new_fragment(struct chfs_full_dnode *fdn, uint32_t ofs, uint32_t size) 469 { 470 struct chfs_node_frag *newfrag; 471 newfrag = chfs_alloc_node_frag(); 472 if (newfrag) { 473 newfrag->ofs = ofs; 474 newfrag->size = size; 475 newfrag->node = fdn; 476 } else { 477 chfs_err("cannot allocate a chfs_node_frag object\n"); 478 } 479 return newfrag; 480 } 481 482 int 483 no_overlapping_node(struct rb_tree *fragtree, 484 struct chfs_node_frag *newfrag, 485 struct chfs_node_frag *this, uint32_t lastend) 486 { 487 if (lastend < newfrag->node->ofs) { 488 struct chfs_node_frag *holefrag; 489 490 holefrag = new_fragment(NULL, lastend, newfrag->node->ofs - lastend); 491 if (!holefrag) { 492 chfs_free_node_frag(newfrag); 493 return ENOMEM; 494 } 495 496 rb_tree_insert_node(fragtree, holefrag); 497 this = holefrag; 498 } 499 500 rb_tree_insert_node(fragtree, newfrag); 501 502 return 0; 503 } 504 505 int 506 chfs_add_frag_to_fragtree(struct chfs_mount *chmp, 507 struct rb_tree *fragtree, 508 struct chfs_node_frag *newfrag) 509 { 510 struct chfs_node_frag *this; 511 uint32_t lastend; 512 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 513 514 this = (struct chfs_node_frag *)rb_tree_find_node_leq(fragtree, &newfrag->ofs); 515 516 if (this) { 517 lastend = this->ofs + this->size; 518 } else { 519 lastend = 0; 520 } 521 522 if (lastend <= newfrag->ofs) { 523 //dbg("no overlapping node\n"); 524 if (lastend && (lastend - 1) >> PAGE_SHIFT == newfrag->ofs >> PAGE_SHIFT) { 525 if (this->node) 526 CHFS_MARK_REF_NORMAL(this->node->nref); 527 CHFS_MARK_REF_NORMAL(newfrag->node->nref); 528 } 529 return no_overlapping_node(fragtree, newfrag, this, lastend); 530 } 531 532 if (newfrag->ofs > this->ofs) { 533 534 CHFS_MARK_REF_NORMAL(newfrag->node->nref); 535 if (this->node) 536 CHFS_MARK_REF_NORMAL(this->node->nref); 537 538 if (this->ofs + this->size > newfrag->ofs + newfrag->size) { 539 /* newfrag is inside of this */ 540 //dbg("newfrag is inside of this\n"); 541 struct chfs_node_frag *newfrag2; 542 543 newfrag2 = new_fragment(this->node, newfrag->ofs + newfrag->size, 544 this->ofs + this->size - newfrag->ofs - newfrag->size); 545 if (!newfrag2) 546 return ENOMEM; 547 if (this->node) 548 this->node->frags++; 549 550 this->size = newfrag->ofs - this->ofs; 551 552 rb_tree_insert_node(fragtree, newfrag); 553 rb_tree_insert_node(fragtree, newfrag2); 554 555 return 0; 556 } 557 /* newfrag is bottom of this */ 558 //dbg("newfrag is bottom of this\n"); 559 this->size = newfrag->ofs - this->ofs; 560 rb_tree_insert_node(fragtree, newfrag); 561 } else { 562 /* newfrag start at same point */ 563 //dbg("newfrag start at same point\n"); 564 //TODO replace instead of remove and insert 565 rb_tree_remove_node(fragtree, this); 566 rb_tree_insert_node(fragtree, newfrag); 567 568 if (newfrag->ofs + newfrag->size >= this->ofs+this->size) { 569 chfs_obsolete_node_frag(chmp, this); 570 } else { 571 this->ofs += newfrag->size; 572 this->size -= newfrag->size; 573 574 rb_tree_insert_node(fragtree, this); 575 return 0; 576 } 577 } 578 /* OK, now we have newfrag added in the correct place in the tree, but 579 frag_next(newfrag) may be a fragment which is overlapped by it 580 */ 581 while ((this = frag_next(fragtree, newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) { 582 rb_tree_remove_node(fragtree, this); 583 chfs_obsolete_node_frag(chmp, this); 584 } 585 586 if (!this || newfrag->ofs + newfrag->size == this->ofs) 587 return 0; 588 589 this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size); 590 this->ofs = newfrag->ofs + newfrag->size; 591 592 if (this->node) 593 CHFS_MARK_REF_NORMAL(this->node->nref); 594 CHFS_MARK_REF_NORMAL(newfrag->node->nref); 595 596 return 0; 597 } 598 599 void 600 chfs_kill_fragtree(struct rb_tree *fragtree) 601 { 602 struct chfs_node_frag *this, *next; 603 //dbg("start\n"); 604 605 this = (struct chfs_node_frag *)RB_TREE_MIN(fragtree); 606 while (this) { 607 //for (this = (struct chfs_node_frag *)RB_TREE_MIN(&fragtree); this != NULL; this = (struct chfs_node_frag *)rb_tree_iterate(&fragtree, &this->rb_node, RB_DIR_RIGHT)) { 608 next = frag_next(fragtree, this); 609 rb_tree_remove_node(fragtree, this); 610 chfs_free_node_frag(this); 611 //dbg("one frag killed\n"); 612 this = next; 613 } 614 //dbg("end\n"); 615 } 616 617 uint32_t 618 chfs_truncate_fragtree(struct chfs_mount *chmp, 619 struct rb_tree *fragtree, uint32_t size) 620 { 621 struct chfs_node_frag *frag; 622 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 623 624 dbg("truncate to size: %u\n", size); 625 626 frag = (struct chfs_node_frag *)rb_tree_find_node_leq(fragtree, &size); 627 628 /* Find the last frag before size and set its new size. */ 629 if (frag && frag->ofs != size) { 630 if (frag->ofs + frag->size > size) { 631 frag->size = size - frag->ofs; 632 } 633 frag = frag_next(fragtree, frag); 634 } 635 636 /* Delete frags after new size. */ 637 while (frag && frag->ofs >= size) { 638 struct chfs_node_frag *next = frag_next(fragtree, frag); 639 640 rb_tree_remove_node(fragtree, frag); 641 chfs_obsolete_node_frag(chmp, frag); 642 frag = next; 643 } 644 645 if (size == 0) { 646 return 0; 647 } 648 649 frag = frag_last(fragtree); 650 651 if (!frag) { 652 return 0; 653 } 654 655 if (frag->ofs + frag->size < size) { 656 return frag->ofs + frag->size; 657 } 658 659 /* FIXME Should we check the postion of the last node? (PAGE_CACHE size, etc.) */ 660 if (frag->node && (frag->ofs & (PAGE_SIZE - 1)) == 0) { 661 frag->node->nref->nref_offset = CHFS_GET_OFS(frag->node->nref->nref_offset) | CHFS_PRISTINE_NODE_MASK; 662 } 663 664 return size; 665 } 666 667 void 668 chfs_obsolete_node_frag(struct chfs_mount *chmp, 669 struct chfs_node_frag *this) 670 { 671 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 672 if (this->node) { 673 this->node->frags--; 674 if (!this->node->frags) { 675 struct chfs_vnode_cache *vc = chfs_nref_to_vc(this->node->nref); 676 chfs_mark_node_obsolete(chmp, this->node->nref); 677 678 if (vc->dnode == this->node->nref) { 679 vc->dnode = this->node->nref->nref_next; 680 } else { 681 struct chfs_node_ref *tmp = vc->dnode; 682 while (tmp->nref_next != (struct chfs_node_ref*) vc 683 && tmp->nref_next != this->node->nref) { 684 tmp = tmp->nref_next; 685 } 686 if (tmp->nref_next == this->node->nref) { 687 tmp->nref_next = this->node->nref->nref_next; 688 } 689 // FIXME should we free here the this->node->nref? 690 } 691 692 chfs_free_full_dnode(this->node); 693 } else { 694 CHFS_MARK_REF_NORMAL(this->node->nref); 695 } 696 } 697 chfs_free_node_frag(this); 698 } 699 700 int 701 chfs_add_full_dnode_to_inode(struct chfs_mount *chmp, 702 struct chfs_inode *ip, 703 struct chfs_full_dnode *fd) 704 { 705 int ret; 706 struct chfs_node_frag *newfrag; 707 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 708 709 if (unlikely(!fd->size)) 710 return 0; 711 712 newfrag = new_fragment(fd, fd->ofs, fd->size); 713 if (unlikely(!newfrag)) 714 return ENOMEM; 715 716 newfrag->node->frags = 1; 717 718 ret = chfs_add_frag_to_fragtree(chmp, &ip->fragtree, newfrag); 719 if (ret) 720 return ret; 721 722 if (newfrag->ofs & (PAGE_SIZE - 1)) { 723 struct chfs_node_frag *prev = frag_prev(&ip->fragtree, newfrag); 724 725 CHFS_MARK_REF_NORMAL(fd->nref); 726 if (prev->node) 727 CHFS_MARK_REF_NORMAL(prev->node->nref); 728 } 729 730 if ((newfrag->ofs+newfrag->size) & (PAGE_SIZE - 1)) { 731 struct chfs_node_frag *next = frag_next(&ip->fragtree, newfrag); 732 733 if (next) { 734 CHFS_MARK_REF_NORMAL(fd->nref); 735 if (next->node) 736 CHFS_MARK_REF_NORMAL(next->node->nref); 737 } 738 } 739 740 return 0; 741 } 742 743 744 /* 745 * ----------------------- 746 * general node operations 747 * ----------------------- 748 */ 749 /* get tmp nodes of an inode */ 750 int 751 chfs_get_data_nodes(struct chfs_mount *chmp, 752 struct chfs_inode *ip, 753 struct chfs_readinode_info *rii) 754 { 755 uint32_t crc; 756 int err; 757 size_t len, retlen; 758 struct chfs_node_ref *nref; 759 struct chfs_flash_data_node *dnode; 760 struct chfs_tmp_dnode *td; 761 char* buf; 762 763 len = sizeof(struct chfs_flash_data_node); 764 buf = kmem_alloc(len, KM_SLEEP); 765 766 dnode = kmem_alloc(len, KM_SLEEP); 767 if (!dnode) 768 return ENOMEM; 769 770 nref = chfs_first_valid_data_ref(ip->chvc->dnode); 771 772 rii->highest_version = ip->chvc->highest_version; 773 774 while(nref && (struct chfs_vnode_cache *)nref != ip->chvc) { 775 err = chfs_read_leb(chmp, nref->nref_lnr, buf, CHFS_GET_OFS(nref->nref_offset), len, &retlen); 776 if (err || len != retlen) 777 goto out; 778 dnode = (struct chfs_flash_data_node*)buf; 779 780 //check header crc 781 crc = crc32(0, (uint8_t *)dnode, CHFS_NODE_HDR_SIZE - 4); 782 if (crc != le32toh(dnode->hdr_crc)) { 783 chfs_err("CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->hdr_crc)); 784 goto cont; 785 } 786 //check header magic bitmask 787 if (le16toh(dnode->magic) != CHFS_FS_MAGIC_BITMASK) { 788 chfs_err("Wrong magic bitmask.\n"); 789 goto cont; 790 } 791 //check node crc 792 crc = crc32(0, (uint8_t *)dnode, sizeof(*dnode) - 4); 793 if (crc != le32toh(dnode->node_crc)) { 794 chfs_err("Node CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->node_crc)); 795 goto cont; 796 } 797 td = chfs_alloc_tmp_dnode(); 798 if (!td) { 799 chfs_err("Can't allocate tmp dnode info.\n"); 800 err = ENOMEM; 801 goto out; 802 } 803 /* We don't check data crc here, just add nodes to tmp frag tree, because 804 * we don't want to check nodes which have been overlapped by a new node 805 * with a higher version number. 806 */ 807 td->node = chfs_alloc_full_dnode(); 808 if (!td->node) { 809 chfs_err("Can't allocate full dnode info.\n"); 810 err = ENOMEM; 811 goto out_tmp_dnode; 812 } 813 td->version = le64toh(dnode->version); 814 td->node->ofs = le64toh(dnode->offset); 815 td->data_crc = le32toh(dnode->data_crc); 816 td->node->nref = nref; 817 td->node->size = le32toh(dnode->data_length); 818 td->overlapped = 0; 819 820 if (td->version > rii->highest_version) { 821 rii->highest_version = td->version; 822 } 823 824 err = chfs_add_tmp_dnode_to_tree(chmp, rii, td); 825 if (err) 826 goto out_full_dnode; 827 828 cont: 829 nref = chfs_first_valid_data_ref(nref->nref_next); 830 } 831 832 ip->chvc->highest_version = rii->highest_version; 833 return 0; 834 835 /* Exit points */ 836 out_full_dnode: 837 chfs_free_full_dnode(td->node); 838 out_tmp_dnode: 839 chfs_free_tmp_dnode(td); 840 out: 841 kmem_free(buf, len); 842 kmem_free(dnode, len); 843 return err; 844 } 845 846 847 /* Build final normal fragtree from tdi tree. */ 848 int 849 chfs_build_fragtree(struct chfs_mount *chmp, struct chfs_inode *ip, 850 struct chfs_readinode_info *rii) 851 { 852 struct chfs_tmp_dnode_info *pen, *last, *this; 853 struct rb_tree ver_tree; /* version tree */ 854 uint64_t high_ver = 0; 855 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 856 857 rb_tree_init(&ver_tree, &tmp_node_rbtree_ops); 858 859 if (rii->mdata_tn) { 860 high_ver = rii->mdata_tn->tmpnode->version; 861 rii->latest_ref = rii->mdata_tn->tmpnode->node->nref; 862 } 863 864 pen = (struct chfs_tmp_dnode_info *)RB_TREE_MAX(&rii->tdi_root); 865 866 while((last = pen)) { 867 pen = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&rii->tdi_root, last, RB_DIR_LEFT); 868 869 rb_tree_remove_node(&rii->tdi_root, last); 870 rb_tree_insert_node(&ver_tree, last); 871 872 if (last->tmpnode->overlapped) { 873 if (pen) 874 continue; 875 876 last->tmpnode->overlapped = 0; 877 } 878 879 this = (struct chfs_tmp_dnode_info *)RB_TREE_MAX(&ver_tree); 880 881 while (this) { 882 struct chfs_tmp_dnode_info *vers_next; 883 int ret; 884 885 vers_next = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&ver_tree, this, RB_DIR_LEFT); 886 rb_tree_remove_node(&ver_tree, this); 887 888 struct chfs_tmp_dnode *tmp_td = this->tmpnode; 889 while (tmp_td) { 890 struct chfs_tmp_dnode *next_td = tmp_td->next; 891 892 if (chfs_check_td_node(chmp, tmp_td)) { 893 if (next_td) { 894 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 895 } else { 896 break; 897 } 898 } else { 899 if (tmp_td->version > high_ver) { 900 high_ver = tmp_td->version; 901 dbg("highver: %llu\n", (unsigned long long)high_ver); 902 rii->latest_ref = tmp_td->node->nref; 903 } 904 905 ret = chfs_add_full_dnode_to_inode(chmp, ip, tmp_td->node); 906 if (ret) { 907 while (1) { 908 vers_next = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&ver_tree, this, RB_DIR_LEFT); 909 while (tmp_td) { 910 next_td = tmp_td->next; 911 if (chfs_check_td_node(chmp, tmp_td) > 1) { 912 chfs_mark_node_obsolete(chmp, 913 tmp_td->node->nref); 914 } 915 chfs_free_full_dnode(tmp_td->node); 916 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 917 chfs_free_tmp_dnode(tmp_td); 918 tmp_td = next_td; 919 } 920 chfs_free_tmp_dnode_info(this); 921 this = vers_next; 922 if (!this) 923 break; 924 rb_tree_remove_node(&ver_tree, vers_next); 925 } 926 return ret; 927 } 928 929 chfs_remove_tmp_dnode_from_tdi(this, tmp_td); 930 chfs_free_tmp_dnode(tmp_td); 931 } 932 tmp_td = next_td; 933 } 934 chfs_kill_tdi(chmp, this); 935 this = vers_next; 936 } 937 } 938 939 return 0; 940 } 941 942 int chfs_read_inode(struct chfs_mount *chmp, struct chfs_inode *ip) 943 { 944 struct chfs_vnode_cache *vc = ip->chvc; 945 946 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 947 948 retry: 949 /* XXX locking */ 950 //mutex_enter(&chmp->chm_lock_vnocache); 951 switch (vc->state) { 952 case VNO_STATE_UNCHECKED: 953 case VNO_STATE_CHECKEDABSENT: 954 // chfs_vnode_cache_set_state(chmp, vc, VNO_STATE_READING); 955 vc->state = VNO_STATE_READING; 956 break; 957 case VNO_STATE_CHECKING: 958 case VNO_STATE_GC: 959 //sleep_on_spinunlock(&chmp->chm_lock_vnocache); 960 //KASSERT(!mutex_owned(&chmp->chm_lock_vnocache)); 961 goto retry; 962 break; 963 case VNO_STATE_PRESENT: 964 case VNO_STATE_READING: 965 chfs_err("Reading inode #%llu in state %d!\n", 966 (unsigned long long)vc->vno, vc->state); 967 chfs_err("wants to read a nonexistent ino %llu\n", 968 (unsigned long long)vc->vno); 969 return ENOENT; 970 default: 971 panic("BUG() Bad vno cache state."); 972 } 973 //mutex_exit(&chmp->chm_lock_vnocache); 974 975 return chfs_read_inode_internal(chmp, ip); 976 } 977 978 /* 979 * Read inode frags. 980 * Firstly get tmp nodes, 981 * secondly build fragtree from those. 982 */ 983 int 984 chfs_read_inode_internal(struct chfs_mount *chmp, struct chfs_inode *ip) 985 { 986 int err; 987 size_t len, retlen; 988 char* buf; 989 struct chfs_readinode_info rii; 990 struct chfs_flash_vnode *fvnode; 991 992 KASSERT(mutex_owned(&chmp->chm_lock_mountfields)); 993 994 len = sizeof(*fvnode); 995 996 memset(&rii, 0, sizeof(rii)); 997 998 rb_tree_init(&rii.tdi_root, &tmp_node_rbtree_ops); 999 1000 /* build up a temp node frag tree */ 1001 err = chfs_get_data_nodes(chmp, ip, &rii); 1002 if (err) { 1003 if (ip->chvc->state == VNO_STATE_READING) 1004 ip->chvc->state = VNO_STATE_CHECKEDABSENT; 1005 /* FIXME Should we kill fragtree or something here? */ 1006 return err; 1007 } 1008 1009 rb_tree_init(&ip->fragtree, &frag_rbtree_ops); 1010 /* 1011 * build fragtree from temp nodes 1012 */ 1013 err = chfs_build_fragtree(chmp, ip, &rii); 1014 if (err) { 1015 if (ip->chvc->state == VNO_STATE_READING) 1016 ip->chvc->state = VNO_STATE_CHECKEDABSENT; 1017 /* FIXME Should we kill fragtree or something here? */ 1018 return err; 1019 } 1020 1021 if (!rii.latest_ref) { 1022 return 0; 1023 } 1024 1025 buf = kmem_alloc(len, KM_SLEEP); 1026 if (!buf) 1027 return ENOMEM; 1028 1029 /* 1030 * set inode size from chvc->v 1031 */ 1032 err = chfs_read_leb(chmp, ip->chvc->v->nref_lnr, buf, CHFS_GET_OFS(ip->chvc->v->nref_offset), len, &retlen); 1033 if (err || retlen != len) { 1034 kmem_free(buf, len); 1035 return err?err:EIO; 1036 } 1037 1038 fvnode = (struct chfs_flash_vnode*)buf; 1039 1040 dbg("set size from v: %u\n", fvnode->dn_size); 1041 chfs_set_vnode_size(ITOV(ip), fvnode->dn_size); 1042 uint32_t retsize = chfs_truncate_fragtree(chmp, &ip->fragtree, fvnode->dn_size); 1043 if (retsize != fvnode->dn_size) { 1044 dbg("Truncating failed. It is %u instead of %u\n", retsize, fvnode->dn_size); 1045 } 1046 1047 kmem_free(buf, len); 1048 1049 if (ip->chvc->state == VNO_STATE_READING) { 1050 ip->chvc->state = VNO_STATE_PRESENT; 1051 } 1052 1053 return 0; 1054 } 1055 1056 int 1057 chfs_read_data(struct chfs_mount* chmp, struct vnode *vp, 1058 struct buf *bp) 1059 { 1060 off_t ofs; 1061 struct chfs_node_frag *frag; 1062 char * buf; 1063 int err = 0; 1064 size_t size, retlen; 1065 uint32_t crc; 1066 struct chfs_inode *ip = VTOI(vp); 1067 struct chfs_flash_data_node *dnode; 1068 struct chfs_node_ref *nref; 1069 1070 memset(bp->b_data, 0, bp->b_bcount); 1071 1072 ofs = bp->b_blkno * PAGE_SIZE; 1073 frag = (struct chfs_node_frag *)rb_tree_find_node_leq(&ip->fragtree, &ofs); 1074 1075 if (!frag || frag->ofs > ofs || frag->ofs + frag->size <= ofs) { 1076 dbg("not found in frag tree\n"); 1077 return 0; 1078 } 1079 1080 if (!frag->node) { 1081 dbg("no node in frag\n"); 1082 return 0; 1083 } 1084 1085 nref = frag->node->nref; 1086 1087 size = sizeof(*dnode) + frag->size; 1088 1089 buf = kmem_alloc(size, KM_SLEEP); 1090 1091 dbg("reading from lnr: %u, offset: %u, size: %zu\n", nref->nref_lnr, CHFS_GET_OFS(nref->nref_offset), size); 1092 err = chfs_read_leb(chmp, nref->nref_lnr, buf, CHFS_GET_OFS(nref->nref_offset), size, &retlen); 1093 if (err) { 1094 chfs_err("error after reading: %d\n", err); 1095 goto out; 1096 } 1097 if (retlen != size) { 1098 chfs_err("retlen: %zu != size: %zu\n", retlen, size); 1099 err = EIO; 1100 goto out; 1101 } 1102 1103 dnode = (struct chfs_flash_data_node *)buf; 1104 crc = crc32(0, (uint8_t *)dnode, CHFS_NODE_HDR_SIZE - 4); 1105 if (crc != le32toh(dnode->hdr_crc)) { 1106 chfs_err("CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->hdr_crc)); 1107 err = EIO; 1108 goto out; 1109 } 1110 //check header magic bitmask 1111 if (le16toh(dnode->magic) != CHFS_FS_MAGIC_BITMASK) { 1112 chfs_err("Wrong magic bitmask.\n"); 1113 err = EIO; 1114 goto out; 1115 } 1116 //check node crc 1117 crc = crc32(0, (uint8_t *)dnode, sizeof(*dnode) - 4); 1118 if (crc != le32toh(dnode->node_crc)) { 1119 chfs_err("Node CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->node_crc)); 1120 err = EIO; 1121 goto out; 1122 } 1123 crc = crc32(0, (uint8_t *)dnode->data, dnode->data_length); 1124 if (crc != le32toh(dnode->data_crc)) { 1125 chfs_err("Data CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->data_crc)); 1126 err = EIO; 1127 goto out; 1128 } 1129 1130 memcpy(bp->b_data, dnode->data, dnode->data_length); 1131 bp->b_resid = 0; 1132 1133 out: 1134 kmem_free(buf, size); 1135 return err; 1136 } 1137