net/

http_cache.rs

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

#![deny(missing_docs)]

//! A memory cache implementing the logic specified in <http://tools.ietf.org/html/rfc7234>
//! and <http://tools.ietf.org/html/rfc7232>.

use std::ops::Bound;
use std::sync::Arc as StdArc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::time::{Duration, SystemTime};

use headers::{
    CacheControl, ContentRange, ContentType, Expires, HeaderMapExt, LastModified, Pragma, Range,
    Vary,
};
use http::{HeaderMap, Method, StatusCode, header};
use hyper_serde::Serde;
use log::{debug, error, info};
use malloc_size_of::{MallocSizeOf, MallocSizeOfOps};
use malloc_size_of_derive::MallocSizeOf;
use net_traits::http_status::HttpStatus;
use net_traits::request::{CacheMode, Request};
use net_traits::response::{Response, ResponseBody};
use net_traits::{CacheEntryDescriptor, Metadata, ResourceFetchTiming};
use parking_lot::Mutex as ParkingLotMutex;
use quick_cache::sync::{Cache, PlaceholderGuard};
use quick_cache::{DefaultHashBuilder, Lifecycle, UnitWeighter};
use serde::{Deserialize, Serialize};
use servo_arc::Arc;
use servo_config::pref;
use servo_url::ServoUrl;
use tokio::sync::mpsc::{UnboundedSender as TokioSender, unbounded_channel as unbounded};
use tokio::sync::{OwnedRwLockWriteGuard, RwLock as TokioRwLock};

use crate::disk_cache::DiskCache;
use crate::fetch::methods::{Data, DoneChannel};

/// A duration in seconds.
///
/// This is the same as std::time::Duration except that we do not care about nanosecond precision.
#[derive(
    Copy,
    Clone,
    Default,
    Debug,
    Deserialize,
    MallocSizeOf,
    Serialize,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
)]
struct ApproxDuration(u64);

impl ApproxDuration {
    const fn zero() -> Self {
        Self(0)
    }

    fn is_zero(&self) -> bool {
        self.0 == 0
    }

    fn saturating_sub(&self, rhs: ApproxDuration) -> Self {
        Self(self.0.saturating_sub(rhs.0))
    }

    fn from_secs(seconds: u64) -> Self {
        Self(seconds)
    }
}

impl From<Duration> for ApproxDuration {
    fn from(value: Duration) -> Self {
        Self(value.as_secs())
    }
}

impl std::ops::Add for ApproxDuration {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Self(self.0 + rhs.0)
    }
}

impl std::ops::Sub for ApproxDuration {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        Self(self.0 - rhs.0)
    }
}

impl std::ops::Div<u64> for ApproxDuration {
    type Output = Self;

    fn div(self, rhs: u64) -> Self::Output {
        Self(self.0 / rhs)
    }
}

/// The key used to differentiate requests in the cache.
#[derive(Clone, Debug, Eq, Hash, MallocSizeOf, PartialEq)]
pub struct CacheKey {
    url: ServoUrl,
}

impl AsRef<str> for CacheKey {
    fn as_ref(&self) -> &str {
        self.url.as_str()
    }
}

impl CacheKey {
    /// Create a cache-key from a request.
    pub fn new(request: &Request) -> CacheKey {
        CacheKey {
            url: request.current_url(),
        }
    }

    /// Create a cache-key from a resolved URL.
    pub fn from_url(url: ServoUrl) -> CacheKey {
        CacheKey { url }
    }
}

/// A complete cached resource.
#[derive(Clone, Debug, Deserialize, MallocSizeOf, Serialize)]
pub struct CachedResource {
    #[conditional_malloc_size_of]
    request_headers: Arc<ParkingLotMutex<SerializeableHeaderMap>>,
    #[conditional_malloc_size_of]
    body: Arc<ParkingLotMutex<ResponseBody>>,
    #[conditional_malloc_size_of]
    aborted: Arc<AtomicBool>,
    #[conditional_malloc_size_of]
    #[serde(skip)]
    awaiting_body: Arc<ParkingLotMutex<Vec<TokioSender<Data>>>>,
    metadata: CachedMetadata,
    location_url: Option<Result<ServoUrl, String>>,
    status: HttpStatus,
    url_list: Vec<ServoUrl>,
    expires: ApproxDuration,
    stale_while_revalidate: ApproxDuration,
    #[conditional_malloc_size_of]
    #[serde(skip)]
    revalidating: StdArc<AtomicBool>,
    last_validated: SystemTime,
}

impl CachedResource {
    pub(crate) fn is_done(&self) -> bool {
        self.body.lock().is_done()
    }

    /// Whether this [`CachedResource`] can be used to answer the given `Request`. This
    /// is true if:
    ///
    /// 1. The resource is not for an aborted load.
    /// 2. The fields named in the `Vary` header match those of the `Request`.
    /// 3. It is not a partial (206) response or the request has a `Range` header. When the request
    ///    has a `Range` header the caller is expected to decide which part of the resource to use.
    fn can_be_used_to_answer(&self, request: &Request) -> bool {
        if self.aborted.load(Ordering::Acquire) {
            return false;
        }
        if !self.vary_header_matches(&request.headers) {
            return false;
        }
        if request.headers.typed_get::<Range>().is_some() {
            return true;
        }

        // From <https://httpwg.org/specs/rfc9111.html#incomplete.responses>
        // > A cache MAY complete a stored incomplete response by making a subsequent range
        // > request (Section 14.2 of [HTTP]) and combining the successful response with the
        // > stored response, as defined in Section 3.4. A cache MUST NOT use an incomplete
        // > response to answer requests unless the response has been made complete, or the
        // > request is partial and specifies a range wholly within the incomplete response.
        // > A cache MUST NOT send a partial response to a client without explicitly marking
        // > it using the 206 (Partial Content) status code.
        //
        // TODO: Combining partial content to fulfill a non-Range request
        // See <https://httpwg.org/specs/rfc9111.html#combining.responses>.
        self.status
            .try_code()
            .is_some_and(|code| code != StatusCode::PARTIAL_CONTENT)
    }

    /// Whether the given request headers match the cached resource's request headers
    /// on every field named in the `Vary` header according to the rules specified in
    /// <https://httpwg.org/specs/rfc9111.html#caching.negotiated.responses>.
    ///
    /// > When a cache receives a request that can be satisfied by a stored response and
    /// > that stored response contains a Vary header field (Section 12.5.5 of [HTTP]), the
    /// > cache MUST NOT use that stored response without revalidation unless all the
    /// > presented request header fields nominated by that Vary field value match those
    /// > fields in the original request (i.e., the request that caused the cached response
    /// > to be stored).
    fn vary_header_matches(&self, request_headers: &HeaderMap) -> bool {
        let cached_headers = self.metadata.headers.lock();
        let original_request_headers = self.request_headers.lock();
        let Some(vary_value) = cached_headers.typed_get::<Vary>() else {
            return true;
        };

        if vary_value.is_any() {
            return false;
        }

        for vary_header_field in vary_value.iter_strs() {
            if request_headers.get(vary_header_field) !=
                original_request_headers.get(vary_header_field)
            {
                return false;
            }
        }

        true
    }
}

#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
/// Wrapper type for HeaderMap
struct SerializeableHeaderMap(
    #[serde(
        deserialize_with = "hyper_serde::deserialize",
        serialize_with = "hyper_serde::serialize"
    )]
    HeaderMap,
);

impl std::ops::Deref for SerializeableHeaderMap {
    type Target = HeaderMap;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl std::ops::DerefMut for SerializeableHeaderMap {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl From<HeaderMap> for SerializeableHeaderMap {
    fn from(value: HeaderMap) -> Self {
        SerializeableHeaderMap(value)
    }
}

/// Metadata about a loaded resource, such as is obtained from HTTP headers.
#[derive(Clone, Debug, Deserialize, Serialize, MallocSizeOf)]
struct CachedMetadata {
    /// Headers
    #[conditional_malloc_size_of]
    pub headers: Arc<ParkingLotMutex<SerializeableHeaderMap>>,
    /// Final URL after redirects.
    pub final_url: ServoUrl,
    /// MIME type / subtype.
    pub content_type: Option<Serde<ContentType>>,
    /// Character set.
    pub charset: Option<String>,
    /// HTTP Status
    pub status: HttpStatus,
}

/// Whether a cached response is fresh or requires validation before or after use.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum ValidationStatus {
    /// The response is fresh and can be used without any revalidation.
    Valid,
    /// The response is stale.
    Stale {
        /// Whether the stale response can be served immediately, leaving the
        /// caller responsible for revalidating it in the background.
        revalidate_in_background: bool,
    },
}

/// Wrapper around a cached response, including information on re-validation needs
pub(crate) struct CachedResponse {
    /// The response constructed from the cached resource
    pub response: Response,
    /// Whether the stored response is fresh or stale
    pub validation_status: ValidationStatus,
    /// Single-flight guard for the background revalidation.
    pub revalidation_guard: StdArc<AtomicBool>,
}

pub(crate) type CacheEntry = std::sync::Arc<TokioRwLock<Vec<CachedResource>>>;
type QuickCache =
    Cache<CacheKey, CacheEntry, UnitWeighter, DefaultHashBuilder, MemoryCacheLifecycle>;
type QuickCachePlaceholderGuard<'a> = PlaceholderGuard<
    'a,
    CacheKey,
    CacheEntry,
    UnitWeighter,
    DefaultHashBuilder,
    MemoryCacheLifecycle,
>;

/// Is this state assigned to the private or public side.
#[derive(Debug, MallocSizeOf, PartialEq)]
pub enum HttpCacheAssignment {
    /// Public Cache State, possibly stored to disk.
    Public,
    /// Private Cache State, not stored to disk.
    Private,
}

/// A simple memory cache.
/// Elements will be evicted based on the cache heuristic. We weight elements
/// by the number of entries per given url. We evict currently a whole url.
/// The cache makes extensive use of `Arc::unwrap_or_clone or` and `Arc::into_inner`
/// to modify the cached entries. This is ok because `CachedResource` are cheap to clone
pub struct HttpCache {
    /// cached responses.
    entries: QuickCache,
    disk_cache: Option<std::sync::Arc<DiskCache>>,
}

impl std::fmt::Debug for HttpCache {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_list().entries(self.entries.iter()).finish()
    }
}

impl MallocSizeOf for HttpCache {
    fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
        self.entries
            .iter()
            .map(|(_key, entry)| entry.blocking_read().size_of(ops))
            .sum::<usize>() +
            self.disk_cache
                .as_ref()
                .map(|data| data.size_of(ops))
                .unwrap_or(0)
    }
}

impl HttpCache {
    /// Create a new HttpCache with [`HttpCacheAssignment`]
    pub fn new(assignment: HttpCacheAssignment) -> Self {
        let size = pref!(network_http_cache_size)
            .try_into()
            .expect("http_cache_size needs to fit into u64");
        let (disk_cache, lifecycle) = DiskCache::new(assignment);
        let memory_cache = Cache::with(
            size,
            size as u64,
            UnitWeighter,
            DefaultHashBuilder::default(),
            lifecycle,
        );

        Self {
            entries: memory_cache,
            disk_cache,
        }
    }

    #[expect(clippy::len_without_is_empty)]
    /// The number of entries in the memory cache. This does not say anything about the disk cache.
    pub fn len(&self) -> usize {
        self.entries.len()
    }
}

#[derive(Clone)]
/// The lifecycle hooks of the HttpCache.
/// Responsible for moving data to the disk.
pub struct MemoryCacheLifecycle {
    pub(crate) disk_cache: Option<StdArc<DiskCache>>,
}

impl MemoryCacheLifecycle {
    pub(crate) fn empty() -> MemoryCacheLifecycle {
        MemoryCacheLifecycle { disk_cache: None }
    }
}

impl Lifecycle<CacheKey, CacheEntry> for MemoryCacheLifecycle {
    type RequestState = ();

    // Cached Resources that are not complete could get evicted which means they cannot fill their body.
    // We allow unfinished resources to stay in the cache.
    fn is_pinned(&self, key: &CacheKey, val: &CacheEntry) -> bool {
        let pinned = val
            .try_read()
            .map(|cached_resources| cached_resources.iter().any(|resource| !resource.is_done()))
            .unwrap_or(true);
        info!("Key {key:?} is pinned",);
        pinned
    }

    fn on_evict(&self, _state: &mut Self::RequestState, key: CacheKey, value: CacheEntry) {
        info!("Evicting {key:?} from memory cache");
        if let Some(disk_cache_data) = &self.disk_cache {
            let disk_cache_data = disk_cache_data.clone();
            tokio::spawn(async move { disk_cache_data.store(key, value).await });
        }
    }
}

/// Determine if a response is cacheable by default <https://tools.ietf.org/html/rfc7231#section-6.1>
fn is_cacheable_by_default(status_code: StatusCode) -> bool {
    matches!(
        status_code.as_u16(),
        200 | 203 | 204 | 206 | 300 | 301 | 404 | 405 | 410 | 414 | 501
    )
}

/// Determine if a given response is cacheable.
/// Based on <https://tools.ietf.org/html/rfc7234#section-3>
fn response_is_cacheable(metadata: &Metadata) -> bool {
    // This kind of response does not have a body. It just freshens existing cached resources.
    if metadata.status == StatusCode::NOT_MODIFIED {
        return false;
    }

    // Resources with `Vary: '*'` can never be returned as cache results, so
    // do not store them in the cache.
    let headers = metadata.headers.as_ref().unwrap();
    if headers
        .typed_get::<Vary>()
        .is_some_and(|vary| vary.is_any())
    {
        return false;
    }

    // TODO: if we determine that this cache should be considered shared:
    // 1. check for absence of private response directive <https://tools.ietf.org/html/rfc7234#section-5.2.2.6>
    // 2. check for absence of the Authorization header field.
    let mut is_cacheable = false;
    if headers.contains_key(header::EXPIRES) ||
        headers.contains_key(header::LAST_MODIFIED) ||
        headers.contains_key(header::ETAG)
    {
        is_cacheable = true;
    }
    if let Some(ref directive) = headers.typed_get::<CacheControl>() {
        if directive.no_store() {
            return false;
        }
        if directive.public() ||
            directive.s_max_age().is_some() ||
            directive.max_age().is_some() ||
            directive.no_cache()
        {
            // If cache-control is understood, we can use it and ignore pragma.
            return true;
        }
    }
    if let Some(pragma) = headers.typed_get::<Pragma>() &&
        pragma.is_no_cache()
    {
        return false;
    }

    is_cacheable
}

/// Calculating Age
/// <https://tools.ietf.org/html/rfc7234#section-4.2.3>
fn calculate_response_age(response: &Response) -> ApproxDuration {
    // TODO: follow the spec more closely (Date headers, request/response lag, ...)
    response
        .headers
        .get(header::AGE)
        .and_then(|age_header| age_header.to_str().ok())
        .and_then(|age_string| age_string.parse::<u64>().ok())
        .map(ApproxDuration::from_secs)
        .unwrap_or_default()
}

/// Determine the expiry date from relevant headers,
/// or uses a heuristic if none are present.
fn get_response_expiry(response: &Response) -> ApproxDuration {
    // Calculating Freshness Lifetime <https://tools.ietf.org/html/rfc7234#section-4.2.1>
    let age = calculate_response_age(response);
    let now = SystemTime::now();
    if let Some(directives) = response.headers.typed_get::<CacheControl>() {
        if directives.no_cache() {
            // Requires validation on first use.
            return ApproxDuration::zero();
        }
        if let Some(max_age) = directives.max_age().or(directives.s_max_age()) {
            let max_age: ApproxDuration = max_age.into();
            return max_age.saturating_sub(age);
        }
    }
    match response.headers.typed_get::<Expires>() {
        Some(expiry) => {
            // `duration_since` fails if `now` is later than `expiry_time` in which case,
            // this whole thing return `Duration::ZERO`.
            let expiry_time: SystemTime = expiry.into();
            return expiry_time
                .duration_since(now)
                .map(|duration| duration.into())
                .unwrap_or(ApproxDuration::zero());
        },
        // Malformed Expires header, shouldn't be used to construct a valid response.
        None if response.headers.contains_key(header::EXPIRES) => return ApproxDuration::zero(),
        _ => {},
    }
    // Calculating Heuristic Freshness
    // <https://tools.ietf.org/html/rfc7234#section-4.2.2>
    if let Some(ref code) = response.status.try_code() {
        // <https://tools.ietf.org/html/rfc7234#section-5.5.4>
        // Since presently we do not generate a Warning header field with a 113 warn-code,
        // 24 hours minus response age is the max for heuristic calculation.
        let max_heuristic = ApproxDuration::from_secs(24 * 60 * 60).saturating_sub(age);
        let heuristic_freshness = if let Some(last_modified) =
            // If the response has a Last-Modified header field,
            // caches are encouraged to use a heuristic expiration value
            // that is no more than some fraction of the interval since that time.
            response.headers.typed_get::<LastModified>()
        {
            // `time_since_last_modified` will be `Duration::ZERO` if `last_modified` is
            // after `now`.
            let last_modified: SystemTime = last_modified.into();
            let time_since_last_modified: ApproxDuration =
                now.duration_since(last_modified).unwrap_or_default().into();

            // A typical setting of this fraction might be 10%.
            let raw_heuristic_calc = time_since_last_modified / 10;
            if raw_heuristic_calc < max_heuristic {
                raw_heuristic_calc
            } else {
                max_heuristic
            }
        } else {
            // Compatible with other browsers.
            ApproxDuration::zero()
        };
        if is_cacheable_by_default(*code) {
            // Status codes that are cacheable by default can use heuristics to determine freshness.
            return heuristic_freshness;
        }
        // Other status codes can only use heuristic freshness if the public cache directive is present.
        if let Some(ref directives) = response.headers.typed_get::<CacheControl>() &&
            directives.public()
        {
            return heuristic_freshness;
        }
    }
    // Requires validation upon first use as default.
    ApproxDuration::zero()
}

/// The `headers` crate's `CacheControl` does not understand `stale-while-revalidate` directive,
/// so we need to parse the raw `Cache-Control` header values.
/// <https://datatracker.ietf.org/doc/html/rfc5861#section-3>
fn get_stale_while_revalidate(headers: &HeaderMap) -> ApproxDuration {
    for value in headers.get_all(header::CACHE_CONTROL) {
        let Ok(value) = value.to_str() else {
            continue;
        };
        for directive in value.split(',') {
            let directive = directive.trim();
            let Some((name, argument)) = directive.split_once('=') else {
                continue;
            };
            if !name.trim().eq_ignore_ascii_case("stale-while-revalidate") {
                continue;
            }
            // The argument is a number of seconds, optionally quoted.
            let argument = argument.trim().trim_matches('"');
            if let Ok(seconds) = argument.parse::<u64>() {
                return ApproxDuration::from_secs(seconds);
            }
        }
    }
    ApproxDuration::zero()
}

/// Determine whether the request itself demands revalidation.
/// <https://www.rfc-editor.org/rfc/rfc9111.html#section-5.2.1>
fn request_demands_revalidation(request: &Request) -> bool {
    if matches!(
        request.cache_mode,
        CacheMode::NoCache | CacheMode::Reload | CacheMode::NoStore
    ) {
        return true;
    }
    if let Some(directive) = request.headers.typed_get::<CacheControl>() {
        // The request's `no-store` directive is deliberately *not* treated as
        // demanding revalidation: https://www.rfc-editor.org/rfc/rfc9111.html#section-5.2.1.5
        // > "does not apply to the already stored response".
        if directive.no_cache() {
            return true;
        }

        if directive.max_age() == Some(Duration::ZERO) {
            return true;
        }
    }
    false
}

/// Request Cache-Control Directives
/// <https://tools.ietf.org/html/rfc7234#section-5.2.1>
fn get_expiry_adjustment_from_request_headers(
    request: &Request,
    expires: ApproxDuration,
) -> ApproxDuration {
    let Some(directive) = request.headers.typed_get::<CacheControl>() else {
        return expires;
    };

    if let Some(max_age) = directive.max_stale() {
        let max_age: ApproxDuration = max_age.into();
        return expires + max_age;
    };

    let max_age: Option<ApproxDuration> = directive.max_age().map(|max_age| max_age.into());
    match max_age {
        Some(max_age) if expires > max_age => return ApproxDuration::zero(),
        Some(max_age) => return expires - max_age,
        None => {},
    };

    if let Some(min_fresh) = directive.min_fresh() {
        let min_fresh: ApproxDuration = min_fresh.into();
        if expires < min_fresh {
            return ApproxDuration::zero();
        };
        return expires - min_fresh;
    }

    if directive.no_cache() || directive.no_store() {
        return ApproxDuration::zero();
    }

    expires
}

/// Create a CachedResponse from a request and a CachedResource.
fn create_cached_response(
    request: &Request,
    cached_resource: &CachedResource,
    cached_headers: &HeaderMap,
    done_chan: &mut DoneChannel,
) -> Option<CachedResponse> {
    debug!("creating a cached response for {:?}", request.url());
    if cached_resource.aborted.load(Ordering::Acquire) {
        return None;
    }
    let resource_timing = ResourceFetchTiming::new(request.timing_type());
    let mut response = Response::new(cached_resource.metadata.final_url.clone(), resource_timing);
    response.headers = cached_headers.clone();
    response.body = cached_resource.body.clone();
    if let ResponseBody::Receiving(_) = *cached_resource.body.lock() {
        debug!("existing body is in progress");
        let (done_sender, done_receiver) = unbounded();
        *done_chan = Some((done_sender.clone(), done_receiver));
        cached_resource.awaiting_body.lock().push(done_sender);
    }
    response
        .location_url
        .clone_from(&cached_resource.location_url);
    response.status.clone_from(&cached_resource.status);
    response.url_list.clone_from(&cached_resource.url_list);
    response.referrer = request.referrer.to_url().cloned();
    response.referrer_policy = request.referrer_policy;
    response.aborted = cached_resource.aborted.clone();

    let expires = cached_resource.expires;
    let adjusted_expires = get_expiry_adjustment_from_request_headers(request, expires);
    let Ok(time_since_validated) = SystemTime::now().duration_since(cached_resource.last_validated)
    else {
        return None;
    };

    let time_since_validated: ApproxDuration = time_since_validated.into();
    // TODO: take must-revalidate into account <https://tools.ietf.org/html/rfc7234#section-5.2.2.1>
    // TODO: if this cache is to be considered shared, take proxy-revalidate into account
    // <https://tools.ietf.org/html/rfc7234#section-5.2.2.7>
    let has_expired = adjusted_expires <= time_since_validated;

    // - fresh: return immediately, no validation.
    // - stale:
    //    - within the stale-while-revalidate window: return immediately + revalidate in the background
    //    - beyond the stale-while-revalidate window: synchronous validation is required.
    let stale_for = time_since_validated.saturating_sub(adjusted_expires);
    let within_stale_while_revalidate_window = stale_for <= cached_resource.stale_while_revalidate;
    let validation_status = if !has_expired {
        ValidationStatus::Valid
    } else {
        ValidationStatus::Stale {
            revalidate_in_background: within_stale_while_revalidate_window &&
                !cached_resource.stale_while_revalidate.is_zero() &&
                !request_demands_revalidation(request),
        }
    };

    let cached_response = CachedResponse {
        response,
        validation_status,
        revalidation_guard: cached_resource.revalidating.clone(),
    };
    Some(cached_response)
}

/// Create a new resource, based on the bytes requested, and an existing resource,
/// with a status-code of 206.
fn create_resource_with_bytes_from_resource(
    bytes: &[u8],
    resource: &CachedResource,
) -> CachedResource {
    CachedResource {
        request_headers: resource.request_headers.clone(),
        body: Arc::new(ParkingLotMutex::new(ResponseBody::Done(bytes.to_owned()))),
        aborted: Arc::new(AtomicBool::new(false)),
        awaiting_body: Arc::new(ParkingLotMutex::new(vec![])),
        metadata: resource.metadata.clone(),
        location_url: resource.location_url.clone(),
        status: StatusCode::PARTIAL_CONTENT.into(),
        url_list: resource.url_list.clone(),
        expires: resource.expires,
        stale_while_revalidate: resource.stale_while_revalidate,
        revalidating: resource.revalidating.clone(),
        last_validated: resource.last_validated,
    }
}

/// Support for range requests <https://tools.ietf.org/html/rfc7233>.
fn handle_range_request(
    request: &Request,
    candidates: &[&CachedResource],
    range_spec: &Range,
    done_chan: &mut DoneChannel,
) -> Option<CachedResponse> {
    let mut complete_cached_resources = candidates
        .iter()
        .filter(|resource| resource.status == StatusCode::OK);
    let partial_cached_resources = candidates
        .iter()
        .filter(|resource| resource.status == StatusCode::PARTIAL_CONTENT);
    if let Some(complete_resource) = complete_cached_resources.next() {
        // TODO: take the full range spec into account.
        // If we have a complete resource, take the request range from the body.
        // When there isn't a complete resource available, we loop over cached partials,
        // and see if any individual partial response can fulfill the current request for a bytes range.
        // TODO: combine partials that in combination could satisfy the requested range?
        // see <https://tools.ietf.org/html/rfc7233#section-4.3>.
        // TODO: add support for complete and partial resources,
        // whose body is in the ResponseBody::Receiving state.
        let body_len = match *complete_resource.body.lock() {
            ResponseBody::Done(ref body) => body.len(),
            _ => 0,
        };
        let bound = range_spec
            .satisfiable_ranges(body_len.try_into().unwrap())
            .next()
            .unwrap();
        match bound {
            (Bound::Included(beginning), Bound::Included(end)) => {
                if let ResponseBody::Done(ref body) = *complete_resource.body.lock() {
                    if end == u64::MAX {
                        // Prevent overflow on the addition below.
                        return None;
                    }
                    let b = beginning as usize;
                    let e = end as usize + 1;
                    let requested = body.get(b..e);
                    if let Some(bytes) = requested {
                        let new_resource =
                            create_resource_with_bytes_from_resource(bytes, complete_resource);
                        let cached_headers = new_resource.metadata.headers.lock();
                        let cached_response = create_cached_response(
                            request,
                            &new_resource,
                            &cached_headers,
                            done_chan,
                        );
                        if let Some(cached_response) = cached_response {
                            return Some(cached_response);
                        }
                    }
                }
            },
            (Bound::Included(beginning), Bound::Unbounded) => {
                if let ResponseBody::Done(ref body) = *complete_resource.body.lock() {
                    let b = beginning as usize;
                    let requested = body.get(b..);
                    if let Some(bytes) = requested {
                        let new_resource =
                            create_resource_with_bytes_from_resource(bytes, complete_resource);
                        let cached_headers = new_resource.metadata.headers.lock();
                        let cached_response = create_cached_response(
                            request,
                            &new_resource,
                            &cached_headers,
                            done_chan,
                        );
                        if let Some(cached_response) = cached_response {
                            return Some(cached_response);
                        }
                    }
                }
            },
            _ => return None,
        }
    } else {
        for partial_resource in partial_cached_resources {
            let headers = partial_resource.metadata.headers.lock();
            let content_range = headers.typed_get::<ContentRange>();

            let Some(body_len) = content_range.as_ref().and_then(|range| range.bytes_len()) else {
                continue;
            };
            match range_spec.satisfiable_ranges(body_len - 1).next().unwrap() {
                (Bound::Included(beginning), Bound::Included(end)) => {
                    let (res_beginning, res_end) = match content_range {
                        Some(range) => {
                            if let Some(bytes_range) = range.bytes_range() {
                                bytes_range
                            } else {
                                continue;
                            }
                        },
                        _ => continue,
                    };
                    if res_beginning <= beginning && res_end >= end {
                        let resource_body = &*partial_resource.body.lock();
                        let requested = match resource_body {
                            ResponseBody::Done(body) => {
                                let b = beginning as usize - res_beginning as usize;
                                let e = end as usize - res_beginning as usize + 1;
                                body.get(b..e)
                            },
                            _ => continue,
                        };
                        if let Some(bytes) = requested {
                            let new_resource =
                                create_resource_with_bytes_from_resource(bytes, partial_resource);
                            let cached_response =
                                create_cached_response(request, &new_resource, &headers, done_chan);
                            if let Some(cached_response) = cached_response {
                                return Some(cached_response);
                            }
                        }
                    }
                },

                (Bound::Included(beginning), Bound::Unbounded) => {
                    let (res_beginning, res_end, total) = if let Some(range) = content_range {
                        match (range.bytes_range(), range.bytes_len()) {
                            (Some(bytes_range), Some(total)) => {
                                (bytes_range.0, bytes_range.1, total)
                            },
                            _ => continue,
                        }
                    } else {
                        continue;
                    };
                    if total == 0 {
                        // Prevent overflow in the below operations from occuring.
                        continue;
                    };
                    if res_beginning <= beginning && res_end == total - 1 {
                        let resource_body = &*partial_resource.body.lock();
                        let requested = match resource_body {
                            ResponseBody::Done(body) => {
                                let from_byte = beginning as usize - res_beginning as usize;
                                body.get(from_byte..)
                            },
                            _ => continue,
                        };
                        if let Some(bytes) = requested {
                            if bytes.len() as u64 + beginning < total - 1 {
                                // Requested range goes beyond the available range.
                                continue;
                            }
                            let new_resource =
                                create_resource_with_bytes_from_resource(bytes, partial_resource);
                            let cached_response =
                                create_cached_response(request, &new_resource, &headers, done_chan);
                            if let Some(cached_response) = cached_response {
                                return Some(cached_response);
                            }
                        }
                    }
                },

                _ => continue,
            }
        }
    }

    None
}

/// Constructing Responses from Caches.
/// <https://tools.ietf.org/html/rfc7234#section-4>
pub(crate) fn construct_response(
    request: &Request,
    done_chan: &mut DoneChannel,
    cache_result: &[CachedResource],
) -> Option<CachedResponse> {
    if pref!(network_http_cache_disabled) {
        return None;
    }

    // TODO: generate warning headers as appropriate <https://tools.ietf.org/html/rfc7234#section-5.5>
    debug!("trying to construct cache response for {:?}", request.url());
    if request.method != Method::GET {
        // Only Get requests are cached, avoid a url based match for others.
        debug!("non-GET method, not caching");
        return None;
    }

    let mut candidates: Vec<_> = cache_result
        .iter()
        .filter(|resource| resource.can_be_used_to_answer(request))
        .collect();

    // Support for range requests
    if let Some(range_spec) = request.headers.typed_get::<Range>() {
        return handle_range_request(request, candidates.as_slice(), &range_spec, done_chan);
    }

    while let Some(cached_resource) = candidates.pop() {
        // Returning a response that can be constructed
        // TODO: select the most appropriate one, using a known mechanism from a selecting header field,
        // or using the Date header to return the most recent one.
        let cached_headers = cached_resource.metadata.headers.lock();
        let cached_response =
            create_cached_response(request, cached_resource, &cached_headers, done_chan);
        if let Some(cached_response) = cached_response {
            return Some(cached_response);
        }
    }
    debug!("couldn't find an appropriate response, not caching");
    // The cache wasn't able to construct anything.
    None
}

/// Freshening Stored Responses upon Validation.
/// <https://httpwg.org/specs/rfc9111.html#freshening.responses>
pub fn refresh(
    request: &Request,
    response: Response,
    done_chan: &mut DoneChannel,
    cached_resources: &mut [CachedResource],
) -> Option<Response> {
    assert_eq!(response.status, StatusCode::NOT_MODIFIED);

    // Refresh the last cached resource that can be used to answer the request.
    // TODO: This should follow the rules specified in
    // <https://httpwg.org/specs/rfc9111.html#freshening.responses> more closely.
    let cached_resource_index = cached_resources
        .iter()
        .rposition(|resource| resource.can_be_used_to_answer(request))?;

    let mut constructed_response = if let Some(range_spec) = request.headers.typed_get::<Range>() {
        let cached_resources: Vec<_> = cached_resources
            .iter()
            .filter(|resource| resource.can_be_used_to_answer(request))
            .collect();
        handle_range_request(request, &cached_resources, &range_spec, done_chan)
            .map(|cached_response| cached_response.response)
    } else {
        // done_chan will have been set to Some(..) by http_network_fetch.
        // If the body is not receiving data, set the done_chan back to None.
        // Otherwise, create a new dedicated channel to update the consumer.
        // The response constructed here will replace the 304 one from the network.
        let cached_resource = &mut cached_resources[cached_resource_index];
        let in_progress_channel = match &*cached_resource.body.lock() {
            ResponseBody::Receiving(..) => Some(unbounded()),
            ResponseBody::Empty | ResponseBody::Done(..) => None,
        };
        match in_progress_channel {
            Some((done_sender, done_receiver)) => {
                *done_chan = Some((done_sender.clone(), done_receiver));
                cached_resource.awaiting_body.lock().push(done_sender);
            },
            None => *done_chan = None,
        }
        // Received a response with 304 status code, in response to a request that matches a cached resource.
        // 1. update the headers of the cached resource.
        // 2. return a response, constructed from the cached resource.
        let resource_timing = ResourceFetchTiming::new(request.timing_type());
        let mut constructed_response =
            Response::new(cached_resource.metadata.final_url.clone(), resource_timing);

        constructed_response.body = cached_resource.body.clone();

        constructed_response
            .status
            .clone_from(&cached_resource.status);
        constructed_response.referrer = request.referrer.to_url().cloned();
        constructed_response.referrer_policy = request.referrer_policy;
        constructed_response
            .status
            .clone_from(&cached_resource.status);
        constructed_response
            .url_list
            .clone_from(&cached_resource.url_list);
        Some(constructed_response)
    };

    // Update cached Resource with response and constructed response.
    if let Some(constructed_response) = constructed_response.as_mut() {
        let cached_resource = &mut cached_resources[cached_resource_index];

        // Bracket is to minimize lock duration.
        {
            let mut stored_headers = cached_resource.metadata.headers.lock();
            stored_headers.extend(response.headers);
            constructed_response.headers = stored_headers.clone();
        }
        cached_resource.expires = get_response_expiry(constructed_response);
        cached_resource.stale_while_revalidate =
            get_stale_while_revalidate(&constructed_response.headers);
        cached_resource.last_validated = SystemTime::now();
    }

    constructed_response
}

pub(crate) fn invalidate_cached_resources(cached_resources: &mut [CachedResource]) {
    for cached_resource in cached_resources.iter_mut() {
        cached_resource.expires = ApproxDuration::zero();
    }
}

fn resolve_location_url(
    request: &Request,
    response: &Response,
    header_name: header::HeaderName,
) -> Option<ServoUrl> {
    response
        .headers
        .get(header_name)
        .and_then(|value| value.to_str().ok())
        .and_then(|location| request.current_url().join(location).ok())
}

impl HttpCache {
    /// Wake-up consumers of cached resources
    /// whose response body was still receiving data when the resource was constructed,
    /// and whose response has now either been completed or cancelled.
    pub(crate) async fn update_awaiting_consumers(&self, request: &Request, response: &Response) {
        let entry_key = CacheKey::new(request);

        let cached_resources = match self.entries.get(&entry_key) {
            None => return,
            Some(resources) => resources,
        };

        let actual_response = response.actual_response();

        // Ensure we only wake-up consumers of relevant resources,
        // ie we don't want to wake-up 200 awaiting consumers with a 206.
        let lock = cached_resources.read().await;
        let relevant_cached_resources = lock.iter().filter(|resource| {
            if actual_response.is_network_error() {
                return *resource.body.lock() == ResponseBody::Empty;
            }
            resource.status == actual_response.status
        });

        for cached_resource in relevant_cached_resources {
            let mut awaiting_consumers = cached_resource.awaiting_body.lock();
            if awaiting_consumers.is_empty() {
                continue;
            }
            let to_send = if cached_resource.aborted.load(Ordering::Acquire) {
                // In the case of an aborted fetch,
                // wake-up all awaiting consumers.
                // Each will then start a new network request.
                // TODO: Wake-up only one consumer, and make it the producer on which others wait.
                Data::Cancelled
            } else {
                match *cached_resource.body.lock() {
                    ResponseBody::Done(_) | ResponseBody::Empty => Data::Done,
                    ResponseBody::Receiving(_) => {
                        continue;
                    },
                }
            };
            for done_sender in awaiting_consumers.drain(..) {
                let _ = done_sender.send(to_send.clone());
            }
        }
    }

    /// Returns descriptors for cache entries currently stored in this cache.
    pub(crate) fn cache_entry_descriptors(&self) -> Vec<CacheEntryDescriptor> {
        self.entries
            .iter()
            .map(|(key, _)| CacheEntryDescriptor::new(key.url.to_string()))
            .collect()
    }

    /// Clear the contents of this cache.
    pub(crate) fn clear(&self) {
        self.entries.clear();
        if let Some(disk_cache) = &self.disk_cache {
            disk_cache.clear();
        }
    }

    /// Insert a response for `request` into the cache (used by tests that need direct access).
    pub async fn store(&self, request: &Request, response: &Response) {
        let guard = self.get_or_guard(CacheKey::new(request)).await;
        guard.insert(request, response);
    }

    /// Try to construct a cached response for `request`.
    pub async fn construct_response(
        &self,
        request: &Request,
        done_chan: &mut DoneChannel,
    ) -> Option<Response> {
        let entry = self.entries.get(&CacheKey::new(request))?;
        let cached_resources = entry.read().await;
        construct_response(request, done_chan, cached_resources.as_slice())
            .map(|cached| cached.response)
    }

    /// Like [`construct_response`](Self::construct_response), but additionally
    /// reports the [`ValidationStatus`] of the constructed response.
    #[cfg(feature = "test-util")]
    pub async fn construct_response_freshness(
        &self,
        request: &Request,
        done_chan: &mut DoneChannel,
    ) -> Option<ValidationStatus> {
        let entry = self.entries.get(&CacheKey::new(request))?;
        let cached_resources = entry.read().await;
        construct_response(request, done_chan, cached_resources.as_slice())
            .map(|cached| cached.validation_status)
    }

    /// Invalidate cache entries referenced by Location/Content-Location headers.
    pub(crate) async fn invalidate_related_urls(
        &self,
        request: &Request,
        response: &Response,
        skip_key: &CacheKey,
    ) {
        for header_name in &[header::LOCATION, header::CONTENT_LOCATION] {
            if let Some(location_url) = resolve_location_url(request, response, header_name.clone())
            {
                let location_key = CacheKey::from_url(location_url);
                if &location_key != skip_key {
                    self.invalidate_entry(&location_key).await;
                }
            }
        }
    }

    async fn invalidate_entry(&self, key: &CacheKey) {
        if let Some(entry) = self.entries.get(key) {
            let mut guarded_resources = entry.write().await;
            invalidate_cached_resources(guarded_resources.as_mut_slice());
        }
    }

    /// If the value exist in the cache, return it. If the value does not exist, return a guard you can use to insert values in the cache.
    /// If the guard is alive, all other accesses to this function will block.
    #[servo_tracing::instrument(skip(self))]
    pub async fn get_or_guard(&self, entry_key: CacheKey) -> CachedResourcesOrGuard<'_> {
        let guard_or_value = self.entries.get_value_or_guard_async(&entry_key).await;
        if let Ok(value) = guard_or_value {
            return CachedResourcesOrGuard::Value(value.write_owned().await);
        }
        let guard = guard_or_value.unwrap_err();

        if let Some(disk_cache) = &self.disk_cache {
            if let Some(response) = disk_cache.get(entry_key).await {
                if guard.insert(response.clone()).is_err() {
                    error!(
                        "Cache guard is invalid. This should not happen. Cache will be in inconsistent state."
                    );
                }
                let response = response.write_owned().await;
                CachedResourcesOrGuard::Value(response)
            } else {
                CachedResourcesOrGuard::Guard(guard)
            }
        } else {
            CachedResourcesOrGuard::Guard(guard)
        }
    }
}

/// Returns an writeable entry into the cache or a guard for insertint an entry
/// The guard will block other queries to the cache entry in both cases.
pub enum CachedResourcesOrGuard<'a> {
    /// The value of the resource in the cache.
    Value(OwnedRwLockWriteGuard<Vec<CachedResource>>),
    /// A guard that blocks requests to the cache entry this guard is for.
    Guard(QuickCachePlaceholderGuard<'a>),
}

impl<'a> CachedResourcesOrGuard<'a> {
    /// Insert into the cache according to http spec
    pub fn insert(self, request: &Request, response: &Response) {
        if pref!(network_http_cache_disabled) {
            return;
        }

        if request.method != Method::GET {
            // Only Get requests are cached.
            return;
        }
        if request.headers.contains_key(header::AUTHORIZATION) {
            // https://tools.ietf.org/html/rfc7234#section-3.1
            // A shared cache MUST NOT use a cached response
            // to a request with an Authorization header field
            //
            // TODO: unless a cache directive that allows such
            // responses to be stored is present in the response.
            return;
        };
        let Ok(metadata): Result<Metadata, _> = response.metadata().map(Into::into) else {
            return;
        };
        if !response_is_cacheable(&metadata) {
            return;
        }
        let expiry = get_response_expiry(response);
        let stale_while_revalidate = get_stale_while_revalidate(&response.headers);
        let cacheable_metadata = CachedMetadata {
            headers: Arc::new(ParkingLotMutex::new(response.headers.clone().into())),
            final_url: metadata.final_url,
            content_type: metadata.content_type,
            charset: metadata.charset,
            status: metadata.status,
        };
        let entry_resource = CachedResource {
            request_headers: Arc::new(ParkingLotMutex::new(request.headers.clone().into())),
            body: response.body.clone(),
            aborted: response.aborted.clone(),
            awaiting_body: Arc::new(ParkingLotMutex::new(vec![])),
            metadata: cacheable_metadata,
            location_url: response.location_url.clone(),
            status: response.status.clone(),
            url_list: response.url_list.clone(),
            expires: expiry,
            stale_while_revalidate,
            revalidating: StdArc::new(AtomicBool::new(false)),
            last_validated: SystemTime::now(),
        };

        match self {
            CachedResourcesOrGuard::Value(mut cached_resources) => {
                // Ensure that any existing complete response is replaced by the new
                // complete response if the two responses match according to the fields
                // named in the `Vary` header.
                if response.status == StatusCode::OK {
                    cached_resources.retain(|cached_resource| {
                        cached_resource.status != StatusCode::OK ||
                            !cached_resource.is_done() ||
                            !cached_resource.vary_header_matches(&request.headers)
                    });
                }

                cached_resources.push(entry_resource);
            },
            CachedResourcesOrGuard::Guard(placeholder_guard) => {
                if placeholder_guard
                    .insert(std::sync::Arc::new(TokioRwLock::new(vec![entry_resource])))
                    .is_err()
                {
                    error!("Could not insert into cache");
                }
            },
        }
    }

    /// If the guard is a value, return it as a mut reference. If the guard is a guard, return None
    pub fn try_as_mut(&mut self) -> Option<&mut Vec<CachedResource>> {
        match self {
            CachedResourcesOrGuard::Value(owned_rw_lock_write_guard) => {
                Some(owned_rw_lock_write_guard.as_mut())
            },
            CachedResourcesOrGuard::Guard(_) => None,
        }
    }
}