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 | 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 |
177 | void IORangeAllocator::deallocElement( UInt32 index ) |
178 | { |
179 | numElements--; |
180 | bcopy( elements + index + 1, |
181 | elements + index, |
182 | (numElements - index) * sizeof( IORangeAllocatorElement)); |
183 | } |
184 | |
185 | bool 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 | |
242 | bool 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 | |
292 | void 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 | |
333 | bool 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 | |
366 | IORangeScalar 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 | |