Draft: Issue #3482279: Cache tags / hash collision

• Repurposes "cloudflarepurger.cache_tag_header_limit" to be the limit in bytes of the "Cache-Tag" response header contents
• Hashes cache tags via md5() only when they're longer than 32 characters
• Creates method regroupCacheTagsByLimit() to split cache tags into separate groups respecting the configured size limit in bytes
• Adds multiple "Cache-Tag" response headers when over the size limit
• Moves denylisted tags logic to its own method
• Add unit tests for cacheTagsToHashes() and regroupCacheTagsByLimit()

Closes #3482279

modules/cloudflarepurger/src/EventSubscriber/CloudFlareCacheTagHeaderGenerator.php

@@ -68,31 +68,17 @@ class CloudFlareCacheTagHeaderGenerator implements EventSubscriberInterface {
 
     $response = $event->getResponse();
 
-    $cloudflare_cachetag_header_value = static::drupalCacheTagsToCloudFlareCacheTag($cache_tags);
-
-    // Hash each cache tag to make the header fit, at the cost of potentially
-    // invalidating too much (cfr. hash collisions).
-    $cache_tags = explode(',', $cloudflare_cachetag_header_value);
-
-    // Remove any cache tags that are blacklisted.
-    $config = $this->configFactory->get('cloudflarepurger.settings');
-    $blacklist = $config->get('edge_cache_tag_header_blacklist');
-    $blacklist = is_array($blacklist) ? $blacklist : [];
-    if (!empty($blacklist)) {
-      $cache_tags = array_filter($cache_tags, function ($tag) use ($blacklist) {
-        foreach ($blacklist as $prefix) {
-          if (str_starts_with($tag, $prefix)) {
-            return FALSE;
-          }
-        }
-        return TRUE;
-      });
-    }
+    // Remove denylisted tags, if any.
+    $cache_tags = $this->removeDenylistedTags($cache_tags);
 
+    // Hash each cache tag if needed and group cache tags observing the
+    // Cache-Tag response header size limit.
     $hashes = static::cacheTagsToHashes($cache_tags);
-    $cloudflare_cachetag_header_value = implode(',', $hashes);
+    $cache_tags_groups = static::regroupCacheTagsByLimit($hashes, $this->limit, ',');
 
-    $response->headers->set('Cache-Tag', $cloudflare_cachetag_header_value);
+    foreach ($cache_tags_groups as $group) {
+      $response->headers->set('Cache-Tag', static::drupalCacheTagsToCloudFlareCacheTag($group), FALSE);
+    }
   }
 
   /**
@@ -109,9 +95,70 @@ class CloudFlareCacheTagHeaderGenerator implements EventSubscriberInterface {
   }
 
   /**
-   * Maps cache tags to hashes.
+   * Removes cache tags from the list based on the deny list configuration.
    *
-   * Used when the Cache-Tag header exceeds CloudFlare's limit.
+   * @param array $drupal_cache_tags
+   *   List of cache tags.
+   */
+  protected function removeDenylistedTags($drupal_cache_tags) {
+    $config = $this->configFactory->get('cloudflarepurger.settings');
+    $denylist = $config->get('edge_cache_tag_header_denylist') ?? [];
+    if (empty($denylist)) {
+      return $drupal_cache_tags;
+    }
+
+    return array_filter($drupal_cache_tags, function ($tag) use ($denylist) {
+      foreach ($denylist as $prefix) {
+        if (str_starts_with($tag, $prefix)) {
+          return FALSE;
+        }
+      }
+      return TRUE;
+    });
+  }
+
+  /**
+   * Splits cache tags into separate groups based on a size limit.
+   *
+   * @param array $cache_tags
+   *   List of Cloudflare cache tags.
+   * @param int $limit
+   *   Size limit in bytes to be enforced for every group. Defaults to 16KB.
+   * @param string $separator
+   *   Character to be used as separator.
+   */
+  protected static function regroupCacheTagsByLimit($cache_tags, $limit = 16 * 1024, string $separator = ',') {
+    $groups = [];
+    $current_group = [];
+    $current_group_size = 0;
+
+    foreach ($cache_tags as $tag) {
+      // strlen() is used here to ensure we're getting the length in bytes
+      // rather than characters.
+      $tag_size = strlen($tag . $separator);
+
+      // Check if adding the tag exceeds the limit.
+      if ($current_group_size + $tag_size > $limit) {
+        if ($current_group) {
+          $groups[] = $current_group;
+        }
+        $current_group = [];
+        $current_group_size = 0;
+      }
+
+      $current_group[] = $tag;
+      $current_group_size += $tag_size;
+    }
+
+    if ($current_group) {
+      $groups[] = $current_group;
+    }
+
+    return $groups;
+  }
+
+  /**
+   * Maps Drupal cache tags to Cloudflare cache tags.
    *
    * @param string[] $cache_tags
    *   The cache tags in the header.
@@ -122,7 +169,10 @@ class CloudFlareCacheTagHeaderGenerator implements EventSubscriberInterface {
   public static function cacheTagsToHashes(array $cache_tags) {
     $hashes = [];
     foreach ($cache_tags as $cache_tag) {
-      $hashes[] = substr(base_convert(md5($cache_tag), 16, 36), 0, 4);
+      // Only create an md5() hash if the current length exceeds 32 characters.
+      // That allows using the minimal representation for a tag without
+      // potential for collisions.
+      $hashes[] = (mb_strlen($cache_tag) > 32) ? md5($cache_tag) : $cache_tag;
     }
     return $hashes;
   }