peer_sourcehash.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 /* DEBUG: section 39 Peer source hash based selection */
10 
11 #include "squid.h"
12 #include "CachePeer.h"
13 #include "HttpRequest.h"
14 #include "mgr/Registration.h"
15 #include "neighbors.h"
16 #include "peer_sourcehash.h"
17 #include "PeerSelectState.h"
18 #include "SquidConfig.h"
19 #include "Store.h"
20 
21 #include <cmath>
22 
23 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
24 
25 static int n_sourcehash_peers = 0;
29 
30 static int
31 peerSortWeight(const void *a, const void *b)
32 {
33  const CachePeer *const *p1 = (const CachePeer *const *)a;
34  const CachePeer *const *p2 = (const CachePeer *const *)b;
35  return (*p1)->weight - (*p2)->weight;
36 }
37 
38 void
40 {
41  int W = 0;
42  int K;
43  int k;
44  double P_last, X_last, Xn;
45  CachePeer *p;
46  CachePeer **P;
47  char *t;
48  /* Clean up */
49 
50  for (k = 0; k < n_sourcehash_peers; ++k) {
52  }
53 
56  /* find out which peers we have */
57 
58  for (p = Config.peers; p; p = p->next) {
59  if (!p->options.sourcehash)
60  continue;
61 
62  assert(p->type == PEER_PARENT);
63 
64  if (p->weight == 0)
65  continue;
66 
68 
69  W += p->weight;
70  }
71 
73 
74  if (n_sourcehash_peers == 0)
75  return;
76 
78 
79  /* Build a list of the found peers and calculate hashes and load factors */
80  for (P = sourcehash_peers, p = Config.peers; p; p = p->next) {
81  if (!p->options.sourcehash)
82  continue;
83 
84  if (p->weight == 0)
85  continue;
86 
87  /* calculate this peers hash */
88  p->sourcehash.hash = 0;
89 
90  for (t = p->name; *t != 0; ++t)
91  p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t;
92 
93  p->sourcehash.hash += p->sourcehash.hash * 0x62531965;
94 
95  p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21);
96 
97  /* and load factor */
98  p->sourcehash.load_factor = ((double) p->weight) / (double) W;
99 
100  if (floor(p->sourcehash.load_factor * 1000.0) == 0.0)
101  p->sourcehash.load_factor = 0.0;
102 
103  /* add it to our list of peers */
104  *P++ = cbdataReference(p);
105  }
106 
107  /* Sort our list on weight */
109 
110  /* Calculate the load factor multipliers X_k
111  *
112  * X_1 = pow ((K*p_1), (1/K))
113  * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
114  * X_k += pow ((X_{k-1}, {K-k+1})
115  * X_k = pow (X_k, {1/(K-k+1)})
116  * simplified to have X_1 part of the loop
117  */
118  K = n_sourcehash_peers;
119 
120  P_last = 0.0; /* Empty P_0 */
121 
122  Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
123 
124  X_last = 0.0; /* Empty X_0, nullifies the first pow statement */
125 
126  for (k = 1; k <= K; ++k) {
127  double Kk1 = (double) (K - k + 1);
128  p = sourcehash_peers[k - 1];
129  p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn;
130  p->sourcehash.load_multiplier += pow(X_last, Kk1);
131  p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1);
132  Xn *= p->sourcehash.load_multiplier;
133  X_last = p->sourcehash.load_multiplier;
134  P_last = p->sourcehash.load_factor;
135  }
136 }
137 
138 static void
140 {
141  Mgr::RegisterAction("sourcehash", "peer sourcehash information",
142  peerSourceHashCachemgr, 0, 1);
143 }
144 
145 CachePeer *
147 {
148  int k;
149  const char *c;
150  CachePeer *p = NULL;
151  CachePeer *tp;
152  unsigned int user_hash = 0;
153  unsigned int combined_hash;
154  double score;
155  double high_score = 0;
156  const char *key = NULL;
157  char ntoabuf[MAX_IPSTRLEN];
158 
159  if (n_sourcehash_peers == 0)
160  return NULL;
161 
162  assert(ps);
163  HttpRequest *request = ps->request;
164 
165  key = request->client_addr.toStr(ntoabuf, sizeof(ntoabuf));
166 
167  /* calculate hash key */
168  debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key);
169 
170  for (c = key; *c != 0; ++c)
171  user_hash += ROTATE_LEFT(user_hash, 19) + *c;
172 
173  /* select CachePeer */
174  for (k = 0; k < n_sourcehash_peers; ++k) {
175  tp = sourcehash_peers[k];
176  combined_hash = (user_hash ^ tp->sourcehash.hash);
177  combined_hash += combined_hash * 0x62531965;
178  combined_hash = ROTATE_LEFT(combined_hash, 21);
179  score = combined_hash * tp->sourcehash.load_multiplier;
180  debugs(39, 3, "peerSourceHashSelectParent: " << tp->name << " combined_hash " << combined_hash <<
181  " score " << std::setprecision(0) << score);
182 
183  if ((score > high_score) && peerHTTPOkay(tp, ps)) {
184  p = tp;
185  high_score = score;
186  }
187  }
188 
189  if (p)
190  debugs(39, 2, "peerSourceHashSelectParent: selected " << p->name);
191 
192  return p;
193 }
194 
195 static void
197 {
198  CachePeer *p;
199  int sumfetches = 0;
200  storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
201  "Hostname",
202  "Hash",
203  "Multiplier",
204  "Factor",
205  "Actual");
206 
207  for (p = Config.peers; p; p = p->next)
208  sumfetches += p->stats.fetches;
209 
210  for (p = Config.peers; p; p = p->next) {
211  storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
212  p->name, p->sourcehash.hash,
213  p->sourcehash.load_multiplier,
214  p->sourcehash.load_factor,
215  sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
216  }
217 }
218 
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
int fetches
Definition: CachePeer.h:48
HttpRequest * request
peer_t type
Definition: CachePeer.h:41
struct CachePeer::@30 options
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:869
static int n_sourcehash_peers
static void peerSourceHashRegisterWithCacheManager(void)
#define cbdataReference(var)
Definition: cbdata.h:341
bool sourcehash
Definition: CachePeer.h:116
char * name
Definition: CachePeer.h:39
#define ROTATE_LEFT(x, n)
#define MAX_IPSTRLEN
Length of buffer that needs to be allocated to old a null-terminated IP-string.
Definition: forward.h:25
int weight
Definition: CachePeer.h:125
void OBJH(StoreEntry *)
Definition: forward.h:44
#define NULL
Definition: types.h:166
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
@ PEER_PARENT
Definition: enums.h:30
struct CachePeer::@28 stats
#define safe_free(x)
Definition: xalloc.h:73
#define assert(EX)
Definition: assert.h:19
void EVH void double
Definition: stub_event.cc:16
static int peerSortWeight(const void *a, const void *b)
#define cbdataReferenceDone(var)
Definition: cbdata.h:350
CachePeer * peerSourceHashSelectParent(PeerSelector *ps)
static CachePeer ** sourcehash_peers
CachePeer * peers
Definition: SquidConfig.h:252
CachePeer * next
Definition: CachePeer.h:153
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:259
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
static OBJH peerSourceHashCachemgr
struct _request * request(char *urlin)
Definition: tcp-banger2.c:291
void peerSourceHashInit(void)
class SquidConfig Config
Definition: SquidConfig.cc:12
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors