1/*
2 * Copyright 2001-2010, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 *		Janito V. Ferreira Filho
7 */
8
9
10#include "DataStream.h"
11
12#include "CachedBlock.h"
13#include "Volume.h"
14
15
16//#define TRACE_EXT2
17#ifdef TRACE_EXT2
18#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
19#else
20#	define TRACE(x...) ;
21#endif
22#define ERROR(x...)	dprintf("\33[34mext2:\33[0m " x)
23
24
25DataStream::DataStream(Volume* volume, ext2_data_stream* stream,
26	off_t size)
27	:
28	kBlockSize(volume->BlockSize()),
29	kIndirectsPerBlock(kBlockSize / sizeof(uint32)),
30	kIndirectsPerBlock2(kIndirectsPerBlock * kIndirectsPerBlock),
31	kIndirectsPerBlock3(kIndirectsPerBlock2 * kIndirectsPerBlock),
32	kMaxDirect(EXT2_DIRECT_BLOCKS),
33	kMaxIndirect(kMaxDirect + kIndirectsPerBlock),
34	kMaxDoubleIndirect(kMaxIndirect + kIndirectsPerBlock2),
35	fVolume(volume),
36	fStream(stream),
37	fFirstBlock(volume->FirstDataBlock()),
38	fAllocated(0),
39	fAllocatedPos(fFirstBlock),
40	fWaiting(0),
41	fFreeStart(0),
42	fFreeCount(0),
43	fRemovedBlocks(0),
44	fSize(size)
45{
46	fNumBlocks = size == 0 ? 0 : ((size - 1) >> fVolume->BlockShift()) + 1;
47}
48
49
50DataStream::~DataStream()
51{
52}
53
54
55status_t
56DataStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
57{
58	uint32 index = offset >> fVolume->BlockShift();
59
60	if (offset >= fSize) {
61		TRACE("FindBlock: offset larger than inode size\n");
62		return B_ENTRY_NOT_FOUND;
63	}
64
65	// TODO: we could return the size of the sparse range, as this might be more
66	// than just a block
67
68	if (index < EXT2_DIRECT_BLOCKS) {
69		// direct blocks
70		block = B_LENDIAN_TO_HOST_INT32(fStream->direct[index]);
71		ASSERT(block != 0);
72		if (_count) {
73			*_count = 1;
74			uint32 nextBlock = block;
75			while (++index < EXT2_DIRECT_BLOCKS
76				&& fStream->direct[index] == ++nextBlock)
77				(*_count)++;
78		}
79	} else if ((index -= EXT2_DIRECT_BLOCKS) < kIndirectsPerBlock) {
80		// indirect blocks
81		CachedBlock cached(fVolume);
82		uint32* indirectBlocks = (uint32*)cached.SetTo(B_LENDIAN_TO_HOST_INT32(
83			fStream->indirect));
84		if (indirectBlocks == NULL)
85			return B_IO_ERROR;
86
87		block = B_LENDIAN_TO_HOST_INT32(indirectBlocks[index]);
88		ASSERT(block != 0);
89		if (_count) {
90			*_count = 1;
91			uint32 nextBlock = block;
92			while (++index < kIndirectsPerBlock
93				&& indirectBlocks[index] == ++nextBlock)
94				(*_count)++;
95		}
96	} else if ((index -= kIndirectsPerBlock) < kIndirectsPerBlock2) {
97		// double indirect blocks
98		CachedBlock cached(fVolume);
99		uint32* indirectBlocks = (uint32*)cached.SetTo(B_LENDIAN_TO_HOST_INT32(
100			fStream->double_indirect));
101		if (indirectBlocks == NULL)
102			return B_IO_ERROR;
103
104		uint32 indirectIndex = B_LENDIAN_TO_HOST_INT32(indirectBlocks[index
105			/ kIndirectsPerBlock]);
106		if (indirectIndex == 0) {
107			// a sparse indirect block
108			block = 0;
109		} else {
110			indirectBlocks = (uint32*)cached.SetTo(indirectIndex);
111			if (indirectBlocks == NULL)
112				return B_IO_ERROR;
113
114			block = B_LENDIAN_TO_HOST_INT32(
115				indirectBlocks[index & (kIndirectsPerBlock - 1)]);
116			if (_count) {
117				*_count = 1;
118				uint32 nextBlock = block;
119				while (((++index & (kIndirectsPerBlock - 1)) != 0)
120					&& indirectBlocks[index & (kIndirectsPerBlock - 1)]
121						== ++nextBlock)
122					(*_count)++;
123			}
124		}
125		ASSERT(block != 0);
126	} else if ((index -= kIndirectsPerBlock2) < kIndirectsPerBlock3) {
127		// triple indirect blocks
128		CachedBlock cached(fVolume);
129		uint32* indirectBlocks = (uint32*)cached.SetTo(B_LENDIAN_TO_HOST_INT32(
130			fStream->triple_indirect));
131		if (indirectBlocks == NULL)
132			return B_IO_ERROR;
133
134		uint32 indirectIndex = B_LENDIAN_TO_HOST_INT32(indirectBlocks[index
135			/ kIndirectsPerBlock2]);
136		if (indirectIndex == 0) {
137			// a sparse indirect block
138			block = 0;
139		} else {
140			indirectBlocks = (uint32*)cached.SetTo(indirectIndex);
141			if (indirectBlocks == NULL)
142				return B_IO_ERROR;
143
144			indirectIndex = B_LENDIAN_TO_HOST_INT32(
145				indirectBlocks[(index / kIndirectsPerBlock) & (kIndirectsPerBlock - 1)]);
146			if (indirectIndex == 0) {
147				// a sparse indirect block
148				block = 0;
149			} else {
150				indirectBlocks = (uint32*)cached.SetTo(indirectIndex);
151				if (indirectBlocks == NULL)
152					return B_IO_ERROR;
153
154				block = B_LENDIAN_TO_HOST_INT32(
155					indirectBlocks[index & (kIndirectsPerBlock - 1)]);
156				if (_count) {
157					*_count = 1;
158					uint32 nextBlock = block;
159					while (((++index & (kIndirectsPerBlock - 1)) != 0)
160						&& indirectBlocks[index & (kIndirectsPerBlock - 1)]
161							== ++nextBlock)
162						(*_count)++;
163				}
164			}
165		}
166		ASSERT(block != 0);
167	} else {
168		// Outside of the possible data stream
169		ERROR("ext2: block outside datastream!\n");
170		return B_ERROR;
171	}
172
173	TRACE("FindBlock(offset %" B_PRIdOFF "): %" B_PRIu64" %" B_PRIu32 "\n", offset,
174		block, _count != NULL ? *_count : 1);
175	return B_OK;
176}
177
178
179status_t
180DataStream::Enlarge(Transaction& transaction, off_t& numBlocks)
181{
182	TRACE("DataStream::Enlarge(): current size: %" B_PRIdOFF ", target size: %"
183		B_PRIdOFF "\n", fNumBlocks, numBlocks);
184
185	off_t targetBlocks = numBlocks;
186	fWaiting = _BlocksNeeded(numBlocks);
187	numBlocks = fWaiting;
188
189	status_t status;
190
191	if (fNumBlocks <= kMaxDirect) {
192		status = _AddForDirectBlocks(transaction, targetBlocks);
193
194		if (status != B_OK) {
195			ERROR("DataStream::Enlarge(): _AddForDirectBlocks() failed\n");
196			return status;
197		}
198
199		TRACE("DataStream::Enlarge(): current size: %" B_PRIdOFF
200			", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
201
202		if (fNumBlocks == targetBlocks)
203			return B_OK;
204	}
205
206	TRACE("DataStream::Enlarge(): indirect current size: %" B_PRIdOFF
207		", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
208
209	if (fNumBlocks <= kMaxIndirect) {
210		status = _AddForIndirectBlock(transaction, targetBlocks);
211
212		if (status != B_OK) {
213			ERROR("DataStream::Enlarge(): _AddForIndirectBlock() failed\n");
214			return status;
215		}
216
217		TRACE("DataStream::Enlarge(): current size: %" B_PRIdOFF
218			", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
219
220		if (fNumBlocks == targetBlocks)
221			return B_OK;
222	}
223
224	TRACE("DataStream::Enlarge(): indirect2 current size: %" B_PRIdOFF
225		", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
226
227	if (fNumBlocks <= kMaxDoubleIndirect) {
228		status = _AddForDoubleIndirectBlock(transaction, targetBlocks);
229
230		if (status != B_OK) {
231			ERROR("DataStream::Enlarge(): _AddForDoubleIndirectBlock() failed\n");
232			return status;
233		}
234
235		TRACE("DataStream::Enlarge(): current size: %" B_PRIdOFF
236			", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
237
238		if (fNumBlocks == targetBlocks)
239			return B_OK;
240	}
241
242	TRACE("DataStream::Enlarge(): indirect3 current size: %" B_PRIdOFF
243		", target size: %" B_PRIdOFF "\n", fNumBlocks, targetBlocks);
244
245	TRACE("DataStream::Enlarge(): allocated: %" B_PRIu32 ", waiting: %"
246		B_PRIu32 "\n", fAllocated, fWaiting);
247
248	return _AddForTripleIndirectBlock(transaction, targetBlocks);
249}
250
251
252status_t
253DataStream::Shrink(Transaction& transaction, off_t& numBlocks)
254{
255	TRACE("DataStream::Shrink(): current size: %" B_PRIdOFF ", target size: %"
256		B_PRIdOFF "\n", fNumBlocks, numBlocks);
257
258	fFreeStart = 0;
259	fFreeCount = 0;
260	fRemovedBlocks = 0;
261
262	off_t oldNumBlocks = fNumBlocks;
263	off_t blocksToRemove = fNumBlocks - numBlocks;
264
265	status_t status;
266
267	if (numBlocks < kMaxDirect) {
268		status = _RemoveFromDirectBlocks(transaction, numBlocks);
269
270		if (status != B_OK) {
271			ERROR("DataStream::Shrink(): _RemoveFromDirectBlocks() failed\n");
272			return status;
273		}
274
275		if (fRemovedBlocks == blocksToRemove) {
276			fNumBlocks -= fRemovedBlocks;
277			numBlocks = _BlocksNeeded(oldNumBlocks);
278
279			return _PerformFree(transaction);
280		}
281	}
282
283	if (numBlocks < kMaxIndirect) {
284		status = _RemoveFromIndirectBlock(transaction, numBlocks);
285
286		if (status != B_OK) {
287			ERROR("DataStream::Shrink(): _RemoveFromIndirectBlock() failed\n");
288			return status;
289		}
290
291		if (fRemovedBlocks == blocksToRemove) {
292			fNumBlocks -= fRemovedBlocks;
293			numBlocks = _BlocksNeeded(oldNumBlocks);
294
295			return _PerformFree(transaction);
296		}
297	}
298
299	if (numBlocks < kMaxDoubleIndirect) {
300		status = _RemoveFromDoubleIndirectBlock(transaction, numBlocks);
301
302		if (status != B_OK) {
303			ERROR("DataStream::Shrink(): _RemoveFromDoubleIndirectBlock() failed\n");
304			return status;
305		}
306
307		if (fRemovedBlocks == blocksToRemove) {
308			fNumBlocks -= fRemovedBlocks;
309			numBlocks = _BlocksNeeded(oldNumBlocks);
310
311			return _PerformFree(transaction);
312		}
313	}
314
315	status = _RemoveFromTripleIndirectBlock(transaction, numBlocks);
316
317	if (status != B_OK) {
318		ERROR("DataStream::Shrink(): _RemoveFromTripleIndirectBlock() failed\n");
319		return status;
320	}
321
322	fNumBlocks -= fRemovedBlocks;
323	numBlocks = _BlocksNeeded(oldNumBlocks);
324
325	return _PerformFree(transaction);
326}
327
328
329uint32
330DataStream::_BlocksNeeded(off_t numBlocks)
331{
332	TRACE("DataStream::BlocksNeeded(): num blocks %" B_PRIdOFF "\n", numBlocks);
333	off_t blocksNeeded = 0;
334
335	if (numBlocks > fNumBlocks) {
336		blocksNeeded += numBlocks - fNumBlocks;
337
338		if (numBlocks > kMaxDirect) {
339			if (fNumBlocks <= kMaxDirect)
340				blocksNeeded += 1;
341
342			if (numBlocks > kMaxIndirect) {
343				if (fNumBlocks <= kMaxIndirect) {
344					blocksNeeded += 2 + (numBlocks - kMaxIndirect - 1)
345						/ kIndirectsPerBlock;
346				} else {
347					blocksNeeded += (numBlocks - kMaxIndirect - 1)
348						/ kIndirectsPerBlock - (fNumBlocks
349							- kMaxIndirect - 1) / kIndirectsPerBlock;
350				}
351
352				if (numBlocks > kMaxDoubleIndirect) {
353					if (fNumBlocks <= kMaxDoubleIndirect) {
354						blocksNeeded += 2 + (numBlocks - kMaxDoubleIndirect - 1)
355							/ kIndirectsPerBlock2;
356					} else {
357						blocksNeeded += (numBlocks - kMaxDoubleIndirect - 1)
358							/ kIndirectsPerBlock - (fNumBlocks
359								- kMaxDoubleIndirect - 1) / kIndirectsPerBlock;
360					}
361				}
362			}
363		}
364	}
365
366	TRACE("DataStream::BlocksNeeded(): %" B_PRIdOFF "\n", blocksNeeded);
367	return blocksNeeded;
368}
369
370
371status_t
372DataStream::_GetBlock(Transaction& transaction, uint32& blockNum)
373{
374	TRACE("DataStream::_GetBlock(): allocated: %" B_PRIu32 ", pos: %" B_PRIu64
375		", waiting: %" B_PRIu32 "\n", fAllocated, fAllocatedPos, fWaiting);
376
377	if (fAllocated == 0) {
378		uint32 blockGroup = (fAllocatedPos - fFirstBlock)
379			/ fVolume->BlocksPerGroup();
380
381		status_t status = fVolume->AllocateBlocks(transaction, 1, fWaiting,
382			blockGroup, fAllocatedPos, fAllocated);
383		if (status != B_OK) {
384			ERROR("DataStream::_GetBlock(): AllocateBlocks() failed()\n");
385			return status;
386		}
387		if (fAllocatedPos > UINT_MAX)
388			return B_FILE_TOO_LARGE;
389
390		fWaiting -= fAllocated;
391
392		TRACE("DataStream::_GetBlock(): newAllocated: %" B_PRIu32 ", newpos: %"
393			B_PRIu64 ", newwaiting: %" B_PRIu32 "\n", fAllocated,
394			fAllocatedPos, fWaiting);
395	}
396
397	fAllocated--;
398	blockNum = (uint32)fAllocatedPos++;
399
400	return B_OK;
401}
402
403
404status_t
405DataStream::_PrepareBlock(Transaction& transaction, uint32* pos,
406	uint32& blockNum, bool& clear)
407{
408	blockNum = B_LENDIAN_TO_HOST_INT32(*pos);
409	clear = false;
410
411	if (blockNum == 0) {
412		status_t status = _GetBlock(transaction, blockNum);
413		if (status != B_OK) {
414			ERROR("DataStream::_PrepareBlock() _GetBlock() failed blockNum %"
415				B_PRIu32 "\n", blockNum);
416			return status;
417		}
418
419		*pos = B_HOST_TO_LENDIAN_INT32(blockNum);
420		clear = true;
421	}
422
423	return B_OK;
424}
425
426
427status_t
428DataStream::_AddBlocks(Transaction& transaction, uint32* block, off_t _count)
429{
430	off_t count = _count;
431	TRACE("DataStream::_AddBlocks(): count: %" B_PRIdOFF "\n", count);
432
433	while (count > 0) {
434		uint32 blockNum;
435		status_t status = _GetBlock(transaction, blockNum);
436		if (status != B_OK)
437			return status;
438
439		*(block++) = B_HOST_TO_LENDIAN_INT32(blockNum);
440		--count;
441	}
442
443	fNumBlocks += _count;
444
445	return B_OK;
446}
447
448
449status_t
450DataStream::_AddBlocks(Transaction& transaction, uint32* block, off_t start,
451	off_t end, int recursion)
452{
453	TRACE("DataStream::_AddBlocks(): start: %" B_PRIdOFF ", end %" B_PRIdOFF
454		", recursion: %d\n", start, end, recursion);
455
456	bool clear;
457	uint32 blockNum;
458	status_t status = _PrepareBlock(transaction, block, blockNum, clear);
459	if (status != B_OK)
460		return status;
461
462	CachedBlock cached(fVolume);
463	uint32* childBlock = (uint32*)cached.SetToWritable(transaction, blockNum,
464		clear);
465	if (childBlock == NULL)
466		return B_IO_ERROR;
467
468	if (recursion == 0)
469		return _AddBlocks(transaction, &childBlock[start], end - start);
470
471	uint32 elementWidth;
472	if (recursion == 1)
473		elementWidth = kIndirectsPerBlock;
474	else if (recursion == 2)
475		elementWidth = kIndirectsPerBlock2;
476	else {
477		panic("Undefined recursion level\n");
478		elementWidth = 0;
479	}
480
481	uint32 elementPos = start / elementWidth;
482	uint32 endPos = end / elementWidth;
483
484	TRACE("DataStream::_AddBlocks(): element pos: %" B_PRIu32 ", end pos: %"
485		B_PRIu32 "\n", elementPos, endPos);
486
487	recursion--;
488
489	if (elementPos == endPos) {
490		return _AddBlocks(transaction, &childBlock[elementPos],
491			start % elementWidth, end % elementWidth, recursion);
492	}
493
494	if (start % elementWidth != 0) {
495		status = _AddBlocks(transaction, &childBlock[elementPos],
496			start % elementWidth, elementWidth, recursion);
497		if (status != B_OK) {
498			ERROR("DataStream::_AddBlocks() _AddBlocks() start failed\n");
499			return status;
500		}
501
502		elementPos++;
503	}
504
505	while (elementPos < endPos) {
506		status = _AddBlocks(transaction, &childBlock[elementPos], 0,
507			elementWidth, recursion);
508		if (status != B_OK) {
509			ERROR("DataStream::_AddBlocks() _AddBlocks() mid failed\n");
510			return status;
511		}
512
513		elementPos++;
514	}
515
516	if (end % elementWidth != 0) {
517		status = _AddBlocks(transaction, &childBlock[elementPos], 0,
518			end % elementWidth, recursion);
519		if (status != B_OK) {
520			ERROR("DataStream::_AddBlocks() _AddBlocks() end failed\n");
521			return status;
522		}
523	}
524
525	return B_OK;
526}
527
528
529status_t
530DataStream::_AddForDirectBlocks(Transaction& transaction, uint32 numBlocks)
531{
532	TRACE("DataStream::_AddForDirectBlocks(): current size: %" B_PRIdOFF
533		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
534	uint32* direct = &fStream->direct[fNumBlocks];
535	uint32 end = numBlocks > kMaxDirect ? kMaxDirect : numBlocks;
536
537	return _AddBlocks(transaction, direct, end - fNumBlocks);
538}
539
540
541status_t
542DataStream::_AddForIndirectBlock(Transaction& transaction, uint32 numBlocks)
543{
544	TRACE("DataStream::_AddForIndirectBlocks(): current size: %" B_PRIdOFF
545		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
546	uint32 *indirect = &fStream->indirect;
547	uint32 start = fNumBlocks - kMaxDirect;
548	uint32 end = numBlocks - kMaxDirect;
549
550	if (end > kIndirectsPerBlock)
551		end = kIndirectsPerBlock;
552
553	return _AddBlocks(transaction, indirect, start, end, 0);
554}
555
556
557status_t
558DataStream::_AddForDoubleIndirectBlock(Transaction& transaction,
559	uint32 numBlocks)
560{
561	TRACE("DataStream::_AddForDoubleIndirectBlock(): current size: %" B_PRIdOFF
562		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
563	uint32 *doubleIndirect = &fStream->double_indirect;
564	uint32 start = fNumBlocks - kMaxIndirect;
565	uint32 end = numBlocks - kMaxIndirect;
566
567	if (end > kIndirectsPerBlock2)
568		end = kIndirectsPerBlock2;
569
570	return _AddBlocks(transaction, doubleIndirect, start, end, 1);
571}
572
573
574status_t
575DataStream::_AddForTripleIndirectBlock(Transaction& transaction,
576	uint32 numBlocks)
577{
578	TRACE("DataStream::_AddForTripleIndirectBlock(): current size: %" B_PRIdOFF
579		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
580	uint32 *tripleIndirect = &fStream->triple_indirect;
581	uint32 start = fNumBlocks - kMaxDoubleIndirect;
582	uint32 end = numBlocks - kMaxDoubleIndirect;
583
584	return _AddBlocks(transaction, tripleIndirect, start, end, 2);
585}
586
587
588status_t
589DataStream::_PerformFree(Transaction& transaction)
590{
591	TRACE("DataStream::_PerformFree(): start: %" B_PRIu32 ", count: %" B_PRIu32
592		"\n", fFreeStart, fFreeCount);
593	status_t status;
594
595	if (fFreeCount == 0)
596		status = B_OK;
597	else
598		status = fVolume->FreeBlocks(transaction, fFreeStart, fFreeCount);
599
600	fFreeStart = 0;
601	fFreeCount = 0;
602
603	return status;
604}
605
606
607status_t
608DataStream::_MarkBlockForRemoval(Transaction& transaction, uint32* block)
609{
610
611	TRACE("DataStream::_MarkBlockForRemoval(*(%p) = %" B_PRIu32
612		"): free start: %" B_PRIu32 ", free count: %" B_PRIu32 "\n", block,
613		B_LENDIAN_TO_HOST_INT32(*block), fFreeStart, fFreeCount);
614	uint32 blockNum = B_LENDIAN_TO_HOST_INT32(*block);
615	*block = 0;
616
617	if (blockNum != fFreeStart + fFreeCount) {
618		if (fFreeCount != 0) {
619			status_t status = fVolume->FreeBlocks(transaction, fFreeStart,
620				fFreeCount);
621			if (status != B_OK)
622				return status;
623		}
624
625		fFreeStart = blockNum;
626		fFreeCount = 0;
627	}
628
629	fFreeCount++;
630
631	return B_OK;
632}
633
634
635status_t
636DataStream::_FreeBlocks(Transaction& transaction, uint32* block, uint32 _count)
637{
638	uint32 count = _count;
639	TRACE("DataStream::_FreeBlocks(%p, %" B_PRIu32 ")\n", block, count);
640
641	while (count > 0) {
642		status_t status = _MarkBlockForRemoval(transaction, block);
643		if (status != B_OK)
644			return status;
645
646		block++;
647		count--;
648	}
649
650	fRemovedBlocks += _count;
651
652	return B_OK;
653}
654
655
656status_t
657DataStream::_FreeBlocks(Transaction& transaction, uint32* block, off_t start,
658	off_t end, bool freeParent, int recursion)
659{
660	// TODO: Designed specifically for shrinking. Perhaps make it more general?
661	TRACE("DataStream::_FreeBlocks(%p, %" B_PRIdOFF ", %" B_PRIdOFF
662		", %c, %d)\n", block, start, end, freeParent ? 't' : 'f', recursion);
663
664	uint32 blockNum = B_LENDIAN_TO_HOST_INT32(*block);
665
666	if (freeParent) {
667		status_t status = _MarkBlockForRemoval(transaction, block);
668		if (status != B_OK)
669			return status;
670	}
671
672	CachedBlock cached(fVolume);
673	uint32* childBlock = (uint32*)cached.SetToWritable(transaction, blockNum);
674	if (childBlock == NULL)
675		return B_IO_ERROR;
676
677	if (recursion == 0)
678		return _FreeBlocks(transaction, &childBlock[start], end - start);
679
680	uint32 elementWidth;
681	if (recursion == 1)
682		elementWidth = kIndirectsPerBlock;
683	else if (recursion == 2)
684		elementWidth = kIndirectsPerBlock2;
685	else {
686		panic("Undefinied recursion level\n");
687		elementWidth = 0;
688	}
689
690	uint32 elementPos = start / elementWidth;
691	uint32 endPos = end / elementWidth;
692
693	recursion--;
694
695	if (elementPos == endPos) {
696		bool free = freeParent || start % elementWidth == 0;
697		return _FreeBlocks(transaction, &childBlock[elementPos],
698			start % elementWidth, end % elementWidth, free, recursion);
699	}
700
701	status_t status = B_OK;
702
703	if (start % elementWidth != 0) {
704		status = _FreeBlocks(transaction, &childBlock[elementPos],
705			start % elementWidth, elementWidth, false, recursion);
706		if (status != B_OK)
707			return status;
708
709		elementPos++;
710	}
711
712	while (elementPos < endPos) {
713		status = _FreeBlocks(transaction, &childBlock[elementPos], 0,
714			elementWidth, true, recursion);
715		if (status != B_OK)
716			return status;
717
718		elementPos++;
719	}
720
721	if (end % elementWidth != 0) {
722		status = _FreeBlocks(transaction, &childBlock[elementPos], 0,
723			end % elementWidth, true, recursion);
724	}
725
726	return status;
727}
728
729
730status_t
731DataStream::_RemoveFromDirectBlocks(Transaction& transaction, uint32 numBlocks)
732{
733	TRACE("DataStream::_RemoveFromDirectBlocks(): current size: %" B_PRIdOFF
734		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
735	uint32* direct = &fStream->direct[numBlocks];
736	off_t end = fNumBlocks > kMaxDirect ? kMaxDirect : fNumBlocks;
737
738	return _FreeBlocks(transaction, direct, end - numBlocks);
739}
740
741
742status_t
743DataStream::_RemoveFromIndirectBlock(Transaction& transaction, uint32 numBlocks)
744{
745	TRACE("DataStream::_RemoveFromIndirectBlock(): current size: %" B_PRIdOFF
746		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
747	uint32* indirect = &fStream->indirect;
748	off_t start = numBlocks <= kMaxDirect ? 0 : numBlocks - kMaxDirect;
749	off_t end = fNumBlocks - kMaxDirect;
750
751	if (end > kIndirectsPerBlock)
752		end = kIndirectsPerBlock;
753
754	bool freeAll = start == 0;
755
756	return _FreeBlocks(transaction, indirect, start, end, freeAll, 0);
757}
758
759
760status_t
761DataStream::_RemoveFromDoubleIndirectBlock(Transaction& transaction,
762	uint32 numBlocks)
763{
764	TRACE("DataStream::_RemoveFromDoubleIndirectBlock(): current size: %" B_PRIdOFF
765		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
766	uint32* doubleIndirect = &fStream->double_indirect;
767	off_t start = numBlocks <= kMaxIndirect ? 0 : numBlocks - kMaxIndirect;
768	off_t end = fNumBlocks - kMaxIndirect;
769
770	if (end > kIndirectsPerBlock2)
771		end = kIndirectsPerBlock2;
772
773	bool freeAll = start == 0;
774
775	return _FreeBlocks(transaction, doubleIndirect, start, end, freeAll, 1);
776}
777
778
779status_t
780DataStream::_RemoveFromTripleIndirectBlock(Transaction& transaction,
781	uint32 numBlocks)
782{
783	TRACE("DataStream::_RemoveFromTripleIndirectBlock(): current size: %" B_PRIdOFF
784		", target size: %" B_PRIu32 "\n", fNumBlocks, numBlocks);
785	uint32* tripleIndirect = &fStream->triple_indirect;
786	off_t start = numBlocks <= kMaxDoubleIndirect ? 0
787		: numBlocks - kMaxDoubleIndirect;
788	off_t end = fNumBlocks - kMaxDoubleIndirect;
789
790	bool freeAll = start == 0;
791
792	return _FreeBlocks(transaction, tripleIndirect, start, end, freeAll, 2);
793}
794