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 57IOLock * gIORangeAllocatorLock; 58 59#define LOCK() \ 60 if( options & kLocking) IOTakeLock( gIORangeAllocatorLock ) 61#define UNLOCK() \ 62 if( options & kLocking) IOUnlock( gIORangeAllocatorLock ) 63 64/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 65 66bool 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 94IORangeAllocator * 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 112void IORangeAllocator::free() 113{ 114 if( elements) 115 IODelete( elements, IORangeAllocatorElement, capacity ); 116 117 super::free(); 118} 119 120UInt32 IORangeAllocator::getFragmentCount( void ) 121{ 122 return( numElements ); 123} 124 125UInt32 IORangeAllocator::getFragmentCapacity( void ) 126{ 127 return( capacity ); 128} 129 130void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count ) 131{ 132 capacityIncrement = count; 133} 134 135 136// allocate element at index 137bool IORangeAllocator::allocElement( UInt32 index ) 138{ 139 UInt32 newCapacity; 140 IORangeAllocatorElement * newElements; 141 142 if( ((numElements == capacity) && capacityIncrement) 143 || (!elements)) { 144 145 newCapacity = capacity + capacityIncrement; 146 newElements = IONew( IORangeAllocatorElement, newCapacity ); 147 if( !newElements) 148 return( false ); 149 150 if( elements) { 151 bcopy( elements, 152 newElements, 153 index * sizeof( IORangeAllocatorElement)); 154 bcopy( elements + index, 155 newElements + index + 1, 156 (numElements - index) * sizeof( IORangeAllocatorElement)); 157 158 IODelete( elements, IORangeAllocatorElement, capacity ); 159 } 160 161 elements = newElements; 162 capacity = newCapacity; 163 164 } else { 165 166 bcopy( elements + index, 167 elements + index + 1, 168 (numElements - index) * sizeof( IORangeAllocatorElement)); 169 } 170 numElements++; 171 172 return( true ); 173} 174 175// destroy element at index 176void IORangeAllocator::deallocElement( UInt32 index ) 177{ 178 numElements--; 179 bcopy( elements + index + 1, 180 elements + index, 181 (numElements - index) * sizeof( IORangeAllocatorElement)); 182} 183 184bool IORangeAllocator::allocate( IORangeScalar size, 185 IORangeScalar * result, 186 IORangeScalar alignment ) 187{ 188 IORangeScalar data, dataEnd; 189 IORangeScalar thisStart, thisEnd; 190 UInt32 index; 191 bool ok = false; 192 193 if( !size || !result) 194 return( false ); 195 196 if( 0 == alignment) 197 alignment = defaultAlignmentMask; 198 else 199 alignment--; 200 201 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask; 202 203 LOCK(); 204 205 for( index = 0; index < numElements; index++ ) { 206 207 thisStart = elements[index].start; 208 thisEnd = elements[index].end; 209 data = (thisStart + alignment) & ~alignment; 210 dataEnd = (data + size - 1); 211 212 ok = (dataEnd <= thisEnd); 213 if( ok) { 214 if( data != thisStart) { 215 if( dataEnd != thisEnd) { 216 if( allocElement( index + 1 )) { 217 elements[index++].end = data - 1; 218 elements[index].start = dataEnd + 1; 219 elements[index].end = thisEnd; 220 } else 221 ok = false; 222 } else 223 elements[index].end = data - 1; 224 } else { 225 if( dataEnd != thisEnd) 226 elements[index].start = dataEnd + 1; 227 else 228 deallocElement( index ); 229 } 230 if( ok) 231 *result = data; 232 break; 233 } 234 } 235 236 UNLOCK(); 237 238 return( ok ); 239} 240 241bool IORangeAllocator::allocateRange( IORangeScalar data, 242 IORangeScalar size ) 243{ 244 IORangeScalar thisStart, thisEnd; 245 IORangeScalar dataEnd; 246 UInt32 index; 247 bool found = false; 248 249 if( !size) 250 return( 0 ); 251 252 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask; 253 dataEnd = data + size - 1; 254 255 LOCK(); 256 257 for( index = 0; 258 (!found) && (index < numElements); 259 index++ ) { 260 261 thisStart = elements[index].start; 262 thisEnd = elements[index].end; 263 264 if( thisStart > data) 265 break; 266 found = (dataEnd <= thisEnd); 267 268 if( found) { 269 if( data != thisStart) { 270 if( dataEnd != thisEnd) { 271 found = allocElement( index + 1 ); 272 if( found) { 273 elements[index++].end = data - 1; 274 elements[index].start = dataEnd + 1; 275 elements[index].end = thisEnd; 276 } 277 } else 278 elements[index].end = data - 1; 279 } else if( dataEnd != thisEnd) 280 elements[index].start = dataEnd + 1; 281 else 282 deallocElement( index ); 283 } 284 } 285 286 UNLOCK(); 287 288 return( found ); 289} 290 291void IORangeAllocator::deallocate( IORangeScalar data, 292 IORangeScalar size ) 293{ 294 IORangeScalar dataEnd; 295 UInt32 index; 296 bool headContig = false; 297 bool tailContig = false; 298 299 size = (size + defaultAlignmentMask) & ~defaultAlignmentMask; 300 dataEnd = data + size - 1; 301 302 LOCK(); 303 304 for( index = 0; index < numElements; index++ ) { 305 if( elements[index].start < data) { 306 headContig = (data <= (elements[index].end + 1)); 307 continue; 308 } 309 tailContig = ((data + size) >= elements[index].start); 310 break; 311 } 312 313 if( headContig) { 314 if( tailContig) { 315 elements[index-1].end = elements[index].end; 316 deallocElement( index ); 317 } else /*safe*/ if( dataEnd > elements[index-1].end) 318 elements[index-1].end = dataEnd; 319 320 } else if( tailContig) { 321 if( data < elements[index].start) /*safe*/ 322 elements[index].start = data; 323 324 } else if( allocElement( index)) { 325 elements[index].start = data; 326 elements[index].end = dataEnd; 327 } 328 329 UNLOCK(); 330} 331 332bool IORangeAllocator::serialize(OSSerialize *s) const 333{ 334 OSArray * array = OSArray::withCapacity( numElements * 2 ); 335 OSNumber * num; 336 UInt32 index; 337 bool ret; 338 339 if( !array) 340 return( false ); 341 342 LOCK(); 343 344 for( index = 0; index < numElements; index++) { 345 if( (num = OSNumber::withNumber( elements[index].start, 346 8 * sizeof(IORangeScalar) ))) { 347 array->setObject(num); 348 num->release(); 349 } 350 if( (num = OSNumber::withNumber( elements[index].end, 351 8 * sizeof(IORangeScalar) ))) { 352 array->setObject(num); 353 num->release(); 354 } 355 } 356 357 UNLOCK(); 358 359 ret = array->serialize(s); 360 array->release(); 361 362 return( ret ); 363} 364 365IORangeScalar IORangeAllocator::getFreeCount( void ) 366{ 367 UInt32 index; 368 IORangeScalar sum = 0; 369 370 for( index = 0; index < numElements; index++) 371 sum += elements[index].end - elements[index].start + 1; 372 373 return( sum ); 374} 375 376