Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for concurrent
2 : persistent shared maps based on chaining. A map can store a
3 : practically unbounded number of elements. If sized on creation for
4 : the maximum number of mapped elements, typical map operations are a
5 : fast O(1) time and map element overhead is a small O(1) space.
6 : Further, large numbers of composite map operations can be done
7 : concurrently with very low risk of conflicts.
8 :
9 : In the current implementation, each map chain has a version number.
10 : Operations that require changing a chain's connectivity (e.g.
11 : inserting or removing an element from a chain) or modifying an
12 : element managed by that chain, the chain's version number is
13 : increased by one (atomic fetch-and-or based) such that other
14 : potential users of keys managed by that chain detect and react
15 : appropriately to a potentially concurrent conflicting operation in
16 : progress. When an operation completes, the chain version number is
17 : increased by one again to notify other users the operation is no
18 : longer in progress and that the set of keys managed by that chain
19 : and/or values associated with those keys has potentially changed
20 : since the previous version. For example, lockfree queries can
21 : interoperate with this via a zero-copy
22 : try-speculatively-process-then-test pattern similar to that used in
23 : fd_tango for high throughput message processing.
24 :
25 : As such, there can be an arbitrary number of concurrent readers
26 : processing map keys. These readers will not interfere with each
27 : other and will not block any concurrent insert / remove / modify
28 : operations. Insert / remove / modify operations can potentially
29 : block each other. Since there are typically O(1) keys per chain, the
30 : probability of concurrent insert / remove / modify operations
31 : involving different keys blocking each other is small. Further, this
32 : controllable a priori by provisioning the number of chains
33 : appropriately. Concurrent operations on the same key are serialized
34 : (as they necessarily would be any implementation). Since the
35 : operations are HPC implementations, collisions are resolved as fast
36 : as is practical. The upshot is that the map supports massive
37 : concurrency while preserving concurrent operation serializability.
38 :
39 : Version numbers are stored with chain head pointers such that the
40 : cache traffic required for managing chain versioning is covered by
41 : the same cache traffic required for managing chains in a
42 : non-concurrent implementation (e.g. fd_map_chain). Operations do
43 : many internal integrity checking / bounds checking for use in high
44 : reliability applications.
45 :
46 : Lastly, fine grained versioning allows for concurrent execution of
47 : complex operations involving multiple keys simultaneously. This
48 : allows using the map as a concurrent transactional memory and for
49 : serialization of all map elements at a consistent point in time while
50 : minimizing impact on ongoing concurrent operations (e.g. snapshotting
51 : all the elements in the map).
52 :
53 : The main drawback of chain versioning is the extra memory footprint
54 : required for chain metadata storage. The current implementation
55 : supports indexing compression and uses atomic bit field techniques to
56 : minimize this overhead.
57 :
58 : Concurrent operation requires FD_HAS_ATOMIC. This will still work on
59 : platforms without FD_HAS_ATOMIC but concurrent operations will not be
60 : safe.
61 :
62 : In short, if you need a concurrent map, this is a lot better than
63 : protecting a non-concurrent implementation with a global lock. And,
64 : if you don't, it will be comparably performant to a non-concurrent
65 : implementation.
66 :
67 : This generator is designed for ultra tight coupling with pools,
68 : treaps, heaps, lists, other maps, etc. Likewise, a map can be
69 : persisted beyond the lifetime of the creating process, be used
70 : inter-process, relocated in memory, be naively
71 : serialized/deserialized, be moved between hosts, use index
72 : compression for cache and memory bandwidth efficiency, etc.
73 : Concurrency and flexibility are prioritized.
74 :
75 : Typical usage:
76 :
77 : struct myele {
78 : ulong key; // Technically "MAP_KEY_T MAP_KEY" (default is ulong key), managed by mymap when the element is in the mymap
79 : ulong next; // Technically "MAP_IDX_T MAP_NEXT" (default is ulong next), managed by mymap when the element is in the mymap
80 :
81 : ... key and next can be located arbitrarily in the element and
82 : ... can be reused for other purposes when the element is not in a
83 : ... mymap. The mapping of a key to an element in the element
84 : ... store is arbitrary. An element should not be moved /
85 : ... released from the element store while in the mymap.
86 :
87 : };
88 :
89 : typedef struct myele myele_t;
90 :
91 : #define MAP_NAME mymap
92 : #define MAP_ELE_T myele_t
93 : #include "tmpl/fd_map_chain_para.c"
94 :
95 : will declare the following APIs as a header only style library in the
96 : compilation unit:
97 :
98 : // A mymap_t is a stack declaration friendly quasi-opaque local
99 : // object used to hold the state of a local join to a mymap.
100 : // Similarly, a mymap_query_t and a mymap_iter_t hold the local
101 : // state of an ongoing local query and local iteration
102 : // respectively. E.g. it is fine to do mymap_t join[1];" to
103 : // allocate a mymap_t but the contents should not be used directly.
104 :
105 : typedef struct mymap_private mymap_t;
106 : typedef struct mymap_query_private mymap_query_t;
107 : typedef struct mymap_iter_private mymap_iter_t;
108 :
109 : // mymap_ele_max_max returns the maximum element store capacity
110 : // compatible with a mymap.
111 :
112 : ulong mymap_ele_max_max( void );
113 :
114 : // mymap_chain_max returns the maximum number of chains supported
115 : // by a mymap. Will be an integer power-of-two.
116 :
117 : ulong mymap_chain_max( void );
118 :
119 : // mymap_chain_cnt_est returns a reasonable number of chains to use
120 : // for a map that is expected to hold up to ele_max_est elements.
121 : // ele_max_est will be clamped to be in [1,mymap_ele_max_max()] and
122 : // the return value will be an integer power-of-two in
123 : // [1,mymap_chain_max()].
124 :
125 : ulong mymap_chain_cnt_est( ulong ele_max_est );
126 :
127 : // mymap_{align,footprint} returns the alignment and footprint
128 : // needed for a memory region to be used as a mymap. align will be
129 : // an integer power-of-two and footprint will be a multiple of
130 : // align. footprint returns 0 if chain_cnt is not an integer
131 : // power-of-two in [1,mymap_chain_max()].
132 : //
133 : // mymap_new formats a memory region with the required alignment
134 : // and footprint into a mymap. shmem points in the caller's
135 : // address space to the memory region to use. Returns shmem on
136 : // success (mymap has ownership of the memory region) and NULL on
137 : // failure (no changes, logs details). The caller is not joined on
138 : // return. The mymap will be empty with all map chains at version
139 : // 0 (unlocked).
140 : //
141 : // mymap_join joins the caller to an existing mymap. ljoin points
142 : // to a mymap_t compatible memory region in the caller's address
143 : // space, shmap points in the caller's address space to the memory
144 : // region containing the mymap, shele points in the caller's
145 : // address space to mymap's element store and ele_max gives the
146 : // element store's capacity in [0,ele_max_max]. Returns a handle
147 : // to the caller's local join on success (join has ownership of the
148 : // ljoin region) and NULL on failure (no changes, logs details).
149 : //
150 : // mymap_leave leaves a mymap join. join points to a current local
151 : // join. Returns the memory region used for the join on success
152 : // (caller has ownership on return and the caller is no longer
153 : // joined) and NULL on failure (no changes, logs details). Use the
154 : // join accessors before leaving to get shmap, shele and ele_max
155 : // used by the join if needed.
156 : //
157 : // mymap_delete unformats a memory region used as a mymap. Assumes
158 : // shmap points in the caller's address space to a memory region
159 : // containing the mymap and that there are no joins. Returns shmem
160 : // on success (caller has ownership of the memory region, any
161 : // remaining elements still in the mymap are released to the caller
162 : // implicitly) and NULL on failure (no changes, logs details).
163 :
164 : ulong mymap_align ( void );
165 : ulong mymap_footprint( ulong chain_cnt );
166 : void * mymap_new ( void * shmem, ulong chain_cnt, ulong seed );
167 : mymap_t * mymap_join ( void * ljoin, void * shmap, void * shele, ulong ele_max );
168 : void * mymap_leave ( mymap_t * join );
169 : void * mymap_delete ( void * shmap );
170 :
171 : // mymap_{chain_cnt,seed} return the mymap configuration. Assumes
172 : // join is a current local join. The values will be valid for the
173 : // mymap lifetime.
174 :
175 : ulong mymap_chain_cnt( mymap_t const * join );
176 : ulong mymap_seed ( mymap_t const * join );
177 :
178 : // mymap_{shmap,shele,ele_max} return join details. Assumes join
179 : // is a current local join. The values will be valid for the join
180 : // lifetime. mymap_{shmap_const,shele_const} are const correct
181 : // versions.
182 :
183 : void const * mymap_shmap_const( mymap_t const * join );
184 : void const * mymap_shele_const( mymap_t const * join );
185 : ulong mymap_ele_max ( mymap_t const * join );
186 :
187 : void * mymap_shmap( mymap_t * join );
188 : void * mymap_shele( mymap_t * join );
189 :
190 : // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
191 : // as inlines with strict semantics. They assume that the provided
192 : // pointers are in the caller's address space to keys that will not
193 : // be changed during the call. They retain no interest in any keys
194 : // on return.
195 : //
196 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
197 : //
198 : // mymap_key_hash returns the hash of *key using the hash function
199 : // seed. Should ideally be a random mapping from a MAP_KEY_T to a
200 : // ulong but this depends on what the user actually used for
201 : // MAP_KEY_HASH. The seed used by a particular mymap instance can
202 : // be obtained above.
203 :
204 : int mymap_key_eq ( ulong * k0, ulong * k1 );
205 : ulong mymap_key_hash( ulong * key, ulong seed );
206 :
207 : // mymap_backoff does FD_SPIN_PAUSE a random number of times. The
208 : // number of pauses is an approximately uniform IID random number
209 : // in [0,scale/2^16] where scale is in [0,2^32). Specifically, the
210 : // number of pauses is:
211 : //
212 : // floor( scale r / 2^48 )
213 : //
214 : // where r is a non-deterministic 32-bit uniform IID random number.
215 : // Under the hood, r is generated by hashing the user provided seed
216 : // and the least significant 32-bits of the CPU tickcounter.
217 : // Ideally, seed is a 32-bit globally unique identifier for the
218 : // logical thread of execution but this is up to the application to
219 : // specify and rarely matters in practice. This is a useful
220 : // building block for random exponential backoffs.
221 :
222 : void mymap_backoff( ulong scale, ulong seed );
223 :
224 : // mymap_query_memo returns the key_hash of the query associated
225 : // with the query's key to allow users to minimize potentially
226 : // expensive key hash computations in various operations.
227 : //
228 : // mymap_query_ele returns a pointer in the caller's address space
229 : // to the element store element associated with the query or a
230 : // sentinel value. The sentinel value is application dependent and
231 : // thus arbitrary (e.g. not necessarily in the element store,
232 : // including NULL, a local temporary used as a bit bucket, etc).
233 : // Assumes query is valid. The lifetime of the returned pointer
234 : // depends on the query. mymap_query_ele_const is a const correct
235 : // version.
236 :
237 : ulong mymap_query_memo ( mymap_query_t const * query );
238 : myele_t const * mymap_query_ele_const( mymap_query_t const * query );
239 : myele_t * mymap_query_ele ( mymap_query_t * query );
240 :
241 : // mymap_hint hints that the caller plans to do an operation
242 : // involving key soon. Assumes join is a current local join, key
243 : // points to a valid key in the caller's address space for the
244 : // duration of the call and query points to a local scratch to hold
245 : // info about the hint. Retains no interest in key. On return,
246 : // the query memo will be initialized.
247 : //
248 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_USE_HINT
249 : // is set, this will assume that query's memo is already
250 : // initialized for key (e.g. mostly useful for hashless
251 : // prefetching). If FD_MAP_FLAG_PREFETCH_META /
252 : // FD_MAP_FLAG_PREFETCH_DATA is set, this will issue a prefetch for
253 : // key's mymap metadata (i.e. lock version) / the element at the
254 : // start of key's chain if any (i.e. typically the key of interest
255 : // in a well managed map). FD_MAP_FLAG_PREFETCH combines both for
256 : // convenience. This can be used to overlap key access latency
257 : // with unrelated operations. All other flags are ignored.
258 :
259 : void
260 : mymap_hint( MAP_(t) const * join
261 : MAP_KEY_T const * key
262 : MAP_(query_t) * query,
263 : int flags );
264 :
265 : // mymap_insert inserts into a mymap a mapping from a key to an
266 : // element store element. ele points in the caller's address space
267 : // to the element and ele->key is initialized to the key. flags is
268 : // a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING is set /
269 : // clear in flags, this is allowed / not allowed to block the
270 : // caller. Assumes join is a current local join, element is not in
271 : // the mymap and the key is not currently mapped to anything in the
272 : // mymap. This is a non-blocking fast O(1) and supports highly
273 : // concurrent operation.
274 : //
275 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
276 : // (negative) on failure. On success, ele was inserted into the
277 : // mymap at some point during the call (mymap took ownership of the
278 : // element at that time but the application is free to manage all
279 : // fields of the element except ele->key, ele->next and, if the
280 : // mymap is memoized, ele->hash ... insert will initialize the hash
281 : // field to mymap_key_hash( key, seed ) and this will be stable
282 : // while ele is in mymap). On failure, the mymap was not modified
283 : // by the call, no changes of ownership occurred in the call and
284 : // returns:
285 : //
286 : // - FD_MAP_ERR_INVAL: ele is not a pointer to an element store
287 : // element.
288 : //
289 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
290 : // progress at some point during the call. Try again later (e.g.
291 : // after a random exponential backoff). Specifically, this
292 : // operation requires locking the map chain associated with key.
293 : // Since there are typically O(1) keys per chain, the probability
294 : // of getting AGAIN due to a false conflict is negligible even
295 : // under highly concurrent loads. Since insert / remove are fast
296 : // O(1) operations, any remaining conflicts, real or imagined,
297 : // are typically very short lived. Never returned for a blocking
298 : // call.
299 : //
300 : // IMPORTANT SAFETY TIP! Do not use inside a modify try/test,
301 : // query try/test, txn try/test or iter lock/unlock.
302 :
303 : int mymap_insert( mymap_t * join, myele_t * ele, int flags );
304 :
305 : // mymap_remove removes the mapping (if any) for key from the
306 : // mymap. On return, query will contain information about the
307 : // removed mapping and memo will be initialized for key. sentinel
308 : // gives the query element pointer value (arbitrary) to pass
309 : // through when this did not remove a mapping for any reason.
310 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING
311 : // is set / clear in flags, this is allowed / not allowed to block
312 : // the caller. If FD_MAP_FLAG_USE_HINT is set, this assumes
313 : // query's memo is already initialized for key. Assumes join is a
314 : // current local join and key is valid for the duration of the
315 : // call. Retains no interest in key, sentinel or query. This is a
316 : // non-blocking fast O(1) and supports highly concurrent operation.
317 : //
318 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
319 : // (negative) on failure. On success, key's mapping was removed at
320 : // some point during the call. mymap_query_ele( query ) will point
321 : // in the caller's address space to the element store element where
322 : // key mapped just before it was removed (element ownership
323 : // transferred to the caller at that time). On failure, no changes
324 : // were made by this call, mymap_query_ele( query ) will be
325 : // sentinel and:
326 : //
327 : // - FD_MAP_ERR_KEY: Key was not found in the mymap at some point
328 : // during the call.
329 : //
330 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
331 : // progress at some point during the call. Same considerations
332 : // as insert above. Never returned for a blocking call.
333 : //
334 : // - FD_MAP_ERR_CORRUPT: Memory corruption was detected at some
335 : // point during the call.
336 : //
337 : // IMPORTANT SAFETY TIP! Do not use inside a modify try/test,
338 : // query try/test, txn try/test or iter lock/unlock.
339 :
340 : int
341 : mymap_remove( mymap_t * join,
342 : ulong const * key,
343 : myele_t const * sentinel,
344 : mymap_query_t * query,
345 : int flags );
346 :
347 : // mymap_modify_try tries to start modification of the mymap
348 : // element corresponding to key. On return, query will hold
349 : // information about the try and memo will be initialized for key.
350 : // sentinel gives the query element pointer value (arbitrary) to
351 : // pass through when it is not safe to try. flags is a bit-or of
352 : // FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING is set / clear, this
353 : // call is allowed / not allowed to block the caller. If
354 : // FD_MAP_FLAG_USE_HINT is set, this assumes query's memo is
355 : // already initialized for key. If FD_MAP_FLAG_ADAPTIVE is set /
356 : // clear, this call should / should not adapt the mymap to
357 : // accelerate future operations on this key. Adaptation for a key
358 : // can potentially slow future operations for other keys. The
359 : // marginal benefit of adaptation for a key grows linearly with the
360 : // number of keys managed by the key's chain. Assumes join is a
361 : // current local join and key is valid for the duration of the
362 : // call. Retains no interest in key, sentinel or query. This is a
363 : // non-blocking fast O(1) and supports highly concurrent operation.
364 : //
365 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
366 : // (negative) on failure. On success, mymap_query_ele( query )
367 : // will point in the caller's address space to the element to
368 : // modify and the chain that manages key will be locked. The mymap
369 : // retains ownership of this element and management of the key and
370 : // next fields. The caller is free to modify any other fields. On
371 : // failure, the mymap was not modified by this call,
372 : // mymap_query_ele( query ) will be sentinel and returns:
373 : //
374 : // - FD_MAP_ERR_KEY: Key was not found in the mymap in some point
375 : // during the call.
376 : //
377 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
378 : // progress at some point during the try. Same considerations as
379 : // insert above. Never returned for a blocking call.
380 : //
381 : // - FD_MAP_ERR_CORRUPT: Memory corruption was detected at some
382 : // point during the call.
383 : //
384 : // IMPORTANT SAFETY TIP! Do not interleave or nest with a query
385 : // try/test, txn try/test or iter_lock/unlock on the same thread.
386 :
387 : int
388 : mymap_modify_try( mymap_t * join,
389 : ulong const * key,
390 : myele_t * sentinel,
391 : mymap_query_t * query,
392 : int flags );
393 :
394 : // mymap_modify_test finishes an in-progress modification. Assumes
395 : // query is valid and the caller is in a modify try. Returns
396 : // FD_MAP_SUCCESS (0). On return, the caller will no longer be in
397 : // a modify try. Guaranteed to succeed.
398 : //
399 : // IMPORTANT SAFETY TIP! Do not interleave or nest with a query
400 : // try/test, txn try/test or iter_lock/unlock on the same thread.
401 :
402 : int mymap_modify_test( mymap_query_t * query );
403 :
404 : // mymap_query_try tries to speculatively query a mymap for key.
405 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_USE_HINT
406 : // is set, this assumes query's memo is already initialized for
407 : // key. On return, query will hold information about the try and
408 : // memo will be initialized for key. sentinel gives the query
409 : // element pointer value (arbitrary) to pass through when it is not
410 : // safe to try the query. Assumes join is a current local join and
411 : // key is valid for the duration of the call. Does not modify the
412 : // mymap and retains no interest in key, sentinel or query. This
413 : // is a non-blocking fast O(1) and supports highly concurrent
414 : // operation.
415 : //
416 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
417 : // (negative) on failure. On success, key mapped to an element in
418 : // the element store at some point during the call.
419 : // mymap_query_ele( query ) will point in the caller's address
420 : // space to the element store element where key mapped at that
421 : // time. The mymap retains ownership of this element but the
422 : // caller can zero copy speculatively process the element. On
423 : // failure, mymap_query_ele( query ) will be sentinel and returns:
424 : //
425 : // - FD_MAP_ERR_KEY: Key was not found in the mymap in some point
426 : // during the call.
427 : //
428 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
429 : // progress at some point during the call. Try again later (e.g.
430 : // after a random exponential backoff). Unlike insert and
431 : // remove, this call does _not_ require a lock on the chain
432 : // associated with key. As such, AGAIN can only be caused by
433 : // concurrent operations that require a lock on the chain that
434 : // manages key (with similar considerations as insert and remove)
435 : // and this will never interfere with any other concurrent
436 : // operation. Among the many implications, a query will never
437 : // delay a concurrent query and AGAIN will never be returned if
438 : // only concurrent queries are in progress.
439 : //
440 : // - FD_MAP_ERR_CORRUPT: Memory corruption was detected at some
441 : // point during the call.
442 : //
443 : // IMPORTANT SAFETY TIP! THE CALLER SHOULD BE PREPARED TO HANDLE
444 : // ARBITRARY AND/OR INCONSISTENT VALUES FOR ELEMENT FIELDS DURING
445 : // SPECULATIVE PROCESSING. CALLERS SHOULD NOT COMMIT ANY RESULTS
446 : // OF SPECULATIVE PROCESSING UNTIL IT TESTS THE QUERY WAS
447 : // SUCCESSFUL.
448 : //
449 : // The simplest form of speculative processing is to copy the
450 : // element from the element store into a local temporary, test that
451 : // the speculation was valid, and then process the local temporary
452 : // copy at its leisure. Zero copy, more selective copying and/or
453 : // writing speculative results into local tempoaries are more
454 : // advanced examples of speculative processing.
455 : //
456 : // Use mymap_modify to do a blocking (non-speculative) and/or
457 : // adaptive query (just don't actually modify the element).
458 : //
459 : // IMPORTANT SAFETY TIP! Do not interleave or nest with a modify
460 : // try/test, txn try/test or iter_lock/unlock on the same thread.
461 :
462 : int
463 : mymap_query_try( mymap_t const * join,
464 : ulong const * key,
465 : myele_t const * sentinel,
466 : mymap_query_t * query,
467 : int flags );
468 :
469 : // mymap_query_test tests if an in-progress query is still valid.
470 : // Assumes query is valid, we are still in a query try and chain
471 : // version numbers have not wrapped since we started the try.
472 : // Returns FD_MAP_SUCCESS (0) if the query is still valid and
473 : // FD_MAP_ERR_AGAIN (negative) if a potentially conflicting
474 : // operation was in progress at some point during the try.
475 : //
476 : // IMPORTANT SAFETY TIP! Do not interleave or nest with a modify
477 : // try/test, txn try/test or iter_lock/unlock on the same thread.
478 :
479 : int mymap_query_test( mymap_query_t const * query );
480 :
481 : // mymap_txn_key_max_max() returns the theoretical maximum number
482 : // of keys that can be in a transaction. (Practically unbounded.)
483 :
484 : ulong mymap_txn_key_max_max( void );
485 :
486 : // mymap_txn_{align,footprint} return the alignment and footprint
487 : // required for a mymap_txn_t that can support at least key_max
488 : // keys. align will be an integer power of two. footprint will be
489 : // a multiple of align. Returns 0 if key_max > key_max_max.
490 : //
491 : // mymap_txn_init formats a memory region with the required
492 : // alignment and footprint as a txn_t that can support at least
493 : // key_max keys. ltxn points in the caller's address space to the
494 : // memory region to use. Assumes join is a current local join.
495 : // On success, returns ltxn (txn will have ownership of the memory
496 : // region, txn will be valid with empty speculative and locked key
497 : // sets). The lifetime of the join should be at least the lifetime
498 : // of the txn. On failure (obviously bad inputs), returns NULL (no
499 : // changes).
500 : //
501 : // mymap_txn_fini unformats a memory region as a txn_t and returns
502 : // a pointer to the underlying memory. On success, returns ltxn.
503 : // The caller has ownership of the memory region on return. On
504 : // failure (e.g. NULL input), returns NULL (no changes).
505 :
506 : ulong mymap_txn_align ( void );
507 : ulong mymap_txn_footprint( ulong key_max );
508 : mymap_txn_t * mymap_txn_init ( void * ltxn, mymap_t * join, ulong key_max );
509 : void * mymap_txn_fini ( mymap_txn_t * txn );
510 :
511 : // mymap_txn_add indicates that key may be used in a txn. Assumes
512 : // txn is valid and not in a try and key is valid for duration of
513 : // the call. Retains no interest in key. A zero value for lock
514 : // indicates the key will be operated on speculatively. A non-zero
515 : // value indicates the key will potentially be inserted / removed /
516 : // modified by the transaction. It is okay to have a mixture of
517 : // speculative and locked keys in a transaction. Further, it is
518 : // okay to add the same key multiple times (though not particularly
519 : // efficient), including as a mixture of speculative and locked (if
520 : // _any_ adds of same key are locked, it will be treated as a
521 : // locked key for the txn overall). Returns FD_MAP_SUCCESS (zero)
522 : // on success (txn is valid and not in a try) and FD_MAP_ERR_INVAL
523 : // (negative) on failure (txn is valid and not in a try but key was
524 : // not added). INVAL is only possible when more than key_max adds
525 : // have been done since init.
526 :
527 : int mymap_txn_add( mymap_txn_t * txn, mymap_key_t const * key, int lock );
528 :
529 : // mymap_txn_try returns FD_MAP_SUCCESS (zero) if it is safe to try
530 : // the transaction and FD_MAP_ERR_AGAIN (negative) if the user
531 : // should try again later (e.g. after a random exponential
532 : // backoff). flags is a bit-of of FD_MAP_FLAG flags. If
533 : // FD_MAP_FLAG_BLOCKING is set / clear, this call is allowed / not
534 : // allowed to block the caller. The upper 30-bits of flags can be
535 : // used to provide a seed for random backoffs (but this is up to
536 : // the application and rarely matters in practice). Assumes txn is
537 : // valid and not in a try. On success, txn will be valid and in a
538 : // try. On a failure, txn will be valid and not in a try.
539 : //
540 : // IMPORTANT SAFETY TIP! Do not interleave or nest with modify
541 : // try/test, query try/test or iter_lock/unlock on the same thread.
542 : //
543 : // To better under the restrictions on nesting and interleaving,
544 : // mymap_{insert,remove,query_try,modify_try,query_try} will fail
545 : // with FD_MAP_ERR_AGAIN for any key managed by a chain locked by
546 : // the txn but can succeed for keys on managed by other chains.
547 : // This behavior is unpredictable as it depends on the keys in the
548 : // txn, keys not in the transaction, map seed, map chain count and
549 : // user provided key hash function. Interleaving a query_test,
550 : // modify_test, iter_unlock can be similarly unpredictable. Worse,
551 : // an interleaved modify_test or iter_unlock can muck up the chain
552 : // locks and used by the txn try. Similarly for other cases.
553 : //
554 : // IMPORTANT SAFETY TIP! If some txn keys were speculative, the
555 : // caller should not rely on any reads from the corresponding
556 : // element until the transaction tests successfully. Similar
557 : // considerations as mymap_query_try.
558 :
559 : int mymap_txn_try( mymap_txn_t * txn, int flags );
560 :
561 : // mymap_txn_hint behaves _identially_ to mymap_hint but is allowed
562 : // to assume we are in a txn try and key was added to the txn as
563 : // either speculative or locked.
564 : //
565 : // mymap_txn_{insert,remove} behave _identically_ to
566 : // mymap_{insert,remove} from the caller's point of view but
567 : // assumes we are in a txn try and key was added to the txn as
568 : // locked. These will never return FD_MAP_ERR_AGAIN.
569 : //
570 : // Similarly, mymap_txn_query behaves _identically_ to
571 : // mymap_query_try from the caller's point of view but assumes we
572 : // are in a txn try and key was added to txn as either speculative
573 : // or locked. Will never return FD_MAP_ERR_AGAIN.
574 : //
575 : // Likewise, mymap_txn_modify behaves _identically_ to
576 : // mymap_modify_try from the caller's point of view but assumes we
577 : // are in a txn try and key was added to txn as locked. It will
578 : // never return FD_MAP_ERR_AGAIN.
579 : //
580 : // There is no mymap_query_test or mymap_modify_test because these
581 : // are part of the overall txn test.
582 : //
583 : // IMPORTANT SAFETY TIP!
584 : //
585 : // These never should be used outside a txn try.
586 : //
587 : // IMPORTANT SAFETY TIP!
588 : //
589 : // For a speculative txn key, mymap_query can return FD_MAP_ERR_KEY
590 : // and/or FD_MAP_ERR_CORRUPT if there are locked concurrent
591 : // operations on the chain managing key (e.g a concurrent remove of
592 : // a key that happens to be on the same chain). When such
593 : // operations are possible, these errors can be canaries that the
594 : // transaction has already failed (testing the txn is still
595 : // necessary to it "official"). CORRUPT in this situation is most
596 : // likely an "unofficial" failure than memory corruption.
597 : // Similarly, while mymap_txn_query is guaranteed give a pointer to
598 : // an element store element on success, there is no guarantee it
599 : // will be to the correct element, a well formed element (or even
600 : // to the same location if used multiple times in the try). When
601 : // such concurrent operations are not possible (e.g. single
602 : // threaded operation), SUCCESS, KEY, CORRUPT and the element
603 : // pointer returned have their usual interpretations.
604 : //
605 : // TL;DR speculative txn keys are best used for common stable
606 : // constant-ish read-only data to minimize concurrent complex
607 : // transactions using these common keys from unnecessarily blocking
608 : // each other.
609 : //
610 : // TL;DR resolve all speculative txn keys to elements at
611 : // transaction start exactly once for sanity.
612 : //
613 : // TL;DR avoid using speculative txn keys at all unless very well
614 : // versed in lockfree programming idioms and gotchas.
615 :
616 : int mymap_txn_hint ( mymap_t const * join, ulong const * key, mymap_query_t * query, int flags );
617 : int mymap_txn_insert( mymap_t * join, myele_t * ele );
618 : int mymap_txn_remove( mymap_t * join, ulong const * key, myele_t const * sentinel, mymap_query_t * query, int flags );
619 : int mymap_txn_modify( mymap_t * join, ulong const * key, myele_t * sentinel, mymap_query_t * query, int flags );
620 : int mymap_txn_query ( mymap_t const * join, ulong const * key, myele_t const * sentinel, mymap_query_t * query, int flags );
621 :
622 : // mymap_txn_test returns FD_MAP_SUCCESS (zero) if the txn try
623 : // succeeded and FD_MAP_ERR_AGAIN (negative) if it failed (e.g. the
624 : // test detected a potentially conflicting concurrent operation
625 : // during the try). On success, any results from processing of
626 : // keys marked as speculative can be trusted. On failure, the
627 : // mymap was not changed by the try. Regardless of return value,
628 : // txn will _not_ be in a try on return _but_ will still be valid.
629 : // As such, if a transaction fails, it can be retried (e.g. after a
630 : // random exponential backoff) without needing to recreate it (e.g.
631 : // no need to fini then init/add again). Assumes txn is in a try
632 : // and, for any txn speculative keys, no wrapping of txn version
633 : // numbers has occurred since the try started.
634 : //
635 : // IMPORTANT SAFETY TIP! This is guaranteed to succeed if no keys
636 : // were added to the transaction as speculative.
637 : //
638 : // IMPORTANT SAFETY TIP! Do not interleave or nest with modify
639 : // try/test, query try/test or iter_lock/unlock on the same thread.
640 :
641 : int mymap_txn_test( mymap_txn_t * txn );
642 :
643 : // mymap_iter_lock locks zero or more map chains. Assumes join is
644 : // a current local join. On input, lock_seq[i] for i in
645 : // [0,lock_cnt) gives the set of chains to lock. flags is a bit-or
646 : // of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING is set / not set,
647 : // this call is allowed / not allowed to block the caller. Assumes
648 : // join, lock_seq and lock_cnt are valid and the caller does not
649 : // already have any of these locks. The upper 30-bits of flags
650 : // can be used to provide a seed for random backoffs (but this is
651 : // up to the application and rarely necessary). In particular,
652 : // lock_seq should contain unique values in [0,chain_cnt), which
653 : // also implies lock_cnt is at most chain_cnt. Retains no interest
654 : // in lock_seq. Returns FD_MAP_SUCCESS (zero) on success and
655 : // FD_MAP_ERR_AGAIN (negative) on failure. On return:
656 : //
657 : // FD_MAP_SUCCESS: lock_seq will be a permutation of the input
658 : // giving the actual order (from oldest to newest) in which the
659 : // locks were acquired. This can be used, for example, to unlock
660 : // in the same order and can be used by the caller to optimize
661 : // the order for iterating over keys to reduce the amount of
662 : // contention with other concurrent operations. If there were no
663 : // potentially conflicting concurrent operations during the call,
664 : // lock_seq will be in the input order.
665 : //
666 : // FD_MAP_ERR_AGAIN: a potentially conflicting operation was in
667 : // progress at some point during the call. lock_seq might have
668 : // been changed (but will still be a permutation of the input).
669 : // The mymap itself wasn't changed by the call.
670 : //
671 : // FD_MAP_ERR_INVAL: join, lock_seq and/or lock_cnt were
672 : // obviously invalid. Same considerations as FD_MAP_ERR_AGAIN.
673 : //
674 : // Guaranteed to succeed if blocking (but will not return to the
675 : // caller until all the requested chains are locked).
676 : //
677 : // IMPORTANT SAFETY TIP! Do not use interleave or nest with modify
678 : // try/test, query try/test or txn try/test on the same thread.
679 :
680 : int
681 : mymap_iter_lock( mymap_t * join,
682 : ulong * lock_seq,
683 : ulong lock_cnt,
684 : int flags );
685 :
686 : // mymap_iter_unlock unlocks chains lock_seq[i] for i in
687 : // [0,lock_cnt) in that order. Assumes join is a current local
688 : // join, lock_seq and lock_cnt are valid (same requirements as
689 : // mymap_iter_lock) and the caller has a lock on those chains.
690 : // Retains no interest in lock_seq. Guaranteed to succeed.
691 : //
692 : // IMPORTANT SAFETY TIP! Do not use interleave or nest with modify
693 : // try/test, query try/test or txn try/test on the same thread.
694 :
695 : void
696 : mymap_iter_unlock( mymap_t * join,
697 : ulong const * lock_seq,
698 : ulong lock_cnt );
699 :
700 : // mymap_iter_chain_idx returns the index of the map chain that
701 : // manages key. Useful for iterating over groups of related keys
702 : // when the map hash function is designed to group all related keys
703 : // onto the same chain.
704 :
705 : ulong
706 : mymap_iter_chain_idx( mymap_t const * join,
707 : ulong const * key );
708 :
709 : // mymap_{iter,iter_done,iter_next,iter_ele,iter_ele_const} iterate
710 : // over a single map chain. Assumes join is a current local join,
711 : // chain_idx is in [0,mymap_chain_cnt(join)) and the caller lock on
712 : // chain idx or the chain is otherwise known to be idle.
713 : //
714 : // These are building blocks for concurrent parallel iteration. As
715 : // the locking and ordering requirements for such an iterator are
716 : // very application specific, no default global iterators are
717 : // provided (i.e. a generic global iterator will need to be so
718 : // conservative on locking than typical application requirements,
719 : // it is practically more mischievious than useful). E.g. a mymap
720 : // snapshot might lock all chains to get the state of the entire
721 : // mymap at a consistent point in time. For each chain (in the
722 : // order given by the lock acquisition), the snapshot would
723 : // serialize all keys on that chain and then unlock it
724 : // incrementally.
725 :
726 : mymap_iter_t mymap_iter ( mymap_t const * join, ulong chain_idx );
727 : mymap_iter_t mymap_iter_done ( mymap_iter_t iter );
728 : mymap_iter_t mymap_iter_next ( mymap_iter_t iter );
729 : myele_t const * mymap_iter_ele_const( mymap_iter_t iter );
730 : myele_t * mymap_iter_ele ( mymap_iter_t iter );
731 :
732 : // mymap_reset removes all elements from the mymap. Caller has
733 : // ownership of all items removed on return. Assumes that join is
734 : // a current local join and the caller has a lock on all map chains
735 : // or the map is otherwise known to be idle.
736 :
737 : void mymap_reset( mymap_t * join );
738 :
739 : // mymap_verify returns FD_MAP_SUCCESS (0) if the join, underlying
740 : // map and underlying element store give a valid mapping of unique
741 : // keys to unique elements in the element store. Assumes that
742 : // caller has a lock on all map chains or the map is otherwise
743 : // known to be idle. Returns FD_MAP_ERR_INVAL (negative) otherwise
744 : // (no changes by this call, logs details).
745 :
746 : int mymap_verify( mymap_t const * join );
747 :
748 : // mymap_strerror converts an FD_MAP_SUCCESS / FD_MAP_ERR code into
749 : // a human readable cstr. The lifetime of the returned pointer is
750 : // infinite. The returned pointer is always to a non-NULL cstr.
751 :
752 : char const * mymap_strerror( int err );
753 :
754 : Do this as often as desired in a compilation unit to get different
755 : types of concurrent maps. Options exist for generating library
756 : header prototypes and/or library implementations for concurrent maps
757 : usable across multiple compilation units. Additional options exist
758 : to use index compression, different hashing functions, key comparison
759 : functions, etc as detailed below.
760 :
761 : To better understand the insert/remove/{modify,query}_{try,test}
762 : APIs:
763 :
764 : ... basic insert
765 :
766 : myele_t * ele = ... acquire an unused element from the element store
767 :
768 : ... populate ele appropriately, including
769 :
770 : ele->key = ... key associated with this element
771 :
772 : int err = mymap_insert( join, ele, FD_MAP_FLAG_BLOCKING );
773 :
774 : if( FD_UNLIKELY( err ) ) { // Not possible in this example
775 :
776 : ... If err is FD_MAP_ERR_INVAL, ele did not point at an element
777 : ... store element.
778 : ...
779 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
780 : ... conflicting operation in progress on the mymap during the
781 : ... call. We can try again later (e.g. after a random backoff or
782 : ... doing other non-conflicting work).
783 :
784 : } else {
785 :
786 : ... At this point, a mapping from key to the element store
787 : ... element pointed to by ele in our address space was added
788 : ... during the call. ele->key will be stable while in the mymap.
789 : ... Neither ele->key nor ele->next should be modified by the
790 : ... application while in the mymap. The application is free to
791 : ... manage all other fields of the element as desired.
792 :
793 : }
794 :
795 : ... basic remove
796 :
797 : ulong key = ... key to remove
798 :
799 : mymap_query_t query[1];
800 : int err = mymap_remove( join, &key, NULL, query, FD_MAP_FLAG_BLOCKING );
801 : mymap_ele_t * ele = mymap_query_ele( query );
802 :
803 : if( FD_UNLIKELY( err ) ) {
804 :
805 : ... At this point, ele==sentinel==NULL.
806 : ...
807 : ... If err is FD_MAP_ERR_KEY, key was not in the mymap at some
808 : ... point during the remove.
809 : ...
810 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
811 : ... conflicting operation in progress during the remove. We can
812 : ... try again later (e.g. after a random backoff or doing other
813 : ... non-conflicting work). (Not possible in this example.)
814 : ...
815 : ... If err is FD_MAP_ERR_CORRUPT, memory corruption was detected
816 : ... at some point during the call. (Usually abortive.)
817 :
818 : } else {
819 :
820 : ... At this point, ele points into the element store (non-NULL),
821 : ... ele->key matches key, key mapped to that element before the
822 : ... remove, and we have ownership of that element.
823 :
824 : ... release ele to the element store
825 :
826 : }
827 :
828 : ... basic modify
829 :
830 : ulong key = ... key to modify
831 :
832 : mymap_query_t query[1];
833 : int err = mymap_modify_try( join, &key, NULL, query, FD_MAP_FLAG_BLOCKING );
834 : mymap_ele_t * ele = mymap_query_ele( query );
835 :
836 : if( FD_UNLIKELY( err ) ) {
837 :
838 : ... At this point, ele==sentinel==NULL.
839 : ...
840 : ... If err is FD_MAP_ERR_KEY, key was not in the mymap at some
841 : ... point during the try.
842 : ...
843 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
844 : ... conflicting operation in progress during the try. We can try
845 : ... again later (e.g. after a random backoff or doing other
846 : ... non-conflicting work). (Not possible in this example.)
847 : ...
848 : ... If err is FD_MAP_ERR_CORRUPT, memory corruption was detected
849 : ... at some point during the call. (Usually abortive.)
850 :
851 : } else {
852 :
853 : ... At this point, ele points in our address space to an element
854 : ... store element, ele->key matches key and we are in a modify try
855 : ... such that it is safe to modify fields ele not managed by the
856 : ... mymap.
857 :
858 : ... Modify application managed fields of ele here.
859 :
860 : ... IMPORTANT SAFETY TIP! IF THE USER WANTS TO SUPPORT ROLLING
861 : ... BACK A MODIFICATION AT THIS POINT, THEY CAN DO SO BY SAVING
862 : ... THE ORIGINAL VALUE OF ELE BEFORE MODIFYING ANY FIELDS AND
863 : ... THEN RESTORING IT HERE.
864 :
865 : ... Finish the modification (guaranteed to succeed)
866 :
867 : mymap_modify_test( query );
868 :
869 : ... At this point, the modification is done and we are no
870 : ... longer in a try.
871 :
872 : }
873 :
874 : ... basic speculative query
875 :
876 : ulong key = ... key to query
877 :
878 : mymap_query_t query[1];
879 : int err = mymap_query_try( join, &key, NULL, query, 0 );
880 : mymap_ele_t const * ele = mymap_query_ele_const( query );
881 :
882 : if( FD_UNLIKELY( err ) ) {
883 :
884 : ... At this point, ele==sentinel==NULL.
885 : ...
886 : ... If err is FD_MAP_ERR_KEY, key was not in the mymap at some
887 : ... point during the try.
888 : ...
889 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
890 : ... conflicting operation in progress during the try and we can
891 : ... try again later (e.g. after a random backoff or doing other
892 : ... non-conflicting work).
893 : ...
894 : ... If err is FD_MAP_ERR_CORRUPT, memory corruption was detected
895 : ... during the call. (Usually abortive.)
896 :
897 : } else {
898 :
899 : ... At this point, ele points in our address space to an element
900 : ... in the element store (non-NULL) and ele->key matched key at
901 : ... some point during the try.
902 :
903 : ... Speculatively process ele here.
904 : ...
905 : ... DO NOT TRUST ANY RESULTS OF THIS SPECULATIVE PROCESSING YET.
906 : ... THERE IS NO GUARANTEE YET THAT A CONCURRENT USER HASN'T
907 : ... CHANGED THE MYMAP IN A WAY THAT COULD YIELD ARBITRARY AND
908 : ... INCONSISTENT RESULTS.
909 : ...
910 : ... The simplest and most common form of speculative processing
911 : ... is to copy the needed portions of ele into a local stack
912 : ... temp.
913 : ...
914 : ... Note: concurrent operations could include removing key from
915 : ... the mymap (and maybe multiple cycles of inserting and
916 : ... removing it and then at potentially different element store
917 : ... locations). That's not an issue practically as the ele
918 : ... pointer here will be to an element compatible memory region
919 : ... that will continue to exist regardless and we shouldn't be
920 : ... trusting any query reads yet (the query test will detect if
921 : ... if these can be trusted).
922 : ...
923 : ... Rant: If ele is more complex than plain-old-data, so long ele
924 : ... is using allocators like fd_alloc and fd_wksp for dynamically
925 : ... allocated fields (e.g. not using the giant steaming pile of
926 : ... page based memory virtual memory, operating system, language
927 : ... and standard library fail that is heap based allocation ala
928 : ... malloc/free), concurrent removes are _still_ fine for the
929 : ... exact same reason. That is, the memory that actually backed
930 : ... dynamically allocated fields will still continue to exist
931 : ... post remove ... you know ... just like reality (turns out,
932 : ... surprise, "free" doesn't actually uninstall any DIMMs and
933 : ... malloc/free are the worst possible abstraction for resource
934 : ... management).
935 : ...
936 : ... The concurrent remove case actually demonstrates why fd_alloc
937 : ... / fd_wksp / fd_shmem / etc exist in the first place. Beyond
938 : ... being faster, simpler, more concurrent and more reliable
939 : ... (especially in cases like this), they are more flexible (e.g.
940 : ... sharing and persisting the data structure asynchronously
941 : ... across multiple processes in different address spaces) and
942 : ... more secure (e.g. can easily bounds check memory accesses
943 : ... and then use the memory subsystem to sandbox different
944 : ... components from touching memory they shouldn't, actually
945 : ... using a modern virtual memory subsystem for something useful
946 : ... for a change instead of bending over backwards to provide
947 : ... exactly the wrong abstraction of the real world). Common
948 : ... hardware and software practices have turned computers into an
949 : ... unreliable and insecure Tower of Babel. Had virtual memory
950 : ... been better abstracted and better implemented all levels of
951 : ... the stack, life would be much easier (and things like fast
952 : ... persistent memories might have seen a lot more commercial
953 : ... success). In the meantime, dispelling the magical thinking
954 : ... encouraged by the conventional abstractions, the key lessons
955 : ... are:
956 : ...
957 : ... * Friends don't let friends malloc.
958 : ... * Lockfree is not a synonym for garbage collection.
959 : ... * Real world computers aren't infinite tape Turing machines.
960 : ... * Real world memory doesn't magically disappear.
961 :
962 : ... At this point, we are done with speculative processing (or we
963 : ... don't want to do any more speculative processing if the try
964 : ... has already failed).
965 :
966 : err = mymap_query_test( query );
967 : if( FD_UNLIKELY( err ) ) {
968 :
969 : ... At this point, err will be FD_MAP_ERR_AGAIN and a
970 : ... potentially conflicting operation in the try was detected
971 : ... by the test.
972 :
973 : ... Application specific handling here (e.g. try again after a
974 : ... random backoff or doing other non-conflicting work).
975 :
976 : } else {
977 :
978 : ... At this point, the results of the speculation thus far can
979 : ... be trusted and can be considered to have been computed at
980 : ... some point in time between try and test.
981 :
982 : }
983 : }
984 :
985 : To better understand the txn API:
986 :
987 : ... allocate a txn
988 :
989 : ulong align = mymap_txn_align();
990 : ulong footprint = mymap_txn_footprint( key_max );
991 : void * ltxn = ... allocate align/footprint local scratch memory
992 : mymap_txn_t * txn = mymap_txn_init( ltxn, join, key_max );
993 :
994 : ... add at most key_max keys to the transaction as locked
995 :
996 : for( ... all keys involved in the transaction ... ) mymap_txn_add( txn, key, 1 ); // guaranteed to succeed for this example
997 :
998 : ... try to do the transaction
999 :
1000 : int err = mymap_txn_try( txn, FD_MAP_FLAG_BLOCKING );
1001 :
1002 : if( FD_UNLIKELY( err ) ) { // Not possible in this example
1003 :
1004 : ... At this point, err is FD_MAP_ERR_AGAIN and there was a
1005 : ... potentially conflicting operation in progress during the try.
1006 : ... We can try again later (e.g. after a random backoff or doing
1007 : ... other non-conflicting work). We are no longer in a try but
1008 : ... we could reuse the txn as-is to retry.
1009 :
1010 : } else {
1011 :
1012 : ... At this point, it is safe to try the transaction.
1013 :
1014 : ... Do the transaction here. Since all keys are locked in this
1015 : ... example, we don't need to worry about any changing behind our
1016 : ... back (i.e. the try is guaranteed to succeed).
1017 :
1018 : ... Like modify, if we wants to rollback the transaction at this
1019 : ... point, we should save the state of all locked keys involved
1020 : ... to local temporaries before we do the transaction and then
1021 : ... restore the state here.
1022 :
1023 : ... Finish the try (guaranteed to succeed for this example)
1024 :
1025 : mymap_txn_test( txn );
1026 :
1027 : ... At this point, we are no longer in a txn try but the txn is
1028 : ... valid such that we could reuse the txn as-is for another
1029 : ... transaction involving the same keys.
1030 :
1031 : mymap_txn_fini( txn );
1032 :
1033 : ... At this point, txn is no longer valid and we have ownership of
1034 : ... the ltxn memory region
1035 :
1036 : ... free ltxn
1037 :
1038 : }
1039 :
1040 : To better understand the iter API:
1041 :
1042 : ... basic mymap element snapshot (i.e. iterate over all elements in
1043 : ... the mymap at a globally consistent point in time while
1044 : ... minimizing contention with other concurrent operations)
1045 :
1046 : ulong lock_cnt = mymap_chain_cnt( join );
1047 :
1048 : ulong * lock_seq = ... allocate lock_cnt ulong scratch ...
1049 :
1050 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) lock_seq[ lock_idx ] = lock_idx;
1051 :
1052 : mymap_iter_lock( join, lock_seq, lock_cnt, FD_MAP_FLAG_BLOCKING );
1053 :
1054 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) {
1055 : ulong chain_idx = lock_seq[ lock_idx ]; // process chains in the order they were locked
1056 :
1057 : for( mymap_iter_t iter = mymap_iter( join, chain_idx ); !mymap_iter_done( iter ); iter = mymap_iter_next( iter ) ) {
1058 : myele_t const * ele = mymap_iter_ele_const( iter );
1059 :
1060 : ... append ele to snapshot here (ele will be appended in
1061 : ... no particular order for this example). Note that, as
1062 : ... the caller has a lock on the chain that manages ele,
1063 : ... the caller is free to modify the fields of ele it
1064 : ... manages.
1065 :
1066 : }
1067 :
1068 : mymap_iter_unlock( join, lock_seq + lock_idx, 1UL ); // unlock incrementally
1069 : }
1070 :
1071 : ... free lock_seq here
1072 : */
1073 :
1074 : #include "fd_map.h"
1075 :
1076 : /* FIXME: consider adding a parallel verify that operates on a
1077 : locked/idle subset of the chains. */
1078 :
1079 : /* MAP_NAME gives the API prefix to use for map */
1080 :
1081 : #ifndef MAP_NAME
1082 : #error "Define MAP_NAME"
1083 : #endif
1084 :
1085 : /* MAP_ELE_T is the map element type */
1086 :
1087 : #ifndef MAP_ELE_T
1088 : #error "Define MAP_ELE_T"
1089 : #endif
1090 :
1091 : /* MAP_KEY_T is the map key type */
1092 :
1093 : #ifndef MAP_KEY_T
1094 : #define MAP_KEY_T ulong
1095 : #endif
1096 :
1097 : /* MAP_KEY is the MAP_ELE_T key field */
1098 :
1099 : #ifndef MAP_KEY
1100 : #define MAP_KEY key
1101 : #endif
1102 :
1103 : /* MAP_IDX_T is the map next index type. Should be a primitive unsigned
1104 : integer type large enough to represent the largest capacity element
1105 : store of interest. (E.g. if ushort, the maximum element store
1106 : capacity compatible with the map will be 65535 elements.) */
1107 :
1108 : #ifndef MAP_IDX_T
1109 2966346 : #define MAP_IDX_T ulong
1110 : #endif
1111 :
1112 : /* MAP_NEXT is the MAP_ELE_T next field */
1113 :
1114 : #ifndef MAP_NEXT
1115 : #define MAP_NEXT next
1116 : #endif
1117 :
1118 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
1119 :
1120 : #ifndef MAP_KEY_EQ
1121 22516527 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
1122 : #endif
1123 :
1124 : /* MAP_KEY_HASH returns a random mapping of *key into ulong. The
1125 : mapping is parameterized by the 64-bit ulong seed. */
1126 :
1127 : #ifndef MAP_KEY_HASH
1128 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
1129 : #endif
1130 :
1131 : /* If MAP_MEMOIZE is defined to non-zero, elements have a field that
1132 : can be used while in the map to hold the MAP_KEY_HASH for an
1133 : element's key. This is useful for accelerating user code that might
1134 : need a hash and various map operations. */
1135 :
1136 : #ifndef MAP_MEMOIZE
1137 : #define MAP_MEMOIZE 0
1138 : #endif
1139 :
1140 : /* If MAP_MEMOIZE is non-zero, MAP_MEMO is the memo element field.
1141 : Should be a ulong. Like MAP_KEY and MAP_NEXT, when an element is in
1142 : the map, this value is managed by the map and will contain the
1143 : MAP_KEY_HASH of the element's key and the map's seed. */
1144 :
1145 : #ifndef MAP_MEMO
1146 : #define MAP_MEMO memo
1147 : #endif
1148 :
1149 : /* If MAP_MEMOIZE is defined to non-zero, a non-zero MAP_KEY_EQ_IS_SLOW
1150 : indicates the MAP_MEMO field should be used to accelerate MAP_KEY_EQ
1151 : operations. This is useful when MAP_KEY_EQ is non-trivial (e.g.
1152 : variable length string compare, large buffer compares, etc). */
1153 :
1154 : #ifndef MAP_KEY_EQ_IS_SLOW
1155 : #define MAP_KEY_EQ_IS_SLOW 0
1156 : #endif
1157 :
1158 : /* MAP_CNT_WIDTH gives the number of bits in a ulong to reserve for
1159 : encoding the count in a versioned count. Element store capacity
1160 : should be representable in this width. Default is 43 bits (e.g.
1161 : enough to support a ~1 PiB element store of 128 byte elements). The
1162 : versioning width will be 64-MAP_CNT_WIDTH. Since the least
1163 : significant bit of the version is used to indicate locked, versioning
1164 : width should be at least 2 and ideally as large as possible. With
1165 : the 43 default, a chain's version number will not be reused until
1166 : 2^20 individual operations on a chain have been done. Version
1167 : numbers only impact speculative operations. If not using speculative
1168 : operations, version width can be reduced to the minimum. */
1169 :
1170 : #ifndef MAP_CNT_WIDTH
1171 107099283 : #define MAP_CNT_WIDTH (43)
1172 : #endif
1173 :
1174 : /* MAP_ALIGN gives the alignment required for the map shared memory.
1175 : Default is 128 for double cache line alignment. Should be at least
1176 : ulong alignment. */
1177 :
1178 : #ifndef MAP_ALIGN
1179 : #define MAP_ALIGN (128UL)
1180 : #endif
1181 :
1182 : /* MAP_MAGIC is the shared memory magic number to aid in persistent
1183 : and/or interprocess usage. */
1184 :
1185 : #ifndef MAP_MAGIC
1186 3 : #define MAP_MAGIC (0xf17eda2c37a7a900UL) /* firedancer map_para version 0 */
1187 : #endif
1188 :
1189 : /* MAP_IMPL_STYLE controls what to generate:
1190 : 0 - header only library
1191 : 1 - library header declaration
1192 : 2 - library implementation */
1193 :
1194 : #ifndef MAP_IMPL_STYLE
1195 : #define MAP_IMPL_STYLE 0
1196 : #endif
1197 :
1198 : /* If MAP_PEDANTIC is defined to non-zero, aborts with FD_LOG_CRIT
1199 : instead of gracefully returning if corruption is found. */
1200 :
1201 : #ifndef MAP_PEDANTIC
1202 : #define MAP_PEDANTIC 0
1203 : #endif
1204 :
1205 : /* Implementation *****************************************************/
1206 :
1207 57413286 : #define MAP_VER_WIDTH (64-MAP_CNT_WIDTH)
1208 :
1209 : #if MAP_IMPL_STYLE==0 /* local use only */
1210 : #define MAP_STATIC FD_FN_UNUSED static
1211 : #else /* library header and/or implementation */
1212 : #define MAP_STATIC
1213 : #endif
1214 :
1215 397589535 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
1216 :
1217 : #if MAP_IMPL_STYLE!=2 /* need header */
1218 :
1219 : #include "../bits/fd_bits.h"
1220 : #include "../racesan/fd_racesan_target.h"
1221 :
1222 : /* Note: we don't overalign chain metadata to reduce on map metadata
1223 : footprint requirements. Though this can cause cache false sharing
1224 : for concurrent operations on different keys that are managed
1225 : different chains that share a cache line, this risk can be controlled
1226 : by overprovisioning chain_cnt. That is, for a fixed map metadata
1227 : footprint, this false sharing seems preferable to using fewer chains
1228 : as that would lead to an equivalent increase in the amount of locking
1229 : necessary to avoid potential conflicts for keys managed by the same
1230 : chain (i.e. the former makes good use of the padding that would be
1231 : otherwise wasted if overaligning this). */
1232 :
1233 : struct MAP_(shmem_private_chain) {
1234 : ulong ver_cnt; /* versioned count, cnt is in [0,ele_max] in lsb, ver in msb, odd: chain locked, even: chain unlocked */
1235 : MAP_IDX_T head_cidx; /* compressed index of the first element on the chain */
1236 : };
1237 :
1238 : typedef struct MAP_(shmem_private_chain) MAP_(shmem_private_chain_t);
1239 :
1240 : struct __attribute__((aligned(MAP_ALIGN))) MAP_(shmem_private) {
1241 :
1242 : /* FIXME: consider having a memo of the chain in which an element is
1243 : stored and/or using doubly linked list chains (maybe with the xor
1244 : trick)? We could do faster variants of remove and maybe amortize
1245 : some hash calcs. */
1246 :
1247 : ulong magic; /* == MAP_MAGIC */
1248 : ulong seed; /* Hash seed, arbitrary */
1249 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
1250 :
1251 : /* Padding to MAP_ALIGN alignment here */
1252 :
1253 : /* MAP_(shmem_private_chain_t) chain[ chain_cnt ] here */
1254 : };
1255 :
1256 : typedef struct MAP_(shmem_private) MAP_(shmem_t);
1257 :
1258 : struct MAP_(private) {
1259 : MAP_(shmem_t) * map; /* Location of the map in the local address space */
1260 : MAP_ELE_T * ele; /* Location of the element store in the local address space */
1261 : ulong ele_max; /* Capacity of the element store, in [0,ele_max_max] */
1262 : };
1263 :
1264 : typedef struct MAP_(private) MAP_(t);
1265 :
1266 : struct MAP_(query_private) {
1267 : ulong memo; /* Query key memo */
1268 : MAP_ELE_T * ele; /* Points to the operation element in the local address space (or a sentinel) */
1269 : MAP_(shmem_private_chain_t) * chain; /* Points to the chain that manages element in the local address space */
1270 : ulong ver_cnt; /* Versioned count of the chain at operation try */
1271 : };
1272 :
1273 : typedef struct MAP_(query_private) MAP_(query_t);
1274 :
1275 : struct MAP_(txn_private_info) {
1276 : MAP_(shmem_private_chain_t) * chain; /* Points to the chain that manages one or more txn keys (set by txn_add) */
1277 : ulong ver_cnt; /* Versioned count of the chain at the transaction start (set by txn_try) */
1278 : };
1279 :
1280 : typedef struct MAP_(txn_private_info) MAP_(txn_private_info_t);
1281 :
1282 : struct MAP_(txn_private) {
1283 : MAP_(shmem_t) * map; /* Map used by this transaction */
1284 : ulong info_max; /* Number of chains possible for this transaction */
1285 : ulong lock_cnt; /* Number of chains in the locked set, in [0,info_max] */
1286 : ulong spec_cnt; /* Number of chains in the speculative set, in [0,info_max], lock_cnt + spec_cnt <= info_max */
1287 :
1288 : /* MAP_(txn_private_info_t) info[ info_max ] here (obligatory sigh
1289 : about lagging C++ support for 0 sized structure array footers).
1290 :
1291 : The locked set is at indices [0,lock_cnt), lock_cnt infos.
1292 : The free set is at indices [lock_cnt,info_max-spec_cnt), free_cnt = info_max-spec_cnt-lock_cnt infos.
1293 : The speculative set is at indices [info_max-spec_cnt,info_max), spec_cnt infos.
1294 :
1295 : A chain will appear at most once in a set. A chain will not appear
1296 : in both sets.
1297 :
1298 : Note that it would be trivial to make this shared memory persistent
1299 : though not obvious if that would be useful. (A precomputed
1300 : template for a common transaction done by multiple threads is a
1301 : possibility but the versions would still need to be local.) */
1302 :
1303 : };
1304 :
1305 : typedef struct MAP_(txn_private) MAP_(txn_t);
1306 :
1307 : struct MAP_(iter_private) {
1308 : MAP_ELE_T const * ele; /* Pointer to the element store in the caller's address space */
1309 : ulong ele_idx; /* Current iteration element store index (or the null index) */
1310 : };
1311 :
1312 : typedef struct MAP_(iter_private) MAP_(iter_t);
1313 :
1314 : FD_PROTOTYPES_BEGIN
1315 :
1316 : /* map_private_vcnt pack ver and cnt into a versioned cnt. ver is
1317 : masked to fit into MAP_VER_WIDTH bits. cnt is assumed in
1318 : [0,ele_max_max].
1319 :
1320 : map_private_vcnt_{ver,cnt} extract the {version,index} from a
1321 : versioned index. Return will fit into {MAP_VER_WIDTH,MAP_CNT_WIDTH}
1322 : bits. */
1323 :
1324 11538462 : FD_FN_CONST static inline ulong MAP_(private_vcnt)( ulong ver, ulong cnt ) { return (ver<<MAP_CNT_WIDTH) | cnt; }
1325 :
1326 12712338 : FD_FN_CONST static inline ulong MAP_(private_vcnt_ver)( ulong ver_cnt ) { return ver_cnt >> MAP_CNT_WIDTH; }
1327 27205536 : FD_FN_CONST static inline ulong MAP_(private_vcnt_cnt)( ulong ver_cnt ) { return (ver_cnt << MAP_VER_WIDTH) >> MAP_VER_WIDTH; }
1328 :
1329 : /* map_shmem_private_chain returns the location in the caller's address
1330 : space of the map chain metadata associated with hash. The chain
1331 : associated with hash 0 is the first chain. Assumes map is valid.
1332 : map_shmem_private_chain_const is a const correct version. */
1333 :
1334 : FD_FN_PURE static inline MAP_(shmem_private_chain_t) *
1335 : MAP_(shmem_private_chain)( MAP_(shmem_t) * map,
1336 42574947 : ulong hash ) {
1337 42574947 : return (MAP_(shmem_private_chain_t) *)(map+1) + (hash & (map->chain_cnt-1UL));
1338 42574947 : }
1339 :
1340 : FD_FN_PURE static inline MAP_(shmem_private_chain_t) const *
1341 : MAP_(shmem_private_chain_const)( MAP_(shmem_t) const * map,
1342 13060719 : ulong hash ) {
1343 13060719 : return (MAP_(shmem_private_chain_t) const *)(map+1) + (hash & (map->chain_cnt-1UL));
1344 13060719 : }
1345 :
1346 : /* map_txn_private_info returns the location in the caller's address
1347 : space of the txn info. Assumes txn is valid. */
1348 :
1349 : FD_FN_CONST static inline MAP_(txn_private_info_t) *
1350 12157923 : MAP_(txn_private_info)( MAP_(txn_t) * txn ) {
1351 12157923 : return (MAP_(txn_private_info_t) *)(txn+1);
1352 12157923 : }
1353 :
1354 : /* map_private_{cidx,idx} compress / decompress 64-bit in-register
1355 : indices to/from their in-memory representations. */
1356 :
1357 7928304 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_cidx)( ulong idx ) { return (MAP_IDX_T)idx; }
1358 44957682 : FD_FN_CONST static inline ulong MAP_(private_idx) ( MAP_IDX_T cidx ) { return (ulong) cidx; }
1359 :
1360 : /* map_private_idx_null returns the element storage index that
1361 : represents NULL. */
1362 :
1363 809061 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
1364 :
1365 : /* map_private_idx_is_null returns 1 if idx is the NULL map index and 0
1366 : otherwise. */
1367 :
1368 16687224 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
1369 :
1370 : /* map_private_fetch_and_or does a ulong FD_ATOMIC_FETCH_AND_OR when the
1371 : target has FD_HAS_ATOMIC and emulates it when not. When emulated,
1372 : the map will not be safe to use concurrently but will still work. */
1373 :
1374 : static inline ulong
1375 : MAP_(private_fetch_and_or)( ulong volatile * p,
1376 21711138 : ulong b ) {
1377 21711138 : ulong x;
1378 21711138 : FD_COMPILER_MFENCE();
1379 21711138 : # if FD_HAS_ATOMIC
1380 21711138 : x = FD_ATOMIC_FETCH_AND_OR( p, b );
1381 : # else
1382 : x = *p;
1383 : *p = x | b;
1384 : # endif
1385 21711138 : FD_COMPILER_MFENCE();
1386 21711138 : return x;
1387 21711138 : }
1388 :
1389 3002214 : FD_FN_CONST static inline ulong MAP_(ele_max_max)( void ) { return (ulong)(MAP_IDX_T)(ULONG_MAX >> MAP_VER_WIDTH); }
1390 :
1391 : FD_FN_CONST static inline ulong
1392 3002745 : MAP_(chain_max)( void ) {
1393 3002745 : return fd_ulong_pow2_dn( (ULONG_MAX - sizeof(MAP_(shmem_t)) - alignof(MAP_(shmem_t)) + 1UL) /
1394 3002745 : sizeof(MAP_(shmem_private_chain_t)) );
1395 3002745 : }
1396 :
1397 : FD_FN_CONST static inline ulong
1398 3001212 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
1399 :
1400 : /* Clamp to be in [1,ele_max_max] (as ele_max_est 0 is degenerate and
1401 : as the map is guaranteed to hold at most ele_max_max keys). */
1402 :
1403 3001212 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max_max)() );
1404 :
1405 : /* Compute the number of chains as the power of 2 that makes the
1406 : average chain length between ~1 and ~2 when ele_max_est are stored
1407 : in the map and then clamp to the chain max. */
1408 :
1409 3001212 : ulong chain_min = (ele_max_est>>1) + (ele_max_est&1UL); /* chain_min = ceil(ele_max_est/2), in [1,2^63], computed w/o overflow */
1410 3001212 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
1411 :
1412 3001212 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
1413 3001212 : }
1414 :
1415 3906 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(shmem_t)); }
1416 :
1417 : FD_FN_CONST static inline ulong
1418 1050 : MAP_(footprint)( ulong chain_cnt ) {
1419 1050 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
1420 : /* Note: assumes shmem_t and shmem_private_chain_t have compatible alignments */
1421 1038 : return fd_ulong_align_up( sizeof(MAP_(shmem_t)) + chain_cnt*sizeof(MAP_(shmem_private_chain_t)),
1422 1038 : alignof(MAP_(shmem_t)) ); /* no overflow */
1423 1050 : }
1424 :
1425 408 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return join->map->seed; }
1426 2259 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return join->map->chain_cnt; }
1427 :
1428 3 : FD_FN_PURE static inline void const * MAP_(shmap_const)( MAP_(t) const * join ) { return join->map; }
1429 3 : FD_FN_PURE static inline void const * MAP_(shele_const)( MAP_(t) const * join ) { return join->ele; }
1430 3 : FD_FN_PURE static inline ulong MAP_(ele_max) ( MAP_(t) const * join ) { return join->ele_max; }
1431 :
1432 3 : FD_FN_PURE static inline void * MAP_(shmap)( MAP_(t) * join ) { return join->map; }
1433 3 : FD_FN_PURE static inline void * MAP_(shele)( MAP_(t) * join ) { return join->ele; }
1434 :
1435 : FD_FN_PURE static inline int
1436 : MAP_(key_eq)( MAP_KEY_T const * k0,
1437 27692190 : MAP_KEY_T const * k1 ) {
1438 27692190 : return !!(MAP_KEY_EQ( (k0), (k1) ));
1439 27692190 : }
1440 :
1441 : FD_FN_PURE static inline ulong
1442 : MAP_(key_hash)( MAP_KEY_T const * key,
1443 57816855 : ulong seed ) {
1444 57816855 : return (MAP_KEY_HASH( (key), (seed) ));
1445 57816855 : }
1446 :
1447 : static inline void
1448 : MAP_(backoff)( ulong scale,
1449 0 : ulong seed ) {
1450 0 : ulong r = (ulong)(uint)fd_ulong_hash( seed ^ (((ulong)fd_tickcount())<<32) );
1451 0 : for( ulong rem=(scale*r)>>48; rem; rem-- ) FD_SPIN_PAUSE();
1452 0 : }
1453 :
1454 25042929 : FD_FN_PURE static inline ulong MAP_(query_memo )( MAP_(query_t) const * query ) { return query->memo; }
1455 5380869 : FD_FN_PURE static inline MAP_ELE_T const * MAP_(query_ele_const)( MAP_(query_t) const * query ) { return query->ele; }
1456 12591579 : FD_FN_PURE static inline MAP_ELE_T * MAP_(query_ele )( MAP_(query_t) * query ) { return query->ele; }
1457 :
1458 : static inline int
1459 1873248 : MAP_(modify_test)( MAP_(query_t) * query ) {
1460 1873248 : MAP_(shmem_private_chain_t) * chain = query->chain;
1461 1873248 : ulong ver_cnt = query->ver_cnt;
1462 1873248 : FD_COMPILER_MFENCE();
1463 1873248 : chain->ver_cnt = ver_cnt + (2UL<<MAP_CNT_WIDTH);
1464 1873248 : FD_COMPILER_MFENCE();
1465 1873248 : return FD_MAP_SUCCESS;
1466 1873248 : }
1467 :
1468 : static inline int
1469 2444868 : MAP_(query_test)( MAP_(query_t) const * query ) {
1470 2444868 : MAP_(shmem_private_chain_t) const * chain = query->chain;
1471 2444868 : ulong ver_cnt = query->ver_cnt;
1472 2444868 : FD_COMPILER_MFENCE();
1473 2444868 : ulong _ver_cnt = chain->ver_cnt;
1474 2444868 : FD_COMPILER_MFENCE();
1475 2444868 : return fd_int_if( ver_cnt==_ver_cnt, FD_MAP_SUCCESS, FD_MAP_ERR_AGAIN );
1476 2444868 : }
1477 :
1478 : FD_FN_CONST static inline ulong
1479 3742632 : MAP_(txn_key_max_max)( void ) {
1480 3742632 : return (ULONG_MAX - sizeof(MAP_(txn_t)) - alignof(MAP_(txn_t)) + 1UL) / sizeof( MAP_(txn_private_info_t) );
1481 3742632 : }
1482 :
1483 3742626 : FD_FN_CONST static inline ulong MAP_(txn_align)( void ) { return alignof(MAP_(txn_t)); }
1484 :
1485 : FD_FN_CONST static inline ulong
1486 6 : MAP_(txn_footprint)( ulong key_max ) {
1487 6 : if( key_max > MAP_(txn_key_max_max)() ) return 0UL;
1488 3 : return sizeof(MAP_(txn_t)) + key_max*sizeof(MAP_(txn_private_info_t)); /* no overflow */
1489 6 : }
1490 :
1491 : static inline MAP_(txn_t) *
1492 : MAP_(txn_init)( void * mem,
1493 : MAP_(t) * join,
1494 3742623 : ulong key_max ) {
1495 3742623 : MAP_(txn_t) * txn = (MAP_(txn_t) *)mem;
1496 3742623 : if( FD_UNLIKELY( (!mem ) |
1497 3742623 : (!fd_ulong_is_aligned( (ulong)mem, MAP_(txn_align)() )) |
1498 3742623 : (!join ) |
1499 3742623 : (key_max > MAP_(txn_key_max_max)() ) ) ) return NULL;
1500 3742611 : txn->map = join->map;
1501 3742611 : txn->info_max = key_max; /* Worst case number of chains impacted by this transaction */
1502 3742611 : txn->lock_cnt = 0UL;
1503 3742611 : txn->spec_cnt = 0UL;
1504 3742611 : return txn;
1505 3742623 : }
1506 :
1507 3742614 : FD_FN_CONST static inline void * MAP_(txn_fini)( MAP_(txn_t) * txn ) { return (void *)txn; }
1508 :
1509 : FD_FN_PURE static inline ulong
1510 : MAP_(iter_chain_idx)( MAP_(t) const * join,
1511 3 : MAP_KEY_T const * key ) {
1512 3 : MAP_(shmem_t) const * map = join->map;
1513 3 : return MAP_(key_hash)( key, map->seed ) & (map->chain_cnt-1UL);
1514 3 : }
1515 :
1516 : FD_FN_PURE static inline MAP_(iter_t)
1517 : MAP_(iter)( MAP_(t) const * join,
1518 6774318 : ulong chain_idx ) {
1519 : /* FIXME: consider iter = {NULL,NULL} if chain_idx >= join->map->chain_cnt? */
1520 6774318 : MAP_(shmem_private_chain_t) const * chain = MAP_(shmem_private_chain_const)( join->map, 0UL ) + chain_idx;
1521 6774318 : MAP_(iter_t) iter;
1522 6774318 : iter.ele = join->ele;
1523 6774318 : iter.ele_idx = MAP_(private_idx)( chain->head_cidx );
1524 6774318 : return iter;
1525 6774318 : }
1526 :
1527 9630201 : FD_FN_CONST static inline int MAP_(iter_done)( MAP_(iter_t) iter ) { return MAP_(private_idx_is_null)( iter.ele_idx ); }
1528 :
1529 : __attribute__((warn_unused_result))
1530 : FD_FN_PURE static inline MAP_(iter_t)
1531 2850792 : MAP_(iter_next)( MAP_(iter_t) iter ) {
1532 2850792 : MAP_ELE_T const * ele = iter.ele + iter.ele_idx;
1533 2850792 : iter.ele_idx = MAP_(private_idx)( ele->MAP_NEXT );
1534 2850792 : return iter;
1535 2850792 : }
1536 :
1537 : FD_FN_CONST static inline MAP_ELE_T *
1538 32598 : MAP_(iter_ele)( MAP_(iter_t) iter ) {
1539 32598 : return (MAP_ELE_T *)(iter.ele + iter.ele_idx);
1540 32598 : }
1541 :
1542 : FD_FN_CONST static inline MAP_ELE_T const *
1543 2823282 : MAP_(iter_ele_const)( MAP_(iter_t) iter ) {
1544 2823282 : return iter.ele + iter.ele_idx;
1545 2823282 : }
1546 :
1547 : MAP_STATIC void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
1548 : MAP_STATIC MAP_(t) * MAP_(join) ( void * ljoin, void * shmap, void * shele, ulong ele_max );
1549 : MAP_STATIC void * MAP_(leave) ( MAP_(t) * join );
1550 : MAP_STATIC void * MAP_(delete)( void * shmap );
1551 :
1552 : MAP_STATIC void
1553 : MAP_(hint)( MAP_(t) const * join,
1554 : MAP_KEY_T const * key,
1555 : MAP_(query_t) * query,
1556 : int flags );
1557 :
1558 : MAP_STATIC int MAP_(insert)( MAP_(t) * join, MAP_ELE_T * ele, int flags );
1559 :
1560 : MAP_STATIC int
1561 : MAP_(remove)( MAP_(t) * join,
1562 : MAP_KEY_T const * key,
1563 : MAP_ELE_T const * sentinel,
1564 : MAP_(query_t) * query,
1565 : int flags );
1566 :
1567 : MAP_STATIC int
1568 : MAP_(modify_try)( MAP_(t) * join,
1569 : MAP_KEY_T const * key,
1570 : MAP_ELE_T * sentinel,
1571 : MAP_(query_t) * query,
1572 : int flags );
1573 :
1574 : MAP_STATIC int
1575 : MAP_(query_try)( MAP_(t) const * join,
1576 : MAP_KEY_T const * key,
1577 : MAP_ELE_T const * sentinel,
1578 : MAP_(query_t) * query,
1579 : int flags );
1580 :
1581 : MAP_STATIC int MAP_(txn_add)( MAP_(txn_t) * txn, MAP_KEY_T const * key, int lock );
1582 :
1583 : MAP_STATIC int MAP_(txn_try)( MAP_(txn_t) * txn, int flags );
1584 :
1585 : static inline void
1586 : MAP_(txn_hint)( MAP_(t) const * join,
1587 : MAP_KEY_T const * key,
1588 : MAP_(query_t) * query,
1589 3276729 : int flags ) {
1590 3276729 : MAP_(hint)( join, key, query, flags );
1591 3276729 : }
1592 :
1593 : MAP_STATIC int
1594 : MAP_(txn_insert)( MAP_(t) * join,
1595 : MAP_ELE_T * ele );
1596 :
1597 : MAP_STATIC int
1598 : MAP_(txn_remove)( MAP_(t) * join,
1599 : MAP_KEY_T const * key,
1600 : MAP_ELE_T const * sentinel,
1601 : MAP_(query_t) * query,
1602 : int flags );
1603 :
1604 : MAP_STATIC int
1605 : MAP_(txn_modify)( MAP_(t) * join,
1606 : MAP_KEY_T const * key,
1607 : MAP_ELE_T * sentinel,
1608 : MAP_(query_t) * query,
1609 : int flags );
1610 :
1611 : static inline int
1612 : MAP_(txn_query)( MAP_(t) const * join,
1613 : MAP_KEY_T const * key,
1614 : MAP_ELE_T const * sentinel,
1615 : MAP_(query_t) * query,
1616 1636176 : int flags ) {
1617 1636176 : return MAP_(txn_modify)( (MAP_(t) *)join, key, (MAP_ELE_T *)sentinel, query, flags & (~FD_MAP_FLAG_ADAPTIVE) );
1618 1636176 : }
1619 :
1620 : MAP_STATIC int MAP_(txn_test)( MAP_(txn_t) * txn );
1621 :
1622 : MAP_STATIC int
1623 : MAP_(iter_lock)( MAP_(t) * join,
1624 : ulong * lock_seq,
1625 : ulong lock_cnt,
1626 : int flags );
1627 :
1628 : MAP_STATIC void
1629 : MAP_(iter_unlock)( MAP_(t) * join,
1630 : ulong const * lock_seq,
1631 : ulong lock_cnt );
1632 :
1633 : MAP_STATIC void MAP_(reset)( MAP_(t) * join );
1634 :
1635 : MAP_STATIC int MAP_(verify)( MAP_(t) const * join );
1636 :
1637 : MAP_STATIC FD_FN_CONST char const * MAP_(strerror)( int err );
1638 :
1639 : FD_PROTOTYPES_END
1640 :
1641 : #endif
1642 :
1643 : #if MAP_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
1644 :
1645 : #include "../log/fd_log.h" /* Used by constructors and verify (FIXME: Consider making a compile time option) */
1646 :
1647 : /* MAP_CRIT_{BEGIN,BLOCKED,END} handle virtually all atomic boilerplate
1648 : for operations that require modifying a map chain's structure or
1649 : elements managed by that chain. Usage:
1650 :
1651 : MAP_CRIT( chain, blocking ) {
1652 :
1653 : ... At this point, we have a lock on the chain and the "ulong"
1654 : ... ver_cnt contains the chain's versioned count just before we
1655 : ... took the lock. The "int" retain_lock is zero.
1656 : ...
1657 : ... Do locked operations on the map chain here
1658 : ...
1659 : ... On exiting this block, if retain_lock is non-zero, we resume
1660 : ... execution immediately after MAP_CRIT_END. This is used for
1661 : ... "try" style operations where a "test" operation is done to
1662 : ... unlock the chain after the caller does their try/test work.
1663 : ... Otherwise, we will update the version number, unlock the
1664 : ... chain and then resume execution after MAP_CRIT_END.
1665 : ...
1666 : ... Because compiler memory fences are done just before entering
1667 : ... and after exiting this block, there is typically no need to
1668 : ... use any atomics / volatile / fencing here. That is, we can
1669 : ... just write "normal" code on platforms where writes to memory
1670 : ... become visible to other threads in the order in which they
1671 : ... were issued in the machine code (e.g. x86) as the version
1672 : ... update and unlock writes are after the changes done here
1673 : ... and others will not proceed until they see the new version
1674 : ... and unlock. YMMV for non-x86 platforms (probably need
1675 : ... additional hardware store fences in these macros).
1676 : ...
1677 : ... It is safe to use "break" and/or "continue" within this
1678 : ... block. The overall MAP_CRIT will exit with the appropriate
1679 : ... compiler fencing, version update and unlocking and then
1680 : ... execution will resume immediately after MAP_CRIT_END.
1681 : ...
1682 : ... IMPORTANT SAFETY TIP! DO NOT RETURN FROM THIS BLOCK.
1683 : ...
1684 : ... IMPORTANT SAFETY TIP! OPERATIONS THAT CHANGE THE CHAIN
1685 : ... ELEMENT COUNT SHOULD UPDATE VER_CNT's COUNT WHILE HOLDING
1686 : ... THE VERSION CONSTANT.
1687 :
1688 : } MAP_CRIT_BLOCKED {
1689 :
1690 : ... At this point, somebody else had a lock on the chain when we
1691 : ... tried to take the lock.
1692 : ...
1693 : ... Handle blocked here.
1694 : ...
1695 : ... On exiting this block, if blocking was zero in MAP_CRIT, we
1696 : ... will resume execution immediately after MAP_CRIT_END. If
1697 : ... blocking was non-zero, we will resume execution immediately
1698 : ... before MAP_CRIT (e.g. we will retry again after a short spin
1699 : ... pause). Similar considerations to the above for compiler
1700 : ... memory fences, "break" and "continue". As we do not have the
1701 : ... lock here, retain_lock is neither relevant nor available.
1702 : ...
1703 : ... IMPORTANT SAFETY TIP! DO NOT RETURN FROM THIS BLOCK.
1704 :
1705 : } MAP_CRIT_END; */
1706 :
1707 21711138 : #define MAP_CRIT(c,b) do { \
1708 21711138 : ulong volatile * _vc = (ulong volatile *)&(c)->ver_cnt; \
1709 21711138 : int _b = (b); \
1710 21711138 : int retain_lock = 0; \
1711 21711138 : for(;;) { \
1712 21711138 : fd_racesan_hook( "map_crit:check" ); \
1713 21711138 : ulong ver_cnt = *_vc; \
1714 21711138 : /* use a test-and-test-and-set style to reduce atomic contention */ \
1715 21711138 : if( FD_LIKELY( !(ver_cnt & (1UL<<MAP_CNT_WIDTH)) ) ) { /* opt for low contention */ \
1716 21711138 : ver_cnt = MAP_(private_fetch_and_or)( _vc, 1UL<<MAP_CNT_WIDTH ); \
1717 21711138 : if( FD_LIKELY( !(ver_cnt & (1UL<<MAP_CNT_WIDTH)) ) ) { /* opt for low contention */ \
1718 21711138 : fd_racesan_hook( "map_crit:pre_acquire" ); \
1719 21711138 : FD_COMPILER_MFENCE(); \
1720 21711138 : do
1721 :
1722 : #define MAP_CRIT_BLOCKED \
1723 21711138 : while(0); \
1724 21711138 : FD_COMPILER_MFENCE(); \
1725 9356079 : fd_racesan_hook( "map_crit:pre_release" ); \
1726 21711138 : if( !retain_lock ) *_vc = ver_cnt+(2UL<<MAP_CNT_WIDTH); /* likely compile time */ \
1727 21711138 : FD_COMPILER_MFENCE(); \
1728 9356079 : break; \
1729 21711138 : } \
1730 21711138 : } \
1731 21711138 : FD_COMPILER_MFENCE(); \
1732 0 : do
1733 :
1734 : #define MAP_CRIT_END \
1735 0 : while(0); \
1736 0 : FD_COMPILER_MFENCE(); \
1737 0 : if( !_b ) break; /* likely compile time */ \
1738 0 : FD_SPIN_PAUSE(); \
1739 0 : } \
1740 21711138 : } while(0)
1741 :
1742 : MAP_STATIC void *
1743 : MAP_(new)( void * shmem,
1744 : ulong chain_cnt,
1745 252 : ulong seed ) {
1746 :
1747 252 : if( FD_UNLIKELY( !shmem ) ) {
1748 3 : FD_LOG_WARNING(( "NULL shmem" ));
1749 3 : return NULL;
1750 3 : }
1751 :
1752 249 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) {
1753 3 : FD_LOG_WARNING(( "misaligned shmem" ));
1754 3 : return NULL;
1755 3 : }
1756 :
1757 246 : ulong footprint = MAP_(footprint)( chain_cnt );
1758 246 : if( FD_UNLIKELY( !footprint ) ) {
1759 6 : FD_LOG_WARNING(( "bad footprint" ));
1760 6 : return NULL;
1761 6 : }
1762 :
1763 : /* seed is arbitrary */
1764 :
1765 : /* Init the metadata */
1766 :
1767 240 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmem;
1768 :
1769 240 : map->seed = seed;
1770 240 : map->chain_cnt = chain_cnt;
1771 :
1772 : /* Set all the chains to version 0 and empty */
1773 :
1774 240 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, 0UL );
1775 807765 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
1776 807525 : chain[ chain_idx ].ver_cnt = MAP_(private_vcnt)( 0UL, 0UL );
1777 807525 : chain[ chain_idx ].head_cidx = MAP_(private_cidx)( MAP_(private_idx_null)() );
1778 807525 : }
1779 :
1780 240 : FD_COMPILER_MFENCE();
1781 240 : map->magic = MAP_MAGIC;
1782 240 : FD_COMPILER_MFENCE();
1783 :
1784 240 : return shmem;
1785 246 : }
1786 :
1787 : MAP_STATIC MAP_(t) *
1788 : MAP_(join)( void * ljoin,
1789 : void * shmap,
1790 : void * shele,
1791 540 : ulong ele_max ) {
1792 540 : MAP_(t) * join = (MAP_(t) *)ljoin;
1793 540 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmap;
1794 540 : MAP_ELE_T * ele = (MAP_ELE_T *)shele;
1795 :
1796 540 : if( FD_UNLIKELY( !join ) ) {
1797 3 : FD_LOG_WARNING(( "NULL ljoin" ));
1798 3 : return NULL;
1799 3 : }
1800 :
1801 537 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(MAP_(t)) ) ) ) {
1802 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
1803 3 : return NULL;
1804 3 : }
1805 :
1806 534 : if( FD_UNLIKELY( !map ) ) {
1807 3 : FD_LOG_WARNING(( "NULL shmap" ));
1808 3 : return NULL;
1809 3 : }
1810 :
1811 531 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
1812 3 : FD_LOG_WARNING(( "misaligned shmap" ));
1813 3 : return NULL;
1814 3 : }
1815 :
1816 528 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
1817 3 : FD_LOG_WARNING(( "bad magic" ));
1818 3 : return NULL;
1819 3 : }
1820 :
1821 525 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
1822 3 : FD_LOG_WARNING(( "NULL shele" ));
1823 3 : return NULL;
1824 3 : }
1825 :
1826 522 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(MAP_ELE_T) ) ) ) {
1827 3 : FD_LOG_WARNING(( "misaligned shele" ));
1828 3 : return NULL;
1829 3 : }
1830 :
1831 519 : if( FD_UNLIKELY( ele_max > MAP_(ele_max_max)() ) ) {
1832 0 : FD_LOG_WARNING(( "ele_max greater than ele_max_max" ));
1833 0 : return NULL;
1834 0 : }
1835 :
1836 519 : join->map = map;
1837 519 : join->ele = ele;
1838 519 : join->ele_max = ele_max;
1839 :
1840 519 : return join;
1841 519 : }
1842 :
1843 : MAP_STATIC void *
1844 165 : MAP_(leave)( MAP_(t) * join ) {
1845 :
1846 165 : if( FD_UNLIKELY( !join ) ) {
1847 3 : FD_LOG_WARNING(( "NULL join" ));
1848 3 : return NULL;
1849 3 : }
1850 :
1851 162 : return (void *)join;
1852 165 : }
1853 :
1854 : MAP_STATIC void *
1855 12 : MAP_(delete)( void * shmap ) {
1856 12 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmap;
1857 :
1858 12 : if( FD_UNLIKELY( !map ) ) {
1859 3 : FD_LOG_WARNING(( "NULL shmap" ));
1860 3 : return NULL;
1861 3 : }
1862 :
1863 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
1864 3 : FD_LOG_WARNING(( "misaligned shmap" ));
1865 3 : return NULL;
1866 3 : }
1867 :
1868 6 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
1869 3 : FD_LOG_WARNING(( "bad magic" ));
1870 3 : return NULL;
1871 3 : }
1872 :
1873 3 : FD_COMPILER_MFENCE();
1874 3 : map->magic = 0UL;
1875 3 : FD_COMPILER_MFENCE();
1876 :
1877 3 : return (void *)map;
1878 6 : }
1879 :
1880 : MAP_STATIC int
1881 : MAP_(insert)( MAP_(t) * join,
1882 : MAP_ELE_T * ele,
1883 9358809 : int flags ) {
1884 :
1885 : /* Determine the element index (fastest if ele are power-of-two) and
1886 : the chain that should hold ele */
1887 :
1888 9358809 : ulong ele_idx = (ulong)(ele - join->ele);
1889 9358809 : if( FD_UNLIKELY( ele_idx>=join->ele_max ) ) return FD_MAP_ERR_INVAL;
1890 :
1891 3729912 : MAP_(shmem_t) * map = join->map;
1892 :
1893 3729912 : ulong memo = MAP_(key_hash)( &ele->MAP_KEY, map->seed );
1894 3729912 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
1895 :
1896 : /* Insert element at the head of chain. If chain is already locked,
1897 : signal to try again later. */
1898 :
1899 3729912 : int err;
1900 :
1901 7459824 : MAP_CRIT( chain, flags & FD_MAP_FLAG_BLOCKING ) {
1902 3729912 : ulong version = MAP_(private_vcnt_ver)( ver_cnt );
1903 3729912 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
1904 :
1905 3729912 : ele->MAP_NEXT = chain->head_cidx;
1906 : # if MAP_MEMOIZE
1907 1874826 : ele->MAP_MEMO = memo;
1908 : # endif
1909 3729912 : chain->head_cidx = MAP_(private_cidx)( ele_idx );
1910 3729912 : ver_cnt = MAP_(private_vcnt)( version, ele_cnt+1UL ); /* version updated on exit */
1911 3729912 : err = FD_MAP_SUCCESS;
1912 :
1913 3729912 : } MAP_CRIT_BLOCKED {
1914 :
1915 0 : err = FD_MAP_ERR_AGAIN;
1916 :
1917 0 : } MAP_CRIT_END;
1918 :
1919 3729912 : return err;
1920 9358809 : }
1921 :
1922 : MAP_STATIC void
1923 : MAP_(hint)( MAP_(t) const * join,
1924 : MAP_KEY_T const * key,
1925 : MAP_(query_t) * query,
1926 8893983 : int flags ) {
1927 8893983 : MAP_(shmem_t) * map = join->map;
1928 8893983 : MAP_ELE_T * ele0 = join->ele;
1929 8893983 : ulong ele_max = join->ele_max;
1930 :
1931 8893983 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
1932 8893983 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
1933 :
1934 8893983 : if( FD_LIKELY( flags & FD_MAP_FLAG_PREFETCH_META ) ) FD_VOLATILE_CONST( chain->ver_cnt );
1935 8893983 : if( FD_LIKELY( flags & FD_MAP_FLAG_PREFETCH_DATA ) ) {
1936 4448334 : ulong ele_idx = MAP_(private_idx)( chain->head_cidx );
1937 4448334 : if( FD_LIKELY( ele_idx < ele_max ) ) FD_VOLATILE_CONST( ele0[ ele_idx ] );
1938 4448334 : }
1939 :
1940 8893983 : query->memo = memo;
1941 8893983 : }
1942 :
1943 : MAP_STATIC int
1944 : MAP_(remove)( MAP_(t) * join,
1945 : MAP_KEY_T const * key,
1946 : MAP_ELE_T const * sentinel,
1947 : MAP_(query_t) * query,
1948 5610051 : int flags ) {
1949 :
1950 : /* Determine the chain that should hold key */
1951 :
1952 5610051 : MAP_(shmem_t) * map = join->map;
1953 5610051 : MAP_ELE_T * ele = join->ele;
1954 5610051 : ulong ele_max = join->ele_max;
1955 :
1956 5610051 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
1957 5610051 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
1958 :
1959 : /* Find the key on the chain. If found, remove it. If not found,
1960 : corrupt or blocked, fail the operation. */
1961 :
1962 5610051 : query->memo = memo;
1963 5610051 : query->ele = (MAP_ELE_T *)sentinel;
1964 5610051 : query->chain = chain;
1965 :
1966 5610051 : int err;
1967 :
1968 11220102 : MAP_CRIT( chain, flags & FD_MAP_FLAG_BLOCKING ) {
1969 5610051 : ulong version = MAP_(private_vcnt_ver)( ver_cnt );
1970 5610051 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
1971 :
1972 5610051 : query->ver_cnt = ver_cnt;
1973 :
1974 5610051 : if( FD_UNLIKELY( ele_cnt>ele_max ) ) { /* optimize for not corrupt */
1975 : # if MAP_PEDANTIC
1976 0 : FD_LOG_NOTICE(( "Corrupt map chain %p (memo %016lx): ele_cnt=%lu > ele_max=%lu", (void *)chain, memo, ele_cnt, ele_max ));
1977 : # else
1978 0 : err = FD_MAP_ERR_CORRUPT;
1979 : goto done;
1980 : # endif /* MAP_PEDANTIC */
1981 0 : }
1982 :
1983 5610051 : MAP_IDX_T * cur = &chain->head_cidx;
1984 8553900 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) { /* guarantee bounded exec under corruption */
1985 6678624 : ulong ele_idx = MAP_(private_idx)( *cur );
1986 6678624 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* optimize for not corrupt */
1987 : # if MAP_PEDANTIC
1988 0 : FD_LOG_CRIT(( "Corrupt MAP_NEXT pointer at node %p (memo %016lx, ele_rem=%lu, ele_cnt=%lu): map_next=%lu >= ele_max=%lu",
1989 : (void *)cur, memo, ele_rem, ele_cnt, ele_idx, ele_max ));
1990 : # else
1991 0 : err = FD_MAP_ERR_CORRUPT;
1992 : goto done;
1993 : # endif /* MAP_PEDANTIC */
1994 0 : }
1995 :
1996 6678624 : if(
1997 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1998 3973413 : FD_LIKELY( ele[ ele_idx ].MAP_MEMO==memo ) &&
1999 3973413 : # endif
2000 4585869 : FD_LIKELY( MAP_(key_eq)( &ele[ ele_idx ].MAP_KEY, key ) ) ) { /* optimize for found */
2001 :
2002 3734775 : *cur = ele[ ele_idx ].MAP_NEXT;
2003 3734775 : ver_cnt = MAP_(private_vcnt)( version, ele_cnt-1UL ); /* version updated on exit */
2004 3734775 : query->ele = &ele[ ele_idx ];
2005 3734775 : err = FD_MAP_SUCCESS;
2006 3734775 : goto done;
2007 3734775 : }
2008 :
2009 2943849 : cur = &ele[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it on found */
2010 2943849 : }
2011 :
2012 : /* Key was not found */
2013 :
2014 1875276 : ulong ele_idx = MAP_(private_idx)( *cur );
2015 1875276 : if( FD_UNLIKELY( !MAP_(private_idx_is_null( ele_idx ) ) ) ) { /* optimize for not corrupt */
2016 : # if MAP_PEDANTIC
2017 0 : FD_LOG_CRIT(( "Corrupt map chain %p (memo %016lx, ele_cnt=%lu): Found element past chain: ele_idx=%lu",
2018 : (void *)chain, memo, ele_cnt, ele_idx ));
2019 : # else
2020 0 : err = FD_MAP_ERR_CORRUPT;
2021 : goto done;
2022 : # endif /* MAP_PEDANTIC */
2023 0 : }
2024 :
2025 1875276 : err = FD_MAP_ERR_KEY;
2026 :
2027 5610051 : done: /* silly language restriction */;
2028 :
2029 5610051 : } MAP_CRIT_BLOCKED {
2030 :
2031 0 : query->ver_cnt = ver_cnt;
2032 0 : err = FD_MAP_ERR_AGAIN;
2033 :
2034 0 : } MAP_CRIT_END;
2035 :
2036 5610051 : return err;
2037 5610051 : }
2038 :
2039 : MAP_STATIC int
2040 : MAP_(modify_try)( MAP_(t) * join,
2041 : MAP_KEY_T const * key,
2042 : MAP_ELE_T * sentinel,
2043 : MAP_(query_t) * query,
2044 3746028 : int flags ) {
2045 :
2046 : /* Determine which chain might hold key */
2047 :
2048 3746028 : MAP_(shmem_t) * map = join->map;
2049 3746028 : MAP_ELE_T * ele = join->ele;
2050 3746028 : ulong ele_max = join->ele_max;
2051 :
2052 3746028 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
2053 3746028 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
2054 :
2055 : /* Search for the key on chain. If found, retain the chain lock
2056 : and return the found element. If not found, corrupt or blocked,
2057 : fail. */
2058 :
2059 3746028 : query->memo = memo;
2060 3746028 : query->ele = (MAP_ELE_T *)sentinel;
2061 3746028 : query->chain = chain;
2062 :
2063 3746028 : int err;
2064 :
2065 7492056 : MAP_CRIT( chain, flags & FD_MAP_FLAG_BLOCKING ) {
2066 :
2067 3746028 : query->ver_cnt = ver_cnt;
2068 :
2069 3746028 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
2070 3746028 : if( FD_UNLIKELY( ele_cnt>ele_max ) ) { /* optimize for not corrupt */
2071 : # if MAP_PEDANTIC
2072 0 : FD_LOG_NOTICE(( "Corrupt map chain %p (memo %016lx): ele_cnt=%lu > ele_max=%lu", (void *)chain, memo, ele_cnt, ele_max ));
2073 : # else
2074 0 : err = FD_MAP_ERR_CORRUPT;
2075 : goto done;
2076 : # endif /* MAP_PEDANTIC */
2077 0 : }
2078 :
2079 3746028 : MAP_IDX_T * cur = &chain->head_cidx;
2080 5839254 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) { /* guarantee bounded exec under corruption */
2081 3966474 : ulong ele_idx = MAP_(private_idx)( *cur );
2082 3966474 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* optimize for not corrupt */
2083 : # if MAP_PEDANTIC
2084 0 : FD_LOG_CRIT(( "Corrupt MAP_NEXT pointer at node %p (memo %016lx, ele_rem=%lu, ele_cnt=%lu): map_next=%lu >= ele_max=%lu",
2085 : (void *)cur, memo, ele_rem, ele_cnt, ele_idx, ele_max ));
2086 : # else
2087 0 : err = FD_MAP_ERR_CORRUPT;
2088 : goto done;
2089 : # endif /* MAP_PEDANTIC */
2090 0 : }
2091 :
2092 3966474 : if(
2093 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2094 3966474 : FD_LIKELY( ele[ ele_idx ].MAP_MEMO==memo ) &&
2095 3966474 : # endif
2096 3966474 : FD_LIKELY( MAP_(key_eq)( &ele[ ele_idx ].MAP_KEY, key ) ) ) { /* optimize for found */
2097 1873248 : if( flags & FD_MAP_FLAG_ADAPTIVE ) {
2098 937638 : *cur = ele[ ele_idx ].MAP_NEXT;
2099 937638 : ele[ ele_idx ].MAP_NEXT = chain->head_cidx;
2100 937638 : chain->head_cidx = MAP_(private_cidx)( ele_idx );
2101 937638 : }
2102 1873248 : query->ele = &ele[ ele_idx ];
2103 1873248 : err = FD_MAP_SUCCESS;
2104 1873248 : retain_lock = 1;
2105 1873248 : goto done;
2106 1873248 : }
2107 :
2108 2093226 : cur = &ele[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it on found */
2109 2093226 : }
2110 :
2111 1872780 : ulong ele_idx = MAP_(private_idx)( *cur );
2112 1872780 : if( FD_UNLIKELY( !MAP_(private_idx_is_null( ele_idx ) ) ) ) { /* optimize for not corrupt */
2113 : # if MAP_PEDANTIC
2114 0 : FD_LOG_CRIT(( "Corrupt map chain %p (memo %016lx, ele_cnt=%lu): Found element past chain: ele_idx=%lu",
2115 : (void *)chain, memo, ele_cnt, ele_idx ));
2116 : # else
2117 0 : err = FD_MAP_ERR_CORRUPT;
2118 : goto done;
2119 : # endif /* MAP_PEDANTIC */
2120 0 : }
2121 :
2122 1872780 : err = FD_MAP_ERR_KEY;
2123 :
2124 3746028 : done: /* silly language restriction */;
2125 :
2126 3746028 : } MAP_CRIT_BLOCKED {
2127 :
2128 0 : query->ver_cnt = ver_cnt;
2129 0 : err = FD_MAP_ERR_AGAIN;
2130 :
2131 0 : } MAP_CRIT_END;
2132 :
2133 3746028 : return err;
2134 3746028 : }
2135 :
2136 : MAP_STATIC int
2137 : MAP_(query_try)( MAP_(t) const * join,
2138 : MAP_KEY_T const * key,
2139 : MAP_ELE_T const * sentinel,
2140 : MAP_(query_t) * query,
2141 6187842 : int flags ) {
2142 :
2143 : /* Determine which chain might hold key */
2144 :
2145 6187842 : MAP_(shmem_t) const * map = join->map;
2146 6187842 : MAP_ELE_T const * ele = join->ele;
2147 6187842 : ulong ele_max = join->ele_max;
2148 :
2149 6187842 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
2150 6187842 : MAP_(shmem_private_chain_t) const * chain = MAP_(shmem_private_chain_const)( map, memo );
2151 :
2152 : /* Determine the version of the chain we are querying. Then
2153 : speculatively read and validate the number of elements on the chain
2154 : at that version. If the chain is locked, tell the user to try
2155 : again later. If the number of elements in the chain is invalid,
2156 : tell user the map is corrupt. */
2157 :
2158 6187842 : ulong volatile const * _vc = &chain->ver_cnt;
2159 :
2160 6187842 : FD_COMPILER_MFENCE();
2161 6187842 : ulong then = *_vc;
2162 6187842 : FD_COMPILER_MFENCE();
2163 :
2164 6187842 : ulong ele_cnt = MAP_(private_vcnt_cnt)( then );
2165 :
2166 6187842 : FD_COMPILER_MFENCE();
2167 6187842 : ulong now = *_vc;
2168 6187842 : FD_COMPILER_MFENCE();
2169 :
2170 6187842 : query->memo = memo;
2171 6187842 : query->ele = (MAP_ELE_T *) sentinel;
2172 6187842 : query->chain = (MAP_(shmem_private_chain_t) *)chain;
2173 6187842 : query->ver_cnt = then;
2174 :
2175 6187842 : if( FD_UNLIKELY( (now!=then) | (!!(then & (1UL<<MAP_CNT_WIDTH))) ) ) return FD_MAP_ERR_AGAIN;
2176 6187842 : if( FD_UNLIKELY( ele_cnt>ele_max ) ) {
2177 : # if MAP_PEDANTIC
2178 0 : FD_LOG_NOTICE(( "Corrupt map chain %p (memo %016lx): ele_cnt=%lu > ele_max=%lu", (void *)chain, memo, ele_cnt, ele_max ));
2179 : # else
2180 0 : return FD_MAP_ERR_CORRUPT;
2181 : # endif /* MAP_PEDANTIC */
2182 0 : }
2183 :
2184 : /* Search the chain for key. Since we know the numer of elements on
2185 : the chain, we can bound this search to avoid corruption causing out
2186 : of bound reads, infinite loops and such. */
2187 :
2188 6187842 : MAP_IDX_T const * cur = &chain->head_cidx;
2189 8880591 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) {
2190 :
2191 : /* Speculatively read the index of the chain, speculate if a valid
2192 : index and, if so, speculate if the chain element matches the
2193 : query. Note that this assumes element keys have a lifetime of at
2194 : least that of the element. A sufficient (but not a necessary,
2195 : see rant) condition for this is that key is a plain-old-data
2196 : fields in the element. */
2197 :
2198 6434145 : FD_COMPILER_MFENCE();
2199 6434145 : ulong ele_idx = MAP_(private_idx)( *cur );
2200 6434145 : FD_COMPILER_MFENCE();
2201 :
2202 6434145 : int corrupt = (ele_idx>=ele_max);
2203 6434145 : int found = ( FD_LIKELY( !corrupt ) &&
2204 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2205 3966459 : FD_LIKELY( ele[ ele_idx ].MAP_MEMO==memo ) &&
2206 : # endif
2207 6434145 : FD_LIKELY( MAP_(key_eq)( &ele[ ele_idx ].MAP_KEY, key ) ) ) ? 1 : 0;
2208 :
2209 : /* Validate the speculation. If validation fails (e.g. the chain
2210 : was modified behind our back), tell the user to try again later.
2211 : If the element index was not valid, tell the user the map has
2212 : been corrupted. If key was found at element, tell the user they
2213 : can speculate element ele_idx contains key. */
2214 :
2215 6434145 : FD_COMPILER_MFENCE();
2216 6434145 : now = *_vc;
2217 6434145 : FD_COMPILER_MFENCE();
2218 :
2219 6434145 : if( FD_UNLIKELY( now!=then ) ) return FD_MAP_ERR_AGAIN;
2220 6434145 : if( FD_UNLIKELY( corrupt ) ) {
2221 : # if MAP_PEDANTIC
2222 0 : FD_LOG_CRIT(( "Corrupt MAP_NEXT pointer at node %p (memo %016lx, ele_rem=%lu, ele_cnt=%lu): map_next=%lu >= ele_max=%lu",
2223 : (void *)cur, memo, ele_rem, ele_cnt, ele_idx, ele_max ));
2224 : # else
2225 0 : return FD_MAP_ERR_CORRUPT;
2226 : # endif /* MAP_PEDANTIC */
2227 0 : }
2228 :
2229 6434145 : if( FD_LIKELY( found ) ) { /* Optimize for found */
2230 3741396 : query->ele = (MAP_ELE_T *)&ele[ ele_idx ];
2231 3741396 : return FD_MAP_SUCCESS;
2232 3741396 : }
2233 :
2234 : /* The chain element didn't hold the key ... move to next element */
2235 :
2236 2692749 : cur = &ele[ ele_idx ].MAP_NEXT;
2237 2692749 : }
2238 :
2239 : /* At this point, the chain didn't hold the key. We could probably
2240 : return immediately but we speculative read the tail pointer,
2241 : validate it as an additional integrity check. If these checks
2242 : pass, we are confident the whole chain looked valid and did not
2243 : hold key between now and then. */
2244 :
2245 2446446 : ulong ele_idx = MAP_(private_idx)( *cur );
2246 :
2247 2446446 : FD_COMPILER_MFENCE();
2248 2446446 : now = *_vc;
2249 2446446 : FD_COMPILER_MFENCE();
2250 :
2251 2446446 : if( FD_UNLIKELY( now!=then ) ) return FD_MAP_ERR_AGAIN;
2252 2446446 : if( FD_UNLIKELY( !MAP_(private_idx_is_null( ele_idx ) ) ) ) {
2253 : # if MAP_PEDANTIC
2254 0 : FD_LOG_CRIT(( "Corrupt map chain %p (memo %016lx, ele_cnt=%lu): Found element past chain: ele_idx=%lu",
2255 : (void *)chain, memo, ele_cnt, ele_idx ));
2256 : # else
2257 0 : return FD_MAP_ERR_CORRUPT;
2258 : # endif /* MAP_PEDANTIC */
2259 0 : }
2260 :
2261 2446446 : return FD_MAP_ERR_KEY;
2262 2446446 : }
2263 :
2264 : /* Note: txn_add is currently optimized for reasonably small number
2265 : of keys per transaction. For a huge number of transaction keys (e.g.
2266 : an iterator over all keys for all keys), probably should use the
2267 : iterator API. For a moderate number of transaction keys, probably
2268 : should consider data structures where set insert/remove/test are
2269 : sublinear time. Similarly, if MAP_KEY_HASH is costly, might be
2270 : useful to stash the key hashes in the transaction, memoize it in the
2271 : elements, etc. */
2272 :
2273 : MAP_STATIC int
2274 : MAP_(txn_add)( MAP_(txn_t) * txn,
2275 : MAP_KEY_T const * key,
2276 8417175 : int lock ) {
2277 :
2278 : /* Unpack txn fields */
2279 :
2280 8417175 : MAP_(shmem_t) * map = txn->map;
2281 8417175 : ulong info_max = txn->info_max;
2282 8417175 : ulong lock_cnt = txn->lock_cnt;
2283 8417175 : ulong spec_cnt = txn->spec_cnt;
2284 :
2285 8417175 : MAP_(txn_private_info_t) * lock_info = MAP_(txn_private_info)( txn );
2286 8417175 : MAP_(txn_private_info_t) * spec_info = lock_info + (info_max - spec_cnt);
2287 :
2288 : /* Determine which chain manages this key */
2289 :
2290 8417175 : ulong memo = MAP_(key_hash)( key, map->seed );
2291 8417175 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
2292 :
2293 : /* If this chain already needs to be locked for this transaction,
2294 : nothing to do. */
2295 :
2296 18080526 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ )
2297 9719457 : if( FD_UNLIKELY( chain==lock_info[ lock_idx ].chain ) ) return FD_MAP_SUCCESS;
2298 :
2299 8361069 : if( FD_UNLIKELY( !lock ) ) { /* optimize for locked key, possible compile time */
2300 :
2301 : /* At this point, key is used speculatively by the transaction and
2302 : its managing chain isn't in the locked set. If this chain is
2303 : already in the speculative set, nothing to do. */
2304 :
2305 3343212 : for( ulong spec_idx=0UL; spec_idx<spec_cnt; spec_idx++ )
2306 795423 : if( FD_UNLIKELY( chain==spec_info[ spec_idx ].chain ) ) return FD_MAP_SUCCESS;
2307 :
2308 : /* Add the chain to the speculative set. If we don't have any room,
2309 : fail. */
2310 :
2311 2547789 : ulong free_cnt = info_max - lock_cnt - spec_cnt;
2312 2547789 : if( FD_UNLIKELY( !free_cnt ) ) return FD_MAP_ERR_INVAL; /* Impossible if less than key_max keys added */
2313 1611543 : spec_info[-1].chain = chain;
2314 1611543 : txn->spec_cnt = spec_cnt + 1UL;
2315 :
2316 5805903 : } else {
2317 :
2318 : /* At this point, key is used locked by the transaction and its
2319 : managing chain isn't in the locked set. If this chain is
2320 : currently in the speculative set, move it to the locked
2321 : set. */
2322 :
2323 8178213 : for( ulong spec_idx=0UL; spec_idx<spec_cnt; spec_idx++ )
2324 2388156 : if( FD_UNLIKELY( chain==spec_info[ spec_idx ].chain ) ) {
2325 15846 : spec_info[ spec_idx ].chain = spec_info[ 0 ].chain; /* Fill the hole at spec_idx, making a hole at 0 */
2326 15846 : lock_info[ lock_cnt ].chain = chain; /* Either uses unused entry or fills hole at 0 */
2327 15846 : txn->spec_cnt = spec_cnt - 1UL;
2328 15846 : txn->lock_cnt = lock_cnt + 1UL;
2329 15846 : return FD_MAP_SUCCESS;
2330 15846 : }
2331 :
2332 : /* Add the chain to the locked set. If we don't have any room,
2333 : fail. */
2334 :
2335 5790057 : ulong free_cnt = info_max - lock_cnt - spec_cnt;
2336 5790057 : if( FD_UNLIKELY( !free_cnt ) ) return FD_MAP_ERR_INVAL; /* Impossible if less than key_max keys added */
2337 4854066 : lock_info[lock_cnt].chain = chain;
2338 4854066 : txn->lock_cnt = lock_cnt + 1UL;
2339 :
2340 4854066 : }
2341 :
2342 6465609 : return FD_MAP_SUCCESS;
2343 8361069 : }
2344 :
2345 : MAP_STATIC int
2346 : MAP_(txn_try)( MAP_(txn_t) * txn,
2347 1870374 : int flags ) {
2348 1870374 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
2349 :
2350 : /* Unpack txn fields */
2351 :
2352 1870374 : ulong info_max = txn->info_max;
2353 1870374 : ulong lock_cnt = txn->lock_cnt;
2354 1870374 : ulong spec_cnt = txn->spec_cnt;
2355 :
2356 1870374 : MAP_(txn_private_info_t) * lock_info = MAP_(txn_private_info)( txn );
2357 1870374 : MAP_(txn_private_info_t) * spec_info = lock_info + info_max - spec_cnt;
2358 :
2359 1870374 : ulong backoff_exp = (1UL<<32); /* See iter_lock for details */
2360 1870374 : ulong backoff_seed = ((ulong)(uint)flags)>>2;
2361 :
2362 1870374 : int err;
2363 :
2364 1870374 : for(;; ) {
2365 :
2366 1870374 : err = FD_MAP_SUCCESS;
2367 :
2368 1870374 : FD_COMPILER_MFENCE();
2369 :
2370 : /* Get the chain versions for all keys in the speculative set.
2371 : If any are locked, set AGAIN if any are locked. */
2372 :
2373 3466071 : for( ulong spec_idx=0UL; spec_idx<spec_cnt; spec_idx++ ) {
2374 1595697 : ulong ver_cnt = spec_info[ spec_idx ].chain->ver_cnt;
2375 1595697 : if( FD_UNLIKELY( ver_cnt & (1UL<<MAP_CNT_WIDTH) ) ) { /* Already locked */
2376 0 : err = FD_MAP_ERR_AGAIN;
2377 0 : break;
2378 0 : }
2379 1595697 : spec_info[ spec_idx ].ver_cnt = ver_cnt;
2380 1595697 : }
2381 :
2382 1870374 : if( FD_LIKELY( !err ) ) {
2383 :
2384 : /* At this point, all the chains we are speculating on were
2385 : unlocked and we have recorded their versions. Try to lock
2386 : all the chains for the locked key. */
2387 : /* FIXME: consider reordering like iter_lock? */
2388 :
2389 6740286 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) {
2390 :
2391 9739824 : MAP_CRIT( lock_info[ lock_idx ].chain, 0 ) { /* non-blocking */
2392 :
2393 : /* Got the lock ... save the version and retain the lock for
2394 : test. */
2395 :
2396 4869912 : lock_info[ lock_idx ].ver_cnt = ver_cnt;
2397 4869912 : retain_lock = 1;
2398 :
2399 4869912 : } MAP_CRIT_BLOCKED {
2400 :
2401 : /* We hit contention for this lock. Unlock the chains that
2402 : we already locked to prevent possible deadlock (see
2403 : iter_lock) */
2404 :
2405 0 : for( ulong unlock_idx=0UL; unlock_idx<lock_idx; unlock_idx++ )
2406 0 : lock_info[ unlock_idx ].chain->ver_cnt = lock_info[ unlock_idx ].ver_cnt + (2UL<<MAP_CNT_WIDTH);
2407 :
2408 0 : err = FD_MAP_ERR_AGAIN;
2409 :
2410 0 : } MAP_CRIT_END;
2411 :
2412 4869912 : if( FD_UNLIKELY( err ) ) break;
2413 :
2414 4869912 : }
2415 :
2416 1870374 : }
2417 :
2418 1870374 : FD_COMPILER_MFENCE();
2419 :
2420 1870374 : if( FD_LIKELY( (!err) | non_blocking ) ) break;
2421 :
2422 : /* At this point, we hit contention and are blocking (need to try
2423 : again). Do a random backoff (see iter_lock for details). */
2424 :
2425 0 : ulong scale = fd_ulong_min( (fd_ulong_min( lock_cnt+spec_cnt, (1UL<<16)-1UL )*backoff_exp) >> 16, (1UL<<32)-1UL );
2426 0 : backoff_exp = fd_ulong_min( backoff_exp + (backoff_exp>>2) + (backoff_exp>>4), (1UL<<48)-1UL );
2427 0 : MAP_(backoff)( scale, backoff_seed );
2428 0 : }
2429 :
2430 : /* At this point, if we don't have an error, we have the chain
2431 : versions for txn keys used speculatively and they were unlocked and
2432 : we have locks on the chains for txn keys used locked. Otherwise,
2433 : this is a non-blocking call and we return AGAIN. */
2434 :
2435 1870374 : return err;
2436 1870374 : }
2437 :
2438 : MAP_STATIC int
2439 1870374 : MAP_(txn_test)( MAP_(txn_t) * txn ) {
2440 :
2441 : /* Unpack txn fields */
2442 :
2443 1870374 : ulong info_max = txn->info_max;
2444 1870374 : ulong lock_cnt = txn->lock_cnt;
2445 1870374 : ulong spec_cnt = txn->spec_cnt;
2446 :
2447 1870374 : MAP_(txn_private_info_t) * lock_info = MAP_(txn_private_info)( txn );
2448 1870374 : MAP_(txn_private_info_t) * spec_info = lock_info + info_max - spec_cnt;
2449 :
2450 : /* Unlock all chains locked for this transaction. Then test if any
2451 : keys used speculatively could have changed in locking / trying /
2452 : unlocking. If so, tell user to retry later. */
2453 :
2454 1870374 : int err = FD_MAP_SUCCESS;
2455 :
2456 1870374 : FD_COMPILER_MFENCE();
2457 :
2458 6740286 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) lock_info[ lock_idx ].chain->ver_cnt += (1UL<<MAP_CNT_WIDTH);
2459 :
2460 3466071 : for( ulong spec_idx=0UL; spec_idx<spec_cnt; spec_idx++ ) {
2461 1595697 : MAP_(shmem_private_chain_t) const * chain = spec_info[ spec_idx ].chain;
2462 1595697 : ulong ver_cnt = spec_info[ spec_idx ].ver_cnt;
2463 1595697 : if( FD_UNLIKELY( chain->ver_cnt!=ver_cnt ) ) {
2464 0 : err = FD_MAP_ERR_AGAIN;
2465 0 : break;
2466 0 : }
2467 1595697 : }
2468 :
2469 1870374 : FD_COMPILER_MFENCE();
2470 :
2471 1870374 : return err;
2472 1870374 : }
2473 :
2474 : MAP_STATIC int
2475 : MAP_(txn_insert)( MAP_(t) * join,
2476 6540909 : MAP_ELE_T * ele ) {
2477 :
2478 : /* Determine the element index (fastest if ele are power-of-two) and
2479 : the chain that should hold ele */
2480 :
2481 6540909 : MAP_(shmem_t) * map = join->map;
2482 6540909 : ulong ele_max = join->ele_max;
2483 :
2484 6540909 : ulong ele_idx = (ulong)(ele - join->ele);
2485 6540909 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) return FD_MAP_ERR_INVAL;
2486 :
2487 1635288 : ulong memo = MAP_(key_hash)( &ele->MAP_KEY, map->seed );
2488 1635288 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
2489 :
2490 : /* Insert ele_idx at head of chain. */
2491 :
2492 1635288 : ulong ver_cnt = chain->ver_cnt;
2493 1635288 : ulong version = MAP_(private_vcnt_ver)( ver_cnt );
2494 1635288 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
2495 :
2496 1635288 : ele->MAP_NEXT = chain->head_cidx;
2497 : # if MAP_MEMOIZE
2498 1635207 : ele->MAP_MEMO = memo;
2499 : # endif
2500 1635288 : chain->head_cidx = MAP_(private_cidx)( ele_idx );
2501 1635288 : chain->ver_cnt = MAP_(private_vcnt)( version, ele_cnt+1UL );
2502 :
2503 1635288 : return FD_MAP_SUCCESS;
2504 6540909 : }
2505 :
2506 : MAP_STATIC int
2507 : MAP_(txn_remove)( MAP_(t) * join,
2508 : MAP_KEY_T const * key,
2509 : MAP_ELE_T const * sentinel,
2510 : MAP_(query_t) * query,
2511 1635840 : int flags ) {
2512 :
2513 : /* Determine the chain that should hold key */
2514 :
2515 1635840 : MAP_(shmem_t) * map = join->map;
2516 1635840 : MAP_ELE_T * ele = join->ele;
2517 1635840 : ulong ele_max = join->ele_max;
2518 :
2519 1635840 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
2520 1635840 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
2521 :
2522 : /* Find the key on the chain and remove it */
2523 :
2524 1635840 : ulong ver_cnt = chain->ver_cnt;
2525 1635840 : ulong version = MAP_(private_vcnt_ver)( ver_cnt );
2526 1635840 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
2527 :
2528 1635840 : query->memo = memo;
2529 1635840 : query->ele = (MAP_ELE_T *)sentinel;
2530 1635840 : query->chain = chain;
2531 1635840 : query->ver_cnt = ver_cnt;
2532 :
2533 1635840 : if( FD_UNLIKELY( ele_cnt>ele_max ) ) { /* optimize for not corrupt */
2534 : # if MAP_PEDANTIC
2535 0 : FD_LOG_NOTICE(( "Corrupt map chain %p (memo %016lx): ele_cnt=%lu > ele_max=%lu", (void *)chain, memo, ele_cnt, ele_max ));
2536 : # else
2537 0 : return FD_MAP_ERR_CORRUPT;
2538 : # endif /* MAP_PEDANTIC */
2539 0 : }
2540 :
2541 1635840 : MAP_IDX_T * cur = &chain->head_cidx;
2542 2244978 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) { /* guarantee bounded exec under corruption */
2543 2238564 : ulong ele_idx = MAP_(private_idx)( *cur );
2544 2238564 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* optimize for not corrupt */
2545 : # if MAP_PEDANTIC
2546 0 : FD_LOG_CRIT(( "Corrupt MAP_NEXT pointer at node %p (memo %016lx, ele_rem=%lu, ele_cnt=%lu): map_next=%lu >= ele_max=%lu",
2547 : (void *)cur, memo, ele_rem, ele_cnt, ele_idx, ele_max ));
2548 : # else
2549 0 : return FD_MAP_ERR_CORRUPT;
2550 : # endif /* MAP_PEDANTIC */
2551 0 : }
2552 :
2553 2238564 : if(
2554 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2555 2238495 : FD_LIKELY( ele[ ele_idx ].MAP_MEMO==memo ) &&
2556 2238495 : # endif
2557 2238495 : FD_LIKELY( MAP_(key_eq)( &ele[ ele_idx ].MAP_KEY, key ) ) ) { /* optimize for found */
2558 1629426 : *cur = ele[ ele_idx ].MAP_NEXT;
2559 1629426 : chain->ver_cnt = MAP_(private_vcnt)( version, ele_cnt-1UL );
2560 1629426 : query->ele = &ele[ ele_idx ];
2561 1629426 : return FD_MAP_SUCCESS;
2562 1629426 : }
2563 :
2564 609138 : cur = &ele[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it on found */
2565 609138 : }
2566 :
2567 6414 : ulong ele_idx = MAP_(private_idx)( *cur );
2568 6414 : if( FD_UNLIKELY( !MAP_(private_idx_is_null( ele_idx ) ) ) ) { /* optimize for not found */
2569 : # if MAP_PEDANTIC
2570 0 : FD_LOG_CRIT(( "Corrupt map chain %p (memo %016lx, ele_cnt=%lu): Found element past chain: ele_idx=%lu",
2571 : (void *)chain, memo, ele_cnt, ele_idx ));
2572 : # else
2573 0 : return FD_MAP_ERR_CORRUPT;
2574 : # endif /* MAP_PEDANTIC */
2575 0 : }
2576 6414 : return FD_MAP_ERR_KEY;
2577 6414 : }
2578 :
2579 : MAP_STATIC int
2580 : MAP_(txn_modify)( MAP_(t) * join,
2581 : MAP_KEY_T const * key,
2582 : MAP_ELE_T * sentinel,
2583 : MAP_(query_t) * query,
2584 3273936 : int flags ) {
2585 :
2586 : /* Determine which chain might hold key */
2587 :
2588 3273936 : MAP_(shmem_t) * map = join->map;
2589 3273936 : MAP_ELE_T * ele = join->ele;
2590 3273936 : ulong ele_max = join->ele_max;
2591 :
2592 3273936 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, map->seed );
2593 3273936 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, memo );
2594 :
2595 : /* Search the chain for key */
2596 :
2597 3273936 : ulong ver_cnt = chain->ver_cnt;
2598 3273936 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
2599 :
2600 3273936 : query->memo = memo;
2601 3273936 : query->ele = sentinel;
2602 3273936 : query->chain = chain;
2603 3273936 : query->ver_cnt = ver_cnt;
2604 :
2605 3273936 : if( FD_UNLIKELY( ele_cnt>ele_max ) ) { /* optimize for not corrupt */
2606 : # if MAP_PEDANTIC
2607 0 : FD_LOG_NOTICE(( "Corrupt map chain %p (memo %016lx): ele_cnt=%lu > ele_max=%lu", (void *)chain, memo, ele_cnt, ele_max ));
2608 : # else
2609 0 : return FD_MAP_ERR_CORRUPT;
2610 : # endif /* MAP_PEDANTIC */
2611 0 : }
2612 :
2613 3273936 : MAP_IDX_T * cur = &chain->head_cidx;
2614 4500864 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) {
2615 4487781 : ulong ele_idx = MAP_(private_idx)( *cur );
2616 :
2617 4487781 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* optimize for not corrupt */
2618 : # if MAP_PEDANTIC
2619 0 : FD_LOG_CRIT(( "Corrupt MAP_NEXT pointer at node %p (memo %016lx, ele_rem=%lu, ele_cnt=%lu): map_next=%lu >= ele_max=%lu",
2620 : (void *)cur, memo, ele_rem, ele_cnt, ele_idx, ele_max ));
2621 : # else
2622 0 : return FD_MAP_ERR_CORRUPT;
2623 : # endif /* MAP_PEDANTIC */
2624 0 : }
2625 :
2626 4487781 : if(
2627 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2628 4487718 : FD_LIKELY( ele[ ele_idx ].MAP_MEMO==memo ) &&
2629 4487718 : # endif
2630 4487718 : FD_LIKELY( MAP_(key_eq)( &ele[ ele_idx ].MAP_KEY, key ) ) ) { /* optimize for found */
2631 3260853 : if( flags & FD_MAP_FLAG_ADAPTIVE ) {
2632 816405 : *cur = ele[ ele_idx ].MAP_NEXT;
2633 816405 : ele[ ele_idx ].MAP_NEXT = chain->head_cidx;
2634 816405 : chain->head_cidx = MAP_(private_cidx)( ele_idx );
2635 816405 : }
2636 3260853 : query->ele = &ele[ ele_idx ];
2637 3260853 : return FD_MAP_SUCCESS;
2638 3260853 : }
2639 :
2640 1226928 : cur = &ele[ ele_idx ].MAP_NEXT;
2641 1226928 : }
2642 :
2643 13083 : ulong ele_idx = MAP_(private_idx)( *cur );
2644 13083 : if( FD_UNLIKELY( !MAP_(private_idx_is_null( ele_idx ) ) ) ) { /* optimize for not corrupt */
2645 : # if MAP_PEDANTIC
2646 0 : FD_LOG_CRIT(( "Corrupt map chain %p (memo %016lx, ele_cnt=%lu): Found element past chain: ele_idx=%lu",
2647 : (void *)chain, memo, ele_cnt, ele_idx ));
2648 : # else
2649 0 : return FD_MAP_ERR_CORRUPT;
2650 : # endif /* MAP_PEDANTIC */
2651 0 : }
2652 :
2653 13083 : return FD_MAP_ERR_KEY;
2654 13083 : }
2655 :
2656 : MAP_STATIC int
2657 : MAP_(iter_lock)( MAP_(t) * join,
2658 : ulong * lock_seq,
2659 : ulong lock_cnt,
2660 1877061 : int flags ) {
2661 1877061 : if( FD_UNLIKELY( !lock_cnt ) ) return FD_MAP_SUCCESS; /* nothing to do */
2662 1877052 : if( FD_UNLIKELY( (!join) | (!lock_seq) ) ) return FD_MAP_ERR_INVAL;
2663 :
2664 1877046 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
2665 :
2666 1877046 : MAP_(shmem_t) * map = join->map;
2667 :
2668 1877046 : ulong chain_cnt = map->chain_cnt;
2669 1877046 : if( FD_UNLIKELY( lock_cnt>chain_cnt ) ) return FD_MAP_ERR_INVAL;
2670 :
2671 1877043 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( join->map, 0UL );
2672 :
2673 1877043 : int err;
2674 :
2675 1877043 : ulong backoff = 1UL<<32; /* in [1,2^16)*2^32 */
2676 1877043 : ulong backoff_seed = ((ulong)(uint)flags)>>2; /* 0 usually fine */
2677 1877043 : ulong lock_idx = 0UL;
2678 1877043 : ulong locked_cnt = 0UL;
2679 3755235 : for(;;) {
2680 :
2681 3755235 : err = FD_MAP_SUCCESS;
2682 :
2683 : /* At this point, we've acquired locks [0,locked_cnt), we need to
2684 : acquire locks [locked_cnt,lock_cnt), [locked_cnt,lock_cnt) is non
2685 : empty and i is in [locked_cnt,lock_cnt). Try to acquire lock
2686 : lock_idx this iteration. */
2687 :
2688 3755235 : ulong chain_idx = lock_seq[ lock_idx ];
2689 :
2690 3755235 : if( FD_UNLIKELY( chain_idx>=chain_cnt ) ) { /* optimize for valid lock_seq */
2691 0 : for( ulong unlock_idx=0UL; unlock_idx<locked_cnt; unlock_idx++ )
2692 0 : chain[ lock_seq[ unlock_idx ] ].ver_cnt += (1UL<<MAP_CNT_WIDTH);
2693 0 : locked_cnt = 0UL;
2694 0 : err = FD_MAP_ERR_AGAIN;
2695 0 : break;
2696 0 : }
2697 :
2698 7510470 : MAP_CRIT( chain + chain_idx, 0 ) {
2699 :
2700 : /* At this point, we got the lock. Swap lock at locked_cnt and
2701 : lock_idx and increment locked_cnt to move lock_idx to the
2702 : locked set as the most recently acquired lock. Since we
2703 : increment lock_idx below, when locked_cnt<lock_idx (i.e. we had
2704 : contention for lock locked_cnt recently), this will move the
2705 : next attempt to lock locked_cnt as far as possible from now of
2706 : the remaining locks to acquire. When locked_cnt==lock_idx,
2707 : this is a branchless no-op (and the increment of lock_idx below
2708 : will guarantee lock_idx will be at least locked_cnt next
2709 : iteration, preserving the invariant that lock_idx is in
2710 : [locked_cnt,lock_cnt) on the next iteration if there is one. */
2711 :
2712 3755235 : ulong chain_idx_tmp = lock_seq[ locked_cnt ];
2713 3755235 : lock_seq[ lock_idx ] = chain_idx_tmp;
2714 3755235 : lock_seq[ locked_cnt ] = chain_idx;
2715 3755235 : locked_cnt++;
2716 :
2717 3755235 : retain_lock = 1;
2718 :
2719 3755235 : } MAP_CRIT_BLOCKED {
2720 :
2721 : /* We failed to get lock lock_idx. To avoid deadlock with the
2722 : thread that has this lock and is trying to get a lock we
2723 : already have, we unlock the chains we've already locked (note
2724 : that we need to unlock here in non-blocking operation too).
2725 : Quick experiments in extreme contention scenarios found more
2726 : incremental approaches in blocking operation could take an
2727 : excessively long time to resolve so we bulk unlock. */
2728 :
2729 0 : for( ulong unlock_idx=0UL; unlock_idx<locked_cnt; unlock_idx++ )
2730 0 : chain[ lock_seq[ unlock_idx ] ].ver_cnt += (1UL<<MAP_CNT_WIDTH);
2731 0 : locked_cnt = 0UL;
2732 :
2733 0 : err = FD_MAP_ERR_AGAIN;
2734 :
2735 0 : } MAP_CRIT_END;
2736 :
2737 3755235 : if( FD_UNLIKELY( (locked_cnt==lock_cnt ) | /* all locks acquired */
2738 3755235 : ((!!err) & non_blocking) ) ) break; /* or hit contention and are non-blocking */
2739 :
2740 : /* Move to the next lock. Everytime we wrap around, we hit
2741 : contention since the last wrap / iter start. We do a random
2742 : exponential backoff with saturation on wrapping to minimize
2743 : contention with other threads hitting these locks. Normalizing
2744 : out fixed point scalings baked into the below, we spin pause a
2745 : uniform IID random number of times in [0,unlocked_cnt*backoff]
2746 : where backoff is 1 on the first wrap and increases by ~30% each
2747 : time to a maximum of 2^16 (i.e. hundreds microseconds per
2748 : remaining lock for typical CPU speeds and spin pause delays at
2749 : maximum backoff). */
2750 :
2751 1878192 : lock_idx++;
2752 1878192 : if( FD_UNLIKELY( lock_idx==lock_cnt ) ) { /* optimize for lots of locks */
2753 0 : lock_idx = locked_cnt;
2754 0 : ulong scale = fd_ulong_min( (fd_ulong_min( lock_cnt-locked_cnt, (1UL<<16)-1UL )*backoff) >> 16, (1UL<<32)-1UL );
2755 0 : backoff = fd_ulong_min( backoff + (backoff>>2) + (backoff>>4), (1UL<<48)-1UL );
2756 0 : MAP_(backoff)( scale, backoff_seed );
2757 0 : }
2758 1878192 : }
2759 :
2760 1877043 : return err;
2761 1877046 : }
2762 :
2763 : MAP_STATIC void
2764 : MAP_(iter_unlock)( MAP_(t) * join,
2765 : ulong const * lock_seq,
2766 3755235 : ulong lock_cnt ) {
2767 3755235 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( join->map, 0UL );
2768 :
2769 3755235 : FD_COMPILER_MFENCE();
2770 7510470 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ )
2771 3755235 : chain[ lock_seq[ lock_idx ] ].ver_cnt += (1UL<<MAP_CNT_WIDTH);
2772 3755235 : FD_COMPILER_MFENCE();
2773 3755235 : }
2774 :
2775 : MAP_STATIC void
2776 3 : MAP_(reset)( MAP_(t) * join ) {
2777 3 : MAP_(shmem_t) * map = join->map;
2778 :
2779 3 : ulong chain_cnt = map->chain_cnt;
2780 3 : MAP_(shmem_private_chain_t) * chain = MAP_(shmem_private_chain)( map, 0UL );
2781 :
2782 1539 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
2783 1536 : ulong ver_cnt = chain[ chain_idx ].ver_cnt;
2784 1536 : ulong version = MAP_(private_vcnt_ver)( ver_cnt );
2785 1536 : chain[ chain_idx ].ver_cnt = MAP_(private_vcnt)( version+2UL, 0UL );
2786 1536 : chain[ chain_idx ].head_cidx = MAP_(private_cidx)( MAP_(private_idx_null)() );
2787 1536 : }
2788 3 : }
2789 :
2790 : MAP_STATIC int
2791 480 : MAP_(verify)( MAP_(t) const * join ) {
2792 :
2793 1721286 : # define MAP_TEST(c) do { \
2794 1721286 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_MAP_ERR_INVAL; } \
2795 1721286 : } while(0)
2796 :
2797 : /* Validate join */
2798 :
2799 480 : MAP_TEST( join );
2800 480 : MAP_TEST( fd_ulong_is_aligned( (ulong)join, alignof(MAP_(t)) ) );
2801 :
2802 480 : MAP_(shmem_t) const * map = join->map;
2803 480 : MAP_ELE_T const * ele = join->ele;
2804 480 : ulong ele_max = join->ele_max;
2805 :
2806 480 : MAP_TEST( map );
2807 480 : MAP_TEST( fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) );
2808 :
2809 480 : MAP_TEST( (!!ele) | (!ele_max) );
2810 480 : MAP_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(MAP_ELE_T) ) );
2811 :
2812 480 : MAP_TEST( ele_max<=MAP_(ele_max_max)() );
2813 :
2814 : /* Validate map metadata */
2815 :
2816 480 : ulong magic = map->magic;
2817 480 : ulong seed = map->seed;
2818 480 : ulong chain_cnt = map->chain_cnt;
2819 :
2820 480 : MAP_TEST( magic==MAP_MAGIC );
2821 : /* seed is arbitrary */
2822 480 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
2823 480 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
2824 :
2825 480 : MAP_(shmem_private_chain_t) const * chain = MAP_(shmem_private_chain_const)( map, 0UL );
2826 :
2827 : /* Validate the map chains */
2828 :
2829 480 : ulong unmapped_ele_cnt = ele_max;
2830 843504 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
2831 :
2832 : /* Validate the chain length */
2833 :
2834 843024 : ulong ver_cnt = chain[ chain_idx ].ver_cnt;
2835 :
2836 843024 : ulong ele_cnt = MAP_(private_vcnt_cnt)( ver_cnt );
2837 843024 : MAP_TEST( ele_cnt<=unmapped_ele_cnt );
2838 843024 : unmapped_ele_cnt -= ele_cnt;
2839 :
2840 : /* Validate chain linkage, element membership and element uniqueness */
2841 :
2842 843024 : ulong head_idx = MAP_(private_idx)( chain[ chain_idx ].head_cidx );
2843 843024 : ulong cur_idx = head_idx;
2844 856926 : for( ulong ele_rem=ele_cnt; ele_rem; ele_rem-- ) {
2845 13902 : MAP_TEST( cur_idx<ele_max ); /* In element store */
2846 :
2847 13902 : MAP_KEY_T const * key = &ele[ cur_idx ].MAP_KEY;
2848 :
2849 13902 : ulong memo = MAP_(key_hash)( key, seed );
2850 13902 : ulong ele_chain_idx = memo & (chain_cnt-1UL);
2851 13902 : MAP_TEST( ele_chain_idx==chain_idx ); /* On correct chain */
2852 : # if MAP_MEMOIZE
2853 0 : MAP_TEST( ele[ cur_idx ].MAP_MEMO==memo );
2854 0 : # endif
2855 :
2856 : /* Note that we've already validated linkage from head_idx to
2857 : cur_idx so pointer chasing here is safe. */
2858 :
2859 13902 : ulong prv_idx = head_idx;
2860 16536 : while( prv_idx!=cur_idx ) {
2861 2634 : MAP_TEST( !MAP_(key_eq)( &ele[ prv_idx ].MAP_KEY, key ) ); /* Unique */
2862 2634 : prv_idx = MAP_(private_idx)( ele[ prv_idx ].MAP_NEXT );
2863 2634 : }
2864 :
2865 13902 : cur_idx = MAP_(private_idx)( ele[ cur_idx ].MAP_NEXT );
2866 13902 : }
2867 :
2868 843024 : MAP_TEST( MAP_(private_idx_is_null)( cur_idx ) );
2869 843024 : }
2870 :
2871 : /* At this point, we know the sum of the chain lengths do not exceed
2872 : the size of the element store, each chain is of their stated
2873 : length, each chain element is in element store, and that every
2874 : element on a chain belongs on that chain (which precludes the
2875 : possibility of two chains merging into one) and that every element
2876 : on a chain is unique (which implies unique among all chains since
2877 : elements with each key maps to a single chain).
2878 :
2879 : That is, join is a current local join to a valid shared mapping of
2880 : unique keys to unique elements in the element store.
2881 :
2882 : We don't know anything about unmapped elements in the element store
2883 : and cannot do any verification of them (here be dragons). But
2884 : that's kinda the point ... what's in the unmapped elements depends
2885 : on how the application is managing those. */
2886 :
2887 480 : # undef MAP_TEST
2888 :
2889 480 : return FD_MAP_SUCCESS;
2890 480 : }
2891 :
2892 : MAP_STATIC char const *
2893 18 : MAP_(strerror)( int err ) {
2894 18 : switch( err ) {
2895 3 : case FD_MAP_SUCCESS: return "success";
2896 3 : case FD_MAP_ERR_INVAL: return "bad input";
2897 3 : case FD_MAP_ERR_AGAIN: return "try again";
2898 3 : case FD_MAP_ERR_CORRUPT: return "corruption detected";
2899 3 : case FD_MAP_ERR_KEY: return "key not found";
2900 3 : default: break;
2901 18 : }
2902 3 : return "unknown";
2903 18 : }
2904 :
2905 : #undef MAP_CRIT_END
2906 : #undef MAP_CRIT_BLOCKED
2907 : #undef MAP_CRIT
2908 :
2909 : #endif
2910 :
2911 : #undef MAP_
2912 : #undef MAP_STATIC
2913 : #undef MAP_VER_WIDTH
2914 : #undef MAP_PEDANTIC
2915 : #undef MAP_IMPL_STYLE
2916 : #undef MAP_MAGIC
2917 : #undef MAP_ALIGN
2918 : #undef MAP_CNT_WIDTH
2919 : #undef MAP_KEY_EQ_IS_SLOW
2920 : #undef MAP_MEMO
2921 : #undef MAP_MEMOIZE
2922 : #undef MAP_KEY_HASH
2923 : #undef MAP_KEY_EQ
2924 : #undef MAP_NEXT
2925 : #undef MAP_IDX_T
2926 : #undef MAP_KEY
2927 : #undef MAP_KEY_T
2928 : #undef MAP_ELE_T
2929 : #undef MAP_NAME
|
