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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors