id.c revision 299742
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 34typedef 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 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 */ 59static svn_boolean_t 60locale_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. */ 106static svn_boolean_t 107part_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 */ 142static svn_boolean_t 143txn_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 */ 162static char * 163unparse_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 189 190/* Operations on ID parts */ 191 192svn_boolean_t 193svn_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 198svn_boolean_t 199svn_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 205svn_boolean_t 206svn_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 211void 212svn_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 218svn_error_t * 219svn_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 229const char * 230svn_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 244 245/* Accessing ID Pieces. */ 246 247const svn_fs_fs__id_part_t * 248svn_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 256const svn_fs_fs__id_part_t * 257svn_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 265const svn_fs_fs__id_part_t * 266svn_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 274const svn_fs_fs__id_part_t * 275svn_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 282svn_revnum_t 283svn_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 290apr_uint64_t 291svn_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 298svn_boolean_t 299svn_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 306svn_string_t * 307svn_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 335/*** Comparing node IDs ***/ 336 337svn_boolean_t 338svn_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 358svn_boolean_t 359svn_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 390svn_fs_node_relation_t 391svn_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 400int 401svn_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 414/* Creating ID's. */ 415 416static id_vtable_t id_vtable = { 417 svn_fs_fs__id_unparse, 418 svn_fs_fs__id_compare 419}; 420 421svn_fs_id_t * 422svn_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 438svn_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 453svn_fs_id_t * 454svn_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 473svn_fs_id_t * 474svn_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 493svn_fs_id_t * 494svn_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. */ 506static svn_fs_id_t * 507id_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 584svn_error_t * 585svn_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 */ 603void 604svn_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 */ 621void 622svn_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 642