1
template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
2
class DenseSet : public detail::DenseSetImpl<
3
                     ValueT, DenseMap<ValueT, detail::DenseSetEmpty,
4
                                      DenseMapValueInfo<detail::DenseSetEmpty>,
5
                                      ValueInfoT, detail::DenseSetPair<ValueT>>,
6
                     ValueInfoT> {
7
  using BaseT =
8
      detail::DenseSetImpl<ValueT,
9
                           DenseMap<ValueT, detail::DenseSetEmpty,
10
                                    DenseMapValueInfo<detail::DenseSetEmpty>,
11
                                    ValueInfoT, detail::DenseSetPair<ValueT>>,
12
                           ValueInfoT>;
13

14
public:
15
  using BaseT::BaseT;
16
};

1
/// Base class for DenseSet and DenseSmallSet.
2
///
3
/// MapTy should be either
4
///
5
///   DenseMap<ValueT, detail::DenseSetEmpty,
6
///            DenseMapValueInfo<detail::DenseSetEmpty>,
7
///            ValueInfoT, detail::DenseSetPair<ValueT>>
8
///
9
/// or the equivalent SmallDenseMap type.  ValueInfoT must implement the
10
/// DenseMapInfo "concept".
11
template <typename ValueT, typename MapTy, typename ValueInfoT>
12
class DenseSetImpl {
13
  static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
14
                "DenseMap buckets unexpectedly large!");
15
  MapTy TheMap;
16

17
  template <typename T>
18
  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
19

20
public:
21
  using key_type = ValueT;
22
  using value_type = ValueT;
23
  using size_type = unsigned;
24

25
...
26

27
std::pair<iterator, bool> insert(const ValueT &V) {
28
    detail::DenseSetEmpty Empty;
29
    return TheMap.try_emplace(V, Empty);
30
  }
31

32
  std::pair<iterator, bool> insert(ValueT &&V) {
33
    detail::DenseSetEmpty Empty;
34
    return TheMap.try_emplace(std::move(V), Empty);
35
  }
36
...

1
template <typename KeyT, typename ValueT,
2
          typename ValueInfoT = DenseMapValueInfo<ValueT>,
3
          typename KeyInfoT = DenseMapInfo<KeyT>,
4
          typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
5
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>,
6
                                     KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT> {
7
  friend class DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;
8
  ...

1
map_images → map_images_nolock → sel_init
2
                         ↓
3
                     _read_images → sel_registerNameNoLock → namedSelectors

1
/***********************************************************************
2
* sel_init
3
* Initialize selector tables and register selectors used internally.
4
**********************************************************************/
5
void sel_init(size_t selrefCount)
6
{
7
#if SUPPORT_PREOPT
8
    if (PrintPreopt) {
9
        _objc_inform("PREOPTIMIZATION: using dyld selector opt");
10
    }
11
#endif
12

13
  namedSelectors.init((unsigned)selrefCount);
14

15
    // Register selectors used by libobjc
16

17
    mutex_locker_t lock(selLock);
18

19
    SEL_cxx_construct = sel_registerNameNoLock(".cxx_construct", NO);
20
    SEL_cxx_destruct = sel_registerNameNoLock(".cxx_destruct", NO);
21
}

1
void
2
map_images_nolock(unsigned mhCount, const struct _dyld_objc_notify_mapped_info infos[],
3
                  bool *disabledClassROEnforcement,
4
                  _dyld_objc_mark_image_mutable makeImageMutable)
5
{
6
...
7
      if (hCount > 0) {
8
          _read_images(mappedInfos, hCount, totalClasses, unoptimizedTotalClasses, makeImageMutable);
9
      }
10
}

1
  MSG_ENTRY _objc_msgSend
2
  UNWIND _objc_msgSend, NoFrame
3

4
  cmp  p0, #0      // nil check and tagged pointer check
5
#if SUPPORT_TAGGED_POINTERS
6
  b.le  LNilOrTagged    //  (MSB tagged pointer looks negative)
7
#else
8
  b.eq  LReturnZero
9
#endif
10
  ldr  p14, [x0]    // p14 = raw isa
11
  GetClassFromIsa_p16 p14, 1, x0  // p16 = class
12
LGetIsaDone:
13
  // calls imp or objc_msgSend_uncached
14
  CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

1
IMP objc_msgSend(id receiver, SEL sel, ...) {
2
    if (receiver == nil) return 0;
3

4
    cls = decode_isa(receiver->isa);
5
    imp = cache_lookup(cls, sel);
6

7
    if (imp == NULL) {
8
        imp = __objc_msgSend_uncached(cls, sel);
9
    }
10

11
    return imp(receiver, sel, ...);
12
}

1
#if SUPPORT_TAGGED_POINTERS
2
LNilOrTagged:
3
  b.eq  LReturnZero    // nil check
4
  GetTaggedClass
5
  b  LGetIsaDone
6
// SUPPORT_TAGGED_POINTERS
7
#endif
8

9
LReturnZero:
10
  // x0 is already zero
11
  mov  x1, #0
12
  movi  d0, #0
13
  movi  d1, #0
14
  movi  d2, #0
15
  movi  d3, #0
16
  ret
17

18
  END_ENTRY _objc_msgSend

1
struct objc_class : objc_object {
2
  objc_class(const objc_class&) = delete;
3
  objc_class(objc_class&&) = delete;
4
  void operator=(const objc_class&) = delete;
5
  void operator=(objc_class&&) = delete;
6
    // Class ISA;
7
    Class superclass;
8
    cache_t cache;             // formerly cache pointer and vtable
9
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
10
    ...

1
struct cache_t {
2
private:
3
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
4
    union {
5
        // Note: _flags on ARM64 needs to line up with the unused bits of
6
        // _originalPreoptCache because we access some flags (specifically
7
        // FAST_CACHE_HAS_DEFAULT_CORE and FAST_CACHE_HAS_DEFAULT_AWZ) on
8
        // unrealized classes with the assumption that they will start out
9
        // as 0.
10
        struct {
11
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED && !__LP64__
12
            // Outlined cache mask storage, 32-bit, we have mask and occupied.
13
            explicit_atomic<mask_t>    _mask;
14
            uint16_t                   _occupied;
15
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED && __LP64__
16
            // Outlined cache mask storage, 64-bit, we have mask, occupied, flags.
17
            explicit_atomic<mask_t>    _mask;
18
            uint16_t                   _occupied;
19
            uint16_t                   _flags;
20
#   define CACHE_T_HAS_FLAGS 1
21
#elif __LP64__
22
            // Inline cache mask storage, 64-bit, we have occupied, flags, and
23
            // empty space to line up flags with originalPreoptCache.
24
            //
25
            // Note: the assembly code for objc_release_xN knows about the
26
            // location of _flags and the
27
            // FAST_CACHE_HAS_CUSTOM_DEALLOC_INITIATION flag within. Any changes
28
            // must be applied there as well.
29
            uint32_t                   _disguisedPreoptCacheSignature;
30
            uint16_t                   _occupied;
31
            uint16_t                   _flags;
32
#   define CACHE_T_HAS_FLAGS 1
33
#else
34
            // Inline cache mask storage, 32-bit, we have occupied, flags.
35
            uint16_t                   _occupied;
36
            uint16_t                   _flags;
37
#   define CACHE_T_HAS_FLAGS 1
38
#endif
39

40
        };
41
        explicit_atomic<preopt_cache_t *, PTRAUTH_STR(originalPreoptCache, ptrauth_key_process_independent_data)> _originalPreoptCache;
42
    };

1
[ bucket0 ][ bucket1 ][ bucket2 ][ bucket3 ] ...

1
struct bucket_t {
2
private:
3
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
4
    // SEL-first is better for armv7* and i386 and x86_64.
5
#if __arm64__
6
    explicit_atomic<uintptr_t> _imp;
7
    explicit_atomic<SEL> _sel;
8
#else
9
    explicit_atomic<SEL> _sel;
10
    explicit_atomic<uintptr_t> _imp;
11
#endif

1
// 1️⃣ decode isa（mask 取 class pointer）
2
Class cls = raw_isa & ISA_MASK;
3

4
// 2️⃣ cache_t 在 class 内的偏移
5
cache_t *cache = (cache_t *)((uint8_t*)cls + CACHE_OFFSET);
6

7
// 3️⃣ buckets 在 cache_t 内的偏移
8
bucket_t *buckets = *(bucket_t **)((uint8_t*)cache + BUCKETS_OFFSET);

1
/********************************************************************
2
 *
3
 * CacheLookup NORMAL|GETIMP|LOOKUP <function> MissLabelDynamic MissLabelConstant
4
 *
5
 * MissLabelConstant is only used for the GETIMP variant.
6
 *
7
 * Locate the implementation for a selector in a class method cache.
8
 *
9
 * When this is used in a function that doesn't hold the runtime lock,
10
 * this represents the critical section that may access dead memory.
11
 * If the kernel causes one of these functions to go down the recovery
12
 * path, we pretend the lookup failed by jumping the JumpMiss branch.
13
 *
14
 * Takes:
15
 *   x1 = selector
16
 *   x16 = class to be searched
17
 *
18
 * Kills:
19
 *    x9,x10,x11,x12,x13,x15,x17
20
 *
21
 * Untouched:
22
 *    x14
23
 *
24
 * On exit: (found) calls or returns IMP
25
 *                  with x16 = class, x17 = IMP
26
 *                  In LOOKUP mode, the two low bits are set to 0x3
27
 *                  if we hit a constant cache (used in objc_trace)
28
 *          (not found) jumps to LCacheMiss
29
 *                  with x15 = class
30
 *                  For constant caches in LOOKUP mode, the low bit
31
 *                  of x16 is set to 0x1 to indicate we had to fallback.
32
 *          In addition, when LCacheMiss is __objc_msgSend_uncached or
33
 *          __objc_msgLookup_uncached, 0x2 will be set in x16
34
 *          to remember we took the slowpath.
35
 *          So the two low bits of x16 on exit mean:
36
 *            0: dynamic hit
37
 *            1: fallback to the parent class, when there is a preoptimized cache
38
 *            2: slowpath
39
 *            3: preoptimized cache hit
40
 *
41
 ********************************************************************/
42

43
#define NORMAL 0
44
#define GETIMP 1
45
#define LOOKUP 2
46

47
// CacheHit: x17 = cached IMP, x10 = address of buckets, x1 = SEL, x16 = isa
48
.macro CacheHit
49
.if $0 == NORMAL
50
  TailCallCachedImp x17, x10, x1, x16  // authenticate and call imp
51
.elseif $0 == GETIMP
52
  mov  p0, p17
53
  cbz  p0, 9f          // don't ptrauth a nil imp
54
  AuthAndResignAsIMP x0, x10, x1, x16, x17  // authenticate imp and re-sign as IMP
55
9:  ret            // return IMP
56
.elseif $0 == LOOKUP
57
  // No nil check for ptrauth: the caller would crash anyway when they
58
  // jump to a nil IMP. We don't care if that jump also fails ptrauth.
59
  AuthAndResignAsIMP x17, x10, x1, x16, x10  // authenticate imp and re-sign as IMP
60
  cmp  x16, x15
61
  cinc  x16, x16, ne      // x16 += 1 when x15 != x16 (for instrumentation ; fallback to the parent class)
62
  ret        // return imp via x17
63
.else
64
.abort oops
65
.endif
66
.endmacro
67

68
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
69
  //
70
  // Restart protocol:
71
  //
72
  //   As soon as we're past the LLookupStart\Function label we may have
73
  //   loaded an invalid cache pointer or mask.
74
  //
75
  //   When task_restartable_ranges_synchronize() is called,
76
  //   (or when a signal hits us) before we're past LLookupEnd\Function,
77
  //   then our PC will be reset to LLookupRecover\Function which forcefully
78
  //   jumps to the cache-miss codepath which have the following
79
  //   requirements:
80
  //
81
  //   GETIMP:
82
  //     The cache-miss is just returning NULL (setting x0 to 0)
83
  //
84
  //   NORMAL and LOOKUP:
85
  //   - x0 contains the receiver
86
  //   - x1 contains the selector
87
  //   - x16 contains the isa
88
  //   - other registers are set as per calling conventions
89
  //
90

91
  mov  x15, x16      // stash the original isa
92
LLookupStart\Function:
93
  // p1 = SEL, p16 = isa
94
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
95
  ldr  p10, [x16, #CACHE]        // p10 = mask|buckets
96
  lsr  p11, p10, #48      // p11 = mask
97
  and  p10, p10, #0xffffffffffff  // p10 = buckets
98
  and  w12, w1, w11      // x12 = _cmd & mask
99
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
100
  ldr  p11, [x16, #CACHE]      // p11 = mask|buckets
101
#if CONFIG_USE_PREOPT_CACHES
102
#if __has_feature(ptrauth_calls)
103
  tbnz  p11, #0, LLookupPreopt\Function
104
  and  p10, p11, #0x0000ffffffffffff  // p10 = buckets
105
#else
106
  and  p10, p11, #0x0000fffffffffffe  // p10 = buckets
107
  tbnz  p11, #0, LLookupPreopt\Function
108
#endif
109
  eor  p12, p1, p1, LSR #7
110
  and  p12, p12, p11, LSR #48    // x12 = (_cmd ^ (_cmd >> 7)) & mask
111
#else
112
  and  p10, p11, #0x0000ffffffffffff  // p10 = buckets
113
  and  p12, p1, p11, LSR #48    // x12 = _cmd & mask
114
#endif // CONFIG_USE_PREOPT_CACHES
115
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
116
  ldr  p11, [x16, #CACHE]        // p11 = mask|buckets
117
  and  p10, p11, #~0xf      // p10 = buckets
118
  and  p11, p11, #0xf      // p11 = maskShift
119
  mov  p12, #0xffff
120
  lsr  p11, p12, p11      // p11 = mask = 0xffff >> p11
121
  and  p12, p1, p11      // x12 = _cmd & mask
122
#else
123
#error Unsupported cache mask storage for ARM64.
124
#endif
125

126
  add  p13, p10, p12, LSL #(1+PTRSHIFT)
127
            // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
128

129
            // do {
130
1:  ldp  p17, p9, [x13], #-BUCKET_SIZE  //     {imp, sel} = *bucket--
131
  cmp  p9, p1        //     if (sel != _cmd) {
132
  b.ne  3f        //         scan more
133
            //     } else {
134
2:  CacheHit \Mode        // hit:    call or return imp
135
            //     }
136
3:  cbz  p9, \MissLabelDynamic    //     if (sel == 0) goto Miss;
137
  cmp  p13, p10      // } while (bucket >= buckets)
138
  b.hs  1b
139

140
  // wrap-around:
141
  //   p10 = first bucket
142
  //   p11 = mask (and maybe other bits on LP64)
143
  //   p12 = _cmd & mask
144
  //
145
  // A full cache can happen with CACHE_ALLOW_FULL_UTILIZATION.
146
  // So stop when we circle back to the first probed bucket
147
  // rather than when hitting the first bucket again.
148
  //
149
  // Note that we might probe the initial bucket twice
150
  // when the first probed slot is the last entry.
151

152
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
153
  add  p13, p10, w11, UXTW #(1+PTRSHIFT)
154
            // p13 = buckets + (mask << 1+PTRSHIFT)
155
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
156
  add  p13, p10, p11, LSR #(48 - (1+PTRSHIFT))
157
            // p13 = buckets + (mask << 1+PTRSHIFT)
158
            // see comment about maskZeroBits
159
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
160
  add  p13, p10, p11, LSL #(1+PTRSHIFT)
161
            // p13 = buckets + (mask << 1+PTRSHIFT)
162
#else
163
#error Unsupported cache mask storage for ARM64.
164
#endif
165
  add  p12, p10, p12, LSL #(1+PTRSHIFT)
166
            // p12 = first probed bucket
167

168
            // do {
169
4:  ldp  p17, p9, [x13], #-BUCKET_SIZE  //     {imp, sel} = *bucket--
170
  cmp  p9, p1        //     if (sel == _cmd)
171
  b.eq  2b        //         goto hit
172
  cmp  p9, #0        // } while (sel != 0 &&
173
  ccmp  p13, p12, #0, ne    //     bucket > first_probed)
174
  b.hi  4b
175

176
LLookupEnd\Function:
177
LLookupRecover\Function:
178
  b  \MissLabelDynamic
179

180
#if CONFIG_USE_PREOPT_CACHES
181
#if CACHE_MASK_STORAGE != CACHE_MASK_STORAGE_HIGH_16
182
#error config unsupported
183
#endif
184
LLookupPreopt\Function:
185
#if __has_feature(ptrauth_calls)
186
  and  p10, p11, #0x007ffffffffffffe  // p10 = buckets
187
  autdb  x10, x16      // auth as early as possible
188
#endif
189

190
  // x12 = (_cmd - first_shared_cache_sel)
191
  adrp  x9, _MagicSelRef@PAGE
192
  ldr  p9, [x9, _MagicSelRef@PAGEOFF]
193
  sub  p12, p1, p9
194

195
  // w9  = ((_cmd - first_shared_cache_sel) >> hash_shift & hash_mask)
196
#if __has_feature(ptrauth_calls)
197
  // bits 63..60 of x11 are the number of bits in hash_mask
198
  // bits 59..55 of x11 is hash_shift
199

200
  lsr  x17, x11, #55      // w17 = (hash_shift, ...)
201
  lsr  w9, w12, w17      // >>= shift
202

203
  lsr  x17, x11, #60      // w17 = mask_bits
204
  mov  x11, #0x7fff
205
  lsr  x11, x11, x17      // p11 = mask (0x7fff >> mask_bits)
206
  and  x9, x9, x11      // &= mask
207
#else
208
  // bits 63..53 of x11 is hash_mask
209
  // bits 52..48 of x11 is hash_shift
210
  lsr  x17, x11, #48      // w17 = (hash_shift, hash_mask)
211
  lsr  w9, w12, w17      // >>= shift
212
  and  x9, x9, x11, LSR #53    // &=  mask
213
#endif
214

215
  // sel_offs is 26 bits because it needs to address a 64 MB buffer (~ 20 MB as of writing)
216
  // keep the remaining 38 bits for the IMP offset, which may need to reach
217
  // across the shared cache. This offset needs to be shifted << 2. We did this
218
  // to give it even more reach, given the alignment of source (the class data)
219
  // and destination (the IMP)
220
  ldr  x17, [x10, x9, LSL #3]    // x17 == (sel_offs << 38) | imp_offs
221
  cmp  x12, x17, LSR #38
222

223
.if \Mode == GETIMP
224
  b.ne  \MissLabelConstant    // cache miss
225
  sbfiz x17, x17, #2, #38         // imp_offs = combined_imp_and_sel[0..37] << 2
226
  sub  x0, x16, x17            // imp = isa - imp_offs
227
  SignAsImp x0, x17
228
  ret
229
.else
230
  b.ne  5f                // cache miss
231
  sbfiz x17, x17, #2, #38         // imp_offs = combined_imp_and_sel[0..37] << 2
232
  sub x17, x16, x17               // imp = isa - imp_offs
233
.if \Mode == NORMAL
234
  br  x17
235
.elseif \Mode == LOOKUP
236
  orr x16, x16, #3 // for instrumentation, note that we hit a constant cache
237
  SignAsImp x17, x10
238
  ret
239
.else
240
.abort  unhandled mode \Mode
241
.endif
242

243
5:  ldur  x9, [x10, #-16]      // offset -16 is the fallback offset
244
  add  x16, x16, x9      // compute the fallback isa
245
  b  LLookupStart\Function    // lookup again with a new isa
246
.endif
247
#endif // CONFIG_USE_PREOPT_CACHES
248

249
.endmacro

1
.macro MethodTableLookup
2

3
  SAVE_REGS MSGSEND
4

5
  // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
6
  // receiver and selector already in x0 and x1
7
  mov  x2, x16
8
  mov  x3, #3
9
  bl  _lookUpImpOrForward
10

11
  // IMP in x0
12
  mov  x17, x0
13

14
  RESTORE_REGS MSGSEND
15

16
.endmacro
17

18
  STATIC_ENTRY __objc_msgSend_uncached
19
  UNWIND __objc_msgSend_uncached, FrameWithNoSaves
20

21
  // THIS IS NOT A CALLABLE C FUNCTION
22
  // Out-of-band p15 is the class to search
23

24
  MethodTableLookup
25
  TailCallFunctionPointer x17
26

27
  END_ENTRY __objc_msgSend_uncached

1
.macro TailCallFunctionPointer
2
  // $0 = function pointer value
3
  br  $0
4
.endmacro