contrib/subversion/subversion/libsvn_fs_fs/id.c

   1 /* id.c : operations on node-revision IDs
   2  *
   3  * ====================================================================
   4  *    Licensed to the Apache Software Foundation (ASF) under one
   5  *    or more contributor license agreements.  See the NOTICE file
   6  *    distributed with this work for additional information
   7  *    regarding copyright ownership.  The ASF licenses this file
   8  *    to you under the Apache License, Version 2.0 (the
   9  *    "License"); you may not use this file except in compliance
  10  *    with the License.  You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  *    Unless required by applicable law or agreed to in writing,
  15  *    software distributed under the License is distributed on an
  16  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  17  *    KIND, either express or implied.  See the License for the
  18  *    specific language governing permissions and limitations
  19  *    under the License.
  20  * ====================================================================
  21  */
  22
  23 #include <string.h>
  24 #include <stdlib.h>
  25
  26 #include "id.h"
  27 #include "index.h"
  28
  29 #include "../libsvn_fs/fs-loader.h"
  30 #include "private/svn_temp_serializer.h"
  31 #include "private/svn_string_private.h"
  32
  33 \f
  34 typedef struct fs_fs__id_t
  35 {
  36   /* API visible part */
  37   svn_fs_id_t generic_id;
  38
  39   /* private members */
  40   struct
  41     {
  42       svn_fs_fs__id_part_t node_id;
  43       svn_fs_fs__id_part_t copy_id;
  44       svn_fs_fs__id_part_t txn_id;
  45       svn_fs_fs__id_part_t rev_item;
  46     } private_id;
  47 } fs_fs__id_t;
  48
  49 \f
  50
  51 /** Like strtol but with a fixed base of 10, locale independent and limited
  52  * to non-negative values.  Overflows are indicated by a FALSE return value
  53  * in which case *RESULT_P will not be modified.
  54  *
  55  * This allows the compiler to generate massively faster code.
  56  * (E.g. Avoiding locale specific processing).  ID parsing is one of the
  57  * most CPU consuming parts of FSFS data access.  Better be quick.
  58  */
  59 static svn_boolean_t
  60 locale_independent_strtol(long *result_p,
  61                           const char* buffer,
  62                           const char** end)
  63 {
  64   /* We allow positive values only.  We use unsigned arithmetics to get
  65    * well-defined overflow behavior.  It also happens to allow for a wider
  66    * range of compiler-side optimizations. */
  67   unsigned long result = 0;
  68   while (1)
  69     {
  70       unsigned long c = (unsigned char)*buffer - (unsigned char)'0';
  71       unsigned long next;
  72
  73       /* This implies the NUL check. */
  74       if (c > 9)
  75         break;
  76
  77       /* Overflow check.  Passing this, NEXT can be no more than ULONG_MAX+9
  78        * before being truncated to ULONG but it still covers 0 .. ULONG_MAX.
  79        */
  80       if (result > ULONG_MAX / 10)
  81         return FALSE;
  82
  83       next = result * 10 + c;
  84
  85       /* Overflow check.  In case of an overflow, NEXT is 0..9.
  86        * In the non-overflow case, RESULT is either >= 10 or RESULT and NEXT
  87        * are both 0. */
  88       if (next < result)
  89         return FALSE;
  90
  91       result = next;
  92       ++buffer;
  93     }
  94
  95   *end = buffer;
  96   if (result > LONG_MAX)
  97     return FALSE;
  98
  99   *result_p = (long)result;
 100
 101   return TRUE;
 102 }
 103
 104 /* Parse the NUL-terminated ID part at DATA and write the result into *PART.
 105  * Return TRUE if no errors were detected. */
 106 static svn_boolean_t
 107 part_parse(svn_fs_fs__id_part_t *part,
 108            const char *data)
 109 {
 110   const char *end;
 111
 112   /* special case: ID inside some transaction */
 113   if (data[0] == '_')
 114     {
 115       part->revision = SVN_INVALID_REVNUM;
 116       part->number = svn__base36toui64(&data, data + 1);
 117       return *data == '\0';
 118     }
 119
 120   /* special case: 0 / default ID */
 121   if (data[0] == '0' && data[1] == '\0')
 122     {
 123       part->revision = 0;
 124       part->number = 0;
 125       return TRUE;
 126     }
 127
 128   /* read old style / new style ID */
 129   part->number = svn__base36toui64(&data, data);
 130   if (data[0] != '-')
 131     {
 132       part->revision = 0;
 133       return *data == '\0';
 134     }
 135
 136   return locale_independent_strtol(&part->revision, data+1, &end);
 137 }
 138
 139 /* Parse the transaction id in DATA and store the result in *TXN_ID.
 140  * Return FALSE if there was some problem.
 141  */
 142 static svn_boolean_t
 143 txn_id_parse(svn_fs_fs__id_part_t *txn_id,
 144              const char *data)
 145 {
 146   const char *end;
 147   if (!locale_independent_strtol(&txn_id->revision, data, &end))
 148     return FALSE;
 149
 150   data = end;
 151   if (*data != '-')
 152     return FALSE;
 153
 154   ++data;
 155   txn_id->number = svn__base36toui64(&data, data);
 156   return *data == '\0';
 157 }
 158
 159 /* Write the textual representation of *PART into P and return a pointer
 160  * to the first position behind that string.
 161  */
 162 static char *
 163 unparse_id_part(char *p,
 164                 const svn_fs_fs__id_part_t *part)
 165 {
 166   if (SVN_IS_VALID_REVNUM(part->revision))
 167     {
 168       /* ordinary old style / new style ID */
 169       p += svn__ui64tobase36(p, part->number);
 170       if (part->revision > 0)
 171         {
 172           *(p++) = '-';
 173           p += svn__i64toa(p, part->revision);
 174         }
 175     }
 176   else
 177     {
 178       /* in txn: mark with "_" prefix */
 179       *(p++) = '_';
 180       p += svn__ui64tobase36(p, part->number);
 181     }
 182
 183   *(p++) = '.';
 184
 185   return p;
 186 }
 187
 188 \f
 189
 190 /* Operations on ID parts */
 191
 192 svn_boolean_t
 193 svn_fs_fs__id_part_is_root(const svn_fs_fs__id_part_t* part)
 194 {
 195   return part->revision == 0 && part->number == 0;
 196 }
 197
 198 svn_boolean_t
 199 svn_fs_fs__id_part_eq(const svn_fs_fs__id_part_t *lhs,
 200                       const svn_fs_fs__id_part_t *rhs)
 201 {
 202   return lhs->revision == rhs->revision && lhs->number == rhs->number;
 203 }
 204
 205 svn_boolean_t
 206 svn_fs_fs__id_txn_used(const svn_fs_fs__id_part_t *txn_id)
 207 {
 208   return SVN_IS_VALID_REVNUM(txn_id->revision) || (txn_id->number != 0);
 209 }
 210
 211 void
 212 svn_fs_fs__id_txn_reset(svn_fs_fs__id_part_t *txn_id)
 213 {
 214   txn_id->revision = SVN_INVALID_REVNUM;
 215   txn_id->number = 0;
 216 }
 217
 218 svn_error_t *
 219 svn_fs_fs__id_txn_parse(svn_fs_fs__id_part_t *txn_id,
 220                         const char *data)
 221 {
 222   if (! txn_id_parse(txn_id, data))
 223     return svn_error_createf(SVN_ERR_FS_MALFORMED_TXN_ID, NULL,
 224                              "malformed txn id '%s'", data);
 225
 226   return SVN_NO_ERROR;
 227 }
 228
 229 const char *
 230 svn_fs_fs__id_txn_unparse(const svn_fs_fs__id_part_t *txn_id,
 231                           apr_pool_t *pool)
 232 {
 233   char string[2 * SVN_INT64_BUFFER_SIZE + 1];
 234   char *p = string;
 235
 236   p += svn__i64toa(p, txn_id->revision);
 237   *(p++) = '-';
 238   p += svn__ui64tobase36(p, txn_id->number);
 239
 240   return apr_pstrmemdup(pool, string, p - string);
 241 }
 242
 243 \f
 244
 245 /* Accessing ID Pieces.  */
 246
 247 const svn_fs_fs__id_part_t *
 248 svn_fs_fs__id_node_id(const svn_fs_id_t *fs_id)
 249 {
 250   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 251
 252   return &id->private_id.node_id;
 253 }
 254
 255
 256 const svn_fs_fs__id_part_t *
 257 svn_fs_fs__id_copy_id(const svn_fs_id_t *fs_id)
 258 {
 259   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 260
 261   return &id->private_id.copy_id;
 262 }
 263
 264
 265 const svn_fs_fs__id_part_t *
 266 svn_fs_fs__id_txn_id(const svn_fs_id_t *fs_id)
 267 {
 268   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 269
 270   return &id->private_id.txn_id;
 271 }
 272
 273
 274 const svn_fs_fs__id_part_t *
 275 svn_fs_fs__id_rev_item(const svn_fs_id_t *fs_id)
 276 {
 277   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 278
 279   return &id->private_id.rev_item;
 280 }
 281
 282 svn_revnum_t
 283 svn_fs_fs__id_rev(const svn_fs_id_t *fs_id)
 284 {
 285   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 286
 287   return id->private_id.rev_item.revision;
 288 }
 289
 290 apr_uint64_t
 291 svn_fs_fs__id_item(const svn_fs_id_t *fs_id)
 292 {
 293   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 294
 295   return id->private_id.rev_item.number;
 296 }
 297
 298 svn_boolean_t
 299 svn_fs_fs__id_is_txn(const svn_fs_id_t *fs_id)
 300 {
 301   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 302
 303   return svn_fs_fs__id_txn_used(&id->private_id.txn_id);
 304 }
 305
 306 svn_string_t *
 307 svn_fs_fs__id_unparse(const svn_fs_id_t *fs_id,
 308                       apr_pool_t *pool)
 309 {
 310   char string[6 * SVN_INT64_BUFFER_SIZE + 10];
 311   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 312
 313   char *p = unparse_id_part(string, &id->private_id.node_id);
 314   p = unparse_id_part(p, &id->private_id.copy_id);
 315
 316   if (svn_fs_fs__id_txn_used(&id->private_id.txn_id))
 317     {
 318       *(p++) = 't';
 319       p += svn__i64toa(p, id->private_id.txn_id.revision);
 320       *(p++) = '-';
 321       p += svn__ui64tobase36(p, id->private_id.txn_id.number);
 322     }
 323   else
 324     {
 325       *(p++) = 'r';
 326       p += svn__i64toa(p, id->private_id.rev_item.revision);
 327       *(p++) = '/';
 328       p += svn__i64toa(p, id->private_id.rev_item.number);
 329     }
 330
 331   return svn_string_ncreate(string, p - string, pool);
 332 }
 333
 334 \f
 335 /*** Comparing node IDs ***/
 336
 337 svn_boolean_t
 338 svn_fs_fs__id_eq(const svn_fs_id_t *a,
 339                  const svn_fs_id_t *b)
 340 {
 341   const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
 342   const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
 343
 344   if (a == b)
 345     return TRUE;
 346
 347   return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
 348                                &id_b->private_id.node_id)
 349       && svn_fs_fs__id_part_eq(&id_a->private_id.copy_id,
 350                                &id_b->private_id.copy_id)
 351       && svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
 352                                &id_b->private_id.txn_id)
 353       && svn_fs_fs__id_part_eq(&id_a->private_id.rev_item,
 354                                &id_b->private_id.rev_item);
 355 }
 356
 357
 358 svn_boolean_t
 359 svn_fs_fs__id_check_related(const svn_fs_id_t *a,
 360                             const svn_fs_id_t *b)
 361 {
 362   const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
 363   const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
 364
 365   if (a == b)
 366     return TRUE;
 367
 368   /* If both node_ids have been created within _different_ transactions
 369      (and are still uncommitted), then it is impossible for them to be
 370      related.
 371
 372      Due to our txn-local temporary IDs, however, they might have been
 373      given the same temporary node ID.  We need to detect that case.
 374    */
 375   if (   id_a->private_id.node_id.revision == SVN_INVALID_REVNUM
 376       && id_b->private_id.node_id.revision == SVN_INVALID_REVNUM)
 377     {
 378       if (!svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
 379                                  &id_b->private_id.txn_id))
 380         return FALSE;
 381
 382       /* At this point, matching node_ids implies relatedness. */
 383     }
 384
 385   return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
 386                                &id_b->private_id.node_id);
 387 }
 388
 389
 390 svn_fs_node_relation_t
 391 svn_fs_fs__id_compare(const svn_fs_id_t *a,
 392                       const svn_fs_id_t *b)
 393 {
 394   if (svn_fs_fs__id_eq(a, b))
 395     return svn_fs_node_unchanged;
 396   return (svn_fs_fs__id_check_related(a, b) ? svn_fs_node_common_ancestor
 397                                             : svn_fs_node_unrelated);
 398 }
 399
 400 int
 401 svn_fs_fs__id_part_compare(const svn_fs_fs__id_part_t *a,
 402                            const svn_fs_fs__id_part_t *b)
 403 {
 404   if (a->revision < b->revision)
 405     return -1;
 406   if (a->revision > b->revision)
 407     return 1;
 408
 409   return a->number < b->number ? -1 : a->number == b->number ? 0 : 1;
 410 }
 411
 412
 413 \f
 414 /* Creating ID's.  */
 415
 416 static id_vtable_t id_vtable = {
 417   svn_fs_fs__id_unparse,
 418   svn_fs_fs__id_compare
 419 };
 420
 421 svn_fs_id_t *
 422 svn_fs_fs__id_txn_create_root(const svn_fs_fs__id_part_t *txn_id,
 423                               apr_pool_t *pool)
 424 {
 425   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 426
 427   /* node ID and copy ID are "0" */
 428
 429   id->private_id.txn_id = *txn_id;
 430   id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 431
 432   id->generic_id.vtable = &id_vtable;
 433   id->generic_id.fsap_data = id;
 434
 435   return (svn_fs_id_t *)id;
 436 }
 437
 438 svn_fs_id_t *svn_fs_fs__id_create_root(const svn_revnum_t revision,
 439                                        apr_pool_t *pool)
 440 {
 441   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 442
 443   id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 444   id->private_id.rev_item.revision = revision;
 445   id->private_id.rev_item.number = SVN_FS_FS__ITEM_INDEX_ROOT_NODE;
 446
 447   id->generic_id.vtable = &id_vtable;
 448   id->generic_id.fsap_data = id;
 449
 450   return (svn_fs_id_t *)id;
 451 }
 452
 453 svn_fs_id_t *
 454 svn_fs_fs__id_txn_create(const svn_fs_fs__id_part_t *node_id,
 455                          const svn_fs_fs__id_part_t *copy_id,
 456                          const svn_fs_fs__id_part_t *txn_id,
 457                          apr_pool_t *pool)
 458 {
 459   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 460
 461   id->private_id.node_id = *node_id;
 462   id->private_id.copy_id = *copy_id;
 463   id->private_id.txn_id = *txn_id;
 464   id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 465
 466   id->generic_id.vtable = &id_vtable;
 467   id->generic_id.fsap_data = id;
 468
 469   return (svn_fs_id_t *)id;
 470 }
 471
 472
 473 svn_fs_id_t *
 474 svn_fs_fs__id_rev_create(const svn_fs_fs__id_part_t *node_id,
 475                          const svn_fs_fs__id_part_t *copy_id,
 476                          const svn_fs_fs__id_part_t *rev_item,
 477                          apr_pool_t *pool)
 478 {
 479   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 480
 481   id->private_id.node_id = *node_id;
 482   id->private_id.copy_id = *copy_id;
 483   id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 484   id->private_id.rev_item = *rev_item;
 485
 486   id->generic_id.vtable = &id_vtable;
 487   id->generic_id.fsap_data = id;
 488
 489   return (svn_fs_id_t *)id;
 490 }
 491
 492
 493 svn_fs_id_t *
 494 svn_fs_fs__id_copy(const svn_fs_id_t *source, apr_pool_t *pool)
 495 {
 496   const fs_fs__id_t *id = (const fs_fs__id_t *)source;
 497   fs_fs__id_t *new_id = apr_pmemdup(pool, id, sizeof(*new_id));
 498
 499   new_id->generic_id.fsap_data = new_id;
 500
 501   return (svn_fs_id_t *)new_id;
 502 }
 503
 504 /* Return an ID resulting from parsing the string DATA, or NULL if DATA is
 505    an invalid ID string. *DATA will be modified / invalidated by this call. */
 506 static svn_fs_id_t *
 507 id_parse(char *data,
 508          apr_pool_t *pool)
 509 {
 510   fs_fs__id_t *id;
 511   char *str;
 512
 513   /* Alloc a new svn_fs_id_t structure. */
 514   id = apr_pcalloc(pool, sizeof(*id));
 515   id->generic_id.vtable = &id_vtable;
 516   id->generic_id.fsap_data = id;
 517
 518   /* Now, we basically just need to "split" this data on `.'
 519      characters.  We will use svn_cstring_tokenize, which will put
 520      terminators where each of the '.'s used to be.  Then our new
 521      id field will reference string locations inside our duplicate
 522      string.*/
 523
 524   /* Node Id */
 525   str = svn_cstring_tokenize(".", &data);
 526   if (str == NULL)
 527     return NULL;
 528   if (! part_parse(&id->private_id.node_id, str))
 529     return NULL;
 530
 531   /* Copy Id */
 532   str = svn_cstring_tokenize(".", &data);
 533   if (str == NULL)
 534     return NULL;
 535   if (! part_parse(&id->private_id.copy_id, str))
 536     return NULL;
 537
 538   /* Txn/Rev Id */
 539   str = svn_cstring_tokenize(".", &data);
 540   if (str == NULL)
 541     return NULL;
 542
 543   if (str[0] == 'r')
 544     {
 545       apr_int64_t val;
 546       const char *tmp;
 547       svn_error_t *err;
 548
 549       /* This is a revision type ID */
 550       id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 551       id->private_id.txn_id.number = 0;
 552
 553       data = str + 1;
 554       str = svn_cstring_tokenize("/", &data);
 555       if (str == NULL)
 556         return NULL;
 557       if (!locale_independent_strtol(&id->private_id.rev_item.revision,
 558                                      str, &tmp))
 559         return NULL;
 560
 561       err = svn_cstring_atoi64(&val, data);
 562       if (err)
 563         {
 564           svn_error_clear(err);
 565           return NULL;
 566         }
 567       id->private_id.rev_item.number = (apr_uint64_t)val;
 568     }
 569   else if (str[0] == 't')
 570     {
 571       /* This is a transaction type ID */
 572       id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 573       id->private_id.rev_item.number = 0;
 574
 575       if (! txn_id_parse(&id->private_id.txn_id, str + 1))
 576         return NULL;
 577     }
 578   else
 579     return NULL;
 580
 581   return (svn_fs_id_t *)id;
 582 }
 583
 584 svn_error_t *
 585 svn_fs_fs__id_parse(const svn_fs_id_t **id_p,
 586                     char *data,
 587                     apr_pool_t *pool)
 588 {
 589   svn_fs_id_t *id = id_parse(data, pool);
 590   if (id == NULL)
 591     return svn_error_createf(SVN_ERR_FS_MALFORMED_NODEREV_ID, NULL,
 592                              "Malformed node revision ID string");
 593
 594   *id_p = id;
 595
 596   return SVN_NO_ERROR;
 597 }
 598
 599 /* (de-)serialization support */
 600
 601 /* Serialize an ID within the serialization CONTEXT.
 602  */
 603 void
 604 svn_fs_fs__id_serialize(svn_temp_serializer__context_t *context,
 605                         const svn_fs_id_t * const *in)
 606 {
 607   const fs_fs__id_t *id = (const fs_fs__id_t *)*in;
 608
 609   /* nothing to do for NULL ids */
 610   if (id == NULL)
 611     return;
 612
 613   /* serialize the id data struct itself */
 614   svn_temp_serializer__add_leaf(context,
 615                                 (const void * const *)in,
 616                                 sizeof(fs_fs__id_t));
 617 }
 618
 619 /* Deserialize an ID inside the BUFFER.
 620  */
 621 void
 622 svn_fs_fs__id_deserialize(void *buffer, svn_fs_id_t **in_out)
 623 {
 624   fs_fs__id_t *id;
 625
 626   /* The id maybe all what is in the whole buffer.
 627    * Don't try to fixup the pointer in that case*/
 628   if (*in_out != buffer)
 629     svn_temp_deserializer__resolve(buffer, (void**)in_out);
 630
 631   id = (fs_fs__id_t *)*in_out;
 632
 633   /* no id, no sub-structure fixup necessary */
 634   if (id == NULL)
 635     return;
 636
 637   /* the stored vtable is bogus at best -> set the right one */
 638   id->generic_id.vtable = &id_vtable;
 639   id->generic_id.fsap_data = id;
 640 }
 641