| 1 |
|
| # Shared::Arena::Cuckoo - a set that answers "no" exactly, "yes" probably, and |
| 2 |
|
| # can forget. |
| 3 |
|
| |
| 4 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena PREFIX = sar_ |
| 5 |
|
| |
| 6 |
|
| # $arena->cuckoo($name, capacity => N) |
| 7 |
|
| # |
| 8 |
|
| # Sized from how many keys it should hold. There is no rate to ask for: the |
| 9 |
|
| # fingerprint width fixes it, and a caller who needs another wants the bloom |
| 10 |
|
| # filter. |
| 11 |
|
| SV * |
| 12 |
|
| sar_cuckoo(self, name, ...) |
| 13 |
|
| SV *self |
| 14 |
|
| SV *name |
| 15 |
|
| PREINIT: |
| 16 |
|
| sa_region *arena; |
| 17 |
|
| sa_reg *e; |
| 18 |
|
| sa_cuckoo *c; |
| 19 |
|
| const char *nm; |
| 20 |
|
| STRLEN nlen; |
| 21 |
20 |
| UV capacity = 10000; |
| 22 |
|
| uint64_t buckets; |
| 23 |
20 |
| int err = SA_E_OK; |
| 24 |
|
| I32 i; |
| 25 |
|
| SV *obj; |
| 26 |
|
| CODE: |
| 27 |
20 |
| arena = SA_SELF(sa_region, self); |
| 28 |
20 |
▶ | if (!arena || !arena->map.base) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!arena || !arena->map.base) |
20 |
0 |
20 |
| if (!arena || !arena->map.base) |
0 |
20 |
20 |
|
| 29 |
0 |
| croak("Shared::Arena: this region is released"); |
| 30 |
20 |
| nm = SvPV(name, nlen); |
| 31 |
40 |
▶ | for (i = 2; i + 1 < items; i += 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 2; i + 1 < items; i += 2) { |
20 |
20 |
40 |
|
| 32 |
20 |
| const char *o = SvPV_nolen(ST(i)); |
| 33 |
20 |
▶ | if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1)); |
20 |
0 |
20 |
|
| 34 |
|
| } |
| 35 |
20 |
| buckets = sa_cuckoo_buckets((uint64_t)capacity); |
| 36 |
|
| |
| 37 |
20 |
| e = sa_carve(arena, nm, (size_t)nlen, sa_cuckoo_bytes(buckets), |
| 38 |
|
| SA_T_CUCKOO, &err); |
| 39 |
20 |
▶ | if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); |
2 |
18 |
20 |
|
| 40 |
|
| |
| 41 |
18 |
| c = sa_cuckoo_bind(arena, e, buckets, (uint64_t)capacity, &err); |
| 42 |
18 |
▶ | if (!c) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); |
1 |
17 |
18 |
|
| 43 |
|
| |
| 44 |
17 |
| obj = newSV(0); |
| 45 |
17 |
| sv_setref_pv(obj, "Shared::Arena::Cuckoo", (void *)c); |
| 46 |
17 |
| sv_magicext(SvRV(obj), SvRV(self), PERL_MAGIC_ext, NULL, NULL, 0); |
| 47 |
17 |
| SvREFCNT_inc(SvRV(self)); |
| 48 |
17 |
| RETVAL = obj; |
| 49 |
|
| OUTPUT: |
| 50 |
|
| RETVAL |
| 51 |
|
| |
| 52 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena::Cuckoo PREFIX = sack_ |
| 53 |
|
| |
| 54 |
|
| # 1 when the key is stored, 0 when there is no room for it. Every call stores a |
| 55 |
|
| # copy: a key added twice needs removing twice. |
| 56 |
|
| int |
| 57 |
|
| sack_add(self, key) |
| 58 |
|
| SV *self |
| 59 |
|
| SV *key |
| 60 |
|
| PREINIT: |
| 61 |
|
| sa_cuckoo *c; |
| 62 |
|
| const char *k; |
| 63 |
|
| STRLEN klen; |
| 64 |
|
| CODE: |
| 65 |
1 |
| c = SA_SELF(sa_cuckoo, self); |
| 66 |
1 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
1 |
1 |
|
| 67 |
1 |
| k = SvPV(key, klen); |
| 68 |
1 |
| RETVAL = sa_cuckoo_add(c, k, (uint32_t)klen); |
| 69 |
|
| OUTPUT: |
| 70 |
|
| RETVAL |
| 71 |
|
| |
| 72 |
|
| # A false answer is exact. A true one is probably right. |
| 73 |
|
| int |
| 74 |
|
| sack_check(self, key) |
| 75 |
|
| SV *self |
| 76 |
|
| SV *key |
| 77 |
|
| PREINIT: |
| 78 |
|
| sa_cuckoo *c; |
| 79 |
|
| const char *k; |
| 80 |
|
| STRLEN klen; |
| 81 |
|
| CODE: |
| 82 |
2 |
| c = SA_SELF(sa_cuckoo, self); |
| 83 |
2 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
2 |
2 |
|
| 84 |
2 |
| k = SvPV(key, klen); |
| 85 |
2 |
| RETVAL = sa_cuckoo_check(c, k, (uint32_t)klen); |
| 86 |
|
| OUTPUT: |
| 87 |
|
| RETVAL |
| 88 |
|
| |
| 89 |
|
| # 1 when a copy was found and taken out. Only for keys that were added: a key |
| 90 |
|
| # never added can take another key's copy with it. |
| 91 |
|
| int |
| 92 |
|
| sack_remove(self, key) |
| 93 |
|
| SV *self |
| 94 |
|
| SV *key |
| 95 |
|
| PREINIT: |
| 96 |
|
| sa_cuckoo *c; |
| 97 |
|
| const char *k; |
| 98 |
|
| STRLEN klen; |
| 99 |
|
| CODE: |
| 100 |
505 |
| c = SA_SELF(sa_cuckoo, self); |
| 101 |
505 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
505 |
505 |
|
| 102 |
505 |
| k = SvPV(key, klen); |
| 103 |
505 |
| RETVAL = sa_cuckoo_remove(c, k, (uint32_t)klen); |
| 104 |
|
| OUTPUT: |
| 105 |
|
| RETVAL |
| 106 |
|
| |
| 107 |
|
| void |
| 108 |
|
| sack_reset(self) |
| 109 |
|
| SV *self |
| 110 |
|
| PREINIT: |
| 111 |
|
| sa_cuckoo *c; |
| 112 |
|
| CODE: |
| 113 |
1 |
| c = SA_SELF(sa_cuckoo, self); |
| 114 |
1 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
1 |
1 |
|
| 115 |
1 |
| sa_cuckoo_reset(c); |
| 116 |
|
| |
| 117 |
|
| UV |
| 118 |
|
| sack_count(self) |
| 119 |
|
| SV *self |
| 120 |
|
| PREINIT: |
| 121 |
|
| sa_cuckoo *c; |
| 122 |
|
| CODE: |
| 123 |
10232 |
| c = SA_SELF(sa_cuckoo, self); |
| 124 |
10232 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
10232 |
10232 |
|
| 125 |
|
| #if SA_HAVE_ATOMICS |
| 126 |
10232 |
| RETVAL = (UV)sa_at_load64_acq(&c->hdr->count); |
| 127 |
|
| #else |
| 128 |
|
| RETVAL = 0; |
| 129 |
|
| #endif |
| 130 |
|
| OUTPUT: |
| 131 |
|
| RETVAL |
| 132 |
|
| |
| 133 |
|
| UV |
| 134 |
|
| sack_slots(self) |
| 135 |
|
| SV *self |
| 136 |
|
| PREINIT: |
| 137 |
|
| sa_cuckoo *c; |
| 138 |
|
| CODE: |
| 139 |
10229 |
| c = SA_SELF(sa_cuckoo, self); |
| 140 |
10229 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
10229 |
10229 |
|
| 141 |
10229 |
▶ | RETVAL = (UV)(c->buckets * SA_CK_LANES); |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (UV)(c->buckets * SA_CK_LANES); |
0 |
10229 |
10229 |
|
| 142 |
|
| OUTPUT: |
| 143 |
|
| RETVAL |
| 144 |
|
| |
| 145 |
|
| # capacity / slots / buckets / bytes / count / load / fp_rate / kicks / moves / |
| 146 |
|
| # full / recovered |
| 147 |
|
| # |
| 148 |
|
| # `load` is the number to watch: the filter refuses adds somewhere past 0.95, |
| 149 |
|
| # and `fp_rate` is what the current load makes the chance of a wrong "yes". |
| 150 |
|
| void |
| 151 |
|
| sack_stats(self) |
| 152 |
|
| SV *self |
| 153 |
|
| PREINIT: |
| 154 |
|
| sa_cuckoo *c; |
| 155 |
|
| uint64_t slots, count; |
| 156 |
|
| double load; |
| 157 |
|
| PPCODE: |
| 158 |
5 |
| c = SA_SELF(sa_cuckoo, self); |
| 159 |
5 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
5 |
5 |
|
| 160 |
5 |
| slots = c->buckets * SA_CK_LANES; |
| 161 |
|
| #if SA_HAVE_ATOMICS |
| 162 |
5 |
| count = sa_at_load64_acq(&c->hdr->count); |
| 163 |
|
| #else |
| 164 |
|
| count = 0; |
| 165 |
|
| #endif |
| 166 |
5 |
▶ | load = slots ? (double)count / (double)slots : 0.0; |
Branch: 1 branch
| Branch | True | False | Total |
| load = slots ? (double)count / (double)slots : 0.0; |
5 |
0 |
5 |
|
| 167 |
5 |
▶ | EXTEND(SP, 22); |
Branch: 1 branch
| Branch | True | False | Total |
| EXTEND(SP, 22); |
0 |
5 |
5 |
|
| 168 |
5 |
| mPUSHp("capacity", 8); mPUSHu((UV)c->hdr->capacity); |
| 169 |
5 |
| mPUSHp("slots", 5); mPUSHu((UV)slots); |
| 170 |
5 |
| mPUSHp("buckets", 7); mPUSHu((UV)c->buckets); |
| 171 |
5 |
| mPUSHp("bytes", 5); mPUSHu((UV)sa_cuckoo_bytes(c->buckets)); |
| 172 |
5 |
| mPUSHp("count", 5); mPUSHu((UV)count); |
| 173 |
5 |
| mPUSHp("load", 4); mPUSHn(load); |
| 174 |
|
| /* Eight fingerprints are compared per check, each matching a random |
| 175 |
|
| * one with probability 1/65535. */ |
| 176 |
5 |
| mPUSHp("fp_rate", 7); mPUSHn(8.0 * load / 65535.0); |
| 177 |
|
| #if SA_HAVE_ATOMICS |
| 178 |
5 |
| mPUSHp("kicks", 5); mPUSHu((UV)sa_at_load64_acq(&c->hdr->kicks)); |
| 179 |
5 |
| mPUSHp("moves", 5); mPUSHu((UV)sa_at_load64_acq(&c->hdr->moves)); |
| 180 |
5 |
| mPUSHp("full", 4); mPUSHu((UV)sa_at_load64_acq(&c->hdr->full)); |
| 181 |
5 |
| mPUSHp("recovered", 9); mPUSHu((UV)sa_at_load64_acq(&c->hdr->recovered)); |
| 182 |
|
| #endif |
| 183 |
|
| |
| 184 |
|
| # The pid the relocation lock names, and with an argument, sets it. A test |
| 185 |
|
| # hook: it is how t/32-cuckoo.t makes a lock holder that has died, without |
| 186 |
|
| # having to kill one at exactly the wrong instant. |
| 187 |
|
| UV |
| 188 |
|
| sack__owner(self, ...) |
| 189 |
|
| SV *self |
| 190 |
|
| PREINIT: |
| 191 |
|
| sa_cuckoo *c; |
| 192 |
|
| CODE: |
| 193 |
3 |
| c = SA_SELF(sa_cuckoo, self); |
| 194 |
3 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
3 |
3 |
|
| 195 |
|
| #if SA_HAVE_ATOMICS |
| 196 |
3 |
▶ | if (items > 1) sa_at_store64_rel(&c->hdr->owner, (uint64_t)SvUV(ST(1))); |
Branch: 1 branch
| Branch | True | False | Total |
| if (items > 1) sa_at_store64_rel(&c->hdr->owner, (uint64_t)SvUV(ST(1))); |
1 |
2 |
3 |
|
| 197 |
3 |
| RETVAL = (UV)sa_at_load64_acq(&c->hdr->owner); |
| 198 |
|
| #else |
| 199 |
|
| RETVAL = 0; |
| 200 |
|
| #endif |
| 201 |
|
| OUTPUT: |
| 202 |
|
| RETVAL |
| 203 |
|
| |
| 204 |
|
| # Microseconds every check that misses its first bucket sleeps before reading |
| 205 |
|
| # its second. A test hook: the window it holds open is otherwise a few |
| 206 |
|
| # instructions wide, and a test that races it passes whether or not the filter |
| 207 |
|
| # protects it. Shared by every process on the filter, and zero unless set. |
| 208 |
|
| UV |
| 209 |
|
| sack__stall(self, ...) |
| 210 |
|
| SV *self |
| 211 |
|
| PREINIT: |
| 212 |
|
| sa_cuckoo *c; |
| 213 |
|
| CODE: |
| 214 |
2 |
| c = SA_SELF(sa_cuckoo, self); |
| 215 |
2 |
▶ | if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); |
0 |
2 |
2 |
|
| 216 |
|
| #if SA_HAVE_ATOMICS |
| 217 |
2 |
▶ | if (items > 1) |
Branch: 1 branch
| Branch | True | False | Total |
| if (items > 1) |
2 |
0 |
2 |
|
| 218 |
2 |
| sa_at_store32_rel(&c->hdr->stall_us, (uint32_t)SvUV(ST(1))); |
| 219 |
2 |
▶ | RETVAL = (UV)sa_at_load32_acq(&c->hdr->stall_us); |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (UV)sa_at_load32_acq(&c->hdr->stall_us); |
0 |
2 |
2 |
|
| 220 |
|
| #else |
| 221 |
|
| RETVAL = 0; |
| 222 |
|
| #endif |
| 223 |
|
| OUTPUT: |
| 224 |
|
| RETVAL |
| 225 |
|
| |
| 226 |
|
| void |
| 227 |
|
| sack_DESTROY(self) |
| 228 |
|
| SV *self |
| 229 |
|
| PREINIT: |
| 230 |
|
| sa_cuckoo *c; |
| 231 |
|
| CODE: |
| 232 |
17 |
| c = SA_SELF(sa_cuckoo, self); |
| 233 |
17 |
▶ | if (c) { sa_cuckoo_free(c); sv_setiv(SvRV(self), 0); } |
Branch: 1 branch
| Branch | True | False | Total |
| if (c) { sa_cuckoo_free(c); sv_setiv(SvRV(self), 0); } |
17 |
0 |
17 |
|