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           1 : func newEntry(s *shard, key key, size int64) *entry {
      69           1 :         e := entryAllocNew()
      70           1 :         *e = entry{
      71           1 :                 key:   key,
      72           1 :                 size:  size,
      73           1 :                 ptype: etCold,
      74           1 :                 shard: s,
      75           1 :         }
      76           1 :         e.blockLink.next = e
      77           1 :         e.blockLink.prev = e
      78           1 :         e.fileLink.next = e
      79           1 :         e.fileLink.prev = e
      80           1 :         e.ref.init(1)
      81           1 :         return e
      82           1 : }
      83             : 
      84           1 : func (e *entry) free() {
      85           1 :         e.setValue(nil)
      86           1 :         *e = entry{}
      87           1 :         entryAllocFree(e)
      88           1 : }
      89             : 
      90           1 : func (e *entry) next() *entry {
      91           1 :         if e == nil {
      92           1 :                 return nil
      93           1 :         }
      94           1 :         return e.blockLink.next
      95             : }
      96             : 
      97           1 : func (e *entry) prev() *entry {
      98           1 :         if e == nil {
      99           0 :                 return nil
     100           0 :         }
     101           1 :         return e.blockLink.prev
     102             : }
     103             : 
     104           1 : func (e *entry) link(s *entry) {
     105           1 :         s.blockLink.prev = e.blockLink.prev
     106           1 :         s.blockLink.prev.blockLink.next = s
     107           1 :         s.blockLink.next = e
     108           1 :         s.blockLink.next.blockLink.prev = s
     109           1 : }
     110             : 
     111           1 : func (e *entry) unlink() *entry {
     112           1 :         next := e.blockLink.next
     113           1 :         e.blockLink.prev.blockLink.next = e.blockLink.next
     114           1 :         e.blockLink.next.blockLink.prev = e.blockLink.prev
     115           1 :         e.blockLink.prev = e
     116           1 :         e.blockLink.next = e
     117           1 :         return next
     118           1 : }
     119             : 
     120           1 : func (e *entry) linkFile(s *entry) {
     121           1 :         s.fileLink.prev = e.fileLink.prev
     122           1 :         s.fileLink.prev.fileLink.next = s
     123           1 :         s.fileLink.next = e
     124           1 :         s.fileLink.next.fileLink.prev = s
     125           1 : }
     126             : 
     127           1 : func (e *entry) unlinkFile() *entry {
     128           1 :         next := e.fileLink.next
     129           1 :         e.fileLink.prev.fileLink.next = e.fileLink.next
     130           1 :         e.fileLink.next.fileLink.prev = e.fileLink.prev
     131           1 :         e.fileLink.prev = e
     132           1 :         e.fileLink.next = e
     133           1 :         return next
     134           1 : }
     135             : 
     136           1 : func (e *entry) setValue(v *Value) {
     137           1 :         if v != nil {
     138           1 :                 v.acquire()
     139           1 :         }
     140           1 :         old := e.val
     141           1 :         e.val = v
     142           1 :         old.release()
     143             : }
     144             : 
     145           1 : func (e *entry) peekValue() *Value {
     146           1 :         return e.val
     147           1 : }
     148             : 
     149           1 : func (e *entry) acquireValue() *Value {
     150           1 :         v := e.val
     151           1 :         if v != nil {
     152           1 :                 v.acquire()
     153           1 :         }
     154           1 :         return v
     155             : }