index.c (fa3cacf544636b2dc48cfb2f277a2071f14d66a2) index.c (195c52bdd5d5ecfdabf5a7c6159efe299e534f84)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 *
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
5 *
6 */
7
8#include <linux/blkdev.h>

--- 668 unchanged lines hidden (view full) ---

677#ifdef NTFS3_INDEX_BINARY_SEARCH
678 int max_idx = 0, fnd, min_idx;
679 int nslots = 64;
680 u16 *offs;
681
682 if (end > 0x10000)
683 goto next;
684
1// SPDX-License-Identifier: GPL-2.0
2/*
3 *
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
5 *
6 */
7
8#include <linux/blkdev.h>

--- 668 unchanged lines hidden (view full) ---

677#ifdef NTFS3_INDEX_BINARY_SEARCH
678 int max_idx = 0, fnd, min_idx;
679 int nslots = 64;
680 u16 *offs;
681
682 if (end > 0x10000)
683 goto next;
684
685 offs = ntfs_malloc(sizeof(u16) * nslots);
685 offs = kmalloc(sizeof(u16) * nslots, GFP_NOFS);
686 if (!offs)
687 goto next;
688
689 /* use binary search algorithm */
690next1:
691 if (off + sizeof(struct NTFS_DE) > end) {
692 e = NULL;
693 goto out1;

--- 5 unchanged lines hidden (view full) ---

699 e = NULL;
700 goto out1;
701 }
702
703 if (max_idx >= nslots) {
704 u16 *ptr;
705 int new_slots = ALIGN(2 * nslots, 8);
706
686 if (!offs)
687 goto next;
688
689 /* use binary search algorithm */
690next1:
691 if (off + sizeof(struct NTFS_DE) > end) {
692 e = NULL;
693 goto out1;

--- 5 unchanged lines hidden (view full) ---

699 e = NULL;
700 goto out1;
701 }
702
703 if (max_idx >= nslots) {
704 u16 *ptr;
705 int new_slots = ALIGN(2 * nslots, 8);
706
707 ptr = ntfs_malloc(sizeof(u16) * new_slots);
707 ptr = kmalloc(sizeof(u16) * new_slots, GFP_NOFS);
708 if (ptr)
709 memcpy(ptr, offs, sizeof(u16) * max_idx);
708 if (ptr)
709 memcpy(ptr, offs, sizeof(u16) * max_idx);
710 ntfs_free(offs);
710 kfree(offs);
711 offs = ptr;
712 nslots = new_slots;
713 if (!ptr)
714 goto next;
715 }
716
717 /* Store entry table */
718 offs[max_idx] = off;

--- 40 unchanged lines hidden (view full) ---

759 e = NULL;
760 goto out1;
761 }
762
763 *diff = -1;
764 e = Add2Ptr(hdr, offs[fnd]);
765
766out1:
711 offs = ptr;
712 nslots = new_slots;
713 if (!ptr)
714 goto next;
715 }
716
717 /* Store entry table */
718 offs[max_idx] = off;

--- 40 unchanged lines hidden (view full) ---

759 e = NULL;
760 goto out1;
761 }
762
763 *diff = -1;
764 e = Add2Ptr(hdr, offs[fnd]);
765
766out1:
767 ntfs_free(offs);
767 kfree(offs);
768
769 return e;
770#endif
771
772next:
773 /*
774 * Entries index are sorted
775 * Enumerate all entries until we find entry that is <= to the search value

--- 153 unchanged lines hidden (view full) ---

929 struct indx_node *r;
930 struct INDEX_HDR *hdr;
931 struct INDEX_BUFFER *index;
932 u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
933 u32 bytes = 1u << indx->index_bits;
934 u16 fn;
935 u32 eo;
936
768
769 return e;
770#endif
771
772next:
773 /*
774 * Entries index are sorted
775 * Enumerate all entries until we find entry that is <= to the search value

--- 153 unchanged lines hidden (view full) ---

929 struct indx_node *r;
930 struct INDEX_HDR *hdr;
931 struct INDEX_BUFFER *index;
932 u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
933 u32 bytes = 1u << indx->index_bits;
934 u16 fn;
935 u32 eo;
936
937 r = ntfs_zalloc(sizeof(struct indx_node));
937 r = kzalloc(sizeof(struct indx_node), GFP_NOFS);
938 if (!r)
939 return ERR_PTR(-ENOMEM);
940
938 if (!r)
939 return ERR_PTR(-ENOMEM);
940
941 index = ntfs_zalloc(bytes);
941 index = kzalloc(bytes, GFP_NOFS);
942 if (!index) {
942 if (!index) {
943 ntfs_free(r);
943 kfree(r);
944 return ERR_PTR(-ENOMEM);
945 }
946
947 err = ntfs_get_bh(ni->mi.sbi, &indx->alloc_run, vbo, bytes, &r->nb);
948
949 if (err) {
944 return ERR_PTR(-ENOMEM);
945 }
946
947 err = ntfs_get_bh(ni->mi.sbi, &indx->alloc_run, vbo, bytes, &r->nb);
948
949 if (err) {
950 ntfs_free(index);
951 ntfs_free(r);
950 kfree(index);
951 kfree(r);
952 return ERR_PTR(err);
953 }
954
955 /* Create header */
956 index->rhdr.sign = NTFS_INDX_SIGNATURE;
957 index->rhdr.fix_off = cpu_to_le16(sizeof(struct INDEX_BUFFER)); // 0x28
958 fn = (bytes >> SECTOR_SHIFT) + 1; // 9
959 index->rhdr.fix_num = cpu_to_le16(fn);

--- 62 unchanged lines hidden (view full) ---

1022 struct runs_tree *run = &indx->alloc_run;
1023 struct rw_semaphore *lock = &indx->run_lock;
1024 u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
1025 u32 bytes = 1u << indx->index_bits;
1026 struct indx_node *in = *node;
1027 const struct INDEX_NAMES *name;
1028
1029 if (!in) {
952 return ERR_PTR(err);
953 }
954
955 /* Create header */
956 index->rhdr.sign = NTFS_INDX_SIGNATURE;
957 index->rhdr.fix_off = cpu_to_le16(sizeof(struct INDEX_BUFFER)); // 0x28
958 fn = (bytes >> SECTOR_SHIFT) + 1; // 9
959 index->rhdr.fix_num = cpu_to_le16(fn);

--- 62 unchanged lines hidden (view full) ---

1022 struct runs_tree *run = &indx->alloc_run;
1023 struct rw_semaphore *lock = &indx->run_lock;
1024 u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
1025 u32 bytes = 1u << indx->index_bits;
1026 struct indx_node *in = *node;
1027 const struct INDEX_NAMES *name;
1028
1029 if (!in) {
1030 in = ntfs_zalloc(sizeof(struct indx_node));
1030 in = kzalloc(sizeof(struct indx_node), GFP_NOFS);
1031 if (!in)
1032 return -ENOMEM;
1033 } else {
1034 nb_put(&in->nb);
1035 }
1036
1037 ib = in->index;
1038 if (!ib) {
1031 if (!in)
1032 return -ENOMEM;
1033 } else {
1034 nb_put(&in->nb);
1035 }
1036
1037 ib = in->index;
1038 if (!ib) {
1039 ib = ntfs_malloc(bytes);
1039 ib = kmalloc(bytes, GFP_NOFS);
1040 if (!ib) {
1041 err = -ENOMEM;
1042 goto out;
1043 }
1044 }
1045
1046 down_read(lock);
1047 err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);

--- 30 unchanged lines hidden (view full) ---

1078 err = 0;
1079 }
1080
1081 in->index = ib;
1082 *node = in;
1083
1084out:
1085 if (ib != in->index)
1040 if (!ib) {
1041 err = -ENOMEM;
1042 goto out;
1043 }
1044 }
1045
1046 down_read(lock);
1047 err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);

--- 30 unchanged lines hidden (view full) ---

1078 err = 0;
1079 }
1080
1081 in->index = ib;
1082 *node = in;
1083
1084out:
1085 if (ib != in->index)
1086 ntfs_free(ib);
1086 kfree(ib);
1087
1088 if (*node != in) {
1089 nb_put(&in->nb);
1087
1088 if (*node != in) {
1089 nb_put(&in->nb);
1090 ntfs_free(in);
1090 kfree(in);
1091 }
1092
1093 return err;
1094}
1095
1096/*
1097 * indx_find
1098 *

--- 115 unchanged lines hidden (view full) ---

1214 if (iter++ >= 1000)
1215 return -EINVAL;
1216
1217 while (de_has_vcn_ex(e)) {
1218 if (le16_to_cpu(e->size) <
1219 sizeof(struct NTFS_DE) + sizeof(u64)) {
1220 if (n) {
1221 fnd_pop(fnd);
1091 }
1092
1093 return err;
1094}
1095
1096/*
1097 * indx_find
1098 *

--- 115 unchanged lines hidden (view full) ---

1214 if (iter++ >= 1000)
1215 return -EINVAL;
1216
1217 while (de_has_vcn_ex(e)) {
1218 if (le16_to_cpu(e->size) <
1219 sizeof(struct NTFS_DE) + sizeof(u64)) {
1220 if (n) {
1221 fnd_pop(fnd);
1222 ntfs_free(n);
1222 kfree(n);
1223 }
1224 return -EINVAL;
1225 }
1226
1227 /* Read next level */
1228 err = indx_read(indx, ni, de_get_vbn(e), &n);
1229 if (err)
1230 return err;
1231
1232 /* Try next level */
1233 e = hdr_first_de(&n->index->ihdr);
1234 if (!e) {
1223 }
1224 return -EINVAL;
1225 }
1226
1227 /* Read next level */
1228 err = indx_read(indx, ni, de_get_vbn(e), &n);
1229 if (err)
1230 return err;
1231
1232 /* Try next level */
1233 e = hdr_first_de(&n->index->ihdr);
1234 if (!e) {
1235 ntfs_free(n);
1235 kfree(n);
1236 return -EINVAL;
1237 }
1238
1239 fnd_push(fnd, n, e);
1240 }
1241
1242 if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1243 *entry = e;
1244 return 0;
1245 }
1246
1247pop_level:
1248 for (;;) {
1249 if (!de_is_last(e))
1250 goto next_iter;
1251
1252 /* Pop one level */
1253 if (n) {
1254 fnd_pop(fnd);
1236 return -EINVAL;
1237 }
1238
1239 fnd_push(fnd, n, e);
1240 }
1241
1242 if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1243 *entry = e;
1244 return 0;
1245 }
1246
1247pop_level:
1248 for (;;) {
1249 if (!de_is_last(e))
1250 goto next_iter;
1251
1252 /* Pop one level */
1253 if (n) {
1254 fnd_pop(fnd);
1255 ntfs_free(n);
1255 kfree(n);
1256 }
1257
1258 level = fnd->level;
1259
1260 if (level) {
1261 n = fnd->nodes[level - 1];
1262 e = fnd->de[level - 1];
1263 } else if (fnd->root_de) {

--- 320 unchanged lines hidden (view full) ---

1584 WARN_ON(!e);
1585 fnd_clear(fnd);
1586 fnd->root_de = e;
1587
1588 return 0;
1589 }
1590
1591 /* Make a copy of root attribute to restore if error */
1256 }
1257
1258 level = fnd->level;
1259
1260 if (level) {
1261 n = fnd->nodes[level - 1];
1262 e = fnd->de[level - 1];
1263 } else if (fnd->root_de) {

--- 320 unchanged lines hidden (view full) ---

1584 WARN_ON(!e);
1585 fnd_clear(fnd);
1586 fnd->root_de = e;
1587
1588 return 0;
1589 }
1590
1591 /* Make a copy of root attribute to restore if error */
1592 a_root = ntfs_memdup(attr, asize);
1592 a_root = kmemdup(attr, asize, GFP_NOFS);
1593 if (!a_root) {
1594 err = -ENOMEM;
1595 goto out;
1596 }
1597
1598 /* copy all the non-end entries from the index root to the new buffer.*/
1599 to_move = 0;
1600 e0 = hdr_first_de(hdr);

--- 9 unchanged lines hidden (view full) ---

1610 break;
1611 to_move += le16_to_cpu(e->size);
1612 }
1613
1614 n = NULL;
1615 if (!to_move) {
1616 re = NULL;
1617 } else {
1593 if (!a_root) {
1594 err = -ENOMEM;
1595 goto out;
1596 }
1597
1598 /* copy all the non-end entries from the index root to the new buffer.*/
1599 to_move = 0;
1600 e0 = hdr_first_de(hdr);

--- 9 unchanged lines hidden (view full) ---

1610 break;
1611 to_move += le16_to_cpu(e->size);
1612 }
1613
1614 n = NULL;
1615 if (!to_move) {
1616 re = NULL;
1617 } else {
1618 re = ntfs_memdup(e0, to_move);
1618 re = kmemdup(e0, to_move, GFP_NOFS);
1619 if (!re) {
1620 err = -ENOMEM;
1621 goto out;
1622 }
1623 }
1624
1625 sub_vbn = NULL;
1626 if (de_has_vcn(e)) {

--- 76 unchanged lines hidden (view full) ---

1703 /* Check if we can insert new entry new index buffer */
1704 if (hdr_used + new_de_size > hdr_total) {
1705 /*
1706 * This occurs if mft record is the same or bigger than index
1707 * buffer. Move all root new index and have no space to add
1708 * new entry classic case when mft record is 1K and index
1709 * buffer 4K the problem should not occurs
1710 */
1619 if (!re) {
1620 err = -ENOMEM;
1621 goto out;
1622 }
1623 }
1624
1625 sub_vbn = NULL;
1626 if (de_has_vcn(e)) {

--- 76 unchanged lines hidden (view full) ---

1703 /* Check if we can insert new entry new index buffer */
1704 if (hdr_used + new_de_size > hdr_total) {
1705 /*
1706 * This occurs if mft record is the same or bigger than index
1707 * buffer. Move all root new index and have no space to add
1708 * new entry classic case when mft record is 1K and index
1709 * buffer 4K the problem should not occurs
1710 */
1711 ntfs_free(re);
1711 kfree(re);
1712 indx_write(indx, ni, n, 0);
1713
1714 put_indx_node(n);
1715 fnd_clear(fnd);
1716 err = indx_insert_entry(indx, ni, new_de, ctx, fnd);
1717 goto out;
1718 }
1719

--- 9 unchanged lines hidden (view full) ---

1729 fnd_push(fnd, n, e);
1730
1731 /* Just write updates index into disk */
1732 indx_write(indx, ni, n, 0);
1733
1734 n = NULL;
1735
1736out1:
1712 indx_write(indx, ni, n, 0);
1713
1714 put_indx_node(n);
1715 fnd_clear(fnd);
1716 err = indx_insert_entry(indx, ni, new_de, ctx, fnd);
1717 goto out;
1718 }
1719

--- 9 unchanged lines hidden (view full) ---

1729 fnd_push(fnd, n, e);
1730
1731 /* Just write updates index into disk */
1732 indx_write(indx, ni, n, 0);
1733
1734 n = NULL;
1735
1736out1:
1737 ntfs_free(re);
1737 kfree(re);
1738 if (n)
1739 put_indx_node(n);
1740
1741out:
1738 if (n)
1739 put_indx_node(n);
1740
1741out:
1742 ntfs_free(a_root);
1742 kfree(a_root);
1743 return err;
1744}
1745
1746/*
1747 * indx_insert_into_buffer
1748 *
1749 * attempts to insert an entry into an Index Allocation Buffer.
1750 * If necessary, it will split the buffer.

--- 36 unchanged lines hidden (view full) ---

1787 * - Insert sp into parent buffer (or root)
1788 * - Make sp a parent for new buffer
1789 */
1790 sp = hdr_find_split(hdr1);
1791 if (!sp)
1792 return -EINVAL;
1793
1794 sp_size = le16_to_cpu(sp->size);
1743 return err;
1744}
1745
1746/*
1747 * indx_insert_into_buffer
1748 *
1749 * attempts to insert an entry into an Index Allocation Buffer.
1750 * If necessary, it will split the buffer.

--- 36 unchanged lines hidden (view full) ---

1787 * - Insert sp into parent buffer (or root)
1788 * - Make sp a parent for new buffer
1789 */
1790 sp = hdr_find_split(hdr1);
1791 if (!sp)
1792 return -EINVAL;
1793
1794 sp_size = le16_to_cpu(sp->size);
1795 up_e = ntfs_malloc(sp_size + sizeof(u64));
1795 up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS);
1796 if (!up_e)
1797 return -ENOMEM;
1798 memcpy(up_e, sp, sp_size);
1799
1800 if (!hdr1->flags) {
1801 up_e->flags |= NTFS_IE_HAS_SUBNODES;
1802 up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1803 sub_vbn = NULL;

--- 61 unchanged lines hidden (view full) ---

1865 */
1866 err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1867 level - 1, fnd);
1868 if (err)
1869 goto out;
1870 }
1871
1872out:
1796 if (!up_e)
1797 return -ENOMEM;
1798 memcpy(up_e, sp, sp_size);
1799
1800 if (!hdr1->flags) {
1801 up_e->flags |= NTFS_IE_HAS_SUBNODES;
1802 up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1803 sub_vbn = NULL;

--- 61 unchanged lines hidden (view full) ---

1865 */
1866 err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1867 level - 1, fnd);
1868 if (err)
1869 goto out;
1870 }
1871
1872out:
1873 ntfs_free(up_e);
1873 kfree(up_e);
1874
1875 return err;
1876}
1877
1878/*
1879 * indx_insert_entry
1880 *
1881 * inserts new entry into index

--- 262 unchanged lines hidden (view full) ---

2144 }
2145
2146 if (level == -1)
2147 goto out;
2148
2149 n = fnd->nodes[level];
2150 te = hdr_first_de(&n->index->ihdr);
2151 /* Copy the candidate entry into the replacement entry buffer. */
1874
1875 return err;
1876}
1877
1878/*
1879 * indx_insert_entry
1880 *
1881 * inserts new entry into index

--- 262 unchanged lines hidden (view full) ---

2144 }
2145
2146 if (level == -1)
2147 goto out;
2148
2149 n = fnd->nodes[level];
2150 te = hdr_first_de(&n->index->ihdr);
2151 /* Copy the candidate entry into the replacement entry buffer. */
2152 re = ntfs_malloc(le16_to_cpu(te->size) + sizeof(u64));
2152 re = kmalloc(le16_to_cpu(te->size) + sizeof(u64), GFP_NOFS);
2153 if (!re) {
2154 err = -ENOMEM;
2155 goto out;
2156 }
2157
2158 *de_to_replace = re;
2159 memcpy(re, te, le16_to_cpu(te->size));
2160

--- 135 unchanged lines hidden (view full) ---

2296 hdr_delete_de(hdr, e);
2297
2298 err = level ? indx_insert_into_buffer(indx, ni, root,
2299 re, ctx,
2300 fnd->level - 1,
2301 fnd)
2302 : indx_insert_into_root(indx, ni, re, e,
2303 ctx, fnd);
2153 if (!re) {
2154 err = -ENOMEM;
2155 goto out;
2156 }
2157
2158 *de_to_replace = re;
2159 memcpy(re, te, le16_to_cpu(te->size));
2160

--- 135 unchanged lines hidden (view full) ---

2296 hdr_delete_de(hdr, e);
2297
2298 err = level ? indx_insert_into_buffer(indx, ni, root,
2299 re, ctx,
2300 fnd->level - 1,
2301 fnd)
2302 : indx_insert_into_root(indx, ni, re, e,
2303 ctx, fnd);
2304 ntfs_free(re);
2304 kfree(re);
2305
2306 if (err)
2307 goto out;
2308 } else {
2309 /*
2310 * There is no replacement for the current entry.
2311 * This means that the subtree rooted at its node is empty,
2312 * and can be deleted, which turn means that the node can

--- 141 unchanged lines hidden (view full) ---

2454 }
2455
2456 /*
2457 * Copy the current entry into a temporary buffer (stripping off its
2458 * down-pointer, if any) and delete it from the current buffer or root,
2459 * as appropriate.
2460 */
2461 e_size = le16_to_cpu(e->size);
2305
2306 if (err)
2307 goto out;
2308 } else {
2309 /*
2310 * There is no replacement for the current entry.
2311 * This means that the subtree rooted at its node is empty,
2312 * and can be deleted, which turn means that the node can

--- 141 unchanged lines hidden (view full) ---

2454 }
2455
2456 /*
2457 * Copy the current entry into a temporary buffer (stripping off its
2458 * down-pointer, if any) and delete it from the current buffer or root,
2459 * as appropriate.
2460 */
2461 e_size = le16_to_cpu(e->size);
2462 me = ntfs_memdup(e, e_size);
2462 me = kmemdup(e, e_size, GFP_NOFS);
2463 if (!me) {
2464 err = -ENOMEM;
2465 goto out;
2466 }
2467
2468 if (de_has_vcn(me)) {
2469 me->flags &= ~NTFS_IE_HAS_SUBNODES;
2470 le16_sub_cpu(&me->size, sizeof(u64));

--- 29 unchanged lines hidden (view full) ---

2500 fnd_clear(fnd);
2501 /*fnd->root_de = NULL;*/
2502
2503 /*
2504 * Re-insert the entry into the tree.
2505 * Find the spot the tree where we want to insert the new entry.
2506 */
2507 err = indx_insert_entry(indx, ni, me, ctx, fnd);
2463 if (!me) {
2464 err = -ENOMEM;
2465 goto out;
2466 }
2467
2468 if (de_has_vcn(me)) {
2469 me->flags &= ~NTFS_IE_HAS_SUBNODES;
2470 le16_sub_cpu(&me->size, sizeof(u64));

--- 29 unchanged lines hidden (view full) ---

2500 fnd_clear(fnd);
2501 /*fnd->root_de = NULL;*/
2502
2503 /*
2504 * Re-insert the entry into the tree.
2505 * Find the spot the tree where we want to insert the new entry.
2506 */
2507 err = indx_insert_entry(indx, ni, me, ctx, fnd);
2508 ntfs_free(me);
2508 kfree(me);
2509 if (err)
2510 goto out;
2511
2512 if (trim_bit != -1)
2513 indx_shrink(indx, ni, trim_bit);
2514 } else {
2515 /*
2516 * This tree needs to be collapsed down to an empty root.

--- 132 unchanged lines hidden --- 		2509 if (err)
2510 goto out;
2511
2512 if (trim_bit != -1)
2513 indx_shrink(indx, ni, trim_bit);
2514 } else {
2515 /*
2516 * This tree needs to be collapsed down to an empty root.

--- 132 unchanged lines hidden ---