168f08f67SAxel Dörfler/*
239f437f7SAxel Dörfler * Copyright 2001-2017, Axel D��rfler, axeld@pinc-software.de.
3fb02804aSAxel Dörfler * This file may be used under the terms of the MIT License.
4fb02804aSAxel Dörfler */
5c42ee134SAxel Dörfler
6fd91cf4dSAxel Dörfler
75edde94cSAxel Dörfler//! Block bitmap handling and allocation policies
868f08f67SAxel Dörfler
9c42ee134SAxel Dörfler
10c42ee134SAxel Dörfler#include "BlockAllocator.h"
11c42ee134SAxel Dörfler
12a9ae9781SAxel Dörfler#include "Debug.h"
13a9ae9781SAxel Dörfler#include "Inode.h"
14a9ae9781SAxel Dörfler#include "Volume.h"
151a49a098SNathan Whitehorn
163f870da9SAxel Dörfler
17c42ee134SAxel Dörfler// Things the BlockAllocator should do:
18c42ee134SAxel Dörfler
19c42ee134SAxel Dörfler// - find a range of blocks of a certain size nearby a specific position
20820dca19SAxel Dörfler// - allocating an unsharp range of blocks for pre-allocation
21c42ee134SAxel Dörfler// - free blocks
22c42ee134SAxel Dörfler// - know how to deal with each allocation, special handling for directories,
23c42ee134SAxel Dörfler//   files, symlinks, etc. (type sensitive allocation policies)
24c42ee134SAxel Dörfler
25c42ee134SAxel Dörfler// What makes the code complicated is the fact that we are not just reading
26c42ee134SAxel Dörfler// in the whole bitmap and operate on that in memory - e.g. a 13 GB partition
27c42ee134SAxel Dörfler// with a block size of 2048 bytes already has a 800kB bitmap, and the size
28c42ee134SAxel Dörfler// of partitions will grow even more - so that's not an option.
29c42ee134SAxel Dörfler// Instead we are reading in every block when it's used - since an allocation
30c42ee134SAxel Dörfler// group can span several blocks in the block bitmap, the AllocationBlock
31c42ee134SAxel Dörfler// class is there to make handling those easier.
32c42ee134SAxel Dörfler
33820dca19SAxel Dörfler// The current implementation is only slightly optimized and could probably
34820dca19SAxel Dörfler// be improved a lot. Furthermore, the allocation policies used here should
35820dca19SAxel Dörfler// have some real world tests.
36c42ee134SAxel Dörfler
37de9c0613SAxel Dörfler#if BFS_TRACING && !defined(FS_SHELL)
38d7477802SAxel Dörflernamespace BFSBlockTracing {
39d7477802SAxel Dörfler
40a300055eSAxel Dörfler
41d7477802SAxel Dörflerclass Allocate : public AbstractTraceEntry {
42a9ae9781SAxel Dörflerpublic:
43a9ae9781SAxel Dörfler	Allocate(block_run run)
44a9ae9781SAxel Dörfler		:
45a9ae9781SAxel Dörfler		fRun(run)
46a9ae9781SAxel Dörfler	{
47a9ae9781SAxel Dörfler		Initialized();
48a9ae9781SAxel Dörfler	}
49d7477802SAxel Dörfler
50a9ae9781SAxel Dörfler	virtual void AddDump(TraceOutput& out)
51a9ae9781SAxel Dörfler	{
52a9ae9781SAxel Dörfler		out.Print("bfs:alloc %lu.%u.%u", fRun.AllocationGroup(),
53a9ae9781SAxel Dörfler			fRun.Start(), fRun.Length());
54a9ae9781SAxel Dörfler	}
55d7477802SAxel Dörfler
56a8744b0eSAxel Dörfler	const block_run& Run() const { return fRun; }
57a8744b0eSAxel Dörfler
58a9ae9781SAxel Dörflerprivate:
59a300055eSAxel Dörfler			block_run			fRun;
60d7477802SAxel Dörfler};
61d7477802SAxel Dörfler
62a300055eSAxel Dörfler
63d7477802SAxel Dörflerclass Free : public AbstractTraceEntry {
64a9ae9781SAxel Dörflerpublic:
65a9ae9781SAxel Dörfler	Free(block_run run)
66a9ae9781SAxel Dörfler		:
67a9ae9781SAxel Dörfler		fRun(run)
68a9ae9781SAxel Dörfler	{
69a9ae9781SAxel Dörfler		Initialized();
70a9ae9781SAxel Dörfler	}
71d7477802SAxel Dörfler
72a9ae9781SAxel Dörfler	virtual void AddDump(TraceOutput& out)
73a9ae9781SAxel Dörfler	{
74a9ae9781SAxel Dörfler		out.Print("bfs:free %lu.%u.%u", fRun.AllocationGroup(),
75a9ae9781SAxel Dörfler			fRun.Start(), fRun.Length());
76a9ae9781SAxel Dörfler	}
77d7477802SAxel Dörfler
78a8744b0eSAxel Dörfler	const block_run& Run() const { return fRun; }
79a8744b0eSAxel Dörfler
80a9ae9781SAxel Dörflerprivate:
81a300055eSAxel Dörfler			block_run			fRun;
82d7477802SAxel Dörfler};
83d7477802SAxel Dörfler
8442ef796eSAxel Dörfler
8542ef796eSAxel Dörflerstatic uint32
86a9ae9781SAxel Dörflerchecksum(const uint8* data, size_t size)
8742ef796eSAxel Dörfler{
88a9ae9781SAxel Dörfler	const uint32* data4 = (const uint32*)data;
8942ef796eSAxel Dörfler	uint32 sum = 0;
9042ef796eSAxel Dörfler	while (size >= 4) {
9142ef796eSAxel Dörfler		sum += *data4;
9242ef796eSAxel Dörfler		data4++;
9342ef796eSAxel Dörfler		size -= 4;
9442ef796eSAxel Dörfler	}
9542ef796eSAxel Dörfler	return sum;
9642ef796eSAxel Dörfler}
9742ef796eSAxel Dörfler
9842ef796eSAxel Dörfler
9942ef796eSAxel Dörflerclass Block : public AbstractTraceEntry {
100a9ae9781SAxel Dörflerpublic:
101a9ae9781SAxel Dörfler	Block(const char* label, off_t blockNumber, const uint8* data,
102a9ae9781SAxel Dörfler			size_t size, uint32 start = 0, uint32 length = 0)
103a9ae9781SAxel Dörfler		:
104a9ae9781SAxel Dörfler		fBlock(blockNumber),
105a9ae9781SAxel Dörfler		fData(data),
106a9ae9781SAxel Dörfler		fStart(start),
1079ec59fc9SAxel Dörfler		fLength(length),
1089ec59fc9SAxel Dörfler		fLabel(label)
109a9ae9781SAxel Dörfler	{
110a9ae9781SAxel Dörfler		fSum = checksum(data, size);
111a9ae9781SAxel Dörfler		Initialized();
112a9ae9781SAxel Dörfler	}
11342ef796eSAxel Dörfler
114a9ae9781SAxel Dörfler	virtual void AddDump(TraceOutput& out)
115a9ae9781SAxel Dörfler	{
116a9ae9781SAxel Dörfler		out.Print("bfs:%s: block %Ld (%p), sum %lu, s/l %lu/%lu", fLabel,
117a9ae9781SAxel Dörfler			fBlock, fData, fSum, fStart, fLength);
118a9ae9781SAxel Dörfler	}
11942ef796eSAxel Dörfler
120a9ae9781SAxel Dörflerprivate:
121a300055eSAxel Dörfler			off_t				fBlock;
122a300055eSAxel Dörfler			const uint8*		fData;
123a300055eSAxel Dörfler			uint32				fStart;
124a300055eSAxel Dörfler			uint32				fLength;
125a300055eSAxel Dörfler			uint32				fSum;
126a300055eSAxel Dörfler			const char*			fLabel;
1279ec59fc9SAxel Dörfler};
1289ec59fc9SAxel Dörfler
1299ec59fc9SAxel Dörfler
1309ec59fc9SAxel Dörflerclass BlockChange : public AbstractTraceEntry {
1319ec59fc9SAxel Dörflerpublic:
1329ec59fc9SAxel Dörfler	BlockChange(const char* label, int32 block, uint32 oldData, uint32 newData)
1339ec59fc9SAxel Dörfler		:
1349ec59fc9SAxel Dörfler		fBlock(block),
1359ec59fc9SAxel Dörfler		fOldData(oldData),
1369ec59fc9SAxel Dörfler		fNewData(newData),
1379ec59fc9SAxel Dörfler		fLabel(label)
1389ec59fc9SAxel Dörfler	{
1399ec59fc9SAxel Dörfler		Initialized();
1409ec59fc9SAxel Dörfler	}
1419ec59fc9SAxel Dörfler
1429ec59fc9SAxel Dörfler	virtual void AddDump(TraceOutput& out)
1439ec59fc9SAxel Dörfler	{
1449ec59fc9SAxel Dörfler		out.Print("bfs:%s: block %ld, %08lx -> %08lx", fLabel,
1459ec59fc9SAxel Dörfler			fBlock, fOldData, fNewData);
1469ec59fc9SAxel Dörfler	}
1479ec59fc9SAxel Dörfler
1489ec59fc9SAxel Dörflerprivate:
149a300055eSAxel Dörfler			int32				fBlock;
150a300055eSAxel Dörfler			uint32				fOldData;
151a300055eSAxel Dörfler			uint32				fNewData;
152a300055eSAxel Dörfler			const char*			fLabel;
15342ef796eSAxel Dörfler};
15442ef796eSAxel Dörfler
155a300055eSAxel Dörfler
156d7477802SAxel Dörfler}	// namespace BFSBlockTracing
157d7477802SAxel Dörfler
158d7477802SAxel Dörfler#	define T(x) new(std::nothrow) BFSBlockTracing::x;
159d7477802SAxel Dörfler#else
160d7477802SAxel Dörfler#	define T(x) ;
161d7477802SAxel Dörfler#endif
162d7477802SAxel Dörfler
163a8744b0eSAxel Dörfler#ifdef DEBUG_ALLOCATION_GROUPS
164a8744b0eSAxel Dörfler#	define CHECK_ALLOCATION_GROUP(group) _CheckGroup(group)
165a8744b0eSAxel Dörfler#else
166a8744b0eSAxel Dörfler#	define CHECK_ALLOCATION_GROUP(group) ;
167a8744b0eSAxel Dörfler#endif
168a8744b0eSAxel Dörfler
169c42ee134SAxel Dörfler
170c42ee134SAxel Dörflerclass AllocationBlock : public CachedBlock {
171a9ae9781SAxel Dörflerpublic:
172a9ae9781SAxel Dörfler	AllocationBlock(Volume* volume);
17398887c63SAxel Dörfler
174b06a5d91SAxel Dörfler	inline void Allocate(uint16 start, uint16 numBlocks);
175b06a5d91SAxel Dörfler	inline void Free(uint16 start, uint16 numBlocks);
176a9ae9781SAxel Dörfler	inline bool IsUsed(uint16 block);
177c42ee134SAxel Dörfler
178a9ae9781SAxel Dörfler	status_t SetTo(AllocationGroup& group, uint16 block);
179a9ae9781SAxel Dörfler	status_t SetToWritable(Transaction& transaction, AllocationGroup& group,
180a9ae9781SAxel Dörfler		uint16 block);
181c42ee134SAxel Dörfler
182a9ae9781SAxel Dörfler	uint32 NumBlockBits() const { return fNumBits; }
183a9ae9781SAxel Dörfler	uint32& Block(int32 index) { return ((uint32*)fBlock)[index]; }
184a9ae9781SAxel Dörfler	uint8* Block() const { return (uint8*)fBlock; }
185c42ee134SAxel Dörfler
186a9ae9781SAxel Dörflerprivate:
187a9ae9781SAxel Dörfler	uint32	fNumBits;
188fb02804aSAxel Dörfler#ifdef DEBUG
189a9ae9781SAxel Dörfler	bool	fWritable;
190fb02804aSAxel Dörfler#endif
191c42ee134SAxel Dörfler};
192c42ee134SAxel Dörfler
193c42ee134SAxel Dörfler
194c42ee134SAxel Dörflerclass AllocationGroup {
195a9ae9781SAxel Dörflerpublic:
196a9ae9781SAxel Dörfler	AllocationGroup();
197c42ee134SAxel Dörfler
198a9ae9781SAxel Dörfler	void AddFreeRange(int32 start, int32 blocks);
199a9ae9781SAxel Dörfler	bool IsFull() const { return fFreeBits == 0; }
200c42ee134SAxel Dörfler
201a9ae9781SAxel Dörfler	status_t Allocate(Transaction& transaction, uint16 start, int32 length);
202a9ae9781SAxel Dörfler	status_t Free(Transaction& transaction, uint16 start, int32 length);
203820dca19SAxel Dörfler
204a9ae9781SAxel Dörfler	uint32 NumBits() const { return fNumBits; }
205a9ae9781SAxel Dörfler	uint32 NumBlocks() const { return fNumBlocks; }
206a9ae9781SAxel Dörfler	int32 Start() const { return fStart; }
207f41837b4SAxel Dörfler
208a9ae9781SAxel Dörflerprivate:
209a9ae9781SAxel Dörfler	friend class BlockAllocator;
210f41837b4SAxel Dörfler
211a9ae9781SAxel Dörfler	uint32	fNumBits;
212a9ae9781SAxel Dörfler	uint32	fNumBlocks;
213a9ae9781SAxel Dörfler	int32	fStart;
214a8744b0eSAxel Dörfler	int32	fFirstFree;
215a9ae9781SAxel Dörfler	int32	fFreeBits;
216a8744b0eSAxel Dörfler
217a8744b0eSAxel Dörfler	int32	fLargestStart;
218a8744b0eSAxel Dörfler	int32	fLargestLength;
219a8744b0eSAxel Dörfler	bool	fLargestValid;
220c42ee134SAxel Dörfler};
221c42ee134SAxel Dörfler
222c42ee134SAxel Dörfler
223a9ae9781SAxel DörflerAllocationBlock::AllocationBlock(Volume* volume)
224c42ee134SAxel Dörfler	: CachedBlock(volume)
225c42ee134SAxel Dörfler{
226c42ee134SAxel Dörfler}
227c42ee134SAxel Dörfler
228c42ee134SAxel Dörfler
229f41837b4SAxel Dörflerstatus_t
230a9ae9781SAxel DörflerAllocationBlock::SetTo(AllocationGroup& group, uint16 block)
231c42ee134SAxel Dörfler{
232c42ee134SAxel Dörfler	// 8 blocks per byte
233c42ee134SAxel Dörfler	fNumBits = fVolume->BlockSize() << 3;
234f41837b4SAxel Dörfler	// the last group may have less bits than the others
235f41837b4SAxel Dörfler	if ((block + 1) * fNumBits > group.NumBits())
236f41837b4SAxel Dörfler		fNumBits = group.NumBits() % fNumBits;
237c42ee134SAxel Dörfler
238fb02804aSAxel Dörfler#ifdef DEBUG
239fb02804aSAxel Dörfler	fWritable = false;
240fb02804aSAxel Dörfler#endif
241f41837b4SAxel Dörfler	return CachedBlock::SetTo(group.Start() + block) != NULL ? B_OK : B_ERROR;
242c42ee134SAxel Dörfler}
243c42ee134SAxel Dörfler
244c42ee134SAxel Dörfler
245f41837b4SAxel Dörflerstatus_t
246a9ae9781SAxel DörflerAllocationBlock::SetToWritable(Transaction& transaction, AllocationGroup& group,
24709c46ea8SAxel Dörfler	uint16 block)
248fb02804aSAxel Dörfler{
249fb02804aSAxel Dörfler	// 8 blocks per byte
250fb02804aSAxel Dörfler	fNumBits = fVolume->BlockSize() << 3;
251fb02804aSAxel Dörfler	// the last group may have less bits in the last block
252f41837b4SAxel Dörfler	if ((block + 1) * fNumBits > group.NumBits())
253f41837b4SAxel Dörfler		fNumBits = group.NumBits() % fNumBits;
254fb02804aSAxel Dörfler
255fb02804aSAxel Dörfler#ifdef DEBUG
256fb02804aSAxel Dörfler	fWritable = true;
257fb02804aSAxel Dörfler#endif
25809c46ea8SAxel Dörfler	return CachedBlock::SetToWritable(transaction, group.Start() + block)
25909c46ea8SAxel Dörfler		!= NULL ? B_OK : B_ERROR;
260fb02804aSAxel Dörfler}
261fb02804aSAxel Dörfler
262fb02804aSAxel Dörfler
263f41837b4SAxel Dörflerbool
264c42ee134SAxel DörflerAllocationBlock::IsUsed(uint16 block)
265c42ee134SAxel Dörfler{
266c42ee134SAxel Dörfler	if (block > fNumBits)
267c42ee134SAxel Dörfler		return true;
268f41837b4SAxel Dörfler
2692b5451f1SAxel Dörfler	// the block bitmap is accessed in 32-bit blocks
270cb94280cSAxel Dörfler	return Block(block >> 5) & HOST_ENDIAN_TO_BFS_INT32(1UL << (block % 32));
271c42ee134SAxel Dörfler}
272c42ee134SAxel Dörfler
273c42ee134SAxel Dörfler
274c42ee134SAxel Dörflervoid
275820dca19SAxel DörflerAllocationBlock::Allocate(uint16 start, uint16 numBlocks)
276c42ee134SAxel Dörfler{
27798887c63SAxel Dörfler	ASSERT(start < fNumBits);
27898b972c9SAxel Dörfler	ASSERT(uint32(start + numBlocks) <= fNumBits);
279fb02804aSAxel Dörfler#ifdef DEBUG
280fb02804aSAxel Dörfler	ASSERT(fWritable);
281fb02804aSAxel Dörfler#endif
28298887c63SAxel Dörfler
28309c46ea8SAxel Dörfler	T(Block("b-alloc-in", fBlockNumber, fBlock, fVolume->BlockSize(),
28409c46ea8SAxel Dörfler		start, numBlocks));
28509c46ea8SAxel Dörfler
286c42ee134SAxel Dörfler	int32 block = start >> 5;
287c42ee134SAxel Dörfler
288c42ee134SAxel Dörfler	while (numBlocks > 0) {
289c42ee134SAxel Dörfler		uint32 mask = 0;
2903f870da9SAxel Dörfler		for (int32 i = start % 32; i < 32 && numBlocks; i++, numBlocks--)
29109c46ea8SAxel Dörfler			mask |= 1UL << i;
2929ec59fc9SAxel Dörfler
2939ec59fc9SAxel Dörfler		T(BlockChange("b-alloc", block, Block(block),
2949ec59fc9SAxel Dörfler			Block(block) | HOST_ENDIAN_TO_BFS_INT32(mask)));
2959ec59fc9SAxel Dörfler
2969ec59fc9SAxel Dörfler#if KDEBUG
29798887c63SAxel Dörfler		// check for already set blocks
298a9ae9781SAxel Dörfler		if (HOST_ENDIAN_TO_BFS_INT32(mask) & ((uint32*)fBlock)[block]) {
299a8744b0eSAxel Dörfler			FATAL(("AllocationBlock::Allocate(): some blocks are already "
300a8744b0eSAxel Dörfler				"allocated, start = %u, numBlocks = %u\n", start, numBlocks));
3019ec59fc9SAxel Dörfler			panic("blocks already set!");
30223d098b6SAxel Dörfler		}
30323d098b6SAxel Dörfler#endif
3049ec59fc9SAxel Dörfler
305cb94280cSAxel Dörfler		Block(block++) |= HOST_ENDIAN_TO_BFS_INT32(mask);
306c42ee134SAxel Dörfler		start = 0;
307c42ee134SAxel Dörfler	}
30809c46ea8SAxel Dörfler	T(Block("b-alloc-out", fBlockNumber, fBlock, fVolume->BlockSize(),
30909c46ea8SAxel Dörfler		start, numBlocks));
310c42ee134SAxel Dörfler}
311c42ee134SAxel Dörfler
312c42ee134SAxel Dörfler
313c42ee134SAxel Dörflervoid
314820dca19SAxel DörflerAllocationBlock::Free(uint16 start, uint16 numBlocks)
315c42ee134SAxel Dörfler{
31698887c63SAxel Dörfler	ASSERT(start < fNumBits);
31798b972c9SAxel Dörfler	ASSERT(uint32(start + numBlocks) <= fNumBits);
318fb02804aSAxel Dörfler#ifdef DEBUG
319fb02804aSAxel Dörfler	ASSERT(fWritable);
320fb02804aSAxel Dörfler#endif
32198887c63SAxel Dörfler
322c42ee134SAxel Dörfler	int32 block = start >> 5;
323c42ee134SAxel Dörfler
324c42ee134SAxel Dörfler	while (numBlocks > 0) {
325c42ee134SAxel Dörfler		uint32 mask = 0;
3263f870da9SAxel Dörfler		for (int32 i = start % 32; i < 32 && numBlocks; i++, numBlocks--)
327c42ee134SAxel Dörfler			mask |= 1UL << (i % 32);
328c42ee134SAxel Dörfler
3299ec59fc9SAxel Dörfler		T(BlockChange("b-free", block, Block(block),
3309ec59fc9SAxel Dörfler			Block(block) & HOST_ENDIAN_TO_BFS_INT32(~mask)));
3319ec59fc9SAxel Dörfler
332cb94280cSAxel Dörfler		Block(block++) &= HOST_ENDIAN_TO_BFS_INT32(~mask);
333c42ee134SAxel Dörfler		start = 0;
334c42ee134SAxel Dörfler	}
335c42ee134SAxel Dörfler}
336c42ee134SAxel Dörfler
337c42ee134SAxel Dörfler
338c42ee134SAxel Dörfler//	#pragma mark -
339c42ee134SAxel Dörfler
340c42ee134SAxel Dörfler
34109c46ea8SAxel Dörfler/*!	The allocation groups are created and initialized in
34209c46ea8SAxel Dörfler	BlockAllocator::Initialize() and BlockAllocator::InitializeAndClearBitmap()
34309c46ea8SAxel Dörfler	respectively.
34409c46ea8SAxel Dörfler*/
345c42ee134SAxel DörflerAllocationGroup::AllocationGroup()
346c42ee134SAxel Dörfler	:
347c42ee134SAxel Dörfler	fFirstFree(-1),
348a8744b0eSAxel Dörfler	fFreeBits(0),
349a8744b0eSAxel Dörfler	fLargestValid(false)
350c42ee134SAxel Dörfler{
351c42ee134SAxel Dörfler}
352c42ee134SAxel Dörfler
353c42ee134SAxel Dörfler
354f41837b4SAxel Dörflervoid
355c42ee134SAxel DörflerAllocationGroup::AddFreeRange(int32 start, int32 blocks)
356c42ee134SAxel Dörfler{
357b98d9a33SAxel Dörfler	//D(if (blocks > 512)
358b98d9a33SAxel Dörfler	//	PRINT(("range of %ld blocks starting at %ld\n",blocks,start)));
359c42ee134SAxel Dörfler
360c42ee134SAxel Dörfler	if (fFirstFree == -1)
361c42ee134SAxel Dörfler		fFirstFree = start;
362c42ee134SAxel Dörfler
363a8744b0eSAxel Dörfler	if (!fLargestValid || fLargestLength < blocks) {
364a8744b0eSAxel Dörfler		fLargestStart = start;
365a8744b0eSAxel Dörfler		fLargestLength = blocks;
366a8744b0eSAxel Dörfler		fLargestValid = true;
367c42ee134SAxel Dörfler	}
368c42ee134SAxel Dörfler
369c42ee134SAxel Dörfler	fFreeBits += blocks;
370c42ee134SAxel Dörfler}
371c42ee134SAxel Dörfler
372c42ee134SAxel Dörfler
37309c46ea8SAxel Dörfler/*!	Allocates the specified run in the allocation group.
37409c46ea8SAxel Dörfler	Doesn't check if the run is valid or already allocated partially, nor
37509c46ea8SAxel Dörfler	does it maintain the free ranges hints or the volume's used blocks count.
37609c46ea8SAxel Dörfler	It only does the low-level work of allocating some bits in the block bitmap.
37709c46ea8SAxel Dörfler	Assumes that the block bitmap lock is hold.
37809c46ea8SAxel Dörfler*/
379820dca19SAxel Dörflerstatus_t
380a9ae9781SAxel DörflerAllocationGroup::Allocate(Transaction& transaction, uint16 start, int32 length)
381820dca19SAxel Dörfler{
382a0a1bf7fSAxel Dörfler	ASSERT(start + length <= (int32)fNumBits);
38398887c63SAxel Dörfler
38498887c63SAxel Dörfler	// Update the allocation group info
385a9ae9781SAxel Dörfler	// TODO: this info will be incorrect if something goes wrong later
38698887c63SAxel Dörfler	// Note, the fFirstFree block doesn't have to be really free
38798887c63SAxel Dörfler	if (start == fFirstFree)
38898887c63SAxel Dörfler		fFirstFree = start + length;
38998887c63SAxel Dörfler	fFreeBits -= length;
39098887c63SAxel Dörfler
391a8744b0eSAxel Dörfler	if (fLargestValid) {
39258a77fd3SAxel Dörfler		bool cut = false;
393a8744b0eSAxel Dörfler		if (fLargestStart == start) {
39458a77fd3SAxel Dörfler			// cut from start
395a8744b0eSAxel Dörfler			fLargestStart += length;
396a8744b0eSAxel Dörfler			fLargestLength -= length;
39758a77fd3SAxel Dörfler			cut = true;
398a8744b0eSAxel Dörfler		} else if (start > fLargestStart
399a8744b0eSAxel Dörfler			&& start < fLargestStart + fLargestLength) {
40058a77fd3SAxel Dörfler			// cut from end
401a8744b0eSAxel Dörfler			fLargestLength = start - fLargestStart;
40258a77fd3SAxel Dörfler			cut = true;
403a8744b0eSAxel Dörfler		}
40458a77fd3SAxel Dörfler		if (cut && (fLargestLength < fLargestStart
40558a77fd3SAxel Dörfler				|| fLargestLength
40658a77fd3SAxel Dörfler						< (int32)fNumBits - (fLargestStart + fLargestLength))) {
40758a77fd3SAxel Dörfler			// might not be the largest block anymore
408a8744b0eSAxel Dörfler			fLargestValid = false;
409a8744b0eSAxel Dörfler		}
410a8744b0eSAxel Dörfler	}
411a8744b0eSAxel Dörfler
412a9ae9781SAxel Dörfler	Volume* volume = transaction.GetVolume();
41323d098b6SAxel Dörfler
41423d098b6SAxel Dörfler	// calculate block in the block bitmap and position within
41523d098b6SAxel Dörfler	uint32 bitsPerBlock = volume->BlockSize() << 3;
41623d098b6SAxel Dörfler	uint32 block = start / bitsPerBlock;
41723d098b6SAxel Dörfler	start = start % bitsPerBlock;
41823d098b6SAxel Dörfler
419820dca19SAxel Dörfler	AllocationBlock cached(volume);
420820dca19SAxel Dörfler
421820dca19SAxel Dörfler	while (length > 0) {
422a8744b0eSAxel Dörfler		if (cached.SetToWritable(transaction, *this, block) < B_OK) {
423a8744b0eSAxel Dörfler			fLargestValid = false;
424820dca19SAxel Dörfler			RETURN_ERROR(B_IO_ERROR);
425a8744b0eSAxel Dörfler		}
426820dca19SAxel Dörfler
427820dca19SAxel Dörfler		uint32 numBlocks = length;
428820dca19SAxel Dörfler		if (start + numBlocks > cached.NumBlockBits())
429820dca19SAxel Dörfler			numBlocks = cached.NumBlockBits() - start;
430820dca19SAxel Dörfler
431820dca19SAxel Dörfler		cached.Allocate(start, numBlocks);
432820dca19SAxel Dörfler
433820dca19SAxel Dörfler		length -= numBlocks;
434820dca19SAxel Dörfler		start = 0;
435820dca19SAxel Dörfler		block++;
436820dca19SAxel Dörfler	}
43798887c63SAxel Dörfler
438820dca19SAxel Dörfler	return B_OK;
439820dca19SAxel Dörfler}
440820dca19SAxel Dörfler
441820dca19SAxel Dörfler
44209c46ea8SAxel Dörfler/*!	Frees the specified run in the allocation group.
44309c46ea8SAxel Dörfler	Doesn't check if the run is valid or was not completely allocated, nor
44409c46ea8SAxel Dörfler	does it maintain the free ranges hints or the volume's used blocks count.
44509c46ea8SAxel Dörfler	It only does the low-level work of freeing some bits in the block bitmap.
44609c46ea8SAxel Dörfler	Assumes that the block bitmap lock is hold.
44709c46ea8SAxel Dörfler*/
448820dca19SAxel Dörflerstatus_t
449a9ae9781SAxel DörflerAllocationGroup::Free(Transaction& transaction, uint16 start, int32 length)
450820dca19SAxel Dörfler{
451a0a1bf7fSAxel Dörfler	ASSERT(start + length <= (int32)fNumBits);
45298887c63SAxel Dörfler
45398887c63SAxel Dörfler	// Update the allocation group info
454a9ae9781SAxel Dörfler	// TODO: this info will be incorrect if something goes wrong later
45598887c63SAxel Dörfler	if (fFirstFree > start)
45698887c63SAxel Dörfler		fFirstFree = start;
45798887c63SAxel Dörfler	fFreeBits += length;
45898887c63SAxel Dörfler
459a8744b0eSAxel Dörfler	// The range to be freed cannot be part of the valid largest range
46058a77fd3SAxel Dörfler	ASSERT(!fLargestValid || start + length <= fLargestStart
46158a77fd3SAxel Dörfler		|| start > fLargestStart);
462a8744b0eSAxel Dörfler
463a8744b0eSAxel Dörfler	if (fLargestValid
464a8744b0eSAxel Dörfler		&& (start + length == fLargestStart
465a8744b0eSAxel Dörfler			|| fLargestStart + fLargestLength == start
466a8744b0eSAxel Dörfler			|| (start < fLargestStart && fLargestStart > fLargestLength)
467a8744b0eSAxel Dörfler			|| (start > fLargestStart
468a8744b0eSAxel Dörfler				&& (int32)fNumBits - (fLargestStart + fLargestLength)
469a8744b0eSAxel Dörfler						> fLargestLength))) {
470a8744b0eSAxel Dörfler		fLargestValid = false;
471a8744b0eSAxel Dörfler	}
472a8744b0eSAxel Dörfler
473a9ae9781SAxel Dörfler	Volume* volume = transaction.GetVolume();
47423d098b6SAxel Dörfler
47523d098b6SAxel Dörfler	// calculate block in the block bitmap and position within
47623d098b6SAxel Dörfler	uint32 bitsPerBlock = volume->BlockSize() << 3;
47723d098b6SAxel Dörfler	uint32 block = start / bitsPerBlock;
47823d098b6SAxel Dörfler	start = start % bitsPerBlock;
47923d098b6SAxel Dörfler
480820dca19SAxel Dörfler	AllocationBlock cached(volume);
481820dca19SAxel Dörfler
482820dca19SAxel Dörfler	while (length > 0) {
483fb02804aSAxel Dörfler		if (cached.SetToWritable(transaction, *this, block) < B_OK)
484820dca19SAxel Dörfler			RETURN_ERROR(B_IO_ERROR);
485820dca19SAxel Dörfler
48642ef796eSAxel Dörfler		T(Block("free-1", block, cached.Block(), volume->BlockSize()));
487820dca19SAxel Dörfler		uint16 freeLength = length;
488bc8d3bdaSAxel Dörfler		if (uint32(start + length) > cached.NumBlockBits())
489820dca19SAxel Dörfler			freeLength = cached.NumBlockBits() - start;
490820dca19SAxel Dörfler
491820dca19SAxel Dörfler		cached.Free(start, freeLength);
492820dca19SAxel Dörfler
493820dca19SAxel Dörfler		length -= freeLength;
494820dca19SAxel Dörfler		start = 0;
49542ef796eSAxel Dörfler		T(Block("free-2", block, cached.Block(), volume->BlockSize()));
496820dca19SAxel Dörfler		block++;
497820dca19SAxel Dörfler	}
49898b972c9SAxel Dörfler	return B_OK;
499820dca19SAxel Dörfler}
500820dca19SAxel Dörfler
501820dca19SAxel Dörfler
502c42ee134SAxel Dörfler//	#pragma mark -
503c42ee134SAxel Dörfler
504c42ee134SAxel Dörfler
505a9ae9781SAxel DörflerBlockAllocator::BlockAllocator(Volume* volume)
506c42ee134SAxel Dörfler	:
507c42ee134SAxel Dörfler	fVolume(volume),
508aa775038Sahenriksson	fGroups(NULL)
509aa775038Sahenriksson	//fCheckBitmap(NULL),
510aa775038Sahenriksson	//fCheckCookie(NULL)
511c42ee134SAxel Dörfler{
512b81ce430SAxel Dörfler	recursive_lock_init(&fLock, "bfs allocator");
513c42ee134SAxel Dörfler}
514c42ee134SAxel Dörfler
515c42ee134SAxel Dörfler
516c42ee134SAxel DörflerBlockAllocator::~BlockAllocator()
517c42ee134SAxel Dörfler{
518b81ce430SAxel Dörfler	recursive_lock_destroy(&fLock);
519c42ee134SAxel Dörfler	delete[] fGroups;
520c42ee134SAxel Dörfler}
521c42ee134SAxel Dörfler
522c42ee134SAxel Dörfler
523f41837b4SAxel Dörflerstatus_t
52481566b93SAxel DörflerBlockAllocator::Initialize(bool full)
525c42ee134SAxel Dörfler{
526c42ee134SAxel Dörfler	fNumGroups = fVolume->AllocationGroups();
527cb94280cSAxel Dörfler	fBlocksPerGroup = fVolume->SuperBlock().BlocksPerAllocationGroup();
528aa775038Sahenriksson	//fNumBlocks = (fVolume->NumBlocks() + fVolume->BlockSize() * 8 - 1)
529aa775038Sahenriksson		/// (fVolume->BlockSize() * 8);
530aa775038Sahenriksson	fNumBlocks = fVolume->NumBitmapBlocks();
5313e69a3c2SAxel Dörfler
532bdce1498SJérôme Duval	fGroups = new(std::nothrow) AllocationGroup[fNumGroups];
533c42ee134SAxel Dörfler	if (fGroups == NULL)
534c42ee134SAxel Dörfler		return B_NO_MEMORY;
535b98d9a33SAxel Dörfler
53681566b93SAxel Dörfler	if (!full)
53781566b93SAxel Dörfler		return B_OK;
53881566b93SAxel Dörfler
539b81ce430SAxel Dörfler	recursive_lock_lock(&fLock);
54003fa417bSAxel Dörfler		// the lock will be released by the _Initialize() method
541c832ff1eSAxel Dörfler
542f41837b4SAxel Dörfler	thread_id id = spawn_kernel_thread((thread_func)BlockAllocator::_Initialize,
543a9ae9781SAxel Dörfler		"bfs block allocator", B_LOW_PRIORITY, this);
544c42ee134SAxel Dörfler	if (id < B_OK)
545f41837b4SAxel Dörfler		return _Initialize(this);
546a9ae9781SAxel Dörfler
547b81ce430SAxel Dörfler	recursive_lock_transfer_lock(&fLock, id);
548c42ee134SAxel Dörfler
549c42ee134SAxel Dörfler	return resume_thread(id);
550c42ee134SAxel Dörfler}
551c42ee134SAxel Dörfler
552c42ee134SAxel Dörfler
553f41837b4SAxel Dörflerstatus_t
554a9ae9781SAxel DörflerBlockAllocator::InitializeAndClearBitmap(Transaction& transaction)
55581566b93SAxel Dörfler{
55681566b93SAxel Dörfler	status_t status = Initialize(false);
5573e69a3c2SAxel Dörfler	if (status != B_OK)
55881566b93SAxel Dörfler		return status;
55981566b93SAxel Dörfler
5603e69a3c2SAxel Dörfler	uint32 numBits = 8 * fBlocksPerGroup * fVolume->BlockSize();
561fb02804aSAxel Dörfler	uint32 blockShift = fVolume->BlockShift();
56281566b93SAxel Dörfler
563a9ae9781SAxel Dörfler	uint32* buffer = (uint32*)malloc(numBits >> 3);
56481566b93SAxel Dörfler	if (buffer == NULL)
56581566b93SAxel Dörfler		RETURN_ERROR(B_NO_MEMORY);
56681566b93SAxel Dörfler
56781566b93SAxel Dörfler	memset(buffer, 0, numBits >> 3);
56881566b93SAxel Dörfler
56981566b93SAxel Dörfler	off_t offset = 1;
57046cf7a5aSPrzemysław Buczkowski		// the bitmap starts directly after the superblock
57181566b93SAxel Dörfler
57281566b93SAxel Dörfler	// initialize the AllocationGroup objects and clear the on-disk bitmap
57381566b93SAxel Dörfler
57481566b93SAxel Dörfler	for (int32 i = 0; i < fNumGroups; i++) {
575a9ae9781SAxel Dörfler		if (write_pos(fVolume->Device(), offset << blockShift, buffer,
576579e19f5SAxel Dörfler				fBlocksPerGroup << blockShift) < B_OK) {
577579e19f5SAxel Dörfler			free(buffer);
57881566b93SAxel Dörfler			return B_ERROR;
579579e19f5SAxel Dörfler		}
58081566b93SAxel Dörfler
58181566b93SAxel Dörfler		// the last allocation group may contain less blocks than the others
582f41837b4SAxel Dörfler		if (i == fNumGroups - 1) {
58360a50e3aSAxel Dörfler			fGroups[i].fNumBits = fVolume->NumBlocks() - i * numBits;
584a9ae9781SAxel Dörfler			fGroups[i].fNumBlocks = 1 + ((fGroups[i].NumBits() - 1)
585a9ae9781SAxel Dörfler				>> (blockShift + 3));
586f41837b4SAxel Dörfler		} else {
587f41837b4SAxel Dörfler			fGroups[i].fNumBits = numBits;
5883e69a3c2SAxel Dörfler			fGroups[i].fNumBlocks = fBlocksPerGroup;
589f41837b4SAxel Dörfler		}
59081566b93SAxel Dörfler		fGroups[i].fStart = offset;
591a8744b0eSAxel Dörfler		fGroups[i].fFirstFree = fGroups[i].fLargestStart = 0;
592a8744b0eSAxel Dörfler		fGroups[i].fFreeBits = fGroups[i].fLargestLength = fGroups[i].fNumBits;
593a8744b0eSAxel Dörfler		fGroups[i].fLargestValid = true;
59481566b93SAxel Dörfler
5953e69a3c2SAxel Dörfler		offset += fBlocksPerGroup;
59681566b93SAxel Dörfler	}
59781566b93SAxel Dörfler	free(buffer);
59881566b93SAxel Dörfler
59981566b93SAxel Dörfler	// reserve the boot block, the log area, and the block bitmap itself
60081566b93SAxel Dörfler	uint32 reservedBlocks = fVolume->Log().Start() + fVolume->Log().Length();
60181566b93SAxel Dörfler
602fb02804aSAxel Dörfler	if (fGroups[0].Allocate(transaction, 0, reservedBlocks) < B_OK) {
60381566b93SAxel Dörfler		FATAL(("could not allocate reserved space for block bitmap/log!\n"));
60481566b93SAxel Dörfler		return B_ERROR;
60581566b93SAxel Dörfler	}
606a9ae9781SAxel Dörfler	fVolume->SuperBlock().used_blocks
607a9ae9781SAxel Dörfler		= HOST_ENDIAN_TO_BFS_INT64(reservedBlocks);
60881566b93SAxel Dörfler
60981566b93SAxel Dörfler	return B_OK;
61081566b93SAxel Dörfler}
61181566b93SAxel Dörfler
61281566b93SAxel Dörfler
613f41837b4SAxel Dörflerstatus_t
614a9ae9781SAxel DörflerBlockAllocator::_Initialize(BlockAllocator* allocator)
615c42ee134SAxel Dörfler{
61634cf473dSAxel Dörfler	// The lock must already be held at this point
617b81ce430SAxel Dörfler	RecursiveLocker locker(allocator->fLock, true);
618c42ee134SAxel Dörfler
619a9ae9781SAxel Dörfler	Volume* volume = allocator->fVolume;
620c42ee134SAxel Dörfler	uint32 blocks = allocator->fBlocksPerGroup;
621fb02804aSAxel Dörfler	uint32 blockShift = volume->BlockShift();
622c42ee134SAxel Dörfler	off_t freeBlocks = 0;
623c42ee134SAxel Dörfler
624a9ae9781SAxel Dörfler	uint32* buffer = (uint32*)malloc(blocks << blockShift);
625b81ce430SAxel Dörfler	if (buffer == NULL)
626c42ee134SAxel Dörfler		RETURN_ERROR(B_NO_MEMORY);
627c42ee134SAxel Dörfler
628a9ae9781SAxel Dörfler	AllocationGroup* groups = allocator->fGroups;
629c42ee134SAxel Dörfler	off_t offset = 1;
63068f08f67SAxel Dörfler	uint32 bitsPerGroup = 8 * (blocks << blockShift);
63168f08f67SAxel Dörfler	int32 numGroups = allocator->fNumGroups;
632c42ee134SAxel Dörfler
63368f08f67SAxel Dörfler	for (int32 i = 0; i < numGroups; i++) {
634f41837b4SAxel Dörfler		if (read_pos(volume->Device(), offset << blockShift, buffer,
635f41837b4SAxel Dörfler				blocks << blockShift) < B_OK)
636c42ee134SAxel Dörfler			break;
637c42ee134SAxel Dörfler
638c42ee134SAxel Dörfler		// the last allocation group may contain less blocks than the others
63968f08f67SAxel Dörfler		if (i == numGroups - 1) {
64068f08f67SAxel Dörfler			groups[i].fNumBits = volume->NumBlocks() - i * bitsPerGroup;
641a9ae9781SAxel Dörfler			groups[i].fNumBlocks = 1 + ((groups[i].NumBits() - 1)
642a9ae9781SAxel Dörfler				>> (blockShift + 3));
643f41837b4SAxel Dörfler		} else {
64468f08f67SAxel Dörfler			groups[i].fNumBits = bitsPerGroup;
645f41837b4SAxel Dörfler			groups[i].fNumBlocks = blocks;
646f41837b4SAxel Dörfler		}
647c42ee134SAxel Dörfler		groups[i].fStart = offset;
648c42ee134SAxel Dörfler
649c42ee134SAxel Dörfler		// finds all free ranges in this allocation group
650bc8d3bdaSAxel Dörfler		int32 start = -1, range = 0;
65168f08f67SAxel Dörfler		int32 numBits = groups[i].fNumBits, bit = 0;
65268f08f67SAxel Dörfler		int32 count = (numBits + 31) / 32;
653c42ee134SAxel Dörfler
65468f08f67SAxel Dörfler		for (int32 k = 0; k < count; k++) {
65568f08f67SAxel Dörfler			for (int32 j = 0; j < 32 && bit < numBits; j++, bit++) {
656c42ee134SAxel Dörfler				if (buffer[k] & (1UL << j)) {
65768f08f67SAxel Dörfler					// block is in use
658c42ee134SAxel Dörfler					if (range > 0) {
659820dca19SAxel Dörfler						groups[i].AddFreeRange(start, range);
660c42ee134SAxel Dörfler						range = 0;
661c42ee134SAxel Dörfler					}
66268f08f67SAxel Dörfler				} else if (range++ == 0) {
66368f08f67SAxel Dörfler					// block is free, start new free range
66468f08f67SAxel Dörfler					start = bit;
66568f08f67SAxel Dörfler				}
666c42ee134SAxel Dörfler			}
667c42ee134SAxel Dörfler		}
668c42ee134SAxel Dörfler		if (range)
669820dca19SAxel Dörfler			groups[i].AddFreeRange(start, range);
670c42ee134SAxel Dörfler
671c42ee134SAxel Dörfler		freeBlocks += groups[i].fFreeBits;
672c42ee134SAxel Dörfler
673c42ee134SAxel Dörfler		offset += blocks;
674c42ee134SAxel Dörfler	}
675c42ee134SAxel Dörfler	free(buffer);
676c42ee134SAxel Dörfler
677820dca19SAxel Dörfler	// check if block bitmap and log area are reserved
678cb94280cSAxel Dörfler	uint32 reservedBlocks = volume->Log().Start() + volume->Log().Length();
6793e69a3c2SAxel Dörfler
6803e69a3c2SAxel Dörfler	if (allocator->CheckBlocks(0, reservedBlocks) != B_OK) {
68166ae5b2dSAxel Dörfler		if (volume->IsReadOnly()) {
68266ae5b2dSAxel Dörfler			FATAL(("Space for block bitmap or log area is not reserved "
68366ae5b2dSAxel Dörfler				"(volume is mounted read-only)!\n"));
684820dca19SAxel Dörfler		} else {
68566ae5b2dSAxel Dörfler			Transaction transaction(volume, 0);
68666ae5b2dSAxel Dörfler			if (groups[0].Allocate(transaction, 0, reservedBlocks) != B_OK) {
68766ae5b2dSAxel Dörfler				FATAL(("Could not allocate reserved space for block "
68866ae5b2dSAxel Dörfler					"bitmap/log!\n"));
68966ae5b2dSAxel Dörfler				volume->Panic();
69066ae5b2dSAxel Dörfler			} else {
69166ae5b2dSAxel Dörfler				transaction.Done();
69266ae5b2dSAxel Dörfler				FATAL(("Space for block bitmap or log area was not "
69366ae5b2dSAxel Dörfler					"reserved!\n"));
69466ae5b2dSAxel Dörfler			}
695820dca19SAxel Dörfler		}
696