"GOT", but the "O" is a cute, smiling sun Index | Thread

From:
Stefan Sperling <stsp@stsp.name>
Subject:
reuse tree entries array while parsing trees
To:
gameoftrees@openbsd.org
Date:
Tue, 18 Oct 2022 22:15:57 +0200

Download raw body.

This patch avoids a per-tree malloc/free dance in got-read-tree
and got-read-pack while parsing trees.

Instead of throwing the parsed-tree-entries array away after
parsing a tree, we can leave its memory allocation in place,
and keep extending it as needed with recallocarray().

An exception is enumerate_tree() in got-read-pack, which builds
up a list of trees and hence still needs separate allocations,
one per tree in the list.

On OpenBSD, where calling free(3) is relatively expensive, this
might give us a minor performance boost for repositories with a
lot of trees (e.g. ports.git).

ok?

diff cae60ab8f2a261b006b3ccbded2d53dccbd6f300 refs/heads/entries-alloc
commit - cae60ab8f2a261b006b3ccbded2d53dccbd6f300
commit + bcbef89c3f31a6dbb08629bb352ec50b24c1637b
blob - 79b6e83d9872c4ee03472131af53beb3186ab6be
blob + 723508cf635f39153b1b47082dca8bf6b3bb09ca
--- lib/got_lib_object_parse.h
+++ lib/got_lib_object_parse.h
@@ -30,7 +30,7 @@ const struct got_error *got_object_parse_tree(struct g
 	uint8_t *id; /* Points to ID in parsed tree buffer. */
 };
 const struct got_error *got_object_parse_tree(struct got_parsed_tree_entry **,
-    int *, uint8_t *, size_t);
+    size_t *, size_t *, uint8_t *, size_t);
 
 const struct got_error *got_object_parse_tag(struct got_tag_object **,
     uint8_t *, size_t);
blob - ec233429206e7196cf189fc056e4a4902b222519
blob + 1e7ebaf7fd5125d8622a43d7387611208e41209c
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -713,11 +713,11 @@ got_object_parse_tree(struct got_parsed_tree_entry **e
 }
 
 const struct got_error *
-got_object_parse_tree(struct got_parsed_tree_entry **entries, int *nentries,
-    uint8_t *buf, size_t len)
+got_object_parse_tree(struct got_parsed_tree_entry **entries, size_t *nentries,
+    size_t *nentries_alloc, uint8_t *buf, size_t len)
 {
 	const struct got_error *err = NULL;
-	size_t remain = len, totalloc;
+	size_t remain = len;
 	const size_t nalloc = 16;
 	struct got_parsed_tree_entry *pte;
 	int i;
@@ -726,23 +726,18 @@ got_object_parse_tree(struct got_parsed_tree_entry **e
 	if (remain == 0)
 		return NULL; /* tree is empty */
 
-	*entries = calloc(nalloc, sizeof(**entries));
-	if (*entries == NULL)
-		return got_error_from_errno("calloc");
-	totalloc = nalloc;
-
 	while (remain > 0) {
 		size_t elen;
 
-		if (*nentries >= totalloc) {
-			pte = recallocarray(*entries, totalloc,
-			    totalloc + nalloc, sizeof(**entries));
+		if (*nentries >= *nentries_alloc) {
+			pte = recallocarray(*entries, *nentries_alloc,
+			    *nentries_alloc + nalloc, sizeof(**entries));
 			if (pte == NULL) {
 				err = got_error_from_errno("recallocarray");
 				goto done;
 			}
 			*entries = pte;
-			totalloc += nalloc;
+			*nentries_alloc += nalloc;
 		}
 
 		pte = &(*entries)[*nentries];
@@ -773,11 +768,8 @@ done:
 		}
 	}
 done:
-	if (err) {
-		free(*entries);
-		*entries = NULL;
+	if (err)
 		*nentries = 0;
-	}
 	return err;
 }
 
blob - b2896d83221d70e883140fef22f1569195a28079
blob + 268ab18c5371e622b7f9c3a62c9a894a7050de85
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -183,9 +183,9 @@ open_tree(uint8_t **buf, struct got_parsed_tree_entry 
 }
 
 static const struct got_error *
-open_tree(uint8_t **buf, struct got_parsed_tree_entry **entries, int *nentries,
-    struct got_pack *pack, struct got_packidx *packidx, int obj_idx,
-    struct got_object_id *id, struct got_object_cache *objcache)
+open_tree(uint8_t **buf, struct got_parsed_tree_entry **entries, size_t *nentries,
+    size_t *nentries_alloc, struct got_pack *pack, struct got_packidx *packidx,
+    int obj_idx, struct got_object_id *id, struct got_object_cache *objcache)
 {
 	const struct got_error *err = NULL;
 	struct got_object *obj = NULL;
@@ -210,7 +210,8 @@ open_tree(uint8_t **buf, struct got_parsed_tree_entry 
 
 	obj->size = len;
 
-	err = got_object_parse_tree(entries, nentries, *buf, len);
+	err = got_object_parse_tree(entries, nentries, nentries_alloc,
+	    *buf, len);
 done:
 	got_object_close(obj);
 	if (err) {
@@ -222,12 +223,12 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 
 static const struct got_error *
 tree_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack,
-    struct got_packidx *packidx, struct got_object_cache *objcache)
+    struct got_packidx *packidx, struct got_object_cache *objcache,
+    struct got_parsed_tree_entry **entries, size_t *nentries,
+    size_t *nentries_alloc)
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_packed_object iobj;
-	struct got_parsed_tree_entry *entries = NULL;
-	int nentries = 0;
 	uint8_t *buf = NULL;
 	struct got_object_id id;
 	size_t datalen;
@@ -238,13 +239,12 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	memcpy(&iobj, imsg->data, sizeof(iobj));
 	memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH);
 
-	err = open_tree(&buf, &entries, &nentries, pack, packidx, iobj.idx,
-	    &id, objcache);
+	err = open_tree(&buf, entries, nentries, nentries_alloc,
+	    pack, packidx, iobj.idx, &id, objcache);
 	if (err)
 		return err;
 
-	err = got_privsep_send_tree(ibuf, entries, nentries);
-	free(entries);
+	err = got_privsep_send_tree(ibuf, *entries, *nentries);
 	free(buf);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
@@ -453,8 +453,10 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 
 static const struct got_error *
 tree_path_changed(int *changed, uint8_t **buf1, uint8_t **buf2,
-    struct got_parsed_tree_entry **entries1, int *nentries1,
-    struct got_parsed_tree_entry **entries2, int *nentries2,
+    struct got_parsed_tree_entry **entries1, size_t *nentries1,
+    size_t *nentries_alloc1,
+    struct got_parsed_tree_entry **entries2, size_t *nentries2,
+    size_t *nentries_alloc2,
     const char *path, struct got_pack *pack, struct got_packidx *packidx,
     struct imsgbuf *ibuf, struct got_object_cache *objcache)
 {
@@ -522,12 +524,12 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id1);
 				break;
 			}
-			free(*entries1);
 			*nentries1 = 0;
 			free(*buf1);
 			*buf1 = NULL;
-			err = open_tree(buf1, entries1, nentries1, pack,
-			    packidx, idx, &id1, objcache);
+			err = open_tree(buf1, entries1, nentries1,
+			    nentries_alloc1, pack, packidx, idx, &id1,
+			    objcache);
 			pte1 = NULL;
 			if (err)
 				break;
@@ -538,12 +540,11 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id2);
 				break;
 			}
-			free(*entries2);
 			*nentries2 = 0;
 			free(*buf2);
 			*buf2 = NULL;
-			err = open_tree(buf2, entries2, nentries2, pack,
-			    packidx, idx, &id2, objcache);
+			err = open_tree(buf2, entries2, nentries2,
+			nentries_alloc2, pack, packidx, idx, &id2, objcache);
 			pte2 = NULL;
 			if (err)
 				break;
@@ -603,7 +604,8 @@ commit_traversal_request(struct imsg *imsg, struct ims
 	struct got_object_qid *pid;
 	struct got_commit_object *commit = NULL, *pcommit = NULL;
 	struct got_parsed_tree_entry *entries = NULL, *pentries = NULL;
-	int nentries = 0, pnentries = 0;
+	size_t nentries = 0, nentries_alloc = 0;
+	size_t pnentries = 0, pnentries_alloc = 0;
 	struct got_object_id id;
 	size_t datalen, path_len;
 	char *path = NULL;
@@ -713,27 +715,26 @@ commit_traversal_request(struct imsg *imsg, struct ims
 			if (pidx == -1)
 				break;
 
-			err = open_tree(&buf, &entries, &nentries, pack,
-			    packidx, idx, commit->tree_id, objcache);
+			err = open_tree(&buf, &entries, &nentries,
+			    &nentries_alloc, pack, packidx, idx,
+			    commit->tree_id, objcache);
 			if (err)
 				goto done;
-			err = open_tree(&pbuf, &pentries, &pnentries, pack,
-			    packidx, pidx, pcommit->tree_id, objcache);
+			err = open_tree(&pbuf, &pentries, &pnentries,
+			    &pnentries_alloc, pack, packidx, pidx,
+			    pcommit->tree_id, objcache);
 			if (err) {
 				free(buf);
 				goto done;
 			}
 
 			err = tree_path_changed(&changed, &buf, &pbuf,
-			    &entries, &nentries, &pentries, &pnentries, path,
-			    pack, packidx, ibuf, objcache);
+			    &entries, &nentries, &nentries_alloc,
+			    &pentries, &pnentries, &pnentries_alloc,
+			    path, pack, packidx, ibuf, objcache);
 
-			free(entries);
-			entries = NULL;
 			nentries = 0;
 			free(buf);
-			free(pentries);
-			pentries = NULL;
 			pnentries = 0;
 			free(pbuf);
 			if (err) {
@@ -1191,7 +1192,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf *
 	struct got_object_qid *qid;
 	uint8_t *buf = NULL;
 	struct got_parsed_tree_entry *entries = NULL;
-	int nentries = 0, i;
+	size_t nentries = 0, nentries_alloc = 0, i;
 	struct enumerated_tree *tree;
 
 	*ntrees = 0;
@@ -1230,7 +1231,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf *
 			break;
 		}
 
-		err = open_tree(&buf, &entries, &nentries,
+		err = open_tree(&buf, &entries, &nentries, &nentries_alloc,
 		    pack, packidx, idx, &qid->id, objcache);
 		if (err) {
 			if (err->code != GOT_ERR_NO_OBJ)
@@ -1289,7 +1290,9 @@ enumerate_tree(int *have_all_entries, struct imsgbuf *
 		buf = NULL;
 		tree->entries = entries;
 		entries = NULL;
+		nentries_alloc = 0;
 		tree->nentries = nentries;
+		nentries = 0;
 
 		got_object_qid_free(qid);
 		qid = NULL;
@@ -1898,6 +1901,8 @@ main(int argc, char *argv[])
 	struct got_object_cache objcache;
 	FILE *basefile = NULL, *accumfile = NULL, *delta_outfile = NULL;
 	struct got_object_idset *keep = NULL, *drop = NULL, *skip = NULL;
+	struct got_parsed_tree_entry *entries = NULL;
+	size_t nentries = 0, nentries_alloc = 0;
 
 	//static int attached;
 	//while (!attached) sleep(1);
@@ -2005,7 +2010,7 @@ main(int argc, char *argv[])
 			break;
 		case GOT_IMSG_TREE_REQUEST:
 			err = tree_request(&imsg, &ibuf, pack, packidx,
-			    &objcache);
+			    &objcache, &entries, &nentries, &nentries_alloc);
 			break;
 		case GOT_IMSG_BLOB_REQUEST:
 			if (basefile == NULL || accumfile == NULL) {
@@ -2054,6 +2059,7 @@ main(int argc, char *argv[])
 			break;
 	}
 
+	free(entries);
 	commit_painting_free(&keep, &drop, &skip);
 	if (packidx)
 		got_packidx_close(packidx);
blob - 225f928a01e58925e0d8bcb3e1ffb1a2cc09d631
blob + 70c37485b3b652e8c3c0fd4dfe8a25350f6d1565
--- libexec/got-read-tree/got-read-tree.c
+++ libexec/got-read-tree/got-read-tree.c
@@ -50,8 +50,8 @@ read_tree_object(struct got_parsed_tree_entry **entrie
 }
 
 static const struct got_error *
-read_tree_object(struct got_parsed_tree_entry **entries, int *nentries,
-    uint8_t **p, FILE *f, struct got_object_id *expected_id)
+read_tree_object(struct got_parsed_tree_entry **entries, size_t *nentries,
+    size_t *nentries_alloc, uint8_t **p, FILE *f, struct got_object_id *expected_id)
 {
 	const struct got_error *err = NULL;
 	struct got_object *obj = NULL;
@@ -89,7 +89,8 @@ read_tree_object(struct got_parsed_tree_entry **entrie
 
 	/* Skip object header. */
 	len -= obj->hdrlen;
-	err = got_object_parse_tree(entries, nentries, *p + obj->hdrlen, len);
+	err = got_object_parse_tree(entries, nentries, nentries_alloc,
+	    *p + obj->hdrlen, len);
 done:
 	if (obj)
 		got_object_close(obj);
@@ -102,6 +103,8 @@ main(int argc, char *argv[])
 	const struct got_error *err = NULL;
 	struct imsgbuf ibuf;
 	size_t datalen;
+	struct got_parsed_tree_entry *entries = NULL;
+	size_t nentries = 0, nentries_alloc = 0;
 
 	signal(SIGINT, catch_sigint);
 
@@ -119,8 +122,6 @@ main(int argc, char *argv[])
 	for (;;) {
 		struct imsg imsg;
 		FILE *f = NULL;
-		struct got_parsed_tree_entry *entries = NULL;
-		int nentries = 0;
 		uint8_t *buf = NULL;
 		struct got_object_id expected_id;
 
@@ -163,14 +164,13 @@ main(int argc, char *argv[])
 			goto done;
 		}
 
-		err = read_tree_object(&entries, &nentries, &buf, f,
-		    &expected_id);
+		err = read_tree_object(&entries, &nentries, &nentries_alloc,
+		    &buf, f, &expected_id);
 		if (err)
 			goto done;
 
 		err = got_privsep_send_tree(&ibuf, entries, nentries);
 done:
-		free(entries);
 		free(buf);
 		if (f) {
 			if (fclose(f) == EOF && err == NULL)
@@ -184,6 +184,7 @@ done:
 			break;
 	}
 
+	free(entries);
 	imsg_clear(&ibuf);
 	if (err) {
 		if (!sigint_received && err->code != GOT_ERR_PRIVSEP_PIPE) {