1 /*
2  * Copyright (C) 2023 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 BERBERIS_RUNTIME_PRIMITIVES_TRANSLATION_CACHE_H_
18 #define BERBERIS_RUNTIME_PRIMITIVES_TRANSLATION_CACHE_H_
19 
20 #include <atomic>
21 #include <cstdint>
22 #include <mutex>
23 
24 #include "berberis/base/forever_map.h"
25 #include "berberis/base/forever_set.h"
26 #include "berberis/guest_state/guest_addr.h"
27 #include "berberis/runtime_primitives/host_code.h"
28 #include "berberis/runtime_primitives/runtime_library.h"
29 #include "berberis/runtime_primitives/table_of_tables.h"
30 
31 namespace berberis {
32 
33 // Translated code entry.
34 // ATTENTION: associated guest pc and host code pointer never change!
35 // TODO(b/232598137): consider making TranslationCache-internal!
36 struct GuestCodeEntry {
37   std::atomic<HostCode>* const host_code;
38 
39   // Fields below are protected by TranslationCache mutex.
40 
41   uint32_t host_size;
42 
43   // Must be greater than zero even for special entries, such as wrapped or
44   // translation-in-progress.
45   uint32_t guest_size;
46 
47   enum class Kind {
48     kInterpreted,
49     kLightTranslated,
50     kHeavyOptimized,
51     kGuestWrapped,
52     kHostWrapped,
53     // E.g. translating, wrapping, invalidating.
54     kUnderProcessing,
55     // E.g. non-executable, unpredictable.
56     kSpecialHandler,
57   };
58 
59   Kind kind;
60 
61   // The number of times this entry has been invoked.
62   uint32_t invocation_counter;
63 };
64 
65 // Cache of translated code regions:
66 // - Thread-safe: coordinates translation across threads.
67 // - Provides host code to execute for a given guest pc.
68 //   This is lock- and wait-free.
69 // - Tracks translated regions and invalidates them when corresponding guest code is updated.
70 //   This is protected by mutex.
71 //
72 // Each guest code cache entry is not necessarily translated code. Each entry is a _state machine_,
73 // where only one state actually contains translated guest code. However, each entry always contains
74 // a pointer to code that should be executed; such code will either be translated code, or an
75 // berberis function e.g. to call the interpreter or to call a 'trampoline' function which
76 // calls a host function, or a no-op function for when the entry is to be invalidated, etc.
77 //
78 // The possible guest entry states are:
79 // - Not Translated. Execution should interpret or translate.
80 //   Nothing to track.
81 // - Translating. 'Locked' by a translating thread. Execution should interpret or wait for
82 //   translation to complete.
83 //   At this point the guest range for a region is still unknown, since we don't know how much of
84 //   the guest code at the start address can be translated to a continuous region until it is
85 //   translated.
86 //   If ANY guest code gets updated, translation should be abandoned (invalidated). Because we don't
87 //   know the size of the region before translation, any updated code could overlap with a region
88 //   that is being translated, and thereby invalidates the translation. (Also, in the future
89 //   translated regions may not be simple linear blocks.)
90 // - Invalidating. Execution should interpret or wait.
91 //   'Locked' by a translating thread, which should abandon the translation.
92 //   Nothing to track.
93 // - Translated. Execution should run generated code.
94 //   Guest range is now known. If guest code that overlaps the region gets updated, the entry should
95 //   be invalidated.
96 //
97 // There are more entries that do not correspond to real guest code:
98 // - wrapping. Execution should wait.
99 //   'locked' by a wrapper generating thread.
100 //   Nothing to track.
101 // - wrapped. Execution should run generated code.
102 //   Nothing to track.
103 //
104 class TranslationCache {
105  public:
106   TranslationCache() = default;
107   TranslationCache(const TranslationCache&) = delete;
108   TranslationCache& operator=(const TranslationCache&) = delete;
109 
110   [[nodiscard]] static TranslationCache* GetInstance();
111 
SetStop(GuestAddr pc)112   bool SetStop(GuestAddr pc) {
113     auto expected = kEntryNotTranslated;  // expect default value.
114     auto host_code_ptr = GetHostCodePtrWritable(pc);
115     if (host_code_ptr->compare_exchange_strong(expected, kEntryStop)) {
116       return true;
117     }
118     return expected == kEntryStop;
119   }
120 
TestingClearStop(GuestAddr pc)121   void TestingClearStop(GuestAddr pc) {
122     GetHostCodePtrWritable(pc)->store(kEntryNotTranslated);  // set default value.
123   }
124 
125   // Inserts NotTranslated entry for the given PC if not inserted already. Then transitions from
126   // NotTranslated state to Translating, or returns nullptr if the entry has not yet been
127   // interpreted at least counter_threshold times, in which case the entry's interpretation counter
128   // will be incremented. Also returns nullptr if the state was not Translating, or if somehow there
129   // is no entry for the given PC.
130   [[nodiscard]] GuestCodeEntry* AddAndLockForTranslation(GuestAddr pc, uint32_t counter_threshold);
131 
132   // Locks entry for the given PC for translation if it's currently in LightTranslated state.
133   // If successful returns the locked entry, otherwise returns nullptr.
134   [[nodiscard]] GuestCodeEntry* LockForGearUpTranslation(GuestAddr pc);
135 
136   // Transitions the entry for the given guest address from Translating to Translated, making it
137   // available to other threads.
138   void SetTranslatedAndUnlock(GuestAddr pc,
139                               GuestCodeEntry* entry,
140                               uint32_t guest_size,
141                               GuestCodeEntry::Kind kind,
142                               HostCodePiece code);
143 
144   // ATTENTION: interpreter doesn't handle code that is being wrapped!
145   [[nodiscard]] GuestCodeEntry* AddAndLockForWrapping(GuestAddr pc);
146 
147   void SetWrappedAndUnlock(GuestAddr pc,
148                            GuestCodeEntry* entry,
149                            bool is_host_func,
150                            HostCodePiece code);
151 
152   [[nodiscard]] bool IsHostFunctionWrapped(GuestAddr pc) const;
153 
154   // TODO(b/232598137): flawed, used only in profiler - replace or remove!
155   [[nodiscard]] GuestCodeEntry* ProfilerLookupGuestCodeEntryByGuestPC(GuestAddr pc);
156 
157   [[nodiscard]] uint32_t GetInvocationCounter(GuestAddr pc) const;
158 
159   // Find guest entry pc by a host pc.
160   // WARNING: SUPER SLOW! Use it with caution.
161   GuestAddr SlowLookupGuestCodeEntryPCByHostPC(HostCode pc);
162 
163   // Invalidate region of entries.
164   void InvalidateGuestRange(GuestAddr start, GuestAddr end);
165 
main_table_ptr()166   [[nodiscard]] const std::atomic<std::atomic<HostCode>*>* main_table_ptr() const {
167     return address_map_.main_table();
168   }
169 
GetHostCodePtr(GuestAddr pc)170   [[nodiscard]] const std::atomic<HostCode>* GetHostCodePtr(GuestAddr pc) {
171     return address_map_.GetPointer(pc);
172   }
173 
PreZygoteForkUnsafe()174   void PreZygoteForkUnsafe() {
175     // Zygote's fork doesn't allow unrecognized open file descriptors, so we close them.
176     address_map_.CloseDefaultMemfdUnsafe();
177   }
178 
LookupGuestCodeEntryUnsafeForTesting(GuestAddr pc)179   [[nodiscard]] GuestCodeEntry* LookupGuestCodeEntryUnsafeForTesting(GuestAddr pc) {
180     return LookupGuestCodeEntryUnsafe(pc);
181   }
182 
183  private:
184   [[nodiscard]] GuestCodeEntry* LookupGuestCodeEntryUnsafe(GuestAddr pc);
185   [[nodiscard]] const GuestCodeEntry* LookupGuestCodeEntryUnsafe(GuestAddr pc) const;
GetHostCodePtrWritable(GuestAddr pc)186   [[nodiscard]] std::atomic<HostCode>* GetHostCodePtrWritable(GuestAddr pc) {
187     return address_map_.GetPointer(pc);
188   }
189 
190   // Add call record for an address, reuse if already here.
191   [[nodiscard]] GuestCodeEntry* AddUnsafe(GuestAddr pc,
192                                           std::atomic<HostCode>* host_code_ptr,
193                                           HostCodePiece host_code_piece,
194                                           uint32_t guest_size,
195                                           GuestCodeEntry::Kind kind,
196                                           bool* added);
197 
198   void LockForTranslationUnsafe(GuestCodeEntry* entry);
199 
200   void InvalidateEntriesBeingTranslatedUnsafe();
201 
202   // ATTENTION: all GuestCodeEntry state transitions must be protected by mutex!
203   mutable std::mutex mutex_;
204 
205   // Stores guest entries that are in Translating state. These will also be in guest_entries_.
206   ForeverSet<GuestCodeEntry*> translating_;
207 
208   // Guest code entries for all guest PCs ever looked up.
209   ForeverMap<GuestAddr, GuestCodeEntry> guest_entries_;
210 
211   // Maps guest code addresses to the host address of the translated code.
212   TableOfTables<GuestAddr, HostCode> address_map_{kEntryNotTranslated};
213 
214   // The size of the largest entry.
215   // Wrapped entries do not update it, so if we only have wrapped the size
216   // should be 1 at least. This is practically only important for tests.
217   size_t max_guest_size_{1};
218 };
219 
220 }  // namespace berberis
221 
222 #endif  // BERBERIS_RUNTIME_PRIMITIVES_TRANSLATION_CACHE_H_
223