1 /**************************************************************************************************
2 $Id: sort.c,v 1.22 2006/01/18 20:46:47 bboy Exp $
3
4 Copyright (C) 2002-2005 Don Moore <bboy@bboy.net>
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at Your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 **************************************************************************************************/
20
21 #include "named.h"
22
23 /* Make this nonzero to enable debugging for this source file */
24 #define DEBUG_SORT 1
25
26 #define RR_IS_RR(R) ((R)->rrtype == DNS_RRTYPE_RR)
27 #define RR_IS_ADDR(R) (RR_IS_RR((R)) && (RR_IS_A((R)) || RR_IS_AAAA((R))))
28 #define RR_IS_A(R) (RR_IS_RR((R)) && (((MYDNS_RR *)(R)->rr)->type == DNS_QTYPE_A))
29 #define RR_IS_AAAA(R) (RR_IS_RR((R)) && (((MYDNS_RR *)(R)->rr)->type == DNS_QTYPE_AAAA))
30 #define RR_IS_MX(R) (RR_IS_RR((R)) && (((MYDNS_RR *)(R)->rr)->type == DNS_QTYPE_MX))
31 #define RR_IS_SRV(R) (RR_IS_RR((R)) && (((MYDNS_RR *)(R)->rr)->type == DNS_QTYPE_SRV))
32
33 #define RAND(x) ((uint32_t)(((double)(x) + 1.0) * rand() / (RAND_MAX)))
34
35
36 /**************************************************************************************************
37 SORTCMP
38 Comparison function; sorts records:
39 1. According to rr->sort_level
40 2. According to rr->sort1
41 3. According to rr->sort2
42 4. According to rr->id
43 **************************************************************************************************/
44 static int
sortcmp(RR * rr1,RR * rr2)45 sortcmp(RR *rr1, RR *rr2)
46 {
47 if (rr1->sort_level != rr2->sort_level)
48 return (rr1->sort_level - rr2->sort_level);
49
50 if (rr1->sort1 != rr2->sort1)
51 return (rr1->sort1 - rr2->sort1);
52
53 if (rr1->sort2 != rr2->sort2)
54 return (rr1->sort2 - rr2->sort2);
55
56 return (rr1->id - rr2->id);
57 }
58 /*--- sortcmp() ---------------------------------------------------------------------------------*/
59
60
61 /**************************************************************************************************
62 RRSORT
63 Sorts the contents of an RR list according to the value(s) in 'sort'
64 **************************************************************************************************/
65 static RR *
rrsort(RR * head,int (* compar)(RR *,RR *))66 rrsort(RR *head, int (*compar)(RR *, RR *))
67 {
68 RR *low, *high, *current, *pivot, *temp;
69 int result;
70
71 if (!head)
72 return (NULL);
73 current = head;
74 do
75 {
76 current = current->next;
77 if (!current)
78 return (head);
79 } while (!(result = compar(head,current)));
80
81 if (result > 0)
82 pivot = current;
83 else
84 pivot = head;
85 low = high = NULL;
86 current = head;
87 while (current)
88 {
89 temp = current->next;
90 if (compar(pivot,current) < 0)
91 {
92 current->next = high;
93 high = current;
94 }
95 else
96 {
97 current->next = low;
98 low = current;
99 }
100 current = temp;
101 }
102 low = rrsort(low, compar);
103 high = rrsort(high, compar);
104 current = temp = low;
105 while (1)
106 {
107 current = current->next;
108 if (!current)
109 break;
110 temp = current;
111 }
112 temp->next = high;
113 return low;
114 }
115 /*--- rrsort() ----------------------------------------------------------------------------------*/
116
117
118 /**************************************************************************************************
119 SORT_RRLIST
120 Sorts the specified RRLIST; reassigns tail node.
121 **************************************************************************************************/
122 static inline void
sort_rrlist(RRLIST * rrlist,int (* compar)(RR *,RR *))123 sort_rrlist(RRLIST *rrlist, int (*compar)(RR *, RR *))
124 {
125 register RR *node;
126
127 /* Do the sort */
128 rrlist->head = rrsort(rrlist->head, compar);
129
130 /* Redetermine list tail */
131 for (node = rrlist->head; node; node = node->next)
132 if (!node->next)
133 rrlist->tail = node;
134 }
135 /*--- sort_rrlist() -----------------------------------------------------------------------------*/
136
137
138 /**************************************************************************************************
139 LOAD_BALANCE
140 Use the 'aux' value to weight multiple A nodes.
141 **************************************************************************************************/
142 static inline void
load_balance(TASK * t,RRLIST * rrlist,datasection_t section,int sort_level)143 load_balance(TASK *t, RRLIST *rrlist, datasection_t section, int sort_level)
144 {
145 register RR *node; /* Current node */
146 register int order = 1; /* Current order */
147
148 #if DEBUG_ENABLED && DEBUG_SORT
149 Debug("%s: Load balancing A records in %s section", desctask(t), datasection_str[section]);
150 #endif
151
152 /* Hosts with 'aux' values > 50000 are always listed last */
153 for (node = rrlist->head; node; node = node->next)
154 if (RR_IS_ADDR(node) && node->sort_level == sort_level && !node->sort1)
155 if (((MYDNS_RR *)node->rr)->aux >= 50000)
156 node->sort1 = 50000;
157
158 for (;;)
159 {
160 register int found = 0; /* Number of records with this aux */
161 uint64_t weights = 0; /* Sum of aux */
162 register uint32_t rweight = 0; /* Random aux */
163
164 /* Compute the sum of the weights for all nodes where 'sort1' == 0 */
165 for (node = rrlist->head; node; node = node->next)
166 if (RR_IS_ADDR(node) && node->sort_level == sort_level && !node->sort1)
167 {
168 found++;
169 weights += ((MYDNS_RR *)node->rr)->aux;
170 }
171 if (!found)
172 break;
173
174 /* Set 'sort1' to 'order' for the first node found where the running sum
175 value is greater than or equal to 'rweight' */
176 rweight = RAND(weights);
177 for (weights = 0, node = rrlist->head; node; node = node->next)
178 if (RR_IS_ADDR(node) && node->sort_level == sort_level && !node->sort1)
179 {
180 weights += ((MYDNS_RR *)node->rr)->aux;
181 if (weights >= rweight)
182 {
183 node->sort1 = 65535 - order++;
184 break;
185 }
186 }
187 }
188 }
189 /*--- load_balance() ----------------------------------------------------------------------------*/
190
191
192 /**************************************************************************************************
193 _SORT_A_RECS
194 If the request is for 'A' or 'AAAA' and there are multiple A or AAAA records, sort them.
195 Since this is an A or AAAA record, the answer section contains only addresses.
196 If any of the RR's have nonzero "aux" values, do load balancing, else do round robin.
197 **************************************************************************************************/
198 static inline void
_sort_a_recs(TASK * t,RRLIST * rrlist,datasection_t section,int sort_level)199 _sort_a_recs(TASK *t, RRLIST *rrlist, datasection_t section, int sort_level)
200 {
201 register RR *node;
202 register int nonzero_aux = 0;
203 register int count = 0; /* Number of nodes at this level */
204
205 /* If any addresses have nonzero 'aux' values, do load balancing */
206 for (count = 0, node = rrlist->head; node; node = node->next)
207 if (RR_IS_ADDR(node) && node->sort_level == sort_level)
208 {
209 count++;
210 if (((MYDNS_RR *)node->rr)->aux)
211 nonzero_aux = 1;
212 }
213
214 if (count < 2) /* Only one node here, don't bother */
215 return;
216 t->reply_cache_ok = 0; /* Don't cache load-balanced replies */
217
218 if (nonzero_aux)
219 {
220 load_balance(t, rrlist, section, sort_level);
221 }
222 else /* Round robin - for address records, set 'sort' to a random number */
223 {
224 #if DEBUG_ENABLED && DEBUG_SORT
225 Debug("%s: Sorting A records in %s section (round robin)", desctask(t), datasection_str[section]);
226 #endif
227
228 for (node = rrlist->head; node; node = node->next)
229 if (RR_IS_ADDR(node) && node->sort_level == sort_level)
230 node->sort1 = RAND(4294967294U);
231 t->reply_cache_ok = 0; /* Don't cache load-balanced replies */
232 }
233 }
234 /*--- _sort_a_recs() ----------------------------------------------------------------------------*/
235
236
237 /**************************************************************************************************
238 SORT_A_RECS
239 If the request is for 'A' or 'AAAA' and there are multiple A or AAAA records, sort them.
240 Since this is an A or AAAA record, the answer section contains only addresses.
241 If any of the RR's have nonzero "aux" values, do load balancing, else do round robin.
242 **************************************************************************************************/
243 void
sort_a_recs(TASK * t,RRLIST * rrlist,datasection_t section)244 sort_a_recs(TASK *t, RRLIST *rrlist, datasection_t section)
245 {
246 register RR *node;
247
248 /* Sort each sort level */
249 for (node = rrlist->head; node; node = node->next)
250 if (RR_IS_ADDR(node) && !node->sort2)
251 _sort_a_recs(t, rrlist, section, node->sort_level);
252
253 return (sort_rrlist(rrlist, sortcmp));
254 }
255 /*--- sort_a_recs() -----------------------------------------------------------------------------*/
256
257
258 /**************************************************************************************************
259 SORT_MX_RECS
260 When there are multiple equal-preference MX records, randomize them to help keep the load
261 equal.
262 **************************************************************************************************/
263 void
sort_mx_recs(TASK * t,RRLIST * rrlist,datasection_t section)264 sort_mx_recs(TASK *t, RRLIST *rrlist, datasection_t section)
265 {
266 register RR *node;
267
268 #if DEBUG_ENABLED && DEBUG_SORT
269 Debug("%s: Sorting MX records in %s section", desctask(t), datasection_str[section]);
270 #endif
271
272 /* Set 'sort' to a random number */
273 for (node = rrlist->head; node; node = node->next)
274 if (RR_IS_MX(node))
275 {
276 node->sort1 = ((MYDNS_RR *)node->rr)->aux;
277 node->sort2 = RAND(4294967294U);
278 }
279 return (sort_rrlist(rrlist, sortcmp));
280 }
281 /*--- sort_mx_recs() ----------------------------------------------------------------------------*/
282
283
284 /**************************************************************************************************
285 SORT_SRV_PRIORITY
286 Sorts one record for a single specified priority.
287 After calling this function, 'sort2' should be 'weight' for the node affected.
288 Returns the number of nodes processed (0 means "done with this priority").
289 **************************************************************************************************/
290 static inline int
sort_srv_priority(TASK * t,RRLIST * rrlist,datasection_t section,uint32_t priority,int sort_level,int order)291 sort_srv_priority(TASK *t, RRLIST *rrlist, datasection_t section, uint32_t priority,
292 int sort_level, int order)
293 {
294 register RR *node; /* Current node */
295 register int found = 0; /* Number of records with this priority */
296 uint64_t weights = 0; /* Sum of weights */
297 register uint32_t rweight = 0; /* Random weight */
298
299 #if DEBUG_ENABLED && DEBUG_SORT
300 Debug("%s: Sorting SRV records in %s section with priority %u",
301 desctask(t), datasection_str[section], priority);
302 #endif
303
304 /* Compute the sum of the weights for all nodes with this priority where 'sort2' == 0 */
305 for (node = rrlist->head; node; node = node->next)
306 if (RR_IS_SRV(node) && node->sort_level == sort_level && node->sort1 == priority && !node->sort2)
307 {
308 found++;
309 weights += ((MYDNS_RR *)node->rr)->srv_weight;
310 }
311 if (!found)
312 return (0);
313
314 /* Set 'sort2' to 'order' for the first node found at this priority where the running sum
315 value is greater than or equal to 'rweight' */
316 rweight = RAND(weights+1);
317 for (weights = 0, node = rrlist->head; node; node = node->next)
318 if (RR_IS_SRV(node) && node->sort_level == sort_level
319 && node->sort1 == priority && !node->sort2)
320 {
321 weights += ((MYDNS_RR *)node->rr)->srv_weight;
322 if (weights >= rweight)
323 {
324 node->sort2 = order;
325 return (1);
326 }
327 }
328 return (1);
329 }
330 /*--- sort_srv_priority() -----------------------------------------------------------------------*/
331
332
333 /**************************************************************************************************
334 _SORT_SRV_RECS
335 Sorts SRV records at the specified sort level.
336 1. Sort by priority, lowest to highest.
337 2. Sort by weight; 0 means "almost never choose me", higher-than-zero yields
338 increased likelihood of being first.
339 **************************************************************************************************/
340 static inline void
_sort_srv_recs(TASK * t,RRLIST * rrlist,datasection_t section,int sort_level)341 _sort_srv_recs(TASK *t, RRLIST *rrlist, datasection_t section, int sort_level)
342 {
343 register RR *node; /* Current node */
344 register int count; /* Number of SRV nodes on this level */
345
346 #if DEBUG_ENABLED && DEBUG_SORT
347 Debug("%s: Sorting SRV records in %s section", desctask(t), datasection_str[section]);
348 #endif
349
350 /* Assign 'sort1' to the priority (aux) and 'sort2' to 0 if there's a zero weight, else random */
351 for (count = 0, node = rrlist->head; node; node = node->next)
352 if (RR_IS_SRV(node) && node->sort_level == sort_level)
353 {
354 count++;
355 node->sort1 = ((MYDNS_RR *)node->rr)->aux;
356 if (((MYDNS_RR *)node->rr)->srv_weight == 0)
357 node->sort2 = 0;
358 else
359 node->sort2 = RAND(4294967294U);
360 }
361
362 if (count < 2) /* Only one node here, don't bother */
363 return;
364 t->reply_cache_ok = 0; /* Don't cache these replies */
365
366 /* Sort a first time, so that the list is ordered by priority/weight */
367 sort_rrlist(rrlist, sortcmp);
368
369 /* Reset 'sort2' to zero for each SRV */
370 for (node = rrlist->head; node; node = node->next)
371 if (RR_IS_SRV(node) && node->sort_level == sort_level)
372 node->sort2 = 0;
373
374 /* For each unique priority, sort by weight */
375 for (node = rrlist->head; node; node = node->next)
376 if (RR_IS_SRV(node) && node->sort_level == sort_level && !node->sort2)
377 {
378 register int priority = node->sort1;
379 register int order = 1;
380
381 while (sort_srv_priority(t, rrlist, section, priority, sort_level, order++))
382 /* DONOTHING */;
383 }
384 }
385 /*--- _sort_srv_recs() --------------------------------------------------------------------------*/
386
387
388 /**************************************************************************************************
389 SORT_SRV_RECS
390 **************************************************************************************************/
391 void
sort_srv_recs(TASK * t,RRLIST * rrlist,datasection_t section)392 sort_srv_recs(TASK *t, RRLIST *rrlist, datasection_t section)
393 {
394 register RR *node; /* Current node */
395
396 /* Sort each sort level */
397 for (node = rrlist->head; node; )
398 {
399 /* _sort_srv_recs() will sort the list, so we need to reset the list each time */
400 if (RR_IS_SRV(node) && !node->sort2)
401 {
402 _sort_srv_recs(t, rrlist, section, node->sort_level);
403 node = rrlist->head;
404 }
405 else
406 node = node->next;
407 }
408 }
409 /*--- sort_srv_recs() ---------------------------------------------------------------------------*/
410
411 /* vi:set ts=3: */
412