pcache.go raw

   1  /*
   2   * Copyright 2021 ByteDance Inc.
   3   *
   4   * Licensed under the Apache License, Version 2.0 (the "License");
   5   * you may not use this file except in compliance with the License.
   6   * You may obtain a copy of the License at
   7   *
   8   *     http://www.apache.org/licenses/LICENSE-2.0
   9   *
  10   * Unless required by applicable law or agreed to in writing, software
  11   * distributed under the License is distributed on an "AS IS" BASIS,
  12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13   * See the License for the specific language governing permissions and
  14   * limitations under the License.
  15   */
  16  
  17  package caching
  18  
  19  import (
  20      `sync`
  21      `sync/atomic`
  22      `unsafe`
  23  
  24      `github.com/bytedance/sonic/internal/rt`
  25  )
  26  
  27  /** Program Map **/
  28  
  29  const (
  30      _LoadFactor   = 0.5
  31      _InitCapacity = 4096    // must be a power of 2
  32  )
  33  
  34  type _ProgramMap struct {
  35      n uint64
  36      m uint32
  37      b []_ProgramEntry
  38  }
  39  
  40  type _ProgramEntry struct {
  41      vt *rt.GoType
  42      fn interface{}
  43  }
  44  
  45  func newProgramMap() *_ProgramMap {
  46      return &_ProgramMap {
  47          n: 0,
  48          m: _InitCapacity - 1,
  49          b: make([]_ProgramEntry, _InitCapacity),
  50      }
  51  }
  52  
  53  func (self *_ProgramMap) copy() *_ProgramMap {
  54      fork := &_ProgramMap{
  55          n: self.n,
  56          m: self.m,
  57          b: make([]_ProgramEntry, len(self.b)),
  58      }
  59      for i, f := range self.b {
  60          fork.b[i] = f
  61      }
  62      return fork
  63  }
  64  
  65  func (self *_ProgramMap) get(vt *rt.GoType) interface{} {
  66      i := self.m + 1
  67      p := vt.Hash & self.m
  68  
  69      /* linear probing */
  70      for ; i > 0; i-- {
  71          if b := self.b[p]; b.vt == vt {
  72              return b.fn
  73          } else if b.vt == nil {
  74              break
  75          } else {
  76              p = (p + 1) & self.m
  77          }
  78      }
  79  
  80      /* not found */
  81      return nil
  82  }
  83  
  84  func (self *_ProgramMap) add(vt *rt.GoType, fn interface{}) *_ProgramMap {
  85      p := self.copy()
  86      f := float64(atomic.LoadUint64(&p.n) + 1) / float64(p.m + 1)
  87  
  88      /* check for load factor */
  89      if f > _LoadFactor {
  90          p = p.rehash()
  91      }
  92  
  93      /* insert the value */
  94      p.insert(vt, fn)
  95      return p
  96  }
  97  
  98  func (self *_ProgramMap) rehash() *_ProgramMap {
  99      c := (self.m + 1) << 1
 100      r := &_ProgramMap{m: c - 1, b: make([]_ProgramEntry, int(c))}
 101  
 102      /* rehash every entry */
 103      for i := uint32(0); i <= self.m; i++ {
 104          if b := self.b[i]; b.vt != nil {
 105              r.insert(b.vt, b.fn)
 106          }
 107      }
 108  
 109      /* rebuild successful */
 110      return r
 111  }
 112  
 113  func (self *_ProgramMap) insert(vt *rt.GoType, fn interface{}) {
 114      h := vt.Hash
 115      p := h & self.m
 116  
 117      /* linear probing */
 118      for i := uint32(0); i <= self.m; i++ {
 119          if b := &self.b[p]; b.vt != nil {
 120              p += 1
 121              p &= self.m
 122          } else {
 123              b.vt = vt
 124              b.fn = fn
 125              atomic.AddUint64(&self.n, 1)
 126              return
 127          }
 128      }
 129  
 130      /* should never happens */
 131      panic("no available slots")
 132  }
 133  
 134  /** RCU Program Cache **/
 135  
 136  type ProgramCache struct {
 137      m sync.Mutex
 138      p unsafe.Pointer
 139  }
 140  
 141  func CreateProgramCache() *ProgramCache {
 142      return &ProgramCache {
 143          m: sync.Mutex{},
 144          p: unsafe.Pointer(newProgramMap()),
 145      }
 146  }
 147  
 148  func (self *ProgramCache) Get(vt *rt.GoType) interface{} {
 149      return (*_ProgramMap)(atomic.LoadPointer(&self.p)).get(vt)
 150  }
 151  
 152  func (self *ProgramCache) Compute(vt *rt.GoType, compute func(*rt.GoType, ... interface{}) (interface{}, error), ex ...interface{}) (interface{}, error) {
 153      var err error
 154      var val interface{}
 155  
 156      /* use defer to prevent inlining of this function */
 157      self.m.Lock()
 158      defer self.m.Unlock()
 159  
 160      /* double check with write lock held */
 161      if val = self.Get(vt); val != nil {
 162          return val, nil
 163      }
 164  
 165      /* compute the value */
 166      if val, err = compute(vt, ex...); err != nil {
 167          return nil, err
 168      }
 169  
 170      /* update the RCU cache */
 171      atomic.StorePointer(&self.p, unsafe.Pointer((*_ProgramMap)(atomic.LoadPointer(&self.p)).add(vt, val)))
 172      return val, nil
 173  }
 174