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 LCK_GRP_DECLARE(range_allocator_grp, "range_allocator_grp");
58 LCK_MTX_DECLARE(gIORangeAllocatorLock, &range_allocator_grp);
59
60 #define LOCK() \
61 if( options & kLocking) lck_mtx_lock( &gIORangeAllocatorLock )
62 #define UNLOCK() \
63 if( options & kLocking) lck_mtx_unlock( &gIORangeAllocatorLock )
64
65 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
66
67 bool
init(IORangeScalar endOfRange,IORangeScalar _defaultAlignment,UInt32 _capacity,IOOptionBits _options)68 IORangeAllocator::init( IORangeScalar endOfRange,
69 IORangeScalar _defaultAlignment,
70 UInt32 _capacity,
71 IOOptionBits _options )
72 {
73 if (!super::init()) {
74 return false;
75 }
76
77 if (!_capacity) {
78 _capacity = 1;
79 }
80 if (!_defaultAlignment) {
81 _defaultAlignment = 1;
82 }
83 capacity = 0;
84 capacityIncrement = _capacity;
85 numElements = 0;
86 elements = NULL;
87 defaultAlignmentMask = _defaultAlignment - 1;
88 options = _options;
89
90 if (endOfRange) {
91 deallocate( 0, endOfRange + 1 );
92 }
93
94 return true;
95 }
96
97 IORangeAllocator *
withRange(IORangeScalar endOfRange,IORangeScalar defaultAlignment,UInt32 capacity,IOOptionBits options)98 IORangeAllocator::withRange(
99 IORangeScalar endOfRange,
100 IORangeScalar defaultAlignment,
101 UInt32 capacity,
102 IOOptionBits options )
103 {
104 IORangeAllocator * thingy;
105
106 thingy = new IORangeAllocator;
107 if (thingy && !thingy->init( endOfRange, defaultAlignment,
108 capacity, options )) {
109 thingy->release();
110 thingy = NULL;
111 }
112
113 return thingy;
114 }
115
116 void
free()117 IORangeAllocator::free()
118 {
119 if (elements) {
120 IODeleteData( elements, IORangeAllocatorElement, capacity );
121 }
122
123 super::free();
124 }
125
126 UInt32
getFragmentCount(void)127 IORangeAllocator::getFragmentCount( void )
128 {
129 return numElements;
130 }
131
132 UInt32
getFragmentCapacity(void)133 IORangeAllocator::getFragmentCapacity( void )
134 {
135 return capacity;
136 }
137
138 void
setFragmentCapacityIncrement(UInt32 count)139 IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
140 {
141 capacityIncrement = count;
142 }
143
144
145 // allocate element at index
146 bool
allocElement(UInt32 index)147 IORangeAllocator::allocElement( UInt32 index )
148 {
149 UInt32 newCapacity;
150 IORangeAllocatorElement * newElements;
151
152 if (((numElements == capacity) && capacityIncrement)
153 || (!elements)) {
154 if (os_add_overflow(capacity, capacityIncrement, &newCapacity)) {
155 return false;
156 }
157 newElements = IONewData( IORangeAllocatorElement, newCapacity );
158 if (!newElements) {
159 return false;
160 }
161
162 if (elements) {
163 bcopy( elements,
164 newElements,
165 index * sizeof(IORangeAllocatorElement));
166 bcopy( elements + index,
167 newElements + index + 1,
168 (numElements - index) * sizeof(IORangeAllocatorElement));
169
170 IODeleteData( elements, IORangeAllocatorElement, capacity );
171 }
172
173 elements = newElements;
174 capacity = newCapacity;
175 } else {
176 bcopy( elements + index,
177 elements + index + 1,
178 (numElements - index) * sizeof(IORangeAllocatorElement));
179 }
180 numElements++;
181
182 return true;
183 }
184
185 // destroy element at index
186 void
deallocElement(UInt32 index)187 IORangeAllocator::deallocElement( UInt32 index )
188 {
189 numElements--;
190 bcopy( elements + index + 1,
191 elements + index,
192 (numElements - index) * sizeof(IORangeAllocatorElement));
193 }
194
195 bool
allocate(IORangeScalar size,IORangeScalar * result,IORangeScalar alignment)196 IORangeAllocator::allocate( IORangeScalar size,
197 IORangeScalar * result,
198 IORangeScalar alignment )
199 {
200 IORangeScalar data, dataEnd;
201 IORangeScalar thisStart, thisEnd;
202 UInt32 index;
203 bool ok = false;
204
205 if (!size || !result) {
206 return false;
207 }
208
209 if (0 == alignment) {
210 alignment = defaultAlignmentMask;
211 } else {
212 alignment--;
213 }
214
215 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
216
217 LOCK();
218
219 for (index = 0; index < numElements; index++) {
220 thisStart = elements[index].start;
221 thisEnd = elements[index].end;
222 data = (thisStart + alignment) & ~alignment;
223 dataEnd = (data + size - 1);
224
225 ok = (dataEnd <= thisEnd);
226 if (ok) {
227 if (data != thisStart) {
228 if (dataEnd != thisEnd) {
229 if (allocElement( index + 1 )) {
230 elements[index++].end = data - 1;
231 elements[index].start = dataEnd + 1;
232 elements[index].end = thisEnd;
233 } else {
234 ok = false;
235 }
236 } else {
237 elements[index].end = data - 1;
238 }
239 } else {
240 if (dataEnd != thisEnd) {
241 elements[index].start = dataEnd + 1;
242 } else {
243 deallocElement( index );
244 }
245 }
246 if (ok) {
247 *result = data;
248 }
249 break;
250 }
251 }
252
253 UNLOCK();
254
255 return ok;
256 }
257
258 bool
allocateRange(IORangeScalar data,IORangeScalar size)259 IORangeAllocator::allocateRange( IORangeScalar data,
260 IORangeScalar size )
261 {
262 IORangeScalar thisStart, thisEnd;
263 IORangeScalar dataEnd;
264 UInt32 index;
265 bool found = false;
266
267 if (!size) {
268 return 0;
269 }
270
271 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
272 dataEnd = data + size - 1;
273
274 LOCK();
275
276 for (index = 0;
277 (!found) && (index < numElements);
278 index++) {
279 thisStart = elements[index].start;
280 thisEnd = elements[index].end;
281
282 if (thisStart > data) {
283 break;
284 }
285 found = (dataEnd <= thisEnd);
286
287 if (found) {
288 if (data != thisStart) {
289 if (dataEnd != thisEnd) {
290 found = allocElement( index + 1 );
291 if (found) {
292 elements[index++].end = data - 1;
293 elements[index].start = dataEnd + 1;
294 elements[index].end = thisEnd;
295 }
296 } else {
297 elements[index].end = data - 1;
298 }
299 } else if (dataEnd != thisEnd) {
300 elements[index].start = dataEnd + 1;
301 } else {
302 deallocElement( index );
303 }
304 }
305 }
306
307 UNLOCK();
308
309 return found;
310 }
311
312 void
deallocate(IORangeScalar data,IORangeScalar size)313 IORangeAllocator::deallocate( IORangeScalar data,
314 IORangeScalar size )
315 {
316 IORangeScalar dataEnd;
317 UInt32 index;
318 bool headContig = false;
319 bool tailContig = false;
320
321 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
322 dataEnd = data + size - 1;
323
324 LOCK();
325
326 for (index = 0; index < numElements; index++) {
327 if (elements[index].start < data) {
328 headContig = (data <= (elements[index].end + 1));
329 continue;
330 }
331 tailContig = ((data + size) >= elements[index].start);
332 break;
333 }
334
335 if (headContig) {
336 if (tailContig) {
337 elements[index - 1].end = elements[index].end;
338 deallocElement( index );
339 } else /*safe*/ if (dataEnd > elements[index - 1].end) {
340 elements[index - 1].end = dataEnd;
341 }
342 } else if (tailContig) {
343 if (data < elements[index].start) { /*safe*/
344 elements[index].start = data;
345 }
346 } else if (allocElement( index)) {
347 elements[index].start = data;
348 elements[index].end = dataEnd;
349 }
350
351 UNLOCK();
352 }
353
354 bool
serialize(OSSerialize * s) const355 IORangeAllocator::serialize(OSSerialize *s) const
356 {
357 OSArray * array = OSArray::withCapacity( numElements * 2 );
358 OSNumber * num;
359 UInt32 index;
360 bool ret;
361
362 if (!array) {
363 return false;
364 }
365
366 LOCK();
367
368 for (index = 0; index < numElements; index++) {
369 if ((num = OSNumber::withNumber( elements[index].start,
370 8 * sizeof(IORangeScalar)))) {
371 array->setObject(num);
372 num->release();
373 }
374 if ((num = OSNumber::withNumber( elements[index].end,
375 8 * sizeof(IORangeScalar)))) {
376 array->setObject(num);
377 num->release();
378 }
379 }
380
381 UNLOCK();
382
383 ret = array->serialize(s);
384 array->release();
385
386 return ret;
387 }
388
389 IORangeScalar
getFreeCount(void)390 IORangeAllocator::getFreeCount( void )
391 {
392 UInt32 index;
393 IORangeScalar sum = 0;
394
395 for (index = 0; index < numElements; index++) {
396 sum += elements[index].end - elements[index].start + 1;
397 }
398
399 return sum;
400 }
401