← Back to branch summary

~clint-fewbar/ubuntu/precise/squid3/ignore-sighup-early

« back to all changes in this revision

Viewing changes to src/carp.cc

  • Committer: Bazaar Package Importer
  • Author(s): Luigi Gangitano
  • Date: 2006-11-11 10:32:06 UTC
  • Revision ID: james.westby@ubuntu.com-20061111103206-f3p0r9g0vq44rp3r
Tags: upstream-3.0.PRE5
Import upstream version 3.0.PRE5

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/carp.cc
 
1
 
 
2
/*
 
3
 * $Id: carp.cc,v 1.25 2006/05/29 00:15:01 robertc Exp $
 
4
 *
 
5
 * DEBUG: section 39    Cache Array Routing Protocol
 
6
 * AUTHOR: Henrik Nordstrom
 
7
 * BASED ON: carp.c by Eric Stern and draft-vinod-carp-v1-03.txt
 
8
 *
 
9
 * SQUID Web Proxy Cache          http://www.squid-cache.org/
 
10
 * ----------------------------------------------------------
 
11
 *
 
12
 *  Squid is the result of efforts by numerous individuals from
 
13
 *  the Internet community; see the CONTRIBUTORS file for full
 
14
 *  details.   Many organizations have provided support for Squid's
 
15
 *  development; see the SPONSORS file for full details.  Squid is
 
16
 *  Copyrighted (C) 2001 by the Regents of the University of
 
17
 *  California; see the COPYRIGHT file for full details.  Squid
 
18
 *  incorporates software developed and/or copyrighted by other
 
19
 *  sources; see the CREDITS file for full details.
 
20
 *
 
21
 *  This program is free software; you can redistribute it and/or modify
 
22
 *  it under the terms of the GNU General Public License as published by
 
23
 *  the Free Software Foundation; either version 2 of the License, or
 
24
 *  (at your option) any later version.
 
25
 *  
 
26
 *  This program is distributed in the hope that it will be useful,
 
27
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
28
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
29
 *  GNU General Public License for more details.
 
30
 *  
 
31
 *  You should have received a copy of the GNU General Public License
 
32
 *  along with this program; if not, write to the Free Software
 
33
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 
34
 *
 
35
 */
 
36
 
 
37
#include "squid.h"
 
38
#include "CacheManager.h"
 
39
#include "Store.h"
 
40
 
 
41
#if USE_CARP
 
42
 
 
43
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
 
44
 
 
45
static int n_carp_peers = 0;
 
46
static peer **carp_peers = NULL;
 
47
static OBJH carpCachemgr;
 
48
 
 
49
static int
 
50
peerSortWeight(const void *a, const void *b)
 
51
{
 
52
    const peer *const *p1 = (const peer *const *)a;
 
53
    const peer *const *p2 = (const peer *const *)b;
 
54
    return (*p1)->weight - (*p2)->weight;
 
55
}
 
56
 
 
57
void
 
58
carpInit(void)
 
59
{
 
60
    int W = 0;
 
61
    int K;
 
62
    int k;
 
63
    double P_last, X_last, Xn;
 
64
    peer *p;
 
65
    peer **P;
 
66
    char *t;
 
67
    /* Clean up */
 
68
 
 
69
    for (k = 0; k < n_carp_peers; k++) {
 
70
        cbdataReferenceDone(carp_peers[k]);
 
71
    }
 
72
 
 
73
    safe_free(carp_peers);
 
74
    n_carp_peers = 0;
 
75
    /* find out which peers we have */
 
76
 
 
77
    for (p = Config.peers; p; p = p->next) {
 
78
        if (!p->options.carp)
 
79
            continue;
 
80
 
 
81
        assert(p->type == PEER_PARENT);
 
82
 
 
83
        if (p->weight == 0)
 
84
            continue;
 
85
 
 
86
        n_carp_peers++;
 
87
 
 
88
        W += p->weight;
 
89
    }
 
90
 
 
91
    if (n_carp_peers == 0)
 
92
        return;
 
93
 
 
94
    carp_peers = (peer **)xcalloc(n_carp_peers, sizeof(*carp_peers));
 
95
 
 
96
    /* Build a list of the found peers and calculate hashes and load factors */
 
97
    for (P = carp_peers, p = Config.peers; p; p = p->next) {
 
98
        if (!p->options.carp)
 
99
            continue;
 
100
 
 
101
        if (p->weight == 0)
 
102
            continue;
 
103
 
 
104
        /* calculate this peers hash */
 
105
        p->carp.hash = 0;
 
106
 
 
107
        for (t = p->host; *t != 0; t++)
 
108
            p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t;
 
109
 
 
110
        p->carp.hash += p->carp.hash * 0x62531965;
 
111
 
 
112
        p->carp.hash = ROTATE_LEFT(p->carp.hash, 21);
 
113
 
 
114
        /* and load factor */
 
115
        p->carp.load_factor = ((double) p->weight) / (double) W;
 
116
 
 
117
        if (floor(p->carp.load_factor * 1000.0) == 0.0)
 
118
            p->carp.load_factor = 0.0;
 
119
 
 
120
        /* add it to our list of peers */
 
121
        *P++ = cbdataReference(p);
 
122
    }
 
123
 
 
124
    /* Sort our list on weight */
 
125
    qsort(carp_peers, n_carp_peers, sizeof(*carp_peers), peerSortWeight);
 
126
 
 
127
    /* Calculate the load factor multipliers X_k
 
128
     *
 
129
     * X_1 = pow ((K*p_1), (1/K))
 
130
     * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
 
131
     * X_k += pow ((X_{k-1}, {K-k+1})
 
132
     * X_k = pow (X_k, {1/(K-k+1)})
 
133
     * simplified to have X_1 part of the loop
 
134
     */
 
135
    K = n_carp_peers;
 
136
 
 
137
    P_last = 0.0;               /* Empty P_0 */
 
138
 
 
139
    Xn = 1.0;                   /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
 
140
 
 
141
    X_last = 0.0;               /* Empty X_0, nullifies the first pow statement */
 
142
 
 
143
    for (k = 1; k <= K; k++) {
 
144
        double Kk1 = (double) (K - k + 1);
 
145
        p = carp_peers[k - 1];
 
146
        p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn;
 
147
        p->carp.load_multiplier += pow(X_last, Kk1);
 
148
        p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1);
 
149
        Xn *= p->carp.load_multiplier;
 
150
        X_last = p->carp.load_multiplier;
 
151
        P_last = p->carp.load_factor;
 
152
    }
 
153
}
 
154
 
 
155
void
 
156
carpRegisterWithCacheManager(CacheManager & manager)
 
157
{
 
158
    manager.registerAction("carp", "CARP information", carpCachemgr, 0, 1);
 
159
}
 
160
 
 
161
peer *
 
162
carpSelectParent(HttpRequest * request)
 
163
{
 
164
    int k;
 
165
    const char *c;
 
166
    peer *p = NULL;
 
167
    peer *tp;
 
168
    unsigned int user_hash = 0;
 
169
    unsigned int combined_hash;
 
170
    double score;
 
171
    double high_score = 0;
 
172
    const char *key = NULL;
 
173
 
 
174
    if (n_carp_peers == 0)
 
175
        return NULL;
 
176
 
 
177
    key = urlCanonical(request);
 
178
 
 
179
    /* calculate hash key */
 
180
    debug(39, 2) ("carpSelectParent: Calculating hash for %s\n", key);
 
181
 
 
182
    for (c = key; *c != 0; c++)
 
183
        user_hash += ROTATE_LEFT(user_hash, 19) + *c;
 
184
 
 
185
    /* select peer */
 
186
    for (k = 0; k < n_carp_peers; k++) {
 
187
        tp = carp_peers[k];
 
188
        combined_hash = (user_hash ^ tp->carp.hash);
 
189
        combined_hash += combined_hash * 0x62531965;
 
190
        combined_hash = ROTATE_LEFT(combined_hash, 21);
 
191
        score = combined_hash * tp->carp.load_multiplier;
 
192
        debug(39, 3) ("carpSelectParent: %s combined_hash %u score %.0f\n",
 
193
                      tp->host, combined_hash, score);
 
194
 
 
195
        if ((score > high_score) && peerHTTPOkay(tp, request)) {
 
196
            p = tp;
 
197
            high_score = score;
 
198
        }
 
199
    }
 
200
 
 
201
    if (p)
 
202
        debug(39, 2) ("carpSelectParent: selected %s\n", p->host);
 
203
 
 
204
    return p;
 
205
}
 
206
 
 
207
static void
 
208
carpCachemgr(StoreEntry * sentry)
 
209
{
 
210
    peer *p;
 
211
    int sumfetches = 0;
 
212
    storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 
213
                      "Hostname",
 
214
                      "Hash",
 
215
                      "Multiplier",
 
216
                      "Factor",
 
217
                      "Actual");
 
218
 
 
219
    for (p = Config.peers; p; p = p->next)
 
220
        sumfetches += p->stats.fetches;
 
221
 
 
222
    for (p = Config.peers; p; p = p->next) {
 
223
        storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 
224
                          p->host, p->carp.hash,
 
225
                          p->carp.load_multiplier,
 
226
                          p->carp.load_factor,
 
227
                          sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 
228
    }
 
229
}
 
230
 
 
231
#endif