ntfs/libntfs/runlist.c

90  * @rl:		original runlist
91  * @old_size:	number of runlist elements in the original runlist @rl
104 static runlist_element *ntfs_rl_realloc(runlist_element *rl, int old_size,
110 		return rl;
111 	return realloc(rl, new_size);
123 runlist_element *ntfs_rl_extend(ntfs_attr *na, runlist_element *rl,
130 	if (na->rl && rl) {
131 		irl = (int)(rl - na->rl);
133 		while (na->rl[last].length)
135 		newrl = ntfs_rl_realloc(na->rl,last+1,last+more_entries+1);
138 			rl = (runlist_element*)NULL;
140 			na->rl = newrl;
141 			rl = &newrl[irl];
146 		rl = (runlist_element*)NULL;
148 	return (rl);
509 	int di, si;		/* Current index into @[ds]rl. */
512 	int dend, send;		/* Last index into @[ds]rl. */
513 	int dfinal, sfinal;	/* The last index into @[ds]rl with
748 	runlist_element *rl;
751 	rl = ntfs_runlists_merge_i(drl, srl);
753 	return rl;
789 	runlist_element *rl;	/* The output runlist. */
820 	rl = ntfs_malloc(rlsize);
821 	if (!rl)
825 		rl->vcn = (VCN)0;
826 		rl->lcn = (LCN)LCN_RL_NOT_MAPPED;
827 		rl->length = vcn;
839 			rl2 = realloc(rl, rlsize);
842 				free(rl);
846 			rl = rl2;
849 		rl[rlpos].vcn = vcn;
880 		rl[rlpos].length = deltaxcn;
889 			rl[rlpos].lcn = (LCN)LCN_HOLE;
922 			if ((lcn != (LCN)-1) && !rl[rlpos].length) {
928 			rl[rlpos].lcn = lcn;
931 		if (rl[rlpos].length)
974 			rl[rlpos].vcn = vcn;
975 			vcn += rl[rlpos].length = num_clusters - vcn;
976 			rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
989 		rl[rlpos].lcn = (LCN)LCN_ENOENT;
991 		rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
994 	rl[rlpos].vcn = vcn;
995 	rl[rlpos].length = (s64)0;
999 		ntfs_debug_runlist_dump(rl);
1002 		return rl;
1005 	if (rl[0].length)
1006 		old_rl = ntfs_runlists_merge(old_rl, rl);
1008 		free(rl);
1012 	free(rl);
1019 	free(rl);
1037  * @rl:		runlist to use for conversion
1041  * cluster number (lcn) of a device using the runlist @rl to map vcns to their
1054 LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
1061 	 * If rl is NULL, assume that we have found an unmapped runlist. The
1065 	if (!rl)
1069 	if (vcn < rl[0].vcn)
1072 	for (i = 0; rl[i].length; i++) {
1073 		if (vcn < rl[i+1].vcn) {
1074 			if (rl[i].lcn >= (LCN)0)
1075 				return rl[i].lcn + (vcn - rl[i].vcn);
1076 			return rl[i].lcn;
1083 	if (rl[i].lcn < (LCN)0)
1084 		return rl[i].lcn;
1092  * @rl:		runlist specifying where to read the data from
1093  * @pos:	byte position within runlist @rl at which to begin the read
1098  * @b gathering the data as specified by the runlist @rl. The read begins at
1099  * offset @pos into the runlist @rl.
1113 s64 ntfs_rl_pread(const ntfs_volume *vol, const runlist_element *rl,
1119 	if (!vol || !rl || pos < 0 || count < 0) {
1121 		ntfs_log_perror("Failed to read runlist [vol: %p rl: %p "
1122 				"pos: %lld count: %lld]", vol, rl,
1128 	/* Seek in @rl to the run containing @pos. */
1129 	for (ofs = 0; rl->length && (ofs + (rl->length <<
1130 			vol->cluster_size_bits) <= pos); rl++)
1131 		ofs += (rl->length << vol->cluster_size_bits);
1134 	for (total = 0LL; count; rl++, ofs = 0) {
1135 		if (!rl->length)
1137 		if (rl->lcn < (LCN)0) {
1138 			if (rl->lcn != (LCN)LCN_HOLE)
1141 			to_read = min(count, (rl->length <<
1151 		to_read = min(count, (rl->length << vol->cluster_size_bits) -
1154 		bytes_read = ntfs_pread(vol->dev, (rl->lcn <<
1182  * @rl:		runlist entry specifying where to write the data to
1183  * @ofs:	offset in file for runlist element indicated in @rl
1189  * scattering the data as specified by the runlist @rl. The write begins at
1190  * offset @pos into the runlist @rl. If a run is sparse then the related buffer
1202 s64 ntfs_rl_pwrite(const ntfs_volume *vol, const runlist_element *rl,
1208 	if (!vol || !rl || pos < 0 || count < 0) {
1210 		ntfs_log_perror("Failed to write runlist [vol: %p rl: %p "
1211 				"pos: %lld count: %lld]", vol, rl,
1217 	/* Seek in @rl to the run containing @pos. */
1218 	while (rl->length && (ofs + (rl->length <<
1220 		ofs += (rl->length << vol->cluster_size_bits);
1221 		rl++;
1225 	for (total = 0LL; count; rl++, ofs = 0) {
1226 		if (!rl->length)
1228 		if (rl->lcn < (LCN)0) {
1230 			if (rl->lcn != (LCN)LCN_HOLE)
1233 			to_write = min(count, (rl->length <<
1242 		to_write = min(count, (rl->length << vol->cluster_size_bits) -
1246 			written = ntfs_pwrite(vol->dev, (rl->lcn <<
1309  * @rl:		runlist for which to determine the size of the mapping pairs
1312  * Walk the runlist @rl and calculate the size in bytes of the mapping pairs
1313  * array corresponding to the runlist @rl, starting at vcn @start_vcn.  This
1317  * If @rl is NULL, just return 1 (for the single terminator byte).
1327 		const runlist_element *rl, const VCN start_vcn, int max_size)
1338 	if (!rl) {
1340 			ntfs_log_trace("rl NULL, start_vcn %lld (should be > 0)\n",
1349 	while (rl->length && start_vcn >= rl[1].vcn)
1350 		rl++;
1351 	if ((!rl->length && start_vcn > rl->vcn) || start_vcn < rl->vcn) {
1359 	if (start_vcn > rl->vcn) {
1362 		/* We know rl->length != 0 already. */
1363 		if (rl->length < 0 || rl->lcn < LCN_HOLE)
1365 		delta = start_vcn - rl->vcn;
1367 		rls += 1 + ntfs_get_nr_significant_bytes(rl->length - delta);
1375 		if (rl->lcn >= 0 || vol->major_ver < 3) {
1376 			prev_lcn = rl->lcn;
1377 			if (rl->lcn >= 0)
1383 		rl++;
1386 	for (; rl->length && (rls <= max_size); rl++) {
1387 		if (rl->length < 0 || rl->lcn < LCN_HOLE)
1390 		rls += 1 + ntfs_get_nr_significant_bytes(rl->length);
1398 		if (rl->lcn >= 0 || vol->major_ver < 3) {
1400 			rls += ntfs_get_nr_significant_bytes(rl->lcn -
1402 			prev_lcn = rl->lcn;
1408 	if (rl->lcn == LCN_RL_NOT_MAPPED)
1463  * @rl:		runlist for which to build the mapping pairs array
1467  * Create the mapping pairs array from the runlist @rl, starting at vcn
1472  * If @rl is NULL, just write a single terminator byte to @dst.
1490 		const int dst_len, const runlist_element *rl,
1500 	if (!rl) {
1504 			*stop_rl = rl;
1510 	while (rl->length && start_vcn >= rl[1].vcn)
1511 		rl++;
1512 	if ((!rl->length && start_vcn > rl->vcn) || start_vcn < rl->vcn)
1521 	if (start_vcn > rl->vcn) {
1524 		/* We know rl->length != 0 already. */
1525 		if (rl->length < 0 || rl->lcn < LCN_HOLE)
1527 		delta = start_vcn - rl->vcn;
1530 				rl->length - delta);
1542 		if (rl->lcn >= 0 || vol->major_ver < 3) {
1543 			prev_lcn = rl->lcn;
1544 			if (rl->lcn >= 0)
1561 		rl++;
1564 	for (; rl->length; rl++) {
1565 		if (rl->length < 0 || rl->lcn < LCN_HOLE)
1569 				rl->length);
1581 		if (rl->lcn >= 0 || vol->major_ver < 3) {
1584 					len_len, dst_max, rl->lcn - prev_lcn);
1587 			prev_lcn = rl->lcn;
1600 		*stop_rl = rl;
1609 		*stop_rl = rl;
1619 	if (rl->lcn == LCN_RL_NOT_MAPPED)
1643 	runlist *rl;
1656 	rl = *arl;
1658 	if (start_vcn < rl->vcn) {
1665 	while (rl->length) {
1666 		if (start_vcn < rl[1].vcn)
1668 		rl++;
1671 	if (!rl->length) {
1678 	rl->length = start_vcn - rl->vcn;
1685 	if (rl->length) {
1686 		++rl;
1688 		if (!rl->length)
1691 		rl->vcn = start_vcn;
1692 		rl->length = 0;
1694 	rl->lcn = (LCN)LCN_ENOENT;
1702 		size_t new_size = (rl - *arl + 1) * sizeof(runlist_element);
1703 		rl = realloc(*arl, new_size);
1704 		if (rl)
1705 			*arl = rl;
1713  * @rl:		runlist to check
1717 int ntfs_rl_sparse(runlist *rl)
1721 	if (!rl) {
1727 	for (rlc = rl; rlc->length; rlc++)
1742  * @rl:		runlist to calculate for
1746 s64 ntfs_rl_get_compressed_size(ntfs_volume *vol, runlist *rl)
1751 	if (!rl) {
1757 	for (rlc = rl; rlc->length; rlc++) {
1784  * @rl:
1790 static void test_rl_dump_runlist(const runlist_element *rl)
1797 	if (!rl) {
1803 		for (len = 0; rl[len].length; len++) ;
1806 	for (i = 0; ; i++, rl++) {
1807 		LCN lcn = rl->lcn;
1822 				rl->vcn, lcn_str[ind], rl->length);
1825 				rl->vcn, rl->lcn, rl->length);
1826 		if (!rl->length)
2014 		printf("rl pure [contig|noncontig] [single|multi]\n");
2022 		printf("rl pure [contig|noncontig] [single|multi]\n");
2185 		printf("rl [zero|frag|pure] {args}\n");