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