Lines Matching refs:icx
73 static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
75 return vcn << icx->vcn_size_bits;
78 static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos)
80 return pos >> icx->vcn_size_bits;
83 static int ntfs_ib_write(ntfs_index_context *icx, INDEX_BLOCK *ib)
89 ret = ntfs_attr_mst_pwrite(icx->ia_na, ntfs_ib_vcn_to_pos(icx, vcn),
90 1, icx->block_size, ib);
93 (long long)vcn, (unsigned long long)icx->ni->mft_no);
100 static int ntfs_icx_ib_write(ntfs_index_context *icx)
102 if (ntfs_ib_write(icx, icx->ib))
105 icx->ib_dirty = FALSE;
122 ntfs_index_context *icx;
132 icx = ntfs_calloc(sizeof(ntfs_index_context));
133 if (icx)
134 *icx = (ntfs_index_context) {
139 return icx;
142 static void ntfs_index_ctx_free(ntfs_index_context *icx)
146 if (!icx->bad_index && !icx->entry)
149 if (icx->actx)
150 ntfs_attr_put_search_ctx(icx->actx);
152 if (!icx->is_in_root) {
153 if (icx->ib_dirty) {
155 ntfs_ib_write(icx, icx->ib);
157 free(icx->ib);
160 ntfs_attr_close(icx->ia_na);
165 * @icx: index context to free
167 * Release the index context @icx, releasing all associated resources.
169 void ntfs_index_ctx_put(ntfs_index_context *icx)
171 ntfs_index_ctx_free(icx);
172 free(icx);
177 * @icx: index context to reinitialize
179 * Reinitialize the index context @icx so it can be used for ntfs_index_lookup.
181 void ntfs_index_ctx_reinit(ntfs_index_context *icx)
185 ntfs_index_ctx_free(icx);
187 *icx = (ntfs_index_context) {
188 .ni = icx->ni,
189 .name = icx->name,
190 .name_len = icx->name_len,
576 ntfs_index_context *icx, INDEX_HEADER *ih,
598 (unsigned long long)icx->ni->mft_no);
611 if (!icx->collate) {
617 if (ntfs_index_entry_inconsistent(ie, icx->ir->collation_rule,
618 icx->ni->mft_no)) {
622 rc = icx->collate(icx->ni->vol, key, key_len,
641 icx->parent_pos[icx->pindex] = item;
664 (unsigned long long)icx->ni->mft_no);
669 icx->parent_pos[icx->pindex] = item;
674 static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni)
678 na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len);
688 static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst)
694 pos = ntfs_ib_vcn_to_pos(icx, vcn);
696 ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst);
706 if (ntfs_index_block_inconsistent((INDEX_BLOCK*)dst, icx->block_size,
707 icx->ia_na->ni->mft_no, vcn)) {
715 static int ntfs_icx_parent_inc(ntfs_index_context *icx)
717 icx->pindex++;
718 if (icx->pindex >= MAX_PARENT_VCN) {
726 static int ntfs_icx_parent_dec(ntfs_index_context *icx)
728 icx->pindex--;
729 if (icx->pindex < 0) {
731 ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex);
741 * @icx: [IN/OUT] context describing the index and the returned entry
743 * Before calling ntfs_index_lookup(), @icx must have been obtained from a
746 * Look for the @key in the index specified by the index lookup context @icx.
749 * If the @key is found in the index, 0 is returned and @icx is setup to
750 * describe the index entry containing the matching @key. @icx->entry is the
751 * index entry and @icx->data and @icx->data_len are the index entry data and
755 * @icx is setup to describe the index entry whose key collates immediately
759 * If an error occurs return -1, set errno to error code and @icx is left
769 int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx)
772 ntfs_inode *ni = icx->ni;
786 ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx);
793 icx->block_size = le32_to_cpu(ir->index_block_size);
794 if (icx->block_size < NTFS_BLOCK_SIZE) {
797 "sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE);
801 if (ni->vol->cluster_size <= icx->block_size)
802 icx->vcn_size_bits = ni->vol->cluster_size_bits;
804 icx->vcn_size_bits = NTFS_BLOCK_SIZE_BITS;
806 icx->ir = ir;
807 icx->collate = ntfs_get_collate_function(ir->collation_rule);
808 if (!icx->collate) {
816 ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
822 icx->ir = ir;
827 icx->is_in_root = TRUE;
828 icx->parent_vcn[icx->pindex] = old_vcn;
834 icx->ia_na = ntfs_ia_open(icx, ni);
835 if (!icx->ia_na)
838 ib = ntfs_malloc(icx->block_size);
846 icx->parent_vcn[icx->pindex] = old_vcn;
847 if (ntfs_icx_parent_inc(icx)) {
855 if (ntfs_ib_read(icx, vcn, ib))
858 ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
865 icx->is_in_root = FALSE;
866 icx->ib = ib;
867 icx->parent_vcn[icx->pindex] = vcn;
880 icx->bad_index = TRUE; /* Force icx->* to be freed */
882 if (icx->actx) {
883 ntfs_attr_put_search_ctx(icx->actx);
884 icx->actx = NULL;
892 icx->entry = ie;
893 icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
894 icx->data_len = le16_to_cpu(ie->key_length);
966 static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
968 return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size;
971 static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos)
973 return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size);
976 static int ntfs_ibm_add(ntfs_index_context *icx)
982 if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len))
988 if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len,
997 static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set)
1000 s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
1008 na = ntfs_attr_open(icx->ni, AT_BITMAP, icx->name, icx->name_len);
1045 static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
1047 return ntfs_ibm_modify(icx, vcn, 1);
1050 static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
1052 return ntfs_ibm_modify(icx, vcn, 0);
1055 static VCN ntfs_ibm_get_free(ntfs_index_context *icx)
1063 bm = ntfs_attr_readall(icx->ni, AT_BITMAP, icx->name, icx->name_len,
1075 vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit);
1081 vcn = ntfs_ibm_pos_to_vcn(icx, size * 8);
1085 if (ntfs_ibm_set(icx, vcn))
1142 static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src,
1152 dst = ntfs_ib_alloc(new_vcn, icx->block_size,
1165 ret = ntfs_ib_write(icx, dst);
1171 static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib,
1191 if (ntfs_ib_write(icx, ib))
1197 static int ntfs_ia_add(ntfs_index_context *icx)
1201 if (ntfs_ibm_add(icx))
1204 if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
1206 if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name,
1207 icx->name_len, NULL, 0)) {
1213 icx->ia_na = ntfs_ia_open(icx, icx->ni);
1214 if (!icx->ia_na)
1220 static int ntfs_ir_reparent(ntfs_index_context *icx)
1232 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1237 if (ntfs_ia_add(icx))
1240 new_ib_vcn = ntfs_ibm_get_free(icx);
1244 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1254 if (ntfs_ib_write(icx, ib))
1258 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
1281 && (ctx->al_entry || !ntfs_inode_add_attrlist(icx->ni))) {
1284 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len,
1310 ntfs_ibm_clear(icx, new_ib_vcn);
1319 static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
1326 na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
1338 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1339 if (!icx->ir)
1342 icx->ir->index.allocated_size = cpu_to_le32(data_size);
1357 static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
1363 ret = ntfs_ir_truncate(icx, data_size);
1366 ret = ntfs_ir_reparent(icx);
1424 static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx)
1426 return icx->parent_vcn[icx->pindex];
1429 static VCN ntfs_icx_parent_pos(ntfs_index_context *icx)
1431 return icx->parent_pos[icx->pindex];
1435 static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median,
1443 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1444 if (!icx->ir)
1447 new_size = le32_to_cpu(icx->ir->index.index_length) +
1452 ret = ntfs_ir_make_space(icx, new_size);
1456 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1457 if (!icx->ir)
1460 return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
1461 ntfs_icx_parent_pos(icx));
1464 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib);
1470 static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1479 ib = ntfs_malloc(icx->block_size);
1483 old_vcn = ntfs_icx_parent_vcn(icx);
1485 if (ntfs_ib_read(icx, old_vcn, ib))
1492 err = ntfs_ib_split(icx, ib);
1498 if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1501 if (ntfs_ib_write(icx, ib))
1516 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib)
1524 if (ntfs_icx_parent_dec(icx))
1528 new_vcn = ntfs_ibm_get_free(icx);
1532 if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) {
1533 ntfs_ibm_clear(icx, new_vcn);
1537 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1538 ret = ntfs_ir_insert_median(icx, median, new_vcn);
1540 ret = ntfs_ib_insert(icx, median, new_vcn);
1543 ntfs_ibm_clear(icx, new_vcn);
1547 ret = ntfs_ib_cut_tail(icx, ib, median);
1553 int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1570 if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1580 if (icx->is_in_root)
1581 ih = &icx->ir->index;
1583 ih = &icx->ib->index;
1594 if (icx->is_in_root) {
1595 if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR)
1598 if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR)
1602 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1603 ntfs_index_ctx_reinit(icx);
1606 ntfs_ie_insert(ih, ie, icx->entry);
1607 ntfs_index_entry_mark_dirty(icx);
1626 ntfs_index_context *icx;
1650 icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4);
1651 if (!icx)
1654 ret = ntfs_ie_add(icx, ie);
1656 ntfs_index_ctx_put(icx);
1663 static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih,
1680 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1688 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1691 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1693 if (ntfs_ib_write(icx, ib))
1696 ntfs_index_ctx_reinit(icx);
1698 ret = ntfs_ie_add(icx, ie_roam);
1708 static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih)
1722 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1729 static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih,
1736 ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1741 return ntfs_ih_takeout(icx, ih, ie_prev, ib);
1744 static int ntfs_index_rm_leaf(ntfs_index_context *icx)
1751 ntfs_log_trace("pindex: %d\n", icx->pindex);
1753 if (ntfs_icx_parent_dec(icx))
1756 if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]))
1759 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1760 parent_ih = &icx->ir->index;
1762 ib = ntfs_malloc(icx->block_size);
1766 if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib))
1772 ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1774 ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1780 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1781 ntfs_ir_leafify(icx, parent_ih);
1785 ret = ntfs_index_rm_leaf(icx);
1789 if (ntfs_ih_reparent_end(icx, parent_ih, ib))
1798 static int ntfs_index_rm_node(ntfs_index_context *icx)
1803 INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1810 if (!icx->ia_na) {
1811 icx->ia_na = ntfs_ia_open(icx, icx->ni);
1812 if (!icx->ia_na)
1816 ib = ntfs_malloc(icx->block_size);
1820 ie_succ = ntfs_ie_get_next(icx->entry);
1821 entry_pos = icx->parent_pos[icx->pindex]++;
1822 pindex = icx->pindex;
1825 if (ntfs_ib_read(icx, vcn, ib))
1830 if (ntfs_icx_parent_inc(icx))
1833 icx->parent_vcn[icx->pindex] = vcn;
1834 icx->parent_pos[icx->pindex] = 0;
1852 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1854 if (icx->is_in_root)
1855 ih = &icx->ir->index;
1857 ih = &icx->ib->index;
1859 delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1862 if (icx->is_in_root) {
1863 ret = ntfs_ir_make_space(icx, new_size);
1867 ih = &icx->ir->index;
1871 icx->pindex = pindex;
1872 ret = ntfs_ib_split(icx, icx->ib);
1882 if (icx->is_in_root) {
1883 if (ntfs_ir_truncate(icx, new_size))
1886 if (ntfs_icx_ib_write(icx))
1892 if (ntfs_index_rm_leaf(icx))
1895 if (ntfs_ib_write(icx, ib))
1908 * @icx: index context describing entry to delete
1910 * Delete entry described by @icx from the index. Index context is always
1917 int ntfs_index_rm(ntfs_index_context *icx)
1924 if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
1929 if (icx->is_in_root)
1930 ih = &icx->ir->index;
1932 ih = &icx->ib->index;
1934 if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
1936 ret = ntfs_index_rm_node(icx);
1938 } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
1940 ntfs_ie_delete(ih, icx->entry);
1942 if (icx->is_in_root) {
1943 err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1947 if (ntfs_icx_ib_write(icx))
1950 if (ntfs_index_rm_leaf(icx))
1965 ntfs_index_context *icx;
1967 icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4);
1968 if (!icx)
1973 if (ntfs_index_lookup(key, keylen, icx))
1976 ret = ntfs_index_rm(icx);
1982 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1983 ntfs_index_ctx_reinit(icx);
1986 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1988 ntfs_index_ctx_put(icx);