12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793 |
- #if !__OBJC2__
- #include "objc-private.h"
- #include "objc-cache-old.h"
- #include "hashtable2.h"
- typedef struct {
- SEL name;
- void *unused;
- IMP imp;
- } cache_entry;
- static const int _class_slow_grow = 1;
- enum {
- INIT_CACHE_SIZE_LOG2 = 2,
- INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2)
- };
- #define TABLE_SIZE(count) ((count - 1) * sizeof(cache_entry *))
- #if !TARGET_OS_WIN32
- # define CACHE_ALLOCATOR
- #endif
- #define CACHE_ALLOCATOR_MIN 512
- #define CACHE_QUANTUM (CACHE_ALLOCATOR_MIN+sizeof(struct objc_cache)-sizeof(cache_entry*))
- #define CACHE_REGION_SIZE ((128*1024 / CACHE_QUANTUM) * CACHE_QUANTUM)
- static uintptr_t cache_allocator_mask_for_size(size_t size)
- {
- return (size - sizeof(struct objc_cache)) / sizeof(cache_entry *);
- }
- static size_t cache_allocator_size_for_mask(uintptr_t mask)
- {
- size_t requested = sizeof(struct objc_cache) + TABLE_SIZE(mask+1);
- size_t actual = CACHE_QUANTUM;
- while (actual < requested) actual += CACHE_QUANTUM;
- return actual;
- }
- #ifdef OBJC_INSTRUMENTED
- typedef struct
- {
- unsigned int hitCount;
- unsigned int hitProbes;
- unsigned int maxHitProbes;
- unsigned int missCount;
- unsigned int missProbes;
- unsigned int maxMissProbes;
- unsigned int flushCount;
- unsigned int flushedEntries;
- unsigned int maxFlushedEntries;
- } CacheInstrumentation;
- #define CACHE_INSTRUMENTATION(cache) (CacheInstrumentation *) &cache->buckets[cache->mask + 1];
- #endif
- static int totalCacheFills = 0;
- #ifdef OBJC_INSTRUMENTED
- unsigned int LinearFlushCachesCount = 0;
- unsigned int LinearFlushCachesVisitedCount = 0;
- unsigned int MaxLinearFlushCachesVisitedCount = 0;
- unsigned int NonlinearFlushCachesCount = 0;
- unsigned int NonlinearFlushCachesClassCount = 0;
- unsigned int NonlinearFlushCachesVisitedCount = 0;
- unsigned int MaxNonlinearFlushCachesVisitedCount = 0;
- unsigned int IdealFlushCachesCount = 0;
- unsigned int MaxIdealFlushCachesCount = 0;
- #endif
- struct objc_cache _objc_empty_cache =
- {
- 0,
- 0,
- { NULL }
- };
- #ifdef OBJC_INSTRUMENTED
- CacheInstrumentation emptyCacheInstrumentation = {0};
- #endif
- static bool _cache_isEmpty(Cache cache);
- static Cache _cache_malloc(uintptr_t slotCount);
- static Cache _cache_create(Class cls);
- static Cache _cache_expand(Class cls);
- static int _collecting_in_critical(void);
- static void _garbage_make_room(void);
- static void _cache_collect_free(void *data, size_t size);
- #if defined(CACHE_ALLOCATOR)
- static bool cache_allocator_is_block(void *block);
- static Cache cache_allocator_calloc(size_t size);
- static void cache_allocator_free(void *block);
- #endif
- static unsigned int cache_counts[16];
- static size_t cache_allocations;
- static size_t cache_collections;
- static size_t cache_allocator_regions;
- static size_t log2u(size_t x)
- {
- unsigned int log;
- log = 0;
- while (x >>= 1)
- log += 1;
- return log;
- }
- static bool _cache_isEmpty(Cache cache)
- {
- return (cache == NULL || cache == (Cache)&_objc_empty_cache || cache->mask == 0);
- }
- static Cache _cache_malloc(uintptr_t slotCount)
- {
- Cache new_cache;
- size_t size;
- cacheUpdateLock.assertLocked();
-
- size = sizeof(struct objc_cache) + TABLE_SIZE(slotCount);
- #if defined(OBJC_INSTRUMENTED)
-
- size += sizeof(CacheInstrumentation);
- new_cache = calloc(size, 1);
- new_cache->mask = slotCount - 1;
- #elif !defined(CACHE_ALLOCATOR)
-
- new_cache = calloc(size, 1);
- new_cache->mask = (unsigned int)(slotCount - 1);
- #else
- if (size < CACHE_ALLOCATOR_MIN) {
- new_cache = (Cache)calloc(size, 1);
- new_cache->mask = slotCount - 1;
-
- } else {
- new_cache = cache_allocator_calloc(size);
-
-
- }
- #endif
- if (PrintCaches) {
- size_t bucket = log2u(slotCount);
- if (bucket < sizeof(cache_counts) / sizeof(cache_counts[0])) {
- cache_counts[bucket]++;
- }
- cache_allocations++;
- }
- return new_cache;
- }
- static inline int isPowerOf2(unsigned long l) { return 1 == __builtin_popcountl(l); }
- static void _cache_free_block(void *block)
- {
- cacheUpdateLock.assertLocked();
- #if !TARGET_OS_WIN32
- if (PrintCaches) {
- Cache cache = (Cache)block;
- size_t slotCount = cache->mask + 1;
- if (isPowerOf2(slotCount)) {
- size_t bucket = log2u(slotCount);
- if (bucket < sizeof(cache_counts) / sizeof(cache_counts[0])) {
- cache_counts[bucket]--;
- }
- }
- }
- #endif
- #if defined(CACHE_ALLOCATOR)
- if (cache_allocator_is_block(block)) {
- cache_allocator_free(block);
- } else
- #endif
- {
- free(block);
- }
- }
- void _cache_free(Cache cache)
- {
- unsigned int i;
- mutex_locker_t lock(cacheUpdateLock);
- for (i = 0; i < cache->mask + 1; i++) {
- cache_entry *entry = (cache_entry *)cache->buckets[i];
- if (entry && entry->imp == _objc_msgForward_impcache) {
- _cache_free_block(entry);
- }
- }
-
- _cache_free_block(cache);
- }
- static Cache _cache_create(Class cls)
- {
- Cache new_cache;
- cacheUpdateLock.assertLocked();
-
- new_cache = _cache_malloc(INIT_CACHE_SIZE);
-
- cls->cache = new_cache;
-
-
-
- if (_class_slow_grow) {
- cls->setShouldGrowCache(false);
- }
-
- return new_cache;
- }
- static Cache _cache_expand(Class cls)
- {
- Cache old_cache;
- Cache new_cache;
- uintptr_t slotCount;
- uintptr_t index;
- cacheUpdateLock.assertLocked();
-
- old_cache = cls->cache;
- if (_cache_isEmpty(old_cache))
- return _cache_create (cls);
- if (_class_slow_grow) {
-
- if (cls->shouldGrowCache()) {
-
- cls->setShouldGrowCache(false);
- }
- else {
-
- cls->setShouldGrowCache(true);
-
- old_cache->occupied = 0;
-
- for (index = 0; index < old_cache->mask + 1; index += 1)
- {
-
-
- cache_entry *oldEntry = (cache_entry *)old_cache->buckets[index];
-
-
- if (!oldEntry)
- continue;
-
- old_cache->buckets[index] = NULL;
-
- if (oldEntry->imp == _objc_msgForward_impcache) {
- _cache_collect_free (oldEntry, sizeof(cache_entry));
- }
- }
-
- return old_cache;
- }
- }
-
- slotCount = (old_cache->mask + 1) << 1;
- new_cache = _cache_malloc(slotCount);
- #ifdef OBJC_INSTRUMENTED
-
- {
- CacheInstrumentation *oldCacheData;
- CacheInstrumentation *newCacheData;
- oldCacheData = CACHE_INSTRUMENTATION(old_cache);
- newCacheData = CACHE_INSTRUMENTATION(new_cache);
- bcopy ((const char *)oldCacheData, (char *)newCacheData, sizeof(CacheInstrumentation));
- }
- #endif
-
- for (index = 0; index < old_cache->mask + 1; index++) {
- cache_entry *entry = (cache_entry *)old_cache->buckets[index];
- if (entry && entry->imp == _objc_msgForward_impcache) {
- _cache_collect_free (entry, sizeof(cache_entry));
- }
- }
-
- cls->cache = new_cache;
-
- _cache_collect_free (old_cache, old_cache->mask * sizeof(cache_entry *));
- _cache_collect(false);
- return new_cache;
- }
- bool _cache_fill(Class cls, Method smt, SEL sel)
- {
- uintptr_t newOccupied;
- uintptr_t index;
- cache_entry **buckets;
- cache_entry *entry;
- Cache cache;
- cacheUpdateLock.assertUnlocked();
-
- if (!cls->isInitialized()) {
- return NO;
- }
-
- totalCacheFills += 1;
- mutex_locker_t lock(cacheUpdateLock);
- entry = (cache_entry *)smt;
- cache = cls->cache;
-
-
-
-
- if (_cache_getImp(cls, sel)) {
- return NO;
- }
-
- newOccupied = cache->occupied + 1;
- if ((newOccupied * 4) <= (cache->mask + 1) * 3) {
-
- cache->occupied = (unsigned int)newOccupied;
- } else {
-
- cache = _cache_expand (cls);
-
- cache->occupied += 1;
- }
-
-
-
- buckets = (cache_entry **)cache->buckets;
- for (index = CACHE_HASH(sel, cache->mask);
- buckets[index] != NULL;
- index = (index+1) & cache->mask)
- {
-
- }
- buckets[index] = entry;
- return YES;
- }
- void _cache_addForwardEntry(Class cls, SEL sel)
- {
- cache_entry *smt;
-
- smt = (cache_entry *)malloc(sizeof(cache_entry));
- smt->name = sel;
- smt->imp = _objc_msgForward_impcache;
- if (! _cache_fill(cls, (Method)smt, sel)) {
-
- free(smt);
- }
- }
- void _cache_flush(Class cls)
- {
- Cache cache;
- unsigned int index;
- cacheUpdateLock.assertLocked();
-
- cache = cls->cache;
- if (_cache_isEmpty(cache)) return;
- #ifdef OBJC_INSTRUMENTED
- {
- CacheInstrumentation *cacheData;
-
- cacheData = CACHE_INSTRUMENTATION(cache);
- cacheData->flushCount += 1;
- cacheData->flushedEntries += cache->occupied;
- if (cache->occupied > cacheData->maxFlushedEntries)
- cacheData->maxFlushedEntries = cache->occupied;
- }
- #endif
-
- for (index = 0; index <= cache->mask; index += 1)
- {
-
-
- cache_entry *oldEntry = (cache_entry *)cache->buckets[index];
-
- cache->buckets[index] = NULL;
-
- if (oldEntry && oldEntry->imp == _objc_msgForward_impcache)
- _cache_collect_free (oldEntry, sizeof(cache_entry));
- }
-
- cache->occupied = 0;
- }
- void flush_cache(Class cls)
- {
- if (cls) {
- mutex_locker_t lock(cacheUpdateLock);
- _cache_flush(cls);
- }
- }
- #if !TARGET_OS_WIN32
- #define PC_SENTINEL 1
- #if !__DARWIN_UNIX03
- #define __srr0 srr0
- #define __eip eip
- #endif
- static uintptr_t _get_pc_for_thread(thread_t thread)
- #if defined(__i386__)
- {
- i386_thread_state_t state;
- unsigned int count = i386_THREAD_STATE_COUNT;
- kern_return_t okay = thread_get_state (thread, i386_THREAD_STATE, (thread_state_t)&state, &count);
- return (okay == KERN_SUCCESS) ? state.__eip : PC_SENTINEL;
- }
- #elif defined(__x86_64__)
- {
- x86_thread_state64_t state;
- unsigned int count = x86_THREAD_STATE64_COUNT;
- kern_return_t okay = thread_get_state (thread, x86_THREAD_STATE64, (thread_state_t)&state, &count);
- return (okay == KERN_SUCCESS) ? state.__rip : PC_SENTINEL;
- }
- #elif defined(__arm__)
- {
- arm_thread_state_t state;
- unsigned int count = ARM_THREAD_STATE_COUNT;
- kern_return_t okay = thread_get_state (thread, ARM_THREAD_STATE, (thread_state_t)&state, &count);
- return (okay == KERN_SUCCESS) ? state.__pc : PC_SENTINEL;
- }
- #else
- {
- #error _get_pc_for_thread () not implemented for this architecture
- }
- #endif
- #endif
- extern "C" uintptr_t objc_entryPoints[];
- extern "C" uintptr_t objc_exitPoints[];
- static int _collecting_in_critical(void)
- {
- #if TARGET_OS_WIN32
- return TRUE;
- #else
- thread_act_port_array_t threads;
- unsigned number;
- unsigned count;
- kern_return_t ret;
- int result;
- mach_port_t mythread = pthread_mach_thread_np(pthread_self());
-
- ret = task_threads (mach_task_self (), &threads, &number);
- if (ret != KERN_SUCCESS)
- {
- _objc_fatal("task_thread failed (result %d)\n", ret);
- }
-
- result = FALSE;
- for (count = 0; count < number; count++)
- {
- int region;
- uintptr_t pc;
-
- if (threads[count] == mythread)
- continue;
-
- pc = _get_pc_for_thread (threads[count]);
-
- if (pc == PC_SENTINEL)
- {
- result = TRUE;
- goto done;
- }
-
-
- for (region = 0; objc_entryPoints[region] != 0; region++)
- {
- if ((pc >= objc_entryPoints[region]) &&
- (pc <= objc_exitPoints[region]))
- {
- result = TRUE;
- goto done;
- }
- }
- }
- done:
-
- for (count = 0; count < number; count++) {
- mach_port_deallocate(mach_task_self (), threads[count]);
- }
-
- vm_deallocate (mach_task_self (), (vm_address_t) threads, sizeof(threads[0]) * number);
-
- return result;
- #endif
- }
- static size_t garbage_byte_size = 0;
- static size_t garbage_threshold = 1024;
- static void **garbage_refs = 0;
- static size_t garbage_count = 0;
- static size_t garbage_max = 0;
- enum {
- INIT_GARBAGE_COUNT = 128
- };
- static void _garbage_make_room(void)
- {
- static int first = 1;
-
- if (first)
- {
- first = 0;
- garbage_refs = (void**)
- malloc(INIT_GARBAGE_COUNT * sizeof(void *));
- garbage_max = INIT_GARBAGE_COUNT;
- }
-
- else if (garbage_count == garbage_max)
- {
- garbage_refs = (void**)
- realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
- garbage_max *= 2;
- }
- }
- static void _cache_collect_free(void *data, size_t size)
- {
- cacheUpdateLock.assertLocked();
- _garbage_make_room ();
- garbage_byte_size += size;
- garbage_refs[garbage_count++] = data;
- }
- void _cache_collect(bool collectALot)
- {
- cacheUpdateLock.assertLocked();
-
- if (garbage_byte_size < garbage_threshold && !collectALot) {
- return;
- }
-
- if (!collectALot) {
- if (_collecting_in_critical ()) {
-
-
- if (PrintCaches) {
- _objc_inform ("CACHES: not collecting; "
- "objc_msgSend in progress");
- }
- return;
- }
- }
- else {
-
- while (_collecting_in_critical())
- ;
- }
-
-
- if (PrintCaches) {
- cache_collections++;
- _objc_inform ("CACHES: COLLECTING %zu bytes (%zu regions, %zu allocations, %zu collections)", garbage_byte_size, cache_allocator_regions, cache_allocations, cache_collections);
- }
-
-
- while (garbage_count--) {
- _cache_free_block(garbage_refs[garbage_count]);
- }
-
-
- garbage_count = 0;
- garbage_byte_size = 0;
- if (PrintCaches) {
- size_t i;
- size_t total = 0;
- size_t ideal_total = 0;
- size_t malloc_total = 0;
- size_t local_total = 0;
- for (i = 0; i < sizeof(cache_counts) / sizeof(cache_counts[0]); i++) {
- int count = cache_counts[i];
- int slots = 1 << i;
- size_t size = sizeof(struct objc_cache) + TABLE_SIZE(slots);
- size_t ideal = size;
- #if TARGET_OS_WIN32
- size_t malloc = size;
- #else
- size_t malloc = malloc_good_size(size);
- #endif
- size_t local = size < CACHE_ALLOCATOR_MIN ? malloc : cache_allocator_size_for_mask(cache_allocator_mask_for_size(size));
- if (!count) continue;
- _objc_inform("CACHES: %4d slots: %4d caches, %6zu / %6zu / %6zu bytes ideal/malloc/local, %6zu / %6zu bytes wasted malloc/local", slots, count, ideal*count, malloc*count, local*count, malloc*count-ideal*count, local*count-ideal*count);
- total += count;
- ideal_total += ideal*count;
- malloc_total += malloc*count;
- local_total += local*count;
- }
- _objc_inform("CACHES: total: %4zu caches, %6zu / %6zu / %6zu bytes ideal/malloc/local, %6zu / %6zu bytes wasted malloc/local", total, ideal_total, malloc_total, local_total, malloc_total-ideal_total, local_total-ideal_total);
- }
- }
- #if defined(CACHE_ALLOCATOR)
- typedef struct cache_allocator_block {
- uintptr_t size;
- uintptr_t state;
- struct cache_allocator_block *nextFree;
- } cache_allocator_block;
- typedef struct cache_allocator_region {
- cache_allocator_block *start;
- cache_allocator_block *end;
- cache_allocator_block *freeList;
- struct cache_allocator_region *next;
- } cache_allocator_region;
- static cache_allocator_region *cacheRegion = NULL;
- static cache_allocator_region *cache_allocator_add_region(size_t size)
- {
- vm_address_t addr;
- cache_allocator_block *b;
- cache_allocator_region **rgnP;
- cache_allocator_region *newRegion = (cache_allocator_region *)
- calloc(1, sizeof(cache_allocator_region));
-
- size += CACHE_QUANTUM - (size % CACHE_QUANTUM);
- if (size < CACHE_REGION_SIZE) size = CACHE_REGION_SIZE;
-
- addr = (vm_address_t)calloc(size, 1);
- newRegion->start = (cache_allocator_block *)addr;
- newRegion->end = (cache_allocator_block *)(addr + size);
-
- b = newRegion->start;
- b->size = size;
- b->state = (uintptr_t)-1;
- b->nextFree = NULL;
- newRegion->freeList = b;
-
-
- newRegion->next = NULL;
- rgnP = &cacheRegion;
- while (*rgnP) {
- rgnP = &(**rgnP).next;
- }
- *rgnP = newRegion;
- cache_allocator_regions++;
- return newRegion;
- }
- static void cache_allocator_coalesce(cache_allocator_block *block)
- {
- if (block->size + (uintptr_t)block == (uintptr_t)block->nextFree) {
- block->size += block->nextFree->size;
- block->nextFree = block->nextFree->nextFree;
- }
- }
- static void *cache_region_calloc(cache_allocator_region *rgn, size_t size)
- {
- cache_allocator_block **blockP;
- uintptr_t mask;
-
-
- mask = cache_allocator_mask_for_size(size);
- size = cache_allocator_size_for_mask(mask);
-
- for (blockP = &rgn->freeList;
- *blockP != NULL;
- blockP = &(**blockP).nextFree)
- {
- cache_allocator_block *block = *blockP;
- if (block->size < size) continue;
-
-
-
- if (block->size - size >= CACHE_QUANTUM) {
- cache_allocator_block *leftover =
- (cache_allocator_block *)(size + (uintptr_t)block);
- leftover->size = block->size - size;
- leftover->state = (uintptr_t)-1;
- leftover->nextFree = block->nextFree;
- *blockP = leftover;
- } else {
- *blockP = block->nextFree;
- }
-
-
- bzero(block, size);
- block->size = mask;
- block->state = 0;
- return block;
- }
-
- return NULL;
- }
- static Cache cache_allocator_calloc(size_t size)
- {
- cache_allocator_region *rgn;
- cacheUpdateLock.assertLocked();
- for (rgn = cacheRegion; rgn != NULL; rgn = rgn->next) {
- void *p = cache_region_calloc(rgn, size);
- if (p) {
- return (Cache)p;
- }
- }
-
-
- return (Cache)cache_region_calloc(cache_allocator_add_region(size), size);
- }
- static cache_allocator_region *cache_allocator_region_for_block(cache_allocator_block *block)
- {
- cache_allocator_region *rgn;
- for (rgn = cacheRegion; rgn != NULL; rgn = rgn->next) {
- if (block >= rgn->start && block < rgn->end) return rgn;
- }
- return NULL;
- }
- static bool cache_allocator_is_block(void *ptr)
- {
- cacheUpdateLock.assertLocked();
- return (cache_allocator_region_for_block((cache_allocator_block *)ptr) != NULL);
- }
- static void cache_allocator_free(void *ptr)
- {
- cache_allocator_block *dead = (cache_allocator_block *)ptr;
- cache_allocator_block *cur;
- cache_allocator_region *rgn;
- cacheUpdateLock.assertLocked();
- if (! (rgn = cache_allocator_region_for_block(dead))) {
-
- _objc_inform("cache_allocator_free of non-pointer %p", dead);
- return;
- }
- dead->size = cache_allocator_size_for_mask(dead->size);
- dead->state = (uintptr_t)-1;
- if (!rgn->freeList || rgn->freeList > dead) {
-
- dead->nextFree = rgn->freeList;
- rgn->freeList = dead;
- cache_allocator_coalesce(dead);
- return;
- }
-
- for (cur = rgn->freeList; cur != NULL; cur = cur->nextFree) {
- cache_allocator_block *ahead = cur->nextFree;
-
- if (!ahead || ahead > dead) {
-
- cur->nextFree = dead;
- dead->nextFree = ahead;
-
-
- cache_allocator_coalesce(dead);
- cache_allocator_coalesce(cur);
- return;
- }
- }
-
- _objc_inform("cache_allocator_free of non-pointer %p", ptr);
- }
- #endif
- #ifdef OBJC_INSTRUMENTED
- enum {
- CACHE_HISTOGRAM_SIZE = 512
- };
- unsigned int CacheHitHistogram [CACHE_HISTOGRAM_SIZE];
- unsigned int CacheMissHistogram [CACHE_HISTOGRAM_SIZE];
- #endif
- static void _cache_print(Cache cache)
- {
- uintptr_t index;
- uintptr_t count;
- count = cache->mask + 1;
- for (index = 0; index < count; index += 1) {
- cache_entry *entry = (cache_entry *)cache->buckets[index];
- if (entry) {
- if (entry->imp == _objc_msgForward_impcache)
- printf ("does not recognize: \n");
- printf ("%s\n", sel_getName(entry->name));
- }
- }
- }
- void _class_printMethodCaches(Class cls)
- {
- if (_cache_isEmpty(cls->cache)) {
- printf("no instance-method cache for class %s\n",cls->nameForLogging());
- } else {
- printf("instance-method cache for class %s:\n", cls->nameForLogging());
- _cache_print(cls->cache);
- }
- if (_cache_isEmpty(cls->ISA()->cache)) {
- printf("no class-method cache for class %s\n", cls->nameForLogging());
- } else {
- printf ("class-method cache for class %s:\n", cls->nameForLogging());
- _cache_print(cls->ISA()->cache);
- }
- }
- #if 0
- #warning fixme
- void _class_printDuplicateCacheEntries(bool detail)
- {
- NXHashState state;
- Class cls;
- unsigned int duplicates;
- unsigned int index1;
- unsigned int index2;
- unsigned int mask;
- unsigned int count;
- unsigned int isMeta;
- Cache cache;
- printf ("Checking for duplicate cache entries \n");
-
- state = NXInitHashState (class_hash);
- duplicates = 0;
- while (NXNextHashState (class_hash, &state, (void **) &cls))
- {
-
- for (isMeta = 0; isMeta <= 1; isMeta += 1)
- {
-
- cache = (isMeta ? cls->ISA : cls)->cache;
- if (_cache_isEmpty(cache))
- continue;
-
- mask = cache->mask;
- count = mask + 1;
- for (index1 = 0; index1 < count; index1 += 1)
- {
-
- if (!cache->buckets[index1])
- continue;
-
- for (index2 = index1 + 1; index2 < count; index2 += 1)
- {
-
- if (!cache->buckets[index2])
- continue;
-
- if (strcmp ((char *) cache->buckets[index1]->name),
- (char *) cache->buckets[index2]->name)) == 0)
- {
- if (detail)
- printf ("%s %s\n", cls->nameForLogging(), sel_getName(cache->buckets[index1]->name));
- duplicates += 1;
- break;
- }
- }
- }
- }
- }
-
- printf ("duplicates = %d\n", duplicates);
- printf ("total cache fills = %d\n", totalCacheFills);
- }
- static void PrintCacheHeader(void)
- {
- #ifdef OBJC_INSTRUMENTED
- printf ("Cache Cache Slots Avg Max AvgS MaxS AvgS MaxS TotalD AvgD MaxD TotalD AvgD MaxD TotD AvgD MaxD\n");
- printf ("Size Count Used Used Used Hit Hit Miss Miss Hits Prbs Prbs Misses Prbs Prbs Flsh Flsh Flsh\n");
- printf ("----- ----- ----- ----- ---- ---- ---- ---- ---- ------- ---- ---- ------- ---- ---- ---- ---- ----\n");
- #else
- printf ("Cache Cache Slots Avg Max AvgS MaxS AvgS MaxS\n");
- printf ("Size Count Used Used Used Hit Hit Miss Miss\n");
- printf ("----- ----- ----- ----- ---- ---- ---- ---- ----\n");
- #endif
- }
- static void PrintCacheInfo(unsigned int cacheSize,
- unsigned int cacheCount,
- unsigned int slotsUsed,
- float avgUsed, unsigned int maxUsed,
- float avgSHit, unsigned int maxSHit,
- float avgSMiss, unsigned int maxSMiss
- #ifdef OBJC_INSTRUMENTED
- , unsigned int totDHits,
- float avgDHit,
- unsigned int maxDHit,
- unsigned int totDMisses,
- float avgDMiss,
- unsigned int maxDMiss,
- unsigned int totDFlsh,
- float avgDFlsh,
- unsigned int maxDFlsh
- #endif
- )
- {
- #ifdef OBJC_INSTRUMENTED
- printf ("%5u %5u %5u %5.1f %4u %4.1f %4u %4.1f %4u %7u %4.1f %4u %7u %4.1f %4u %4u %4.1f %4u\n",
- #else
- printf ("%5u %5u %5u %5.1f %4u %4.1f %4u %4.1f %4u\n",
- #endif
- cacheSize, cacheCount, slotsUsed, avgUsed, maxUsed, avgSHit, maxSHit, avgSMiss, maxSMiss
- #ifdef OBJC_INSTRUMENTED
- , totDHits, avgDHit, maxDHit, totDMisses, avgDMiss, maxDMiss, totDFlsh, avgDFlsh, maxDFlsh
- #endif
- );
-
- }
- #ifdef OBJC_INSTRUMENTED
- static void PrintCacheHistogram(char *title,
- unsigned int *firstEntry,
- unsigned int entryCount)
- {
- unsigned int index;
- unsigned int *thisEntry;
- printf ("%s\n", title);
- printf (" Probes Tally\n");
- printf (" ------ -----\n");
- for (index = 0, thisEntry = firstEntry;
- index < entryCount;
- index += 1, thisEntry += 1)
- {
- if (*thisEntry == 0)
- continue;
- printf (" %6d %5d\n", index, *thisEntry);
- }
- }
- #endif
- #define MAX_LOG2_SIZE 32
- #define MAX_CHAIN_SIZE 100
- void _class_printMethodCacheStatistics(void)
- {
- unsigned int isMeta;
- unsigned int index;
- NXHashState state;
- Class cls;
- unsigned int totalChain;
- unsigned int totalMissChain;
- unsigned int maxChain;
- unsigned int maxMissChain;
- unsigned int classCount;
- unsigned int negativeEntryCount;
- unsigned int cacheExpandCount;
- unsigned int cacheCountBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int totalEntriesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxEntriesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int totalChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int totalMissChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int totalMaxChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int totalMaxMissChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxMissChainBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int chainCount[MAX_CHAIN_SIZE] = {0};
- unsigned int missChainCount[MAX_CHAIN_SIZE] = {0};
- #ifdef OBJC_INSTRUMENTED
- unsigned int hitCountBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int hitProbesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxHitProbesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int missCountBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int missProbesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxMissProbesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int flushCountBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int flushedEntriesBySize[2][MAX_LOG2_SIZE] = {{0}};
- unsigned int maxFlushedEntriesBySize[2][MAX_LOG2_SIZE] = {{0}};
- #endif
- printf ("Printing cache statistics\n");
-
- state = NXInitHashState (class_hash);
- classCount = 0;
- negativeEntryCount = 0;
- cacheExpandCount = 0;
- while (NXNextHashState (class_hash, &state, (void **) &cls))
- {
-
- classCount += 1;
-
- for (isMeta = 0; isMeta <= 1; isMeta += 1)
- {
- Cache cache;
- unsigned int mask;
- unsigned int log2Size;
- unsigned int entryCount;
-
- cache = (isMeta ? cls->ISA : cls)->cache;
-
- if (_cache_isEmpty(cache))
- continue;
-
- mask = cache->mask;
- entryCount = 0;
- totalChain = 0;
- totalMissChain = 0;
- maxChain = 0;
- maxMissChain = 0;
- for (index = 0; index < mask + 1; index += 1)
- {
- cache_entry **buckets;
- cache_entry *entry;
- unsigned int hash;
- unsigned int methodChain;
- unsigned int methodMissChain;
- unsigned int index2;
-
-
-
- buckets = (cache_entry **)cache->buckets;
- if (!buckets[index])
- {
- missChainCount[0] += 1;
- continue;
- }
- entry = buckets[index];
-
- entryCount += 1;
-
- if (entry->imp == _objc_msgForward_impcache)
- negativeEntryCount += 1;
-
-
- hash = CACHE_HASH(entry->name, mask);
- if (index >= hash) methodChain = index - hash;
- else methodChain = (mask+1) + index - hash;
-
- if (methodChain < MAX_CHAIN_SIZE)
- chainCount[methodChain] += 1;
-
- totalChain += methodChain;
-
- if (methodChain > maxChain)
- maxChain = methodChain;
-
- index2 = index;
- while (buckets[index2])
- {
- index2 += 1;
- index2 &= mask;
- }
- methodMissChain = ((index2 - index) & mask);
-
- if (methodMissChain < MAX_CHAIN_SIZE)
- missChainCount[methodMissChain] += 1;
-
- totalMissChain += methodMissChain;
-
- if (methodMissChain > maxMissChain)
- maxMissChain = methodMissChain;
- }
-
-
- log2Size = log2u (mask + 1);
- cacheCountBySize[isMeta][log2Size] += 1;
- totalEntriesBySize[isMeta][log2Size] += entryCount;
- if (entryCount > maxEntriesBySize[isMeta][log2Size])
- maxEntriesBySize[isMeta][log2Size] = entryCount;
- totalChainBySize[isMeta][log2Size] += totalChain;
- totalMissChainBySize[isMeta][log2Size] += totalMissChain;
- totalMaxChainBySize[isMeta][log2Size] += maxChain;
- totalMaxMissChainBySize[isMeta][log2Size] += maxMissChain;
- if (maxChain > maxChainBySize[isMeta][log2Size])
- maxChainBySize[isMeta][log2Size] = maxChain;
- if (maxMissChain > maxMissChainBySize[isMeta][log2Size])
- maxMissChainBySize[isMeta][log2Size] = maxMissChain;
- #ifdef OBJC_INSTRUMENTED
- {
- CacheInstrumentation *cacheData;
- cacheData = CACHE_INSTRUMENTATION(cache);
- hitCountBySize[isMeta][log2Size] += cacheData->hitCount;
- hitProbesBySize[isMeta][log2Size] += cacheData->hitProbes;
- if (cacheData->maxHitProbes > maxHitProbesBySize[isMeta][log2Size])
- maxHitProbesBySize[isMeta][log2Size] = cacheData->maxHitProbes;
- missCountBySize[isMeta][log2Size] += cacheData->missCount;
- missProbesBySize[isMeta][log2Size] += cacheData->missProbes;
- if (cacheData->maxMissProbes > maxMissProbesBySize[isMeta][log2Size])
- maxMissProbesBySize[isMeta][log2Size] = cacheData->maxMissProbes;
- flushCountBySize[isMeta][log2Size] += cacheData->flushCount;
- flushedEntriesBySize[isMeta][log2Size] += cacheData->flushedEntries;
- if (cacheData->maxFlushedEntries > maxFlushedEntriesBySize[isMeta][log2Size])
- maxFlushedEntriesBySize[isMeta][log2Size] = cacheData->maxFlushedEntries;
- }
- #endif
-
-
- cacheExpandCount += log2Size - INIT_CACHE_SIZE_LOG2;
- }
- }
- {
- unsigned int cacheCountByType[2] = {0};
- unsigned int totalCacheCount = 0;
- unsigned int totalEntries = 0;
- unsigned int maxEntries = 0;
- unsigned int totalSlots = 0;
- #ifdef OBJC_INSTRUMENTED
- unsigned int totalHitCount = 0;
- unsigned int totalHitProbes = 0;
- unsigned int maxHitProbes = 0;
- unsigned int totalMissCount = 0;
- unsigned int totalMissProbes = 0;
- unsigned int maxMissProbes = 0;
- unsigned int totalFlushCount = 0;
- unsigned int totalFlushedEntries = 0;
- unsigned int maxFlushedEntries = 0;
- #endif
- totalChain = 0;
- maxChain = 0;
- totalMissChain = 0;
- maxMissChain = 0;
-
- for (isMeta = 0; isMeta <= 1; isMeta += 1)
- {
- for (index = 0; index < MAX_LOG2_SIZE; index += 1)
- {
- cacheCountByType[isMeta] += cacheCountBySize[isMeta][index];
- totalEntries += totalEntriesBySize[isMeta][index];
- totalSlots += cacheCountBySize[isMeta][index] * (1 << index);
- totalChain += totalChainBySize[isMeta][index];
- if (maxEntriesBySize[isMeta][index] > maxEntries)
- maxEntries = maxEntriesBySize[isMeta][index];
- if (maxChainBySize[isMeta][index] > maxChain)
- maxChain = maxChainBySize[isMeta][index];
- totalMissChain += totalMissChainBySize[isMeta][index];
- if (maxMissChainBySize[isMeta][index] > maxMissChain)
- maxMissChain = maxMissChainBySize[isMeta][index];
- #ifdef OBJC_INSTRUMENTED
- totalHitCount += hitCountBySize[isMeta][index];
- totalHitProbes += hitProbesBySize[isMeta][index];
- if (maxHitProbesBySize[isMeta][index] > maxHitProbes)
- maxHitProbes = maxHitProbesBySize[isMeta][index];
- totalMissCount += missCountBySize[isMeta][index];
- totalMissProbes += missProbesBySize[isMeta][index];
- if (maxMissProbesBySize[isMeta][index] > maxMissProbes)
- maxMissProbes = maxMissProbesBySize[isMeta][index];
- totalFlushCount += flushCountBySize[isMeta][index];
- totalFlushedEntries += flushedEntriesBySize[isMeta][index];
- if (maxFlushedEntriesBySize[isMeta][index] > maxFlushedEntries)
- maxFlushedEntries = maxFlushedEntriesBySize[isMeta][index];
- #endif
- }
- totalCacheCount += cacheCountByType[isMeta];
- }
-
- printf ("There are %u classes\n", classCount);
- for (isMeta = 0; isMeta <= 1; isMeta += 1)
- {
-
- printf ("\nThere are %u %s-method caches, broken down by size (slot count):\n",
- cacheCountByType[isMeta],
- isMeta ? "class" : "instance");
-
- PrintCacheHeader ();
-
- if (cacheCountByType[isMeta] == 0)
- {
- printf ("(none)\n");
- continue;
- }
-
- for (index = 0; index < MAX_LOG2_SIZE; index += 1)
- {
- unsigned int cacheCount;
- unsigned int cacheSlotCount;
- unsigned int cacheEntryCount;
-
- cacheCount = cacheCountBySize[isMeta][index];
- if (cacheCount == 0)
- continue;
-
- cacheSlotCount = (1 << index);
- cacheEntryCount = totalEntriesBySize[isMeta][index];
-
- PrintCacheInfo (cacheSlotCount,
- cacheCount,
- cacheEntryCount,
- (float) cacheEntryCount / (float) cacheCount,
- maxEntriesBySize[isMeta][index],
- (float) totalChainBySize[isMeta][index] / (float) cacheEntryCount,
- maxChainBySize[isMeta][index],
- (float) totalMissChainBySize[isMeta][index] / (float) (cacheCount * cacheSlotCount),
- maxMissChainBySize[isMeta][index]
- #ifdef OBJC_INSTRUMENTED
- , hitCountBySize[isMeta][index],
- hitCountBySize[isMeta][index] ?
- (float) hitProbesBySize[isMeta][index] / (float) hitCountBySize[isMeta][index] : 0.0,
- maxHitProbesBySize[isMeta][index],
- missCountBySize[isMeta][index],
- missCountBySize[isMeta][index] ?
- (float) missProbesBySize[isMeta][index] / (float) missCountBySize[isMeta][index] : 0.0,
- maxMissProbesBySize[isMeta][index],
- flushCountBySize[isMeta][index],
- flushCountBySize[isMeta][index] ?
- (float) flushedEntriesBySize[isMeta][index] / (float) flushCountBySize[isMeta][index] : 0.0,
- maxFlushedEntriesBySize[isMeta][index]
- #endif
- );
- }
- }
-
- printf ("\nCumulative:\n");
- PrintCacheHeader ();
- PrintCacheInfo (totalSlots,
- totalCacheCount,
- totalEntries,
- (float) totalEntries / (float) totalCacheCount,
- maxEntries,
- (float) totalChain / (float) totalEntries,
- maxChain,
- (float) totalMissChain / (float) totalSlots,
- maxMissChain
- #ifdef OBJC_INSTRUMENTED
- , totalHitCount,
- totalHitCount ?
- (float) totalHitProbes / (float) totalHitCount : 0.0,
- maxHitProbes,
- totalMissCount,
- totalMissCount ?
- (float) totalMissProbes / (float) totalMissCount : 0.0,
- maxMissProbes,
- totalFlushCount,
- totalFlushCount ?
- (float) totalFlushedEntries / (float) totalFlushCount : 0.0,
- maxFlushedEntries
- #endif
- );
- printf ("\nNumber of \"forward::\" entries: %d\n", negativeEntryCount);
- printf ("Number of cache expansions: %d\n", cacheExpandCount);
- #ifdef OBJC_INSTRUMENTED
- printf ("flush_caches: total calls total visits average visits max visits total classes visits/class\n");
- printf (" ----------- ------------ -------------- ---------- ------------- -------------\n");
- printf (" linear %11u %12u %14.1f %10u %13u %12.2f\n",
- LinearFlushCachesCount,
- LinearFlushCachesVisitedCount,
- LinearFlushCachesCount ?
- (float) LinearFlushCachesVisitedCount / (float) LinearFlushCachesCount : 0.0,
- MaxLinearFlushCachesVisitedCount,
- LinearFlushCachesVisitedCount,
- 1.0);
- printf (" nonlinear %11u %12u %14.1f %10u %13u %12.2f\n",
- NonlinearFlushCachesCount,
- NonlinearFlushCachesVisitedCount,
- NonlinearFlushCachesCount ?
- (float) NonlinearFlushCachesVisitedCount / (float) NonlinearFlushCachesCount : 0.0,
- MaxNonlinearFlushCachesVisitedCount,
- NonlinearFlushCachesClassCount,
- NonlinearFlushCachesClassCount ?
- (float) NonlinearFlushCachesVisitedCount / (float) NonlinearFlushCachesClassCount : 0.0);
- printf (" ideal %11u %12u %14.1f %10u %13u %12.2f\n",
- LinearFlushCachesCount + NonlinearFlushCachesCount,
- IdealFlushCachesCount,
- LinearFlushCachesCount + NonlinearFlushCachesCount ?
- (float) IdealFlushCachesCount / (float) (LinearFlushCachesCount + NonlinearFlushCachesCount) : 0.0,
- MaxIdealFlushCachesCount,
- LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount,
- LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount ?
- (float) IdealFlushCachesCount / (float) (LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount) : 0.0);
- PrintCacheHistogram ("\nCache hit histogram:", &CacheHitHistogram[0], CACHE_HISTOGRAM_SIZE);
- PrintCacheHistogram ("\nCache miss histogram:", &CacheMissHistogram[0], CACHE_HISTOGRAM_SIZE);
- #endif
- #if 0
- printf ("\nLookup chains:");
- for (index = 0; index < MAX_CHAIN_SIZE; index += 1)
- {
- if (chainCount[index] != 0)
- printf (" %u:%u", index, chainCount[index]);
- }
- printf ("\nMiss chains:");
- for (index = 0; index < MAX_CHAIN_SIZE; index += 1)
- {
- if (missChainCount[index] != 0)
- printf (" %u:%u", index, missChainCount[index]);
- }
- printf ("\nTotal memory usage for cache data structures: %lu bytes\n",
- totalCacheCount * (sizeof(struct objc_cache) - sizeof(cache_entry *)) +
- totalSlots * sizeof(cache_entry *) +
- negativeEntryCount * sizeof(cache_entry));
- #endif
- }
- }
- #endif
- #endif
|