|
|
1.1 ! root 1: /* ! 2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. ! 3: * ! 4: * @APPLE_LICENSE_HEADER_START@ ! 5: * ! 6: * "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights ! 7: * Reserved. This file contains Original Code and/or Modifications of ! 8: * Original Code as defined in and that are subject to the Apple Public ! 9: * Source License Version 1.0 (the 'License'). You may not use this file ! 10: * except in compliance with the License. Please obtain a copy of the ! 11: * License at http://www.apple.com/publicsource and read it before using ! 12: * this file. ! 13: * ! 14: * The Original Code and all software distributed under the License are ! 15: * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER ! 16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, ! 17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, ! 18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the ! 19: * License for the specific language governing rights and limitations ! 20: * under the License." ! 21: * ! 22: * @APPLE_LICENSE_HEADER_END@ ! 23: */ ! 24: /* ! 25: * objc-sel.m ! 26: * Copyright 1988, NeXT, Inc. ! 27: * Author: s. naroff ! 28: * ! 29: * Public functions: ! 30: * -------------- ! 31: * ! 32: * sel_getName ! 33: * sel_getUid ! 34: * sel_isMapped ! 35: * sel_registerName ! 36: * _strhash (undocumented) ! 37: * ! 38: * Private functions: ! 39: * --------------- ! 40: * ! 41: * _sel_init (private extern) ! 42: * _sel_unloadSelectors (private extern) ! 43: * ! 44: */ ! 45: ! 46: #ifdef SHLIB ! 47: #import "shlib.h" ! 48: #endif SHLIB ! 49: ! 50: #import "objc-private.h" ! 51: ! 52: /* Number of hashtable buckets to malloc in a chunk */ ! 53: ! 54: #define HASH_ALLOC_LIST_SIZE 40 ! 55: ! 56: /* Size of the dynamic and freeze-dried hashtables */ ! 57: ! 58: #define SIZEHASHTABLE 821 ! 59: ! 60: ! 61: typedef struct _hashEntry ! 62: { ! 63: struct _hashEntry *next; ! 64: const char *sel; ! 65: } HASH, *PHASH; ! 66: ! 67: typedef struct _hashTable ! 68: { ! 69: const struct mach_header *header; ! 70: unsigned int count; ! 71: unsigned int entries; ! 72: const char *min; ! 73: const char *max; ! 74: PHASH *list; ! 75: struct _hashTable *next; ! 76: } hashTable; ! 77: ! 78: /* The dynamic hashtable contains all selectors which are not present in ! 79: any freeze-dried hashtable. Space for it is allocated only on demand. ! 80: We use a sentinel to avoid extra tests for NULL. */ ! 81: ! 82: static const PHASH sentinel = NULL; ! 83: ! 84: static hashTable dynamicHashTable = ! 85: { ! 86: NULL, ! 87: 1, // count ! 88: 0, // entries ! 89: NULL, // Range checking does not work for the dynamic hashtable. ! 90: NULL, ! 91: (PHASH *) &sentinel, ! 92: NULL, // next ! 93: }; ! 94: ! 95: ! 96: /* The list of all hashtables. The freeze-dried hashtables are placed on ! 97: the list in order of size, and the dynamic hashtable is always last. */ ! 98: ! 99: static hashTable *hashTableChain = &dynamicHashTable; ! 100: ! 101: #ifndef FREEZE ! 102: /* Lock for all static data in objc-sel.m */ ! 103: ! 104: static OBJC_DECLARE_LOCK (selectorLock); ! 105: #endif ! 106: ! 107: /* This is a duplicate of a static function in objc-class.m! We should ! 108: make this a private extern. */ ! 109: ! 110: static void *objc_malloc (unsigned int size) ! 111: { ! 112: NXZone *zone; ! 113: void *space; ! 114: ! 115: #ifdef FREEZE ! 116: zone = NXDefaultMallocZone (); ! 117: #else ! 118: zone = _objc_create_zone (); ! 119: #endif ! 120: ! 121: space = NXZoneMalloc (zone, size); ! 122: ! 123: if (space == 0 && size != 0) ! 124: __S(_objc_fatal) ("unable to allocate space"); ! 125: ! 126: return space; ! 127: } ! 128: ! 129: ! 130: /* For compatibility only. This function is public even though it never ! 131: should have been. */ ! 132: ! 133: #ifndef FREEZE ! 134: unsigned int _strhash (const unsigned char *s) ! 135: { ! 136: return _objc_strhash (s); ! 137: } ! 138: #endif ! 139: ! 140: /* Allocate and initialize a new bucket for the dynamic hashtable. ! 141: The selector lock is assumed to be already taken out. */ ! 142: ! 143: static inline PHASH opthashNew (const char *key, PHASH link) ! 144: { ! 145: static PHASH HASH_alloc_list = 0; ! 146: static int HASH_alloc_index = 0; ! 147: PHASH new; ! 148: ! 149: if (!HASH_alloc_list || HASH_alloc_index >= HASH_ALLOC_LIST_SIZE) ! 150: { ! 151: HASH_alloc_list = objc_malloc (sizeof (HASH) * HASH_ALLOC_LIST_SIZE); ! 152: HASH_alloc_index = 0; ! 153: } ! 154: ! 155: new = &HASH_alloc_list[HASH_alloc_index++]; ! 156: new->next = link; ! 157: new->sel = key; ! 158: return new; ! 159: } ! 160: ! 161: ! 162: #ifndef FREEZE ! 163: /* This is no longer used. We should remove this from the API. */ ! 164: ! 165: BOOL sel_isMapped (SEL sel) ! 166: { ! 167: hashTable *table; ! 168: ! 169: if (sel == (SEL) 0) ! 170: return NO; ! 171: ! 172: OBJC_LOCK (&selectorLock); ! 173: ! 174: for (table = hashTableChain; table; table = table->next) ! 175: { ! 176: if ((const char *) sel >= table->min && (const char *) sel < table->max) ! 177: { ! 178: OBJC_UNLOCK (&selectorLock); ! 179: return YES; ! 180: } ! 181: else if (table == &dynamicHashTable) ! 182: { ! 183: unsigned int slot; ! 184: ! 185: for (slot = 0; slot < table->count; slot++) ! 186: { ! 187: PHASH target; ! 188: ! 189: for (target = table->list[slot]; target; target = target->next) ! 190: if (sel == (SEL)target->sel) ! 191: { ! 192: OBJC_UNLOCK (&selectorLock); ! 193: return YES; ! 194: } ! 195: } ! 196: } ! 197: } ! 198: ! 199: OBJC_UNLOCK (&selectorLock); ! 200: ! 201: return NO; ! 202: } ! 203: #endif ! 204: ! 205: #ifndef FREEZE ! 206: /* This is now very fast! ! 207: Note that previously we would return NULL if passed an invalid selector. */ ! 208: ! 209: const char *sel_getName (SEL sel) ! 210: { ! 211: return (const char *) sel; ! 212: } ! 213: #endif ! 214: ! 215: /* Add a new selector if not already present. Formerly _sel_registerName(). ! 216: Now again _sel_registerName(), and a public safe variant added. */ ! 217: ! 218: SEL __S(_sel_registerName) (const char *key) ! 219: { ! 220: unsigned int hash; ! 221: hashTable *table; ! 222: ! 223: if (!key) ! 224: return (SEL) 0; ! 225: ! 226: hash = _objc_strhash (key); ! 227: ! 228: OBJC_LOCK (&selectorLock); ! 229: ! 230: for (table = hashTableChain; table; table = table->next) ! 231: { ! 232: if (key >= table->min && key < table->max) ! 233: { ! 234: OBJC_UNLOCK (&selectorLock); ! 235: return (SEL) key; ! 236: } ! 237: else ! 238: { ! 239: PHASH target; ! 240: unsigned int slot = hash % table->count; ! 241: ! 242: for (target = table->list[slot]; target; target = target->next) ! 243: if (key[0] == target->sel[0] && ! 244: strcmp (key, target->sel) == 0) ! 245: { ! 246: OBJC_UNLOCK (&selectorLock); ! 247: return (SEL) target->sel; ! 248: } ! 249: ! 250: /* If we have reached the dynamic hashtable, insert a new entry. */ ! 251: if (table == &dynamicHashTable) ! 252: { ! 253: table->entries++; ! 254: ! 255: /* Allocate hashtable if needed. */ ! 256: if (table->list == &sentinel) ! 257: { ! 258: /* Allocate a new empty array. */ ! 259: table->count = SIZEHASHTABLE; ! 260: table->list = objc_malloc (table->count * sizeof (PHASH)); ! 261: bzero (table->list, table->count * sizeof (PHASH)); ! 262: slot = hash % table->count; ! 263: } ! 264: ! 265: table->list[slot] = opthashNew (key, table->list[slot]); ! 266: OBJC_UNLOCK (&selectorLock); ! 267: return (SEL) key; ! 268: } ! 269: } ! 270: } ! 271: ! 272: /* We searched all hashtables without finding the dynamic hashtable! */ ! 273: abort (); ! 274: } ! 275: ! 276: /* ! 277: * Public version of _sel_registerName, which assures that the ! 278: * argument key is copied if nessecary. ! 279: */ ! 280: ! 281: #ifndef FREEZE ! 282: SEL sel_registerName (const char *key) ! 283: { ! 284: SEL s = sel_getUid (key); ! 285: if (s) ! 286: return s; ! 287: else ! 288: return __S(_sel_registerName) (NXUniqueString (key)); ! 289: } ! 290: #endif ! 291: ! 292: /* Remove all of the selectors associated with a dynamically loaded module. ! 293: We currently leak the removed entries (because they are allocated in ! 294: chunks). We could instead build a free chain out of them to reuse. */ ! 295: ! 296: #ifndef FREEZE ! 297: void __S(_sel_unloadSelectors) (const char *min, const char *max) ! 298: { ! 299: hashTable *table = &dynamicHashTable; ! 300: unsigned int slot; ! 301: ! 302: OBJC_LOCK (&selectorLock); ! 303: ! 304: for (slot = 0; slot < table->count; slot++) ! 305: { ! 306: PHASH *ptr = &table->list[slot]; ! 307: ! 308: while (*ptr) ! 309: { ! 310: PHASH target = *ptr; ! 311: ! 312: if (target->sel >= min && target->sel < max) ! 313: *ptr = target->next; /* Remove this entry */ ! 314: else ! 315: ptr = &target->next; /* Skip */ ! 316: } ! 317: } ! 318: ! 319: OBJC_UNLOCK (&selectorLock); ! 320: } ! 321: #endif ! 322: ! 323: /* Search each hashtable in the chain for the string. */ ! 324: ! 325: #ifndef FREEZE ! 326: SEL sel_getUid (const char *key) ! 327: { ! 328: unsigned int hash; ! 329: hashTable *table; ! 330: ! 331: if (!key) ! 332: return (SEL) 0; ! 333: ! 334: hash = _objc_strhash (key); ! 335: ! 336: OBJC_LOCK (&selectorLock); ! 337: ! 338: for (table = hashTableChain; table; table = table->next) ! 339: { ! 340: if (key >= table->min && key < table->max) ! 341: { ! 342: OBJC_UNLOCK (&selectorLock); ! 343: return (SEL) key; ! 344: } ! 345: else ! 346: { ! 347: PHASH target; ! 348: unsigned int slot = hash % table->count; ! 349: ! 350: for (target = table->list[slot]; target; target = target->next) ! 351: if (key[0] == target->sel[0] && ! 352: strcmp (key, target->sel) == 0) ! 353: { ! 354: OBJC_UNLOCK (&selectorLock); ! 355: return (SEL) target->sel; ! 356: } ! 357: } ! 358: } ! 359: ! 360: OBJC_UNLOCK (&selectorLock); ! 361: ! 362: return (SEL) 0; ! 363: } ! 364: #endif ! 365: ! 366: /* Register a freeze-dried hashtable. */ ! 367: ! 368: void __S(_sel_init) (const struct mach_header *header, ! 369: const char *strings, ! 370: unsigned int stringSize, ! 371: void *frozenHashTable) ! 372: { ! 373: hashTable *frozenTable = NXZoneMalloc (NXDefaultMallocZone(), sizeof (hashTable)); ! 374: hashTable **tablePtr; ! 375: ! 376: frozenTable->header = header; ! 377: frozenTable->count = SIZEHASHTABLE; ! 378: frozenTable->entries = 0; ! 379: frozenTable->min = strings; ! 380: frozenTable->max = strings + stringSize; ! 381: frozenTable->list = frozenHashTable; ! 382: ! 383: /* Insert the freeze-dried hashtable at the end of the hashtable chain. */ ! 384: ! 385: for (tablePtr = &hashTableChain; *tablePtr; tablePtr = &(*tablePtr)->next) ! 386: if (*tablePtr == &dynamicHashTable) ! 387: { ! 388: frozenTable->next = &dynamicHashTable; ! 389: *tablePtr = frozenTable; ! 390: break; ! 391: } ! 392: } ! 393: ! 394: ! 395: #if !defined(KERNEL) && !defined(FREEZE) ! 396: ! 397: void _sel_printHashTable (void) ! 398: { ! 399: hashTable *table; ! 400: ! 401: for (table = hashTableChain; table; table = table->next) ! 402: { ! 403: unsigned int slot; ! 404: ! 405: printf ("%s selector hashtable for %s:\n", ! 406: (table == &dynamicHashTable) ? "dynamic" : "freeze-dried", ! 407: __S(_nameForHeader) (table->header)); ! 408: ! 409: printf ("\n"); ! 410: ! 411: for (slot = 0; slot < table->count; slot++) ! 412: { ! 413: PHASH target; ! 414: ! 415: printf ("slot[%u]: ", slot); ! 416: ! 417: for (target = table->list[slot]; target; target = target->next) ! 418: printf (" %s", target->sel); ! 419: ! 420: printf ("\n"); ! 421: } ! 422: ! 423: printf ("\n"); ! 424: } ! 425: } ! 426: ! 427: ! 428: void _sel_printStatistics (void) ! 429: { ! 430: hashTable *table; ! 431: unsigned int totalCount = 0; ! 432: unsigned int totalEntries = 0; ! 433: unsigned int totalUniqueEntries = 0; ! 434: unsigned int totalEmptySlots = 0; ! 435: unsigned int grandTotalChain = 0; ! 436: unsigned int grandTotalMissChain = 0; ! 437: unsigned int maxMaxChain = 0; ! 438: unsigned int maxMaxMissChain = 0; ! 439: unsigned int totalMallocedData = 0; ! 440: unsigned int totalSharedData = 0; ! 441: unsigned int depth = 0; ! 442: unsigned int totalDepth = 0; ! 443: ! 444: for (table = hashTableChain; table; table = table->next) ! 445: { ! 446: unsigned int slot; ! 447: unsigned int entries = 0; ! 448: unsigned int uniqueEntries = 0; ! 449: unsigned int emptySlots = 0; ! 450: unsigned int totalChain = 0; ! 451: unsigned int totalMissChain = 0; ! 452: unsigned int maxChain = 0; ! 453: unsigned int maxMissChain = 0; ! 454: unsigned int mallocedData; ! 455: unsigned int sharedData; ! 456: ! 457: for (slot = 0; slot < table->count; slot++) ! 458: { ! 459: PHASH target; ! 460: unsigned int chain = 0; ! 461: ! 462: for (target = table->list[slot]; target; target = target->next) ! 463: { ! 464: entries++; ! 465: ! 466: if (sel_getUid (target->sel) == (SEL) target->sel) ! 467: { ! 468: uniqueEntries++; ! 469: ! 470: chain++; ! 471: ! 472: if (chain > maxChain) ! 473: maxChain = chain; ! 474: ! 475: totalChain += chain; ! 476: } ! 477: } ! 478: ! 479: if (chain > maxMissChain) ! 480: maxMissChain = chain; ! 481: ! 482: totalMissChain += chain; ! 483: ! 484: if (chain == 0) ! 485: emptySlots++; ! 486: } ! 487: ! 488: printf ("%s selector hashtable for %s (depth = %u):\n", ! 489: (table == &dynamicHashTable) ? "dynamic" : "freeze-dried", ! 490: __S(_nameForHeader) (table->header), ! 491: depth); ! 492: ! 493: printf ("%u entries in %u slots (%.2f entries/slot)\n", ! 494: entries, table->count, (float) entries / (float) table->count); ! 495: printf ("%u empty slots (%u%%)\n", ! 496: emptySlots, (100 * emptySlots + 50) / table->count); ! 497: printf ("%u redundant entries (%u%%)\n", ! 498: entries - uniqueEntries, ! 499: (100 * (entries - uniqueEntries) + 50) / entries); ! 500: printf ("%.2f average lookup chain (%u maximum)\n", ! 501: (float) totalChain / (float) uniqueEntries, maxChain); ! 502: printf ("%.2f average miss chain (%u maximum)\n", ! 503: (float) totalMissChain / (float) table->count, maxMissChain); ! 504: if (table == &dynamicHashTable) ! 505: { ! 506: unsigned int chunks = (entries + HASH_ALLOC_LIST_SIZE - 1) / ! 507: HASH_ALLOC_LIST_SIZE; ! 508: ! 509: mallocedData = table->count * sizeof (PHASH) + ! 510: chunks * HASH_ALLOC_LIST_SIZE * sizeof (HASH); ! 511: sharedData = 0; ! 512: } ! 513: else ! 514: { ! 515: mallocedData = sizeof (hashTable); ! 516: sharedData = table->count * sizeof (PHASH) + entries * sizeof (HASH); ! 517: } ! 518: ! 519: if (sharedData) ! 520: printf ("%u bytes malloced data + %u bytes shared data\n", ! 521: mallocedData, sharedData); ! 522: else ! 523: printf ("%u bytes malloced data\n", mallocedData); ! 524: ! 525: totalCount += table->count; ! 526: totalEntries += entries; ! 527: totalUniqueEntries += uniqueEntries; ! 528: totalEmptySlots += emptySlots; ! 529: grandTotalChain += totalChain; ! 530: grandTotalMissChain += totalMissChain; ! 531: if (maxChain > maxMaxChain) ! 532: maxMaxChain = maxChain; ! 533: if (maxMissChain > maxMaxMissChain) ! 534: maxMaxMissChain = maxMissChain; ! 535: totalMallocedData += mallocedData; ! 536: totalSharedData += sharedData; ! 537: totalDepth += depth * uniqueEntries; ! 538: depth++; ! 539: ! 540: printf ("\n"); ! 541: } ! 542: ! 543: printf ("cummulative selector hashtable statistics:\n"); ! 544: ! 545: printf ("%u entries in %u slots (%.2f entries/slot)\n", ! 546: totalEntries, totalCount, (float) totalEntries / (float) totalCount); ! 547: printf ("%u empty slots (%u%%)\n", ! 548: totalEmptySlots, (100 * totalEmptySlots + 50) / totalCount); ! 549: printf ("%u redundant entries (%u%%)\n", ! 550: totalEntries - totalUniqueEntries, ! 551: (100 * (totalEntries - totalUniqueEntries) + 50) / totalEntries); ! 552: printf ("%.2f average lookup depth (%u maximum)\n", ! 553: (float) totalDepth / (float) totalUniqueEntries, ! 554: depth - 1); ! 555: printf ("%.2f average lookup chain (%u maximum)\n", ! 556: (float) grandTotalChain / (float) totalUniqueEntries, ! 557: maxMaxChain); ! 558: printf ("%u miss depth\n", depth - 1); ! 559: printf ("%.2f average miss chain (%u maximum)\n", ! 560: (float) grandTotalMissChain / (float) totalCount, ! 561: maxMaxMissChain); ! 562: ! 563: if (totalSharedData) ! 564: printf ("%u bytes malloced data + %u bytes shared data\n", ! 565: totalMallocedData, totalSharedData); ! 566: else ! 567: printf ("%u bytes malloced data\n", totalMallocedData); ! 568: } ! 569: ! 570: #endif /* KERNEL */ ! 571: ! 572: #ifdef FREEZE ! 573: ! 574: void volatile __S(_objc_fatal) (const char *msg) ! 575: { ! 576: printf ("objc fatal: %s\n", msg); ! 577: exit (1); ! 578: } ! 579: ! 580: ! 581: /* used by `objcopt' to freeze dry a hash table */ ! 582: ! 583: void __S(_sel_writeHashTable) (int start_addr, ! 584: char *myAddressSpace, ! 585: char *shlibAddressSpace, ! 586: void **addr, int *size) ! 587: { ! 588: hashTable *table = &dynamicHashTable; ! 589: unsigned int frozenSize = table->count * sizeof (PHASH) + ! 590: table->entries * sizeof (HASH); ! 591: PHASH *frozenTable = NXZoneMalloc (NXDefaultMallocZone(), frozenSize); ! 592: PHASH frozenEntries = (PHASH) (frozenTable + table->count); ! 593: PHASH vm_hashEntryList = (PHASH) (start_addr + ! 594: table->count * sizeof (PHASH)); ! 595: unsigned int slot; ! 596: ! 597: bzero (frozenTable, frozenSize); ! 598: ! 599: for (slot = 0; slot < table->count; slot++) ! 600: if (table->list[slot]) ! 601: { ! 602: PHASH target; ! 603: ! 604: frozenTable[slot] = vm_hashEntryList; ! 605: ! 606: for (target = table->list[slot]; target; target = target->next) ! 607: { ! 608: frozenEntries->sel = (target->sel - myAddressSpace) + ! 609: shlibAddressSpace; ! 610: if (target->next) ! 611: frozenEntries->next = vm_hashEntryList + 1; ! 612: ! 613: frozenEntries++; ! 614: vm_hashEntryList++; ! 615: } ! 616: } ! 617: ! 618: *addr = frozenTable; ! 619: *size = frozenSize; ! 620: } ! 621: ! 622: const char *__S(_nameForHeader) (const struct mach_header *header) ! 623: { ! 624: return "objcopt"; ! 625: } ! 626: ! 627: #endif /* FREEZE */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.