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 void
 132 ext2db_itbegin(struct ext2_iterator* iter, struct v_inode* inode)
 133 {
 134     struct ext2_inode* e_ino;
 135
 136     e_ino = EXT2_INO(inode);
 137     *iter = (struct ext2_iterator){
 138         .pos = 0,
 139         .inode = inode,
 140         .blksz = inode->sb->blksize,
 141         .end_pos = ICEIL(e_ino->isize, inode->sb->blksize)
 142     };
 143 }
 144
 145 void
 146 ext2db_itreset(struct ext2_iterator* iter)
 147 {
 148     if (likely(iter->sel_buf)) {
 149         fsblock_put(iter->sel_buf);
 150         iter->sel_buf = NULL;
 151     }
 152
 153     iter->pos = 0;
 154 }
 155
 156 int
 157 ext2db_itffw(struct ext2_iterator* iter, int count)
 158 {
 159     iter->pos += count;
 160     return count;
 161 }
 162
 163 void
 164 ext2db_itend(struct ext2_iterator* iter)
 165 {
 166     if (likely(iter->sel_buf)) {
 167         fsblock_put(iter->sel_buf);
 168         iter->sel_buf = NULL;
 169     }
 170 }
 171
 172 bool
 173 ext2db_itnext(struct ext2_iterator* iter)
 174 {
 175     bbuf_t buf;
 176
 177     if (unlikely(iter->has_error)) {
 178         return false;
 179     }
 180
 181     if (unlikely(iter->pos > iter->end_pos)) {
 182         return false;
 183     }
 184
 185     if (likely(iter->sel_buf)) {
 186         fsblock_put(iter->sel_buf);
 187     }
 188
 189     buf = ext2db_get(iter->inode, iter->pos);
 190     iter->sel_buf = buf;
 191
 192     if (!buf || !ext2_itcheckbuf(iter)) {
 193         return false;
 194     }
 195
 196     iter->pos++;
 197     iter->data = blkbuf_data(buf);
 198
 199     return true;
 200 }
 201
 202 void
 203 ext2ino_init(struct v_superblock* vsb, struct v_inode* inode)
 204 {
 205     // Placeholder, to make vsb happy
 206 }
 207
 208 static void
 209 __destruct_ext2_inode(struct ext2_inode* e_inode)
 210 {
 211     __btlb_flushall(e_inode);
 212
 213     fsblock_put(e_inode->ind_ord1);
 214     fsblock_put(e_inode->buf);
 215
 216     ext2gd_put(e_inode->blk_grp);
 217
 218     vfree_safe(e_inode->symlink);
 219     vfree(e_inode->btlb);
 220     vfree(e_inode);
 221 }
 222
 223 static void
 224 ext2_destruct_inode(struct v_inode* inode)
 225 {
 226     struct ext2_inode* e_inode;
 227
 228     e_inode = EXT2_INO(inode);
 229
 230     assert(e_inode);
 231     __destruct_ext2_inode(e_inode);
 232 }
 233
 234 static inline void
 235 __ext2ino_fill_common(struct v_inode* inode, ino_t ino_id)
 236 {
 237     fsapi_inode_setid(inode, ino_id, ino_id);
 238     fsapi_inode_setfops(inode, &ext2_file_ops);
 239     fsapi_inode_setops(inode, &ext2_inode_ops);
 240     fsapi_inode_setdector(inode, ext2_destruct_inode);
 241 }
 242
 243
 244 static unsigned int
 245 __translate_vfs_itype(unsigned int v_itype)
 246 {
 247     unsigned int e_itype = IMODE_IFREG;
 248
 249     if (v_itype == VFS_IFFILE) {
 250         e_itype = IMODE_IFREG;
 251     }
 252     else if (check_itype(v_itype, VFS_IFDIR)) {
 253         e_itype = IMODE_IFDIR;
 254         e_itype |= IMODE_UEX;
 255     }
 256     else if (check_itype(v_itype, VFS_IFSEQDEV)) {
 257         e_itype = IMODE_IFCHR;
 258     }
 259     else if (check_itype(v_itype, VFS_IFVOLDEV)) {
 260         e_itype = IMODE_IFBLK;
 261     }
 262
 263     if (check_itype(v_itype, VFS_IFSYMLINK)) {
 264         e_itype |= IMODE_IFLNK;
 265     }
 266
 267     // FIXME we keep this until we have our own user manager
 268     e_itype |= (IMODE_URD | IMODE_GRD | IMODE_ORD);
 269     return e_itype;
 270 }
 271
 272 int
 273 ext2ino_fill(struct v_inode* inode, ino_t ino_id)
 274 {
 275     struct ext2_sbinfo* sb;
 276     struct ext2_inode* e_ino;
 277     struct v_superblock* vsb;
 278     struct ext2b_inode* b_ino;
 279     unsigned int type = VFS_IFFILE;
 280     int errno = 0;
 281
 282     vsb = inode->sb;
 283     sb = EXT2_SB(vsb);
 284
 285     if ((errno = ext2ino_get(vsb, ino_id, &e_ino))) {
 286         return errno;
 287     }
 288
 289     b_ino = e_ino->ino;
 290     ino_id = e_ino->ino_id;
 291
 292     fsapi_inode_setsize(inode, e_ino->isize);
 293
 294     fsapi_inode_settime(inode, b_ino->i_ctime,
 295                                b_ino->i_mtime,
 296                                b_ino->i_atime);
 297
 298     __ext2ino_fill_common(inode, ino_id);
 299
 300     if (check_itype(b_ino->i_mode, IMODE_IFLNK)) {
 301         type = VFS_IFSYMLINK;
 302     }
 303     else if (check_itype(b_ino->i_mode, IMODE_IFDIR)) {
 304         type = VFS_IFDIR;
 305     }
 306     else if (check_itype(b_ino->i_mode, IMODE_IFCHR)) {
 307         type = VFS_IFSEQDEV;
 308     }
 309     else if (check_itype(b_ino->i_mode, IMODE_IFBLK)) {
 310         type = VFS_IFVOLDEV;
 311     }
 312
 313     fsapi_inode_settype(inode, type);
 314
 315     fsapi_inode_complete(inode, e_ino);
 316
 317     return 0;
 318 }
 319
 320 static int
 321 __get_group_desc(struct v_superblock* vsb, int ino,
 322                  struct ext2_gdesc** gd_out)
 323 {
 324     unsigned int blkgrp_id;
 325     struct ext2_sbinfo* sb;
 326
 327     sb = EXT2_SB(vsb);
 328
 329     blkgrp_id = to_fsblock_id(ino) / sb->raw->s_ino_per_grp;
 330     return ext2gd_take(vsb, blkgrp_id, gd_out);
 331 }
 332
 333 static struct ext2b_inode*
 334 __get_raw_inode(struct v_superblock* vsb, struct ext2_gdesc* gd,
 335                 bbuf_t* buf_out, int ino_index)
 336 {
 337     bbuf_t ino_tab;
 338     struct ext2_sbinfo* sb;
 339     struct ext2b_inode* b_inode;
 340     unsigned int ino_tab_sel, ino_tab_off, tab_partlen;
 341
 342     assert(buf_out);
 343
 344     sb = gd->sb;
 345     tab_partlen = sb->block_size / sb->raw->s_ino_size;
 346     ino_tab_sel = ino_index / tab_partlen;
 347     ino_tab_off = ino_index % tab_partlen;
 348
 349     ino_tab = fsblock_get(vsb, gd->info->bg_ino_tab + ino_tab_sel);
 350     if (blkbuf_errbuf(ino_tab)) {
 351         return NULL;
 352     }
 353
 354     b_inode = (struct ext2b_inode*)blkbuf_data(ino_tab);
 355     b_inode = &b_inode[ino_tab_off];
 356
 357     *buf_out = ino_tab;
 358
 359     return b_inode;
 360 }
 361
 362 static struct ext2_inode*
 363 __create_inode(struct v_superblock* vsb, struct ext2_gdesc* gd, int ino_index)
 364 {
 365     bbuf_t ino_tab;
 366     struct ext2_sbinfo* sb;
 367     struct ext2b_inode* b_inode;
 368     struct ext2_inode* inode;
 369     unsigned int ind_ents;
 370     size_t inds_blks;
 371
 372     sb = gd->sb;
 373     b_inode = __get_raw_inode(vsb, gd, &ino_tab, ino_index);
 374     if (!b_inode) {
 375         return NULL;
 376     }
 377
 378     inode            = vzalloc(sizeof(*inode));
 379     inode->btlb      = vzalloc(sizeof(struct ext2_btlb));
 380     inode->buf       = ino_tab;
 381     inode->ino       = b_inode;
 382     inode->blk_grp   = gd;
 383     inode->isize     = b_inode->i_size;
 384
 385     if (ext2_feature(vsb, FEAT_LARGE_FILE)) {
 386         inode->isize |= (size_t)((u64_t)(b_inode->i_size_h32) << 32);
 387     }
 388
 389     if (b_inode->i_blocks) {
 390         inds_blks  = (size_t)b_inode->i_blocks;
 391         inds_blks -= ICEIL(inode->isize, 512);
 392         inds_blks /= (sb->block_size / 512);
 393
 394         inode->indirect_blocks = inds_blks;
 395     }
 396
 397     ind_ents = sb->block_size / sizeof(int);
 398     assert(is_pot(ind_ents));
 399
 400     inode->inds_lgents = ilog2(ind_ents);
 401     inode->ino_id = gd->ino_base + to_ext2ino_id(ino_index);
 402
 403     return inode;
 404 }
 405
 406 int
 407 ext2ino_get_fast(struct v_superblock* vsb,
 408                  unsigned int ino, struct ext2_fast_inode* fast_ino)
 409 {
 410     int errno;
 411     bbuf_t ino_tab;
 412     struct ext2_gdesc* gd;
 413     struct ext2_sbinfo* sb;
 414     struct ext2b_inode* b_inode;
 415     unsigned int ino_rel_id;
 416
 417     sb = EXT2_SB(vsb);
 418     errno = __get_group_desc(vsb, ino, &gd);
 419     if (errno) {
 420         return errno;
 421     }
 422
 423     ino_rel_id  = to_fsblock_id(ino) % sb->raw->s_ino_per_grp;
 424     b_inode = __get_raw_inode(vsb, gd, &ino_tab, ino_rel_id);
 425
 426     fast_ino->buf = ino_tab;
 427     fast_ino->ino = b_inode;
 428
 429     return 0;
 430 }
 431
 432 int
 433 ext2ino_get(struct v_superblock* vsb,
 434             unsigned int ino, struct ext2_inode** out)
 435 {
 436     struct ext2_sbinfo* sb;
 437     struct ext2_inode* inode;
 438     struct ext2_gdesc* gd;
 439     struct ext2b_inode* b_inode;
 440     unsigned int ino_rel_id;
 441     unsigned int tab_partlen;
 442     unsigned int ind_ents, prima_ind;
 443     int errno = 0;
 444
 445     sb = EXT2_SB(vsb);
 446
 447     if ((errno = __get_group_desc(vsb, ino, &gd))) {
 448         return errno;
 449     }
 450
 451     ino_rel_id  = to_fsblock_id(ino) % sb->raw->s_ino_per_grp;
 452     inode = __create_inode(vsb, gd, ino_rel_id);
 453     if (!inode) {
 454         return EIO;
 455     }
 456
 457     b_inode = inode->ino;
 458     prima_ind = b_inode->i_block.ind1;
 459     *out = inode;
 460
 461     if (!prima_ind) {
 462         return errno;
 463     }
 464
 465     inode->ind_ord1 = fsblock_get(vsb, prima_ind);
 466     if (blkbuf_errbuf(inode->ind_ord1)) {
 467         vfree(inode->btlb);
 468         vfree(inode);
 469         *out = NULL;
 470         return EIO;
 471     }
 472
 473     return errno;
 474 }
 475
 476 int
 477 ext2ino_alloc(struct v_superblock* vsb,
 478                  struct ext2_inode* hint, struct ext2_inode** out)
 479 {
 480     int free_ino_idx;
 481     struct ext2_gdesc* gd;
 482     struct ext2_inode* inode;
 483
 484     free_ino_idx = ALLOC_FAIL;
 485     if (hint) {
 486         gd = hint->blk_grp;
 487         free_ino_idx = ext2gd_alloc_inode(gd);
 488     }
 489
 490     // locality hinted alloc failed, try entire fs
 491     if (!valid_bmp_slot(free_ino_idx)) {
 492         free_ino_idx = ext2ino_alloc_slot(vsb, &gd);
 493     }
 494
 495     if (!valid_bmp_slot(free_ino_idx)) {
 496         return EDQUOT;
 497     }
 498
 499     inode = __create_inode(vsb, gd, free_ino_idx);
 500     if (!inode) {
 501         // what a shame!
 502         ext2gd_free_inode(gd, free_ino_idx);
 503         return EIO;
 504     }
 505
 506     memset(inode->ino, 0, sizeof(*inode->ino));
 507     fsblock_dirty(inode->buf);
 508
 509     *out = inode;
 510     return 0;
 511 }
 512
 513 static inline int
 514 __free_block_at(struct v_superblock *vsb, unsigned int block_pos)
 515 {
 516     int errno, gd_index;
 517     struct ext2_gdesc* gd;
 518     struct ext2_sbinfo * sb;
 519
 520     if (!block_pos) {
 521         return 0;
 522     }
 523
 524     block_pos = ext2_datablock(vsb, block_pos);
 525
 526     sb = EXT2_SB(vsb);
 527     gd_index = block_pos / sb->raw->s_blk_per_grp;
 528
 529     if ((errno = ext2gd_take(vsb, gd_index, &gd))) {
 530         return errno;
 531     }
 532
 533     assert(block_pos >= gd->base);
 534     ext2gd_free_block(gd, block_pos - gd->base);
 535
 536     ext2gd_put(gd);
 537     return 0;
 538 }
 539
 540 static int
 541 __free_recurisve_from(struct v_superblock *vsb, struct ext2_inode* inode,
 542                       struct walk_stack* stack, int depth)
 543 {
 544     bbuf_t tab;
 545     int idx, len, errno;
 546     u32_t* db_tab;
 547
 548     int ind_entries = 1 << inode->inds_lgents;
 549     int max_len[] = { 15, ind_entries, ind_entries, ind_entries };
 550
 551     u32_t* tables  = stack->tables;
 552     u32_t* indices = stack->indices;
 553
 554     if (depth > MAX_INDS_DEPTH || !tables[depth]) {
 555         return 0;
 556     }
 557
 558     idx = indices[depth];
 559     len = max_len[depth];
 560     tab = fsblock_get(vsb, ext2_datablock(vsb, tables[depth]));
 561
 562     if (blkbuf_errbuf(tab)) {
 563         return EIO;
 564     }
 565
 566     db_tab = blkbuf_data(tab);
 567     if (depth == 0) {
 568         int offset = offsetof(struct ext2b_inode, i_block_arr);
 569         db_tab = offset(db_tab, offset);
 570     }
 571
 572     errno = 0;
 573     indices[depth] = 0;
 574
 575     for (; idx < len; idx++)
 576     {
 577         u32_t db_id = db_tab[idx];
 578
 579         if (!db_id) {
 580             continue;
 581         }
 582
 583         if (depth >= MAX_INDS_DEPTH) {
 584             goto cont;
 585         }
 586
 587         tables[depth] = db_id;
 588         errno = __free_recurisve_from(vsb, inode, stack, depth + 1);
 589         if (errno) {
 590             break;
 591         }
 592
 593 cont:
 594         __free_block_at(vsb, db_id);
 595         db_tab[idx] = 0;
 596     }
 597
 598     fsblock_dirty(tab);
 599     fsblock_put(tab);
 600     return errno;
 601 }
 602
 603 int
 604 ext2ino_free(struct v_inode* inode)
 605 {
 606     int errno = 0;
 607     unsigned int ino_slot;
 608     struct ext2_inode*  e_ino;
 609     struct ext2_gdesc*  e_gd;
 610     struct ext2b_inode* b_ino;
 611     struct ext2_sbinfo* sb;
 612
 613     sb    = EXT2_SB(inode->sb);
 614     e_ino = EXT2_INO(inode);
 615     b_ino = e_ino->ino;
 616     e_gd  = e_ino->blk_grp;
 617
 618     assert_fs(b_ino->i_lnk_cnt > 0);
 619     fsblock_dirty(e_ino->buf);
 620
 621     b_ino->i_lnk_cnt--;
 622     if (b_ino->i_lnk_cnt >= 1) {
 623         return 0;
 624     }
 625
 626     ext2ino_resizing(inode, 0);
 627
 628     ino_slot = e_ino->ino_id;
 629     ino_slot = to_fsblock_id(ino_slot - e_gd->base);
 630     ext2gd_free_inode(e_ino->blk_grp, ino_slot);
 631
 632     __destruct_ext2_inode(e_ino);
 633
 634     inode->data = NULL;
 635
 636     return errno;
 637 }
 638
 639 static void
 640 __update_inode_access_metadata(struct ext2b_inode* b_ino,
 641                         struct v_inode* inode)
 642 {
 643     b_ino->i_ctime = inode->ctime;
 644     b_ino->i_atime = inode->atime;
 645     b_ino->i_mtime = inode->mtime;
 646 }
 647
 648 static inline void
 649 __update_inode_size(struct v_inode* inode, size_t size)
 650 {
 651     struct ext2b_inode* b_ino;
 652     struct ext2_inode*  e_ino;
 653
 654     e_ino = EXT2_INO(inode);
 655     b_ino = e_ino->ino;
 656
 657     e_ino->isize = size;
 658
 659     if (ext2_feature(inode->sb, FEAT_LARGE_FILE)) {
 660         b_ino->i_size_l32 = (unsigned int)size;
 661         b_ino->i_size_h32 = (unsigned int)((u64_t)size >> 32);
 662     }
 663     else {
 664         b_ino->i_size  = size;
 665     }
 666
 667     b_ino->i_blocks = ICEIL(size, 512);
 668     b_ino->i_blocks += e_ino->indirect_blocks;
 669 }
 670
 671 int
 672 ext2ino_make(struct v_superblock* vsb, unsigned int itype,
 673              struct ext2_inode* hint, struct v_inode** out)
 674 {
 675     int errno = 0;
 676     struct ext2_inode* e_ino;
 677     struct ext2b_inode* b_ino;
 678     struct v_inode* inode;
 679
 680     errno = ext2ino_alloc(vsb, hint, &e_ino);
 681     if (errno) {
 682         return errno;
 683     }
 684
 685     b_ino = e_ino->ino;
 686     inode = vfs_i_alloc(vsb);
 687
 688     __ext2ino_fill_common(inode, e_ino->ino_id);
 689
 690     __update_inode_access_metadata(b_ino, inode);
 691     b_ino->i_mode  = __translate_vfs_itype(itype);
 692
 693     fsapi_inode_settype(inode, itype);
 694     fsapi_inode_complete(inode, e_ino);
 695
 696     *out = inode;
 697     return errno;
 698 }
 699
 700 int
 701 ext2_create(struct v_inode* this, struct v_dnode* dnode, unsigned int itype)
 702 {
 703     int errno;
 704     struct v_inode* created;
 705
 706     errno = ext2ino_make(this->sb, itype, EXT2_INO(this), &created);
 707     if (errno) {
 708         return errno;
 709     }
 710
 711     return ext2_link(created, dnode);
 712 }
 713
 714 int
 715 ext2_link(struct v_inode* this, struct v_dnode* new_name)
 716 {
 717     int errno = 0;
 718     struct v_inode* parent;
 719     struct ext2_inode* e_ino;
 720     struct ext2_dnode* e_dno;
 721     struct ext2b_dirent dirent;
 722
 723     e_ino  = EXT2_INO(this);
 724     parent = fsapi_dnode_parent(new_name);
 725
 726     ext2dr_setup_dirent(&dirent, this, &new_name->name);
 727     ext2ino_linkto(e_ino, &dirent);
 728
 729     errno = ext2dr_insert(parent, &dirent, &e_dno);
 730     if (errno) {
 731         goto done;
 732     }
 733
 734     new_name->data = e_dno;
 735     vfs_assign_inode(new_name, this);
 736
 737 done:
 738     return errno;
 739 }
 740
 741 int
 742 ext2_unlink(struct v_inode* this, struct v_dnode* name)
 743 {
 744     int errno = 0;
 745     struct ext2_inode* e_ino;
 746     struct ext2_dnode* e_dno;
 747
 748     e_ino = EXT2_INO(this);
 749     e_dno = EXT2_DNO(name);
 750
 751     assert_fs(e_dno);
 752     assert_fs(e_dno->self.dirent->inode == e_ino->ino_id);
 753
 754     errno = ext2dr_remove(e_dno);
 755     if (errno) {
 756         return errno;
 757     }
 758
 759     return ext2ino_free(this);
 760 }
 761
 762 void
 763 ext2ino_update(struct v_inode* inode)
 764 {
 765     struct ext2_inode* e_ino;
 766
 767     e_ino = EXT2_INO(inode);
 768     __update_inode_access_metadata(e_ino->ino, inode);
 769
 770     fsblock_dirty(e_ino->buf);
 771 }
 772
 773 /* ******************* Data Blocks ******************* */
 774
 775 static inline void
 776 __walkstate_set_stack(struct walk_state* state, int depth,
 777                       bbuf_t tab, unsigned int index)
 778 {
 779     state->stack.tables[depth] = fsblock_id(tab);
 780     state->stack.indices[depth] = index;
 781 }
 782
 783 /**
 784  * @brief Walk the indrection chain given the position of data block
 785  *        relative to the inode. Upon completed, walk_state will be
 786  *        populated with result. On error, walk_state is untouched.
 787  *
 788  *        Note, the result will always be one above the stopping level.
 789  *        That means, if your pos is pointed directly to file-content block
 790  *        (i.e., a leaf block), then the state is the indirect block that
 791  *        containing the ID of that leaf block.
 792  *
 793  *        If `resolve` is set, it will resolve any absence encountered
 794  *        during the walk by allocating and chaining indirect block.
 795  *        It require the file system is mounted writable.
 796  *
 797  * @param inode     inode to walk
 798  * @param pos       flattened data block position to be located
 799  * @param state     contain the walk result
 800  * @param resolve   whether to auto allocate the indirection structure during
 801  *                  walk if `pos` is not exist.
 802  * @return int
 803  */
 804 static int
 805 __walk_indirects(struct v_inode* inode, unsigned int pos,
 806                  struct walk_state* state, bool resolve, bool full_walk)
 807 {
 808     int errno;
 809     int inds, stride, shifts, level;
 810     unsigned int *slotref, index, next, mask;
 811     struct ext2_inode* e_inode;
 812     struct ext2b_inode* b_inode;
 813     struct v_superblock* vsb;
 814     bbuf_t table, next_table;
 815
 816     e_inode = EXT2_INO(inode);
 817     b_inode = e_inode->ino;
 818     vsb = inode->sb;
 819     level = 0;
 820     resolve = resolve && !EXT2_SB(vsb)->read_only;
 821
 822     if (pos < 12) {
 823         index = pos;
 824         slotref = &b_inode->i_block_arr[pos];
 825         table = fsblock_take(e_inode->buf);
 826         inds = 0;
 827         goto _return;
 828     }
 829
 830     pos -= 12;
 831     stride = e_inode->inds_lgents;
 832     if (!(pos >> stride)) {
 833         inds = 1;
 834     }
 835     else if (!(pos >> (stride * 2))) {
 836         inds = 2;
 837     }
 838     else if (!(pos >> (stride * 3))) {
 839         inds = 3;
 840     }
 841     else {
 842         fail("unrealistic block pos");
 843     }
 844
 845     // bTLB cache the last level indirect block
 846     if (!full_walk && (table = __btlb_hit(e_inode, pos))) {
 847         level = inds;
 848         index = pos & ((1 << stride) - 1);
 849         slotref = &block_buffer(table, u32_t)[index];
 850         goto _return;
 851     }
 852
 853     shifts = stride * (inds - 1);
 854     mask = ((1 << stride) - 1) << shifts;
 855
 856     index   = 12 + inds - 1;
 857     slotref = &b_inode->i_block.inds[inds - 1];
 858     table   = fsblock_take(e_inode->buf);
 859
 860     for (; level < inds; level++)
 861     {
 862         __walkstate_set_stack(state, level, table, index);
 863
 864         next = *slotref;
 865         if (!next) {
 866             if (!resolve) {
 867                 goto _return;
 868             }
 869
 870             if ((errno = ext2db_alloc(inode, &next_table))) {
 871                 fsblock_put(table);
 872                 return errno;
 873             }
 874
 875             e_inode->indirect_blocks++;
 876             *slotref = fsblock_id(next_table);
 877             fsblock_dirty(table);
 878         }
 879         else {
 880             next_table = fsblock_get(vsb, next);
 881         }
 882
 883         fsblock_put(table);
 884         table = next_table;
 885
 886         if (blkbuf_errbuf(table)) {
 887             return EIO;
 888         }
 889
 890         assert(shifts >= 0);
 891
 892         index = (pos & mask) >> shifts;
 893
 894         slotref = &block_buffer(table, u32_t)[index];
 895
 896         shifts -= stride;
 897         mask  = mask >> stride;
 898     }
 899
 900     __btlb_insert(e_inode, pos, table);
 901
 902 _return:
 903     assert(blkbuf_refcounts(table) >= 1);
 904     assert_fs(table);
 905     assert_fs(slotref);
 906
 907     state->slot_ref = slotref;
 908     state->table = table;
 909     state->level = level;
 910     state->indirections = inds;
 911
 912     __walkstate_set_stack(state, level, table, index);
 913
 914     return 0;
 915 }
 916
 917 bbuf_t
 918 ext2db_get(struct v_inode* inode, unsigned int data_pos)
 919 {
 920     int errno;
 921     unsigned int blkid;
 922     struct walk_state state;
 923
 924     ext2walk_init_state(&state);
 925
 926     errno = __walk_indirects(inode, data_pos, &state, false, false);
 927     if (errno) {
 928         return (bbuf_t)INVL_BUFFER;
 929     }
 930
 931     blkid = *state.slot_ref;
 932
 933     ext2walk_free_state(&state);
 934
 935     if (!blkid) {
 936         return NULL;
 937     }
 938
 939     return fsblock_get(inode->sb, blkid);
 940 }
 941
 942 int
 943 ext2db_acquire(struct v_inode* inode, unsigned int data_pos, bbuf_t* out)
 944 {
 945     int errno = 0;
 946     bbuf_t buf;
 947     unsigned int block_id;
 948     struct walk_state state;
 949
 950     ext2walk_init_state(&state);
 951
 952     errno = __walk_indirects(inode, data_pos, &state, true, false);
 953     if (errno) {
 954         return errno;
 955     }
 956
 957     block_id = *state.slot_ref;
 958     if (block_id) {
 959         buf = fsblock_get(inode->sb, block_id);
 960         goto done;
 961     }
 962
 963     errno = ext2db_alloc(inode, &buf);
 964     if (errno) {
 965         ext2walk_free_state(&state);
 966         return errno;
 967     }
 968
 969     *state.slot_ref = fsblock_id(buf);
 970     fsblock_dirty(state.table);
 971
 972 done:
 973     ext2walk_free_state(&state);
 974
 975     if (blkbuf_errbuf(buf)) {
 976         return EIO;
 977     }
 978
 979     *out = buf;
 980     return 0;
 981 }
 982
 983 int
 984 ext2db_alloc(struct v_inode* inode, bbuf_t* out)
 985 {
 986     int free_ino_idx;
 987     struct ext2_gdesc* gd;
 988     struct ext2_inode* e_inode;
 989     struct v_superblock* vsb;
 990
 991     free_ino_idx = ALLOC_FAIL;
 992     e_inode = EXT2_INO(inode);
 993     vsb = inode->sb;
 994
 995     gd = e_inode->blk_grp;
 996     free_ino_idx = ext2gd_alloc_block(gd);
 997
 998     // locality alloc failed, try entire fs
 999     if (!valid_bmp_slot(free_ino_idx)) {
1000         free_ino_idx = ext2db_alloc_slot(vsb, &gd);
1001     }
1002
1003     if (!valid_bmp_slot(free_ino_idx)) {
1004         return EDQUOT;
1005     }
1006
1007     free_ino_idx += gd->base;
1008     free_ino_idx = ext2_datablock(vsb, free_ino_idx);
1009     free_ino_idx = to_ext2ino_id(free_ino_idx);
1010
1011     bbuf_t buf = fsblock_get(vsb, free_ino_idx);
1012     if (blkbuf_errbuf(buf)) {
1013         return EIO;
1014     }
1015
1016     *out = buf;
1017     return 0;
1018 }
1019
1020 void
1021 ext2db_free_pos(struct v_inode* inode, unsigned int block_pos)
1022 {
1023     struct ext2_inode* e_inode;
1024     struct ext2_gdesc* gd;
1025
1026     e_inode = EXT2_INO(inode);
1027     gd = e_inode->blk_grp;
1028
1029     assert(block_pos >= gd->base);
1030
1031     block_pos -= gd->base;
1032
1033     ext2gd_free_block(gd, block_pos);
1034 }
1035
1036 int
1037 ext2db_free(struct v_inode* inode, bbuf_t buf)
1038 {
1039     assert(blkbuf_not_shared(buf));
1040
1041     ext2db_free_pos(inode, blkbuf_id(buf));
1042     fsblock_put(buf);
1043
1044     return 0;
1045 }
1046
1047 int
1048 ext2ino_resizing(struct v_inode* inode, size_t new_size)
1049 {
1050     int errno;
1051     unsigned int pos;
1052     size_t oldsize;
1053     struct walk_state state;
1054     struct ext2_inode*  e_ino;
1055     struct ext2b_inode* b_ino;
1056
1057     e_ino = EXT2_INO(inode);
1058     b_ino = e_ino->ino;
1059     oldsize = e_ino->isize;
1060
1061     if (oldsize == new_size) {
1062         return 0;
1063     }
1064
1065     __update_inode_size(inode, new_size);
1066     fsblock_dirty(e_ino->buf);
1067
1068     if (check_symlink_node(inode)) {
1069         return 0;
1070     }
1071
1072     if (oldsize < new_size) {
1073         return 0;
1074     }
1075
1076     ext2walk_init_state(&state);
1077
1078     pos   = new_size / fsapi_block_size(inode->sb);
1079     errno = __walk_indirects(inode, pos, &state, false, true);
1080     if (errno) {
1081         return errno;
1082     }
1083
1084     errno = __free_recurisve_from(inode->sb, e_ino, &state.stack, 0);
1085
1086     ext2walk_free_state(&state);
1087     return errno;
1088 }