2 * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 #include <sys/types.h>
32 #include "got_error.h"
33 #include "got_object.h"
34 #include "got_opentemp.h"
37 #include "got_lib_sha1.h"
38 #include "got_lib_delta.h"
39 #include "got_lib_delta_cache.h"
40 #include "got_lib_inflate.h"
41 #include "got_lib_object.h"
42 #include "got_lib_object_parse.h"
43 #include "got_lib_privsep.h"
44 #include "got_lib_pack.h"
47 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
51 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
54 static const struct got_error
*
55 verify_fanout_table(uint32_t *fanout_table
)
59 for (i
= 0; i
< 0xff - 1; i
++) {
60 if (be32toh(fanout_table
[i
]) > be32toh(fanout_table
[i
+ 1]))
61 return got_error(GOT_ERR_BAD_PACKIDX
);
67 const struct got_error
*
68 got_packidx_init_hdr(struct got_packidx
*p
, int verify
, off_t packfile_size
)
70 const struct got_error
*err
= NULL
;
71 struct got_packidx_v2_hdr
*h
;
73 uint8_t sha1
[SHA1_DIGEST_LENGTH
];
74 size_t nobj
, len_fanout
, len_ids
, offset
, remain
;
84 if (remain
< sizeof(*h
->magic
)) {
85 err
= got_error(GOT_ERR_BAD_PACKIDX
);
89 h
->magic
= (uint32_t *)(p
->map
+ offset
);
91 h
->magic
= malloc(sizeof(*h
->magic
));
92 if (h
->magic
== NULL
) {
93 err
= got_error_from_errno("malloc");
96 n
= read(p
->fd
, h
->magic
, sizeof(*h
->magic
));
98 err
= got_error_from_errno("read");
100 } else if (n
!= sizeof(*h
->magic
)) {
101 err
= got_error(GOT_ERR_BAD_PACKIDX
);
105 if (*h
->magic
!= htobe32(GOT_PACKIDX_V2_MAGIC
)) {
106 err
= got_error(GOT_ERR_BAD_PACKIDX
);
109 offset
+= sizeof(*h
->magic
);
110 remain
-= sizeof(*h
->magic
);
113 SHA1Update(&ctx
, (uint8_t *)h
->magic
, sizeof(*h
->magic
));
115 if (remain
< sizeof(*h
->version
)) {
116 err
= got_error(GOT_ERR_BAD_PACKIDX
);
120 h
->version
= (uint32_t *)(p
->map
+ offset
);
122 h
->version
= malloc(sizeof(*h
->version
));
123 if (h
->version
== NULL
) {
124 err
= got_error_from_errno("malloc");
127 n
= read(p
->fd
, h
->version
, sizeof(*h
->version
));
129 err
= got_error_from_errno("read");
131 } else if (n
!= sizeof(*h
->version
)) {
132 err
= got_error(GOT_ERR_BAD_PACKIDX
);
136 if (*h
->version
!= htobe32(GOT_PACKIDX_VERSION
)) {
137 err
= got_error(GOT_ERR_BAD_PACKIDX
);
140 offset
+= sizeof(*h
->version
);
141 remain
-= sizeof(*h
->version
);
144 SHA1Update(&ctx
, (uint8_t *)h
->version
, sizeof(*h
->version
));
147 sizeof(*h
->fanout_table
) * GOT_PACKIDX_V2_FANOUT_TABLE_ITEMS
;
148 if (remain
< len_fanout
) {
149 err
= got_error(GOT_ERR_BAD_PACKIDX
);
153 h
->fanout_table
= (uint32_t *)(p
->map
+ offset
);
155 h
->fanout_table
= malloc(len_fanout
);
156 if (h
->fanout_table
== NULL
) {
157 err
= got_error_from_errno("malloc");
160 n
= read(p
->fd
, h
->fanout_table
, len_fanout
);
162 err
= got_error_from_errno("read");
164 } else if (n
!= len_fanout
) {
165 err
= got_error(GOT_ERR_BAD_PACKIDX
);
169 err
= verify_fanout_table(h
->fanout_table
);
173 SHA1Update(&ctx
, (uint8_t *)h
->fanout_table
, len_fanout
);
174 offset
+= len_fanout
;
175 remain
-= len_fanout
;
177 nobj
= be32toh(h
->fanout_table
[0xff]);
178 len_ids
= nobj
* sizeof(*h
->sorted_ids
);
179 if (len_ids
<= nobj
|| len_ids
> remain
) {
180 err
= got_error(GOT_ERR_BAD_PACKIDX
);
185 (struct got_packidx_object_id
*)((uint8_t*)(p
->map
+ offset
));
187 h
->sorted_ids
= malloc(len_ids
);
188 if (h
->sorted_ids
== NULL
) {
189 err
= got_error(GOT_ERR_BAD_PACKIDX
);
192 n
= read(p
->fd
, h
->sorted_ids
, len_ids
);
194 err
= got_error_from_errno("read");
195 else if (n
!= len_ids
) {
196 err
= got_error(GOT_ERR_BAD_PACKIDX
);
201 SHA1Update(&ctx
, (uint8_t *)h
->sorted_ids
, len_ids
);
205 if (remain
< nobj
* sizeof(*h
->crc32
)) {
206 err
= got_error(GOT_ERR_BAD_PACKIDX
);
210 h
->crc32
= (uint32_t *)((uint8_t*)(p
->map
+ offset
));
212 h
->crc32
= malloc(nobj
* sizeof(*h
->crc32
));
213 if (h
->crc32
== NULL
) {
214 err
= got_error_from_errno("malloc");
217 n
= read(p
->fd
, h
->crc32
, nobj
* sizeof(*h
->crc32
));
219 err
= got_error_from_errno("read");
220 else if (n
!= nobj
* sizeof(*h
->crc32
)) {
221 err
= got_error(GOT_ERR_BAD_PACKIDX
);
226 SHA1Update(&ctx
, (uint8_t *)h
->crc32
, nobj
* sizeof(*h
->crc32
));
227 remain
-= nobj
* sizeof(*h
->crc32
);
228 offset
+= nobj
* sizeof(*h
->crc32
);
230 if (remain
< nobj
* sizeof(*h
->offsets
)) {
231 err
= got_error(GOT_ERR_BAD_PACKIDX
);
235 h
->offsets
= (uint32_t *)((uint8_t*)(p
->map
+ offset
));
237 h
->offsets
= malloc(nobj
* sizeof(*h
->offsets
));
238 if (h
->offsets
== NULL
) {
239 err
= got_error_from_errno("malloc");
242 n
= read(p
->fd
, h
->offsets
, nobj
* sizeof(*h
->offsets
));
244 err
= got_error_from_errno("read");
245 else if (n
!= nobj
* sizeof(*h
->offsets
)) {
246 err
= got_error(GOT_ERR_BAD_PACKIDX
);
251 SHA1Update(&ctx
, (uint8_t *)h
->offsets
,
252 nobj
* sizeof(*h
->offsets
));
253 remain
-= nobj
* sizeof(*h
->offsets
);
254 offset
+= nobj
* sizeof(*h
->offsets
);
256 /* Large file offsets are contained only in files > 2GB. */
257 if (verify
|| packfile_size
> 0x7fffffff) {
258 for (i
= 0; i
< nobj
; i
++) {
259 uint32_t o
= h
->offsets
[i
];
260 if (o
& htobe32(GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX
))
264 if (p
->nlargeobj
== 0)
266 else if (packfile_size
<= 0x7fffffff) {
267 err
= got_error(GOT_ERR_BAD_PACKIDX
);
271 if (remain
< p
->nlargeobj
* sizeof(*h
->large_offsets
)) {
272 err
= got_error(GOT_ERR_BAD_PACKIDX
);
276 h
->large_offsets
= (uint64_t *)((uint8_t*)(p
->map
+ offset
));
278 h
->large_offsets
= malloc(p
->nlargeobj
*
279 sizeof(*h
->large_offsets
));
280 if (h
->large_offsets
== NULL
) {
281 err
= got_error_from_errno("malloc");
284 n
= read(p
->fd
, h
->large_offsets
,
285 p
->nlargeobj
* sizeof(*h
->large_offsets
));
287 err
= got_error_from_errno("read");
288 else if (n
!= p
->nlargeobj
* sizeof(*h
->large_offsets
)) {
289 err
= got_error(GOT_ERR_BAD_PACKIDX
);
294 SHA1Update(&ctx
, (uint8_t*)h
->large_offsets
,
295 p
->nlargeobj
* sizeof(*h
->large_offsets
));
296 remain
-= p
->nlargeobj
* sizeof(*h
->large_offsets
);
297 offset
+= p
->nlargeobj
* sizeof(*h
->large_offsets
);
300 if (remain
< sizeof(*h
->trailer
)) {
301 err
= got_error(GOT_ERR_BAD_PACKIDX
);
306 (struct got_packidx_trailer
*)((uint8_t*)(p
->map
+ offset
));
308 h
->trailer
= malloc(sizeof(*h
->trailer
));
309 if (h
->trailer
== NULL
) {
310 err
= got_error_from_errno("malloc");
313 n
= read(p
->fd
, h
->trailer
, sizeof(*h
->trailer
));
315 err
= got_error_from_errno("read");
316 else if (n
!= sizeof(*h
->trailer
)) {
317 err
= got_error(GOT_ERR_BAD_PACKIDX
);
322 SHA1Update(&ctx
, h
->trailer
->packfile_sha1
, SHA1_DIGEST_LENGTH
);
323 SHA1Final(sha1
, &ctx
);
324 if (memcmp(h
->trailer
->packidx_sha1
, sha1
,
325 SHA1_DIGEST_LENGTH
) != 0)
326 err
= got_error(GOT_ERR_PACKIDX_CSUM
);
332 const struct got_error
*
333 got_packidx_open(struct got_packidx
**packidx
,
334 int dir_fd
, const char *relpath
, int verify
)
336 const struct got_error
*err
= NULL
;
337 struct got_packidx
*p
= NULL
;
339 struct stat idx_sb
, pack_sb
;
343 err
= got_packidx_get_packfile_path(&pack_relpath
, relpath
);
348 * Ensure that a corresponding pack file exists.
349 * Some Git repositories have this problem. Git seems to ignore
350 * the existence of lonely pack index files but we do not.
352 if (fstatat(dir_fd
, pack_relpath
, &pack_sb
, 0) == -1) {
353 if (errno
== ENOENT
) {
354 err
= got_error_fmt(GOT_ERR_LONELY_PACKIDX
,
357 err
= got_error_from_errno2("fstatat", pack_relpath
);
361 p
= calloc(1, sizeof(*p
));
363 err
= got_error_from_errno("calloc");
367 p
->fd
= openat(dir_fd
, relpath
, O_RDONLY
| O_NOFOLLOW
| O_CLOEXEC
);
369 err
= got_error_from_errno2("openat", relpath
);
374 if (fstat(p
->fd
, &idx_sb
) != 0) {
375 err
= got_error_from_errno2("fstat", relpath
);
380 p
->len
= idx_sb
.st_size
;
381 if (p
->len
< sizeof(p
->hdr
)) {
382 err
= got_error(GOT_ERR_BAD_PACKIDX
);
388 p
->path_packidx
= strdup(relpath
);
389 if (p
->path_packidx
== NULL
) {
390 err
= got_error_from_errno("strdup");
394 #ifndef GOT_PACK_NO_MMAP
395 p
->map
= mmap(NULL
, p
->len
, PROT_READ
, MAP_PRIVATE
, p
->fd
, 0);
396 if (p
->map
== MAP_FAILED
) {
397 if (errno
!= ENOMEM
) {
398 err
= got_error_from_errno("mmap");
401 p
->map
= NULL
; /* fall back to read(2) */
405 err
= got_packidx_init_hdr(p
, verify
, pack_sb
.st_size
);
409 got_packidx_close(p
);
416 const struct got_error
*
417 got_packidx_close(struct got_packidx
*packidx
)
419 const struct got_error
*err
= NULL
;
421 free(packidx
->path_packidx
);
423 if (munmap(packidx
->map
, packidx
->len
) == -1)
424 err
= got_error_from_errno("munmap");
426 free(packidx
->hdr
.magic
);
427 free(packidx
->hdr
.version
);
428 free(packidx
->hdr
.fanout_table
);
429 free(packidx
->hdr
.sorted_ids
);
430 free(packidx
->hdr
.crc32
);
431 free(packidx
->hdr
.offsets
);
432 free(packidx
->hdr
.large_offsets
);
433 free(packidx
->hdr
.trailer
);
435 if (close(packidx
->fd
) == -1 && err
== NULL
)
436 err
= got_error_from_errno("close");
442 const struct got_error
*
443 got_packidx_get_packfile_path(char **path_packfile
, const char *path_packidx
)
447 /* Packfile path contains ".pack" instead of ".idx", so add one byte. */
448 size
= strlen(path_packidx
) + 2;
449 if (size
< GOT_PACKFILE_NAMELEN
+ 1)
450 return got_error_path(path_packidx
, GOT_ERR_BAD_PATH
);
452 *path_packfile
= malloc(size
);
453 if (*path_packfile
== NULL
)
454 return got_error_from_errno("malloc");
456 /* Copy up to and excluding ".idx". */
457 if (strlcpy(*path_packfile
, path_packidx
,
458 size
- strlen(GOT_PACKIDX_SUFFIX
) - 1) >= size
)
459 return got_error(GOT_ERR_NO_SPACE
);
461 if (strlcat(*path_packfile
, GOT_PACKFILE_SUFFIX
, size
) >= size
)
462 return got_error(GOT_ERR_NO_SPACE
);
468 got_packidx_get_object_offset(struct got_packidx
*packidx
, int idx
)
470 uint32_t offset
= be32toh(packidx
->hdr
.offsets
[idx
]);
471 if (offset
& GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX
) {
473 idx
= offset
& GOT_PACKIDX_OFFSET_VAL_MASK
;
474 if (idx
< 0 || idx
>= packidx
->nlargeobj
||
475 packidx
->hdr
.large_offsets
== NULL
)
477 loffset
= be64toh(packidx
->hdr
.large_offsets
[idx
]);
478 return (loffset
> INT64_MAX
? -1 : (off_t
)loffset
);
480 return (off_t
)(offset
& GOT_PACKIDX_OFFSET_VAL_MASK
);
484 got_packidx_get_object_idx(struct got_packidx
*packidx
,
485 struct got_object_id
*id
)
487 u_int8_t id0
= id
->sha1
[0];
488 uint32_t totobj
= be32toh(packidx
->hdr
.fanout_table
[0xff]);
489 int left
= 0, right
= totobj
- 1;
492 left
= be32toh(packidx
->hdr
.fanout_table
[id0
- 1]);
494 while (left
<= right
) {
495 struct got_packidx_object_id
*oid
;
498 i
= ((left
+ right
) / 2);
499 oid
= &packidx
->hdr
.sorted_ids
[i
];
500 cmp
= memcmp(id
->sha1
, oid
->sha1
, SHA1_DIGEST_LENGTH
);
512 const struct got_error
*
513 got_packidx_match_id_str_prefix(struct got_object_id_queue
*matched_ids
,
514 struct got_packidx
*packidx
, const char *id_str_prefix
)
516 const struct got_error
*err
= NULL
;
518 uint32_t totobj
= be32toh(packidx
->hdr
.fanout_table
[0xff]);
520 size_t prefix_len
= strlen(id_str_prefix
);
521 struct got_packidx_object_id
*oid
;
524 STAILQ_INIT(matched_ids
);
527 return got_error_path(id_str_prefix
, GOT_ERR_BAD_OBJ_ID_STR
);
529 hex
[0] = id_str_prefix
[0];
530 hex
[1] = id_str_prefix
[1];
532 if (!got_parse_xdigit(&id0
, hex
))
533 return got_error_path(id_str_prefix
, GOT_ERR_BAD_OBJ_ID_STR
);
536 i
= be32toh(packidx
->hdr
.fanout_table
[id0
- 1]);
537 oid
= &packidx
->hdr
.sorted_ids
[i
];
538 while (i
< totobj
&& oid
->sha1
[0] == id0
) {
539 char id_str
[SHA1_DIGEST_STRING_LENGTH
];
540 struct got_object_qid
*qid
;
543 if (!got_sha1_digest_to_str(oid
->sha1
, id_str
, sizeof(id_str
)))
544 return got_error(GOT_ERR_NO_SPACE
);
546 cmp
= strncmp(id_str
, id_str_prefix
, prefix_len
);
548 oid
= &packidx
->hdr
.sorted_ids
[++i
];
553 err
= got_object_qid_alloc_partial(&qid
);
556 memcpy(qid
->id
->sha1
, oid
->sha1
, SHA1_DIGEST_LENGTH
);
557 STAILQ_INSERT_TAIL(matched_ids
, qid
, entry
);
559 oid
= &packidx
->hdr
.sorted_ids
[++i
];
563 got_object_id_queue_free(matched_ids
);
567 static const struct got_error
*
568 pack_stop_privsep_child(struct got_pack
*pack
)
570 const struct got_error
*err
= NULL
;
572 if (pack
->privsep_child
== NULL
)
575 err
= got_privsep_send_stop(pack
->privsep_child
->imsg_fd
);
578 err
= got_privsep_wait_for_child(pack
->privsep_child
->pid
);
579 if (close(pack
->privsep_child
->imsg_fd
) == -1 && err
== NULL
)
580 err
= got_error_from_errno("close");
581 imsg_clear(pack
->privsep_child
->ibuf
);
582 free(pack
->privsep_child
->ibuf
);
583 free(pack
->privsep_child
);
584 pack
->privsep_child
= NULL
;
588 const struct got_error
*
589 got_pack_close(struct got_pack
*pack
)
591 const struct got_error
*err
= NULL
;
593 err
= pack_stop_privsep_child(pack
);
594 if (pack
->map
&& munmap(pack
->map
, pack
->filesize
) == -1 && !err
)
595 err
= got_error_from_errno("munmap");
596 if (pack
->fd
!= -1 && close(pack
->fd
) == -1 && err
== NULL
)
597 err
= got_error_from_errno("close");
599 free(pack
->path_packfile
);
600 pack
->path_packfile
= NULL
;
602 if (pack
->delta_cache
) {
603 got_delta_cache_free(pack
->delta_cache
);
604 pack
->delta_cache
= NULL
;
610 const struct got_error
*
611 got_pack_parse_object_type_and_size(uint8_t *type
, uint64_t *size
, size_t *len
,
612 struct got_pack
*pack
, off_t offset
)
622 if (offset
>= pack
->filesize
)
623 return got_error(GOT_ERR_PACK_OFFSET
);
626 mapoff
= (size_t)offset
;
628 if (lseek(pack
->fd
, offset
, SEEK_SET
) == -1)
629 return got_error_from_errno("lseek");
633 /* We do not support size values which don't fit in 64 bit. */
635 return got_error(GOT_ERR_NO_SPACE
);
638 if (mapoff
+ sizeof(sizeN
) >= pack
->filesize
)
639 return got_error(GOT_ERR_BAD_PACKFILE
);
640 sizeN
= *(pack
->map
+ mapoff
);
641 mapoff
+= sizeof(sizeN
);
643 ssize_t n
= read(pack
->fd
, &sizeN
, sizeof(sizeN
));
645 return got_error_from_errno("read");
646 if (n
!= sizeof(sizeN
))
647 return got_error(GOT_ERR_BAD_PACKFILE
);
649 *len
+= sizeof(sizeN
);
652 t
= (sizeN
& GOT_PACK_OBJ_SIZE0_TYPE_MASK
) >>
653 GOT_PACK_OBJ_SIZE0_TYPE_MASK_SHIFT
;
654 s
= (sizeN
& GOT_PACK_OBJ_SIZE0_VAL_MASK
);
656 size_t shift
= 4 + 7 * (i
- 1);
657 s
|= ((sizeN
& GOT_PACK_OBJ_SIZE_VAL_MASK
) << shift
);
660 } while (sizeN
& GOT_PACK_OBJ_SIZE_MORE
);
667 static const struct got_error
*
668 open_plain_object(struct got_object
**obj
, struct got_object_id
*id
,
669 uint8_t type
, off_t offset
, size_t size
, int idx
)
671 *obj
= calloc(1, sizeof(**obj
));
673 return got_error_from_errno("calloc");
676 (*obj
)->flags
= GOT_OBJ_FLAG_PACKED
;
677 (*obj
)->pack_idx
= idx
;
680 memcpy(&(*obj
)->id
, id
, sizeof((*obj
)->id
));
681 (*obj
)->pack_offset
= offset
;
686 static const struct got_error
*
687 parse_negative_offset(int64_t *offset
, size_t *len
, struct got_pack
*pack
,
698 /* We do not support offset values which don't fit in 64 bit. */
700 return got_error(GOT_ERR_NO_SPACE
);
704 mapoff
= (size_t)delta_offset
+ *len
;
705 if (mapoff
+ sizeof(offN
) >= pack
->filesize
)
706 return got_error(GOT_ERR_PACK_OFFSET
);
707 offN
= *(pack
->map
+ mapoff
);
710 n
= read(pack
->fd
, &offN
, sizeof(offN
));
712 return got_error_from_errno("read");
713 if (n
!= sizeof(offN
))
714 return got_error(GOT_ERR_BAD_PACKFILE
);
716 *len
+= sizeof(offN
);
719 o
= (offN
& GOT_PACK_OBJ_DELTA_OFF_VAL_MASK
);
723 o
+= (offN
& GOT_PACK_OBJ_DELTA_OFF_VAL_MASK
);
726 } while (offN
& GOT_PACK_OBJ_DELTA_OFF_MORE
);
732 const struct got_error
*
733 got_pack_parse_offset_delta(off_t
*base_offset
, size_t *len
,
734 struct got_pack
*pack
, off_t offset
, int tslen
)
736 const struct got_error
*err
;
742 err
= parse_negative_offset(&negoffset
, &negofflen
, pack
,
747 /* Compute the base object's offset (must be in the same pack file). */
748 *base_offset
= (offset
- negoffset
);
749 if (*base_offset
<= 0)
750 return got_error(GOT_ERR_BAD_PACKFILE
);
756 static const struct got_error
*
757 read_delta_data(uint8_t **delta_buf
, size_t *delta_len
,
758 size_t delta_data_offset
, struct got_pack
*pack
)
760 const struct got_error
*err
= NULL
;
763 if (delta_data_offset
>= pack
->filesize
)
764 return got_error(GOT_ERR_PACK_OFFSET
);
765 err
= got_inflate_to_mem_mmap(delta_buf
, delta_len
,
766 NULL
, NULL
, pack
->map
, delta_data_offset
,
767 pack
->filesize
- delta_data_offset
);
769 if (lseek(pack
->fd
, delta_data_offset
, SEEK_SET
) == -1)
770 return got_error_from_errno("lseek");
771 err
= got_inflate_to_mem_fd(delta_buf
, delta_len
, NULL
,
777 static const struct got_error
*
778 add_delta(struct got_delta_chain
*deltas
, off_t delta_offset
, size_t tslen
,
779 int delta_type
, size_t delta_size
, size_t delta_data_offset
)
781 struct got_delta
*delta
;
783 delta
= got_delta_open(delta_offset
, tslen
, delta_type
, delta_size
,
786 return got_error_from_errno("got_delta_open");
787 /* delta is freed in got_object_close() */
789 STAILQ_INSERT_HEAD(&deltas
->entries
, delta
, entry
);
793 static const struct got_error
*
794 resolve_offset_delta(struct got_delta_chain
*deltas
,
795 struct got_packidx
*packidx
, struct got_pack
*pack
, off_t delta_offset
,
796 size_t tslen
, int delta_type
, size_t delta_size
, unsigned int recursion
)
799 const struct got_error
*err
;
804 off_t delta_data_offset
;
807 err
= got_pack_parse_offset_delta(&base_offset
, &consumed
, pack
,
808 delta_offset
, tslen
);
812 delta_data_offset
= delta_offset
+ tslen
+ consumed
;
813 if (delta_data_offset
>= pack
->filesize
)
814 return got_error(GOT_ERR_PACK_OFFSET
);
816 if (pack
->map
== NULL
) {
817 delta_data_offset
= lseek(pack
->fd
, 0, SEEK_CUR
);
818 if (delta_data_offset
== -1)
819 return got_error_from_errno("lseek");
822 err
= add_delta(deltas
, delta_offset
, tslen
, delta_type
, delta_size
,
827 /* An offset delta must be in the same packfile. */
828 if (base_offset
>= pack
->filesize
)
829 return got_error(GOT_ERR_PACK_OFFSET
);
831 err
= got_pack_parse_object_type_and_size(&base_type
, &base_size
,
832 &base_tslen
, pack
, base_offset
);
836 return got_pack_resolve_delta_chain(deltas
, packidx
, pack
, base_offset
,
837 base_tslen
, base_type
, base_size
, recursion
- 1);
840 const struct got_error
*
841 got_pack_parse_ref_delta(struct got_object_id
*id
,
842 struct got_pack
*pack
, off_t delta_offset
, int tslen
)
845 size_t mapoff
= delta_offset
+ tslen
;
846 if (mapoff
+ sizeof(*id
) >= pack
->filesize
)
847 return got_error(GOT_ERR_PACK_OFFSET
);
848 memcpy(id
, pack
->map
+ mapoff
, sizeof(*id
));
851 n
= read(pack
->fd
, id
, sizeof(*id
));
853 return got_error_from_errno("read");
854 if (n
!= sizeof(*id
))
855 return got_error(GOT_ERR_BAD_PACKFILE
);
861 static const struct got_error
*
862 resolve_ref_delta(struct got_delta_chain
*deltas
, struct got_packidx
*packidx
,
863 struct got_pack
*pack
, off_t delta_offset
, size_t tslen
, int delta_type
,
864 size_t delta_size
, unsigned int recursion
)
866 const struct got_error
*err
;
867 struct got_object_id id
;
873 off_t delta_data_offset
;
875 if (delta_offset
+ tslen
>= pack
->filesize
)
876 return got_error(GOT_ERR_PACK_OFFSET
);
878 err
= got_pack_parse_ref_delta(&id
, pack
, delta_offset
, tslen
);
882 delta_data_offset
= delta_offset
+ tslen
+ sizeof(id
);
884 delta_data_offset
= lseek(pack
->fd
, 0, SEEK_CUR
);
885 if (delta_data_offset
== -1)
886 return got_error_from_errno("lseek");
889 err
= add_delta(deltas
, delta_offset
, tslen
, delta_type
, delta_size
,
894 /* Delta base must be in the same pack file. */
895 idx
= got_packidx_get_object_idx(packidx
, &id
);
897 return got_error(GOT_ERR_NO_OBJ
);
899 base_offset
= got_packidx_get_object_offset(packidx
, idx
);
900 if (base_offset
== (uint64_t)-1)
901 return got_error(GOT_ERR_BAD_PACKIDX
);
903 if (base_offset
>= pack
->filesize
)
904 return got_error(GOT_ERR_PACK_OFFSET
);
906 err
= got_pack_parse_object_type_and_size(&base_type
, &base_size
,
907 &base_tslen
, pack
, base_offset
);
911 return got_pack_resolve_delta_chain(deltas
, packidx
, pack
, base_offset
,
912 base_tslen
, base_type
, base_size
, recursion
- 1);
915 const struct got_error
*
916 got_pack_resolve_delta_chain(struct got_delta_chain
*deltas
,
917 struct got_packidx
*packidx
, struct got_pack
*pack
, off_t delta_offset
,
918 size_t tslen
, int delta_type
, size_t delta_size
, unsigned int recursion
)
920 const struct got_error
*err
= NULL
;
922 if (--recursion
== 0)
923 return got_error(GOT_ERR_RECURSION
);
925 switch (delta_type
) {
926 case GOT_OBJ_TYPE_COMMIT
:
927 case GOT_OBJ_TYPE_TREE
:
928 case GOT_OBJ_TYPE_BLOB
:
929 case GOT_OBJ_TYPE_TAG
:
930 /* Plain types are the final delta base. Recursion ends. */
931 err
= add_delta(deltas
, delta_offset
, tslen
, delta_type
,
934 case GOT_OBJ_TYPE_OFFSET_DELTA
:
935 err
= resolve_offset_delta(deltas
, packidx
, pack
,
936 delta_offset
, tslen
, delta_type
, delta_size
, recursion
- 1);
938 case GOT_OBJ_TYPE_REF_DELTA
:
939 err
= resolve_ref_delta(deltas
, packidx
, pack
,
940 delta_offset
, tslen
, delta_type
, delta_size
, recursion
- 1);
943 return got_error(GOT_ERR_OBJ_TYPE
);
949 static const struct got_error
*
950 open_delta_object(struct got_object
**obj
, struct got_packidx
*packidx
,
951 struct got_pack
*pack
, struct got_object_id
*id
, off_t offset
,
952 size_t tslen
, int delta_type
, size_t delta_size
, int idx
)
954 const struct got_error
*err
= NULL
;
957 *obj
= calloc(1, sizeof(**obj
));
959 return got_error_from_errno("calloc");
963 (*obj
)->size
= 0; /* Not known because deltas aren't applied yet. */
964 memcpy(&(*obj
)->id
, id
, sizeof((*obj
)->id
));
965 (*obj
)->pack_offset
= offset
+ tslen
;
967 STAILQ_INIT(&(*obj
)->deltas
.entries
);
968 (*obj
)->flags
|= GOT_OBJ_FLAG_DELTIFIED
;
969 (*obj
)->flags
|= GOT_OBJ_FLAG_PACKED
;
970 (*obj
)->pack_idx
= idx
;
972 err
= got_pack_resolve_delta_chain(&(*obj
)->deltas
, packidx
, pack
,
973 offset
, tslen
, delta_type
, delta_size
,
974 GOT_DELTA_CHAIN_RECURSION_MAX
);
978 err
= got_delta_chain_get_base_type(&resolved_type
, &(*obj
)->deltas
);
981 (*obj
)->type
= resolved_type
;
984 got_object_close(*obj
);
990 const struct got_error
*
991 got_packfile_open_object(struct got_object
**obj
, struct got_pack
*pack
,
992 struct got_packidx
*packidx
, int idx
, struct got_object_id
*id
)
994 const struct got_error
*err
= NULL
;
1002 offset
= got_packidx_get_object_offset(packidx
, idx
);
1003 if (offset
== (uint64_t)-1)
1004 return got_error(GOT_ERR_BAD_PACKIDX
);
1006 err
= got_pack_parse_object_type_and_size(&type
, &size
, &tslen
,
1012 case GOT_OBJ_TYPE_COMMIT
:
1013 case GOT_OBJ_TYPE_TREE
:
1014 case GOT_OBJ_TYPE_BLOB
:
1015 case GOT_OBJ_TYPE_TAG
:
1016 err
= open_plain_object(obj
, id
, type
, offset
+ tslen
,
1019 case GOT_OBJ_TYPE_OFFSET_DELTA
:
1020 case GOT_OBJ_TYPE_REF_DELTA
:
1021 err
= open_delta_object(obj
, packidx
, pack
, id
, offset
,
1022 tslen
, type
, size
, idx
);
1025 err
= got_error(GOT_ERR_OBJ_TYPE
);
1032 const struct got_error
*
1033 got_pack_get_delta_chain_max_size(uint64_t *max_size
,
1034 struct got_delta_chain
*deltas
, struct got_pack
*pack
)
1036 struct got_delta
*delta
;
1037 uint64_t base_size
= 0, result_size
= 0;
1040 STAILQ_FOREACH(delta
, &deltas
->entries
, entry
) {
1041 /* Plain object types are the delta base. */
1042 if (delta
->type
!= GOT_OBJ_TYPE_COMMIT
&&
1043 delta
->type
!= GOT_OBJ_TYPE_TREE
&&
1044 delta
->type
!= GOT_OBJ_TYPE_BLOB
&&
1045 delta
->type
!= GOT_OBJ_TYPE_TAG
) {
1046 const struct got_error
*err
;
1051 got_delta_cache_get(&delta_buf
, &delta_len
,
1052 pack
->delta_cache
, delta
->data_offset
);
1053 if (delta_buf
== NULL
) {
1055 err
= read_delta_data(&delta_buf
, &delta_len
,
1056 delta
->data_offset
, pack
);
1059 err
= got_delta_cache_add(pack
->delta_cache
,
1060 delta
->data_offset
, delta_buf
, delta_len
);
1063 else if (err
->code
!= GOT_ERR_NO_SPACE
) {
1068 err
= got_delta_get_sizes(&base_size
, &result_size
,
1069 delta_buf
, delta_len
);
1075 base_size
= delta
->size
;
1076 if (base_size
> *max_size
)
1077 *max_size
= base_size
;
1078 if (result_size
> *max_size
)
1079 *max_size
= result_size
;
1085 const struct got_error
*
1086 got_pack_get_max_delta_object_size(uint64_t *size
, struct got_object
*obj
,
1087 struct got_pack
*pack
)
1089 if ((obj
->flags
& GOT_OBJ_FLAG_DELTIFIED
) == 0)
1090 return got_error(GOT_ERR_OBJ_TYPE
);
1092 return got_pack_get_delta_chain_max_size(size
, &obj
->deltas
, pack
);
1095 const struct got_error
*
1096 got_pack_dump_delta_chain_to_file(size_t *result_size
,
1097 struct got_delta_chain
*deltas
, struct got_pack
*pack
, FILE *outfile
,
1098 FILE *base_file
, FILE *accum_file
)
1100 const struct got_error
*err
= NULL
;
1101 struct got_delta
*delta
;
1102 uint8_t *base_buf
= NULL
, *accum_buf
= NULL
, *delta_buf
;
1103 size_t base_bufsz
= 0, accum_size
= 0, delta_len
;
1109 if (STAILQ_EMPTY(&deltas
->entries
))
1110 return got_error(GOT_ERR_BAD_DELTA_CHAIN
);
1112 /* We process small enough files entirely in memory for speed. */
1113 err
= got_pack_get_delta_chain_max_size(&max_size
, deltas
, pack
);
1116 if (max_size
< GOT_DELTA_RESULT_SIZE_CACHED_MAX
) {
1117 accum_buf
= malloc(max_size
);
1118 if (accum_buf
== NULL
)
1119 return got_error_from_errno("malloc");
1123 if (fseeko(base_file
, 0L, SEEK_SET
) == -1)
1124 return got_error_from_errno("fseeko");
1125 if (fseeko(accum_file
, 0L, SEEK_SET
) == -1)
1126 return got_error_from_errno("fseeko");
1129 /* Deltas are ordered in ascending order. */
1130 STAILQ_FOREACH(delta
, &deltas
->entries
, entry
) {
1134 off_t delta_data_offset
;
1136 /* Plain object types are the delta base. */
1137 if (delta
->type
!= GOT_OBJ_TYPE_COMMIT
&&
1138 delta
->type
!= GOT_OBJ_TYPE_TREE
&&
1139 delta
->type
!= GOT_OBJ_TYPE_BLOB
&&
1140 delta
->type
!= GOT_OBJ_TYPE_TAG
) {
1141 err
= got_error(GOT_ERR_BAD_DELTA_CHAIN
);
1145 delta_data_offset
= delta
->offset
+ delta
->tslen
;
1146 if (delta_data_offset
>= pack
->filesize
) {
1147 err
= got_error(GOT_ERR_PACK_OFFSET
);
1150 if (pack
->map
== NULL
) {
1151 if (lseek(pack
->fd
, delta_data_offset
, SEEK_SET
)
1153 err
= got_error_from_errno("lseek");
1159 mapoff
= (size_t)delta_data_offset
;
1160 err
= got_inflate_to_file_mmap(
1161 &base_bufsz
, NULL
, NULL
, pack
->map
,
1162 mapoff
, pack
->filesize
- mapoff
,
1165 err
= got_inflate_to_file_fd(
1166 &base_bufsz
, NULL
, NULL
, pack
->fd
,
1170 mapoff
= (size_t)delta_data_offset
;
1171 err
= got_inflate_to_mem_mmap(&base_buf
,
1172 &base_bufsz
, NULL
, NULL
,
1174 pack
->filesize
- mapoff
);
1176 err
= got_inflate_to_mem_fd(&base_buf
,
1177 &base_bufsz
, NULL
, NULL
, max_size
,
1188 got_delta_cache_get(&delta_buf
, &delta_len
,
1189 pack
->delta_cache
, delta
->data_offset
);
1190 if (delta_buf
== NULL
) {
1192 err
= read_delta_data(&delta_buf
, &delta_len
,
1193 delta
->data_offset
, pack
);
1196 err
= got_delta_cache_add(pack
->delta_cache
,
1197 delta
->data_offset
, delta_buf
, delta_len
);
1200 else if (err
->code
!= GOT_ERR_NO_SPACE
) {
1206 err
= got_delta_apply_in_mem(base_buf
, base_bufsz
,
1207 delta_buf
, delta_len
, accum_buf
,
1208 &accum_size
, max_size
);
1211 err
= got_delta_apply(base_file
, delta_buf
,
1213 /* Final delta application writes to output file. */
1214 ++n
< deltas
->nentries
? accum_file
: outfile
,
1222 if (n
< deltas
->nentries
) {
1223 /* Accumulated delta becomes the new base. */
1225 uint8_t *tmp
= accum_buf
;
1227 * Base buffer switches roles with accumulation
1228 * buffer. Ensure it can hold the largest
1229 * result in the delta chain. The initial
1230 * allocation might have been smaller.
1232 if (base_bufsz
< max_size
) {
1234 p
= reallocarray(base_buf
, 1, max_size
);
1236 err
= got_error_from_errno(
1241 base_bufsz
= max_size
;
1243 accum_buf
= base_buf
;
1246 FILE *tmp
= accum_file
;
1247 accum_file
= base_file
;
1258 size_t len
= fwrite(accum_buf
, 1, accum_size
, outfile
);
1260 if (len
!= accum_size
)
1261 err
= got_ferror(outfile
, GOT_ERR_IO
);
1265 *result_size
= accum_size
;
1269 const struct got_error
*
1270 got_pack_dump_delta_chain_to_mem(uint8_t **outbuf
, size_t *outlen
,
1271 struct got_delta_chain
*deltas
, struct got_pack
*pack
)
1273 const struct got_error
*err
= NULL
;
1274 struct got_delta
*delta
;
1275 uint8_t *base_buf
= NULL
, *accum_buf
= NULL
, *delta_buf
;
1276 size_t base_bufsz
= 0, accum_size
= 0, delta_len
;
1283 if (STAILQ_EMPTY(&deltas
->entries
))
1284 return got_error(GOT_ERR_BAD_DELTA_CHAIN
);
1286 err
= got_pack_get_delta_chain_max_size(&max_size
, deltas
, pack
);
1289 accum_buf
= malloc(max_size
);
1290 if (accum_buf
== NULL
)
1291 return got_error_from_errno("malloc");
1293 /* Deltas are ordered in ascending order. */
1294 STAILQ_FOREACH(delta
, &deltas
->entries
, entry
) {
1297 size_t delta_data_offset
;
1299 /* Plain object types are the delta base. */
1300 if (delta
->type
!= GOT_OBJ_TYPE_COMMIT
&&
1301 delta
->type
!= GOT_OBJ_TYPE_TREE
&&
1302 delta
->type
!= GOT_OBJ_TYPE_BLOB
&&
1303 delta
->type
!= GOT_OBJ_TYPE_TAG
) {
1304 err
= got_error(GOT_ERR_BAD_DELTA_CHAIN
);
1308 delta_data_offset
= delta
->offset
+ delta
->tslen
;
1309 if (delta_data_offset
>= pack
->filesize
) {
1310 err
= got_error(GOT_ERR_PACK_OFFSET
);
1314 size_t mapoff
= (size_t)delta_data_offset
;
1315 err
= got_inflate_to_mem_mmap(&base_buf
,
1316 &base_bufsz
, NULL
, NULL
, pack
->map
,
1317 mapoff
, pack
->filesize
- mapoff
);
1319 if (lseek(pack
->fd
, delta_data_offset
, SEEK_SET
)
1321 err
= got_error_from_errno("lseek");
1324 err
= got_inflate_to_mem_fd(&base_buf
,
1325 &base_bufsz
, NULL
, NULL
, max_size
,
1334 got_delta_cache_get(&delta_buf
, &delta_len
,
1335 pack
->delta_cache
, delta
->data_offset
);
1336 if (delta_buf
== NULL
) {
1338 err
= read_delta_data(&delta_buf
, &delta_len
,
1339 delta
->data_offset
, pack
);
1342 err
= got_delta_cache_add(pack
->delta_cache
,
1343 delta
->data_offset
, delta_buf
, delta_len
);
1346 else if (err
->code
!= GOT_ERR_NO_SPACE
) {
1351 err
= got_delta_apply_in_mem(base_buf
, base_bufsz
,
1352 delta_buf
, delta_len
, accum_buf
,
1353 &accum_size
, max_size
);
1360 if (n
< deltas
->nentries
) {
1361 /* Accumulated delta becomes the new base. */
1362 uint8_t *tmp
= accum_buf
;
1364 * Base buffer switches roles with accumulation buffer.
1365 * Ensure it can hold the largest result in the delta
1366 * chain. Initial allocation might have been smaller.
1368 if (base_bufsz
< max_size
) {
1370 p
= reallocarray(base_buf
, 1, max_size
);
1372 err
= got_error_from_errno(
1377 base_bufsz
= max_size
;
1379 accum_buf
= base_buf
;
1391 *outbuf
= accum_buf
;
1392 *outlen
= accum_size
;
1397 const struct got_error
*
1398 got_packfile_extract_object(struct got_pack
*pack
, struct got_object
*obj
,
1399 FILE *outfile
, FILE *base_file
, FILE *accum_file
)
1401 const struct got_error
*err
= NULL
;
1403 if ((obj
->flags
& GOT_OBJ_FLAG_PACKED
) == 0)
1404 return got_error(GOT_ERR_OBJ_NOT_PACKED
);
1406 if ((obj
->flags
& GOT_OBJ_FLAG_DELTIFIED
) == 0) {
1407 if (obj
->pack_offset
>= pack
->filesize
)
1408 return got_error(GOT_ERR_PACK_OFFSET
);
1411 size_t mapoff
= (size_t)obj
->pack_offset
;
1412 err
= got_inflate_to_file_mmap(&obj
->size
, NULL
, NULL
,
1413 pack
->map
, mapoff
, pack
->filesize
- mapoff
,
1416 if (lseek(pack
->fd
, obj
->pack_offset
, SEEK_SET
) == -1)
1417 return got_error_from_errno("lseek");
1418 err
= got_inflate_to_file_fd(&obj
->size
, NULL
, NULL
,
1422 err
= got_pack_dump_delta_chain_to_file(&obj
->size
,
1423 &obj
->deltas
, pack
, outfile
, base_file
, accum_file
);
1428 const struct got_error
*
1429 got_packfile_extract_object_to_mem(uint8_t **buf
, size_t *len
,
1430 struct got_object
*obj
, struct got_pack
*pack
)
1432 const struct got_error
*err
= NULL
;
1434 if ((obj
->flags
& GOT_OBJ_FLAG_PACKED
) == 0)
1435 return got_error(GOT_ERR_OBJ_NOT_PACKED
);
1437 if ((obj
->flags
& GOT_OBJ_FLAG_DELTIFIED
) == 0) {
1438 if (obj
->pack_offset
>= pack
->filesize
)
1439 return got_error(GOT_ERR_PACK_OFFSET
);
1441 size_t mapoff
= (size_t)obj
->pack_offset
;
1442 err
= got_inflate_to_mem_mmap(buf
, len
, NULL
, NULL
,
1443 pack
->map
, mapoff
, pack
->filesize
- mapoff
);
1445 if (lseek(pack
->fd
, obj
->pack_offset
, SEEK_SET
) == -1)
1446 return got_error_from_errno("lseek");
1447 err
= got_inflate_to_mem_fd(buf
, len
, NULL
, NULL
,
1448 obj
->size
, pack
->fd
);
1451 err
= got_pack_dump_delta_chain_to_mem(buf
, len
, &obj
->deltas
,