src/carp.cc

   1
   2 /*
   3  * $Id: carp.cc,v 1.14 2000/12/05 10:10:57 wessels Exp $
   4  *
   5  * DEBUG: section 39    Cache Array Routing Protocol
   6  * AUTHOR: Eric Stern
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  the Regents of the University of California.  Please see the
  16  *  COPYRIGHT file for full details.  Squid incorporates software
  17  *  developed and/or copyrighted by other sources.  Please see the
  18  *  CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37
  38 #if USE_CARP
  39
  40 static OBJH carpCachemgr;
  41
  42 void
  43 carpInit(void)
  44 {
  45     /* calculate load factors */
  46     int K = 0;
  47     double a = 0.0;
  48     double dJ;
  49     double Xn;
  50     double P_last;
  51     double X_last;
  52     int k;
  53     peer *p;
  54     for (p = Config.peers; p; p = p->next) {
  55         a += p->carp.load_factor;
  56         K++;
  57     }
  58     if (a == 0.0) {
  59         for (p = Config.peers; p; p = p->next)
  60             p->carp.load_multiplier = 1.0;
  61         return;
  62     }
  63     /*
  64      * sum of carp-load-factor's for all cache_peer's in squid.conf
  65      * must equal 1.0.  If this doesn't work, see
  66      * http://www.eskimo.com/~scs/C-faq/q14.4.html
  67      */
  68     assert(1000 == (int) (1000.0 * a));
  69     k = 1;
  70     P_last = 0;
  71     p = Config.peers;
  72     p->carp.load_multiplier = pow(p->carp.load_factor * K, 1.0 / K);
  73     Xn = p->carp.load_multiplier;
  74     P_last = p->carp.load_factor;
  75     X_last = p->carp.load_multiplier;
  76     if (!p->next)
  77         return;
  78     for (p = p->next; p; p = p->next) {
  79         k++;
  80         dJ = (double) (K - k + 1);
  81         p->carp.load_multiplier = (dJ * (p->carp.load_factor - P_last)) / Xn;
  82         p->carp.load_multiplier += pow(X_last, dJ);
  83         p->carp.load_multiplier = pow(p->carp.load_multiplier, 1 / dJ);
  84         Xn *= p->carp.load_multiplier;
  85         X_last = p->carp.load_multiplier;
  86         P_last = p->carp.load_factor;
  87     }
  88     cachemgrRegister("carp", "CARP information", carpCachemgr, 0, 1);
  89 }
  90
  91 peer *
  92 carpSelectParent(request_t * request)
  93 {
  94 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (((sizeof(unsigned long)*8)-(n)))))
  95     const char *c;
  96     peer *p = NULL;
  97     peer *tp;
  98     unsigned long url_hash = 0;
  99     unsigned long combined_hash;
 100     unsigned long high_score = 0;
 101     const char *url = urlCanonical(request);
 102     /* calculate url hash */
 103     debug(39, 2) ("carpSelectParent: CARP Calculating hash for %s\n", url);
 104     for (c = url; *c != 0; c++)
 105         url_hash += ROTATE_LEFT(url_hash, 19) + *c;
 106     /* select peer */
 107     for (tp = Config.peers; tp; tp = tp->next) {
 108         if (0.0 == tp->carp.load_factor)
 109             continue;
 110         if (tp->tcp_up != PEER_TCP_MAGIC_COUNT)
 111             continue;
 112         assert(tp->type == PEER_PARENT);
 113         combined_hash = (url_hash ^ tp->carp.hash);
 114         combined_hash += combined_hash * 0x62531965;
 115         combined_hash = ROTATE_LEFT(combined_hash, 21);
 116         combined_hash = combined_hash * tp->carp.load_multiplier;
 117         debug(39, 3) ("carpSelectParent: %s combined_hash %d\n",
 118             tp->host, combined_hash);
 119         if ((combined_hash > high_score) && neighborUp(tp)) {
 120             p = tp;
 121             high_score = combined_hash;
 122         }
 123     }
 124     if (p)
 125         debug(39, 3) ("carpSelectParent: selected CARP %s\n", p->host);
 126     return p;
 127 }
 128
 129 static void
 130 carpCachemgr(StoreEntry * sentry)
 131 {
 132     peer *p;
 133     int sumfetches = 0;
 134     storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 135         "Hostname",
 136         "Hash",
 137         "Multiplier",
 138         "Factor",
 139         "Actual");
 140     for (p = Config.peers; p; p = p->next)
 141         sumfetches += p->stats.fetches;
 142     for (p = Config.peers; p; p = p->next) {
 143         storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 144             p->host, p->carp.hash,
 145             p->carp.load_multiplier,
 146             p->carp.load_factor,
 147             sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 148     }
 149
 150 }
 151
 152 #endif