IndexedDB: Protect against key prefix overflows
[WebKit-https.git] / Source / WebCore / Modules / indexeddb / IDBLevelDBCoding.h
1 /*
2  * Copyright (C) 2011 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef IDBLevelDBCoding_h
27 #define IDBLevelDBCoding_h
28
29 #if ENABLE(INDEXED_DATABASE)
30 #if USE(LEVELDB)
31
32 #include <wtf/RefPtr.h>
33 #include <wtf/Vector.h>
34 #include <wtf/text/WTFString.h>
35
36 namespace WebCore {
37
38 class IDBKey;
39 class IDBKeyPath;
40 class LevelDBSlice;
41
42 namespace IDBLevelDBCoding {
43
44 const unsigned char MinimumIndexId = 30;
45
46 // As most of the IDBKeys and encoded values are short, we initialize some Vectors with a default inline buffer size
47 // to reduce the memory re-allocations when the Vectors are appended.
48 static const size_t DefaultInlineBufferSize = 32;
49
50 Vector<char> encodeByte(unsigned char);
51 const char* decodeByte(const char* p, const char* limit, unsigned char& foundChar);
52 Vector<char> maxIDBKey();
53 Vector<char> minIDBKey();
54 Vector<char> encodeBool(bool);
55 bool decodeBool(const char* begin, const char* end);
56 Vector<char> encodeInt(int64_t);
57 inline Vector<char> encodeIntSafely(int64_t nParam, size_t max)
58 {
59     ASSERT(static_cast<size_t>(nParam) <= max);
60     return encodeInt(nParam);
61 }
62 int64_t decodeInt(const char* begin, const char* end);
63 Vector<char> encodeVarInt(int64_t);
64 const char* decodeVarInt(const char* p, const char* limit, int64_t& foundInt);
65 Vector<char> encodeString(const String&);
66 String decodeString(const char* p, const char* end);
67 Vector<char> encodeStringWithLength(const String&);
68 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString);
69 int compareEncodedStringsWithLength(const char*& p, const char* limitP, const char*& q, const char* limitQ, bool& ok);
70 Vector<char> encodeDouble(double);
71 const char* decodeDouble(const char* p, const char* limit, double*);
72 void encodeIDBKey(const IDBKey&, Vector<char, DefaultInlineBufferSize>& into);
73 Vector<char> encodeIDBKey(const IDBKey&);
74 const char* decodeIDBKey(const char* p, const char* limit, RefPtr<IDBKey>& foundKey);
75 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result);
76 int compareEncodedIDBKeys(const Vector<char>&, const Vector<char>&, bool& ok);
77 Vector<char> encodeIDBKeyPath(const IDBKeyPath&);
78 IDBKeyPath decodeIDBKeyPath(const char*, const char*);
79
80 int compare(const LevelDBSlice&, const LevelDBSlice&, bool indexKeys = false);
81
82 class KeyPrefix {
83 public:
84     KeyPrefix();
85     explicit KeyPrefix(int64_t databaseId);
86     KeyPrefix(int64_t databaseId, int64_t objectStoreId);
87     KeyPrefix(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
88     static KeyPrefix createWithSpecialIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
89
90     static const char* decode(const char* start, const char* limit, KeyPrefix* result);
91     Vector<char> encode() const;
92     static Vector<char> encodeEmpty();
93     int compare(const KeyPrefix& other) const;
94
95     enum Type {
96         GlobalMetaData,
97         DatabaseMetaData,
98         ObjectStoreData,
99         ExistsEntry,
100         IndexData,
101         InvalidType
102     };
103
104     static const size_t kMaxDatabaseIdSizeBits = 3;
105     static const size_t kMaxObjectStoreIdSizeBits = 3;
106     static const size_t kMaxIndexIdSizeBits = 2;
107
108     static const size_t kMaxDatabaseIdSizeBytes = 1UL << kMaxDatabaseIdSizeBits; // 8
109     static const size_t kMaxObjectStoreIdSizeBytes = 1UL << kMaxObjectStoreIdSizeBits; // 8
110     static const size_t kMaxIndexIdSizeBytes = 1UL << kMaxIndexIdSizeBits; // 4
111
112     static const size_t kMaxDatabaseIdBits = kMaxDatabaseIdSizeBytes * 8 - 1; // 63
113     static const size_t kMaxObjectStoreIdBits = kMaxObjectStoreIdSizeBytes * 8 - 1; // 63
114     static const size_t kMaxIndexIdBits = kMaxIndexIdSizeBytes * 8 - 1; // 31
115
116     static const int64_t kMaxDatabaseId = (1UL << kMaxDatabaseIdBits) - 1; // max signed int64_t
117     static const int64_t kMaxObjectStoreId = (1UL << kMaxObjectStoreIdBits) - 1; // max signed int64_t
118     static const int64_t kMaxIndexId = (1UL << kMaxIndexIdBits) - 1; // max signed int32_t
119
120     static bool isValidDatabaseId(int64_t databaseId);
121     static bool isValidObjectStoreId(int64_t indexId);
122     static bool isValidIndexId(int64_t indexId);
123     static bool validIds(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
124     {
125         return isValidDatabaseId(databaseId) && isValidObjectStoreId(objectStoreId) && isValidIndexId(indexId);
126     }
127     static bool validIds(int64_t databaseId, int64_t objectStoreId)
128     {
129         return isValidDatabaseId(databaseId) && isValidObjectStoreId(objectStoreId);
130     }
131
132     Type type() const;
133
134     int64_t m_databaseId;
135     int64_t m_objectStoreId;
136     int64_t m_indexId;
137
138     static const int64_t InvalidId = -1;
139
140 private:
141     static Vector<char> encodeInternal(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
142     // Special constructor for createWithSpecialIndex()
143     KeyPrefix(Type, int64_t databaseId, int64_t objectStoreId, int64_t indexId);
144 };
145
146 class SchemaVersionKey {
147 public:
148     static Vector<char> encode();
149 };
150
151 class MaxDatabaseIdKey {
152 public:
153     static Vector<char> encode();
154 };
155
156 class DataVersionKey {
157 public:
158     static Vector<char> encode();
159 };
160
161 class DatabaseFreeListKey {
162 public:
163     DatabaseFreeListKey();
164     static const char* decode(const char* start, const char* limit, DatabaseFreeListKey* result);
165     static Vector<char> encode(int64_t databaseId);
166     static Vector<char> encodeMaxKey();
167     int64_t databaseId() const;
168     int compare(const DatabaseFreeListKey& other) const;
169
170 private:
171     int64_t m_databaseId;
172 };
173
174 class DatabaseNameKey {
175 public:
176     static const char* decode(const char* start, const char* limit, DatabaseNameKey* result);
177     static Vector<char> encode(const String& origin, const String& databaseName);
178     static Vector<char> encodeMinKeyForOrigin(const String& origin);
179     static Vector<char> encodeStopKeyForOrigin(const String& origin);
180     String origin() const { return m_origin; }
181     String databaseName() const { return m_databaseName; }
182     int compare(const DatabaseNameKey& other);
183
184 private:
185     String m_origin; // FIXME: Store encoded strings, or just pointers.
186     String m_databaseName;
187 };
188
189 class DatabaseMetaDataKey {
190 public:
191     enum MetaDataType {
192         OriginName = 0,
193         DatabaseName = 1,
194         UserVersion = 2,
195         MaxObjectStoreId = 3,
196         UserIntVersion = 4,
197         MaxSimpleMetaDataType = 5
198     };
199
200     static Vector<char> encode(int64_t databaseId, MetaDataType);
201 };
202
203 class ObjectStoreMetaDataKey {
204 public:
205     enum MetaDataType {
206         Name = 0,
207         KeyPath = 1,
208         AutoIncrement = 2,
209         Evictable = 3,
210         LastVersion = 4,
211         MaxIndexId = 5,
212         HasKeyPath = 6,
213         KeyGeneratorCurrentNumber = 7
214     };
215
216     ObjectStoreMetaDataKey();
217     static const char* decode(const char* start, const char* limit, ObjectStoreMetaDataKey* result);
218     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, unsigned char metaDataType);
219     static Vector<char> encodeMaxKey(int64_t databaseId);
220     static Vector<char> encodeMaxKey(int64_t databaseId, int64_t objectStoreId);
221     int64_t objectStoreId() const;
222     unsigned char metaDataType() const;
223     int compare(const ObjectStoreMetaDataKey& other);
224
225 private:
226     int64_t m_objectStoreId;
227     unsigned char m_metaDataType;
228 };
229
230 class IndexMetaDataKey {
231 public:
232     enum MetaDataType {
233         Name = 0,
234         Unique = 1,
235         KeyPath = 2,
236         MultiEntry = 3
237     };
238
239     IndexMetaDataKey();
240     static const char* decode(const char* start, const char* limit, IndexMetaDataKey* result);
241     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, unsigned char metaDataType);
242     static Vector<char> encodeMaxKey(int64_t databaseId, int64_t objectStoreId);
243     static Vector<char> encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
244     int compare(const IndexMetaDataKey& other);
245     int64_t indexId() const;
246     unsigned char metaDataType() const { return m_metaDataType; }
247
248 private:
249     int64_t m_objectStoreId;
250     int64_t m_indexId;
251     unsigned char m_metaDataType;
252 };
253
254 class ObjectStoreFreeListKey {
255 public:
256     ObjectStoreFreeListKey();
257     static const char* decode(const char* start, const char* limit, ObjectStoreFreeListKey* result);
258     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId);
259     static Vector<char> encodeMaxKey(int64_t databaseId);
260     int64_t objectStoreId() const;
261     int compare(const ObjectStoreFreeListKey& other);
262
263 private:
264     int64_t m_objectStoreId;
265 };
266
267 class IndexFreeListKey {
268 public:
269     IndexFreeListKey();
270     static const char* decode(const char* start, const char* limit, IndexFreeListKey* result);
271     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
272     static Vector<char> encodeMaxKey(int64_t databaseId, int64_t objectStoreId);
273     int compare(const IndexFreeListKey& other);
274     int64_t objectStoreId() const;
275     int64_t indexId() const;
276
277 private:
278     int64_t m_objectStoreId;
279     int64_t m_indexId;
280 };
281
282 class ObjectStoreNamesKey {
283 public:
284     // FIXME: We never use this to look up object store ids, because a mapping
285     // is kept in the IDBDatabaseBackendImpl. Can the mapping become unreliable?
286     // Can we remove this?
287     static const char* decode(const char* start, const char* limit, ObjectStoreNamesKey* result);
288     static Vector<char> encode(int64_t databaseId, const String& objectStoreName);
289     int compare(const ObjectStoreNamesKey& other);
290     String objectStoreName() const { return m_objectStoreName; }
291
292 private:
293     String m_objectStoreName; // FIXME: Store the encoded string, or just pointers to it.
294 };
295
296 class IndexNamesKey {
297 public:
298     IndexNamesKey();
299     // FIXME: We never use this to look up index ids, because a mapping
300     // is kept at a higher level.
301     static const char* decode(const char* start, const char* limit, IndexNamesKey* result);
302     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, const String& indexName);
303     int compare(const IndexNamesKey& other);
304     String indexName() const { return m_indexName; }
305
306 private:
307     int64_t m_objectStoreId;
308     String m_indexName;
309 };
310
311 class ObjectStoreDataKey {
312 public:
313     static const char* decode(const char* start, const char* end, ObjectStoreDataKey* result);
314     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, const Vector<char> encodedUserKey);
315     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey);
316     int compare(const ObjectStoreDataKey& other, bool& ok);
317     PassRefPtr<IDBKey> userKey() const;
318     static const int64_t SpecialIndexNumber;
319
320 private:
321     Vector<char> m_encodedUserKey;
322 };
323
324 class ExistsEntryKey {
325 public:
326     static const char* decode(const char* start, const char* end, ExistsEntryKey* result);
327     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, const Vector<char>& encodedKey);
328     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey);
329     int compare(const ExistsEntryKey& other, bool& ok);
330     PassRefPtr<IDBKey> userKey() const;
331
332     static const int64_t SpecialIndexNumber;
333
334 private:
335     Vector<char> m_encodedUserKey;
336 };
337
338 class IndexDataKey {
339 public:
340     IndexDataKey();
341     static const char* decode(const char* start, const char* limit, IndexDataKey* result);
342     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const Vector<char>& encodedUserKey, const Vector<char>& encodedPrimaryKey, int64_t sequenceNumber = 0);
343     static Vector<char> encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& userKey);
344     static Vector<char> encodeMinKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
345     static Vector<char> encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId);
346     int compare(const IndexDataKey& other, bool ignoreDuplicates, bool& ok);
347     int64_t databaseId() const;
348     int64_t objectStoreId() const;
349     int64_t indexId() const;
350     PassRefPtr<IDBKey> userKey() const;
351     PassRefPtr<IDBKey> primaryKey() const;
352
353 private:
354     int64_t m_databaseId;
355     int64_t m_objectStoreId;
356     int64_t m_indexId;
357     Vector<char> m_encodedUserKey;
358     Vector<char> m_encodedPrimaryKey;
359     int64_t m_sequenceNumber;
360 };
361
362 } // namespace IDBLevelDBCoding
363
364 } // namespace WebCore
365
366 #endif // USE(LEVELDB)
367 #endif // ENABLE(INDEXED_DATABASE)
368
369 #endif // IDBLevelDBCoding_h