1/*
2 * Copyright 2001-2011, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 *		J��r��me Duval
7 */
8
9
10#include "ExtentStream.h"
11
12#include <string.h>
13
14#include "CachedBlock.h"
15#include "Inode.h"
16#include "Volume.h"
17
18
19#undef ASSERT
20//#define TRACE_EXT2
21#ifdef TRACE_EXT2
22#	define TRACE(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x)
23#	define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); }
24#else
25#	define TRACE(x...) ;
26#	define ASSERT(x) ;
27#endif
28#define ERROR(x...)	dprintf("\33[34mext2:\33[0m ExtentStream::" x)
29
30
31ExtentStream::ExtentStream(Volume* volume, Inode* inode,
32	ext2_extent_stream* stream, off_t size)
33	:
34	fVolume(volume),
35	fInode(inode),
36	fStream(stream),
37	fFirstBlock(volume->FirstDataBlock()),
38	fAllocatedPos(fFirstBlock),
39	fSize(size)
40{
41	fNumBlocks = size == 0 ? 0 : ((size - 1) >> fVolume->BlockShift()) + 1;
42}
43
44
45ExtentStream::~ExtentStream()
46{
47}
48
49
50status_t
51ExtentStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
52{
53	fileblock_t index = offset >> fVolume->BlockShift();
54	TRACE("FindBlock(%" B_PRIdOFF ", %" B_PRIu64 ")\n", offset, index);
55
56	if (offset >= fSize) {
57		TRACE("FindBlock: offset larger than inode size\n");
58		return B_ENTRY_NOT_FOUND;
59	}
60
61	ext2_extent_stream *stream = fStream;
62	if (!stream->extent_header.IsValid())
63		panic("ExtentStream::FindBlock() invalid header\n");
64
65	CachedBlock cached(fVolume);
66	while (stream->extent_header.Depth() != 0) {
67		TRACE("FindBlock() depth %d\n",
68			stream->extent_header.Depth());
69		int32 i = 1;
70		while (i < stream->extent_header.NumEntries()
71			&& stream->extent_index[i].LogicalBlock() <= index) {
72			i++;
73		}
74		TRACE("FindBlock() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
75			i - 1, stream->extent_index[i - 1].PhysicalBlock());
76		stream = (ext2_extent_stream *)cached.SetTo(
77			stream->extent_index[i - 1].PhysicalBlock());
78		if (!stream->extent_header.IsValid())
79			panic("ExtentStream::FindBlock() invalid header\n");
80		if (!fInode->VerifyExtentChecksum(stream)) {
81			panic("ExtentStream::FindBlock() invalid checksum\n");
82			return B_BAD_DATA;
83		}
84	}
85
86	// find the extend following the one that should contain the logical block
87	int32 extentIndex;
88	if (stream->extent_header.NumEntries() > 7) {
89		// binary search when enough entries
90		int32 low = 0;
91		int32 high = stream->extent_header.NumEntries() - 1;
92		while (low < high) {
93			int32 middle = (high + low + 1) / 2;
94			if (stream->extent_entries[middle].LogicalBlock() > index)
95				high = middle - 1;
96			else
97				low = middle;
98		}
99
100		extentIndex = low + 1;
101	} else {
102		extentIndex = stream->extent_header.NumEntries();
103		for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
104			if (stream->extent_entries[i].LogicalBlock() > index) {
105				extentIndex = i;
106				break;
107			}
108		}
109	}
110
111	fileblock_t logicalEndIndex
112		= (fSize + fVolume->BlockSize() - 1) >> fVolume->BlockShift();
113
114	if (extentIndex == 0) {
115		// sparse block at the beginning of the stream
116		block = 0;
117		if (_count != NULL) {
118			*_count = stream->extent_header.NumEntries() == 0
119				? logicalEndIndex - index
120				: stream->extent_entries[0].LogicalBlock() - index;
121		}
122		TRACE("FindBlock() sparse block index %" B_PRIu64 " at beginning of "
123			"stream\n", index);
124		return B_OK;
125	}
126
127	const ext2_extent_entry& extent = stream->extent_entries[extentIndex - 1];
128		// the extent supposedly containing the offset
129	fileblock_t diff = index - extent.LogicalBlock();
130	if (diff >= extent.Length()) {
131		// sparse block between extends or at the end of the stream
132		TRACE("FindBlock() sparse block index %" B_PRIu64 " at %" B_PRIu32
133			"\n", index, extent.LogicalBlock());
134		block = 0;
135		if (_count != NULL) {
136			*_count = stream->extent_header.NumEntries() == extentIndex
137				? logicalEndIndex - index
138				: stream->extent_entries[extentIndex].LogicalBlock() - index;
139		}
140		return B_OK;
141	}
142
143	block = extent.PhysicalBlock() + diff;
144	if (_count != NULL)
145		*_count = extent.Length() - diff;
146
147	TRACE("FindBlock(offset %" B_PRIdOFF "): %" B_PRIu64 " %" B_PRIu32
148		"\n", offset, block, _count != NULL ? *_count : 1);
149
150	return B_OK;
151}
152
153
154status_t
155ExtentStream::Enlarge(Transaction& transaction, off_t& numBlocks)
156{
157	TRACE("Enlarge(): current size: %" B_PRIdOFF ", target size: %" B_PRIdOFF
158		"\n", fNumBlocks, numBlocks);
159
160	off_t targetBlocks = numBlocks;
161	numBlocks = targetBlocks - fNumBlocks;
162	uint32 allocated = 0;
163
164	while (fNumBlocks < targetBlocks) {
165		// allocate new blocks
166		uint32 blockGroup = (fAllocatedPos - fFirstBlock)
167				/ fVolume->BlocksPerGroup();
168
169		if (allocated == 0) {
170			status_t status = fVolume->AllocateBlocks(transaction, 1,
171				targetBlocks - fNumBlocks, blockGroup, fAllocatedPos,
172				allocated);
173			if (status != B_OK) {
174				ERROR("Enlarge(): AllocateBlocks() failed()\n");
175				return status;
176			}
177		}
178
179		ASSERT(_CheckBlock(fStream, fAllocatedPos) == B_OK);
180
181		ext2_extent_stream *stream = fStream;
182		fsblock_t path[stream->extent_header.Depth()];
183
184		// search for the leaf
185		CachedBlock cached(fVolume);
186		int32 level = -1;
187		for (; stream->extent_header.Depth() != 0;) {
188			if (stream->extent_header.NumEntries() == 0)
189				panic("stream->extent_header.NumEntries() == 0\n");
190			int32 lastIndex = stream->extent_header.NumEntries() - 1;
191			TRACE("Enlarge() depth %d\n", stream->extent_header.Depth());
192			TRACE("Enlarge() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
193				lastIndex, stream->extent_index[lastIndex].PhysicalBlock());
194			path[++level] = stream->extent_index[lastIndex].PhysicalBlock();
195			stream = (ext2_extent_stream *)cached.SetTo(path[level]);
196			if (stream == NULL)
197				return B_IO_ERROR;
198		}
199
200		// check if the new extent is adjacent
201		if (stream->extent_header.NumEntries() > 0) {
202			ext2_extent_entry &last = stream->extent_entries[
203				stream->extent_header.NumEntries() - 1];
204			TRACE("Enlarge() last %" B_PRIu64 " allocatedPos %" B_PRIu64 "\n",
205				last.PhysicalBlock() + last.Length(), fAllocatedPos);
206			if (last.PhysicalBlock() + last.Length() == fAllocatedPos
207				&& (last.Length() + allocated) <= EXT2_EXTENT_MAX_LENGTH) {
208				if (stream != fStream) {
209					stream = (ext2_extent_stream *)cached.SetToWritable(
210						transaction, cached.BlockNumber());
211					if (stream == NULL)
212						return B_IO_ERROR;
213				}
214				stream->extent_entries[stream->extent_header.NumEntries() - 1]
215					.SetLength(last.Length() + allocated);
216				fInode->SetExtentChecksum(stream);
217				fNumBlocks += allocated;
218				allocated = 0;
219				TRACE("Enlarge() entry extended\n");
220				continue;
221			}
222		}
223
224		if (stream->extent_header.NumEntries()
225			>= stream->extent_header.MaxEntries()) {
226			TRACE("Enlarge() adding leaf and indexes at depth %d level %"
227				B_PRId32 "\n", stream->extent_header.Depth(), level);
228			// try to add a leaf and indexes
229			while (--level >= 0) {
230				stream = (ext2_extent_stream *)cached.SetTo(path[level]);
231				if (stream == NULL)
232					return B_IO_ERROR;
233				if (stream->extent_header.NumEntries()
234					< stream->extent_header.MaxEntries()) {
235					break;
236				}
237				TRACE("Enlarge() going up from level %" B_PRId32 "\n", level);
238			}
239
240			if (level < 0 && fStream->extent_header.NumEntries()
241					>= fStream->extent_header.MaxEntries()) {
242				TRACE("Enlarge() add a level, increment root depth\n");
243				fsblock_t newBlock = fStream->extent_index[0].PhysicalBlock();
244				uint32 _allocated;
245				status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
246					blockGroup, newBlock, _allocated);
247				if (status != B_OK) {
248					ERROR("Enlarge() AllocateBlocks() failed()\n");
249					return status;
250				}
251				ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
252				TRACE("Enlarge() move root to block %" B_PRIu64 "\n",
253					newBlock);
254				numBlocks++;
255				stream = (ext2_extent_stream *)cached.SetToWritable(
256					transaction, newBlock);
257				if (stream == NULL)
258					return B_IO_ERROR;
259				ASSERT(fStream->extent_header.IsValid());
260				memcpy(stream, fStream, sizeof(ext2_extent_stream));
261				fStream->extent_header.SetDepth(stream->extent_header.Depth()
262					+ 1);
263				TRACE("Enlarge() new root depth %d\n",
264					fStream->extent_header.Depth());
265				fStream->extent_header.SetNumEntries(1);
266				fStream->extent_index[0].SetLogicalBlock(0);
267				fStream->extent_index[0].SetPhysicalBlock(newBlock);
268				stream->extent_header.SetMaxEntries((fVolume->BlockSize()
269					- sizeof(ext2_extent_header)) / sizeof(ext2_extent_index));
270				fInode->SetExtentChecksum(stream);
271				ASSERT(stream->extent_header.IsValid());
272
273				ASSERT(Check());
274				continue;
275			}
276
277			if (level < 0)
278				stream = fStream;
279
280			uint16 depth = stream->extent_header.Depth();
281			while (depth > 1) {
282				TRACE("Enlarge() adding an index block at depth %d\n", depth);
283				fsblock_t newBlock = path[level];
284				uint32 _allocated;
285				status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
286					blockGroup, newBlock, _allocated);
287				if (status != B_OK) {
288					ERROR("Enlarge(): AllocateBlocks() failed()\n");
289					return status;
290				}
291				ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
292				numBlocks++;
293				int32 index = stream->extent_header.NumEntries();
294				stream->extent_index[index].SetLogicalBlock(fNumBlocks);
295				stream->extent_index[index].SetPhysicalBlock(newBlock);
296				stream->extent_header.SetNumEntries(index + 1);
297				fInode->SetExtentChecksum(stream);
298				path[level++] = newBlock;
299
300				depth = stream->extent_header.Depth() - 1;
301				TRACE("Enlarge() init index block %" B_PRIu64 " at depth %d\n",
302					newBlock, depth);
303				stream = (ext2_extent_stream *)cached.SetToWritable(
304					transaction, newBlock);
305				if (stream == NULL)
306					return B_IO_ERROR;
307				stream->extent_header.magic = EXT2_EXTENT_MAGIC;
308				stream->extent_header.SetNumEntries(0);
309				stream->extent_header.SetMaxEntries((fVolume->BlockSize()
310					- sizeof(ext2_extent_header)) / sizeof(ext2_extent_index));
311				stream->extent_header.SetDepth(depth);
312				stream->extent_header.SetGeneration(0);
313				fInode->SetExtentChecksum(stream);
314
315				ASSERT(Check());
316			}
317
318			TRACE("Enlarge() depth %d level %" B_PRId32 "\n",
319				stream->extent_header.Depth(), level);
320
321			if (stream->extent_header.Depth() == 1) {
322				TRACE("Enlarge() adding an entry block at depth %d level %"
323					B_PRId32 "\n", depth, level);
324				fsblock_t newBlock;
325				if (level >= 0)
326					newBlock = path[level];
327				else
328					newBlock = fStream->extent_index[0].PhysicalBlock();
329				uint32 _allocated;
330				status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
331					blockGroup, newBlock, _allocated);
332				if (status != B_OK) {
333					ERROR("Enlarge(): AllocateBlocks() failed()\n");
334					return status;
335				}
336
337				ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
338				numBlocks++;
339				int32 index = stream->extent_header.NumEntries();
340				stream->extent_index[index].SetLogicalBlock(fNumBlocks);
341				stream->extent_index[index].SetPhysicalBlock(newBlock);
342				stream->extent_header.SetNumEntries(index + 1);
343				fInode->SetExtentChecksum(stream);
344
345				TRACE("Enlarge() init entry block %" B_PRIu64
346					" at depth %d\n", newBlock, depth);
347				stream = (ext2_extent_stream *)cached.SetToWritable(
348					transaction, newBlock);
349				if (stream == NULL)
350					return B_IO_ERROR;
351				stream->extent_header.magic = EXT2_EXTENT_MAGIC;
352				stream->extent_header.SetNumEntries(0);
353				stream->extent_header.SetMaxEntries((fVolume->BlockSize()
354					- sizeof(ext2_extent_header)) / sizeof(ext2_extent_entry));
355				stream->extent_header.SetDepth(0);
356				stream->extent_header.SetGeneration(0);
357				fInode->SetExtentChecksum(stream);
358				ASSERT(Check());
359			}
360		}
361
362		// add a new entry
363		TRACE("Enlarge() add entry %" B_PRIu64 "\n", fAllocatedPos);
364		if (stream != fStream) {
365			stream = (ext2_extent_stream *)cached.SetToWritable(
366				transaction, cached.BlockNumber());
367			if (stream == NULL)
368				return B_IO_ERROR;
369		}
370		int32 index = stream->extent_header.NumEntries();
371		stream->extent_entries[index].SetLogicalBlock(fNumBlocks);
372		stream->extent_entries[index].SetLength(allocated);
373		stream->extent_entries[index].SetPhysicalBlock(fAllocatedPos);
374		stream->extent_header.SetNumEntries(index + 1);
375		fInode->SetExtentChecksum(stream);
376		TRACE("Enlarge() entry added at index %" B_PRId32 "\n", index);
377		ASSERT(stream->extent_header.IsValid());
378
379		fNumBlocks += allocated;
380		allocated = 0;
381	}
382
383	return B_OK;
384}
385
386
387status_t
388ExtentStream::Shrink(Transaction& transaction, off_t& numBlocks)
389{
390	TRACE("DataStream::Shrink(): current size: %" B_PRIdOFF ", target size: %"
391		B_PRIdOFF "\n", fNumBlocks, numBlocks);
392
393	off_t targetBlocks = numBlocks;
394	numBlocks = fNumBlocks - targetBlocks;
395
396	while (targetBlocks < fNumBlocks) {
397		ext2_extent_stream *stream = fStream;
398		fsblock_t path[stream->extent_header.Depth()];
399
400		// search for the leaf
401		CachedBlock cached(fVolume);
402		int32 level = -1;
403		for (; stream->extent_header.Depth() != 0;) {
404			if (stream->extent_header.NumEntries() == 0)
405				panic("stream->extent_header.NumEntries() == 0\n");
406			int32 lastIndex = stream->extent_header.NumEntries() - 1;
407			TRACE("Shrink() depth %d\n", stream->extent_header.Depth());
408			TRACE("Shrink() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
409				lastIndex, stream->extent_index[lastIndex].PhysicalBlock());
410			path[++level] = stream->extent_index[lastIndex].PhysicalBlock();
411			stream = (ext2_extent_stream *)cached.SetToWritable(transaction,
412				path[level]);
413			if (stream == NULL)
414				return B_IO_ERROR;
415			if (!stream->extent_header.IsValid())
416				panic("Shrink() invalid header\n");
417		}
418
419		int32 index = stream->extent_header.NumEntries() - 1;
420		status_t status = B_OK;
421		while (index >= 0 && targetBlocks < fNumBlocks) {
422			ext2_extent_entry &last = stream->extent_entries[index];
423			if (last.LogicalBlock() + last.Length() < targetBlocks) {
424				status = B_BAD_DATA;
425				break;
426			}
427			uint16 length = min_c(last.Length(), fNumBlocks - targetBlocks);
428			fsblock_t block = last.PhysicalBlock() + last.Length() - length;
429			TRACE("Shrink() free block %" B_PRIu64 " length %d\n", block,
430				length);
431			status = fVolume->FreeBlocks(transaction, block, length);
432			if (status != B_OK)
433				break;
434			fNumBlocks -= length;
435			stream->extent_entries[index].SetLength(last.Length() - length);
436			TRACE("Shrink() new length for %" B_PRId32 ": %d\n", index, last.Length());
437			if (last.Length() != 0)
438				break;
439			index--;
440			TRACE("Shrink() next index: %" B_PRId32 "\n", index);
441		}
442		TRACE("Shrink() new entry count: %" B_PRId32 "\n", index + 1);
443		stream->extent_header.SetNumEntries(index + 1);
444		fInode->SetExtentChecksum(stream);
445		ASSERT(Check());
446
447		if (status != B_OK)
448			return status;
449
450		while (stream != fStream && stream->extent_header.NumEntries() == 0) {
451			TRACE("Shrink() empty leaf at depth %d\n",
452				stream->extent_header.Depth());
453			level--;
454			if (level >= 0) {
455				stream = (ext2_extent_stream *)cached.SetToWritable(
456					transaction, path[level]);
457				if (stream == NULL)
458					return B_IO_ERROR;
459			} else
460				stream = fStream;
461			if (!stream->extent_header.IsValid())
462				panic("Shrink() invalid header\n");
463			uint16 index = stream->extent_header.NumEntries() - 1;
464			ext2_extent_index &last = stream->extent_index[index];
465			if (last.PhysicalBlock() != path[level + 1])
466				panic("Shrink() last.PhysicalBlock() != path[level + 1]\n");
467			status = fVolume->FreeBlocks(transaction, last.PhysicalBlock(), 1);
468			if (status != B_OK)
469				return status;
470			numBlocks++;
471			stream->extent_header.SetNumEntries(index);
472			fInode->SetExtentChecksum(stream);
473			TRACE("Shrink() new entry count: %d\n", index);
474		}
475		if (stream == fStream && stream->extent_header.NumEntries() == 0)
476			stream->extent_header.SetDepth(0);
477
478		ASSERT(Check());
479	}
480
481	return B_OK;
482}
483
484
485void
486ExtentStream::Init()
487{
488	fStream->extent_header.magic = EXT2_EXTENT_MAGIC;
489	fStream->extent_header.SetNumEntries(0);
490	fStream->extent_header.SetMaxEntries(4);
491	fStream->extent_header.SetDepth(0);
492	fStream->extent_header.SetGeneration(0);
493	fInode->SetExtentChecksum(fStream);
494}
495
496
497status_t
498ExtentStream::_Check(ext2_extent_stream *stream, fileblock_t &block)
499{
500	if (!stream->extent_header.IsValid()) {
501		panic("_Check() invalid header\n");
502		return B_BAD_VALUE;
503	}
504	if (stream->extent_header.Depth() == 0) {
505		for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
506			ext2_extent_entry &entry = stream->extent_entries[i];
507			if (entry.LogicalBlock() < block) {
508				panic("_Check() entry %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32
509					"\n", i, block, entry.LogicalBlock());
510				return B_BAD_VALUE;
511			}
512			block = entry.LogicalBlock() + entry.Length();
513		}
514		return B_OK;
515	}
516
517	CachedBlock cached(fVolume);
518	for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
519		ext2_extent_index &index = stream->extent_index[i];
520		if (index.LogicalBlock() < block) {
521			panic("_Check() index %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32
522				"\n", i, block, index.LogicalBlock());
523			return B_BAD_VALUE;
524		}
525		ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
526			index.PhysicalBlock());
527		if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1)
528			|| _Check(child, block) != B_OK)
529			return B_BAD_VALUE;
530	}
531	return B_OK;
532}
533
534
535bool
536ExtentStream::Check()
537{
538	fileblock_t block = 0;
539	return _Check(fStream, block) == B_OK;
540}
541
542
543status_t
544ExtentStream::_CheckBlock(ext2_extent_stream *stream, fsblock_t block)
545{
546	if (stream->extent_header.Depth() == 0) {
547		for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
548			ext2_extent_entry &entry = stream->extent_entries[i];
549			if (entry.PhysicalBlock() <= block
550				&& (entry.PhysicalBlock() + entry.Length()) > block) {
551				panic("_CheckBlock() entry %" B_PRId32 " %" B_PRIu64 " %"
552					B_PRIu64 " %d\n", i, block, entry.PhysicalBlock(),
553					entry.Length());
554				return B_BAD_VALUE;
555			}
556		}
557		return B_OK;
558	}
559
560	CachedBlock cached(fVolume);
561	for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
562		ext2_extent_index &index = stream->extent_index[i];
563		if (index.PhysicalBlock() == block) {
564			panic("_CheckBlock() index %" B_PRId32 " %" B_PRIu64 "\n", i, block);
565			return B_BAD_VALUE;
566		}
567		ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
568			index.PhysicalBlock());
569		if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1)
570			|| _CheckBlock(child, block) != B_OK)
571			return B_BAD_VALUE;
572	}
573	return B_OK;
574}
575
576