Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for concurrent
2 : persistent shared maps based on linear probing with some insights
3 : from cuckoo hashing for improved concurrent performance. Notably:
4 :
5 : - Supports an arbitrary number of concurrent operations with a
6 : comparable performance to a single threaded HPC linear probed map
7 : for non-conflicting operations (likely hardware NOC limited for
8 : conflicting operations).
9 :
10 : - Concurrent queries do not interfere with other concurrent queries.
11 :
12 : - All map operations can be serialized.
13 :
14 : - Does not require a key sentinel (but can support them useful for
15 : the application).
16 :
17 : - Does not require a guarantee there's at least one free element in
18 : the element store (but like a serial linear probed map, it is a
19 : good idea to keep utilization below the absolute theoretical
20 : capacity for strong algorithmic performance guarantees).
21 :
22 : - Insert/modify/query have a run-time configurable worst case O(1)
23 : cost, regardless of map fill ratio. (Remove's worst case cost is
24 : not configurable due to cases involving maps filled to or near
25 : capacity. For reasonable fill ratios, remove is also comparable.)
26 :
27 : - Stable in the sense that all keys with the same hash (or more
28 : generally same initial probe element) are ordered in the element
29 : store by insertion order. (This allows the user to use the key
30 : hash to group related keys contiguously in the element store and
31 : then stably iterate over them with fast streaming.)
32 :
33 : - Query requires no atomic operations at all. (Usual target memory
34 : subsystem requirements that writes to memory become visible to
35 : other threads in the order in which they were issued in the machine
36 : code.)
37 :
38 : - Insert/modify/remove only require atomic fetch-and-or (typically
39 : just one). There's no need for an atomic compare-and-swap /
40 : underlying pool of free elements / etc. (Can also be used as a
41 : non-concurrent map on targets without FD_HAS_ATOMIC.)
42 :
43 : - Map concurrency metadata and the actual map element store can be
44 : located in separate memory regions (can also split the element
45 : store over multiple memory regions ... e.g. keys here / values
46 : there) and can back any of these memory regions by a file system to
47 : scale beyond billions of elements with no code change.
48 :
49 : - Map metadata easily fits in CPU caches with a fixed O(1) overhead
50 : regardless of element store capacity. Access patterns naturally
51 : exploit CPU and storage caching, streaming and prefetching
52 : behaviors.
53 :
54 : - Supports asynchronous execution (e.g. issue hints for keys that
55 : will be accessed soon, do unrelated work while hints are
56 : prefetching need info into local cache in the background, then do
57 : key operations ... now all fast and local cache hits).
58 :
59 : - Supports non-plain-old-data keys and non-plain-old-data values
60 : (both of which are gross on real world computers but commonly done
61 : nevertheless).
62 :
63 : A map can be persisted beyond the lifetime of the creating process,
64 : be used inter-process, relocated in memory, be naively
65 : serialized/deserialized, be moved between hosts, etc. Massive
66 : concurrency, high algorithmic and implementation performance for
67 : normal usage and friendly cache / file system streaming access
68 : patterns for heavily loaded / heavily concurrent usage are
69 : prioritized. In particular, unlike fd_map_chain_para, this takes
70 : ownership of the underlying element store for the lifetime of the map
71 : in order to speed up operations and increase concurrency.
72 :
73 : Typical usage:
74 :
75 : struct myele {
76 : ulong key; // Technically "MAP_KEY_T MAP_KEY" (default is ulong key)
77 :
78 : ... key can be located arbitrarily in the element. The mapping
79 : ... of a key to an element in the element store is arbitrary and
80 : ... can move while the key is in the map.
81 : };
82 :
83 : typedef struct myele myele_t;
84 :
85 : #define MAP_NAME mymap
86 : #define MAP_ELE_T myele_t
87 : #include "tmpl/fd_map_slot_para.c"
88 :
89 : will declare the following APIs as a header only style library in the
90 : compilation unit:
91 :
92 : // A mymap_t is a stack declaration friendly quasi-opaque local
93 : // object used to hold the state of a local join to a mymap.
94 : // Similarly, a mymap_query_t / mymap_iter_t holds the local state
95 : // of an ongoing operation / iteration. E.g. it is fine to do
96 : // mymap_t join[1];" to allocate a mymap_t but the contents should
97 : // not be used directly.
98 :
99 : typedef struct mymap_private mymap_t;
100 : typedef struct mymap_query_private mymap_query_t;
101 : typedef struct mymap_iter_private mymap_iter_t;
102 :
103 : // mymap_lock_max returns the maximum number of version locks that
104 : // can be used by a mymap. Will be a positive integer
105 : // power-of-two.
106 :
107 : ulong mymap_lock_max( void );
108 :
109 : // mymap_lock_cnt_est returns a reasonable number of locks to use
110 : // for a map backed by an ele_max capacity element store. Assumes
111 : // ele_max is an integer power-of-two. Returns an integer
112 : // power-of-two in [1,mymap_lock_max()].
113 :
114 : ulong mymap_lock_cnt_est( ulong ele_max );
115 :
116 : // mymap_probe_max_est returns a reasonable maximum probe sequence
117 : // length for a map backed by an ele_max capacity element store.
118 : // Assumes ele_max is an integer power-of-two. Returns an integer
119 : // in [1,ele_max].
120 :
121 : ulong mymap_probe_max_est( ulong ele_max );
122 :
123 : // mymap_{align,footprint} returns the alignment and footprint
124 : // needed for a memory region to be used as a mymap. align will be
125 : // an integer power-of-two and footprint will be a multiple of
126 : // align. ele_max / lock_cnt / probe_max specify the capacity of
127 : // the element store / number of version locks / maximum probe
128 : // sequence length for the map. footprint returns 0 for invalid
129 : // configurations. In a valid configuration, ele_max is an integer
130 : // power-of-two, lock_cnt is an integer power-of-two, lock_cnt is
131 : // at most min( lock_max, ele_max ) and probe_max is in
132 : // [1,ele_max].
133 : //
134 : // mymap_new formats a memory region with the required alignment
135 : // and footprint into a mymap. shmem points in the caller's
136 : // address space to the memory region to use. Returns shmem on
137 : // success (mymap has ownership of the memory region) and NULL on
138 : // failure (no changes, logs details). The caller is not joined on
139 : // return. All map versions will be at version 0 / unlocked. The
140 : // map contents will be in whatever state the backing element store
141 : // is in. IMPORTANT SAFETY TIP! THE ELEMENT STORE SHOULD BE IN A
142 : // CONSISTENT STATE BEFORE USING MYMAP_NEW. For example, the
143 : // caller could mark all elements as free before calling this and
144 : // the caller could use verify immediately after creation to verify
145 : // integrity.
146 : //
147 : // mymap_join joins the caller to an existing mymap. ljoin points
148 : // to a mymap_t compatible memory region in the caller's address
149 : // space, shmap points in the caller's address space to the memory
150 : // region containing the mymap, and shele points in the caller's
151 : // address space to mymap's element store. Returns a handle to the
152 : // caller's local join on success (join has ownership of the ljoin
153 : // region) and NULL on failure (no changes, logs details).
154 : //
155 : // mymap_leave leaves a mymap join. join points to a current local
156 : // join. Returns the memory region used for the join on success
157 : // (caller has ownership on return and the caller is no longer
158 : // joined) and NULL on failure (no changes, logs details). Use the
159 : // join accessors before leaving to get shmap and shele used by the
160 : // join if needed.
161 : //
162 : // mymap_delete unformats a memory region used as a mymap. Assumes
163 : // shmap points in the caller's address space to a memory region
164 : // containing the mymap and that there are no joins. Returns shmem
165 : // on success (caller has ownership of the memory region, any
166 : // remaining elements still in the mymap are released to the caller
167 : // implicitly) and NULL on failure (no changes, logs details).
168 :
169 : ulong mymap_align ( void );
170 : ulong mymap_footprint( ulong ele_max, ulong lock_cnt, ulong probe_max );
171 : void * mymap_new ( void * shmem, ulong ele_max, ulong lock_cnt, ulong probe_max, ulong seed );
172 : mymap_t * mymap_join ( void * ljoin, void * shmap, void * shele );
173 : void * mymap_leave ( mymap_t * join );
174 : void * mymap_delete ( void * shmap );
175 :
176 : // mymap_{ele_max,lock_cnt,probe_max,seed} return the mymap
177 : // configuration. Assumes join is a current local join. The
178 : // values will be valid for the mymap lifetime.
179 :
180 : ulong mymap_ele_max ( mymap_t const * join );
181 : ulong mymap_lock_cnt ( mymap_t const * join );
182 : ulong mymap_probe_max( mymap_t const * join );
183 : ulong mymap_seed ( mymap_t const * join );
184 :
185 : // mymap_{shmap,shele} return join details. Assumes join is a
186 : // current local join. The values will be valid for the join
187 : // lifetime. mymap_{shmap_const,shele_const} are const correct
188 : // versions.
189 :
190 : void const * mymap_shmap_const( mymap_t const * join );
191 : void const * mymap_shele_const( mymap_t const * join );
192 :
193 : void * mymap_shmap( mymap_t * join );
194 : void * mymap_shele( mymap_t * join );
195 :
196 : // mymap_{ele_lock,lock_ele0,lock_ele1} specify the mapping between
197 : // map version lock indices and element store element indices.
198 : // Assumes join is a current local join and ele_idx / lock_idx is
199 : // in [0,ele_max) / is in [0,lock_cnt). mymap_ele_lock is the
200 : // index of the version lock that protects element store element
201 : // ele_idx, in [0,lock_cnt). [mymap_lock_ele0,mymap_lock_ele1) is
202 : // the contiguous range of elements protected by lock lock_idx.
203 : // ele0 is in [0,ele_max), ele1 is in (0,ele_max], and ele0<ele1.
204 :
205 : ulong mymap_ele_lock ( mymap_t const * join, ulong ele_idx );
206 : ulong mymap_lock_ele0( mymap_t const * join, ulong lock_idx );
207 : ulong mymap_lock_ele1( mymap_t const * join, ulong lock_idx );
208 :
209 : // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
210 : // as inlines with strict semantics. They assume that the provided
211 : // pointers are in the caller's address space to keys that will not
212 : // be changed during the call. They retain no interest in any keys
213 : // on return.
214 : //
215 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
216 : //
217 : // mymap_key_hash returns the hash of *key using the hash function
218 : // seed. Should ideally be a random mapping from a MAP_KEY_T to a
219 : // ulong but this depends on what the user actually used for
220 : // MAP_KEY_HASH. The seed used by a particular mymap instance can
221 : // be obtained above.
222 :
223 : int mymap_key_eq ( ulong * k0, ulong * k1 );
224 : ulong mymap_key_hash( ulong * key, ulong seed );
225 :
226 : // mymap_backoff does FD_SPIN_PAUSE a random number of times. The
227 : // number of pauses is an approximately uniform IID random number
228 : // in [0,scale/2^16] where scale is in [0,2^32). Specifically, the
229 : // number of pauses is:
230 : //
231 : // floor( scale r / 2^48 )
232 : //
233 : // where r is a non-deterministic 32-bit uniform IID random number.
234 : // Under the hood, r is generated by hashing the user provided seed
235 : // and the least significant 32-bits of the CPU tickcounter.
236 : // Ideally, seed is a 32-bit globally unique identifier for the
237 : // logical thread of execution but this is up to the application to
238 : // specify and rarely matters in practice. This is a useful
239 : // building block for random exponential backoffs.
240 :
241 : void mymap_backoff( ulong scale, ulong seed );
242 :
243 : // mymap_query_memo returns the key_hash of the query associated
244 : // with the query's key to allow users to minimize potentially
245 : // expensive key hash computations in various operations.
246 : //
247 : // mymap_query_ele returns a pointer in the caller's address space
248 : // to the element store element associated with the query or a
249 : // sentinel value. The sentinel value is application dependent and
250 : // thus arbitrary (e.g. not necessarily in the element store,
251 : // including NULL, a local temporary used as a bit bucket, etc).
252 : // Assumes query is valid. The lifetime of the returned pointer
253 : // depends on the query. mymap_query_ele_const is a const correct
254 : // version.
255 :
256 : ulong mymap_query_memo ( mymap_query_t const * query );
257 : myele_t const * mymap_query_ele_const( mymap_query_t const * query );
258 : myele_t * mymap_query_ele ( mymap_query_t * query );
259 :
260 : // mymap_hint hints that the caller plans to do an operation
261 : // involving key soon. Assumes join is a current local join, key
262 : // points to a valid key in the caller's address space for the
263 : // duration of the call and query points to a local scratch to hold
264 : // info about the hint. Retains no interest in key. On return,
265 : // the query memo will be initialized.
266 : //
267 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_USE_HINT
268 : // is set, this will assume that query's memo is already
269 : // initialized for key (e.g. mostly useful for hashless
270 : // prefetching). If FD_MAP_FLAG_PREFETCH_META /
271 : // FD_MAP_FLAG_PREFETCH_DATA is set, this will issue a prefetch for
272 : // key's mymap metadata (i.e. lock version) / the element at the
273 : // start of key's probe sequence (i.e. the location of key or
274 : // contiguously shortly before it) FD_MAP_FLAG_PREFETCH combines
275 : // both for convenience. This can be used to overlap key access
276 : // latency with unrelated operations. All other flags are ignored.
277 :
278 : void
279 : mymap_hint( MAP_(t) const * join
280 : MAP_KEY_T const * key
281 : MAP_(query_t) * query,
282 : int flags );
283 :
284 : // mymap_prepare tries to start an insert/modify/blocking query
285 : // operation for key. Assumes join is a current local join, key
286 : // points to valid key in the caller's address space for the
287 : // duration of the call and query points to a local scratch to hold
288 : // the info about the prepare. Retains no interest in key.
289 : // Returns FD_MAP_SUCCESS (0) and an FD_MAP_ERR (negative) on
290 : // failure. This is a non-blocking fast O(1) (O(probe_max) worst
291 : // case) and supports highly concurrent operation.
292 : //
293 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING
294 : // is set / clear in flags, this is allowed / not allowed to block
295 : // the caller. If FD_MAP_FLAG_USE_HINT is set, this assumes
296 : // query's memo is already initialized for key. This can be used
297 : // to avoid redundant expensive key hashing when prefetching. All
298 : // other flags are ignored (the upper 26-bits of flags can be used
299 : // to provide a local seed for random backoffs but this is up to
300 : // the application and rarely matters in practice).
301 : //
302 : // On success, the caller is in a prepare for key, query is
303 : // initialized with info about prepare (including query's memo
304 : // initialized for key). ele=mymap_query_ele(query) gives the
305 : // location in the caller's address space to an element store
306 : // element for the prepare that will be stable for the duration of
307 : // the prepare and memo=mymap_query_memo(query) gives the key hash.
308 : //
309 : // If the element is marked as free, key is not in the map and ele
310 : // is where key could be inserted. If the caller is inserting key,
311 : // the caller should populate element's key with key, element's
312 : // memo (if any) with memo (avoids having to rehash the key), mark
313 : // ele as used and then do a mymap_publish to complete the insert.
314 : // If not, the caller should keep ele marked as free and do a
315 : // mymap_cancel to complete the prepare (doesn't matter from the
316 : // map's point-of-view if anything else was clobbered /
317 : // mymap_publish would also work here).
318 : //
319 : // If the element is marked as used, key is in the map at ele. If
320 : // the caller is modifying key's value, the caller should do the
321 : // modification and then mymap_publish to complete the modify. If
322 : // not (e.g. blocking query), the caller can inspect ele contents
323 : // and the mymap_cancel to complete the blocking query
324 : // (mymap_publish would also work here). In both cases, the caller
325 : // should not modify ele's key, modify ele's memo, or mark ele as
326 : // free. Note that mymap_publish must be used even if the
327 : // modifications were only temporary.
328 : //
329 : // On failure, the caller is not in a prepare for key, query
330 : // ele==sentinel and query memo will be initialized for key.
331 : / Reasons for failure:
332 : //
333 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
334 : // progress at some point during the call. Try again later (e.g.
335 : // after a random exponential backoff). Never returned on a
336 : // blocking call.
337 : //
338 : // - FD_MAP_ERR_FULL: key was not in the map but inserting ele
339 : // would require making a probe sequence longer than probe_max.
340 : // Try again when the map is less full (e.g. after removing some
341 : // elements).
342 : //
343 : // mymap_publish ends the prepare described by query, updating the
344 : // map version to reflect changes made during the prepare. Assumes
345 : // query is valid and describes an active prepare. Cannot fail and
346 : // will not be in the prepare will finished on return (query's memo
347 : // will still be intialized for key). This is a generally safe way
348 : // to end a prepare even if the caller did not modify the map
349 : // during the prepare.
350 : //
351 : // mymap_cancel ends the prepare described by query, reverting the
352 : // map version to reflect that the caller did not change the map
353 : // during the prepare. Assumes query is valid and describes an
354 : // active prepare and that the caller did not make any meaningful
355 : // modifications to the map during the prepare (note that temporary
356 : // changes during the prepare can be considered modifications as
357 : // per the above). Cannot fail and will not be in the prepare will
358 : // finished on return (query's memo will still be initialized
359 : // for key). This is a safe way to end a prepare only if the
360 : // caller did not modify the map during the prepare.
361 : //
362 : // IMPORTANT SAFETY TIP! Do not nest or interleave prepares,
363 : // remove or queries for the same map on the same thread.
364 : //
365 : // IMPORTANT SAFETY TIP! A successful prepare must have a matching
366 : // publish or cancel (and then ideally as soon as possible).
367 : //
368 : // IMPORTANT SAFETY TIP! The order in which keys that hash to the
369 : // same slot were inserted into the map is preserved for the
370 : // lifetime of the keys. Thus the hash function used can be
371 : // constructed to create ordered iterators over groups of keys.
372 :
373 : int mymap_prepare( mymap_t * join, ulong const * key, myele_t * sentinel, mymap_query_t * query, int flags );
374 : void mymap_publish( mymap_query_t * query );
375 : void mymap_cancel ( mymap_query_t * query );
376 :
377 : // mymap_remove removes key from the mymap. Assumes join is a
378 : // current local join and key is valid for the duration of the
379 : // call. Retains no interest in key. This is non-blocking fast
380 : // typically O(1) and supports highly concurrent operation.
381 : //
382 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING
383 : // is set / clear in flags, this is allowed / not allowed to block
384 : // the caller. If FD_MAP_FLAG_USE_HINT is set, this assumes
385 : // query's memo is already initialized for key. This can be used
386 : // to avoid redundant expensive key hashing when prefetching. If
387 : // clear, query is ignored and can be set NULL. All other flags
388 : // are ignored (the upper 26-bits of flags can be used to provide a
389 : // local seed for random backoffs but this is up to the application
390 : // and rarely matters in practice).
391 : //
392 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
393 : // (negative) on failure. On success, key's mapping was removed at
394 : // some point during the call. On failure, no changes were made by
395 : // this call and:
396 : //
397 : // - FD_MAP_ERR_KEY: Key was not found in the mymap at some point
398 : // during the call.
399 : //
400 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
401 : // progress at some point during the call. Same considerations
402 : // as prepare above. Never returned on a blocking call.
403 : //
404 : // IMPORTANT SAFETY TIP! Do not nest or interleave prepares,
405 : // remove or queries for the same map on the same thread.
406 :
407 : int mymap_remove( mymap_t * join, ulong const * key, mymap_query_t const * query, int flags );
408 :
409 : // mymap_query_try tries to speculatively query a mymap for key.
410 : // On return, query will hold information about the try (including
411 : // query's memo initialized for key). sentinel gives the query
412 : // element pointer value (arbitrary) to pass through when it is not
413 : // safe to try the query. Assumes join is a current local join and
414 : // key is valid for the duration of the call. Does not modify the
415 : // mymap and retains no interest in key, sentinel or query. This
416 : // is a non-blocking fast O(1) (O(probe_max) worst case) and
417 : // supports highly concurrent operation.
418 : //
419 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING
420 : // is set / clear in flags, this is allowed / not allowed to block
421 : // the caller. If FD_MAP_FLAG_USE_HINT is set, this assumes
422 : // query's memo is already initialized for key. This can be used
423 : // to avoid redundant expensive key hashing when prefetching. All
424 : // other flags are ignored (the upper 26-bits of flags can be used
425 : // to provide a local seed for random backoffs but this is up to
426 : // the application and rarely matters in practice).
427 : //
428 : // Returns FD_MAP_SUCCESS (0) on success and an FD_MAP_ERR
429 : // (negative) on failure. On success, key mapped to the element
430 : // store element mymap_query_ele( query ) in the caller's address
431 : // space at some point during the call. The mymap retains
432 : // ownership of this element but the caller can zero copy
433 : // speculatively process the element's contents. On failure,
434 : // mymap_query_ele( query ) will be sentinel and returns:
435 : //
436 : // - FD_MAP_ERR_KEY: Key was not found in the mymap in some point
437 : // during the call.
438 : //
439 : // - FD_MAP_ERR_AGAIN: A potentially conflicting operation was in
440 : // progress at some point during the call. Try again later (e.g.
441 : // after a random exponential backoff). Unlike prepare and
442 : // remove, this call does _not_ require any locks for key's probe
443 : // sequence. As such, AGAIN can only be caused by concurrent
444 : // prepare/remove operations and this will never interfere with
445 : // any other concurrent operation. Among the many implications,
446 : // a query will never delay a concurrent query and AGAIN will
447 : // never be returned if only concurrent speculative queries are
448 : // in progress. Never returned on a blocking call.
449 : //
450 : // IMPORTANT SAFETY TIP! THE CALLER SHOULD BE PREPARED TO HANDLE
451 : // ARBITRARY AND/OR INCONSISTENT VALUES FOR ELEMENT FIELDS DURING
452 : // SPECULATIVE PROCESSING. CALLERS SHOULD NOT COMMIT ANY RESULTS
453 : // OF SPECULATIVE PROCESSING UNTIL IT TESTS THE QUERY WAS
454 : // SUCCESSFUL.
455 : //
456 : // The simplest form of speculative processing is to copy the
457 : // element store element into a local temporary, test that the
458 : // speculation was valid, and then process the local temporary copy
459 : // at its leisure. Zero copy, more selective copying and/or
460 : // writing speculative results into local temporaries are more
461 : // advanced examples of speculative processing.
462 : //
463 : // Use mymap_prepare to do a blocking (non-speculative) query.
464 : //
465 : // mymap_query_test tests if an in-progress query is still valid.
466 : // Assumes query is valid, we are still in a query try and lock
467 : // version numbers have not wrapped since we started the try.
468 : // Returns FD_MAP_SUCCESS (0) if the query is still valid and
469 : // FD_MAP_ERR_AGAIN (negative) if a potentially conflicting
470 : // operation was in progress at some point during the try.
471 : //
472 : // IMPORTANT SAFETY TIP! Do not nest or interleave prepares,
473 : // remove or queries for the same map on the same thread.
474 :
475 : int
476 : mymap_query_try( mymap_t const * join,
477 : ulong const * key,
478 : myele_t const * sentinel,
479 : mymap_query_t * query,
480 : int flags );
481 :
482 : int mymap_query_test( mymap_query_t const * query );
483 :
484 : // mymap_lock_range tries to acquire locks lock_idx for lock_idx in
485 : // [range_start,range_start+range_cnt) (cyclic).
486 : //
487 : // flags is a bit-or of FD_MAP_FLAG flags. If FD_MAP_FLAG_BLOCKING
488 : // is set / clear in flags, this is allowed / not allowed to block
489 : // the caller. If FD_MAP_FLAG_RDONLY is set, the caller promises
490 : // to only read the elements covered by the range while holding the
491 : // locks. All other flags are ignored (the upper 26-bits of flags
492 : // can be used to provide a local seed for random backoffs but this
493 : // is up to the application and rarely matters in practice).
494 : //
495 : // Returns FD_MAP_SUCCESS (0) on success and FD_MAP_ERR_AGAIN
496 : // (negative) if there was a potentially conflicting operation in
497 : // progress at some point during the call. On success,
498 : // version[lock_idx] will hold the version to use when releasing
499 : // that lock. On failure, version may have been clobbered. AGAIN
500 : // is never returned if BLOCKING is set.
501 : //
502 : // mymap_unlock_range unlocks a similarly specified range. Assumes
503 : // caller has the locks and version[lock_idx] is the value set when
504 : // locked was obtained.
505 : //
506 : // These both assume join is a current local join, range_start is
507 : // in [0,lock_cnt), range_cnt is in [0,lock_cnt] and version is
508 : // valid with space for lock_cnt entries (YES ... LOCK_CNT, NOT
509 : // RANGE_CNT ... this is trivial with a compile time stack
510 : // temporary as lock_cnt<=MAP_LOCK_MAX).
511 :
512 : int
513 : mymap_lock_range( mymap_t * join,
514 : ulong range_start,
515 : ulong range_cnt,
516 : int flags,
517 : ulong * version );
518 :
519 : void
520 : mymap_unlock_range( mymap_t * join,
521 : ulong range_start,
522 : ulong range_cnt,
523 : ulong const * version );
524 :
525 : // The mymap_iter_* APIs are used to iterate over all keys inserted
526 : // into the map with the same memo (to support grouping of keys by
527 : // key hash value). The iteration order will be from the least
528 : // recently inserted to most recently inserted. flags has similar
529 : // meaning as other APIs. Example usage:
530 : //
531 : // ulong memo = ... hash of keys to iterate over ...
532 : //
533 : // mymap_iter_t iter[1];
534 : // int err = mymap_iter_init( join, memo, 0, iter );
535 : //
536 : // if( FD_UNLIKELY( err ) ) {
537 : //
538 : // ... At this point, err is FD_MAP_ERR_AGAIN and caller has
539 : // ... ownership of iter. There was a potentially conflicting
540 : // ... prepare or remove in progress at some point during the
541 : // ... call. We can try again later (e.g. after a random
542 : // ... backoff or doing other non-conflicting work).
543 : // ... mymap_iter_done will be 1, mymap_iter_fini will be a
544 : // ... no-op. Never returned if mymap_iter_init flags has
545 : // ... FD_MAP_FLAG_BLOCKING set.
546 : //
547 : // } else {
548 : //
549 : // ... At this point, we are in an iteration and iteration has
550 : // ... ownership of iter.
551 : //
552 : // while( !mymap_iter_done( iter ) ) {
553 : // myele_t * ele = mymap_iter_ele( iter );
554 : //
555 : // ... At this point, mymap_key_hash( ele->key, seed ) == memo (==ele's memo if memoized)
556 : //
557 : // ... process ele here.
558 : //
559 : // ... IMPORTANT! Generally speaking, it is not okay to
560 : // ... insert, remove, modify, blocking read, non-blocking
561 : // ... read here. It is okay to read ele and modify any
562 : // ... value fields though. If mymap_iter_init flags had
563 : // ... FD_MAP_FLAG_RDONLY set, caller promises it is only
564 : // ... reading ele here.
565 : //
566 : // mymap_iter_next( iter );
567 : // }
568 : //
569 : // mymap_iter_fini( iter );
570 : //
571 : // ... At this point, we are not in an iteration and caller has
572 : // ... ownership of iter.
573 : //
574 : // }
575 :
576 : int mymap_iter_init( mymap_t * join, ulong memo, int flags, mymap_iter_t * lmem );
577 : int mymap_iter_done( mymap_iter_t * iter );
578 : myele_t * mymap_iter_ele ( mymap_iter_t * iter );
579 : mymap_iter_t * mymap_iter_next( mymap_iter_t * iter );
580 : mymap_iter_t * mymap_iter_fini( mymap_iter_t * iter );
581 :
582 : // mymap_verify returns FD_MAP_SUCCESS (0) if the join, underlying
583 : // map and underlying element store give a mapping of unique keys
584 : // to unique elements in the element store with a bounded maximum
585 : // probe length. Returns FD_MAP_ERR_INVAL (negative) otherwise (no
586 : // changes by this call, logs details). Assumes that caller has
587 : // all the map locks and/or the map is otherwise known to be idle.
588 :
589 : int mymap_verify( mymap_t const * join );
590 :
591 : // mymap_strerror converts an FD_MAP_SUCCESS / FD_MAP_ERR code into
592 : // a human readable cstr. The lifetime of the returned pointer is
593 : // infinite. The returned pointer is always to a non-NULL cstr.
594 :
595 : char const * mymap_strerror( int err );
596 :
597 : Do this as often as desired in a compilation unit to get different
598 : types of concurrent maps. Options exist for generating library
599 : header prototypes and/or library implementations for concurrent maps
600 : usable across multiple compilation units. Additional options exist
601 : to use different hashing functions, key comparison functions, etc as
602 : detailed below.
603 :
604 : IMPORTANT SAFETY TIP! If using a key sentinel, prepare/remove/query
605 : operations assume the input key is not the key sentinel (i.e. a
606 : sentinel is not considered a "valid key). Sentinel keys are not
607 : necessary if MAP_ELE_IS_FREE, MAP_ELE_FREE and MAP_ELE_MOVE are set
608 : appropriately.
609 :
610 : To better understand prepare / publish / cancel semantics:
611 :
612 : mykey_t * key = ... key to insert / modify / blocking query
613 :
614 : mymap_query_t query[1];
615 : int err = mymap_prepare( map, key, sentinel, query, 0 );
616 : myele_t * ele = mymap_query_ele ( query );
617 : ulong memo = mymap_query_memo( query );
618 :
619 : ... At this point, memo == mymap_key_hash( key, seed )
620 :
621 : if( FD_UNLIKELY( err ) ) {
622 :
623 : ... At this point, we are not in a prepare for key and
624 : ... ele==sentinel.
625 :
626 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
627 : ... conflicting prepare or remove in progress at some point
628 : ... during the call. We can try again later (e.g. after a
629 : ... random backoff or doing other non-conflicting work).
630 : ... Never returned for a blocking call.
631 :
632 : ... If err is FD_MAP_ERR_FULL, key was not in the map but
633 : ... inserting it would have created a key probe sequence longer
634 : ... than probe_max at some point during the call. We can try
635 : ... again later when it is less full (e.g. after removing keys
636 : ... from the map).
637 :
638 : } else if( ... ele is marked as free ... ) ) {
639 :
640 : ... At this point, we are in a prepare for key, key is not in
641 : ... the map and ele points in the caller's address space to free
642 : ... element in the element store suitable for holding key.
643 :
644 : ... initialize ele here, including populating ele's key with key
645 : ... and (if memoized) populating ele's memo with memo.
646 :
647 : if( ... we decided not to insert key ... ) mymap_cancel( query ); // "failed insert"
648 : else {
649 : ... mark ele as used
650 : mymap_publish( query ); // "insert"
651 : }
652 :
653 : } else {
654 :
655 : ... At this point, we are in a prepare for key, key is in the map
656 : ... and ele points in the caller's address space to the element
657 : ... store element that currently contains key. We are free to
658 : ... modify ele's value. We should not modify ele's key, modify
659 : ... ele's memo (if memoized) or mark ele as free.
660 :
661 : ... process ele here
662 :
663 : if( ... we didn't modify ele ... ) mymap_cancel ( query ); // "blocking query"
664 : else mymap_publish( query ); // "modify"
665 :
666 : }
667 :
668 : To better understand remove semantics:
669 :
670 : mykey_t * key = ... key to remove
671 :
672 : int err = mymap_remove( map, key, NULL, 0 );
673 :
674 : if( FD_UNLIKELY( err ) ) {
675 :
676 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
677 : ... conflicting prepare or remove in progress at some point
678 : ... during the call. We can try again later (e.g. after a random
679 : ... backoff or doing other non-conflicting work).
680 : ... Never returned for a blocking call.
681 :
682 : ... If err is FD_MAP_ERR_KEY, key was not in the map at some
683 : ... point during the call (so remove did not do anything).
684 :
685 : } else {
686 :
687 : ... key was removed from the map at some point during the call.
688 : ... The remove might have shuffled other keys. This shuffling
689 : ... can only decrease probe sequence length for any remaining
690 : ... keys and preserves insertion ordering for keys with the same
691 : ... hash (or initial probe element more generally).
692 :
693 : }
694 :
695 : To better understand query semantics:
696 :
697 : mykey_t * key = ... key to query
698 :
699 : mymap_query_t query[1];
700 : int err = mymap_query_try( join, key, sentinel, query, 0 );
701 : myele_t const * ele = mymap_query_ele_const( query );
702 : ulong memo = mymap_query_memo ( query );
703 :
704 : ... At this point, memo==mymap_key_hash( key, seed )
705 :
706 : if( FD_UNLIKELY( err ) ) {
707 :
708 : ... At this point, ele==sentinel
709 : ...
710 : ... If err is FD_MAP_ERR_KEY, key was not in the mymap at some
711 : ... point during the try.
712 : ...
713 : ... If err is FD_MAP_ERR_AGAIN, there was a potentially
714 : ... conflicting operation in progress during the try and we can
715 : ... try again later (e.g. after a random backoff or doing other
716 : ... non-conflicting work).
717 :
718 : } else {
719 :
720 : ... At this point, ele points in our address space to an element
721 : ... in the element store (non-NULL) and ele->key matched key at
722 : ... some point during the try.
723 :
724 : ... Speculatively process ele here.
725 : ...
726 : ... DO NOT TRUST ANY RESULTS OF THIS SPECULATIVE PROCESSING YET.
727 : ... THERE IS NO GUARANTEE YET THAT A CONCURRENT USER HASN'T
728 : ... CHANGED THE MYMAP IN A WAY THAT COULD YIELD ARBITRARY AND
729 : ... INCONSISTENT RESULTS.
730 : ...
731 : ... The simplest and most common form of speculative processing
732 : ... is to copy the needed portions of ele into local stack temps.
733 : ...
734 : ... Note: concurrent operations include removing key from the
735 : ... mymap (and maybe multiple cycles of inserting and removing it
736 : ... and then at potentially different element store locations) or
737 : ... unrelated removes potentially shuffling the location of this
738 : ... key. That's not an issue practically as the ele pointer here
739 : ... will be to an element compatible memory region that will
740 : ... continue to exist regardless and we shouldn't be trusting any
741 : ... query reads yet (the query test will detect if these can be
742 : ... trusted). See rant in fd_map_chain_para.c for more details.
743 :
744 : ... At this point, we are done with speculative processing (or we
745 : ... don't want to do any more speculative processing if the try
746 : ... has already failed).
747 :
748 : err = mymap_query_test( query );
749 : if( FD_UNLIKELY( err ) ) {
750 :
751 : ... At this point, err will be FD_MAP_ERR_AGAIN and a
752 : ... potentially conflicting operation in the try was detected
753 : ... by the test.
754 :
755 : ... Application specific handling here (e.g. try again after a
756 : ... random backoff or doing other non-conflicting work).
757 :
758 : } else {
759 :
760 : ... At this point, the results of the speculation thus far can
761 : ... be trusted and can be considered to have been computed at
762 : ... some point in time between try and test.
763 :
764 : }
765 : }
766 :
767 : Example use of lock_range / unlock (do a parallel snapshot of an
768 : entire map at a globally well defined point in time with minimal
769 : interference to ongoing concurrent modifications):
770 :
771 : ulong version[ mymap_lock_max() ];
772 :
773 : ulong lock_cnt = mymap_lock_cnt( join );
774 :
775 : mymap_lock_range( join, 0, lock_cnt, FD_MAP_FLAGS_BLOCKING | FD_MAP_FLAGS_RDONLY, version );
776 :
777 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) { ... parallelize this loop over snapshot threads as desired
778 : ulong ele0 = mymap_lock_ele0( join, lock_idx );
779 : ulong ele1 = mymap_lock_ele1( join, lock_idx );
780 :
781 : ... process element store elements [ele0,ele1) here
782 :
783 : mymap_unlock_range( join, lock_idx, 1UL, version );
784 : }
785 :
786 : Note that mymap_lock_range in this example might block the caller for
787 : a long time if the map is under heavy concurrent modification. To
788 : prioritize the snapshotting over these operations, the same API can
789 : be used to prioritize the snapshot over ongoing concurrent
790 : modifications:
791 :
792 : ulong version[ mymap_lock_max() ];
793 :
794 : ulong lock_cnt = mymap_lock_cnt( join );
795 :
796 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ )
797 : mymap_lock_range( join, lock_idx, 1UL, FD_MAP_FLAGS_BLOCKING | FD_MAP_FLAGS_RDONLY, version );
798 :
799 : for( ulong lock_idx=0UL; lock_idx<lock_cnt; lock_idx++ ) { ... parallelize this loop over snapshot threads as desired
800 : ulong ele0 = mymap_lock_ele0( join, lock_idx );
801 : ulong ele1 = mymap_lock_ele1( join, lock_idx );
802 :
803 : ... process element store elements [ele0,ele1) here
804 :
805 : mymap_unlock_range( join, lock_idx, 1UL, version );
806 : }
807 :
808 : Implementation overview:
809 :
810 : A map is basically a persistent shared array of version numbers
811 : named lock. lock[ lock_idx ] contains a version number that covers
812 : map slots [lock_idx(ele_max/lock_cnt),(lock_idx+1)(ele_max/lock_cnt)).
813 :
814 : When trying an operation that could impact probe sequences passing
815 : through a lock's range of slots, the version number is atomically
816 : incremented. It is incremented again at completion. It may also
817 : be decremented if the operation didn't end up modifying any of the
818 : covered slots.
819 :
820 : Thus, an {odd,even} version number indicates that there is {a
821 : potential,not any} operation in progress that could impact probe
822 : sequences passing through the corresponding slots. The most
823 : significant bits of the version number can be used for lockfree
824 : style operations to detect changes to any probe sequences they use.
825 :
826 : When the map is not overloaded, key probe sequences are typically
827 : O(1) long and, in general, at most a (user configured) probe_max
828 : long. Since a version number covers many slots typically, this
829 : implies that the typical "read" operation (e.g.
830 : query_try/query_test) looks like:
831 :
832 : - try: observe lock version numbers covering all slots in key's
833 : probe sequence, fail if any locked (typically 1 normal read
834 : that hits L1/L2 cache, especially in the common case of
835 : reads more frequent than writes)
836 : - spec: speculatively process the element containing key
837 : - test: check version numbers haven't changed (typically 1 normal
838 : read that is an even more likely L1/L2 cache hit), fail if
839 : any changed
840 :
841 : And the typical "write" operation (e.g. prepare/publish) looks
842 : like:
843 :
844 : - prepare: increment lock version numbers covering all slots in
845 : key's probe sequence, fail if any locked (typically 1
846 : atomic fetch-and-or done test-and-test-and-set style to
847 : minimize hardware NOC contention)
848 : - exec: (non-speculatively) process the element containing key
849 : - publish: increment version numbers (typically 1 normal read/write
850 : that hits L1/L2 cache)
851 :
852 : Readers never block concurrent readers or writers. Writers can
853 : block other readers and other writers. If there are many more
854 : version locks than concurrent writers though, writers are unlikely
855 : to interfere with concurrent readers or writers. In all cases, all
856 : map operations are serializable.
857 :
858 : For maps that are loaded to their capacity, probe sequences could
859 : be up to probe_max long and probe_max might be quite large. This
860 : implies that more than one version lock might be needed. Since
861 : this range is cyclic contiguous in memory, the locking operations
862 : are nice compact streaming access patterns. And similarly for the
863 : element store access patterns. */
864 :
865 : #include "fd_map.h"
866 :
867 : /* MAP_NAME gives the API prefix to use for map */
868 :
869 : #ifndef MAP_NAME
870 : #error "Define MAP_NAME"
871 : #endif
872 :
873 : /* MAP_ELE_T is the map element type */
874 :
875 : #ifndef MAP_ELE_T
876 : #error "Define MAP_ELE_T"
877 : #endif
878 :
879 : /* MAP_KEY_T is the map key type */
880 :
881 : #ifndef MAP_KEY_T
882 : #define MAP_KEY_T ulong
883 : #endif
884 :
885 : /* MAP_KEY is the MAP_ELE_T key field */
886 :
887 : #ifndef MAP_KEY
888 5516805 : #define MAP_KEY key
889 : #endif
890 :
891 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
892 :
893 : #ifndef MAP_KEY_EQ
894 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
895 : #endif
896 :
897 : /* MAP_KEY_HASH returns a random mapping of *key into ulong. The
898 : mapping is parameterized by the 64-bit ulong seed. */
899 :
900 : #ifndef MAP_KEY_HASH
901 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
902 : #endif
903 :
904 : /* If MAP_MEMOIZE is defined to non-zero, elements have a field that
905 : can be used while in the map to hold the MAP_KEY_HASH for an
906 : element's key. This is useful for accelerating user code that might
907 : need a hash and various map operations. */
908 :
909 : #ifndef MAP_MEMOIZE
910 : #define MAP_MEMOIZE 0
911 : #endif
912 :
913 : /* If MAP_MEMOIZE is non-zero, MAP_MEMO is the memo element field.
914 : Should be a ulong. Like MAP_KEY and MAP_NEXT, when an element is in
915 : the map, this value is managed by the map and will contain the
916 : MAP_KEY_HASH of the element's key and the map's seed. */
917 :
918 : #ifndef MAP_MEMO
919 : #define MAP_MEMO memo
920 : #endif
921 :
922 : /* If MAP_MEMOIZE is defined to non-zero, a non-zero MAP_KEY_EQ_IS_SLOW
923 : indicates the MAP_MEMO field should be used to accelerate MAP_KEY_EQ
924 : operations. This is useful when MAP_KEY_EQ is non-trivial (e.g.
925 : variable length string compare, large buffer compares, etc). */
926 :
927 : #ifndef MAP_KEY_EQ_IS_SLOW
928 : #define MAP_KEY_EQ_IS_SLOW 0
929 : #endif
930 :
931 : /* MAP_ELE_IS_FREE returns 0/1 if the slot pointed to by ele in the
932 : caller's address space contains / does not contain a key-value pair.
933 : The implementation can assume ele is valid and that it is safe to
934 : speculate on ele. The default implementation tests if key is not 0.
935 : If using a different key sentinel or not using a key sentinel, update
936 : this appropriately. */
937 :
938 : #ifndef MAP_ELE_IS_FREE
939 : #define MAP_ELE_IS_FREE(ctx,ele) (!((ele)->MAP_KEY))
940 : #endif
941 :
942 : /* MAP_ELE_FREE frees the key-value pair in the slot pointed to by ele
943 : in the caller's address space. The implementation can assume ele is
944 : valid, ele contains a key-value pair on entry and there will be no
945 : concurrent operations on ele during the free. The default
946 : implementation sets key to 0. If using a different key sentinel or
947 : not using a key sentinel, update this appropriately. Likewise, if
948 : not using plain-old-data keys and values, this should do the
949 : appropriate resource management. The join ctx is provided to
950 : facilitate this. */
951 :
952 : #ifndef MAP_ELE_FREE
953 : #define MAP_ELE_FREE(ctx,ele) do (ele)->MAP_KEY = (MAP_KEY_T)0; while(0)
954 : #endif
955 :
956 : /* MAP_ELE_MOVE moves the key-value pair in slot src to slot dst.
957 : src and dst are in the caller's address space. The implementation
958 : can assume src and dst are valid, dst does not contain a key-value
959 : pair on entry, src contains a key-value on pair on entry, and there
960 : will be no concurrent operations on src and dst during the move. The
961 : default implementation shallow copies src to dst and sets src key to
962 : 0. If using a different key sentinel or not using a key sentinel,
963 : update this appropriately. Likewise, if elements do not use
964 : plain-old-data keys and/or values, this should do the appropriate key
965 : and/or value resource management. The join ctx is provided to
966 : facilitate this. */
967 :
968 : #ifndef MAP_ELE_MOVE
969 : #define MAP_ELE_MOVE(ctx,dst,src) do { MAP_ELE_T * _src = (src); (*(dst)) = *_src; _src->MAP_KEY = (MAP_KEY_T)0; } while(0)
970 : #endif
971 :
972 : /* MAP_KEY_FROM_ELE returns a MAP_KEY_T const * to the key for element
973 : ele. The join ctx is provided to facilitate indirect key lookups
974 : (e.g. the key data lives in an external pool, and the element
975 : stores an index into that pool). The default returns the address
976 : of the MAP_KEY field in the element. */
977 :
978 : #ifndef MAP_KEY_FROM_ELE
979 13025082 : #define MAP_KEY_FROM_ELE(ctx,ele) (&(ele)->MAP_KEY)
980 : #endif
981 :
982 : /* MAP_CTX_MAX specifies the maximum number of bytes of user context
983 : for use in MAP_ELE above (e.g. custom allocators / workspaces / local
984 : pointers to additional value arrays / etc). This context will be
985 : ulong aligned. Default is up to 72 bytes. */
986 :
987 : #ifndef MAP_CTX_MAX
988 5622555 : #define MAP_CTX_MAX (72UL)
989 : #endif
990 :
991 : /* MAP_VERSION_T gives the map version index type. Should be a
992 : primitive unsigned integer type. The least significant bit is used
993 : to indicate whether or not a slot could be impacted by an in progress
994 : map operation. The remaining bits indicate the version number. The
995 : default is ulong, yielding effectively infinite ABA protection (e.g.
996 : a lockfree query operation would need to be stalled for over ~2^63
997 : concurrent insert/modify/remove map operations before risk of getting
998 : confused by version number reuse ... which would take millennia for
999 : modern hardware practically). Narrow types yield less metadata
1000 : footprint overhead for the map and lower ABA protection. (For human
1001 : hard real-time applications, uint is probably fine and, in for
1002 : computer hard computer real-time applications, ushort and/or uchar
1003 : could be fine). */
1004 :
1005 : #ifndef MAP_VERSION_T
1006 209136240 : #define MAP_VERSION_T ulong
1007 : #endif
1008 :
1009 : /* MAP_LOCK_MAX gives the maximum number of version locks the map can
1010 : support. This should be positive and an integer power-of-two. This
1011 : essentially is limit on the maximum number of concurrent operations
1012 : and thus should be much greater than the number of concurrent
1013 : insert/modify/remove operations in expected map usage. Default is
1014 : 1024.
1015 :
1016 : Note that this is not theoretically required for the below
1017 : implementation. This exists to compile time bound stack utilization
1018 : of prepare/remove/query_try. That is,
1019 : sizeof(MAP_VERSION_T)*MAP_LOCK_MAX should be a L1D cache / L2D cache
1020 : / stack allocation friendly footprint (defaults yield 8 KiB).
1021 : MAP_LOCK_MAX could be removed by using an dynamic stack allocation
1022 : but that would limit this to targets with FD_HAS_ALLOCA. Could also
1023 : be eliminated by using a dynamic footprint lock cache in the query
1024 : structure, join structures and/or combining the query and join
1025 : structures. These are cumbersome for the user and the last two add
1026 : restrictions to intra-process multithreaded usage not seen in other
1027 : FD persistent inter-process datastructures. (Consider using a
1028 : massive/reasonable MAP_LOCK_MAX when FD_HAS_ALLOCA is set/clear and
1029 : then using alloca in prepare/remove/query_try when FD_HAS_ALLOCA is
1030 : set? Almost the best of both worlds but does imply some subtle
1031 : restrictions if trying to interoperate between targets compiled with
1032 : different features ... avoiding for now.) */
1033 :
1034 : #ifndef MAP_LOCK_MAX
1035 3000057 : #define MAP_LOCK_MAX (1024)
1036 : #endif
1037 :
1038 : /* MAP_ALIGN gives the alignment required for the map shared memory.
1039 : Default is 128 for double cache line alignment. Should be at least
1040 : ulong alignment. */
1041 :
1042 : #ifndef MAP_ALIGN
1043 : #define MAP_ALIGN (128UL)
1044 : #endif
1045 :
1046 : /* MAP_MAGIC gives the shared memory magic number to aid in persistent
1047 : and/or interprocess usage. */
1048 :
1049 : #ifndef MAP_MAGIC
1050 6 : #define MAP_MAGIC (0xf17eda2c37c5107UL) /* firedancer cslot version 0 */
1051 : #endif
1052 :
1053 : /* MAP_IMPL_STYLE controls what to generate:
1054 : 0 - header only library
1055 : 1 - library header declaration
1056 : 2 - library implementation */
1057 :
1058 : #ifndef MAP_IMPL_STYLE
1059 : #define MAP_IMPL_STYLE 0
1060 : #endif
1061 :
1062 : /* Implementation *****************************************************/
1063 :
1064 : #if MAP_IMPL_STYLE==0 /* local use only */
1065 : #define MAP_STATIC FD_FN_UNUSED static
1066 : #else /* library header and/or implementation */
1067 : #define MAP_STATIC
1068 : #endif
1069 :
1070 187013649 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
1071 :
1072 : #if MAP_IMPL_STYLE!=2 /* need header */
1073 :
1074 : #include "../bits/fd_bits.h"
1075 :
1076 : struct __attribute__((aligned(MAP_ALIGN))) MAP_(shmem_private) {
1077 :
1078 : /* This point is MAP_ALIGN aligned */
1079 :
1080 : ulong magic; /* ==MAP_MAGIC */
1081 : ulong ele_max; /* Element store capacity, positive and an integer power-of-two */
1082 : ulong lock_cnt; /* Number of locks, positive and an integer power-of-two <= min( ele_max, MAP_LOCK_MAX ) */
1083 : ulong probe_max; /* Maximum length probe sequence, in [1,ele_max] */
1084 : ulong seed; /* Key hash seed, arbitrary */
1085 : int lock_shift; /* log2( ele_max / lock_cnt ), non-negative */
1086 :
1087 : /* Padding to MAP_ALIGN alignment here */
1088 :
1089 : /* MAP_VERSION_T lock[ lock_cnt ] here (obligatory sigh about lagging
1090 : C++ support for 0 sized structure array footers). */
1091 :
1092 : /* Padding to MAP_ALIGN alignment here */
1093 : };
1094 :
1095 : typedef struct MAP_(shmem_private) MAP_(shmem_t);
1096 :
1097 : struct MAP_(private) {
1098 : MAP_ELE_T * ele; /* Location of the element store in the local address space, indexed [0,ele_max) */
1099 : MAP_VERSION_T * lock; /* Location of the lock versions in the local address space, indexed [0,lock_cnt) */
1100 : ulong ele_max; /* ==shmem->ele_max */
1101 : ulong lock_cnt; /* ==shmem->lock_cnt */
1102 : ulong probe_max; /* ==shmem->probe_max */
1103 : ulong seed; /* ==shmem->seed */
1104 : int lock_shift; /* ==shmem->lock_shift */
1105 : int _pad; /* padding to ulong alignment */
1106 : uchar ctx[ MAP_CTX_MAX ]; /* User context for MAP_ELE_IS_FREE/MAP_ELE_FREE/MAP_ELE_MOVE */
1107 : };
1108 :
1109 : typedef struct MAP_(private) MAP_(t);
1110 :
1111 : struct MAP_(query_private) {
1112 : ulong memo; /* Query key memo */
1113 : MAP_ELE_T * ele; /* Query element in the local address space */
1114 : MAP_VERSION_T * l; /* Lock needed for this query in the local address space */
1115 : MAP_VERSION_T v; /* Version of lock at query start */
1116 : };
1117 :
1118 : typedef struct MAP_(query_private) MAP_(query_t);
1119 :
1120 : struct MAP_(iter_private) {
1121 : MAP_ELE_T * ele; /* Location of the element store in the local address space, indexed [0,ele_max) */
1122 : MAP_VERSION_T * lock; /* Location of the lock versions in the local address space, indexed [0,lock_cnt) */
1123 : ulong ele_max; /* ==shmem->ele_max */
1124 : ulong lock_cnt; /* ==shmem->lock_cnt */
1125 : ulong seed; /* ==shmem->seed */
1126 : ulong memo; /* matching memo for iteration */
1127 : ulong ele_idx; /* If ele_rem>0, current matching element, ignored otherwise */
1128 : ulong ele_rem; /* Number of elements remaining to probe, in [0,probe_max] */
1129 : ulong version_lock0; /* Index of first lock used by this iter, in [0,lock_cnt] */
1130 : ulong version_cnt; /* Number of locks used by this iter, in [0,lock_cnt] (typically 1) */
1131 : uchar ctx[ MAP_CTX_MAX ]; /* User context for MAP_KEY_FROM_ELE */
1132 : MAP_VERSION_T version[ MAP_LOCK_MAX ]; /* Direct mapped cache of version numbers for unlock */
1133 : };
1134 :
1135 : typedef struct MAP_(iter_private) MAP_(iter_t);
1136 :
1137 : FD_PROTOTYPES_BEGIN
1138 :
1139 : /* map_private_try returns the version of the lock observed at some
1140 : point during the call. Assumes lock is valid. If the least
1141 : significant bit of the returned value is set (i.e. is odd), an
1142 : operation was in progress on a key whose probe sequence includes a
1143 : map slot covered by this lock (i.e. it is not a good time to try the
1144 : operation). If the LSB is clear (i.e. is even), no operation was in
1145 : progress (i.e. it is a good time to try). This is a compiler memory
1146 : fence. */
1147 :
1148 : static inline MAP_VERSION_T
1149 12010335 : MAP_(private_try)( MAP_VERSION_T volatile const * l ) {
1150 12010335 : MAP_VERSION_T v;
1151 12010335 : FD_COMPILER_MFENCE();
1152 12010335 : v = *l;
1153 12010335 : FD_COMPILER_MFENCE();
1154 12010335 : return v;
1155 12010335 : }
1156 :
1157 : /* map_private_test tests a range of lock versions matched their locally
1158 : cached versions at some point during the call. Specifically, tests
1159 : lock[lock_idx]==version[lock_idx] for all lock_idx in
1160 : [version_lock0,version_lock0+version_cnt) (cyclic). lock_cnt is the
1161 : number of locks and assumed to be positive and an integer
1162 : power-of-two. Returns SUCCESS (zero) if all match (i.e. no probe
1163 : sequences through slots covered by the locks between when the last
1164 : lock in the range was observed and this was called changed) and AGAIN
1165 : (negative) otherwise. This is a compiler memory fence. */
1166 :
1167 : static inline int
1168 : MAP_(private_test)( MAP_VERSION_T volatile const * lock,
1169 : ulong lock_cnt,
1170 : MAP_VERSION_T const * version,
1171 : ulong lock_idx, /* version_lock0 */
1172 5615946 : ulong version_cnt ) {
1173 5615946 : FD_COMPILER_MFENCE();
1174 11767713 : for( ; version_cnt; version_cnt-- ) {
1175 6151767 : if( FD_UNLIKELY( lock[ lock_idx ]!=version[ lock_idx ] ) ) break; /* opt for low contention */
1176 6151767 : lock_idx = (lock_idx+1UL) & (lock_cnt-1UL);
1177 6151767 : }
1178 5615946 : FD_COMPILER_MFENCE();
1179 5615946 : return version_cnt ? FD_MAP_ERR_AGAIN : FD_MAP_SUCCESS; /* cmov */
1180 5615946 : }
1181 :
1182 : /* map_private_lock returns the version of the lock observed at some
1183 : point during the call. Assumes lock is valid. If the least
1184 : significant bit of the returned version is set (i.e. is odd), the
1185 : caller did not get the lock (i.e. an operation was already in
1186 : progress on a key whose probe sequence includes a map slot covered by
1187 : this lock). If the LSB is clear (i.e. is even), the caller got the
1188 : lock (i.e. is free to do an operation involving probe sequences that
1189 : pass through the range covered by the lock) and *lock LSB was set.
1190 : This is a compiler memory fence. When the target does not have
1191 : FD_HAS_ATOMIC, this operation is emulated. When emulated, the map
1192 : will not be safe to use concurrently but will still work with
1193 : comparable performance to a serial implementation. */
1194 :
1195 : static inline MAP_VERSION_T
1196 60325158 : MAP_(private_lock)( MAP_VERSION_T volatile * l ) {
1197 60325158 : MAP_VERSION_T v;
1198 60325158 : FD_COMPILER_MFENCE();
1199 : # if FD_HAS_ATOMIC /* test-and-test-and-set style */
1200 60325158 : v = *l;
1201 60325158 : if( FD_LIKELY( !((ulong)v & 1UL) ) ) v = FD_ATOMIC_FETCH_AND_OR( l, (MAP_VERSION_T)1 ); /* opt for low contention */
1202 : # else
1203 : v = *l;
1204 : *l = (MAP_VERSION_T)((ulong)v | 1UL);
1205 : # endif
1206 60325158 : FD_COMPILER_MFENCE();
1207 60325158 : return v;
1208 60325158 : }
1209 :
1210 : /* map_private_unlock unlocks lock[lock_idx] for lock_idx in
1211 : [version_lock0,version_lock0+version_cnt) (cyclic). Assumes
1212 : version[lock_idx] is the version the caller wants post unlock (which
1213 : implies that, on entry, version[lock_idx] = lock[lock_idx] + delta
1214 : where delta is odd and >=-1 (the -1 case corresponds "unlock with no
1215 : changes made to the covered elements"). This cannot fail. This is a
1216 : compiler memory fence. */
1217 :
1218 : static inline void
1219 : MAP_(private_unlock)( MAP_VERSION_T volatile * lock,
1220 : ulong lock_cnt,
1221 : MAP_VERSION_T const * version,
1222 : ulong lock_idx, /* version_lock0 */
1223 44987652 : ulong version_cnt ) {
1224 44987652 : FD_COMPILER_MFENCE();
1225 82803999 : for( ; version_cnt; version_cnt-- ) {
1226 37816347 : lock[ lock_idx ] = version[ lock_idx ];
1227 37816347 : lock_idx = (lock_idx+1UL) & (lock_cnt-1UL);
1228 37816347 : }
1229 44987652 : FD_COMPILER_MFENCE();
1230 44987652 : }
1231 :
1232 : /* map_private_ele_{is_free,free,move} expose the
1233 : MAP_ELE_{IS_FREE,FREE,MOVE} macros as inlines with strict semantics.
1234 :
1235 : map_private_ele_is_free returns 1 if ele does not contain a key-val
1236 : pair and 0 otherwise. ctx will be the join's user context, ele will
1237 : be a valid pointer to an element store element in the caller's
1238 : address space that is safe to speculate on. Retains no interest in
1239 : ele.
1240 :
1241 : map_private_ele_free frees any key and/or val resources used by ele
1242 : and marks ele as free. ctx will be the join's user context, ele will
1243 : be a valid pointer to an element store element in the caller's
1244 : address space that is marked as used. Retains no interest in ele.
1245 :
1246 : map_private_ele_move moves the key-val pair from element src to
1247 : element dst and marks src as free. ctx will be the join's user
1248 : context, src/dst will be a valid pointers to an element store element
1249 : in the caller's address space. dst/src will be marked as free/used
1250 : on entry and should be marked as used/free on return. Retains no
1251 : interest in dst or src. */
1252 :
1253 : FD_FN_PURE static inline int
1254 : MAP_(private_ele_is_free)( void const * ctx,
1255 79457385 : MAP_ELE_T const * ele ) {
1256 79457385 : (void)ctx;
1257 79457385 : return !!(MAP_ELE_IS_FREE( (ctx), (ele) ));
1258 79457385 : }
1259 :
1260 : static inline void
1261 : MAP_(private_ele_free)( void * ctx,
1262 5625612 : MAP_ELE_T * ele ) {
1263 5625612 : (void)ctx;
1264 5625612 : MAP_ELE_FREE( (ctx), (ele) );
1265 1875204 : }
1266 :
1267 : static inline void
1268 : MAP_(private_ele_move)( void * ctx,
1269 : MAP_ELE_T * dst,
1270 513120 : MAP_ELE_T * src ) {
1271 513120 : (void)ctx;
1272 513120 : MAP_ELE_MOVE( (ctx), (dst), (src) );
1273 170652 : }
1274 :
1275 12 : FD_FN_CONST static inline ulong MAP_(lock_max)( void ) { return MAP_LOCK_MAX; }
1276 :
1277 3000009 : FD_FN_CONST static inline ulong MAP_(lock_cnt_est) ( ulong ele_max ) { return fd_ulong_min( ele_max, MAP_LOCK_MAX ); }
1278 3000009 : FD_FN_CONST static inline ulong MAP_(probe_max_est)( ulong ele_max ) { return ele_max; }
1279 :
1280 336 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(shmem_t)); }
1281 :
1282 : FD_FN_CONST static inline ulong
1283 : MAP_(footprint)( ulong ele_max,
1284 : ulong lock_cnt,
1285 48 : ulong probe_max ) {
1286 48 : if( !( fd_ulong_is_pow2( ele_max ) &
1287 48 : fd_ulong_is_pow2( lock_cnt ) & (lock_cnt<=fd_ulong_min( ele_max, MAP_LOCK_MAX )) &
1288 48 : (1UL<=probe_max) & (probe_max<=ele_max) ) ) return 0UL;
1289 18 : return fd_ulong_align_up( sizeof(MAP_(shmem_t)) + lock_cnt*sizeof(MAP_VERSION_T), alignof(MAP_(shmem_t)) ); /* no overflow */
1290 48 : }
1291 :
1292 15 : FD_FN_PURE static inline ulong MAP_(ele_max) ( MAP_(t) const * join ) { return join->ele_max; }
1293 12 : FD_FN_PURE static inline ulong MAP_(lock_cnt) ( MAP_(t) const * join ) { return join->lock_cnt; }
1294 3 : FD_FN_PURE static inline ulong MAP_(probe_max)( MAP_(t) const * join ) { return join->probe_max; }
1295 15 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return join->seed; }
1296 :
1297 3 : FD_FN_PURE static inline void const * MAP_(shmap_const)( MAP_(t) const * join ) { return ((MAP_(shmem_t) const *)join->lock)-1; }
1298 3 : FD_FN_PURE static inline void const * MAP_(shele_const)( MAP_(t) const * join ) { return join->ele; }
1299 :
1300 3 : FD_FN_CONST static inline void * MAP_(ctx) ( MAP_(t) * join ) { return join->ctx; }
1301 3 : FD_FN_CONST static inline void const * MAP_(ctx_const)( MAP_(t) const * join ) { return join->ctx; }
1302 3 : FD_FN_CONST static inline ulong MAP_(ctx_max) ( MAP_(t) const * join ) { (void)join; return MAP_CTX_MAX; }
1303 :
1304 3 : FD_FN_PURE static inline void * MAP_(shmap)( MAP_(t) * join ) { return ((MAP_(shmem_t) *)join->lock)-1; }
1305 15 : FD_FN_PURE static inline void * MAP_(shele)( MAP_(t) * join ) { return join->ele; }
1306 :
1307 12288 : FD_FN_PURE static inline ulong MAP_(ele_lock) ( MAP_(t) const * join, ulong ele_idx ) { return ele_idx >> join->lock_shift; }
1308 11208219 : FD_FN_PURE static inline ulong MAP_(lock_ele0)( MAP_(t) const * join, ulong lock_idx ) { return lock_idx << join->lock_shift; }
1309 11208219 : FD_FN_PURE static inline ulong MAP_(lock_ele1)( MAP_(t) const * join, ulong lock_idx ) { return (lock_idx+1UL) << join->lock_shift; }
1310 :
1311 : FD_FN_PURE static inline int
1312 : MAP_(key_eq)( MAP_KEY_T const * k0,
1313 38725677 : MAP_KEY_T const * k1 ) {
1314 38725677 : return !!(MAP_KEY_EQ( (k0), (k1) ));
1315 38725677 : }
1316 :
1317 : FD_FN_PURE static inline ulong
1318 : MAP_(key_hash)( MAP_KEY_T const * key,
1319 93709515 : ulong seed ) {
1320 93709515 : return (MAP_KEY_HASH( (key), (seed) ));
1321 93709515 : }
1322 :
1323 : static inline void
1324 : MAP_(backoff)( ulong scale,
1325 0 : ulong seed ) {
1326 0 : ulong r = (ulong)(uint)fd_ulong_hash( seed ^ (((ulong)fd_tickcount())<<32) );
1327 0 : for( ulong rem=(scale*r)>>48; rem; rem-- ) FD_SPIN_PAUSE();
1328 0 : }
1329 :
1330 56230416 : FD_FN_PURE static inline ulong MAP_(query_memo )( MAP_(query_t) const * query ) { return query->memo; }
1331 11234070 : FD_FN_PURE static inline MAP_ELE_T const * MAP_(query_ele_const)( MAP_(query_t) const * query ) { return query->ele; }
1332 22508811 : FD_FN_PURE static inline MAP_ELE_T * MAP_(query_ele )( MAP_(query_t) * query ) { return query->ele; }
1333 :
1334 : static inline void
1335 11248263 : MAP_(publish)( MAP_(query_t) * query ) {
1336 11248263 : MAP_VERSION_T volatile * l = query->l;
1337 11248263 : MAP_VERSION_T v = (MAP_VERSION_T)((ulong)query->v + 2UL);
1338 11248263 : FD_COMPILER_MFENCE();
1339 11248263 : *l = v;
1340 11248263 : FD_COMPILER_MFENCE();
1341 11248263 : }
1342 :
1343 : static inline void
1344 11260548 : MAP_(cancel)( MAP_(query_t) * query ) {
1345 11260548 : MAP_VERSION_T volatile * l = query->l;
1346 11260548 : MAP_VERSION_T v = query->v;
1347 11260548 : FD_COMPILER_MFENCE();
1348 11260548 : *l = v;
1349 11260548 : FD_COMPILER_MFENCE();
1350 11260548 : }
1351 :
1352 : static inline int
1353 5618124 : MAP_(query_test)( MAP_(query_t) const * query ) {
1354 5618124 : MAP_VERSION_T volatile const * l = query->l;
1355 5618124 : ulong v = query->v;
1356 5618124 : FD_COMPILER_MFENCE();
1357 5618124 : ulong _v = *l;
1358 5618124 : FD_COMPILER_MFENCE();
1359 5618124 : return _v==v ? FD_MAP_SUCCESS : FD_MAP_ERR_AGAIN;
1360 5618124 : }
1361 :
1362 : static inline void
1363 : MAP_(unlock_range)( MAP_(t) * join,
1364 : ulong range_start,
1365 : ulong range_cnt,
1366 5609781 : MAP_VERSION_T const * version ) {
1367 5609781 : MAP_(private_unlock)( join->lock, join->lock_cnt, version, range_start, range_cnt );
1368 5609781 : }
1369 :
1370 11238525 : FD_FN_PURE static inline int MAP_(iter_done)( MAP_(iter_t) * iter ) { return !iter->ele_rem; }
1371 5615973 : FD_FN_PURE static inline MAP_ELE_T * MAP_(iter_ele) ( MAP_(iter_t) * iter ) { return iter->ele + iter->ele_idx; }
1372 :
1373 : static inline MAP_(iter_t) *
1374 5622552 : MAP_(iter_fini)( MAP_(iter_t) * iter ) {
1375 5622552 : MAP_(private_unlock)( iter->lock, iter->lock_cnt, iter->version, iter->version_lock0, iter->version_cnt );
1376 5622552 : return iter;
1377 5622552 : }
1378 :
1379 : MAP_STATIC void * MAP_(new) ( void * shmem, ulong ele_max, ulong lock_cnt, ulong probe_max, ulong seed );
1380 : MAP_STATIC MAP_(t) * MAP_(join) ( void * ljoin, void * shmap, void * shele );
1381 : MAP_STATIC void * MAP_(leave) ( MAP_(t) * join );
1382 : MAP_STATIC void * MAP_(delete)( void * shmap );
1383 :
1384 : MAP_STATIC void
1385 : MAP_(hint)( MAP_(t) const * join,
1386 : MAP_KEY_T const * key,
1387 : MAP_(query_t) * query,
1388 : int flags );
1389 :
1390 : MAP_STATIC int
1391 : MAP_(prepare)( MAP_(t) * join,
1392 : MAP_KEY_T const * key,
1393 : MAP_ELE_T * sentinel,
1394 : MAP_(query_t) * query,
1395 : int flags );
1396 :
1397 : MAP_STATIC int
1398 : MAP_(remove)( MAP_(t) * join,
1399 : MAP_KEY_T const * key,
1400 : MAP_(query_t) const * query,
1401 : int flags );
1402 :
1403 : MAP_STATIC int
1404 : MAP_(query_try)( MAP_(t) const * join,
1405 : MAP_KEY_T const * key,
1406 : MAP_ELE_T const * sentinel,
1407 : MAP_(query_t) * query,
1408 : int flags );
1409 :
1410 : /* FIXME: Consider adding txn API too? Would work recording the start
1411 : of probe sequences for keys in the transaction and then the txn_try
1412 : would use a bitfield to lock all contiguous regions covered by the
1413 : set of probe sequences. */
1414 :
1415 : MAP_STATIC int
1416 : MAP_(lock_range)( MAP_(t) * join,
1417 : ulong range_start,
1418 : ulong range_cnt,
1419 : int flags,
1420 : MAP_VERSION_T * version );
1421 :
1422 : MAP_STATIC int
1423 : MAP_(iter_init)( MAP_(t) * join,
1424 : ulong memo,
1425 : int flags,
1426 : MAP_(iter_t) * iter );
1427 :
1428 : MAP_STATIC MAP_(iter_t) *
1429 : MAP_(iter_next)( MAP_(iter_t) * iter );
1430 :
1431 : MAP_STATIC int MAP_(verify)( MAP_(t) const * join );
1432 :
1433 : MAP_STATIC FD_FN_CONST char const * MAP_(strerror)( int err );
1434 :
1435 : FD_PROTOTYPES_END
1436 :
1437 : #endif
1438 :
1439 : #if MAP_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
1440 :
1441 : #include "../log/fd_log.h" /* Used by constructors and verify (FIXME: Consider making a compile time option) */
1442 :
1443 : MAP_STATIC void *
1444 : MAP_(new)( void * shmem,
1445 : ulong ele_max,
1446 : ulong lock_cnt,
1447 : ulong probe_max,
1448 30 : ulong seed ) {
1449 :
1450 30 : if( FD_UNLIKELY( !shmem ) ) {
1451 3 : FD_LOG_WARNING(( "NULL shmem" ));
1452 3 : return NULL;
1453 3 : }
1454 :
1455 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) {
1456 3 : FD_LOG_WARNING(( "misaligned shmem" ));
1457 3 : return NULL;
1458 3 : }
1459 :
1460 24 : ulong footprint = MAP_(footprint)( ele_max, lock_cnt, probe_max );
1461 24 : if( FD_UNLIKELY( !footprint ) ) {
1462 15 : FD_LOG_WARNING(( "ele_max, lock_cnt and/or probe_max" ));
1463 15 : return NULL;
1464 15 : }
1465 :
1466 : /* seed arbitrary */
1467 :
1468 : /* Init the metadata */
1469 :
1470 9 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmem;
1471 :
1472 9 : memset( map, 0, footprint );
1473 :
1474 9 : map->ele_max = ele_max;
1475 9 : map->lock_cnt = lock_cnt;
1476 9 : map->probe_max = probe_max;
1477 9 : map->seed = seed;
1478 9 : map->lock_shift = fd_ulong_find_msb( ele_max ) - fd_ulong_find_msb( lock_cnt );
1479 :
1480 : /* Note: memset set all the locks to version 0/unlocked */
1481 :
1482 : /* Note: caller set all elements in underlying element store set to
1483 : free (or, more pedantically, to a key-val pair configuration
1484 : consistent with ele_max and probe_max). */
1485 :
1486 9 : FD_COMPILER_MFENCE();
1487 9 : map->magic = MAP_MAGIC;
1488 9 : FD_COMPILER_MFENCE();
1489 :
1490 9 : return shmem;
1491 24 : }
1492 :
1493 : MAP_STATIC MAP_(t) *
1494 : MAP_(join)( void * ljoin,
1495 : void * shmap,
1496 30 : void * shele ) {
1497 30 : MAP_(t) * join = (MAP_(t) *)ljoin;
1498 30 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmap;
1499 30 : MAP_ELE_T * ele = (MAP_ELE_T *)shele;
1500 :
1501 30 : if( FD_UNLIKELY( !join ) ) {
1502 3 : FD_LOG_WARNING(( "NULL ljoin" ));
1503 3 : return NULL;
1504 3 : }
1505 :
1506 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(MAP_(t)) ) ) ) {
1507 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
1508 3 : return NULL;
1509 3 : }
1510 :
1511 24 : if( FD_UNLIKELY( !map ) ) {
1512 3 : FD_LOG_WARNING(( "NULL shmap" ));
1513 3 : return NULL;
1514 3 : }
1515 :
1516 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
1517 3 : FD_LOG_WARNING(( "misaligned shmap" ));
1518 3 : return NULL;
1519 3 : }
1520 :
1521 18 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
1522 3 : FD_LOG_WARNING(( "bad magic" ));
1523 3 : return NULL;
1524 3 : }
1525 :
1526 15 : if( FD_UNLIKELY( !ele ) ) {
1527 3 : FD_LOG_WARNING(( "NULL shele" ));
1528 3 : return NULL;
1529 3 : }
1530 :
1531 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(MAP_ELE_T) ) ) ) {
1532 3 : FD_LOG_WARNING(( "misaligned shele" ));
1533 3 : return NULL;
1534 3 : }
1535 :
1536 9 : join->lock = (MAP_VERSION_T *)(map+1);
1537 9 : join->ele = ele;
1538 9 : join->ele_max = map->ele_max;
1539 9 : join->lock_cnt = map->lock_cnt;
1540 9 : join->probe_max = map->probe_max;
1541 9 : join->seed = map->seed;
1542 9 : join->lock_shift = map->lock_shift;
1543 :
1544 9 : return join;
1545 12 : }
1546 :
1547 : MAP_STATIC void *
1548 12 : MAP_(leave)( MAP_(t) * join ) {
1549 :
1550 12 : if( FD_UNLIKELY( !join ) ) {
1551 3 : FD_LOG_WARNING(( "NULL join" ));
1552 3 : return NULL;
1553 3 : }
1554 :
1555 9 : return (void *)join;
1556 12 : }
1557 :
1558 : MAP_STATIC void *
1559 18 : MAP_(delete)( void * shmap ) {
1560 18 : MAP_(shmem_t) * map = (MAP_(shmem_t) *)shmap;
1561 :
1562 18 : if( FD_UNLIKELY( !map ) ) {
1563 3 : FD_LOG_WARNING(( "NULL shmap" ));
1564 3 : return NULL;
1565 3 : }
1566 :
1567 15 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
1568 3 : FD_LOG_WARNING(( "misaligned shmap" ));
1569 3 : return NULL;
1570 3 : }
1571 :
1572 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
1573 3 : FD_LOG_WARNING(( "bad magic" ));
1574 3 : return NULL;
1575 3 : }
1576 :
1577 9 : FD_COMPILER_MFENCE();
1578 9 : map->magic = 0UL;
1579 9 : FD_COMPILER_MFENCE();
1580 :
1581 9 : return (void *)map;
1582 12 : }
1583 :
1584 : void
1585 : MAP_(hint)( MAP_(t) const * join,
1586 : MAP_KEY_T const * key,
1587 : MAP_(query_t) * query,
1588 22487535 : int flags ) {
1589 22487535 : MAP_ELE_T const * ele0 = join->ele;
1590 22487535 : MAP_VERSION_T const * lock = join->lock;
1591 22487535 : ulong ele_max = join->ele_max;
1592 22487535 : ulong seed = join->seed;
1593 22487535 : int lock_shift = join->lock_shift;
1594 :
1595 22487535 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, seed );
1596 22487535 : ulong ele_idx = memo & (ele_max-1UL);
1597 22487535 : ulong lock_idx = ele_idx >> lock_shift;
1598 :
1599 : /* TODO: target specific prefetch hints */
1600 22487535 : if( FD_LIKELY( flags & FD_MAP_FLAG_PREFETCH_META ) ) FD_VOLATILE_CONST( lock[ lock_idx ] );
1601 22487535 : if( FD_LIKELY( flags & FD_MAP_FLAG_PREFETCH_DATA ) ) FD_VOLATILE_CONST( ele0[ ele_idx ] );
1602 :
1603 22487535 : query->memo = memo;
1604 22487535 : }
1605 :
1606 : int
1607 : MAP_(prepare)( MAP_(t) * join,
1608 : MAP_KEY_T const * key,
1609 : MAP_ELE_T * sentinel,
1610 : MAP_(query_t) * query,
1611 22508811 : int flags ) {
1612 22508811 : MAP_ELE_T * ele0 = join->ele;
1613 22508811 : MAP_VERSION_T * lock = join->lock;
1614 22508811 : ulong ele_max = join->ele_max;
1615 22508811 : ulong lock_cnt = join->lock_cnt;
1616 22508811 : ulong probe_max = join->probe_max;
1617 22508811 : ulong seed = join->seed;
1618 22508811 : int lock_shift = join->lock_shift;
1619 22508811 : void * ctx = join->ctx;
1620 :
1621 22508811 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, seed );
1622 22508811 : ulong start_idx = memo & (ele_max-1UL);
1623 22508811 : ulong version_lock0 = start_idx >> lock_shift;
1624 :
1625 22508811 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
1626 22508811 : ulong backoff_max = (1UL<<32); /* in [2^32,2^48) */
1627 22508811 : ulong backoff_seed = ((ulong)(uint)flags)>>6; /* 0 usually fine */
1628 :
1629 22508811 : for(;;) { /* Fresh try */
1630 :
1631 22508811 : int err;
1632 :
1633 22508811 : MAP_VERSION_T version[ MAP_LOCK_MAX ];
1634 22508811 : ulong version_cnt = 0UL;
1635 22508811 : ulong lock_idx = version_lock0;
1636 :
1637 : /* At this point, finding any key in the map requires testing at
1638 : most probe_max contiguous slots. */
1639 :
1640 22508811 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
1641 22508811 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail; } /* opt for low contention */
1642 22508811 : version[ lock_idx ] = v;
1643 22508811 : version_cnt++;
1644 :
1645 22508811 : ulong ele_idx = start_idx;
1646 :
1647 25624827 : for( ulong probe_rem=probe_max; probe_rem; probe_rem-- ) {
1648 :
1649 : /* At this point, we've acquired the locks from the start of key's
1650 : probe sequence to ele_idx inclusive and have tested fewer than
1651 : probe_max slots for key.
1652 :
1653 : If slot ele_idx is empty, we know that the key is currently not
1654 : in the map and we can insert it here without creating a probe
1655 : sequence longer than probe_max. This does not lengthen the
1656 : probe sequence for any currently mapped keys, preserving the
1657 : maximum probe sequence length invariant. Further, this is at
1658 : the end of all keys that map to the same probe sequence start.
1659 : So, we have preserved the key group ordering invariant.
1660 :
1661 : On return, ele will be marked as free. To insert key into the
1662 : map, the caller should initialize the slot's key (and memo if
1663 : necessary), mark the slot as used, and publish to complete the
1664 : insert.
1665 :
1666 : If the caller doesn't want to insert anything (e.g. caller only
1667 : wants to modify an existing value), the caller should keep the
1668 : slot marked as free (doesn't matter how the caller modified any
1669 : other fields) and return the slot as free, and cancel to
1670 : complete the failed insert (publish would also work ... cancel
1671 : has theoretically lower risk of false contention).
1672 :
1673 : Likewise, if slot ele_idx contains key, we return that slot to
1674 : the caller. The caller can tell the difference between the
1675 : previous case because the slot will be marked as used.
1676 :
1677 : On return, the caller can modify the slot's value arbitrarily.
1678 : IMPORTANT SAFETY TIP! THE CALLER MUST NOT MODIFY THE SLOT'S KEY
1679 : OR MARK THE SLOT AS FREE. USE REMOVE BELOW TO REMOVE KEYS.
1680 : When done modifying the slot's value, the caller should either
1681 : publish or cancel depending on what the caller did to the
1682 : slot's value and how the application manages access to values
1683 : (publish is always safe but cancel when appropriate has
1684 : theoretically lower risk of false contention). Note that
1685 : cancel is not appropriate for temporary modifications to value
1686 : (because it can confuse query ABA protection).
1687 :
1688 : In both cases, since we have the lock that covers slot ele_idx,
1689 : we can unlock any other locks (typically the leading
1690 : version_cnt-1 but possibly the trailing version_cnt-1 in cases
1691 : with maps near capacity) locks already acquired to reduce
1692 : contention with other unrelated operations. That is, at this
1693 : point, lock lock_idx is sufficient to prevent any operation for
1694 : any key breaking key's probe sequence (because it would need to
1695 : acquire the lock covering ele_idx first). */
1696 :
1697 25624827 : MAP_ELE_T * ele = ele0 + ele_idx;
1698 :
1699 25624827 : if( FD_LIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) || /* opt for low collision */
1700 25624827 : (
1701 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1702 4785555 : FD_LIKELY( ele->MAP_MEMO==memo ) &&
1703 : # endif
1704 14367150 : FD_LIKELY( MAP_(key_eq)( MAP_KEY_FROM_ELE( ctx, ele ), key ) ) /* opt for already in map */
1705 22508811 : ) ) {
1706 :
1707 22508811 : lock_idx = ele_idx >> lock_shift;
1708 22508811 : version_lock0 = (version_lock0 + (ulong)(version_lock0==lock_idx)) & (lock_cnt-1UL);
1709 22508811 : MAP_(private_unlock)( lock, lock_cnt, version, version_lock0, version_cnt-1UL );
1710 :
1711 22508811 : query->memo = memo;
1712 22508811 : query->ele = ele;
1713 22508811 : query->l = lock + lock_idx;
1714 22508811 : query->v = version[ lock_idx ];
1715 22508811 : return FD_MAP_SUCCESS;
1716 22508811 : }
1717 :
1718 : /* At this point, slot ele_idx is used by something other than
1719 : key. If we still have probes remaining, continue probing for
1720 : key, locking as necessary. If we can't acquire a lock, we
1721 : fail. */
1722 :
1723 3116016 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
1724 :
1725 : /* FIXME: FURTHER RESTRICT TO PROBE_REM>1? */
1726 3116016 : ulong lock_next = ele_idx >> lock_shift;
1727 3116016 : if( FD_UNLIKELY( (lock_next!=lock_idx) & (lock_next!=version_lock0) ) ) { /* opt for locks that cover many contiguous slots */
1728 1561197 : lock_idx = lock_next;
1729 :
1730 1561197 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
1731 1561197 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail; } /* opt for low contention */
1732 1561197 : version[ lock_idx ] = v;
1733 1561197 : version_cnt++;
1734 1561197 : }
1735 3116016 : }
1736 :
1737 : /* At this point, we've done probe_max probes without encountering
1738 : key and we have all the locks. So we know key is not in the map
1739 : and that, even if we have space, inserting this key will create a
1740 : probe sequence longer than probe_max. That is, map is loaded
1741 : enough that we consider it full.
1742 :
1743 : If probe_max==ele_max, this meaning of full is the traditional
1744 : non-concurrent meaning of full (literally every slot is known to
1745 : be used). Even if probe_max << ele_max, it is possible to fill
1746 : every slot (e.g. at probe_max==1, a perfect hash of ele_max keys
1747 : to slot would fill every slot). */
1748 :
1749 0 : err = FD_MAP_ERR_FULL;
1750 :
1751 0 : fail:
1752 :
1753 0 : MAP_(private_unlock)( lock, lock_cnt, version, version_lock0, version_cnt );
1754 :
1755 0 : if( FD_UNLIKELY( non_blocking | (err!=FD_MAP_ERR_AGAIN) ) ) {
1756 0 : query->memo = memo;
1757 0 : query->ele = sentinel;
1758 0 : query->l = NULL;
1759 0 : query->v = (MAP_VERSION_T)0;
1760 0 : return err;
1761 0 : }
1762 :
1763 : /* At this point, we hit contention and are blocking (need to try
1764 : again). We do a random exponential backoff (with saturation on
1765 : wrapping) to minimize contention with other threads. Normalizing
1766 : out fixed point scalings baked into the below, we spin pause a
1767 : uniform IID random number of times in [0,backoff_max) where
1768 : backoff_max is 1 on the first hit and increases by ~30% each time
1769 : to a maximum of 2^16 (i.e. hundreds microseconds per remaining
1770 : lock for typical CPU speeds and spin pause delays at maximum
1771 : backoff). */
1772 :
1773 0 : ulong scale = backoff_max >> 16; /* in [2^16,2^32) */
1774 0 : backoff_max = fd_ulong_min( backoff_max + (backoff_max>>2) + (backoff_max>>4), (1UL<<48)-1UL ); /* in [2^32,2^48) */
1775 0 : MAP_(backoff)( scale, backoff_seed );
1776 :
1777 0 : }
1778 :
1779 : /* never get here */
1780 :
1781 22508811 : }
1782 :
1783 : int
1784 : MAP_(remove)( MAP_(t) * join,
1785 : MAP_KEY_T const * key,
1786 : MAP_(query_t) const * query,
1787 11246508 : int flags ) {
1788 :
1789 11246508 : MAP_VERSION_T * lock = join->lock;
1790 11246508 : ulong lock_cnt = join->lock_cnt;
1791 11246508 : ulong seed = join->seed;
1792 11246508 : ulong probe_max = join->probe_max;
1793 11246508 : MAP_ELE_T * ele0 = join->ele;
1794 11246508 : ulong ele_max = join->ele_max;
1795 11246508 : int lock_shift = join->lock_shift;
1796 11246508 : void * ctx = join->ctx;
1797 :
1798 11246508 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, seed );
1799 11246508 : ulong start_idx = memo & (ele_max-1UL);
1800 11246508 : ulong version_lock0 = start_idx >> lock_shift;
1801 :
1802 11246508 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
1803 11246508 : ulong backoff_max = (1UL<<32); /* in [2^32,2^48) */
1804 11246508 : ulong backoff_seed = ((ulong)(uint)flags)>>6; /* 0 usually fine */
1805 :
1806 11246508 : for(;;) { /* Fresh try */
1807 :
1808 11246508 : int err;
1809 :
1810 11246508 : MAP_VERSION_T version[ MAP_LOCK_MAX ];
1811 11246508 : ulong version_cnt = 0UL;
1812 11246508 : ulong lock_idx = version_lock0;
1813 :
1814 : /* At this point, we need to acquire locks covering the start of the
1815 : probe sequence through up to all contiguously used slots (and, if
1816 : the map is not completely full, the trailing empty slot). */
1817 :
1818 11246508 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
1819 11246508 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail; } /* opt for low contention */
1820 11246508 : version[ lock_idx ] = v;
1821 11246508 : version_cnt++;
1822 :
1823 11246508 : ulong ele_idx = start_idx;
1824 11246508 : ulong hole_idx = start_idx;
1825 11246508 : int found = 0;
1826 :
1827 11246508 : ulong contig_cnt;
1828 19976013 : for( contig_cnt=0UL; contig_cnt<ele_max; contig_cnt++ ) {
1829 :
1830 : /* At this point, we've acquired the locks covering slots
1831 : [start_idx,ele_idx] (cyclic) and have confirmed that the
1832 : contig_cnt slots [start_idx,ele_idx) (cyclic) are used.
1833 :
1834 : If slot ele_idx is empty, we are done probing.
1835 :
1836 : Otherwise, if we haven't found key yet, we test if slot ele_idx
1837 : contains key.
1838 :
1839 : We can optimize this further by noting that the key can only be
1840 : in the first probe_max probes and that when we don't find the
1841 : key, remove has nothing to do (such that we don't have to keep
1842 : probing for contiguous slots). */
1843 :
1844 19976013 : MAP_ELE_T const * ele = ele0 + ele_idx;
1845 :
1846 19976013 : if( FD_UNLIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) ) break; /* opt for first pass low collision */
1847 :
1848 8729505 : if( FD_LIKELY( !found ) ) { /* opt for first pass low collision */
1849 7177608 : if( FD_UNLIKELY( contig_cnt>=probe_max ) ) break; /* opt for first pass low collision */
1850 7177608 : found =
1851 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1852 2391282 : FD_LIKELY( ele->MAP_MEMO==memo ) &&
1853 : # endif
1854 7177608 : MAP_(key_eq)( MAP_KEY_FROM_ELE( ctx, ele ), key );
1855 7177608 : if( found ) hole_idx = ele_idx; /* cmov */
1856 7177608 : }
1857 :
1858 : /* Continue probing, locking as necessary. If we can't acquire a
1859 : lock, fail. */
1860 :
1861 8729505 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
1862 :
1863 8729505 : ulong lock_next = ele_idx >> lock_shift;
1864 8729505 : if( FD_UNLIKELY( (lock_next!=lock_idx) & (lock_next!=version_lock0) ) ) { /* opt for locks covering many contiguous slots */
1865 4365567 : lock_idx = lock_next;
1866 :
1867 4365567 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
1868 4365567 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail; } /* opt for low contention */
1869 4365567 : version[ lock_idx ] = v;
1870 4365567 : version_cnt++;
1871 4365567 : }
1872 8729505 : }
1873 :
1874 : /* At this point, if we haven't found the key, key did not exist in
1875 : the map at some point during the call. Release the locks and
1876 : tell the user the key was already removed. */
1877 :
1878 11246508 : if( FD_UNLIKELY( !found ) ) { err = FD_MAP_ERR_KEY; goto fail; }
1879 :
1880 : /* At this point, we have locks covering the contig_cnt used slots
1881 : starting from start_idx cyclic (and, if contig_cnt<ele_max, any
1882 : trailing empty slot). The key to remove is in this range at
1883 : hole_idx. Further, all probe sequences are intact. Make a hole
1884 : at hole_idx by freeing the key. Also update the cached lock
1885 : version to indicate "modified" when we unlock below. */
1886 :
1887 5625612 : MAP_(private_ele_free)( ctx, ele0 + hole_idx );
1888 :
1889 5625612 : lock_idx = hole_idx >> lock_shift;
1890 5625612 : version[ lock_idx ] = (MAP_VERSION_T)((ulong)version[ lock_idx ] + 2UL);
1891 :
1892 : /* When contig_cnt<ele_max, the trailing empty slot guarantees that
1893 : the just made hole didn't break any probe sequences for keys not
1894 : in the contig_cnt slots and that it didn't break any probe
1895 : sequences in [start_idx,hole_idx). Probe sequences for keys in
1896 : (hole_idx,start_idx+contig_cnt) (cyclic) might have been broken
1897 : though.
1898 :
1899 : We fix the first key with a broken probe sequence by moving it to
1900 : the hole just made. This fills the hole but makes a new hole
1901 : (and one closer to the empty trailing slot) in the process. As
1902 : this shortens the probe sequence for that key, this doesn't break
1903 : any probe length invariants. We are repeating this process until
1904 : we've fixed all the contiguous slots after hole_idx. (As an
1905 : additional optimization to reduce remove costs when map is nearly
1906 : full but probe_max << ele_max, we could exploit that only the
1907 : leading probe_max-1 slots after any created hole might have
1908 : broken probe sequences.)
1909 :
1910 : Unfortunately, when contig_cnt==ele_max, we no longer have this
1911 : guarantee. But we do have the entire map locked at this point.
1912 : And we know that probe sequences are intact starting from the
1913 : most recently created hole. If we verify enough to eventually
1914 : wrap back to most recently created hole, we know all probe
1915 : sequences are intact. Since fixing broken probe sequences in
1916 : this fashion always shortens them and there always will be one
1917 : hole in this process, verifying until we hit the most recently
1918 : made hole is guaranteed to terminate. Since there is only one
1919 : hole, it is sufficient to just test if the next slot to verify is
1920 : a hole.
1921 :
1922 : This test works just as well for the more common
1923 : contig_cnt<ele_max case (it will terminate at the preexisting
1924 : trailing empty slot instead of the most recently created hole).
1925 : So, for code simplicity, we just do that.
1926 :
1927 : A nice side effect is this removal process is that implicitly
1928 : improves probing for remaining keys in the map and does not
1929 : require tombstones.
1930 :
1931 : TL;DR It's a bad idea on many levels to fill up linearly probed
1932 : maps to their absolute limits ... but this will still work if you
1933 : do.
1934 :
1935 : Note also that this process preserves the ordering of keys that
1936 : hash to the same slot (such that key group ordering is
1937 : preserved). */
1938 :
1939 5625612 : ele_idx = hole_idx;
1940 7177509 : for(;;) {
1941 7177509 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
1942 :
1943 : /* At this point, slots (hole_idx,ele_idx) (cyclic) are used with
1944 : verified probe sequences. As per the above, we are guaranteed
1945 : to eventually hit an empty slot (typically very quickly in
1946 : practice) and hitting an empty slot guarantees all probe
1947 : sequences are intact (such that we are done). */
1948 :
1949 7177509 : MAP_ELE_T * ele = ele0 + ele_idx;
1950 7177509 : if( FD_LIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) ) break;
1951 :
1952 : /* Otherwise, if ele_idx's key probe sequence doesn't start in
1953 : (hole_idx,ele_idx] (cyclic), its probe sequence is currently
1954 : broken by the hole at hole_idx. We fix it by moving ele_idx to
1955 : hole_idx. This shortens that key's probe sequence (preserving
1956 : the invariant) and makes a new hole at ele_idx. We mark the
1957 : lock version covering the new hole idx as modified for the
1958 : unlock below. Note that the version for the existing hole was
1959 : already marked as modified when the hole was created so we only
1960 : bump if ele_idx is covered by a different lock than hole_idx to
1961 : reduce version churn to near theoretical minimum. */
1962 :
1963 : # if MAP_MEMOIZE
1964 518058 : memo = ele->MAP_MEMO;
1965 : # else
1966 1033839 : memo = MAP_(key_hash)( MAP_KEY_FROM_ELE( ctx, ele ), seed );
1967 : # endif
1968 1033839 : start_idx = memo & (ele_max-1UL);
1969 :
1970 1551897 : if( !( ((hole_idx<start_idx) & (start_idx<=ele_idx) ) |
1971 1551897 : ((hole_idx>ele_idx) & ((hole_idx<start_idx) | (start_idx<=ele_idx))) ) ) {
1972 :
1973 513120 : MAP_(private_ele_move)( ctx, ele0 + hole_idx, ele );
1974 :
1975 513120 : ulong lock_next = ele_idx >> lock_shift;
1976 513120 : version[ lock_next ] = (MAP_VERSION_T)((ulong)version[ lock_next ] + ((lock_next!=lock_idx) ? 2UL : 0UL) /* cmov */);
1977 513120 : lock_idx = lock_next;
1978 :
1979 513120 : hole_idx = ele_idx;
1980 513120 : }
1981 :
1982 1033839 : }
1983 :
1984 : /* At this point, key is removed and all remaining keys have intact
1985 : and ordered probe sequences and we have updated the necessary
1986 : version cache entries. Unlock and return success. */
1987 :
1988 5625612 : MAP_(private_unlock)( lock, lock_cnt, version, version_lock0, version_cnt );
1989 5625612 : return FD_MAP_SUCCESS;
1990 :
1991 5620896 : fail:
1992 :
1993 5620896 : MAP_(private_unlock)( lock, lock_cnt, version, version_lock0, version_cnt );
1994 :
1995 5620896 : if( FD_UNLIKELY( non_blocking | (err!=FD_MAP_ERR_AGAIN) ) ) return err;
1996 :
1997 : /* At this point, we are blocking and hit contention. Backoff. See
1998 : note in prepare for how this works */
1999 :
2000 0 : ulong scale = backoff_max >> 16; /* in [2^16,2^32) */
2001 0 : backoff_max = fd_ulong_min( backoff_max + (backoff_max>>2) + (backoff_max>>4), (1UL<<48)-1UL ); /* in [2^32,2^48) */
2002 0 : MAP_(backoff)( scale, backoff_seed );
2003 0 : }
2004 :
2005 : /* never get here */
2006 11246508 : }
2007 :
2008 : int
2009 : MAP_(query_try)( MAP_(t) const * join,
2010 : MAP_KEY_T const * key,
2011 : MAP_ELE_T const * sentinel,
2012 : MAP_(query_t) * query,
2013 11234070 : int flags ) {
2014 :
2015 11234070 : MAP_ELE_T * ele0 = join->ele;
2016 11234070 : MAP_VERSION_T * lock = join->lock;
2017 11234070 : ulong ele_max = join->ele_max;
2018 11234070 : ulong lock_cnt = join->lock_cnt;
2019 11234070 : ulong probe_max = join->probe_max;
2020 11234070 : ulong seed = join->seed;
2021 11234070 : int lock_shift = join->lock_shift;
2022 11234070 : void const * ctx = join->ctx;
2023 :
2024 11234070 : ulong memo = (flags & FD_MAP_FLAG_USE_HINT) ? query->memo : MAP_(key_hash)( key, seed );
2025 11234070 : ulong start_idx = memo & (ele_max-1UL);
2026 11234070 : ulong version_lock0 = start_idx >> lock_shift;
2027 :
2028 11234070 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
2029 11234070 : ulong backoff_max = (1UL<<32); /* in [2^32,2^48) */
2030 11234070 : ulong backoff_seed = ((ulong)(uint)flags)>>6; /* 0 usually fine */
2031 :
2032 11234070 : for(;;) { /* fresh try */
2033 :
2034 11234070 : int err;
2035 :
2036 11234070 : MAP_VERSION_T version[ MAP_LOCK_MAX ];
2037 11234070 : ulong version_cnt = 0UL;
2038 11234070 : ulong lock_idx = version_lock0;
2039 :
2040 : /* At this point, finding any key in the map requires probing at
2041 : most probe_max contiguous slots. */
2042 :
2043 11234070 : MAP_VERSION_T v = MAP_(private_try)( lock + lock_idx );
2044 11234070 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail_fast; } /* opt for low contention */
2045 11234070 : version[ lock_idx ] = v;
2046 11234070 : version_cnt++;
2047 :
2048 11234070 : ulong ele_idx = start_idx;
2049 :
2050 12787923 : for( ulong probe_rem=probe_max; probe_rem; probe_rem-- ) {
2051 :
2052 : /* At this point, we've observed the locks covering the start of
2053 : key's probe sequence to ele_idx inclusive, they were unlocked
2054 : when observed and we have done fewer than probe_max probes.
2055 :
2056 : If slot ele_idx is empty, we speculate that key was not in the
2057 : map at some point during the call.
2058 :
2059 : If slot ele_idx holds key, we let the caller continue speculating
2060 : about key's value. We only need to observe the lock covering key
2061 : after we've found it (if key gets moved or removed, the version
2062 : of the lock covering it will change). */
2063 :
2064 12787923 : MAP_ELE_T const * ele = ele0 + ele_idx;
2065 :
2066 12787923 : if( FD_UNLIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) ) { err = FD_MAP_ERR_KEY; goto fail; } /* opt for low collision */
2067 :
2068 7171977 : if(
2069 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2070 2391399 : FD_LIKELY( ele->MAP_MEMO==memo ) &&
2071 2391399 : # endif
2072 6653286 : FD_LIKELY( MAP_(key_eq)( MAP_KEY_FROM_ELE( ctx, ele ), key ) ) /* opt for found */
2073 7171977 : ) {
2074 :
2075 5618124 : lock_idx = ele_idx >> lock_shift;
2076 :
2077 5618124 : query->memo = memo;
2078 5618124 : query->ele = (MAP_ELE_T *)ele;
2079 5618124 : query->l = lock + lock_idx;
2080 5618124 : query->v = version[ lock_idx ];
2081 5618124 : return FD_MAP_SUCCESS;
2082 5618124 : }
2083 :
2084 : /* At this point, we speculate slot ele_idx was used by something
2085 : other than key when observed. Continue probing slot for key,
2086 : observing locks as necessary. */
2087 :
2088 1553853 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
2089 :
2090 : /* FIXME: FURTHER RESTRICT TO PROBE_REM>1? */
2091 1553853 : ulong lock_next = ele_idx >> lock_shift;
2092 1553853 : if( FD_UNLIKELY( (lock_next!=lock_idx) & (lock_next!=version_lock0) ) ) { /* opt for locks cover many contiguous slots */
2093 776265 : lock_idx = lock_next;
2094 :
2095 776265 : v = MAP_(private_try)( lock + lock_idx );
2096 776265 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) { err = FD_MAP_ERR_AGAIN; goto fail_fast; } /* opt for low contention */
2097 776265 : version[ lock_idx ] = v;
2098 776265 : version_cnt++;
2099 776265 : }
2100 1553853 : }
2101 :
2102 : /* At this point, we did probe_max probes without finding key. We
2103 : speculate key was not in the map at some point during the call. */
2104 :
2105 0 : err = FD_MAP_ERR_KEY;
2106 :
2107 5615946 : fail:
2108 :
2109 : /* If we didn't encounter any contention (i.e. no version numbers
2110 : changed), we can trust our speculated error. Otherwise, we tell
2111 : the user to try again. */
2112 :
2113 5615946 : err = MAP_(private_test)( lock, lock_cnt, version, version_lock0, version_cnt ) ? FD_MAP_ERR_AGAIN : err; /* cmov */
2114 :
2115 5615946 : fail_fast: /* Used when the err is already AGAIN */
2116 :
2117 5615946 : if( FD_UNLIKELY( non_blocking | (err!=FD_MAP_ERR_AGAIN) ) ) {
2118 5615946 : query->memo = memo;
2119 5615946 : query->ele = (MAP_ELE_T *)sentinel;
2120 5615946 : query->l = NULL;
2121 5615946 : query->v = (MAP_VERSION_T)0;
2122 5615946 : return err;
2123 5615946 : }
2124 :
2125 : /* At this point, we are blocking and hit contention. Backoff. See
2126 : note in prepare for how this works */
2127 :
2128 0 : ulong scale = backoff_max >> 16; /* in [2^16,2^32) */
2129 0 : backoff_max = fd_ulong_min( backoff_max + (backoff_max>>2) + (backoff_max>>4), (1UL<<48)-1UL ); /* in [2^32,2^48) */
2130 0 : MAP_(backoff)( scale, backoff_seed );
2131 0 : }
2132 : /* never get here */
2133 11234070 : }
2134 :
2135 : int
2136 : MAP_(lock_range)( MAP_(t) * join,
2137 : ulong range_start,
2138 : ulong range_cnt,
2139 : int flags,
2140 5609781 : MAP_VERSION_T * version ) {
2141 5609781 : MAP_VERSION_T * lock = join->lock;
2142 5609781 : ulong lock_cnt = join->lock_cnt;
2143 :
2144 5609781 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
2145 5609781 : ulong backoff_max = (1UL<<32); /* in [2^32,2^48) */
2146 5609781 : ulong backoff_seed = ((ulong)(uint)flags)>>6; /* 0 usually fine */
2147 5609781 : ulong version_delta = (flags & FD_MAP_FLAG_RDONLY) ? 0UL : 2UL;
2148 :
2149 5609781 : for(;;) { /* fresh try */
2150 :
2151 5609781 : ulong lock_idx = range_start;
2152 5609781 : ulong locked_cnt = 0UL;
2153 16802640 : for( ; locked_cnt<range_cnt; locked_cnt++ ) {
2154 11192859 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
2155 11192859 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) goto fail; /* opt for low contention */
2156 11192859 : version[ lock_idx ] = (MAP_VERSION_T)((ulong)v + version_delta);
2157 11192859 : lock_idx = (lock_idx+1UL) & (lock_cnt-1UL);
2158 11192859 : }
2159 :
2160 5609781 : return FD_MAP_SUCCESS;
2161 :
2162 0 : fail:
2163 :
2164 0 : MAP_(private_unlock)( lock, lock_cnt, version, range_start, locked_cnt );
2165 :
2166 0 : if( FD_UNLIKELY( non_blocking ) ) return FD_MAP_ERR_AGAIN;
2167 :
2168 : /* At this point, we are blocking and hit contention. Backoff. See
2169 : note in prepare for how this works */
2170 :
2171 0 : ulong scale = backoff_max >> 16; /* in [2^16,2^32) */
2172 0 : backoff_max = fd_ulong_min( backoff_max + (backoff_max>>2) + (backoff_max>>4), (1UL<<48)-1UL ); /* in [2^32,2^48) */
2173 0 : MAP_(backoff)( scale, backoff_seed );
2174 0 : }
2175 : /* never get here */
2176 5609781 : }
2177 :
2178 : int
2179 : MAP_(iter_init)( MAP_(t) * join,
2180 : ulong memo,
2181 : int flags,
2182 5622552 : MAP_(iter_t) * iter ) {
2183 :
2184 5622552 : MAP_ELE_T * ele0 = join->ele;
2185 5622552 : MAP_VERSION_T * lock = join->lock;
2186 5622552 : ulong ele_max = join->ele_max;
2187 5622552 : ulong lock_cnt = join->lock_cnt;
2188 5622552 : ulong probe_max = join->probe_max;
2189 5622552 : ulong seed = join->seed;
2190 5622552 : int lock_shift = join->lock_shift;
2191 5622552 : void * ctx = join->ctx;
2192 :
2193 5622552 : MAP_VERSION_T * version = iter->version;
2194 :
2195 5622552 : ulong start_idx = memo & (ele_max-1UL);
2196 5622552 : ulong version_lock0 = start_idx >> lock_shift;
2197 5622552 : ulong version_delta = (flags & FD_MAP_FLAG_RDONLY) ? 0UL : 2UL;
2198 :
2199 5622552 : int non_blocking = !(flags & FD_MAP_FLAG_BLOCKING);
2200 5622552 : ulong backoff_max = (1UL<<32); /* in [2^32,2^48) */
2201 5622552 : ulong backoff_seed = ((ulong)(uint)flags)>>6; /* 0 usually fine */
2202 :
2203 5622552 : for(;;) { /* fresh try */
2204 :
2205 5622552 : ulong version_cnt = 0UL;
2206 5622552 : ulong lock_idx = version_lock0;
2207 :
2208 : /* At this point, finding any key-val pair that matches memo in the
2209 : map requires probing at most probe_max contiguous slots. */
2210 :
2211 5622552 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
2212 5622552 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) goto fail; /* opt for low contention */
2213 5622552 : version[ lock_idx ] = (MAP_VERSION_T)((ulong)v + version_delta);
2214 5622552 : version_cnt++;
2215 :
2216 5622552 : ulong ele_idx = start_idx;
2217 5622552 : ulong ele_rem = 0UL;
2218 :
2219 5622552 : ulong iter_cnt = 0UL;
2220 5622552 : ulong iter_start = start_idx;
2221 :
2222 13263789 : for( ; ele_rem<probe_max; ele_rem++ ) {
2223 :
2224 : /* At this point, we've acquired the locks covering slots
2225 : [start_idx,ele_idx] (cyclic) and have confirmed that the
2226 : ele_rem slots [start_idx,ele_idx) (cyclic) are used. If slot
2227 : ele_idx is empty, we are done probing. */
2228 :
2229 13263789 : MAP_ELE_T const * ele = ele0 + ele_idx;
2230 :
2231 13263789 : if( FD_UNLIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) ) break; /* opt for first pass low collision */
2232 :
2233 7641237 : iter_start = fd_ulong_if( iter_cnt==0UL, ele_idx, iter_start );
2234 : # if MAP_MEMOIZE
2235 2543658 : iter_cnt += (ulong)(ele->MAP_MEMO==memo);
2236 : # else
2237 5097579 : iter_cnt += (ulong)(MAP_(key_hash)( MAP_KEY_FROM_ELE( ctx, ele ), seed )==memo);
2238 : # endif
2239 :
2240 : /* Continue probing, locking as necessary. If we can't acquire a
2241 : lock, fail. */
2242 :
2243 7641237 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
2244 :
2245 7641237 : ulong lock_next = ele_idx >> lock_shift;
2246 7641237 : if( FD_UNLIKELY( (lock_next!=lock_idx) & (lock_next!=version_lock0) ) ) { /* opt for locks covering many contiguous slots */
2247 3827664 : lock_idx = lock_next;
2248 :
2249 3827664 : MAP_VERSION_T v = MAP_(private_lock)( lock + lock_idx );
2250 3827664 : if( FD_UNLIKELY( (ulong)v & 1UL ) ) goto fail; /* opt for low contention */
2251 3827664 : version[ lock_idx ] = (MAP_VERSION_T)((ulong)v + version_delta);
2252 3827664 : version_cnt++;
2253 3827664 : }
2254 7641237 : }
2255 :
2256 : /* At this point, we've acquired the locks covering used slots
2257 : [start_idx,start_idx+ele_rem) (cyclic) where ele_rem<=probe_max
2258 : (and, if ele_rem<probe_max, any trailing empty slot). iter_cnt
2259 : is the number of slots that matched in this range and iter_start
2260 : is the index of the first element in this range that matched
2261 : (start_idx if no matches). */
2262 :
2263 5622552 : iter->ele = ele0;
2264 5622552 : iter->lock = lock;
2265 5622552 : iter->ele_max = ele_max;
2266 5622552 : iter->lock_cnt = lock_cnt;
2267 5622552 : iter->seed = seed;
2268 5622552 : iter->memo = memo;
2269 5622552 : iter->ele_rem = iter_cnt;
2270 5622552 : iter->ele_idx = iter_start;
2271 5622552 : iter->version_lock0 = version_lock0;
2272 5622552 : iter->version_cnt = version_cnt;
2273 5622552 : fd_memcpy( iter->ctx, ctx, MAP_CTX_MAX );
2274 : /* iter->version initialized above */
2275 :
2276 5622552 : return FD_MAP_SUCCESS;
2277 :
2278 0 : fail:
2279 :
2280 : /* At this point, we hit contention acquiring the locks for
2281 : iteration. If we not blocking, tell caller to try again later.
2282 : Otherwise, backoff. See note in prepare for how this works. */
2283 :
2284 0 : MAP_(private_unlock)( lock, lock_cnt, version, version_lock0, version_cnt );
2285 :
2286 0 : if( FD_UNLIKELY( non_blocking ) ) {
2287 0 : iter->ele_rem = 0UL; /* make sure can't iterate */
2288 0 : iter->version_cnt = 0UL; /* make sure fini is a no-op */
2289 0 : return FD_MAP_ERR_AGAIN;
2290 0 : }
2291 :
2292 0 : ulong scale = backoff_max >> 16; /* in [2^16,2^32) */
2293 0 : backoff_max = fd_ulong_min( backoff_max + (backoff_max>>2) + (backoff_max>>4), (1UL<<48)-1UL ); /* in [2^32,2^48) */
2294 0 : MAP_(backoff)( scale, backoff_seed );
2295 0 : }
2296 : /* never get here */
2297 5622552 : }
2298 :
2299 : __attribute__((warn_unused_result)) MAP_(iter_t) *
2300 5615973 : MAP_(iter_next)( MAP_(iter_t) * iter ) {
2301 5615973 : ulong ele_idx = iter->ele_idx;
2302 5615973 : ulong ele_rem = iter->ele_rem - 1UL;
2303 :
2304 : /* We just finished processing pair ele_idx and we have ele_rem
2305 : more pairs to process. If there is at least 1, scan for it. */
2306 :
2307 5615973 : if( ele_rem ) {
2308 0 : MAP_ELE_T * ele0 = iter->ele;
2309 0 : ulong ele_max = iter->ele_max;
2310 0 : ulong seed = iter->seed; (void)seed;
2311 0 : ulong memo = iter->memo;
2312 0 : void * ctx = iter->ctx; (void)ctx;
2313 :
2314 0 : for(;;) {
2315 0 : ele_idx = (ele_idx+1UL) & (ele_max-1UL);
2316 0 : MAP_ELE_T * ele = ele0 + ele_idx;
2317 : # if MAP_MEMOIZE
2318 0 : if( FD_LIKELY( ele->MAP_MEMO==memo ) ) break;
2319 : # else
2320 0 : if( FD_LIKELY( MAP_(key_hash)( MAP_KEY_FROM_ELE( ctx, ele ), seed )==memo ) ) break;
2321 : # endif
2322 0 : }
2323 0 : }
2324 :
2325 5615973 : iter->ele_idx = ele_idx;
2326 5615973 : iter->ele_rem = ele_rem;
2327 5615973 : return iter;
2328 5615973 : }
2329 :
2330 : MAP_STATIC int
2331 132 : MAP_(verify)( MAP_(t) const * join ) {
2332 :
2333 290982 : # define MAP_TEST(c) do { \
2334 290982 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_MAP_ERR_INVAL; } \
2335 290982 : } while(0)
2336 :
2337 : /* Validate join */
2338 :
2339 132 : MAP_TEST( join );
2340 132 : MAP_TEST( fd_ulong_is_aligned( (ulong)join, alignof(MAP_(t)) ) );
2341 :
2342 132 : MAP_ELE_T const * ele0 = join->ele;
2343 132 : MAP_VERSION_T const * lock = join->lock;
2344 132 : ulong ele_max = join->ele_max;
2345 132 : ulong lock_cnt = join->lock_cnt;
2346 132 : ulong probe_max = join->probe_max;
2347 132 : ulong seed = join->seed;
2348 132 : int lock_shift = join->lock_shift;
2349 132 : void const * ctx = join->ctx;
2350 :
2351 132 : MAP_TEST( ele0 );
2352 132 : MAP_TEST( fd_ulong_is_aligned( (ulong)ele0, alignof(MAP_ELE_T) ) );
2353 132 : MAP_TEST( lock );
2354 132 : MAP_TEST( fd_ulong_is_aligned( (ulong)lock, MAP_(align)() ) );
2355 132 : MAP_TEST( fd_ulong_is_pow2( ele_max ) );
2356 132 : MAP_TEST( fd_ulong_is_pow2( lock_cnt ) );
2357 132 : MAP_TEST( lock_cnt <= fd_ulong_min( ele_max, MAP_LOCK_MAX ) );
2358 132 : MAP_TEST( (1UL<=probe_max) & (probe_max<=ele_max) );
2359 : /* seed is arbitrary */
2360 132 : MAP_TEST( (1UL<<lock_shift) == (ele_max/lock_cnt) );
2361 :
2362 : /* Validate map metadata */
2363 :
2364 132 : MAP_(shmem_t) const * map = ((MAP_(shmem_t) const *)lock)-1;
2365 :
2366 132 : MAP_TEST( map );
2367 132 : MAP_TEST( fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) );
2368 132 : MAP_TEST( map->magic == MAP_MAGIC );
2369 132 : MAP_TEST( map->ele_max == ele_max );
2370 132 : MAP_TEST( map->lock_cnt == lock_cnt );
2371 132 : MAP_TEST( map->probe_max == probe_max );
2372 132 : MAP_TEST( map->seed == seed );
2373 132 : MAP_TEST( map->lock_shift == lock_shift );
2374 :
2375 : /* Validate map elements */
2376 :
2377 540804 : for( ulong ele_idx=0UL; ele_idx<ele_max; ele_idx++ ) {
2378 540672 : MAP_ELE_T const * ele = ele0 + ele_idx;
2379 540672 : if( FD_LIKELY( MAP_(private_ele_is_free)( ctx, ele ) ) ) continue; /* opt for sparse */
2380 :
2381 74358 : ulong memo = MAP_(key_hash)( MAP_KEY_FROM_ELE( ctx, ele ), seed );
2382 :
2383 : # if MAP_MEMOIZE
2384 40812 : MAP_TEST( ele->MAP_MEMO==memo );
2385 40812 : # endif
2386 :
2387 40812 : ulong probe_idx = memo & (ele_max-1UL);
2388 40812 : ulong probe_cnt = fd_ulong_if( ele_idx>=probe_idx, ele_idx - probe_idx, ele_max + ele_idx - probe_idx ) + 1UL;
2389 74358 : MAP_TEST( probe_cnt<=probe_max );
2390 :
2391 161010 : for( ulong probe_rem=probe_cnt; probe_rem; probe_rem-- ) {
2392 86652 : MAP_ELE_T const * probe = ele0 + probe_idx;
2393 86652 : MAP_TEST( !MAP_(private_ele_is_free)( ctx, probe ) );
2394 :
2395 86652 : int found =
2396 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
2397 48576 : FD_LIKELY( probe->MAP_MEMO == ele->MAP_MEMO ) &&
2398 : # endif
2399 86652 : MAP_(key_eq)( MAP_KEY_FROM_ELE( ctx, probe ), MAP_KEY_FROM_ELE( ctx, ele ) );
2400 :
2401 86652 : MAP_TEST( (probe_rem==1UL) ? found : !found );
2402 :
2403 86652 : probe_idx = (probe_idx+1UL) & (ele_max-1UL);
2404 86652 : }
2405 74358 : }
2406 :
2407 : /* At this point, every key in the map is reachable via it's probe
2408 : sequence and every probe sequence is at most probe_max probes long.
2409 : By extension, if a key is in the map, it will be found in at most
2410 : probe_max probes. */
2411 :
2412 132 : # undef MAP_TEST
2413 :
2414 132 : return FD_MAP_SUCCESS;
2415 132 : }
2416 :
2417 : MAP_STATIC char const *
2418 18 : MAP_(strerror)( int err ) {
2419 18 : switch( err ) {
2420 3 : case FD_MAP_SUCCESS: return "success";
2421 3 : case FD_MAP_ERR_INVAL: return "bad input";
2422 3 : case FD_MAP_ERR_AGAIN: return "try again later";
2423 3 : case FD_MAP_ERR_FULL: return "map too full";
2424 3 : case FD_MAP_ERR_KEY: return "key not found";
2425 3 : default: break;
2426 18 : }
2427 3 : return "unknown";
2428 18 : }
2429 :
2430 : #endif
2431 :
2432 : #undef MAP_
2433 : #undef MAP_STATIC
2434 :
2435 : #undef MAP_IMPL_STYLE
2436 : #undef MAP_MAGIC
2437 : #undef MAP_ALIGN
2438 : #undef MAP_LOCK_MAX
2439 : #undef MAP_VERSION_T
2440 : #undef MAP_CTX_MAX
2441 : #undef MAP_ELE_MOVE
2442 : #undef MAP_ELE_FREE
2443 : #undef MAP_ELE_IS_FREE
2444 : #undef MAP_KEY_EQ_IS_SLOW
2445 : #undef MAP_MEMO
2446 : #undef MAP_MEMOIZE
2447 : #undef MAP_KEY_HASH
2448 : #undef MAP_KEY_FROM_ELE
2449 : #undef MAP_KEY_EQ
2450 : #undef MAP_KEY
2451 : #undef MAP_KEY_T
2452 : #undef MAP_ELE_T
2453 : #undef MAP_NAME
|
