summaryrefslogtreecommitdiff
path: root/http-walker.c
diff options
context:
space:
mode:
authorEric Wong <e@80x24.org>2016-07-11 20:51:31 +0000
committerJunio C Hamano <gitster@pobox.com>2016-07-12 15:17:42 -0700
commit94e99012fc7a02c5504214294279fa49b4cc8ce3 (patch)
tree6d60fd9cd99b5ea19a3fc9a32e48bcd74342fc42 /http-walker.c
parent17966c0a63d25b1cc2dd1e98d30873e643bd581f (diff)
downloadgit-94e99012fc7a02c5504214294279fa49b4cc8ce3.tar.gz
http-walker: reduce O(n) ops with doubly-linked list
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. This change reduces enqueue times in the prefetch() function where object request queue could grow to several thousand objects. I left out the list_for_each_entry* family macros from list.h which relied on the __typeof__ operator as we support platforms without it. Thus, list_entry (aka "container_of") needs to be called explicitly inside macro-wrapped for loops. The downside is this costs us an additional pointer per object request, but this is offset by reduced overhead on queue operations leading to improved performance and shorter queue depths. Signed-off-by: Eric Wong <e@80x24.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'http-walker.c')
-rw-r--r--http-walker.c42
1 files changed, 15 insertions, 27 deletions
diff --git a/http-walker.c b/http-walker.c
index 48f2df4d31..0b2425531a 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,10 @@ 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 +122,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 +142,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 +150,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 +435,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);