iOS/Pods/Realm/include/core/realm/sync/object_id.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2017 Realm Inc.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  **************************************************************************/
  18
  19 #ifndef REALM_SYNC_OBJECT_ID_HPP
  20 #define REALM_SYNC_OBJECT_ID_HPP
  21
  22 #include <functional> // std::hash
  23 #include <string>
  24 #include <iosfwd> // operator<<
  25 #include <map>
  26 #include <set>
  27
  28 #include <stdint.h>
  29
  30 #include <realm/util/optional.hpp>
  31 #include <realm/string_data.hpp>
  32 #include <realm/data_type.hpp>
  33
  34 // Only set this to one when testing the code paths that exercise object ID
  35 // hash collisions. It artificially limits the "optimistic" local ID to use
  36 // only the lower 15 bits of the ID rather than the lower 63 bits, making it
  37 // feasible to generate collisions within reasonable time.
  38 #define REALM_EXERCISE_OBJECT_ID_COLLISION 0
  39
  40 namespace realm {
  41
  42 class Group;
  43
  44 namespace sync {
  45
  46 /// ObjectIDs are globally unique, and up to 128 bits wide. They are represented
  47 /// as two 64-bit integers, each of which may frequently be small, for best
  48 /// on-wire compressibility.
  49 struct ObjectID {
  50     constexpr ObjectID(uint64_t hi, uint64_t lo);
  51     static ObjectID from_string(StringData);
  52
  53     // FIXME: Remove "empty" ObjectIDs, wrap in Optional instead.
  54     constexpr ObjectID(realm::util::None = realm::util::none);
  55     constexpr ObjectID(const ObjectID&) noexcept = default;
  56     ObjectID& operator=(const ObjectID&) noexcept = default;
  57
  58     constexpr uint64_t lo() const { return m_lo; }
  59     constexpr uint64_t hi() const { return m_hi; }
  60
  61     std::string to_string() const;
  62
  63     constexpr bool operator<(const ObjectID& other) const;
  64     constexpr bool operator==(const ObjectID& other) const;
  65     constexpr bool operator!=(const ObjectID& other) const;
  66
  67 private:
  68     uint64_t m_lo;
  69     uint64_t m_hi;
  70 };
  71
  72 /// Implementors of this interface should define a way to map from 128-bit
  73 /// on-write ObjectIDs to local 64-bit object IDs.
  74 ///
  75 /// The three object ID types are:
  76 /// a. Object IDs for objects in tables without primary keys.
  77 /// b. Object IDs for objects in tables with integer primary keys.
  78 /// c. Object IDs for objects in tables with other primary key types.
  79 ///
  80 /// For integer primary keys (b), the Object ID is just the integer value.
  81 ///
  82 /// For objects without primary keys (a), a "squeezed" tuple of the
  83 /// client_file_ident and a peer-local sequence number is used as the local
  84 /// Object ID. The on-write Object ID is the "unsqueezed" format. The methods on
  85 /// this interface ending in "_squeezed" aid in the creation and conversion of
  86 /// these IDs.
  87 ///
  88 /// For objects with other types of primary keys (c), the ObjectID
  89 /// is a 128-bit hash of the primary key value. However, the local object ID
  90 /// must be a 64-bit integer, because that is the maximum size integer that
  91 /// Realm is able to store. The solution is to optimistically use the lower 63
  92 /// bits of the on-wire Object ID, and use a local ID with the upper 64th bit
  93 /// set when there is a collision in the lower 63 bits between two different
  94 /// hash values.
  95 class ObjectIDProvider {
  96 public:
  97     using LocalObjectID = int_fast64_t;
  98
  99     /// Calculate optimistic local ID that may collide with others. It is up to
 100     /// the caller to ensure that collisions are detected and that
 101     /// allocate_local_id_after_collision() is called to obtain a non-colliding
 102     /// ID.
 103     static LocalObjectID get_optimistic_local_id_hashed(ObjectID global_id);
 104
 105     /// Find the local 64-bit object ID for the provided global 128-bit ID.
 106     virtual LocalObjectID global_to_local_object_id_hashed(size_t table_ndx, ObjectID global_id) const = 0;
 107
 108     /// After a local ID collision has been detected, this function may be
 109     /// called to obtain a non-colliding local ID in such a way that subsequence
 110     /// calls to global_to_local_object_id() will return the correct local ID
 111     /// for both \a incoming_id and \a colliding_id.
 112     virtual LocalObjectID allocate_local_id_after_hash_collision(size_t table_ndx,
 113                                                                  ObjectID incoming_id,
 114                                                                  ObjectID colliding_id,
 115                                                                  LocalObjectID colliding_local_id) = 0;
 116     static LocalObjectID make_tagged_local_id_after_hash_collision(uint64_t sequence_number);
 117     virtual void free_local_id_after_hash_collision(size_t table_ndx, ObjectID object_id) = 0;
 118
 119     /// Some Object IDs are generated as a tuple of the client_file_ident and a
 120     /// local sequence number. This function takes the next number in the
 121     /// sequence for the given table and returns an appropriate globally unique
 122     /// ObjectID.
 123     virtual ObjectID allocate_object_id_squeezed(size_t table_ndx) = 0;
 124     static LocalObjectID global_to_local_object_id_squeezed(ObjectID);
 125     static ObjectID local_to_global_object_id_squeezed(LocalObjectID);
 126
 127     virtual int_fast64_t get_client_file_ident() const = 0;
 128 };
 129
 130 // ObjectIDSet is a set of (table name, object id)
 131 class ObjectIDSet {
 132 public:
 133
 134     void insert(StringData table, ObjectID object_id);
 135     void erase(StringData table, ObjectID object_id);
 136     bool contains(StringData table, ObjectID object_id) const noexcept;
 137
 138 private:
 139
 140     // A map from table name to a set of object ids.
 141     std::map<std::string, std::set<ObjectID>, std::less<>> m_objects;
 142 };
 143
 144 /// Implementation:
 145
 146
 147 constexpr ObjectID::ObjectID(uint64_t hi, uint64_t lo): m_lo(lo), m_hi(hi)
 148 {
 149 }
 150
 151 constexpr ObjectID::ObjectID(realm::util::None): m_lo(-1), m_hi(-1)
 152 {
 153 }
 154
 155 constexpr bool ObjectID::operator<(const ObjectID& other) const
 156 {
 157     return (m_hi == other.m_hi) ? (m_lo < other.m_lo) : (m_hi < other.m_hi);
 158 }
 159
 160 constexpr bool ObjectID::operator==(const ObjectID& other) const
 161 {
 162     return m_hi == other.m_hi && m_lo == other.m_lo;
 163 }
 164
 165 constexpr bool ObjectID::operator!=(const ObjectID& other) const
 166 {
 167     return !(*this == other);
 168 }
 169
 170 std::ostream& operator<<(std::ostream&, const realm::sync::ObjectID&);
 171
 172 inline ObjectIDProvider::LocalObjectID
 173 ObjectIDProvider::get_optimistic_local_id_hashed(ObjectID global_id)
 174 {
 175 #if REALM_EXERCISE_OBJECT_ID_COLLISION
 176     const uint64_t optimistic_mask = 0xff;
 177 #else
 178     const uint64_t optimistic_mask = 0x7fffffffffffffff;
 179 #endif
 180     static_assert(optimistic_mask < 0x8000000000000000, "optimistic Object ID mask must leave the 64th bit zero");
 181     return global_id.lo() & optimistic_mask;
 182 }
 183
 184 inline ObjectIDProvider::LocalObjectID
 185 ObjectIDProvider::make_tagged_local_id_after_hash_collision(uint64_t sequence_number)
 186 {
 187     REALM_ASSERT(sequence_number < 0x8000000000000000);
 188     return 0x8000000000000000 | sequence_number;
 189 }
 190
 191 inline ObjectIDProvider::LocalObjectID
 192 ObjectIDProvider::global_to_local_object_id_squeezed(ObjectID object_id)
 193 {
 194     REALM_ASSERT(object_id.hi() <= std::numeric_limits<uint32_t>::max());
 195     REALM_ASSERT(object_id.lo() <= std::numeric_limits<uint32_t>::max());
 196
 197     uint64_t a =  object_id.lo() & 0xff;
 198     uint64_t b = (object_id.hi() & 0xff) << 8;
 199     uint64_t c = (object_id.lo() & 0xffffff00) << 8;
 200     uint64_t d = (object_id.hi() & 0xffffff00) << 32;
 201     union {
 202         uint64_t u;
 203         int64_t  s;
 204     } bitcast;
 205     bitcast.u = a | b | c | d;
 206     return bitcast.s;
 207 }
 208
 209 inline ObjectID
 210 ObjectIDProvider::local_to_global_object_id_squeezed(LocalObjectID squeezed)
 211 {
 212     union {
 213         uint64_t u;
 214         int64_t  s;
 215     } bitcast;
 216     bitcast.s = squeezed;
 217
 218     uint64_t u = bitcast.u;
 219
 220     uint64_t lo = (u & 0xff) | ((u & 0xffffff0000) >> 8);
 221     uint64_t hi = ((u & 0xff00) >> 8) | ((u & 0xffffff0000000000) >> 32);
 222     return ObjectID{hi, lo};
 223 }
 224
 225 } // namespace sync
 226 } // namespace realm
 227
 228 namespace std {
 229
 230 template <>
 231 struct hash<realm::sync::ObjectID> {
 232     size_t operator()(realm::sync::ObjectID oid) const
 233     {
 234         return std::hash<uint64_t>{}(oid.lo()) ^ std::hash<uint64_t>{}(oid.hi());
 235     }
 236 };
 237
 238 } // namespace std
 239
 240 #endif // REALM_SYNC_OBJECT_ID_HPP
 241