Lines Matching +full:ip +full:- +full:block
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
64 static void ext2_append_entry(char *block, uint32_t blksize,
69 static int ext2_htree_check_next(struct inode *ip, uint32_t hash,
72 static int ext2_htree_find_leaf(struct inode *ip, const char *name,
83 static uint32_t ext2_htree_node_limit(struct inode *ip);
92 static int ext2_htree_split_dirblock(struct inode *ip,
97 static uint32_t ext2_htree_root_limit(struct inode *ip, int len);
98 static int ext2_htree_writebuf(struct inode *ip,
102 ext2_htree_has_idx(struct inode *ip) in ext2_htree_has_idx() argument
104 if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && in ext2_htree_has_idx()
105 ip->i_flag & IN_E3INDEX) in ext2_htree_has_idx()
112 ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name, in ext2_htree_check_next() argument
115 struct vnode *vp = ITOV(ip); in ext2_htree_check_next()
119 int idx = info->h_levels_num - 1; in ext2_htree_check_next()
123 level = &info->h_levels[idx]; in ext2_htree_check_next()
124 level->h_entry++; in ext2_htree_check_next()
125 if (level->h_entry < level->h_entries + in ext2_htree_check_next()
126 ext2_htree_get_count(level->h_entries)) in ext2_htree_check_next()
130 idx--; in ext2_htree_check_next()
134 next_hash = ext2_htree_get_hash(level->h_entry); in ext2_htree_check_next()
141 levels--; in ext2_htree_check_next()
142 if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) * in ext2_htree_check_next()
143 ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0) in ext2_htree_check_next()
145 level = &info->h_levels[idx + 1]; in ext2_htree_check_next()
146 brelse(level->h_bp); in ext2_htree_check_next()
147 level->h_bp = bp; in ext2_htree_check_next()
148 level->h_entry = level->h_entries = in ext2_htree_check_next()
149 ((struct ext2fs_htree_node *)bp->b_data)->h_entries; in ext2_htree_check_next()
158 return (le32toh(ep->h_blk) & 0x00FFFFFF); in ext2_htree_get_block()
164 ep->h_blk = htole32(blk); in ext2_htree_set_block()
170 return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_num)); in ext2_htree_get_count()
176 ((struct ext2fs_htree_count *)(ep))->h_entries_num = htole16(cnt); in ext2_htree_set_count()
182 return (le32toh(ep->h_hash)); in ext2_htree_get_hash()
188 return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_max)); in ext2_htree_get_limit()
194 ep->h_hash = htole32(hash); in ext2_htree_set_hash()
200 ((struct ext2fs_htree_count *)(ep))->h_entries_max = htole16(limit); in ext2_htree_set_limit()
208 for (i = 0; i < info->h_levels_num; i++) { in ext2_htree_release()
209 struct buf *bp = info->h_levels[i].h_bp; in ext2_htree_release()
217 ext2_htree_root_limit(struct inode *ip, int len) in ext2_htree_root_limit() argument
222 fs = ip->i_e2fs; in ext2_htree_root_limit()
223 space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - in ext2_htree_root_limit()
224 EXT2_DIR_REC_LEN(2) - len; in ext2_htree_root_limit()
227 space -= sizeof(struct ext2fs_htree_tail); in ext2_htree_root_limit()
233 ext2_htree_node_limit(struct inode *ip) in ext2_htree_node_limit() argument
238 fs = ip->i_e2fs; in ext2_htree_node_limit()
239 space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0); in ext2_htree_node_limit()
242 space -= sizeof(struct ext2fs_htree_tail); in ext2_htree_node_limit()
252 seed[i] = le32toh(es->e3fs_hash_seed[i]); in ext2_get_hash_seed()
256 ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen, in ext2_htree_find_leaf() argument
273 return (-1); in ext2_htree_find_leaf()
275 vp = ITOV(ip); in ext2_htree_find_leaf()
276 fs = ip->i_e2fs->e2fs; in ext2_htree_find_leaf()
277 m_fs = ip->i_e2fs; in ext2_htree_find_leaf()
280 return (-1); in ext2_htree_find_leaf()
282 info->h_levels_num = 1; in ext2_htree_find_leaf()
283 info->h_levels[0].h_bp = bp; in ext2_htree_find_leaf()
284 rootp = (struct ext2fs_htree_root *)bp->b_data; in ext2_htree_find_leaf()
285 if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY && in ext2_htree_find_leaf()
286 rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 && in ext2_htree_find_leaf()
287 rootp->h_info.h_hash_version != EXT2_HTREE_TEA) in ext2_htree_find_leaf()
290 hash_version = rootp->h_info.h_hash_version; in ext2_htree_find_leaf()
292 hash_version += m_fs->e2fs_uhash; in ext2_htree_find_leaf()
300 if ((levels = rootp->h_info.h_ind_levels) > 1) in ext2_htree_find_leaf()
303 entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) + in ext2_htree_find_leaf()
304 rootp->h_info.h_info_len); in ext2_htree_find_leaf()
307 ext2_htree_root_limit(ip, rootp->h_info.h_info_len)) in ext2_htree_find_leaf()
316 end = entp + cnt - 1; in ext2_htree_find_leaf()
318 middle = start + (end - start) / 2; in ext2_htree_find_leaf()
320 end = middle - 1; in ext2_htree_find_leaf()
324 found = start - 1; in ext2_htree_find_leaf()
326 level_info = &(info->h_levels[info->h_levels_num - 1]); in ext2_htree_find_leaf()
327 level_info->h_bp = bp; in ext2_htree_find_leaf()
328 level_info->h_entries = entp; in ext2_htree_find_leaf()
329 level_info->h_entry = found; in ext2_htree_find_leaf()
332 levels--; in ext2_htree_find_leaf()
334 ext2_htree_get_block(found) * m_fs->e2fs_bsize, in ext2_htree_find_leaf()
337 entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries; in ext2_htree_find_leaf()
338 info->h_levels_num++; in ext2_htree_find_leaf()
339 info->h_levels[info->h_levels_num - 1].h_bp = bp; in ext2_htree_find_leaf()
344 return (-1); in ext2_htree_find_leaf()
351 ext2_htree_lookup(struct inode *ip, const char *name, int namelen, in ext2_htree_lookup() argument
368 m_fs = ip->i_e2fs; in ext2_htree_lookup()
369 bsize = m_fs->e2fs_bsize; in ext2_htree_lookup()
370 vp = ITOV(ip); in ext2_htree_lookup()
375 if (ext2_htree_find_leaf(ip, name, namelen, &dirhash, in ext2_htree_lookup()
377 return (-1); in ext2_htree_lookup()
380 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; in ext2_htree_lookup()
384 return (-1); in ext2_htree_lookup()
392 if (ss->slotstatus == NONE) { in ext2_htree_lookup()
393 ss->slotoffset = -1; in ext2_htree_lookup()
394 ss->slotfreespace = 0; in ext2_htree_lookup()
397 if (ext2_search_dirblock(ip, bp->b_data, &found, in ext2_htree_lookup()
402 return (-1); in ext2_htree_lookup()
412 search_next = ext2_htree_check_next(ip, dirhash, name, &info); in ext2_htree_lookup()
429 cursize = roundup(dp->i_size, blksize); in ext2_htree_append_block()
441 error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred); in ext2_htree_append_block()
443 dp->i_size = newsize; in ext2_htree_append_block()
449 ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info) in ext2_htree_writebuf() argument
453 for (i = 0; i < info->h_levels_num; i++) { in ext2_htree_writebuf()
454 struct buf *bp = info->h_levels[i].h_bp; in ext2_htree_writebuf()
455 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data); in ext2_htree_writebuf()
471 target = level->h_entry + 1; in ext2_htree_insert_entry_to_level()
472 entries_num = ext2_htree_get_count(level->h_entries); in ext2_htree_insert_entry_to_level()
474 memmove(target + 1, target, (char *)(level->h_entries + entries_num) - in ext2_htree_insert_entry_to_level()
478 ext2_htree_set_count(level->h_entries, entries_num + 1); in ext2_htree_insert_entry_to_level()
490 level = &info->h_levels[info->h_levels_num - 1]; in ext2_htree_insert_entry()
506 if (le32toh(entry1->h_hash) < le32toh(entry2->h_hash)) in ext2_htree_cmp_sort_entry()
507 return (-1); in ext2_htree_cmp_sort_entry()
508 if (le32toh(entry1->h_hash) > le32toh(entry2->h_hash)) in ext2_htree_cmp_sort_entry()
514 * Append an entry to the end of the directory block.
517 ext2_append_entry(char *block, uint32_t blksize, in ext2_append_entry() argument
523 entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen); in ext2_append_entry()
524 last_entry->e2d_reclen = htole16(entry_len); in ext2_append_entry()
526 new_entry->e2d_reclen = htole16(block + blksize - (char *)last_entry - in ext2_append_entry()
528 memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen)); in ext2_append_entry()
532 * Move half of entries from the old directory block to the new one.
535 ext2_htree_split_dirblock(struct inode *ip, char *block1, char *block2, in ext2_htree_split_dirblock() argument
550 fs = ip->i_e2fs; in ext2_htree_split_dirblock()
562 ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed, in ext2_htree_split_dirblock()
568 while ((char *)ep < block1 + blksize - csum_size) { in ext2_htree_split_dirblock()
569 if (le32toh(ep->e2d_ino) && ep->e2d_namlen) { in ext2_htree_split_dirblock()
571 sort_info--; in ext2_htree_split_dirblock()
572 sort_info->h_size = ep->e2d_reclen; in ext2_htree_split_dirblock()
573 sort_info->h_offset = htole16((char *)ep - block1); in ext2_htree_split_dirblock()
574 ext2_htree_hash(ep->e2d_name, ep->e2d_namlen, in ext2_htree_split_dirblock()
576 &sort_info->h_hash, NULL); in ext2_htree_split_dirblock()
577 sort_info->h_hash = htole32(sort_info->h_hash); in ext2_htree_split_dirblock()
580 ((char *)ep + le16toh(ep->e2d_reclen)); in ext2_htree_split_dirblock()
590 * Count the number of entries to move to directory block 2. in ext2_htree_split_dirblock()
592 for (i = entry_cnt - 1; i >= 0; i--) { in ext2_htree_split_dirblock()
607 * Move half of directory entries from block 1 to block 2. in ext2_htree_split_dirblock()
612 entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); in ext2_htree_split_dirblock()
614 ((struct ext2fs_direct_2 *)dest)->e2d_reclen = in ext2_htree_split_dirblock()
617 ep->e2d_ino = 0; in ext2_htree_split_dirblock()
620 dest -= entry_len; in ext2_htree_split_dirblock()
622 /* Shrink directory entries in block 1. */ in ext2_htree_split_dirblock()
625 for (offset = 0; offset < blksize - csum_size; ) { in ext2_htree_split_dirblock()
627 offset += le16toh(ep->e2d_reclen); in ext2_htree_split_dirblock()
628 if (le32toh(ep->e2d_ino)) { in ext2_htree_split_dirblock()
631 entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); in ext2_htree_split_dirblock()
633 last->e2d_reclen = htole16(entry_len); in ext2_htree_split_dirblock()
638 /* Add entry to block 2. */ in ext2_htree_split_dirblock()
642 /* Adjust length field of last entry of block 1. */ in ext2_htree_split_dirblock()
643 last->e2d_reclen = htole16(block1 + blksize - (char *)last - in ext2_htree_split_dirblock()
646 /* Add entry to block 1. */ in ext2_htree_split_dirblock()
649 /* Adjust length field of last entry of block 2. */ in ext2_htree_split_dirblock()
650 ((struct ext2fs_direct_2 *)dest)->e2d_reclen = in ext2_htree_split_dirblock()
651 htole16(block2 + blksize - dest - csum_size); in ext2_htree_split_dirblock()
684 fs = dp->i_e2fs->e2fs; in ext2_htree_create_index()
685 m_fs = dp->i_e2fs; in ext2_htree_create_index()
686 blksize = m_fs->e2fs_bsize; in ext2_htree_create_index()
694 root = (struct ext2fs_htree_root *)bp->b_data; in ext2_htree_create_index()
695 dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot)); in ext2_htree_create_index()
697 le16toh(dotdot->e2d_reclen)); in ext2_htree_create_index()
698 dirlen = (char *)root + blksize - (char *)ep; in ext2_htree_create_index()
703 ((char *)ep + le16toh(ep->e2d_reclen)); in ext2_htree_create_index()
704 ep->e2d_reclen = htole16(buf1 + blksize - (char *)ep); in ext2_htree_create_index()
706 dp->i_flag |= IN_E3INDEX; in ext2_htree_create_index()
711 dotdot->e2d_reclen = htole16(blksize - EXT2_DIR_REC_LEN(1)); in ext2_htree_create_index()
712 memset(&root->h_info, 0, sizeof(root->h_info)); in ext2_htree_create_index()
713 root->h_info.h_hash_version = fs->e3fs_def_hash_version; in ext2_htree_create_index()
714 root->h_info.h_info_len = sizeof(root->h_info); in ext2_htree_create_index()
715 ext2_htree_set_block(root->h_entries, 1); in ext2_htree_create_index()
716 ext2_htree_set_count(root->h_entries, 1); in ext2_htree_create_index()
717 ext2_htree_set_limit(root->h_entries, in ext2_htree_create_index()
718 ext2_htree_root_limit(dp, sizeof(root->h_info))); in ext2_htree_create_index()
722 info.h_levels[0].h_entries = root->h_entries; in ext2_htree_create_index()
723 info.h_levels[0].h_entry = root->h_entries; in ext2_htree_create_index()
725 hash_version = root->h_info.h_hash_version; in ext2_htree_create_index()
727 hash_version += m_fs->e2fs_uhash; in ext2_htree_create_index()
734 * Write directory block 0. in ext2_htree_create_index()
736 ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data); in ext2_htree_create_index()
743 dp->i_flag |= IN_CHANGE | IN_UPDATE; in ext2_htree_create_index()
748 * Write directory block 1. in ext2_htree_create_index()
756 * Write directory block 2. in ext2_htree_create_index()
785 struct inode *ip; in ext2_htree_add_entry() local
800 ip = VTOI(dvp); in ext2_htree_add_entry()
801 m_fs = ip->i_e2fs; in ext2_htree_add_entry()
802 fs = m_fs->e2fs; in ext2_htree_add_entry()
803 blksize = m_fs->e2fs_bsize; in ext2_htree_add_entry()
805 if (ip->i_count != 0) in ext2_htree_add_entry()
808 /* Target directory block is full, split it */ in ext2_htree_add_entry()
810 error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen, in ext2_htree_add_entry()
815 entries = info.h_levels[info.h_levels_num - 1].h_entries; in ext2_htree_add_entry()
822 memset(&dst_node->h_fake_dirent, 0, in ext2_htree_add_entry()
823 sizeof(dst_node->h_fake_dirent)); in ext2_htree_add_entry()
824 dst_node->h_fake_dirent.e2d_reclen = htole16(blksize); in ext2_htree_add_entry()
826 cursize = roundup(ip->i_size, blksize); in ext2_htree_add_entry()
828 blknum = dirsize / blksize - 1; in ext2_htree_add_entry()
829 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)newidxblock); in ext2_htree_add_entry()
837 dst_node = (struct ext2fs_htree_node *)dst_bp->b_data; in ext2_htree_add_entry()
838 dst_entries = dst_node->h_entries; in ext2_htree_add_entry()
852 dst_ent_num = ent_num - src_ent_num; in ext2_htree_add_entry()
861 ext2_htree_node_limit(ip)); in ext2_htree_add_entry()
870 info.h_levels[1].h_entry - in ext2_htree_add_entry()
879 ext2_dx_csum_set(ip, in ext2_htree_add_entry()
880 (struct ext2fs_direct_2 *)dst_bp->b_data); in ext2_htree_add_entry()
882 ip->i_flag |= IN_CHANGE | IN_UPDATE; in ext2_htree_add_entry()
893 ext2_htree_node_limit(ip)); in ext2_htree_add_entry()
896 info.h_levels[0].h_bp->b_data; in ext2_htree_add_entry()
897 idx_root->h_info.h_ind_levels = 1; in ext2_htree_add_entry()
904 info.h_levels[1].h_entry = info.h_levels[0].h_entry - in ext2_htree_add_entry()
911 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; in ext2_htree_add_entry()
917 /* Split target directory block */ in ext2_htree_add_entry()
920 ext2_htree_split_dirblock(ip, (char *)bp->b_data, newdirblock, blksize, in ext2_htree_add_entry()
922 cursize = roundup(ip->i_size, blksize); in ext2_htree_add_entry()
924 blknum = dirsize / blksize - 1; in ext2_htree_add_entry()
926 /* Add index entry for the new directory block */ in ext2_htree_add_entry()
929 /* Write the new directory block to the end of the directory */ in ext2_htree_add_entry()
930 ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)newdirblock); in ext2_htree_add_entry()
935 /* Write the target directory block */ in ext2_htree_add_entry()
936 ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data); in ext2_htree_add_entry()
938 ip->i_flag |= IN_CHANGE | IN_UPDATE; in ext2_htree_add_entry()
943 /* Write the index block */ in ext2_htree_add_entry()
944 error = ext2_htree_writebuf(ip, &info); in ext2_htree_add_entry()