[PATCH 1/4] cache: get rid of search loop in cache_add()

[PATCH 1/4] cache: get rid of search loop in cache_add()

[Petr Tesarik]

The intention was that cache code is re-entrant, so all cache entries
should go through these states:

  1. free
  2. pending read
  3. used

The cache_add() function is used to move an entry from state 2 to 3, but
since the caller did not know cache entry pointer, it had to search the
pending list for a pending read for the given physical address. This is
not needed if cache_alloc() returns this pointer.

Signed-off-by: Petr Tesarik <ptesarik@suse.cz>
---
 cache.c        | 26 ++++++--------------------
 cache.h        | 10 ++++++++--
 makedumpfile.c |  8 +++++---
 3 files changed, 19 insertions(+), 25 deletions(-)

diff --git a/cache.c b/cache.c
index 0dd957c..700ba0c 100644
--- a/cache.c
+++ b/cache.c
@@ -20,12 +20,6 @@
 #include "cache.h"
 #include "print_info.h"
 
-struct cache_entry {
-	unsigned long long paddr;
-	void *bufptr;
-	struct cache_entry *next, *prev;
-};
-
 struct cache {
 	struct cache_entry *head, *tail;
 };
@@ -98,38 +92,30 @@ cache_search(unsigned long long paddr)
 	return NULL;		/* cache miss */
 }
 
-void *
+struct cache_entry *
 cache_alloc(unsigned long long paddr)
 {
 	struct cache_entry *entry = NULL;
 
 	if (avail) {
 		entry = &pool[--avail];
-		entry->paddr = paddr;
 		add_entry(&pending, entry);
 	} else if (pending.tail) {
 		entry = pending.tail;
-		entry->paddr = paddr;
 	} else if (used.tail) {
 		entry = used.tail;
 		remove_entry(&used, entry);
-		entry->paddr = paddr;
 		add_entry(&pending, entry);
 	} else
 		return NULL;
 
-	return entry->bufptr;
+	entry->paddr = paddr;
+	return entry;
 }
 
 void
-cache_add(unsigned long long paddr)
+cache_add(struct cache_entry *entry)
 {
-	struct cache_entry *entry;
-	for (entry = pending.head; entry; entry = entry->next) {
-		if (entry->paddr == paddr) {
-			remove_entry(&pending, entry);
-			add_entry(&used, entry);
-			break;
-		}
-	}
+	remove_entry(&pending, entry);
+	add_entry(&used, entry);
 }
diff --git a/cache.h b/cache.h
index 4730e12..dab8eb9 100644
--- a/cache.h
+++ b/cache.h
@@ -19,9 +19,15 @@
 #ifndef _CACHE_H
 #define _CACHE_H
 
+struct cache_entry {
+	unsigned long long paddr;
+	void *bufptr;
+	struct cache_entry *next, *prev;
+};
+
 int cache_init(void);
 void *cache_search(unsigned long long paddr);
-void *cache_alloc(unsigned long long paddr);
-void cache_add(unsigned long long paddr);
+struct cache_entry *cache_alloc(unsigned long long paddr);
+void cache_add(struct cache_entry *entry);
 
 #endif	/* _CACHE_H */
diff --git a/makedumpfile.c b/makedumpfile.c
index 74bc9db..828adeb 100644
--- a/makedumpfile.c
+++ b/makedumpfile.c
@@ -591,6 +591,7 @@ readmem(int type_addr, unsigned long long addr, void *bufptr, size_t size)
 	unsigned long long paddr, maddr = NOT_PADDR;
 	unsigned long long pgaddr;
 	void *pgbuf;
+	struct cache_entry *cached;
 
 next_page:
 	switch (type_addr) {
@@ -644,9 +645,10 @@ next_page:
 	pgaddr = PAGEBASE(paddr);
 	pgbuf = cache_search(pgaddr);
 	if (!pgbuf) {
-		pgbuf = cache_alloc(pgaddr);
-		if (!pgbuf)
+		cached = cache_alloc(pgaddr);
+		if (!cached)
 			goto error;
+		pgbuf = cached->bufptr;
 
 		if (info->flag_refiltering) {
 			if (!readpage_kdump_compressed(pgaddr, pgbuf))
@@ -658,7 +660,7 @@ next_page:
 			if (!readpage_elf(pgaddr, pgbuf))
 				goto error;
 		}
-		cache_add(pgaddr);
+		cache_add(cached);
 	}
 
 	memcpy(bufptr, pgbuf + PAGEOFFSET(paddr), read_size);
-- 
1.8.4.5


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec

[PATCH 2/4] cache: allow to return a page to the pool

[Petr Tesarik]

After a failed read, the page should no longer be pending, but rather
available for future allocation.

Signed-off-by: Petr Tesarik <ptesarik@suse.cz>
---
 cache.c        | 15 ++++++++++++---
 cache.h        |  1 +
 makedumpfile.c |  8 +++++---
 3 files changed, 18 insertions(+), 6 deletions(-)

diff --git a/cache.c b/cache.c
index 700ba0c..ad9f0f1 100644
--- a/cache.c
+++ b/cache.c
@@ -26,7 +26,8 @@ struct cache {
 
 /* 8 pages covers 4-level paging plus 4 data pages */
 #define CACHE_SIZE	8
-static struct cache_entry pool[CACHE_SIZE];
+static struct cache_entry entries[CACHE_SIZE];
+static struct cache_entry *pool[CACHE_SIZE];
 static int avail = CACHE_SIZE;
 
 static struct cache used, pending;
@@ -44,7 +45,8 @@ cache_init(void)
 			       strerror(errno));
 			return FALSE;
 		}
-		pool[i].bufptr = bufptr;
+		entries[i].bufptr = bufptr;
+		pool[i] = &entries[i];
 	}
 
 	return TRUE;
@@ -98,7 +100,7 @@ cache_alloc(unsigned long long paddr)
 	struct cache_entry *entry = NULL;
 
 	if (avail) {
-		entry = &pool[--avail];
+		entry = pool[--avail];
 		add_entry(&pending, entry);
 	} else if (pending.tail) {
 		entry = pending.tail;
@@ -119,3 +121,10 @@ cache_add(struct cache_entry *entry)
 	remove_entry(&pending, entry);
 	add_entry(&used, entry);
 }
+
+void
+cache_free(struct cache_entry *entry)
+{
+	remove_entry(&pending, entry);
+	pool[avail++] = entry;
+}
diff --git a/cache.h b/cache.h
index dab8eb9..0e65f97 100644
--- a/cache.h
+++ b/cache.h
@@ -29,5 +29,6 @@ int cache_init(void);
 void *cache_search(unsigned long long paddr);
 struct cache_entry *cache_alloc(unsigned long long paddr);
 void cache_add(struct cache_entry *entry);
+void cache_free(struct cache_entry *entry);
 
 #endif	/* _CACHE_H */
diff --git a/makedumpfile.c b/makedumpfile.c
index 828adeb..c62d035 100644
--- a/makedumpfile.c
+++ b/makedumpfile.c
@@ -652,13 +652,13 @@ next_page:
 
 		if (info->flag_refiltering) {
 			if (!readpage_kdump_compressed(pgaddr, pgbuf))
-				goto error;
+				goto error_cached;
 		} else if (info->flag_sadump) {
 			if (!readpage_sadump(pgaddr, pgbuf))
-				goto error;
+				goto error_cached;
 		} else {
 			if (!readpage_elf(pgaddr, pgbuf))
-				goto error;
+				goto error_cached;
 		}
 		cache_add(cached);
 	}
@@ -674,6 +674,8 @@ next_page:
 
 	return size_orig;
 
+error_cached:
+	cache_free(cached);
 error:
 	ERRMSG("type_addr: %d, addr:%llx, size:%zd\n", type_addr, addr, size_orig);
 	return FALSE;
-- 
1.8.4.5


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec

[PATCH 3/4] cache: do not allocate from the pending list

[Petr Tesarik]

Since pending entries are under read, they should not be reused. This
change allows recursive use of the cache (reading pages from within
readpage itself). Although this feature is not used by makedumpfile
right now, this was the original intention of the pending list.
The cache_alloc() function may return NULL if and only if the recursion
level is bigger than CACHE_SIZE.

Signed-off-by: Petr Tesarik <ptesarik@suse.cz>
---
 cache.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/cache.c b/cache.c
index ad9f0f1..344b4f6 100644
--- a/cache.c
+++ b/cache.c
@@ -101,16 +101,13 @@ cache_alloc(unsigned long long paddr)
 
 	if (avail) {
 		entry = pool[--avail];
-		add_entry(&pending, entry);
-	} else if (pending.tail) {
-		entry = pending.tail;
 	} else if (used.tail) {
 		entry = used.tail;
 		remove_entry(&used, entry);
-		add_entry(&pending, entry);
 	} else
 		return NULL;
 
+	add_entry(&pending, entry);
 	entry->paddr = paddr;
 	return entry;
 }
-- 
1.8.4.5


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec

[PATCH 4/4] cache: add hit/miss statistics to the final report

[Petr Tesarik]

Add the most basic cache statistics (pages hit and missed). Note that
the hit rate is not printed if cache was not used to avoid division
by zero.

Signed-off-by: Petr Tesarik <ptesarik@suse.cz>
---
 makedumpfile.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/makedumpfile.c b/makedumpfile.c
index c62d035..d778139 100644
--- a/makedumpfile.c
+++ b/makedumpfile.c
@@ -39,6 +39,10 @@ struct SplitBlock		*splitblock = NULL;
 
 char filename_stdout[] = FILENAME_STDOUT;
 
+/* Cache statistics */
+static unsigned long long	cache_hit;
+static unsigned long long	cache_miss;
+
 static void first_cycle(mdf_pfn_t start, mdf_pfn_t max, struct cycle *cycle)
 {
 	cycle->start_pfn = round(start, info->pfn_cyclic);
@@ -645,6 +649,7 @@ next_page:
 	pgaddr = PAGEBASE(paddr);
 	pgbuf = cache_search(pgaddr);
 	if (!pgbuf) {
+		++cache_miss;
 		cached = cache_alloc(pgaddr);
 		if (!cached)
 			goto error;
@@ -661,7 +666,8 @@ next_page:
 				goto error_cached;
 		}
 		cache_add(cached);
-	}
+	} else
+		++cache_hit;
 
 	memcpy(bufptr, pgbuf + PAGEOFFSET(paddr), read_size);
 
@@ -8294,6 +8300,11 @@ print_report(void)
 	REPORT_MSG("--------------------------------------------------\n");
 	REPORT_MSG("Total pages     : 0x%016llx\n", info->max_mapnr);
 	REPORT_MSG("\n");
+	REPORT_MSG("Cache hit: %lld, miss: %lld", cache_hit, cache_miss);
+	if (cache_hit + cache_miss)
+		REPORT_MSG(", hit rate: %.1f%%",
+		    100.0 * cache_hit / (cache_hit + cache_miss));
+	REPORT_MSG("\n\n");
 }
 
 static void
-- 
1.8.4.5


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec

[PATCH 0/4] Clean up makedumpfile cache handling

[Petr Tesarik]

The cache code is somewhat clumsy. This patch series tries to clean up
the code and clarify the concept, especially the meaning of the pending
list (allocated cache entries whose content is not yet valid).

The last patch adds some basic statistics to the final report.

Petr Tesarik (4):
  cache: get rid of search loop in cache_add()
  cache: allow to return a page to the pool
  cache: do not allocate from the pending list
  cache: add hit/miss statistics to the final report

 cache.c        | 46 +++++++++++++++++++---------------------------
 cache.h        | 11 +++++++++--
 makedumpfile.c | 29 ++++++++++++++++++++++-------
 3 files changed, 50 insertions(+), 36 deletions(-)

-- 
1.8.4.5


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec