commit 96f5e8b328f93ac1abe4b49a7e73ecdaf7bb8526 from: Stefan Sperling date: Tue Jan 23 12:38:17 2018 UTC add support for delta chains; implement them for offset deltas commit - cecc778e888f28115f89b151312d6201a5f530fd commit + 96f5e8b328f93ac1abe4b49a7e73ecdaf7bb8526 blob - b85bd54d8416997549d793f8e47ea9dc6dc802ed blob + c25f0bf68b076236a834cec3f33f2b61af12ca14 --- include/got_error.h +++ include/got_error.h @@ -35,6 +35,7 @@ #define GOT_ERR_NO_OBJ 17 #define GOT_ERR_NOT_IMPL 18 #define GOT_ERR_OBJ_NOT_PACKED 19 +#define GOT_ERR_BAD_DELTA_CHAIN 20 static const struct got_error { int code; @@ -60,6 +61,7 @@ static const struct got_error { { GOT_ERR_NO_OBJ, "object not found" }, { GOT_ERR_NOT_IMPL, "feature not implemented" }, { GOT_ERR_OBJ_NOT_PACKED,"object is not packed" }, + { GOT_ERR_BAD_DELTA_CHAIN,"bad delta chain" }, }; const struct got_error * got_error(int code); blob - d7921f101a80ac0e5ff01abfb10b96c552c42d31 blob + 9c70b677f3a1b9e8dafc55e075a180cdf42e887d --- lib/delta.c +++ lib/delta.c @@ -17,6 +17,8 @@ #include #include +#include +#include #include #include @@ -26,7 +28,59 @@ #include "delta.h" +struct got_delta_base * +got_delta_base_open(const char *path_packfile, int type, off_t offset, + size_t size) +{ + struct got_delta_base *base; + + base = calloc(1, sizeof(*base)); + if (base == NULL) + return NULL; + + base->path_packfile = strdup(path_packfile); + if (base->path_packfile == NULL) { + free(base); + return NULL; + } + base->type = type; + base->offset = offset; + base->size = size; + return base; +} + +void +got_delta_base_close(struct got_delta_base *base) +{ + free(base->path_packfile); + free(base); + +} + const struct got_error * +got_delta_chain_get_base_type(int *type, struct got_delta_chain *deltas) +{ + struct got_delta_base *base; + int n = 0; + + /* Find the last base in the chain. It should be a plain object. */ + SIMPLEQ_FOREACH(base, &deltas->entries, entry) { + n++; + if (base->type == GOT_OBJ_TYPE_COMMIT || + base->type == GOT_OBJ_TYPE_TREE || + base->type == GOT_OBJ_TYPE_BLOB || + base->type == GOT_OBJ_TYPE_TAG) { + if (n != deltas->nentries) + return got_error(GOT_ERR_BAD_DELTA_CHAIN); + *type = base->type; + return NULL; + } + } + + return got_error(GOT_ERR_BAD_DELTA_CHAIN); +} + +const struct got_error * got_delta_apply(struct got_repository *repo, FILE *infile, size_t size, struct got_object *base_obj, FILE *outfile) { blob - 88d8a5df95209ae177089165c92a4ca8cb03fc70 blob + 62886c7c82e09b5d1c86b0ca6f0a878d32fdd799 --- lib/delta.h +++ lib/delta.h @@ -14,6 +14,23 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +struct got_delta_base { + SIMPLEQ_ENTRY(got_delta_base) entry; + char *path_packfile; + off_t offset; + int type; + size_t size; +}; + +struct got_delta_chain { + int nentries; + SIMPLEQ_HEAD(, got_delta_base) entries; +}; + +struct got_delta_base *got_delta_base_open(const char *, int, off_t, size_t); +void got_delta_base_close(struct got_delta_base *); +const struct got_error *got_delta_chain_get_base_type(int *, + struct got_delta_chain *) ; const struct got_error * got_delta_apply(struct got_repository *, FILE *, size_t, struct got_object *, FILE *); blob - 5ff0a64ea609322f8b19eb00050c8efb05c57fac blob + e3f1c9f9a937caec05aa78177ba1e2dd15b7efa5 --- lib/object.c +++ lib/object.c @@ -31,6 +31,7 @@ #include "got_repository.h" #include "got_sha1.h" #include "pack.h" +#include "delta.h" #include "object.h" #ifndef MIN @@ -71,12 +72,13 @@ got_object_get_type(struct got_object *obj) case GOT_OBJ_TYPE_BLOB: case GOT_OBJ_TYPE_TAG: return obj->type; - case GOT_OBJ_TYPE_REF_DELTA: - case GOT_OBJ_TYPE_OFFSET_DELTA: - return obj->base_type; + default: + abort(); + break; } - abort(); + /* not reached */ + return 0; } static void @@ -333,7 +335,16 @@ done: void got_object_close(struct got_object *obj) { - free(obj->path_packfile); + if (obj->flags & GOT_OBJ_FLAG_DELTIFIED) { + struct got_delta_base *base; + while (!SIMPLEQ_EMPTY(&obj->deltas.entries)) { + base = SIMPLEQ_FIRST(&obj->deltas.entries); + SIMPLEQ_REMOVE_HEAD(&obj->deltas.entries, entry); + got_delta_base_close(base); + } + } + if (obj->flags & GOT_OBJ_FLAG_PACKED) + free(obj->path_packfile); free(obj); } blob - 393b9418c56aafff75322d28585c875c169ec7ed blob + 7d64bfaba781aa3e3e2aa9f60b316106f3bc6bc6 --- lib/object.h +++ lib/object.h @@ -18,6 +18,7 @@ struct got_object { int type; int flags; #define GOT_OBJ_FLAG_PACKED 0x01 +#define GOT_OBJ_FLAG_DELTIFIED 0x02 size_t hdrlen; size_t size; @@ -25,10 +26,5 @@ struct got_object { char *path_packfile; /* if packed */ off_t pack_offset; /* if packed */ - - /* If type is OFFSET_DELTA: */ - int base_type; - uint64_t base_size; - off_t base_obj_offset; + struct got_delta_chain deltas; /* if deltified */ }; - blob - dc45c887d6105490d8412920d3598072c6f4170a blob + 6ffdffe8385a6d8f951907f6de530a8bcfb074fe --- lib/pack.c +++ lib/pack.c @@ -421,30 +421,35 @@ decode_negative_offset(int64_t *offset, size_t *len, F } static const struct got_error * -open_offset_delta_object(struct got_object **obj, struct got_repository *repo, - const char *path_packfile, FILE *packfile, struct got_object_id *id, - off_t offset, size_t tslen, size_t size) +parse_offset_delta(off_t *base_offset, FILE *packfile, off_t offset) { - const struct got_error *err = NULL; + const struct got_error *err; int64_t negoffset; size_t negofflen; - off_t base_obj_offset; - struct got_object *base_obj; - struct got_object_id base_id; - uint8_t base_type; - uint64_t base_size; - size_t base_tslen; err = decode_negative_offset(&negoffset, &negofflen, packfile); if (err) return err; /* Compute the base object's offset (must be in the same pack file). */ - base_obj_offset = (offset - negoffset); - if (base_obj_offset <= 0) + *base_offset = (offset - negoffset); + if (*base_offset <= 0) return got_error(GOT_ERR_BAD_PACKFILE); - if (fseeko(packfile, base_obj_offset, SEEK_SET) != 0) + return NULL; +} + +static const struct got_error * +resolve_delta_chain(struct got_delta_chain *deltas, FILE *packfile, + const char *path_packfile, off_t offset, size_t delta_size) +{ + const struct got_error *err = NULL; + uint8_t base_type; + uint64_t base_size; + size_t base_tslen; + struct got_delta_base *base; + + if (fseeko(packfile, offset, SEEK_SET) != 0) return got_error_from_errno(); err = decode_type_and_size(&base_type, &base_size, &base_tslen, @@ -452,43 +457,91 @@ open_offset_delta_object(struct got_object **obj, stru if (err) return err; - /* - * XXX We currently only support plain objects as a delta base, - * i.e. deltas cannot be chained. Is this a problem? - * If so, we would have to resolve a plain object base type here. - */ + base = got_delta_base_open(path_packfile, base_type, offset, + delta_size); + if (base == NULL) + return got_error(GOT_ERR_NO_MEM); + deltas->nentries++; + SIMPLEQ_INSERT_TAIL(&deltas->entries, base, entry); + /* In case of error below, base will be freed in got_object_close(). */ + switch (base_type) { case GOT_OBJ_TYPE_COMMIT: case GOT_OBJ_TYPE_TREE: case GOT_OBJ_TYPE_BLOB: case GOT_OBJ_TYPE_TAG: break; - case GOT_OBJ_TYPE_OFFSET_DELTA: + case GOT_OBJ_TYPE_OFFSET_DELTA: { + off_t next_offset; + err = parse_offset_delta(&next_offset, packfile, offset); + if (err) + return err; + /* Next offset must be in the same packfile. */ + err = resolve_delta_chain(deltas, packfile, path_packfile, + next_offset, base_size); + break; + } case GOT_OBJ_TYPE_REF_DELTA: default: return got_error(GOT_ERR_NOT_IMPL); } + + return err; +} + +static const struct got_error * +open_offset_delta_object(struct got_object **obj, + struct got_repository *repo, struct got_packidx_v2_hdr *packidx, + const char *path_packfile, FILE *packfile, struct got_object_id *id, + off_t offset, size_t tslen, size_t size) +{ + const struct got_error *err = NULL; + off_t base_offset; + struct got_object_id base_id; + uint8_t base_type; + int resolved_type; + uint64_t base_size; + size_t base_tslen; + err = parse_offset_delta(&base_offset, packfile, offset); + if (err) + return err; + *obj = calloc(1, sizeof(**obj)); if (*obj == NULL) return got_error(GOT_ERR_NO_MEM); - (*obj)->path_packfile = strdup(path_packfile); - if ((*obj)->path_packfile == NULL) { - free(*obj); - return got_error(GOT_ERR_NO_MEM); - } - (*obj)->type = GOT_OBJ_TYPE_OFFSET_DELTA; - (*obj)->flags = GOT_OBJ_FLAG_PACKED; + (*obj)->flags = 0; (*obj)->hdrlen = 0; - (*obj)->size = size; + (*obj)->size = 0; /* Not yet known because deltas aren't combined. */ memcpy(&(*obj)->id, id, sizeof((*obj)->id)); (*obj)->pack_offset = offset + tslen; - (*obj)->base_type = base_type; - (*obj)->base_size = base_size; - (*obj)->base_obj_offset = base_obj_offset; - return NULL; + (*obj)->path_packfile = strdup(path_packfile); + if ((*obj)->path_packfile == NULL) { + err = got_error(GOT_ERR_NO_MEM); + goto done; + } + (*obj)->flags |= GOT_OBJ_FLAG_PACKED; + + SIMPLEQ_INIT(&(*obj)->deltas.entries); + (*obj)->flags |= GOT_OBJ_FLAG_DELTIFIED; + err = resolve_delta_chain(&(*obj)->deltas, packfile, path_packfile, + base_offset, size); + if (err) + goto done; + + err = got_delta_chain_get_base_type(&resolved_type, &(*obj)->deltas); + if (err) + goto done; + (*obj)->type = resolved_type; + +done: + if (err) { + got_object_close(*obj); + *obj = NULL; + } + return err; } static const struct got_error * @@ -552,21 +605,18 @@ open_packed_object(struct got_object **obj, struct got break; case GOT_OBJ_TYPE_OFFSET_DELTA: - err = open_offset_delta_object(obj, repo, path_packfile, - packfile, id, offset, tslen, size); + err = open_offset_delta_object(obj, repo, packidx, + path_packfile, packfile, id, offset, tslen, size); break; case GOT_OBJ_TYPE_REF_DELTA: case GOT_OBJ_TYPE_TAG: - break; default: err = got_error(GOT_ERR_NOT_IMPL); goto done; } done: free(path_packfile); - if (err) - free(*obj); if (packfile && fclose(packfile) == -1 && err == 0) err = got_error_from_errno(); return err;