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