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