1
     ;ˆÎÐ„_iŸÍ¾Ò .§    ;/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
   lru_cache.c

   This file is part of DRBD by Philipp Reisner and Lars Ellenberg.

   Copyright (C) 2003-2008, LINBIT Information Technologies GmbH.
   Copyright (C) 2003-2008, Philipp Reisner <philipp.reisner@linbit.com>.
   Copyright (C) 2003-2008, Lars Ellenberg <lars.ellenberg@linbit.com>.


 */

#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <linux/list.h>
#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/string.h> /* for memset */
#include <linux/seq_file.h>

/*
This header file (and its .c file; kernel-doc of functions see there)
  define a helper framework to easily keep track of index:label associations,
  and changes to an "active set" of objects, as well as pending transactions,
  to persistently record those changes.

  We use an LRU policy if it is necessary to "cool down" a region currently in
  the active set before we can "heat" a previously unused region.

  Because of this later property, it is called "lru_cache".
  As it actually Tracks Objects in an Active SeT, we could also call it
  toast (incidentally that is what may happen to the data on the
  backend storage upon next resync, if we don't get it right).

What for?

We replicate IO (more or less synchronously) to local and remote disk.

For crash recovery after replication node failure,
  we need to resync all regions that have been target of in-flight WRITE IO
  (in use, or "hot", regions), as we don't know whether or not those WRITEs
  have made it to stable storage.

  To avoid a "full resync", we need to persistently track these regions.

  This is known as "write intent log", and can be implemented as on-disk
  (coarse or fine grained) bitmap, or other meta data.

  To avoid the overhead of frequent extra writes to this meta data area,
  usually the condition is softened to regions that _may_ have been target of
  in-flight WRITE IO, e.g. by only lazily clearing the on-disk write-intent
  bitmap, trading frequency of meta data transactions against amount of
  (possibly unnecessary) resync traffic.

  If we set a hard limit on the area that may be "hot" at any given time, we
  limit the amount of resync traffic needed for crash recovery.

For recovery after replication link failure,
  we need to resync all blocks that have been changed on the other replica
  in the mean time, or, if both replica have been changed independently [*],
  all blocks that have been changed on either replica in the mean time.
  [*] usually as a result of a cluster split-brain and insufficient protection.
      but there are valid use cases to do this on purpose.

  Tracking those blocks can be implemented as "dirty bitmap".
  Having it fine-grained reduces the amount of resync traffic.
  It should also be persistent, to allow for reboots (or crashes)
  while the replication link is down.

There are various possible implementations for persistently storing
write intent log information, three of which are mentioned here.

"Chunk dirtying"
  The on-disk "dirty bitmap" may be re-used as "write-intent" bitmap as well.
  To reduce the frequency of bitmap updates for write-intent log purposes,
  one could dirty "chunks" (of some size) at a time of the (fine grained)
  on-disk bitmap, while keeping the in-memory "dirty" bitmap as clean as
  possible, flushing it to disk again when a previously "hot" (and on-disk
  dirtied as full chunk) area "cools down" again (no IO in flight anymore,
  and none expected in the near future either).

"Explicit (coarse) write intent bitmap"
  An other implementation could chose a (probably coarse) explicit bitmap,
  for write-intent log purposes, additionally to the fine grained dirty bitmap.

"Activity log"
  Yet an other implementation may keep track of the hot regions, by starting
  with an empty set, and writing down a journal of region numbers that have
  become "hot", or have "cooled down" again.

  To be able to use a ring buffer for this journal of changes to the active
  set, we not only record the actual changes to that set, but