iokit/Kernel/IORangeAllocator.cpp

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