![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to IORangeAllocator.cpp CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / iokit / Kernel|
Return to IORangeAllocator.cpp CVS log | Up to [Apple XNU] / XNU / iokit / Kernel |
1.1 root 1: /*
2: * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * Copyright (c) 1999 Apple Computer, Inc.
24: *
25: *
26: * HISTORY
27: *
28: * sdouglas 05 Nov 99 - created.
29: */
30:
31: #include <libkern/c++/OSArray.h>
32: #include <libkern/c++/OSNumber.h>
33: #include <IOKit/IORangeAllocator.h>
34: #include <IOKit/IOLib.h>
35: #include <IOKit/IOLocks.h>
36: #include <IOKit/assert.h>
37:
38: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
39:
40: #undef super
41: #define super OSObject
42:
43: OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
44:
45: struct IORangeAllocatorElement {
46: // closed range
47: IORangeScalar start;
48: IORangeScalar end;
49: };
50:
51: IOLock * gIORangeAllocatorLock;
52:
53: #define LOCK() \
54: if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )
55: #define UNLOCK() \
56: if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
57:
58: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
59:
60: bool IORangeAllocator::init( IORangeScalar endOfRange,
61: IORangeScalar _defaultAlignment,
62: UInt32 _capacity,
63: IOOptionBits _options )
64: {
65: if( !super::init())
66: return( false );
67:
68: if( !_capacity)
69: _capacity = 1;
70: if( !_defaultAlignment)
71: _defaultAlignment = 1;
72: capacity = 0;
73: capacityIncrement = _capacity;
74: numElements = 0;
75: elements = 0;
76: defaultAlignmentMask = _defaultAlignment - 1;
77: options = _options;
78:
79: if( (!gIORangeAllocatorLock) && (options & kLocking))
80: gIORangeAllocatorLock = IOLockAlloc();
81:
82: if( endOfRange)
83: deallocate( 0, endOfRange + 1 );
84:
85: return( true );
86: }
87:
88: IORangeAllocator * IORangeAllocator:: withRange(
89: IORangeScalar endOfRange,
90: IORangeScalar defaultAlignment = 0,
91: UInt32 capacity = 0,
92: IOOptionBits options = 0 )
93: {
94: IORangeAllocator * thingy;
95:
96: thingy = new IORangeAllocator;
97: if( thingy && ! thingy->init( endOfRange, defaultAlignment,
98: capacity, options )) {
99: thingy->release();
100: thingy = 0;
101: }
102:
103: return( thingy );
104: }
105:
106: void IORangeAllocator::free()
107: {
108: if( elements)
109: IODelete( elements, IORangeAllocatorElement, capacity );
110:
111: super::free();
112: }
113:
114: UInt32 IORangeAllocator::getFragmentCount( void )
115: {
116: return( numElements );
117: }
118:
119: UInt32 IORangeAllocator::getFragmentCapacity( void )
120: {
121: return( capacity );
122: }
123:
124: void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
125: {
126: capacityIncrement = count;
127: }
128:
129:
130: // allocate element at index
131: bool IORangeAllocator::allocElement( UInt32 index )
132: {
133: UInt32 newCapacity;
134: IORangeAllocatorElement * newElements;
135:
136: if( ((numElements == capacity) && capacityIncrement)
137: || (!elements)) {
138:
139: newCapacity = capacity + capacityIncrement;
140: newElements = IONew( IORangeAllocatorElement, newCapacity );
141: if( !newElements)
142: return( false );
143:
144: if( elements) {
145: bcopy( elements,
146: newElements,
147: index * sizeof( IORangeAllocatorElement));
148: bcopy( elements + index,
149: newElements + index + 1,
150: (numElements - index) * sizeof( IORangeAllocatorElement));
151:
152: IODelete( elements, IORangeAllocatorElement, capacity );
153: }
154:
155: elements = newElements;
156: capacity = newCapacity;
157:
158: } else {
159:
160: bcopy( elements + index,
161: elements + index + 1,
162: (numElements - index) * sizeof( IORangeAllocatorElement));
163: }
164: numElements++;
165:
166: return( true );
167: }
168:
169: // destroy element at index
170: void IORangeAllocator::deallocElement( UInt32 index )
171: {
172: numElements--;
173: bcopy( elements + index + 1,
174: elements + index,
175: (numElements - index) * sizeof( IORangeAllocatorElement));
176: }
177:
178: bool IORangeAllocator::allocate( IORangeScalar size,
179: IORangeScalar * result,
180: IORangeScalar alignment = 0 )
181: {
182: IORangeScalar data, dataEnd;
183: IORangeScalar thisStart, thisEnd;
184: UInt32 index;
185: bool ok = false;
186:
187: if( !size || !result)
188: return( false );
189:
190: if( 0 == alignment)
191: alignment = defaultAlignmentMask;
192: else
193: alignment--;
194:
195: size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
196:
197: LOCK();
198:
199: for( index = 0; index < numElements; index++ ) {
200:
201: thisStart = elements[index].start;
202: thisEnd = elements[index].end;
203: data = (thisStart + alignment) & ~alignment;
204: dataEnd = (data + size - 1);
205:
206: ok = (dataEnd <= thisEnd);
207: if( ok) {
208: if( data != thisStart) {
209: if( dataEnd != thisEnd) {
210: if( allocElement( index + 1 )) {
211: elements[index++].end = data - 1;
212: elements[index].start = dataEnd + 1;
213: elements[index].end = thisEnd;
214: } else
215: ok = false;
216: } else
217: elements[index].end = data - 1;
218: } else {
219: if( dataEnd != thisEnd)
220: elements[index].start = dataEnd + 1;
221: else
222: deallocElement( index );
223: }
224: if( ok)
225: *result = data;
226: break;
227: }
228: }
229:
230: UNLOCK();
231:
232: return( ok );
233: }
234:
235: bool IORangeAllocator::allocateRange( IORangeScalar data,
236: IORangeScalar size )
237: {
238: IORangeScalar thisStart, thisEnd;
239: IORangeScalar dataEnd;
240: UInt32 index;
241: bool found = false;
242:
243: if( !size)
244: return( 0 );
245:
246: size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
247: dataEnd = data + size - 1;
248:
249: LOCK();
250:
251: for( index = 0;
252: (!found) && (index < numElements);
253: index++ ) {
254:
255: thisStart = elements[index].start;
256: thisEnd = elements[index].end;
257:
258: if( thisStart > data)
259: break;
260: found = (dataEnd <= thisEnd);
261:
262: if( found) {
263: if( data != thisStart) {
264: if( dataEnd != thisEnd) {
265: found = allocElement( index + 1 );
266: if( found) {
267: elements[index++].end = data - 1;
268: elements[index].start = dataEnd + 1;
269: elements[index].end = thisEnd;
270: }
271: } else
272: elements[index].end = data - 1;
273: } else if( dataEnd != thisEnd)
274: elements[index].start = dataEnd + 1;
275: else
276: deallocElement( index );
277: }
278: }
279:
280: UNLOCK();
281:
282: return( found );
283: }
284:
285: void IORangeAllocator::deallocate( IORangeScalar data,
286: IORangeScalar size )
287: {
288: IORangeScalar dataEnd;
289: UInt32 index;
290: bool headContig = false;
291: bool tailContig = false;
292:
293: size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
294: dataEnd = data + size - 1;
295:
296: LOCK();
297:
298: for( index = 0; index < numElements; index++ ) {
299: if( elements[index].start < data) {
300: headContig = (data <= (elements[index].end + 1));
301: continue;
302: }
303: tailContig = ((data + size) >= elements[index].start);
304: break;
305: }
306:
307: if( headContig) {
308: if( tailContig) {
309: elements[index-1].end = elements[index].end;
310: deallocElement( index );
311: } else /*safe*/ if( dataEnd > elements[index-1].end)
312: elements[index-1].end = dataEnd;
313:
314: } else if( tailContig) {
315: if( data < elements[index].start) /*safe*/
316: elements[index].start = data;
317:
318: } else if( allocElement( index)) {
319: elements[index].start = data;
320: elements[index].end = dataEnd;
321: }
322:
323: UNLOCK();
324: }
325:
326: bool IORangeAllocator::serialize(OSSerialize *s) const
327: {
328: OSArray * array = OSArray::withCapacity( numElements * 2 );
329: OSNumber * num;
330: UInt32 index;
331: bool ret;
332:
333: if( !array)
334: return( false );
335:
336: LOCK();
337:
338: for( index = 0; index < numElements; index++) {
339: if( (num = OSNumber::withNumber( elements[index].start,
340: 8 * sizeof(IORangeScalar) ))) {
341: array->setObject(num);
342: num->release();
343: }
344: if( (num = OSNumber::withNumber( elements[index].end,
345: 8 * sizeof(IORangeScalar) ))) {
346: array->setObject(num);
347: num->release();
348: }
349: }
350:
351: UNLOCK();
352:
353: ret = array->serialize(s);
354: array->release();
355:
356: return( ret );
357: }
358:
359: IORangeScalar IORangeAllocator::getFreeCount( void )
360: {
361: UInt32 index;
362: IORangeScalar sum = 0;
363:
364: for( index = 0; index < numElements; index++)
365: sum += elements[index].end - elements[index].start + 1;
366:
367: return( sum );
368: }
369:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.