1 /* Copyright (C) 2012-2023 Free Software Foundation, Inc.
2
3 This file is part of GCC.
4
5 GCC is free software; you can redistribute it and/or modify it
6 under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3, or (at your option)
8 any later version.
9
10 GCC is distributed in the hope that it will be useful, but WITHOUT
11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
13 License for more details.
14
15 Under Section 7 of GPL version 3, you are granted additional
16 permissions described in the GCC Runtime Library Exception, version
17 3.1, as published by the Free Software Foundation.
18
19 You should have received a copy of the GNU General Public License
20 and a copy of the GCC Runtime Library Exception along with this
21 program; see the files COPYING3 and COPYING.RUNTIME respectively.
22 If not, see <http://www.gnu.org/licenses/>. */
23
24 #ifndef _VTV_SET_H
25 #define _VTV_SET_H 1
26
27 /* Code in this file manages a collection of insert-only sets. We
28 have only tested the case where Key is uintptr_t, though it
29 theoretically should work for some other cases. All odd keys are
30 reserved, and must not be inserted into any of the sets. This code
31 is intended primarily for sets of pointers, and the code is
32 optimized for small sets (including size 0 and 1), but regardless
33 of the set size, insert() and contains() have close to O(1) speed
34 in practice.
35
36 TODO(gpike): fix this comment.
37
38 Recommended multithreaded use of a set:
39
40 For speed, we want to use a lock-free test for set membership. The
41 code handles simultaneous reads and inserts, as long as at most one
42 insertion is in progress at a time. After an insert, other threads
43 may not immediately "see" the inserted key if they perform a
44 lock-free read, so we recommend retrying, as explained below.
45
46 Also, to make data corruption less likely, we recommend using a
47 "normal" RW page as well as one or pages that are typically RO
48 but that can be switched to RW and back as needed. The latter
49 pages should contain sets. The former should contain a lock, L,
50 and an int or similar, num_writers. Then, to insert, something
51 like this would be safe:
52 o Acquire L.
53 o Increment num_writers; if that made it 1, change pages to RW.
54 o Release L.
55 o while (there are insertions to do in some set, S) {
56 acquire L;
57 do some insertions in S;
58 release L;
59 }
60 o Acquire L.
61 o Decrement num_writers; if that made it 0, change pages to RO.
62 o Release L.
63
64 And to check if the set contains some key, one could use
65 set.contains(key) ||
66 ({ Acquire L; bool b = set.contains(key); Release L; b; })
67
68 In this scheme, the number of threads with reads in progress isn't
69 tracked, so old sets can never be deleted. In addition, on some
70 architectures the intentionally racy reads might cause contains()
71 to return true when it should have returned false. This should be
72 no problem on x86, and most other machines, where reading or
73 writing an aligned uintptr_t is atomic. E.g., on those machines,
74 if *p is 0 and one thread does *p = x while another reads *p, the
75 read will see either 0 or x.
76
77 To make the above easier, the insert_only_hash_sets class provides
78 an interface to manipulate any number of hash sets. One shouldn't
79 create objects of that class, as it has no member data and its
80 methods are static.
81
82 So the recommended model is to have a single lock, a single
83 num_writers variable, and some number of sets. If lock contention
84 becomes a problem then the sets can be divided into k groups, each
85 of which has a lock and a num_writers variable; or each set can be
86 represented as a set of values that equal 0 mod m, a set of values
87 that equal 1 mod m, ..., plus a set of values that equal m-1 mod m.
88
89 However, we expect most or all uses of this code to call contains()
90 much more frequently than anything else, so lock contention is
91 likely to be low. */
92
93 #include <algorithm>
94
95 #ifndef HASHTABLE_STATS
96 #define HASHTABLE_STATS 0
97 #endif
98
99 #ifndef HASHTABLE_STATS_ATOMIC
100 #define HASHTABLE_STATS_ATOMIC 0
101 #endif
102
103 #if HASHTABLE_STATS
104 #if HASHTABLE_STATS_ATOMIC
105 /* Stat counters, with atomics. */
106 #include <bits/atomic_word.h>
107
108 typedef _Atomic_word _AtomicStatCounter;
109
110 void
111 inc_by (_AtomicStatCounter &stat, int amount)
112 {
113 __atomic_add_fetch (&stat, amount, __ATOMIC_ACQ_REL);
114 }
115
116 #else
117
118 /* Stat counters, but without atomics. */
119 typedef int _AtomicStatCounter;
120
121 void
122 inc_by (_AtomicStatCounter& stat, int amount)
123 {
124 stat += amount;
125 }
126
127 #endif
128
129
130 /* Number of calls to contains(), insert(), etc. */
131 extern _AtomicStatCounter stat_insert;
132 extern _AtomicStatCounter stat_contains;
133 extern _AtomicStatCounter stat_resize;
134 extern _AtomicStatCounter stat_create;
135
136 /* Sum of set size over all calls to contains(). */
137 extern _AtomicStatCounter stat_contains_sizes;
138
139 /* contains() calls in a set whose capacity is more than 1. */
140 extern _AtomicStatCounter stat_contains_in_non_trivial_set;
141
142 /* Probes in a set whose capacity is more than 1. Ideally, this will
143 be pretty close to stat_contains_in_non_trivial_set. That will
144 happen if our hash function is good and/or important keys were
145 inserted before unimportant keys. */
146 extern _AtomicStatCounter stat_probes_in_non_trivial_set;
147
148 /* number of calls to contains() with size=0, 1, etc. */
149 extern _AtomicStatCounter stat_contains_size0;
150 extern _AtomicStatCounter stat_contains_size1;
151 extern _AtomicStatCounter stat_contains_size2;
152 extern _AtomicStatCounter stat_contains_size3;
153 extern _AtomicStatCounter stat_contains_size4;
154 extern _AtomicStatCounter stat_contains_size5;
155 extern _AtomicStatCounter stat_contains_size6;
156 extern _AtomicStatCounter stat_contains_size7;
157 extern _AtomicStatCounter stat_contains_size8;
158 extern _AtomicStatCounter stat_contains_size9;
159 extern _AtomicStatCounter stat_contains_size10;
160 extern _AtomicStatCounter stat_contains_size11;
161 extern _AtomicStatCounter stat_contains_size12;
162 extern _AtomicStatCounter stat_contains_size13_or_more;
163 extern _AtomicStatCounter stat_grow_from_size0_to_1;
164 extern _AtomicStatCounter stat_grow_from_size1_to_2;
165 extern _AtomicStatCounter stat_double_the_number_of_buckets;
166 extern _AtomicStatCounter stat_insert_key_that_was_already_present;
167
168 /* Hash collisions detected during insert_no_resize(). Only counts
169 hasher(k) == hasher(k'); hasher(k) % tablesize == hasher(k') %
170 tablesize is not sufficient. Will count collisions that are
171 detected during table resizes etc., so the same two keys may add to
172 this stat multiple times. */
173 extern _AtomicStatCounter stat_insert_found_hash_collision;
174
175 #include <string>
176
177 struct insert_only_hash_sets_logger
178 {
179 static char *
180 log (char c, char *buf)
181 {
182 *buf++ = c;
183 return buf;
184 }
185
186 static char *
187 log (const char *s, char *buf)
188 { return strcpy (buf, s) + strlen (s); }
189
190 static char *
191 log (_AtomicStatCounter i, char *buf)
192 {
193 if (i < 10)
194 return log ((char) ('0' + i), buf);
195 else
196 return log ((char) ('0' + i % 10), log (i / 10, buf));
197 }
198
199 static char *
200 log (const char *label, _AtomicStatCounter i, char *buf)
201 {
202 buf = log (label, buf);
203 buf = log (": ", buf);
204 buf = log (i, buf);
205 return log ('\n', buf);
206 }
207 };
208
209 // Write stats to the given buffer, which should be at least 4000 bytes.
210 static inline void
211 insert_only_hash_tables_stats (char *buf)
212 {
213 buf = insert_only_hash_sets_logger::log ("insert", stat_insert, buf);
214 buf = insert_only_hash_sets_logger::log ("contains", stat_contains, buf);
215 buf = insert_only_hash_sets_logger::log ("resize", stat_resize, buf);
216 buf = insert_only_hash_sets_logger::log ("create", stat_create, buf);
217 buf = insert_only_hash_sets_logger::log ("insert_key_that_was_already_"
218 "present",
219 stat_insert_key_that_was_already_present,
220 buf);
221 buf = insert_only_hash_sets_logger::log ("contains_sizes",
222 stat_contains_sizes, buf);
223 buf = insert_only_hash_sets_logger::log ("contains_in_non_trivial_set",
224 stat_contains_in_non_trivial_set,
225 buf);
226 buf = insert_only_hash_sets_logger::log ("probes_in_non_trivial_set",
227 stat_probes_in_non_trivial_set,
228 buf);
229 buf = insert_only_hash_sets_logger::log ("contains_size0",
230 stat_contains_size0, buf);
231 buf = insert_only_hash_sets_logger::log ("contains_size1",
232 stat_contains_size1, buf);
233 buf = insert_only_hash_sets_logger::log ("contains_size2",
234 stat_contains_size2, buf);
235 buf = insert_only_hash_sets_logger::log ("contains_size3",
236 stat_contains_size3, buf);
237 buf = insert_only_hash_sets_logger::log ("contains_size4",
238 stat_contains_size4, buf);
239 buf = insert_only_hash_sets_logger::log ("contains_size5",
240 stat_contains_size5, buf);
241 buf = insert_only_hash_sets_logger::log ("contains_size6",
242 stat_contains_size6, buf);
243 buf = insert_only_hash_sets_logger::log ("contains_size7",
244 stat_contains_size7, buf);
245 buf = insert_only_hash_sets_logger::log ("contains_size8",
246 stat_contains_size8, buf);
247 buf = insert_only_hash_sets_logger::log ("contains_size9",
248 stat_contains_size9, buf);
249 buf = insert_only_hash_sets_logger::log ("contains_size10",
250 stat_contains_size10, buf);
251 buf = insert_only_hash_sets_logger::log ("contains_size11",
252 stat_contains_size11, buf);
253 buf = insert_only_hash_sets_logger::log ("contains_size12",
254 stat_contains_size12, buf);
255 buf = insert_only_hash_sets_logger::log ("contains_size13_or_more",
256 stat_contains_size13_or_more, buf);
257 buf = insert_only_hash_sets_logger::log ("grow_from_size0_to_1",
258 stat_grow_from_size0_to_1, buf);
259 buf = insert_only_hash_sets_logger::log ("grow_from_size1_to_2",
260 stat_grow_from_size1_to_2, buf);
261 buf = insert_only_hash_sets_logger::log ("insert_found_hash_collision",
262 stat_insert_found_hash_collision,
263 buf);
264 buf = insert_only_hash_sets_logger::log ("double_the_number_of_buckets",
265 stat_double_the_number_of_buckets,
266 buf);
267 *buf = '\0';
268 }
269
270 #else
271
272 /* No stats. */
273 #define inc_by(statname, amount) do { } while (false && (amount))
274
275 #endif
276
277 #define inc(statname) inc_by (statname, 1)
278
279 template <typename Key, class HashFcn, class Alloc>
280 class insert_only_hash_sets
281 {
282 public:
283 typedef Key key_type;
284 typedef size_t size_type;
285 typedef Alloc alloc_type;
286 enum { illegal_key = 1 };
287 enum { min_capacity = 4 };
288 #if HASHTABLE_STATS
289 enum { stats = true };
290 #else
291 enum { stats = false };
292 #endif
293
294 /* Do not directly use insert_only_hash_set. Instead, use the
295 static methods below to create and manipulate objects of the
296 following class.
297
298 Implementation details: each set is represented by a pointer
299 plus, perhaps, out-of-line data, which would be an object of type
300 insert_only_hash_set. For a pointer, s, the interpretation is: s
301 == NULL means empty set, lsb(s) == 1 means a set with one
302 element, which is (uintptr_t)s - 1, and otherwise s is a pointer
303 of type insert_only_hash_set*. So, to increase the size of a set
304 we have to change s and/or *s. To check if a set contains some
305 key we have to examine s and possibly *s. */
306 class insert_only_hash_set
307 {
308 public:
309 /* Insert a key. The key must not be a reserved key. */
310 static inline insert_only_hash_set *insert (key_type key,
311 insert_only_hash_set *s);
312
313
314 /* Create an empty set. */
315 static inline insert_only_hash_set *create (size_type capacity);
316
317 /* Return whether the given key is present. If key is illegal_key
318 then either true or false may be returned, but for all other
319 reserved keys false will be returned. */
320 static bool
321 contains (key_type key, const insert_only_hash_set *s)
322 {
323 if (stats)
324 {
325 inc (stat_contains);
326 switch (size (s))
327 {
328 case 0: inc (stat_contains_size0); break;
329 case 1: inc (stat_contains_size1); break;
330 case 2: inc (stat_contains_size2); break;
331 case 3: inc (stat_contains_size3); break;
332 case 4: inc (stat_contains_size4); break;
333 case 5: inc (stat_contains_size5); break;
334 case 6: inc (stat_contains_size6); break;
335 case 7: inc (stat_contains_size7); break;
336 case 8: inc (stat_contains_size8); break;
337 case 9: inc (stat_contains_size9); break;
338 case 10: inc (stat_contains_size10); break;
339 case 11: inc (stat_contains_size11); break;
340 case 12: inc (stat_contains_size12); break;
341 default: inc (stat_contains_size13_or_more); break;
342 }
343 inc_by (stat_contains_sizes, size (s));
344 }
345
346 return (singleton (s) ?
347 singleton_key (key) == s :
348 ((s != NULL) && s->contains (key)));
349 }
350
351 /* Return a set's size. */
352 static size_type
353 size (const insert_only_hash_set *s)
354 { return (s == NULL) ? 0 : (singleton (s) ? 1 : s->num_entries); }
355
356 static inline insert_only_hash_set *resize (size_type target_num_buckets,
357 insert_only_hash_set *s);
358
359
360 private:
361 /* Return whether a set has size 1. */
362 static bool
363 singleton (const insert_only_hash_set *s)
364 { return (uintptr_t) s & 1; }
365
366 /* Return the representation of a singleton set containing the
367 given key. */
368 static insert_only_hash_set *
369 singleton_key (key_type key)
370 { return (insert_only_hash_set *) ((uintptr_t) key + 1); }
371
372 /* Given a singleton set, what key does it contain? */
373 static key_type
374 extract_singleton_key (const insert_only_hash_set *s)
375 {
376 VTV_DEBUG_ASSERT (singleton (s));
377 return (key_type) ((uintptr_t) s - 1);
378 }
379
380 volatile key_type &
381 key_at_index (size_type index)
382 { return buckets[index]; }
383
384 key_type
385 key_at_index (size_type index) const
386 { return buckets[index]; }
387
388 size_type
389 next_index (size_type index, size_type indices_examined) const
390 { return (index + indices_examined) & (num_buckets - 1); }
391
392 inline void insert_no_resize (key_type key);
393
394 inline bool contains (key_type key) const;
395
396 inline insert_only_hash_set *resize_if_necessary (void);
397
398 size_type num_buckets; /* Must be a power of 2 not less than
399 min_capacity. */
400 volatile size_type num_entries;
401 volatile key_type buckets[0]; /* Actual array size is num_buckets. */
402 };
403
404 /* Create an empty set with the given capacity. Requires that n be
405 0 or a power of 2. If 1 < n < min_capacity then treat n as
406 min_capacity. Sets *handle. Returns true unless the allocator
407 fails. Subsequent operations on this set should use the same
408 handle. */
409
410 static inline bool create (size_type n, insert_only_hash_set **handle);
411
412 /* Force the capacity of a set to be n, unless it was more than n
413 already. Requires that n be 0 or a power of 2. Sets *handle
414 unless the current capacity is n or more. Returns true unless
415 the allocator fails. */
416
417 static inline bool resize (size_type n, insert_only_hash_set **handle);
418
419 /* Insert a key. *handle is unmodified unless (1) a resize occurs,
420 or (2) the set was initially empty. Returns true unless the
421 allocator fails during a resize. If the allocator fails during a
422 resize then the set is reset to be the empty set. The key must
423 not be a reserved key. */
424
425 static inline bool insert (key_type key, insert_only_hash_set **handle);
426
427 /* Check for the presence of a key. If key is illegal_key then
428 either true or false may be returned, but for all other reserved
429 keys false will be returned. */
430
431 static inline bool
432 contains (key_type key, /* const */ insert_only_hash_set **handle)
433 { return insert_only_hash_set::contains (key, *handle); }
434
435 /* Return the size of the given set. */
436 static size_type
437 size (const insert_only_hash_set **handle)
438 { return insert_only_hash_set::size (*handle); }
439
440 static bool
441 is_reserved_key (key_type key)
442 { return ((uintptr_t) key % 2) == 1; }
443 };
444
445 template <typename Key, class HashFcn, class Alloc>
446 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
447 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::resize
448 (size_type n, insert_only_hash_set *s)
449 {
450 if (s == NULL)
451 return create (n);
452
453 size_type capacity = singleton (s) ? 1 : s->num_buckets;
454
455 if (n <= capacity)
456 return s;
457
458 insert_only_hash_set *result =
459 create (std::max<size_type> (n, min_capacity));
460 if (result != NULL)
461 {
462 if (singleton (s))
463 {
464 result->insert_no_resize (extract_singleton_key (s));
465 }
466 else
467 {
468 for (size_type i = 0; i < s->num_buckets; i++)
469 if (s->buckets[i] != (key_type) illegal_key)
470 result->insert_no_resize (s->buckets[i]);
471 }
472 VTV_DEBUG_ASSERT (size (result) == size (s));
473 }
474 return result;
475 }
476
477 template <typename Key, class HashFcn, class Alloc>
478 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
479 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::insert
480 (key_type key, insert_only_hash_set *s)
481 {
482 VTV_DEBUG_ASSERT (!is_reserved_key (key));
483
484 inc_by (stat_grow_from_size0_to_1, s == NULL);
485
486 if (s == NULL)
487 return singleton_key (key);
488
489 if (singleton (s))
490 {
491 const key_type old_key = extract_singleton_key (s);
492 if (old_key == key)
493 return s;
494
495 /* Grow from size 1 to size 2. */
496 inc (stat_grow_from_size1_to_2);
497 s = create (2);
498 if (s == NULL)
499 return NULL;
500
501 s->insert_no_resize (old_key);
502 s->insert_no_resize (key);
503 VTV_DEBUG_ASSERT (size (s) == 2);
504 return s;
505 }
506 s = s->resize_if_necessary();
507 if (s != NULL)
508 s->insert_no_resize (key);
509 return s;
510 }
511
512 template <typename Key, class HashFcn, class Alloc>
513 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
514 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::create
515 (size_type capacity)
516 {
517 if (capacity <= 1)
518 return NULL;
519
520 VTV_DEBUG_ASSERT (capacity > 1 && (capacity & (capacity - 1)) == 0);
521 VTV_DEBUG_ASSERT (sizeof (insert_only_hash_set) == 2 * sizeof (size_type));
522 capacity = std::max <size_type> (capacity, min_capacity);
523 const size_t num_bytes = sizeof (insert_only_hash_set) +
524 sizeof (key_type) * capacity;
525 alloc_type alloc;
526 insert_only_hash_set *result = (insert_only_hash_set *) alloc (num_bytes);
527 result->num_buckets = capacity;
528 result->num_entries = 0;
529 for (size_type i = 0; i < capacity; i++)
530 result->buckets[i] = (key_type) illegal_key;
531 return result;
532 }
533
534 template <typename Key, class HashFcn, class Alloc>
535 void
536 insert_only_hash_sets<Key, HashFcn,
537 Alloc>::insert_only_hash_set::insert_no_resize
538 (key_type key)
539 {
540 HashFcn hasher;
541 const size_type capacity = num_buckets;
542 VTV_DEBUG_ASSERT (capacity >= min_capacity);
543 VTV_DEBUG_ASSERT (!is_reserved_key (key));
544 size_type index = hasher (key) & (capacity - 1);
545 key_type k = key_at_index (index);
546 size_type indices_examined = 0;
547 while (k != key)
548 {
549 ++indices_examined;
550 if (k == (key_type) illegal_key)
551 {
552 key_at_index (index) = key;
553 ++num_entries;
554 return;
555 }
556 else
557 {
558 inc_by (stat_insert_found_hash_collision,
559 hasher (k) == hasher (key));
560 }
561 VTV_DEBUG_ASSERT (indices_examined < capacity);
562 index = next_index (index, indices_examined);
563 k = key_at_index (index);
564 }
565 }
566
567 template<typename Key, class HashFcn, class Alloc>
568 bool
569 insert_only_hash_sets<Key, HashFcn, Alloc>::insert_only_hash_set::contains
570 (key_type key) const
571 {
572 inc (stat_contains_in_non_trivial_set);
573 HashFcn hasher;
574 const size_type capacity = num_buckets;
575 size_type index = hasher (key) & (capacity - 1);
576 key_type k = key_at_index (index);
577 size_type indices_examined = 0;
578 inc (stat_probes_in_non_trivial_set);
579 while (k != key)
580 {
581 ++indices_examined;
582 if (/*UNLIKELY*/(k == (key_type) illegal_key
583 || indices_examined == capacity))
584 return false;
585
586 index = next_index (index, indices_examined);
587 k = key_at_index (index);
588 inc (stat_probes_in_non_trivial_set);
589 }
590 return true;
591 }
592
593 template <typename Key, class HashFcn, class Alloc>
594 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
595 insert_only_hash_sets<Key, HashFcn,
596 Alloc>::insert_only_hash_set::resize_if_necessary (void)
597 {
598 VTV_DEBUG_ASSERT (num_buckets >= min_capacity);
599 size_type unused = num_buckets - num_entries;
600 if (unused < (num_buckets >> 2))
601 {
602 inc (stat_double_the_number_of_buckets);
603 size_type new_num_buckets = num_buckets * 2;
604 insert_only_hash_set *s = create (new_num_buckets);
605 for (size_type i = 0; i < num_buckets; i++)
606 if (buckets[i] != (key_type) illegal_key)
607 s->insert_no_resize (buckets[i]);
608 VTV_DEBUG_ASSERT (size (this) == size (s));
609 return s;
610 }
611 else
612 return this;
613 }
614
615 template<typename Key, class HashFcn, class Alloc>
616 bool
617 insert_only_hash_sets<Key, HashFcn, Alloc>::create (size_type n,
618 insert_only_hash_set **handle)
619
620 {
621 inc (stat_create);
622 *handle = insert_only_hash_set::create (n);
623 return (n <= 1) || (*handle != NULL);
624 }
625
626 template<typename Key, class HashFcn, class Alloc>
627 bool
628 insert_only_hash_sets<Key, HashFcn, Alloc>::resize (size_type n,
629 insert_only_hash_set **handle)
630 {
631 inc (stat_resize);
632 *handle = insert_only_hash_set::resize (n, *handle);
633 return (n <= 1) || (*handle != NULL);
634 }
635
636 template<typename Key, class HashFcn, class Alloc>
637 bool
638 insert_only_hash_sets<Key, HashFcn, Alloc>::insert (key_type key,
639 insert_only_hash_set **handle)
640 {
641 inc (stat_insert);
642 const size_type old_size = insert_only_hash_set::size (*handle);
643 *handle = insert_only_hash_set::insert (key, *handle);
644 if (*handle != NULL)
645 {
646 const size_type delta = insert_only_hash_set::size (*handle) - old_size;
647 inc_by (stat_insert_key_that_was_already_present, delta == 0);
648 }
649 return *handle != NULL;
650 }
651
652 #endif /* VTV_SET_H */