1//----------------------------------------------------------------------
2//  This software is part of the OpenBeOS distribution and is covered
3//  by the OpenBeOS license.
4//
5//  Copyright (c) 2003 Tyler Dauwalder, tyler@dauwalder.net
6//----------------------------------------------------------------------
7
8/*! \file Allocator.cpp
9
10	Physical block allocator class implementation.
11*/
12
13#include "Allocator.h"
14
15#include <limits.h>
16
17#include "Utils.h"
18
19/*! \brief Creates a new Allocator object.
20*/
21Allocator::Allocator(uint32 blockSize)
22	: fLength(0)
23	, fBlockSize(blockSize)
24	, fBlockShift(0)
25	, fInitStatus(B_NO_INIT)
26{
27	status_t error = Udf::get_block_shift(BlockSize(), fBlockShift);
28	if (!error)
29		fInitStatus = B_OK;
30}
31
32status_t
33Allocator::InitCheck() const
34{
35	return fInitStatus;
36}
37
38/*! \brief Allocates the given block, if available.
39
40	\return
41	- B_OK: Success.
42	- error code: Failure, the block has already been allocated.
43*/
44status_t
45Allocator::GetBlock(uint32 block)
46{
47	Udf::extent_address extent(block, BlockSize());
48	return GetExtent(extent);
49}
50
51/*! \brief Allocates the given extent, if available.
52
53	\return
54	- B_OK: Success.
55	- error code: Failure, the extent (or some portion of it) has already
56	              been allocated.
57*/
58status_t
59Allocator::GetExtent(Udf::extent_address extent)
60{
61	status_t error = InitCheck();
62	if (!error) {
63		uint32 offset = extent.location();
64		uint32 length = BlocksFor(extent.length());
65		// First see if the extent is past the allocation tail,
66		// since we then don't have to do any chunklist traversal
67		if (offset >= Length()) {
68			// Add a new chunk to the end of the chunk list if
69			// necessary
70			if (offset > Length()) {
71				Udf::extent_address chunk(Length(), (offset-Length())<<BlockShift());
72				fChunkList.push_back(chunk);
73			}
74			// Adjust the tail
75			fLength = offset+length;
76			return B_OK;
77		} else {
78			// Block is not past tail, so check the chunk list
79			for (list<Udf::extent_address>::iterator i = fChunkList.begin();
80			       i != fChunkList.end();
81			         i++)
82			{
83				uint32 chunkOffset = i->location();
84				uint32 chunkLength = BlocksFor(i->length());
85				if (chunkOffset <= offset && (offset+length) <= (chunkOffset+chunkLength)) {
86					// Found it. Split the chunk. First look for an orphan
87					// before the block, then after.
88					if (chunkOffset < offset) {
89						// Orhpan before; add a new chunk in front
90						// of the current one
91						Udf::extent_address chunk(chunkOffset, (offset-chunkOffset)<<BlockShift());
92						fChunkList.insert(i, chunk);
93					}
94					if ((offset+length) < (chunkOffset+chunkLength)) {
95						// Orphan after; resize the original chunk
96						i->set_location(offset+length);
97						i->set_length(((chunkOffset+chunkLength)-(offset+length))<<BlockSize());
98					} else {
99						// No orphan after; remove the original chunk
100						fChunkList.erase(i);
101					}
102					return B_OK;
103				}
104			}
105			// No matching chunk found, we're SOL.
106			error = B_ERROR;
107		}
108	}
109	return error;
110}
111
112/*! \brief Allocates the next available block.
113
114	\param block Output parameter into which the number of the
115	             allocated block is stored.
116	\param minimumBlock The minimum acceptable block number (used
117	                    by the physical partition allocator).
118
119	\return
120	- B_OK: Success.
121	- error code: Failure, no blocks available.
122*/
123status_t
124Allocator::GetNextBlock(uint32 &block, uint32 minimumBlock)
125{
126	status_t error = InitCheck();
127	if (!error) {
128		Udf::extent_address extent;
129		error = GetNextExtent(BlockSize(), true, extent, minimumBlock);
130		if (!error)
131			block = extent.location();
132	}
133	return error;
134}
135
136/*! \brief Allocates the next available extent of given length.
137
138	\param length The desired length (in bytes) of the extent.
139	\param contiguous If false, signals that an extent of shorter length will
140	                  be accepted. This allows for small chunks of
141	                  unallocated space to be consumed, provided a
142	                  contiguous chunk is not needed.
143	\param extent Output parameter into which the extent as allocated
144	              is stored. Note that the length field of the extent
145	              may be shorter than the length parameter passed
146	              to this function is \a contiguous is false.
147	\param minimumStartingBlock The minimum acceptable starting block
148	                            for the extent (used by the physical
149	                            partition allocator).
150
151	\return
152	- B_OK: Success.
153	- error code: Failure.
154*/
155status_t
156Allocator::GetNextExtent(uint32 _length, bool contiguous,
157                         Udf::extent_address &extent,
158	                     uint32 minimumStartingBlock)
159{
160	DEBUG_INIT_ETC("Allocator", ("length: %lld, contiguous: %d", _length, contiguous));
161	uint32 length = BlocksFor(_length);
162	bool isPartial = false;
163	status_t error = InitCheck();
164	PRINT(("allocation length: %lu\n", Length()));
165	if (!error) {
166		for (list<Udf::extent_address>::iterator i = fChunkList.begin();
167		       i != fChunkList.end();
168		         i++)
169		{
170			uint32 chunkOffset = i->location();
171			uint32 chunkLength = BlocksFor(i->length());
172			if (chunkOffset < minimumStartingBlock)
173			{
174				if (minimumStartingBlock < chunkOffset+chunkLength) {
175					// Start of chunk is below min starting block. See if
176					// any part of the chunk would make for an acceptable
177					// allocation
178					uint32 difference = minimumStartingBlock - chunkOffset;
179					uint32 newOffset = minimumStartingBlock;
180					uint32 newLength = chunkLength-difference;
181					if (length <= newLength) {
182						// new chunk is still long enough
183						Udf::extent_address newExtent(newOffset, _length);
184						if (GetExtent(newExtent) == B_OK) {
185							extent = newExtent;
186							return B_OK;
187						}
188					} else if (!contiguous) {
189						// new chunk is too short, but we're allowed to
190						// allocate a shorter extent, so we'll do it.
191						Udf::extent_address newExtent(newOffset, newLength<<BlockShift());
192						if (GetExtent(newExtent) == B_OK) {
193							extent = newExtent;
194							return B_OK;
195						}
196					}
197				}
198			} else if (length <= chunkLength) {
199				// Chunk is larger than necessary. Allocate first
200				// length blocks, and resize the chunk appropriately.
201				extent.set_location(chunkOffset);
202				extent.set_length(_length);
203				if (length != chunkLength) {
204					i->set_location(chunkOffset+length);
205					i->set_length((chunkLength-length)<<BlockShift());
206				} else {
207					fChunkList.erase(i);
208				}
209				return B_OK;
210			} else if (!contiguous) {
211				extent.set_location(chunkOffset);
212				extent.set_length(chunkLength<<BlockShift());
213				fChunkList.erase(i);
214				return B_OK;
215			}
216		}
217		// No sufficient chunk found, so try to allocate from the tail
218		PRINT(("ULONG_MAX: %lu\n", ULONG_MAX));
219		uint32 maxLength = ULONG_MAX-Length();
220		PRINT(("maxLength: %lu\n", maxLength));
221		error = maxLength > 0 ? B_OK : B_DEVICE_FULL;
222		if (!error) {
223			if (minimumStartingBlock > Tail())
224				maxLength -= minimumStartingBlock - Tail();
225			uint32 tail = minimumStartingBlock > Tail() ? minimumStartingBlock : Tail();
226			if (length > maxLength) {
227				if (contiguous)
228					error = B_DEVICE_FULL;
229				else {
230					isPartial = true;
231					length = maxLength;
232				}
233			}
234			if (!error) {
235				Udf::extent_address newExtent(tail, isPartial ? length<<BlockShift() : _length);
236				if (GetExtent(newExtent) == B_OK) {
237					extent = newExtent;
238					return B_OK;
239				}
240			}
241		}
242	}
243	return error;
244}
245
246/*! \brief Returns the number of blocks needed to accomodate the
247	given number of bytes.
248*/
249uint32
250Allocator::BlocksFor(off_t bytes)
251{
252	if (BlockSize() == 0) {
253		DEBUG_INIT_ETC("Allocator", ("bytes: %ld\n", bytes));
254		PRINT(("WARNING: Allocator::BlockSize() == 0!\n"));
255		return 0;
256	} else {
257		off_t blocks = bytes >> BlockShift();
258		if (bytes % BlockSize() != 0)
259			blocks++;
260		uint64 mask = 0xffffffff;
261		mask <<= 32;
262		if (blocks & mask) {
263			// ToDo: Convert this to actually signal an error
264			DEBUG_INIT_ETC("Allocator", ("bytes: %ld\n", bytes));
265			PRINT(("WARNING: bytes argument too large for corresponding number "
266			       "of blocks to be specified with a uint32! (bytes: %Ld, blocks: %Ld, "
267			       "maxblocks: %ld).\n", bytes, blocks, ULONG_MAX));
268			blocks = 0;
269		}
270		return blocks;
271	}
272}
273