1 /*
2  * Copyright (C) 2011 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_RUNTIME_LOCK_WORD_H_
18 #define ART_RUNTIME_LOCK_WORD_H_
19 
20 #include <cstdint>
21 #include <iosfwd>
22 
23 #include <android-base/logging.h>
24 
25 #include "base/bit_utils.h"
26 #include "base/macros.h"
27 #include "read_barrier.h"
28 
29 namespace art HIDDEN {
30 namespace mirror {
31 class Object;
32 }  // namespace mirror
33 
34 class Monitor;
35 
36 /* The lock value itself as stored in mirror::Object::monitor_.  The two most significant bits
37  * encode the state. The four possible states are fat locked, thin/unlocked, hash code, and
38  * forwarding address.
39  *
40  * When the lock word is in the "thin" state and its bits are formatted as follows:
41  *
42  *  |33|2|2|222222221111|1111110000000000|
43  *  |10|9|8|765432109876|5432109876543210|
44  *  |00|m|r| lock count |thread id owner |
45  *
46  * The lock count is zero, but the owner is nonzero for a simply held lock.
47  * When the lock word is in the "fat" state and its bits are formatted as follows:
48  *
49  *  |33|2|2|2222222211111111110000000000|
50  *  |10|9|8|7654321098765432109876543210|
51  *  |01|m|r| MonitorId                  |
52  *
53  * When the lock word is in hash state and its bits are formatted as follows:
54  *
55  *  |33|2|2|2222222211111111110000000000|
56  *  |10|9|8|7654321098765432109876543210|
57  *  |10|m|r| HashCode                   |
58  *
59  * When the lock word is in forwarding address state and its bits are formatted as follows:
60  *
61  *  |33|2|22222222211111111110000000000|
62  *  |10|9|87654321098765432109876543210|
63  *  |11|0| ForwardingAddress           |
64  *
65  * The `r` bit stores the read barrier state.
66  * The `m` bit stores the mark bit state.
67  */
68 class LockWord {
69  public:
70   enum SizeShiftsAndMasks : uint32_t {  // private marker to avoid generate-operator-out.py from processing.
71     // Number of bits to encode the state, currently just fat or thin/unlocked or hash code.
72     kStateSize = 2,
73     kReadBarrierStateSize = 1,
74     kMarkBitStateSize = 1,
75     // Number of bits to encode the thin lock owner.
76     kThinLockOwnerSize = 16,
77     // Remaining bits are the recursive lock count. Zero means it is locked exactly once
78     // and not recursively.
79     kThinLockCountSize = 32 - kThinLockOwnerSize - kStateSize - kReadBarrierStateSize -
80         kMarkBitStateSize,
81 
82     // Thin lock bits. Owner in lowest bits.
83     kThinLockOwnerShift = 0,
84     kThinLockOwnerMask = (1 << kThinLockOwnerSize) - 1,
85     kThinLockOwnerMaskShifted = kThinLockOwnerMask << kThinLockOwnerShift,
86     kThinLockMaxOwner = kThinLockOwnerMask,
87     // Count in higher bits.
88     kThinLockCountShift = kThinLockOwnerSize + kThinLockOwnerShift,
89     kThinLockCountMask = (1 << kThinLockCountSize) - 1,
90     kThinLockMaxCount = kThinLockCountMask,
91     kThinLockCountOne = 1 << kThinLockCountShift,  // == 65536 (0x10000)
92     kThinLockCountMaskShifted = kThinLockCountMask << kThinLockCountShift,
93 
94     // State in the highest bits.
95     kStateShift = kReadBarrierStateSize + kThinLockCountSize + kThinLockCountShift +
96         kMarkBitStateSize,
97     kStateMask = (1 << kStateSize) - 1,
98     kStateMaskShifted = kStateMask << kStateShift,
99     kStateThinOrUnlocked = 0,
100     kStateFat = 1,
101     kStateHash = 2,
102     kStateForwardingAddress = 3,
103     kStateForwardingAddressShifted = kStateForwardingAddress << kStateShift,
104     kStateForwardingAddressOverflow = (1 + kStateMask - kStateForwardingAddress) << kStateShift,
105 
106     // Read barrier bit.
107     kReadBarrierStateShift = kThinLockCountSize + kThinLockCountShift,
108     kReadBarrierStateMask = (1 << kReadBarrierStateSize) - 1,
109     kReadBarrierStateMaskShifted = kReadBarrierStateMask << kReadBarrierStateShift,
110     kReadBarrierStateMaskShiftedToggled = ~kReadBarrierStateMaskShifted,
111 
112     // Mark bit.
113     kMarkBitStateShift = kReadBarrierStateSize + kReadBarrierStateShift,
114     kMarkBitStateMask = (1 << kMarkBitStateSize) - 1,
115     kMarkBitStateMaskShifted = kMarkBitStateMask << kMarkBitStateShift,
116     kMarkBitStateMaskShiftedToggled = ~kMarkBitStateMaskShifted,
117 
118     // GC state is mark bit and read barrier state.
119     kGCStateSize = kReadBarrierStateSize + kMarkBitStateSize,
120     kGCStateShift = kReadBarrierStateShift,
121     kGCStateMaskShifted = kReadBarrierStateMaskShifted | kMarkBitStateMaskShifted,
122     kGCStateMaskShiftedToggled = ~kGCStateMaskShifted,
123 
124     // When the state is kHashCode, the non-state bits hold the hashcode.
125     // Note Object.hashCode() has the hash code layout hardcoded.
126     kHashShift = 0,
127     kHashSize = 32 - kStateSize - kReadBarrierStateSize - kMarkBitStateSize,
128     kHashMask = (1 << kHashSize) - 1,
129     kMaxHash = kHashMask,
130 
131     // Forwarding address shift.
132     kForwardingAddressShift = kObjectAlignmentShift,
133 
134     kMonitorIdShift = kHashShift,
135     kMonitorIdSize = kHashSize,
136     kMonitorIdMask = kHashMask,
137     kMonitorIdAlignmentShift = 32 - kMonitorIdSize,
138     kMonitorIdAlignment = 1 << kMonitorIdAlignmentShift,
139     kMaxMonitorId = kMaxHash
140   };
141 
FromThinLockId(uint32_t thread_id,uint32_t count,uint32_t gc_state)142   static LockWord FromThinLockId(uint32_t thread_id, uint32_t count, uint32_t gc_state) {
143     CHECK_LE(thread_id, static_cast<uint32_t>(kThinLockMaxOwner));
144     CHECK_LE(count, static_cast<uint32_t>(kThinLockMaxCount));
145     // DCHECK_EQ(gc_bits & kGCStateMaskToggled, 0U);
146     return LockWord((thread_id << kThinLockOwnerShift) |
147                     (count << kThinLockCountShift) |
148                     (gc_state << kGCStateShift) |
149                     (kStateThinOrUnlocked << kStateShift));
150   }
151 
FromForwardingAddress(size_t target)152   static LockWord FromForwardingAddress(size_t target) {
153     DCHECK_ALIGNED(target, (1 << kStateSize));
154     return LockWord((target >> kForwardingAddressShift) | kStateForwardingAddressShifted);
155   }
156 
FromHashCode(uint32_t hash_code,uint32_t gc_state)157   static LockWord FromHashCode(uint32_t hash_code, uint32_t gc_state) {
158     CHECK_LE(hash_code, static_cast<uint32_t>(kMaxHash));
159     // DCHECK_EQ(gc_bits & kGCStateMaskToggled, 0U);
160     return LockWord((hash_code << kHashShift) |
161                     (gc_state << kGCStateShift) |
162                     (kStateHash << kStateShift));
163   }
164 
FromDefault(uint32_t gc_state)165   static LockWord FromDefault(uint32_t gc_state) {
166     return LockWord(gc_state << kGCStateShift);
167   }
168 
IsDefault(LockWord lw)169   static bool IsDefault(LockWord lw) {
170     return LockWord().GetValue() == lw.GetValue();
171   }
172 
Default()173   static LockWord Default() {
174     return LockWord();
175   }
176 
177   enum LockState {
178     kUnlocked,    // No lock owners.
179     kThinLocked,  // Single uncontended owner.
180     kFatLocked,   // See associated monitor.
181     kHashCode,    // Lock word contains an identity hash.
182     kForwardingAddress,  // Lock word contains the forwarding address of an object.
183   };
184 
GetState()185   LockState GetState() const {
186     CheckReadBarrierState();
187     if (gUseReadBarrier || gUseUserfaultfd) {
188       if ((value_ & kGCStateMaskShiftedToggled) == 0) {
189         return kUnlocked;
190       }
191     } else if (value_ == 0) {
192       return kUnlocked;
193     }
194     uint32_t internal_state = (value_ >> kStateShift) & kStateMask;
195     switch (internal_state) {
196       case kStateThinOrUnlocked:
197         return kThinLocked;
198       case kStateHash:
199         return kHashCode;
200       case kStateForwardingAddress:
201         return kForwardingAddress;
202       default:
203         DCHECK_EQ(internal_state, static_cast<uint32_t>(kStateFat));
204         return kFatLocked;
205     }
206   }
207 
ReadBarrierState()208   uint32_t ReadBarrierState() const {
209     return (value_ >> kReadBarrierStateShift) & kReadBarrierStateMask;
210   }
211 
GCState()212   uint32_t GCState() const {
213     return (value_ & kGCStateMaskShifted) >> kGCStateShift;
214   }
215 
SetReadBarrierState(uint32_t rb_state)216   void SetReadBarrierState(uint32_t rb_state) {
217     DCHECK_EQ(rb_state & ~kReadBarrierStateMask, 0U);
218     DCHECK(rb_state == ReadBarrier::NonGrayState() ||
219            rb_state == ReadBarrier::GrayState()) << rb_state;
220     DCHECK_NE(static_cast<uint32_t>(GetState()), static_cast<uint32_t>(kForwardingAddress));
221     // Clear and or the bits.
222     value_ &= ~(kReadBarrierStateMask << kReadBarrierStateShift);
223     value_ |= (rb_state & kReadBarrierStateMask) << kReadBarrierStateShift;
224   }
225 
226 
MarkBitState()227   uint32_t MarkBitState() const {
228     return (value_ >> kMarkBitStateShift) & kMarkBitStateMask;
229   }
230 
SetMarkBitState(uint32_t mark_bit)231   void SetMarkBitState(uint32_t mark_bit) {
232     DCHECK_EQ(mark_bit & ~kMarkBitStateMask, 0U);
233     DCHECK_NE(static_cast<uint32_t>(GetState()), static_cast<uint32_t>(kForwardingAddress));
234     // Clear and or the bits.
235     value_ &= kMarkBitStateMaskShiftedToggled;
236     value_ |= mark_bit << kMarkBitStateShift;
237   }
238 
239   // Return the owner thin lock thread id.
240   uint32_t ThinLockOwner() const;
241 
242   // Return the number of times a lock value has been re-locked. Only valid in thin-locked state.
243   // If the lock is held only once the return value is zero.
244   uint32_t ThinLockCount() const;
245 
246   // Return the Monitor encoded in a fat lock.
247   Monitor* FatLockMonitor() const;
248 
249   // Return the forwarding address stored in the monitor.
250   size_t ForwardingAddress() const;
251 
252   // Constructor a lock word for inflation to use a Monitor.
253   LockWord(Monitor* mon, uint32_t gc_state);
254 
255   // Return the hash code stored in the lock word, must be kHashCode state.
256   int32_t GetHashCode() const;
257 
258   template <bool kIncludeReadBarrierState>
Equal(LockWord lw1,LockWord lw2)259   static bool Equal(LockWord lw1, LockWord lw2) {
260     if (kIncludeReadBarrierState) {
261       return lw1.GetValue() == lw2.GetValue();
262     }
263     return lw1.GetValueWithoutGCState() == lw2.GetValueWithoutGCState();
264   }
265 
Dump(std::ostream & os)266   void Dump(std::ostream& os) {
267     os << "LockWord:" << std::hex << value_;
268   }
269 
270  private:
271   // Default constructor with no lock ownership.
272   LockWord();
273 
LockWord(uint32_t val)274   explicit LockWord(uint32_t val) : value_(val) {
275     // Make sure adding the overflow causes an overflow.
276     constexpr uint64_t overflow = static_cast<uint64_t>(kStateForwardingAddressShifted) +
277         static_cast<uint64_t>(kStateForwardingAddressOverflow);
278     constexpr bool is_larger = overflow > static_cast<uint64_t>(0xFFFFFFFF);
279     static_assert(is_larger, "should have overflowed");
280     static_assert(
281          (~kStateForwardingAddress & kStateMask) == 0,
282         "READ_BARRIER_MARK_REG relies on the forwarding address state being only one bits");
283     CheckReadBarrierState();
284   }
285 
286   // Disallow this in favor of explicit Equal() with the
287   // kIncludeReadBarrierState param to make clients be aware of the
288   // read barrier state.
289   bool operator==(const LockWord& rhs) = delete;
290 
CheckReadBarrierState()291   void CheckReadBarrierState() const {
292     if (kIsDebugBuild && ((value_ >> kStateShift) & kStateMask) != kStateForwardingAddress) {
293       uint32_t rb_state = ReadBarrierState();
294       if (!gUseReadBarrier) {
295         DCHECK_EQ(rb_state, 0U);
296       } else {
297         DCHECK(rb_state == ReadBarrier::NonGrayState() ||
298                rb_state == ReadBarrier::GrayState()) << rb_state;
299       }
300     }
301   }
302 
303   // Note GetValue() includes the read barrier bits and comparing (==)
304   // GetValue() between two lock words to compare the lock states may
305   // not work. Prefer Equal() or GetValueWithoutReadBarrierState().
GetValue()306   uint32_t GetValue() const {
307     CheckReadBarrierState();
308     return value_;
309   }
310 
GetValueWithoutGCState()311   uint32_t GetValueWithoutGCState() const {
312     CheckReadBarrierState();
313     return value_ & kGCStateMaskShiftedToggled;
314   }
315 
316   // Only Object should be converting LockWords to/from uints.
317   friend class mirror::Object;
318 
319   // The encoded value holding all the state.
320   uint32_t value_;
321 };
322 EXPORT std::ostream& operator<<(std::ostream& os, LockWord::LockState code);
323 
324 }  // namespace art
325 
326 #endif  // ART_RUNTIME_LOCK_WORD_H_
327