| 1 | package assetcache |
| 2 | |
| 3 | // makeRoom evicts entries until a reservation of need bytes fits the budget |
| 4 | // beside what the store holds and has promised (used + reserved + need <= |
| 5 | // Budget), or until nothing is left to evict. Each round takes the least |
| 6 | // recently used entry of the app furthest over its share. Bytes that open |
| 7 | // Readers hold stay counted (drop keeps them), so room can stay short; the |
| 8 | // caller's budget check decides. Reserve calls it only for a reservation |
| 9 | // that fits once room is made, and Open with need 0 to bring a store found |
| 10 | // over its budget back under. It is called without s.mu held and takes s.mu |
| 11 | // only to choose a victim, never across the deletion. |
| 12 | func (s *Store) makeRoom(need int64) { |
| 13 | var failed map[*entry]bool // victims drop could not delete; not chosen again |
| 14 | for { |
| 15 | s.mu.Lock() |
| 16 | if s.used <= s.cfg.Budget-s.reserved-need { |
| 17 | s.mu.Unlock() |
| 18 | return |
| 19 | } |
| 20 | victim := s.victimLocked(failed) |
| 21 | s.mu.Unlock() |
| 22 | if victim == nil { |
| 23 | return |
| 24 | } |
| 25 | if !s.drop(victim) { |
| 26 | if failed == nil { |
| 27 | failed = make(map[*entry]bool) |
| 28 | } |
| 29 | failed[victim] = true |
| 30 | } |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | // victimLocked returns the least recently used entry, outside skip, of the |
| 35 | // app with the largest bytes - share, or nil when no entry qualifies. Equal |
| 36 | // excess goes to the app whose candidate was used longest ago. The caller |
| 37 | // holds s.mu. |
| 38 | func (s *Store) victimLocked(skip map[*entry]bool) *entry { |
| 39 | share := s.shareOf(len(s.apps)) |
| 40 | var victim *entry |
| 41 | var victimOver int64 |
| 42 | for _, app := range s.apps { |
| 43 | var cand *entry |
| 44 | for el := app.lru.Back(); el != nil; el = el.Prev() { |
| 45 | if e := el.Value.(*entry); !skip[e] { |
| 46 | cand = e |
| 47 | break |
| 48 | } |
| 49 | } |
| 50 | if cand == nil { |
| 51 | continue |
| 52 | } |
| 53 | over := app.bytes - share |
| 54 | if victim == nil || over > victimOver || (over == victimOver && cand.used < victim.used) { |
| 55 | victim, victimOver = cand, over |
| 56 | } |
| 57 | } |
| 58 | return victim |
| 59 | } |
| 60 | |
| 61 | // shareOf is the bytes each of apps apps may hold before eviction takes |
| 62 | // from them: the budget divided among them, never more than a quarter of it |
| 63 | // for one app. |
| 64 | func (s *Store) shareOf(apps int) int64 { |
| 65 | if apps < 1 { |
| 66 | apps = 1 |
| 67 | } |
| 68 | share := s.cfg.Budget / int64(apps) |
| 69 | if limit := s.cfg.Budget / 4; share > limit { |
| 70 | share = limit |
| 71 | } |
| 72 | return share |
| 73 | } |
| 74 | |
| 75 | // Retain deletes every entry whose key keep rejects and returns how many it |
| 76 | // deleted. keep is called without any store lock held, once per entry that |
| 77 | // was indexed when Retain began; an entry committed meanwhile is not judged. |
| 78 | // An entry a Reader holds is deleted like any other: its files go at once |
| 79 | // and its bytes stay counted until the Reader closes. Retain first retries |
| 80 | // the unlinks that failed earlier, so a sweep frees their disk even when |
| 81 | // there is no entry left for it to judge. |
| 82 | func (s *Store) Retain(keep func(Key) bool) int { |
| 83 | s.retryStuck() |
| 84 | s.mu.Lock() |
| 85 | all := make([]*entry, 0, len(s.entries)) |
| 86 | for _, e := range s.entries { |
| 87 | all = append(all, e) |
| 88 | } |
| 89 | s.mu.Unlock() |
| 90 | n := 0 |
| 91 | for _, e := range all { |
| 92 | if !keep(e.meta.Key) && s.drop(e) { |
| 93 | n++ |
| 94 | } |
| 95 | } |
| 96 | return n |
| 97 | } |
| 98 | |
amadan