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 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. */ 108static svn_boolean_t 109part_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 */ 144static svn_boolean_t 145txn_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 */ 164static char * 165unparse_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 191 192/* Operations on ID parts */ 193 194svn_boolean_t 195svn_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 200svn_boolean_t 201svn_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 207svn_boolean_t 208svn_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 213void 214svn_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 220svn_error_t * 221svn_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 231const char * 232svn_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 246 247/* Accessing ID Pieces. */ 248 249const svn_fs_fs__id_part_t * 250svn_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 258const svn_fs_fs__id_part_t * 259svn_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 267const svn_fs_fs__id_part_t * 268svn_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 276const svn_fs_fs__id_part_t * 277svn_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 284svn_revnum_t 285svn_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 292apr_uint64_t 293svn_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 300svn_boolean_t 301svn_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 308svn_string_t * 309svn_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 337/*** Comparing node IDs ***/ 338 339svn_boolean_t 340svn_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 360svn_boolean_t 361svn_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 392svn_fs_node_relation_t 393svn_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 402int 403svn_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 416/* Creating ID's. */ 417 418static id_vtable_t id_vtable = { 419 svn_fs_fs__id_unparse, 420 svn_fs_fs__id_compare 421}; 422 423svn_fs_id_t * 424svn_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 440svn_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 455svn_fs_id_t * 456svn_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 475svn_fs_id_t * 476svn_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 495svn_fs_id_t * 496svn_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. */ 508static svn_fs_id_t * 509id_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 586svn_error_t * 587svn_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 '%s'", 595 data); 596 597 *id_p = id; 598 599 return SVN_NO_ERROR; 600} 601 602/* (de-)serialization support */ 603 604/* Serialize an ID within the serialization CONTEXT. 605 */ 606void 607svn_fs_fs__id_serialize(svn_temp_serializer__context_t *context, 608 const svn_fs_id_t * const *in) 609{ 610 const fs_fs__id_t *id = (const fs_fs__id_t *)*in; 611 612 /* nothing to do for NULL ids */ 613 if (id == NULL) 614 return; 615 616 /* Serialize the id data struct itself. 617 * Note that the structure behind IN is actually larger than a mere 618 * svn_fs_id_t . */ 619 svn_temp_serializer__add_leaf(context, 620 (const void * const *)in, 621 sizeof(fs_fs__id_t)); 622} 623 624/* Deserialize an ID inside the BUFFER. 625 */ 626void 627svn_fs_fs__id_deserialize(void *buffer, svn_fs_id_t **in_out) 628{ 629 fs_fs__id_t *id; 630 631 /* The id maybe all what is in the whole buffer. 632 * Don't try to fixup the pointer in that case*/ 633 if (*in_out != buffer) 634 svn_temp_deserializer__resolve(buffer, (void**)in_out); 635 636 id = (fs_fs__id_t *)*in_out; 637 638 /* no id, no sub-structure fixup necessary */ 639 if (id == NULL) 640 return; 641 642 /* the stored vtable is bogus at best -> set the right one */ 643 id->generic_id.vtable = &id_vtable; 644 id->generic_id.fsap_data = id; 645} 646 647