Re: [PATCH 12/12] index-pack: resolve v4 one-base trees
On Sun, Sep 8, 2013 at 10:28 AM, Nicolas Pitre wrote:
>> @@ -794,6 +799,83 @@ static void *unpack_raw_entry(struct object_entry *obj,
>> return data;
>> }
>>
>> +static void *patch_one_base_tree(const struct object_entry *src,
>> + const unsigned char *src_buf,
>> + const unsigned char *delta_buf,
>> + unsigned long delta_size,
>> + unsigned long *dst_size)
>> +{
>> + unsigned int nr;
>> + const unsigned char *last_base = NULL;
>> + struct strbuf sb = STRBUF_INIT;
>> + const unsigned char *p = delta_buf;
>> +
>> + nr = decode_varint(&p);
>> + while (nr && p < delta_buf + delta_size) {
>> + unsigned int copy_start_or_path = decode_varint(&p);
>> + if (copy_start_or_path & 1) { /* copy_start */
>> + struct tree_desc desc;
>> + struct name_entry entry;
>> + unsigned int copy_count = decode_varint(&p);
>> + unsigned int copy_start = copy_start_or_path >> 1;
>> + if (!src)
>> + die("we are not supposed to copy from another
>> tree!");
>> + if (copy_count & 1) { /* first delta */
>> + unsigned int id = decode_varint(&p);
>> + if (!id) {
>> + last_base = p;
>> + p += 20;
>> + } else
>> + last_base = sha1_table + (id - 1) * 20;
>> + if (hashcmp(last_base, src->idx.sha1))
>> + die(_("bad tree base in
>> patch_one_base_tree"));
>> + } else if (!last_base)
>> + die(_("bad copy count index in
>> patch_one_base_tree"));
>> + copy_count >>= 1;
>> + if (!copy_count)
>> + die(_("bad copy count index in
>> patch_one_base_tree"));
>> + nr -= copy_count;
>> +
>> + init_tree_desc(&desc, src_buf, src->size);
>> + while (tree_entry(&desc, &entry)) {
>> + if (copy_start)
>> + copy_start--;
>> + else if (copy_count) {
>> + strbuf_addf(&sb, "%o %s%c",
>> entry.mode, entry.path, '\0');
>> + strbuf_add(&sb, entry.sha1, 20);
>> + copy_count--;
>> + } else
>> + break;
>> + }
>> + } else {/* path */
>> + unsigned int path_idx = copy_start_or_path >> 1;
>> + const unsigned char *path;
>> + unsigned mode;
>> + unsigned int id;
>> + const unsigned char *entry_sha1;
>> +
>> + if (path_idx >= path_dict->nb_entries)
>> + die(_("bad path index in unpack_tree_v4"));
>> + id = decode_varint(&p);
>> + if (!id) {
>> + entry_sha1 = p;
>> + p += 20;
>> + } else
>> + entry_sha1 = sha1_table + (id - 1) * 20;
>
> You should verify that id doesn't overflow the sha1 table here.
> Similarly in other places.
I think it's unnecessary. All trees must have been checked by
unpack_tree_v4() in the first pass. Overflow should be caught there if
found.
--
Duy
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 12/12] index-pack: resolve v4 one-base trees
On Sat, 7 Sep 2013, Nguyễn Thái Ngọc Duy wrote:
> This is the most common case for delta trees. In fact it's the only
> kind that's produced by packv4-create. It fits well in the way
> index-pack resolves deltas and benefits from threading (the set of
> objects depending on this base does not overlap with the set of
> objects depending on another base)
>
> Multi-base trees will be probably processed differently.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy
> ---
> builtin/index-pack.c | 194
> ++-
> 1 file changed, 178 insertions(+), 16 deletions(-)
>
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index 1fa74f4..4a24bc3 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -12,6 +12,8 @@
> #include "streaming.h"
> #include "thread-utils.h"
> #include "packv4-parse.h"
> +#include "varint.h"
> +#include "tree-walk.h"
>
> static const char index_pack_usage[] =
> "git index-pack [-v] [-o ] [--keep | --keep=] [--verify]
> [--strict] ( | --stdin [--fix-thin] [])";
> @@ -38,8 +40,8 @@ struct base_data {
> struct object_entry *obj;
> void *data;
> unsigned long size;
> - int ref_first, ref_last;
> - int ofs_first, ofs_last;
> + int ref_first, ref_last, tree_first;
> + int ofs_first, ofs_last, tree_last;
> };
>
> #if !defined(NO_PTHREADS) && defined(NO_THREAD_SAFE_PREAD)
> @@ -437,6 +439,7 @@ static struct base_data *alloc_base_data(void)
> memset(base, 0, sizeof(*base));
> base->ref_last = -1;
> base->ofs_last = -1;
> + base->tree_last = -1;
> return base;
> }
>
> @@ -670,6 +673,8 @@ static void *unpack_tree_v4(struct object_entry *obj,
> }
>
> if (last_base) {
> + if (nr_deltas - delta_start > 1)
> + die("sorry guys, multi-base trees are not supported
> yet");
> strbuf_release(&sb);
> return NULL;
> } else {
> @@ -794,6 +799,83 @@ static void *unpack_raw_entry(struct object_entry *obj,
> return data;
> }
>
> +static void *patch_one_base_tree(const struct object_entry *src,
> + const unsigned char *src_buf,
> + const unsigned char *delta_buf,
> + unsigned long delta_size,
> + unsigned long *dst_size)
> +{
> + unsigned int nr;
> + const unsigned char *last_base = NULL;
> + struct strbuf sb = STRBUF_INIT;
> + const unsigned char *p = delta_buf;
> +
> + nr = decode_varint(&p);
> + while (nr && p < delta_buf + delta_size) {
> + unsigned int copy_start_or_path = decode_varint(&p);
> + if (copy_start_or_path & 1) { /* copy_start */
> + struct tree_desc desc;
> + struct name_entry entry;
> + unsigned int copy_count = decode_varint(&p);
> + unsigned int copy_start = copy_start_or_path >> 1;
> + if (!src)
> + die("we are not supposed to copy from another
> tree!");
> + if (copy_count & 1) { /* first delta */
> + unsigned int id = decode_varint(&p);
> + if (!id) {
> + last_base = p;
> + p += 20;
> + } else
> + last_base = sha1_table + (id - 1) * 20;
> + if (hashcmp(last_base, src->idx.sha1))
> + die(_("bad tree base in
> patch_one_base_tree"));
> + } else if (!last_base)
> + die(_("bad copy count index in
> patch_one_base_tree"));
> + copy_count >>= 1;
> + if (!copy_count)
> + die(_("bad copy count index in
> patch_one_base_tree"));
> + nr -= copy_count;
> +
> + init_tree_desc(&desc, src_buf, src->size);
> + while (tree_entry(&desc, &entry)) {
> + if (copy_start)
> + copy_start--;
> + else if (copy_count) {
> + strbuf_addf(&sb, "%o %s%c", entry.mode,
> entry.path, '\0');
> + strbuf_add(&sb, entry.sha1, 20);
> + copy_count--;
> + } else
> + break;
> + }
> + } else {/* path */
> + unsigned int path_idx = copy_start_or_path >> 1;
> + const unsigned char *path;
> + unsigned mode;
> + unsigned int id;
> + const unsigned char *entry_sha1;
> +
> +
[PATCH 12/12] index-pack: resolve v4 one-base trees
This is the most common case for delta trees. In fact it's the only
kind that's produced by packv4-create. It fits well in the way
index-pack resolves deltas and benefits from threading (the set of
objects depending on this base does not overlap with the set of
objects depending on another base)
Multi-base trees will be probably processed differently.
Signed-off-by: Nguyễn Thái Ngọc Duy
---
builtin/index-pack.c | 194 ++-
1 file changed, 178 insertions(+), 16 deletions(-)
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 1fa74f4..4a24bc3 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -12,6 +12,8 @@
#include "streaming.h"
#include "thread-utils.h"
#include "packv4-parse.h"
+#include "varint.h"
+#include "tree-walk.h"
static const char index_pack_usage[] =
"git index-pack [-v] [-o ] [--keep | --keep=] [--verify]
[--strict] ( | --stdin [--fix-thin] [])";
@@ -38,8 +40,8 @@ struct base_data {
struct object_entry *obj;
void *data;
unsigned long size;
- int ref_first, ref_last;
- int ofs_first, ofs_last;
+ int ref_first, ref_last, tree_first;
+ int ofs_first, ofs_last, tree_last;
};
#if !defined(NO_PTHREADS) && defined(NO_THREAD_SAFE_PREAD)
@@ -437,6 +439,7 @@ static struct base_data *alloc_base_data(void)
memset(base, 0, sizeof(*base));
base->ref_last = -1;
base->ofs_last = -1;
+ base->tree_last = -1;
return base;
}
@@ -670,6 +673,8 @@ static void *unpack_tree_v4(struct object_entry *obj,
}
if (last_base) {
+ if (nr_deltas - delta_start > 1)
+ die("sorry guys, multi-base trees are not supported
yet");
strbuf_release(&sb);
return NULL;
} else {
@@ -794,6 +799,83 @@ static void *unpack_raw_entry(struct object_entry *obj,
return data;
}
+static void *patch_one_base_tree(const struct object_entry *src,
+const unsigned char *src_buf,
+const unsigned char *delta_buf,
+unsigned long delta_size,
+unsigned long *dst_size)
+{
+ unsigned int nr;
+ const unsigned char *last_base = NULL;
+ struct strbuf sb = STRBUF_INIT;
+ const unsigned char *p = delta_buf;
+
+ nr = decode_varint(&p);
+ while (nr && p < delta_buf + delta_size) {
+ unsigned int copy_start_or_path = decode_varint(&p);
+ if (copy_start_or_path & 1) { /* copy_start */
+ struct tree_desc desc;
+ struct name_entry entry;
+ unsigned int copy_count = decode_varint(&p);
+ unsigned int copy_start = copy_start_or_path >> 1;
+ if (!src)
+ die("we are not supposed to copy from another
tree!");
+ if (copy_count & 1) { /* first delta */
+ unsigned int id = decode_varint(&p);
+ if (!id) {
+ last_base = p;
+ p += 20;
+ } else
+ last_base = sha1_table + (id - 1) * 20;
+ if (hashcmp(last_base, src->idx.sha1))
+ die(_("bad tree base in
patch_one_base_tree"));
+ } else if (!last_base)
+ die(_("bad copy count index in
patch_one_base_tree"));
+ copy_count >>= 1;
+ if (!copy_count)
+ die(_("bad copy count index in
patch_one_base_tree"));
+ nr -= copy_count;
+
+ init_tree_desc(&desc, src_buf, src->size);
+ while (tree_entry(&desc, &entry)) {
+ if (copy_start)
+ copy_start--;
+ else if (copy_count) {
+ strbuf_addf(&sb, "%o %s%c", entry.mode,
entry.path, '\0');
+ strbuf_add(&sb, entry.sha1, 20);
+ copy_count--;
+ } else
+ break;
+ }
+ } else {/* path */
+ unsigned int path_idx = copy_start_or_path >> 1;
+ const unsigned char *path;
+ unsigned mode;
+ unsigned int id;
+ const unsigned char *entry_sha1;
+
+ if (path_idx >= path_dict->nb_entries)
+ die(_("bad path index in unpack_tree_v4"));
+ id
