2 * Copyright (c) 2018-2020 Inria
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * Definition of a dictionary based cache compressor. Each entry is compared
31 * against a dictionary to search for matches.
33 * The dictionary is composed of 32-bit entries, and the comparison is done
36 * The patterns are implemented as individual classes that have a checking
37 * function isPattern(), to determine if the data fits the pattern, and a
38 * decompress() function, which decompresses the contents of a pattern.
39 * Every new pattern must inherit from the Pattern class and be added to the
43 #ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
44 #define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
51 #include <type_traits>
54 #include "base/statistics.hh"
55 #include "base/types.hh"
56 #include "mem/cache/compressors/base.hh"
58 struct BaseDictionaryCompressorParams;
60 namespace Compressor {
62 class BaseDictionaryCompressor : public Base
65 /** Dictionary size. */
66 const std::size_t dictionarySize;
68 /** Number of valid entries in the dictionary. */
69 std::size_t numEntries;
71 struct DictionaryStats : public Stats::Group
73 const BaseDictionaryCompressor& compressor;
75 DictionaryStats(BaseStats &base_group,
76 BaseDictionaryCompressor& _compressor);
78 void regStats() override;
80 /** Number of data entries that were compressed to each pattern. */
81 Stats::Vector patterns;
85 * Trick function to get the number of patterns.
87 * @return The number of defined patterns.
89 virtual uint64_t getNumPatterns() const = 0;
92 * Get meta-name assigned to the given pattern.
94 * @param number The number of the pattern.
95 * @return The meta-name of the pattern.
97 virtual std::string getName(int number) const = 0;
100 typedef BaseDictionaryCompressorParams Params;
101 BaseDictionaryCompressor(const Params *p);
102 ~BaseDictionaryCompressor() = default;
106 * A template version of the dictionary compressor that allows to choose the
109 * @tparam The type of a dictionary entry (e.g., uint16_t, uint32_t, etc).
112 class DictionaryCompressor : public BaseDictionaryCompressor
115 /** Convenience typedef for a dictionary entry. */
116 typedef std::array<uint8_t, sizeof(T)> DictionaryEntry;
119 * Compression data for the dictionary compressor. It consists of a vector
124 // Forward declaration of a pattern
126 class UncompressedPattern;
129 template <T value, T mask>
130 class MaskedValuePattern;
131 template <T mask, int location>
132 class LocatedMaskedPattern;
133 template <class RepT>
134 class RepeatedValuePattern;
135 template <std::size_t DeltaSizeBits>
139 * Create a factory to determine if input matches a pattern. The if else
140 * chains are constructed by recursion. The patterns should be explored
141 * sorted by size for correct behaviour.
143 template <class Head, class... Tail>
146 static std::unique_ptr<Pattern> getPattern(
147 const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
148 const int match_location)
150 // If match this pattern, instantiate it. If a negative match
151 // location is used, the patterns that use the dictionary bytes
152 // must return false. This is used when there are no dictionary
154 if (Head::isPattern(bytes, dict_bytes, match_location)) {
155 return std::unique_ptr<Pattern>(
156 new Head(bytes, match_location));
157 // Otherwise, go for next pattern
159 return Factory<Tail...>::getPattern(bytes, dict_bytes,
166 * Specialization to end the recursion. This must be called when all
167 * other patterns failed, and there is no choice but to leave data
168 * uncompressed. As such, this pattern must inherit from the uncompressed
171 template <class Head>
174 static_assert(std::is_base_of<UncompressedPattern, Head>::value,
175 "The last pattern must always be derived from the uncompressed "
178 static std::unique_ptr<Pattern>
179 getPattern(const DictionaryEntry& bytes,
180 const DictionaryEntry& dict_bytes, const int match_location)
182 return std::unique_ptr<Pattern>(new Head(bytes, match_location));
186 /** The dictionary. */
187 std::vector<DictionaryEntry> dictionary;
190 * Since the factory cannot be instantiated here, classes that inherit
191 * from this base class have to implement the call to their factory's
194 virtual std::unique_ptr<Pattern>
195 getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
196 const int match_location) const = 0;
201 * @param data Data to be compressed.
202 * @return The pattern this data matches.
204 std::unique_ptr<Pattern> compressValue(const T data);
207 * Decompress a pattern into a value that fits in a dictionary entry.
209 * @param pattern The pattern to be decompressed.
210 * @return The decompressed word.
212 T decompressValue(const Pattern* pattern);
214 /** Clear all dictionary entries. */
215 virtual void resetDictionary();
218 * Add an entry to the dictionary.
220 * @param data The new entry.
222 virtual void addToDictionary(const DictionaryEntry data) = 0;
225 * Instantiate a compression data of the sub-class compressor.
227 * @return The new compression data entry.
229 virtual std::unique_ptr<DictionaryCompressor::CompData>
230 instantiateDictionaryCompData() const;
235 * @param chunks The cache line to be compressed.
236 * @return Cache line after compression.
238 std::unique_ptr<Base::CompressionData> compress(
239 const std::vector<Chunk>& chunks);
241 using BaseDictionaryCompressor::compress;
246 * @param comp_data Compressed cache line.
247 * @param data The cache line to be decompressed.
249 void decompress(const CompressionData* comp_data, uint64_t* data) override;
252 * Turn a value into a dictionary entry.
254 * @param value The value to turn.
255 * @return A dictionary entry containing the value.
257 static DictionaryEntry toDictionaryEntry(T value);
260 * Turn a dictionary entry into a value.
262 * @param The dictionary entry to turn.
263 * @return The value that the dictionary entry contained.
265 static T fromDictionaryEntry(const DictionaryEntry& entry);
268 typedef BaseDictionaryCompressorParams Params;
269 DictionaryCompressor(const Params *p);
270 ~DictionaryCompressor() = default;
274 * The compressed data is composed of multiple pattern entries. To add a new
275 * pattern one should inherit from this class and implement isPattern() and
276 * decompress(). Then the new pattern must be added to the PatternFactory
277 * declaration in crescent order of size (in the DictionaryCompressor class).
280 class DictionaryCompressor<T>::Pattern
283 /** Pattern enum number. */
284 const int patternNumber;
286 /** Code associated to the pattern. */
289 /** Length, in bits, of the code and match location. */
290 const uint8_t length;
292 /** Number of unmatched bits. */
293 const uint8_t numUnmatchedBits;
295 /** Index representing the the match location. */
296 const int matchLocation;
298 /** Wether the pattern allocates a dictionary entry or not. */
303 * Default constructor.
305 * @param number Pattern number.
306 * @param code Code associated to this pattern.
307 * @param metadata_length Length, in bits, of the code and match location.
308 * @param num_unmatched_bits Number of unmatched bits.
309 * @param match_location Index of the match location.
311 Pattern(const int number, const uint64_t code,
312 const uint64_t metadata_length, const uint64_t num_unmatched_bits,
313 const int match_location, const bool allocate = true)
314 : patternNumber(number), code(code), length(metadata_length),
315 numUnmatchedBits(num_unmatched_bits),
316 matchLocation(match_location), allocate(allocate)
320 /** Default destructor. */
321 virtual ~Pattern() = default;
324 * Get enum number associated to this pattern.
326 * @return The pattern enum number.
328 int getPatternNumber() const { return patternNumber; };
331 * Get code of this pattern.
335 uint8_t getCode() const { return code; }
338 * Get the index of the dictionary match location.
340 * @return The index of the match location.
342 uint8_t getMatchLocation() const { return matchLocation; }
345 * Get size, in bits, of the pattern (excluding prefix). Corresponds to
346 * unmatched_data_size + code_length.
353 return numUnmatchedBits + length;
357 * Determine if pattern allocates a dictionary entry.
359 * @return True if should allocate a dictionary entry.
361 bool shouldAllocate() const { return allocate; }
364 * Extract pattern's information to a string.
366 * @return A string containing the relevant pattern metadata.
371 return csprintf("pattern %s (encoding %x, size %u bits)",
372 getPatternNumber(), getCode(), getSizeBits());
376 * Decompress the pattern. Each pattern has its own way of interpreting
379 * @param dict_bytes The bytes in the corresponding matching entry.
380 * @return The decompressed pattern.
382 virtual DictionaryEntry decompress(
383 const DictionaryEntry dict_bytes) const = 0;
387 class DictionaryCompressor<T>::CompData : public CompressionData
390 /** The patterns matched in the original line. */
391 std::vector<std::unique_ptr<Pattern>> entries;
394 ~CompData() = default;
397 * Add a pattern entry to the list of patterns.
399 * @param entry The new pattern entry.
401 virtual void addEntry(std::unique_ptr<Pattern>);
405 * A pattern containing the original uncompressed data. This should be the
406 * worst case of every pattern factory, where if all other patterns fail,
407 * an instance of this pattern is created.
410 class DictionaryCompressor<T>::UncompressedPattern
411 : public DictionaryCompressor<T>::Pattern
414 /** A copy of the original data. */
415 const DictionaryEntry data;
418 UncompressedPattern(const int number,
420 const uint64_t metadata_length,
421 const int match_location,
422 const DictionaryEntry bytes)
423 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
424 sizeof(T) * 8, match_location, true),
430 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
431 const int match_location)
433 // An entry can always be uncompressed
438 decompress(const DictionaryEntry dict_bytes) const override
445 * A pattern that compares masked values against dictionary entries. If
446 * the masked dictionary entry matches perfectly the masked value to be
447 * compressed, there is a pattern match.
449 * For example, if the mask is 0xFF00 (that is, this pattern matches the MSB),
450 * the value (V) 0xFF20 is being compressed, and the dictionary contains
451 * the value (D) 0xFF03, this is a match (V & mask == 0xFF00 == D & mask),
452 * and 0x0020 is added to the list of unmatched bits.
454 * @tparam mask A mask containing the bits that must match.
458 class DictionaryCompressor<T>::MaskedPattern
459 : public DictionaryCompressor<T>::Pattern
462 static_assert(mask != 0, "The pattern's value mask must not be zero. Use "
463 "the uncompressed pattern instead.");
465 /** A copy of the bits that do not belong to the mask. */
469 MaskedPattern(const int number,
471 const uint64_t metadata_length,
472 const int match_location,
473 const DictionaryEntry bytes,
474 const bool allocate = true)
475 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
476 popCount(static_cast<T>(~mask)), match_location, allocate),
477 bits(DictionaryCompressor<T>::fromDictionaryEntry(bytes) & ~mask)
482 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
483 const int match_location)
485 const T masked_bytes =
486 DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
487 const T masked_dict_bytes =
488 DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
489 return (match_location >= 0) && (masked_bytes == masked_dict_bytes);
493 decompress(const DictionaryEntry dict_bytes) const override
495 const T masked_dict_bytes =
496 DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
497 return DictionaryCompressor<T>::toDictionaryEntry(
498 bits | masked_dict_bytes);
503 * A pattern that compares masked values to a masked portion of a fixed value.
504 * If all the masked bits match the provided non-dictionary value, there is a
507 * For example, assume the mask is 0xFF00 (that is, this pattern matches the
508 * MSB), and we are searching for data containing only ones (i.e., the fixed
510 * If the value (V) 0xFF20 is being compressed, this is a match (V & mask ==
511 * 0xFF00 == 0xFFFF & mask), and 0x20 is added to the list of unmatched bits.
512 * If the value (V2) 0x0120 is being compressed, this is not a match
513 * ((V2 & mask == 0x0100) != (0xFF00 == 0xFFFF & mask).
515 * @tparam value The value that is being matched against.
516 * @tparam mask A mask containing the bits that must match the given value.
519 template <T value, T mask>
520 class DictionaryCompressor<T>::MaskedValuePattern
521 : public MaskedPattern<mask>
524 static_assert(mask != 0, "The pattern's value mask must not be zero.");
527 MaskedValuePattern(const int number,
529 const uint64_t metadata_length,
530 const int match_location,
531 const DictionaryEntry bytes,
532 const bool allocate = false)
533 : MaskedPattern<mask>(number, code, metadata_length, match_location,
539 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
540 const int match_location)
542 // Compare the masked fixed value to the value being checked for
543 // patterns. Since the dictionary is not being used the match_location
545 const T masked_bytes =
546 DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
547 return ((value & mask) == masked_bytes);
551 decompress(const DictionaryEntry dict_bytes) const override
553 return MaskedPattern<mask>::decompress(
554 DictionaryCompressor<T>::toDictionaryEntry(value));
559 * A pattern that narrows the MaskedPattern by allowing a only single possible
560 * dictionary entry to be matched against.
562 * @tparam mask A mask containing the bits that must match.
563 * @tparam location The index of the single entry allowed to match.
566 template <T mask, int location>
567 class DictionaryCompressor<T>::LocatedMaskedPattern
568 : public MaskedPattern<mask>
571 LocatedMaskedPattern(const int number,
573 const uint64_t metadata_length,
574 const int match_location,
575 const DictionaryEntry bytes,
576 const bool allocate = true)
577 : MaskedPattern<mask>(number, code, metadata_length, match_location,
583 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
584 const int match_location)
586 // Besides doing the regular masked pattern matching, the match
587 // location must match perfectly with this instance's
588 return (match_location == location) &&
589 MaskedPattern<mask>::isPattern(bytes, dict_bytes, match_location);
594 * A pattern that checks if dictionary entry sized values are solely composed
595 * of multiple copies of a single value.
597 * For example, if we are looking for repeated bytes in a 1-byte granularity
598 * (RepT is uint8_t), the value 0x3232 would match, however 0x3332 wouldn't.
600 * @tparam RepT The type of the repeated value, which must fit in a dictionary
604 template <class RepT>
605 class DictionaryCompressor<T>::RepeatedValuePattern
606 : public DictionaryCompressor<T>::Pattern
609 static_assert(sizeof(T) > sizeof(RepT), "The repeated value's type must "
610 "be smaller than the dictionary entry's type.");
612 /** The repeated value. */
616 RepeatedValuePattern(const int number,
618 const uint64_t metadata_length,
619 const int match_location,
620 const DictionaryEntry bytes,
621 const bool allocate = true)
622 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
623 8 * sizeof(RepT), match_location, allocate),
624 value(DictionaryCompressor<T>::fromDictionaryEntry(bytes))
629 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
630 const int match_location)
632 // Parse the dictionary entry in a RepT granularity, and if all values
633 // are equal, this is a repeated value pattern. Since the dictionary
634 // is not being used, the match_location is irrelevant
635 T bytes_value = DictionaryCompressor<T>::fromDictionaryEntry(bytes);
636 const RepT rep_value = bytes_value;
637 for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
638 RepT cur_value = bytes_value;
639 if (cur_value != rep_value) {
642 bytes_value >>= 8 * sizeof(RepT);
648 decompress(const DictionaryEntry dict_bytes) const override
650 // The decompressed value is just multiple consecutive instances of
653 for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
654 decomp_value <<= 8 * sizeof(RepT);
655 decomp_value |= value;
657 return DictionaryCompressor<T>::toDictionaryEntry(decomp_value);
662 * A pattern that checks whether the difference of the value and the dictionary
663 * entries' is below a certain threshold. If so, the pattern is successful,
664 * and only the delta bits need to be stored.
666 * For example, if the delta can only contain up to 4 bits, and the dictionary
667 * contains the entry 0xA231, the value 0xA232 would be compressible, and
668 * the delta 0x1 would be stored. The value 0xA249, on the other hand, would
669 * not be compressible, since its delta (0x18) needs 5 bits to be stored.
671 * @tparam DeltaSizeBits Size of a delta entry, in number of bits, which
672 * determines the threshold. Must always be smaller
673 * than the dictionary entry type's size.
676 template <std::size_t DeltaSizeBits>
677 class DictionaryCompressor<T>::DeltaPattern
678 : public DictionaryCompressor<T>::Pattern
681 static_assert(DeltaSizeBits < (sizeof(T) * 8),
682 "Delta size must be smaller than base size");
685 * The original value. In theory we should keep only the deltas, but
686 * the dictionary entry is not inserted in the dictionary before the
687 * call to the constructor, so the delta cannot be calculated then.
689 const DictionaryEntry bytes;
692 DeltaPattern(const int number,
694 const uint64_t metadata_length,
695 const int match_location,
696 const DictionaryEntry bytes)
697 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
698 DeltaSizeBits, match_location, false),
704 * Compares a given value against a base to calculate their delta, and
705 * then determines whether it fits a limited sized container.
707 * @param bytes Value to be compared against base.
708 * @param base_bytes Base value.
709 * @return Whether the value fits in the container.
712 isValidDelta(const DictionaryEntry& bytes,
713 const DictionaryEntry& base_bytes)
715 const typename std::make_signed<T>::type limit = DeltaSizeBits ?
716 mask(DeltaSizeBits - 1) : 0;
718 DictionaryCompressor<T>::fromDictionaryEntry(bytes);
720 DictionaryCompressor<T>::fromDictionaryEntry(base_bytes);
721 const typename std::make_signed<T>::type delta = value - base;
722 return (delta >= -limit) && (delta <= limit);
726 isPattern(const DictionaryEntry& bytes,
727 const DictionaryEntry& dict_bytes, const int match_location)
729 return (match_location >= 0) && isValidDelta(bytes, dict_bytes);
733 decompress(const DictionaryEntry dict_bytes) const override
739 } // namespace Compressor
741 #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__