{"thread":{"id":"1400","subject":"[PATCH 1/3] Object library enhancements","startedAt":"2005-08-02T23:45:12Z","lastAt":"2005-08-02T23:46:29Z","messageCount":4,"participants":["barkalow@iabervon.org"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"6733","messageId":"Pine.LNX.4.62.0508021939320.23721@iabervon.org","threadId":"1400","inReplyTo":null,"subject":"[PATCH 0/3] Parallel pull for SSH","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-02T23:45:12Z","receivedAt":"2005-08-02T23:45:12Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This series pipelines pulling by ssh; objects are requested as soon as \npossible, and read once as many hashes as possible have been stuffed in \nthe queue. This seems to be a major improvement in throughput, although it \ndoesn't do any packing, so the total data transferred is higher than it \ncould be.\n\n 1: Object library additions\n 2: Parallel pull algorithm\n 3: Pipelined SSH support\n\nIt replaces these commits from -pu:\n 9d469633827c3ac9736ff5cca620db0491ecb200\n 7e11bade2166d11e3ce0b8635eb9f61716cddcd6\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"6732","messageId":"Pine.LNX.4.62.0508021945200.23721@iabervon.org","threadId":"1400","inReplyTo":"Pine.LNX.4.62.0508021939320.23721@iabervon.org","subject":"[PATCH 1/3] Object library enhancements","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-02T23:45:48Z","receivedAt":"2005-08-02T23:45:48Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Add function to look up an object which is entirely unknown, so that\nit can be put in a list. Various other functions related to lists of\nobjects.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n object.c |   55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n object.h |   10 ++++++++++\n tree.h   |    1 +\n 3 files changed, 65 insertions(+), 1 deletions(-)\n\n6f610ea3a0118fd7bcda89b75b538d3711418b72\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,33 @@ 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+}\n+\n+int object_list_contains(struct object_list *list, struct object *obj)\n+{\n+\twhile (list) {\n+\t\tif (list->item == obj)\n+\t\t\treturn 1;\n+\t\tlist = list->next;\n+\t}\n+\treturn 0;\n+}\ndiff --git a/object.h b/object.h\n--- a/object.h\n+++ b/object.h\n@@ -31,8 +31,18 @@ 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+int object_list_contains(struct object_list *list, struct object *obj);\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":"6735","messageId":"Pine.LNX.4.62.0508021945510.23721@iabervon.org","threadId":"1400","inReplyTo":"Pine.LNX.4.62.0508021939320.23721@iabervon.org","subject":"[PATCH 2/3] Parallelize the pull algorithm","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-02T23:46:10Z","receivedAt":"2005-08-02T23:46:10Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This processes objects in two simultaneous passes. Each object will\nfirst be given to prefetch(), as soon as it is possible to tell that\nit will be needed, and then will be given to fetch(), when it is the\nnext object that needs to be parsed. Unless an implementation does\nsomething with prefetch(), this should have no effect.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n http-pull.c  |    4 ++\n local-pull.c |    4 ++\n pull.c       |  132 ++++++++++++++++++++++++++++++++++------------------------\n pull.h       |    7 +++\n ssh-pull.c   |    4 ++\n 5 files changed, 97 insertions(+), 54 deletions(-)\n\nadf8aa039f2db3fb3bfc4dee0a7354b662cd5422\ndiff --git a/http-pull.c b/http-pull.c\n--- a/http-pull.c\n+++ b/http-pull.c\n@@ -67,6 +67,10 @@ static size_t fwrite_sha1_file(void *ptr\n \treturn size;\n }\n \n+void prefetch(unsigned char *sha1)\n+{\n+}\n+\n static int got_indices = 0;\n \n static struct packed_git *packs = NULL;\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,118 @@ 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+\tif (object_list_contains(process_queue, obj))\n+\t\treturn 0;\n+\tobject_list_insert(obj, process_queue_end);\n+\tprocess_queue_end = &(*process_queue_end)->next;\n+\n+\t//fprintf(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\t/*\n+\t\tfprintf(stderr, \"%d objects to pull\\n\", \n+\t\t\tobject_list_length(process_queue));\n+\t\t*/\n+\t\tprocess_queue = process_queue->next;\n+\t\tif (!process_queue)\n+\t\t\tprocess_queue_end = &process_queue;\n+\n+\t\t//fprintf(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 +186,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"},{"id":"6734","messageId":"Pine.LNX.4.62.0508021946130.23721@iabervon.org","threadId":"1400","inReplyTo":"Pine.LNX.4.62.0508021939320.23721@iabervon.org","subject":"[PATCH 3/3] Parallelize pulling by ssh","fromName":"","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-02T23:46:29Z","receivedAt":"2005-08-02T23:46:29Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"This causes ssh-pull to request objects in prefetch() and read then in\nfetch(), such that it reduces the unpipelined round-trip time.\n\nThis also makes sha1_write_from_fd() support having a buffer of data\nwhich it accidentally read from the fd after the object; this was\nformerly not a problem, because it would always get a short read at\nthe end of an object, because the next object had not been\nrequested. This is no longer true.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n cache.h     |    3 ++-\n sha1_file.c |   37 ++++++++++++++++++++++---------------\n ssh-pull.c  |   44 ++++++++++++++++++++++++++++++++++++--------\n 3 files changed, 60 insertions(+), 24 deletions(-)\n\n9bd15230cb65acc78a97550c9467f98a04720ee8\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -198,7 +198,8 @@ extern int check_sha1_signature(const un\n /* Read a tree into the cache */\n extern int read_tree(void *buffer, unsigned long size, int stage, const char **paths);\n \n-extern int write_sha1_from_fd(const unsigned char *sha1, int fd);\n+extern int write_sha1_from_fd(const unsigned char *sha1, int fd, char *buffer,\n+\t\t\t      size_t bufsize, size_t *bufposn);\n extern int write_sha1_to_fd(int fd, const unsigned char *sha1);\n \n extern int has_sha1_pack(const unsigned char *sha1);\ndiff --git a/sha1_file.c b/sha1_file.c\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1389,14 +1389,14 @@ int write_sha1_to_fd(int fd, const unsig\n \treturn 0;\n }\n \n-int write_sha1_from_fd(const unsigned char *sha1, int fd)\n+int write_sha1_from_fd(const unsigned char *sha1, int fd, char *buffer,\n+\t\t       size_t bufsize, size_t *bufposn)\n {\n \tchar *filename = sha1_file_name(sha1);\n \n \tint local;\n \tz_stream stream;\n \tunsigned char real_sha1[20];\n-\tunsigned char buf[4096];\n \tunsigned char discard[4096];\n \tint ret;\n \tSHA_CTX c;\n@@ -1414,7 +1414,24 @@ int write_sha1_from_fd(const unsigned ch\n \n \tdo {\n \t\tssize_t size;\n-\t\tsize = read(fd, buf, 4096);\n+\t\tif (*bufposn) {\n+\t\t\tstream.avail_in = *bufposn;\n+\t\t\tstream.next_in = buffer;\n+\t\t\tdo {\n+\t\t\t\tstream.next_out = discard;\n+\t\t\t\tstream.avail_out = sizeof(discard);\n+\t\t\t\tret = inflate(&stream, Z_SYNC_FLUSH);\n+\t\t\t\tSHA1_Update(&c, discard, sizeof(discard) -\n+\t\t\t\t\t    stream.avail_out);\n+\t\t\t} while (stream.avail_in && ret == Z_OK);\n+\t\t\twrite(local, buffer, *bufposn - stream.avail_in);\n+\t\t\tmemmove(buffer, buffer + *bufposn - stream.avail_in,\n+\t\t\t\tstream.avail_in);\n+\t\t\t*bufposn = stream.avail_in;\n+\t\t\tif (ret != Z_OK)\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tsize = read(fd, buffer + *bufposn, bufsize - *bufposn);\n \t\tif (size <= 0) {\n \t\t\tclose(local);\n \t\t\tunlink(filename);\n@@ -1423,18 +1440,8 @@ int write_sha1_from_fd(const unsigned ch\n \t\t\tperror(\"Reading from connection\");\n \t\t\treturn -1;\n \t\t}\n-\t\twrite(local, buf, size);\n-\t\tstream.avail_in = size;\n-\t\tstream.next_in = buf;\n-\t\tdo {\n-\t\t\tstream.next_out = discard;\n-\t\t\tstream.avail_out = sizeof(discard);\n-\t\t\tret = inflate(&stream, Z_SYNC_FLUSH);\n-\t\t\tSHA1_Update(&c, discard, sizeof(discard) -\n-\t\t\t\t    stream.avail_out);\n-\t\t} while (stream.avail_in && ret == Z_OK);\n-\t\t\n-\t} while (ret == Z_OK);\n+\t\t*bufposn += size;\n+\t} while (1);\n \tinflateEnd(&stream);\n \n \tclose(local);\ndiff --git a/ssh-pull.c b/ssh-pull.c\n--- a/ssh-pull.c\n+++ b/ssh-pull.c\n@@ -10,24 +10,49 @@ static int fd_out;\n static unsigned char remote_version = 0;\n static unsigned char local_version = 1;\n \n+ssize_t force_write(int fd, void *buffer, size_t length)\n+{\n+\tssize_t ret = 0;\n+\twhile (ret < length) {\n+\t\tssize_t size = write(fd, buffer + ret, length - ret);\n+\t\tif (size < 0) {\n+\t\t\treturn size;\n+\t\t}\n+\t\tif (size == 0) {\n+\t\t\treturn ret;\n+\t\t}\n+\t\tret += size;\n+\t}\n+\treturn ret;\n+}\n+\n void prefetch(unsigned char *sha1)\n {\n+\tchar type = 'o';\n+\tforce_write(fd_out, &type, 1);\n+\tforce_write(fd_out, sha1, 20);\n+\t//memcpy(requested + 20 * prefetches++, sha1, 20);\n }\n \n+static char conn_buf[4096];\n+static size_t conn_buf_posn = 0;\n+\n int fetch(unsigned char *sha1)\n {\n \tint ret;\n \tsigned char remote;\n-\tchar type = 'o';\n-\tif (has_sha1_file(sha1))\n-\t\treturn 0;\n-\twrite(fd_out, &type, 1);\n-\twrite(fd_out, sha1, 20);\n-\tif (read(fd_in, &remote, 1) < 1)\n-\t\treturn -1;\n+\n+\tif (conn_buf_posn) {\n+\t\tremote = conn_buf[0];\n+\t\tmemmove(conn_buf, conn_buf + 1, --conn_buf_posn);\n+\t} else {\n+\t\tif (read(fd_in, &remote, 1) < 1)\n+\t\t\treturn -1;\n+\t}\n+\t//fprintf(stderr, \"Got %d\\n\", remote);\n \tif (remote < 0)\n \t\treturn remote;\n-\tret = write_sha1_from_fd(sha1, fd_in);\n+\tret = write_sha1_from_fd(sha1, fd_in, conn_buf, 4096, &conn_buf_posn);\n \tif (!ret)\n \t\tpull_say(\"got %s\\n\", sha1_to_hex(sha1));\n \treturn ret;\n"}]}