aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAnton Altaparmakov <aia21@cantab.net>2005-09-08 15:26:34 -0400
committerAnton Altaparmakov <aia21@cantab.net>2005-09-08 15:26:34 -0400
commit6e48321a40610f7213e3ac75ba234f6f8b3ed5f5 (patch)
tree6ba4b289e1fd0c8a3554a75206c4d2a88b54d1bc
parent3ffc5a443824fcf426d8d35dc632acc4dd9fb6d1 (diff)
NTFS: Add ntfs_rl_punch_nolock() which punches a caller specified hole into a runlist.
Signed-off-by: Anton Altaparmakov <aia21@cantab.net>
-rw-r--r--fs/ntfs/ChangeLog2
-rw-r--r--fs/ntfs/runlist.c284
-rw-r--r--fs/ntfs/runlist.h3
3 files changed, 289 insertions, 0 deletions
diff --git a/fs/ntfs/ChangeLog b/fs/ntfs/ChangeLog
index 79d9899b3b01..39dca6dced11 100644
--- a/fs/ntfs/ChangeLog
+++ b/fs/ntfs/ChangeLog
@@ -53,6 +53,8 @@ ToDo/Notes:
53 pointing this out. 53 pointing this out.
54 - Change ntfs_rl_truncate_nolock() to throw away the runlist if the new 54 - Change ntfs_rl_truncate_nolock() to throw away the runlist if the new
55 length is zero. 55 length is zero.
56 - Add runlist.[hc]::ntfs_rl_punch_nolock() which punches a caller
57 specified hole into a runlist.
56 58
572.1.23 - Implement extension of resident files and make writing safe as well as 592.1.23 - Implement extension of resident files and make writing safe as well as
58 many bug fixes, cleanups, and enhancements... 60 many bug fixes, cleanups, and enhancements...
diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index 539fa2b7f361..f5b2ac929081 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -1601,4 +1601,288 @@ int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
1601 return 0; 1601 return 0;
1602} 1602}
1603 1603
1604/**
1605 * ntfs_rl_punch_nolock - punch a hole into a runlist
1606 * @vol: ntfs volume (needed for error output)
1607 * @runlist: runlist to punch a hole into
1608 * @start: starting VCN of the hole to be created
1609 * @length: size of the hole to be created in units of clusters
1610 *
1611 * Punch a hole into the runlist @runlist starting at VCN @start and of size
1612 * @length clusters.
1613 *
1614 * Return 0 on success and -errno on error, in which case @runlist has not been
1615 * modified.
1616 *
1617 * If @start and/or @start + @length are outside the runlist return error code
1618 * -ENOENT.
1619 *
1620 * If the runlist contains unmapped or error elements between @start and @start
1621 * + @length return error code -EINVAL.
1622 *
1623 * Locking: The caller must hold @runlist->lock for writing.
1624 */
1625int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
1626 const VCN start, const s64 length)
1627{
1628 const VCN end = start + length;
1629 s64 delta;
1630 runlist_element *rl, *rl_end, *rl_real_end, *trl;
1631 int old_size;
1632 BOOL lcn_fixup = FALSE;
1633
1634 ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
1635 (long long)start, (long long)length);
1636 BUG_ON(!runlist);
1637 BUG_ON(start < 0);
1638 BUG_ON(length < 0);
1639 BUG_ON(end < 0);
1640 rl = runlist->rl;
1641 if (unlikely(!rl)) {
1642 if (likely(!start && !length))
1643 return 0;
1644 return -ENOENT;
1645 }
1646 /* Find @start in the runlist. */
1647 while (likely(rl->length && start >= rl[1].vcn))
1648 rl++;
1649 rl_end = rl;
1650 /* Find @end in the runlist. */
1651 while (likely(rl_end->length && end >= rl_end[1].vcn)) {
1652 /* Verify there are no unmapped or error elements. */
1653 if (unlikely(rl_end->lcn < LCN_HOLE))
1654 return -EINVAL;
1655 rl_end++;
1656 }
1657 /* Check the last element. */
1658 if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
1659 return -EINVAL;
1660 /* This covers @start being out of bounds, too. */
1661 if (!rl_end->length && end > rl_end->vcn)
1662 return -ENOENT;
1663 if (!length)
1664 return 0;
1665 if (!rl->length)
1666 return -ENOENT;
1667 rl_real_end = rl_end;
1668 /* Determine the runlist size. */
1669 while (likely(rl_real_end->length))
1670 rl_real_end++;
1671 old_size = rl_real_end - runlist->rl + 1;
1672 /* If @start is in a hole simply extend the hole. */
1673 if (rl->lcn == LCN_HOLE) {
1674 /*
1675 * If both @start and @end are in the same sparse run, we are
1676 * done.
1677 */
1678 if (end <= rl[1].vcn) {
1679 ntfs_debug("Done (requested hole is already sparse).");
1680 return 0;
1681 }
1682extend_hole:
1683 /* Extend the hole. */
1684 rl->length = end - rl->vcn;
1685 /* If @end is in a hole, merge it with the current one. */
1686 if (rl_end->lcn == LCN_HOLE) {
1687 rl_end++;
1688 rl->length = rl_end->vcn - rl->vcn;
1689 }
1690 /* We have done the hole. Now deal with the remaining tail. */
1691 rl++;
1692 /* Cut out all runlist elements up to @end. */
1693 if (rl < rl_end)
1694 memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1695 sizeof(*rl));
1696 /* Adjust the beginning of the tail if necessary. */
1697 if (end > rl->vcn) {
1698 s64 delta = end - rl->vcn;
1699 rl->vcn = end;
1700 rl->length -= delta;
1701 /* Only adjust the lcn if it is real. */
1702 if (rl->lcn >= 0)
1703 rl->lcn += delta;
1704 }
1705shrink_allocation:
1706 /* Reallocate memory if the allocation changed. */
1707 if (rl < rl_end) {
1708 rl = ntfs_rl_realloc(runlist->rl, old_size,
1709 old_size - (rl_end - rl));
1710 if (IS_ERR(rl))
1711 ntfs_warning(vol->sb, "Failed to shrink "
1712 "runlist buffer. This just "
1713 "wastes a bit of memory "
1714 "temporarily so we ignore it "
1715 "and return success.");
1716 else
1717 runlist->rl = rl;
1718 }
1719 ntfs_debug("Done (extend hole).");
1720 return 0;
1721 }
1722 /*
1723 * If @start is at the beginning of a run things are easier as there is
1724 * no need to split the first run.
1725 */
1726 if (start == rl->vcn) {
1727 /*
1728 * @start is at the beginning of a run.
1729 *
1730 * If the previous run is sparse, extend its hole.
1731 *
1732 * If @end is not in the same run, switch the run to be sparse
1733 * and extend the newly created hole.
1734 *
1735 * Thus both of these cases reduce the problem to the above
1736 * case of "@start is in a hole".
1737 */
1738 if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
1739 rl--;
1740 goto extend_hole;
1741 }
1742 if (end >= rl[1].vcn) {
1743 rl->lcn = LCN_HOLE;
1744 goto extend_hole;
1745 }
1746 /*
1747 * The final case is when @end is in the same run as @start.
1748 * For this need to split the run into two. One run for the
1749 * sparse region between the beginning of the old run, i.e.
1750 * @start, and @end and one for the remaining non-sparse
1751 * region, i.e. between @end and the end of the old run.
1752 */
1753 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1754 if (IS_ERR(trl))
1755 goto enomem_out;
1756 old_size++;
1757 if (runlist->rl != trl) {
1758 rl = trl + (rl - runlist->rl);
1759 rl_end = trl + (rl_end - runlist->rl);
1760 rl_real_end = trl + (rl_real_end - runlist->rl);
1761 runlist->rl = trl;
1762 }
1763split_end:
1764 /* Shift all the runs up by one. */
1765 memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1766 /* Finally, setup the two split runs. */
1767 rl->lcn = LCN_HOLE;
1768 rl->length = length;
1769 rl++;
1770 rl->vcn += length;
1771 /* Only adjust the lcn if it is real. */
1772 if (rl->lcn >= 0 || lcn_fixup)
1773 rl->lcn += length;
1774 rl->length -= length;
1775 ntfs_debug("Done (split one).");
1776 return 0;
1777 }
1778 /*
1779 * @start is neither in a hole nor at the beginning of a run.
1780 *
1781 * If @end is in a hole, things are easier as simply truncating the run
1782 * @start is in to end at @start - 1, deleting all runs after that up
1783 * to @end, and finally extending the beginning of the run @end is in
1784 * to be @start is all that is needed.
1785 */
1786 if (rl_end->lcn == LCN_HOLE) {
1787 /* Truncate the run containing @start. */
1788 rl->length = start - rl->vcn;
1789 rl++;
1790 /* Cut out all runlist elements up to @end. */
1791 if (rl < rl_end)
1792 memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1793 sizeof(*rl));
1794 /* Extend the beginning of the run @end is in to be @start. */
1795 rl->vcn = start;
1796 rl->length = rl[1].vcn - start;
1797 goto shrink_allocation;
1798 }
1799 /*
1800 * If @end is not in a hole there are still two cases to distinguish.
1801 * Either @end is or is not in the same run as @start.
1802 *
1803 * The second case is easier as it can be reduced to an already solved
1804 * problem by truncating the run @start is in to end at @start - 1.
1805 * Then, if @end is in the next run need to split the run into a sparse
1806 * run followed by a non-sparse run (already covered above) and if @end
1807 * is not in the next run switching it to be sparse, again reduces the
1808 * problem to the already covered case of "@start is in a hole".
1809 */
1810 if (end >= rl[1].vcn) {
1811 /*
1812 * If @end is not in the next run, reduce the problem to the
1813 * case of "@start is in a hole".
1814 */
1815 if (rl[1].length && end >= rl[2].vcn) {
1816 /* Truncate the run containing @start. */
1817 rl->length = start - rl->vcn;
1818 rl++;
1819 rl->vcn = start;
1820 rl->lcn = LCN_HOLE;
1821 goto extend_hole;
1822 }
1823 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1824 if (IS_ERR(trl))
1825 goto enomem_out;
1826 old_size++;
1827 if (runlist->rl != trl) {
1828 rl = trl + (rl - runlist->rl);
1829 rl_end = trl + (rl_end - runlist->rl);
1830 rl_real_end = trl + (rl_real_end - runlist->rl);
1831 runlist->rl = trl;
1832 }
1833 /* Truncate the run containing @start. */
1834 rl->length = start - rl->vcn;
1835 rl++;
1836 /*
1837 * @end is in the next run, reduce the problem to the case
1838 * where "@start is at the beginning of a run and @end is in
1839 * the same run as @start".
1840 */
1841 delta = rl->vcn - start;
1842 rl->vcn = start;
1843 if (rl->lcn >= 0) {
1844 rl->lcn -= delta;
1845 /* Need this in case the lcn just became negative. */
1846 lcn_fixup = TRUE;
1847 }
1848 rl->length += delta;
1849 goto split_end;
1850 }
1851 /*
1852 * The first case from above, i.e. @end is in the same run as @start.
1853 * We need to split the run into three. One run for the non-sparse
1854 * region between the beginning of the old run and @start, one for the
1855 * sparse region between @start and @end, and one for the remaining
1856 * non-sparse region, i.e. between @end and the end of the old run.
1857 */
1858 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
1859 if (IS_ERR(trl))
1860 goto enomem_out;
1861 old_size += 2;
1862 if (runlist->rl != trl) {
1863 rl = trl + (rl - runlist->rl);
1864 rl_end = trl + (rl_end - runlist->rl);
1865 rl_real_end = trl + (rl_real_end - runlist->rl);
1866 runlist->rl = trl;
1867 }
1868 /* Shift all the runs up by two. */
1869 memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1870 /* Finally, setup the three split runs. */
1871 rl->length = start - rl->vcn;
1872 rl++;
1873 rl->vcn = start;
1874 rl->lcn = LCN_HOLE;
1875 rl->length = length;
1876 rl++;
1877 delta = end - rl->vcn;
1878 rl->vcn = end;
1879 rl->lcn += delta;
1880 rl->length -= delta;
1881 ntfs_debug("Done (split both).");
1882 return 0;
1883enomem_out:
1884 ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
1885 return -ENOMEM;
1886}
1887
1604#endif /* NTFS_RW */ 1888#endif /* NTFS_RW */
diff --git a/fs/ntfs/runlist.h b/fs/ntfs/runlist.h
index aa0ee6540e7c..47728fbb610b 100644
--- a/fs/ntfs/runlist.h
+++ b/fs/ntfs/runlist.h
@@ -94,6 +94,9 @@ extern int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
94extern int ntfs_rl_truncate_nolock(const ntfs_volume *vol, 94extern int ntfs_rl_truncate_nolock(const ntfs_volume *vol,
95 runlist *const runlist, const s64 new_length); 95 runlist *const runlist, const s64 new_length);
96 96
97int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
98 const VCN start, const s64 length);
99
97#endif /* NTFS_RW */ 100#endif /* NTFS_RW */
98 101
99#endif /* _LINUX_NTFS_RUNLIST_H */ 102#endif /* _LINUX_NTFS_RUNLIST_H */