Line data Source code
1 : #ifndef HEADER_fd_src_flamenco_runtime_fd_alut_h
2 : #define HEADER_fd_src_flamenco_runtime_fd_alut_h
3 :
4 : /* fd_alut.h provides APIs for interpreting Solana address lookup table
5 : usages.
6 :
7 : https://solana.com/de/developers/guides/advanced/lookup-tables */
8 :
9 : #include "../../ballet/txn/fd_txn.h"
10 : #include "../../ballet/base58/fd_base58.h"
11 : #include "fd_runtime_err.h"
12 : #include "fd_system_ids.h"
13 : #include "sysvar/fd_sysvar_base.h"
14 :
15 9696 : #define FD_ADDRLUT_STATUS_ACTIVATED (0)
16 4854 : #define FD_ADDRLUT_STATUS_DEACTIVATING (1)
17 8 : #define FD_ADDRLUT_STATUS_DEACTIVATED (2)
18 :
19 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L19 */
20 9710 : #define FD_LOOKUP_TABLE_META_SIZE (56)
21 :
22 : /* https://github.com/solana-program/address-lookup-table/blob/a9fc56e413727e2a9d6dce58df6691f4b45320d7/program/src/state.rs#L12 */
23 0 : #define FD_LOOKUP_TABLE_MAX_ADDRESSES (256)
24 0 : #define FD_LOOKUP_TABLE_SZ_MAX (FD_LOOKUP_TABLE_META_SIZE + (FD_LOOKUP_TABLE_MAX_ADDRESSES * 32UL))
25 :
26 : /* Discriminants for the ProgramState enum wrapping the lookup table
27 : metadata in the on-disk account format. */
28 :
29 4857 : #define FD_ALUT_STATE_DISC_UNINITIALIZED (0U)
30 0 : #define FD_ALUT_STATE_DISC_LOOKUP_TABLE (1U)
31 :
32 : /* fd_alut_meta_t is the in-memory representation of address lookup
33 : table account state (ProgramState + LookupTableMeta in Agave).
34 : The on-disk format is 56 bytes: u32 discriminant,
35 : u64 deactivation_slot, u64 last_extended_slot,
36 : u8 last_extended_slot_start_index, Option<Pubkey> authority
37 : (1-byte tag + 32 bytes), u16 _padding. When discriminant is
38 : FD_ALUT_STATE_DISC_UNINITIALIZED the remaining fields are ignored. */
39 :
40 : struct fd_alut_meta {
41 : uint discriminant;
42 : ulong deactivation_slot;
43 : ulong last_extended_slot;
44 : uchar last_extended_slot_start_index;
45 : uchar has_authority;
46 : fd_pubkey_t authority;
47 : };
48 : typedef struct fd_alut_meta fd_alut_meta_t;
49 :
50 : /* fd_alut_interp_t interprets indirect account references of a txn. */
51 :
52 : struct fd_alut_interp {
53 : fd_acct_addr_t * out_accts_alt;
54 : fd_txn_t const * txn;
55 : uchar const * txn_payload;
56 : fd_slot_hashes_t const * hashes;
57 : ulong slot;
58 : ulong alut_idx;
59 : ulong ro_indir_cnt;
60 : ulong rw_indir_cnt;
61 : };
62 :
63 : typedef struct fd_alut_interp fd_alut_interp_t;
64 :
65 : FD_PROTOTYPES_BEGIN
66 :
67 : /* fd_alut_state_encode writes a 56-byte ALUT state header into
68 : [buf, buf+bufsz). Uses meta->discriminant to decide the variant;
69 : fields other than discriminant are ignored when discriminant ==
70 : FD_ALUT_STATE_DISC_UNINITIALIZED. Returns 0 on success, -1 on short
71 : buffer. */
72 :
73 : static inline int
74 : fd_alut_state_encode( fd_alut_meta_t const * meta,
75 : uchar * buf,
76 0 : ulong bufsz ) {
77 0 : uchar * const _payload = buf;
78 0 : ulong const _payload_sz = bufsz;
79 0 : ulong _i = 0UL;
80 :
81 0 : # define CHECK( cond ) { if( FD_UNLIKELY( !(cond) ) ) { return -1; } }
82 0 : # define CHECK_LEFT( n ) CHECK( (n)<=(_payload_sz-_i) )
83 0 : # define INC( n ) (_i += (ulong)(n))
84 0 : # define CURSOR (_payload+_i)
85 :
86 0 : CHECK_LEFT( 4UL ); FD_STORE( uint, CURSOR, meta->discriminant ); INC( 4UL );
87 :
88 0 : if( meta->discriminant==FD_ALUT_STATE_DISC_LOOKUP_TABLE ) {
89 0 : CHECK_LEFT( 8UL ); FD_STORE( ulong, CURSOR, meta->deactivation_slot ); INC( 8UL );
90 0 : CHECK_LEFT( 8UL ); FD_STORE( ulong, CURSOR, meta->last_extended_slot ); INC( 8UL );
91 0 : CHECK_LEFT( 1UL ); FD_STORE( uchar, CURSOR, meta->last_extended_slot_start_index ); INC( 1UL );
92 :
93 0 : CHECK_LEFT( 1UL ); FD_STORE( uchar, CURSOR, (uchar)!!meta->has_authority ); INC( 1UL );
94 :
95 0 : if( meta->has_authority ) {
96 0 : CHECK_LEFT( 32UL ); fd_memcpy( CURSOR, meta->authority.key, 32UL ); INC( 32UL );
97 0 : }
98 :
99 : /* u16 _padding (always 0 on the wire). */
100 0 : CHECK_LEFT( 2UL ); FD_STORE( ushort, CURSOR, (ushort)0 ); INC( 2UL );
101 0 : }
102 :
103 0 : fd_memset( CURSOR, 0, _payload_sz-_i ); /* zero-pad the rest of the buffer */
104 :
105 0 : # undef CHECK
106 0 : # undef CHECK_LEFT
107 0 : # undef INC
108 0 : # undef CURSOR
109 :
110 0 : return 0;
111 0 : }
112 :
113 : /* fd_alut_state_decode reads an ALUT state header from
114 : [data, data+data_sz). On success populates *out (including
115 : out->discriminant) and returns 0. Returns -1 on decode failure
116 : (short buffer or unknown discriminant). */
117 :
118 : static inline int
119 : fd_alut_state_decode( uchar const * data,
120 : ulong data_sz,
121 4857 : fd_alut_meta_t * out ) {
122 4857 : uchar const * _payload = data;
123 4857 : ulong const _payload_sz = data_sz;
124 4857 : ulong _i = 0UL;
125 :
126 41331 : # define CHECK( cond ) { if( FD_UNLIKELY( !(cond) ) ) { return -1; } }
127 31620 : # define CHECK_LEFT( n ) CHECK( (n)<=(_payload_sz-_i) )
128 31620 : # define INC( n ) (_i += (ulong)(n))
129 4857 : # define CURSOR (_payload+_i)
130 :
131 4857 : CHECK_LEFT( 4UL ); uint disc = FD_LOAD( uint, CURSOR ); INC( 4UL );
132 4857 : out->discriminant = disc;
133 :
134 4857 : if( disc==FD_ALUT_STATE_DISC_UNINITIALIZED ) return 0;
135 :
136 4856 : CHECK( disc==FD_ALUT_STATE_DISC_LOOKUP_TABLE );
137 :
138 4855 : CHECK_LEFT( 8UL ); out->deactivation_slot = FD_LOAD( ulong, CURSOR ); INC( 8UL );
139 4855 : CHECK_LEFT( 8UL ); out->last_extended_slot = FD_LOAD( ulong, CURSOR ); INC( 8UL );
140 4855 : CHECK_LEFT( 1UL ); out->last_extended_slot_start_index = FD_LOAD( uchar, CURSOR ); INC( 1UL );
141 :
142 : /* Option<Pubkey> tag: bincode rejects any byte outside {0,1}. */
143 4855 : CHECK_LEFT( 1UL ); uchar has_auth = FD_LOAD( uchar, CURSOR ); INC( 1UL );
144 4855 : CHECK( !(has_auth & (uchar)~1U) );
145 4854 : out->has_authority = has_auth;
146 :
147 4854 : if( has_auth ) {
148 2489 : CHECK_LEFT( 32UL );
149 2489 : fd_memcpy( out->authority.key, CURSOR, 32UL );
150 2489 : INC( 32UL );
151 2489 : }
152 :
153 : /* u16 _padding. Value is ignored but the 2 bytes must be present. */
154 4854 : CHECK_LEFT( 2UL ); INC( 2UL );
155 :
156 4854 : # undef CHECK
157 4854 : # undef CHECK_LEFT
158 4854 : # undef INC
159 4854 : # undef CURSOR
160 :
161 4854 : return 0;
162 4854 : }
163 :
164 : /* fd_alut_slot_hashes_position, fd_alut_status, and fd_alut_is_active
165 : are all helper methods for determining the number of active addresses
166 : in an address lookup table account. */
167 :
168 :
169 : /* Logic here is copied from slice::binary_search_by() in Rust. While
170 : not fully optimized, it aims to achieve fuzzing conformance for both
171 : sorted and unsorted inputs. */
172 : FD_FN_UNUSED static ulong
173 : fd_alut_slot_hashes_position( fd_slot_hashes_t const * hashes,
174 5 : ulong slot ) {
175 5 : ulong size = hashes->cnt;
176 5 : if( FD_UNLIKELY( size==0UL ) ) return ULONG_MAX;
177 :
178 5 : ulong base = 0UL;
179 11 : while( size>1UL ) {
180 6 : ulong half = size / 2UL;
181 6 : ulong mid = base + half;
182 6 : ulong mid_slot = hashes->elems[ mid ].slot;
183 6 : base = (slot>mid_slot) ? base : mid;
184 6 : size -= half;
185 6 : }
186 :
187 5 : return hashes->elems[ base ].slot==slot ? base : ULONG_MAX;
188 5 : }
189 :
190 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L81-L104 */
191 : FD_FN_UNUSED static uchar
192 : fd_alut_status( fd_alut_meta_t const * state,
193 : ulong current_slot,
194 4855 : fd_slot_hashes_t const * slot_hashes ) {
195 4855 : if( state->deactivation_slot==ULONG_MAX ) {
196 4848 : return FD_ADDRLUT_STATUS_ACTIVATED;
197 4848 : }
198 :
199 7 : if( state->deactivation_slot==current_slot ) {
200 2 : return FD_ADDRLUT_STATUS_DEACTIVATING;
201 2 : }
202 :
203 5 : ulong slot_hash_position = fd_alut_slot_hashes_position( slot_hashes, state->deactivation_slot );
204 5 : if( slot_hash_position!=ULONG_MAX ) {
205 1 : return FD_ADDRLUT_STATUS_DEACTIVATING;
206 1 : }
207 :
208 4 : return FD_ADDRLUT_STATUS_DEACTIVATED;
209 5 : }
210 :
211 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L72-L78 */
212 : FD_FN_UNUSED static uchar
213 : fd_alut_is_active( fd_alut_meta_t const * self,
214 : ulong current_slot,
215 4854 : fd_slot_hashes_t const * slot_hashes ) {
216 4854 : uchar status = fd_alut_status( self, current_slot, slot_hashes );
217 4854 : switch( status ) {
218 4848 : case FD_ADDRLUT_STATUS_ACTIVATED:
219 4851 : case FD_ADDRLUT_STATUS_DEACTIVATING:
220 4851 : return 1;
221 4 : case FD_ADDRLUT_STATUS_DEACTIVATED:
222 4 : return 0;
223 0 : default:
224 0 : FD_LOG_CRIT(( "invalid lut status %d", status ));
225 4854 : }
226 4854 : }
227 :
228 : /* fd_alut_active_addresses_len returns the number of active addresses
229 : in an address lookup table account.
230 : https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L142-L164 */
231 : FD_FN_UNUSED static int
232 : fd_alut_active_addresses_len( fd_alut_meta_t const * self,
233 : ulong current_slot,
234 : fd_slot_hashes_t const * slot_hashes,
235 : ulong addresses_len,
236 4854 : ulong * active_addresses_len /* out */ ) {
237 4854 : if( FD_UNLIKELY( !fd_alut_is_active( self, current_slot, slot_hashes ) ) ) {
238 4 : return FD_RUNTIME_TXN_ERR_ADDRESS_LOOKUP_TABLE_NOT_FOUND;
239 4 : }
240 :
241 4850 : *active_addresses_len = ( current_slot > self->last_extended_slot )
242 4850 : ? addresses_len
243 4850 : : self->last_extended_slot_start_index;
244 :
245 4850 : return FD_RUNTIME_EXECUTE_SUCCESS;
246 4854 : }
247 :
248 : /* fd_alut_interp_new creates a new ALUT interpreter.
249 : Will write indirectly referenced addresses to out_addrs.
250 : txn_payload points to a valid serialized transaction, txn points to
251 : the associated transaction descriptor. alut_interp retains a write
252 : interest in out_addrs, and a read interest in txn, txn_payload, and
253 : hashes until it is destroyed. */
254 :
255 : FD_FN_UNUSED static fd_alut_interp_t *
256 : fd_alut_interp_new( fd_alut_interp_t * interp,
257 : fd_acct_addr_t * out_addrs,
258 : fd_txn_t const * txn,
259 : uchar const * txn_payload,
260 : fd_slot_hashes_t const * hashes,
261 7353 : ulong slot ) {
262 7353 : *interp = (fd_alut_interp_t){
263 7353 : .out_accts_alt = out_addrs,
264 7353 : .txn = txn,
265 7353 : .txn_payload = txn_payload,
266 7353 : .hashes = hashes,
267 7353 : .slot = slot,
268 7353 : .alut_idx = 0UL,
269 7353 : .ro_indir_cnt = 0UL,
270 7353 : .rw_indir_cnt = 0UL
271 7353 : };
272 7353 : return interp;
273 7353 : }
274 :
275 : static inline int
276 4894 : fd_alut_interp_done( fd_alut_interp_t const * interp ) {
277 4894 : return interp->alut_idx >= interp->txn->addr_table_lookup_cnt;
278 4894 : }
279 :
280 : /* fd_alut_interp_next resolves a subset of a txn's indirect account
281 : references. Resolves all addresses that are specified in the ALUT
282 : at index alut_idx. Returns one of:
283 : - FD_RUNTIME_EXECUTE_SUCCESS
284 : - FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_OWNER
285 : - FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA
286 : - FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_INDEX
287 : - FD_RUNTIME_TXN_ERR_ADDRESS_LOOKUP_TABLE_NOT_FOUND */
288 :
289 : FD_FN_UNUSED static int
290 : fd_alut_interp_next( fd_alut_interp_t * interp,
291 : void const * alut_addr,
292 : void const * alut_owner,
293 : uchar const * alut_data,
294 4894 : ulong alut_data_sz ) {
295 4894 : if( FD_UNLIKELY( fd_alut_interp_done( interp ) ) ) FD_LOG_CRIT(( "invariant violation" ));
296 4894 : fd_acct_addr_t alut_addr_expected =
297 4894 : FD_LOAD( fd_acct_addr_t, interp->txn_payload+fd_txn_get_address_tables_const( interp->txn )[ interp->alut_idx ].addr_off );
298 4894 : if( FD_UNLIKELY( !fd_memeq( alut_addr, &alut_addr_expected, sizeof(fd_acct_addr_t) ) ) ) {
299 0 : FD_BASE58_ENCODE_32_BYTES( alut_addr, alut_addr_b58 );
300 0 : FD_BASE58_ENCODE_32_BYTES( alut_addr_expected.b, alut_addr_expected_b58 );
301 0 : FD_LOG_CRIT(( "expected address lookup table account %s but got %s",
302 0 : alut_addr_expected_b58, alut_addr_b58 ));
303 0 : }
304 4894 : fd_txn_acct_addr_lut_t const * addr_lut =
305 4894 : &fd_txn_get_address_tables_const( interp->txn )[ interp->alut_idx ];
306 :
307 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/accounts-db/src/accounts.rs#L96-L114 */
308 4894 : if( FD_UNLIKELY( !fd_memeq( alut_owner, fd_solana_address_lookup_table_program_id.key, sizeof(fd_pubkey_t) ) ) ) {
309 0 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_OWNER;
310 0 : }
311 :
312 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L205-L209 */
313 4894 : if( FD_UNLIKELY( alut_data_sz < FD_LOOKUP_TABLE_META_SIZE ) ) {
314 35 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA;
315 35 : }
316 :
317 : /* https://github.com/anza-xyz/agave/blob/574bae8fefc0ed256b55340b9d87b7689bcdf222/accounts-db/src/accounts.rs#L141-L142 */
318 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L197-L214 */
319 4859 : fd_alut_meta_t meta;
320 4859 : if( FD_UNLIKELY( fd_alut_state_decode( alut_data, FD_LOOKUP_TABLE_META_SIZE, &meta ) ) ) {
321 2 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA;
322 2 : }
323 :
324 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L200-L203 */
325 4857 : if( FD_UNLIKELY( meta.discriminant!=FD_ALUT_STATE_DISC_LOOKUP_TABLE ) ) {
326 1 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA;
327 1 : }
328 :
329 : /* Again probably an impossible case, but the ALUT data needs to be 32-byte aligned
330 : https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L210-L214 */
331 4856 : if( FD_UNLIKELY( (alut_data_sz - FD_LOOKUP_TABLE_META_SIZE) & 0x1fUL ) ) {
332 1 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA;
333 1 : }
334 :
335 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/accounts-db/src/accounts.rs#L101-L112 */
336 4855 : fd_acct_addr_t const * lookup_addrs = fd_type_pun_const( alut_data+FD_LOOKUP_TABLE_META_SIZE );
337 4855 : ulong lookup_addrs_cnt = (alut_data_sz - FD_LOOKUP_TABLE_META_SIZE) >> 5UL; // = (dlen - 56) / 32
338 :
339 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L175-L176 */
340 4855 : ulong active_addresses_len;
341 4855 : int err = fd_alut_active_addresses_len(
342 4855 : &meta,
343 4855 : interp->slot,
344 4855 : interp->hashes,
345 4855 : lookup_addrs_cnt,
346 4855 : &active_addresses_len
347 4855 : );
348 4855 : if( FD_UNLIKELY( err ) ) return err;
349 :
350 : /* https://github.com/anza-xyz/solana-sdk/blob/address-lookup-table-interface%40v3.0.1/address-lookup-table-interface/src/state.rs#L208-L211 */
351 4851 : if( FD_UNLIKELY( active_addresses_len>lookup_addrs_cnt ) ) {
352 1 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_DATA;
353 1 : }
354 :
355 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L169-L182 */
356 4850 : uchar const * writable_lut_idxs = interp->txn_payload + addr_lut->writable_off;
357 23740 : for( ulong j=0UL; j<addr_lut->writable_cnt; j++ ) {
358 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L177-L181 */
359 19363 : if( writable_lut_idxs[j] >= active_addresses_len ) {
360 473 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_INDEX;
361 473 : }
362 18890 : interp->out_accts_alt[ interp->rw_indir_cnt++ ] = lookup_addrs[ writable_lut_idxs[ j ] ];
363 18890 : }
364 :
365 4377 : uchar const * readonly_lut_idxs = interp->txn_payload + addr_lut->readonly_off;
366 4377 : fd_acct_addr_t * out_accts_ro = interp->out_accts_alt + interp->txn->addr_table_adtl_writable_cnt;
367 25523 : for( ulong j=0UL; j<addr_lut->readonly_cnt; j++ ) {
368 : /* https://github.com/anza-xyz/agave/blob/368ea563c423b0a85cc317891187e15c9a321521/sdk/program/src/address_lookup_table/state.rs#L177-L181 */
369 21295 : if( readonly_lut_idxs[j] >= active_addresses_len ) {
370 149 : return FD_RUNTIME_TXN_ERR_INVALID_ADDRESS_LOOKUP_TABLE_INDEX;
371 149 : }
372 21146 : out_accts_ro[ interp->ro_indir_cnt++ ] = lookup_addrs[ readonly_lut_idxs[ j ] ];
373 21146 : }
374 :
375 4228 : interp->alut_idx++;
376 4228 : return FD_RUNTIME_EXECUTE_SUCCESS;
377 4377 : }
378 :
379 : FD_PROTOTYPES_END
380 :
381 :
382 : #endif /* HEADER_fd_src_flamenco_runtime_fd_alut_h */
|
