1/* changes.h --- FSX changed paths lists container 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 "svn_private_config.h" 24 25#include "private/svn_packed_data.h" 26 27#include "changes.h" 28#include "string_table.h" 29#include "temp_serializer.h" 30 31/* These flags will be used with the FLAGS field in binary_change_t. 32 */ 33 34/* the change contains a text modification */ 35#define CHANGE_TEXT_MOD 0x00001 36 37/* the change contains a property modification */ 38#define CHANGE_PROP_MOD 0x00002 39 40/* the last part (rev_id) of node revision ID is a transaction ID */ 41#define CHANGE_TXN_NODE 0x00004 42 43/* (flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT extracts the node type */ 44#define CHANGE_NODE_SHIFT 0x00003 45#define CHANGE_NODE_MASK 0x00018 46 47/* node types according to svn_node_kind_t */ 48#define CHANGE_NODE_NONE 0x00000 49#define CHANGE_NODE_FILE 0x00008 50#define CHANGE_NODE_DIR 0x00010 51#define CHANGE_NODE_UNKNOWN 0x00018 52 53/* (flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT extracts the change type */ 54#define CHANGE_KIND_SHIFT 0x00005 55#define CHANGE_KIND_MASK 0x000E0 56 57/* node types according to svn_fs_path_change_kind_t */ 58#define CHANGE_KIND_MODIFY 0x00000 59#define CHANGE_KIND_ADD 0x00020 60#define CHANGE_KIND_DELETE 0x00040 61#define CHANGE_KIND_REPLACE 0x00060 62#define CHANGE_KIND_RESET 0x00080 63#define CHANGE_KIND_MOVE 0x000A0 64#define CHANGE_KIND_MOVEREPLACE 0x000C0 65 66/* Our internal representation of a change */ 67typedef struct binary_change_t 68{ 69 /* define the kind of change and what specific information is present */ 70 int flags; 71 72 /* Path of the change. */ 73 apr_size_t path; 74 75 /* copy-from information. 76 * Not present if COPYFROM_REV is SVN_INVALID_REVNUM. */ 77 svn_revnum_t copyfrom_rev; 78 apr_size_t copyfrom_path; 79 80 /* Relevant parts of the node revision ID of the change. 81 * Empty, if REV_ID is not "used". */ 82 svn_fs_x__id_t noderev_id; 83 84} binary_change_t; 85 86/* The actual container object. Change lists are concatenated into CHANGES 87 * and and their begins and ends are stored in OFFSETS. 88 */ 89struct svn_fs_x__changes_t 90{ 91 /* The paths - either in 'builder' mode or finalized mode. 92 * The respective other pointer will be NULL. */ 93 string_table_builder_t *builder; 94 string_table_t *paths; 95 96 /* All changes of all change lists concatenated. 97 * Array elements are binary_change_t.structs (not pointer!) */ 98 apr_array_header_t *changes; 99 100 /* [Offsets[index] .. Offsets[index+1]) is the range in CHANGES that 101 * forms the contents of change list INDEX. */ 102 apr_array_header_t *offsets; 103}; 104 105/* Create and return a new container object, allocated in RESULT_POOL with 106 * an initial capacity of INITIAL_COUNT changes. The PATH and BUILDER 107 * members must be initialized by the caller afterwards. 108 */ 109static svn_fs_x__changes_t * 110changes_create_body(apr_size_t initial_count, 111 apr_pool_t *result_pool) 112{ 113 svn_fs_x__changes_t *changes = apr_pcalloc(result_pool, sizeof(*changes)); 114 115 changes->changes = apr_array_make(result_pool, (int)initial_count, 116 sizeof(binary_change_t)); 117 changes->offsets = apr_array_make(result_pool, 16, sizeof(int)); 118 APR_ARRAY_PUSH(changes->offsets, int) = 0; 119 120 return changes; 121} 122 123svn_fs_x__changes_t * 124svn_fs_x__changes_create(apr_size_t initial_count, 125 apr_pool_t *result_pool) 126{ 127 svn_fs_x__changes_t *changes = changes_create_body(initial_count, 128 result_pool); 129 changes->builder = svn_fs_x__string_table_builder_create(result_pool); 130 131 return changes; 132} 133 134/* Add CHANGE to the latest change list in CHANGES. 135 */ 136static svn_error_t * 137append_change(svn_fs_x__changes_t *changes, 138 svn_fs_x__change_t *change) 139{ 140 binary_change_t binary_change = { 0 }; 141 svn_boolean_t is_txn_id; 142 143 /* CHANGE must be sufficiently complete */ 144 SVN_ERR_ASSERT(change); 145 SVN_ERR_ASSERT(change->path.data); 146 147 /* Relevant parts of the revision ID of the change. */ 148 binary_change.noderev_id = change->noderev_id; 149 150 /* define the kind of change and what specific information is present */ 151 is_txn_id = svn_fs_x__is_txn(binary_change.noderev_id.change_set); 152 binary_change.flags = (change->text_mod ? CHANGE_TEXT_MOD : 0) 153 | (change->prop_mod ? CHANGE_PROP_MOD : 0) 154 | (is_txn_id ? CHANGE_TXN_NODE : 0) 155 | ((int)change->change_kind << CHANGE_KIND_SHIFT) 156 | ((int)change->node_kind << CHANGE_NODE_SHIFT); 157 158 /* Path of the change. */ 159 binary_change.path 160 = svn_fs_x__string_table_builder_add(changes->builder, 161 change->path.data, 162 change->path.len); 163 164 /* copy-from information, if presence is indicated by FLAGS */ 165 if (SVN_IS_VALID_REVNUM(change->copyfrom_rev)) 166 { 167 binary_change.copyfrom_rev = change->copyfrom_rev; 168 binary_change.copyfrom_path 169 = svn_fs_x__string_table_builder_add(changes->builder, 170 change->copyfrom_path, 171 0); 172 } 173 else 174 { 175 binary_change.copyfrom_rev = SVN_INVALID_REVNUM; 176 binary_change.copyfrom_path = 0; 177 } 178 179 APR_ARRAY_PUSH(changes->changes, binary_change_t) = binary_change; 180 181 return SVN_NO_ERROR; 182} 183 184svn_error_t * 185svn_fs_x__changes_append_list(apr_size_t *list_index, 186 svn_fs_x__changes_t *changes, 187 apr_array_header_t *list) 188{ 189 int i; 190 191 /* CHANGES must be in 'builder' mode */ 192 SVN_ERR_ASSERT(changes->builder); 193 SVN_ERR_ASSERT(changes->paths == NULL); 194 195 /* simply append the list and all changes */ 196 for (i = 0; i < list->nelts; ++i) 197 append_change(changes, APR_ARRAY_IDX(list, i, svn_fs_x__change_t *)); 198 199 /* terminate the list by storing the next changes offset */ 200 APR_ARRAY_PUSH(changes->offsets, int) = changes->changes->nelts; 201 *list_index = (apr_size_t)(changes->offsets->nelts - 2); 202 203 return SVN_NO_ERROR; 204} 205 206apr_size_t 207svn_fs_x__changes_estimate_size(const svn_fs_x__changes_t *changes) 208{ 209 /* CHANGES must be in 'builder' mode */ 210 if (changes->builder == NULL) 211 return 0; 212 213 /* string table code makes its own prediction, 214 * changes should be < 10 bytes each, 215 * some static overhead should be assumed */ 216 return svn_fs_x__string_table_builder_estimate_size(changes->builder) 217 + changes->changes->nelts * 10 218 + 100; 219} 220 221svn_error_t * 222svn_fs_x__changes_get_list(apr_array_header_t **list, 223 const svn_fs_x__changes_t *changes, 224 apr_size_t idx, 225 apr_pool_t *pool) 226{ 227 int first; 228 int last; 229 int i; 230 231 /* CHANGES must be in 'finalized' mode */ 232 SVN_ERR_ASSERT(changes->builder == NULL); 233 SVN_ERR_ASSERT(changes->paths); 234 235 /* validate index */ 236 if (idx + 1 >= (apr_size_t)changes->offsets->nelts) 237 return svn_error_createf(SVN_ERR_FS_CONTAINER_INDEX, NULL, 238 apr_psprintf(pool, 239 _("Changes list index %%%s" 240 " exceeds container size %%d"), 241 APR_SIZE_T_FMT), 242 idx, changes->offsets->nelts - 1); 243 244 /* range of changes to return */ 245 first = APR_ARRAY_IDX(changes->offsets, (int)idx, int); 246 last = APR_ARRAY_IDX(changes->offsets, (int)idx + 1, int); 247 248 /* construct result */ 249 *list = apr_array_make(pool, last - first, sizeof(svn_fs_x__change_t*)); 250 for (i = first; i < last; ++i) 251 { 252 const binary_change_t *binary_change 253 = &APR_ARRAY_IDX(changes->changes, i, binary_change_t); 254 255 /* convert BINARY_CHANGE into a standard FSX svn_fs_x__change_t */ 256 svn_fs_x__change_t *change = apr_pcalloc(pool, sizeof(*change)); 257 change->path.data = svn_fs_x__string_table_get(changes->paths, 258 binary_change->path, 259 &change->path.len, 260 pool); 261 262 if (binary_change->noderev_id.change_set != SVN_FS_X__INVALID_CHANGE_SET) 263 change->noderev_id = binary_change->noderev_id; 264 265 change->change_kind = (svn_fs_path_change_kind_t) 266 ((binary_change->flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT); 267 change->text_mod = (binary_change->flags & CHANGE_TEXT_MOD) != 0; 268 change->prop_mod = (binary_change->flags & CHANGE_PROP_MOD) != 0; 269 change->node_kind = (svn_node_kind_t) 270 ((binary_change->flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT); 271 272 change->copyfrom_rev = binary_change->copyfrom_rev; 273 change->copyfrom_known = TRUE; 274 if (SVN_IS_VALID_REVNUM(binary_change->copyfrom_rev)) 275 change->copyfrom_path 276 = svn_fs_x__string_table_get(changes->paths, 277 binary_change->copyfrom_path, 278 NULL, 279 pool); 280 281 /* add it to the result */ 282 APR_ARRAY_PUSH(*list, svn_fs_x__change_t*) = change; 283 } 284 285 return SVN_NO_ERROR; 286} 287 288svn_error_t * 289svn_fs_x__write_changes_container(svn_stream_t *stream, 290 const svn_fs_x__changes_t *changes, 291 apr_pool_t *scratch_pool) 292{ 293 int i; 294 295 string_table_t *paths = changes->paths 296 ? changes->paths 297 : svn_fs_x__string_table_create(changes->builder, 298 scratch_pool); 299 300 svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool); 301 302 /* one top-level stream for each array */ 303 svn_packed__int_stream_t *offsets_stream 304 = svn_packed__create_int_stream(root, TRUE, FALSE); 305 svn_packed__int_stream_t *changes_stream 306 = svn_packed__create_int_stream(root, FALSE, FALSE); 307 308 /* structure the CHANGES_STREAM such we can extract much of the redundancy 309 * from the binary_change_t structs */ 310 svn_packed__create_int_substream(changes_stream, TRUE, FALSE); 311 svn_packed__create_int_substream(changes_stream, TRUE, FALSE); 312 svn_packed__create_int_substream(changes_stream, TRUE, TRUE); 313 svn_packed__create_int_substream(changes_stream, TRUE, FALSE); 314 svn_packed__create_int_substream(changes_stream, TRUE, TRUE); 315 svn_packed__create_int_substream(changes_stream, TRUE, FALSE); 316 317 /* serialize offsets array */ 318 for (i = 0; i < changes->offsets->nelts; ++i) 319 svn_packed__add_uint(offsets_stream, 320 APR_ARRAY_IDX(changes->offsets, i, int)); 321 322 /* serialize changes array */ 323 for (i = 0; i < changes->changes->nelts; ++i) 324 { 325 const binary_change_t *change 326 = &APR_ARRAY_IDX(changes->changes, i, binary_change_t); 327 328 svn_packed__add_uint(changes_stream, change->flags); 329 svn_packed__add_uint(changes_stream, change->path); 330 331 svn_packed__add_int(changes_stream, change->copyfrom_rev); 332 svn_packed__add_uint(changes_stream, change->copyfrom_path); 333 334 svn_packed__add_int(changes_stream, change->noderev_id.change_set); 335 svn_packed__add_uint(changes_stream, change->noderev_id.number); 336 } 337 338 /* write to disk */ 339 SVN_ERR(svn_fs_x__write_string_table(stream, paths, scratch_pool)); 340 SVN_ERR(svn_packed__data_write(stream, root, scratch_pool)); 341 342 return SVN_NO_ERROR; 343} 344 345svn_error_t * 346svn_fs_x__read_changes_container(svn_fs_x__changes_t **changes_p, 347 svn_stream_t *stream, 348 apr_pool_t *result_pool, 349 apr_pool_t *scratch_pool) 350{ 351 apr_size_t i; 352 apr_size_t count; 353 354 svn_fs_x__changes_t *changes = apr_pcalloc(result_pool, sizeof(*changes)); 355 356 svn_packed__data_root_t *root; 357 svn_packed__int_stream_t *offsets_stream; 358 svn_packed__int_stream_t *changes_stream; 359 360 /* read from disk */ 361 SVN_ERR(svn_fs_x__read_string_table(&changes->paths, stream, 362 result_pool, scratch_pool)); 363 364 SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool)); 365 offsets_stream = svn_packed__first_int_stream(root); 366 changes_stream = svn_packed__next_int_stream(offsets_stream); 367 368 /* read offsets array */ 369 count = svn_packed__int_count(offsets_stream); 370 changes->offsets = apr_array_make(result_pool, (int)count, sizeof(int)); 371 for (i = 0; i < count; ++i) 372 APR_ARRAY_PUSH(changes->offsets, int) 373 = (int)svn_packed__get_uint(offsets_stream); 374 375 /* read changes array */ 376 count 377 = svn_packed__int_count(svn_packed__first_int_substream(changes_stream)); 378 changes->changes 379 = apr_array_make(result_pool, (int)count, sizeof(binary_change_t)); 380 for (i = 0; i < count; ++i) 381 { 382 binary_change_t change; 383 384 change.flags = (int)svn_packed__get_uint(changes_stream); 385 change.path = (apr_size_t)svn_packed__get_uint(changes_stream); 386 387 change.copyfrom_rev = (svn_revnum_t)svn_packed__get_int(changes_stream); 388 change.copyfrom_path = (apr_size_t)svn_packed__get_uint(changes_stream); 389 390 change.noderev_id.change_set = svn_packed__get_int(changes_stream); 391 change.noderev_id.number = svn_packed__get_uint(changes_stream); 392 393 APR_ARRAY_PUSH(changes->changes, binary_change_t) = change; 394 } 395 396 *changes_p = changes; 397 398 return SVN_NO_ERROR; 399} 400 401svn_error_t * 402svn_fs_x__serialize_changes_container(void **data, 403 apr_size_t *data_len, 404 void *in, 405 apr_pool_t *pool) 406{ 407 svn_fs_x__changes_t *changes = in; 408 svn_stringbuf_t *serialized; 409 410 /* make a guesstimate on the size of the serialized data. Erring on the 411 * low side will cause the serializer to re-alloc its buffer. */ 412 apr_size_t size 413 = changes->changes->elt_size * changes->changes->nelts 414 + changes->offsets->elt_size * changes->offsets->nelts 415 + 10 * changes->changes->elt_size 416 + 100; 417 418 /* serialize array header and all its elements */ 419 svn_temp_serializer__context_t *context 420 = svn_temp_serializer__init(changes, sizeof(*changes), size, pool); 421 422 /* serialize sub-structures */ 423 svn_fs_x__serialize_string_table(context, &changes->paths); 424 svn_fs_x__serialize_apr_array(context, &changes->changes); 425 svn_fs_x__serialize_apr_array(context, &changes->offsets); 426 427 /* return the serialized result */ 428 serialized = svn_temp_serializer__get(context); 429 430 *data = serialized->data; 431 *data_len = serialized->len; 432 433 return SVN_NO_ERROR; 434} 435 436svn_error_t * 437svn_fs_x__deserialize_changes_container(void **out, 438 void *data, 439 apr_size_t data_len, 440 apr_pool_t *pool) 441{ 442 svn_fs_x__changes_t *changes = (svn_fs_x__changes_t *)data; 443 444 /* de-serialize sub-structures */ 445 svn_fs_x__deserialize_string_table(changes, &changes->paths); 446 svn_fs_x__deserialize_apr_array(changes, &changes->changes, pool); 447 svn_fs_x__deserialize_apr_array(changes, &changes->offsets, pool); 448 449 /* done */ 450 *out = changes; 451 452 return SVN_NO_ERROR; 453} 454 455svn_error_t * 456svn_fs_x__changes_get_list_func(void **out, 457 const void *data, 458 apr_size_t data_len, 459 void *baton, 460 apr_pool_t *pool) 461{ 462 int first; 463 int last; 464 int i; 465 apr_array_header_t *list; 466 467 apr_uint32_t idx = *(apr_uint32_t *)baton; 468 const svn_fs_x__changes_t *container = data; 469 470 /* resolve all the sub-container pointers we need */ 471 const string_table_t *paths 472 = svn_temp_deserializer__ptr(container, 473 (const void *const *)&container->paths); 474 const apr_array_header_t *serialized_offsets 475 = svn_temp_deserializer__ptr(container, 476 (const void *const *)&container->offsets); 477 const apr_array_header_t *serialized_changes 478 = svn_temp_deserializer__ptr(container, 479 (const void *const *)&container->changes); 480 const int *offsets 481 = svn_temp_deserializer__ptr(serialized_offsets, 482 (const void *const *)&serialized_offsets->elts); 483 const binary_change_t *changes 484 = svn_temp_deserializer__ptr(serialized_changes, 485 (const void *const *)&serialized_changes->elts); 486 487 /* validate index */ 488 if (idx + 1 >= (apr_size_t)serialized_offsets->nelts) 489 return svn_error_createf(SVN_ERR_FS_CONTAINER_INDEX, NULL, 490 _("Changes list index %u exceeds container " 491 "size %d"), 492 (unsigned)idx, serialized_offsets->nelts - 1); 493 494 /* range of changes to return */ 495 first = offsets[idx]; 496 last = offsets[idx+1]; 497 498 /* construct result */ 499 list = apr_array_make(pool, last - first, sizeof(svn_fs_x__change_t*)); 500 501 for (i = first; i < last; ++i) 502 { 503 const binary_change_t *binary_change = &changes[i]; 504 505 /* convert BINARY_CHANGE into a standard FSX svn_fs_x__change_t */ 506 svn_fs_x__change_t *change = apr_pcalloc(pool, sizeof(*change)); 507 change->path.data 508 = svn_fs_x__string_table_get_func(paths, binary_change->path, 509 &change->path.len, pool); 510 511 change->noderev_id = binary_change->noderev_id; 512 513 change->change_kind = (svn_fs_path_change_kind_t) 514 ((binary_change->flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT); 515 change->text_mod = (binary_change->flags & CHANGE_TEXT_MOD) != 0; 516 change->prop_mod = (binary_change->flags & CHANGE_PROP_MOD) != 0; 517 change->node_kind = (svn_node_kind_t) 518 ((binary_change->flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT); 519 520 change->copyfrom_rev = binary_change->copyfrom_rev; 521 change->copyfrom_known = TRUE; 522 if (SVN_IS_VALID_REVNUM(binary_change->copyfrom_rev)) 523 change->copyfrom_path 524 = svn_fs_x__string_table_get_func(paths, 525 binary_change->copyfrom_path, 526 NULL, 527 pool); 528 529 /* add it to the result */ 530 APR_ARRAY_PUSH(list, svn_fs_x__change_t*) = change; 531 } 532 533 *out = list; 534 535 return SVN_NO_ERROR; 536} 537