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 
49 OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
50 
51 struct IORangeAllocatorElement {
52     // closed range
53     IORangeScalar	start;
54     IORangeScalar	end;
55 };
56 
57 IOLock *	gIORangeAllocatorLock;
58 
59 #define LOCK()		\
60 	if( options & kLocking)	IOTakeLock( gIORangeAllocatorLock )
61 #define UNLOCK()	\
62 	if( options & kLocking)	IOUnlock( gIORangeAllocatorLock )
63 
64 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
65 
66 bool 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 
94 IORangeAllocator * 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 
112 void IORangeAllocator::free()
113 {
114     if( elements)
115 	IODelete( elements, IORangeAllocatorElement, capacity );
116 
117     super::free();
118 }
119 
120 UInt32 IORangeAllocator::getFragmentCount( void )
121 {
122     return( numElements );
123 }
124 
125 UInt32 IORangeAllocator::getFragmentCapacity( void )
126 {
127     return( capacity );
128 }
129 
130 void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
131 {
132     capacityIncrement = count;
133 }
134 
135 
136 // allocate element at index
137 bool 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
176 void IORangeAllocator::deallocElement( UInt32 index )
177 {
178     numElements--;
179     bcopy( elements + index + 1,
180 	   elements + index,
181 	   (numElements - index) * sizeof( IORangeAllocatorElement));
182 }
183 
184 bool 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 
241 bool 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 
291 void 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 
332 bool 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 
365 IORangeScalar 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