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