iokit/Kernel/IORangeAllocator.cpp

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