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
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
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
locale_independent_strtol(long * result_p,const char * buffer,const char ** end)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
part_parse(svn_fs_fs__id_part_t * part,const char * data)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
txn_id_parse(svn_fs_fs__id_part_t * txn_id,const char * data)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 *
unparse_id_part(char * p,const svn_fs_fs__id_part_t * part)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
191
192 /* Operations on ID parts */
193
194 svn_boolean_t
svn_fs_fs__id_part_is_root(const svn_fs_fs__id_part_t * part)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
svn_fs_fs__id_part_eq(const svn_fs_fs__id_part_t * lhs,const svn_fs_fs__id_part_t * rhs)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
svn_fs_fs__id_txn_used(const svn_fs_fs__id_part_t * txn_id)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
svn_fs_fs__id_txn_reset(svn_fs_fs__id_part_t * txn_id)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 *
svn_fs_fs__id_txn_parse(svn_fs_fs__id_part_t * txn_id,const char * data)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 *
svn_fs_fs__id_txn_unparse(const svn_fs_fs__id_part_t * txn_id,apr_pool_t * pool)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
246
247 /* Accessing ID Pieces. */
248
249 const svn_fs_fs__id_part_t *
svn_fs_fs__id_node_id(const svn_fs_id_t * fs_id)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 *
svn_fs_fs__id_copy_id(const svn_fs_id_t * fs_id)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 *
svn_fs_fs__id_txn_id(const svn_fs_id_t * fs_id)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 *
svn_fs_fs__id_rev_item(const svn_fs_id_t * fs_id)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
svn_fs_fs__id_rev(const svn_fs_id_t * fs_id)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
svn_fs_fs__id_item(const svn_fs_id_t * fs_id)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
svn_fs_fs__id_is_txn(const svn_fs_id_t * fs_id)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 *
svn_fs_fs__id_unparse(const svn_fs_id_t * fs_id,apr_pool_t * pool)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
337 /*** Comparing node IDs ***/
338
339 svn_boolean_t
svn_fs_fs__id_eq(const svn_fs_id_t * a,const svn_fs_id_t * b)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
svn_fs_fs__id_check_related(const svn_fs_id_t * a,const svn_fs_id_t * b)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
svn_fs_fs__id_compare(const svn_fs_id_t * a,const svn_fs_id_t * b)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
svn_fs_fs__id_part_compare(const svn_fs_fs__id_part_t * a,const svn_fs_fs__id_part_t * b)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
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 *
svn_fs_fs__id_txn_create_root(const svn_fs_fs__id_part_t * txn_id,apr_pool_t * pool)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
svn_fs_fs__id_create_root(const svn_revnum_t revision,apr_pool_t * pool)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 *
svn_fs_fs__id_txn_create(const svn_fs_fs__id_part_t * node_id,const svn_fs_fs__id_part_t * copy_id,const svn_fs_fs__id_part_t * txn_id,apr_pool_t * pool)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 *
svn_fs_fs__id_rev_create(const svn_fs_fs__id_part_t * node_id,const svn_fs_fs__id_part_t * copy_id,const svn_fs_fs__id_part_t * rev_item,apr_pool_t * pool)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 *
svn_fs_fs__id_copy(const svn_fs_id_t * source,apr_pool_t * pool)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 *
id_parse(char * data,apr_pool_t * pool)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 *
svn_fs_fs__id_parse(const svn_fs_id_t ** id_p,char * data,apr_pool_t * pool)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 '%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 */
606 void
svn_fs_fs__id_serialize(svn_temp_serializer__context_t * context,const svn_fs_id_t * const * in)607 svn_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 */
626 void
svn_fs_fs__id_deserialize(void * buffer,svn_fs_id_t ** in_out)627 svn_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