]>
Commit | Line | Data |
---|---|---|
63104e28 | 1 | /* |
f70aedc4 | 2 | * Copyright (C) 1996-2021 The Squid Software Foundation and contributors |
63104e28 | 3 | * |
bbc27441 AJ |
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. | |
63104e28 HN |
7 | */ |
8 | ||
bbc27441 AJ |
9 | /* DEBUG: section 39 Peer user hash based selection */ |
10 | ||
582c2af2 | 11 | #include "squid.h" |
2f1431ea AJ |
12 | |
13 | #if USE_AUTH | |
14 | ||
582c2af2 | 15 | #include "auth/UserRequest.h" |
a011edee | 16 | #include "CachePeer.h" |
582c2af2 FC |
17 | #include "globals.h" |
18 | #include "HttpRequest.h" | |
8822ebee | 19 | #include "mgr/Registration.h" |
f0ba2534 | 20 | #include "neighbors.h" |
8b082ed9 | 21 | #include "peer_userhash.h" |
cb365059 | 22 | #include "PeerSelectState.h" |
4d5904f7 | 23 | #include "SquidConfig.h" |
63104e28 | 24 | #include "Store.h" |
582c2af2 | 25 | |
074d6a40 | 26 | #include <cmath> |
63104e28 HN |
27 | |
28 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) | |
29 | ||
f7e1d9ce | 30 | static int n_userhash_peers = 0; |
a3c6762c | 31 | static CachePeer **userhash_peers = NULL; |
f7e1d9ce | 32 | static OBJH peerUserHashCachemgr; |
6b661f2e | 33 | static void peerUserHashRegisterWithCacheManager(void); |
63104e28 HN |
34 | |
35 | static int | |
36 | peerSortWeight(const void *a, const void *b) | |
37 | { | |
a3c6762c FC |
38 | const CachePeer *const *p1 = (const CachePeer *const *)a; |
39 | const CachePeer *const *p2 = (const CachePeer *const *)b; | |
63104e28 HN |
40 | return (*p1)->weight - (*p2)->weight; |
41 | } | |
42 | ||
43 | void | |
f7e1d9ce | 44 | peerUserHashInit(void) |
63104e28 HN |
45 | { |
46 | int W = 0; | |
47 | int K; | |
48 | int k; | |
49 | double P_last, X_last, Xn; | |
a3c6762c FC |
50 | CachePeer *p; |
51 | CachePeer **P; | |
63104e28 HN |
52 | char *t; |
53 | /* Clean up */ | |
54 | ||
5db6bf73 | 55 | for (k = 0; k < n_userhash_peers; ++k) { |
f7e1d9ce | 56 | cbdataReferenceDone(userhash_peers[k]); |
63104e28 HN |
57 | } |
58 | ||
f7e1d9ce HN |
59 | safe_free(userhash_peers); |
60 | n_userhash_peers = 0; | |
63104e28 HN |
61 | /* find out which peers we have */ |
62 | ||
6b661f2e FC |
63 | peerUserHashRegisterWithCacheManager(); |
64 | ||
63104e28 | 65 | for (p = Config.peers; p; p = p->next) { |
f7e1d9ce | 66 | if (!p->options.userhash) |
63104e28 HN |
67 | continue; |
68 | ||
69 | assert(p->type == PEER_PARENT); | |
70 | ||
71 | if (p->weight == 0) | |
72 | continue; | |
73 | ||
5db6bf73 | 74 | ++n_userhash_peers; |
63104e28 HN |
75 | |
76 | W += p->weight; | |
77 | } | |
78 | ||
f7e1d9ce | 79 | if (n_userhash_peers == 0) |
63104e28 HN |
80 | return; |
81 | ||
a3c6762c | 82 | userhash_peers = (CachePeer **)xcalloc(n_userhash_peers, sizeof(*userhash_peers)); |
63104e28 HN |
83 | |
84 | /* Build a list of the found peers and calculate hashes and load factors */ | |
f7e1d9ce HN |
85 | for (P = userhash_peers, p = Config.peers; p; p = p->next) { |
86 | if (!p->options.userhash) | |
63104e28 HN |
87 | continue; |
88 | ||
89 | if (p->weight == 0) | |
90 | continue; | |
91 | ||
92 | /* calculate this peers hash */ | |
f7e1d9ce | 93 | p->userhash.hash = 0; |
63104e28 | 94 | |
5db6bf73 | 95 | for (t = p->name; *t != 0; ++t) |
f7e1d9ce | 96 | p->userhash.hash += ROTATE_LEFT(p->userhash.hash, 19) + (unsigned int) *t; |
63104e28 | 97 | |
f7e1d9ce | 98 | p->userhash.hash += p->userhash.hash * 0x62531965; |
63104e28 | 99 | |
f7e1d9ce | 100 | p->userhash.hash = ROTATE_LEFT(p->userhash.hash, 21); |
63104e28 HN |
101 | |
102 | /* and load factor */ | |
f7e1d9ce | 103 | p->userhash.load_factor = ((double) p->weight) / (double) W; |
63104e28 | 104 | |
f7e1d9ce HN |
105 | if (floor(p->userhash.load_factor * 1000.0) == 0.0) |
106 | p->userhash.load_factor = 0.0; | |
63104e28 HN |
107 | |
108 | /* add it to our list of peers */ | |
109 | *P++ = cbdataReference(p); | |
110 | } | |
111 | ||
112 | /* Sort our list on weight */ | |
f7e1d9ce | 113 | qsort(userhash_peers, n_userhash_peers, sizeof(*userhash_peers), peerSortWeight); |
63104e28 HN |
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 | */ | |
f7e1d9ce | 123 | K = n_userhash_peers; |
63104e28 | 124 | |
f53969cc | 125 | P_last = 0.0; /* Empty P_0 */ |
63104e28 | 126 | |
f53969cc | 127 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ |
63104e28 | 128 | |
f53969cc | 129 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ |
63104e28 | 130 | |
5db6bf73 | 131 | for (k = 1; k <= K; ++k) { |
63104e28 | 132 | double Kk1 = (double) (K - k + 1); |
f7e1d9ce HN |
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; | |
63104e28 HN |
140 | } |
141 | } | |
142 | ||
6b661f2e FC |
143 | static void |
144 | peerUserHashRegisterWithCacheManager(void) | |
63104e28 | 145 | { |
8822ebee | 146 | Mgr::RegisterAction("userhash", "peer userhash information", peerUserHashCachemgr, |
d9fc6862 | 147 | 0, 1); |
63104e28 HN |
148 | } |
149 | ||
a3c6762c | 150 | CachePeer * |
cb365059 | 151 | peerUserHashSelectParent(PeerSelector *ps) |
63104e28 HN |
152 | { |
153 | int k; | |
154 | const char *c; | |
a3c6762c FC |
155 | CachePeer *p = NULL; |
156 | CachePeer *tp; | |
63104e28 HN |
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 | ||
f7e1d9ce | 163 | if (n_userhash_peers == 0) |
63104e28 HN |
164 | return NULL; |
165 | ||
cb365059 EB |
166 | assert(ps); |
167 | HttpRequest *request = ps->request; | |
168 | ||
a33a428a | 169 | if (request->auth_user_request != NULL) |
26ac0430 | 170 | key = request->auth_user_request->username(); |
eec27647 HN |
171 | |
172 | if (!key) | |
26ac0430 | 173 | return NULL; |
63104e28 HN |
174 | |
175 | /* calculate hash key */ | |
f7e1d9ce | 176 | debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key); |
63104e28 | 177 | |
5db6bf73 | 178 | for (c = key; *c != 0; ++c) |
63104e28 HN |
179 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
180 | ||
a3c6762c | 181 | /* select CachePeer */ |
5db6bf73 | 182 | for (k = 0; k < n_userhash_peers; ++k) { |
f7e1d9ce HN |
183 | tp = userhash_peers[k]; |
184 | combined_hash = (user_hash ^ tp->userhash.hash); | |
63104e28 HN |
185 | combined_hash += combined_hash * 0x62531965; |
186 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
f7e1d9ce | 187 | score = combined_hash * tp->userhash.load_multiplier; |
26ac0430 | 188 | debugs(39, 3, "peerUserHashSelectParent: " << tp->name << " combined_hash " << combined_hash << |
63104e28 HN |
189 | " score " << std::setprecision(0) << score); |
190 | ||
cb365059 | 191 | if ((score > high_score) && peerHTTPOkay(tp, ps)) { |
63104e28 HN |
192 | p = tp; |
193 | high_score = score; | |
194 | } | |
195 | } | |
196 | ||
197 | if (p) | |
f7e1d9ce | 198 | debugs(39, 2, "peerUserHashSelectParent: selected " << p->name); |
63104e28 HN |
199 | |
200 | return p; | |
201 | } | |
202 | ||
203 | static void | |
f7e1d9ce | 204 | peerUserHashCachemgr(StoreEntry * sentry) |
63104e28 | 205 | { |
a3c6762c | 206 | CachePeer *p; |
63104e28 HN |
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", | |
f7e1d9ce HN |
220 | p->name, p->userhash.hash, |
221 | p->userhash.load_multiplier, | |
222 | p->userhash.load_factor, | |
63104e28 HN |
223 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); |
224 | } | |
225 | } | |
2f1431ea AJ |
226 | |
227 | #endif /* USE_AUTH */ | |
f53969cc | 228 |