peer_userhash.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 user hash based selection */
10 
11 #include "squid.h"
12 
13 #if USE_AUTH
14 
15 #include "auth/UserRequest.h"
16 #include "CachePeer.h"
17 #include "globals.h"
18 #include "HttpRequest.h"
19 #include "mgr/Registration.h"
20 #include "neighbors.h"
21 #include "peer_userhash.h"
22 #include "PeerSelectState.h"
23 #include "SquidConfig.h"
24 #include "Store.h"
25 
26 #include <cmath>
27 
28 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
29 
30 static int n_userhash_peers = 0;
33 static void peerUserHashRegisterWithCacheManager(void);
34 
35 static int
36 peerSortWeight(const void *a, const void *b)
37 {
38  const CachePeer *const *p1 = (const CachePeer *const *)a;
39  const CachePeer *const *p2 = (const CachePeer *const *)b;
40  return (*p1)->weight - (*p2)->weight;
41 }
42 
43 void
45 {
46  int W = 0;
47  int K;
48  int k;
49  double P_last, X_last, Xn;
50  CachePeer *p;
51  CachePeer **P;
52  char *t;
53  /* Clean up */
54 
55  for (k = 0; k < n_userhash_peers; ++k) {
57  }
58 
60  n_userhash_peers = 0;
61  /* find out which peers we have */
62 
64 
65  for (p = Config.peers; p; p = p->next) {
66  if (!p->options.userhash)
67  continue;
68 
69  assert(p->type == PEER_PARENT);
70 
71  if (p->weight == 0)
72  continue;
73 
75 
76  W += p->weight;
77  }
78 
79  if (n_userhash_peers == 0)
80  return;
81 
83 
84  /* Build a list of the found peers and calculate hashes and load factors */
85  for (P = userhash_peers, p = Config.peers; p; p = p->next) {
86  if (!p->options.userhash)
87  continue;
88 
89  if (p->weight == 0)
90  continue;
91 
92  /* calculate this peers hash */
93  p->userhash.hash = 0;
94 
95  for (t = p->name; *t != 0; ++t)
96  p->userhash.hash += ROTATE_LEFT(p->userhash.hash, 19) + (unsigned int) *t;
97 
98  p->userhash.hash += p->userhash.hash * 0x62531965;
99 
100  p->userhash.hash = ROTATE_LEFT(p->userhash.hash, 21);
101 
102  /* and load factor */
103  p->userhash.load_factor = ((double) p->weight) / (double) W;
104 
105  if (floor(p->userhash.load_factor * 1000.0) == 0.0)
106  p->userhash.load_factor = 0.0;
107 
108  /* add it to our list of peers */
109  *P++ = cbdataReference(p);
110  }
111 
112  /* Sort our list on weight */
114 
115  /* Calculate the load factor multipliers X_k
116  *
117  * X_1 = pow ((K*p_1), (1/K))
118  * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
119  * X_k += pow ((X_{k-1}, {K-k+1})
120  * X_k = pow (X_k, {1/(K-k+1)})
121  * simplified to have X_1 part of the loop
122  */
123  K = n_userhash_peers;
124 
125  P_last = 0.0; /* Empty P_0 */
126 
127  Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
128 
129  X_last = 0.0; /* Empty X_0, nullifies the first pow statement */
130 
131  for (k = 1; k <= K; ++k) {
132  double Kk1 = (double) (K - k + 1);
133  p = userhash_peers[k - 1];
134  p->userhash.load_multiplier = (Kk1 * (p->userhash.load_factor - P_last)) / Xn;
135  p->userhash.load_multiplier += pow(X_last, Kk1);
136  p->userhash.load_multiplier = pow(p->userhash.load_multiplier, 1.0 / Kk1);
137  Xn *= p->userhash.load_multiplier;
138  X_last = p->userhash.load_multiplier;
139  P_last = p->userhash.load_factor;
140  }
141 }
142 
143 static void
145 {
146  Mgr::RegisterAction("userhash", "peer userhash information", peerUserHashCachemgr,
147  0, 1);
148 }
149 
150 CachePeer *
152 {
153  int k;
154  const char *c;
155  CachePeer *p = NULL;
156  CachePeer *tp;
157  unsigned int user_hash = 0;
158  unsigned int combined_hash;
159  double score;
160  double high_score = 0;
161  const char *key = NULL;
162 
163  if (n_userhash_peers == 0)
164  return NULL;
165 
166  assert(ps);
167  HttpRequest *request = ps->request;
168 
169  if (request->auth_user_request != NULL)
170  key = request->auth_user_request->username();
171 
172  if (!key)
173  return NULL;
174 
175  /* calculate hash key */
176  debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key);
177 
178  for (c = key; *c != 0; ++c)
179  user_hash += ROTATE_LEFT(user_hash, 19) + *c;
180 
181  /* select CachePeer */
182  for (k = 0; k < n_userhash_peers; ++k) {
183  tp = userhash_peers[k];
184  combined_hash = (user_hash ^ tp->userhash.hash);
185  combined_hash += combined_hash * 0x62531965;
186  combined_hash = ROTATE_LEFT(combined_hash, 21);
187  score = combined_hash * tp->userhash.load_multiplier;
188  debugs(39, 3, "peerUserHashSelectParent: " << tp->name << " combined_hash " << combined_hash <<
189  " score " << std::setprecision(0) << score);
190 
191  if ((score > high_score) && peerHTTPOkay(tp, ps)) {
192  p = tp;
193  high_score = score;
194  }
195  }
196 
197  if (p)
198  debugs(39, 2, "peerUserHashSelectParent: selected " << p->name);
199 
200  return p;
201 }
202 
203 static void
205 {
206  CachePeer *p;
207  int sumfetches = 0;
208  storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
209  "Hostname",
210  "Hash",
211  "Multiplier",
212  "Factor",
213  "Actual");
214 
215  for (p = Config.peers; p; p = p->next)
216  sumfetches += p->stats.fetches;
217 
218  for (p = Config.peers; p; p = p->next) {
219  storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
220  p->name, p->userhash.hash,
221  p->userhash.load_multiplier,
222  p->userhash.load_factor,
223  sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
224  }
225 }
226 
227 #endif /* USE_AUTH */
228 
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
static CachePeer ** userhash_peers
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
CachePeer * peerUserHashSelectParent(PeerSelector *ps)
static int n_userhash_peers
static int peerSortWeight(const void *a, const void *b)
static void peerUserHashRegisterWithCacheManager(void)
#define cbdataReference(var)
Definition: cbdata.h:341
char * name
Definition: CachePeer.h:39
static OBJH peerUserHashCachemgr
int weight
Definition: CachePeer.h:125
bool userhash
Definition: CachePeer.h:114
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
#define cbdataReferenceDone(var)
Definition: cbdata.h:350
#define ROTATE_LEFT(x, n)
CachePeer * peers
Definition: SquidConfig.h:252
void peerUserHashInit(void)
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
struct _request * request(char *urlin)
Definition: tcp-banger2.c:291
class SquidConfig Config
Definition: SquidConfig.cc:12
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors