sys/cddl/contrib/opensolaris/uts/common/fs/zfs/aggsum.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * This file and its contents are supplied under the terms of the
   5  * Common Development and Distribution License ("CDDL"), version 1.0.
   6  * You may only use this file in accordance with the terms of version
   7  * 1.0 of the CDDL.
   8  *
   9  * A full copy of the text of the CDDL should have accompanied this
  10  * source.  A copy of the CDDL is also available via the Internet at
  11  * http://www.illumos.org/license/CDDL.
  12  *
  13  * CDDL HEADER END
  14  */
  15 /*
  16  * Copyright (c) 2017, 2018 by Delphix. All rights reserved.
  17  */
  18
  19 #include <sys/zfs_context.h>
  20 #include <sys/aggsum.h>
  21
  22 /*
  23  * Aggregate-sum counters are a form of fanned-out counter, used when atomic
  24  * instructions on a single field cause enough CPU cache line contention to
  25  * slow system performance. Due to their increased overhead and the expense
  26  * involved with precisely reading from them, they should only be used in cases
  27  * where the write rate (increment/decrement) is much higher than the read rate
  28  * (get value).
  29  *
  30  * Aggregate sum counters are comprised of two basic parts, the core and the
  31  * buckets. The core counter contains a lock for the entire counter, as well
  32  * as the current upper and lower bounds on the value of the counter. The
  33  * aggsum_bucket structure contains a per-bucket lock to protect the contents of
  34  * the bucket, the current amount that this bucket has changed from the global
  35  * counter (called the delta), and the amount of increment and decrement we have
  36  * "borrowed" from the core counter.
  37  *
  38  * The basic operation of an aggsum is simple. Threads that wish to modify the
  39  * counter will modify one bucket's counter (determined by their current CPU, to
  40  * help minimize lock and cache contention). If the bucket already has
  41  * sufficient capacity borrowed from the core structure to handle their request,
  42  * they simply modify the delta and return.  If the bucket does not, we clear
  43  * the bucket's current state (to prevent the borrowed amounts from getting too
  44  * large), and borrow more from the core counter. Borrowing is done by adding to
  45  * the upper bound (or subtracting from the lower bound) of the core counter,
  46  * and setting the borrow value for the bucket to the amount added (or
  47  * subtracted).  Clearing the bucket is the opposite; we add the current delta
  48  * to both the lower and upper bounds of the core counter, subtract the borrowed
  49  * incremental from the upper bound, and add the borrowed decrement from the
  50  * lower bound.  Note that only borrowing and clearing require access to the
  51  * core counter; since all other operations access CPU-local resources,
  52  * performance can be much higher than a traditional counter.
  53  *
  54  * Threads that wish to read from the counter have a slightly more challenging
  55  * task. It is fast to determine the upper and lower bounds of the aggum; this
  56  * does not require grabbing any locks. This suffices for cases where an
  57  * approximation of the aggsum's value is acceptable. However, if one needs to
  58  * know whether some specific value is above or below the current value in the
  59  * aggsum, they invoke aggsum_compare(). This function operates by repeatedly
  60  * comparing the target value to the upper and lower bounds of the aggsum, and
  61  * then clearing a bucket. This proceeds until the target is outside of the
  62  * upper and lower bounds and we return a response, or the last bucket has been
  63  * cleared and we know that the target is equal to the aggsum's value. Finally,
  64  * the most expensive operation is determining the precise value of the aggsum.
  65  * To do this, we clear every bucket and then return the upper bound (which must
  66  * be equal to the lower bound). What makes aggsum_compare() and aggsum_value()
  67  * expensive is clearing buckets. This involves grabbing the global lock
  68  * (serializing against themselves and borrow operations), grabbing a bucket's
  69  * lock (preventing threads on those CPUs from modifying their delta), and
  70  * zeroing out the borrowed value (forcing that thread to borrow on its next
  71  * request, which will also be expensive).  This is what makes aggsums well
  72  * suited for write-many read-rarely operations.
  73  */
  74
  75 /*
  76  * We will borrow aggsum_borrow_multiplier times the current request, so we will
  77  * have to get the as_lock approximately every aggsum_borrow_multiplier calls to
  78  * aggsum_delta().
  79  */
  80 static uint_t aggsum_borrow_multiplier = 10;
  81
  82 void
  83 aggsum_init(aggsum_t *as, uint64_t value)
  84 {
  85         bzero(as, sizeof (*as));
  86         as->as_lower_bound = as->as_upper_bound = value;
  87         mutex_init(&as->as_lock, NULL, MUTEX_DEFAULT, NULL);
  88         as->as_numbuckets = boot_ncpus;
  89         as->as_buckets = kmem_zalloc(boot_ncpus * sizeof (aggsum_bucket_t),
  90             KM_SLEEP);
  91         for (int i = 0; i < as->as_numbuckets; i++) {
  92                 mutex_init(&as->as_buckets[i].asc_lock,
  93                     NULL, MUTEX_DEFAULT, NULL);
  94         }
  95 }
  96
  97 void
  98 aggsum_fini(aggsum_t *as)
  99 {
 100         for (int i = 0; i < as->as_numbuckets; i++)
 101                 mutex_destroy(&as->as_buckets[i].asc_lock);
 102         kmem_free(as->as_buckets, as->as_numbuckets * sizeof (aggsum_bucket_t));
 103         mutex_destroy(&as->as_lock);
 104 }
 105
 106 int64_t
 107 aggsum_lower_bound(aggsum_t *as)
 108 {
 109         return (as->as_lower_bound);
 110 }
 111
 112 int64_t
 113 aggsum_upper_bound(aggsum_t *as)
 114 {
 115         return (as->as_upper_bound);
 116 }
 117
 118 static void
 119 aggsum_flush_bucket(aggsum_t *as, struct aggsum_bucket *asb)
 120 {
 121         ASSERT(MUTEX_HELD(&as->as_lock));
 122         ASSERT(MUTEX_HELD(&asb->asc_lock));
 123
 124         /*
 125          * We use atomic instructions for this because we read the upper and
 126          * lower bounds without the lock, so we need stores to be atomic.
 127          */
 128         atomic_add_64((volatile uint64_t *)&as->as_lower_bound,
 129             asb->asc_delta + asb->asc_borrowed);
 130         atomic_add_64((volatile uint64_t *)&as->as_upper_bound,
 131             asb->asc_delta - asb->asc_borrowed);
 132         asb->asc_delta = 0;
 133         asb->asc_borrowed = 0;
 134 }
 135
 136 uint64_t
 137 aggsum_value(aggsum_t *as)
 138 {
 139         int64_t rv;
 140
 141         mutex_enter(&as->as_lock);
 142         if (as->as_lower_bound == as->as_upper_bound) {
 143                 rv = as->as_lower_bound;
 144                 for (int i = 0; i < as->as_numbuckets; i++) {
 145                         ASSERT0(as->as_buckets[i].asc_delta);
 146                         ASSERT0(as->as_buckets[i].asc_borrowed);
 147                 }
 148                 mutex_exit(&as->as_lock);
 149                 return (rv);
 150         }
 151         for (int i = 0; i < as->as_numbuckets; i++) {
 152                 struct aggsum_bucket *asb = &as->as_buckets[i];
 153                 mutex_enter(&asb->asc_lock);
 154                 aggsum_flush_bucket(as, asb);
 155                 mutex_exit(&asb->asc_lock);
 156         }
 157         VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound);
 158         rv = as->as_lower_bound;
 159         mutex_exit(&as->as_lock);
 160
 161         return (rv);
 162 }
 163
 164 void
 165 aggsum_add(aggsum_t *as, int64_t delta)
 166 {
 167         struct aggsum_bucket *asb =
 168             &as->as_buckets[CPU_SEQID % as->as_numbuckets];
 169         int64_t borrow;
 170
 171         /* Try fast path if we already borrowed enough before. */
 172         mutex_enter(&asb->asc_lock);
 173         if (asb->asc_delta + delta <= (int64_t)asb->asc_borrowed &&
 174             asb->asc_delta + delta >= -(int64_t)asb->asc_borrowed) {
 175                 asb->asc_delta += delta;
 176                 mutex_exit(&asb->asc_lock);
 177                 return;
 178         }
 179         mutex_exit(&asb->asc_lock);
 180
 181         /*
 182          * We haven't borrowed enough.  Take the global lock and borrow
 183          * considering what is requested now and what we borrowed before.
 184          */
 185         borrow = (delta < 0 ? -delta : delta) * aggsum_borrow_multiplier;
 186         mutex_enter(&as->as_lock);
 187         mutex_enter(&asb->asc_lock);
 188         delta += asb->asc_delta;
 189         asb->asc_delta = 0;
 190         if (borrow >= asb->asc_borrowed)
 191                 borrow -= asb->asc_borrowed;
 192         else
 193                 borrow = (borrow - (int64_t)asb->asc_borrowed) / 4;
 194         asb->asc_borrowed += borrow;
 195         atomic_add_64((volatile uint64_t *)&as->as_lower_bound,
 196             delta - borrow);
 197         atomic_add_64((volatile uint64_t *)&as->as_upper_bound,
 198             delta + borrow);
 199         mutex_exit(&asb->asc_lock);
 200         mutex_exit(&as->as_lock);
 201 }
 202
 203 /*
 204  * Compare the aggsum value to target efficiently. Returns -1 if the value
 205  * represented by the aggsum is less than target, 1 if it's greater, and 0 if
 206  * they are equal.
 207  */
 208 int
 209 aggsum_compare(aggsum_t *as, uint64_t target)
 210 {
 211         if (as->as_upper_bound < target)
 212                 return (-1);
 213         if (as->as_lower_bound > target)
 214                 return (1);
 215         mutex_enter(&as->as_lock);
 216         for (int i = 0; i < as->as_numbuckets; i++) {
 217                 struct aggsum_bucket *asb = &as->as_buckets[i];
 218                 mutex_enter(&asb->asc_lock);
 219                 aggsum_flush_bucket(as, asb);
 220                 mutex_exit(&asb->asc_lock);
 221                 if (as->as_upper_bound < target) {
 222                         mutex_exit(&as->as_lock);
 223                         return (-1);
 224                 }
 225                 if (as->as_lower_bound > target) {
 226                         mutex_exit(&as->as_lock);
 227                         return (1);
 228                 }
 229         }
 230         VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound);
 231         ASSERT3U(as->as_lower_bound, ==, target);
 232         mutex_exit(&as->as_lock);
 233         return (0);
 234 }