1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
*
* Copyright 1998-2022 The OpenLDAP Foundation.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted only as authorized by the OpenLDAP
* Public License.
*
* A copy of this license is available in the file LICENSE in the
* top-level directory of the distribution or, alternatively, at
* <http://www.OpenLDAP.org/license.html>.
*/
#include "portable.h"
#include <ac/string.h>
#include "lload.h"
#include "lutil.h"
static LloadTierInit weighted_init;
static LloadTierBackendCb weighted_add_backend;
static LloadTierBackendCb weighted_remove_backend;
static LloadTierSelect weighted_select;
struct lload_tier_type weighted_tier;
/*
* Linear Congruential Generator - we don't need
* high quality randomness, and we don't want to
* interfere with anyone else's use of srand().
*
* The PRNG here cycles thru 941,955 numbers.
*/
static float weighted_seed;
static void
weighted_srand( int seed )
{
weighted_seed = (float)seed / (float)RAND_MAX;
}
static float
weighted_rand()
{
float val = 9821.0 * weighted_seed + .211327;
weighted_seed = val - (int)val;
return weighted_seed;
}
static void
weighted_shuffle( LloadBackend **b, int n )
{
int i, j, p;
uintptr_t total = 0, r;
for ( i = 0; i < n; i++ )
total += b[i]->b_weight;
/* all weights are zero, do a straight Fisher-Yates shuffle */
if ( !total ) {
while ( n ) {
LloadBackend *t;
i = weighted_rand() * n--;
t = b[n];
b[n] = b[i];
b[i] = t;
}
return;
}
/* Do a shuffle per RFC2782 Page 4 */
p = n;
for ( i = 0; i < n - 1; i++ ) {
r = weighted_rand() * total;
for ( j = 0; j < p; j++ ) {
r -= b[j]->b_weight;
if ( r <= 0 ) {
if ( j ) {
LloadBackend *t = b[0];
b[0] = b[j];
b[j] = t;
}
total -= b[0]->b_weight;
b++;
p--;
break;
}
}
/* TODO: once we have total == 0, should we jump over to the previous
* case? */
}
}
LloadTier *
weighted_init( void )
{
LloadTier *tier;
tier = ch_calloc( 1, sizeof(LloadTier) );
tier->t_type = weighted_tier;
ldap_pvt_thread_mutex_init( &tier->t_mutex );
LDAP_CIRCLEQ_INIT( &tier->t_backends );
weighted_srand( rand() );
return tier;
}
int
weighted_add_backend( LloadTier *tier, LloadBackend *to_add )
{
LloadBackend *b;
uintptr_t added = 1;
assert( to_add->b_tier == tier );
/* This requires us to use LDAP_CIRCLEQ_ENTRY_INIT() every time we have
* removed the backend from the list */
if ( LDAP_CIRCLEQ_NEXT( to_add, b_next ) ) {
added = 0;
LDAP_CIRCLEQ_REMOVE( &tier->t_backends, to_add, b_next );
}
/*
* Keep it sorted. The only thing RFC 2782 specifies is that weight 0
* entries are at the front of the list so they have a chance to be
* selected.
*
* Even with that in mind, there is a problem outlined in the RFC 2782
* errata[0] where the ordering affects the likelihood of an entry being
* selected with weight 0 entries in the mix - they are an afterthought
* into the design after all.
*
* [0]. https://www.rfc-editor.org/errata/eid2984
*/
LDAP_CIRCLEQ_FOREACH ( b, &tier->t_backends, b_next ) {
if ( to_add->b_weight < b->b_weight ) {
LDAP_CIRCLEQ_INSERT_BEFORE( &tier->t_backends, b, to_add, b_next );
goto done;
}
}
LDAP_CIRCLEQ_INSERT_TAIL( &tier->t_backends, to_add, b_next );
done:
tier->t_nbackends += added;
return LDAP_SUCCESS;
}
static int
weighted_remove_backend( LloadTier *tier, LloadBackend *b )
{
assert_locked( &tier->t_mutex );
assert_locked( &b->b_mutex );
assert( b->b_tier == tier );
assert( tier->t_nbackends );
LDAP_CIRCLEQ_REMOVE( &tier->t_backends, b, b_next );
LDAP_CIRCLEQ_ENTRY_INIT( b, b_next );
tier->t_nbackends--;
return LDAP_SUCCESS;
}
int
weighted_select(
LloadTier *tier,
LloadOperation *op,
LloadConnection **cp,
int *res,
char **message )
{
LloadBackend *b, **sorted;
int rc = 0, i = 0;
if ( !tier->t_nbackends ) return rc;
sorted = ch_malloc( tier->t_nbackends * sizeof(LloadBackend *) );
LDAP_CIRCLEQ_FOREACH ( b, &tier->t_backends, b_next ) {
sorted[i++] = b;
}
assert( i == tier->t_nbackends );
weighted_shuffle( sorted, tier->t_nbackends );
for ( i = 0; i < tier->t_nbackends; i++ ) {
int result;
checked_lock( &sorted[i]->b_mutex );
result = backend_select( sorted[i], op, cp, res, message );
checked_unlock( &sorted[i]->b_mutex );
rc |= result;
if ( result && *cp ) {
break;
}
}
ch_free( sorted );
return rc;
}
struct lload_tier_type weighted_tier = {
.tier_name = "weighted",
.tier_init = weighted_init,
.tier_startup = tier_startup,
.tier_reset = tier_reset,
.tier_destroy = tier_destroy,
.tier_oc = BER_BVC("olcBkLloadTierConfig"),
.tier_backend_oc = BER_BVC("olcBkLloadBackendConfig"),
.tier_add_backend = weighted_add_backend,
.tier_remove_backend = weighted_remove_backend,
.tier_select = weighted_select,
};
|
