third_party/upb/upb/msg.c

   1 /*
   2  * Copyright (c) 2009-2021, Google LLC
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of Google LLC nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "upb/msg.h"
  29
  30 #include "upb/msg_internal.h"
  31 #include "upb/port_def.inc"
  32 #include "upb/table_internal.h"
  33
  34 /** upb_msg *******************************************************************/
  35
  36 static const size_t overhead = sizeof(upb_msg_internaldata);
  37
  38 static const upb_msg_internal *upb_msg_getinternal_const(const upb_msg *msg) {
  39   ptrdiff_t size = sizeof(upb_msg_internal);
  40   return (upb_msg_internal*)((char*)msg - size);
  41 }
  42
  43 upb_msg *_upb_msg_new(const upb_msglayout *l, upb_arena *a) {
  44   return _upb_msg_new_inl(l, a);
  45 }
  46
  47 void _upb_msg_clear(upb_msg *msg, const upb_msglayout *l) {
  48   void *mem = UPB_PTR_AT(msg, -sizeof(upb_msg_internal), char);
  49   memset(mem, 0, upb_msg_sizeof(l));
  50 }
  51
  52 static bool realloc_internal(upb_msg *msg, size_t need, upb_arena *arena) {
  53   upb_msg_internal *in = upb_msg_getinternal(msg);
  54   if (!in->internal) {
  55     /* No internal data, allocate from scratch. */
  56     size_t size = UPB_MAX(128, _upb_lg2ceilsize(need + overhead));
  57     upb_msg_internaldata *internal = upb_arena_malloc(arena, size);
  58     if (!internal) return false;
  59     internal->size = size;
  60     internal->unknown_end = overhead;
  61     internal->ext_begin = size;
  62     in->internal = internal;
  63   } else if (in->internal->ext_begin - in->internal->unknown_end < need) {
  64     /* Internal data is too small, reallocate. */
  65     size_t new_size = _upb_lg2ceilsize(in->internal->size + need);
  66     size_t ext_bytes = in->internal->size - in->internal->ext_begin;
  67     size_t new_ext_begin = new_size - ext_bytes;
  68     upb_msg_internaldata *internal =
  69         upb_arena_realloc(arena, in->internal, in->internal->size, new_size);
  70     if (!internal) return false;
  71     if (ext_bytes) {
  72       /* Need to move extension data to the end. */
  73       char *ptr = (char*)internal;
  74       memmove(ptr + new_ext_begin, ptr + internal->ext_begin, ext_bytes);
  75     }
  76     internal->ext_begin = new_ext_begin;
  77     internal->size = new_size;
  78     in->internal = internal;
  79   }
  80   UPB_ASSERT(in->internal->ext_begin - in->internal->unknown_end >= need);
  81   return true;
  82 }
  83
  84 bool _upb_msg_addunknown(upb_msg *msg, const char *data, size_t len,
  85                          upb_arena *arena) {
  86   if (!realloc_internal(msg, len, arena)) return false;
  87   upb_msg_internal *in = upb_msg_getinternal(msg);
  88   memcpy(UPB_PTR_AT(in->internal, in->internal->unknown_end, char), data, len);
  89   in->internal->unknown_end += len;
  90   return true;
  91 }
  92
  93 void _upb_msg_discardunknown_shallow(upb_msg *msg) {
  94   upb_msg_internal *in = upb_msg_getinternal(msg);
  95   if (in->internal) {
  96     in->internal->unknown_end = overhead;
  97   }
  98 }
  99
 100 const char *upb_msg_getunknown(const upb_msg *msg, size_t *len) {
 101   const upb_msg_internal *in = upb_msg_getinternal_const(msg);
 102   if (in->internal) {
 103     *len = in->internal->unknown_end - overhead;
 104     return (char*)(in->internal + 1);
 105   } else {
 106     *len = 0;
 107     return NULL;
 108   }
 109 }
 110
 111 const upb_msg_ext *_upb_msg_getexts(const upb_msg *msg, size_t *count) {
 112   const upb_msg_internal *in = upb_msg_getinternal_const(msg);
 113   if (in->internal) {
 114     *count =
 115         (in->internal->size - in->internal->ext_begin) / sizeof(upb_msg_ext);
 116     return UPB_PTR_AT(in->internal, in->internal->ext_begin, void);
 117   } else {
 118     *count = 0;
 119     return NULL;
 120   }
 121 }
 122
 123 const upb_msg_ext *_upb_msg_getext(const upb_msg *msg,
 124                                    const upb_msglayout_ext *e) {
 125   size_t n;
 126   const upb_msg_ext *ext = _upb_msg_getexts(msg, &n);
 127
 128   /* For now we use linear search exclusively to find extensions. If this
 129    * becomes an issue due to messages with lots of extensions, we can introduce
 130    * a table of some sort. */
 131   for (size_t i = 0; i < n; i++) {
 132     if (ext[i].ext == e) {
 133       return &ext[i];
 134     }
 135   }
 136
 137   return NULL;
 138 }
 139
 140 upb_msg_ext *_upb_msg_getorcreateext(upb_msg *msg, const upb_msglayout_ext *e,
 141                                      upb_arena *arena) {
 142   upb_msg_ext *ext = (upb_msg_ext*)_upb_msg_getext(msg, e);
 143   if (ext) return ext;
 144   if (!realloc_internal(msg, sizeof(upb_msg_ext), arena)) return NULL;
 145   upb_msg_internal *in = upb_msg_getinternal(msg);
 146   in->internal->ext_begin -= sizeof(upb_msg_ext);
 147   ext = UPB_PTR_AT(in->internal, in->internal->ext_begin, void);
 148   memset(ext, 0, sizeof(upb_msg_ext));
 149   ext->ext = e;
 150   return ext;
 151 }
 152
 153 /** upb_array *****************************************************************/
 154
 155 bool _upb_array_realloc(upb_array *arr, size_t min_size, upb_arena *arena) {
 156   size_t new_size = UPB_MAX(arr->size, 4);
 157   int elem_size_lg2 = arr->data & 7;
 158   size_t old_bytes = arr->size << elem_size_lg2;
 159   size_t new_bytes;
 160   void* ptr = _upb_array_ptr(arr);
 161
 162   /* Log2 ceiling of size. */
 163   while (new_size < min_size) new_size *= 2;
 164
 165   new_bytes = new_size << elem_size_lg2;
 166   ptr = upb_arena_realloc(arena, ptr, old_bytes, new_bytes);
 167
 168   if (!ptr) {
 169     return false;
 170   }
 171
 172   arr->data = _upb_tag_arrptr(ptr, elem_size_lg2);
 173   arr->size = new_size;
 174   return true;
 175 }
 176
 177 static upb_array *getorcreate_array(upb_array **arr_ptr, int elem_size_lg2,
 178                                     upb_arena *arena) {
 179   upb_array *arr = *arr_ptr;
 180   if (!arr) {
 181     arr = _upb_array_new(arena, 4, elem_size_lg2);
 182     if (!arr) return NULL;
 183     *arr_ptr = arr;
 184   }
 185   return arr;
 186 }
 187
 188 void *_upb_array_resize_fallback(upb_array **arr_ptr, size_t size,
 189                                  int elem_size_lg2, upb_arena *arena) {
 190   upb_array *arr = getorcreate_array(arr_ptr, elem_size_lg2, arena);
 191   return arr && _upb_array_resize(arr, size, arena) ? _upb_array_ptr(arr)
 192                                                     : NULL;
 193 }
 194
 195 bool _upb_array_append_fallback(upb_array **arr_ptr, const void *value,
 196                                 int elem_size_lg2, upb_arena *arena) {
 197   upb_array *arr = getorcreate_array(arr_ptr, elem_size_lg2, arena);
 198   if (!arr) return false;
 199
 200   size_t elems = arr->len;
 201
 202   if (!_upb_array_resize(arr, elems + 1, arena)) {
 203     return false;
 204   }
 205
 206   char *data = _upb_array_ptr(arr);
 207   memcpy(data + (elems << elem_size_lg2), value, 1 << elem_size_lg2);
 208   return true;
 209 }
 210
 211 /** upb_map *******************************************************************/
 212
 213 upb_map *_upb_map_new(upb_arena *a, size_t key_size, size_t value_size) {
 214   upb_map *map = upb_arena_malloc(a, sizeof(upb_map));
 215
 216   if (!map) {
 217     return NULL;
 218   }
 219
 220   upb_strtable_init(&map->table, 4, a);
 221   map->key_size = key_size;
 222   map->val_size = value_size;
 223
 224   return map;
 225 }
 226
 227 static void _upb_mapsorter_getkeys(const void *_a, const void *_b, void *a_key,
 228                                    void *b_key, size_t size) {
 229   const upb_tabent *const*a = _a;
 230   const upb_tabent *const*b = _b;
 231   upb_strview a_tabkey = upb_tabstrview((*a)->key);
 232   upb_strview b_tabkey = upb_tabstrview((*b)->key);
 233   _upb_map_fromkey(a_tabkey, a_key, size);
 234   _upb_map_fromkey(b_tabkey, b_key, size);
 235 }
 236
 237 static int _upb_mapsorter_cmpi64(const void *_a, const void *_b) {
 238   int64_t a, b;
 239   _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
 240   return a - b;
 241 }
 242
 243 static int _upb_mapsorter_cmpu64(const void *_a, const void *_b) {
 244   uint64_t a, b;
 245   _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
 246   return a - b;
 247 }
 248
 249 static int _upb_mapsorter_cmpi32(const void *_a, const void *_b) {
 250   int32_t a, b;
 251   _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
 252   return a - b;
 253 }
 254
 255 static int _upb_mapsorter_cmpu32(const void *_a, const void *_b) {
 256   uint32_t a, b;
 257   _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
 258   return a - b;
 259 }
 260
 261 static int _upb_mapsorter_cmpbool(const void *_a, const void *_b) {
 262   bool a, b;
 263   _upb_mapsorter_getkeys(_a, _b, &a, &b, 1);
 264   return a - b;
 265 }
 266
 267 static int _upb_mapsorter_cmpstr(const void *_a, const void *_b) {
 268   upb_strview a, b;
 269   _upb_mapsorter_getkeys(_a, _b, &a, &b, UPB_MAPTYPE_STRING);
 270   size_t common_size = UPB_MIN(a.size, b.size);
 271   int cmp = memcmp(a.data, b.data, common_size);
 272   if (cmp) return cmp;
 273   return a.size - b.size;
 274 }
 275
 276 bool _upb_mapsorter_pushmap(_upb_mapsorter *s, upb_descriptortype_t key_type,
 277                             const upb_map *map, _upb_sortedmap *sorted) {
 278   int map_size = _upb_map_size(map);
 279   sorted->start = s->size;
 280   sorted->pos = sorted->start;
 281   sorted->end = sorted->start + map_size;
 282
 283   /* Grow s->entries if necessary. */
 284   if (sorted->end > s->cap) {
 285     s->cap = _upb_lg2ceilsize(sorted->end);
 286     s->entries = realloc(s->entries, s->cap * sizeof(*s->entries));
 287     if (!s->entries) return false;
 288   }
 289
 290   s->size = sorted->end;
 291
 292   /* Copy non-empty entries from the table to s->entries. */
 293   upb_tabent const**dst = &s->entries[sorted->start];
 294   const upb_tabent *src = map->table.t.entries;
 295   const upb_tabent *end = src + upb_table_size(&map->table.t);
 296   for (; src < end; src++) {
 297     if (!upb_tabent_isempty(src)) {
 298       *dst = src;
 299       dst++;
 300     }
 301   }
 302   UPB_ASSERT(dst == &s->entries[sorted->end]);
 303
 304   /* Sort entries according to the key type. */
 305
 306   int (*compar)(const void *, const void *);
 307
 308   switch (key_type) {
 309     case UPB_DESCRIPTOR_TYPE_INT64:
 310     case UPB_DESCRIPTOR_TYPE_SFIXED64:
 311     case UPB_DESCRIPTOR_TYPE_SINT64:
 312       compar = _upb_mapsorter_cmpi64;
 313       break;
 314     case UPB_DESCRIPTOR_TYPE_UINT64:
 315     case UPB_DESCRIPTOR_TYPE_FIXED64:
 316       compar = _upb_mapsorter_cmpu64;
 317       break;
 318     case UPB_DESCRIPTOR_TYPE_INT32:
 319     case UPB_DESCRIPTOR_TYPE_SINT32:
 320     case UPB_DESCRIPTOR_TYPE_SFIXED32:
 321     case UPB_DESCRIPTOR_TYPE_ENUM:
 322       compar = _upb_mapsorter_cmpi32;
 323       break;
 324     case UPB_DESCRIPTOR_TYPE_UINT32:
 325     case UPB_DESCRIPTOR_TYPE_FIXED32:
 326       compar = _upb_mapsorter_cmpu32;
 327       break;
 328     case UPB_DESCRIPTOR_TYPE_BOOL:
 329       compar = _upb_mapsorter_cmpbool;
 330       break;
 331     case UPB_DESCRIPTOR_TYPE_STRING:
 332       compar = _upb_mapsorter_cmpstr;
 333       break;
 334     default:
 335       UPB_UNREACHABLE();
 336   }
 337
 338   qsort(&s->entries[sorted->start], map_size, sizeof(*s->entries), compar);
 339   return true;
 340 }
 341
 342 /** upb_extreg ****************************************************************/
 343
 344 struct upb_extreg {
 345   upb_arena *arena;
 346   upb_strtable exts;  /* Key is upb_msglayout* concatenated with fieldnum. */
 347 };
 348
 349 #define EXTREG_KEY_SIZE (sizeof(upb_msglayout*) + sizeof(uint32_t))
 350
 351 static void extreg_key(char *buf, const upb_msglayout *l, uint32_t fieldnum) {
 352   memcpy(buf, &l, sizeof(l));
 353   memcpy(buf + sizeof(l), &fieldnum, sizeof(fieldnum));
 354 }
 355
 356 upb_extreg *upb_extreg_new(upb_arena *arena) {
 357   upb_extreg *r = upb_arena_malloc(arena, sizeof(*r));
 358   if (!r) return NULL;
 359   r->arena = arena;
 360   if (!upb_strtable_init(&r->exts, 8, arena)) return NULL;
 361   return r;
 362 }
 363
 364 bool _upb_extreg_add(upb_extreg *r, const upb_msglayout_ext *e, size_t count) {
 365   char buf[EXTREG_KEY_SIZE];
 366   const upb_msglayout_ext *start = e;
 367   const upb_msglayout_ext *end = e + count;
 368   for (; e < end; e++) {
 369     extreg_key(buf, e->extendee, e->field.number);
 370     if (!upb_strtable_insert(&r->exts, buf, EXTREG_KEY_SIZE,
 371                              upb_value_constptr(e), r->arena)) {
 372       goto failure;
 373     }
 374   }
 375   return true;
 376
 377 failure:
 378   /* Back out the entries previously added. */
 379   for (end = e, e = start; e < end; e++) {
 380     extreg_key(buf, e->extendee, e->field.number);
 381     upb_strtable_remove(&r->exts, buf, EXTREG_KEY_SIZE, NULL);
 382   }
 383   return false;
 384 }
 385
 386 const upb_msglayout_field *_upb_extreg_get(const upb_extreg *r,
 387                                            const upb_msglayout *l,
 388                                            uint32_t num) {
 389   char buf[EXTREG_KEY_SIZE];
 390   upb_value v;
 391   extreg_key(buf, l, num);
 392   if (upb_strtable_lookup2(&r->exts, buf, EXTREG_KEY_SIZE, &v)) {
 393     return upb_value_getconstptr(v);
 394   } else {
 395     return NULL;
 396   }
 397 }