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 |
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( start: 0, size: endOfRange + 1 ); |
92 | } |
93 | |
94 | return true; |
95 | } |
96 | |
97 | IORangeAllocator * |
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: defaultAlignment, |
108 | capacity: capacity, options: options )) { |
109 | thingy->release(); |
110 | thingy = NULL; |
111 | } |
112 | |
113 | return thingy; |
114 | } |
115 | |
116 | void |
117 | IORangeAllocator::free() |
118 | { |
119 | if (elements) { |
120 | IODeleteData( elements, IORangeAllocatorElement, capacity ); |
121 | } |
122 | |
123 | super::free(); |
124 | } |
125 | |
126 | UInt32 |
127 | IORangeAllocator::getFragmentCount( void ) |
128 | { |
129 | return numElements; |
130 | } |
131 | |
132 | UInt32 |
133 | IORangeAllocator::getFragmentCapacity( void ) |
134 | { |
135 | return capacity; |
136 | } |
137 | |
138 | void |
139 | IORangeAllocator::setFragmentCapacityIncrement( UInt32 count ) |
140 | { |
141 | capacityIncrement = count; |
142 | } |
143 | |
144 | |
145 | // allocate element at index |
146 | bool |
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( 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 |
186 | void |
187 | IORangeAllocator::deallocElement( UInt32 index ) |
188 | { |
189 | numElements--; |
190 | bcopy( src: elements + index + 1, |
191 | dst: elements + index, |
192 | n: (numElements - index) * sizeof(IORangeAllocatorElement)); |
193 | } |
194 | |
195 | bool |
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: 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 |
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: 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 |
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 |
355 | IORangeAllocator::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 | |
389 | IORangeScalar |
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 | |