![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to objc-sel.m CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / objc|
Return to objc-sel.m CVS log | Up to [Apple Darwin 0.x] / objc |
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.