cache: implement LRU cache to hold glfs objects

Problem:
-------

1. Currently, each cli command take ~5 secs for execution. The Maximum
latency is due to initializing a glfs object (glfs_init() and friends).

2. OOM kills due to glfs_fini() leaks (~10MB per object)

Solution:
--------

Caching bipasses glfs_init() calls from the very next command, as in the first
command it goes via the glfs_init route, since there will be cache miss.
Hence with caching cli command on a local machine should take ~1 sec.

ATM, the cache query looks at the volume name only, as the host name will be
localhost in our case and transport will be tcp 24007 always.

The default cache capacity is 5 i.e there can be a max of five glfs entries in
the cache, anything more will lead to release of least recently used object.

This way, if there are <= 5 volume in use for block, there will be no
glfs_fini() calls, hence no leaks, no OOM's.

The next patch will help in making cache capacity configurable.

Change-Id: Ia891451cb92cf09959c1aff85976d78302ec7014
Signed-off-by: Prasanna Kumar Kalever <prasanna.kalever@redhat.com>
[ndevos: correct compiling+linking against libgfapi.so]

4 files changed, 393 insertions, 3 deletions

diff --git a/utils/Makefile.am b/utils/Makefile.am
index 40442c3..0da7857 100644
--- a/utils/Makefile.am
+++ b/utils/Makefile.am
@@ -1,10 +1,13 @@
 noinst_LTLIBRARIES = libgb.la
 
-libgb_la_SOURCES = common.c utils.c
+libgb_la_SOURCES = common.c utils.c lru.c
 
-noinst_HEADERS = common.h utils.h
+noinst_HEADERS = common.h utils.h lru.h list.h
 
-libgb_la_CFLAGS = -DDATADIR=\"$(localstatedir)\" -I$(top_builddir)/rpc/rpcl
+libgb_la_CFLAGS = $(GFAPI_CFLAGS) -DDATADIR=\"$(localstatedir)\"          \
+                  -I$(top_builddir)/rpc/rpcl
+
+libgb_la_LIBADD = $(GFAPI_LIBS)
 
 libgb_ladir = $(includedir)/gluster-block/utils
 
diff --git a/utils/list.h b/utils/list.h
new file mode 100644
index 0000000..98b5b25
--- /dev/null
+++ b/utils/list.h
@@ -0,0 +1,244 @@
+#ifndef __LIST_H
+#define __LIST_H
+
+/* This file is from Linux Kernel (include/linux/list.h)
+ * and modified by simply removing hardware prefetching of list items.
+ * Here by copyright, credits attributed to wherever they belong.
+ * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)
+ */
+
+/*
+ * Simple doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+struct list_head {
+	struct list_head *next, *prev;
+};
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+	struct list_head name = LIST_HEAD_INIT(name)
+
+#define INIT_LIST_HEAD(ptr) do { \
+	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
+} while (0)
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head *new,
+			      struct list_head *prev,
+			      struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
+ */
+static inline void list_del(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	entry->next = (void *) 0;
+	entry->prev = (void *) 0;
+}
+
+/**
+ * list_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ */
+static inline void list_del_init(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	INIT_LIST_HEAD(entry);
+}
+
+/**
+ * list_move - delete from one list and add as another's head
+ * @list: the entry to move
+ * @head: the head that will precede our entry
+ */
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add(list, head);
+}
+
+/**
+ * list_move_tail - delete from one list and add as another's tail
+ * @list: the entry to move
+ * @head: the head that will follow our entry
+ */
+static inline void list_move_tail(struct list_head *list,
+				  struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add_tail(list, head);
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(struct list_head *head)
+{
+	return head->next == head;
+}
+
+static inline void __list_splice(struct list_head *list,
+				 struct list_head *head)
+{
+	struct list_head *first = list->next;
+	struct list_head *last = list->prev;
+	struct list_head *at = head->next;
+
+	first->prev = head;
+	head->next = first;
+
+	last->next = at;
+	at->prev = last;
+}
+
+/**
+ * list_splice - join two lists
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice(struct list_head *list, struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head);
+}
+
+/**
+ * list_splice_init - join two lists and reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_init(struct list_head *list,
+				    struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr:	the &struct list_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_entry(ptr, type, member) \
+	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+
+/**
+ * list_for_each	-	iterate over a list
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ */
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); \
+        	pos = pos->next)
+/**
+ * list_for_each_prev	-	iterate over a list backwards
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ */
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev; pos != (head); \
+        	pos = pos->prev)
+
+/**
+ * list_for_each_safe	-	iterate over a list safe against removal of list entry
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @n:		another &struct list_head to use as temporary storage
+ * @head:	the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+	for (pos = (head)->next, n = pos->next; pos != (head); \
+		pos = n, n = pos->next)
+
+/**
+ * list_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop counter.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry(pos, head, member)				\
+	for (pos = list_entry((head)->next, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos:	the type * to use as a loop counter.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_entry((head)->next, typeof(*pos), member),	\
+		n = list_entry(pos->member.next, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
+
+
+#endif
diff --git a/utils/lru.c b/utils/lru.c
new file mode 100644
index 0000000..f1e884b
--- /dev/null
+++ b/utils/lru.c
@@ -0,0 +1,112 @@
+/*
+  Copyright (c) 2017 Red Hat, Inc. <http://www.redhat.com>
+  This file is part of gluster-block.
+
+  This file is licensed to you under your choice of the GNU Lesser
+  General Public License, version 3 or any later version (LGPLv3 or
+  later), or the GNU General Public License, version 2 (GPLv2), in all
+  cases as published by the Free Software Foundation.
+*/
+
+# include "lru.h"
+
+# define  LRU_CAPACITY  5
+
+
+static struct list_head Cache;
+static int lruCount;
+
+typedef struct Entry {
+  char volume[256];
+  glfs_t *glfs;
+
+  struct list_head list;
+} Entry;
+
+
+static void
+releaseColdEntry(void)
+{
+  Entry *tmp;
+  struct list_head *pos, *q = &Cache;
+
+
+  list_for_each_prev(pos, q) {
+    tmp = list_entry(pos, Entry, list);
+    list_del(pos);
+
+    glfs_fini(tmp->glfs);
+    GB_FREE(tmp);
+    lruCount--;
+
+    break;
+  }
+}
+
+
+int
+appendNewEntry(const char *volname, glfs_t *fs)
+{
+  Entry *tmp;
+
+
+  if (lruCount == LRU_CAPACITY) {
+    releaseColdEntry();
+  }
+
+  if (GB_ALLOC(tmp) < 0) {
+    return -1;
+  }
+  strcpy(tmp->volume, volname);
+  tmp->glfs = fs;
+
+  list_add(&(tmp->list), &Cache);
+
+  lruCount++;
+
+  return 0;
+}
+
+
+static void
+boostEntryWarmness(const char *volname)
+{
+  Entry *tmp;
+  struct list_head *pos, *q;
+
+
+  list_for_each_safe(pos, q, &Cache){
+    tmp = list_entry(pos, Entry, list);
+    if (!strcmp(tmp->volume, volname)) {
+      list_del(pos);
+      list_add(&(tmp->list), &Cache);
+      break;
+    }
+  }
+}
+
+
+glfs_t *
+queryCache(const char *volname)
+{
+  Entry *tmp;
+  struct list_head *pos, *q, *r = &Cache;
+
+
+  list_for_each_safe(pos, q, r){
+    tmp = list_entry(pos, Entry, list);
+    if (!strcmp(tmp->volume, volname)) {
+      boostEntryWarmness(volname);
+      return tmp->glfs;
+    }
+  }
+
+  return NULL;
+}
+
+
+void
+initCache(void)
+{
+  INIT_LIST_HEAD(&Cache);
+}
diff --git a/utils/lru.h b/utils/lru.h
new file mode 100644
index 0000000..e9af217
--- /dev/null
+++ b/utils/lru.h
@@ -0,0 +1,31 @@
+/*
+  Copyright (c) 2017 Red Hat, Inc. <http://www.redhat.com>
+  This file is part of gluster-block.
+
+  This file is licensed to you under your choice of the GNU Lesser
+  General Public License, version 3 or any later version (LGPLv3 or
+  later), or the GNU General Public License, version 2 (GPLv2), in all
+  cases as published by the Free Software Foundation.
+*/
+
+
+# ifndef   _LRU_H
+# define   _LRU_H   1
+
+# include  <api/glfs.h>
+
+# include  "common.h"
+# include  "list.h"
+
+
+void
+initCache(void);
+
+glfs_t *
+queryCache(const char *volname);
+
+int
+appendNewEntry(const char *volname, glfs_t *glfs);
+
+
+# endif /* _LRU_H */