path: root/fs/ntfs/lcnalloc.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Cluster (de)allocation code.
 *
 * Copyright (c) 2004-2005 Anton Altaparmakov
 * Copyright (c) 2025 LG Electronics Co., Ltd.
 *
 * Part of this file is based on code from the NTFS-3G.
 * and is copyrighted by the respective authors below:
 * Copyright (c) 2002-2004 Anton Altaparmakov
 * Copyright (c) 2004 Yura Pakhuchiy
 * Copyright (c) 2004-2008 Szabolcs Szakacsits
 * Copyright (c) 2008-2009 Jean-Pierre Andre
 */

#include <linux/blkdev.h>

#include "lcnalloc.h"
#include "bitmap.h"
#include "ntfs.h"

/*
 * ntfs_cluster_free_from_rl_nolock - free clusters from runlist
 * @vol:	mounted ntfs volume on which to free the clusters
 * @rl:		runlist describing the clusters to free
 *
 * Free all the clusters described by the runlist @rl on the volume @vol.  In
 * the case of an error being returned, at least some of the clusters were not
 * freed.
 *
 * Return 0 on success and -errno on error.
 *
 * Locking: - The volume lcn bitmap must be locked for writing on entry and is
 *	      left locked on return.
 */
int ntfs_cluster_free_from_rl_nolock(struct ntfs_volume *vol,
		const struct runlist_element *rl)
{
	struct inode *lcnbmp_vi = vol->lcnbmp_ino;
	int ret = 0;
	s64 nr_freed = 0;

	ntfs_debug("Entering.");
	if (!rl)
		return 0;

	if (!NVolFreeClusterKnown(vol))
		wait_event(vol->free_waitq, NVolFreeClusterKnown(vol));

	for (; rl->length; rl++) {
		int err;

		if (rl->lcn < 0)
			continue;
		err = ntfs_bitmap_clear_run(lcnbmp_vi, rl->lcn, rl->length);
		if (unlikely(err && (!ret || ret == -ENOMEM) && ret != err))
			ret = err;
		else
			nr_freed += rl->length;
	}
	ntfs_inc_free_clusters(vol, nr_freed);
	ntfs_debug("Done.");
	return ret;
}

static s64 max_empty_bit_range(unsigned char *buf, int size)
{
	int i, j, run = 0;
	int max_range = 0;
	s64 start_pos = -1;

	ntfs_debug("Entering\n");

	i = 0;
	while (i < size) {
		switch (*buf) {
		case 0:
			do {
				buf++;
				run += 8;
				i++;
			} while ((i < size) && !*buf);
			break;
		case 255:
			if (run > max_range) {
				max_range = run;
				start_pos = (s64)i * 8 - run;
			}
			run = 0;
			do {
				buf++;
				i++;
			} while ((i < size) && (*buf == 255));
			break;
		default:
			for (j = 0; j < 8; j++) {
				int bit = *buf & (1 << j);

				if (bit) {
					if (run > max_range) {
						max_range = run;
						start_pos = (s64)i * 8 + (j - run);
					}
					run = 0;
				} else
					run++;
			}
			i++;
			buf++;
		}
	}

	if (run > max_range)
		start_pos = (s64)i * 8 - run;

	return start_pos;
}

/*
 * ntfs_cluster_alloc - allocate clusters on an ntfs volume
 * @vol:		mounted ntfs volume on which to allocate clusters
 * @start_vcn:		vcn of the first allocated cluster
 * @count:		number of clusters to allocate
 * @start_lcn:		starting lcn at which to allocate the clusters or -1 if none
 * @zone:		zone from which to allocate (MFT_ZONE or DATA_ZONE)
 * @is_extension:	if true, the caller is extending an attribute
 * @is_contig:		if true, require contiguous allocation
 * @is_dealloc:		if true, the allocation is for deallocation purposes
 *
 * Allocate @count clusters preferably starting at cluster @start_lcn or at the
 * current allocator position if @start_lcn is -1, on the mounted ntfs volume
 * @vol. @zone is either DATA_ZONE for allocation of normal clusters or
 * MFT_ZONE for allocation of clusters for the master file table, i.e. the
 * $MFT/$DATA attribute.
 *
 * @start_vcn specifies the vcn of the first allocated cluster.  This makes
 * merging the resulting runlist with the old runlist easier.
 *
 * If @is_extension is 'true', the caller is allocating clusters to extend an
 * attribute and if it is 'false', the caller is allocating clusters to fill a
 * hole in an attribute.  Practically the difference is that if @is_extension
 * is 'true' the returned runlist will be terminated with LCN_ENOENT and if
 * @is_extension is 'false' the runlist will be terminated with
 * LCN_RL_NOT_MAPPED.
 *
 * You need to check the return value with IS_ERR().  If this is false, the
 * function was successful and the return value is a runlist describing the
 * allocated cluster(s).  If IS_ERR() is true, the function failed and
 * PTR_ERR() gives you the error code.
 *
 * Notes on the allocation algorithm
 * =================================
 *
 * There are two data zones.  First is the area between the end of the mft zone
 * and the end of the volume, and second is the area between the start of the
 * volume and the start of the mft zone.  On unmodified/standard NTFS 1.x
 * volumes, the second data zone does not exist due to the mft zone being
 * expanded to cover the start of the volume in order to reserve space for the
 * mft bitmap attribute.
 *<