iokit/Kernel/IORangeAllocator.cpp

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