peer_sourcehash.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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
25static int n_sourcehash_peers = 0;
26static CachePeer **sourcehash_peers = nullptr;
29
30static int
31peerSortWeight(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
38void
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 */
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
138static void
140{
141 Mgr::RegisterAction("sourcehash", "peer sourcehash information",
143}
144
145CachePeer *
147{
148 int k;
149 const char *c;
150 CachePeer *p = nullptr;
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 = nullptr;
157 char ntoabuf[MAX_IPSTRLEN];
158
159 if (n_sourcehash_peers == 0)
160 return nullptr;
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, *tp << " 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, "selected " << *p);
191
192 return p;
193}
194
195static 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
class SquidConfig Config
Definition: SquidConfig.cc:12
#define assert(EX)
Definition: assert.h:17
#define cbdataReferenceDone(var)
Definition: cbdata.h:352
#define cbdataReference(var)
Definition: cbdata.h:343
int weight
Definition: CachePeer.h:152
peer_t type
Definition: CachePeer.h:68
CachePeer * next
Definition: CachePeer.h:184
bool sourcehash
Definition: CachePeer.h:143
struct CachePeer::@27 stats
struct CachePeer::@29 options
char * name
Definition: CachePeer.h:60
int fetches
Definition: CachePeer.h:75
Ip::Address client_addr
Definition: HttpRequest.h:149
char * toStr(char *buf, const unsigned int blen, int force=AF_UNSPEC) const
Definition: Address.cc:792
HttpRequest * request
CachePeer * peers
Definition: SquidConfig.h:245
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:193
@ PEER_PARENT
Definition: enums.h:30
#define MAX_IPSTRLEN
Length of buffer that needs to be allocated to old a null-terminated IP-string.
Definition: forward.h:25
void OBJH(StoreEntry *)
Definition: forward.h:44
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:259
static void peerSourceHashRegisterWithCacheManager(void)
static OBJH peerSourceHashCachemgr
void peerSourceHashInit(void)
#define ROTATE_LEFT(x, n)
CachePeer * peerSourceHashSelectParent(PeerSelector *ps)
static int peerSortWeight(const void *a, const void *b)
static CachePeer ** sourcehash_peers
static int n_sourcehash_peers
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:829
void EVH void double
Definition: stub_event.cc:16
int unsigned int
Definition: stub_fd.cc:19
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors