1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef CONTENT_BROWSER_INDEXED_DB_INDEXED_DB_LEVELDB_CODING_H_ 6 #define CONTENT_BROWSER_INDEXED_DB_INDEXED_DB_LEVELDB_CODING_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include <memory> 12 #include <string> 13 #include <utility> 14 #include <vector> 15 16 #include "base/logging.h" 17 #include "base/macros.h" 18 #include "base/memory/ref_counted.h" 19 #include "base/strings/string16.h" 20 #include "base/strings/string_piece.h" 21 #include "components/services/storage/indexed_db/scopes/scope_lock_range.h" 22 #include "content/common/content_export.h" 23 #include "third_party/blink/public/common/indexeddb/indexeddb_key.h" 24 #include "third_party/blink/public/common/indexeddb/indexeddb_key_path.h" 25 26 namespace content { 27 28 namespace indexed_db { 29 // 0 - Initial version. 30 // 1 - Adds UserIntVersion to DatabaseMetaData. 31 // 2 - Adds DataVersion to to global metadata. 32 // 3 - Adds metadata needed for blob support. 33 // 4 - Adds size & last_modified to 'file' blob_info encodings. 34 const constexpr int64_t kLatestKnownSchemaVersion = 4; 35 } // namespace indexed_db 36 37 CONTENT_EXPORT extern const unsigned char kMinimumIndexId; 38 39 CONTENT_EXPORT std::string MaxIDBKey(); 40 CONTENT_EXPORT std::string MinIDBKey(); 41 42 // DatabaseId, BlobNumber 43 typedef std::pair<int64_t, int64_t> BlobJournalEntryType; 44 typedef std::vector<BlobJournalEntryType> BlobJournalType; 45 46 CONTENT_EXPORT void EncodeByte(unsigned char value, std::string* into); 47 CONTENT_EXPORT void EncodeBool(bool value, std::string* into); 48 49 // Unlike EncodeVarInt, this is a 'dumb' implementation of a variable int 50 // encoder. It writes, little-endian', until there are no more '1' bits in the 51 // number. The Decoder must know how to calculate the size of the encoded int, 52 // typically by having this reside at the end of the value or key. 53 CONTENT_EXPORT void EncodeInt(int64_t value, std::string* into); 54 CONTENT_EXPORT void EncodeString(const base::string16& value, 55 std::string* into); 56 CONTENT_EXPORT void EncodeStringWithLength(const base::string16& value, 57 std::string* into); 58 CONTENT_EXPORT void EncodeBinary(const std::string& value, std::string* into); 59 CONTENT_EXPORT void EncodeBinary(base::span<const uint8_t> value, 60 std::string* into); 61 CONTENT_EXPORT void EncodeDouble(double value, std::string* into); 62 CONTENT_EXPORT void EncodeIDBKey(const blink::IndexedDBKey& value, 63 std::string* into); 64 CONTENT_EXPORT void EncodeIDBKeyPath(const blink::IndexedDBKeyPath& value, 65 std::string* into); 66 CONTENT_EXPORT void EncodeBlobJournal(const BlobJournalType& journal, 67 std::string* into); 68 69 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeByte(base::StringPiece* slice, 70 unsigned char* value); 71 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeBool(base::StringPiece* slice, 72 bool* value); 73 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeInt(base::StringPiece* slice, 74 int64_t* value); 75 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeString(base::StringPiece* slice, 76 base::string16* value); 77 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeStringWithLength( 78 base::StringPiece* slice, 79 base::string16* value); 80 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeBinary(base::StringPiece* slice, 81 std::string* value); 82 // The returned span is only valid as long as the date behind |slice| is 83 // still valid. 84 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeBinary( 85 base::StringPiece* slice, 86 base::span<const uint8_t>* value); 87 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeDouble(base::StringPiece* slice, 88 double* value); 89 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeIDBKey( 90 base::StringPiece* slice, 91 std::unique_ptr<blink::IndexedDBKey>* value); 92 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeIDBKeyPath( 93 base::StringPiece* slice, 94 blink::IndexedDBKeyPath* value); 95 CONTENT_EXPORT WARN_UNUSED_RESULT bool DecodeBlobJournal( 96 base::StringPiece* slice, 97 BlobJournalType* journal); 98 99 CONTENT_EXPORT int CompareEncodedStringsWithLength(base::StringPiece* slice1, 100 base::StringPiece* slice2, 101 bool* ok); 102 103 CONTENT_EXPORT WARN_UNUSED_RESULT bool ExtractEncodedIDBKey( 104 base::StringPiece* slice, 105 std::string* result); 106 107 CONTENT_EXPORT int CompareEncodedIDBKeys(base::StringPiece* slice1, 108 base::StringPiece* slice2, 109 bool* ok); 110 111 CONTENT_EXPORT int Compare(const base::StringPiece& a, 112 const base::StringPiece& b, 113 bool index_keys); 114 115 CONTENT_EXPORT int CompareKeys(const base::StringPiece& a, 116 const base::StringPiece& b); 117 118 CONTENT_EXPORT int CompareIndexKeys(const base::StringPiece& a, 119 const base::StringPiece& b); 120 121 // Logging support. 122 std::string IndexedDBKeyToDebugString(base::StringPiece key); 123 124 const constexpr int kDatabaseRangeLockLevel = 0; 125 const constexpr int kObjectStoreRangeLockLevel = 1; 126 const constexpr int kIndexedDBLockLevelCount = 2; 127 128 CONTENT_EXPORT ScopeLockRange GetDatabaseLockRange(int64_t database_id); 129 CONTENT_EXPORT ScopeLockRange GetObjectStoreLockRange(int64_t database_id, 130 int64_t object_store_id); 131 132 // TODO(dmurph): Modify all decoding methods to return something more sensible, 133 // as it is not obvious that they modify the input slice to remove the decoded 134 // bit. https://crbug.com/922225 135 class KeyPrefix { 136 public: 137 // These are serialized to disk; any new items must be appended, and none can 138 // be deleted. 139 enum Type { 140 GLOBAL_METADATA = 0, 141 DATABASE_METADATA = 1, 142 OBJECT_STORE_DATA = 2, 143 EXISTS_ENTRY = 3, 144 INDEX_DATA = 4, 145 INVALID_TYPE = 5, 146 BLOB_ENTRY = 6 147 }; 148 149 static const size_t kMaxDatabaseIdSizeBits = 3; 150 static const size_t kMaxObjectStoreIdSizeBits = 3; 151 static const size_t kMaxIndexIdSizeBits = 2; 152 153 static const size_t kMaxDatabaseIdSizeBytes = 154 1ULL << kMaxDatabaseIdSizeBits; // 8 155 static const size_t kMaxObjectStoreIdSizeBytes = 156 1ULL << kMaxObjectStoreIdSizeBits; // 8 157 static const size_t kMaxIndexIdSizeBytes = 1ULL << kMaxIndexIdSizeBits; // 4 158 159 static const size_t kMaxDatabaseIdBits = 160 kMaxDatabaseIdSizeBytes * 8 - 1; // 63 161 static const size_t kMaxObjectStoreIdBits = 162 kMaxObjectStoreIdSizeBytes * 8 - 1; // 63 163 static const size_t kMaxIndexIdBits = kMaxIndexIdSizeBytes * 8 - 1; // 31 164 165 static const int64_t kMaxDatabaseId = 166 (1ULL << kMaxDatabaseIdBits) - 1; // max signed int64_t 167 static const int64_t kMaxObjectStoreId = 168 (1ULL << kMaxObjectStoreIdBits) - 1; // max signed int64_t 169 static const int64_t kMaxIndexId = 170 (1ULL << kMaxIndexIdBits) - 1; // max signed int32_t 171 172 static const int64_t kInvalidId = -1; 173 174 KeyPrefix(); 175 explicit KeyPrefix(int64_t database_id); 176 KeyPrefix(int64_t database_id, int64_t object_store_id); 177 KeyPrefix(int64_t database_id, int64_t object_store_id, int64_t index_id); 178 static KeyPrefix CreateWithSpecialIndex(int64_t database_id, 179 int64_t object_store_id, 180 int64_t index_id); 181 182 static bool Decode(base::StringPiece* slice, KeyPrefix* result); 183 std::string Encode() const; 184 static std::string EncodeEmpty(); 185 int Compare(const KeyPrefix& other) const; 186 187 CONTENT_EXPORT static bool IsValidDatabaseId(int64_t database_id); 188 static bool IsValidObjectStoreId(int64_t index_id); 189 static bool IsValidIndexId(int64_t index_id); ValidIds(int64_t database_id,int64_t object_store_id,int64_t index_id)190 static bool ValidIds(int64_t database_id, 191 int64_t object_store_id, 192 int64_t index_id) { 193 return IsValidDatabaseId(database_id) && 194 IsValidObjectStoreId(object_store_id) && IsValidIndexId(index_id); 195 } ValidIds(int64_t database_id,int64_t object_store_id)196 static bool ValidIds(int64_t database_id, int64_t object_store_id) { 197 return IsValidDatabaseId(database_id) && 198 IsValidObjectStoreId(object_store_id); 199 } 200 201 std::string DebugString(); 202 203 Type type() const; 204 205 int64_t database_id_; 206 int64_t object_store_id_; 207 int64_t index_id_; 208 209 private: 210 // Special constructor for CreateWithSpecialIndex() 211 KeyPrefix(enum Type, 212 int64_t database_id, 213 int64_t object_store_id, 214 int64_t index_id); 215 216 static std::string EncodeInternal(int64_t database_id, 217 int64_t object_store_id, 218 int64_t index_id); 219 }; 220 221 class SchemaVersionKey { 222 public: 223 CONTENT_EXPORT static std::string Encode(); 224 }; 225 226 class MaxDatabaseIdKey { 227 public: 228 CONTENT_EXPORT static std::string Encode(); 229 }; 230 231 class DataVersionKey { 232 public: 233 CONTENT_EXPORT static std::string Encode(); 234 }; 235 236 class RecoveryBlobJournalKey { 237 public: 238 static std::string Encode(); 239 }; 240 241 class ActiveBlobJournalKey { 242 public: 243 static std::string Encode(); 244 }; 245 246 class EarliestSweepKey { 247 public: 248 static std::string Encode(); 249 }; 250 251 class ScopesPrefix { 252 public: 253 CONTENT_EXPORT static std::vector<uint8_t> Encode(); 254 }; 255 256 class DatabaseFreeListKey { 257 public: 258 DatabaseFreeListKey(); 259 static bool Decode(base::StringPiece* slice, DatabaseFreeListKey* result); 260 CONTENT_EXPORT static std::string Encode(int64_t database_id); 261 static CONTENT_EXPORT std::string EncodeMaxKey(); 262 int64_t DatabaseId() const; 263 int Compare(const DatabaseFreeListKey& other) const; 264 std::string DebugString() const; 265 266 private: 267 int64_t database_id_; 268 }; 269 270 class DatabaseNameKey { 271 public: 272 static bool Decode(base::StringPiece* slice, DatabaseNameKey* result); 273 CONTENT_EXPORT static std::string Encode(const std::string& origin_identifier, 274 const base::string16& database_name); 275 static std::string EncodeMinKeyForOrigin( 276 const std::string& origin_identifier); 277 static std::string EncodeStopKeyForOrigin( 278 const std::string& origin_identifier); origin()279 base::string16 origin() const { return origin_; } database_name()280 base::string16 database_name() const { return database_name_; } 281 int Compare(const DatabaseNameKey& other); 282 std::string DebugString() const; 283 284 private: 285 base::string16 origin_; // TODO(jsbell): Store encoded strings, or just 286 // pointers. 287 base::string16 database_name_; 288 }; 289 290 class DatabaseMetaDataKey { 291 public: 292 enum MetaDataType { 293 ORIGIN_NAME = 0, 294 DATABASE_NAME = 1, 295 USER_STRING_VERSION = 2, // Obsolete 296 MAX_OBJECT_STORE_ID = 3, 297 USER_VERSION = 4, 298 BLOB_KEY_GENERATOR_CURRENT_NUMBER = 5, 299 MAX_SIMPLE_METADATA_TYPE = 6 300 }; 301 302 CONTENT_EXPORT static const int64_t kAllBlobsNumber; 303 static const int64_t kBlobNumberGeneratorInitialNumber; 304 // All keys <= 0 are invalid. This one's just a convenient example. 305 static const int64_t kInvalidBlobNumber; 306 307 CONTENT_EXPORT static bool IsValidBlobNumber(int64_t blob_number); 308 CONTENT_EXPORT static std::string Encode(int64_t database_id, 309 MetaDataType type); 310 }; 311 312 class ObjectStoreMetaDataKey { 313 public: 314 enum MetaDataType { 315 NAME = 0, 316 KEY_PATH = 1, 317 AUTO_INCREMENT = 2, 318 EVICTABLE = 3, 319 LAST_VERSION = 4, 320 MAX_INDEX_ID = 5, 321 HAS_KEY_PATH = 6, 322 KEY_GENERATOR_CURRENT_NUMBER = 7 323 }; 324 325 // From the IndexedDB specification. 326 static const int64_t kKeyGeneratorInitialNumber; 327 328 ObjectStoreMetaDataKey(); 329 static bool Decode(base::StringPiece* slice, ObjectStoreMetaDataKey* result); 330 CONTENT_EXPORT static std::string Encode(int64_t database_id, 331 int64_t object_store_id, 332 unsigned char meta_data_type); 333 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id); 334 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id, 335 int64_t object_store_id); 336 int64_t ObjectStoreId() const; 337 unsigned char MetaDataType() const; 338 int Compare(const ObjectStoreMetaDataKey& other); 339 std::string DebugString() const; 340 341 private: 342 int64_t object_store_id_; 343 unsigned char meta_data_type_; 344 }; 345 346 class IndexMetaDataKey { 347 public: 348 enum MetaDataType { 349 NAME = 0, 350 UNIQUE = 1, 351 KEY_PATH = 2, 352 MULTI_ENTRY = 3 353 }; 354 355 IndexMetaDataKey(); 356 static bool Decode(base::StringPiece* slice, IndexMetaDataKey* result); 357 CONTENT_EXPORT static std::string Encode(int64_t database_id, 358 int64_t object_store_id, 359 int64_t index_id, 360 unsigned char meta_data_type); 361 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id, 362 int64_t object_store_id); 363 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id, 364 int64_t object_store_id, 365 int64_t index_id); 366 int Compare(const IndexMetaDataKey& other); 367 std::string DebugString() const; 368 369 int64_t IndexId() const; meta_data_type()370 unsigned char meta_data_type() const { return meta_data_type_; } 371 372 private: 373 int64_t object_store_id_; 374 int64_t index_id_; 375 unsigned char meta_data_type_; 376 }; 377 378 class ObjectStoreFreeListKey { 379 public: 380 ObjectStoreFreeListKey(); 381 static bool Decode(base::StringPiece* slice, ObjectStoreFreeListKey* result); 382 CONTENT_EXPORT static std::string Encode(int64_t database_id, 383 int64_t object_store_id); 384 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id); 385 int64_t ObjectStoreId() const; 386 int Compare(const ObjectStoreFreeListKey& other); 387 std::string DebugString() const; 388 389 private: 390 int64_t object_store_id_; 391 }; 392 393 class IndexFreeListKey { 394 public: 395 IndexFreeListKey(); 396 static bool Decode(base::StringPiece* slice, IndexFreeListKey* result); 397 CONTENT_EXPORT static std::string Encode(int64_t database_id, 398 int64_t object_store_id, 399 int64_t index_id); 400 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id, 401 int64_t object_store_id); 402 int Compare(const IndexFreeListKey& other); 403 int64_t ObjectStoreId() const; 404 int64_t IndexId() const; 405 std::string DebugString() const; 406 407 private: 408 int64_t object_store_id_; 409 int64_t index_id_; 410 }; 411 412 class ObjectStoreNamesKey { 413 public: 414 // TODO(jsbell): We never use this to look up object store ids, 415 // because a mapping is kept in the IndexedDBDatabase. Can the 416 // mapping become unreliable? Can we remove this? 417 static bool Decode(base::StringPiece* slice, ObjectStoreNamesKey* result); 418 CONTENT_EXPORT static std::string Encode( 419 int64_t database_id, 420 const base::string16& object_store_name); 421 int Compare(const ObjectStoreNamesKey& other); 422 std::string DebugString() const; 423 object_store_name()424 base::string16 object_store_name() const { return object_store_name_; } 425 426 private: 427 // TODO(jsbell): Store the encoded string, or just pointers to it. 428 base::string16 object_store_name_; 429 }; 430 431 class IndexNamesKey { 432 public: 433 IndexNamesKey(); 434 // TODO(jsbell): We never use this to look up index ids, because a mapping 435 // is kept at a higher level. 436 static bool Decode(base::StringPiece* slice, IndexNamesKey* result); 437 CONTENT_EXPORT static std::string Encode(int64_t database_id, 438 int64_t object_store_id, 439 const base::string16& index_name); 440 int Compare(const IndexNamesKey& other); 441 std::string DebugString() const; 442 index_name()443 base::string16 index_name() const { return index_name_; } 444 445 private: 446 int64_t object_store_id_; 447 base::string16 index_name_; 448 }; 449 450 class ObjectStoreDataKey { 451 public: 452 static const int64_t kSpecialIndexNumber; 453 454 ObjectStoreDataKey(); 455 ~ObjectStoreDataKey(); 456 457 static bool Decode(base::StringPiece* slice, ObjectStoreDataKey* result); 458 CONTENT_EXPORT static std::string Encode(int64_t database_id, 459 int64_t object_store_id, 460 const std::string encoded_user_key); 461 CONTENT_EXPORT static std::string Encode(int64_t database_id, 462 int64_t object_store_id, 463 const blink::IndexedDBKey& user_key); 464 std::string DebugString() const; 465 466 std::unique_ptr<blink::IndexedDBKey> user_key() const; 467 468 private: 469 std::string encoded_user_key_; 470 }; 471 472 class ExistsEntryKey { 473 public: 474 ExistsEntryKey(); 475 ~ExistsEntryKey(); 476 477 static bool Decode(base::StringPiece* slice, ExistsEntryKey* result); 478 CONTENT_EXPORT static std::string Encode(int64_t database_id, 479 int64_t object_store_id, 480 const std::string& encoded_key); 481 static std::string Encode(int64_t database_id, 482 int64_t object_store_id, 483 const blink::IndexedDBKey& user_key); 484 std::string DebugString() const; 485 486 std::unique_ptr<blink::IndexedDBKey> user_key() const; 487 488 private: 489 static const int64_t kSpecialIndexNumber; 490 491 std::string encoded_user_key_; 492 DISALLOW_COPY_AND_ASSIGN(ExistsEntryKey); 493 }; 494 495 class CONTENT_EXPORT BlobEntryKey { 496 public: BlobEntryKey()497 BlobEntryKey() : database_id_(0), object_store_id_(0) {} 498 static bool Decode(base::StringPiece* slice, BlobEntryKey* result); 499 static bool FromObjectStoreDataKey(base::StringPiece* slice, 500 BlobEntryKey* result); 501 static std::string ReencodeToObjectStoreDataKey(base::StringPiece* slice); 502 static std::string EncodeMinKeyForObjectStore(int64_t database_id, 503 int64_t object_store_id); 504 static std::string EncodeStopKeyForObjectStore(int64_t database_id, 505 int64_t object_store_id); 506 static std::string Encode(int64_t database_id, 507 int64_t object_store_id, 508 const blink::IndexedDBKey& user_key); 509 std::string Encode() const; 510 std::string DebugString() const; 511 database_id()512 int64_t database_id() const { return database_id_; } object_store_id()513 int64_t object_store_id() const { return object_store_id_; } 514 515 private: 516 static const int64_t kSpecialIndexNumber; 517 518 static std::string Encode(int64_t database_id, 519 int64_t object_store_id, 520 const std::string& encoded_user_key); 521 int64_t database_id_; 522 int64_t object_store_id_; 523 // This is the user's ObjectStoreDataKey, not the BlobEntryKey itself. 524 std::string encoded_user_key_; 525 }; 526 527 class IndexDataKey { 528 public: 529 CONTENT_EXPORT IndexDataKey(); 530 CONTENT_EXPORT IndexDataKey(IndexDataKey&& other); 531 CONTENT_EXPORT ~IndexDataKey(); 532 CONTENT_EXPORT static bool Decode(base::StringPiece* slice, 533 IndexDataKey* result); 534 CONTENT_EXPORT static std::string Encode( 535 int64_t database_id, 536 int64_t object_store_id, 537 int64_t index_id, 538 const std::string& encoded_user_key, 539 const std::string& encoded_primary_key, 540 int64_t sequence_number); 541 static std::string Encode(int64_t database_id, 542 int64_t object_store_id, 543 int64_t index_id, 544 const blink::IndexedDBKey& user_key); 545 CONTENT_EXPORT static std::string Encode( 546 int64_t database_id, 547 int64_t object_store_id, 548 int64_t index_id, 549 const blink::IndexedDBKey& user_key, 550 const blink::IndexedDBKey& user_primary_key); 551 CONTENT_EXPORT static std::string EncodeMinKey(int64_t database_id, 552 int64_t object_store_id, 553 int64_t index_id); 554 555 // An index's keys are guaranteed to fall in [EncodeMinKey(), EncodeMaxKey()] 556 CONTENT_EXPORT static std::string EncodeMaxKey(int64_t database_id, 557 int64_t object_store_id, 558 int64_t index_id); 559 int64_t DatabaseId() const; 560 int64_t ObjectStoreId() const; 561 int64_t IndexId() const; 562 std::unique_ptr<blink::IndexedDBKey> user_key() const; 563 std::unique_ptr<blink::IndexedDBKey> primary_key() const; 564 565 CONTENT_EXPORT std::string Encode() const; 566 567 std::string DebugString() const; 568 569 private: 570 int64_t database_id_; 571 int64_t object_store_id_; 572 int64_t index_id_; 573 std::string encoded_user_key_; 574 std::string encoded_primary_key_; 575 int64_t sequence_number_; 576 577 DISALLOW_COPY_AND_ASSIGN(IndexDataKey); 578 }; 579 580 } // namespace content 581 582 #endif // CONTENT_BROWSER_INDEXED_DB_INDEXED_DB_LEVELDB_CODING_H_ 583