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 *		Janito V. Ferreira Filho
7 *		Jérôme Duval
8 */
9
10
11#include "BlockAllocator.h"
12
13#include <util/AutoLock.h>
14
15#include "BitmapBlock.h"
16#include "Inode.h"
17
18
19#undef ASSERT
20//#define TRACE_EXT2
21#ifdef TRACE_EXT2
22#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " 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 " x)
29
30
31class AllocationBlockGroup : public TransactionListener {
32public:
33						AllocationBlockGroup();
34						~AllocationBlockGroup();
35
36			status_t	Initialize(Volume* volume, uint32 blockGroup,
37							uint32 numBits);
38
39			bool		IsFull() const;
40
41			status_t	Allocate(Transaction& transaction, fsblock_t start,
42							uint32 length);
43			status_t	Free(Transaction& transaction, uint32 start,
44							uint32 length);
45			status_t	FreeAll(Transaction& transaction);
46			status_t	Check(uint32 start, uint32 length);
47
48			uint32		NumBits() const;
49			uint32		FreeBits() const;
50			fsblock_t	Start() const;
51
52			fsblock_t	LargestStart() const;
53			uint32		LargestLength() const;
54
55			// TransactionListener implementation
56			void		TransactionDone(bool success);
57			void		RemovedFromTransaction();
58
59private:
60			status_t	_ScanFreeRanges();
61			void		_AddFreeRange(uint32 start, uint32 length);
62			void		_LockInTransaction(Transaction& transaction);
63			status_t	_InitGroup(Transaction& transaction);
64			bool		_IsSparse();
65			uint32		_FirstFreeBlock();
66
67			Volume*		fVolume;
68			uint32		fBlockGroup;
69			ext2_block_group* fGroupDescriptor;
70
71			mutex		fLock;
72			mutex		fTransactionLock;
73			int32		fCurrentTransaction;
74
75			fsblock_t	fStart;
76			uint32		fNumBits;
77			fsblock_t	fBitmapBlock;
78
79			uint32		fFreeBits;
80			uint32		fFirstFree;
81			uint32		fLargestStart;
82			uint32		fLargestLength;
83
84			uint32		fPreviousFreeBits;
85			uint32		fPreviousFirstFree;
86			uint32		fPreviousLargestStart;
87			uint32		fPreviousLargestLength;
88};
89
90
91AllocationBlockGroup::AllocationBlockGroup()
92	:
93	fVolume(NULL),
94	fBlockGroup(0),
95	fGroupDescriptor(NULL),
96	fStart(0),
97	fNumBits(0),
98	fBitmapBlock(0),
99	fFreeBits(0),
100	fFirstFree(0),
101	fLargestStart(0),
102	fLargestLength(0),
103	fPreviousFreeBits(0),
104	fPreviousFirstFree(0),
105	fPreviousLargestStart(0),
106	fPreviousLargestLength(0)
107{
108	mutex_init(&fLock, "ext2 allocation block group");
109	mutex_init(&fTransactionLock, "ext2 allocation block group transaction");
110}
111
112
113AllocationBlockGroup::~AllocationBlockGroup()
114{
115	mutex_destroy(&fLock);
116	mutex_destroy(&fTransactionLock);
117}
118
119
120status_t
121AllocationBlockGroup::Initialize(Volume* volume, uint32 blockGroup,
122	uint32 numBits)
123{
124	fVolume = volume;
125	fBlockGroup = blockGroup;
126	fNumBits = numBits;
127	fStart = blockGroup * numBits + fVolume->FirstDataBlock();
128
129	status_t status = fVolume->GetBlockGroup(blockGroup, &fGroupDescriptor);
130	if (status != B_OK)
131		return status;
132
133	fBitmapBlock = fGroupDescriptor->BlockBitmap(fVolume->Has64bitFeature());
134
135	if (fGroupDescriptor->Flags() & EXT2_BLOCK_GROUP_BLOCK_UNINIT) {
136		fFreeBits = fGroupDescriptor->FreeBlocks(fVolume->Has64bitFeature());
137		fLargestLength = fFreeBits;
138		fLargestStart = _FirstFreeBlock();
139		TRACE("Group %ld is uninit\n", fBlockGroup);
140		return B_OK;
141	}
142
143	status = _ScanFreeRanges();
144	if (status != B_OK)
145		return status;
146
147	if (fGroupDescriptor->FreeBlocks(fVolume->Has64bitFeature())
148		!= fFreeBits) {
149		ERROR("AllocationBlockGroup(%lu,%lld)::Initialize(): Mismatch between "
150			"counted free blocks (%lu/%lu) and what is set on the group "
151			"descriptor (%lu)\n", fBlockGroup, fBitmapBlock, fFreeBits,
152			fNumBits, fGroupDescriptor->FreeBlocks(
153				fVolume->Has64bitFeature()));
154		return B_BAD_DATA;
155	}
156
157	fPreviousFreeBits = fFreeBits;
158	fPreviousFirstFree = fFirstFree;
159	fPreviousLargestStart = fLargestStart;
160	fPreviousLargestLength = fLargestLength;
161
162	return status;
163}
164
165
166status_t
167AllocationBlockGroup::_ScanFreeRanges()
168{
169	TRACE("AllocationBlockGroup::_ScanFreeRanges() for group %ld\n",
170		fBlockGroup);
171	BitmapBlock block(fVolume, fNumBits);
172
173	if (!block.SetTo(fBitmapBlock))
174		return B_ERROR;
175
176	fFreeBits = 0;
177	uint32 start = 0;
178	uint32 end = 0;
179
180	while (end < fNumBits) {
181		block.FindNextUnmarked(start);
182		ASSERT(block.CheckMarked(end, start - end));
183		end = start;
184
185		if (start != block.NumBits()) {
186			block.FindNextMarked(end);
187			_AddFreeRange(start, end - start);
188			ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
189			start = end;
190		}
191	}
192
193	return B_OK;
194}
195
196
197bool
198AllocationBlockGroup::IsFull() const
199{
200	return fFreeBits == 0;
201}
202
203
204status_t
205AllocationBlockGroup::Allocate(Transaction& transaction, fsblock_t _start,
206	uint32 length)
207{
208	uint32 start = _start - fStart;
209	TRACE("AllocationBlockGroup::Allocate(%ld,%ld)\n", start, length);
210	if (length == 0)
211		return B_OK;
212
213	uint32 end = start + length;
214	if (end > fNumBits)
215		return B_BAD_VALUE;
216
217	_LockInTransaction(transaction);
218	_InitGroup(transaction);
219
220	BitmapBlock block(fVolume, fNumBits);
221
222	if (!block.SetToWritable(transaction, fBitmapBlock))
223		return B_ERROR;
224
225	TRACE("AllocationBlockGroup::Allocate(): Largest range in %lu-%lu\n",
226		fLargestStart, fLargestStart + fLargestLength);
227	ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
228
229	if (!block.Mark(start, length)) {
230		ERROR("Failed to allocate blocks from %lu to %lu. Some were "
231			"already allocated.\n", start, start + length);
232		return B_ERROR;
233	}
234
235	fFreeBits -= length;
236	fGroupDescriptor->SetFreeBlocks(fFreeBits, fVolume->Has64bitFeature());
237	fVolume->WriteBlockGroup(transaction, fBlockGroup);
238
239	if (start == fLargestStart) {
240		if (fFirstFree == fLargestStart)
241			fFirstFree += length;
242
243		fLargestStart += length;
244		fLargestLength -= length;
245	} else if (start + length == fLargestStart + fLargestLength) {
246		fLargestLength -= length;
247	} else if (start < fLargestStart + fLargestLength
248			&& start > fLargestStart) {
249		uint32 firstLength = start - fLargestStart;
250		uint32 secondLength = fLargestStart + fLargestLength
251			- (start + length);
252
253		if (firstLength >= secondLength) {
254			fLargestLength = firstLength;
255		} else {
256			fLargestLength = secondLength;
257			fLargestStart = start + length;
258		}
259	} else {
260		// No need to revalidate the largest free range
261		return B_OK;
262	}
263
264	TRACE("AllocationBlockGroup::Allocate(): Largest range in %lu-%lu\n",
265		fLargestStart, fLargestStart + fLargestLength);
266	ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
267
268	if (fLargestLength < fNumBits / 2)
269		block.FindLargestUnmarkedRange(fLargestStart, fLargestLength);
270	ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
271
272	return B_OK;
273}
274
275
276status_t
277AllocationBlockGroup::Free(Transaction& transaction, uint32 start,
278	uint32 length)
279{
280	TRACE("AllocationBlockGroup::Free(): start: %lu, length %lu\n", start,
281		length);
282
283	if (length == 0)
284		return B_OK;
285
286	uint32 end = start + length;
287	if (end > fNumBits)
288		return B_BAD_VALUE;
289
290	_LockInTransaction(transaction);
291	if (fGroupDescriptor->Flags() & EXT2_BLOCK_GROUP_BLOCK_UNINIT)
292		panic("AllocationBlockGroup::Free() can't free blocks if uninit\n");
293
294	BitmapBlock block(fVolume, fNumBits);
295
296	if (!block.SetToWritable(transaction, fBitmapBlock))
297		return B_ERROR;
298
299	TRACE("AllocationBlockGroup::Free(): Largest range in %lu-%lu\n",
300		fLargestStart, fLargestStart + fLargestLength);
301	ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
302
303	if (!block.Unmark(start, length)) {
304		ERROR("Failed to free blocks from %lu to %lu. Some were "
305			"already freed.\n", start, start + length);
306		return B_ERROR;
307	}
308
309	TRACE("AllocationGroup::Free(): Unmarked bits in bitmap\n");
310
311	if (fFirstFree > start)
312		fFirstFree = start;
313
314	if (start + length == fLargestStart) {
315		fLargestStart = start;
316		fLargestLength += length;
317	} else if (start == fLargestStart + fLargestLength) {
318		fLargestLength += length;
319	} else if (fLargestLength <= fNumBits / 2) {
320		// May have merged with some free blocks, becoming the largest
321		uint32 newEnd = start + length;
322		block.FindNextMarked(newEnd);
323
324		uint32 newStart = start;
325		block.FindPreviousMarked(newStart);
326		newStart++;
327
328		if (newEnd - newStart > fLargestLength) {
329			fLargestLength = newEnd - newStart;
330			fLargestStart = newStart;
331		}
332	}
333
334	TRACE("AllocationBlockGroup::Free(): Largest range in %lu-%lu\n",
335		fLargestStart, fLargestStart + fLargestLength);
336	ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength));
337
338	fFreeBits += length;
339	fGroupDescriptor->SetFreeBlocks(fFreeBits, fVolume->Has64bitFeature());
340	fVolume->WriteBlockGroup(transaction, fBlockGroup);
341
342	return B_OK;
343}
344
345
346status_t
347AllocationBlockGroup::FreeAll(Transaction& transaction)
348{
349	return Free(transaction, 0, fNumBits);
350}
351
352
353uint32
354AllocationBlockGroup::NumBits() const
355{
356	return fNumBits;
357}
358
359
360uint32
361AllocationBlockGroup::FreeBits() const
362{
363	return fFreeBits;
364}
365
366
367fsblock_t
368AllocationBlockGroup::Start() const
369{
370	return fStart;
371}
372
373
374fsblock_t
375AllocationBlockGroup::LargestStart() const
376{
377	return fStart + fLargestStart;
378}
379
380
381uint32
382AllocationBlockGroup::LargestLength() const
383{
384	return fLargestLength;
385}
386
387
388void
389AllocationBlockGroup::_AddFreeRange(uint32 start, uint32 length)
390{
391	if (IsFull()) {
392		fFirstFree = start;
393		fLargestStart = start;
394		fLargestLength = length;
395	} else if (length > fLargestLength) {
396		fLargestStart = start;
397		fLargestLength = length;
398	}
399
400	fFreeBits += length;
401}
402
403
404void
405AllocationBlockGroup::_LockInTransaction(Transaction& transaction)
406{
407	mutex_lock(&fLock);
408
409	if (transaction.ID() != fCurrentTransaction) {
410		mutex_unlock(&fLock);
411
412		mutex_lock(&fTransactionLock);
413		mutex_lock(&fLock);
414
415		fCurrentTransaction = transaction.ID();
416		transaction.AddListener(this);
417	}
418
419	mutex_unlock(&fLock);
420}
421
422
423status_t
424AllocationBlockGroup::_InitGroup(Transaction& transaction)
425{
426	TRACE("AllocationBlockGroup::_InitGroup()\n");
427	uint16 flags = fGroupDescriptor->Flags();
428	if ((flags & EXT2_BLOCK_GROUP_BLOCK_UNINIT) == 0)
429		return B_OK;
430
431	TRACE("AllocationBlockGroup::_InitGroup() initing\n");
432
433	BitmapBlock blockBitmap(fVolume, fNumBits);
434	if (!blockBitmap.SetToWritable(transaction, fBitmapBlock))
435		return B_ERROR;
436	blockBitmap.Mark(0, _FirstFreeBlock(), true);
437	blockBitmap.Unmark(0, fNumBits, true);
438
439	fGroupDescriptor->SetFlags(flags & ~EXT2_BLOCK_GROUP_BLOCK_UNINIT);
440	fVolume->WriteBlockGroup(transaction, fBlockGroup);
441
442	status_t status = _ScanFreeRanges();
443	if (status != B_OK)
444		return status;
445
446	if (fGroupDescriptor->FreeBlocks(fVolume->Has64bitFeature())
447		!= fFreeBits) {
448		ERROR("AllocationBlockGroup(%lu,%lld)::_InitGroup(): Mismatch between "
449			"counted free blocks (%lu/%lu) and what is set on the group "
450			"descriptor (%lu)\n", fBlockGroup, fBitmapBlock, fFreeBits,
451			fNumBits, fGroupDescriptor->FreeBlocks(
452				fVolume->Has64bitFeature()));
453		return B_BAD_DATA;
454	}
455
456	TRACE("AllocationBlockGroup::_InitGroup() init OK\n");
457
458	return B_OK;
459}
460
461
462bool
463AllocationBlockGroup::_IsSparse()
464{
465	if (fBlockGroup <= 1)
466		return true;
467	if (fBlockGroup & 0x1)
468		return false;
469
470	uint32 i = fBlockGroup;
471	while (i % 7 == 0)
472		i /= 7;
473	if (i == 1)
474		return true;
475
476	i = fBlockGroup;
477	while (i % 5 == 0)
478		i /= 5;
479	if (i == 1)
480		return true;
481
482	i = fBlockGroup;
483	while (i % 3 == 0)
484		i /= 3;
485	if (i == 1)
486		return true;
487
488	return false;
489}
490
491
492uint32
493AllocationBlockGroup::_FirstFreeBlock()
494{
495	uint32 first = 1;
496	if (_IsSparse())
497		first = 0;
498	else if (!fVolume->HasMetaGroupFeature()) {
499		first += fVolume->SuperBlock().ReservedGDTBlocks();
500		first += fVolume->NumGroups();
501	}
502	return first;
503}
504
505
506void
507AllocationBlockGroup::TransactionDone(bool success)
508{
509	if (success) {
510		TRACE("AllocationBlockGroup::TransactionDone(): The transaction "
511			"succeeded, discarding previous state\n");
512		fPreviousFreeBits = fFreeBits;
513		fPreviousFirstFree = fFirstFree;
514		fPreviousLargestStart = fLargestStart;
515		fPreviousLargestLength = fLargestLength;
516	} else {
517		TRACE("AllocationBlockGroup::TransactionDone(): The transaction "
518			"failed, restoring to previous state\n");
519		fFreeBits = fPreviousFreeBits;
520		fFirstFree = fPreviousFirstFree;
521		fLargestStart = fPreviousLargestStart;
522		fLargestLength = fPreviousLargestLength;
523	}
524}
525
526
527void
528AllocationBlockGroup::RemovedFromTransaction()
529{
530	mutex_unlock(&fTransactionLock);
531	fCurrentTransaction = -1;
532}
533
534
535BlockAllocator::BlockAllocator(Volume* volume)
536	:
537	fVolume(volume),
538	fGroups(NULL),
539	fBlocksPerGroup(0),
540	fNumBlocks(0),
541	fNumGroups(0)
542{
543	mutex_init(&fLock, "ext2 block allocator");
544}
545
546
547BlockAllocator::~BlockAllocator()
548{
549	mutex_destroy(&fLock);
550
551	if (fGroups != NULL)
552		delete [] fGroups;
553}
554
555
556status_t
557BlockAllocator::Initialize()
558{
559	fBlocksPerGroup = fVolume->BlocksPerGroup();
560	fNumGroups = fVolume->NumGroups();
561	fFirstBlock = fVolume->FirstDataBlock();
562	fNumBlocks = fVolume->NumBlocks();
563
564	TRACE("BlockAllocator::Initialize(): blocks per group: %lu, block groups: "
565		"%lu, first block: %llu, num blocks: %llu\n", fBlocksPerGroup,
566		fNumGroups, fFirstBlock, fNumBlocks);
567
568	fGroups = new(std::nothrow) AllocationBlockGroup[fNumGroups];
569	if (fGroups == NULL)
570		return B_NO_MEMORY;
571
572	TRACE("BlockAllocator::Initialize(): allocated allocation block groups\n");
573
574	mutex_lock(&fLock);
575		// Released by _Initialize
576
577	thread_id id = -1; // spawn_kernel_thread(
578		// (thread_func)BlockAllocator::_Initialize, "ext2 block allocator",
579		// B_LOW_PRIORITY, this);
580	if (id < B_OK)
581		return _Initialize(this);
582
583	// mutex_transfer_lock(&fLock, id);
584
585	// return resume_thread(id);
586	panic("Failed to fall back to synchronous block allocator"
587		"initialization.\n");
588	return B_ERROR;
589}
590
591
592status_t
593BlockAllocator::AllocateBlocks(Transaction& transaction, uint32 minimum,
594	uint32 maximum, uint32& blockGroup, fsblock_t& start, uint32& length)
595{
596	TRACE("BlockAllocator::AllocateBlocks()\n");
597	MutexLocker lock(fLock);
598	TRACE("BlockAllocator::AllocateBlocks(): Acquired lock\n");
599
600	TRACE("BlockAllocator::AllocateBlocks(): transaction: %ld, min: %lu, "
601		"max: %lu, block group: %lu, start: %llu, num groups: %lu\n",
602		transaction.ID(), minimum, maximum, blockGroup, start, fNumGroups);
603
604	fsblock_t bestStart = 0;
605	uint32 bestLength = 0;
606	uint32 bestGroup = 0;
607
608	uint32 groupNum = blockGroup;
609
610	AllocationBlockGroup* last = &fGroups[fNumGroups];
611	AllocationBlockGroup* group = &fGroups[blockGroup];
612
613	for (int32 iterations = 0; iterations < 2; iterations++) {
614		for (; group < last; ++group, ++groupNum) {
615			TRACE("BlockAllocator::AllocateBlocks(): Group %lu has largest "
616			"length of %lu\n", groupNum, group->LargestLength());
617
618			if (group->LargestLength() > bestLength) {
619				if (start <= group->LargestStart()) {
620					bestStart = group->LargestStart();
621					bestLength = group->LargestLength();
622					bestGroup = groupNum;
623
624					TRACE("BlockAllocator::AllocateBlocks(): Found a better "
625						"range: block group: %lu, %llu-%llu\n", groupNum,
626						bestStart, bestStart + bestLength);
627
628					if (bestLength >= maximum)
629						break;
630				}
631			}
632
633			start = 0;
634		}
635
636		if (bestLength >= maximum)
637			break;
638
639		groupNum = 0;
640
641		group = &fGroups[0];
642		last = &fGroups[blockGroup + 1];
643	}
644
645	if (bestLength < minimum) {
646		TRACE("BlockAllocator::AllocateBlocks(): best range (length %lu) "
647			"doesn't have minimum length of %lu\n", bestLength, minimum);
648		return B_DEVICE_FULL;
649	}
650
651	if (bestLength > maximum)
652		bestLength = maximum;
653
654	TRACE("BlockAllocator::AllocateBlocks(): Selected range: block group %lu, "
655		"%llu-%llu\n", bestGroup, bestStart, bestStart + bestLength);
656
657	status_t status = fGroups[bestGroup].Allocate(transaction, bestStart,
658		bestLength);
659	if (status != B_OK) {
660		TRACE("BlockAllocator::AllocateBlocks(): Failed to allocate %lu blocks "
661			"inside block group %lu.\n", bestLength, bestGroup);
662		return status;
663	}
664
665	start = bestStart;
666	length = bestLength;
667	blockGroup = bestGroup;
668
669	return B_OK;
670}
671
672
673status_t
674BlockAllocator::Allocate(Transaction& transaction, Inode* inode,
675	off_t numBlocks, uint32 minimum, fsblock_t& start, uint32& allocated)
676{
677	if (numBlocks <= 0)
678		return B_ERROR;
679	if (start > fNumBlocks)
680		return B_BAD_VALUE;
681
682	uint32 group = inode->ID() / fVolume->InodesPerGroup();
683	uint32 preferred = 0;
684
685	if (inode->Size() > 0) {
686		// Try to allocate near it's last blocks
687		ext2_data_stream* dataStream = &inode->Node().stream;
688		uint32 numBlocks = inode->Size() / fVolume->BlockSize() + 1;
689		uint32 lastBlock = 0;
690
691		// DANGER! What happens with sparse files?
692		if (numBlocks < EXT2_DIRECT_BLOCKS) {
693			// Only direct blocks
694			lastBlock = dataStream->direct[numBlocks];
695		} else {
696			numBlocks -= EXT2_DIRECT_BLOCKS - 1;
697			uint32 numIndexes = fVolume->BlockSize() / 4;
698				// block size / sizeof(int32)
699			uint32 numIndexes2 = numIndexes * numIndexes;
700			uint32 numIndexes3 = numIndexes2 * numIndexes;
701			uint32 indexesInIndirect = numIndexes;
702			uint32 indexesInDoubleIndirect = indexesInIndirect
703				+ numIndexes2;
704			// uint32 indexesInTripleIndirect = indexesInDoubleIndirect
705				// + numIndexes3;
706
707			uint32 doubleIndirectBlock = EXT2_DIRECT_BLOCKS + 1;
708			uint32 indirectBlock = EXT2_DIRECT_BLOCKS;
709
710			CachedBlock cached(fVolume);
711			uint32* indirectData;
712
713			if (numBlocks > indexesInDoubleIndirect) {
714				// Triple indirect blocks
715				indirectData = (uint32*)cached.SetTo(EXT2_DIRECT_BLOCKS + 2);
716				if (indirectData == NULL)
717					return B_IO_ERROR;
718
719				uint32 index = (numBlocks - indexesInDoubleIndirect)
720					/ numIndexes3;
721				doubleIndirectBlock = indirectData[index];
722			}
723
724			if (numBlocks > indexesInIndirect) {
725				// Double indirect blocks
726				indirectData = (uint32*)cached.SetTo(doubleIndirectBlock);
727				if (indirectData == NULL)
728					return B_IO_ERROR;
729
730				uint32 index = (numBlocks - indexesInIndirect) / numIndexes2;
731				indirectBlock = indirectData[index];
732			}
733
734			indirectData = (uint32*)cached.SetTo(indirectBlock);
735				if (indirectData == NULL)
736					return B_IO_ERROR;
737
738			uint32 index = numBlocks / numIndexes;
739			lastBlock = indirectData[index];
740		}
741
742		group = (lastBlock - fFirstBlock) / fBlocksPerGroup;
743		preferred = (lastBlock - fFirstBlock) % fBlocksPerGroup + 1;
744	}
745
746	// TODO: Apply some more policies
747
748	return AllocateBlocks(transaction, minimum, minimum + 8, group, start,
749		allocated);
750}
751
752
753status_t
754BlockAllocator::Free(Transaction& transaction, fsblock_t start, uint32 length)
755{
756	TRACE("BlockAllocator::Free(%llu, %lu)\n", start, length);
757	MutexLocker lock(fLock);
758
759	if (start <= fFirstBlock) {
760		panic("Trying to free superblock!\n");
761		return B_BAD_VALUE;
762	}
763
764	if (length == 0)
765		return B_OK;
766	if (start > fNumBlocks || length > fNumBlocks)
767		return B_BAD_VALUE;
768
769	TRACE("BlockAllocator::Free(): first block: %llu, blocks per group: %lu\n",
770		fFirstBlock, fBlocksPerGroup);
771
772	start -= fFirstBlock;
773	off_t end = start + length - 1;
774
775	uint32 group = start / fBlocksPerGroup;
776	if (group >= fNumGroups) {
777		panic("BlockAllocator::Free() group %ld too big (fNumGroups %ld)\n",
778			group, fNumGroups);
779	}
780	uint32 lastGroup = end / fBlocksPerGroup;
781	start = start % fBlocksPerGroup;
782
783	if (group == lastGroup)
784		return fGroups[group].Free(transaction, start, length);
785
786	TRACE("BlockAllocator::Free(): Freeing from group %lu: %llu, %llu\n", group,
787		start, fGroups[group].NumBits() - start);
788
789	status_t status = fGroups[group].Free(transaction, start,
790		fGroups[group].NumBits() - start);
791	if (status != B_OK)
792		return status;
793
794	for (++group; group < lastGroup; ++group) {
795		TRACE("BlockAllocator::Free(): Freeing all from group %lu\n", group);
796		status = fGroups[group].FreeAll(transaction);
797		if (status != B_OK)
798			return status;
799	}
800
801	TRACE("BlockAllocator::Free(): Freeing from group %lu: 0-%llu \n", group,
802		end % fBlocksPerGroup);
803	return fGroups[group].Free(transaction, 0, (end + 1) % fBlocksPerGroup);
804}
805
806
807/*static*/ status_t
808BlockAllocator::_Initialize(BlockAllocator* allocator)
809{
810	TRACE("BlockAllocator::_Initialize()\n");
811	// fLock is already heald
812	Volume* volume = allocator->fVolume;
813
814	AllocationBlockGroup* groups = allocator->fGroups;
815	uint32 numGroups = allocator->fNumGroups - 1;
816
817	off_t freeBlocks = 0;
818	TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks);
819
820	for (uint32 i = 0; i < numGroups; ++i) {
821		status_t status = groups[i].Initialize(volume, i,
822			allocator->fBlocksPerGroup);
823		if (status != B_OK) {
824			mutex_unlock(&allocator->fLock);
825			return status;
826		}
827
828		freeBlocks += groups[i].FreeBits();
829		TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks);
830	}
831
832	// Last block group may have less blocks
833	status_t status = groups[numGroups].Initialize(volume, numGroups,
834		allocator->fNumBlocks - allocator->fBlocksPerGroup * numGroups
835		- allocator->fFirstBlock);
836	if (status != B_OK) {
837		mutex_unlock(&allocator->fLock);
838		return status;
839	}
840
841	freeBlocks += groups[numGroups].FreeBits();
842
843	TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks);
844
845	mutex_unlock(&allocator->fLock);
846
847	if (freeBlocks != volume->NumFreeBlocks()) {
848		TRACE("Counted free blocks (%llu) doesn't match value in the "
849			"superblock (%llu).\n", freeBlocks, volume->NumFreeBlocks());
850		return B_BAD_DATA;
851	}
852
853	return B_OK;
854}
855