1 // Copyright (C) 2019 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // A disk-backed bitmap. 16 // 17 // For writing: 18 // 19 // Init(); 20 // SetBit(bit_idx, <true|false>) // Automatically grows with SetBit. 21 // ... 22 // Sync(); // SetBit takes effect immediately but Sync persists to disk. 23 // 24 // For reading: 25 // 26 // InitForRead(); 27 // GetBit(bit_idx); 28 // ... 29 // Close(); 30 // 31 // InitForRead uses mmap MAP_POPULATE to fault the entire file to 32 // memory. Subsequent random GetBits are very fast (nanoseconds). 33 // 34 // It's ok to call Init after InitForRead. The last "Init" call takes 35 // effect. 36 37 #ifndef ICING_LEGACY_INDEX_ICING_FLASH_BITMAP_H_ 38 #define ICING_LEGACY_INDEX_ICING_FLASH_BITMAP_H_ 39 40 #include <cstdint> 41 #include <memory> 42 #include <string> 43 44 #include "icing/legacy/index/icing-filesystem.h" 45 #include "icing/legacy/index/icing-mmapper.h" 46 #include "icing/util/crc32.h" 47 48 namespace icing { 49 namespace lib { 50 51 class IcingFlashBitmap { 52 public: 53 using Word = uint32_t; 54 55 static constexpr size_t kGrowSize = (1u << 12); // 4KB; 56 static constexpr size_t kWordBits = 8 * sizeof(Word); 57 IcingFlashBitmap(const std::string & filename,const IcingFilesystem * filesystem)58 IcingFlashBitmap(const std::string &filename, 59 const IcingFilesystem *filesystem) 60 : filesystem_(filesystem), filename_(filename), open_type_(UNOPENED) {} ~IcingFlashBitmap()61 ~IcingFlashBitmap() { Close(); } 62 63 // Init for read and write. Returns true on success. Does not verify 64 // the data checksum. To do so call Verify explicitly. 65 bool Init(); 66 67 // Init for read only. Also faults the entire file into memory with 68 // MAP_POPULATE. Does not verify the data checksum. To do so call Verify 69 // explicitly. 70 bool InitForRead(); 71 72 // Verifies the integrity of the data by checking the header values 73 // and data checksum. Returns true if opened with InitForRead() and 74 // file does not exist. 75 bool Verify() const; 76 77 // If either of the init functions was called successfully. is_initialized()78 bool is_initialized() const { return open_type_ != UNOPENED; } 79 80 // Close file and release resources. Leaves the bitmap in uninitialized state. 81 void Close(); 82 83 // The following functions require is_initialized() with Init() 84 // EXCEPT GetBit() which requires Init() or InitForRead(). 85 86 // Close and delete the underlying file. Leaves the bitmap in uninitialized 87 // state (even if deletion failed). 88 bool Delete(); 89 90 // Delete the underlying file, and reinitialize it. If successful, the bitmap 91 // is initialized. Clear()92 bool Clear() { return Delete() && Init(); } 93 94 // Sync the changes to disk. 95 bool Sync(); 96 97 uint64_t GetDiskUsage() const; 98 99 // Set or clear a bit at idx. Automatically resizes the file to fit 100 // idx. Returns true on success. 101 bool SetBit(uint64_t idx, bool value); 102 103 // Get the value of bit at idx. If idx is out of range, returns false. 104 // Can be called with InitForRead(). 105 bool GetBit(uint64_t idx) const; 106 107 // Get the idx'th word in the bitmap. If idx is out of range, returns zero. 108 // Can be called with InitForRead(). 109 Word GetWord(uint64_t idx) const; 110 size_t NumWords() const; 111 112 // Clear all bits starting at idx. 113 void Truncate(uint64_t idx); 114 115 // Ors all the set bits from a given bitmap into this bitmap. 116 bool OrBitmap(const IcingFlashBitmap &bitmap); 117 filename()118 const std::string &filename() const { return filename_; } 119 120 // If the bitmap is dirty, update the crc and mark it clean. 121 Crc32 UpdateCrc(); 122 123 // Calculates the crc and returns it. This function does NOT update the crc 124 // in the header. 125 Crc32 GetCrc() const; 126 127 private: 128 class Accessor; 129 struct Header; 130 131 static const uint32_t kMagic = 0x394b0698; 132 static const uint32_t kCurVersion = 18; 133 134 enum OpenType { UNOPENED, READ_ONLY, READ_WRITE }; 135 136 static Word GetWordBitmask(uint64_t idx); 137 138 // Increase the size of the bitmap file to the new size. Return true 139 // on success. 140 bool Grow(size_t new_file_size); 141 142 // Upgrade for version 18. 143 bool UpgradeTo18(); 144 145 // Legacy file system. Switch to use the new Filesystem class instead. 146 const IcingFilesystem *const filesystem_; 147 std::string filename_; 148 OpenType open_type_; 149 std::unique_ptr<IcingMMapper> mmapper_; 150 }; 151 152 } // namespace lib 153 } // namespace icing 154 155 #endif // ICING_LEGACY_INDEX_ICING_FLASH_BITMAP_H_ 156