592134522267af6aa2d3438cb87cc22594090ec2
[ep-engine.git] / src / stored-value.h
1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2016 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17
18 #pragma once
19
20 #include "config.h"
21
22 #include "item.h"
23 #include "item_pager.h"
24 #include "utility.h"
25
26 #include <boost/intrusive/list.hpp>
27
28 class HashTable;
29 class OrderedStoredValue;
30
31 /**
32  * In-memory storage for an item.
33  *
34  * This class represents a single document which is present in the HashTable -
35  * essentially this is value_type used by HashTable.
36  *
37  * It contains the documents' key, related metadata (CAS, rev, seqno, ...).
38  * It also has a pointer to the documents' value - which may be null if the
39  * value of the item is not currently resident (for example it's been evicted to
40  * save memory).
41  * Additionally it contains flags to help HashTable manage the state of the
42  * item - such as dirty flag, NRU bits, and a `next` pointer to support
43  * chaining of StoredValues which hash to the same hash bucket.
44  *
45  * The key of the item is of variable length (from 1 to ~256 bytes). As an
46  * optimization, we allocate the key directly after the fixed size of
47  * StoredValue, so StoredValue and its key are contiguous in memory. This saves
48  * us the cost of an indirection compared to storing the key out-of-line, and
49  * the space of a pointer in StoredValue to point to the out-of-line
50  * allocation. It does, however complicate the management of StoredValue
51  * objects as they are now variable-sized - they must be created using a
52  * factory method (StoredValueFactory) and must be heap-allocated, managed
53  * using a unique_ptr (StoredValue::UniquePtr).
54  *
55  * Graphically the looks like:
56  *
57  *              StoredValue::UniquePtr
58  *                          |
59  *                          V
60  *               .-------------------.
61  *               | StoredValue       |
62  *               +-------------------+
63  *           {   | value [ptr]       | ======> Blob (nullptr if evicted)
64  *           {   | next  [ptr]       | ======> StoredValue (next in hash chain).
65  *     fixed {   | CAS               |
66  *    length {   | revSeqno          |
67  *           {   | ...               |
68  *           {   | datatype          |
69  *           {   | internal flags: isDirty, deleted, isOrderedStoredValue ...
70  *               + - - - - - - - - - +
71  *  variable {   | key[]             |
72  *   length  {   | ...               |
73  *               +-------------------+
74  *
75  * OrderedStoredValue is a "subclass" of StoredValue, which is used by
76  * Ephemeral buckets as it supports maintaining a seqno ordering of items in
77  * memory (for Persistent buckets this ordering is maintained on-disk).
78  *
79  * The implementation of OrderedStoredValue is tightly coupled to StoredValue
80  * so it will be described here:
81  *
82  * OrderedStoredValue has the fixed length members of StoredValue, then it's
83  * own fixed length fields (seqno list), followed finally by the variable
84  * length key (again, allocated contiguously):
85  *
86  *              StoredValue::UniquePtr
87  *                          |
88  *                          V
89  *               .--------------------.
90  *               | OrderedStoredValue |
91  *               +--------------------+
92  *           {   | value [ptr]        | ======> Blob (nullptr if evicted)
93  *           {   | next  [ptr]        | ======> StoredValue (next in hash chain).
94  *     fixed {   | StoredValue fixed ...
95  *    length {   + - - - - - - - - - -+
96  *           {   | seqno next [ptr]   |
97  *           {   | seqno prev [ptr]   |
98  *               + - - - - - - - - - -+
99  *  variable {   | key[]              |
100  *   length  {   | ...                |
101  *               +--------------------+
102  *
103  * To support dynamic dispatch (for example to lookup the key, whose location
104  * varies depending if it's StoredValue or OrderedStoredValue), we choose to
105  * use a manual flag-based dispatching (as opposed to a normal vTable based
106  * approach) as the per-object costs are much cheaper - 1 bit for the flag vs.
107  * 8 bytes for a vTable ptr.
108  * StoredValue::isOrderedStoredValue is set to false for StoredValue objects,
109  * and true for OrderedStoredValue objects, and then any methods
110  * needing dynamic dispatch read the value of the flag. Note this means that
111  * the 'base' class (StoredValue) needs to know about all possible subclasses
112  * (only one currently) and what class-specific code to call.
113  * Similary, deletion of OrderedStoredValue objects is delicate - we cannot
114  * safely delete via the base-class pointer directly, as that would only run
115  * ~StoredValue and not the members of the derived class. Instead a custom
116  * deleter is associated with StoredValue::UniquePtr, which checks the flag
117  * and dispatches to the correct destructor.
118  */
119 class StoredValue {
120 public:
121     // Custom deleter for StoredValue objects.
122     struct Deleter {
123         void operator()(StoredValue* val);
124     };
125
126     // Owning pointer type for StoredValue objects.
127     using UniquePtr = std::unique_ptr<StoredValue, Deleter>;
128
129     uint8_t getNRUValue() const;
130
131     void setNRUValue(uint8_t nru_val);
132
133     uint8_t incrNRUValue();
134
135     void referenced();
136
137     /**
138      * Mark this item as needing to be persisted.
139      */
140     void markDirty() {
141         _isDirty = 1;
142     }
143
144     /**
145      * Mark this item as clean.
146      */
147     void markClean() {
148         _isDirty = 0;
149     }
150
151     /**
152      * True if this object is dirty.
153      */
154     bool isDirty() const {
155         return _isDirty;
156     }
157
158     bool eligibleForEviction(item_eviction_policy_t policy) {
159         if (policy == VALUE_ONLY) {
160             return isResident() && !isDirty() && !isDeleted();
161         } else {
162             return !isDirty() && !isDeleted();
163         }
164     }
165
166     /**
167      * Check if this item is expired or not.
168      *
169      * @param asOf the time to be compared with this item's expiry time
170      * @return true if this item's expiry time < asOf
171      */
172     bool isExpired(time_t asOf) const {
173         if (getExptime() != 0 && getExptime() < asOf) {
174             return true;
175         }
176         return false;
177     }
178
179     /**
180      * True if this item is for the given key.
181      *
182      * @param k the key we're checking
183      * @return true if this item's key is equal to k
184      */
185     bool hasKey(const DocKey& k) const {
186         return getKey() == k;
187     }
188
189     /**
190      * Get this item's key.
191      */
192     const SerialisedDocKey& getKey() const {
193         return *const_cast<const SerialisedDocKey*>(
194                 const_cast<StoredValue&>(*this).key());
195     }
196
197     /**
198      * Get this item's value.
199      */
200     const value_t &getValue() const {
201         return value;
202     }
203
204     /**
205      * Get the expiration time of this item.
206      *
207      * @return the expiration time.
208      */
209     time_t getExptime() const {
210         return exptime;
211     }
212
213     void setExptime(time_t tim) {
214         exptime = tim;
215         markDirty();
216     }
217
218     /**
219      * Get the client-defined flags of this item.
220      *
221      * @return the flags.
222      */
223     uint32_t getFlags() const {
224         return flags;
225     }
226
227     /**
228      * Set the client-defined flags for this item.
229      */
230     void setFlags(uint32_t fl) {
231         flags = fl;
232     }
233
234     /**
235      * get the items datatype
236      */
237     protocol_binary_datatype_t getDatatype() const {
238         return datatype;
239     }
240
241     /**
242      * Set the items datatype
243      */
244     void setDatatype(protocol_binary_datatype_t type) {
245         datatype = type;
246     }
247
248     /**
249      * Set a new value for this item.
250      *
251      * @param itm the item with a new value
252      * @param ht the hashtable that contains this StoredValue instance
253      */
254     void setValue(const Item& itm, HashTable& ht);
255
256     void markDeleted() {
257         deleted = true;
258         markDirty();
259     }
260
261     /**
262      * Eject an item value from memory.
263      * @param ht the hashtable that contains this StoredValue instance
264      */
265     bool ejectValue(HashTable &ht, item_eviction_policy_t policy);
266
267     /**
268      * Restore the value for this item.
269      *
270      * @param itm the item to be restored
271      */
272     void restoreValue(const Item& itm);
273
274     /**
275      * Restore the metadata of of a temporary item upon completion of a
276      * background fetch assuming the hashtable bucket is locked.
277      *
278      * @param itm the Item whose metadata is being restored
279      */
280     void restoreMeta(const Item& itm);
281
282     /**
283      * Get this item's CAS identifier.
284      *
285      * @return the cas ID
286      */
287     uint64_t getCas() const {
288         return cas;
289     }
290
291     /**
292      * Set a new CAS ID.
293      */
294     void setCas(uint64_t c) {
295         cas = c;
296     }
297
298     /**
299      * Lock this item until the given time.
300      */
301     void lock(rel_time_t expiry) {
302         if (isDeleted()) {
303             // Cannot lock Deleted items.
304             throw std::logic_error(
305                     "StoredValue::lock: Called on Deleted item");
306         }
307         lock_expiry_or_delete_time = expiry;
308     }
309
310     /**
311      * Unlock this item.
312      */
313     void unlock() {
314         if (isDeleted()) {
315             // Deleted items are not locked - just skip.
316             return;
317         }
318         lock_expiry_or_delete_time = 0;
319     }
320
321     /**
322      * True if this item has an ID.
323      *
324      * An item always has an ID after it's been persisted.
325      */
326     bool hasBySeqno() {
327         return bySeqno > 0;
328     }
329
330     /**
331      * Get this item's ID.
332      *
333      * @return the ID for the item; 0 if the item has no ID
334      */
335     int64_t getBySeqno() const {
336         return bySeqno;
337     }
338
339     /**
340      * Set the ID for this item.
341      *
342      * This is used by the persistene layer.
343      *
344      * It is an error to set an ID on an item that already has one.
345      */
346     void setBySeqno(int64_t to) {
347         if (to <= 0) {
348             throw std::invalid_argument("StoredValue::setBySeqno: to "
349                     "(which is " + std::to_string(to) + ") must be positive");
350         }
351         bySeqno = to;
352     }
353
354     // Marks the stored item as deleted.
355     void setDeleted()
356     {
357         bySeqno = state_deleted_key;
358     }
359
360     // Marks the stored item as non-existent.
361     void setNonExistent()
362     {
363         bySeqno = state_non_existent_key;
364     }
365
366     /**
367      * Is this a temporary item created for processing a get-meta request?
368      */
369     bool isTempItem() const {
370         return (isTempNonExistentItem() || isTempDeletedItem() ||
371                 isTempInitialItem());
372
373      }
374
375     /**
376      * Is this an initial temporary item?
377      */
378      bool isTempInitialItem() const {
379          return bySeqno == state_temp_init;
380     }
381
382     /**
383      * Is this a temporary item created for a non-existent key?
384      */
385     bool isTempNonExistentItem() const {
386          return bySeqno == state_non_existent_key;
387     }
388
389     /**
390      * Is this a temporary item created for a deleted key?
391      */
392     bool isTempDeletedItem() const {
393         return bySeqno == state_deleted_key;
394
395      }
396
397     size_t valuelen() const {
398         if (!isResident()) {
399             return 0;
400         }
401         return value->length();
402     }
403
404     /**
405      * Get the total size of this item.
406      *
407      * @return the amount of memory used by this item.
408      */
409     size_t size() const {
410         return getObjectSize() + valuelen();
411     }
412
413     size_t metaDataSize() const {
414         return getObjectSize();
415     }
416
417     /**
418      * Return true if this item is locked as of the given timestamp.
419      *
420      * @param curtime lock expiration marker (usually the current time)
421      * @return true if the item is locked
422      */
423     bool isLocked(rel_time_t curtime) const {
424         if (isDeleted()) {
425             // Deleted items cannot be locked.
426             return false;
427         }
428
429         if (lock_expiry_or_delete_time == 0 ||
430             (curtime > lock_expiry_or_delete_time)) {
431             return false;
432         }
433         return true;
434     }
435
436     /**
437      * True if this value is resident in memory currently.
438      */
439     bool isResident() const {
440         return value.get() != NULL;
441     }
442
443     void markNotResident() {
444         value.reset();
445     }
446
447     /**
448      * True if this object is logically deleted.
449      */
450     bool isDeleted() const {
451         return deleted;
452     }
453
454     /**
455      * Logically delete this object.
456      */
457     void del(HashTable &ht);
458
459     uint64_t getRevSeqno() const {
460         return revSeqno;
461     }
462
463     /**
464      * Set a new revision sequence number.
465      */
466     void setRevSeqno(uint64_t s) {
467         revSeqno = s;
468     }
469
470     /**
471      * Return true if this is a new cache item.
472      */
473     bool isNewCacheItem() const {
474         return newCacheItem;
475     }
476
477     /**
478      * Set / reset a new cache item flag.
479      */
480     void setNewCacheItem(bool newitem) {
481         newCacheItem = newitem;
482     }
483
484     /**
485      * Generate a new Item out of this object.
486      *
487      * @param lck if true, the new item will return a locked CAS ID.
488      * @param vbucket the vbucket containing this item.
489      */
490     std::unique_ptr<Item> toItem(bool lck, uint16_t vbucket) const;
491
492     /**
493      * Generate a new Item with only key and metadata out of this object.
494      * The item generated will not contain value
495      *
496      * @param vbucket the vbucket containing this item.
497      */
498     std::unique_ptr<Item> toItemWithNoValue(uint16_t vbucket) const;
499
500     void setNext(UniquePtr&& nextSv) {
501         if (stale) {
502             throw std::logic_error(
503                     "StoredValue::setNext: StoredValue is stale,"
504                     "cannot set chain next value");
505         }
506         chain_next_or_replacement = std::move(nextSv);
507     }
508
509     UniquePtr& getNext() {
510         if (stale) {
511             throw std::logic_error(
512                     "StoredValue::getNext: StoredValue is stale,"
513                     "cannot get chain next value");
514         }
515         return chain_next_or_replacement;
516     }
517
518     /**
519      * Set the memory threshold on the current bucket quota for accepting a new mutation
520      */
521     static void setMutationMemoryThreshold(double memThreshold);
522
523     /**
524      * Return the memory threshold for accepting a new mutation
525      */
526     static double getMutationMemThreshold() {
527         return mutation_mem_threshold;
528     }
529
530     /*
531      * Values of the bySeqno attribute used by temporarily created StoredValue
532      * objects.
533      * state_deleted_key: represents an item that's deleted from memory but
534      *                    present in the persistent store.
535      * state_non_existent_key: represents a non existent item
536      * state_collection_open: a special value used by collections to help
537      *  represent a collections life-time in sequence-numbers (start to end).
538      *  If a collection has no end, it's termed open and has an end
539      *  sequence-number of StoredValue::state_collection_open. We do not
540      *  actually assign this value to StoredValue objects, but it's here in
541      *  this "number space" of special sequence numbers to help ensure it's
542      *  different to the other special sequence numbers we define.
543      *
544      */
545     static const int64_t state_deleted_key;
546     static const int64_t state_non_existent_key;
547     static const int64_t state_temp_init;
548     static const int64_t state_collection_open;
549
550     /**
551      * Return the size in byte of this object; both the fixed fields and the
552      * variable-length key. Doesn't include value size (allocated externally).
553      */
554     inline size_t getObjectSize() const;
555
556     /**
557      * Reallocates the dynamic members of StoredValue. Used as part of
558      * defragmentation.
559      */
560     void reallocate();
561
562     /**
563      * Returns pointer to the subclass OrderedStoredValue if it the object is
564      * of the type, if not throws a bad_cast.
565      *
566      * Equivalent to dynamic cast, but done manually as we wanted to avoid
567      * vptr per object.
568      */
569     OrderedStoredValue* toOrderedStoredValue();
570     const OrderedStoredValue* toOrderedStoredValue() const;
571
572     /**
573      * Check if the contents of the StoredValue is same as that of the other
574      * one. Does not consider the intrusive hash bucket link.
575      *
576      * @param other The StoredValue to be compared with
577      */
578     bool operator==(const StoredValue& other) const;
579
580     /* [TBD] : Move this function out of StoredValue class */
581     static bool hasAvailableSpace(EPStats&,
582                                   const Item& item,
583                                   bool isReplication = false);
584
585     /// Return how many bytes are need to store Item as a StoredValue
586     static size_t getRequiredStorage(const Item& item) {
587         return sizeof(StoredValue) +
588                SerialisedDocKey::getObjectSize(item.getKey().size());
589     }
590
591 protected:
592     /**
593      * Constructor - protected as allocation needs to be done via
594      * StoredValueFactory.
595      *
596      * @param itm Item to base this StoredValue on.
597      * @param n The StoredValue which will follow the new stored value in
598      *           the hash bucket chain, which this new item will take
599      *           ownership of. (Typically the top of the hash bucket into
600      *           which the new item is being inserted).
601      * @param stats EPStats to update for this new StoredValue
602      * @param ht HashTable to update stats for this new StoredValue.
603      * @param isOrdered Are we constructing an OrderedStoredValue?
604      */
605     StoredValue(const Item& itm,
606                 UniquePtr n,
607                 EPStats& stats,
608                 HashTable& ht,
609                 bool isOrdered)
610         : value(itm.getValue()),
611           chain_next_or_replacement(std::move(n)),
612           cas(itm.getCas()),
613           revSeqno(itm.getRevSeqno()),
614           bySeqno(itm.getBySeqno()),
615           lock_expiry_or_delete_time(0),
616           exptime(itm.getExptime()),
617           flags(itm.getFlags()),
618           datatype(itm.getDataType()),
619           deleted(itm.isDeleted()),
620           newCacheItem(true),
621           isOrdered(isOrdered),
622           nru(itm.getNRUValue()),
623           stale(false) {
624         // Placement-new the key which lives in memory directly after this
625         // object.
626         new (key()) SerialisedDocKey(itm.getKey());
627
628         if (isTempInitialItem()) {
629             markClean();
630         } else {
631             markDirty();
632         }
633
634         if (isTempItem()) {
635             markNotResident();
636         }
637
638         increaseMetaDataSize(ht, stats, metaDataSize());
639         increaseCacheSize(ht, size());
640
641         ObjectRegistry::onCreateStoredValue(this);
642     }
643
644     // Destructor. protected, as needs to be carefully deleted (via
645     // StoredValue::Destructor) depending on the value of isOrdered flag.
646     ~StoredValue() {
647         ObjectRegistry::onDeleteStoredValue(this);
648     }
649
650     /**
651      * Copy constructor - protected as allocation needs to be done via
652      * StoredValueFactory.
653      *
654      * @param other StoredValue being copied
655      * @param n The StoredValue which will follow the new stored value in
656      *           the hash bucket chain, which this new item will take
657      *           ownership of. (Typically the top of the hash bucket into
658      *           which the new item is being inserted).
659      * @param stats EPStats to update for this new StoredValue
660      * @param ht HashTable to update stats for this new StoredValue.
661      */
662     StoredValue(const StoredValue& other,
663                 UniquePtr n,
664                 EPStats& stats,
665                 HashTable& ht)
666         : value(other.value),
667           chain_next_or_replacement(std::move(n)),
668           cas(other.cas),
669           revSeqno(other.revSeqno),
670           bySeqno(other.bySeqno),
671           lock_expiry_or_delete_time(other.lock_expiry_or_delete_time),
672           exptime(other.exptime),
673           flags(other.flags),
674           datatype(other.datatype),
675           _isDirty(other._isDirty),
676           deleted(other.deleted),
677           newCacheItem(other.newCacheItem),
678           isOrdered(other.isOrdered),
679           nru(other.nru),
680           stale(false) {
681         // Placement-new the key which lives in memory directly after this
682         // object.
683         StoredDocKey sKey(other.getKey());
684         new (key()) SerialisedDocKey(sKey);
685
686         increaseMetaDataSize(ht, stats, metaDataSize());
687         increaseCacheSize(ht, size());
688
689         ObjectRegistry::onCreateStoredValue(this);
690     }
691
692     /* Do not allow assignment */
693     StoredValue& operator=(const StoredValue& other) = delete;
694
695     /**
696      * Get the address of item's key .
697      */
698     inline SerialisedDocKey* key();
699
700     /**
701      * Logically mark this SV as deleted.
702      * Implementation for StoredValue instances (dispatched to by del() based
703      * on isOrdered==false).
704      */
705     void deleteImpl(HashTable& ht);
706
707     /* Update the value for this SV from the given item.
708      * Implementation for StoredValue instances (dispatched to by setValue()).
709      */
710     void setValueImpl(const Item& itm, HashTable& ht);
711
712     friend class HashTable;
713     friend class StoredValueFactory;
714     friend std::ostream& operator<<(std::ostream& os, const HashTable& ht);
715
716     value_t            value;          // 8 bytes
717
718     // Serves two purposes -
719     // 1. Used to implement HashTable chaining (for elements hashing to the same
720     // bucket).
721     // 2. Once the stored value has been marked stale, this is used to point at
722     // the replacement stored value. In this case, *we do not have ownership*,
723     // so we release the ptr in the destructor. The replacement is needed to
724     // determine if it would also appear in a given rangeRead - we should return
725     // only the newer version if so.
726     UniquePtr chain_next_or_replacement; // 8 bytes
727     uint64_t           cas;            //!< CAS identifier.
728     uint64_t           revSeqno;       //!< Revision id sequence number
729     int64_t            bySeqno;        //!< By sequence id number
730     /// For alive items: GETL lock expiration. For deleted items: delete time.
731     rel_time_t         lock_expiry_or_delete_time;
732     uint32_t           exptime;        //!< Expiration time of this item.
733     uint32_t           flags;          // 4 bytes
734     protocol_binary_datatype_t datatype; // 1 byte
735     bool               _isDirty  :  1; // 1 bit
736     bool               deleted   :  1;
737     bool               newCacheItem : 1;
738     const bool isOrdered : 1; //!< Is this an instance of OrderedStoredValue?
739     uint8_t            nru       :  2; //!< True if referenced since last sweep
740     bool unused : 2; // Unused bits in first byte of bitfields.
741
742     // Indicates if a newer instance of the item is added. Logically part of
743     // OSV, but is physically located in SV as there are spare bytes here.
744     // Guarded by the SequenceList's writeLock.
745     // NOTE: As this is guarded by a different lock to the rest of the SV,
746     // it *must* be in a different byte than any other data not guarded by
747     // writeLock (Hence why this isn't in the same byte as _isDirty, deleted,
748     // newCacheItem etc). To achieve this std::atomic is used to ensure accesses
749     // are not "optimized" and merged with the previous byte. The thread-safety
750     // of std::atomic is not actually used/needed; we just need the no-merge
751     // guarantee.
752     // Note (2): Only 1 bit of this is currently used; rest is "spare".
753     std::atomic<bool> stale;
754
755     static void increaseMetaDataSize(HashTable &ht, EPStats &st, size_t by);
756     static void reduceMetaDataSize(HashTable &ht, EPStats &st, size_t by);
757     static void increaseCacheSize(HashTable &ht, size_t by);
758     static void reduceCacheSize(HashTable &ht, size_t by);
759     static double mutation_mem_threshold;
760
761     friend std::ostream& operator<<(std::ostream& os, const StoredValue& sv);
762 };
763
764 std::ostream& operator<<(std::ostream& os, const StoredValue& sv);
765
766 /**
767  * Subclass of StoredValue which additionally supports sequence number ordering.
768  *
769  * See StoredValue for implementation details.
770  */
771 class OrderedStoredValue : public StoredValue {
772 public:
773     // Intrusive linked-list for sequence number ordering.
774     // Guarded by the SequenceList's writeLock.
775     boost::intrusive::list_member_hook<> seqno_hook;
776
777     ~OrderedStoredValue() {
778         if (stale) {
779             // This points to the replacement OSV which we do not actually own.
780             // We are reusing a unique_ptr so we explicitly release it in this
781             // case. We /do/ own the chain_next if we are not stale.
782             chain_next_or_replacement.release();
783         }
784     }
785
786     /**
787      * True if a newer version of the same key exists in the HashTable.
788      * Note: Only true for OrderedStoredValues which are no longer in the
789      *       HashTable (and only live in SequenceList)
790      * @param writeGuard The locked SeqList writeLock which guards the stale
791      * param.
792      */
793     bool isStale(std::lock_guard<std::mutex>& writeGuard) const {
794         return stale;
795     }
796
797     /**
798      * Marks that newer instance of this item is added in the HashTable
799      * @param writeLock The SeqList writeLock which guards the stale param.
800      */
801     void markStale(std::lock_guard<std::mutex>& writeGuard,
802                    StoredValue* newSv) {
803         // next is a UniquePtr which is up to this point was used for chaining
804         // in the HashTable. Now this item is stale, we are reusing this to
805         // point to the updated version of this StoredValue. _BUT_ we do not
806         // own the new SV. At destruction, we must release this ptr if
807         // we are stale.
808         chain_next_or_replacement.reset(newSv);
809         stale = true;
810     }
811
812     StoredValue* getReplacementIfStale(
813             std::lock_guard<std::mutex>& writeGuard) const {
814         if (!stale) {
815             return nullptr;
816         }
817
818         return chain_next_or_replacement.get();
819     }
820
821     /**
822      * Check if the contents of the StoredValue is same as that of the other
823      * one. Does not consider the intrusive hash bucket link.
824      *
825      * @param other The StoredValue to be compared with
826      */
827     bool operator==(const OrderedStoredValue& other) const;
828
829     /// Return how many bytes are need to store Item as an OrderedStoredValue
830     static size_t getRequiredStorage(const Item& item) {
831         return sizeof(OrderedStoredValue) +
832                SerialisedDocKey::getObjectSize(item.getKey());
833     }
834
835     /**
836      * Return the time the item was deleted. Only valid for deleted items.
837      */
838     rel_time_t getDeletedTime() const;
839
840 protected:
841     SerialisedDocKey* key() {
842         return reinterpret_cast<SerialisedDocKey*>(this + 1);
843     }
844
845     /**
846      * Logically mark this OSV as deleted. Implementation for
847      * OrderedStoredValue instances (dispatched to by del() based on
848      * isOrdered==true).
849      */
850     void deleteImpl(HashTable& ht);
851
852     /* Update the value for this OSV from the given item.
853      * Implementation for OrderedStoredValue instances (dispatched to by
854      *  setValue()).
855      */
856     void setValueImpl(const Item& itm, HashTable& ht);
857
858     /**
859      * Set the time the item was deleted to the specified time.
860      */
861     inline void setDeletedTime(rel_time_t time);
862
863 private:
864     // Constructor. Private, as needs to be carefully created via
865     // OrderedStoredValueFactory.
866     OrderedStoredValue(const Item& itm,
867                        UniquePtr n,
868                        EPStats& stats,
869                        HashTable& ht)
870         : StoredValue(itm, std::move(n), stats, ht, /*isOrdered*/ true) {
871     }
872
873     // Copy Constructor. Private, as needs to be carefully created via
874     // OrderedStoredValueFactory.
875     //
876     // Only StoredValue part (Hash Chain included) is copied. Hence the copied
877     // StoredValue will be in the HashTable, but not in the ordered
878     // data structure.
879     OrderedStoredValue(const StoredValue& other,
880                        UniquePtr n,
881                        EPStats& stats,
882                        HashTable& ht)
883         : StoredValue(other, std::move(n), stats, ht) {
884     }
885
886     /* Do not allow assignment */
887     OrderedStoredValue& operator=(const OrderedStoredValue& other) = delete;
888
889     // Grant friendship so our factory can call our (private) constructor.
890     friend class OrderedStoredValueFactory;
891
892     // Grant friendship to base class so it can perform flag dispatch to our
893     // overridden protected methods.
894     friend class StoredValue;
895 };
896
897 SerialisedDocKey* StoredValue::key() {
898     // key is located immediately following the object.
899     if (isOrdered) {
900         return static_cast<OrderedStoredValue*>(this)->key();
901     } else {
902         return reinterpret_cast<SerialisedDocKey*>(this + 1);
903     }
904 }
905
906 size_t StoredValue::getObjectSize() const {
907     // Size of fixed part of OrderedStoredValue or StoredValue, plus size of
908     // (variable) key.
909     if (isOrdered) {
910         return sizeof(OrderedStoredValue) + getKey().getObjectSize();
911     }
912     return sizeof(*this) + getKey().getObjectSize();
913 }