iokit/Kernel/IORangeAllocator.cpp

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