// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "f2fs.h"

namespace f2fs {

Dir::Dir(F2fs *fs) : VnodeF2fs(fs) {}

Dir::Dir(F2fs *fs, ino_t ino) : VnodeF2fs(fs, ino) {}

uint64_t Dir::DirBlocks() {
  // return ((uint64_t) (i_size_read(inode) + kPageCacheSize - 1))
  //             >> kPageCacheShift;
  // return 0;
  // return Inode().i_blocks - 1;
  return (i_size_ + kF2fsBlockSize - 1) / kF2fsBlockSize;
}

unsigned int Dir::DirBuckets(unsigned int level) {
  if (level < MAX_DIR_HASH_DEPTH / 2)
    return 1 << level;
  else
    return 1 << ((MAX_DIR_HASH_DEPTH / 2) - 1);
}

unsigned int Dir::BucketBlocks(unsigned int level) {
  if (level < MAX_DIR_HASH_DEPTH / 2)
    return 2;
  else
    return 4;
}

void Dir::SetDeType(f2fs_dir_entry *de, VnodeF2fs *vnode) {
  de->file_type = type_by_mode[(vnode->i_mode_ & S_IFMT) >> kStatShift];
}

uint64_t Dir::DirBlockIndex(unsigned int level, unsigned int idx) {
  uint64_t i;
  uint64_t bidx = 0;

  for (i = 0; i < level; i++)
    bidx += DirBuckets(i) * BucketBlocks(i);
  bidx += idx * BucketBlocks(level);
  return bidx;
}

bool Dir::EarlyMatchName(const char *name, int namelen, f2fs_hash_t namehash,
                         f2fs_dir_entry *de) {
  if (LeToCpu(de->name_len) != namelen)
    return false;

  if (LeToCpu(de->hash_code) != namehash)
    return false;

  return true;
}

f2fs_dir_entry *Dir::FindInBlock(Page *dentry_page, const char *name, int namelen,
                                        int *max_slots, f2fs_hash_t namehash, Page **res_page) {
  f2fs_dir_entry *de;
  uint64_t bit_pos, end_pos, next_pos;
#if 0  // porting needed
  // f2fs_dentry_block *dentry_blk = kmap(dentry_page);
#else
  f2fs_dentry_block *dentry_blk = reinterpret_cast<f2fs_dentry_block *>(dentry_page);
#endif
  int slots;

  bit_pos =
      find_next_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK, 0);
  while (bit_pos < NR_DENTRY_IN_BLOCK) {
    de = &dentry_blk->dentry[bit_pos];
    slots = (LeToCpu(de->name_len) + F2FS_NAME_LEN - 1) / F2FS_NAME_LEN;

    if (EarlyMatchName(name, namelen, namehash, de)) {
      if (!memcmp(dentry_blk->filename[bit_pos], name, namelen)) {
        *res_page = dentry_page;
        return de;
      }
    }
    next_pos = bit_pos + slots;
    bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK,
                               next_pos);
    if (bit_pos >= NR_DENTRY_IN_BLOCK)
      end_pos = NR_DENTRY_IN_BLOCK;
    else
      end_pos = bit_pos;
    if (static_cast<uint64_t>(*max_slots) < end_pos - next_pos)
      *max_slots = end_pos - next_pos;
  }

  de = nullptr;
#if 0  // porting needed
//   kunmap(dentry_page);
#endif
  return de;
}

f2fs_dir_entry *Dir::FindInLevel(unsigned int level, fbl::StringPiece name, int namelen,
                                        f2fs_hash_t namehash, Page **res_page) {
  int s = (namelen + F2FS_NAME_LEN - 1) / F2FS_NAME_LEN;
  unsigned int nbucket, nblock;
  unsigned int bidx, end_block;
  Page *dentry_page = nullptr;
  f2fs_dir_entry *de = nullptr;
  bool room = false;
  int max_slots = 0;

  ZX_ASSERT(level <= MAX_DIR_HASH_DEPTH);

  nbucket = DirBuckets(level);
  nblock = BucketBlocks(level);

  bidx = DirBlockIndex(level, namehash % nbucket);
  end_block = bidx + nblock;

  for (; bidx < end_block; bidx++) {
    /* no need to allocate new dentry pages to all the indices */
    if (FindDataPage(bidx, &dentry_page) != ZX_OK) {
      room = true;
      continue;
    }

    if (de = FindInBlock(dentry_page, name.data(), namelen, &max_slots, namehash, res_page); de != nullptr)
      break;

    if (max_slots >= s)
      room = true;
    F2fsPutPage(dentry_page, 0);
  }

  if (!de && room && fi_.chash != namehash) {
    fi_.chash = namehash;
    fi_.clevel = level;
  }

  return de;
}

/*
 * Find an entry in the specified directory with the wanted name.
 * It returns the page where the entry was found (as a parameter - res_page),
 * and the entry itself. Page is returned mapped and unlocked.
 * Entry is guaranteed to be valid.
 */
f2fs_dir_entry *Dir::FindEntry(fbl::StringPiece name, Page **res_page) {
  uint64_t npages = DirBlocks();
  f2fs_dir_entry *de = nullptr;
  f2fs_hash_t name_hash;
  unsigned int max_depth;
  unsigned int level;

  if (npages == 0)
    return nullptr;

  *res_page = nullptr;

  name_hash = DentryHash(name.data(), name.length());
  max_depth = fi_.i_current_depth;

  for (level = 0; level < max_depth; level++) {
    if (de = FindInLevel(level, name, name.length(), name_hash, res_page); de != nullptr)
      break;
  }
  if (!de && fi_.chash != name_hash) {
    fi_.chash = name_hash;
    fi_.clevel = level - 1;
  }
  return de;
}

f2fs_dir_entry *Dir::ParentDir(Page **p) {
  Page *page = nullptr;
  f2fs_dir_entry *de = nullptr;
  f2fs_dentry_block *dentry_blk = nullptr;

  if (GetLockDataPage(0, &page) != ZX_OK)
    return nullptr;

#if 0  // porting needed
  // dentry_blk = kmap(page);
#endif
  dentry_blk = static_cast<f2fs_dentry_block *>(PageAddress(page));
  de = &dentry_blk->dentry[1];
  *p = page;
#if 0  // porting needed
  // unlock_page(page);
#endif
  return de;
}

ino_t Dir::InodeByName(fbl::StringPiece name) {
  ino_t res = 0;
  f2fs_dir_entry *de;
  Page *page;

  if (de = FindEntry(name, &page); de != nullptr) {
    res = LeToCpu(de->ino);
#if 0  // porting needed
    // kunmap(page);
#endif
    F2fsPutPage(page, 0);
  }

  return res;
}

void Dir::SetLink(f2fs_dir_entry *de, Page *page, VnodeF2fs *vnode) {
  f2fs_sb_info &sbi = Vfs()->SbInfo();

  fbl::AutoLock lock(&sbi.fs_lock[DENTRY_OPS]);
#if 0  // porting needed
  // lock_page(page);
#endif
  WaitOnPageWriteback(page);
  de->ino = CpuToLe(vnode->Ino());
  SetDeType(de, vnode);
#if 0  // porting needed
  // kunmap(page);
  // set_page_dirty(page);
#else
  FlushDirtyDataPage(Vfs(), page);
#endif

  auto cur_time = time(nullptr);
  i_mtime_.tv_sec = cur_time;
  i_mtime_.tv_nsec = 0;
  i_ctime_.tv_sec = cur_time;
  i_ctime_.tv_nsec = 0;
  MarkInodeDirty(this);
  F2fsPutPage(page, 1);
}

void Dir::InitDentInode(VnodeF2fs *vnode, Page *ipage) {
#if 0  // porting needed
  // inode *dir = dentry->d_parent->d_inode;
#endif
  f2fs_node *rn;

  if (!ipage)
    return;

  WaitOnPageWriteback(ipage);

  /* copy dentry info. to this inode page */
  rn = static_cast<f2fs_node *>(PageAddress(ipage));
  rn->i.i_pino = CpuToLe(Ino());
  rn->i.i_namelen = CpuToLe(vnode->i_name_sp_.length());
  memcpy(rn->i.i_name, vnode->i_name_sp_.data(), vnode->i_name_sp_.length());
#if 0  // porting needed
  // set_page_dirty(ipage);
#else
  FlushDirtyNodePage(Vfs(), ipage);
#endif
}

zx_status_t Dir::InitInodeMetadata(VnodeF2fs *vnode) {
#if 0  // porting needed
  // inode *dir = dentry->d_parent->d_inode;
#endif

  if (is_inode_flag_set(&vnode->fi_, FI_NEW_INODE)) {
    if (zx_status_t err = Vfs()->Nodemgr().NewInodePage(this, vnode); err != ZX_OK)
      return err;

    if (S_ISDIR(vnode->i_mode_)) {
      if (zx_status_t err = MakeEmpty(vnode, this); err != ZX_OK) {
        Vfs()->Nodemgr().RemoveInodePage(vnode);
        return err;
      }
    }

#if 0  // porting needed
    // err = f2fs_init_acl(inode, dir);
    // if (err) {
    //   remove_inode_page(inode);
    //   return err;
    // }
#endif
  } else {
    Page *ipage = nullptr;

    if (zx_status_t err = Vfs()->Nodemgr().GetNodePage(vnode->Ino(), &ipage); err != ZX_OK)
      return err;
    InitDentInode(vnode, ipage);
    F2fsPutPage(ipage, 1);
  }
  if (is_inode_flag_set(&vnode->fi_, FI_INC_LINK)) {
    vnode->IncNlink();
    vnode->WriteInode(NULL);
  }
  return 0;
}

void Dir::UpdateParentMetadata(VnodeF2fs *vnode, unsigned int current_depth) {
  bool need_dir_update = false;

  if (is_inode_flag_set(&vnode->fi_, FI_NEW_INODE)) {
    if (S_ISDIR(vnode->i_mode_)) {
      IncNlink();
      need_dir_update = true;
    }
    ClearInodeFlag(&vnode->fi_, FI_NEW_INODE);
  }

  auto cur_time = time(nullptr);
  i_mtime_.tv_sec = cur_time;
  i_mtime_.tv_nsec = 0;
  i_ctime_.tv_sec = cur_time;
  i_ctime_.tv_nsec = 0;
  if (fi_.i_current_depth != current_depth) {
    fi_.i_current_depth = current_depth;
    need_dir_update = true;
  }

  if (need_dir_update)
    WriteInode(NULL);
  else
    MarkInodeDirty(this);

  if (is_inode_flag_set(&vnode->fi_, FI_INC_LINK))
    ClearInodeFlag(&vnode->fi_, FI_INC_LINK);
}

int Dir::RoomForFilename(f2fs_dentry_block *dentry_blk, int slots) {
  int bit_start = 0;
  int zero_start, zero_end;

  while (true) {
    zero_start = find_next_zero_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK, bit_start);
    if (zero_start >= NR_DENTRY_IN_BLOCK)
      return NR_DENTRY_IN_BLOCK;

    zero_end = find_next_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK, zero_start);
    if (zero_end - zero_start >= slots)
      return zero_start;

    bit_start = zero_end + 1;

    if (zero_end + 1 >= NR_DENTRY_IN_BLOCK)
      return NR_DENTRY_IN_BLOCK;
  }
}

zx_status_t Dir::AddLink(fbl::StringPiece name, VnodeF2fs *vnode) {
  unsigned int bit_pos;
  unsigned int level;
  unsigned int current_depth;
  uint64_t bidx, block;
  f2fs_hash_t dentry_hash;
  f2fs_dir_entry *de;
  unsigned int nbucket, nblock;
  f2fs_sb_info &sbi = Vfs()->SbInfo();
  int namelen = name.length();
  Page *dentry_page = nullptr;
  f2fs_dentry_block *dentry_blk = nullptr;
  int slots = (namelen + F2FS_NAME_LEN - 1) / F2FS_NAME_LEN;
  zx_status_t err = 0;
  int i;

  dentry_hash = DentryHash(name.data(), namelen);
  level = 0;
  current_depth = fi_.i_current_depth;
  if (fi_.chash == dentry_hash) {
    level = fi_.clevel;
    fi_.chash = 0;
  }

  while (true) {
    if (current_depth == MAX_DIR_HASH_DEPTH)
      return ZX_ERR_OUT_OF_RANGE;

    /* Increase the depth, if required */
    if (level == current_depth)
      ++current_depth;

    nbucket = DirBuckets(level);
    nblock = BucketBlocks(level);

    bidx = DirBlockIndex(level, (dentry_hash % nbucket));

    for (block = bidx; block <= (bidx + nblock - 1); block++) {
      fbl::AutoLock lock(&sbi.fs_lock[DENTRY_OPS]);
      if (err = GetNewDataPage(block, true, &dentry_page); err != ZX_OK) {
        return err;
      }

#if 0  // porting needed
      // dentry_blk = kmap(dentry_page);
#else
      dentry_blk = reinterpret_cast<f2fs_dentry_block *>(dentry_page->data);
#endif
      bit_pos = RoomForFilename(dentry_blk, slots);
      if (bit_pos < NR_DENTRY_IN_BLOCK) {
#if 0  // porting needed
        // if (err = InitInodeMetadata(vnode, dentry); err == ZX_OK) {
#else
        if (err = InitInodeMetadata(vnode); err == ZX_OK) {
#endif
          WaitOnPageWriteback(dentry_page);

          de = &dentry_blk->dentry[bit_pos];
          de->hash_code = CpuToLe(dentry_hash);
          de->name_len = CpuToLe(static_cast<uint16_t>(namelen));
          memcpy(dentry_blk->filename[bit_pos], name.data(), namelen);
          de->ino = CpuToLe(vnode->Ino());
          SetDeType(de, vnode);
          for (i = 0; i < slots; i++)
            test_and_set_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap);
#if 0  // porting needed
          // set_page_dirty(dentry_page);
#else
          FlushDirtyDataPage(Vfs(), dentry_page);
#endif
          UpdateParentMetadata(vnode, current_depth);
        }

#if 0  // porting needed
        // kunmap(dentry_page);
#endif
        F2fsPutPage(dentry_page, 1);
        return err;
      }

#if 0  // porting needed
      // kunmap(dentry_page);
#endif
      F2fsPutPage(dentry_page, 1);
    }

    /* Move to next level to find the empty slot for new dentry */
    ++level;
  }
}

/**
 * It only removes the dentry from the dentry page,corresponding name
 * entry in name page does not need to be touched during deletion.
 */
void Dir::DeleteEntry(f2fs_dir_entry *dentry, Page *page, VnodeF2fs *vnode) {
  f2fs_dentry_block *dentry_blk;
  unsigned int bit_pos;
#if 0  // porting needed
  // address_space *mapping = page->mapping;
#endif
  f2fs_sb_info &sbi = Vfs()->SbInfo();
  int slots = (LeToCpu(dentry->name_len) + F2FS_NAME_LEN - 1) / F2FS_NAME_LEN;
  void *kaddr = PageAddress(page);
  int i;

  fbl::AutoLock lock(&sbi.fs_lock[DENTRY_OPS]);

#if 0  // porting needed
  // lock_page(page);
#endif
  WaitOnPageWriteback(page);

  dentry_blk = static_cast<f2fs_dentry_block *>(kaddr);
  bit_pos = dentry - dentry_blk->dentry;
  for (i = 0; i < slots; i++)
    test_and_clear_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap);

  /* Let's check and deallocate this dentry page */
  bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK, 0);
#if 0  // porting needed
  // kunmap(page); /* kunmap - pair of f2fs_find_entry */
  // set_page_dirty(page);
#else
  FlushDirtyDataPage(Vfs(), page);
#endif

  auto cur_time = time(nullptr);
  i_mtime_.tv_sec = cur_time;
  i_mtime_.tv_nsec = 0;
  i_ctime_.tv_sec = cur_time;
  i_ctime_.tv_nsec = 0;

  if (vnode && S_ISDIR(vnode->i_mode_)) {
    DropNlink();
    WriteInode(NULL);
  } else {
    MarkInodeDirty(this);
  }

  if (vnode) {
    cur_time = time(nullptr);
    i_ctime_.tv_sec = cur_time;
    i_ctime_.tv_nsec = 0;
    i_mtime_.tv_sec = cur_time;
    i_mtime_.tv_nsec = 0;
    vnode->i_ctime_.tv_sec = cur_time;
    vnode->i_ctime_.tv_nsec = 0;
    vnode->DropNlink();
    if (S_ISDIR(vnode->i_mode_)) {
      vnode->DropNlink();
      vnode->i_size_ = 0;
    }
    vnode->WriteInode(NULL);
    if (vnode->i_nlink_ == 0)
      Vfs()->AddOrphanInode(vnode->Ino());
  }

  if (bit_pos == NR_DENTRY_IN_BLOCK) {
    loff_t page_offset;
    TruncateHole(page->index, page->index + 1);
    ClearPageDirtyForIo(page);
#if 0  // porting needed
    // ClearPageUptodate(page);
#endif
    DecPageCount(&sbi, F2FS_DIRTY_DENTS);
    InodeDecDirtyDents(this);
    page_offset = page->index << kPageCacheShift;
    F2fsPutPage(page, 1);
  } else {
    F2fsPutPage(page, 1);
  }
}

zx_status_t Dir::MakeEmpty(VnodeF2fs *vnode, VnodeF2fs *parent) {
  Page *dentry_page = nullptr;
  f2fs_dentry_block *dentry_blk;
  f2fs_dir_entry *de;
  void *kaddr;

  if (zx_status_t err = vnode->GetNewDataPage(0, true, &dentry_page); err != ZX_OK)
    return err;

#if 0  // porting needed
  // kaddr = kmap_atomic(dentry_page);
#else
  kaddr = dentry_page->data;
#endif
  dentry_blk = static_cast<f2fs_dentry_block *>(kaddr);

  de = &dentry_blk->dentry[0];
  de->name_len = CpuToLe(static_cast<uint16_t>(1));
  de->hash_code = 0;
  de->ino = CpuToLe(vnode->Ino());
  memcpy(dentry_blk->filename[0], ".", 1);
  SetDeType(de, vnode);

  de = &dentry_blk->dentry[1];
  de->hash_code = 0;
  de->name_len = CpuToLe(static_cast<uint16_t>(2));
  de->ino = CpuToLe(parent->Ino());
  memcpy(dentry_blk->filename[1], "..", 2);
  SetDeType(de, vnode);

  test_and_set_bit_le(0, &dentry_blk->dentry_bitmap);
  test_and_set_bit_le(1, &dentry_blk->dentry_bitmap);
#if 0  // porting needed
  // kunmap_atomic(kaddr);
  // set_page_dirty(dentry_page);
#else
  FlushDirtyDataPage(Vfs(), dentry_page);
#endif
  F2fsPutPage(dentry_page, 1);
  return 0;
}

bool Dir::IsEmptyDir() {
  uint64_t bidx;
  Page *dentry_page = nullptr;
  unsigned int bit_pos;
  f2fs_dentry_block *dentry_blk;
  uint64_t nblock = DirBlocks();

  for (bidx = 0; bidx < nblock; bidx++) {
    void *kaddr;
    
    if (zx_status_t ret = GetLockDataPage(bidx, &dentry_page); ret != ZX_OK) {
      if (ret == ZX_ERR_NOT_FOUND)
        continue;
      else
        return false;
    }

#if 0  // porting needed
    // kaddr = kmap_atomic(dentry_page);
#else
    kaddr = dentry_page->data;
#endif
    dentry_blk = static_cast<f2fs_dentry_block *>(kaddr);
    if (bidx == 0)
      bit_pos = 2;
    else
      bit_pos = 0;
    bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, NR_DENTRY_IN_BLOCK, bit_pos);
#if 0  // porting needed
    // kunmap_atomic(kaddr);
#endif

    F2fsPutPage(dentry_page, 1);

    if (bit_pos < NR_DENTRY_IN_BLOCK)
      return false;
  }
  return true;
}

zx_status_t Dir::Readdir(fs::VdirCookie *cookie, void *dirents, size_t len, size_t *out_actual) {
  fs::DirentFiller df(dirents, len);
  uint64_t *pos_cookie = reinterpret_cast<uint64_t *>(cookie);
  uint64_t pos = *pos_cookie;
  uint64_t npages = DirBlocks();
  unsigned char *types = nullptr;
  unsigned int bit_pos = 0, start_bit_pos = 0;
  f2fs_dentry_block *dentry_blk = nullptr;
  f2fs_dir_entry *de = nullptr;
  Page *dentry_page = nullptr;
  unsigned int n = 0;
  unsigned char d_type = DT_UNKNOWN;
  int slots;
  zx_status_t ret = ZX_OK;
  bool done = false;

  fbl::AutoLock lock(&i_mutex_);

  types = filetype_table;
  bit_pos = (pos % NR_DENTRY_IN_BLOCK);
  n = (pos / NR_DENTRY_IN_BLOCK);

  for (; n < npages; n++) {
    if (ret = GetLockDataPage(n, &dentry_page); ret != ZX_OK)
      continue;

    start_bit_pos = bit_pos;
#if 0  // porting needed
    //     dentry_blk = kmap(dentry_page);
#else
    dentry_blk = reinterpret_cast<f2fs_dentry_block *>(dentry_page);
#endif
    while (bit_pos < NR_DENTRY_IN_BLOCK) {
      d_type = DT_UNKNOWN;
      bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
                                 NR_DENTRY_IN_BLOCK, bit_pos);
      if (bit_pos >= NR_DENTRY_IN_BLOCK)
        break;

      de = &dentry_blk->dentry[bit_pos];
      if (types && de->file_type < F2FS_FT_MAX)
        d_type = types[de->file_type];

      fbl::StringPiece name(reinterpret_cast<char *>(dentry_blk->filename[bit_pos]), LeToCpu(de->name_len));

      if ((ret = df.Next(name, d_type, LeToCpu(de->ino))) != ZX_OK) {
        *pos_cookie += bit_pos - start_bit_pos;
        done = true;
        break;
      }

      slots = (LeToCpu(de->name_len) + F2FS_NAME_LEN - 1) / F2FS_NAME_LEN;
      bit_pos += slots;
    }
    if (done)
      break;

    bit_pos = 0;
    *pos_cookie = (n + 1) * NR_DENTRY_IN_BLOCK;

#if 0  // porting needed
    //     kunmap(dentry_page);
#endif
    F2fsPutPage(dentry_page, 1);
    dentry_page = nullptr;
  }

  if (dentry_page && ret == ZX_OK) {
#if 0  // porting needed
    //     kunmap(dentry_page);
#endif
    F2fsPutPage(dentry_page, 1);
  }

  *out_actual = df.BytesFilled();

  return ret;
}

#if 0  // porting needed
// const file_operations f2fs_dir_operations = {
//   .llseek    = generic_file_llseek,
//   .read    = generic_read_dir,
//   .readdir  = f2fs_readdir,
// };
#endif

}  // namespace f2fs