"GOT", but the "O" is a cute, smiling pufferfish. Index | Thread | Search

From:
Stefan Sperling <stsp@stsp.name>
Subject:
less memcpy() when parsing trees
To:
gameoftrees@openbsd.org
Date:
Mon, 11 Nov 2019 21:40:09 +0200

Download raw body.

Thread 
Our code is doing quite a bit of redundant memcpy() operations.
This is not incorrect but has an impact on performance. I have
started looking into reducing the amount of memcpy() where possible.

With this diff we copy tree data to an imsg directly from the buffer
into which the on-disk data was decompressed, rather than copying
this decompressed data into a struct got_tree_object first, and then
copying data out of that object into a temporary buffer, and then
copying data from that bufffer into the imsg.

This kind of work could probably be done for other object types,
as well as many other places throughout the code base.
Is anyone interested in helping with this effort?

diff refs/heads/master refs/heads/parse-tree-memcpy
blob - cc4f1837befaa2cccdec42ad171967f789314e22
blob + be9875a2deb1c9b30cfbc5f4ed8d5506c04d78da
--- lib/got_lib_object_parse.h
+++ lib/got_lib_object_parse.h
@@ -14,13 +14,15 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
+struct got_pathlist_head;
+
 const struct got_error *got_object_qid_alloc_partial(struct got_object_qid **);
 struct got_commit_object *got_object_commit_alloc_partial(void);
 struct got_tree_entry *got_alloc_tree_entry_partial(void);
 
 const struct got_error *got_object_parse_commit(struct got_commit_object **,
     char *, size_t);
-const struct got_error *got_object_parse_tree(struct got_tree_object **,
+const struct got_error *got_object_parse_tree(struct got_pathlist_head *, int *,
     uint8_t *, size_t);
 const struct got_error *got_object_parse_tag(struct got_tag_object **,
     uint8_t *, size_t);
blob - f1e7f2ad14684a954b1bc1e9b4a6195cc963c7c3
blob + a37a450e6e18733afec74aa1dc9cb427c9d27acb
--- lib/got_lib_privsep.h
+++ lib/got_lib_privsep.h
@@ -231,6 +231,7 @@ struct got_imsg_packed_object {
 
 struct got_pack;
 struct got_packidx;
+struct got_pathlist_head;
 
 const struct got_error *got_privsep_wait_for_child(pid_t);
 const struct got_error *got_privsep_send_stop(int);
@@ -261,7 +262,7 @@ const struct got_error *got_privsep_recv_commit(struct
 const struct got_error *got_privsep_recv_tree(struct got_tree_object **,
     struct imsgbuf *);
 const struct got_error *got_privsep_send_tree(struct imsgbuf *,
-    struct got_tree_object *);
+    struct got_pathlist_head *, int);
 const struct got_error *got_privsep_send_blob(struct imsgbuf *, size_t, size_t,
     const uint8_t *);
 const struct got_error *got_privsep_recv_blob(uint8_t **, size_t *, size_t *,
blob - 9a37c6f1d7c6414382484dbde632c0fb6bb7591e
blob + 7e07071438257a0baa74864baebdbbc348be6519
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -663,88 +663,83 @@ got_alloc_tree_entry_partial(void)
 }
 
 static const struct got_error *
-parse_tree_entry(struct got_tree_entry **te, size_t *elen, char *buf,
+parse_tree_entry(struct got_imsg_tree_entry **ite, const char **name,
+    size_t *elen, char *buf,
     size_t maxlen)
 {
 	char *p, *space;
 	const struct got_error *err = NULL;
 
+	*name = NULL;
 	*elen = 0;
 
-	*te = got_alloc_tree_entry_partial();
-	if (*te == NULL)
-		return got_error_from_errno("got_alloc_tree_entry_partial");
+	*ite = malloc(sizeof(**ite));
+	if (*ite == NULL)
+		return got_error_from_errno("malloc");
 
 	*elen = strnlen(buf, maxlen) + 1;
 	if (*elen > maxlen) {
-		free(*te);
-		*te = NULL;
+		free(*ite);
+		*ite = NULL;
 		return got_error(GOT_ERR_BAD_OBJ_DATA);
 	}
 
 	space = memchr(buf, ' ', *elen);
 	if (space == NULL || space <= buf) {
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		free(*te);
-		*te = NULL;
+		free(*ite);
+		*ite = NULL;
 		return err;
 	}
-	(*te)->mode = 0;
+	(*ite)->mode = 0;
 	p = buf;
 	while (p < space) {
 		if (*p < '0' && *p > '7') {
 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
 			goto done;
 		}
-		(*te)->mode <<= 3;
-		(*te)->mode |= *p - '0';
+		(*ite)->mode <<= 3;
+		(*ite)->mode |= *p - '0';
 		p++;
 	}
 
-	(*te)->name = strdup(space + 1);
 	if (*elen > maxlen || maxlen - *elen < SHA1_DIGEST_LENGTH) {
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
 		goto done;
 	}
+	*name = space + 1;
 	buf += *elen;
-	memcpy((*te)->id->sha1, buf, SHA1_DIGEST_LENGTH);
+	memcpy((*ite)->id, buf, SHA1_DIGEST_LENGTH);
 	*elen += SHA1_DIGEST_LENGTH;
 done:
 	if (err) {
-		got_object_tree_entry_close(*te);
-		*te = NULL;
+		free(*ite);
+		*ite = NULL;
 	}
 	return err;
 }
 
 const struct got_error *
-got_object_parse_tree(struct got_tree_object **tree, uint8_t *buf, size_t len)
+got_object_parse_tree(struct got_pathlist_head *entries, int *nentries,
+    uint8_t *buf, size_t len)
 {
-	const struct got_error *err;
+	const struct got_error *err = NULL;
 	size_t remain = len;
-	struct got_pathlist_head pathlist;
-	struct got_pathlist_entry *pe;
 
-	TAILQ_INIT(&pathlist);
-
-	*tree = calloc(1, sizeof(**tree));
-	if (*tree == NULL)
-		return got_error_from_errno("calloc");
-
-	SIMPLEQ_INIT(&(*tree)->entries.head);
-
+	*nentries = 0;
 	if (remain == 0)
 		return NULL; /* tree is empty */
 
 	while (remain > 0) {
-		struct got_tree_entry *te;
+		struct got_imsg_tree_entry *ite;
 		struct got_pathlist_entry *new = NULL;
+		const char *name;
 		size_t elen;
 
-		err = parse_tree_entry(&te, &elen, buf, remain);
+		err = parse_tree_entry(&ite, &name, &elen, buf, remain);
 		if (err)
 			goto done;
-		err = got_pathlist_insert(&new, &pathlist, te->name, te);
+		err = got_pathlist_insert(&new, entries, name, ite);
 		if (err)
 			goto done;
 		if (new == NULL) {
@@ -753,22 +748,18 @@ got_object_parse_tree(struct got_tree_object **tree, u
 		}
 		buf += elen;
 		remain -= elen;
+		(*nentries)++;
 	}
 
 	if (remain != 0) {
-		got_object_tree_close(*tree);
-		*tree = NULL;
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
 		goto done;
 	}
-
-	TAILQ_FOREACH(pe, &pathlist, entry) {
-		struct got_tree_entry *te = pe->data;
-		(*tree)->entries.nentries++;
-		SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry);
-	}
 done:
-	got_pathlist_free(&pathlist);
+	if (err) {
+		got_pathlist_free(entries);
+		*nentries = 0;
+	}
 	return err;
 }
 
blob - 62a79cfc9798d9720d38528272f0681cb10d18d6
blob + 971274cf3e8bb654ff2872ae070e2c9e744bd656
--- lib/privsep.c
+++ lib/privsep.c
@@ -33,6 +33,7 @@
 
 #include "got_object.h"
 #include "got_error.h"
+#include "got_path.h"
 
 #include "got_lib_sha1.h"
 #include "got_lib_delta.h"
@@ -690,25 +691,28 @@ got_privsep_recv_commit(struct got_commit_object **com
 }
 
 const struct got_error *
-got_privsep_send_tree(struct imsgbuf *ibuf, struct got_tree_object *tree)
+got_privsep_send_tree(struct imsgbuf *ibuf, struct got_pathlist_head *entries,
+    int nentries)
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_tree_object itree;
-	struct got_tree_entry *te;
+	struct got_pathlist_entry *pe;
 	size_t totlen;
 	int nimsg; /* number of imsg queued in ibuf */
 
-	itree.nentries = tree->entries.nentries;
+	itree.nentries = nentries;
 	if (imsg_compose(ibuf, GOT_IMSG_TREE, 0, 0, -1, &itree, sizeof(itree))
 	    == -1)
 		return got_error_from_errno("imsg_compose TREE");
 
 	totlen = sizeof(itree);
 	nimsg = 1;
-	SIMPLEQ_FOREACH(te, &tree->entries.head, entry) {
-		struct got_imsg_tree_entry *ite;
-		uint8_t *buf = NULL;
-		size_t len = sizeof(*ite) + strlen(te->name);
+	TAILQ_FOREACH(pe, entries, entry) {
+		const char *name = pe->path;
+		struct got_imsg_tree_entry *ite = pe->data;
+		struct ibuf *wbuf;
+		size_t namelen = strlen(name);
+		size_t len = sizeof(*ite) + namelen;
 
 		if (len > MAX_IMSGSIZE)
 			return got_error(GOT_ERR_NO_SPACE);
@@ -721,21 +725,23 @@ got_privsep_send_tree(struct imsgbuf *ibuf, struct got
 			nimsg = 0;
 		}
 
-		buf = malloc(len);
-		if (buf == NULL)
-			return got_error_from_errno("malloc");
+		wbuf = imsg_create(ibuf, GOT_IMSG_TREE_ENTRY, 0, 0, len);
+		if (wbuf == NULL)
+			return got_error_from_errno("imsg_create TREE_ENTRY");
 
-		ite = (struct got_imsg_tree_entry *)buf;
-		memcpy(ite->id, te->id->sha1, sizeof(ite->id));
-		ite->mode = te->mode;
-		memcpy(buf + sizeof(*ite), te->name, strlen(te->name));
+		if (imsg_add(wbuf, ite, sizeof(*ite)) == -1)
+			err = got_error_from_errno("imsg_add TREE_ENTRY");
+		if (err)
+			return err;
 
-		if (imsg_compose(ibuf, GOT_IMSG_TREE_ENTRY, 0, 0, -1,
-		    buf, len) == -1)
-			err = got_error_from_errno("imsg_compose TREE_ENTRY");
-		free(buf);
+		if (imsg_add(wbuf, name, namelen) == -1)
+			err = got_error_from_errno("imsg_add TREE_ENTRY");
 		if (err)
 			return err;
+
+		wbuf->fd = -1;
+		imsg_close(ibuf, wbuf);
+
 		totlen += len;
 	}
 
blob - d8c2e0f8683a4492064ae0e7be3d35a1c6b485f0
blob + f130a21a81e49ebf7483be526ba5b6ea351b3c91
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -33,6 +33,7 @@
 
 #include "got_error.h"
 #include "got_object.h"
+#include "got_path.h"
 
 #include "got_lib_delta.h"
 #include "got_lib_delta_cache.h"
@@ -166,12 +167,15 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	const struct got_error *err = NULL;
 	struct got_imsg_packed_object iobj;
 	struct got_object *obj = NULL;
-	struct got_tree_object *tree = NULL;
+	struct got_pathlist_head entries;
+	int nentries = 0;
 	uint8_t *buf = NULL;
 	size_t len;
 	struct got_object_id id;
 	size_t datalen;
 
+	TAILQ_INIT(&entries);
+
 	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
 	if (datalen != sizeof(iobj))
 		return got_error(GOT_ERR_PRIVSEP_LEN);
@@ -193,16 +197,15 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 		goto done;
 
 	obj->size = len;
-	err = got_object_parse_tree(&tree, buf, len);
+	err = got_object_parse_tree(&entries, &nentries, buf, len);
 	if (err)
 		goto done;
 
-	err = got_privsep_send_tree(ibuf, tree);
+	err = got_privsep_send_tree(ibuf, &entries, nentries);
 done:
+	got_pathlist_free(&entries);
 	free(buf);
 	got_object_close(obj);
-	if (tree)
-		got_object_tree_close(tree);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
 			err = NULL;
blob - 78ffcce7e549655d0c7079dc856ef58d54c92163
blob + 3e24db2fa40abdd99961db56310f1a4814f29c71
--- libexec/got-read-tree/got-read-tree.c
+++ libexec/got-read-tree/got-read-tree.c
@@ -32,6 +32,7 @@
 
 #include "got_error.h"
 #include "got_object.h"
+#include "got_path.h"
 
 #include "got_lib_delta.h"
 #include "got_lib_inflate.h"
@@ -46,19 +47,20 @@ catch_sigint(int signo)
 {
 	sigint_received = 1;
 }
+
 static const struct got_error *
-read_tree_object(struct got_tree_object **tree, FILE *f)
+read_tree_object(struct got_pathlist_head *entries, int *nentries,
+    uint8_t **p, FILE *f)
 {
 	const struct got_error *err = NULL;
 	struct got_object *obj;
 	size_t len;
-	uint8_t *p;
 
-	err = got_inflate_to_mem(&p, &len, f);
+	err = got_inflate_to_mem(p, &len, f);
 	if (err)
 		return err;
 
-	err = got_object_parse_header(&obj, p, len);
+	err = got_object_parse_header(&obj, *p, len);
 	if (err)
 		return err;
 
@@ -69,9 +71,8 @@ read_tree_object(struct got_tree_object **tree, FILE *
 
 	/* Skip object header. */
 	len -= obj->hdrlen;
-	err = got_object_parse_tree(tree, p + obj->hdrlen, len);
+	err = got_object_parse_tree(entries, nentries, *p + obj->hdrlen, len);
 done:
-	free(p);
 	got_object_close(obj);
 	return err;
 }
@@ -98,8 +99,12 @@ main(int argc, char *argv[])
 	for (;;) {
 		struct imsg imsg;
 		FILE *f = NULL;
-		struct got_tree_object *tree = NULL;
+		struct got_pathlist_head entries;
+		int nentries = 0;
+		uint8_t *buf = NULL;
 
+		TAILQ_INIT(&entries);
+
 		if (sigint_received) {
 			err = got_error(GOT_ERR_CANCELLED);
 			break;
@@ -132,12 +137,14 @@ main(int argc, char *argv[])
 			goto done;
 		}
 
-		err = read_tree_object(&tree, f);
+		err = read_tree_object(&entries, &nentries, &buf, f);
 		if (err)
 			goto done;
 
-		err = got_privsep_send_tree(&ibuf, tree);
+		err = got_privsep_send_tree(&ibuf, &entries, nentries);
 done:
+		got_pathlist_free(&entries);
+		free(buf);
 		if (f) {
 			if (fclose(f) != 0 && err == NULL)
 				err = got_error_from_errno("fclose");