1/*
2 * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29 * Copyright (c) 1999 Apple Computer, Inc.
30 *
31 *
32 * HISTORY
33 *
34 * sdouglas 05 Nov 99 - created.
35 */
36
37#include <libkern/c++/OSArray.h>
38#include <libkern/c++/OSNumber.h>
39#include <IOKit/IORangeAllocator.h>
40#include <IOKit/IOLib.h>
41#include <IOKit/IOLocks.h>
42#include <IOKit/assert.h>
43
44/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
45
46#undef super
47#define super OSObject
48
49OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
50
51struct IORangeAllocatorElement {
52 // closed range
53 IORangeScalar start;
54 IORangeScalar end;
55};
56
57IOLock * gIORangeAllocatorLock;
58
59#define LOCK() \
60 if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )
61#define UNLOCK() \
62 if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
63
64/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
65
66bool IORangeAllocator::init( IORangeScalar endOfRange,
67 IORangeScalar _defaultAlignment,
68 UInt32 _capacity,
69 IOOptionBits _options )
70{
71 if( !super::init())
72 return( false );
73
74 if( !_capacity)
75 _capacity = 1;
76 if( !_defaultAlignment)
77 _defaultAlignment = 1;
78 capacity = 0;
79 capacityIncrement = _capacity;
80 numElements = 0;
81 elements = 0;
82 defaultAlignmentMask = _defaultAlignment - 1;
83 options = _options;
84
85 if( (!gIORangeAllocatorLock) && (options & kLocking))
86 gIORangeAllocatorLock = IOLockAlloc();
87
88 if( endOfRange)
89 deallocate( 0, endOfRange + 1 );
90
91 return( true );
92}
93
94IORangeAllocator * IORangeAllocator::withRange(
95 IORangeScalar endOfRange,
96 IORangeScalar defaultAlignment,
97 UInt32 capacity,
98 IOOptionBits options )
99{
100 IORangeAllocator * thingy;
101
102 thingy = new IORangeAllocator;
103 if( thingy && ! thingy->init( endOfRange, defaultAlignment,
104 capacity, options )) {
105 thingy->release();
106 thingy = 0;
107 }
108
109 return( thingy );
110}
111
112void IORangeAllocator::free()
113{
114 if( elements)
115 IODelete( elements, IORangeAllocatorElement, capacity );
116
117 super::free();
118}
119
120UInt32 IORangeAllocator::getFragmentCount( void )
121{
122 return( numElements );
123}
124
125UInt32 IORangeAllocator::getFragmentCapacity( void )
126{
127 return( capacity );
128}
129
130void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
131{
132 capacityIncrement = count;
133}
134
135
136// allocate element at index
137bool IORangeAllocator::allocElement( UInt32 index )
138{
139 UInt32 newCapacity;
140 IORangeAllocatorElement * newElements;
141
142 if( ((numElements == capacity) && capacityIncrement)
143 || (!elements)) {
144
145 if (os_add_overflow(capacity, capacityIncrement, &newCapacity))
146 return( false );
147 newElements = IONew( IORangeAllocatorElement, newCapacity );
148 if( !newElements)
149 return( false );
150
151 if( elements) {
152 bcopy( elements,
153 newElements,
154 index * sizeof( IORangeAllocatorElement));
155 bcopy( elements + index,
156 newElements + index + 1,
157 (numElements - index) * sizeof( IORangeAllocatorElement));
158
159 IODelete( elements, IORangeAllocatorElement, capacity );
160 }
161
162 elements = newElements;
163 capacity = newCapacity;
164
165 } else {
166
167 bcopy( elements + index,
168 elements + index + 1,
169 (numElements - index) * sizeof( IORangeAllocatorElement));
170 }
171 numElements++;
172
173 return( true );
174}
175
176// destroy element at index
177void IORangeAllocator::deallocElement( UInt32 index )
178{
179 numElements--;
180 bcopy( elements + index + 1,
181 elements + index,
182 (numElements - index) * sizeof( IORangeAllocatorElement));
183}
184
185bool IORangeAllocator::allocate( IORangeScalar size,
186 IORangeScalar * result,
187 IORangeScalar alignment )
188{
189 IORangeScalar data, dataEnd;
190 IORangeScalar thisStart, thisEnd;
191 UInt32 index;
192 bool ok = false;
193
194 if( !size || !result)
195 return( false );
196
197 if( 0 == alignment)
198 alignment = defaultAlignmentMask;
199 else
200 alignment--;
201
202 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
203
204 LOCK();
205
206 for( index = 0; index < numElements; index++ ) {
207
208 thisStart = elements[index].start;
209 thisEnd = elements[index].end;
210 data = (thisStart + alignment) & ~alignment;
211 dataEnd = (data + size - 1);
212
213 ok = (dataEnd <= thisEnd);
214 if( ok) {
215 if( data != thisStart) {
216 if( dataEnd != thisEnd) {
217 if( allocElement( index + 1 )) {
218 elements[index++].end = data - 1;
219 elements[index].start = dataEnd + 1;
220 elements[index].end = thisEnd;
221 } else
222 ok = false;
223 } else
224 elements[index].end = data - 1;
225 } else {
226 if( dataEnd != thisEnd)
227 elements[index].start = dataEnd + 1;
228 else
229 deallocElement( index );
230 }
231 if( ok)
232 *result = data;
233 break;
234 }
235 }
236
237 UNLOCK();
238
239 return( ok );
240}
241
242bool IORangeAllocator::allocateRange( IORangeScalar data,
243 IORangeScalar size )
244{
245 IORangeScalar thisStart, thisEnd;
246 IORangeScalar dataEnd;
247 UInt32 index;
248 bool found = false;
249
250 if( !size)
251 return( 0 );
252
253 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
254 dataEnd = data + size - 1;
255
256 LOCK();
257
258 for( index = 0;
259 (!found) && (index < numElements);
260 index++ ) {
261
262 thisStart = elements[index].start;
263 thisEnd = elements[index].end;
264
265 if( thisStart > data)
266 break;
267 found = (dataEnd <= thisEnd);
268
269 if( found) {
270 if( data != thisStart) {
271 if( dataEnd != thisEnd) {
272 found = allocElement( index + 1 );
273 if( found) {
274 elements[index++].end = data - 1;
275 elements[index].start = dataEnd + 1;
276 elements[index].end = thisEnd;
277 }
278 } else
279 elements[index].end = data - 1;
280 } else if( dataEnd != thisEnd)
281 elements[index].start = dataEnd + 1;
282 else
283 deallocElement( index );
284 }
285 }
286
287 UNLOCK();
288
289 return( found );
290}
291
292void IORangeAllocator::deallocate( IORangeScalar data,
293 IORangeScalar size )
294{
295 IORangeScalar dataEnd;
296 UInt32 index;
297 bool headContig = false;
298 bool tailContig = false;
299
300 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
301 dataEnd = data + size - 1;
302
303 LOCK();
304
305 for( index = 0; index < numElements; index++ ) {
306 if( elements[index].start < data) {
307 headContig = (data <= (elements[index].end + 1));
308 continue;
309 }
310 tailContig = ((data + size) >= elements[index].start);
311 break;
312 }
313
314 if( headContig) {
315 if( tailContig) {
316 elements[index-1].end = elements[index].end;
317 deallocElement( index );
318 } else /*safe*/ if( dataEnd > elements[index-1].end)
319 elements[index-1].end = dataEnd;
320
321 } else if( tailContig) {
322 if( data < elements[index].start) /*safe*/
323 elements[index].start = data;
324
325 } else if( allocElement( index)) {
326 elements[index].start = data;
327 elements[index].end = dataEnd;
328 }
329
330 UNLOCK();
331}
332
333bool IORangeAllocator::serialize(OSSerialize *s) const
334{
335 OSArray * array = OSArray::withCapacity( numElements * 2 );
336 OSNumber * num;
337 UInt32 index;
338 bool ret;
339
340 if( !array)
341 return( false );
342
343 LOCK();
344
345 for( index = 0; index < numElements; index++) {
346 if( (num = OSNumber::withNumber( elements[index].start,
347 8 * sizeof(IORangeScalar) ))) {
348 array->setObject(num);
349 num->release();
350 }
351 if( (num = OSNumber::withNumber( elements[index].end,
352 8 * sizeof(IORangeScalar) ))) {
353 array->setObject(num);
354 num->release();
355 }
356 }
357
358 UNLOCK();
359
360 ret = array->serialize(s);
361 array->release();
362
363 return( ret );
364}
365
366IORangeScalar IORangeAllocator::getFreeCount( void )
367{
368 UInt32 index;
369 IORangeScalar sum = 0;
370
371 for( index = 0; index < numElements; index++)
372 sum += elements[index].end - elements[index].start + 1;
373
374 return( sum );
375}
376
377