iokit/Kernel/IOLib.cpp

   1 /*
   2  * Copyright (c) 1998-2006 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  * HISTORY
  30  *
  31  * 17-Apr-91   Portions from libIO.m, Doug Mitchell at NeXT.
  32  * 17-Nov-98   cpp
  33  *
  34  */
  35
  36 #include <IOKit/system.h>
  37 #include <mach/sync_policy.h>
  38 #include <machine/machine_routines.h>
  39 #include <vm/vm_kern.h>
  40 #include <libkern/c++/OSCPPDebug.h>
  41
  42 #include <IOKit/assert.h>
  43
  44 #include <IOKit/IOReturn.h>
  45 #include <IOKit/IOLib.h>
  46 #include <IOKit/IOLocks.h>
  47 #include <IOKit/IOMapper.h>
  48 #include <IOKit/IOBufferMemoryDescriptor.h>
  49 #include <IOKit/IOKitDebug.h>
  50
  51 #include "IOKitKernelInternal.h"
  52
  53 #ifdef IOALLOCDEBUG
  54 #include <libkern/OSDebug.h>
  55 #include <sys/sysctl.h>
  56 #endif
  57
  58 #include "libkern/OSAtomic.h"
  59 #include <libkern/c++/OSKext.h>
  60 #include <IOKit/IOStatisticsPrivate.h>
  61 #include <os/log_private.h>
  62 #include <sys/msgbuf.h>
  63 #include <console/serial_protos.h>
  64
  65 #if IOKITSTATS
  66
  67 #define IOStatisticsAlloc(type, size) \
  68 do { \
  69         IOStatistics::countAlloc(type, size); \
  70 } while (0)
  71
  72 #else
  73
  74 #define IOStatisticsAlloc(type, size)
  75
  76 #endif /* IOKITSTATS */
  77
  78
  79 #define TRACK_ALLOC     (IOTRACKING && (kIOTracking & gIOKitDebug))
  80
  81
  82 extern "C"
  83 {
  84 mach_timespec_t IOZeroTvalspec = { 0, 0 };
  85
  86 extern ppnum_t pmap_find_phys(pmap_t pmap, addr64_t va);
  87
  88 extern int
  89 __doprnt(
  90         const char              *fmt,
  91         va_list                 argp,
  92         void                    (*putc)(int, void *),
  93         void                    *arg,
  94         int                     radix,
  95         int                     is_log);
  96
  97 extern void cons_putc_locked(char);
  98 extern bool bsd_log_lock(bool);
  99 extern void bsd_log_unlock(void);
 100
 101
 102 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 103
 104 lck_grp_t       *IOLockGroup;
 105
 106 /*
 107  * Global variables for use by iLogger
 108  * These symbols are for use only by Apple diagnostic code.
 109  * Binary compatibility is not guaranteed for kexts that reference these symbols.
 110  */
 111
 112 void *_giDebugLogInternal       = NULL;
 113 void *_giDebugLogDataInternal   = NULL;
 114 void *_giDebugReserved1         = NULL;
 115 void *_giDebugReserved2         = NULL;
 116
 117 iopa_t gIOBMDPageAllocator;
 118
 119 /*
 120  * Static variables for this module.
 121  */
 122
 123 static queue_head_t gIOMallocContiguousEntries;
 124 static lck_mtx_t *  gIOMallocContiguousEntriesLock;
 125
 126 #if __x86_64__
 127 enum { kIOMaxPageableMaps    = 8 };
 128 enum { kIOPageableMapSize    = 512 * 1024 * 1024 };
 129 enum { kIOPageableMaxMapSize = 512 * 1024 * 1024 };
 130 #else
 131 enum { kIOMaxPageableMaps    = 16 };
 132 enum { kIOPageableMapSize    = 96 * 1024 * 1024 };
 133 enum { kIOPageableMaxMapSize = 96 * 1024 * 1024 };
 134 #endif
 135
 136 typedef struct {
 137         vm_map_t            map;
 138         vm_offset_t address;
 139         vm_offset_t end;
 140 } IOMapData;
 141
 142 static struct {
 143         UInt32      count;
 144         UInt32      hint;
 145         IOMapData   maps[kIOMaxPageableMaps];
 146         lck_mtx_t * lock;
 147 } gIOKitPageableSpace;
 148
 149 static iopa_t gIOPageablePageAllocator;
 150
 151 uint32_t  gIOPageAllocChunkBytes;
 152
 153 #if IOTRACKING
 154 IOTrackingQueue * gIOMallocTracking;
 155 IOTrackingQueue * gIOWireTracking;
 156 IOTrackingQueue * gIOMapTracking;
 157 #endif /* IOTRACKING */
 158
 159 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 160
 161 void
 162 IOLibInit(void)
 163 {
 164         kern_return_t ret;
 165
 166         static bool libInitialized;
 167
 168         if (libInitialized) {
 169                 return;
 170         }
 171
 172         IOLockGroup = lck_grp_alloc_init("IOKit", LCK_GRP_ATTR_NULL);
 173
 174 #if IOTRACKING
 175         IOTrackingInit();
 176         gIOMallocTracking = IOTrackingQueueAlloc(kIOMallocTrackingName, 0, 0, 0,
 177             kIOTrackingQueueTypeAlloc,
 178             37);
 179         gIOWireTracking   = IOTrackingQueueAlloc(kIOWireTrackingName, 0, 0, page_size, 0, 0);
 180
 181         size_t mapCaptureSize = (kIOTracking & gIOKitDebug) ? page_size : (1024 * 1024);
 182         gIOMapTracking    = IOTrackingQueueAlloc(kIOMapTrackingName, 0, 0, mapCaptureSize,
 183             kIOTrackingQueueTypeDefaultOn
 184             | kIOTrackingQueueTypeMap
 185             | kIOTrackingQueueTypeUser,
 186             0);
 187 #endif
 188
 189         gIOKitPageableSpace.maps[0].address = 0;
 190         ret = kmem_suballoc(kernel_map,
 191             &gIOKitPageableSpace.maps[0].address,
 192             kIOPageableMapSize,
 193             TRUE,
 194             VM_FLAGS_ANYWHERE,
 195             VM_MAP_KERNEL_FLAGS_NONE,
 196             VM_KERN_MEMORY_IOKIT,
 197             &gIOKitPageableSpace.maps[0].map);
 198         if (ret != KERN_SUCCESS) {
 199                 panic("failed to allocate iokit pageable map\n");
 200         }
 201
 202         gIOKitPageableSpace.lock            = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
 203         gIOKitPageableSpace.maps[0].end     = gIOKitPageableSpace.maps[0].address + kIOPageableMapSize;
 204         gIOKitPageableSpace.hint            = 0;
 205         gIOKitPageableSpace.count           = 1;
 206
 207         gIOMallocContiguousEntriesLock      = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
 208         queue_init( &gIOMallocContiguousEntries );
 209
 210         gIOPageAllocChunkBytes = PAGE_SIZE / 64;
 211         assert(sizeof(iopa_page_t) <= gIOPageAllocChunkBytes);
 212         iopa_init(&gIOBMDPageAllocator);
 213         iopa_init(&gIOPageablePageAllocator);
 214
 215
 216         libInitialized = true;
 217 }
 218
 219 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 220
 221 static vm_size_t
 222 log2up(vm_size_t size)
 223 {
 224         if (size <= 1) {
 225                 size = 0;
 226         } else {
 227 #if __LP64__
 228                 size = 64 - __builtin_clzl(size - 1);
 229 #else
 230                 size = 32 - __builtin_clzl(size - 1);
 231 #endif
 232         }
 233         return size;
 234 }
 235
 236 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 237
 238 IOThread
 239 IOCreateThread(IOThreadFunc fcn, void *arg)
 240 {
 241         kern_return_t   result;
 242         thread_t                thread;
 243
 244         result = kernel_thread_start((thread_continue_t)fcn, arg, &thread);
 245         if (result != KERN_SUCCESS) {
 246                 return NULL;
 247         }
 248
 249         thread_deallocate(thread);
 250
 251         return thread;
 252 }
 253
 254
 255 void
 256 IOExitThread(void)
 257 {
 258         (void) thread_terminate(current_thread());
 259 }
 260
 261 void *
 262 IOMalloc_external(
 263         vm_size_t size);
 264 void *
 265 IOMalloc_external(
 266         vm_size_t size)
 267 {
 268         return IOMalloc_internal(KHEAP_KEXT, size);
 269 }
 270
 271 void *
 272 IOMallocZero_external(
 273         vm_size_t size);
 274 void *
 275 IOMallocZero_external(
 276         vm_size_t size)
 277 {
 278         return IOMallocZero_internal(KHEAP_KEXT, size);
 279 }
 280
 281 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 282
 283 void *
 284 IOMallocZero_internal(struct kalloc_heap *kalloc_heap_cfg, vm_size_t size)
 285 {
 286         void * result;
 287         result = IOMalloc_internal(kalloc_heap_cfg, size);
 288         if (result) {
 289                 bzero(result, size);
 290         }
 291         return result;
 292 }
 293
 294 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 295
 296 #if IOTRACKING
 297 struct IOLibMallocHeader {
 298         IOTrackingAddress tracking;
 299 };
 300 #endif
 301
 302 #if IOTRACKING
 303 #define sizeofIOLibMallocHeader (sizeof(IOLibMallocHeader) - (TRACK_ALLOC ? 0 : sizeof(IOTrackingAddress)))
 304 #else
 305 #define sizeofIOLibMallocHeader (0)
 306 #endif
 307
 308 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 309
 310 void *
 311 IOMalloc_internal(struct kalloc_heap *kheap, vm_size_t size)
 312 {
 313         void * address;
 314         vm_size_t allocSize;
 315
 316         allocSize = size + sizeofIOLibMallocHeader;
 317 #if IOTRACKING
 318         if (sizeofIOLibMallocHeader && (allocSize <= size)) {
 319                 return NULL;                                          // overflow
 320         }
 321 #endif
 322         address = kheap_alloc_tag_bt(kheap, allocSize, Z_WAITOK, VM_KERN_MEMORY_IOKIT);
 323
 324         if (address) {
 325 #if IOTRACKING
 326                 if (TRACK_ALLOC) {
 327                         IOLibMallocHeader * hdr;
 328                         hdr = (typeof(hdr))address;
 329                         bzero(&hdr->tracking, sizeof(hdr->tracking));
 330                         hdr->tracking.address = ~(((uintptr_t) address) + sizeofIOLibMallocHeader);
 331                         hdr->tracking.size    = size;
 332                         IOTrackingAdd(gIOMallocTracking, &hdr->tracking.tracking, size, true, VM_KERN_MEMORY_NONE);
 333                 }
 334 #endif
 335                 address = (typeof(address))(((uintptr_t) address) + sizeofIOLibMallocHeader);
 336
 337 #if IOALLOCDEBUG
 338                 OSAddAtomicLong(size, &debug_iomalloc_size);
 339 #endif
 340                 IOStatisticsAlloc(kIOStatisticsMalloc, size);
 341         }
 342
 343         return address;
 344 }
 345
 346 void
 347 IOFree(void * inAddress, vm_size_t size)
 348 {
 349         void * address;
 350
 351         if ((address = inAddress)) {
 352                 address = (typeof(address))(((uintptr_t) address) - sizeofIOLibMallocHeader);
 353
 354 #if IOTRACKING
 355                 if (TRACK_ALLOC) {
 356                         IOLibMallocHeader * hdr;
 357                         struct ptr_reference { void * ptr; };
 358                         volatile struct ptr_reference ptr;
 359
 360                         // we're about to block in IOTrackingRemove(), make sure the original pointer
 361                         // exists in memory or a register for leak scanning to find
 362                         ptr.ptr = inAddress;
 363
 364                         hdr = (typeof(hdr))address;
 365                         if (size != hdr->tracking.size) {
 366                                 OSReportWithBacktrace("bad IOFree size 0x%lx should be 0x%lx", size, hdr->tracking.size);
 367                                 size = hdr->tracking.size;
 368                         }
 369                         IOTrackingRemove(gIOMallocTracking, &hdr->tracking.tracking, size);
 370                         ptr.ptr = NULL;
 371                 }
 372 #endif
 373
 374                 kfree(address, size + sizeofIOLibMallocHeader);
 375 #if IOALLOCDEBUG
 376                 OSAddAtomicLong(-size, &debug_iomalloc_size);
 377 #endif
 378                 IOStatisticsAlloc(kIOStatisticsFree, size);
 379         }
 380 }
 381
 382 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 383
 384 vm_tag_t
 385 IOMemoryTag(vm_map_t map)
 386 {
 387         vm_tag_t tag;
 388
 389         if (!vm_kernel_map_is_kernel(map)) {
 390                 return VM_MEMORY_IOKIT;
 391         }
 392
 393         tag = vm_tag_bt();
 394         if (tag == VM_KERN_MEMORY_NONE) {
 395                 tag = VM_KERN_MEMORY_IOKIT;
 396         }
 397
 398         return tag;
 399 }
 400
 401 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 402
 403 struct IOLibPageMallocHeader {
 404         mach_vm_size_t    allocationSize;
 405         mach_vm_address_t allocationAddress;
 406 #if IOTRACKING
 407         IOTrackingAddress tracking;
 408 #endif
 409 };
 410
 411 #if IOTRACKING
 412 #define sizeofIOLibPageMallocHeader     (sizeof(IOLibPageMallocHeader) - (TRACK_ALLOC ? 0 : sizeof(IOTrackingAddress)))
 413 #else
 414 #define sizeofIOLibPageMallocHeader     (sizeof(IOLibPageMallocHeader))
 415 #endif
 416
 417 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 418 void *
 419 IOMallocAligned_external(
 420         vm_size_t size, vm_size_t alignment);
 421 void *
 422 IOMallocAligned_external(
 423         vm_size_t size, vm_size_t alignment)
 424 {
 425         return IOMallocAligned_internal(KHEAP_KEXT, size, alignment);
 426 }
 427
 428 void *
 429 IOMallocAligned_internal(struct kalloc_heap *kheap, vm_size_t size,
 430     vm_size_t alignment)
 431 {
 432         kern_return_t           kr;
 433         vm_offset_t             address;
 434         vm_offset_t             allocationAddress;
 435         vm_size_t               adjustedSize;
 436         uintptr_t               alignMask;
 437         IOLibPageMallocHeader * hdr;
 438
 439         if (size == 0) {
 440                 return NULL;
 441         }
 442         if (((uint32_t) alignment) != alignment) {
 443                 return NULL;
 444         }
 445
 446         alignment = (1UL << log2up((uint32_t) alignment));
 447         alignMask = alignment - 1;
 448         adjustedSize = size + sizeofIOLibPageMallocHeader;
 449
 450         if (size > adjustedSize) {
 451                 address = 0; /* overflow detected */
 452         } else if (adjustedSize >= page_size) {
 453                 kr = kernel_memory_allocate(kernel_map, &address,
 454                     size, alignMask, 0, IOMemoryTag(kernel_map));
 455                 if (KERN_SUCCESS != kr) {
 456                         address = 0;
 457                 }
 458 #if IOTRACKING
 459                 else if (TRACK_ALLOC) {
 460                         IOTrackingAlloc(gIOMallocTracking, address, size);
 461                 }
 462 #endif
 463         } else {
 464                 adjustedSize += alignMask;
 465
 466                 if (adjustedSize >= page_size) {
 467                         kr = kernel_memory_allocate(kernel_map, &allocationAddress,
 468                             adjustedSize, 0, 0, IOMemoryTag(kernel_map));
 469                         if (KERN_SUCCESS != kr) {
 470                                 allocationAddress = 0;
 471                         }
 472                 } else {
 473                         allocationAddress = (vm_address_t) kheap_alloc_tag_bt(kheap,
 474                             adjustedSize, Z_WAITOK, VM_KERN_MEMORY_IOKIT);
 475                 }
 476
 477                 if (allocationAddress) {
 478                         address = (allocationAddress + alignMask + sizeofIOLibPageMallocHeader)
 479                             & (~alignMask);
 480
 481                         hdr = (typeof(hdr))(address - sizeofIOLibPageMallocHeader);
 482                         hdr->allocationSize    = adjustedSize;
 483                         hdr->allocationAddress = allocationAddress;
 484 #if IOTRACKING
 485                         if (TRACK_ALLOC) {
 486                                 bzero(&hdr->tracking, sizeof(hdr->tracking));
 487                                 hdr->tracking.address = ~address;
 488                                 hdr->tracking.size = size;
 489                                 IOTrackingAdd(gIOMallocTracking, &hdr->tracking.tracking, size, true, VM_KERN_MEMORY_NONE);
 490                         }
 491 #endif
 492                 } else {
 493                         address = 0;
 494                 }
 495         }
 496
 497         assert(0 == (address & alignMask));
 498
 499         if (address) {
 500 #if IOALLOCDEBUG
 501                 OSAddAtomicLong(size, &debug_iomalloc_size);
 502 #endif
 503                 IOStatisticsAlloc(kIOStatisticsMallocAligned, size);
 504         }
 505
 506         return (void *) address;
 507 }
 508
 509 void
 510 IOFreeAligned(void * address, vm_size_t size)
 511 {
 512         vm_address_t            allocationAddress;
 513         vm_size_t               adjustedSize;
 514         IOLibPageMallocHeader * hdr;
 515
 516         if (!address) {
 517                 return;
 518         }
 519
 520         assert(size);
 521
 522         adjustedSize = size + sizeofIOLibPageMallocHeader;
 523         if (adjustedSize >= page_size) {
 524 #if IOTRACKING
 525                 if (TRACK_ALLOC) {
 526                         IOTrackingFree(gIOMallocTracking, (uintptr_t) address, size);
 527                 }
 528 #endif
 529                 kmem_free( kernel_map, (vm_offset_t) address, size);
 530         } else {
 531                 hdr = (typeof(hdr))(((uintptr_t)address) - sizeofIOLibPageMallocHeader);
 532                 adjustedSize = hdr->allocationSize;
 533                 allocationAddress = hdr->allocationAddress;
 534
 535 #if IOTRACKING
 536                 if (TRACK_ALLOC) {
 537                         if (size != hdr->tracking.size) {
 538                                 OSReportWithBacktrace("bad IOFreeAligned size 0x%lx should be 0x%lx", size, hdr->tracking.size);
 539                                 size = hdr->tracking.size;
 540                         }
 541                         IOTrackingRemove(gIOMallocTracking, &hdr->tracking.tracking, size);
 542                 }
 543 #endif
 544                 if (adjustedSize >= page_size) {
 545                         kmem_free( kernel_map, allocationAddress, adjustedSize);
 546                 } else {
 547                         kfree(allocationAddress, adjustedSize);
 548                 }
 549         }
 550
 551 #if IOALLOCDEBUG
 552         OSAddAtomicLong(-size, &debug_iomalloc_size);
 553 #endif
 554
 555         IOStatisticsAlloc(kIOStatisticsFreeAligned, size);
 556 }
 557
 558 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 559
 560 void
 561 IOKernelFreePhysical(mach_vm_address_t address, mach_vm_size_t size)
 562 {
 563         vm_address_t       allocationAddress;
 564         vm_size_t          adjustedSize;
 565         IOLibPageMallocHeader * hdr;
 566
 567         if (!address) {
 568                 return;
 569         }
 570
 571         assert(size);
 572
 573         adjustedSize = (2 * size) + sizeofIOLibPageMallocHeader;
 574         if (adjustedSize >= page_size) {
 575 #if IOTRACKING
 576                 if (TRACK_ALLOC) {
 577                         IOTrackingFree(gIOMallocTracking, address, size);
 578                 }
 579 #endif
 580                 kmem_free( kernel_map, (vm_offset_t) address, size);
 581         } else {
 582                 hdr = (typeof(hdr))(((uintptr_t)address) - sizeofIOLibPageMallocHeader);
 583                 adjustedSize = hdr->allocationSize;
 584                 allocationAddress = hdr->allocationAddress;
 585 #if IOTRACKING
 586                 if (TRACK_ALLOC) {
 587                         IOTrackingRemove(gIOMallocTracking, &hdr->tracking.tracking, size);
 588                 }
 589 #endif
 590                 kfree(allocationAddress, adjustedSize);
 591         }
 592
 593         IOStatisticsAlloc(kIOStatisticsFreeContiguous, size);
 594 #if IOALLOCDEBUG
 595         OSAddAtomicLong(-size, &debug_iomalloc_size);
 596 #endif
 597 }
 598
 599 #if __arm__ || __arm64__
 600 extern unsigned long gPhysBase, gPhysSize;
 601 #endif
 602
 603 mach_vm_address_t
 604 IOKernelAllocateWithPhysicalRestrict(mach_vm_size_t size, mach_vm_address_t maxPhys,
 605     mach_vm_size_t alignment, bool contiguous)
 606 {
 607         kern_return_t           kr;
 608         mach_vm_address_t       address;
 609         mach_vm_address_t       allocationAddress;
 610         mach_vm_size_t          adjustedSize;
 611         mach_vm_address_t       alignMask;
 612         IOLibPageMallocHeader * hdr;
 613
 614         if (size == 0) {
 615                 return 0;
 616         }
 617         if (alignment == 0) {
 618                 alignment = 1;
 619         }
 620
 621         alignMask = alignment - 1;
 622
 623         if (os_mul_and_add_overflow(2, size, sizeofIOLibPageMallocHeader, &adjustedSize)) {
 624                 return 0;
 625         }
 626
 627         contiguous = (contiguous && (adjustedSize > page_size))
 628             || (alignment > page_size);
 629
 630         if (contiguous || maxPhys) {
 631                 int options = 0;
 632                 vm_offset_t virt;
 633
 634                 adjustedSize = size;
 635                 contiguous = (contiguous && (adjustedSize > page_size))
 636                     || (alignment > page_size);
 637
 638                 if (!contiguous) {
 639 #if __arm__ || __arm64__
 640                         if (maxPhys >= (mach_vm_address_t)(gPhysBase + gPhysSize)) {
 641                                 maxPhys = 0;
 642                         } else
 643 #endif
 644                         if (maxPhys <= 0xFFFFFFFF) {
 645                                 maxPhys = 0;
 646                                 options |= KMA_LOMEM;
 647                         } else if (gIOLastPage && (atop_64(maxPhys) > gIOLastPage)) {
 648                                 maxPhys = 0;
 649                         }
 650                 }
 651                 if (contiguous || maxPhys) {
 652                         kr = kmem_alloc_contig(kernel_map, &virt, size,
 653                             alignMask, (ppnum_t) atop(maxPhys), (ppnum_t) atop(alignMask), 0, IOMemoryTag(kernel_map));
 654                 } else {
 655                         kr = kernel_memory_allocate(kernel_map, &virt,
 656                             size, alignMask, options, IOMemoryTag(kernel_map));
 657                 }
 658                 if (KERN_SUCCESS == kr) {
 659                         address = virt;
 660 #if IOTRACKING
 661                         if (TRACK_ALLOC) {
 662                                 IOTrackingAlloc(gIOMallocTracking, address, size);
 663                         }
 664 #endif
 665                 } else {
 666                         address = 0;
 667                 }
 668         } else {
 669                 adjustedSize += alignMask;
 670                 if (adjustedSize < size) {
 671                         return 0;
 672                 }
 673                 allocationAddress = (mach_vm_address_t) kheap_alloc_tag_bt(KHEAP_KEXT,
 674                     adjustedSize, Z_WAITOK, VM_KERN_MEMORY_IOKIT);
 675
 676                 if (allocationAddress) {
 677                         address = (allocationAddress + alignMask + sizeofIOLibPageMallocHeader)
 678                             & (~alignMask);
 679
 680                         if (atop_32(address) != atop_32(address + size - 1)) {
 681                                 address = round_page(address);
 682                         }
 683
 684                         hdr = (typeof(hdr))(address - sizeofIOLibPageMallocHeader);
 685                         hdr->allocationSize    = adjustedSize;
 686                         hdr->allocationAddress = allocationAddress;
 687 #if IOTRACKING
 688                         if (TRACK_ALLOC) {
 689                                 bzero(&hdr->tracking, sizeof(hdr->tracking));
 690                                 hdr->tracking.address = ~address;
 691                                 hdr->tracking.size    = size;
 692                                 IOTrackingAdd(gIOMallocTracking, &hdr->tracking.tracking, size, true, VM_KERN_MEMORY_NONE);
 693                         }
 694 #endif
 695                 } else {
 696                         address = 0;
 697                 }
 698         }
 699
 700         if (address) {
 701                 IOStatisticsAlloc(kIOStatisticsMallocContiguous, size);
 702 #if IOALLOCDEBUG
 703                 OSAddAtomicLong(size, &debug_iomalloc_size);
 704 #endif
 705         }
 706
 707         return address;
 708 }
 709
 710
 711 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 712
 713 struct _IOMallocContiguousEntry {
 714         mach_vm_address_t          virtualAddr;
 715         IOBufferMemoryDescriptor * md;
 716         queue_chain_t              link;
 717 };
 718 typedef struct _IOMallocContiguousEntry _IOMallocContiguousEntry;
 719
 720 void *
 721 IOMallocContiguous(vm_size_t size, vm_size_t alignment,
 722     IOPhysicalAddress * physicalAddress)
 723 {
 724         mach_vm_address_t   address = 0;
 725
 726         if (size == 0) {
 727                 return NULL;
 728         }
 729         if (alignment == 0) {
 730                 alignment = 1;
 731         }
 732
 733         /* Do we want a physical address? */
 734         if (!physicalAddress) {
 735                 address = IOKernelAllocateWithPhysicalRestrict(size, 0 /*maxPhys*/, alignment, true);
 736         } else {
 737                 do {
 738                         IOBufferMemoryDescriptor * bmd;
 739                         mach_vm_address_t          physicalMask;
 740                         vm_offset_t                alignMask;
 741
 742                         alignMask = alignment - 1;
 743                         physicalMask = (0xFFFFFFFF ^ alignMask);
 744
 745                         bmd = IOBufferMemoryDescriptor::inTaskWithPhysicalMask(
 746                                 kernel_task, kIOMemoryPhysicallyContiguous, size, physicalMask);
 747                         if (!bmd) {
 748                                 break;
 749                         }
 750
 751                         _IOMallocContiguousEntry *
 752                             entry = IONew(_IOMallocContiguousEntry, 1);
 753                         if (!entry) {
 754                                 bmd->release();
 755                                 break;
 756                         }
 757                         entry->virtualAddr = (mach_vm_address_t) bmd->getBytesNoCopy();
 758                         entry->md          = bmd;
 759                         lck_mtx_lock(gIOMallocContiguousEntriesLock);
 760                         queue_enter( &gIOMallocContiguousEntries, entry,
 761                             _IOMallocContiguousEntry *, link );
 762                         lck_mtx_unlock(gIOMallocContiguousEntriesLock);
 763
 764                         address          = (mach_vm_address_t) entry->virtualAddr;
 765                         *physicalAddress = bmd->getPhysicalAddress();
 766                 }while (false);
 767         }
 768
 769         return (void *) address;
 770 }
 771
 772 void
 773 IOFreeContiguous(void * _address, vm_size_t size)
 774 {
 775         _IOMallocContiguousEntry * entry;
 776         IOMemoryDescriptor *       md = NULL;
 777
 778         mach_vm_address_t address = (mach_vm_address_t) _address;
 779
 780         if (!address) {
 781                 return;
 782         }
 783
 784         assert(size);
 785
 786         lck_mtx_lock(gIOMallocContiguousEntriesLock);
 787         queue_iterate( &gIOMallocContiguousEntries, entry,
 788             _IOMallocContiguousEntry *, link )
 789         {
 790                 if (entry->virtualAddr == address) {
 791                         md   = entry->md;
 792                         queue_remove( &gIOMallocContiguousEntries, entry,
 793                             _IOMallocContiguousEntry *, link );
 794                         break;
 795                 }
 796         }
 797         lck_mtx_unlock(gIOMallocContiguousEntriesLock);
 798
 799         if (md) {
 800                 md->release();
 801                 IODelete(entry, _IOMallocContiguousEntry, 1);
 802         } else {
 803                 IOKernelFreePhysical((mach_vm_address_t) address, size);
 804         }
 805 }
 806
 807 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 808
 809 kern_return_t
 810 IOIteratePageableMaps(vm_size_t size,
 811     IOIteratePageableMapsCallback callback, void * ref)
 812 {
 813         kern_return_t       kr = kIOReturnNotReady;
 814         vm_size_t           segSize;
 815         UInt32              attempts;
 816         UInt32              index;
 817         vm_offset_t         min;
 818         vm_map_t            map;
 819
 820         if (size > kIOPageableMaxMapSize) {
 821                 return kIOReturnBadArgument;
 822         }
 823
 824         do {
 825                 index = gIOKitPageableSpace.hint;
 826                 attempts = gIOKitPageableSpace.count;
 827                 while (attempts--) {
 828                         kr = (*callback)(gIOKitPageableSpace.maps[index].map, ref);
 829                         if (KERN_SUCCESS == kr) {
 830                                 gIOKitPageableSpace.hint = index;
 831                                 break;
 832                         }
 833                         if (index) {
 834                                 index--;
 835                         } else {
 836                                 index = gIOKitPageableSpace.count - 1;
 837                         }
 838                 }
 839                 if (KERN_NO_SPACE != kr) {
 840                         break;
 841                 }
 842
 843                 lck_mtx_lock( gIOKitPageableSpace.lock );
 844
 845                 index = gIOKitPageableSpace.count;
 846                 if (index >= (kIOMaxPageableMaps - 1)) {
 847                         lck_mtx_unlock( gIOKitPageableSpace.lock );
 848                         break;
 849                 }
 850
 851                 if (size < kIOPageableMapSize) {
 852                         segSize = kIOPageableMapSize;
 853                 } else {
 854                         segSize = size;
 855                 }
 856
 857                 min = 0;
 858                 kr = kmem_suballoc(kernel_map,
 859                     &min,
 860                     segSize,
 861                     TRUE,
 862                     VM_FLAGS_ANYWHERE,
 863                     VM_MAP_KERNEL_FLAGS_NONE,
 864                     VM_KERN_MEMORY_IOKIT,
 865                     &map);
 866                 if (KERN_SUCCESS != kr) {
 867                         lck_mtx_unlock( gIOKitPageableSpace.lock );
 868                         break;
 869                 }
 870
 871                 gIOKitPageableSpace.maps[index].map     = map;
 872                 gIOKitPageableSpace.maps[index].address = min;
 873                 gIOKitPageableSpace.maps[index].end     = min + segSize;
 874                 gIOKitPageableSpace.hint                = index;
 875                 gIOKitPageableSpace.count               = index + 1;
 876
 877                 lck_mtx_unlock( gIOKitPageableSpace.lock );
 878         } while (true);
 879
 880         return kr;
 881 }
 882
 883 struct IOMallocPageableRef {
 884         vm_offset_t address;
 885         vm_size_t   size;
 886         vm_tag_t    tag;
 887 };
 888
 889 static kern_return_t
 890 IOMallocPageableCallback(vm_map_t map, void * _ref)
 891 {
 892         struct IOMallocPageableRef * ref = (struct IOMallocPageableRef *) _ref;
 893         kern_return_t                kr;
 894
 895         kr = kmem_alloc_pageable( map, &ref->address, ref->size, ref->tag );
 896
 897         return kr;
 898 }
 899
 900 static void *
 901 IOMallocPageablePages(vm_size_t size, vm_size_t alignment, vm_tag_t tag)
 902 {
 903         kern_return_t              kr = kIOReturnNotReady;
 904         struct IOMallocPageableRef ref;
 905
 906         if (alignment > page_size) {
 907                 return NULL;
 908         }
 909         if (size > kIOPageableMaxMapSize) {
 910                 return NULL;
 911         }
 912
 913         ref.size = size;
 914         ref.tag  = tag;
 915         kr = IOIteratePageableMaps( size, &IOMallocPageableCallback, &ref );
 916         if (kIOReturnSuccess != kr) {
 917                 ref.address = 0;
 918         }
 919
 920         return (void *) ref.address;
 921 }
 922
 923 vm_map_t
 924 IOPageableMapForAddress( uintptr_t address )
 925 {
 926         vm_map_t    map = NULL;
 927         UInt32      index;
 928
 929         for (index = 0; index < gIOKitPageableSpace.count; index++) {
 930                 if ((address >= gIOKitPageableSpace.maps[index].address)
 931                     && (address < gIOKitPageableSpace.maps[index].end)) {
 932                         map = gIOKitPageableSpace.maps[index].map;
 933                         break;
 934                 }
 935         }
 936         if (!map) {
 937                 panic("IOPageableMapForAddress: null");
 938         }
 939
 940         return map;
 941 }
 942
 943 static void
 944 IOFreePageablePages(void * address, vm_size_t size)
 945 {
 946         vm_map_t map;
 947
 948         map = IOPageableMapForAddress((vm_address_t) address);
 949         if (map) {
 950                 kmem_free( map, (vm_offset_t) address, size);
 951         }
 952 }
 953
 954 static uintptr_t
 955 IOMallocOnePageablePage(iopa_t * a)
 956 {
 957         return (uintptr_t) IOMallocPageablePages(page_size, page_size, VM_KERN_MEMORY_IOKIT);
 958 }
 959
 960 static void *
 961 IOMallocPageableInternal(vm_size_t size, vm_size_t alignment, bool zeroed)
 962 {
 963         void * addr;
 964
 965         if (((uint32_t) alignment) != alignment) {
 966                 return NULL;
 967         }
 968         if (size >= (page_size - 4 * gIOPageAllocChunkBytes) ||
 969             alignment > page_size) {
 970                 addr = IOMallocPageablePages(size, alignment, IOMemoryTag(kernel_map));
 971                 /* Memory allocated this way will already be zeroed. */
 972         } else {
 973                 addr = ((void *) iopa_alloc(&gIOPageablePageAllocator, &IOMallocOnePageablePage, size, (uint32_t) alignment));
 974                 if (zeroed) {
 975                         bzero(addr, size);
 976                 }
 977         }
 978
 979         if (addr) {
 980 #if IOALLOCDEBUG
 981                 OSAddAtomicLong(size, &debug_iomallocpageable_size);
 982 #endif
 983                 IOStatisticsAlloc(kIOStatisticsMallocPageable, size);
 984         }
 985
 986         return addr;
 987 }
 988
 989 void *
 990 IOMallocPageable(vm_size_t size, vm_size_t alignment)
 991 {
 992         return IOMallocPageableInternal(size, alignment, /*zeroed*/ false);
 993 }
 994
 995 void *
 996 IOMallocPageableZero(vm_size_t size, vm_size_t alignment)
 997 {
 998         return IOMallocPageableInternal(size, alignment, /*zeroed*/ true);
 999 }
1000
1001 void
1002 IOFreePageable(void * address, vm_size_t size)
1003 {
1004 #if IOALLOCDEBUG
1005         OSAddAtomicLong(-size, &debug_iomallocpageable_size);
1006 #endif
1007         IOStatisticsAlloc(kIOStatisticsFreePageable, size);
1008
1009         if (size < (page_size - 4 * gIOPageAllocChunkBytes)) {
1010                 address = (void *) iopa_free(&gIOPageablePageAllocator, (uintptr_t) address, size);
1011                 size = page_size;
1012         }
1013         if (address) {
1014                 IOFreePageablePages(address, size);
1015         }
1016 }
1017
1018 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1019
1020 extern "C" void
1021 iopa_init(iopa_t * a)
1022 {
1023         bzero(a, sizeof(*a));
1024         a->lock = IOLockAlloc();
1025         queue_init(&a->list);
1026 }
1027
1028 static uintptr_t
1029 iopa_allocinpage(iopa_page_t * pa, uint32_t count, uint64_t align)
1030 {
1031         uint32_t n, s;
1032         uint64_t avail = pa->avail;
1033
1034         assert(avail);
1035
1036         // find strings of count 1 bits in avail
1037         for (n = count; n > 1; n -= s) {
1038                 s = n >> 1;
1039                 avail = avail & (avail << s);
1040         }
1041         // and aligned
1042         avail &= align;
1043
1044         if (avail) {
1045                 n = __builtin_clzll(avail);
1046                 pa->avail &= ~((-1ULL << (64 - count)) >> n);
1047                 if (!pa->avail && pa->link.next) {
1048                         remque(&pa->link);
1049                         pa->link.next = NULL;
1050                 }
1051                 return n * gIOPageAllocChunkBytes + trunc_page((uintptr_t) pa);
1052         }
1053
1054         return 0;
1055 }
1056
1057 uintptr_t
1058 iopa_alloc(iopa_t * a, iopa_proc_t alloc, vm_size_t bytes, vm_size_t balign)
1059 {
1060         static const uint64_t align_masks[] = {
1061                 0xFFFFFFFFFFFFFFFF,
1062                 0xAAAAAAAAAAAAAAAA,
1063                 0x8888888888888888,
1064                 0x8080808080808080,
1065                 0x8000800080008000,
1066                 0x8000000080000000,
1067                 0x8000000000000000,
1068         };
1069         iopa_page_t * pa;
1070         uintptr_t     addr = 0;
1071         uint32_t      count;
1072         uint64_t      align;
1073         vm_size_t     align_masks_idx;
1074
1075         if (((uint32_t) bytes) != bytes) {
1076                 return 0;
1077         }
1078         if (!bytes) {
1079                 bytes = 1;
1080         }
1081         count = (((uint32_t) bytes) + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes;
1082
1083         align_masks_idx = log2up((balign + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes);
1084         assert(align_masks_idx < sizeof(align_masks) / sizeof(*align_masks));
1085         align = align_masks[align_masks_idx];
1086
1087         IOLockLock(a->lock);
1088         __IGNORE_WCASTALIGN(pa = (typeof(pa))queue_first(&a->list));
1089         while (!queue_end(&a->list, &pa->link)) {
1090                 addr = iopa_allocinpage(pa, count, align);
1091                 if (addr) {
1092                         a->bytecount += bytes;
1093                         break;
1094                 }
1095                 __IGNORE_WCASTALIGN(pa = (typeof(pa))queue_next(&pa->link));
1096         }
1097         IOLockUnlock(a->lock);
1098
1099         if (!addr) {
1100                 addr = alloc(a);
1101                 if (addr) {
1102                         pa = (typeof(pa))(addr + page_size - gIOPageAllocChunkBytes);
1103                         pa->signature = kIOPageAllocSignature;
1104                         pa->avail     = -2ULL;
1105
1106                         addr = iopa_allocinpage(pa, count, align);
1107                         IOLockLock(a->lock);
1108                         if (pa->avail) {
1109                                 enqueue_head(&a->list, &pa->link);
1110                         }
1111                         a->pagecount++;
1112                         if (addr) {
1113                                 a->bytecount += bytes;
1114                         }
1115                         IOLockUnlock(a->lock);
1116                 }
1117         }
1118
1119         assert((addr & ((1 << log2up(balign)) - 1)) == 0);
1120         return addr;
1121 }
1122
1123 uintptr_t
1124 iopa_free(iopa_t * a, uintptr_t addr, vm_size_t bytes)
1125 {
1126         iopa_page_t * pa;
1127         uint32_t      count;
1128         uintptr_t     chunk;
1129
1130         if (((uint32_t) bytes) != bytes) {
1131                 return 0;
1132         }
1133         if (!bytes) {
1134                 bytes = 1;
1135         }
1136
1137         chunk = (addr & page_mask);
1138         assert(0 == (chunk & (gIOPageAllocChunkBytes - 1)));
1139
1140         pa = (typeof(pa))(addr | (page_size - gIOPageAllocChunkBytes));
1141         assert(kIOPageAllocSignature == pa->signature);
1142
1143         count = (((uint32_t) bytes) + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes;
1144         chunk /= gIOPageAllocChunkBytes;
1145
1146         IOLockLock(a->lock);
1147         if (!pa->avail) {
1148                 assert(!pa->link.next);
1149                 enqueue_tail(&a->list, &pa->link);
1150         }
1151         pa->avail |= ((-1ULL << (64 - count)) >> chunk);
1152         if (pa->avail != -2ULL) {
1153                 pa = NULL;
1154         } else {
1155                 remque(&pa->link);
1156                 pa->link.next = NULL;
1157                 pa->signature = 0;
1158                 a->pagecount--;
1159                 // page to free
1160                 pa = (typeof(pa))trunc_page(pa);
1161         }
1162         a->bytecount -= bytes;
1163         IOLockUnlock(a->lock);
1164
1165         return (uintptr_t) pa;
1166 }
1167
1168 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1169
1170 IOReturn
1171 IOSetProcessorCacheMode( task_t task, IOVirtualAddress address,
1172     IOByteCount length, IOOptionBits cacheMode )
1173 {
1174         IOReturn    ret = kIOReturnSuccess;
1175         ppnum_t     pagenum;
1176
1177         if (task != kernel_task) {
1178                 return kIOReturnUnsupported;
1179         }
1180         if ((address | length) & PAGE_MASK) {
1181 //      OSReportWithBacktrace("IOSetProcessorCacheMode(0x%x, 0x%x, 0x%x) fails\n", address, length, cacheMode);
1182                 return kIOReturnUnsupported;
1183         }
1184         length = round_page(address + length) - trunc_page( address );
1185         address = trunc_page( address );
1186
1187         // make map mode
1188         cacheMode = (cacheMode << kIOMapCacheShift) & kIOMapCacheMask;
1189
1190         while ((kIOReturnSuccess == ret) && (length > 0)) {
1191                 // Get the physical page number
1192                 pagenum = pmap_find_phys(kernel_pmap, (addr64_t)address);
1193                 if (pagenum) {
1194                         ret = IOUnmapPages( get_task_map(task), address, page_size );
1195                         ret = IOMapPages( get_task_map(task), address, ptoa_64(pagenum), page_size, cacheMode );
1196                 } else {
1197                         ret = kIOReturnVMError;
1198                 }
1199
1200                 address += page_size;
1201                 length -= page_size;
1202         }
1203
1204         return ret;
1205 }
1206
1207
1208 IOReturn
1209 IOFlushProcessorCache( task_t task, IOVirtualAddress address,
1210     IOByteCount length )
1211 {
1212         if (task != kernel_task) {
1213                 return kIOReturnUnsupported;
1214         }
1215
1216         flush_dcache64((addr64_t) address, (unsigned) length, false );
1217
1218         return kIOReturnSuccess;
1219 }
1220
1221 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1222
1223 vm_offset_t
1224 OSKernelStackRemaining( void )
1225 {
1226         return ml_stack_remaining();
1227 }
1228
1229 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1230
1231 /*
1232  * Spin for indicated number of milliseconds.
1233  */
1234 void
1235 IOSleep(unsigned milliseconds)
1236 {
1237         delay_for_interval(milliseconds, kMillisecondScale);
1238 }
1239
1240 /*
1241  * Spin for indicated number of milliseconds, and potentially an
1242  * additional number of milliseconds up to the leeway values.
1243  */
1244 void
1245 IOSleepWithLeeway(unsigned intervalMilliseconds, unsigned leewayMilliseconds)
1246 {
1247         delay_for_interval_with_leeway(intervalMilliseconds, leewayMilliseconds, kMillisecondScale);
1248 }
1249
1250 /*
1251  * Spin for indicated number of microseconds.
1252  */
1253 void
1254 IODelay(unsigned microseconds)
1255 {
1256         delay_for_interval(microseconds, kMicrosecondScale);
1257 }
1258
1259 /*
1260  * Spin for indicated number of nanoseconds.
1261  */
1262 void
1263 IOPause(unsigned nanoseconds)
1264 {
1265         delay_for_interval(nanoseconds, kNanosecondScale);
1266 }
1267
1268 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1269
1270 static void _IOLogv(const char *format, va_list ap, void *caller) __printflike(1, 0);
1271
1272 __attribute__((noinline, not_tail_called))
1273 void
1274 IOLog(const char *format, ...)
1275 {
1276         void *caller = __builtin_return_address(0);
1277         va_list ap;
1278
1279         va_start(ap, format);
1280         _IOLogv(format, ap, caller);
1281         va_end(ap);
1282 }
1283
1284 __attribute__((noinline, not_tail_called))
1285 void
1286 IOLogv(const char *format, va_list ap)
1287 {
1288         void *caller = __builtin_return_address(0);
1289         _IOLogv(format, ap, caller);
1290 }
1291
1292 void
1293 _IOLogv(const char *format, va_list ap, void *caller)
1294 {
1295         va_list ap2;
1296         struct console_printbuf_state info_data;
1297         console_printbuf_state_init(&info_data, TRUE, TRUE);
1298
1299         va_copy(ap2, ap);
1300
1301         os_log_with_args(OS_LOG_DEFAULT, OS_LOG_TYPE_DEFAULT, format, ap, caller);
1302
1303         __doprnt(format, ap2, console_printbuf_putc, &info_data, 16, TRUE);
1304         console_printbuf_clear(&info_data);
1305         va_end(ap2);
1306
1307         assertf(ml_get_interrupts_enabled() || ml_is_quiescing() || debug_mode_active() || !gCPUsRunning, "IOLog called with interrupts disabled");
1308 }
1309
1310 #if !__LP64__
1311 void
1312 IOPanic(const char *reason)
1313 {
1314         panic("%s", reason);
1315 }
1316 #endif
1317
1318 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1319
1320 void
1321 IOKitKernelLogBuffer(const char * title, const void * buffer, size_t size,
1322     void (*output)(const char *format, ...))
1323 {
1324         size_t idx, linestart;
1325         enum { bytelen = (sizeof("0xZZ, ") - 1) };
1326         char hex[(bytelen * 16) + 1];
1327         uint8_t c, chars[17];
1328
1329         output("%s(0x%lx):\n", title, size);
1330         output("              0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F\n");
1331         if (size > 4096) {
1332                 size = 4096;
1333         }
1334         chars[16] = 0;
1335         for (idx = 0, linestart = 0; idx < size;) {
1336                 c = ((char *)buffer)[idx];
1337                 snprintf(&hex[bytelen * (idx & 15)], bytelen + 1, "0x%02x, ", c);
1338                 chars[idx & 15] = ((c >= 0x20) && (c <= 0x7f)) ? c : ' ';
1339                 idx++;
1340                 if ((idx == size) || !(idx & 15)) {
1341                         if (idx & 15) {
1342                                 chars[idx & 15] = 0;
1343                         }
1344                         output("/* %04lx: */ %-96s /* |%-16s| */\n", linestart, hex, chars);
1345                         linestart += 16;
1346                 }
1347         }
1348 }
1349
1350 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1351
1352 /*
1353  * Convert a integer constant (typically a #define or enum) to a string.
1354  */
1355 static char noValue[80];        // that's pretty
1356
1357 const char *
1358 IOFindNameForValue(int value, const IONamedValue *regValueArray)
1359 {
1360         for (; regValueArray->name; regValueArray++) {
1361                 if (regValueArray->value == value) {
1362                         return regValueArray->name;
1363                 }
1364         }
1365         snprintf(noValue, sizeof(noValue), "0x%x (UNDEFINED)", value);
1366         return (const char *)noValue;
1367 }
1368
1369 IOReturn
1370 IOFindValueForName(const char *string,
1371     const IONamedValue *regValueArray,
1372     int *value)
1373 {
1374         for (; regValueArray->name; regValueArray++) {
1375                 if (!strcmp(regValueArray->name, string)) {
1376                         *value = regValueArray->value;
1377                         return kIOReturnSuccess;
1378                 }
1379         }
1380         return kIOReturnBadArgument;
1381 }
1382
1383 OSString *
1384 IOCopyLogNameForPID(int pid)
1385 {
1386         char   buf[128];
1387         size_t len;
1388         snprintf(buf, sizeof(buf), "pid %d, ", pid);
1389         len = strlen(buf);
1390         proc_name(pid, buf + len, (int) (sizeof(buf) - len));
1391         return OSString::withCString(buf);
1392 }
1393
1394 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1395
1396 IOAlignment
1397 IOSizeToAlignment(unsigned int size)
1398 {
1399         int shift;
1400         const int intsize = sizeof(unsigned int) * 8;
1401
1402         for (shift = 1; shift < intsize; shift++) {
1403                 if (size & 0x80000000) {
1404                         return (IOAlignment)(intsize - shift);
1405                 }
1406                 size <<= 1;
1407         }
1408         return 0;
1409 }
1410
1411 unsigned int
1412 IOAlignmentToSize(IOAlignment align)
1413 {
1414         unsigned int size;
1415
1416         for (size = 1; align; align--) {
1417                 size <<= 1;
1418         }
1419         return size;
1420 }
1421 } /* extern "C" */