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

   1 #include <lunaix/mm/valloc.h>
   2 #include <lunaix/spike.h>
   3 #include <klibc/string.h>
   4
   5 #include "ext2.h"
   6
   7 static inline bool
   8 aligned_reclen(struct ext2b_dirent* dirent)
   9 {
  10     return !(dirent->rec_len % 4);
  11 }
  12
  13 static int
  14 __find_dirent_byname(struct v_inode* inode, struct hstr* name,
  15                      struct ext2_dnode* e_dnode_out)
  16 {
  17     int errno = 0;
  18     struct ext2_iterator iter;
  19     struct ext2b_dirent *dir = NULL, *prev = NULL;
  20     bbuf_t prev_buf = NULL;
  21
  22     ext2dr_itbegin(&iter, inode);
  23
  24     while (ext2dr_itnext(&iter)) {
  25         dir = iter.dirent;
  26
  27         if (dir->name_len != name->len) {
  28             goto cont;
  29         }
  30
  31         if (strneq(dir->name, name->value, name->len)) {
  32             goto done;
  33         }
  34
  35 cont:
  36         prev = dir;
  37         if (prev_buf) {
  38             fsblock_put(prev_buf);
  39         }
  40         prev_buf = fsblock_take(iter.sel_buf);
  41     }
  42
  43     errno = ENOENT;
  44     goto _ret;
  45
  46 done:
  47     e_dnode_out->self = (struct ext2_dnode_sub) {
  48         .buf = fsblock_take(iter.sel_buf),
  49         .dirent = dir
  50     };
  51
  52     e_dnode_out->prev = (struct ext2_dnode_sub) {
  53         .buf = fsblock_take(prev_buf),
  54         .dirent = prev
  55     };
  56
  57 _ret:
  58     fsblock_put(prev_buf);
  59     ext2dr_itend(&iter);
  60
  61     return itstate_sel(&iter, errno);
  62 }
  63
  64 static inline size_t
  65 __dirent_realsize(struct ext2b_dirent* dirent)
  66 {
  67     return sizeof(*dirent) - sizeof(dirent->name) + dirent->name_len;
  68 }
  69
  70 #define DIRENT_INSERT     0
  71 #define DIRENT_APPEND     1
  72
  73 #define DIRENT_ALIGNMENT    sizeof(int)
  74
  75 struct dirent_locator
  76 {
  77     size_t search_size;
  78
  79     int state;
  80     struct ext2_dnode result;
  81     size_t new_prev_reclen;
  82     size_t db_pos;
  83 };
  84
  85
  86 static inline void must_inline
  87 __init_locator(struct dirent_locator* loc, size_t search_size)
  88 {
  89     *loc = (struct dirent_locator) { .search_size = search_size };
  90 }
  91
  92 static int
  93 __find_free_dirent_slot(struct v_inode* inode, struct dirent_locator* loc)
  94 {
  95     struct ext2_iterator dbit;
  96     struct ext2b_dirent *dir = NULL;
  97     struct ext2_dnode* result;
  98
  99     bbuf_t prev_buf = bbuf_null;
 100     bool found = false;
 101
 102     size_t sz = 0, aligned = 0;
 103     unsigned int rec = 0, total_rec = 0;
 104     unsigned int dir_size;
 105
 106     aligned = ROUNDUP(loc->search_size, DIRENT_ALIGNMENT);
 107     result  = &loc->result;
 108
 109     ext2db_itbegin(&dbit, inode, DBIT_MODE_BLOCK);
 110
 111     while (!found && ext2db_itnext(&dbit))
 112     {
 113         rec = 0;
 114         do {
 115             dir = (struct ext2b_dirent*)offset(dbit.data, rec);
 116
 117             sz = dir->rec_len - __dirent_realsize(dir);
 118             sz = ROUNDDOWN(sz, DIRENT_ALIGNMENT);
 119             if ((signed)sz >= (signed)aligned) {
 120                 found = true;
 121                 break;
 122             }
 123
 124             rec += dir->rec_len;
 125             total_rec += dir->rec_len;
 126         } while(rec < dbit.blksz);
 127
 128         if (likely(prev_buf)) {
 129             fsblock_put(prev_buf);
 130         }
 131
 132         prev_buf = fsblock_take(dbit.sel_buf);
 133     }
 134
 135     ext2_debug("dr_find_slot: found=%d, blk_off=%d, off=%d, gap=%d, blk=%d/%d",
 136                 found, rec, total_rec, sz, dbit.pos - 1, dbit.end_pos);
 137
 138     loc->db_pos = dbit.pos - 1;
 139
 140     if (blkbuf_nullbuf(prev_buf)) {
 141         // this dir is brand new
 142         loc->state = DIRENT_APPEND;
 143         goto done;
 144     }
 145
 146     dir_size = ROUNDUP(__dirent_realsize(dir), 4);
 147     loc->new_prev_reclen = dir_size;
 148
 149     result->prev = (struct ext2_dnode_sub) {
 150         .buf = fsblock_take(prev_buf),
 151         .dirent = dir
 152     };
 153
 154     if (!found) {
 155         // if prev is the last, and no more space left behind.
 156         assert_fs(rec == dbit.blksz);
 157
 158         result->self.buf = bbuf_null;
 159         ext2db_itend(&dbit);
 160
 161         loc->state = DIRENT_APPEND;
 162         goto done;
 163     }
 164
 165     rec += dir_size;
 166     dir = (struct ext2b_dirent*)offset(dbit.data, rec);
 167
 168     result->self = (struct ext2_dnode_sub) {
 169         .buf = fsblock_take(dbit.sel_buf),
 170         .dirent = dir
 171     };
 172
 173     ext2db_itend(&dbit);
 174
 175     loc->state = DIRENT_INSERT;
 176
 177 done:
 178     return itstate_sel(&dbit, 0);
 179 }
 180
 181 static inline void
 182 __release_dnode_blocks(struct ext2_dnode* e_dno)
 183 {
 184     fsblock_put(e_dno->prev.buf);
 185     fsblock_put(e_dno->self.buf);
 186 }
 187
 188 static inline void
 189 __destruct_ext2_dnode(struct ext2_dnode* e_dno)
 190 {
 191     __release_dnode_blocks(e_dno);
 192     vfree(e_dno);
 193 }
 194
 195 static inline bool
 196 __check_special(struct v_dnode* dnode)
 197 {
 198     return HSTR_EQ(&dnode->name, &vfs_dot)
 199         || HSTR_EQ(&dnode->name, &vfs_ddot);
 200 }
 201
 202 static bool
 203 __check_empty_dir(struct v_inode* dir_ino)
 204 {
 205     struct ext2_iterator iter;
 206     struct ext2b_dirent* dir;
 207
 208     ext2dr_itbegin(&iter, dir_ino);
 209     while (ext2dr_itnext(&iter))
 210     {
 211         dir = iter.dirent;
 212         if (strneq(dir->name, vfs_dot.value, 1)) {
 213             continue;
 214         }
 215
 216         if (strneq(dir->name, vfs_ddot.value, 2)) {
 217             continue;
 218         }
 219
 220         ext2dr_itend(&iter);
 221         return false;
 222     }
 223
 224     ext2dr_itend(&iter);
 225     return true;
 226 }
 227
 228 void
 229 ext2dr_itbegin(struct ext2_iterator* iter, struct v_inode* inode)
 230 {
 231     *iter = (struct ext2_iterator){
 232         .pos = 0,
 233         .inode = inode,
 234         .blksz = inode->sb->blksize
 235     };
 236
 237     iter->sel_buf = ext2db_get(inode, 0);
 238     ext2_itcheckbuf(iter);
 239 }
 240
 241 void
 242 ext2dr_itreset(struct ext2_iterator* iter)
 243 {
 244     fsblock_put(iter->sel_buf);
 245     iter->sel_buf = ext2db_get(iter->inode, 0);
 246     ext2_itcheckbuf(iter);
 247
 248     iter->pos = 0;
 249 }
 250
 251 int
 252 ext2dr_itffw(struct ext2_iterator* iter, int count)
 253 {
 254     int i = 0;
 255     while (i < count && ext2dr_itnext(iter)) {
 256         i++;
 257     }
 258
 259     return i;
 260 }
 261
 262 void
 263 ext2dr_itend(struct ext2_iterator* iter)
 264 {
 265     if (iter->sel_buf) {
 266         fsblock_put(iter->sel_buf);
 267     }
 268 }
 269
 270 bool
 271 ext2dr_itnext(struct ext2_iterator* iter)
 272 {
 273     struct ext2b_dirent* d;
 274     unsigned int blkpos, db_index;
 275     bbuf_t buf;
 276
 277     buf = iter->sel_buf;
 278
 279     if (iter->has_error) {
 280         return false;
 281     }
 282
 283     if (likely(iter->dirent)) {
 284         d = iter->dirent;
 285
 286         assert_fs(!(d->rec_len % 4));
 287         iter->pos += d->rec_len;
 288
 289         if (!d->rec_len || !d->inode) {
 290             return false;
 291         }
 292     }
 293
 294     blkpos = iter->pos % iter->blksz;
 295     db_index = iter->pos / iter->blksz;
 296
 297     if (unlikely(iter->pos >= iter->blksz)) {
 298         fsblock_put(buf);
 299
 300         buf = ext2db_get(iter->inode, db_index);
 301         iter->sel_buf = buf;
 302
 303         if (!buf || !ext2_itcheckbuf(iter)) {
 304             return false;
 305         }
 306     }
 307
 308     d = (struct ext2b_dirent*)offset(blkbuf_data(buf), blkpos);
 309     iter->dirent = d;
 310
 311     return true;
 312 }
 313
 314 int
 315 ext2dr_open(struct v_inode* this, struct v_file* file)
 316 {
 317     struct ext2_file* e_file;
 318
 319     e_file = EXT2_FILE(file);
 320
 321     ext2dr_itbegin(&e_file->iter, this);
 322
 323     return itstate_sel(&e_file->iter, 0);
 324 }
 325
 326 int
 327 ext2dr_close(struct v_inode* this, struct v_file* file)
 328 {
 329     struct ext2_file* e_file;
 330
 331     e_file = EXT2_FILE(file);
 332
 333     ext2dr_itend(&e_file->iter);
 334
 335     return 0;
 336 }
 337
 338 int
 339 ext2dr_lookup(struct v_inode* inode, struct v_dnode* dnode)
 340 {
 341     int errno;
 342     struct ext2b_dirent* dir;
 343     struct ext2_dnode* e_dnode;
 344     struct v_inode* dir_inode;
 345
 346     e_dnode = valloc(sizeof(struct ext2_dnode));
 347     errno = __find_dirent_byname(inode, &dnode->name, e_dnode);
 348     if (errno) {
 349         vfree(e_dnode);
 350         return errno;
 351     }
 352
 353     dir = e_dnode->self.dirent;
 354     if (!(dir_inode = vfs_i_find(inode->sb, dir->inode))) {
 355         dir_inode = vfs_i_alloc(inode->sb);
 356         ext2ino_fill(dir_inode, dir->inode);
 357     }
 358
 359     dnode->data = e_dnode;
 360     vfs_assign_inode(dnode, dir_inode);
 361
 362     return 0;
 363 }
 364
 365 #define FT_NUL  0
 366 #define FT_REG  1
 367 #define FT_DIR  2
 368 #define FT_CHR  3
 369 #define FT_BLK  4
 370 #define FT_SYM  7
 371 #define check_imode(val, imode)     (((val) & (imode)) == (imode))
 372
 373 static inline unsigned int
 374 __imode_to_filetype(unsigned int imode)
 375 {
 376     if (check_imode(imode, IMODE_IFLNK)) {
 377         return FT_SYM;
 378     }
 379
 380     if (check_imode(imode, IMODE_IFBLK)) {
 381         return FT_BLK;
 382     }
 383
 384     if (check_imode(imode, IMODE_IFCHR)) {
 385         return FT_CHR;
 386     }
 387
 388     if (check_imode(imode, IMODE_IFDIR)) {
 389         return FT_DIR;
 390     }
 391
 392     if (check_imode(imode, IMODE_IFREG)) {
 393         return FT_REG;
 394     }
 395
 396     return FT_NUL;
 397 }
 398
 399 static int
 400 __dir_filetype(struct v_superblock* vsb, struct ext2b_dirent* dir)
 401 {
 402     int errno;
 403     unsigned int type;
 404
 405     if (ext2_feature(vsb, FEAT_FILETYPE)) {
 406         type = dir->file_type;
 407     }
 408     else {
 409         struct ext2_fast_inode e_fino;
 410
 411         errno = ext2ino_get_fast(vsb, dir->inode, &e_fino);
 412         if (errno) {
 413             return errno;
 414         }
 415
 416         type = __imode_to_filetype(e_fino.ino->i_mode);
 417
 418         fsblock_put(e_fino.buf);
 419     }
 420
 421     if (type == FT_DIR) {
 422         return DT_DIR;
 423     }
 424
 425     if (type == FT_SYM) {
 426         return DT_SYMLINK;
 427     }
 428
 429     return DT_FILE;
 430 }
 431
 432 int
 433 ext2dr_read(struct v_file *file, struct dir_context *dctx)
 434 {
 435     struct ext2_file* e_file;
 436     struct ext2b_dirent* dir;
 437     struct ext2_iterator* iter;
 438     struct v_superblock* vsb;
 439     int dirtype;
 440
 441     e_file = EXT2_FILE(file);
 442     vsb    = file->inode->sb;
 443     iter   = &e_file->iter;
 444
 445     if (!ext2dr_itnext(&e_file->iter)) {
 446         return itstate_sel(iter, 0);
 447     }
 448
 449     dir = e_file->iter.dirent;
 450     dirtype =  __dir_filetype(vsb, dir);
 451     if (dirtype < 0) {
 452         return dirtype;
 453     }
 454
 455     fsapi_dir_report(dctx, dir->name, dir->name_len, dirtype);
 456
 457     return 1;
 458 }
 459
 460 int
 461 ext2dr_seek(struct v_file* file, size_t offset)
 462 {
 463     struct ext2_file* e_file;
 464     struct ext2_iterator* iter;
 465     unsigned int fpos;
 466
 467     e_file = EXT2_FILE(file);
 468     iter = &e_file->iter;
 469     fpos = file->f_pos;
 470
 471     if (offset == fpos) {
 472         return 0;
 473     }
 474
 475     if (offset > fpos) {
 476         fpos = ext2dr_itffw(iter, fpos - offset);
 477         return 0;
 478     }
 479
 480     if (!offset || offset < fpos) {
 481         ext2dr_itreset(iter);
 482     }
 483
 484     fpos = ext2dr_itffw(iter, offset);
 485
 486     return itstate_sel(iter, 0);
 487 }
 488
 489 int
 490 ext2dr_insert(struct v_inode* this, struct ext2b_dirent* dirent,
 491               struct ext2_dnode** e_dno_out)
 492 {
 493     int errno;
 494     size_t size, new_reclen, old_reclen;
 495     struct ext2_dnode*  e_dno;
 496     struct ext2b_dirent* prev_dirent;
 497     struct dirent_locator locator;
 498     bbuf_t buf;
 499
 500     size = __dirent_realsize(dirent);
 501     __init_locator(&locator, size);
 502
 503     errno = __find_free_dirent_slot(this, &locator);
 504     if (errno < 0) {
 505         goto failed;
 506     }
 507
 508     e_dno = &locator.result;
 509     new_reclen = locator.new_prev_reclen;
 510     old_reclen = fsapi_block_size(this->sb);
 511
 512     if (locator.state != DIRENT_INSERT)
 513     {
 514         if ((errno = ext2db_acquire(this, locator.db_pos, &buf)))
 515             goto failed;
 516
 517         this->fsize += fsapi_block_size(this->sb);
 518         ext2ino_update(this);
 519
 520         e_dno->self.buf = buf;
 521         e_dno->self.dirent = block_buffer(buf, struct ext2b_dirent);
 522     }
 523
 524
 525     /*
 526                    --- +--------+ ---
 527                     ^  |  prev  |  |
 528                     |  +--------+  |
 529                     |              |   new_reclen
 530                     |              |
 531                     |              v
 532                     |  +--------+ ---  -
 533                     |  | dirent |  |   | size
 534         old_reclen  |  +--------+  |   -
 535                     |              |   dirent.reclen
 536                     |              |
 537                     v              v
 538                    --- +--------+ ---
 539                        |  next  |
 540                        +--------+
 541     */
 542
 543     else
 544     {
 545         prev_dirent = e_dno->prev.dirent;
 546         old_reclen  = prev_dirent->rec_len;
 547         old_reclen -= new_reclen;
 548
 549         prev_dirent->rec_len = new_reclen;
 550         fsblock_dirty(e_dno->prev.buf);
 551     }
 552
 553     ext2_debug("dr_insert: state=%d, blk=%d, prev_rlen=%d, new_rlen=%d",
 554                 locator.state, locator.db_pos, new_reclen, old_reclen);
 555
 556     assert_fs(new_reclen > 0);
 557     assert_fs(old_reclen > 0);
 558
 559     dirent->rec_len = old_reclen;
 560
 561     memcpy(e_dno->self.dirent, dirent, size);
 562     fsblock_dirty(e_dno->self.buf);
 563
 564     if (!e_dno_out) {
 565         __release_dnode_blocks(e_dno);
 566     }
 567     else {
 568         *e_dno_out = e_dno;
 569     }
 570
 571     return errno;
 572
 573 failed:
 574     __release_dnode_blocks(e_dno);
 575     return errno;
 576 }
 577
 578 int
 579 ext2dr_remove(struct ext2_dnode* e_dno)
 580 {
 581     struct ext2_dnode_sub *dir_prev, *dir;
 582     assert(e_dno->prev.dirent);
 583
 584     dir_prev = &e_dno->prev;
 585     dir = &e_dno->self;
 586
 587     dir_prev->dirent->rec_len += dir->dirent->rec_len;
 588     dir->dirent->rec_len = 0;
 589     dir->dirent->inode = 0;
 590
 591     fsblock_dirty(dir_prev->buf);
 592     fsblock_dirty(dir->buf);
 593
 594     __destruct_ext2_dnode(e_dno);
 595
 596     return 0;
 597 }
 598
 599 int
 600 ext2_rmdir(struct v_inode* this, struct v_dnode* dnode)
 601 {
 602     int errno;
 603     struct v_inode* self;
 604     struct ext2_dnode* e_dno;
 605
 606     self = dnode->inode;
 607     e_dno  = EXT2_DNO(dnode);
 608
 609     if (__check_special(dnode)) {
 610         return EINVAL;
 611     }
 612
 613     if (!__check_empty_dir(self)) {
 614         return ENOTEMPTY;
 615     }
 616
 617     if ((errno = ext2ino_free(self))) {
 618         return errno;
 619     }
 620
 621     return ext2dr_remove(e_dno);
 622 }
 623
 624 static int
 625 __d_insert(struct v_inode* parent, struct v_inode* self,
 626            struct ext2b_dirent* dirent,
 627            struct hstr* name, struct ext2_dnode** e_dno_out)
 628 {
 629     ext2dr_setup_dirent(dirent, self, name);
 630
 631     dirent->inode = self->id;
 632     return ext2dr_insert(parent, dirent, e_dno_out);
 633 }
 634
 635 int
 636 ext2_mkdir(struct v_inode* this, struct v_dnode* dnode)
 637 {
 638     int errno;
 639     struct ext2_inode *e_contain, *e_created;
 640     struct v_inode* i_created;
 641     struct ext2_dnode* e_dno = NULL;
 642     struct ext2b_dirent dirent;
 643
 644     e_contain = EXT2_INO(this);
 645
 646     errno = ext2ino_make(this->sb, VFS_IFDIR, e_contain, &i_created);
 647     if (errno) {
 648         return errno;
 649     }
 650
 651     e_created = EXT2_INO(i_created);
 652
 653     if ((errno = __d_insert(this, i_created, &dirent, &dnode->name, &e_dno))) {
 654         goto cleanup1;
 655     }
 656
 657     // link the created dir inode to dirent
 658     ext2ino_linkto(e_created, &dirent);
 659     dnode->data = e_dno;
 660
 661     // insert . and ..
 662     // we don't need ext2ino_linkto here.
 663
 664     if ((errno = __d_insert(i_created, i_created, &dirent, &vfs_dot, NULL))) {
 665         goto cleanup;
 666     }
 667
 668     if ((errno = __d_insert(i_created, this, &dirent, &vfs_ddot, NULL))) {
 669         goto cleanup;
 670     }
 671
 672     vfs_assign_inode(dnode, i_created);
 673     return 0;
 674
 675 cleanup:
 676     __destruct_ext2_dnode(e_dno);
 677
 678 cleanup1:
 679     dnode->data = NULL;
 680     ext2ino_free(i_created);
 681     vfs_i_free(i_created);
 682
 683     return errno;
 684 }
 685
 686 void
 687 ext2dr_setup_dirent(struct ext2b_dirent* dirent,
 688                     struct v_inode* inode, struct hstr* name)
 689 {
 690     unsigned int imode;
 691
 692     imode = EXT2_INO(inode)->ino->i_mode;
 693     *dirent = (struct ext2b_dirent){
 694         .name_len = name->len
 695     };
 696
 697     strncpy(dirent->name, name->value, name->len);
 698
 699     if (ext2_feature(inode->sb, FEAT_FILETYPE)) {
 700         dirent->file_type = __imode_to_filetype(imode);
 701     }
 702 }
 703
 704 int
 705 ext2_rename(struct v_inode* from_inode, struct v_dnode* from_dnode,
 706             struct v_dnode* to_dnode)
 707 {
 708     int errno;
 709     struct v_inode* to_parent;
 710
 711     if (EXT2_DNO(to_dnode)) {
 712         errno = ext2_unlink(to_dnode->inode, to_dnode);
 713         if (errno) {
 714             return errno;
 715         }
 716     }
 717
 718     errno = ext2_link(from_inode, to_dnode);
 719     if (errno) {
 720         return errno;
 721     }
 722
 723     return ext2_unlink(from_inode, from_dnode);
 724 }