[PATCH 4/4] http-walker: use hashmap to eliminate list scan

[PATCH 4/4] http-walker: use hashmap to eliminate list scan

[Eric Wong]

We can reduce list walking in fill_active_slot by deleting items
as we walk through the object request queue of pending objects.

However, we still need to maintain a mapping of live objects
for fetch_object, so introduce the use of a hashmap to keep
track of all live object requests in O(1) average time.

Signed-off-by: Eric Wong <e@80x24.org>
---
 http-walker.c | 42 +++++++++++++++++++++++++++---------------
 1 file changed, 27 insertions(+), 15 deletions(-)

diff --git a/http-walker.c b/http-walker.c
index b9fe33a..25f63de 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -3,6 +3,7 @@
 #include "walker.h"
 #include "http.h"
 #include "list.h"
+#include "hashmap.h"
 
 struct alt_base {
 	char *base;
@@ -19,10 +20,11 @@ enum object_request_state {
 };
 
 struct object_request {
+	struct hashmap_entry ent;
+	enum object_request_state state;
 	struct walker *walker;
 	unsigned char sha1[20];
 	struct alt_base *repo;
-	enum object_request_state state;
 	struct http_object_request *req;
 	struct list_head node;
 };
@@ -43,6 +45,7 @@ struct walker_data {
 };
 
 static LIST_HEAD(object_queue_head);
+static struct hashmap *object_requests;
 
 static void fetch_alternates(struct walker *walker, const char *base);
 
@@ -116,6 +119,7 @@ static void release_object_request(struct object_request *obj_req)
 		error("fd leakage in release: %d", obj_req->req->localfile);
 
 	list_del(&obj_req->node);
+	hashmap_remove(object_requests, obj_req, obj_req->sha1);
 	free(obj_req);
 }
 
@@ -127,13 +131,12 @@ static int fill_active_slot(struct walker *walker)
 
 	list_for_each_safe(pos, tmp, head) {
 		obj_req = list_entry(pos, struct object_request, node);
-		if (obj_req->state == WAITING) {
-			if (has_sha1_file(obj_req->sha1))
-				obj_req->state = COMPLETE;
-			else {
-				start_object_request(walker, obj_req);
-				return 1;
-			}
+		list_del(pos);
+		if (has_sha1_file(obj_req->sha1))
+			obj_req->state = COMPLETE;
+		else {
+			start_object_request(walker, obj_req);
+			return 1;
 		}
 	}
 	return 0;
@@ -146,6 +149,8 @@ static void prefetch(struct walker *walker, unsigned char *sha1)
 	struct walker_data *data = walker->data;
 
 	newreq = xmalloc(sizeof(*newreq));
+	hashmap_entry_init(&newreq->ent, sha1hash(sha1));
+	hashmap_add(object_requests, &newreq->ent);
 	newreq->walker = walker;
 	hashcpy(newreq->sha1, sha1);
 	newreq->repo = data->alt;
@@ -436,15 +441,11 @@ static int fetch_object(struct walker *walker, unsigned char *sha1)
 {
 	char *hex = sha1_to_hex(sha1);
 	int ret = 0;
-	struct object_request *obj_req = NULL;
+	struct object_request *obj_req, key;
 	struct http_object_request *req;
-	struct list_head *pos, *head = &object_queue_head;
 
-	list_for_each(pos, head) {
-		obj_req = list_entry(pos, struct object_request, node);
-		if (!hashcmp(obj_req->sha1, sha1))
-			break;
-	}
+	hashmap_entry_init(&key, sha1hash(sha1));
+	obj_req = hashmap_get(object_requests, &key, sha1);
 	if (obj_req == NULL)
 		return error("Couldn't find request for %s in the queue", hex);
 
@@ -554,6 +555,12 @@ static void cleanup(struct walker *walker)
 	}
 }
 
+static int obj_req_cmp(const struct object_request *e1,
+		const struct object_request *e2, const unsigned char *sha1)
+{
+	return hashcmp(e1->sha1, sha1 ? sha1 : e2->sha1);
+}
+
 struct walker *get_http_walker(const char *url)
 {
 	char *s;
@@ -581,5 +588,10 @@ struct walker *get_http_walker(const char *url)
 	add_fill_function(walker, (int (*)(void *)) fill_active_slot);
 #endif
 
+	if (!object_requests) {
+		object_requests = xmalloc(sizeof(*object_requests));
+		hashmap_init(object_requests, (hashmap_cmp_fn)obj_req_cmp, 0);
+	}
+
 	return walker;
 }
-- 
EW

[PATCH 1/4] http-walker: remove unused parameter from fetch_object

[Eric Wong]

This parameter has not been used since commit 1d389ab65dc6
("Add support for parallel HTTP transfers") back in 2005

Signed-off-by: Eric Wong <e@80x24.org>
---
 http-walker.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/http-walker.c b/http-walker.c
index 2c721f0..9f28523 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -447,7 +447,7 @@ static void abort_object_request(struct object_request *obj_req)
 	release_object_request(obj_req);
 }
 
-static int fetch_object(struct walker *walker, struct alt_base *repo, unsigned char *sha1)
+static int fetch_object(struct walker *walker, unsigned char *sha1)
 {
 	char *hex = sha1_to_hex(sha1);
 	int ret = 0;
@@ -518,7 +518,7 @@ static int fetch(struct walker *walker, unsigned char *sha1)
 	struct walker_data *data = walker->data;
 	struct alt_base *altbase = data->alt;
 
-	if (!fetch_object(walker, altbase, sha1))
+	if (!fetch_object(walker, sha1))
 		return 0;
 	while (altbase) {
 		if (!http_fetch_pack(walker, altbase, sha1))
-- 
EW

[PATCH 2/4] http: avoid disconnecting on 404s for loose objects

[Eric Wong]

Signed-off-by: Eric Wong <e@80x24.org>
---
 http-walker.c |  9 +++++++++
 http.c        | 16 ++++++++++++++--
 2 files changed, 23 insertions(+), 2 deletions(-)

diff --git a/http-walker.c b/http-walker.c
index 9f28523..48f2df4 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -488,6 +488,15 @@ static int fetch_object(struct walker *walker, unsigned char *sha1)
 		req->localfile = -1;
 	}
 
+	/*
+	 * we turned off CURLOPT_FAILONERROR to avoid losing a
+	 * persistent connection and got CURLE_OK.
+	 */
+	if (req->http_code == 404 && req->curl_result == CURLE_OK &&
+			(starts_with(req->url, "http://") ||
+			 starts_with(req->url, "https://")))
+		req->curl_result = CURLE_HTTP_RETURNED_ERROR;
+
 	if (obj_req->state == ABORTED) {
 		ret = error("Request for %s aborted", hex);
 	} else if (req->curl_result != CURLE_OK &&
diff --git a/http.c b/http.c
index d8b2bec..e81dd13 100644
--- a/http.c
+++ b/http.c
@@ -1975,8 +1975,19 @@ static size_t fwrite_sha1_file(char *ptr, size_t eltsize, size_t nmemb,
 	unsigned char expn[4096];
 	size_t size = eltsize * nmemb;
 	int posn = 0;
-	struct http_object_request *freq =
-		(struct http_object_request *)data;
+	struct http_object_request *freq = data;
+	struct active_request_slot *slot = freq->slot;
+
+	if (slot) {
+		CURLcode c = curl_easy_getinfo(slot->curl, CURLINFO_HTTP_CODE,
+						&slot->http_code);
+		if (c != CURLE_OK)
+			die("BUG: curl_easy_getinfo for HTTP code failed: %s",
+				curl_easy_strerror(c));
+		if (slot->http_code >= 400)
+			return size;
+	}
+
 	do {
 		ssize_t retval = xwrite(freq->localfile,
 					(char *) ptr + posn, size - posn);
@@ -2097,6 +2108,7 @@ struct http_object_request *new_http_object_request(const char *base_url,
 	freq->slot = get_active_slot();
 
 	curl_easy_setopt(freq->slot->curl, CURLOPT_FILE, freq);
+	curl_easy_setopt(freq->slot->curl, CURLOPT_FAILONERROR, 0);
 	curl_easy_setopt(freq->slot->curl, CURLOPT_WRITEFUNCTION, fwrite_sha1_file);
 	curl_easy_setopt(freq->slot->curl, CURLOPT_ERRORBUFFER, freq->errorstr);
 	curl_easy_setopt(freq->slot->curl, CURLOPT_URL, freq->url);
-- 
EW

[PATCH 3/4] http-walker: reduce O(n) ops with doubly-linked list

[Eric Wong]

Using the a Linux-kernel-derived doubly-linked list
implementation from the Userspace RCU library allows us to
enqueue and delete items from the object request queue in
constant time (and branchlessly!).

The downside is this costs us an additional pointer per object
request, but allow greater performance with large repos over
dumb stores while improving readability.

Signed-off-by: Eric Wong <e@80x24.org>
---
 http-walker.c |  41 ++++++---------
 list.h        | 164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 179 insertions(+), 26 deletions(-)
 create mode 100644 list.h

diff --git a/http-walker.c b/http-walker.c
index 48f2df4..b9fe33a 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -2,6 +2,7 @@
 #include "commit.h"
 #include "walker.h"
 #include "http.h"
+#include "list.h"
 
 struct alt_base {
 	char *base;
@@ -23,7 +24,7 @@ struct object_request {
 	struct alt_base *repo;
 	enum object_request_state state;
 	struct http_object_request *req;
-	struct object_request *next;
+	struct list_head node;
 };
 
 struct alternates_request {
@@ -41,7 +42,7 @@ struct walker_data {
 	struct alt_base *alt;
 };
 
-static struct object_request *object_queue_head;
+static LIST_HEAD(object_queue_head);
 
 static void fetch_alternates(struct walker *walker, const char *base);
 
@@ -110,19 +111,11 @@ static void process_object_response(void *callback_data)
 
 static void release_object_request(struct object_request *obj_req)
 {
-	struct object_request *entry = object_queue_head;
 
 	if (obj_req->req !=NULL && obj_req->req->localfile != -1)
 		error("fd leakage in release: %d", obj_req->req->localfile);
-	if (obj_req == object_queue_head) {
-		object_queue_head = obj_req->next;
-	} else {
-		while (entry->next != NULL && entry->next != obj_req)
-			entry = entry->next;
-		if (entry->next == obj_req)
-			entry->next = entry->next->next;
-	}
 
+	list_del(&obj_req->node);
 	free(obj_req);
 }
 
@@ -130,8 +123,10 @@ static void release_object_request(struct object_request *obj_req)
 static int fill_active_slot(struct walker *walker)
 {
 	struct object_request *obj_req;
+	struct list_head *pos, *tmp, *head = &object_queue_head;
 
-	for (obj_req = object_queue_head; obj_req; obj_req = obj_req->next) {
+	list_for_each_safe(pos, tmp, head) {
+		obj_req = list_entry(pos, struct object_request, node);
 		if (obj_req->state == WAITING) {
 			if (has_sha1_file(obj_req->sha1))
 				obj_req->state = COMPLETE;
@@ -148,7 +143,6 @@ static int fill_active_slot(struct walker *walker)
 static void prefetch(struct walker *walker, unsigned char *sha1)
 {
 	struct object_request *newreq;
-	struct object_request *tail;
 	struct walker_data *data = walker->data;
 
 	newreq = xmalloc(sizeof(*newreq));
@@ -157,18 +151,9 @@ static void prefetch(struct walker *walker, unsigned char *sha1)
 	newreq->repo = data->alt;
 	newreq->state = WAITING;
 	newreq->req = NULL;
-	newreq->next = NULL;
 
 	http_is_verbose = walker->get_verbosely;
-
-	if (object_queue_head == NULL) {
-		object_queue_head = newreq;
-	} else {
-		tail = object_queue_head;
-		while (tail->next != NULL)
-			tail = tail->next;
-		tail->next = newreq;
-	}
+	list_add_tail(&newreq->node, &object_queue_head);
 
 #ifdef USE_CURL_MULTI
 	fill_active_slots();
@@ -451,11 +436,15 @@ static int fetch_object(struct walker *walker, unsigned char *sha1)
 {
 	char *hex = sha1_to_hex(sha1);
 	int ret = 0;
-	struct object_request *obj_req = object_queue_head;
+	struct object_request *obj_req = NULL;
 	struct http_object_request *req;
+	struct list_head *pos, *head = &object_queue_head;
 
-	while (obj_req != NULL && hashcmp(obj_req->sha1, sha1))
-		obj_req = obj_req->next;
+	list_for_each(pos, head) {
+		obj_req = list_entry(pos, struct object_request, node);
+		if (!hashcmp(obj_req->sha1, sha1))
+			break;
+	}
 	if (obj_req == NULL)
 		return error("Couldn't find request for %s in the queue", hex);
 
diff --git a/list.h b/list.h
new file mode 100644
index 0000000..f65edce
--- /dev/null
+++ b/list.h
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2002 Free Software Foundation, Inc.
+ * (originally part of the GNU C Library and Userspace RCU)
+ * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
+ *
+ * Copyright (C) 2009 Pierre-Marc Fournier
+ * Conversion to RCU list.
+ * Copyright (C) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see
+ * <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef LIST_H
+#define LIST_H	1
+
+/*
+ * The definitions of this file are adopted from those which can be
+ * found in the Linux kernel headers to enable people familiar with the
+ * latter find their way in these sources as well.
+ */
+
+/* Basic type for the double-link list. */
+struct list_head {
+	struct list_head *next, *prev;
+};
+
+/* Define a variable with the head and tail of the list. */
+#define LIST_HEAD(name) \
+	struct list_head name = { &(name), &(name) }
+
+/* Initialize a new list head. */
+#define INIT_LIST_HEAD(ptr) \
+	(ptr)->next = (ptr)->prev = (ptr)
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+/* Add new element at the head of the list. */
+static inline void list_add(struct list_head *newp, struct list_head *head)
+{
+	head->next->prev = newp;
+	newp->next = head->next;
+	newp->prev = head;
+	head->next = newp;
+}
+
+/* Add new element at the tail of the list. */
+static inline void list_add_tail(struct list_head *newp, struct list_head *head)
+{
+	head->prev->next = newp;
+	newp->next = head;
+	newp->prev = head->prev;
+	head->prev = newp;
+}
+
+/* Remove element from list. */
+static inline void __list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+/* Remove element from list. */
+static inline void list_del(struct list_head *elem)
+{
+	__list_del(elem->prev, elem->next);
+}
+
+/* Remove element from list, initializing the element's list pointers. */
+static inline void list_del_init(struct list_head *elem)
+{
+	list_del(elem);
+	INIT_LIST_HEAD(elem);
+}
+
+/* Delete from list, add to another list as head. */
+static inline void list_move(struct list_head *elem, struct list_head *head)
+{
+	__list_del(elem->prev, elem->next);
+	list_add(elem, head);
+}
+
+/* Replace an old entry. */
+static inline void list_replace(struct list_head *old, struct list_head *newp)
+{
+	newp->next = old->next;
+	newp->prev = old->prev;
+	newp->prev->next = newp;
+	newp->next->prev = newp;
+}
+
+/* Join two lists. */
+static inline void list_splice(struct list_head *add, struct list_head *head)
+{
+	/* Do nothing if the list which gets added is empty. */
+	if (add != add->next) {
+		add->next->prev = head;
+		add->prev->next = head->next;
+		head->next->prev = add->prev;
+		head->next = add->next;
+	}
+}
+
+/* Get typed element from list at a given position. */
+#define list_entry(ptr, type, member) \
+	((type *) ((char *) (ptr) - offsetof(type, member)))
+
+/* Get first entry from a list. */
+#define list_first_entry(ptr, type, member) \
+	list_entry((ptr)->next, type, member)
+
+/* Iterate forward over the elements of the list. */
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); pos = pos->next)
+
+/*
+ * Iterate forward over the elements list. The list elements can be
+ * removed from the list while doing this.
+ */
+#define list_for_each_safe(pos, p, head) \
+	for (pos = (head)->next, p = pos->next; \
+		pos != (head); \
+		pos = p, p = pos->next)
+
+/* Iterate backward over the elements of the list. */
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev; pos != (head); pos = pos->prev)
+
+/*
+ * Iterate backwards over the elements list. The list elements can be
+ * removed from the list while doing this.
+ */
+#define list_for_each_prev_safe(pos, p, head) \
+	for (pos = (head)->prev, p = pos->prev; \
+		pos != (head); \
+		pos = p, p = pos->prev)
+
+static inline int list_empty(struct list_head *head)
+{
+	return head == head->next;
+}
+
+static inline void list_replace_init(struct list_head *old,
+				     struct list_head *newp)
+{
+	struct list_head *head = old->next;
+
+	list_del(old);
+	list_add_tail(newp, head);
+	INIT_LIST_HEAD(old);
+}
+
+#endif /* LIST_H */
-- 
EW

[PATCH 4/4] http-walker: use hashmap to eliminate list scan

[Eric Wong]

We can reduce list walking in fill_active_slot by deleting items
as we walk through the object request queue of pending objects.

However, we still need to maintain a mapping of live objects
for fetch_object, so introduce the use of a hashmap to keep
track of all live object requests in O(1) average time.

Signed-off-by: Eric Wong <e@80x24.org>
---
 http-walker.c | 43 ++++++++++++++++++++++++++++---------------
 1 file changed, 28 insertions(+), 15 deletions(-)

diff --git a/http-walker.c b/http-walker.c
index b9fe33a..c6d795f 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -3,6 +3,7 @@
 #include "walker.h"
 #include "http.h"
 #include "list.h"
+#include "hashmap.h"
 
 struct alt_base {
 	char *base;
@@ -19,10 +20,11 @@ enum object_request_state {
 };
 
 struct object_request {
+	struct hashmap_entry ent;
+	enum object_request_state state;
 	struct walker *walker;
 	unsigned char sha1[20];
 	struct alt_base *repo;
-	enum object_request_state state;
 	struct http_object_request *req;
 	struct list_head node;
 };
@@ -43,6 +45,7 @@ struct walker_data {
 };
 
 static LIST_HEAD(object_queue_head);
+static struct hashmap *object_requests;
 
 static void fetch_alternates(struct walker *walker, const char *base);
 
@@ -116,6 +119,7 @@ static void release_object_request(struct object_request *obj_req)
 		error("fd leakage in release: %d", obj_req->req->localfile);
 
 	list_del(&obj_req->node);
+	hashmap_remove(object_requests, obj_req, obj_req->sha1);
 	free(obj_req);
 }
 
@@ -127,13 +131,12 @@ static int fill_active_slot(struct walker *walker)
 
 	list_for_each_safe(pos, tmp, head) {
 		obj_req = list_entry(pos, struct object_request, node);
-		if (obj_req->state == WAITING) {
-			if (has_sha1_file(obj_req->sha1))
-				obj_req->state = COMPLETE;
-			else {
-				start_object_request(walker, obj_req);
-				return 1;
-			}
+		list_del(pos);
+		if (has_sha1_file(obj_req->sha1))
+			obj_req->state = COMPLETE;
+		else {
+			start_object_request(walker, obj_req);
+			return 1;
 		}
 	}
 	return 0;
@@ -146,6 +149,8 @@ static void prefetch(struct walker *walker, unsigned char *sha1)
 	struct walker_data *data = walker->data;
 
 	newreq = xmalloc(sizeof(*newreq));
+	hashmap_entry_init(&newreq->ent, sha1hash(sha1));
+	hashmap_add(object_requests, &newreq->ent);
 	newreq->walker = walker;
 	hashcpy(newreq->sha1, sha1);
 	newreq->repo = data->alt;
@@ -436,15 +441,12 @@ static int fetch_object(struct walker *walker, unsigned char *sha1)
 {
 	char *hex = sha1_to_hex(sha1);
 	int ret = 0;
-	struct object_request *obj_req = NULL;
+	struct object_request *obj_req;
+	struct hashmap_entry key;
 	struct http_object_request *req;
-	struct list_head *pos, *head = &object_queue_head;
 
-	list_for_each(pos, head) {
-		obj_req = list_entry(pos, struct object_request, node);
-		if (!hashcmp(obj_req->sha1, sha1))
-			break;
-	}
+	hashmap_entry_init(&key, sha1hash(sha1));
+	obj_req = hashmap_get(object_requests, &key, sha1);
 	if (obj_req == NULL)
 		return error("Couldn't find request for %s in the queue", hex);
 
@@ -554,6 +556,12 @@ static void cleanup(struct walker *walker)
 	}
 }
 
+static int obj_req_cmp(const struct object_request *e1,
+		const struct object_request *e2, const unsigned char *sha1)
+{
+	return hashcmp(e1->sha1, sha1 ? sha1 : e2->sha1);
+}
+
 struct walker *get_http_walker(const char *url)
 {
 	char *s;
@@ -581,5 +589,10 @@ struct walker *get_http_walker(const char *url)
 	add_fill_function(walker, (int (*)(void *)) fill_active_slot);
 #endif
 
+	if (!object_requests) {
+		object_requests = xmalloc(sizeof(*object_requests));
+		hashmap_init(object_requests, (hashmap_cmp_fn)obj_req_cmp, 0);
+	}
+
 	return walker;
 }
-- 
EW