lunaix-os/kernel/fs/ext2/inode.c

   1 #include <lunaix/fs/api.h>
   2 #include <lunaix/mm/valloc.h>
   3
   4 #include <klibc/string.h>
   5
   6 #include "ext2.h"
   7
   8 static struct v_inode_ops ext2_inode_ops = {
   9     .dir_lookup = ext2dr_lookup,
  10     .open  = ext2_open_inode,
  11     .mkdir = ext2_mkdir,
  12     .rmdir = ext2_rmdir,
  13     .read_symlink = ext2_get_symlink,
  14     .set_symlink  = ext2_set_symlink,
  15     .rename = ext2_rename,
  16     .link = ext2_link,
  17     .unlink = ext2_unlink,
  18     .create = ext2_create,
  19     .sync = ext2_sync_inode
  20 };
  21
  22 static struct v_file_ops ext2_file_ops = {
  23     .close = ext2_close_inode,
  24
  25     .read = ext2_inode_read,
  26     .read_page = ext2_inode_read_page,
  27
  28     .write = ext2_inode_write,
  29     .write_page = ext2_inode_write_page,
  30
  31     .readdir = ext2dr_read,
  32     .seek = ext2_seek_inode,
  33     .sync = ext2_file_sync
  34 };
  35
  36 #define to_tag(e_ino, val)        \
  37         (((val) >> (e_ino)->inds_lgents) | (1 << msbiti))
  38 #define valid_tag(tag)      ((tag) & (1 << msbiti))
  39
  40 static void
  41 __btlb_insert(struct ext2_inode* e_inode, unsigned int blkid, bbuf_t buf)
  42 {
  43     struct ext2_btlb* btlb;
  44     struct ext2_btlb_entry* btlbe = NULL;
  45     unsigned int cap_sel;
  46
  47     if (unlikely(!blkid)) {
  48         return;
  49     }
  50
  51     btlb = e_inode->btlb;
  52
  53     for (int i = 0; i < BTLB_SETS; i++)
  54     {
  55         if (valid_tag(btlb->buffer[i].tag)) {
  56             continue;
  57         }
  58
  59         btlbe = &btlb->buffer[i];
  60         goto found;
  61     }
  62
  63     /*
  64         we have triggered the capacity miss.
  65         since most file operation is heavily linear and strong
  66         locality, we place our bet on it and avoid go through
  67         the whole overhead of LRU eviction stuff. Just a trival
  68         random eviction will do the fine job
  69     */
  70     cap_sel = hash_32(blkid, ilog2(BTLB_SETS));
  71     btlbe = &btlb->buffer[cap_sel];
  72
  73     fsblock_put(btlbe->block);
  74
  75 found:
  76     btlbe->tag = to_tag(e_inode, blkid);
  77     btlbe->block = fsblock_take(buf);
  78 }
  79
  80 static bbuf_t
  81 __btlb_hit(struct ext2_inode* e_inode, unsigned int blkid)
  82 {
  83     struct ext2_btlb* btlb;
  84     struct ext2_btlb_entry* btlbe = NULL;
  85     unsigned int in_tag, ref_cnts;
  86
  87     btlb = e_inode->btlb;
  88     in_tag = to_tag(e_inode, blkid);
  89
  90     for (int i = 0; i < BTLB_SETS; i++)
  91     {
  92         btlbe = &btlb->buffer[i];
  93
  94         if (btlbe->tag != in_tag) {
  95             continue;
  96         }
  97
  98         ref_cnts = blkbuf_refcounts(btlbe->block);
  99         if (!ref_cnts) {
 100             btlbe->tag = 0;
 101             btlbe->block = bbuf_null;
 102             break;
 103         }
 104
 105         return fsblock_take(btlbe->block);
 106     }
 107
 108     return NULL;
 109 }
 110
 111 static void
 112 __btlb_flushall(struct ext2_inode* e_inode)
 113 {
 114     struct ext2_btlb* btlb;
 115     struct ext2_btlb_entry* btlbe = NULL;
 116
 117     btlb = e_inode->btlb;
 118
 119     for (int i = 0; i < BTLB_SETS; i++)
 120     {
 121         btlbe = &btlb->buffer[i];
 122         if (!valid_tag(btlbe->tag)) {
 123             continue;
 124         }
 125
 126         btlbe->tag = 0;
 127         fsblock_put(btlbe->block);
 128     }
 129 }
 130
 131 /**
 132  * Obtain the number of indirect blocks that contains
 133  * pointers to next level blocks.
 134  *
 135  * Let N be the number of ids that a data block can hold,
 136  * then the total number of data blocks assigned (reserved)
 137  * to the inode:
 138  *
 139  * i_blocks = 12 + (N + 1) + (N^2 + N + 1) + (N^3 + N^2 + N + 1)
 140  */
 141 static int
 142 __get_nr_indblks(struct ext2_sbinfo* sb, size_t fsblks)
 143 {
 144     ssize_t blks;
 145     int nr_ents;
 146     int nr_inds, n, acc_nr;
 147
 148     blks    = (ssize_t)fsblks;
 149     nr_ents = sb->block_size / sizeof(int);
 150     acc_nr  = 1;
 151
 152     if (blks <= 12)
 153         return 0;
 154
 155     blks -= 12;
 156
 157     if (blks > 0) // order-1 indirection
 158     {
 159         n = MIN(ICEIL(blks, nr_ents), acc_nr);
 160         blks  -= n * nr_ents;
 161
 162         nr_inds += 1;
 163         acc_nr  *= nr_ents;
 164     }
 165
 166     if (blks > 0) // order-2 indirection
 167     {
 168         n = MIN(ICEIL(blks, nr_ents), acc_nr);
 169         blks  -= n * nr_ents;
 170
 171         nr_inds += n + 1;
 172         acc_nr  *= nr_ents;
 173     }
 174
 175     if (blks > 0) // order-3 indirection
 176     {
 177         n = MAX(ICEIL(blks, nr_ents), acc_nr);
 178         blks  -= n * nr_ents;
 179
 180         nr_inds += n + ICEIL(n, nr_ents) + 1;
 181     }
 182
 183     assert_fs(blks <= 0);
 184
 185     return nr_inds;
 186 }
 187
 188 void
 189 ext2db_itbegin(struct ext2_iterator* iter, struct v_inode* inode, int mode)
 190 {
 191     struct ext2_inode* e_ino;
 192
 193     e_ino = EXT2_INO(inode);
 194     *iter = (struct ext2_iterator){
 195         .pos = 0,
 196         .inode = inode,
 197         .blksz = inode->sb->blksize,
 198     };
 199
 200     if (mode == DBIT_MODE_ISIZE)
 201         iter->end_pos = ICEIL(e_ino->isize, inode->sb->blksize);
 202     else
 203         iter->end_pos = e_ino->nr_fsblks - e_ino->nr_indblks;
 204 }
 205
 206 void
 207 ext2db_itreset(struct ext2_iterator* iter)
 208 {
 209     if (likely(iter->sel_buf)) {
 210         fsblock_put(iter->sel_buf);
 211         iter->sel_buf = NULL;
 212     }
 213
 214     iter->pos = 0;
 215 }
 216
 217 int
 218 ext2db_itffw(struct ext2_iterator* iter, int count)
 219 {
 220     iter->pos += count;
 221     return count;
 222 }
 223
 224 void
 225 ext2db_itend(struct ext2_iterator* iter)
 226 {
 227     if (likely(iter->sel_buf)) {
 228         fsblock_put(iter->sel_buf);
 229         iter->sel_buf = NULL;
 230     }
 231 }
 232
 233 bool
 234 ext2db_itnext(struct ext2_iterator* iter)
 235 {
 236     bbuf_t buf;
 237
 238     if (unlikely(iter->has_error)) {
 239         return false;
 240     }
 241
 242     if (unlikely(iter->pos > iter->end_pos)) {
 243         return false;
 244     }
 245
 246     if (likely(iter->sel_buf)) {
 247         fsblock_put(iter->sel_buf);
 248     }
 249
 250     buf = ext2db_get(iter->inode, iter->pos++);
 251     iter->sel_buf = buf;
 252
 253     if (!buf || !ext2_itcheckbuf(iter)) {
 254         return false;
 255     }
 256
 257     iter->data = blkbuf_data(buf);
 258
 259     return true;
 260 }
 261
 262 void
 263 ext2ino_init(struct v_superblock* vsb, struct v_inode* inode)
 264 {
 265     // Placeholder, to make vsb happy
 266 }
 267
 268 static void
 269 __destruct_ext2_inode(struct ext2_inode* e_inode)
 270 {
 271     __btlb_flushall(e_inode);
 272
 273     fsblock_put(e_inode->ind_ord1);
 274     fsblock_put(e_inode->buf);
 275
 276     ext2gd_put(e_inode->blk_grp);
 277
 278     vfree_safe(e_inode->symlink);
 279     vfree(e_inode->btlb);
 280     vfree(e_inode);
 281 }
 282
 283 static void
 284 ext2_destruct_inode(struct v_inode* inode)
 285 {
 286     struct ext2_inode* e_inode;
 287
 288     e_inode = EXT2_INO(inode);
 289
 290     assert(e_inode);
 291     __destruct_ext2_inode(e_inode);
 292 }
 293
 294 static inline void
 295 __ext2ino_fill_common(struct v_inode* inode, ino_t ino_id)
 296 {
 297     fsapi_inode_setid(inode, ino_id, ino_id);
 298     fsapi_inode_setfops(inode, &ext2_file_ops);
 299     fsapi_inode_setops(inode, &ext2_inode_ops);
 300     fsapi_inode_setdector(inode, ext2_destruct_inode);
 301 }
 302
 303
 304 static unsigned int
 305 __translate_vfs_itype(unsigned int v_itype)
 306 {
 307     unsigned int e_itype = IMODE_IFREG;
 308
 309     if (v_itype == VFS_IFFILE) {
 310         e_itype = IMODE_IFREG;
 311     }
 312     else if (check_itype(v_itype, VFS_IFDIR)) {
 313         e_itype = IMODE_IFDIR;
 314         e_itype |= IMODE_UEX;
 315     }
 316     else if (check_itype(v_itype, VFS_IFSEQDEV)) {
 317         e_itype = IMODE_IFCHR;
 318     }
 319     else if (check_itype(v_itype, VFS_IFVOLDEV)) {
 320         e_itype = IMODE_IFBLK;
 321     }
 322
 323     if (check_itype(v_itype, VFS_IFSYMLINK)) {
 324         e_itype |= IMODE_IFLNK;
 325     }
 326
 327     // FIXME we keep this until we have our own user manager
 328     e_itype |= (IMODE_URD | IMODE_GRD | IMODE_ORD);
 329     return e_itype;
 330 }
 331
 332 int
 333 ext2ino_fill(struct v_inode* inode, ino_t ino_id)
 334 {
 335     struct ext2_sbinfo* sb;
 336     struct ext2_inode* e_ino;
 337     struct v_superblock* vsb;
 338     struct ext2b_inode* b_ino;
 339     unsigned int type = VFS_IFFILE;
 340     int errno = 0;
 341
 342     vsb = inode->sb;
 343     sb = EXT2_SB(vsb);
 344
 345     if ((errno = ext2ino_get(vsb, ino_id, &e_ino))) {
 346         return errno;
 347     }
 348
 349     b_ino = e_ino->ino;
 350     ino_id = e_ino->ino_id;
 351
 352     fsapi_inode_setsize(inode, e_ino->isize);
 353
 354     fsapi_inode_settime(inode, b_ino->i_ctime,
 355                                b_ino->i_mtime,
 356                                b_ino->i_atime);
 357
 358     fsapi_inode_setaccess(inode, b_ino->i_mode & IMODE_ACL_MASK);
 359     fsapi_inode_setowner(inode, b_ino->i_uid,
 360                                 b_ino->i_gid);
 361
 362     __ext2ino_fill_common(inode, ino_id);
 363
 364     if (check_itype(b_ino->i_mode, IMODE_IFLNK)) {
 365         type = VFS_IFSYMLINK;
 366     }
 367     else if (check_itype(b_ino->i_mode, IMODE_IFDIR)) {
 368         type = VFS_IFDIR;
 369     }
 370     else if (check_itype(b_ino->i_mode, IMODE_IFCHR)) {
 371         type = VFS_IFSEQDEV;
 372     }
 373     else if (check_itype(b_ino->i_mode, IMODE_IFBLK)) {
 374         type = VFS_IFVOLDEV;
 375     }
 376
 377     fsapi_inode_settype(inode, type);
 378
 379     fsapi_inode_complete(inode, e_ino);
 380
 381     return 0;
 382 }
 383
 384 static int
 385 __get_group_desc(struct v_superblock* vsb, int ino,
 386                  struct ext2_gdesc** gd_out)
 387 {
 388     unsigned int blkgrp_id;
 389     struct ext2_sbinfo* sb;
 390
 391     sb = EXT2_SB(vsb);
 392
 393     blkgrp_id = to_fsblock_id(ino) / sb->raw->s_ino_per_grp;
 394     return ext2gd_take_at(vsb, blkgrp_id, gd_out);
 395 }
 396
 397 static struct ext2b_inode*
 398 __get_raw_inode(struct v_superblock* vsb, struct ext2_gdesc* gd,
 399                 bbuf_t* buf_out, int ino_index)
 400 {
 401     bbuf_t ino_tab;
 402     struct ext2_sbinfo* sb;
 403     struct ext2b_inode* b_inode;
 404     unsigned int ino_tab_sel, ino_tab_off, tab_partlen;
 405
 406     assert(buf_out);
 407
 408     sb = gd->sb;
 409     tab_partlen = sb->block_size / sb->raw->s_ino_size;
 410     ino_tab_sel = ino_index / tab_partlen;
 411     ino_tab_off = ino_index % tab_partlen;
 412
 413     ino_tab = fsblock_get(vsb, gd->info->bg_ino_tab + ino_tab_sel);
 414     if (blkbuf_errbuf(ino_tab)) {
 415         return NULL;
 416     }
 417
 418     b_inode = (struct ext2b_inode*)blkbuf_data(ino_tab);
 419     b_inode = &b_inode[ino_tab_off];
 420
 421     *buf_out = ino_tab;
 422
 423     return b_inode;
 424 }
 425
 426 static struct ext2_inode*
 427 __create_inode(struct v_superblock* vsb, struct ext2_gdesc* gd, int ino_index)
 428 {
 429     bbuf_t ino_tab;
 430     struct ext2_sbinfo* sb;
 431     struct ext2b_inode* b_inode;
 432     struct ext2_inode* inode;
 433     unsigned int ind_ents;
 434     size_t nr_linked;
 435
 436     sb = gd->sb;
 437     b_inode = __get_raw_inode(vsb, gd, &ino_tab, ino_index);
 438     if (!b_inode) {
 439         return NULL;
 440     }
 441
 442     inode            = vzalloc(sizeof(*inode));
 443     inode->btlb      = vzalloc(sizeof(struct ext2_btlb));
 444     inode->buf       = ino_tab;
 445     inode->ino       = b_inode;
 446     inode->blk_grp   = ext2gd_take(gd);
 447     inode->isize     = b_inode->i_size;
 448
 449     if (ext2_feature(vsb, FEAT_LARGE_FILE)) {
 450         inode->isize |= (size_t)((u64_t)(b_inode->i_size_h32) << 32);
 451     }
 452
 453     if (b_inode->i_blocks) {
 454         nr_linked  = (size_t)b_inode->i_blocks;
 455         nr_linked /= (sb->block_size / 512);
 456
 457         inode->nr_fsblks = nr_linked;
 458         inode->nr_indblks = __get_nr_indblks(sb, nr_linked);
 459     }
 460
 461     ind_ents = sb->block_size / sizeof(int);
 462     assert(is_pot(ind_ents));
 463
 464     inode->inds_lgents = ilog2(ind_ents);
 465     inode->ino_id = gd->ino_base + to_ext2ino_id(ino_index);
 466
 467     ext2_debug("ino(%d): isize=%lu, nr_blk=%lu, nr_inds=%lu",
 468                     inode->ino_id, inode->isize, inode->nr_fsblks, inode->nr_indblks);
 469     return inode;
 470 }
 471
 472 int
 473 ext2ino_get_fast(struct v_superblock* vsb,
 474                  unsigned int ino, struct ext2_fast_inode* fast_ino)
 475 {
 476     int errno;
 477     bbuf_t ino_tab;
 478     struct ext2_gdesc* gd;
 479     struct ext2_sbinfo* sb;
 480     struct ext2b_inode* b_inode;
 481     unsigned int ino_rel_id;
 482
 483     sb = EXT2_SB(vsb);
 484     errno = __get_group_desc(vsb, ino, &gd);
 485     if (errno) {
 486         return errno;
 487     }
 488
 489     ino_rel_id  = to_fsblock_id(ino) % sb->raw->s_ino_per_grp;
 490     b_inode = __get_raw_inode(vsb, gd, &ino_tab, ino_rel_id);
 491
 492     fast_ino->buf = ino_tab;
 493     fast_ino->ino = b_inode;
 494
 495     return 0;
 496 }
 497
 498 int
 499 ext2ino_get(struct v_superblock* vsb,
 500             unsigned int ino, struct ext2_inode** out)
 501 {
 502     struct ext2_sbinfo* sb;
 503     struct ext2_inode* inode;
 504     struct ext2_gdesc* gd;
 505     struct ext2b_inode* b_inode;
 506     unsigned int ino_rel_id;
 507     unsigned int tab_partlen;
 508     unsigned int ind_ents, prima_ind;
 509     int errno = 0;
 510
 511     sb = EXT2_SB(vsb);
 512
 513     if ((errno = __get_group_desc(vsb, ino, &gd))) {
 514         return errno;
 515     }
 516
 517     ino_rel_id  = to_fsblock_id(ino) % sb->raw->s_ino_per_grp;
 518     inode = __create_inode(vsb, gd, ino_rel_id);
 519     if (!inode) {
 520         return EIO;
 521     }
 522
 523     b_inode = inode->ino;
 524     prima_ind = b_inode->i_block.ind1;
 525     *out = inode;
 526
 527     if (!prima_ind) {
 528         return errno;
 529     }
 530
 531     inode->ind_ord1 = fsblock_get(vsb, prima_ind);
 532     if (blkbuf_errbuf(inode->ind_ord1)) {
 533         vfree(inode->btlb);
 534         vfree(inode);
 535         *out = NULL;
 536         return EIO;
 537     }
 538
 539     return errno;
 540 }
 541
 542 int
 543 ext2ino_alloc(struct v_superblock* vsb,
 544                  struct ext2_inode* hint, struct ext2_inode** out)
 545 {
 546     int free_ino_idx;
 547     struct ext2_gdesc* gd;
 548     struct ext2_inode* inode;
 549
 550     free_ino_idx = ALLOC_FAIL;
 551     if (hint) {
 552         gd = hint->blk_grp;
 553         free_ino_idx = ext2gd_alloc_inode(gd);
 554     }
 555
 556     // locality hinted alloc failed, try entire fs
 557     if (!valid_bmp_slot(free_ino_idx)) {
 558         free_ino_idx = ext2ino_alloc_slot(vsb, &gd);
 559     }
 560
 561     if (!valid_bmp_slot(free_ino_idx)) {
 562         return EDQUOT;
 563     }
 564
 565     inode = __create_inode(vsb, gd, free_ino_idx);
 566     if (!inode) {
 567         // what a shame!
 568         ext2gd_free_inode(gd, free_ino_idx);
 569         return EIO;
 570     }
 571
 572     memset(inode->ino, 0, sizeof(*inode->ino));
 573     fsblock_dirty(inode->buf);
 574
 575     *out = inode;
 576     return 0;
 577 }
 578
 579 static inline int
 580 __free_block_at(struct v_superblock *vsb, unsigned int block_pos)
 581 {
 582     int errno, gd_index;
 583     struct ext2_gdesc* gd;
 584     struct ext2_sbinfo * sb;
 585
 586     if (!block_pos) {
 587         return 0;
 588     }
 589
 590     block_pos = ext2_datablock(vsb, block_pos);
 591
 592     sb = EXT2_SB(vsb);
 593     gd_index = block_pos / sb->raw->s_blk_per_grp;
 594
 595     if ((errno = ext2gd_take_at(vsb, gd_index, &gd))) {
 596         return errno;
 597     }
 598
 599     assert(block_pos >= gd->base);
 600     ext2gd_free_block(gd, block_pos - gd->base);
 601
 602     ext2gd_put(gd);
 603     return 0;
 604 }
 605
 606 static int
 607 __free_recurisve_from(struct v_superblock *vsb, struct ext2_inode* inode,
 608                       struct walk_stack* stack, int depth)
 609 {
 610     bbuf_t tab;
 611     int idx, len, errno;
 612     u32_t* db_tab;
 613
 614     int ind_entries = 1 << inode->inds_lgents;
 615     int max_len[] = { 15, ind_entries, ind_entries, ind_entries };
 616
 617     u32_t* tables  = stack->tables;
 618     u32_t* indices = stack->indices;
 619
 620     if (depth > MAX_INDS_DEPTH || !tables[depth]) {
 621         return 0;
 622     }
 623
 624     idx = indices[depth];
 625     len = max_len[depth];
 626     tab = fsblock_get(vsb, ext2_datablock(vsb, tables[depth]));
 627
 628     if (blkbuf_errbuf(tab)) {
 629         return EIO;
 630     }
 631
 632     db_tab = blkbuf_data(tab);
 633     if (depth == 0) {
 634         int offset = offsetof(struct ext2b_inode, i_block_arr);
 635         db_tab = offset(db_tab, offset);
 636     }
 637
 638     errno = 0;
 639     indices[depth] = 0;
 640
 641     for (; idx < len; idx++)
 642     {
 643         u32_t db_id = db_tab[idx];
 644
 645         if (!db_id) {
 646             continue;
 647         }
 648
 649         if (depth >= MAX_INDS_DEPTH) {
 650             goto cont;
 651         }
 652
 653         tables[depth] = db_id;
 654         errno = __free_recurisve_from(vsb, inode, stack, depth + 1);
 655         if (errno) {
 656             break;
 657         }
 658
 659 cont:
 660         __free_block_at(vsb, db_id);
 661         db_tab[idx] = 0;
 662     }
 663
 664     fsblock_dirty(tab);
 665     fsblock_put(tab);
 666     return errno;
 667 }
 668
 669 int
 670 ext2ino_free(struct v_inode* inode)
 671 {
 672     int errno = 0;
 673     unsigned int ino_slot;
 674     struct ext2_inode*  e_ino;
 675     struct ext2_gdesc*  e_gd;
 676     struct ext2b_inode* b_ino;
 677     struct ext2_sbinfo* sb;
 678
 679     sb    = EXT2_SB(inode->sb);
 680     e_ino = EXT2_INO(inode);
 681     b_ino = e_ino->ino;
 682     e_gd  = e_ino->blk_grp;
 683
 684     assert_fs(b_ino->i_lnk_cnt > 0);
 685     fsblock_dirty(e_ino->buf);
 686
 687     b_ino->i_lnk_cnt--;
 688     if (b_ino->i_lnk_cnt >= 1) {
 689         return 0;
 690     }
 691
 692     ext2ino_resizing(inode, 0);
 693
 694     ino_slot = e_ino->ino_id;
 695     ino_slot = to_fsblock_id(ino_slot - e_gd->base);
 696     ext2gd_free_inode(e_ino->blk_grp, ino_slot);
 697
 698     __destruct_ext2_inode(e_ino);
 699
 700     inode->data = NULL;
 701
 702     return errno;
 703 }
 704
 705 static void
 706 __update_inode_access_metadata(struct ext2b_inode* b_ino,
 707                         struct v_inode* inode)
 708 {
 709     b_ino->i_ctime = inode->ctime;
 710     b_ino->i_atime = inode->atime;
 711     b_ino->i_mtime = inode->mtime;
 712 }
 713
 714 static inline void
 715 __update_inode_size(struct v_inode* inode, size_t size)
 716 {
 717     struct ext2b_inode* b_ino;
 718     struct ext2_inode*  e_ino;
 719     struct ext2_sbinfo* sb;
 720
 721     sb    = EXT2_SB(inode->sb);
 722     e_ino = EXT2_INO(inode);
 723     b_ino = e_ino->ino;
 724
 725     e_ino->isize = size;
 726
 727     if (ext2_feature(inode->sb, FEAT_LARGE_FILE)) {
 728         b_ino->i_size_l32 = (unsigned int)size;
 729         b_ino->i_size_h32 = (unsigned int)((u64_t)size >> 32);
 730     }
 731     else {
 732         b_ino->i_size  = size;
 733     }
 734
 735     b_ino->i_blocks = e_ino->nr_fsblks * (sb->block_size / 512);
 736     fsblock_dirty(e_ino->buf);
 737 }
 738
 739 int
 740 ext2ino_make(struct v_superblock* vsb, unsigned int itype,
 741              struct ext2_inode* hint, struct v_inode** out)
 742 {
 743     int errno = 0;
 744     struct ext2_inode* e_ino;
 745     struct ext2b_inode* b_ino;
 746     struct v_inode* inode;
 747
 748     errno = ext2ino_alloc(vsb, hint, &e_ino);
 749     if (errno) {
 750         return errno;
 751     }
 752
 753     b_ino = e_ino->ino;
 754     inode = vfs_i_alloc(vsb);
 755
 756     __ext2ino_fill_common(inode, e_ino->ino_id);
 757
 758     __update_inode_access_metadata(b_ino, inode);
 759     b_ino->i_mode  = __translate_vfs_itype(itype);
 760
 761     fsapi_inode_settype(inode, itype);
 762     fsapi_inode_complete(inode, e_ino);
 763
 764     *out = inode;
 765     return errno;
 766 }
 767
 768 int
 769 ext2_create(struct v_inode* this, struct v_dnode* dnode, unsigned int itype)
 770 {
 771     int errno;
 772     struct v_inode* created;
 773
 774     errno = ext2ino_make(this->sb, itype, EXT2_INO(this), &created);
 775     if (errno) {
 776         return errno;
 777     }
 778
 779     return ext2_link(created, dnode);
 780 }
 781
 782 int
 783 ext2_link(struct v_inode* this, struct v_dnode* new_name)
 784 {
 785     int errno = 0;
 786     struct v_inode* parent;
 787     struct ext2_inode* e_ino;
 788     struct ext2_dnode* e_dno;
 789     struct ext2b_dirent dirent;
 790
 791     e_ino  = EXT2_INO(this);
 792     parent = fsapi_dnode_parent(new_name);
 793
 794     ext2dr_setup_dirent(&dirent, this, &new_name->name);
 795     ext2ino_linkto(e_ino, &dirent);
 796
 797     errno = ext2dr_insert(parent, &dirent, &e_dno);
 798     if (errno) {
 799         goto done;
 800     }
 801
 802     new_name->data = e_dno;
 803     vfs_assign_inode(new_name, this);
 804
 805     // linking a dnode to parent could result new data block allocated
 806     ext2_sync_inode(parent);
 807
 808 done:
 809     return errno;
 810 }
 811
 812 int
 813 ext2_unlink(struct v_inode* this, struct v_dnode* name)
 814 {
 815     int errno = 0;
 816     struct ext2_inode* e_ino;
 817     struct ext2_dnode* e_dno;
 818
 819     e_ino = EXT2_INO(this);
 820     e_dno = EXT2_DNO(name);
 821
 822     assert_fs(e_dno);
 823     assert_fs(e_dno->self.dirent->inode == e_ino->ino_id);
 824
 825     errno = ext2dr_remove(e_dno);
 826     if (errno) {
 827         return errno;
 828     }
 829
 830     // unlink a dnode from parent will not free the allocated data blocks
 831     //  rather, it leads to fragmentation
 832     return ext2ino_free(this);
 833 }
 834
 835 void
 836 ext2ino_update(struct v_inode* inode)
 837 {
 838     struct ext2_inode* e_ino;
 839
 840     e_ino = EXT2_INO(inode);
 841     __update_inode_access_metadata(e_ino->ino, inode);
 842
 843     fsblock_dirty(e_ino->buf);
 844 }
 845
 846 /* ******************* Data Blocks ******************* */
 847
 848 static inline void
 849 __walkstate_set_stack(struct walk_state* state, int depth,
 850                       bbuf_t tab, unsigned int index)
 851 {
 852     state->stack.tables[depth] = fsblock_id(tab);
 853     state->stack.indices[depth] = index;
 854 }
 855
 856 #define WALKMODE_ALLOC  0b01
 857 #define WALKMODE_NOBTLB 0b10
 858
 859 /**
 860  * @brief Walk the indrection chain given the position of data block
 861  *        relative to the inode. Upon completed, walk_state will be
 862  *        populated with result. On error, walk_state is untouched.
 863  *
 864  *        Note, the result will always be one above the stopping level.
 865  *        That means, if your pos is pointed directly to file-content block
 866  *        (i.e., a leaf block), then the state is the indirect block that
 867  *        containing the ID of that leaf block.
 868  *
 869  *        Two modes can be specified to alter the walk process:
 870  *
 871  *        WALKMODE_ALLOC
 872  *          resolve any absence encountered
 873  *          during the walk by allocating and chaining indirect block
 874  *
 875  *        WALKMODE_NOBTLB
 876  *          Ignore the cached result, always perform a complete walk.
 877  *          This does not by pass the cache entirely, lower level caches
 878  *          like block buffer (blkio request cache) will be used transparently
 879  *
 880  * @param inode     inode to walk
 881  * @param pos       flattened data block position to be located
 882  * @param state     contain the walk result
 883  * @param mode      walk mode
 884  * @return int
 885  */
 886 static int
 887 __walk_indirects(struct v_inode* inode, unsigned int pos,
 888                  struct walk_state* state, int mode)
 889 {
 890     int errno;
 891     int inds, stride, shifts, level;
 892     unsigned int *slotref, index, next, mask;
 893     struct ext2_inode* e_inode;
 894     struct ext2b_inode* b_inode;
 895     struct v_superblock* vsb;
 896     bbuf_t table, next_table;
 897     bool alloc;
 898
 899     e_inode = EXT2_INO(inode);
 900     b_inode = e_inode->ino;
 901     vsb = inode->sb;
 902     level = 0;
 903     alloc = (mode & WALKMODE_ALLOC) && !EXT2_SB(vsb)->read_only;
 904
 905     if (pos < 12) {
 906         index = pos;
 907         slotref = &b_inode->i_block_arr[pos];
 908         table = fsblock_take(e_inode->buf);
 909         inds = 0;
 910         goto _return;
 911     }
 912
 913     pos -= 12;
 914     stride = e_inode->inds_lgents;
 915     if (!(pos >> stride)) {
 916         inds = 1;
 917     }
 918     else if (!(pos >> (stride * 2))) {
 919         inds = 2;
 920     }
 921     else if (!(pos >> (stride * 3))) {
 922         inds = 3;
 923     }
 924     else {
 925         fail("unrealistic block pos");
 926     }
 927
 928     // bTLB cache the last level indirect block
 929     if (!(mode & WALKMODE_NOBTLB) && (table = __btlb_hit(e_inode, pos))) {
 930         level = inds;
 931         index = pos & ((1 << stride) - 1);
 932         slotref = &block_buffer(table, u32_t)[index];
 933         goto _return;
 934     }
 935
 936     shifts = stride * (inds - 1);
 937     mask = ((1 << stride) - 1) << shifts;
 938
 939     index   = 12 + inds - 1;
 940     slotref = &b_inode->i_block.inds[inds - 1];
 941     table   = fsblock_take(e_inode->buf);
 942
 943     for (; level < inds; level++)
 944     {
 945         __walkstate_set_stack(state, level, table, index);
 946
 947         next = *slotref;
 948         if (!next) {
 949             if (!alloc) {
 950                 goto _return;
 951             }
 952
 953             if ((errno = ext2db_alloc(inode, &next_table))) {
 954                 fsblock_put(table);
 955                 return errno;
 956             }
 957
 958             *slotref = fsblock_id(next_table);
 959             fsblock_dirty(table);
 960         }
 961         else {
 962             next_table = fsblock_get(vsb, next);
 963         }
 964
 965         fsblock_put(table);
 966         table = next_table;
 967
 968         if (blkbuf_errbuf(table)) {
 969             return EIO;
 970         }
 971
 972         assert(shifts >= 0);
 973
 974         index = (pos & mask) >> shifts;
 975         slotref = &block_buffer(table, u32_t)[index];
 976
 977         shifts -= stride;
 978         mask  = mask >> stride;
 979     }
 980
 981     __btlb_insert(e_inode, pos, table);
 982
 983 _return:
 984     assert(blkbuf_refcounts(table) >= 1);
 985     assert_fs(table);
 986     assert_fs(slotref);
 987
 988     state->slot_ref = slotref;
 989     state->table = table;
 990     state->level = level;
 991     state->indirections = inds;
 992
 993     __walkstate_set_stack(state, level, table, index);
 994
 995     return 0;
 996 }
 997
 998 bbuf_t
 999 ext2db_get(struct v_inode* inode, unsigned int data_pos)
1000 {
1001     int errno;
1002     unsigned int blkid;
1003     struct walk_state state;
1004
1005     ext2walk_init_state(&state);
1006
1007     errno = __walk_indirects(inode, data_pos, &state, 0);
1008     if (errno) {
1009         return (bbuf_t)INVL_BUFFER;
1010     }
1011
1012     blkid = *state.slot_ref;
1013
1014     ext2walk_free_state(&state);
1015
1016     if (!blkid) {
1017         return NULL;
1018     }
1019
1020     return fsblock_get(inode->sb, blkid);
1021 }
1022
1023 int
1024 ext2db_acquire(struct v_inode* inode, unsigned int data_pos, bbuf_t* out)
1025 {
1026     int errno = 0;
1027     bbuf_t buf;
1028     unsigned int block_id;
1029     struct walk_state state;
1030
1031     ext2walk_init_state(&state);
1032
1033     errno = __walk_indirects(inode, data_pos, &state, WALKMODE_ALLOC);
1034     if (errno) {
1035         return errno;
1036     }
1037
1038     block_id = *state.slot_ref;
1039     if (block_id) {
1040         buf = fsblock_get(inode->sb, block_id);
1041         goto done;
1042     }
1043
1044     errno = ext2db_alloc(inode, &buf);
1045     if (errno) {
1046         ext2walk_free_state(&state);
1047         return errno;
1048     }
1049
1050     *state.slot_ref = fsblock_id(buf);
1051     fsblock_dirty(state.table);
1052
1053 done:
1054     ext2walk_free_state(&state);
1055
1056     if (blkbuf_errbuf(buf)) {
1057         return EIO;
1058     }
1059
1060     *out = buf;
1061     return 0;
1062 }
1063
1064 int
1065 ext2db_alloc(struct v_inode* inode, bbuf_t* out)
1066 {
1067     int next_free;
1068     struct ext2_gdesc* gd;
1069     struct ext2_inode* e_inode;
1070     struct v_superblock* vsb;
1071
1072     next_free = ALLOC_FAIL;
1073     e_inode = EXT2_INO(inode);
1074     vsb = inode->sb;
1075
1076     gd = e_inode->blk_grp;
1077     next_free = ext2gd_alloc_block(gd);
1078
1079     // locality alloc failed, try entire fs
1080     if (!valid_bmp_slot(next_free)) {
1081         next_free = ext2db_alloc_slot(vsb, &gd);
1082     }
1083
1084     if (!valid_bmp_slot(next_free)) {
1085         return EDQUOT;
1086     }
1087
1088     next_free += gd->base;
1089     next_free = ext2_datablock(vsb, next_free);
1090
1091     bbuf_t buf = fsblock_get(vsb, next_free);
1092     if (blkbuf_errbuf(buf)) {
1093         return EIO;
1094     }
1095
1096     e_inode->nr_fsblks++;
1097     *out = buf;
1098     return 0;
1099 }
1100
1101 void
1102 ext2db_free_pos(struct v_inode* inode, unsigned int block_pos)
1103 {
1104     struct ext2_inode* e_inode;
1105     struct ext2_gdesc* gd;
1106
1107     e_inode = EXT2_INO(inode);
1108     gd = e_inode->blk_grp;
1109
1110     assert(block_pos >= gd->base);
1111
1112     block_pos -= gd->base;
1113
1114     ext2gd_free_block(gd, block_pos);
1115 }
1116
1117 int
1118 ext2db_free(struct v_inode* inode, bbuf_t buf)
1119 {
1120     assert(blkbuf_not_shared(buf));
1121
1122     ext2db_free_pos(inode, blkbuf_id(buf));
1123     fsblock_put(buf);
1124
1125     return 0;
1126 }
1127
1128 int
1129 ext2ino_resizing(struct v_inode* inode, size_t new_size)
1130 {
1131     int errno;
1132     unsigned int pos;
1133     size_t oldsize;
1134     struct walk_state state;
1135     struct ext2_inode*  e_ino;
1136     struct ext2b_inode* b_ino;
1137
1138     e_ino = EXT2_INO(inode);
1139     b_ino = e_ino->ino;
1140     oldsize = e_ino->isize;
1141
1142     if (oldsize == new_size) {
1143         return 0;
1144     }
1145
1146     __update_inode_size(inode, new_size);
1147
1148     if (check_symlink_node(inode)) {
1149         return 0;
1150     }
1151
1152     if (oldsize < new_size) {
1153         return 0;
1154     }
1155
1156     ext2walk_init_state(&state);
1157
1158     pos   = new_size / fsapi_block_size(inode->sb);
1159     errno = __walk_indirects(inode, pos, &state, WALKMODE_NOBTLB);
1160     if (errno) {
1161         return errno;
1162     }
1163
1164     errno = __free_recurisve_from(inode->sb, e_ino, &state.stack, 0);
1165
1166     ext2walk_free_state(&state);
1167     return errno;
1168 }