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 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
  94 IORangeAllocator * 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
 112 void IORangeAllocator::free()
 113 {
 114     if( elements)
 115         IODelete( elements, IORangeAllocatorElement, capacity );
 116
 117     super::free();
 118 }
 119
 120 UInt32 IORangeAllocator::getFragmentCount( void )
 121 {
 122     return( numElements );
 123 }
 124
 125 UInt32 IORangeAllocator::getFragmentCapacity( void )
 126 {
 127     return( capacity );
 128 }
 129
 130 void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
 131 {
 132     capacityIncrement = count;
 133 }
 134
 135
 136 // allocate element at index
 137 bool 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
 176 void IORangeAllocator::deallocElement( UInt32 index )
 177 {
 178     numElements--;
 179     bcopy( elements + index + 1,
 180            elements + index,
 181            (numElements - index) * sizeof( IORangeAllocatorElement));
 182 }
 183
 184 bool 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
 241 bool 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
 291 void 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
 332 bool 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
 365 IORangeScalar 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