Line data Source code
1 : // Copyright 2020 The LevelDB-Go and Pebble Authors. All rights reserved. Use 2 : // of this source code is governed by a BSD-style license that can be found in 3 : // the LICENSE file. 4 : 5 : package cache 6 : 7 : import "sync/atomic" 8 : 9 : type entryType int8 10 : 11 : const ( 12 : etTest entryType = iota 13 : etCold 14 : etHot 15 : ) 16 : 17 0 : func (p entryType) String() string { 18 0 : switch p { 19 0 : case etTest: 20 0 : return "test" 21 0 : case etCold: 22 0 : return "cold" 23 0 : case etHot: 24 0 : return "hot" 25 : } 26 0 : return "unknown" 27 : } 28 : 29 : // entry holds the metadata for a cache entry. The memory for an entry is 30 : // allocated from manually managed memory. 31 : // 32 : // Using manual memory management for entries is technically a volation of the 33 : // Cgo pointer rules: 34 : // 35 : // https://golang.org/cmd/cgo/#hdr-Passing_pointers 36 : // 37 : // Specifically, Go pointers should not be stored in C allocated memory. The 38 : // reason for this rule is that the Go GC will not look at C allocated memory 39 : // to find pointers to Go objects. If the only reference to a Go object is 40 : // stored in C allocated memory, the object will be reclaimed. The shard field 41 : // of the entry struct points to a Go allocated object, thus the 42 : // violation. What makes this "safe" is that the Cache guarantees that there 43 : // are other pointers to the shard which will keep it alive. 44 : type entry struct { 45 : key key 46 : // The value associated with the entry. The entry holds a reference on the 47 : // value which is maintained by entry.setValue(). 48 : val *Value 49 : blockLink struct { 50 : next *entry 51 : prev *entry 52 : } 53 : fileLink struct { 54 : next *entry 55 : prev *entry 56 : } 57 : size int64 58 : ptype entryType 59 : // referenced is atomically set to indicate that this entry has been accessed 60 : // since the last time one of the clock hands swept it. 61 : referenced atomic.Bool 62 : shard *shard 63 : // Reference count for the entry. The entry is freed when the reference count 64 : // drops to zero. 65 : ref refcnt 66 : } 67 : 68 2 : func newEntry(s *shard, key key, size int64) *entry { 69 2 : e := entryAllocNew() 70 2 : *e = entry{ 71 2 : key: key, 72 2 : size: size, 73 2 : ptype: etCold, 74 2 : shard: s, 75 2 : } 76 2 : e.blockLink.next = e 77 2 : e.blockLink.prev = e 78 2 : e.fileLink.next = e 79 2 : e.fileLink.prev = e 80 2 : e.ref.init(1) 81 2 : return e 82 2 : } 83 : 84 2 : func (e *entry) free() { 85 2 : e.setValue(nil) 86 2 : *e = entry{} 87 2 : entryAllocFree(e) 88 2 : } 89 : 90 2 : func (e *entry) next() *entry { 91 2 : if e == nil { 92 2 : return nil 93 2 : } 94 2 : return e.blockLink.next 95 : } 96 : 97 2 : func (e *entry) prev() *entry { 98 2 : if e == nil { 99 0 : return nil 100 0 : } 101 2 : return e.blockLink.prev 102 : } 103 : 104 2 : func (e *entry) link(s *entry) { 105 2 : s.blockLink.prev = e.blockLink.prev 106 2 : s.blockLink.prev.blockLink.next = s 107 2 : s.blockLink.next = e 108 2 : s.blockLink.next.blockLink.prev = s 109 2 : } 110 : 111 2 : func (e *entry) unlink() *entry { 112 2 : next := e.blockLink.next 113 2 : e.blockLink.prev.blockLink.next = e.blockLink.next 114 2 : e.blockLink.next.blockLink.prev = e.blockLink.prev 115 2 : e.blockLink.prev = e 116 2 : e.blockLink.next = e 117 2 : return next 118 2 : } 119 : 120 2 : func (e *entry) linkFile(s *entry) { 121 2 : s.fileLink.prev = e.fileLink.prev 122 2 : s.fileLink.prev.fileLink.next = s 123 2 : s.fileLink.next = e 124 2 : s.fileLink.next.fileLink.prev = s 125 2 : } 126 : 127 2 : func (e *entry) unlinkFile() *entry { 128 2 : next := e.fileLink.next 129 2 : e.fileLink.prev.fileLink.next = e.fileLink.next 130 2 : e.fileLink.next.fileLink.prev = e.fileLink.prev 131 2 : e.fileLink.prev = e 132 2 : e.fileLink.next = e 133 2 : return next 134 2 : } 135 : 136 2 : func (e *entry) setValue(v *Value) { 137 2 : if v != nil { 138 2 : v.acquire() 139 2 : } 140 2 : old := e.val 141 2 : e.val = v 142 2 : old.release() 143 : } 144 : 145 2 : func (e *entry) peekValue() *Value { 146 2 : return e.val 147 2 : } 148 : 149 2 : func (e *entry) acquireValue() *Value { 150 2 : v := e.val 151 2 : if v != nil { 152 2 : v.acquire() 153 2 : } 154 2 : return v 155 : }