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 and RESULT
  86        * is much larger than 10.  We will then return FALSE.
  87        *
  88        * In the non-overflow case, NEXT is >= 10 * RESULT but never smaller.
  89        * We will continue the loop in that case. */
  90       if (next < result)
  91         return FALSE;
  92
  93       result = next;
  94       ++buffer;
  95     }
  96
  97   *end = buffer;
  98   if (result > LONG_MAX)
  99     return FALSE;
 100
 101   *result_p = (long)result;
 102
 103   return TRUE;
 104 }
 105
 106 /* Parse the NUL-terminated ID part at DATA and write the result into *PART.
 107  * Return TRUE if no errors were detected. */
 108 static svn_boolean_t
 109 part_parse(svn_fs_fs__id_part_t *part,
 110            const char *data)
 111 {
 112   const char *end;
 113
 114   /* special case: ID inside some transaction */
 115   if (data[0] == '_')
 116     {
 117       part->revision = SVN_INVALID_REVNUM;
 118       part->number = svn__base36toui64(&data, data + 1);
 119       return *data == '\0';
 120     }
 121
 122   /* special case: 0 / default ID */
 123   if (data[0] == '0' && data[1] == '\0')
 124     {
 125       part->revision = 0;
 126       part->number = 0;
 127       return TRUE;
 128     }
 129
 130   /* read old style / new style ID */
 131   part->number = svn__base36toui64(&data, data);
 132   if (data[0] != '-')
 133     {
 134       part->revision = 0;
 135       return *data == '\0';
 136     }
 137
 138   return locale_independent_strtol(&part->revision, data+1, &end);
 139 }
 140
 141 /* Parse the transaction id in DATA and store the result in *TXN_ID.
 142  * Return FALSE if there was some problem.
 143  */
 144 static svn_boolean_t
 145 txn_id_parse(svn_fs_fs__id_part_t *txn_id,
 146              const char *data)
 147 {
 148   const char *end;
 149   if (!locale_independent_strtol(&txn_id->revision, data, &end))
 150     return FALSE;
 151
 152   data = end;
 153   if (*data != '-')
 154     return FALSE;
 155
 156   ++data;
 157   txn_id->number = svn__base36toui64(&data, data);
 158   return *data == '\0';
 159 }
 160
 161 /* Write the textual representation of *PART into P and return a pointer
 162  * to the first position behind that string.
 163  */
 164 static char *
 165 unparse_id_part(char *p,
 166                 const svn_fs_fs__id_part_t *part)
 167 {
 168   if (SVN_IS_VALID_REVNUM(part->revision))
 169     {
 170       /* ordinary old style / new style ID */
 171       p += svn__ui64tobase36(p, part->number);
 172       if (part->revision > 0)
 173         {
 174           *(p++) = '-';
 175           p += svn__i64toa(p, part->revision);
 176         }
 177     }
 178   else
 179     {
 180       /* in txn: mark with "_" prefix */
 181       *(p++) = '_';
 182       p += svn__ui64tobase36(p, part->number);
 183     }
 184
 185   *(p++) = '.';
 186
 187   return p;
 188 }
 189
 190 \f
 191
 192 /* Operations on ID parts */
 193
 194 svn_boolean_t
 195 svn_fs_fs__id_part_is_root(const svn_fs_fs__id_part_t* part)
 196 {
 197   return part->revision == 0 && part->number == 0;
 198 }
 199
 200 svn_boolean_t
 201 svn_fs_fs__id_part_eq(const svn_fs_fs__id_part_t *lhs,
 202                       const svn_fs_fs__id_part_t *rhs)
 203 {
 204   return lhs->revision == rhs->revision && lhs->number == rhs->number;
 205 }
 206
 207 svn_boolean_t
 208 svn_fs_fs__id_txn_used(const svn_fs_fs__id_part_t *txn_id)
 209 {
 210   return SVN_IS_VALID_REVNUM(txn_id->revision) || (txn_id->number != 0);
 211 }
 212
 213 void
 214 svn_fs_fs__id_txn_reset(svn_fs_fs__id_part_t *txn_id)
 215 {
 216   txn_id->revision = SVN_INVALID_REVNUM;
 217   txn_id->number = 0;
 218 }
 219
 220 svn_error_t *
 221 svn_fs_fs__id_txn_parse(svn_fs_fs__id_part_t *txn_id,
 222                         const char *data)
 223 {
 224   if (! txn_id_parse(txn_id, data))
 225     return svn_error_createf(SVN_ERR_FS_MALFORMED_TXN_ID, NULL,
 226                              "malformed txn id '%s'", data);
 227
 228   return SVN_NO_ERROR;
 229 }
 230
 231 const char *
 232 svn_fs_fs__id_txn_unparse(const svn_fs_fs__id_part_t *txn_id,
 233                           apr_pool_t *pool)
 234 {
 235   char string[2 * SVN_INT64_BUFFER_SIZE + 1];
 236   char *p = string;
 237
 238   p += svn__i64toa(p, txn_id->revision);
 239   *(p++) = '-';
 240   p += svn__ui64tobase36(p, txn_id->number);
 241
 242   return apr_pstrmemdup(pool, string, p - string);
 243 }
 244
 245 \f
 246
 247 /* Accessing ID Pieces.  */
 248
 249 const svn_fs_fs__id_part_t *
 250 svn_fs_fs__id_node_id(const svn_fs_id_t *fs_id)
 251 {
 252   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 253
 254   return &id->private_id.node_id;
 255 }
 256
 257
 258 const svn_fs_fs__id_part_t *
 259 svn_fs_fs__id_copy_id(const svn_fs_id_t *fs_id)
 260 {
 261   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 262
 263   return &id->private_id.copy_id;
 264 }
 265
 266
 267 const svn_fs_fs__id_part_t *
 268 svn_fs_fs__id_txn_id(const svn_fs_id_t *fs_id)
 269 {
 270   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 271
 272   return &id->private_id.txn_id;
 273 }
 274
 275
 276 const svn_fs_fs__id_part_t *
 277 svn_fs_fs__id_rev_item(const svn_fs_id_t *fs_id)
 278 {
 279   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 280
 281   return &id->private_id.rev_item;
 282 }
 283
 284 svn_revnum_t
 285 svn_fs_fs__id_rev(const svn_fs_id_t *fs_id)
 286 {
 287   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 288
 289   return id->private_id.rev_item.revision;
 290 }
 291
 292 apr_uint64_t
 293 svn_fs_fs__id_item(const svn_fs_id_t *fs_id)
 294 {
 295   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 296
 297   return id->private_id.rev_item.number;
 298 }
 299
 300 svn_boolean_t
 301 svn_fs_fs__id_is_txn(const svn_fs_id_t *fs_id)
 302 {
 303   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 304
 305   return svn_fs_fs__id_txn_used(&id->private_id.txn_id);
 306 }
 307
 308 svn_string_t *
 309 svn_fs_fs__id_unparse(const svn_fs_id_t *fs_id,
 310                       apr_pool_t *pool)
 311 {
 312   char string[6 * SVN_INT64_BUFFER_SIZE + 10];
 313   const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
 314
 315   char *p = unparse_id_part(string, &id->private_id.node_id);
 316   p = unparse_id_part(p, &id->private_id.copy_id);
 317
 318   if (svn_fs_fs__id_txn_used(&id->private_id.txn_id))
 319     {
 320       *(p++) = 't';
 321       p += svn__i64toa(p, id->private_id.txn_id.revision);
 322       *(p++) = '-';
 323       p += svn__ui64tobase36(p, id->private_id.txn_id.number);
 324     }
 325   else
 326     {
 327       *(p++) = 'r';
 328       p += svn__i64toa(p, id->private_id.rev_item.revision);
 329       *(p++) = '/';
 330       p += svn__i64toa(p, id->private_id.rev_item.number);
 331     }
 332
 333   return svn_string_ncreate(string, p - string, pool);
 334 }
 335
 336 \f
 337 /*** Comparing node IDs ***/
 338
 339 svn_boolean_t
 340 svn_fs_fs__id_eq(const svn_fs_id_t *a,
 341                  const svn_fs_id_t *b)
 342 {
 343   const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
 344   const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
 345
 346   if (a == b)
 347     return TRUE;
 348
 349   return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
 350                                &id_b->private_id.node_id)
 351       && svn_fs_fs__id_part_eq(&id_a->private_id.copy_id,
 352                                &id_b->private_id.copy_id)
 353       && svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
 354                                &id_b->private_id.txn_id)
 355       && svn_fs_fs__id_part_eq(&id_a->private_id.rev_item,
 356                                &id_b->private_id.rev_item);
 357 }
 358
 359
 360 svn_boolean_t
 361 svn_fs_fs__id_check_related(const svn_fs_id_t *a,
 362                             const svn_fs_id_t *b)
 363 {
 364   const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
 365   const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
 366
 367   if (a == b)
 368     return TRUE;
 369
 370   /* If both node_ids have been created within _different_ transactions
 371      (and are still uncommitted), then it is impossible for them to be
 372      related.
 373
 374      Due to our txn-local temporary IDs, however, they might have been
 375      given the same temporary node ID.  We need to detect that case.
 376    */
 377   if (   id_a->private_id.node_id.revision == SVN_INVALID_REVNUM
 378       && id_b->private_id.node_id.revision == SVN_INVALID_REVNUM)
 379     {
 380       if (!svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
 381                                  &id_b->private_id.txn_id))
 382         return FALSE;
 383
 384       /* At this point, matching node_ids implies relatedness. */
 385     }
 386
 387   return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
 388                                &id_b->private_id.node_id);
 389 }
 390
 391
 392 svn_fs_node_relation_t
 393 svn_fs_fs__id_compare(const svn_fs_id_t *a,
 394                       const svn_fs_id_t *b)
 395 {
 396   if (svn_fs_fs__id_eq(a, b))
 397     return svn_fs_node_unchanged;
 398   return (svn_fs_fs__id_check_related(a, b) ? svn_fs_node_common_ancestor
 399                                             : svn_fs_node_unrelated);
 400 }
 401
 402 int
 403 svn_fs_fs__id_part_compare(const svn_fs_fs__id_part_t *a,
 404                            const svn_fs_fs__id_part_t *b)
 405 {
 406   if (a->revision < b->revision)
 407     return -1;
 408   if (a->revision > b->revision)
 409     return 1;
 410
 411   return a->number < b->number ? -1 : a->number == b->number ? 0 : 1;
 412 }
 413
 414
 415 \f
 416 /* Creating ID's.  */
 417
 418 static id_vtable_t id_vtable = {
 419   svn_fs_fs__id_unparse,
 420   svn_fs_fs__id_compare
 421 };
 422
 423 svn_fs_id_t *
 424 svn_fs_fs__id_txn_create_root(const svn_fs_fs__id_part_t *txn_id,
 425                               apr_pool_t *pool)
 426 {
 427   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 428
 429   /* node ID and copy ID are "0" */
 430
 431   id->private_id.txn_id = *txn_id;
 432   id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 433
 434   id->generic_id.vtable = &id_vtable;
 435   id->generic_id.fsap_data = id;
 436
 437   return (svn_fs_id_t *)id;
 438 }
 439
 440 svn_fs_id_t *svn_fs_fs__id_create_root(const svn_revnum_t revision,
 441                                        apr_pool_t *pool)
 442 {
 443   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 444
 445   id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 446   id->private_id.rev_item.revision = revision;
 447   id->private_id.rev_item.number = SVN_FS_FS__ITEM_INDEX_ROOT_NODE;
 448
 449   id->generic_id.vtable = &id_vtable;
 450   id->generic_id.fsap_data = id;
 451
 452   return (svn_fs_id_t *)id;
 453 }
 454
 455 svn_fs_id_t *
 456 svn_fs_fs__id_txn_create(const svn_fs_fs__id_part_t *node_id,
 457                          const svn_fs_fs__id_part_t *copy_id,
 458                          const svn_fs_fs__id_part_t *txn_id,
 459                          apr_pool_t *pool)
 460 {
 461   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 462
 463   id->private_id.node_id = *node_id;
 464   id->private_id.copy_id = *copy_id;
 465   id->private_id.txn_id = *txn_id;
 466   id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 467
 468   id->generic_id.vtable = &id_vtable;
 469   id->generic_id.fsap_data = id;
 470
 471   return (svn_fs_id_t *)id;
 472 }
 473
 474
 475 svn_fs_id_t *
 476 svn_fs_fs__id_rev_create(const svn_fs_fs__id_part_t *node_id,
 477                          const svn_fs_fs__id_part_t *copy_id,
 478                          const svn_fs_fs__id_part_t *rev_item,
 479                          apr_pool_t *pool)
 480 {
 481   fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
 482
 483   id->private_id.node_id = *node_id;
 484   id->private_id.copy_id = *copy_id;
 485   id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 486   id->private_id.rev_item = *rev_item;
 487
 488   id->generic_id.vtable = &id_vtable;
 489   id->generic_id.fsap_data = id;
 490
 491   return (svn_fs_id_t *)id;
 492 }
 493
 494
 495 svn_fs_id_t *
 496 svn_fs_fs__id_copy(const svn_fs_id_t *source, apr_pool_t *pool)
 497 {
 498   const fs_fs__id_t *id = (const fs_fs__id_t *)source;
 499   fs_fs__id_t *new_id = apr_pmemdup(pool, id, sizeof(*new_id));
 500
 501   new_id->generic_id.fsap_data = new_id;
 502
 503   return (svn_fs_id_t *)new_id;
 504 }
 505
 506 /* Return an ID resulting from parsing the string DATA, or NULL if DATA is
 507    an invalid ID string. *DATA will be modified / invalidated by this call. */
 508 static svn_fs_id_t *
 509 id_parse(char *data,
 510          apr_pool_t *pool)
 511 {
 512   fs_fs__id_t *id;
 513   char *str;
 514
 515   /* Alloc a new svn_fs_id_t structure. */
 516   id = apr_pcalloc(pool, sizeof(*id));
 517   id->generic_id.vtable = &id_vtable;
 518   id->generic_id.fsap_data = id;
 519
 520   /* Now, we basically just need to "split" this data on `.'
 521      characters.  We will use svn_cstring_tokenize, which will put
 522      terminators where each of the '.'s used to be.  Then our new
 523      id field will reference string locations inside our duplicate
 524      string.*/
 525
 526   /* Node Id */
 527   str = svn_cstring_tokenize(".", &data);
 528   if (str == NULL)
 529     return NULL;
 530   if (! part_parse(&id->private_id.node_id, str))
 531     return NULL;
 532
 533   /* Copy Id */
 534   str = svn_cstring_tokenize(".", &data);
 535   if (str == NULL)
 536     return NULL;
 537   if (! part_parse(&id->private_id.copy_id, str))
 538     return NULL;
 539
 540   /* Txn/Rev Id */
 541   str = svn_cstring_tokenize(".", &data);
 542   if (str == NULL)
 543     return NULL;
 544
 545   if (str[0] == 'r')
 546     {
 547       apr_int64_t val;
 548       const char *tmp;
 549       svn_error_t *err;
 550
 551       /* This is a revision type ID */
 552       id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
 553       id->private_id.txn_id.number = 0;
 554
 555       data = str + 1;
 556       str = svn_cstring_tokenize("/", &data);
 557       if (str == NULL)
 558         return NULL;
 559       if (!locale_independent_strtol(&id->private_id.rev_item.revision,
 560                                      str, &tmp))
 561         return NULL;
 562
 563       err = svn_cstring_atoi64(&val, data);
 564       if (err)
 565         {
 566           svn_error_clear(err);
 567           return NULL;
 568         }
 569       id->private_id.rev_item.number = (apr_uint64_t)val;
 570     }
 571   else if (str[0] == 't')
 572     {
 573       /* This is a transaction type ID */
 574       id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
 575       id->private_id.rev_item.number = 0;
 576
 577       if (! txn_id_parse(&id->private_id.txn_id, str + 1))
 578         return NULL;
 579     }
 580   else
 581     return NULL;
 582
 583   return (svn_fs_id_t *)id;
 584 }
 585
 586 svn_error_t *
 587 svn_fs_fs__id_parse(const svn_fs_id_t **id_p,
 588                     char *data,
 589                     apr_pool_t *pool)
 590 {
 591   svn_fs_id_t *id = id_parse(data, pool);
 592   if (id == NULL)
 593     return svn_error_createf(SVN_ERR_FS_MALFORMED_NODEREV_ID, NULL,
 594                              "Malformed node revision ID string");
 595
 596   *id_p = id;
 597
 598   return SVN_NO_ERROR;
 599 }
 600
 601 /* (de-)serialization support */
 602
 603 /* Serialize an ID within the serialization CONTEXT.
 604  */
 605 void
 606 svn_fs_fs__id_serialize(svn_temp_serializer__context_t *context,
 607                         const svn_fs_id_t * const *in)
 608 {
 609   const fs_fs__id_t *id = (const fs_fs__id_t *)*in;
 610
 611   /* nothing to do for NULL ids */
 612   if (id == NULL)
 613     return;
 614
 615   /* Serialize the id data struct itself.
 616    * Note that the structure behind IN is actually larger than a mere
 617    * svn_fs_id_t . */
 618   svn_temp_serializer__add_leaf(context,
 619                                 (const void * const *)in,
 620                                 sizeof(fs_fs__id_t));
 621 }
 622
 623 /* Deserialize an ID inside the BUFFER.
 624  */
 625 void
 626 svn_fs_fs__id_deserialize(void *buffer, svn_fs_id_t **in_out)
 627 {
 628   fs_fs__id_t *id;
 629
 630   /* The id maybe all what is in the whole buffer.
 631    * Don't try to fixup the pointer in that case*/
 632   if (*in_out != buffer)
 633     svn_temp_deserializer__resolve(buffer, (void**)in_out);
 634
 635   id = (fs_fs__id_t *)*in_out;
 636
 637   /* no id, no sub-structure fixup necessary */
 638   if (id == NULL)
 639     return;
 640
 641   /* the stored vtable is bogus at best -> set the right one */
 642   id->generic_id.vtable = &id_vtable;
 643   id->generic_id.fsap_data = id;
 644 }
 645