This repository has been archived by the owner on Jul 7, 2020. It is now read-only.
forked from keybase/client
/
uidmap.go
522 lines (449 loc) · 16.9 KB
/
uidmap.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
package uidmap
import (
"errors"
"fmt"
"strings"
"sync"
"time"
lru "github.com/hashicorp/golang-lru"
"github.com/keybase/client/go/libkb"
keybase1 "github.com/keybase/client/go/protocol/keybase1"
"golang.org/x/net/context"
)
type UIDMap struct {
sync.Mutex
usernameCache map[keybase1.UID]libkb.NormalizedUsername
fullNameCache *lru.Cache
testBatchIterHook func()
testNoCachingMode bool
serverRefreshers map[keybase1.UID]keybase1.Seqno
}
func NewUIDMap(fullNameCacheSize int) *UIDMap {
cache, err := lru.New(fullNameCacheSize)
if err != nil {
panic(fmt.Sprintf("failed to make an LRU size=%d: %s", fullNameCacheSize, err))
}
return &UIDMap{
usernameCache: make(map[keybase1.UID]libkb.NormalizedUsername),
fullNameCache: cache,
serverRefreshers: make(map[keybase1.UID]keybase1.Seqno),
}
}
func usernameDBKey(u keybase1.UID) libkb.DbKey {
return libkb.DbKey{Typ: libkb.DBUidToUsername, Key: string(u)}
}
func fullNameDBKey(u keybase1.UID) libkb.DbKey {
return libkb.DbKey{Typ: libkb.DBUidToFullName, Key: string(u)}
}
type mapStatus int
const (
foundHardCoded mapStatus = iota
foundInMem mapStatus = iota
foundOnDisk mapStatus = iota
notFound mapStatus = iota
stale mapStatus = iota
)
// The number of UIDs per batch to send. It's not `const` so we can twiddle it in our tests.
var batchSize = 250
func (u *UIDMap) SetTestingNoCachingMode(enabled bool) {
u.testNoCachingMode = enabled
}
func (u *UIDMap) Clear() {
u.Lock()
defer u.Unlock()
u.usernameCache = make(map[keybase1.UID]libkb.NormalizedUsername)
u.fullNameCache.Purge()
}
func (u *UIDMap) findUsernamePackageLocally(ctx context.Context, g libkb.UIDMapperContext, uid keybase1.UID, fullNameFreshness time.Duration, forceNetworkForFullNames bool) (ret *libkb.UsernamePackage, stats mapStatus) {
nun, usernameStatus := u.findUsernameLocally(ctx, g, uid)
if usernameStatus == notFound {
return nil, notFound
}
fullName, fullNameStatus := u.findFullNameLocally(ctx, g, uid, fullNameFreshness)
return &libkb.UsernamePackage{NormalizedUsername: nun, FullName: fullName}, fullNameStatus
}
const CurrentFullNamePackageVersion = keybase1.FullNamePackageVersion_V1
func isStale(g libkb.UIDMapperContext, m keybase1.FullNamePackage, dur time.Duration) (time.Duration, bool) {
if dur == time.Duration(0) {
return time.Duration(0), false
}
now := g.GetClock().Now()
cachedAt := m.CachedAt.Time()
diff := now.Sub(cachedAt)
expired := (diff > dur)
return diff, expired
}
func (u *UIDMap) findFullNameLocally(ctx context.Context, g libkb.UIDMapperContext, uid keybase1.UID, fullNameFreshness time.Duration) (ret *keybase1.FullNamePackage, status mapStatus) {
var staleFullName *keybase1.FullNamePackage
var staleExpired time.Duration
doNotFoundReturn := func() (*keybase1.FullNamePackage, mapStatus) {
if staleFullName != nil {
return staleFullName, stale
}
return nil, notFound
}
voidp, ok := u.fullNameCache.Get(uid)
if ok {
tmp, ok := voidp.(keybase1.FullNamePackage)
if !ok {
g.GetLog().CDebugf(ctx, "Found non-FullNamePackage in LRU cache for uid=%s", uid)
} else if when, expired := isStale(g, tmp, fullNameFreshness); expired {
staleFullName = &tmp
staleExpired = when
g.GetVDebugLog().CLogf(ctx, libkb.VLog0, "fullName memory mapping %s -> %+v is expired (%s ago)", uid, tmp, when)
} else {
ret = &tmp
return ret, foundInMem
}
}
var tmp keybase1.FullNamePackage
key := fullNameDBKey(uid)
found, err := g.GetKVStore().GetInto(&tmp, key)
if err != nil {
g.GetLog().CInfof(ctx, "failed to get dbkey %v: %s", key, err)
return doNotFoundReturn()
}
if !found {
return doNotFoundReturn()
}
if tmp.Version != CurrentFullNamePackageVersion {
g.GetLog().CDebugf(ctx, "Old version (=%d) found for dbkey %s", tmp.Version, key)
return doNotFoundReturn()
}
if when, expired := isStale(g, tmp, fullNameFreshness); expired {
g.GetVDebugLog().CLogf(ctx, libkb.VLog0, "fullName disk mapping %s -> %+v is expired (%s ago)", uid, tmp, when)
if when < staleExpired {
staleFullName = &tmp
}
return doNotFoundReturn()
}
u.fullNameCache.Add(uid, tmp)
return ret, foundOnDisk
}
func (u *UIDMap) findUsernameLocally(ctx context.Context, g libkb.UIDMapperContext, uid keybase1.UID) (libkb.NormalizedUsername, mapStatus) {
un := findHardcoded(uid)
if !un.IsNil() {
return un, foundHardCoded
}
un, ok := u.usernameCache[uid]
if ok {
return un, foundInMem
}
var s string
key := usernameDBKey(uid)
found, err := g.GetKVStore().GetInto(&s, key)
if err != nil {
g.GetLog().CInfof(ctx, "failed to get dbkey %v: %s", key, err)
return libkb.NormalizedUsername(""), notFound
}
if !found {
return libkb.NormalizedUsername(""), notFound
}
ret := libkb.NewNormalizedUsername(s)
u.usernameCache[uid] = ret
return ret, foundOnDisk
}
type apiRow struct {
Username string `json:"username"`
FullName string `json:"full_name,omitempty"`
EldestSeqno keybase1.Seqno `json:"eldest_seqno"`
}
type apiReply struct {
Status libkb.AppStatus `json:"status"`
Users map[keybase1.UID]apiRow `json:"users"`
}
func (a *apiReply) GetAppStatus() *libkb.AppStatus {
return &a.Status
}
func uidsToStringForLog(uids []keybase1.UID) string {
if len(uids) < 5 {
return libkb.UidsToString(uids)
}
return fmt.Sprintf("%s,...,%s [%d total UIDs]", uids[0], uids[len(uids)-1], len(uids))
}
func (u *UIDMap) refreshersForUIDs(uids []keybase1.UID) string {
var v []string
for _, uid := range uids {
if eldestSeqno, found := u.serverRefreshers[uid]; found {
v = append(v, (keybase1.UserVersion{Uid: uid, EldestSeqno: eldestSeqno}).String())
}
}
return strings.Join(v, ",")
}
func (u *UIDMap) lookupFromServerBatch(ctx context.Context, g libkb.UIDMapperContext, uids []keybase1.UID, networkTimeBudget time.Duration) ([]libkb.UsernamePackage, error) {
noCache := u.testNoCachingMode
arg := libkb.NewRetryAPIArg("user/names")
arg.NetContext = ctx
arg.SessionType = libkb.APISessionTypeNONE
refreshers := u.refreshersForUIDs(uids)
if len(refreshers) > 0 {
g.GetLog().CDebugf(ctx, "user/names refreshers: %s", refreshers)
}
arg.Args = libkb.HTTPArgs{
"uids": libkb.S{Val: libkb.UidsToString(uids)},
"no_cache": libkb.B{Val: noCache},
"refreshers": libkb.S{Val: refreshers},
}
if networkTimeBudget > time.Duration(0) {
arg.InitialTimeout = networkTimeBudget
arg.RetryCount = 0
}
var r apiReply
err := g.GetAPI().PostDecode(arg, &r)
if err != nil {
return nil, err
}
ret := make([]libkb.UsernamePackage, len(uids), len(uids))
cachedAt := keybase1.ToTime(g.GetClock().Now())
for i, uid := range uids {
if row, ok := r.Users[uid]; ok {
nun := libkb.NewNormalizedUsername(row.Username)
if !u.CheckUIDAgainstUsername(uid, nun) {
g.GetLog().CWarningf(ctx, "Server returned bad UID -> username mapping: %s -> %s", uid, nun)
} else {
ret[i] = libkb.UsernamePackage{
NormalizedUsername: nun,
FullName: &keybase1.FullNamePackage{
Version: CurrentFullNamePackageVersion,
FullName: keybase1.FullName(row.FullName),
EldestSeqno: row.EldestSeqno,
CachedAt: cachedAt,
},
}
}
}
}
return ret, nil
}
func (u *UIDMap) lookupFromServer(ctx context.Context, g libkb.UIDMapperContext, uids []keybase1.UID, networkTimeBudget time.Duration) ([]libkb.UsernamePackage, error) {
start := g.GetClock().Now()
end := start.Add(networkTimeBudget)
var ret []libkb.UsernamePackage
for i := 0; i < len(uids); i += batchSize {
high := i + batchSize
if high > len(uids) {
high = len(uids)
}
inb := uids[i:high]
var budget time.Duration
// Only useful for testing...
if u.testBatchIterHook != nil {
u.testBatchIterHook()
}
if networkTimeBudget > time.Duration(0) {
now := g.GetClock().Now()
if now.After(end) {
return ret, errors.New("ran out of time")
}
budget = end.Sub(now)
}
outb, err := u.lookupFromServerBatch(ctx, g, inb, budget)
if err != nil {
return ret, err
}
ret = append(ret, outb...)
}
return ret, nil
}
// InformOfEldestSeqno informs the mapper of an up-to-date (uid,eldestSeqno) pair.
// If the cache has a different value, it will clear the cache and then plumb
// the pair all the way through to the server, whose cache may also be in need
// of busting. Will return true if the cached value was up-to-date, and false
// otherwise.
func (u *UIDMap) InformOfEldestSeqno(ctx context.Context, g libkb.UIDMapperContext, uv keybase1.UserVersion) (isCurrent bool, err error) {
// No entry/exit tracing, or common-case tracing, in this function since otherwise
// the spam is overwhelming.
u.Lock()
defer u.Unlock()
uid := uv.Uid
isCurrent = true
updateDisk := true
voidp, ok := u.fullNameCache.Get(uid)
if ok {
if tmp, ok := voidp.(keybase1.FullNamePackage); !ok {
g.GetLog().CDebugf(ctx, "Found non-FullNamePackage in LRU cache for uid=%s", uid)
} else if tmp.EldestSeqno < uv.EldestSeqno {
g.GetLog().CDebugf(ctx, "Stale eldest memory mapping for uid=%s; we had %d, but latest is %d", uid, tmp.EldestSeqno, uv.EldestSeqno)
u.fullNameCache.Remove(uid)
isCurrent = false
} else {
// If the memory state of this UID->Eldest mapping is correct,
// then there is no reason to check the disk state, since we should
// never have a case that the memory state is newer than the disk
// state. And hopefully this is the common case!
updateDisk = false
}
}
if updateDisk {
var tmp keybase1.FullNamePackage
key := fullNameDBKey(uid)
found, err := g.GetKVStore().GetInto(&tmp, key)
if err != nil {
g.GetLog().CDebugf(ctx, "Error reading %s from UID map disk-backed cache: %s", uid, err)
err = nil // don't break the return
}
if found && tmp.EldestSeqno < uv.EldestSeqno {
g.GetLog().CDebugf(ctx, "Stale eldest disk mapping for uid=%s; we had %d, but latest is %d", uid, tmp.EldestSeqno, uv.EldestSeqno)
g.GetKVStore().Delete(key)
isCurrent = false
}
}
if !isCurrent {
u.serverRefreshers[uid] = uv.EldestSeqno
}
return isCurrent, nil
}
// MapUIDsToUsernamePackages maps the given set of UIDs to the username packages, which include
// a username and a fullname, and when the mapping was loaded from the server. It blocks
// on the network until all usernames are known. If the `forceNetworkForFullNames` flag is specified,
// it will block on the network too. If the flag is not specified, then stale values (or unknown values)
// are OK, we won't go to network if we lack them. All network calls are limited by the given timeBudget,
// or if 0 is specified, there is indefinite budget. In the response, a nil FullNamePackage means that the
// lookup failed. A non-nil FullNamePackage means that some previous lookup worked, but
// might be arbitrarily out of date (depending on the cachedAt time). A non-nil FullNamePackage
// with an empty fullName field means that the user just hasn't supplied a fullName.
// FullNames can be cached bt the UIDMap, but expire after networkTimeBudget duration. If that value
// is 0, then infinitely stale names are allowed. If non-zero, and some names aren't stale, we'll
// have to go to the network.
//
// *NOTE* that this function can return useful data and an error. In this regard, the error is more
// like a warning. But if, for instance, the mapper runs out of time budget, it will return the data
// it was able to get, and also the error.
func (u *UIDMap) MapUIDsToUsernamePackages(ctx context.Context, g libkb.UIDMapperContext, uids []keybase1.UID, fullNameFreshness time.Duration, networkTimeBudget time.Duration, forceNetworkForFullNames bool) (res []libkb.UsernamePackage, err error) {
defer libkb.CTrace(ctx, g.GetLog(), fmt.Sprintf("MapUIDsToUserPackages(%s)", uidsToStringForLog(uids)), func() error { return err })()
u.Lock()
defer u.Unlock()
res = make([]libkb.UsernamePackage, len(uids), len(uids))
apiLookupIndex := make(map[int]int)
var uidsToLookup []keybase1.UID
for i, uid := range uids {
up, status := u.findUsernamePackageLocally(ctx, g, uid, fullNameFreshness, forceNetworkForFullNames)
// If we successfully looked up some of the user, set the return slot here.
if up != nil {
res[i] = *up
}
// There are 3 important cases when we should go to network:
//
// 1. No username is found (up == nil)
// 2. No FullName found and we've asked to force network lookups (status == notFound && forceNetworkForNullNames)
// 3. The FullName found was stale (status == stale).
//
// Thus, if you provide forceNetworkForFullName=false, and fullNameFreshness=0, you can avoid
// the network trip as long as all of your username lookups hit the cache or are hardcoded.
if u.testNoCachingMode || up == nil ||
(status == notFound && forceNetworkForFullNames) || (status == stale) {
apiLookupIndex[len(uidsToLookup)] = i
uidsToLookup = append(uidsToLookup, uid)
}
}
if len(uidsToLookup) > 0 {
var apiResults []libkb.UsernamePackage
apiResults, err = u.lookupFromServer(ctx, g, uidsToLookup, networkTimeBudget)
if err == nil {
for i, row := range apiResults {
uid := uidsToLookup[i]
if row.FullName != nil {
g.GetVDebugLog().CLogf(ctx, libkb.VLog0, "| API server resolution %s -> (%s, %v, %v)", uid,
row.NormalizedUsername, row.FullName.FullName, row.FullName.EldestSeqno)
} else {
g.GetVDebugLog().CLogf(ctx, libkb.VLog0, "| API server resolution %s -> (%s, <no fn res>)", uid,
row.NormalizedUsername)
}
// Always write these results out if the cached value is unset.
// Or, see below for other case...
writeResults := res[apiLookupIndex[i]].NormalizedUsername.IsNil()
// Fill in caches independently after a successful return. First fill in
// the username cache...
if nun := row.NormalizedUsername; !nun.IsNil() {
// If we get a non-nil NormalizedUsername from the server, then also
// write results out...
writeResults = true
u.usernameCache[uid] = nun
key := usernameDBKey(uid)
err := g.GetKVStore().PutObj(key, nil, nun.String())
if err != nil {
g.GetLog().CInfof(ctx, "failed to put %v -> %s: %s", key, nun, err)
}
}
// Then fill in the fullName cache...
if fn := row.FullName; fn != nil {
u.fullNameCache.Add(uid, *fn)
key := fullNameDBKey(uid)
err := g.GetKVStore().PutObj(key, nil, *fn)
if err != nil {
g.GetLog().CInfof(ctx, "failed to put %v -> %v: %s", key, *fn, err)
}
// If we had previously busted this lookup, then clear the refresher
// on the server, so we don't have to do it next time through.
delete(u.serverRefreshers, uid)
}
if writeResults {
// Overwrite the row with whatever was returned from the server.
res[apiLookupIndex[i]] = row
}
}
}
}
return res, err
}
func (u *UIDMap) CheckUIDAgainstUsername(uid keybase1.UID, un libkb.NormalizedUsername) bool {
return checkUIDAgainstUsername(uid, un)
}
func (u *UIDMap) ClearUIDAtEldestSeqno(ctx context.Context, g libkb.UIDMapperContext, uid keybase1.UID, s keybase1.Seqno) error {
u.Lock()
defer u.Unlock()
voidp, ok := u.fullNameCache.Get(uid)
clearDB := false
if ok {
tmp, ok := voidp.(keybase1.FullNamePackage)
if !ok || tmp.EldestSeqno == s {
g.GetLog().CDebugf(ctx, "UIDMap: Clearing %s%%%d", uid, s)
u.fullNameCache.Remove(uid)
clearDB = true
}
} else {
clearDB = true
}
if clearDB {
key := fullNameDBKey(uid)
g.GetKVStore().Delete(key)
}
return nil
}
func MapUIDsReturnMap(ctx context.Context, u libkb.UIDMapper, g libkb.UIDMapperContext, uids []keybase1.UID, fullNameFreshness time.Duration, networkTimeBudget time.Duration, forceNetworkForFullNames bool) (res map[keybase1.UID]libkb.UsernamePackage, err error) {
var uidList []keybase1.UID
uidSet := map[keybase1.UID]bool{}
for _, uid := range uids {
_, found := uidSet[uid]
if !found {
uidSet[uid] = true
uidList = append(uidList, uid)
}
}
resultList, err := u.MapUIDsToUsernamePackages(ctx, g, uidList, fullNameFreshness, networkTimeBudget, forceNetworkForFullNames)
if err != nil && len(resultList) != len(uidList) {
return res, err
}
res = make(map[keybase1.UID]libkb.UsernamePackage)
for i, uid := range uidList {
res[uid] = resultList[i]
}
return res, err
}
var _ libkb.UIDMapper = (*UIDMap)(nil)
type OfflineUIDMap struct{}
func (o *OfflineUIDMap) CheckUIDAgainstUsername(uid keybase1.UID, un libkb.NormalizedUsername) bool {
return true
}
func (o *OfflineUIDMap) MapUIDsToUsernamePackages(ctx context.Context, g libkb.UIDMapperContext, uids []keybase1.UID, fullNameFreshness time.Duration, networktimeBudget time.Duration, forceNetworkForFullNames bool) ([]libkb.UsernamePackage, error) {
return nil, errors.New("offline uid map always fails")
}
func (o *OfflineUIDMap) SetTestingNoCachingMode(enabled bool) {
}
func (o *OfflineUIDMap) ClearUIDAtEldestSeqno(ctx context.Context, g libkb.UIDMapperContext, uid keybase1.UID, s keybase1.Seqno) error {
return nil
}
func (o *OfflineUIDMap) InformOfEldestSeqno(ctx context.Context, g libkb.UIDMapperContext, uv keybase1.UserVersion) (bool, error) {
return true, nil
}
var _ libkb.UIDMapper = (*OfflineUIDMap)(nil)