Add caching infrastructure

This enables internal caching of page output.

Page requests are split into four groups:
  1) repo listing (front page)
  2) repo summary
  3) repo pages w/symbolic references in query string
  4) repo pages w/constant sha1's in query string

Each group has a TTL specified in minutes. When a page is requested, a cached
filename is stat(2)'ed and st_mtime is compared to time(2). If TTL has expired
(or the file didn't exist), the cached file is regenerated.

When generating a cached file, locking is used to avoid parallell processing
of the request. If multiple processes tries to aquire the same lock, the ones
who fail to get the lock serves the (expired) cached file. If the cached file
don't exist, the process instead calls sched_yield(2) before restarting the
request processing.

Signed-off-by: Lars Hjemli <hjemli@gmail.com>

9 files changed, 353 insertions, 28 deletions

diff --git a/.gitignore b/.gitignore
index 4eaec97..c4c9ac3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
 # Files I don't care to see in git-status/commit
 cgit
 *.o
+*~
diff --git a/Makefile b/Makefile
index 4e72b07..243f590 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,9 @@ INSTALL_BIN = /var/www/htdocs/cgit.cgi
 INSTALL_CSS = /var/www/htdocs/cgit.css
 
 EXTLIBS = ../git/libgit.a ../git/xdiff/lib.a -lz -lcrypto
-OBJECTS = cgit.o config.o html.o
+OBJECTS = cgit.o config.o html.o cache.o
+
+CFLAGS += -Wall
 
 all: cgit
 
@@ -15,6 +17,6 @@ clean:
         rm -f cgit *.o
 
 cgit: $(OBJECTS)
-        $(CC) -o cgit $(OBJECTS) $(EXTLIBS)
+        $(CC) $(CFLAGS) -o cgit $(OBJECTS) $(EXTLIBS)
 
 $(OBJECTS): cgit.h git.h
diff --git a/README b/README
new file mode 100644
index 0000000..5917c37
--- /dev/null
+++ b/README
@@ -0,0 +1,54 @@
+Cache algorithm
+===============
+
+Cgit normally returns cached pages when invoked. If there is no cache file, or
+the cache file has expired, it is regenerated. Finally, the cache file is 
+printed on stdout.
+
+When it is decided that a cache file needs to be regenerated, an attempt is 
+made to create a corresponding lockfile. If this fails, the process gives up
+and uses the expired cache file instead.
+
+When there is no cache file for a request, an attempt is made to create a 
+corresponding lockfile. If this fails, the process calls sched_yield(2) before
+restarting the request handling.
+
+In pseudocode:
+
+        name = generate_cache_name(request);
+top:
+        if (!exists(name)) {
+                if (lock_cache(name)) {
+                        generate_cache(request, name);
+                        unlock_cache(name);
+                } else {
+                        sched_yield();
+                        goto top;
+                }
+        } else if (expired(name)) {
+                if (lock_cache(name)) {
+                        generate_cache(request, name);
+                        unlock_cache(name);
+                }
+        }
+        print_file(name);
+
+
+The following options can be set in /etc/cgitrc to control cache behaviour:
+  cache-root:        root directory for cache files
+  cache-root-ttl:    TTL for the repo listing page
+  cache-repo-ttl:    TTL for any repos summary page
+  cache-dynamic-ttl: TTL for pages with symbolic references (not SHA1)
+  cache-static-ttl:  TTL for pages with sha1 references
+
+TTL is specified in minutes, -1 meaning "infinite caching". 
+
+
+Naming of cache files
+---------------------
+Repository listing:  <cachedir>/index.html
+Repository summary:  <cachedir>/<repo>/index.html
+Repository subpage:  <cachedir>/<repo>/<page>/<querystring>.html
+
+The corresponding lock files have a ".lock" suffix.
+
diff --git a/cache.c b/cache.c
new file mode 100644
index 0000000..1be1ea4
--- /dev/null
+++ b/cache.c
@@ -0,0 +1,86 @@
+#include "cgit.h"
+
+const int NOLOCK = -1;
+
+int cache_lookup(struct cacheitem *item)
+{
+        if (!cgit_query_repo) {
+                item->name = xstrdup(fmt("%s/index.html", cgit_cache_root));
+                item->ttl = cgit_cache_root_ttl;
+        } else if (!cgit_query_page) {
+                item->name = xstrdup(fmt("%s/%s/index.html", cgit_cache_root, 
+                           cgit_query_repo));
+                item->ttl = cgit_cache_repo_ttl;
+        } else {
+                item->name = xstrdup(fmt("%s/%s/%s/%s.html", cgit_cache_root, 
+                           cgit_query_repo, cgit_query_page, 
+                           cgit_querystring));
+                if (cgit_query_has_symref)
+                        item->ttl = cgit_cache_dynamic_ttl;
+                else if (cgit_query_has_sha1)
+                        item->ttl = cgit_cache_static_ttl;
+                else
+                        item->ttl = cgit_cache_repo_ttl;
+        }
+        if (stat(item->name, &item->st)) {
+                item->st.st_mtime = 0;
+                return 0;
+        }
+        return 1;
+}
+
+int cache_create_dirs()
+{
+        char *path;
+
+        if (!cgit_query_repo)
+                return 0;
+
+        path = fmt("%s/%s", cgit_cache_root, cgit_query_repo);
+        if (mkdir(path, S_IRWXU) && errno!=EEXIST)
+                return 0;
+
+        if (cgit_query_page) {
+                path = fmt("%s/%s/%s", cgit_cache_root, cgit_query_repo, 
+                           cgit_query_page);
+                if (mkdir(path, S_IRWXU) && errno!=EEXIST)
+                        return 0;
+        }
+        return 1;
+}
+
+int cache_lock(struct cacheitem *item)
+{
+        int ret;
+        char *lockfile = fmt("%s.lock", item->name);
+
+ top:  
+        item->fd = open(lockfile, O_WRONLY | O_CREAT | O_EXCL, S_IRUSR|S_IWUSR);
+        if (item->fd == NOLOCK && errno == ENOENT && cache_create_dirs())
+                goto top;
+        if (item->fd == NOLOCK && errno == EEXIST) {
+                struct stat st;
+                time_t t;
+                if (stat(lockfile, &st))
+                        return ret;
+                t = time(NULL);
+                if (t-st.st_mtime > cgit_cache_max_create_time && 
+                    !unlink(lockfile))
+                        goto top;
+                return 0;
+        }
+        return (item->fd > 0);
+}
+
+int cache_unlock(struct cacheitem *item)
+{
+        close(item->fd);
+        return (rename(fmt("%s.lock", item->name), item->name) == 0);
+}
+
+int cache_expired(struct cacheitem *item)
+{
+        if (item->ttl < 0)
+                return 0;
+        return item->st.st_mtime + item->ttl * 60 < time(NULL);
+}
diff --git a/cgit.c b/cgit.c
index 4c14f77..09c857c 100644
--- a/cgit.c
+++ b/cgit.c
@@ -10,29 +10,47 @@ static const char cgit_error[] =
 static const char cgit_lib_error[] =
 "<div class='error'>%s: %s</div>";
 
+int htmlfd = 0;
 
-char *cgit_root         = "/var/git";
+char *cgit_root         = "/usr/src/git";
 char *cgit_root_title   = "Git repository browser";
 char *cgit_css          = "/cgit.css";
 char *cgit_logo         = "/git-logo.png";
 char *cgit_logo_link    = "http://www.kernel.org/pub/software/scm/git/docs/";
 char *cgit_virtual_root = NULL;
 
+char *cgit_cache_root   = "/var/cache/cgit";
+
+int cgit_cache_root_ttl        =  5;
+int cgit_cache_repo_ttl        =  5;
+int cgit_cache_dynamic_ttl     =  5;
+int cgit_cache_static_ttl      = -1;
+int cgit_cache_max_create_time =  5;
+
 char *cgit_repo_name    = NULL;
 char *cgit_repo_desc    = NULL;
 char *cgit_repo_owner   = NULL;
 
+int cgit_query_has_symref = 0;
+int cgit_query_has_sha1   = 0;
+
+char *cgit_querystring  = NULL;
 char *cgit_query_repo   = NULL;
 char *cgit_query_page   = NULL;
 char *cgit_query_head   = NULL;
+char *cgit_query_sha1   = NULL;
+
+struct cacheitem cacheitem;
 
 int cgit_parse_query(char *txt, configfn fn)
 {
-        char *t = txt, *value = NULL, c;
+        char *t, *value = NULL, c;
 
         if (!txt)
                 return 0;
 
+        t = txt = xstrdup(txt);
+ 
         while((c=*t) != '\0') {
                 if (c=='=') {
                         *t = '\0';
@@ -82,8 +100,13 @@ void cgit_querystring_cb(const char *name, const char *value)
                 cgit_query_repo = xstrdup(value);
         else if (!strcmp(name, "p"))
                 cgit_query_page = xstrdup(value);
-        else if (!strcmp(name, "h"))
+        else if (!strcmp(name, "h")) {
                 cgit_query_head = xstrdup(value);
+                cgit_query_has_symref = 1;
+        } else if (!strcmp(name, "id")) {
+                cgit_query_sha1 = xstrdup(value);
+                cgit_query_has_sha1 = 1;
+        }
 }
 
 char *cgit_repourl(const char *reponame)
@@ -136,9 +159,32 @@ static int cgit_print_branch_cb(const char *refname, const unsigned char *sha1,
         return 0;
 }
 
+/* Sun, 06 Nov 1994 08:49:37 GMT */
+static char *http_date(time_t t)
+{
+        static char day[][4] = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
+        static char month[][4] = {"Jan", "Feb", "Mar", "Apr", "May", "Jun",
+                                  "Jul", "Aug", "Sep", "Oct", "Now", "Dec"};
+        struct tm *tm = gmtime(&t);
+        return fmt("%s, %02d %s %04d %02d:%02d:%02d GMT", day[tm->tm_wday],
+                   tm->tm_mday, month[tm->tm_mon], 1900+tm->tm_year,
+                   tm->tm_hour, tm->tm_min, tm->tm_sec);
+}
+
+static int ttl_seconds(int ttl)
+{
+        if (ttl<0)
+                return 60 * 60 * 24 * 365;
+        else 
+                return ttl * 60;
+}
+
 static void cgit_print_docstart(char *title)
 {
         html("Content-Type: text/html; charset=utf-8\n");
+        htmlf("Last-Modified: %s\n", http_date(cacheitem.st.st_mtime));
+        htmlf("Expires: %s\n", http_date(cacheitem.st.st_mtime + 
+                                         ttl_seconds(cacheitem.ttl)));
         html("\n");
         html(cgit_doctype);
         html("<html>\n");
@@ -175,6 +221,7 @@ static void cgit_print_repolist()
         struct stat st;
         char *name;
 
+        chdir(cgit_root);
         cgit_print_docstart(cgit_root_title);
         cgit_print_pageheader(cgit_root_title);
 
@@ -197,7 +244,7 @@ static void cgit_print_repolist()
                         continue;
 
                 cgit_repo_name = cgit_repo_desc = cgit_repo_owner = NULL;
-                name = fmt("%s/.git/info/cgit", de->d_name);
+                name = fmt("%s/info/cgit", de->d_name);
                 if (cgit_read_config(name, cgit_repo_config_cb))
                         continue;
 
@@ -291,7 +338,7 @@ static void cgit_print_commit_shortlog(struct commit *commit)
         strftime(buf, sizeof(buf), "%Y-%m-%d %H:%M:%S", time);
         html_txt(buf);
         html("</td><td>");
-        char *qry = fmt("h=%s", sha1_to_hex(commit->object.sha1));
+        char *qry = fmt("id=%s", sha1_to_hex(commit->object.sha1));
         char *url = cgit_pageurl(cgit_query_repo, "view", qry);
         html_link_open(url, NULL, NULL);
         html_txt(subject);
@@ -371,8 +418,8 @@ static void cgit_print_object(char *hex)
 
 static void cgit_print_repo_page()
 {
-        if (chdir(cgit_query_repo) || 
-            cgit_read_config(".git/info/cgit", cgit_repo_config_cb)) {
+        if (chdir(fmt("%s/%s", cgit_root, cgit_query_repo)) || 
+            cgit_read_config("info/cgit", cgit_repo_config_cb)) {
                 char *title = fmt("%s - %s", cgit_root_title, "Bad request");
                 cgit_print_docstart(title);
                 cgit_print_pageheader(title);
@@ -381,7 +428,7 @@ static void cgit_print_repo_page()
                 cgit_print_docend();
                 return;
         }
-        
+        setenv("GIT_DIR", fmt("%s/%s", cgit_root, cgit_query_repo), 1);
         char *title = fmt("%s - %s", cgit_repo_name, cgit_repo_desc);
         cgit_print_docstart(title);
         cgit_print_pageheader(title);
@@ -390,21 +437,61 @@ static void cgit_print_repo_page()
         else if (!strcmp(cgit_query_page, "log")) {
                 cgit_print_log(cgit_query_head, 0, 100);
         } else if (!strcmp(cgit_query_page, "view")) {
-                cgit_print_object(cgit_query_head);
+                cgit_print_object(cgit_query_sha1);
         }
         cgit_print_docend();
 }
 
-int main(int argc, const char **argv)
+static void cgit_fill_cache(struct cacheitem *item)
 {
-        if (cgit_read_config("/etc/cgitrc", cgit_global_config_cb))
-                die("Error reading config: %d %s", errno, strerror(errno));
-
-        chdir(cgit_root);
-        cgit_parse_query(getenv("QUERY_STRING"), cgit_querystring_cb);
+        htmlfd = item->fd;
+        item->st.st_mtime = time(NULL);
         if (cgit_query_repo)
                 cgit_print_repo_page();
         else
                 cgit_print_repolist();
+}
+
+static void cgit_refresh_cache(struct cacheitem *item)
+{
+ top:
+        if (!cache_lookup(item)) {
+                if (cache_lock(item)) {
+                        cgit_fill_cache(item);
+                        cache_unlock(item);
+                } else {
+                        sched_yield();
+                        goto top;
+                }
+        } else if (cache_expired(item)) {
+                if (cache_lock(item)) {
+                        cgit_fill_cache(item);
+                        cache_unlock(item);
+                }
+        }
+}
+
+static void cgit_print_cache(struct cacheitem *item)<