Skip to contentSkip to conversation

bcache: add "clock" cache replacement policy

PATCH In review Robert Pang 1 participant 3 messages Oct 9, 2025 – Nov 18, 2025

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 bcache: add "clock" cache replacement policy

This new policy extends the FIFO policy to approximate the classic clock policy (O(n) time complexity) by considering bucket priority, similar to the LRU policy.

This clock policy addresses the high IO latency (1-2 seconds) experienced on multi-terabyte cache devices when the free list is empty due to the default LRU policy. The LRU policy's O(n log n) complexity for sorting priorities for the entire bucket list causes this delay.

Here are the average execution times (in microseconds) of the LRU and the clock replacement policies:

SSD Size Bucket Count LRU (us) Clock (us)

375 GB      1536000       58292        1163
750 GB      3072000      121769        1729
1.5 TB      6144000      244012        3862
3 TB       12288000      496569        6428
6 TB       24576000     1067628       14298
9 TB       36864000     1564348       25763
---
 Documentation/admin-guide/bcache.rst |  2 +-
 drivers/md/bcache/alloc.c            | 34 ++++++++++++++++++++++++----
 drivers/md/bcache/bcache_ondisk.h    |  1 +
 drivers/md/bcache/sysfs.c            |  1 +
 4 files changed, 33 insertions(+), 5 deletions(-)
Documentation/admin-guide/bcache.rst +1 -1
index 6fdb495ac466..2be2999c7de4 100644
@@ -616,7 +616,7 @@ bucket_size
   Size of buckets
 
 cache_replacement_policy
-  One of either lru, fifo or random.
+  One of either lru, fifo, random or clock.
 
 discard
   Boolean; if on a discard/TRIM will be issued to each bucket before it is
drivers/md/bcache/alloc.c +30 -4
index 48ce750bf70a..c65c48eab169 100644
@@ -69,7 +69,8 @@
 #include <linux/random.h>
 #include <trace/events/bcache.h>
 
-#define MAX_OPEN_BUCKETS 128
+#define MAX_OPEN_BUCKETS	128
+#define CHECK_PRIO_SLICES	16
 
 /* Bucket heap / gen */
 
@@ -211,19 +212,41 @@ static void invalidate_buckets_lru(struct cache *ca)
 	}
 }
 
-static void invalidate_buckets_fifo(struct cache *ca)
+/*
+ * When check_prio is true, this FIFO policy examines the priority of the
+ * buckets and invalidates only the ones below a threshold in the priority
+ * ladder. As it goes, the threshold will be raised if not enough buckets are
+ * invalidated. Empty buckets are also invalidated. This evaulation resembles
+ * the LRU policy, and is used to approximate the classic clock-sweep cache
+ * replacement algorithm.
+ */
+static void invalidate_buckets_fifo(struct cache *ca, bool check_prio)
 {
 	struct bucket *b;
 	size_t checked = 0;
+	size_t check_quota = 0;
+	uint16_t prio_threshold = ca->set->min_prio;
 
 	while (!fifo_full(&ca->free_inc)) {
 		if (ca->fifo_last_bucket <  ca->sb.first_bucket ||
 		    ca->fifo_last_bucket >= ca->sb.nbuckets)
 			ca->fifo_last_bucket = ca->sb.first_bucket;
 
+		if (check_prio && checked >= check_quota) {
+			BUG_ON(ca->set->min_prio > INITIAL_PRIO);
+			prio_threshold +=
+				DIV_ROUND_UP(INITIAL_PRIO - ca->set->min_prio,
+					     CHECK_PRIO_SLICES);
+			check_quota += DIV_ROUND_UP(ca->sb.nbuckets,
+						    CHECK_PRIO_SLICES);
+		}
+
 		b = ca->buckets + ca->fifo_last_bucket++;
 
-		if (bch_can_invalidate_bucket(ca, b))
+		if (bch_can_invalidate_bucket(ca, b) &&
+		    (!check_prio ||
+		     b->prio <= prio_threshold ||
+		     !GC_SECTORS_USED(b)))
 			bch_invalidate_one_bucket(ca, b);
 
 		if (++checked >= ca->sb.nbuckets) {
@@ -269,11 +292,14 @@ static void invalidate_buckets(struct cache *ca)
 		invalidate_buckets_lru(ca);
 		break;
 	case CACHE_REPLACEMENT_FIFO:
-		invalidate_buckets_fifo(ca);
+		invalidate_buckets_fifo(ca, false);
 		break;
 	case CACHE_REPLACEMENT_RANDOM:
 		invalidate_buckets_random(ca);
 		break;
+	case CACHE_REPLACEMENT_CLOCK:
+		invalidate_buckets_fifo(ca, true);
+		break;
 	}
 }
 
drivers/md/bcache/bcache_ondisk.h +1 -0
index 6620a7f8fffc..d45794e01fe1 100644
@@ -288,6 +288,7 @@ BITMASK(CACHE_REPLACEMENT,		struct cache_sb, flags, 2, 3);
 #define CACHE_REPLACEMENT_LRU		0U
 #define CACHE_REPLACEMENT_FIFO		1U
 #define CACHE_REPLACEMENT_RANDOM	2U
+#define CACHE_REPLACEMENT_CLOCK		3U
 
 BITMASK(BDEV_CACHE_MODE,		struct cache_sb, flags, 0, 4);
 #define CACHE_MODE_WRITETHROUGH		0U
drivers/md/bcache/sysfs.c +1 -0
index 826b14cae4e5..c8617bad0648 100644
@@ -45,6 +45,7 @@ static const char * const cache_replacement_policies[] = {
 	"lru",
 	"fifo",
 	"random",
+	"clock",
 	NULL
 };
 
Signature · 1 line
2.51.0.710.ga91ca5db03-goog
#1 lore raw

Apology for missing the change log earlier:
v2: Add "clock" cache replacement policy to admin-guide/bcache.rst and performance results.
v1: initial version.

Quoted 143 lines · Robert Pang

This new policy extends the FIFO policy to approximate the classic clock policy (O(n) time complexity) by considering bucket priority, similar to the LRU policy.

This clock policy addresses the high IO latency (1-2 seconds) experienced on multi-terabyte cache devices when the free list is empty due to the default LRU policy. The LRU policy's O(n log n) complexity for sorting priorities for the entire bucket list causes this delay.

Here are the average execution times (in microseconds) of the LRU and the clock replacement policies:

SSD Size Bucket Count LRU (us) Clock (us)

375 GB      1536000       58292        1163
750 GB      3072000      121769        1729
1.5 TB      6144000      244012        3862
3 TB       12288000      496569        6428
6 TB       24576000     1067628       14298
9 TB       36864000     1564348       25763
---
 Documentation/admin-guide/bcache.rst |  2 +-
 drivers/md/bcache/alloc.c            | 34 ++++++++++++++++++++++++----
 drivers/md/bcache/bcache_ondisk.h    |  1 +
 drivers/md/bcache/sysfs.c            |  1 +
 4 files changed, 33 insertions(+), 5 deletions(-)
Documentation/admin-guide/bcache.rst +1 -1
index 6fdb495ac466..2be2999c7de4 100644
@@ -616,7 +616,7 @@ bucket_size
   Size of buckets
 
 cache_replacement_policy
-  One of either lru, fifo or random.
+  One of either lru, fifo, random or clock.
 
 discard
   Boolean; if on a discard/TRIM will be issued to each bucket before it is
drivers/md/bcache/alloc.c +30 -4
index 48ce750bf70a..c65c48eab169 100644
@@ -69,7 +69,8 @@
 #include <linux/random.h>
 #include <trace/events/bcache.h>
 
-#define MAX_OPEN_BUCKETS 128
+#define MAX_OPEN_BUCKETS       128
+#define CHECK_PRIO_SLICES      16
 
 /* Bucket heap / gen */
 
@@ -211,19 +212,41 @@ static void invalidate_buckets_lru(struct cache *ca)
        }
 }
 
-static void invalidate_buckets_fifo(struct cache *ca)
+/*
+ * When check_prio is true, this FIFO policy examines the priority of the
+ * buckets and invalidates only the ones below a threshold in the priority
+ * ladder. As it goes, the threshold will be raised if not enough buckets are
+ * invalidated. Empty buckets are also invalidated. This evaulation resembles
+ * the LRU policy, and is used to approximate the classic clock-sweep cache
+ * replacement algorithm.
+ */
+static void invalidate_buckets_fifo(struct cache *ca, bool check_prio)
 {
        struct bucket *b;
        size_t checked = 0;
+       size_t check_quota = 0;
+       uint16_t prio_threshold = ca->set->min_prio;
 
        while (!fifo_full(&ca->free_inc)) {
                if (ca->fifo_last_bucket <  ca->sb.first_bucket ||
                    ca->fifo_last_bucket >= ca->sb.nbuckets)
                        ca->fifo_last_bucket = ca->sb.first_bucket;
 
+               if (check_prio && checked >= check_quota) {
+                       BUG_ON(ca->set->min_prio > INITIAL_PRIO);
+                       prio_threshold +=
+                               DIV_ROUND_UP(INITIAL_PRIO - ca->set->min_prio,
+                                            CHECK_PRIO_SLICES);
+                       check_quota += DIV_ROUND_UP(ca->sb.nbuckets,
+                                                   CHECK_PRIO_SLICES);
+               }
+
                b = ca->buckets + ca->fifo_last_bucket++;
 
-               if (bch_can_invalidate_bucket(ca, b))
+               if (bch_can_invalidate_bucket(ca, b) &&
+                   (!check_prio ||
+                    b->prio <= prio_threshold ||
+                    !GC_SECTORS_USED(b)))
                        bch_invalidate_one_bucket(ca, b);
 
                if (++checked >= ca->sb.nbuckets) {
@@ -269,11 +292,14 @@ static void invalidate_buckets(struct cache *ca)
                invalidate_buckets_lru(ca);
                break;
        case CACHE_REPLACEMENT_FIFO:
-               invalidate_buckets_fifo(ca);
+               invalidate_buckets_fifo(ca, false);
                break;
        case CACHE_REPLACEMENT_RANDOM:
                invalidate_buckets_random(ca);
                break;
+       case CACHE_REPLACEMENT_CLOCK:
+               invalidate_buckets_fifo(ca, true);
+               break;
        }
 }
 
drivers/md/bcache/bcache_ondisk.h +1 -0
index 6620a7f8fffc..d45794e01fe1 100644
@@ -288,6 +288,7 @@ BITMASK(CACHE_REPLACEMENT,          struct cache_sb, flags, 2, 3);
 #define CACHE_REPLACEMENT_LRU          0U
 #define CACHE_REPLACEMENT_FIFO         1U
 #define CACHE_REPLACEMENT_RANDOM       2U
+#define CACHE_REPLACEMENT_CLOCK                3U
 
 BITMASK(BDEV_CACHE_MODE,               struct cache_sb, flags, 0, 4);
 #define CACHE_MODE_WRITETHROUGH                0U
drivers/md/bcache/sysfs.c +1 -1
index 826b14cae4e5..c8617bad0648 100644
@@ -45,6 +45,7 @@ static const char * const cache_replacement_policies[] = {
        "lru",
        "fifo",
        "random",
+       "clock",
        NULL
 };
 
--

2.51.0.710.ga91ca5db03-goog

#2 lore raw

Hi Coly and Kent,

I'm writing to follow up on the patch proposal regarding this new cache replacement policy.

Do you have any feedback on the proposed policy or the implementation?

Best regards
Robert

Quoted 150 lines · Robert Pang

Apology for missing the change log earlier:
v2: Add "clock" cache replacement policy to admin-guide/bcache.rst and performance results.
v1: initial version.

Quoted 143 lines · Robert Pang

This new policy extends the FIFO policy to approximate the classic clock policy (O(n) time complexity) by considering bucket priority, similar to the LRU policy.

This clock policy addresses the high IO latency (1-2 seconds) experienced on multi-terabyte cache devices when the free list is empty due to the default LRU policy. The LRU policy's O(n log n) complexity for sorting priorities for the entire bucket list causes this delay.

Here are the average execution times (in microseconds) of the LRU and the clock replacement policies:

SSD Size Bucket Count LRU (us) Clock (us)

375 GB      1536000       58292        1163
750 GB      3072000      121769        1729
1.5 TB      6144000      244012        3862
3 TB       12288000      496569        6428
6 TB       24576000     1067628       14298
9 TB       36864000     1564348       25763
---
 Documentation/admin-guide/bcache.rst |  2 +-
 drivers/md/bcache/alloc.c            | 34 ++++++++++++++++++++++++----
 drivers/md/bcache/bcache_ondisk.h    |  1 +
 drivers/md/bcache/sysfs.c            |  1 +
 4 files changed, 33 insertions(+), 5 deletions(-)
Documentation/admin-guide/bcache.rst +1 -1
index 6fdb495ac466..2be2999c7de4 100644
@@ -616,7 +616,7 @@ bucket_size
   Size of buckets
 
 cache_replacement_policy
-  One of either lru, fifo or random.
+  One of either lru, fifo, random or clock.
 
 discard
   Boolean; if on a discard/TRIM will be issued to each bucket before it is
drivers/md/bcache/alloc.c +30 -4
index 48ce750bf70a..c65c48eab169 100644
@@ -69,7 +69,8 @@
 #include <linux/random.h>
 #include <trace/events/bcache.h>
 
-#define MAX_OPEN_BUCKETS 128
+#define MAX_OPEN_BUCKETS       128
+#define CHECK_PRIO_SLICES      16
 
 /* Bucket heap / gen */
 
@@ -211,19 +212,41 @@ static void invalidate_buckets_lru(struct cache *ca)
        }
 }
 
-static void invalidate_buckets_fifo(struct cache *ca)
+/*
+ * When check_prio is true, this FIFO policy examines the priority of the
+ * buckets and invalidates only the ones below a threshold in the priority
+ * ladder. As it goes, the threshold will be raised if not enough buckets are
+ * invalidated. Empty buckets are also invalidated. This evaulation resembles
+ * the LRU policy, and is used to approximate the classic clock-sweep cache
+ * replacement algorithm.
+ */
+static void invalidate_buckets_fifo(struct cache *ca, bool check_prio)
 {
        struct bucket *b;
        size_t checked = 0;
+       size_t check_quota = 0;
+       uint16_t prio_threshold = ca->set->min_prio;
 
        while (!fifo_full(&ca->free_inc)) {
                if (ca->fifo_last_bucket <  ca->sb.first_bucket ||
                    ca->fifo_last_bucket >= ca->sb.nbuckets)
                        ca->fifo_last_bucket = ca->sb.first_bucket;
 
+               if (check_prio && checked >= check_quota) {
+                       BUG_ON(ca->set->min_prio > INITIAL_PRIO);
+                       prio_threshold +=
+                               DIV_ROUND_UP(INITIAL_PRIO - ca->set->min_prio,
+                                            CHECK_PRIO_SLICES);
+                       check_quota += DIV_ROUND_UP(ca->sb.nbuckets,
+                                                   CHECK_PRIO_SLICES);
+               }
+
                b = ca->buckets + ca->fifo_last_bucket++;
 
-               if (bch_can_invalidate_bucket(ca, b))
+               if (bch_can_invalidate_bucket(ca, b) &&
+                   (!check_prio ||
+                    b->prio <= prio_threshold ||
+                    !GC_SECTORS_USED(b)))
                        bch_invalidate_one_bucket(ca, b);
 
                if (++checked >= ca->sb.nbuckets) {
@@ -269,11 +292,14 @@ static void invalidate_buckets(struct cache *ca)
                invalidate_buckets_lru(ca);
                break;
        case CACHE_REPLACEMENT_FIFO:
-               invalidate_buckets_fifo(ca);
+               invalidate_buckets_fifo(ca, false);
                break;
        case CACHE_REPLACEMENT_RANDOM:
                invalidate_buckets_random(ca);
                break;
+       case CACHE_REPLACEMENT_CLOCK:
+               invalidate_buckets_fifo(ca, true);
+               break;
        }
 }
 
drivers/md/bcache/bcache_ondisk.h +1 -0
index 6620a7f8fffc..d45794e01fe1 100644
@@ -288,6 +288,7 @@ BITMASK(CACHE_REPLACEMENT,          struct cache_sb, flags, 2, 3);
 #define CACHE_REPLACEMENT_LRU          0U
 #define CACHE_REPLACEMENT_FIFO         1U
 #define CACHE_REPLACEMENT_RANDOM       2U
+#define CACHE_REPLACEMENT_CLOCK                3U
 
 BITMASK(BDEV_CACHE_MODE,               struct cache_sb, flags, 0, 4);
 #define CACHE_MODE_WRITETHROUGH                0U
drivers/md/bcache/sysfs.c +1 -1
index 826b14cae4e5..c8617bad0648 100644
@@ -45,6 +45,7 @@ static const char * const cache_replacement_policies[] = {
        "lru",
        "fifo",
        "random",
+       "clock",
        NULL
 };
 
--

2.51.0.710.ga91ca5db03-goog