2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 39 Peer source hash based selection */
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"
23 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
25 static int n_sourcehash_peers
= 0;
26 static CachePeer
**sourcehash_peers
= nullptr;
27 static OBJH peerSourceHashCachemgr
;
28 static void peerSourceHashRegisterWithCacheManager(void);
31 peerSortWeight(const void *a
, const void *b
)
33 const CachePeer
*const *p1
= (const CachePeer
*const *)a
;
34 const CachePeer
*const *p2
= (const CachePeer
*const *)b
;
35 return (*p1
)->weight
- (*p2
)->weight
;
39 peerSourceHashInit(void)
44 double P_last
, X_last
, Xn
;
50 for (k
= 0; k
< n_sourcehash_peers
; ++k
) {
51 cbdataReferenceDone(sourcehash_peers
[k
]);
54 safe_free(sourcehash_peers
);
55 n_sourcehash_peers
= 0;
56 /* find out which peers we have */
58 for (p
= Config
.peers
; p
; p
= p
->next
) {
59 if (!p
->options
.sourcehash
)
62 assert(p
->type
== PEER_PARENT
);
72 peerSourceHashRegisterWithCacheManager();
74 if (n_sourcehash_peers
== 0)
77 sourcehash_peers
= (CachePeer
**)xcalloc(n_sourcehash_peers
, sizeof(*sourcehash_peers
));
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
)
87 /* calculate this peers hash */
88 p
->sourcehash
.hash
= 0;
90 for (t
= p
->name
; *t
!= 0; ++t
)
91 p
->sourcehash
.hash
+= ROTATE_LEFT(p
->sourcehash
.hash
, 19) + (unsigned int) *t
;
93 p
->sourcehash
.hash
+= p
->sourcehash
.hash
* 0x62531965;
95 p
->sourcehash
.hash
= ROTATE_LEFT(p
->sourcehash
.hash
, 21);
98 p
->sourcehash
.load_factor
= ((double) p
->weight
) / (double) W
;
100 if (floor(p
->sourcehash
.load_factor
* 1000.0) == 0.0)
101 p
->sourcehash
.load_factor
= 0.0;
103 /* add it to our list of peers */
104 *P
++ = cbdataReference(p
);
107 /* Sort our list on weight */
108 qsort(sourcehash_peers
, n_sourcehash_peers
, sizeof(*sourcehash_peers
), peerSortWeight
);
110 /* Calculate the load factor multipliers X_k
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
118 K
= n_sourcehash_peers
;
120 P_last
= 0.0; /* Empty P_0 */
122 Xn
= 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
124 X_last
= 0.0; /* Empty X_0, nullifies the first pow statement */
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
;
139 peerSourceHashRegisterWithCacheManager(void)
141 Mgr::RegisterAction("sourcehash", "peer sourcehash information",
142 peerSourceHashCachemgr
, 0, 1);
146 peerSourceHashSelectParent(PeerSelector
*ps
)
150 CachePeer
*p
= nullptr;
152 unsigned int user_hash
= 0;
153 unsigned int combined_hash
;
155 double high_score
= 0;
156 const char *key
= nullptr;
157 char ntoabuf
[MAX_IPSTRLEN
];
159 if (n_sourcehash_peers
== 0)
163 HttpRequest
*request
= ps
->request
;
165 key
= request
->client_addr
.toStr(ntoabuf
, sizeof(ntoabuf
));
167 /* calculate hash key */
168 debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key
);
170 for (c
= key
; *c
!= 0; ++c
)
171 user_hash
+= ROTATE_LEFT(user_hash
, 19) + *c
;
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
);
183 if ((score
> high_score
) && peerHTTPOkay(tp
, ps
)) {
190 debugs(39, 2, "peerSourceHashSelectParent: selected " << p
->name
);
196 peerSourceHashCachemgr(StoreEntry
* sentry
)
200 storeAppendPrintf(sentry
, "%24s %10s %10s %10s %10s\n",
207 for (p
= Config
.peers
; p
; p
= p
->next
)
208 sumfetches
+= p
->stats
.fetches
;
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);