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