objc-shared-cache.h 56 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623
  1. /*
  2. * Copyright (c) 2008 Apple Inc. All rights reserved.
  3. *
  4. * @APPLE_LICENSE_HEADER_START@
  5. *
  6. * This file contains Original Code and/or Modifications of Original Code
  7. * as defined in and that are subject to the Apple Public Source License
  8. * Version 2.0 (the 'License'). You may not use this file except in
  9. * compliance with the License. Please obtain a copy of the License at
  10. * http://www.opensource.apple.com/apsl/ and read it before using this
  11. * file.
  12. *
  13. * The Original Code and all software distributed under the License are
  14. * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15. * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16. * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17. * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18. * Please see the License for the specific language governing rights and
  19. * limitations under the License.
  20. *
  21. * @APPLE_LICENSE_HEADER_END@
  22. */
  23. /*
  24. Portions derived from:
  25. --------------------------------------------------------------------
  26. lookup8.c, by Bob Jenkins, January 4 1997, Public Domain.
  27. hash(), hash2(), hash3, and mix() are externally useful functions.
  28. Routines to test the hash are included if SELF_TEST is defined.
  29. You can use this free for any purpose. It has no warranty.
  30. --------------------------------------------------------------------
  31. ------------------------------------------------------------------------------
  32. perfect.c: code to generate code for a hash for perfect hashing.
  33. (c) Bob Jenkins, September 1996, December 1999
  34. You may use this code in any way you wish, and it is free. No warranty.
  35. I hereby place this in the public domain.
  36. Source is http://burtleburtle.net/bob/c/perfect.c
  37. ------------------------------------------------------------------------------
  38. */
  39. /*
  40. * objc-selopt.h
  41. * Interface between libobjc and dyld
  42. * for selector uniquing in the dyld shared cache.
  43. *
  44. * When building the shared cache, dyld locates all selectors and selector
  45. * references in the cached images. It builds a perfect hash table out of
  46. * them and writes the table into the shared cache copy of libobjc.
  47. * libobjc then uses that table as the builtin selector list.
  48. *
  49. * Versioning
  50. * The table has a version number. dyld and objc can both ignore the table
  51. * if the other used the wrong version number.
  52. *
  53. * Completeness
  54. * Not all libraries are in the shared cache. Libraries that are in the
  55. * shared cache and were optimized are specially marked. Libraries on
  56. * disk never include those marks.
  57. *
  58. * Coherency
  59. * Libraries optimized in the shared cache can be replaced by unoptimized
  60. * copies from disk when loaded. The copy from disk is not marked and will
  61. * be fixed up by libobjc. The shared cache copy is still mapped into the
  62. * process, so the table can point to cstring data in that library's part
  63. * of the shared cache without trouble.
  64. *
  65. * Atomicity
  66. * dyld writes the table itself last. If dyld marks some metadata as
  67. * updated but then fails to write a table for some reason, libobjc
  68. * fixes up all metadata as if it were not marked.
  69. */
  70. #ifndef _OBJC_SELOPT_H
  71. #define _OBJC_SELOPT_H
  72. /*
  73. DO NOT INCLUDE ANY objc HEADERS HERE
  74. dyld USES THIS FILE AND CANNOT SEE THEM
  75. */
  76. #include <stdint.h>
  77. #include <stdlib.h>
  78. #ifdef CLOSURE_SELOPT_WRITE
  79. #include "Array.h"
  80. #include "Map.h"
  81. #endif
  82. #ifdef SELOPT_WRITE
  83. #include <unordered_map>
  84. #endif
  85. /*
  86. DO NOT INCLUDE ANY objc HEADERS HERE
  87. dyld USES THIS FILE AND CANNOT SEE THEM
  88. */
  89. #ifndef STATIC_ASSERT
  90. # define STATIC_ASSERT(x) _STATIC_ASSERT2(x, __LINE__)
  91. # define _STATIC_ASSERT2(x, line) _STATIC_ASSERT3(x, line)
  92. # define _STATIC_ASSERT3(x, line) \
  93. typedef struct { \
  94. int _static_assert[(x) ? 0 : -1]; \
  95. } _static_assert_ ## line __attribute__((unavailable))
  96. #endif
  97. #define SELOPT_DEBUG 0
  98. #define S32(x) x = little_endian ? OSSwapHostToLittleInt32(x) : OSSwapHostToBigInt32(x)
  99. #define S64(x) x = little_endian ? OSSwapHostToLittleInt64(x) : OSSwapHostToBigInt64(x)
  100. namespace objc_opt {
  101. typedef int32_t objc_stringhash_offset_t;
  102. typedef uint8_t objc_stringhash_check_t;
  103. static uint64_t lookup8( uint8_t *k, size_t length, uint64_t level);
  104. #if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
  105. // Perfect hash code is at the end of this file.
  106. struct __attribute__((packed)) perfect_hash {
  107. uint32_t capacity;
  108. uint32_t occupied;
  109. uint32_t shift;
  110. uint32_t mask;
  111. uint64_t salt;
  112. uint32_t scramble[256];
  113. dyld3::OverflowSafeArray<uint8_t> tab; // count == mask+1
  114. perfect_hash() { }
  115. ~perfect_hash() { }
  116. };
  117. struct eqstr {
  118. bool operator()(const char* s1, const char* s2) const {
  119. return strcmp(s1, s2) == 0;
  120. }
  121. };
  122. struct hashstr {
  123. size_t operator()(const char *s) const {
  124. return (size_t)lookup8((uint8_t *)s, strlen(s), 0);
  125. }
  126. };
  127. #endif // defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
  128. #ifdef SELOPT_WRITE
  129. // cstring => cstring's vmaddress
  130. // (used for selector names and class names)
  131. typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> string_map;
  132. // protocol name => protocol vmaddress
  133. typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> legacy_protocol_map;
  134. // protocol name => (protocol vmaddress, header_info vmaddress)
  135. typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> protocol_map;
  136. // class name => (class vmaddress, header_info vmaddress)
  137. typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> class_map;
  138. static void make_perfect(const string_map& strings, perfect_hash& phash);
  139. #endif // defined(SELOPT_WRITE)
  140. // Precomputed perfect hash table of strings.
  141. // Base class for precomputed selector table and class table.
  142. // Edit objc-sel-table.s if you change this structure.
  143. struct __attribute__((packed)) objc_stringhash_t {
  144. uint32_t capacity;
  145. uint32_t occupied;
  146. uint32_t shift;
  147. uint32_t mask;
  148. uint32_t unused1; // was zero
  149. uint32_t unused2; // alignment pad
  150. uint64_t salt;
  151. uint32_t scramble[256];
  152. uint8_t tab[0]; /* tab[mask+1] (always power-of-2) */
  153. // uint8_t checkbytes[capacity]; /* check byte for each string */
  154. // int32_t offsets[capacity]; /* offsets from &capacity to cstrings */
  155. objc_stringhash_check_t *checkbytes() { return (objc_stringhash_check_t *)&tab[mask+1]; }
  156. const objc_stringhash_check_t *checkbytes() const { return (const objc_stringhash_check_t *)&tab[mask+1]; }
  157. objc_stringhash_offset_t *offsets() { return (objc_stringhash_offset_t *)&checkbytes()[capacity]; }
  158. const objc_stringhash_offset_t *offsets() const { return (const objc_stringhash_offset_t *)&checkbytes()[capacity]; }
  159. uint32_t hash(const char *key, size_t keylen) const
  160. {
  161. uint64_t val = lookup8((uint8_t*)key, keylen, salt);
  162. uint32_t index = (uint32_t)(val>>shift) ^ scramble[tab[val&mask]];
  163. return index;
  164. }
  165. uint32_t hash(const char *key) const
  166. {
  167. return hash(key, strlen(key));
  168. }
  169. // The check bytes areused to reject strings that aren't in the table
  170. // without paging in the table's cstring data. This checkbyte calculation
  171. // catches 4785/4815 rejects when launching Safari; a perfect checkbyte
  172. // would catch 4796/4815.
  173. objc_stringhash_check_t checkbyte(const char *key, size_t keylen) const
  174. {
  175. return
  176. ((key[0] & 0x7) << 5)
  177. |
  178. ((uint8_t)keylen & 0x1f);
  179. }
  180. objc_stringhash_check_t checkbyte(const char *key) const
  181. {
  182. return checkbyte(key, strlen(key));
  183. }
  184. #define INDEX_NOT_FOUND (~(uint32_t)0)
  185. uint32_t getIndex(const char *key) const
  186. {
  187. size_t keylen = strlen(key);
  188. uint32_t h = hash(key, keylen);
  189. // Use check byte to reject without paging in the table's cstrings
  190. objc_stringhash_check_t h_check = checkbytes()[h];
  191. objc_stringhash_check_t key_check = checkbyte(key, keylen);
  192. bool check_fail = (h_check != key_check);
  193. #if ! SELOPT_DEBUG
  194. if (check_fail) return INDEX_NOT_FOUND;
  195. #endif
  196. objc_stringhash_offset_t offset = offsets()[h];
  197. if (offset == 0) return INDEX_NOT_FOUND;
  198. const char *result = (const char *)this + offset;
  199. if (0 != strcmp(key, result)) return INDEX_NOT_FOUND;
  200. #if SELOPT_DEBUG
  201. if (check_fail) abort();
  202. #endif
  203. return h;
  204. }
  205. #ifdef SELOPT_WRITE
  206. size_t size()
  207. {
  208. return sizeof(objc_stringhash_t)
  209. + mask+1
  210. + capacity * sizeof(objc_stringhash_check_t)
  211. + capacity * sizeof(objc_stringhash_offset_t);
  212. }
  213. void byteswap(bool little_endian)
  214. {
  215. // tab and checkbytes are arrays of bytes, no swap needed
  216. for (uint32_t i = 0; i < 256; i++) {
  217. S32(scramble[i]);
  218. }
  219. objc_stringhash_offset_t *o = offsets();
  220. for (uint32_t i = 0; i < capacity; i++) {
  221. S32(o[i]);
  222. }
  223. S32(capacity);
  224. S32(occupied);
  225. S32(shift);
  226. S32(mask);
  227. S64(salt);
  228. }
  229. const char *write(uint64_t base, size_t remaining, string_map& strings)
  230. {
  231. if (sizeof(objc_stringhash_t) > remaining) {
  232. return "selector section too small (metadata not optimized)";
  233. }
  234. if (strings.size() == 0) {
  235. bzero(this, sizeof(objc_stringhash_t));
  236. return NULL;
  237. }
  238. perfect_hash phash;
  239. make_perfect(strings, phash);
  240. if (phash.capacity == 0) {
  241. return "perfect hash failed (metadata not optimized)";
  242. }
  243. // Set header
  244. capacity = phash.capacity;
  245. occupied = phash.occupied;
  246. shift = phash.shift;
  247. mask = phash.mask;
  248. unused1 = 0;
  249. unused2 = 0;
  250. salt = phash.salt;
  251. if (size() > remaining) {
  252. return "selector section too small (metadata not optimized)";
  253. }
  254. // Set hash data
  255. for (uint32_t i = 0; i < 256; i++) {
  256. scramble[i] = phash.scramble[i];
  257. }
  258. for (uint32_t i = 0; i < phash.mask+1; i++) {
  259. tab[i] = phash.tab[i];
  260. }
  261. // Set offsets to 0
  262. for (uint32_t i = 0; i < phash.capacity; i++) {
  263. offsets()[i] = 0;
  264. }
  265. // Set checkbytes to 0
  266. for (uint32_t i = 0; i < phash.capacity; i++) {
  267. checkbytes()[i] = 0;
  268. }
  269. // Set real string offsets and checkbytes
  270. # define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
  271. string_map::const_iterator s;
  272. for (s = strings.begin(); s != strings.end(); ++s) {
  273. int64_t offset = s->second - base;
  274. if ((offset<<SHIFT)>>SHIFT != offset) {
  275. return "selector offset too big (metadata not optimized)";
  276. }
  277. uint32_t h = hash(s->first);
  278. offsets()[h] = (objc_stringhash_offset_t)offset;
  279. checkbytes()[h] = checkbyte(s->first);
  280. }
  281. # undef SHIFT
  282. return NULL;
  283. }
  284. // SELOPT_WRITE
  285. #endif
  286. };
  287. // Precomputed selector table.
  288. // Edit objc-sel-table.s if you change this structure.
  289. struct objc_selopt_t : objc_stringhash_t {
  290. const char* getEntryForIndex(uint32_t index) const {
  291. return (const char *)this + offsets()[index];
  292. }
  293. uint32_t getIndexForKey(const char *key) const {
  294. return getIndex(key);
  295. }
  296. uint32_t getSentinelIndex() const {
  297. return INDEX_NOT_FOUND;
  298. }
  299. const char* get(const char *key) const
  300. {
  301. uint32_t h = getIndex(key);
  302. if (h == INDEX_NOT_FOUND) return NULL;
  303. return getEntryForIndex(h);
  304. }
  305. size_t usedCount() const {
  306. return capacity;
  307. }
  308. };
  309. // Precomputed class list.
  310. // Edit objc-sel-table.s if you change these structures.
  311. struct objc_classheader_t {
  312. objc_stringhash_offset_t clsOffset;
  313. objc_stringhash_offset_t hiOffset;
  314. // For duplicate class names:
  315. // clsOffset = count<<1 | 1
  316. // duplicated classes are duplicateOffsets[hiOffset..hiOffset+count-1]
  317. bool isDuplicate() const { return clsOffset & 1; }
  318. uint32_t duplicateCount() const { return clsOffset >> 1; }
  319. uint32_t duplicateIndex() const { return hiOffset; }
  320. };
  321. struct objc_clsopt_t : objc_stringhash_t {
  322. // ...objc_stringhash_t fields...
  323. // objc_classheader_t classOffsets[capacity]; /* offsets from &capacity to class_t and header_info */
  324. // uint32_t duplicateCount;
  325. // objc_classheader_t duplicateOffsets[duplicatedClasses];
  326. objc_classheader_t *classOffsets() { return (objc_classheader_t *)&offsets()[capacity]; }
  327. const objc_classheader_t *classOffsets() const { return (const objc_classheader_t *)&offsets()[capacity]; }
  328. uint32_t& duplicateCount() { return *(uint32_t *)&classOffsets()[capacity]; }
  329. const uint32_t& duplicateCount() const { return *(const uint32_t *)&classOffsets()[capacity]; }
  330. objc_classheader_t *duplicateOffsets() { return (objc_classheader_t *)(&duplicateCount()+1); }
  331. const objc_classheader_t *duplicateOffsets() const { return (const objc_classheader_t *)(&duplicateCount()+1); }
  332. const char* getClassNameForIndex(uint32_t index) const {
  333. return (const char *)this + offsets()[index];
  334. }
  335. void* getClassForIndex(uint32_t index, uint32_t duplicateIndex) const {
  336. const objc_classheader_t& clshi = classOffsets()[index];
  337. if (! clshi.isDuplicate()) {
  338. // class appears in exactly one header
  339. return (void *)((const char *)this + clshi.clsOffset);
  340. }
  341. else {
  342. // class appears in more than one header - use getClassesAndHeaders
  343. const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
  344. return (void *)((const char *)this + list[duplicateIndex].clsOffset);
  345. }
  346. }
  347. // 0/NULL/NULL: not found
  348. // 1/ptr/ptr: found exactly one
  349. // n/NULL/NULL: found N - use getClassesAndHeaders() instead
  350. uint32_t getClassHeaderAndIndex(const char *key, void*& cls, void*& hi, uint32_t& index) const
  351. {
  352. uint32_t h = getIndex(key);
  353. if (h == INDEX_NOT_FOUND) {
  354. cls = NULL;
  355. hi = NULL;
  356. index = 0;
  357. return 0;
  358. }
  359. index = h;
  360. const objc_classheader_t& clshi = classOffsets()[h];
  361. if (! clshi.isDuplicate()) {
  362. // class appears in exactly one header
  363. cls = (void *)((const char *)this + clshi.clsOffset);
  364. hi = (void *)((const char *)this + clshi.hiOffset);
  365. return 1;
  366. }
  367. else {
  368. // class appears in more than one header - use getClassesAndHeaders
  369. cls = NULL;
  370. hi = NULL;
  371. return clshi.duplicateCount();
  372. }
  373. }
  374. void getClassesAndHeaders(const char *key, void **cls, void **hi) const
  375. {
  376. uint32_t h = getIndex(key);
  377. if (h == INDEX_NOT_FOUND) return;
  378. const objc_classheader_t& clshi = classOffsets()[h];
  379. if (! clshi.isDuplicate()) {
  380. // class appears in exactly one header
  381. cls[0] = (void *)((const char *)this + clshi.clsOffset);
  382. hi[0] = (void *)((const char *)this + clshi.hiOffset);
  383. }
  384. else {
  385. // class appears in more than one header
  386. uint32_t count = clshi.duplicateCount();
  387. const objc_classheader_t *list =
  388. &duplicateOffsets()[clshi.duplicateIndex()];
  389. for (uint32_t i = 0; i < count; i++) {
  390. cls[i] = (void *)((const char *)this + list[i].clsOffset);
  391. hi[i] = (void *)((const char *)this + list[i].hiOffset);
  392. }
  393. }
  394. }
  395. // 0/NULL/NULL: not found
  396. // 1/ptr/ptr: found exactly one
  397. // n/NULL/NULL: found N - use getClassesAndHeaders() instead
  398. uint32_t getClassAndHeader(const char *key, void*& cls, void*& hi) const
  399. {
  400. uint32_t unusedIndex = 0;
  401. return getClassHeaderAndIndex(key, cls, hi, unusedIndex);
  402. }
  403. #ifdef SELOPT_WRITE
  404. size_t size()
  405. {
  406. return
  407. objc_stringhash_t::size()
  408. + capacity * sizeof(objc_classheader_t)
  409. + sizeof(duplicateCount())
  410. + duplicateCount() * sizeof(objc_classheader_t);
  411. }
  412. size_t sizeWithoutDups()
  413. {
  414. return
  415. objc_stringhash_t::size()
  416. + capacity * sizeof(objc_classheader_t);
  417. }
  418. void byteswap(bool little_endian)
  419. {
  420. objc_classheader_t *o;
  421. o = classOffsets();
  422. for (uint32_t i = 0; i < capacity; i++) {
  423. S32(o[i].clsOffset);
  424. S32(o[i].hiOffset);
  425. }
  426. o = duplicateOffsets();
  427. for (uint32_t i = 0; i < duplicateCount(); i++) {
  428. S32(o[i].clsOffset);
  429. S32(o[i].hiOffset);
  430. }
  431. S32(duplicateCount());
  432. objc_stringhash_t::byteswap(little_endian);
  433. }
  434. const char *write(uint64_t base, size_t remaining,
  435. string_map& strings, class_map& classes, bool verbose)
  436. {
  437. const char *err;
  438. err = objc_stringhash_t::write(base, remaining, strings);
  439. if (err) return err;
  440. if (sizeWithoutDups() > remaining) {
  441. return "selector section too small (metadata not optimized)";
  442. }
  443. if (size() > remaining) {
  444. return "selector section too small (metadata not optimized)";
  445. }
  446. // Set class offsets to 0
  447. for (uint32_t i = 0; i < capacity; i++) {
  448. classOffsets()[i].clsOffset = 0;
  449. classOffsets()[i].hiOffset = 0;
  450. }
  451. // Set real class offsets
  452. # define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
  453. class_map::const_iterator c;
  454. for (c = classes.begin(); c != classes.end(); ++c) {
  455. uint32_t h = getIndex(c->first);
  456. if (h == INDEX_NOT_FOUND) {
  457. return "class list busted (metadata not optimized)";
  458. }
  459. if (classOffsets()[h].clsOffset != 0) {
  460. // already did this class
  461. continue;
  462. }
  463. uint32_t count = (uint32_t)classes.count(c->first);
  464. if (count == 1) {
  465. // only one class with this name
  466. int64_t coff = c->second.first - base;
  467. int64_t hoff = c->second.second - base;
  468. if ((coff<<SHIFT)>>SHIFT != coff) {
  469. return "class offset too big (metadata not optimized)";
  470. }
  471. if ((hoff<<SHIFT)>>SHIFT != hoff) {
  472. return "header offset too big (metadata not optimized)";
  473. }
  474. classOffsets()[h].clsOffset = (objc_stringhash_offset_t)coff;
  475. classOffsets()[h].hiOffset = (objc_stringhash_offset_t)hoff;
  476. }
  477. else {
  478. // class name has duplicates - write them all now
  479. if (verbose) {
  480. fprintf(stderr, "update_dyld_shared_cache: %u duplicates of Objective-C class %s\n", count, c->first);
  481. }
  482. uint32_t dest = duplicateCount();
  483. duplicateCount() += count;
  484. if (size() > remaining) {
  485. return "selector section too small (metadata not optimized)";
  486. }
  487. // classOffsets() instead contains count and array index
  488. classOffsets()[h].clsOffset = count*2 + 1;
  489. classOffsets()[h].hiOffset = dest;
  490. std::pair<class_map::const_iterator, class_map::const_iterator>
  491. duplicates = classes.equal_range(c->first);
  492. class_map::const_iterator dup;
  493. for (dup = duplicates.first; dup != duplicates.second; ++dup) {
  494. int64_t coff = dup->second.first - base;
  495. int64_t hoff = dup->second.second - base;
  496. if ((coff<<SHIFT)>>SHIFT != coff) {
  497. return "class offset too big (metadata not optimized)";
  498. }
  499. if ((hoff<<SHIFT)>>SHIFT != hoff) {
  500. return "header offset too big (metadata not optimized)";
  501. }
  502. duplicateOffsets()[dest].clsOffset = (objc_stringhash_offset_t)coff;
  503. duplicateOffsets()[dest].hiOffset = (objc_stringhash_offset_t)hoff;
  504. dest++;
  505. }
  506. }
  507. }
  508. # undef SHIFT
  509. return NULL;
  510. }
  511. // SELOPT_WRITE
  512. #endif
  513. };
  514. struct objc_protocolopt_t : objc_stringhash_t {
  515. // ...objc_stringhash_t fields...
  516. // uint32_t protocolOffsets[capacity]; /* offsets from &capacity to protocol_t */
  517. objc_stringhash_offset_t *protocolOffsets() { return (objc_stringhash_offset_t *)&offsets()[capacity]; }
  518. const objc_stringhash_offset_t *protocolOffsets() const { return (const objc_stringhash_offset_t *)&offsets()[capacity]; }
  519. void* getProtocol(const char *key) const
  520. {
  521. uint32_t h = getIndex(key);
  522. if (h == INDEX_NOT_FOUND) {
  523. return NULL;
  524. }
  525. return (void *)((const char *)this + protocolOffsets()[h]);
  526. }
  527. #ifdef SELOPT_WRITE
  528. size_t size()
  529. {
  530. return
  531. objc_stringhash_t::size() + capacity * sizeof(objc_stringhash_offset_t);
  532. }
  533. void byteswap(bool little_endian)
  534. {
  535. objc_stringhash_offset_t *o;
  536. o = protocolOffsets();
  537. for (objc_stringhash_offset_t i = 0; i < (int)capacity; i++) {
  538. S32(o[i]);
  539. }
  540. objc_stringhash_t::byteswap(little_endian);
  541. }
  542. const char *write(uint64_t base, size_t remaining,
  543. string_map& strings, legacy_protocol_map& protocols,
  544. bool verbose)
  545. {
  546. const char *err;
  547. err = objc_stringhash_t::write(base, remaining, strings);
  548. if (err) return err;
  549. if (size() > remaining) {
  550. return "selector section too small (metadata not optimized)";
  551. }
  552. // Set protocol offsets to 0
  553. for (uint32_t i = 0; i < capacity; i++) {
  554. protocolOffsets()[i] = 0;
  555. }
  556. // Set real protocol offsets
  557. # define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
  558. legacy_protocol_map::const_iterator c;
  559. for (c = protocols.begin(); c != protocols.end(); ++c) {
  560. uint32_t h = getIndex(c->first);
  561. if (h == INDEX_NOT_FOUND) {
  562. return "protocol list busted (metadata not optimized)";
  563. }
  564. int64_t offset = c->second - base;
  565. if ((offset<<SHIFT)>>SHIFT != offset) {
  566. return "protocol offset too big (metadata not optimized)";
  567. }
  568. protocolOffsets()[h] = (objc_stringhash_offset_t)offset;
  569. }
  570. # undef SHIFT
  571. return NULL;
  572. }
  573. // SELOPT_WRITE
  574. #endif
  575. };
  576. struct objc_protocolopt2_t : objc_clsopt_t {
  577. void* getProtocol(const char *key,
  578. bool (*callback)(const void* header_info)) const
  579. {
  580. uint32_t h = getIndex(key);
  581. if (h == INDEX_NOT_FOUND) {
  582. return NULL;
  583. }
  584. const objc_classheader_t& clshi = classOffsets()[h];
  585. if (! clshi.isDuplicate()) {
  586. // protocol appears in exactly one header
  587. void* cls = (void *)((const char *)this + clshi.clsOffset);
  588. void* hi = (void *)((const char *)this + clshi.hiOffset);
  589. return callback(hi) ? cls : NULL;
  590. }
  591. else {
  592. // protocol appears in more than one header
  593. uint32_t count = clshi.duplicateCount();
  594. const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
  595. for (uint32_t i = 0; i < count; i++) {
  596. void* cls = (void *)((const char *)this + list[i].clsOffset);
  597. void* hi = (void *)((const char *)this + list[i].hiOffset);
  598. if (callback(hi))
  599. return cls;
  600. }
  601. return NULL;
  602. }
  603. }
  604. };
  605. // Precomputed image list.
  606. struct objc_headeropt_ro_t;
  607. // Precomputed image list.
  608. struct objc_headeropt_rw_t;
  609. // Precomputed class list.
  610. struct objc_clsopt_t;
  611. // Edit objc-sel-table.s if you change this value.
  612. // lldb and Symbolication read these structures. Inform them of any changes.
  613. enum { VERSION = 15 };
  614. // Values for objc_opt_t::flags
  615. enum : uint32_t {
  616. IsProduction = (1 << 0), // never set in development cache
  617. NoMissingWeakSuperclasses = (1 << 1) // set in development cache and customer
  618. };
  619. // Top-level optimization structure.
  620. // Edit objc-sel-table.s if you change this structure.
  621. struct alignas(alignof(void*)) objc_opt_t {
  622. uint32_t version;
  623. uint32_t flags;
  624. int32_t selopt_offset;
  625. int32_t headeropt_ro_offset;
  626. int32_t clsopt_offset;
  627. int32_t unused_protocolopt_offset; // This is now 0 as we've moved to the new protocolopt_offset
  628. int32_t headeropt_rw_offset;
  629. int32_t protocolopt_offset;
  630. const objc_selopt_t* selopt() const {
  631. if (selopt_offset == 0) return NULL;
  632. return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
  633. }
  634. objc_selopt_t* selopt() {
  635. if (selopt_offset == 0) return NULL;
  636. return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
  637. }
  638. struct objc_headeropt_ro_t* headeropt_ro() const {
  639. if (headeropt_ro_offset == 0) return NULL;
  640. return (struct objc_headeropt_ro_t *)((uint8_t *)this + headeropt_ro_offset);
  641. }
  642. struct objc_clsopt_t* clsopt() const {
  643. if (clsopt_offset == 0) return NULL;
  644. return (objc_clsopt_t *)((uint8_t *)this + clsopt_offset);
  645. }
  646. struct objc_protocolopt_t* protocolopt() const {
  647. if (unused_protocolopt_offset == 0) return NULL;
  648. return (objc_protocolopt_t *)((uint8_t *)this + unused_protocolopt_offset);
  649. }
  650. struct objc_protocolopt2_t* protocolopt2() const {
  651. if (protocolopt_offset == 0) return NULL;
  652. return (objc_protocolopt2_t *)((uint8_t *)this + protocolopt_offset);
  653. }
  654. struct objc_headeropt_rw_t* headeropt_rw() const {
  655. if (headeropt_rw_offset == 0) return NULL;
  656. return (struct objc_headeropt_rw_t *)((uint8_t *)this + headeropt_rw_offset);
  657. }
  658. };
  659. // sizeof(objc_opt_t) must be pointer-aligned
  660. STATIC_ASSERT(sizeof(objc_opt_t) % sizeof(void*) == 0);
  661. // List of offsets in libobjc that the shared cache optimization needs to use.
  662. template <typename T>
  663. struct objc_opt_pointerlist_tt {
  664. T protocolClass;
  665. };
  666. typedef struct objc_opt_pointerlist_tt<uintptr_t> objc_opt_pointerlist_t;
  667. /*
  668. --------------------------------------------------------------------
  669. mix -- mix 3 64-bit values reversibly.
  670. mix() takes 48 machine instructions, but only 24 cycles on a superscalar
  671. machine (like Intel's new MMX architecture). It requires 4 64-bit
  672. registers for 4::2 parallelism.
  673. All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of
  674. (a,b,c), and all deltas of bottom bits were tested. All deltas were
  675. tested both on random keys and on keys that were nearly all zero.
  676. These deltas all cause every bit of c to change between 1/3 and 2/3
  677. of the time (well, only 113/400 to 287/400 of the time for some
  678. 2-bit delta). These deltas all cause at least 80 bits to change
  679. among (a,b,c) when the mix is run either forward or backward (yes it
  680. is reversible).
  681. This implies that a hash using mix64 has no funnels. There may be
  682. characteristics with 3-bit deltas or bigger, I didn't test for
  683. those.
  684. --------------------------------------------------------------------
  685. */
  686. #define mix64(a,b,c) \
  687. { \
  688. a -= b; a -= c; a ^= (c>>43); \
  689. b -= c; b -= a; b ^= (a<<9); \
  690. c -= a; c -= b; c ^= (b>>8); \
  691. a -= b; a -= c; a ^= (c>>38); \
  692. b -= c; b -= a; b ^= (a<<23); \
  693. c -= a; c -= b; c ^= (b>>5); \
  694. a -= b; a -= c; a ^= (c>>35); \
  695. b -= c; b -= a; b ^= (a<<49); \
  696. c -= a; c -= b; c ^= (b>>11); \
  697. a -= b; a -= c; a ^= (c>>12); \
  698. b -= c; b -= a; b ^= (a<<18); \
  699. c -= a; c -= b; c ^= (b>>22); \
  700. }
  701. /*
  702. --------------------------------------------------------------------
  703. hash() -- hash a variable-length key into a 64-bit value
  704. k : the key (the unaligned variable-length array of bytes)
  705. len : the length of the key, counting by bytes
  706. level : can be any 8-byte value
  707. Returns a 64-bit value. Every bit of the key affects every bit of
  708. the return value. No funnels. Every 1-bit and 2-bit delta achieves
  709. avalanche. About 41+5len instructions.
  710. The best hash table sizes are powers of 2. There is no need to do
  711. mod a prime (mod is sooo slow!). If you need less than 64 bits,
  712. use a bitmask. For example, if you need only 10 bits, do
  713. h = (h & hashmask(10));
  714. In which case, the hash table should have hashsize(10) elements.
  715. If you are hashing n strings (uint8_t **)k, do it like this:
  716. for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
  717. By Bob Jenkins, Jan 4 1997. bob_jenkins@burtleburtle.net. You may
  718. use this code any way you wish, private, educational, or commercial,
  719. but I would appreciate if you give me credit.
  720. See http://burtleburtle.net/bob/hash/evahash.html
  721. Use for hash table lookup, or anything where one collision in 2^^64
  722. is acceptable. Do NOT use for cryptographic purposes.
  723. --------------------------------------------------------------------
  724. */
  725. static uint64_t lookup8( uint8_t *k, size_t length, uint64_t level)
  726. // uint8_t *k; /* the key */
  727. // uint64_t length; /* the length of the key */
  728. // uint64_t level; /* the previous hash, or an arbitrary value */
  729. {
  730. uint64_t a,b,c;
  731. size_t len;
  732. /* Set up the internal state */
  733. len = length;
  734. a = b = level; /* the previous hash value */
  735. c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
  736. /*---------------------------------------- handle most of the key */
  737. while (len >= 24)
  738. {
  739. a += (k[0] +((uint64_t)k[ 1]<< 8)+((uint64_t)k[ 2]<<16)+((uint64_t)k[ 3]<<24)
  740. +((uint64_t)k[4 ]<<32)+((uint64_t)k[ 5]<<40)+((uint64_t)k[ 6]<<48)+((uint64_t)k[ 7]<<56));
  741. b += (k[8] +((uint64_t)k[ 9]<< 8)+((uint64_t)k[10]<<16)+((uint64_t)k[11]<<24)
  742. +((uint64_t)k[12]<<32)+((uint64_t)k[13]<<40)+((uint64_t)k[14]<<48)+((uint64_t)k[15]<<56));
  743. c += (k[16] +((uint64_t)k[17]<< 8)+((uint64_t)k[18]<<16)+((uint64_t)k[19]<<24)
  744. +((uint64_t)k[20]<<32)+((uint64_t)k[21]<<40)+((uint64_t)k[22]<<48)+((uint64_t)k[23]<<56));
  745. mix64(a,b,c);
  746. k += 24; len -= 24;
  747. }
  748. /*------------------------------------- handle the last 23 bytes */
  749. c += length;
  750. #pragma clang diagnostic push
  751. #pragma clang diagnostic ignored "-Wimplicit-fallthrough"
  752. switch(len) /* all the case statements fall through */
  753. {
  754. case 23: c+=((uint64_t)k[22]<<56);
  755. case 22: c+=((uint64_t)k[21]<<48);
  756. case 21: c+=((uint64_t)k[20]<<40);
  757. case 20: c+=((uint64_t)k[19]<<32);
  758. case 19: c+=((uint64_t)k[18]<<24);
  759. case 18: c+=((uint64_t)k[17]<<16);
  760. case 17: c+=((uint64_t)k[16]<<8);
  761. /* the first byte of c is reserved for the length */
  762. case 16: b+=((uint64_t)k[15]<<56);
  763. case 15: b+=((uint64_t)k[14]<<48);
  764. case 14: b+=((uint64_t)k[13]<<40);
  765. case 13: b+=((uint64_t)k[12]<<32);
  766. case 12: b+=((uint64_t)k[11]<<24);
  767. case 11: b+=((uint64_t)k[10]<<16);
  768. case 10: b+=((uint64_t)k[ 9]<<8);
  769. case 9: b+=((uint64_t)k[ 8]);
  770. case 8: a+=((uint64_t)k[ 7]<<56);
  771. case 7: a+=((uint64_t)k[ 6]<<48);
  772. case 6: a+=((uint64_t)k[ 5]<<40);
  773. case 5: a+=((uint64_t)k[ 4]<<32);
  774. case 4: a+=((uint64_t)k[ 3]<<24);
  775. case 3: a+=((uint64_t)k[ 2]<<16);
  776. case 2: a+=((uint64_t)k[ 1]<<8);
  777. case 1: a+=((uint64_t)k[ 0]);
  778. /* case 0: nothing left to add */
  779. }
  780. #pragma clang diagnostic pop
  781. mix64(a,b,c);
  782. /*-------------------------------------------- report the result */
  783. return c;
  784. }
  785. #if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
  786. /*
  787. ------------------------------------------------------------------------------
  788. This generates a minimal perfect hash function. That means, given a
  789. set of n keys, this determines a hash function that maps each of
  790. those keys into a value in 0..n-1 with no collisions.
  791. The perfect hash function first uses a normal hash function on the key
  792. to determine (a,b) such that the pair (a,b) is distinct for all
  793. keys, then it computes a^scramble[tab[b]] to get the final perfect hash.
  794. tab[] is an array of 1-byte values and scramble[] is a 256-term array of
  795. 2-byte or 4-byte values. If there are n keys, the length of tab[] is a
  796. power of two between n/3 and n.
  797. I found the idea of computing distinct (a,b) values in "Practical minimal
  798. perfect hash functions for large databases", Fox, Heath, Chen, and Daoud,
  799. Communications of the ACM, January 1992. They found the idea in Chichelli
  800. (CACM Jan 1980). Beyond that, our methods differ.
  801. The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in
  802. 0..*blen*-1. A fast hash function determines both a and b
  803. simultaneously. Any decent hash function is likely to produce
  804. hashes so that (a,b) is distinct for all pairs. I try the hash
  805. using different values of *salt* until all pairs are distinct.
  806. The final hash is (a XOR scramble[tab[b]]). *scramble* is a
  807. predetermined mapping of 0..255 into 0..smax-1. *tab* is an
  808. array that we fill in in such a way as to make the hash perfect.
  809. First we fill in all values of *tab* that are used by more than one
  810. key. We try all possible values for each position until one works.
  811. This leaves m unmapped keys and m values that something could hash to.
  812. If you treat unmapped keys as lefthand nodes and unused hash values
  813. as righthand nodes, and draw a line connecting each key to each hash
  814. value it could map to, you get a bipartite graph. We attempt to
  815. find a perfect matching in this graph. If we succeed, we have
  816. determined a perfect hash for the whole set of keys.
  817. *scramble* is used because (a^tab[i]) clusters keys around *a*.
  818. ------------------------------------------------------------------------------
  819. */
  820. typedef uint64_t ub8;
  821. #define UB8MAXVAL 0xffffffffffffffffLL
  822. #define UB8BITS 64
  823. typedef uint32_t ub4;
  824. #define UB4MAXVAL 0xffffffff
  825. #define UB4BITS 32
  826. typedef uint16_t ub2;
  827. #define UB2MAXVAL 0xffff
  828. #define UB2BITS 16
  829. typedef uint8_t ub1;
  830. #define UB1MAXVAL 0xff
  831. #define UB1BITS 8
  832. #define TRUE 1
  833. #define FALSE 0
  834. #define SCRAMBLE_LEN 256 // ((ub4)1<<16) /* length of *scramble* */
  835. #define RETRY_INITKEY 2048 /* number of times to try to find distinct (a,b) */
  836. #define RETRY_PERFECT 4 /* number of times to try to make a perfect hash */
  837. /* representation of a key */
  838. struct key
  839. {
  840. ub1 *name_k; /* the actual key */
  841. ub4 len_k; /* the length of the actual key */
  842. ub4 hash_k; /* the initial hash value for this key */
  843. /* beyond this point is mapping-dependent */
  844. ub4 a_k; /* a, of the key maps to (a,b) */
  845. ub4 b_k; /* b, of the key maps to (a,b) */
  846. struct key *nextb_k; /* next key with this b */
  847. };
  848. typedef struct key key;
  849. /* things indexed by b of original (a,b) pair */
  850. struct bstuff
  851. {
  852. ub2 val_b; /* hash=a^tabb[b].val_b */
  853. key *list_b; /* tabb[i].list_b is list of keys with b==i */
  854. ub4 listlen_b; /* length of list_b */
  855. ub4 water_b; /* high watermark of who has visited this map node */
  856. };
  857. typedef struct bstuff bstuff;
  858. /* things indexed by final hash value */
  859. struct hstuff
  860. {
  861. key *key_h; /* tabh[i].key_h is the key with a hash of i */
  862. };
  863. typedef struct hstuff hstuff;
  864. /* things indexed by queue position */
  865. struct qstuff
  866. {
  867. bstuff *b_q; /* b that currently occupies this hash */
  868. ub4 parent_q; /* queue position of parent that could use this hash */
  869. ub2 newval_q; /* what to change parent tab[b] to to use this hash */
  870. ub2 oldval_q; /* original value of tab[b] */
  871. };
  872. typedef struct qstuff qstuff;
  873. /*
  874. ------------------------------------------------------------------------------
  875. Find the mapping that will produce a perfect hash
  876. ------------------------------------------------------------------------------
  877. */
  878. /* return the ceiling of the log (base 2) of val */
  879. static ub4 log2u(ub4 val)
  880. {
  881. ub4 i;
  882. for (i=0; ((ub4)1<<i) < val; ++i)
  883. ;
  884. return i;
  885. }
  886. /* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */
  887. /* permute(0)=0. This is intended and useful. */
  888. static ub4 permute(ub4 x, ub4 nbits)
  889. // ub4 x; /* input, a value in some range */
  890. // ub4 nbits; /* input, number of bits in range */
  891. {
  892. int i;
  893. int mask = ((ub4)1<<nbits)-1; /* all ones */
  894. int const2 = 1+nbits/2;
  895. int const3 = 1+nbits/3;
  896. int const4 = 1+nbits/4;
  897. int const5 = 1+nbits/5;
  898. for (i=0; i<20; ++i)
  899. {
  900. x = (x+(x<<const2)) & mask;
  901. x = (x^(x>>const3));
  902. x = (x+(x<<const4)) & mask;
  903. x = (x^(x>>const5));
  904. }
  905. return x;
  906. }
  907. /* initialize scramble[] with distinct random values in 0..smax-1 */
  908. static void scrambleinit(ub4 *scramble, ub4 smax)
  909. // ub4 *scramble; /* hash is a^scramble[tab[b]] */
  910. // ub4 smax; /* scramble values should be in 0..smax-1 */
  911. {
  912. ub4 i;
  913. /* fill scramble[] with distinct random integers in 0..smax-1 */
  914. for (i=0; i<SCRAMBLE_LEN; ++i)
  915. {
  916. scramble[i] = permute(i, log2u(smax));
  917. }
  918. }
  919. /*
  920. * put keys in tabb according to key->b_k
  921. * check if the initial hash might work
  922. */
  923. static int inittab(dyld3::OverflowSafeArray<bstuff>& tabb, dyld3::OverflowSafeArray<key>& keys, int complete)
  924. // bstuff *tabb; /* output, list of keys with b for (a,b) */
  925. // ub4 blen; /* length of tabb */
  926. // key *keys; /* list of keys already hashed */
  927. // int complete; /* TRUE means to complete init despite collisions */
  928. {
  929. int nocollision = TRUE;
  930. ub4 i;
  931. memset((void *)tabb.begin(), 0, (size_t)(sizeof(bstuff)*tabb.maxCount()));
  932. /* Two keys with the same (a,b) guarantees a collision */
  933. for (i = 0; i < keys.count(); i++) {
  934. key *mykey = &keys[i];
  935. key *otherkey;
  936. for (otherkey=tabb[mykey->b_k].list_b;
  937. otherkey;
  938. otherkey=otherkey->nextb_k)
  939. {
  940. if (mykey->a_k == otherkey->a_k)
  941. {
  942. nocollision = FALSE;
  943. if (!complete)
  944. return FALSE;
  945. }
  946. }
  947. ++tabb[mykey->b_k].listlen_b;
  948. mykey->nextb_k = tabb[mykey->b_k].list_b;
  949. tabb[mykey->b_k].list_b = mykey;
  950. }
  951. /* no two keys have the same (a,b) pair */
  952. return nocollision;
  953. }
  954. /* Do the initial hash for normal mode (use lookup and checksum) */
  955. static void initnorm(dyld3::OverflowSafeArray<key>& keys, ub4 alen, ub4 blen, ub4 smax, ub8 salt)
  956. // key *keys; /* list of all keys */
  957. // ub4 alen; /* (a,b) has a in 0..alen-1, a power of 2 */
  958. // ub4 blen; /* (a,b) has b in 0..blen-1, a power of 2 */
  959. // ub4 smax; /* maximum range of computable hash values */
  960. // ub4 salt; /* used to initialize the hash function */
  961. // gencode *final; /* output, code for the final hash */
  962. {
  963. ub4 loga = log2u(alen); /* log based 2 of blen */
  964. #if BUILDING_CACHE_BUILDER
  965. dispatch_apply(keys.count(), DISPATCH_APPLY_AUTO, ^(size_t index) {
  966. ub4 i = (ub4)index;
  967. key *mykey = &keys[i];
  968. ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
  969. mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
  970. mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
  971. });
  972. #else
  973. for (size_t index = 0; index != keys.count(); ++index) {
  974. ub4 i = (ub4)index;
  975. key *mykey = &keys[i];
  976. ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
  977. mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
  978. mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
  979. };
  980. #endif
  981. }
  982. /* Try to apply an augmenting list */
  983. static int apply(dyld3::OverflowSafeArray<bstuff>& tabb,
  984. dyld3::OverflowSafeArray<hstuff>& tabh,
  985. dyld3::OverflowSafeArray<qstuff>& tabq,
  986. ub4 *scramble, ub4 tail, int rollback)
  987. // bstuff *tabb;
  988. // hstuff *tabh;
  989. // qstuff *tabq;
  990. // ub4 blen;
  991. // ub4 *scramble;
  992. // ub4 tail;
  993. // int rollback; /* FALSE applies augmenting path, TRUE rolls back */
  994. {
  995. ub4 hash;
  996. key *mykey;
  997. bstuff *pb;
  998. ub4 child;
  999. ub4 parent;
  1000. ub4 stabb; /* scramble[tab[b]] */
  1001. /* walk from child to parent */
  1002. for (child=tail-1; child; child=parent)
  1003. {
  1004. parent = tabq[child].parent_q; /* find child's parent */
  1005. pb = tabq[parent].b_q; /* find parent's list of siblings */
  1006. /* erase old hash values */
  1007. stabb = scramble[pb->val_b];
  1008. for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
  1009. {
  1010. hash = mykey->a_k^stabb;
  1011. if (mykey == tabh[hash].key_h)
  1012. { /* erase hash for all of child's siblings */
  1013. tabh[hash].key_h = (key *)0;
  1014. }
  1015. }
  1016. /* change pb->val_b, which will change the hashes of all parent siblings */
  1017. pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q);
  1018. /* set new hash values */
  1019. stabb = scramble[pb->val_b];
  1020. for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
  1021. {
  1022. hash = mykey->a_k^stabb;
  1023. if (rollback)
  1024. {
  1025. if (parent == 0) continue; /* root never had a hash */
  1026. }
  1027. else if (tabh[hash].key_h)
  1028. {
  1029. /* very rare: roll back any changes */
  1030. apply(tabb, tabh, tabq, scramble, tail, TRUE);
  1031. return FALSE; /* failure, collision */
  1032. }
  1033. tabh[hash].key_h = mykey;
  1034. }
  1035. }
  1036. return TRUE;
  1037. }
  1038. /*
  1039. -------------------------------------------------------------------------------
  1040. augment(): Add item to the mapping.
  1041. Construct a spanning tree of *b*s with *item* as root, where each
  1042. parent can have all its hashes changed (by some new val_b) with
  1043. at most one collision, and each child is the b of that collision.
  1044. I got this from Tarjan's "Data Structures and Network Algorithms". The
  1045. path from *item* to a *b* that can be remapped with no collision is
  1046. an "augmenting path". Change values of tab[b] along the path so that
  1047. the unmapped key gets mapped and the unused hash value gets used.
  1048. Assuming 1 key per b, if m out of n hash values are still unused,
  1049. you should expect the transitive closure to cover n/m nodes before
  1050. an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect
  1051. this approach to take about nlogn time to map all single-key b's.
  1052. -------------------------------------------------------------------------------
  1053. */
  1054. static int augment(dyld3::OverflowSafeArray<bstuff>& tabb,
  1055. dyld3::OverflowSafeArray<hstuff>& tabh,
  1056. dyld3::OverflowSafeArray<qstuff>& tabq,
  1057. ub4 *scramble, ub4 smax, bstuff *item, ub4 nkeys,
  1058. ub4 highwater)
  1059. // bstuff *tabb; /* stuff indexed by b */
  1060. // hstuff *tabh; /* which key is associated with which hash, indexed by hash */
  1061. // qstuff *tabq; /* queue of *b* values, this is the spanning tree */
  1062. // ub4 *scramble; /* final hash is a^scramble[tab[b]] */
  1063. // ub4 smax; /* highest value in scramble */
  1064. // bstuff *item; /* &tabb[b] for the b to be mapped */
  1065. // ub4 nkeys; /* final hash must be in 0..nkeys-1 */
  1066. // ub4 highwater; /* a value higher than any now in tabb[].water_b */
  1067. {
  1068. ub4 q; /* current position walking through the queue */
  1069. ub4 tail; /* tail of the queue. 0 is the head of the queue. */
  1070. ub4 limit=UB1MAXVAL+1;
  1071. ub4 highhash = smax;
  1072. /* initialize the root of the spanning tree */
  1073. tabq[0].b_q = item;
  1074. tail = 1;
  1075. /* construct the spanning tree by walking the queue, add children to tail */
  1076. for (q=0; q<tail; ++q)
  1077. {
  1078. bstuff *myb = tabq[q].b_q; /* the b for this node */
  1079. ub4 i; /* possible value for myb->val_b */
  1080. if (q == 1)
  1081. break; /* don't do transitive closure */
  1082. for (i=0; i<limit; ++i)
  1083. {
  1084. bstuff *childb = (bstuff *)0; /* the b that this i maps to */
  1085. key *mykey; /* for walking through myb's keys */
  1086. for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k)
  1087. {
  1088. key *childkey;
  1089. ub4 hash = mykey->a_k^scramble[i];
  1090. if (hash >= highhash) break; /* out of bounds */
  1091. childkey = tabh[hash].key_h;
  1092. if (childkey)
  1093. {
  1094. bstuff *hitb = &tabb[childkey->b_k];
  1095. if (childb)
  1096. {
  1097. if (childb != hitb) break; /* hit at most one child b */
  1098. }
  1099. else
  1100. {
  1101. childb = hitb; /* remember this as childb */
  1102. if (childb->water_b == highwater) break; /* already explored */
  1103. }
  1104. }
  1105. }
  1106. if (mykey) continue; /* myb with i has multiple collisions */
  1107. /* add childb to the queue of reachable things */
  1108. if (childb) childb->water_b = highwater;
  1109. tabq[tail].b_q = childb;
  1110. tabq[tail].newval_q = i; /* how to make parent (myb) use this hash */
  1111. tabq[tail].oldval_q = myb->val_b; /* need this for rollback */
  1112. tabq[tail].parent_q = q;
  1113. ++tail;
  1114. if (!childb)
  1115. { /* found an *i* with no collisions? */
  1116. /* try to apply the augmenting path */
  1117. if (apply(tabb, tabh, tabq, scramble, tail, FALSE))
  1118. return TRUE; /* success, item was added to the perfect hash */
  1119. --tail; /* don't know how to handle such a child! */
  1120. }
  1121. }
  1122. }
  1123. return FALSE;
  1124. }
  1125. /* find a mapping that makes this a perfect hash */
  1126. static int perfect(dyld3::OverflowSafeArray<bstuff>& tabb,
  1127. dyld3::OverflowSafeArray<hstuff>& tabh,
  1128. dyld3::OverflowSafeArray<qstuff>& tabq,
  1129. ub4 smax, ub4 *scramble, ub4 nkeys)
  1130. {
  1131. ub4 maxkeys; /* maximum number of keys for any b */
  1132. ub4 i, j;
  1133. const ub4 blen = (ub4)tabb.count();
  1134. #if SELOPT_DEBUG
  1135. fprintf(stderr, " blen %d smax %d nkeys %d\n", blen, smax, nkeys);
  1136. #endif
  1137. /* clear any state from previous attempts */
  1138. memset((void *)tabh.begin(), 0, sizeof(hstuff)*smax);
  1139. memset((void *)tabq.begin(), 0, sizeof(qstuff)*(blen+1));
  1140. for (maxkeys=0,i=0; i<blen; ++i)
  1141. if (tabb[i].listlen_b > maxkeys)
  1142. maxkeys = tabb[i].listlen_b;
  1143. /* In descending order by number of keys, map all *b*s */
  1144. for (j=maxkeys; j>0; --j)
  1145. for (i=0; i<blen; ++i)
  1146. if (tabb[i].listlen_b == j)
  1147. if (!augment(tabb, tabh, tabq, scramble, smax, &tabb[i], nkeys,
  1148. i+1))
  1149. {
  1150. return FALSE;
  1151. }
  1152. /* Success! We found a perfect hash of all keys into 0..nkeys-1. */
  1153. return TRUE;
  1154. }
  1155. /* guess initial values for alen and blen */
  1156. static void initalen(ub4 *alen, ub4 *blen, ub4 smax, ub4 nkeys)
  1157. // ub4 *alen; /* output, initial alen */
  1158. // ub4 *blen; /* output, initial blen */
  1159. // ub4 smax; /* input, power of two greater or equal to max hash value */
  1160. // ub4 nkeys; /* number of keys being hashed */
  1161. {
  1162. /*
  1163. * Find initial *alen, *blen
  1164. * Initial alen and blen values were found empirically. Some factors:
  1165. *
  1166. * If smax<256 there is no scramble, so tab[b] needs to cover 0..smax-1.
  1167. *
  1168. * alen and blen must be powers of 2 because the values in 0..alen-1 and
  1169. * 0..blen-1 are produced by applying a bitmask to the initial hash function.
  1170. *
  1171. * alen must be less than smax, in fact less than nkeys, because otherwise
  1172. * there would often be no i such that a^scramble[i] is in 0..nkeys-1 for
  1173. * all the *a*s associated with a given *b*, so there would be no legal
  1174. * value to assign to tab[b]. This only matters when we're doing a minimal
  1175. * perfect hash.
  1176. *
  1177. * It takes around 800 trials to find distinct (a,b) with nkey=smax*(5/8)
  1178. * and alen*blen = smax*smax/32.
  1179. *
  1180. * Values of blen less than smax/4 never work, and smax/2 always works.
  1181. *
  1182. * We want blen as small as possible because it is the number of bytes in
  1183. * the huge array we must create for the perfect hash.
  1184. *
  1185. * When nkey <= smax*(5/8), blen=smax/4 works much more often with
  1186. * alen=smax/8 than with alen=smax/4. Above smax*(5/8), blen=smax/4
  1187. * doesn't seem to care whether alen=smax/8 or alen=smax/4. I think it
  1188. * has something to do with 5/8 = 1/8 * 5. For example examine 80000,
  1189. * 85000, and 90000 keys with different values of alen. This only matters
  1190. * if we're doing a minimal perfect hash.
  1191. *
  1192. * When alen*blen <= 1<<UB4BITS, the initial hash must produce one integer.
  1193. * Bigger than that it must produce two integers, which increases the
  1194. * cost of the hash per character hashed.
  1195. */
  1196. *alen = smax; /* no reason to restrict alen to smax/2 */
  1197. *blen = ((nkeys <= smax*0.6) ? smax/16 :
  1198. (nkeys <= smax*0.8) ? smax/8 : smax/4);
  1199. if (*alen < 1) *alen = 1;
  1200. if (*blen < 1) *blen = 1;
  1201. #if SELOPT_DEBUG
  1202. fprintf(stderr, "alen %d blen %d smax %d nkeys %d\n", *alen, *blen, smax, nkeys);
  1203. #endif
  1204. }
  1205. /*
  1206. ** Try to find a perfect hash function.
  1207. ** Return the successful initializer for the initial hash.
  1208. ** Return 0 if no perfect hash could be found.
  1209. */
  1210. static int findhash(dyld3::OverflowSafeArray<bstuff>& tabb,
  1211. ub4 *alen, ub8 *salt,
  1212. ub4 *scramble, ub4 smax, dyld3::OverflowSafeArray<key>& keys)
  1213. // bstuff **tabb; /* output, tab[] of the perfect hash, length *blen */
  1214. // ub4 *alen; /* output, 0..alen-1 is range for a of (a,b) */
  1215. // ub4 *blen; /* output, 0..blen-1 is range for b of (a,b) */
  1216. // ub4 *salt; /* output, initializes initial hash */
  1217. // ub4 *scramble; /* input, hash = a^scramble[tab[b]] */
  1218. // ub4 smax; /* input, scramble[i] in 0..smax-1 */
  1219. // key *keys; /* input, keys to hash */
  1220. // ub4 nkeys; /* input, number of keys being hashed */
  1221. {
  1222. ub4 bad_initkey; /* how many times did initkey fail? */
  1223. ub4 bad_perfect; /* how many times did perfect fail? */
  1224. ub4 si; /* trial initializer for initial hash */
  1225. ub4 maxalen;
  1226. dyld3::OverflowSafeArray<hstuff>tabh; /* table of keys indexed by hash value */
  1227. dyld3::OverflowSafeArray<qstuff>tabq; /* table of stuff indexed by queue value, used by augment */
  1228. /* guess initial values for alen and blen */
  1229. ub4 blen = 0;
  1230. initalen(alen, &blen, smax, (ub4)keys.count());
  1231. scrambleinit(scramble, smax);
  1232. maxalen = smax;
  1233. /* allocate working memory */
  1234. tabb.resize(blen);
  1235. tabq.resize(blen+1);
  1236. tabh.resize(smax);
  1237. /* Actually find the perfect hash */
  1238. *salt = 0;
  1239. bad_initkey = 0;
  1240. bad_perfect = 0;
  1241. for (si=1; ; ++si)
  1242. {
  1243. ub4 rslinit;
  1244. /* Try to find distinct (A,B) for all keys */
  1245. *salt = si * 0x9e3779b97f4a7c13LL; /* golden ratio (arbitrary value) */
  1246. initnorm(keys, *alen, blen, smax, *salt);
  1247. rslinit = inittab(tabb, keys, FALSE);
  1248. if (rslinit == 0)
  1249. {
  1250. /* didn't find distinct (a,b) */
  1251. if (++bad_initkey >= RETRY_INITKEY)
  1252. {
  1253. /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
  1254. if (*alen < maxalen)
  1255. {
  1256. *alen *= 2;
  1257. }
  1258. else if (blen < smax)
  1259. {
  1260. blen *= 2;
  1261. tabb.resize(blen);
  1262. tabq.resize(blen+1);
  1263. }
  1264. bad_initkey = 0;
  1265. bad_perfect = 0;
  1266. }
  1267. continue; /* two keys have same (a,b) pair */
  1268. }
  1269. /* Given distinct (A,B) for all keys, build a perfect hash */
  1270. if (!perfect(tabb, tabh, tabq, smax, scramble, (ub4)keys.count()))
  1271. {
  1272. if (++bad_perfect >= RETRY_PERFECT)
  1273. {
  1274. if (blen < smax)
  1275. {
  1276. blen *= 2;
  1277. tabb.resize(blen);
  1278. tabq.resize(blen+1);
  1279. --si; /* we know this salt got distinct (A,B) */
  1280. }
  1281. else
  1282. {
  1283. return 0;
  1284. }
  1285. bad_perfect = 0;
  1286. }
  1287. continue;
  1288. }
  1289. break;
  1290. }
  1291. return 1;
  1292. }
  1293. /*
  1294. ------------------------------------------------------------------------------
  1295. Input/output type routines
  1296. ------------------------------------------------------------------------------
  1297. */
  1298. static void
  1299. make_perfect(dyld3::OverflowSafeArray<key>& keys, perfect_hash& result)
  1300. {
  1301. dyld3::OverflowSafeArray<bstuff> tab; /* table indexed by b */
  1302. ub4 smax; /* scramble[] values in 0..smax-1, a power of 2 */
  1303. ub4 alen; /* a in 0..alen-1, a power of 2 */
  1304. ub8 salt; /* a parameter to the hash function */
  1305. ub4 scramble[SCRAMBLE_LEN]; /* used in final hash function */
  1306. int ok;
  1307. uint32_t i;
  1308. /* find the hash */
  1309. smax = ((ub4)1<<log2u((ub4)keys.count()));
  1310. ok = findhash(tab, &alen, &salt,
  1311. scramble, smax, keys);
  1312. if (!ok) {
  1313. smax = 2 * ((ub4)1<<log2u((ub4)keys.count()));
  1314. ok = findhash(tab, &alen, &salt,
  1315. scramble, smax, keys);
  1316. }
  1317. if (!ok) {
  1318. bzero(&result, sizeof(result));
  1319. } else {
  1320. /* build the tables */
  1321. result.capacity = smax;
  1322. result.occupied = (ub4)keys.count();
  1323. result.shift = UB8BITS - log2u(alen);
  1324. result.mask = (ub4)tab.count() - 1;
  1325. result.salt = salt;
  1326. result.tab.resize(tab.count());
  1327. for (i = 0; i < tab.count(); i++) {
  1328. result.tab[i] = tab[i].val_b;
  1329. }
  1330. for (i = 0; i < 256; i++) {
  1331. result.scramble[i] = scramble[i];
  1332. }
  1333. }
  1334. }
  1335. // SELOPT_WRITE || CLOSURE_SELOPT_WRITE
  1336. #endif
  1337. #ifdef SELOPT_WRITE
  1338. static void
  1339. make_perfect(const string_map& strings, perfect_hash& phash)
  1340. {
  1341. dyld3::OverflowSafeArray<key> keys;
  1342. /* read in the list of keywords */
  1343. keys.reserve(strings.size());
  1344. size_t i;
  1345. string_map::const_iterator s;
  1346. for (i = 0, s = strings.begin(); s != strings.end(); ++s, ++i) {
  1347. key mykey;
  1348. mykey.name_k = (ub1 *)s->first;
  1349. mykey.len_k = (ub4)strlen(s->first);
  1350. keys.push_back(mykey);
  1351. }
  1352. make_perfect(keys, phash);
  1353. }
  1354. // SELOPT_WRITE
  1355. #endif
  1356. #ifdef CLOSURE_SELOPT_WRITE
  1357. static void
  1358. make_perfect(const dyld3::OverflowSafeArray<const char*>& strings, perfect_hash& phash)
  1359. {
  1360. dyld3::OverflowSafeArray<key> keys;
  1361. /* read in the list of keywords */
  1362. keys.reserve(strings.count());
  1363. for (const char* s : strings) {
  1364. key mykey;
  1365. mykey.name_k = (ub1 *)s;
  1366. mykey.len_k = (ub4)strlen(s);
  1367. keys.push_back(mykey);
  1368. }
  1369. make_perfect(keys, phash);
  1370. }
  1371. // CLOSURE_SELOPT_WRITE
  1372. #endif
  1373. // namespace objc_selopt
  1374. };
  1375. #undef S32
  1376. #undef S64
  1377. #endif