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
57LCK_GRP_DECLARE(range_allocator_grp, "range_allocator_grp");
58LCK_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
67bool
68IORangeAllocator::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( start: 0, size: endOfRange + 1 );
92 }
93
94 return true;
95}
96
97IORangeAllocator *
98IORangeAllocator::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: defaultAlignment,
108 capacity: capacity, options: options )) {
109 thingy->release();
110 thingy = NULL;
111 }
112
113 return thingy;
114}
115
116void
117IORangeAllocator::free()
118{
119 if (elements) {
120 IODeleteData( elements, IORangeAllocatorElement, capacity );
121 }
122
123 super::free();
124}
125
126UInt32
127IORangeAllocator::getFragmentCount( void )
128{
129 return numElements;
130}
131
132UInt32
133IORangeAllocator::getFragmentCapacity( void )
134{
135 return capacity;
136}
137
138void
139IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
140{
141 capacityIncrement = count;
142}
143
144
145// allocate element at index
146bool
147IORangeAllocator::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( src: elements,
164 dst: newElements,
165 n: index * sizeof(IORangeAllocatorElement));
166 bcopy( src: elements + index,
167 dst: newElements + index + 1,
168 n: (numElements - index) * sizeof(IORangeAllocatorElement));
169
170 IODeleteData( elements, IORangeAllocatorElement, capacity );
171 }
172
173 elements = newElements;
174 capacity = newCapacity;
175 } else {
176 bcopy( src: elements + index,
177 dst: elements + index + 1,
178 n: (numElements - index) * sizeof(IORangeAllocatorElement));
179 }
180 numElements++;
181
182 return true;
183}
184
185// destroy element at index
186void
187IORangeAllocator::deallocElement( UInt32 index )
188{
189 numElements--;
190 bcopy( src: elements + index + 1,
191 dst: elements + index,
192 n: (numElements - index) * sizeof(IORangeAllocatorElement));
193}
194
195bool
196IORangeAllocator::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: 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
258bool
259IORangeAllocator::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: 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
312void
313IORangeAllocator::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
354bool
355IORangeAllocator::serialize(OSSerialize *s) const
356{
357 OSArray * array = OSArray::withCapacity( capacity: 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( value: elements[index].start,
370 numberOfBits: 8 * sizeof(IORangeScalar)))) {
371 array->setObject(num);
372 num->release();
373 }
374 if ((num = OSNumber::withNumber( value: elements[index].end,
375 numberOfBits: 8 * sizeof(IORangeScalar)))) {
376 array->setObject(num);
377 num->release();
378 }
379 }
380
381 UNLOCK();
382
383 ret = array->serialize(serializer: s);
384 array->release();
385
386 return ret;
387}
388
389IORangeScalar
390IORangeAllocator::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