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	newCapacity = capacity + capacityIncrement;
146	newElements = IONew( IORangeAllocatorElement, newCapacity );
147	if( !newElements)
148	    return( false );
149
150	if( elements) {
151	    bcopy( elements,
152		   newElements,
153		   index * sizeof( IORangeAllocatorElement));
154	    bcopy( elements + index,
155		   newElements + index + 1,
156		   (numElements - index) * sizeof( IORangeAllocatorElement));
157
158	    IODelete( elements, IORangeAllocatorElement, capacity );
159	}
160
161	elements = newElements;
162	capacity = newCapacity;
163
164    } else {
165
166	bcopy( elements + index,
167	       elements + index + 1,
168	       (numElements - index) * sizeof( IORangeAllocatorElement));
169    }
170    numElements++;
171
172    return( true );
173}
174
175// destroy element at index
176void IORangeAllocator::deallocElement( UInt32 index )
177{
178    numElements--;
179    bcopy( elements + index + 1,
180	   elements + index,
181	   (numElements - index) * sizeof( IORangeAllocatorElement));
182}
183
184bool IORangeAllocator::allocate( IORangeScalar size,
185				 IORangeScalar * result,
186				 IORangeScalar alignment )
187{
188    IORangeScalar	data, dataEnd;
189    IORangeScalar	thisStart, thisEnd;
190    UInt32		index;
191    bool		ok = false;
192
193    if( !size || !result)
194	return( false );
195
196    if( 0 == alignment)
197	alignment = defaultAlignmentMask;
198    else
199        alignment--;
200
201    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
202
203    LOCK();
204
205    for( index = 0; index < numElements; index++ ) {
206
207	thisStart = elements[index].start;
208	thisEnd = elements[index].end;
209        data = (thisStart + alignment) & ~alignment;
210	dataEnd = (data + size - 1);
211
212	ok = (dataEnd <= thisEnd);
213	if( ok) {
214	    if( data != thisStart) {
215		if( dataEnd != thisEnd) {
216		    if( allocElement( index + 1 )) {
217			elements[index++].end = data - 1;
218			elements[index].start = dataEnd + 1;
219			elements[index].end = thisEnd;
220		    } else
221			ok = false;
222		} else
223		    elements[index].end = data - 1;
224	    } else {
225		if( dataEnd != thisEnd)
226		    elements[index].start = dataEnd + 1;
227		else
228		    deallocElement( index );
229	    }
230	    if( ok)
231		*result = data;
232      	    break;
233	}
234    }
235
236    UNLOCK();
237
238    return( ok );
239}
240
241bool IORangeAllocator::allocateRange( IORangeScalar data,
242					 IORangeScalar size )
243{
244    IORangeScalar	thisStart, thisEnd;
245    IORangeScalar	dataEnd;
246    UInt32		index;
247    bool		found = false;
248
249    if( !size)
250	return( 0 );
251
252    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
253    dataEnd = data + size - 1;
254
255    LOCK();
256
257    for( index = 0;
258	 (!found) && (index < numElements);
259	 index++ ) {
260
261	thisStart = elements[index].start;
262	thisEnd = elements[index].end;
263
264	if( thisStart > data)
265	    break;
266	found = (dataEnd <= thisEnd);
267
268        if( found) {
269	    if( data != thisStart) {
270	        if( dataEnd != thisEnd) {
271		    found = allocElement( index + 1 );
272		    if( found) {
273		        elements[index++].end = data - 1;
274		        elements[index].start = dataEnd + 1;
275		        elements[index].end = thisEnd;
276		    }
277	        } else
278	       	    elements[index].end = data - 1;
279	    } else if( dataEnd != thisEnd)
280      	        elements[index].start = dataEnd + 1;
281	    else
282	        deallocElement( index );
283        }
284    }
285
286    UNLOCK();
287
288    return( found );
289}
290
291void IORangeAllocator::deallocate( IORangeScalar data,
292				   IORangeScalar size )
293{
294    IORangeScalar	dataEnd;
295    UInt32		index;
296    bool		headContig = false;
297    bool		tailContig = false;
298
299    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
300    dataEnd = data + size - 1;
301
302    LOCK();
303
304    for( index = 0; index < numElements; index++ ) {
305	if( elements[index].start < data) {
306	    headContig = (data <= (elements[index].end + 1));
307	    continue;
308	}
309	tailContig = ((data + size) >= elements[index].start);
310	break;
311    }
312
313    if( headContig) {
314        if( tailContig) {
315            elements[index-1].end = elements[index].end;
316	    deallocElement( index );
317	} else /*safe*/ if( dataEnd > elements[index-1].end)
318	    elements[index-1].end = dataEnd;
319
320    } else if( tailContig) {
321	if( data < elements[index].start) /*safe*/
322	    elements[index].start = data;
323
324    } else if( allocElement( index)) {
325	elements[index].start = data;
326	elements[index].end = dataEnd;
327    }
328
329    UNLOCK();
330}
331
332bool IORangeAllocator::serialize(OSSerialize *s) const
333{
334    OSArray *	array = OSArray::withCapacity( numElements * 2 );
335    OSNumber *	num;
336    UInt32	index;
337    bool	ret;
338
339    if( !array)
340	return( false );
341
342    LOCK();
343
344    for( index = 0; index < numElements; index++) {
345	if( (num = OSNumber::withNumber( elements[index].start,
346					8 * sizeof(IORangeScalar) ))) {
347	    array->setObject(num);
348	    num->release();
349	}
350	if( (num = OSNumber::withNumber( elements[index].end,
351					8 * sizeof(IORangeScalar) ))) {
352	    array->setObject(num);
353	    num->release();
354	}
355    }
356
357    UNLOCK();
358
359    ret = array->serialize(s);
360    array->release();
361
362    return( ret );
363}
364
365IORangeScalar IORangeAllocator::getFreeCount( void )
366{
367    UInt32		index;
368    IORangeScalar	sum = 0;
369
370    for( index = 0; index < numElements; index++)
371	sum += elements[index].end - elements[index].start + 1;
372
373    return( sum );
374}
375
376