| 1 | package assetcache |
| 2 | |
| 3 | import ( |
| 4 | "errors" |
| 5 | "fmt" |
| 6 | "os" |
| 7 | "path/filepath" |
| 8 | "strings" |
| 9 | "sync" |
| 10 | "testing" |
| 11 | "time" |
| 12 | ) |
| 13 | |
| 14 | // The eviction tests use a budget of 1000000 bytes and 20000-byte bodies. A |
| 15 | // committed entry holds its body plus a .meta of a few hundred bytes, and a |
| 16 | // fill of such a body reserves 2*20000 + metaReserve, so a store can be |
| 17 | // filled to a little over 90% before the next fill has to evict. A test |
| 18 | // that wants the next fill to evict reserves for bigBody instead. |
| 19 | |
| 20 | const evictBudget = 1000000 |
| 21 | |
| 22 | var ( |
| 23 | evictBody = []byte(strings.Repeat("x", 20000)) |
| 24 | bigBody = []byte(strings.Repeat("y", 100000)) |
| 25 | ) |
| 26 | |
| 27 | // evictStore opens a store with the eviction budget over a fake FS with |
| 28 | // plenty of room. Tests using it are not acceptance. |
| 29 | func evictStore(t *testing.T) (*Store, string) { |
| 30 | t.Helper() |
| 31 | s, _, dir := entryStore(t, evictBudget) |
| 32 | return s, dir |
| 33 | } |
| 34 | |
| 35 | // commitN commits n entries /<prefix>0 .. /<prefix>n-1 for app, oldest first. |
| 36 | func commitN(t *testing.T, s *Store, app, prefix string, n int) { |
| 37 | t.Helper() |
| 38 | for i := 0; i < n; i++ { |
| 39 | commit(t, s, testKey(app, fmt.Sprintf("/%s%d", prefix, i)), evictBody, cssHeader("1"), false) |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | // present reports whether the entry is indexed, without marking it used. |
| 44 | func present(s *Store, app, path string) bool { |
| 45 | s.mu.Lock() |
| 46 | defer s.mu.Unlock() |
| 47 | e := s.entries[testKey(app, path).ID()] |
| 48 | return e != nil |
| 49 | } |
| 50 | |
| 51 | func mustBePresent(t *testing.T, s *Store, app, path string) { |
| 52 | t.Helper() |
| 53 | if !present(s, app, path) { |
| 54 | t.Fatalf("%s %s was evicted, want kept", app, path) |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | func mustBeGone(t *testing.T, s *Store, app, path string) { |
| 59 | t.Helper() |
| 60 | if present(s, app, path) { |
| 61 | t.Fatalf("%s %s survived, want evicted", app, path) |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | func mustFitBudget(t *testing.T, s *Store) { |
| 66 | t.Helper() |
| 67 | if st := s.Stats(); st.Bytes+st.Reserved > evictBudget { |
| 68 | t.Fatalf("Stats = %+v, over the budget %d", st, evictBudget) |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | // TestEvictionTakesFromTheAppFurthestOverItsShare is not acceptance: it uses |
| 73 | // a fake FS. |
| 74 | func TestEvictionTakesFromTheAppFurthestOverItsShare(t *testing.T) { |
| 75 | s, _ := evictStore(t) |
| 76 | commitN(t, s, "shop", "s", 36) // about 73% of the budget |
| 77 | commitN(t, s, "blog", "b", 5) // about 10% |
| 78 | // Use shop's oldest: it is no longer the least recently used. |
| 79 | mustGet(t, s, testKey("shop", "/s0")) |
| 80 | |
| 81 | f, err := s.Reserve(testKey("blog", "/b5"), int64(len(bigBody))) |
| 82 | if err != nil { |
| 83 | t.Fatalf("Reserve: %v", err) |
| 84 | } |
| 85 | defer f.Abort() |
| 86 | |
| 87 | mustBePresent(t, s, "shop", "/s0") // used since: spared |
| 88 | mustBeGone(t, s, "shop", "/s1") |
| 89 | mustBeGone(t, s, "shop", "/s2") |
| 90 | mustBePresent(t, s, "shop", "/s35") |
| 91 | for i := 0; i < 5; i++ { |
| 92 | mustBePresent(t, s, "blog", fmt.Sprintf("/b%d", i)) |
| 93 | } |
| 94 | mustFitBudget(t, s) |
| 95 | } |
| 96 | |
| 97 | // TestOneAppWalkingUniqueQueriesEvictsItself is not acceptance: it uses a |
| 98 | // fake FS. |
| 99 | func TestOneAppWalkingUniqueQueriesEvictsItself(t *testing.T) { |
| 100 | s, _ := evictStore(t) |
| 101 | commitN(t, s, "blog", "b", 1) |
| 102 | for i := 0; i < 70; i++ { |
| 103 | commit(t, s, testKey("shop", fmt.Sprintf("/q%d", i)), evictBody, cssHeader("1"), false) |
| 104 | mustFitBudget(t, s) |
| 105 | } |
| 106 | mustBePresent(t, s, "blog", "/b0") |
| 107 | mustBeGone(t, s, "shop", "/q0") |
| 108 | mustBePresent(t, s, "shop", "/q69") |
| 109 | if st := s.Stats(); st.Entries < 20 { |
| 110 | t.Fatalf("Stats = %+v, want shop to keep filling its own room", st) |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | // TestNewAppEvictsTheAppOverItsShare is not acceptance: it uses a fake FS. |
| 115 | // The second app has no entries yet. Its fill is admitted by evicting the |
| 116 | // first app's oldest entries, not refused. |
| 117 | func TestNewAppEvictsTheAppOverItsShare(t *testing.T) { |
| 118 | s, _ := evictStore(t) |
| 119 | commitN(t, s, "shop", "s", 40) // about 80% of the budget |
| 120 | mustFitBudget(t, s) |
| 121 | |
| 122 | commit(t, s, testKey("blog", "/b0"), bigBody, cssHeader("1"), false) |
| 123 | |
| 124 | mustBePresent(t, s, "blog", "/b0") |
| 125 | mustBeGone(t, s, "shop", "/s0") |
| 126 | mustBeGone(t, s, "shop", "/s1") |
| 127 | mustBePresent(t, s, "shop", "/s39") |
| 128 | mustFitBudget(t, s) |
| 129 | } |
| 130 | |
| 131 | // TestShareNeverExceedsAQuarter is not acceptance: it uses a fake FS. One app |
| 132 | // alone has the whole budget to itself by division, but its share stops at a |
| 133 | // quarter. |
| 134 | func TestShareNeverExceedsAQuarter(t *testing.T) { |
| 135 | s, _ := evictStore(t) |
| 136 | for apps, want := range map[int]int64{1: evictBudget / 4, 2: evictBudget / 4, 4: evictBudget / 4, 8: evictBudget / 8, 100: evictBudget / 100} { |
| 137 | if got := s.shareOf(apps); got != want { |
| 138 | t.Errorf("shareOf(%d) = %d, want %d", apps, got, want) |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | // One app alone passes 25% and is evicted (itself) when room is needed. |
| 143 | commitN(t, s, "shop", "s", 40) |
| 144 | commit(t, s, testKey("shop", "/new"), bigBody, cssHeader("1"), false) |
| 145 | mustBeGone(t, s, "shop", "/s0") |
| 146 | mustBePresent(t, s, "shop", "/new") |
| 147 | mustFitBudget(t, s) |
| 148 | } |
| 149 | |
| 150 | // TestEvictionKeepsLeasedBytesCounted is not acceptance: it uses a fake FS. |
| 151 | // Eviction goes through drop, so a body a Reader holds stays counted and |
| 152 | // makeRoom stops when nothing is left to evict. |
| 153 | func TestEvictionKeepsLeasedBytesCounted(t *testing.T) { |
| 154 | s, _ := evictStore(t) |
| 155 | commitN(t, s, "shop", "s", 3) |
| 156 | var readers []*Reader |
| 157 | for i := 0; i < 3; i++ { |
| 158 | r, err := mustGet(t, s, testKey("shop", fmt.Sprintf("/s%d", i))).Open(false) |
| 159 | if err != nil { |
| 160 | t.Fatal(err) |
| 161 | } |
| 162 | readers = append(readers, r) |
| 163 | } |
| 164 | s.makeRoom(10 * evictBudget) // cannot fit; evicts everything it can |
| 165 | st := s.Stats() |
| 166 | if st.Entries != 0 || st.Retired != 3*int64(len(evictBody)) || st.Bytes != st.Retired { |
| 167 | t.Fatalf("Stats = %+v, want no entries and the three leased bodies counted", st) |
| 168 | } |
| 169 | for _, r := range readers { |
| 170 | r.Close() |
| 171 | } |
| 172 | if st := s.Stats(); st.Bytes != 0 || st.Retired != 0 { |
| 173 | t.Fatalf("Stats after Close = %+v, want 0", st) |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | // TestRetainDeletesRejectedKeys is not acceptance: it uses a fake FS. |
| 178 | func TestRetainDeletesRejectedKeys(t *testing.T) { |
| 179 | s, dir := evictStore(t) |
| 180 | commitN(t, s, "shop", "s", 3) |
| 181 | commitN(t, s, "blog", "b", 2) |
| 182 | |
| 183 | n := s.Retain(func(k Key) bool { return k.App == "blog" || k.Path == "/s1" }) |
| 184 | if n != 2 { |
| 185 | t.Fatalf("Retain = %d, want 2", n) |
| 186 | } |
| 187 | mustBeGone(t, s, "shop", "/s0") |
| 188 | mustBePresent(t, s, "shop", "/s1") |
| 189 | mustBeGone(t, s, "shop", "/s2") |
| 190 | mustBePresent(t, s, "blog", "/b0") |
| 191 | mustBePresent(t, s, "blog", "/b1") |
| 192 | if st := s.Stats(); st.Entries != 3 || st.Retired != 0 { |
| 193 | t.Fatalf("Stats = %+v, want 3 entries", st) |
| 194 | } |
| 195 | // Nothing of the deleted entries is left on disk: three entries' files. |
| 196 | if got := listDir(t, dir); len(got) != 6 { |
| 197 | t.Fatalf("files = %v, want .meta and .body for 3 entries", got) |
| 198 | } |
| 199 | if n := s.Retain(func(Key) bool { return true }); n != 0 { |
| 200 | t.Fatalf("second Retain = %d, want 0", n) |
| 201 | } |
| 202 | if n := s.Retain(func(Key) bool { return false }); n != 3 { |
| 203 | t.Fatalf("reject-all Retain = %d, want 3", n) |
| 204 | } |
| 205 | if st := s.Stats(); st.Entries != 0 || st.Bytes != 0 || st.Apps != 0 { |
| 206 | t.Fatalf("Stats = %+v, want empty", st) |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | // TestEvictionRacesFillsGetsAndRetain is not acceptance: it uses a fake FS. |
| 211 | // Fills in two apps, Gets and Retain run together under -race; afterwards |
| 212 | // the per-app lists and byte counts agree with the index. |
| 213 | func TestEvictionRacesFillsGetsAndRetain(t *testing.T) { |
| 214 | s, _ := evictStore(t) |
| 215 | body := evictBody |
| 216 | // Retain rejects every worker's fourth entry. It starts at the first |
| 217 | // commit and runs until the last fill is done, and each worker waits |
| 218 | // after committing its fourth entry until that entry is gone, so Retain |
| 219 | // deletes while the other workers' fills are in flight. |
| 220 | rejected := func(k Key) bool { return strings.HasSuffix(k.Path, "-3") } |
| 221 | firstCommit, fillsDone := make(chan struct{}), make(chan struct{}) |
| 222 | var once sync.Once |
| 223 | var fills, wg sync.WaitGroup |
| 224 | for _, app := range []string{"shop", "blog"} { |
| 225 | for w := 0; w < 3; w++ { |
| 226 | fills.Add(1) |
| 227 | go func() { |
| 228 | defer fills.Done() |
| 229 | for i := 0; i < 15; i++ { |
| 230 | k := testKey(app, fmt.Sprintf("/w%d-%d", w, i)) |
| 231 | f, err := s.Reserve(k, int64(len(body))) |
| 232 | if err != nil { |
| 233 | if !errors.Is(err, ErrNoRoom) && !errors.Is(err, ErrBusy) { |
| 234 | t.Errorf("Reserve: %v", err) |
| 235 | } |
| 236 | continue |
| 237 | } |
| 238 | if _, err := f.Write(body); err != nil { |
| 239 | t.Errorf("Write: %v", err) |
| 240 | } |
| 241 | if err := f.Commit(Meta{Header: cssHeader("1"), Lifetime: time.Hour, Expires: testNow.Add(time.Hour)}, false); err != nil { |
| 242 | t.Errorf("Commit: %v", err) |
| 243 | } |
| 244 | once.Do(func() { close(firstCommit) }) |
| 245 | if rejected(k) { |
| 246 | for deadline := time.Now().Add(10 * time.Second); present(s, app, k.Path); time.Sleep(time.Millisecond) { |
| 247 | if time.Now().After(deadline) { |
| 248 | t.Errorf("%s %s still indexed while Retain runs", app, k.Path) |
| 249 | break |
| 250 | } |
| 251 | } |
| 252 | } |
| 253 | s.Get(testKey(app, fmt.Sprintf("/w%d-%d", w, i/2))) |
| 254 | } |
| 255 | }() |
| 256 | } |
| 257 | } |
| 258 | go func() { |
| 259 | fills.Wait() |
| 260 | close(fillsDone) |
| 261 | }() |
| 262 | deleted := 0 |
| 263 | wg.Add(1) |
| 264 | go func() { |
| 265 | defer wg.Done() |
| 266 | select { |
| 267 | case <-firstCommit: |
| 268 | case <-fillsDone: |
| 269 | return |
| 270 | } |
| 271 | for { |
| 272 | select { |
| 273 | case <-fillsDone: |
| 274 | return |
| 275 | default: |
| 276 | deleted += s.Retain(func(k Key) bool { return !rejected(k) }) |
| 277 | } |
| 278 | } |
| 279 | }() |
| 280 | wg.Wait() |
| 281 | if deleted == 0 { |
| 282 | t.Fatal("Retain deleted nothing while the fills ran") |
| 283 | } |
| 284 | |
| 285 | s.mu.Lock() |
| 286 | defer s.mu.Unlock() |
| 287 | if s.reserved != 0 || s.used > evictBudget { |
| 288 | t.Fatalf("reserved %d used %d, want 0 and within %d", s.reserved, s.used, evictBudget) |
| 289 | } |
| 290 | listed := 0 |
| 291 | for scope, app := range s.apps { |
| 292 | var sum int64 |
| 293 | for el := app.lru.Front(); el != nil; el = el.Next() { |
| 294 | e := el.Value.(*entry) |
| 295 | if s.entries[e.id] != e || e.elem != el || e.meta.Key.AppScope() != scope { |
| 296 | t.Fatalf("list of %s holds an entry the index does not", scope) |
| 297 | } |
| 298 | sum += e.bytes() |
| 299 | listed++ |
| 300 | } |
| 301 | if sum != app.bytes { |
| 302 | t.Fatalf("%s bytes = %d, its entries hold %d", scope, app.bytes, sum) |
| 303 | } |
| 304 | } |
| 305 | if listed != len(s.entries) { |
| 306 | t.Fatalf("lists hold %d entries, index %d", listed, len(s.entries)) |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | // mustKeepEverything fails unless every entry and byte in before is still |
| 311 | // there: a refused reservation evicted nothing. |
| 312 | func mustKeepEverything(t *testing.T, s *Store, before Stats) { |
| 313 | t.Helper() |
| 314 | if after := s.Stats(); after != before { |
| 315 | t.Fatalf("Stats after the refusal = %+v, want %+v: nothing evicted", after, before) |
| 316 | } |
| 317 | } |
| 318 | |
| 319 | // TestReserveLargerThanTheBudgetEvictsNothing is not acceptance: it uses a |
| 320 | // fake FS. With a valid 32 MiB budget a fill of unknown length reserves |
| 321 | // about 64 MiB, which no eviction can make room for: it is refused before |
| 322 | // anything is evicted for it. |
| 323 | func TestReserveLargerThanTheBudgetEvictsNothing(t *testing.T) { |
| 324 | s, _, _ := entryStore(t, 32<<20) |
| 325 | commitN(t, s, "shop", "s", 3) |
| 326 | commitN(t, s, "blog", "b", 2) |
| 327 | before := s.Stats() |
| 328 | if _, err := s.Reserve(testKey("shop", "/big"), -1); !errors.Is(err, ErrNoRoom) { |
| 329 | t.Fatalf("err = %v, want ErrNoRoom", err) |
| 330 | } |
| 331 | mustKeepEverything(t, s, before) |
| 332 | } |
| 333 | |
| 334 | // TestReserveCrowdedOutByOtherFillsEvictsNothing is not acceptance: it uses |
| 335 | // a fake FS. The reservation fits the budget alone, but not beside another |
| 336 | // fill's outstanding reservation, which eviction cannot free. |
| 337 | func TestReserveCrowdedOutByOtherFillsEvictsNothing(t *testing.T) { |
| 338 | s, _ := evictStore(t) |
| 339 | commitN(t, s, "shop", "s", 5) |
| 340 | a, err := s.Reserve(testKey("blog", "/a"), 300000) |
| 341 | if err != nil { |
| 342 | t.Fatal(err) |
| 343 | } |
| 344 | before := s.Stats() |
| 345 | if _, err := s.Reserve(testKey("shop", "/b"), 200000); !errors.Is(err, ErrNoRoom) { |
| 346 | t.Fatalf("err = %v, want ErrNoRoom", err) |
| 347 | } |
| 348 | mustKeepEverything(t, s, before) |
| 349 | a.Abort() |
| 350 | b, err := s.Reserve(testKey("shop", "/b"), 200000) |
| 351 | if err != nil { |
| 352 | t.Fatalf("after the other fill aborted: %v", err) |
| 353 | } |
| 354 | b.Abort() |
| 355 | } |
| 356 | |
| 357 | // TestReserveBelowTheFloorEvictsNothing is not acceptance: it uses a fake |
| 358 | // FS. The store is full enough that the fill would have to evict, but the |
| 359 | // disk is at its floor, so it is refused before anything is evicted. |
| 360 | func TestReserveBelowTheFloorEvictsNothing(t *testing.T) { |
| 361 | s, _ := evictStore(t) |
| 362 | fs := s.cfg.FS.(*fakeFS) |
| 363 | commitN(t, s, "shop", "s", 40) // about 80% of the budget |
| 364 | fs.mu.Lock() |
| 365 | fs.total = 8 << 30 |
| 366 | fs.mu.Unlock() |
| 367 | fs.setFree(8 << 30 * floorPercent / 100) |
| 368 | before := s.Stats() |
| 369 | if _, err := s.Reserve(testKey("blog", "/b"), int64(len(bigBody))); !errors.Is(err, ErrBelowFloor) { |
| 370 | t.Fatalf("err = %v, want ErrBelowFloor", err) |
| 371 | } |
| 372 | mustKeepEverything(t, s, before) |
| 373 | // With room on the disk the same fill evicts and is admitted. |
| 374 | fs.setFree(4 << 30) |
| 375 | f, err := s.Reserve(testKey("blog", "/b"), int64(len(bigBody))) |
| 376 | if err != nil { |
| 377 | t.Fatalf("with room on the disk: %v", err) |
| 378 | } |
| 379 | defer f.Abort() |
| 380 | mustBeGone(t, s, "shop", "/s0") |
| 381 | mustFitBudget(t, s) |
| 382 | } |
| 383 | |
| 384 | // stuckBody commits one 100000-byte entry into a 300000-byte store, makes its |
| 385 | // body impossible to unlink (the name becomes a directory holding a file, so |
| 386 | // remove fails) and deletes the entry: its .meta goes, its body is stuck and |
| 387 | // its bytes stay counted. It returns the file whose removal clears the fault. |
| 388 | func stuckBody(t *testing.T) (*Store, string) { |
| 389 | t.Helper() |
| 390 | s, _, dir := entryStore(t, 300000) |
| 391 | k := testKey("shop", "/a.css") |
| 392 | commit(t, s, k, bigBody, cssHeader("1"), false) |
| 393 | body := filepath.Join(dir, bodyName(k.ID(), mustGet(t, s, k).Meta.Version)) |
| 394 | if err := os.Remove(body); err != nil { |
| 395 | t.Fatal(err) |
| 396 | } |
| 397 | if err := os.Mkdir(body, 0o700); err != nil { |
| 398 | t.Fatal(err) |
| 399 | } |
| 400 | pin := filepath.Join(body, "pin") |
| 401 | writeFile(t, pin, []byte("x")) |
| 402 | if n := s.Retain(func(Key) bool { return false }); n != 1 { |
| 403 | t.Fatalf("Retain = %d, want the entry deleted", n) |
| 404 | } |
| 405 | if st := s.Stats(); st.Entries != 0 || st.Retired != int64(len(bigBody)) || st.Bytes != st.Retired { |
| 406 | t.Fatalf("Stats = %+v, want only the stuck body counted", st) |
| 407 | } |
| 408 | return s, pin |
| 409 | } |
| 410 | |
| 411 | // TestReserveRetriesAFailedUnlinkBeforeRefusing is not acceptance: it uses a |
| 412 | // fake FS. A body whose unlink failed holds bytes no eviction can free. While |
| 413 | // the fault lasts the fill is refused; once it clears, the same reservation |
| 414 | // succeeds with no other commit or deletion in between, because Reserve |
| 415 | // retries the unlink before it concludes there is no room. |
| 416 | func TestReserveRetriesAFailedUnlinkBeforeRefusing(t *testing.T) { |
| 417 | s, pin := stuckBody(t) |
| 418 | before := s.Stats() |
| 419 | // 2*90000 + metaReserve fits the budget, but not beside the stuck body. |
| 420 | probe := testKey("blog", "/b.css") |
| 421 | if _, err := s.Reserve(probe, 90000); !errors.Is(err, ErrNoRoom) { |
| 422 | t.Fatalf("while the unlink fails: err = %v, want ErrNoRoom", err) |
| 423 | } |
| 424 | mustKeepEverything(t, s, before) |
| 425 | if err := os.Remove(pin); err != nil { |
| 426 | t.Fatal(err) |
| 427 | } |
| 428 | f, err := s.Reserve(probe, 90000) |
| 429 | if err != nil { |
| 430 | t.Fatalf("once the fault cleared: %v", err) |
| 431 | } |
| 432 | defer f.Abort() |
| 433 | if st := s.Stats(); st.Retired != 0 || st.Bytes != 0 { |
| 434 | t.Fatalf("Stats = %+v, want the stuck body gone", st) |
| 435 | } |
| 436 | } |
| 437 | |
| 438 | // TestRetainRetriesAFailedUnlinkOnAnEmptyIndex is not acceptance: it uses a |
| 439 | // fake FS. The sweep retries stuck unlinks even when there is no entry left |
| 440 | // for it to judge. |
| 441 | func TestRetainRetriesAFailedUnlinkOnAnEmptyIndex(t *testing.T) { |
| 442 | s, pin := stuckBody(t) |
| 443 | if err := os.Remove(pin); err != nil { |
| 444 | t.Fatal(err) |
| 445 | } |
| 446 | if n := s.Retain(func(Key) bool { return true }); n != 0 { |
| 447 | t.Fatalf("Retain = %d, want 0", n) |
| 448 | } |
| 449 | if st := s.Stats(); st.Retired != 0 || st.Bytes != 0 { |
| 450 | t.Fatalf("Stats = %+v, want the stuck body gone", st) |
| 451 | } |
| 452 | } |
| 453 | |
amadan