cacheddiskstoragemanager.go 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343
  1. /*
  2. * EliasDB
  3. *
  4. * Copyright 2016 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the Mozilla Public
  7. * License, v. 2.0. If a copy of the MPL was not distributed with this
  8. * file, You can obtain one at http://mozilla.org/MPL/2.0/.
  9. */
  10. /*
  11. Package storage contains the low-level API for data storage. Data is stored
  12. in slots. The interface defines methods to store, retrieve, update and delete
  13. a given object to and from the disk. There are 3 main implementations:
  14. DiskStorageManager
  15. A disk storage manager handles the data storage on disk. It controls the actual
  16. PhysicalSlotManager and LogicalSlotManager objects. It holds references to all
  17. involved files and ensures exclusive access to them through a generated lock
  18. file. The lockfile is checked and attempting to open another instance of the
  19. DiskStorageManager on the same files will result in an error. The DiskStorageManager
  20. is also responsible for marshalling given abstract objects into a binary form which
  21. can be written to physical slots.
  22. CachedDiskStorageManager
  23. The CachedDiskStorageManager is a cache wrapper for the DiskStorageManager. Its
  24. purpose is to intercept calls and to maintain a cache of stored objects. The cache
  25. is limited in size by the number of total objects it references. Once the cache
  26. is full it will forget the objects which have been requested the least.
  27. MemoryStorageManager
  28. A storage manager which keeps all its data in memory and provides several
  29. error simulation facilities.
  30. */
  31. package storage
  32. import "sync"
  33. /*
  34. CachedDiskStorageManager data structure
  35. */
  36. type CachedDiskStorageManager struct {
  37. diskstoragemanager *DiskStorageManager // Wrapped instance of DiskStorageManager
  38. mutex *sync.Mutex // Mutex to protect list and map operations
  39. cache map[uint64]*cacheEntry // Map of stored cacheEntry objects
  40. maxObjects int // Max number of objects which should be held in the cache
  41. firstentry *cacheEntry // Pointer to first entry in cacheEntry linked list
  42. lastentry *cacheEntry // Pointer to last entry in cacheEntry linked list
  43. }
  44. /*
  45. cacheEntry data structure
  46. */
  47. type cacheEntry struct {
  48. location uint64 // Slot (logical) of the entry
  49. object interface{} // Object of the entry
  50. prev *cacheEntry // Pointer to previous entry in cacheEntry linked list
  51. next *cacheEntry // Pointer to next entry in cacheEntry linked list
  52. }
  53. /*
  54. Pool for cache entries
  55. */
  56. var entryPool = &sync.Pool{New: func() interface{} { return &cacheEntry{} }}
  57. /*
  58. NewCachedDiskStorageManager creates a new cache wrapper for a DiskStorageManger.
  59. */
  60. func NewCachedDiskStorageManager(diskstoragemanager *DiskStorageManager, maxObjects int) *CachedDiskStorageManager {
  61. return &CachedDiskStorageManager{diskstoragemanager, &sync.Mutex{}, make(map[uint64]*cacheEntry),
  62. maxObjects, nil, nil}
  63. }
  64. /*
  65. Name returns the name of the StorageManager instance.
  66. */
  67. func (cdsm *CachedDiskStorageManager) Name() string {
  68. return cdsm.diskstoragemanager.Name()
  69. }
  70. /*
  71. Root returns a root value.
  72. */
  73. func (cdsm *CachedDiskStorageManager) Root(root int) uint64 {
  74. return cdsm.diskstoragemanager.Root(root)
  75. }
  76. /*
  77. SetRoot writes a root value.
  78. */
  79. func (cdsm *CachedDiskStorageManager) SetRoot(root int, val uint64) {
  80. cdsm.diskstoragemanager.SetRoot(root, val)
  81. }
  82. /*
  83. Insert inserts an object and return its storage location.
  84. */
  85. func (cdsm *CachedDiskStorageManager) Insert(o interface{}) (uint64, error) {
  86. // Cannot cache inserts since the calling code needs a location
  87. loc, err := cdsm.diskstoragemanager.Insert(o)
  88. if loc != 0 && err == nil {
  89. cdsm.mutex.Lock()
  90. defer cdsm.mutex.Unlock()
  91. cdsm.addToCache(loc, o)
  92. }
  93. return loc, err
  94. }
  95. /*
  96. Update updates a storage location.
  97. */
  98. func (cdsm *CachedDiskStorageManager) Update(loc uint64, o interface{}) error {
  99. // Store the update in the cache
  100. cdsm.mutex.Lock()
  101. if entry, ok := cdsm.cache[loc]; !ok {
  102. cdsm.addToCache(loc, o)
  103. } else {
  104. entry.object = o
  105. cdsm.llTouchEntry(entry)
  106. }
  107. cdsm.mutex.Unlock()
  108. return cdsm.diskstoragemanager.Update(loc, o)
  109. }
  110. /*
  111. Free frees a storage location.
  112. */
  113. func (cdsm *CachedDiskStorageManager) Free(loc uint64) error {
  114. if ret := cdsm.diskstoragemanager.Free(loc); ret != nil {
  115. return ret
  116. }
  117. cdsm.mutex.Lock()
  118. defer cdsm.mutex.Unlock()
  119. // Remove location entry from the cache
  120. if entry, ok := cdsm.cache[loc]; ok {
  121. delete(cdsm.cache, entry.location)
  122. cdsm.llRemoveEntry(entry)
  123. }
  124. return nil
  125. }
  126. /*
  127. Fetch fetches an object from a given storage location and writes it to
  128. a given data container.
  129. */
  130. func (cdsm *CachedDiskStorageManager) Fetch(loc uint64, o interface{}) error {
  131. err := cdsm.diskstoragemanager.Fetch(loc, o)
  132. if err != nil {
  133. return err
  134. }
  135. cdsm.mutex.Lock()
  136. defer cdsm.mutex.Unlock()
  137. // Put the retrieved value into the cache
  138. if entry, ok := cdsm.cache[loc]; !ok {
  139. cdsm.addToCache(loc, o)
  140. } else {
  141. cdsm.llTouchEntry(entry)
  142. }
  143. return nil
  144. }
  145. /*
  146. FetchCached fetches an object from a cache and returns its reference.
  147. Returns a storage.ErrNotInCache error if the entry is not in the cache.
  148. */
  149. func (cdsm *CachedDiskStorageManager) FetchCached(loc uint64) (interface{}, error) {
  150. cdsm.mutex.Lock()
  151. defer cdsm.mutex.Unlock()
  152. if entry, ok := cdsm.cache[loc]; ok {
  153. return entry.object, nil
  154. }
  155. return nil, ErrNotInCache
  156. }
  157. /*
  158. Rollback cancels all pending changes which have not yet been written to disk.
  159. */
  160. func (cdsm *CachedDiskStorageManager) Rollback() error {
  161. if cdsm.diskstoragemanager.transDisabled {
  162. return nil
  163. }
  164. err := cdsm.diskstoragemanager.Rollback()
  165. cdsm.mutex.Lock()
  166. defer cdsm.mutex.Unlock()
  167. // Cache is emptied in any case
  168. cdsm.cache = make(map[uint64]*cacheEntry)
  169. cdsm.firstentry = nil
  170. cdsm.lastentry = nil
  171. return err
  172. }
  173. /*
  174. Close the StorageManager and write all pending changes to disk.
  175. */
  176. func (cdsm *CachedDiskStorageManager) Close() error {
  177. return cdsm.diskstoragemanager.Close()
  178. }
  179. /*
  180. Flush writes all pending changes to disk.
  181. */
  182. func (cdsm *CachedDiskStorageManager) Flush() error {
  183. return cdsm.diskstoragemanager.Flush()
  184. }
  185. /*
  186. addToCache adds an entry to the cache.
  187. */
  188. func (cdsm *CachedDiskStorageManager) addToCache(loc uint64, o interface{}) {
  189. var entry *cacheEntry
  190. // Get an entry from the pool or recycle an entry from the cacheEntry
  191. // linked list if the list is full
  192. if len(cdsm.cache) >= cdsm.maxObjects {
  193. entry = cdsm.removeOldestFromCache()
  194. } else {
  195. entry = entryPool.Get().(*cacheEntry)
  196. }
  197. // Fill the entry
  198. entry.location = loc
  199. entry.object = o
  200. // Insert entry into the cacheEntry linked list (this will set the entries
  201. // prev and next pointer)
  202. cdsm.llAppendEntry(entry)
  203. // Insert into the map of stored cacheEntry objects
  204. cdsm.cache[loc] = entry
  205. }
  206. /*
  207. removeOldestFromCache removes the oldest entry from the cache and return it.
  208. */
  209. func (cdsm *CachedDiskStorageManager) removeOldestFromCache() *cacheEntry {
  210. entry := cdsm.firstentry
  211. // If no entries were stored yet just return an entry from the pool
  212. if entry == nil {
  213. return entryPool.Get().(*cacheEntry)
  214. }
  215. // Remove entry from the cacheEntry linked list (this will set the entries
  216. // prev and next pointer)
  217. cdsm.llRemoveEntry(entry)
  218. // Remove entry from the map of stored cacheEntry objects
  219. delete(cdsm.cache, entry.location)
  220. return entry
  221. }
  222. /*
  223. llTouchEntry puts an entry to the last position of the cacheEntry linked list.
  224. Calling llTouchEntry on all requested items ensures that the oldest used
  225. entry is at the beginning of the list.
  226. */
  227. func (cdsm *CachedDiskStorageManager) llTouchEntry(entry *cacheEntry) {
  228. if cdsm.lastentry == entry {
  229. return
  230. }
  231. cdsm.llRemoveEntry(entry)
  232. cdsm.llAppendEntry(entry)
  233. }
  234. /*
  235. llAppendEntry appends a cacheEntry to the end of the cacheEntry linked list.
  236. */
  237. func (cdsm *CachedDiskStorageManager) llAppendEntry(entry *cacheEntry) {
  238. if cdsm.firstentry == nil {
  239. cdsm.firstentry = entry
  240. cdsm.lastentry = entry
  241. entry.prev = nil
  242. } else {
  243. cdsm.lastentry.next = entry
  244. entry.prev = cdsm.lastentry
  245. cdsm.lastentry = entry
  246. }
  247. entry.next = nil
  248. }
  249. /*
  250. llRemoveEntry removes a cacheEntry from the cacheEntry linked list.
  251. */
  252. func (cdsm *CachedDiskStorageManager) llRemoveEntry(entry *cacheEntry) {
  253. if entry == cdsm.firstentry {
  254. cdsm.firstentry = entry.next
  255. }
  256. if cdsm.lastentry == entry {
  257. cdsm.lastentry = entry.prev
  258. }
  259. if entry.prev != nil {
  260. entry.prev.next = entry.next
  261. entry.prev = nil
  262. }
  263. if entry.next != nil {
  264. entry.next.prev = entry.prev
  265. entry.next = nil
  266. }
  267. }