registry.gno
45.67 Kb · 1220 lines
1package zones
2
3import (
4 "crypto/sha256"
5 "errors"
6 "strconv"
7
8 "gno.land/p/moul/kit/index/v0"
9 "gno.land/p/moul/kit/store/v0"
10 "gno.land/p/nt/bptree/v0"
11)
12
13// Bounds on what the registry holds.
14//
15// The LIVE registry, pending and approved zones, has a hard cap. Rejected and
16// retired zones are kept for the record but do not count against it: each has
17// a cap of its own, and when it is reached the zone that has been in that state
18// longest is dropped to make room (by when it entered the state, not when it
19// was proposed, so a long-lived network retired today is not the next to go).
20// So nothing a proposer or a curator does, and no amount of time, can fill the
21// registry for good: a cap that only ever fills is a lifetime cap, and on an
22// immutable path that is a brick.
23//
24// The per-address caps make one address cheap to ignore. Neither stops a flood
25// from many addresses, because an address is not an identity, so admission to
26// the review queue has a gate of its own (MaxPending zones, MaxUnverifiedPerZone
27// endpoints awaiting a verdict), well under the hard caps: a flood fills the
28// queue and never crowds out an approved zone or a verified endpoint. A
29// flagged endpoint has its verdict and leaves the queue, so curators keep a
30// warning instead of having to delete it to make room. The gate is checked
31// where something enters (Propose, Register); a review or a reset can push a
32// count past it, and never fails for it. ProposeExempt and RegisterExempt skip
33// it, and the per-address caps, for the reviewers a holder trusts: a full
34// queue must not lock out the people who clear it. The queue clears through
35// approval, verification, a flag, rejection, RemoveZone, RemoveEndpoint, an
36// edit leaving the local kind, and eviction. Flagged endpoints still count
37// toward MaxEndpointsPerZone: a flood a curator flags rather than removes can
38// fill the places a gated registration may use (all but the last
39// ReservedForReviewers), and removing it is the answer. Each entry costs its sender a
40// storage deposit, refunded to whoever signs the transaction that
41// frees it (on a chain where ugnot is not transfer-locked; on one that is, the
42// refund goes to the storage fee collector), so a flooder who withdraws first
43// gets it back: a bond, not a fee.
44const (
45 MaxZones = 256 // pending and approved zones together
46 MaxPending = 64 // zones awaiting review, all proposers together
47 MaxPendingPerProposer = 4 // open proposals one address may have at once
48 MaxRejected = 64 // rejected zones kept for the record
49 MaxRetired = 128 // retired zones kept for the record
50 MaxEndpointsPerZone = 128
51 MaxUnverifiedPerZone = 64 // endpoints on one zone still waiting for a verdict (flagged ones have theirs)
52 MaxEndpointsPerAddress = 16 // endpoints one address may register on one zone
53 // MaxDropPerEdit bounds how many endpoints one edit off the local kind
54 // drops, and so its gas: a removal rewrites up to about 45 later values in
55 // two B+ tree leaves, and a caller can lay ids out so every removal does,
56 // which at 128 measured 2.6B, close to a 3B block, and at 64 measures
57 // 2.02B even with a chain-id reset spread across leaves and both own URLs
58 // moved in the same edit. More waits for removals.
59 MaxDropPerEdit = 64
60 // ReservedForReviewers is how much of each hard cap (MaxZones live,
61 // MaxEndpointsPerZone) only the exempt calls may use: strangers who keep
62 // a cap full refill it the block after a curator clears it, and a cap a
63 // curator cannot reach is one they cannot act under.
64 ReservedForReviewers = 16
65)
66
67// The reasons an endpoint carries when its zone changed under it and sent it
68// back to unverified. A reset caused by an edit to a pending zone by its own
69// proposer records nobody, because that is not a review: ReviewedBy is empty
70// and Reason says why. Every other reset (a rejection, a retirement, anybody
71// else's edit, any edit to an approved zone) records whoever caused it.
72const (
73 ChainIDChanged = "the zone's chain id changed; verify again"
74 ZoneRetired = "the zone was retired; verify again if it returns"
75 ZoneRejected = "the zone was rejected; verify again if it is approved"
76)
77
78// IsReset reports whether an unverified endpoint is unverified only because its
79// zone changed under it: its reason is one of the three above. A reset reaches
80// only a verified endpoint, so it says nothing against the endpoint itself.
81func IsReset(e Endpoint) bool {
82 return e.Status == Unverified && (e.Reason == ChainIDChanged || e.Reason == ZoneRetired || e.Reason == ZoneRejected)
83}
84
85// sequences are the registry-wide counters: the last Revision handed out (so
86// none is reused) and the last status-entry sequence (the eviction order).
87type sequences struct{ rev, seq uint64 }
88
89// fanout is the B+ tree fanout for every container this package builds itself:
90// 32, not the 128 EFFECTIVE_GNO.md measured cheapest in memory. Every value in
91// a B+ tree leaf is a boxed object of its own, and removing (or inserting) a
92// key shifts every later value in the leaf, each shift a store write. Measured
93// on a node, one transaction per step (gno master 3cc494ec4): removing the
94// first key of a fanout-128 leaf filled with 120 cost 15.8M gas, the last 5.1M,
95// about 90k gas per entry shifted for a scalar value (the counters, the unique
96// ids) and about 230k for a pointer (the zone and endpoint tables, kit/index);
97// at fanout 32 each costs the same per shift, on a leaf a quarter the size. Endpoints are removed and their dedup keys inserted at
98// arbitrary positions, so the smaller leaf is worth its larger node overhead
99// (671 B per entry against 592).
100const fanout = 32
101
102// Registry holds the zones and their endpoints. The zero value is not usable:
103// call [NewRegistry]. All its state is behind pointers, so a copy of the value
104// is the same registry, not a second one sharing half of it.
105//
106// Every write touches its record and all of that record's indexes in one
107// method. The index writes cannot fail as written: every key is validated
108// non-empty and every unique key is checked free before the first write. If a
109// later change made one fail, the method returns the error and the holding
110// realm's abort undoes the half-applied write; that abort, not this method, is
111// the atomicity guarantee.
112type Registry struct {
113 // The two sequences live behind a pointer like every container here, so a
114 // copied Registry value shares them: with them inline, r2 := *r1 would
115 // share every zone but count revisions on its own, and hand out a revision
116 // r1 had already used, which a stale decision would then pass.
117 ids *sequences
118
119 zones *table
120 bySlug *unique // slug -> zone id
121 byStatus *index.Index // status -> zone ids, so a page reads only its rows
122 entered *unique // status|entry sequence -> zone id: who has been in a state longest
123 byProposer *counter // proposer -> how many PENDING zones they have
124 approved *index.Index // chain id -> ids of APPROVED zones naming it
125
126 endpoints *table
127 byAddress *unique // slug|kind|hash(canonical address) -> endpoint id
128 byZone *index.Index // slug -> endpoint ids
129 byKind *index.Index // slug|kind -> endpoint ids, so a page reads only its rows
130 byOwner *counter // slug|registrant -> how many endpoints they registered
131 unchecked *index.Index // slug -> ids of endpoints that are not Verified
132 flagged *counter // slug -> how many of those are Flagged
133 fresh *counter // slug -> how many endpoints are Clearable
134 private *index.Index // slug -> ids of endpoints on a private host (a local zone's only)
135}
136
137// NewRegistry returns an empty registry.
138func NewRegistry() *Registry {
139 return &Registry{
140 ids: &sequences{},
141 zones: newTable(),
142 bySlug: newUnique(),
143 byStatus: index.New(),
144 entered: newUnique(),
145 byProposer: newCounter(),
146 approved: index.New(),
147 endpoints: newTable(),
148 byAddress: newUnique(),
149 byZone: index.New(),
150 byKind: index.New(),
151 byOwner: newCounter(),
152 flagged: newCounter(),
153 fresh: newCounter(),
154 unchecked: index.New(),
155 private: index.New(),
156 }
157}
158
159// Propose files a new zone, Pending, under a slug nobody holds.
160func (r *Registry) Propose(by address, at int64, slug string, in Info) error {
161 return r.propose(by, at, slug, in, true)
162}
163
164// ProposeExempt is Propose without the admission gates (MaxPending and
165// MaxPendingPerProposer), for the reviewers a holding realm trusts: a flood
166// that fills the queue would otherwise lock out the people who clear it. It
167// also takes the last ReservedForReviewers places of the live registry, which
168// Propose may not; MaxZones itself still holds.
169func (r *Registry) ProposeExempt(by address, at int64, slug string, in Info) error {
170 return r.propose(by, at, slug, in, false)
171}
172
173func (r *Registry) propose(by address, at int64, slug string, in Info, gated bool) error {
174 in = trimInfo(in)
175 if err := ValidateSlug(slug); err != nil {
176 return err
177 }
178 if err := ValidateInfo(in); err != nil {
179 return err
180 }
181 if !ValidAddress(by) {
182 return errors.New("zones: the proposer is not a valid lowercase address")
183 }
184 if r.bySlug.has(slug) {
185 return errors.New("zones: the slug " + strconv.Quote(slug) + " is taken")
186 }
187 if r.Live() >= MaxZones {
188 return errors.New("zones: the registry is full at " + strconv.Itoa(MaxZones) + " pending and approved zones")
189 }
190 if gated && r.Live() >= MaxZones-ReservedForReviewers {
191 return errors.New("zones: the registry's last " + strconv.Itoa(ReservedForReviewers) + " places are kept for curators")
192 }
193 if gated && r.byStatus.Count(string(Pending)) >= MaxPending {
194 return errors.New("zones: " + strconv.Itoa(MaxPending) + " proposals are already waiting for review; try again once a curator has cleared some")
195 }
196 if n := r.byProposer.count(by.String()); gated && n >= MaxPendingPerProposer {
197 return errors.New("zones: " + by.String() + " already has " + strconv.Itoa(n) +
198 " pending proposals, the limit is " + strconv.Itoa(MaxPendingPerProposer))
199 }
200 z := &Zone{Slug: slug, Proposer: by, ProposedAt: at}
201 z.setInfo(in)
202 id := r.zones.add(z)
203 r.bySlug.set(slug, id)
204 r.byProposer.inc(by.String())
205 return r.enter(z, id, Pending)
206}
207
208// enter files a zone under a status, and bumps its Revision: a decision
209// prepared against the old status must fail too, or an approval opened before
210// a colleague's rejection would quietly reverse it. Only the two states that
211// evict read the entry order, so only they write it. The caller has already
212// taken the zone out of its old status.
213func (r *Registry) enter(z *Zone, id store.ID, to Status) error {
214 r.ids.seq++
215 r.ids.rev++
216 z.Status, z.Entered, z.Revision = to, int64(r.ids.seq), int64(r.ids.rev)
217 if evicts(to) {
218 r.entered.set(enteredKey(to, z.Entered), id)
219 }
220 return r.byStatus.Add(string(to), id)
221}
222
223func evicts(st Status) bool { return st == Rejected || st == Retired }
224
225// leave takes a zone out of its current status.
226func (r *Registry) leave(z *Zone, id store.ID) {
227 r.byStatus.Remove(string(z.Status), id)
228 if evicts(z.Status) {
229 r.entered.remove(enteredKey(z.Status, z.Entered))
230 }
231 if z.Status == Pending {
232 r.byProposer.dec(z.Proposer.String())
233 }
234 if z.Status == Approved {
235 r.approved.Remove(z.ChainID, id)
236 }
237}
238
239func enteredKey(st Status, seq int64) string { return string(st) + "|" + store.ID(seq).Key() }
240
241// Edit replaces a zone's Info: every field but the slug and the status.
242//
243// Only a pending or an approved zone can be edited. A rejected one is removed
244// and proposed again, or approved first; a retired one is a record, and its
245// retirement reason is the thing it is kept for.
246//
247// Every edit bumps the zone's Revision and records who made it and when. On a
248// pending zone that is all, and a reason is refused rather than silently
249// dropped: nobody has reviewed anything yet. On an approved zone an edit is a
250// curator decision of its own: the reviewed values changed, so the review on
251// record is replaced by this one, with a reason required.
252//
253// When the chain id changes, whatever the status, every endpoint verified
254// against the old one goes back to unverified: what was verified was that it
255// answered for a chain this zone no longer names. A reset caused by the
256// proposer's own edit to a pending zone records no reviewer; any other records
257// the editor. An edit that changes nothing is refused, and leaving the local
258// kind removes every endpoint on a private or special-use host (IsPrivateHost),
259// at most MaxDropPerEdit in one edit, and is refused while one of them carries
260// a curator's ruling.
261//
262// An edit names the revision it was written against, like an approval does, so
263// two editors working from the same reading cannot silently undo each other.
264func (r *Registry) Edit(slug string, revision int64, in Info, by address, at int64, reason string) error {
265 z, zid, err := r.zone(slug)
266 if err != nil {
267 return err
268 }
269 if err := stale(z, revision); err != nil {
270 return err
271 }
272 if z.Status != Pending && z.Status != Approved {
273 return errors.New("zones: " + slug + " is " + string(z.Status) + "; only a pending or approved zone can be edited")
274 }
275 in = trimInfo(in)
276 if err := ValidateInfo(in); err != nil {
277 return err
278 }
279 if !ValidAddress(by) {
280 return errors.New("zones: the editor is not a valid lowercase address")
281 }
282 reason = TrimSpaces(reason)
283 if err := ValidateReason(reason); err != nil {
284 return err
285 }
286 switch {
287 case z.Status == Pending && reason != "":
288 return errors.New("zones: " + slug + " is pending, and an edit before review takes no reason")
289 case z.Status == Approved && !HasVisible(reason):
290 return errors.New("zones: " + slug + " is approved, so an edit needs a reason")
291 }
292 // An edit that changes nothing would still bump the revision, so refusing
293 // it is what stops a revision being bumped for its own sake.
294 if in == z.Info() {
295 return errors.New("zones: that edit changes nothing on " + slug)
296 }
297 // Leaving the local kind drops the private hosts only a local zone may
298 // list, whatever their verdict: they name nothing on the zone it becomes.
299 // Dropped in the edit itself, not refused until somebody removes them,
300 // because anybody may register one again between that removal and this
301 // edit. Only those endpoints are read, from their own index. One a
302 // curator ruled on (a verdict, or a reset that left a reason) is a
303 // record, maybe one the editor never saw: the edit fails while one is
304 // listed, and a curator removes it first, naming its revision. Only a
305 // curator can rule, so nobody else can block the edit this way.
306 if z.Kind == Local && in.Kind != Local {
307 drop := r.private.Lookup(slug)
308 if len(drop) > MaxDropPerEdit {
309 return errors.New("zones: leaving local would drop " + strconv.Itoa(len(drop)) + " endpoints, more than " +
310 strconv.Itoa(MaxDropPerEdit) + " in one edit; remove some first")
311 }
312 for _, eid := range drop {
313 v, _ := r.endpoints.get(eid)
314 // Every verdict names its reviewer and a reset leaves a reason, so
315 // these two say "ruled on".
316 if e := v.(*Endpoint); e.ReviewedBy != "" || e.Reason != "" {
317 who := "a curator ruled on; a curator must remove it first"
318 if e.Status == Verified {
319 who = "is verified; its registrant or a curator must remove it first"
320 }
321 return errors.New("zones: leaving local would drop endpoint #" + strconv.FormatInt(e.ID, 10) + ", which " + who)
322 }
323 }
324 for _, eid := range drop {
325 r.removeEndpoint(eid)
326 }
327 }
328 if in.ChainID != z.ChainID {
329 // The proposer is not a reviewer; anybody else editing (a curator, on a
330 // pending zone or an approved one) is, and is named on the reset.
331 resetBy := address("")
332 if z.Status == Approved || by != z.Proposer {
333 resetBy = by
334 }
335 if z.Status == Approved {
336 r.approved.Remove(z.ChainID, zid)
337 if err := r.approved.Add(in.ChainID, zid); err != nil {
338 return err
339 }
340 }
341 if err := r.unverifyAll(slug, resetBy, at, ChainIDChanged); err != nil {
342 return err
343 }
344 }
345 if z.Status == Approved {
346 z.ReviewedBy, z.ReviewedAt, z.Reason = by, at, reason
347 }
348 r.ids.rev++
349 z.Revision = int64(r.ids.rev)
350 z.EditedBy, z.EditedAt = by, at
351 z.setInfo(in)
352 return nil
353}
354
355// ReviewZone records a curator's decision on a zone.
356//
357// The transitions are the curation policy, and they are deliberately few:
358//
359// approve from pending, rejected or retired reason optional
360// reject from pending reason REQUIRED
361// retire from approved reason REQUIRED
362//
363// and a decision restated: the zone's present status again, with a new
364// visible reason, which records the new reviewer and bumps the revision and
365// does nothing else (no new entry in the state, no eviction, no reset). It is
366// the only way to correct a reason.
367//
368// Every decision names the zone's Revision the curator read, and fails if the
369// zone changed since: otherwise a proposer's edit landing just before an
370// approval would become official under the curator's name, and a rejection's
371// public reason would describe text the curator never saw.
372//
373// Rejecting or retiring sends every verified endpoint back to unverified: a
374// rejected zone was never vouched for, and a retired network's peers may be
375// somebody else's hosts by the time anyone reads them. Each state keeps at most
376// MaxRejected or MaxRetired zones; the next one in drops the zone that entered
377// that state first, with its endpoints. Every transition bumps the zone's
378// Revision, so a decision prepared against the old status fails.
379//
380// Nothing goes back to pending: a rejected zone is approved after all, removed,
381// or pushed out by newer rejections. An official zone is never rejected
382// after the fact, it is retired, so the record of it having been official
383// survives.
384func (r *Registry) ReviewZone(slug string, to Status, revision int64, by address, at int64, reason string) error {
385 z, id, err := r.zone(slug)
386 if err != nil {
387 return err
388 }
389 if !ValidAddress(by) {
390 return errors.New("zones: the reviewer is not a valid lowercase address")
391 }
392 reason = TrimSpaces(reason)
393 if err := ValidateReason(reason); err != nil {
394 return err
395 }
396 if err := stale(z, revision); err != nil {
397 return err
398 }
399 if z.Status == to {
400 // A decision is restated with a new reason, the only way to correct
401 // one: a rejected or retired zone is not editable, and an edit to an
402 // approved zone must change something besides its reason.
403 if (to == Approved || to == Rejected || to == Retired) && HasVisible(reason) && reason != z.Reason {
404 r.ids.rev++
405 z.Revision = int64(r.ids.rev)
406 z.ReviewedBy, z.ReviewedAt, z.Reason = by, at, reason
407 return nil
408 }
409 return errors.New("zones: " + slug + " is already " + string(to))
410 }
411 switch to {
412 case Approved:
413 if z.Status != Pending && r.Live() >= MaxZones {
414 return errors.New("zones: the registry is full at " + strconv.Itoa(MaxZones) + " pending and approved zones")
415 }
416 case Rejected:
417 if z.Status == Approved {
418 return errors.New("zones: " + slug + " is approved; retire it instead of rejecting it")
419 }
420 if z.Status != Pending {
421 return errors.New("zones: only a pending zone can be rejected; " + slug + " is " + string(z.Status))
422 }
423 case Retired:
424 if z.Status != Approved {
425 return errors.New("zones: only an approved zone can be retired; " + slug + " is " + string(z.Status))
426 }
427 default:
428 return errors.New("zones: a review cannot set a zone to " + strconv.Quote(string(to)))
429 }
430 if (to == Rejected || to == Retired) && !HasVisible(reason) {
431 return errors.New("zones: " + string(to) + " needs a reason")
432 }
433 switch to {
434 case Rejected:
435 if err := r.unverifyAll(slug, by, at, ZoneRejected); err != nil {
436 return err
437 }
438 r.makeRoom(Rejected, MaxRejected)
439 case Retired:
440 if err := r.unverifyAll(slug, by, at, ZoneRetired); err != nil {
441 return err
442 }
443 r.makeRoom(Retired, MaxRetired)
444 }
445 r.leave(z, id)
446 if to == Approved {
447 if err := r.approved.Add(z.ChainID, id); err != nil {
448 return err
449 }
450 }
451 if err := r.enter(z, id, to); err != nil {
452 return err
453 }
454 z.ReviewedBy, z.ReviewedAt, z.Reason = by, at, reason
455 return nil
456}
457
458// stale refuses a decision written against a revision the zone has moved past.
459func stale(z *Zone, revision int64) error {
460 if revision != z.Revision {
461 return errors.New("zones: " + z.Slug + " changed since you read it: it is at revision " +
462 strconv.FormatInt(z.Revision, 10) + ", you acted on revision " + strconv.FormatInt(revision, 10) +
463 "; read it again")
464 }
465 return nil
466}
467
468// makeRoom drops the zone that has been in that state longest, when the state
469// is at its cap, so the one about to enter fits.
470func (r *Registry) makeRoom(status Status, max int) {
471 for r.byStatus.Count(string(status)) >= max {
472 var oldest store.ID
473 r.entered.tree.Iterate(string(status)+"|", string(status)+"}", func(_ string, v any) bool {
474 oldest = v.(store.ID)
475 return true
476 })
477 v, _ := r.zones.get(oldest)
478 r.removeZone(v.(*Zone), oldest)
479 }
480}
481
482// RemoveZone deletes a pending or rejected zone and every endpoint registered
483// on it, freeing their storage deposit to whoever signs the removal. It names
484// the revision it was decided on, so a removal meant for one proposal cannot
485// land on another proposed again under the same slug. A zone that has ever
486// been official cannot be removed this way: an approved one is retired, and a
487// retired one is kept until MaxRetired newer retirements push it out, so
488// whoever still holds its chain id can find out what happened to it.
489func (r *Registry) RemoveZone(slug string, revision int64) error {
490 z, id, err := r.zone(slug)
491 if err != nil {
492 return err
493 }
494 if err := stale(z, revision); err != nil {
495 return err
496 }
497 if z.Status == Approved {
498 return errors.New("zones: " + slug + " is approved; retire it instead of removing it")
499 }
500 if z.Status == Retired {
501 return errors.New("zones: " + slug + " is retired, and a retired zone is kept on record")
502 }
503 r.removeZone(z, id)
504 return nil
505}
506
507// removeZone unwinds a zone, its endpoints and every index. The per-zone index
508// keys go in one RemoveKey each rather than an id at a time, which would copy
509// the bucket once per endpoint.
510func (r *Registry) removeZone(z *Zone, id store.ID) {
511 slug := z.Slug
512 for _, eid := range r.byZone.Lookup(slug) {
513 v, ok := r.endpoints.remove(eid)
514 if !ok {
515 continue
516 }
517 r.byOwner.dec(ownerKey(slug, v.(*Endpoint).Registrant))
518 }
519 // The zone's dedup keys are one contiguous range (a slug is [a-z0-9-], all
520 // below "|"), so they are dropped without hashing each address again.
521 keys := []string{}
522 r.byAddress.tree.Iterate(slug+"|", slug+"}", func(k string, _ any) bool {
523 keys = append(keys, k)
524 return false
525 })
526 for _, k := range keys {
527 r.byAddress.remove(k)
528 }
529 r.flagged.drop(slug)
530 r.fresh.drop(slug)
531 r.byZone.RemoveKey(slug)
532 r.unchecked.RemoveKey(slug)
533 r.private.RemoveKey(slug)
534 for _, k := range EndpointKinds() {
535 r.byKind.RemoveKey(kindKey(slug, k))
536 }
537 r.leave(z, id)
538 r.bySlug.remove(slug)
539 r.zones.remove(id)
540}
541
542// Register adds an endpoint to a zone, Unverified, and returns its id.
543//
544// A zone takes endpoints while it is pending or approved, and a rejected or
545// retired zone takes none. Who may register on a pending zone is the holding
546// realm's call; a URL is stored with its scheme and host lowercased and
547// without an empty tail (trimEmptyTail), a peer lowercased whole without its
548// host's terminal dot, so what is listed is what dials (Canonical, which also drops default ports and reads tcp as http, is
549// what they are compared in, not what is stored).
550func (r *Registry) Register(by address, at int64, slug string, kind EndpointKind, addr, label string) (int64, error) {
551 return r.register(by, at, slug, kind, addr, label, true)
552}
553
554// RegisterExempt is Register without the admission gates
555// (MaxUnverifiedPerZone and MaxEndpointsPerAddress), for the reviewers a
556// holding realm trusts, as ProposeExempt is, and also takes a zone's last
557// ReservedForReviewers places; the hard cap, MaxEndpointsPerZone, still holds.
558func (r *Registry) RegisterExempt(by address, at int64, slug string, kind EndpointKind, addr, label string) (int64, error) {
559 return r.register(by, at, slug, kind, addr, label, false)
560}
561
562func (r *Registry) register(by address, at int64, slug string, kind EndpointKind, addr, label string, gated bool) (int64, error) {
563 z, _, err := r.zone(slug)
564 if err != nil {
565 return 0, err
566 }
567 if z.Status != Pending && z.Status != Approved {
568 return 0, errors.New("zones: " + slug + " is " + string(z.Status) + " and takes no endpoints")
569 }
570 addr = TrimSpaces(addr)
571 label = TrimSpaces(label)
572 if kind != Seed && kind != Peer {
573 // Validated as it will be stored, so every rule judges the string
574 // that dials, length included.
575 addr = trimEmptyTail(lowerAuthority(addr))
576 }
577 if err := ValidateEndpoint(kind, addr); err != nil {
578 return 0, err
579 }
580 if kind == Seed || kind == Peer {
581 addr = Canonical(kind, addr) // lowercase, no terminal dot: what tm2 dials
582 }
583 private := IsPrivateHost(HostOf(kind, addr))
584 if z.Kind != Local && private {
585 return 0, errors.New("zones: " + slug + " is a " + string(z.Kind) + " zone, and " + addr +
586 " names a private or special-use host; only a local zone lists those")
587 }
588 if err := ValidateLabel(label); err != nil {
589 return 0, err
590 }
591 if !ValidAddress(by) {
592 return 0, errors.New("zones: the registrant is not a valid lowercase address")
593 }
594 akey := addressKey(slug, kind, addr)
595 if r.byAddress.has(akey) {
596 return 0, errors.New("zones: " + slug + " already lists that " + string(kind) + ": " + addr)
597 }
598 if n := r.byZone.Count(slug); n >= MaxEndpointsPerZone {
599 return 0, errors.New("zones: " + slug + " is full at " + strconv.Itoa(MaxEndpointsPerZone) + " endpoints")
600 } else if gated && n >= MaxEndpointsPerZone-ReservedForReviewers {
601 return 0, errors.New("zones: " + slug + "'s last " + strconv.Itoa(ReservedForReviewers) + " endpoint places are kept for curators")
602 }
603 if n := r.Awaiting(slug); gated && n >= MaxUnverifiedPerZone {
604 return 0, errors.New("zones: " + slug + " already has " + strconv.Itoa(n) +
605 " endpoints waiting for review; try again once a curator has cleared some")
606 }
607 okey := ownerKey(slug, by)
608 if n := r.byOwner.count(okey); gated && n >= MaxEndpointsPerAddress {
609 return 0, errors.New("zones: " + by.String() + " already registered " + strconv.Itoa(n) +
610 " endpoints on " + slug + ", the limit is " + strconv.Itoa(MaxEndpointsPerAddress))
611 }
612 e := &Endpoint{Zone: slug, Kind: kind, Address: addr, Label: label, Registrant: by, RegisteredAt: at, Status: Unverified, Exempt: !gated}
613 id := r.endpoints.add(e)
614 e.ID = int64(id)
615 r.ids.rev++
616 e.Revision = int64(r.ids.rev)
617 r.byAddress.set(akey, id)
618 if err := r.byZone.Add(slug, id); err != nil {
619 return 0, err
620 }
621 if err := r.byKind.Add(kindKey(slug, kind), id); err != nil {
622 return 0, err
623 }
624 r.byOwner.inc(okey)
625 if gated {
626 r.fresh.inc(slug)
627 }
628 if err := r.unchecked.Add(slug, id); err != nil {
629 return 0, err
630 }
631 if private {
632 if err := r.private.Add(slug, id); err != nil {
633 return 0, err
634 }
635 }
636 return e.ID, nil
637}
638
639// ReviewEndpoint records a curator's verdict on an endpoint. Any verdict may
640// follow any other, and the same one again with a new reason (so a typo is
641// corrected without passing through a state its registrant may remove it
642// from), with these rules:
643//
644// - every verdict names the endpoint's Revision as read, and fails if the
645// endpoint changed since: a verdict landing after another curator's,
646// unseen, would silently reverse it;
647// - flagging needs a reason, because "do not use this" with no why is not
648// something an operator can act on;
649// - a verification also names the zone's Revision it was checked against,
650// and fails if the zone changed since: what is verified is that the
651// endpoint answers for THIS zone's chain id, and a proposer could otherwise
652// switch it while the verdict is in flight. A flag or an unverify does
653// not, so an edit to the zone cannot hold off a warning;
654// - only an endpoint of a pending or approved zone can be verified.
655func (r *Registry) ReviewEndpoint(id int64, to Verification, zoneRevision, revision int64, by address, at int64, reason string) error {
656 e, err := r.endpoint(id)
657 if err != nil {
658 return err
659 }
660 if !ValidAddress(by) {
661 return errors.New("zones: the reviewer is not a valid lowercase address")
662 }
663 reason = TrimSpaces(reason)
664 if err := ValidateReason(reason); err != nil {
665 return err
666 }
667 switch to {
668 case Unverified, Verified, Flagged:
669 case "":
670 return errors.New("zones: a review needs a verdict")
671 default:
672 // Exact values only: ParseVerification trims, and a " verified " stored
673 // as written would match no filter and count as unverified forever.
674 return errors.New("zones: unknown verification " + strconv.Quote(string(to)) + ", want verified, unverified or flagged")
675 }
676 if e.Status == to && (reason == e.Reason || !HasVisible(reason)) {
677 return errors.New("zones: endpoint #" + strconv.FormatInt(id, 10) + " is already " + string(to) +
678 "; restating it needs a new reason")
679 }
680 if to == Flagged && !HasVisible(reason) {
681 return errors.New("zones: flagging an endpoint needs a reason")
682 }
683 z, _, err := r.zone(e.Zone)
684 if err != nil {
685 return err
686 }
687 if revision != e.Revision {
688 return errors.New("zones: endpoint #" + strconv.FormatInt(id, 10) + " changed since you checked it: it is at revision " +
689 strconv.FormatInt(e.Revision, 10) + ", you acted on revision " + strconv.FormatInt(revision, 10))
690 }
691 if to == Verified {
692 if z.Status != Pending && z.Status != Approved {
693 return errors.New("zones: " + z.Slug + " is " + string(z.Status) + "; nothing on it can be verified")
694 }
695 if zoneRevision != z.Revision {
696 return errors.New("zones: " + z.Slug + " changed since you checked it against it: it is at revision " +
697 strconv.FormatInt(z.Revision, 10) + ", you verified against revision " + strconv.FormatInt(zoneRevision, 10))
698 }
699 }
700 sid := store.ID(id)
701 if to == Verified {
702 r.unchecked.Remove(e.Zone, sid)
703 } else if e.Status == Verified {
704 if err := r.unchecked.Add(e.Zone, sid); err != nil {
705 return err
706 }
707 }
708 if e.Status == Flagged {
709 r.flagged.dec(e.Zone)
710 }
711 if to == Flagged {
712 r.flagged.inc(e.Zone)
713 }
714 if e.Clearable() {
715 r.fresh.dec(e.Zone) // its first verdict: somebody has ruled on it now
716 }
717 e.Status = to
718 e.ReviewedBy, e.ReviewedAt, e.Reason = by, at, reason
719 r.ids.rev++
720 e.Revision = int64(r.ids.rev)
721 return nil
722}
723
724// unverifyAll sends every verified endpoint of a zone back to unverified with
725// that reason, and by as the reviewer ("" when the proposer's own edit caused
726// it). Flagged ones keep their flag. Only the verified ones are read: their
727// ids are the zone's ids minus the unchecked ones, both kept ascending, so one
728// merge pass finds them without loading the rest.
729func (r *Registry) unverifyAll(slug string, by address, at int64, reason string) error {
730 all := r.byZone.Lookup(slug)
731 skip := r.unchecked.Lookup(slug)
732 j := 0
733 for _, id := range all {
734 for j < len(skip) && skip[j] < id {
735 j++
736 }
737 if j < len(skip) && skip[j] == id {
738 continue
739 }
740 v, ok := r.endpoints.get(id)
741 if !ok {
742 continue
743 }
744 e := v.(*Endpoint)
745 if err := r.unchecked.Add(slug, id); err != nil {
746 return err
747 }
748 e.Status = Unverified
749 e.ReviewedBy, e.ReviewedAt, e.Reason = by, at, reason
750 r.ids.rev++
751 e.Revision = int64(r.ids.rev)
752 }
753 return nil
754}
755
756// RemoveEndpoint deletes an endpoint, freeing its storage deposit to whoever
757// signs the removal. revision is the endpoint's Revision as read: a removal
758// fails if a verdict landed since, rather than delete one nobody saw. Who may
759// is the holding realm's call.
760func (r *Registry) RemoveEndpoint(id, revision int64) error {
761 e, err := r.endpoint(id)
762 if err != nil {
763 return err
764 }
765 if revision != e.Revision {
766 return errors.New("zones: endpoint #" + strconv.FormatInt(id, 10) + " changed since you read it: it is at revision " +
767 strconv.FormatInt(e.Revision, 10) + ", you acted on revision " + strconv.FormatInt(revision, 10))
768 }
769 r.removeEndpoint(store.ID(id))
770 return nil
771}
772
773// removeEndpoint unwinds the record and all eight of its indexes and counters
774// together.
775func (r *Registry) removeEndpoint(id store.ID) {
776 v, ok := r.endpoints.remove(id)
777 if !ok {
778 return
779 }
780 e := v.(*Endpoint)
781 r.byAddress.remove(addressKey(e.Zone, e.Kind, e.Address))
782 r.byZone.Remove(e.Zone, id)
783 r.byKind.Remove(kindKey(e.Zone, e.Kind), id)
784 r.byOwner.dec(ownerKey(e.Zone, e.Registrant))
785 r.unchecked.Remove(e.Zone, id)
786 r.private.Remove(e.Zone, id)
787 if e.Status == Flagged {
788 r.flagged.dec(e.Zone)
789 }
790 if e.Clearable() {
791 r.fresh.dec(e.Zone)
792 }
793}
794
795// Revision is the last revision handed out, to a zone or an endpoint. Anything
796// that changes after a read gets a later one.
797func (r *Registry) Revision() int64 { return int64(r.ids.rev) }
798
799// PrivateEndpoints returns a zone's endpoints on a private host, the ones
800// leaving the local kind drops. Only those are read.
801func (r *Registry) PrivateEndpoints(slug string) []Endpoint {
802 out := []Endpoint{}
803 for _, id := range r.private.Lookup(slug) {
804 if v, ok := r.endpoints.get(id); ok {
805 out = append(out, *v.(*Endpoint))
806 }
807 }
808 return out
809}
810
811// Zone returns a copy of the zone under slug.
812func (r *Registry) Zone(slug string) (Zone, bool) {
813 z, _, err := r.zone(slug)
814 if err != nil {
815 return Zone{}, false
816 }
817 return *z, true
818}
819
820// Endpoint returns a copy of the endpoint with that id.
821func (r *Registry) Endpoint(id int64) (Endpoint, bool) {
822 e, err := r.endpoint(id)
823 if err != nil {
824 return Endpoint{}, false
825 }
826 return *e, true
827}
828
829// EndpointByAddress returns a copy of the endpoint a zone lists under that kind
830// and address, compared in [Canonical] form.
831func (r *Registry) EndpointByAddress(slug string, kind EndpointKind, addr string) (Endpoint, bool) {
832 id, ok := r.byAddress.get(addressKey(slug, kind, addr))
833 if !ok {
834 return Endpoint{}, false
835 }
836 v, ok := r.endpoints.get(id)
837 if !ok {
838 return Endpoint{}, false
839 }
840 return *v.(*Endpoint), true
841}
842
843// ZoneFilter selects zones. A zero field matches anything.
844type ZoneFilter struct {
845 Status Status
846 Kind Kind
847}
848
849// Match reports whether z passes the filter.
850func (f ZoneFilter) Match(z Zone) bool {
851 return (f.Status == "" || z.Status == f.Status) && (f.Kind == "" || z.Kind == f.Kind)
852}
853
854// Zones returns copies of the zones passing f, in the order they were
855// proposed. With a status set it reads that status's zones only.
856//
857// The result, like Endpoints', is capped at its length. A slice handed to
858// another realm is readonly there: an append that fits in spare capacity
859// writes into it and aborts, one that does not copies and succeeds. Uncapped,
860// an importer's append would pass or abort by how many rows the filter
861// dropped, which strangers decide by registering.
862func (r *Registry) Zones(f ZoneFilter) []Zone {
863 if f.Status != "" {
864 ids := r.byStatus.Lookup(string(f.Status))
865 out := make([]Zone, 0, len(ids))
866 for _, id := range ids {
867 v, _ := r.zones.get(id)
868 if z := v.(*Zone); f.Match(*z) {
869 out = append(out, *z)
870 }
871 }
872 return out[:len(out):len(out)]
873 }
874 out := make([]Zone, 0, r.zones.len())
875 r.zones.each(func(v any) {
876 if z := v.(*Zone); f.Match(*z) {
877 out = append(out, *z)
878 }
879 })
880 return out[:len(out):len(out)]
881}
882
883// ZoneCount returns how many zones have that status ("" for all), without
884// reading any.
885func (r *Registry) ZoneCount(status Status) int {
886 if status == "" {
887 return r.zones.len()
888 }
889 return r.byStatus.Count(string(status))
890}
891
892// Live returns how many zones are pending or approved: what MaxZones bounds.
893func (r *Registry) Live() int {
894 return r.byStatus.Count(string(Pending)) + r.byStatus.Count(string(Approved))
895}
896
897// ZonePage returns page (1-based) of the zones with that status ("" for every
898// status), size per page, in proposal order. A page past the end is empty.
899//
900// It reads the zones ON the page only; the status's id list (one object, at
901// most MaxZones ids) is read whole and sliced.
902func (r *Registry) ZonePage(status Status, page, size int) []Zone {
903 if status == "" {
904 n := r.zones.len()
905 if page < 1 || size < 1 || page-1 > n/size {
906 return []Zone{}
907 }
908 if size > n {
909 size = n
910 }
911 out := make([]Zone, 0, size)
912 //gnovet:ignore page-offset-overflow bounded by page-1 > n/size at the top
913 r.zones.page((page-1)*size, size, func(v any) { out = append(out, *v.(*Zone)) })
914 return out
915 }
916 ids := pageOf(r.byStatus.Lookup(string(status)), page, size)
917 out := make([]Zone, 0, len(ids))
918 for _, id := range ids {
919 v, _ := r.zones.get(id)
920 out = append(out, *v.(*Zone))
921 }
922 return out
923}
924
925// ApprovedByChainID returns the approved zones naming that chain id, in
926// proposal order. Usually one, but chain ids are not unique across networks
927// (every gnodev is "dev"), so it is a list. Only approved zones are indexed, so
928// proposals naming a real chain id cost a reader of this nothing.
929func (r *Registry) ApprovedByChainID(chainID string) []Zone {
930 ids := r.approved.Lookup(chainID)
931 out := make([]Zone, 0, len(ids))
932 for _, id := range ids {
933 v, _ := r.zones.get(id)
934 out = append(out, *v.(*Zone))
935 }
936 return out
937}
938
939// SoleApproved returns the approved zone naming that chain id when there is
940// exactly one, which is the only case a reader can be pointed at it without a
941// guess. It counts first and reads one record at most.
942func (r *Registry) SoleApproved(chainID string) (Zone, bool) {
943 if r.approved.Count(chainID) != 1 {
944 return Zone{}, false
945 }
946 id, _ := r.approved.First(chainID)
947 v, _ := r.zones.get(id)
948 return *v.(*Zone), true
949}
950
951// EndpointFilter selects endpoints. A zero field matches anything.
952type EndpointFilter struct {
953 Zone string
954 Kind EndpointKind
955 Status Verification
956 Registrant address
957}
958
959// Match reports whether e passes the filter.
960func (f EndpointFilter) Match(e Endpoint) bool {
961 return (f.Zone == "" || e.Zone == f.Zone) &&
962 (f.Kind == "" || e.Kind == f.Kind) &&
963 (f.Status == "" || e.Status == f.Status) &&
964 (f.Registrant == "" || e.Registrant == f.Registrant)
965}
966
967// Endpoints returns copies of the endpoints passing f, oldest first. With a
968// zone set it reads that zone's ids only (that kind's, with a kind set), so it
969// costs at most MaxEndpointsPerZone records. Without one it reads every
970// endpoint in the registry: bound it yourself.
971func (r *Registry) Endpoints(f EndpointFilter) []Endpoint {
972 if f.Zone != "" {
973 var ids []store.ID
974 if f.Kind != "" {
975 ids = r.byKind.Lookup(kindKey(f.Zone, f.Kind))
976 } else {
977 ids = r.byZone.Lookup(f.Zone)
978 }
979 out := make([]Endpoint, 0, len(ids))
980 for _, id := range ids {
981 v, _ := r.endpoints.get(id)
982 if e := v.(*Endpoint); f.Match(*e) {
983 out = append(out, *e)
984 }
985 }
986 return out[:len(out):len(out)]
987 }
988 out := make([]Endpoint, 0, r.endpoints.len())
989 r.endpoints.each(func(v any) {
990 if e := v.(*Endpoint); f.Match(*e) {
991 out = append(out, *e)
992 }
993 })
994 return out[:len(out):len(out)]
995}
996
997// Count returns how many endpoints a zone has, and how many of them are
998// verified, from the index counts: no endpoint is read.
999func (r *Registry) Count(slug string) (verified, total int) {
1000 total = r.byZone.Count(slug)
1001 return total - r.unchecked.Count(slug), total
1002}
1003
1004// EndpointCount returns how many endpoints of that kind a zone has; "" is
1005// every kind. No endpoint is read.
1006func (r *Registry) EndpointCount(slug string, kind EndpointKind) int {
1007 if kind == "" {
1008 return r.byZone.Count(slug)
1009 }
1010 return r.byKind.Count(kindKey(slug, kind))
1011}
1012
1013// Awaiting returns how many of a zone's endpoints are waiting for a verdict,
1014// what MaxUnverifiedPerZone gates. No endpoint is read.
1015func (r *Registry) Awaiting(slug string) int {
1016 return r.unchecked.Count(slug) - r.flagged.count(slug)
1017}
1018
1019// Clearable returns how many of a zone's endpoints are Clearable, what a bulk
1020// clear could remove. No endpoint is read.
1021func (r *Registry) Clearable(slug string) int { return r.fresh.count(slug) }
1022
1023// OwnerCount returns how many endpoints that address registered on a zone. No
1024// endpoint is read.
1025func (r *Registry) OwnerCount(slug string, who address) int {
1026 return r.byOwner.count(ownerKey(slug, who))
1027}
1028
1029// EndpointPage returns page (1-based) of a zone's endpoints of that kind, ""
1030// for every kind, size per page, oldest first. Like [Registry.ZonePage] it reads
1031// the records on the page only, and the bucket's id list (at most
1032// MaxEndpointsPerZone ids) whole.
1033func (r *Registry) EndpointPage(slug string, kind EndpointKind, page, size int) []Endpoint {
1034 var ids []store.ID
1035 if kind != "" {
1036 ids = r.byKind.Lookup(kindKey(slug, kind))
1037 } else {
1038 ids = r.byZone.Lookup(slug)
1039 }
1040 ids = pageOf(ids, page, size)
1041 out := make([]Endpoint, 0, len(ids))
1042 for _, id := range ids {
1043 v, _ := r.endpoints.get(id)
1044 out = append(out, *v.(*Endpoint))
1045 }
1046 return out
1047}
1048
1049// pageOf slices ids to one page, 1-based. Out of range is empty, never a
1050// panic: page and size usually come from a reader's query string.
1051func pageOf(ids []store.ID, page, size int) []store.ID {
1052 // The division comes first so a page number near MaxInt cannot overflow
1053 // the multiplication into a small positive offset.
1054 if page < 1 || size < 1 || page-1 > len(ids)/size {
1055 return nil
1056 }
1057 //gnovet:ignore page-offset-overflow bounded by page-1 > len(ids)/size above
1058 start := (page - 1) * size
1059 if start >= len(ids) {
1060 return nil
1061 }
1062 end := len(ids)
1063 if len(ids)-start > size {
1064 end = start + size
1065 }
1066 return ids[start:end]
1067}
1068
1069// Len returns how many zones the registry holds, whatever their status.
1070func (r *Registry) Len() int { return r.zones.len() }
1071
1072func (r *Registry) zone(slug string) (*Zone, store.ID, error) {
1073 id, ok := r.bySlug.get(slug)
1074 if !ok {
1075 return nil, 0, errors.New("zones: no zone " + strconv.Quote(slug))
1076 }
1077 v, _ := r.zones.get(id)
1078 return v.(*Zone), id, nil
1079}
1080
1081func (r *Registry) endpoint(id int64) (*Endpoint, error) {
1082 if id <= 0 {
1083 return nil, errors.New("zones: no endpoint #" + strconv.FormatInt(id, 10))
1084 }
1085 v, ok := r.endpoints.get(store.ID(id))
1086 if !ok {
1087 return nil, errors.New("zones: no endpoint #" + strconv.FormatInt(id, 10))
1088 }
1089 return v.(*Endpoint), nil
1090}
1091
1092// addressKey is the dedup key: the zone, the kind, and a hash of the address
1093// in [Canonical] form. Hashed so the address part of the key is 16 bytes
1094// whatever the URL's length,
1095// instead of a second copy of up to MaxURLLen bytes the record already holds,
1096// and kept raw rather than hex: it is a key, never shown. Truncated to 128
1097// bits, which no accidental collision reaches and which only lets a deliberate
1098// one refuse its own registration. It is the last field, so a byte that happens
1099// to be "|" cannot be mistaken for a separator.
1100func addressKey(slug string, kind EndpointKind, addr string) string {
1101 sum := sha256.Sum256([]byte(Canonical(kind, addr)))
1102 return slug + "|" + string(kind) + "|" + string(sum[:16])
1103}
1104
1105func kindKey(slug string, kind EndpointKind) string { return slug + "|" + string(kind) }
1106
1107func ownerKey(slug string, who address) string { return slug + "|" + who.String() }
1108
1109// trimInfo normalizes what a caller typed before it is validated: spaces
1110// around every field, and each URL's scheme and host lowercased in ASCII
1111// (both are case-insensitive, gno's link sanitizer is not, so HTTPS:// would
1112// render as a dead link), and a gnoweb or genesis URL's empty tail dropped
1113// (trimEmptyTail), as an address bar writes it. Nothing else is rewritten:
1114// what fails validation is refused, not repaired, and the main RPC with an
1115// empty tail is refused.
1116func trimInfo(in Info) Info {
1117 in.ChainID = TrimSpaces(in.ChainID)
1118 in.Title = TrimSpaces(in.Title)
1119 in.Description = TrimSpaces(in.Description)
1120 in.Kind = Kind(TrimSpaces(string(in.Kind)))
1121 in.GnowebURL = trimEmptyTail(lowerAuthority(TrimSpaces(in.GnowebURL)))
1122 in.RPCURL = lowerAuthority(TrimSpaces(in.RPCURL))
1123 in.GenesisURL = trimEmptyTail(lowerAuthority(TrimSpaces(in.GenesisURL)))
1124 return in
1125}
1126
1127// table is numbered records in a B+ tree: kit/store's shape (an
1128// id that is never reused, keyed by its seqid encoding so the tree iterates in
1129// id order) on a B+ tree, the keyed, ordered container EFFECTIVE_GNO.md
1130// recommends for iteration and pagination. kit/store/v0 sits on an avl, which
1131// it measured at 2,029 B per entry against a B+ tree's 592 to 671, and about
1132// six times the gas per entry iterated, and on an immutable path that choice
1133// is permanent.
1134type table struct {
1135 tree *bptree.BPTree
1136 last uint64
1137}
1138
1139func newTable() *table { return &table{tree: bptree.NewBPTreeN(fanout)} }
1140
1141func (t *table) add(v any) store.ID {
1142 t.last++
1143 id := store.ID(t.last)
1144 t.tree.Set(id.Key(), v)
1145 return id
1146}
1147
1148func (t *table) get(id store.ID) (any, bool) {
1149 v := t.tree.Get(id.Key())
1150 return v, v != nil
1151}
1152
1153func (t *table) remove(id store.ID) (any, bool) { return t.tree.Remove(id.Key()) }
1154
1155func (t *table) len() int { return t.tree.Size() }
1156
1157func (t *table) each(fn func(v any)) {
1158 t.tree.IterateByOffset(0, t.tree.Size(), func(_ string, v any) bool {
1159 fn(v)
1160 return false
1161 })
1162}
1163
1164func (t *table) page(offset, count int, fn func(v any)) {
1165 t.tree.IterateByOffset(offset, count, func(_ string, v any) bool {
1166 fn(v)
1167 return false
1168 })
1169}
1170
1171// unique is a key -> id map in a B+ tree that holds the id itself. kit/index
1172// stores every key as three objects (a box, an entry struct, an ids array), and
1173// for a key that only ever has one id two of them say nothing.
1174type unique struct{ tree *bptree.BPTree }
1175
1176func newUnique() *unique { return &unique{tree: bptree.NewBPTreeN(fanout)} }
1177
1178func (u *unique) has(key string) bool { return u.tree.Has(key) }
1179
1180func (u *unique) get(key string) (store.ID, bool) {
1181 v := u.tree.Get(key)
1182 if v == nil {
1183 return 0, false
1184 }
1185 return v.(store.ID), true
1186}
1187
1188func (u *unique) set(key string, id store.ID) { u.tree.Set(key, id) }
1189
1190func (u *unique) remove(key string) { u.tree.Remove(key) }
1191
1192// counter is a key -> count map in a B+ tree, one object per key. What it
1193// answers (pending proposals per proposer and endpoints per registrant per
1194// zone for the caps, flagged endpoints per zone for the admission gate,
1195// clearable endpoints per zone for the bulk clear) only
1196// ever asks how many, so keeping the ids would be two more objects per key,
1197// written and deleted for nothing.
1198type counter struct{ tree *bptree.BPTree }
1199
1200func newCounter() *counter { return &counter{tree: bptree.NewBPTreeN(fanout)} }
1201
1202func (c *counter) count(key string) int {
1203 v := c.tree.Get(key)
1204 if v == nil {
1205 return 0
1206 }
1207 return v.(int)
1208}
1209
1210func (c *counter) inc(key string) { c.tree.Set(key, c.count(key)+1) }
1211
1212func (c *counter) dec(key string) {
1213 if n := c.count(key) - 1; n > 0 {
1214 c.tree.Set(key, n)
1215 } else {
1216 c.tree.Remove(key)
1217 }
1218}
1219
1220func (c *counter) drop(key string) { c.tree.Remove(key) }
