Line data Source code
1 : #ifndef HEADER_fd_src_flamenco_runtime_program_fd_program_cache_h
2 : #define HEADER_fd_src_flamenco_runtime_program_fd_program_cache_h
3 :
4 : #include "../../types/fd_types_custom.h"
5 : #include "../../../funk/fd_funk_base.h"
6 : #include "../../../ballet/sbpf/fd_sbpf_loader.h"
7 :
8 : /* fd_program_cache contains the core logic for the program cache's
9 : behavior, including accesses, insertions, updates, and verifies.
10 : Specifically, the program cache operates in a lazy manner where
11 : programs are only inserted / reverified when they are referenced
12 : in a transaction.
13 :
14 : The program cache lives in Funk and is fork-aware. The size of the
15 : program cache is bounded by the size of the Funk instance.
16 :
17 : On bootup, the program cache starts out empty. As programs (defined
18 : as accounts owned by one of the BPF loaders that can be invoked
19 : by the user) are referenced as account keys within transactions
20 : (either statically or through address lookup tables),
21 : `fd_program_cache_update_program()` accepts a pubkey as input and
22 : will attempt to either insert the program into the cache (performing
23 : sBPF + ELF validations) if missing, or reverify the program if
24 : needed.
25 :
26 : During transaction execution, we accumulate any program pubkeys that
27 : are deployed, extended, or upgraded (basically, any calls to
28 : `fd_deploy_program()` in the BPF loaders) since those instructions
29 : may have changed the program's executable data (closed / retracted
30 : programs also do, but see comments below on how we handle that).
31 : After a transaction is executed successfully, we iterate through
32 : these accumulated program keys and queue them for reverification.
33 : To mark a program for reverification, we simply update the
34 : `last_slot_modified` field to the current slot. When the program is
35 : next referenced in a transaction, `fd_program_cache_update_program()`
36 : will check if the program was modified since the last time it was
37 : reverified, and reverify the program accordingly to update the cache
38 : entry's sBPF info, calldests, etc. Once the program has been
39 : reverified, the entry's `last_slot_verified` field will be updated
40 : to the current slot.
41 :
42 : When a program is reverified and updated in the cache, we clone the
43 : record down to the current funk transaction from an ancestor, and
44 : then modify the record within the current funk transaction.
45 :
46 : A program cache entry may also be reverified after crossing an
47 : epoch boundary, even if it was not modified recently. This is because
48 : the network's active feature set may have changed, and any previously
49 : {valid,invalid} programs may now be {valid,invalid}. Therefore,
50 : if a program is referenced in a transaction that has not been
51 : reverified since the last epoch (regardless of it having been
52 : modified or not), it will be reverified and updated.
53 :
54 : If a program fails verification due to invalid ELF headers / sBPF
55 : loading failures, then we update the `failed_verification` tag,
56 : set `last_slot_verified` to the current slot, and set
57 : `last_slot_modified` to 0. All other fields have undefined value. A
58 : future program upgrade / network feature set change could make this
59 : program valid again.
60 :
61 : A key invariant with the program cache design is that it does not
62 : evict any entries - it only grows through the lifetime of the
63 : client's execution. Because of this invariant, we do not touch cache
64 : entries for programs which are closed, and instead let
65 : transaction-level account loading and BPF loader program checks
66 : catch cases where a user tries to invoke a closed program.
67 :
68 : Another key invariant is that for any given program, we will insert /
69 : update its cache entry at most ONCE per slot, and this will happen
70 : the FIRST time the program is referenced in a transaction before it
71 : is dispatched to the exec tiles. This is important because it ensures
72 : that the replay tile does not race with the exec tiles by updating
73 : the cache entry for a program while an exec tile is already executing
74 : it. Even if a program is upgraded in the same slot after it has been
75 : reverified, the network forbids invoking programs in the same slot as
76 : they are deployed / upgraded, so we can wait for a future slot to
77 : update the program cache entry when it is invoked next.
78 :
79 : EDGE CASES (and how we handle them):
80 : - Deploying programs
81 : - Deploying a program
82 : - `fd_program_cache_queue_program_for_reverification()` will
83 : not do anything because the program does not exist in the
84 : cache yet, and so there is nothing to update. The next time
85 : the program is referenced in a transaction,
86 : `fd_program_cache_update_program()` will see that the program
87 : is missing in the cache and will perform ELF / sBPF
88 : verifications and insert the entry into the cache.
89 : - Deploying and invoking in the same slot
90 : - BPF loader checks will fail because the program account's
91 : slot value will be equal to the current slot, which
92 : gets caught by the `DelayedVisibility` checks.
93 : - Upgrading programs
94 : - Upgrading a program
95 : - The program account will have been referenced as writable
96 : in the transaction, and thus
97 : `fd_program_cache_queue_program_for_reverification()` will
98 : update the `last_slot_modified` to queue the program
99 : for reverification the next time it is referenced in a
100 : transaction.
101 : - Upgrading and invoking in the same transaction
102 : - Same as "deploy" case
103 : - Closing programs
104 : - Closing a program
105 : - We do not touch the program cache here. We let account
106 : loading / BPF loader checks handle cases where a user may try
107 : to invoke a closed program.
108 : - Closing + invoking a program in the same transaction
109 : - The program account's state will be set to uninitialized /
110 : retracted, so any future instructions that invoke the program
111 : will fail when the BPF loader checks the account state.
112 : - Closing + invoking a program in separate transactions
113 : - The program account's owner will be set to the system program
114 : and thus fail account loading checks.
115 :
116 : TL;DR: Deploys and upgrades are treated the same way - if the cache
117 : entry exists, it's queued for reverification. If it doesn't, the
118 : program cache will verify and add it to the cache the next time it's
119 : invoked. Cases where the program is closed / retracted are not
120 : explicitly handled.
121 :
122 : Q: Is the program cache concurrency-safe?
123 : A: Yes. In any given slot, the replay tile first iterates through
124 : each transaction in a single-threaded manner. For each
125 : transaction, it will read the accounts and will call
126 : `fd_program_cache_update_program()` for each program, and then
127 : dispatch the transaction to the exec tiles. This means
128 : that the first time any program is referenced in any transaction
129 : in the slot, the replay tile will update the associated program
130 : cache entry before dispatching the transaction to any of the exec
131 : tiles. Furthermore, we are not allowed to insert / reverify a
132 : program cache entry more than once within a single slot. This
133 : guarantees that any read / write accesses for a particular program
134 : in the program cache by the exec tiles will occur after the cache
135 : entries have been processed by the replay tile in any given slot.
136 : Furthermore, if the program was upgraded, the exec tile simply
137 : updates a single header in the existing program cache entry
138 : `last_slot_modified`, which is behind a blocking write lock.
139 : Note that if there is read-write or write-write-contention
140 : between two transactions for any accounts, the scheduler will
141 : ensure that those two transactions are scheduled and finalized
142 : in a serial manner. */
143 :
144 : /* `fd_program_cache_entry` defines the structure for a single
145 : program cache entry. */
146 : struct fd_program_cache_entry {
147 : ulong magic;
148 :
149 : /* For any programs that fail verification, we retain this flag for
150 : to prevent any reverification attempts for the remainder of the
151 : epoch / until the program is modified again (instead of removing
152 : them from the cache). When `failed_verification` is set,
153 : the values of all other fields except for
154 : `last_slot_verified` are undefined. Any invocations of a
155 : program that fails verification will continue to fail until the
156 : program is queued for reverification by an eligible BPF loader
157 : instruction (e.g. the program is upgraded). */
158 : uchar failed_verification;
159 :
160 : /* Stores the last slot the program was modified. This field is
161 : updated at the end of a transaction for a program account that was
162 : referenced as a writable account within an instruction. For any
163 : programs that are freshly added to the cache, this field is set to
164 : 0. */
165 : ulong last_slot_modified;
166 :
167 : /* Stores the last slot verification checks were ran for a program.
168 : Programs are reverified if they are mentioned in the current
169 : transaction, and if one of the following are true:
170 : - It is the first time they are referenced in a transaction in the
171 : current epoch
172 : - The program was a writable account in a transaction
173 :
174 : We reverify referenced programs at least once every epoch
175 : regardless of whether they were modified or not because changes
176 : in the active feature set may cause existing deployed programs
177 : to be invalided (e.g. stricter ELF / VM / sBPF checks). */
178 : ulong last_slot_verified;
179 :
180 : ulong entry_pc;
181 : ulong text_cnt;
182 : ulong text_off;
183 : ulong text_sz;
184 :
185 : ulong rodata_sz;
186 :
187 : /* We use offsets to store the calldests and rodata in order to keep
188 : the cache entry gaddr-aware so it can be passed around different
189 : tiles. */
190 : ulong calldests_shmem_off;
191 : ulong rodata_off;
192 :
193 : /* SBPF version, SIMD-0161 */
194 : ulong sbpf_version;
195 : };
196 : typedef struct fd_program_cache_entry fd_program_cache_entry_t;
197 :
198 : static inline uchar *
199 36 : fd_program_cache_get_rodata( fd_program_cache_entry_t const * cache_entry ) {
200 36 : return (uchar *)cache_entry + cache_entry->rodata_off;
201 36 : }
202 :
203 : static inline fd_sbpf_calldests_t *
204 33 : fd_program_cache_get_calldests_shmem( fd_program_cache_entry_t const * cache_entry ) {
205 33 : return (fd_sbpf_calldests_t *)((uchar *)cache_entry + cache_entry->calldests_shmem_off);
206 33 : }
207 :
208 : static inline fd_sbpf_calldests_t *
209 0 : fd_program_cache_get_calldests( fd_program_cache_entry_t const * cache_entry ) {
210 0 : return fd_sbpf_calldests_join( fd_program_cache_get_calldests_shmem( cache_entry ) );
211 0 : }
212 :
213 : /* arbitrary unique value, in this case
214 : echo -n "fd_program_cache_entry" | sha512sum | head -c 16 */
215 48 : #define FD_PROGRAM_CACHE_ENTRY_MAGIC 0xb45640baf006ddf6
216 :
217 : FD_PROTOTYPES_BEGIN
218 :
219 : fd_program_cache_entry_t *
220 : fd_program_cache_entry_new( void * mem,
221 : fd_sbpf_elf_info_t const * elf_info,
222 : ulong last_slot_modified,
223 : ulong last_slot_verified );
224 :
225 : ulong
226 : fd_program_cache_entry_footprint( fd_sbpf_elf_info_t const * elf_info );
227 :
228 : /* Gets the program cache funk record key for a given program pubkey. */
229 : fd_funk_rec_key_t
230 : fd_program_cache_key( fd_pubkey_t const * pubkey );
231 :
232 : /* Loads a single program cache entry for a given pubkey. Returns 0 on
233 : success and -1 on failure. On success, `*cache_entry` holds a pointer
234 : to the program cache entry. */
235 : int
236 : fd_program_cache_load_entry( fd_funk_t const * funk,
237 : fd_funk_txn_xid_t const * xid,
238 : fd_pubkey_t const * program_pubkey,
239 : fd_program_cache_entry_t const ** cache_entry );
240 :
241 : /* Parses the programdata from a program account. Returns a pointer to
242 : the program data and sets `out_program_data_len` on success. Returns
243 : NULL on failure or if the program account is not owned by a BPF
244 : loader program ID, and leaves `out_program_data_len` in an undefined
245 : state. Reasons for failure vary on the loader version. See the
246 : respective functions in this file for more details.
247 :
248 : This is essentially load_program_with_pubkey(), sans the ELF parsing
249 : and whatnot which is done in load_program_from_bytes(). */
250 : uchar const *
251 : fd_program_cache_get_account_programdata( fd_funk_t const * funk,
252 : fd_funk_txn_xid_t const * xid,
253 : fd_txn_account_t const * program_acc,
254 : ulong * out_program_data_len );
255 :
256 : /* Updates the program cache for a single program. This function is
257 : called for every program that is referenced in a transaction, plus
258 : every single account in a lookup table referenced in the transaction.
259 : This function...
260 : - Accepts a pubkey and reads the programdata from the account
261 : - Creates a program cache entry for the program if it doesn't exist
262 : in the cache already
263 : - Reverifies programs if either...
264 : - The program was recently modified in a STRICTLY PRIOR SLOT
265 : - The program has not been verified yet for the current epoch
266 : - Invalidated programs that fail ELF / sBPF verification
267 : - Updates the program cache entry for the program after
268 : reverification (syscalls, calldests, etc)
269 :
270 : With this design, the program cache is designed to only grow as new
271 : programs are deployed / invoked. If a program fails verification, it
272 : stays in the cache so that repeated calls won't DOS the validator by
273 : forcing reverifications (since we won't be able to distinguish failed
274 : verifications from new deployments).
275 :
276 : When a program is reverified (and the cache entry already exists in
277 : some ancestor funk transaction), we clone the record down to the
278 : current funk transaction and acquire a blocking write lock on the
279 : cloned funk record. */
280 : void
281 : fd_program_cache_update_program( fd_bank_t * bank,
282 : fd_funk_t * funk,
283 : fd_funk_txn_xid_t const * xid,
284 : fd_pubkey_t const * program_key,
285 : fd_spad_t * runtime_spad );
286 :
287 : /* Queues a single program account for reverification. This function
288 : queries the cache for an existing entry and queues it for
289 : reverification by setting the `last_slot_modified` field in the
290 : program cache entry to the current slot. If the cache entry
291 : for the program does not exist yet (e.g. newly deployed programs),
292 : this function does nothing and instead,
293 : `fd_program_cache_publish_failed_verification_rec()` will insert
294 : the program into the cache.
295 :
296 : If the record exists in the program cache, this function will
297 : acquire a write-lock on the program cache entry. */
298 : void
299 : fd_program_cache_queue_program_for_reverification( fd_funk_t * funk,
300 : fd_funk_txn_xid_t const * xid,
301 : fd_pubkey_t const * program_key,
302 : ulong current_slot );
303 :
304 : /* fd_funk_rec_insert_para does thread-safe insertion of a funk record.
305 :
306 : Detailed Behavior:
307 :
308 : More specifically, first this function will query the transaction
309 : stack to identify what the youngest transaction with the key is.
310 : If a record is found in some ancestor txn or if the
311 : record doesn't exist, we will allocate a new account record and add
312 : this into the transaction. In either case, the record is set to the
313 : given value. */
314 :
315 : int
316 : fd_funk_rec_insert_para( fd_funk_t * funk,
317 : fd_funk_txn_xid_t const * xid,
318 : fd_funk_rec_key_t const * key,
319 : ulong val_align,
320 : ulong val_sz,
321 : void * val );
322 :
323 : FD_PROTOTYPES_END
324 :
325 : #endif /* HEADER_fd_src_flamenco_runtime_program_fd_program_cache_h */
|
