{"thread":{"id":"1382","subject":"[RFC PATCH 0/2] Parallel pull core","startedAt":"2005-08-01T01:11:25Z","lastAt":"2005-08-01T01:32:46Z","messageCount":3,"participants":["barkalow@iabervon.org"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"6694","messageId":"Pine.LNX.4.62.0507312055030.23721@iabervon.org","threadId":"1382","inReplyTo":null,"subject":"[RFC PATCH 0/2] Parallel pull core","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-01T01:11:25Z","receivedAt":"2005-08-01T01:11:25Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This series makes the core of the pull programs parallel. It should not \nactually make any difference yet. It arranges to call prefetch() for each \nobject as soon as it is determined to be needed, and then call fetch() on \neach object once there is nothing left to prefetch. By implementing \nprefetch(), an implementation can make additional requests while waiting \nfor the data from the earlier ones to come in. Additionally, fetch() will \nbe called in the same order that prefetch() was called, so the \nimplementation can just make a series of requests and get responses.\n\nIf anyone else is also interested in working on this, it could go into \n-pu; I've tested it reasonably well, and I'm pretty sure that it doesn't \nhave any effect until the implementations are changed to have prefetch() \ndo something. I'm working on support for it in ssh-pull, and haven't \nstarted looking at http-pull support.\n\n 1: Adds support to the struct object code to produce struct objects when \n    the type is unknown and the content is unavailable; this allocates \n    memory for the union of the supported types, so it is slightly less \n    efficient, but allows the pull code to track objects it doesn't know \n    anything about (such as the targets to tags).\n 2: Parallelizes the pull algorithm.\n\n\t-Daniel\n"},{"id":"6695","messageId":"Pine.LNX.4.62.0507312112360.23721@iabervon.org","threadId":"1382","inReplyTo":"Pine.LNX.4.62.0507312055030.23721@iabervon.org","subject":"[PATCH 1/2] Support for making struct objects for absent objects of unknown type","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-01T01:29:39Z","receivedAt":"2005-08-01T01:29:39Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This adds support for calling lookup_object_type() with NULL for the type, \nwhich will cause it to allocate enough memory for the largest type. This \nallows struct object_lists for objects that need to be fetched to find out \nwhat they are.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n object.c |   45 ++++++++++++++++++++++++++++++++++++++++++++-\n object.h |    8 ++++++++\n tree.h   |    1 +\n 3 files changed, 53 insertions(+), 1 deletions(-)\n\n6ed7f76e658c02cb2539a52813fe20d3fd9aa250\ndiff --git a/object.c b/object.c\n--- a/object.c\n+++ b/object.c\n@@ -99,7 +99,9 @@ void mark_reachable(struct object *obj, \n \n struct object *lookup_object_type(const unsigned char *sha1, const char *type)\n {\n-\tif (!strcmp(type, blob_type)) {\n+\tif (!type) {\n+\t\treturn lookup_unknown_object(sha1);\n+\t} else if (!strcmp(type, blob_type)) {\n \t\treturn &lookup_blob(sha1)->object;\n \t} else if (!strcmp(type, tree_type)) {\n \t\treturn &lookup_tree(sha1)->object;\n@@ -113,6 +115,27 @@ struct object *lookup_object_type(const \n \t}\n }\n \n+union any_object {\n+\tstruct object object;\n+\tstruct commit commit;\n+\tstruct tree tree;\n+\tstruct blob blob;\n+\tstruct tag tag;\n+};\n+\n+struct object *lookup_unknown_object(const unsigned char *sha1)\n+{\n+\tstruct object *obj = lookup_object(sha1);\n+\tif (!obj) {\n+\t\tunion any_object *ret = xmalloc(sizeof(*ret));\n+\t\tmemset(ret, 0, sizeof(*ret));\n+\t\tcreated_object(sha1, &ret->object);\n+\t\tret->object.type = NULL;\n+\t\treturn &ret->object;\n+\t}\n+\treturn obj;\n+}\n+\n struct object *parse_object(const unsigned char *sha1)\n {\n \tunsigned long size;\n@@ -150,3 +173,23 @@ struct object *parse_object(const unsign\n \t}\n \treturn NULL;\n }\n+\n+struct object_list *object_list_insert(struct object *item,\n+\t\t\t\t       struct object_list **list_p)\n+{\n+\tstruct object_list *new_list = xmalloc(sizeof(struct object_list));\n+        new_list->item = item;\n+        new_list->next = *list_p;\n+        *list_p = new_list;\n+        return new_list;\n+}\n+\n+unsigned object_list_length(struct object_list *list)\n+{\n+\tunsigned ret = 0;\n+\twhile (list) {\n+\t\tlist = list->next;\n+\t\tret++;\n+\t}\n+\treturn ret;\n+}\ndiff --git a/object.h b/object.h\n--- a/object.h\n+++ b/object.h\n@@ -31,8 +31,16 @@ void created_object(const unsigned char \n /** Returns the object, having parsed it to find out what it is. **/\n struct object *parse_object(const unsigned char *sha1);\n \n+/** Returns the object, with potentially excess memory allocated. **/\n+struct object *lookup_unknown_object(const unsigned  char *sha1);\n+\n void add_ref(struct object *refer, struct object *target);\n \n void mark_reachable(struct object *obj, unsigned int mask);\n \n+struct object_list *object_list_insert(struct object *item, \n+\t\t\t\t       struct object_list **list_p);\n+\n+unsigned object_list_length(struct object_list *list);\n+\n #endif /* OBJECT_H */\ndiff --git a/tree.h b/tree.h\n--- a/tree.h\n+++ b/tree.h\n@@ -14,6 +14,7 @@ struct tree_entry_list {\n \tunsigned int mode;\n \tchar *name;\n \tunion {\n+\t\tstruct object *any;\n \t\tstruct tree *tree;\n \t\tstruct blob *blob;\n \t} item;\n"},{"id":"6696","messageId":"Pine.LNX.4.62.0507312129430.23721@iabervon.org","threadId":"1382","inReplyTo":"Pine.LNX.4.62.0507312055030.23721@iabervon.org","subject":"[PATCH 2/2] Parallelize pull algorithm (no change to behavior).","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-01T01:32:46Z","receivedAt":"2005-08-01T01:32:46Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This patch makes the core pull algorithm request all of the objects it can \n(with prefetch()) before actually reading them (with fetch()). Future \npatches (in a later series) will make use of this behavior to have \nmultiple requests in flight at the same time, reducing the need for \nround-trips.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n http-pull.c  |    4 ++\n local-pull.c |    4 ++\n pull.c       |  128 ++++++++++++++++++++++++++++++++++------------------------\n pull.h       |    7 +++\n ssh-pull.c   |    4 ++\n 5 files changed, 93 insertions(+), 54 deletions(-)\n\n02aae5a570341c5b86b914d59732009f015800d8\ndiff --git a/http-pull.c b/http-pull.c\n--- a/http-pull.c\n+++ b/http-pull.c\n@@ -68,6 +68,10 @@ static size_t fwrite_sha1_file(void *ptr\n \treturn size;\n }\n \n+void prefetch(unsigned char *sha1)\n+{\n+}\n+\n int fetch(unsigned char *sha1)\n {\n \tchar *hex = sha1_to_hex(sha1);\ndiff --git a/local-pull.c b/local-pull.c\n--- a/local-pull.c\n+++ b/local-pull.c\n@@ -11,6 +11,10 @@ static int use_filecopy = 1;\n \n static char *path; /* \"Remote\" git repository */\n \n+void prefetch(unsigned char *sha1)\n+{\n+}\n+\n int fetch(unsigned char *sha1)\n {\n \tstatic int object_name_start = -1;\ndiff --git a/pull.c b/pull.c\n--- a/pull.c\n+++ b/pull.c\n@@ -17,11 +17,8 @@ int get_all = 0;\n int get_verbosely = 0;\n static unsigned char current_commit_sha1[20];\n \n-static const char commitS[] = \"commit\";\n-static const char treeS[] = \"tree\";\n-static const char blobS[] = \"blob\";\n-\n-void pull_say(const char *fmt, const char *hex) {\n+void pull_say(const char *fmt, const char *hex) \n+{\n \tif (get_verbosely)\n \t\tfprintf(stderr, fmt, hex);\n }\n@@ -48,93 +45,114 @@ static int make_sure_we_have_it(const ch\n \treturn status;\n }\n \n-static int process_unknown(unsigned char *sha1);\n+static int process(unsigned char *sha1, const char *type);\n \n-static int process_tree(unsigned char *sha1)\n+static int process_tree(struct tree *tree)\n {\n-\tstruct tree *tree = lookup_tree(sha1);\n \tstruct tree_entry_list *entries;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n \tfor (entries = tree->entries; entries; entries = entries->next) {\n-\t\tconst char *what = entries->directory ? treeS : blobS;\n-\t\tif (make_sure_we_have_it(what, entries->item.tree->object.sha1))\n+\t\tif (process(entries->item.any->sha1,\n+\t\t\t    entries->directory ? tree_type : blob_type))\n \t\t\treturn -1;\n-\t\tif (entries->directory) {\n-\t\t\tif (process_tree(entries->item.tree->object.sha1))\n-\t\t\t\treturn -1;\n-\t\t}\n \t}\n \treturn 0;\n }\n \n-static int process_commit(unsigned char *sha1)\n+static int process_commit(struct commit *commit)\n {\n-\tstruct commit *obj = lookup_commit(sha1);\n-\n-\tif (make_sure_we_have_it(commitS, sha1))\n+\tif (parse_commit(commit))\n \t\treturn -1;\n \n-\tif (parse_commit(obj))\n-\t\treturn -1;\n+\tmemcpy(current_commit_sha1, commit->object.sha1, 20);\n \n \tif (get_tree) {\n-\t\tif (make_sure_we_have_it(treeS, obj->tree->object.sha1))\n-\t\t\treturn -1;\n-\t\tif (process_tree(obj->tree->object.sha1))\n+\t\tif (process(commit->tree->object.sha1, tree_type))\n \t\t\treturn -1;\n \t\tif (!get_all)\n \t\t\tget_tree = 0;\n \t}\n \tif (get_history) {\n-\t\tstruct commit_list *parents = obj->parents;\n+\t\tstruct commit_list *parents = commit->parents;\n \t\tfor (; parents; parents = parents->next) {\n \t\t\tif (has_sha1_file(parents->item->object.sha1))\n \t\t\t\tcontinue;\n-\t\t\tif (make_sure_we_have_it(NULL,\n-\t\t\t\t\t\t parents->item->object.sha1)) {\n-\t\t\t\t/* The server might not have it, and\n-\t\t\t\t * we don't mind. \n-\t\t\t\t */\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t\tif (process_commit(parents->item->object.sha1))\n+\t\t\tif (process(parents->item->object.sha1,\n+\t\t\t\t    commit_type))\n \t\t\t\treturn -1;\n-\t\t\tmemcpy(current_commit_sha1, sha1, 20);\n \t\t}\n \t}\n \treturn 0;\n }\n \n-static int process_tag(unsigned char *sha1)\n+static int process_tag(struct tag *tag)\n {\n-\tstruct tag *obj = lookup_tag(sha1);\n-\n-\tif (parse_tag(obj))\n+\tif (parse_tag(tag))\n \t\treturn -1;\n-\treturn process_unknown(obj->tagged->sha1);\n+\treturn process(tag->tagged->sha1, NULL);\n }\n \n-static int process_unknown(unsigned char *sha1)\n+static struct object_list *process_queue = NULL;\n+static struct object_list **process_queue_end = &process_queue;\n+\n+static int process(unsigned char *sha1, const char *type)\n {\n \tstruct object *obj;\n-\tif (make_sure_we_have_it(\"object\", sha1))\n-\t\treturn -1;\n-\tobj = parse_object(sha1);\n-\tif (!obj)\n-\t\treturn error(\"Unable to parse object %s\", sha1_to_hex(sha1));\n-\tif (obj->type == commit_type)\n-\t\treturn process_commit(sha1);\n-\tif (obj->type == tree_type)\n-\t\treturn process_tree(sha1);\n-\tif (obj->type == blob_type)\n+\tif (has_sha1_file(sha1))\n \t\treturn 0;\n-\tif (obj->type == tag_type)\n-\t\treturn process_tag(sha1);\n-\treturn error(\"Unable to determine requirement of type %s for %s\",\n-\t\t     obj->type, sha1_to_hex(sha1));\n+\tobj = lookup_object_type(sha1, type);\n+\tobject_list_insert(obj, process_queue_end);\n+\tprocess_queue_end = &(*process_queue_end)->next;\n+\n+\tfprintf(stderr, \"prefetch %s\\n\", sha1_to_hex(sha1));\n+\tprefetch(sha1);\n+\t\t\n+\treturn 0;\n+}\n+\n+static int loop(void)\n+{\n+\twhile (process_queue) {\n+\t\tstruct object *obj = process_queue->item;\n+\t\tfprintf(stderr, \"%d objects to pull\\n\", \n+\t\t\tobject_list_length(process_queue));\n+\t\tprocess_queue = process_queue->next;\n+\t\tif (!process_queue)\n+\t\t\tprocess_queue_end = &process_queue;\n+\n+\t\tfprintf(stderr, \"fetch %s\\n\", sha1_to_hex(obj->sha1));\n+\t\t\n+\t\tif (make_sure_we_have_it(obj->type ?: \"object\", \n+\t\t\t\t\t obj->sha1))\n+\t\t\treturn -1;\n+\t\tif (!obj->type)\n+\t\t\tparse_object(obj->sha1);\n+\t\tif (obj->type == commit_type) {\n+\t\t\tif (process_commit((struct commit *)obj))\n+\t\t\t\treturn -1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (obj->type == tree_type) {\n+\t\t\tif (process_tree((struct tree *)obj))\n+\t\t\t\treturn -1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (obj->type == blob_type) {\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (obj->type == tag_type) {\n+\t\t\tif (process_tag((struct tag *)obj))\n+\t\t\t\treturn -1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\treturn error(\"Unable to determine requirements \"\n+\t\t\t     \"of type %s for %s\",\n+\t\t\t     obj->type, sha1_to_hex(obj->sha1));\n+\t};\n+\treturn 0;\n }\n \n static int interpret_target(char *target, unsigned char *sha1)\n@@ -164,7 +182,9 @@ int pull(char *target)\n \tif (interpret_target(target, sha1))\n \t\treturn error(\"Could not interpret %s as something to pull\",\n \t\t\t     target);\n-\tif (process_unknown(sha1))\n+\tif (process(sha1, NULL))\n+\t\treturn -1;\n+\tif (loop())\n \t\treturn -1;\n \t\n \tif (write_ref) {\ndiff --git a/pull.h b/pull.h\n--- a/pull.h\n+++ b/pull.h\n@@ -9,6 +9,13 @@\n extern int fetch(unsigned char *sha1);\n \n /*\n+ * Fetch the specified object and store it locally; fetch() will be\n+ * called later to determine success. To be provided by the particular\n+ * implementation.\n+ */\n+extern void prefetch(unsigned char *sha1);\n+\n+/*\n  * Fetch ref (relative to $GIT_DIR/refs) from the remote, and store\n  * the 20-byte SHA1 in sha1.  Return 0 on success, -1 on failure.  To\n  * be provided by the particular implementation.\ndiff --git a/ssh-pull.c b/ssh-pull.c\n--- a/ssh-pull.c\n+++ b/ssh-pull.c\n@@ -10,6 +10,10 @@ static int fd_out;\n static unsigned char remote_version = 0;\n static unsigned char local_version = 1;\n \n+void prefetch(unsigned char *sha1)\n+{\n+}\n+\n int fetch(unsigned char *sha1)\n {\n \tint ret;\n"}]}