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