1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Roman Arutyunyan
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#include <ngx_config.h>
9e18a033bSKonstantin Ananyev#include <ngx_core.h>
10e18a033bSKonstantin Ananyev#include <ngx_http.h>
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyev
13e18a033bSKonstantin Ananyevtypedef struct {
14e18a033bSKonstantin Ananyev    uint32_t                            hash;
15e18a033bSKonstantin Ananyev    ngx_str_t                          *server;
16e18a033bSKonstantin Ananyev} ngx_http_upstream_chash_point_t;
17e18a033bSKonstantin Ananyev
18e18a033bSKonstantin Ananyev
19e18a033bSKonstantin Ananyevtypedef struct {
20e18a033bSKonstantin Ananyev    ngx_uint_t                          number;
21e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_point_t     point[1];
22e18a033bSKonstantin Ananyev} ngx_http_upstream_chash_points_t;
23e18a033bSKonstantin Ananyev
24e18a033bSKonstantin Ananyev
25e18a033bSKonstantin Ananyevtypedef struct {
26e18a033bSKonstantin Ananyev    ngx_http_complex_value_t            key;
27e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_points_t   *points;
28e18a033bSKonstantin Ananyev} ngx_http_upstream_hash_srv_conf_t;
29e18a033bSKonstantin Ananyev
30e18a033bSKonstantin Ananyev
31e18a033bSKonstantin Ananyevtypedef struct {
32e18a033bSKonstantin Ananyev    /* the round robin data must be first */
33e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peer_data_t    rrp;
34e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_srv_conf_t  *conf;
35e18a033bSKonstantin Ananyev    ngx_str_t                           key;
36e18a033bSKonstantin Ananyev    ngx_uint_t                          tries;
37e18a033bSKonstantin Ananyev    ngx_uint_t                          rehash;
38e18a033bSKonstantin Ananyev    uint32_t                            hash;
39e18a033bSKonstantin Ananyev    ngx_event_get_peer_pt               get_rr_peer;
40e18a033bSKonstantin Ananyev} ngx_http_upstream_hash_peer_data_t;
41e18a033bSKonstantin Ananyev
42e18a033bSKonstantin Ananyev
43e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_init_hash(ngx_conf_t *cf,
44e18a033bSKonstantin Ananyev    ngx_http_upstream_srv_conf_t *us);
45e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
46e18a033bSKonstantin Ananyev    ngx_http_upstream_srv_conf_t *us);
47e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc,
48e18a033bSKonstantin Ananyev    void *data);
49e18a033bSKonstantin Ananyev
50e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf,
51e18a033bSKonstantin Ananyev    ngx_http_upstream_srv_conf_t *us);
52e18a033bSKonstantin Ananyevstatic int ngx_libc_cdecl
53e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_cmp_points(const void *one, const void *two);
54e18a033bSKonstantin Ananyevstatic ngx_uint_t ngx_http_upstream_find_chash_point(
55e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_points_t *points, uint32_t hash);
56e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
57e18a033bSKonstantin Ananyev    ngx_http_upstream_srv_conf_t *us);
58e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc,
59e18a033bSKonstantin Ananyev    void *data);
60e18a033bSKonstantin Ananyev
61e18a033bSKonstantin Ananyevstatic void *ngx_http_upstream_hash_create_conf(ngx_conf_t *cf);
62e18a033bSKonstantin Ananyevstatic char *ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd,
63e18a033bSKonstantin Ananyev    void *conf);
64e18a033bSKonstantin Ananyev
65e18a033bSKonstantin Ananyev
66e18a033bSKonstantin Ananyevstatic ngx_command_t  ngx_http_upstream_hash_commands[] = {
67e18a033bSKonstantin Ananyev
68e18a033bSKonstantin Ananyev    { ngx_string("hash"),
69e18a033bSKonstantin Ananyev      NGX_HTTP_UPS_CONF|NGX_CONF_TAKE12,
70e18a033bSKonstantin Ananyev      ngx_http_upstream_hash,
71e18a033bSKonstantin Ananyev      NGX_HTTP_SRV_CONF_OFFSET,
72e18a033bSKonstantin Ananyev      0,
73e18a033bSKonstantin Ananyev      NULL },
74e18a033bSKonstantin Ananyev
75e18a033bSKonstantin Ananyev      ngx_null_command
76e18a033bSKonstantin Ananyev};
77e18a033bSKonstantin Ananyev
78e18a033bSKonstantin Ananyev
79e18a033bSKonstantin Ananyevstatic ngx_http_module_t  ngx_http_upstream_hash_module_ctx = {
80e18a033bSKonstantin Ananyev    NULL,                                  /* preconfiguration */
81e18a033bSKonstantin Ananyev    NULL,                                  /* postconfiguration */
82e18a033bSKonstantin Ananyev
83e18a033bSKonstantin Ananyev    NULL,                                  /* create main configuration */
84e18a033bSKonstantin Ananyev    NULL,                                  /* init main configuration */
85e18a033bSKonstantin Ananyev
86e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_create_conf,    /* create server configuration */
87e18a033bSKonstantin Ananyev    NULL,                                  /* merge server configuration */
88e18a033bSKonstantin Ananyev
89e18a033bSKonstantin Ananyev    NULL,                                  /* create location configuration */
90e18a033bSKonstantin Ananyev    NULL                                   /* merge location configuration */
91e18a033bSKonstantin Ananyev};
92e18a033bSKonstantin Ananyev
93e18a033bSKonstantin Ananyev
94e18a033bSKonstantin Ananyevngx_module_t  ngx_http_upstream_hash_module = {
95e18a033bSKonstantin Ananyev    NGX_MODULE_V1,
96e18a033bSKonstantin Ananyev    &ngx_http_upstream_hash_module_ctx,    /* module context */
97e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_commands,       /* module directives */
98e18a033bSKonstantin Ananyev    NGX_HTTP_MODULE,                       /* module type */
99e18a033bSKonstantin Ananyev    NULL,                                  /* init master */
100e18a033bSKonstantin Ananyev    NULL,                                  /* init module */
101e18a033bSKonstantin Ananyev    NULL,                                  /* init process */
102e18a033bSKonstantin Ananyev    NULL,                                  /* init thread */
103e18a033bSKonstantin Ananyev    NULL,                                  /* exit thread */
104e18a033bSKonstantin Ananyev    NULL,                                  /* exit process */
105e18a033bSKonstantin Ananyev    NULL,                                  /* exit master */
106e18a033bSKonstantin Ananyev    NGX_MODULE_V1_PADDING
107e18a033bSKonstantin Ananyev};
108e18a033bSKonstantin Ananyev
109e18a033bSKonstantin Ananyev
110e18a033bSKonstantin Ananyevstatic ngx_int_t
111e18a033bSKonstantin Ananyevngx_http_upstream_init_hash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
112e18a033bSKonstantin Ananyev{
113e18a033bSKonstantin Ananyev    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
114e18a033bSKonstantin Ananyev        return NGX_ERROR;
115e18a033bSKonstantin Ananyev    }
116e18a033bSKonstantin Ananyev
117e18a033bSKonstantin Ananyev    us->peer.init = ngx_http_upstream_init_hash_peer;
118e18a033bSKonstantin Ananyev
119e18a033bSKonstantin Ananyev    return NGX_OK;
120e18a033bSKonstantin Ananyev}
121e18a033bSKonstantin Ananyev
122e18a033bSKonstantin Ananyev
123e18a033bSKonstantin Ananyevstatic ngx_int_t
124e18a033bSKonstantin Ananyevngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
125e18a033bSKonstantin Ananyev    ngx_http_upstream_srv_conf_t *us)
126e18a033bSKonstantin Ananyev{
127e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_srv_conf_t   *hcf;
128e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_peer_data_t  *hp;
129e18a033bSKonstantin Ananyev
130e18a033bSKonstantin Ananyev    hp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_hash_peer_data_t));
131e18a033bSKonstantin Ananyev    if (hp == NULL) {
132e18a033bSKonstantin Ananyev        return NGX_ERROR;
133e18a033bSKonstantin Ananyev    }
134e18a033bSKonstantin Ananyev
135e18a033bSKonstantin Ananyev    r->upstream->peer.data = &hp->rrp;
136e18a033bSKonstantin Ananyev
137e18a033bSKonstantin Ananyev    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
138e18a033bSKonstantin Ananyev        return NGX_ERROR;
139e18a033bSKonstantin Ananyev    }
140e18a033bSKonstantin Ananyev
141e18a033bSKonstantin Ananyev    r->upstream->peer.get = ngx_http_upstream_get_hash_peer;
142e18a033bSKonstantin Ananyev
143e18a033bSKonstantin Ananyev    hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
144e18a033bSKonstantin Ananyev
145e18a033bSKonstantin Ananyev    if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK) {
146e18a033bSKonstantin Ananyev        return NGX_ERROR;
147e18a033bSKonstantin Ananyev    }
148e18a033bSKonstantin Ananyev
149e18a033bSKonstantin Ananyev    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
150e18a033bSKonstantin Ananyev                   "upstream hash key:\"%V\"", &hp->key);
151e18a033bSKonstantin Ananyev
152e18a033bSKonstantin Ananyev    hp->conf = hcf;
153e18a033bSKonstantin Ananyev    hp->tries = 0;
154e18a033bSKonstantin Ananyev    hp->rehash = 0;
155e18a033bSKonstantin Ananyev    hp->hash = 0;
156e18a033bSKonstantin Ananyev    hp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;
157e18a033bSKonstantin Ananyev
158e18a033bSKonstantin Ananyev    return NGX_OK;
159e18a033bSKonstantin Ananyev}
160e18a033bSKonstantin Ananyev
161e18a033bSKonstantin Ananyev
162e18a033bSKonstantin Ananyevstatic ngx_int_t
163e18a033bSKonstantin Ananyevngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc, void *data)
164e18a033bSKonstantin Ananyev{
165e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_peer_data_t  *hp = data;
166e18a033bSKonstantin Ananyev
167e18a033bSKonstantin Ananyev    time_t                        now;
168e18a033bSKonstantin Ananyev    u_char                        buf[NGX_INT_T_LEN];
169e18a033bSKonstantin Ananyev    size_t                        size;
170e18a033bSKonstantin Ananyev    uint32_t                      hash;
171e18a033bSKonstantin Ananyev    ngx_int_t                     w;
172e18a033bSKonstantin Ananyev    uintptr_t                     m;
173e18a033bSKonstantin Ananyev    ngx_uint_t                    n, p;
174e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peer_t  *peer;
175e18a033bSKonstantin Ananyev
176e18a033bSKonstantin Ananyev    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
177e18a033bSKonstantin Ananyev                   "get hash peer, try: %ui", pc->tries);
178e18a033bSKonstantin Ananyev
179e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peers_wlock(hp->rrp.peers);
180e18a033bSKonstantin Ananyev
181e18a033bSKonstantin Ananyev    if (hp->tries > 20 || hp->rrp.peers->single) {
182e18a033bSKonstantin Ananyev        ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
183e18a033bSKonstantin Ananyev        return hp->get_rr_peer(pc, &hp->rrp);
184e18a033bSKonstantin Ananyev    }
185e18a033bSKonstantin Ananyev
186e18a033bSKonstantin Ananyev    now = ngx_time();
187e18a033bSKonstantin Ananyev
188e18a033bSKonstantin Ananyev    pc->cached = 0;
189e18a033bSKonstantin Ananyev    pc->connection = NULL;
190e18a033bSKonstantin Ananyev
191e18a033bSKonstantin Ananyev    for ( ;; ) {
192e18a033bSKonstantin Ananyev
193e18a033bSKonstantin Ananyev        /*
194e18a033bSKonstantin Ananyev         * Hash expression is compatible with Cache::Memcached:
195e18a033bSKonstantin Ananyev         * ((crc32([REHASH] KEY) >> 16) & 0x7fff) + PREV_HASH
196e18a033bSKonstantin Ananyev         * with REHASH omitted at the first iteration.
197e18a033bSKonstantin Ananyev         */
198e18a033bSKonstantin Ananyev
199e18a033bSKonstantin Ananyev        ngx_crc32_init(hash);
200e18a033bSKonstantin Ananyev
201e18a033bSKonstantin Ananyev        if (hp->rehash > 0) {
202e18a033bSKonstantin Ananyev            size = ngx_sprintf(buf, "%ui", hp->rehash) - buf;
203e18a033bSKonstantin Ananyev            ngx_crc32_update(&hash, buf, size);
204e18a033bSKonstantin Ananyev        }
205e18a033bSKonstantin Ananyev
206e18a033bSKonstantin Ananyev        ngx_crc32_update(&hash, hp->key.data, hp->key.len);
207e18a033bSKonstantin Ananyev        ngx_crc32_final(hash);
208e18a033bSKonstantin Ananyev
209e18a033bSKonstantin Ananyev        hash = (hash >> 16) & 0x7fff;
210e18a033bSKonstantin Ananyev
211e18a033bSKonstantin Ananyev        hp->hash += hash;
212e18a033bSKonstantin Ananyev        hp->rehash++;
213e18a033bSKonstantin Ananyev
214e18a033bSKonstantin Ananyev        w = hp->hash % hp->rrp.peers->total_weight;
215e18a033bSKonstantin Ananyev        peer = hp->rrp.peers->peer;
216e18a033bSKonstantin Ananyev        p = 0;
217e18a033bSKonstantin Ananyev
218e18a033bSKonstantin Ananyev        while (w >= peer->weight) {
219e18a033bSKonstantin Ananyev            w -= peer->weight;
220e18a033bSKonstantin Ananyev            peer = peer->next;
221e18a033bSKonstantin Ananyev            p++;
222e18a033bSKonstantin Ananyev        }
223e18a033bSKonstantin Ananyev
224e18a033bSKonstantin Ananyev        n = p / (8 * sizeof(uintptr_t));
225e18a033bSKonstantin Ananyev        m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
226e18a033bSKonstantin Ananyev
227e18a033bSKonstantin Ananyev        if (hp->rrp.tried[n] & m) {
228e18a033bSKonstantin Ananyev            goto next;
229e18a033bSKonstantin Ananyev        }
230e18a033bSKonstantin Ananyev
231e18a033bSKonstantin Ananyev        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
232e18a033bSKonstantin Ananyev                       "get hash peer, value:%uD, peer:%ui", hp->hash, p);
233e18a033bSKonstantin Ananyev
234e18a033bSKonstantin Ananyev        if (peer->down) {
235e18a033bSKonstantin Ananyev            goto next;
236e18a033bSKonstantin Ananyev        }
237e18a033bSKonstantin Ananyev
238e18a033bSKonstantin Ananyev        if (peer->max_fails
239e18a033bSKonstantin Ananyev            && peer->fails >= peer->max_fails
240e18a033bSKonstantin Ananyev            && now - peer->checked <= peer->fail_timeout)
241e18a033bSKonstantin Ananyev        {
242e18a033bSKonstantin Ananyev            goto next;
243e18a033bSKonstantin Ananyev        }
244e18a033bSKonstantin Ananyev
245e18a033bSKonstantin Ananyev        if (peer->max_conns && peer->conns >= peer->max_conns) {
246e18a033bSKonstantin Ananyev            goto next;
247e18a033bSKonstantin Ananyev        }
248e18a033bSKonstantin Ananyev
249e18a033bSKonstantin Ananyev        break;
250e18a033bSKonstantin Ananyev
251e18a033bSKonstantin Ananyev    next:
252e18a033bSKonstantin Ananyev
253e18a033bSKonstantin Ananyev        if (++hp->tries > 20) {
254e18a033bSKonstantin Ananyev            ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
255e18a033bSKonstantin Ananyev            return hp->get_rr_peer(pc, &hp->rrp);
256e18a033bSKonstantin Ananyev        }
257e18a033bSKonstantin Ananyev    }
258e18a033bSKonstantin Ananyev
259e18a033bSKonstantin Ananyev    hp->rrp.current = peer;
260e18a033bSKonstantin Ananyev
261e18a033bSKonstantin Ananyev    pc->sockaddr = peer->sockaddr;
262e18a033bSKonstantin Ananyev    pc->socklen = peer->socklen;
263e18a033bSKonstantin Ananyev    pc->name = &peer->name;
264e18a033bSKonstantin Ananyev
265e18a033bSKonstantin Ananyev    peer->conns++;
266e18a033bSKonstantin Ananyev
267e18a033bSKonstantin Ananyev    if (now - peer->checked > peer->fail_timeout) {
268e18a033bSKonstantin Ananyev        peer->checked = now;
269e18a033bSKonstantin Ananyev    }
270e18a033bSKonstantin Ananyev
271e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
272e18a033bSKonstantin Ananyev
273e18a033bSKonstantin Ananyev    hp->rrp.tried[n] |= m;
274e18a033bSKonstantin Ananyev
275e18a033bSKonstantin Ananyev    return NGX_OK;
276e18a033bSKonstantin Ananyev}
277e18a033bSKonstantin Ananyev
278e18a033bSKonstantin Ananyev
279e18a033bSKonstantin Ananyevstatic ngx_int_t
280e18a033bSKonstantin Ananyevngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
281e18a033bSKonstantin Ananyev{
282e18a033bSKonstantin Ananyev    u_char                             *host, *port, c;
283e18a033bSKonstantin Ananyev    size_t                              host_len, port_len, size;
284e18a033bSKonstantin Ananyev    uint32_t                            hash, base_hash;
285e18a033bSKonstantin Ananyev    ngx_str_t                          *server;
286e18a033bSKonstantin Ananyev    ngx_uint_t                          npoints, i, j;
287e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peer_t        *peer;
288e18a033bSKonstantin Ananyev    ngx_http_upstream_rr_peers_t       *peers;
289e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_points_t   *points;
290e18a033bSKonstantin Ananyev    ngx_http_upstream_hash_srv_conf_t  *hcf;
291e18a033bSKonstantin Ananyev    union {
292e18a033bSKonstantin Ananyev        uint32_t                        value;
293e18a033bSKonstantin Ananyev        u_char                          byte[4];
294e18a033bSKonstantin Ananyev    } prev_hash;
295e18a033bSKonstantin Ananyev
296e18a033bSKonstantin Ananyev    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
297e18a033bSKonstantin Ananyev        return NGX_ERROR;
298e18a033bSKonstantin Ananyev    }
299e18a033bSKonstantin Ananyev
300e18a033bSKonstantin Ananyev    us->peer.init = ngx_http_upstream_init_chash_peer;
301e18a033bSKonstantin Ananyev
302e18a033bSKonstantin Ananyev    peers = us->peer.data;
303e18a033bSKonstantin Ananyev    npoints = peers->total_weight * 160;
304e18a033bSKonstantin Ananyev
305e18a033bSKonstantin Ananyev    size = sizeof(ngx_http_upstream_chash_points_t)
306e18a033bSKonstantin Ananyev           + sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);
307e18a033bSKonstantin Ananyev
308e18a033bSKonstantin Ananyev    points = ngx_palloc(cf->pool, size);
309e18a033bSKonstantin Ananyev    if (points == NULL) {
310e18a033bSKonstantin Ananyev        return NGX_ERROR;
311e18a033bSKonstantin Ananyev    }
312e18a033bSKonstantin Ananyev
313e18a033bSKonstantin Ananyev    points->number = 0;
314e18a033bSKonstantin Ananyev
315e18a033bSKonstantin Ananyev    for (peer = peers->peer; peer; peer = peer->next) {
316e18a033bSKonstantin Ananyev        server = &peer->server;
317e18a033bSKonstantin Ananyev
318e18a033bSKonstantin Ananyev        /*
319e18a033bSKonstantin Ananyev         * Hash expression is compatible with Cache::Memcached::Fast:
320e18a033bSKonstantin Ananyev         * crc32(HOST \0 PORT PREV_HASH).
321e18a033bSKonstantin Ananyev         */
322e18a033bSKonstantin Ananyev
323e18a033bSKonstantin Ananyev        if (server->len >= 5
324e18a033bSKonstantin Ananyev            && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
325e18a033bSKonstantin Ananyev        {
326e18a033bSKonstantin Ananyev            host = server->data + 5;
327e18a033bSKonstantin Ananyev            host_len = server->len - 5;
328e18a033bSKonstantin Ananyev            port = NULL;
329e18a033bSKonstantin Ananyev            port_len = 0;
330e18a033bSKonstantin Ananyev            goto done;
331e18a033bSKonstantin Ananyev        }
332e18a033bSKonstantin Ananyev
333e18a033bSKonstantin Ananyev        for (j = 0; j < server->len; j++) {
334e18a033bSKonstantin Ananyev            c = server->data[server->len - j - 1];
335e18a033bSKonstantin Ananyev
336e18a033bSKonstantin Ananyev            if (c == ':') {
337e18a033bSKonstantin Ananyev                host = server->data;
338e18a033bSKonstantin Ananyev                host_len = server->len - j - 1;
339e18a033bSKonstantin Ananyev                port = server->data + server->len - j;
340e18a033bSKonstantin Ananyev                port_len = j;
341e18a033bSKonstantin Ananyev                goto done;
342e18a033bSKonstantin Ananyev            }
343e18a033bSKonstantin Ananyev
344e18a033bSKonstantin Ananyev            if (c < '0' || c > '9') {
345e18a033bSKonstantin Ananyev                break;
346e18a033bSKonstantin Ananyev            }
347e18a033bSKonstantin Ananyev        }
348e18a033bSKonstantin Ananyev
349e18a033bSKonstantin Ananyev        host = server->data;
350e18a033bSKonstantin Ananyev        host_len = server->len;
351e18a033bSKonstantin Ananyev        port = NULL;
352e18a033bSKonstantin Ananyev        port_len = 0;
353e18a033bSKonstantin Ananyev
354e18a033bSKonstantin Ananyev    done:
355e18a033bSKonstantin Ananyev
356e18a033bSKonstantin Ananyev        ngx_crc32_init(base_hash);
357e18a033bSKonstantin Ananyev        ngx_crc32_update(&base_hash, host, host_len);
358e18a033bSKonstantin Ananyev        ngx_crc32_update(&base_hash, (u_char *) "", 1);
359e18a033bSKonstantin Ananyev        ngx_crc32_update(&base_hash, port, port_len);
360e18a033bSKonstantin Ananyev
361e18a033bSKonstantin Ananyev        prev_hash.value = 0;
362e18a033bSKonstantin Ananyev        npoints = peer->weight * 160;
363e18a033bSKonstantin Ananyev
364e18a033bSKonstantin Ananyev        for (j = 0; j < npoints; j++) {
365e18a033bSKonstantin Ananyev            hash = base_hash;
366e18a033bSKonstantin Ananyev
367e18a033bSKonstantin Ananyev            ngx_crc32_update(&hash, prev_hash.byte, 4);
368e18a033bSKonstantin Ananyev            ngx_crc32_final(hash);
369e18a033bSKonstantin Ananyev
370e18a033bSKonstantin Ananyev            points->point[points->number].hash = hash;
371e18a033bSKonstantin Ananyev            points->point[points->number].server = server;
372e18a033bSKonstantin Ananyev            points->number++;
373e18a033bSKonstantin Ananyev
374e18a033bSKonstantin Ananyev#if (NGX_HAVE_LITTLE_ENDIAN)
375e18a033bSKonstantin Ananyev            prev_hash.value = hash;
376e18a033bSKonstantin Ananyev#else
377e18a033bSKonstantin Ananyev            prev_hash.byte[0] = (u_char) (hash & 0xff);
378e18a033bSKonstantin Ananyev            prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);
379e18a033bSKonstantin Ananyev            prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);
380e18a033bSKonstantin Ananyev            prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);
381e18a033bSKonstantin Ananyev#endif
382e18a033bSKonstantin Ananyev        }
383e18a033bSKonstantin Ananyev    }
384e18a033bSKonstantin Ananyev
385e18a033bSKonstantin Ananyev    ngx_qsort(points->point,
386e18a033bSKonstantin Ananyev              points->number,
387e18a033bSKonstantin Ananyev              sizeof(ngx_http_upstream_chash_point_t),
388e18a033bSKonstantin Ananyev              ngx_http_upstream_chash_cmp_points);
389e18a033bSKonstantin Ananyev
390e18a033bSKonstantin Ananyev    for (i = 0, j = 1; j < points->number; j++) {
391e18a033bSKonstantin Ananyev        if (points->point[i].hash != points->point[j].hash) {
392e18a033bSKonstantin Ananyev            points->point[++i] = points->point[j];
393e18a033bSKonstantin Ananyev        }
394e18a033bSKonstantin Ananyev    }
395e18a033bSKonstantin Ananyev
396e18a033bSKonstantin Ananyev    points->number = i + 1;
397e18a033bSKonstantin Ananyev
398e18a033bSKonstantin Ananyev    hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
399e18a033bSKonstantin Ananyev    hcf->points = points;
400e18a033bSKonstantin Ananyev
401e18a033bSKonstantin Ananyev    return NGX_OK;
402e18a033bSKonstantin Ananyev}
403e18a033bSKonstantin Ananyev
404e18a033bSKonstantin Ananyev
405e18a033bSKonstantin Ananyevstatic int ngx_libc_cdecl
406e18a033bSKonstantin Ananyevngx_http_upstream_chash_cmp_points(const void *one, const void *two)
407e18a033bSKonstantin Ananyev{
408e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_point_t *first =
409e18a033bSKonstantin Ananyev                                       (ngx_http_upstream_chash_point_t *) one;
410e18a033bSKonstantin Ananyev    ngx_http_upstream_chash_point_t *second =
411e18a033bSKonstantin Ananyev                                       (ngx_http_upstream_chash_point_t *) two;
412e18a033bSKonstantin Ananyev
413e18a033bSKonstantin Ananyev    if (first->hash < second->hash) {
414e18a033b