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