Merge branch 'release' of git://git.kernel.org/pub/scm/linux/kernel/git/aegl/linux-2.6
[linux-2.6] / net / ipv4 / ipvs / ip_vs_lblcr.c
1 /*
2  * IPVS:        Locality-Based Least-Connection with Replication scheduler
3  *
4  * Version:     $Id: ip_vs_lblcr.c,v 1.11 2002/09/15 08:14:08 wensong Exp $
5  *
6  * Authors:     Wensong Zhang <wensong@gnuchina.org>
7  *
8  *              This program is free software; you can redistribute it and/or
9  *              modify it under the terms of the GNU General Public License
10  *              as published by the Free Software Foundation; either version
11  *              2 of the License, or (at your option) any later version.
12  *
13  * Changes:
14  *     Julian Anastasov        :    Added the missing (dest->weight>0)
15  *                                  condition in the ip_vs_dest_set_max.
16  *
17  */
18
19 /*
20  * The lblc/r algorithm is as follows (pseudo code):
21  *
22  *       if serverSet[dest_ip] is null then
23  *               n, serverSet[dest_ip] <- {weighted least-conn node};
24  *       else
25  *               n <- {least-conn (alive) node in serverSet[dest_ip]};
26  *               if (n is null) OR
27  *                  (n.conns>n.weight AND
28  *                   there is a node m with m.conns<m.weight/2) then
29  *                   n <- {weighted least-conn node};
30  *                   add n to serverSet[dest_ip];
31  *               if |serverSet[dest_ip]| > 1 AND
32  *                   now - serverSet[dest_ip].lastMod > T then
33  *                   m <- {most conn node in serverSet[dest_ip]};
34  *                   remove m from serverSet[dest_ip];
35  *       if serverSet[dest_ip] changed then
36  *               serverSet[dest_ip].lastMod <- now;
37  *
38  *       return n;
39  *
40  */
41
42 #include <linux/ip.h>
43 #include <linux/module.h>
44 #include <linux/kernel.h>
45 #include <linux/skbuff.h>
46
47 /* for sysctl */
48 #include <linux/fs.h>
49 #include <linux/sysctl.h>
50 /* for proc_net_create/proc_net_remove */
51 #include <linux/proc_fs.h>
52
53 #include <net/ip_vs.h>
54
55
56 /*
57  *    It is for garbage collection of stale IPVS lblcr entries,
58  *    when the table is full.
59  */
60 #define CHECK_EXPIRE_INTERVAL   (60*HZ)
61 #define ENTRY_TIMEOUT           (6*60*HZ)
62
63 /*
64  *    It is for full expiration check.
65  *    When there is no partial expiration check (garbage collection)
66  *    in a half hour, do a full expiration check to collect stale
67  *    entries that haven't been touched for a day.
68  */
69 #define COUNT_FOR_FULL_EXPIRATION   30
70 static int sysctl_ip_vs_lblcr_expiration = 24*60*60*HZ;
71
72
73 /*
74  *     for IPVS lblcr entry hash table
75  */
76 #ifndef CONFIG_IP_VS_LBLCR_TAB_BITS
77 #define CONFIG_IP_VS_LBLCR_TAB_BITS      10
78 #endif
79 #define IP_VS_LBLCR_TAB_BITS     CONFIG_IP_VS_LBLCR_TAB_BITS
80 #define IP_VS_LBLCR_TAB_SIZE     (1 << IP_VS_LBLCR_TAB_BITS)
81 #define IP_VS_LBLCR_TAB_MASK     (IP_VS_LBLCR_TAB_SIZE - 1)
82
83
84 /*
85  *      IPVS destination set structure and operations
86  */
87 struct ip_vs_dest_list {
88         struct ip_vs_dest_list  *next;          /* list link */
89         struct ip_vs_dest       *dest;          /* destination server */
90 };
91
92 struct ip_vs_dest_set {
93         atomic_t                size;           /* set size */
94         unsigned long           lastmod;        /* last modified time */
95         struct ip_vs_dest_list  *list;          /* destination list */
96         rwlock_t                lock;           /* lock for this list */
97 };
98
99
100 static struct ip_vs_dest_list *
101 ip_vs_dest_set_insert(struct ip_vs_dest_set *set, struct ip_vs_dest *dest)
102 {
103         struct ip_vs_dest_list *e;
104
105         for (e=set->list; e!=NULL; e=e->next) {
106                 if (e->dest == dest)
107                         /* already existed */
108                         return NULL;
109         }
110
111         e = kmalloc(sizeof(struct ip_vs_dest_list), GFP_ATOMIC);
112         if (e == NULL) {
113                 IP_VS_ERR("ip_vs_dest_set_insert(): no memory\n");
114                 return NULL;
115         }
116
117         atomic_inc(&dest->refcnt);
118         e->dest = dest;
119
120         /* link it to the list */
121         write_lock(&set->lock);
122         e->next = set->list;
123         set->list = e;
124         atomic_inc(&set->size);
125         write_unlock(&set->lock);
126
127         set->lastmod = jiffies;
128         return e;
129 }
130
131 static void
132 ip_vs_dest_set_erase(struct ip_vs_dest_set *set, struct ip_vs_dest *dest)
133 {
134         struct ip_vs_dest_list *e, **ep;
135
136         write_lock(&set->lock);
137         for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {
138                 if (e->dest == dest) {
139                         /* HIT */
140                         *ep = e->next;
141                         atomic_dec(&set->size);
142                         set->lastmod = jiffies;
143                         atomic_dec(&e->dest->refcnt);
144                         kfree(e);
145                         break;
146                 }
147                 ep = &e->next;
148         }
149         write_unlock(&set->lock);
150 }
151
152 static void ip_vs_dest_set_eraseall(struct ip_vs_dest_set *set)
153 {
154         struct ip_vs_dest_list *e, **ep;
155
156         write_lock(&set->lock);
157         for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {
158                 *ep = e->next;
159                 /*
160                  * We don't kfree dest because it is refered either
161                  * by its service or by the trash dest list.
162                  */
163                 atomic_dec(&e->dest->refcnt);
164                 kfree(e);
165         }
166         write_unlock(&set->lock);
167 }
168
169 /* get weighted least-connection node in the destination set */
170 static inline struct ip_vs_dest *ip_vs_dest_set_min(struct ip_vs_dest_set *set)
171 {
172         register struct ip_vs_dest_list *e;
173         struct ip_vs_dest *dest, *least;
174         int loh, doh;
175
176         if (set == NULL)
177                 return NULL;
178
179         read_lock(&set->lock);
180         /* select the first destination server, whose weight > 0 */
181         for (e=set->list; e!=NULL; e=e->next) {
182                 least = e->dest;
183                 if (least->flags & IP_VS_DEST_F_OVERLOAD)
184                         continue;
185
186                 if ((atomic_read(&least->weight) > 0)
187                     && (least->flags & IP_VS_DEST_F_AVAILABLE)) {
188                         loh = atomic_read(&least->activeconns) * 50
189                                 + atomic_read(&least->inactconns);
190                         goto nextstage;
191                 }
192         }
193         read_unlock(&set->lock);
194         return NULL;
195
196         /* find the destination with the weighted least load */
197   nextstage:
198         for (e=e->next; e!=NULL; e=e->next) {
199                 dest = e->dest;
200                 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
201                         continue;
202
203                 doh = atomic_read(&dest->activeconns) * 50
204                         + atomic_read(&dest->inactconns);
205                 if ((loh * atomic_read(&dest->weight) >
206                      doh * atomic_read(&least->weight))
207                     && (dest->flags & IP_VS_DEST_F_AVAILABLE)) {
208                         least = dest;
209                         loh = doh;
210                 }
211         }
212         read_unlock(&set->lock);
213
214         IP_VS_DBG(6, "ip_vs_dest_set_min: server %d.%d.%d.%d:%d "
215                   "activeconns %d refcnt %d weight %d overhead %d\n",
216                   NIPQUAD(least->addr), ntohs(least->port),
217                   atomic_read(&least->activeconns),
218                   atomic_read(&least->refcnt),
219                   atomic_read(&least->weight), loh);
220         return least;
221 }
222
223
224 /* get weighted most-connection node in the destination set */
225 static inline struct ip_vs_dest *ip_vs_dest_set_max(struct ip_vs_dest_set *set)
226 {
227         register struct ip_vs_dest_list *e;
228         struct ip_vs_dest *dest, *most;
229         int moh, doh;
230
231         if (set == NULL)
232                 return NULL;
233
234         read_lock(&set->lock);
235         /* select the first destination server, whose weight > 0 */
236         for (e=set->list; e!=NULL; e=e->next) {
237                 most = e->dest;
238                 if (atomic_read(&most->weight) > 0) {
239                         moh = atomic_read(&most->activeconns) * 50
240                                 + atomic_read(&most->inactconns);
241                         goto nextstage;
242                 }
243         }
244         read_unlock(&set->lock);
245         return NULL;
246
247         /* find the destination with the weighted most load */
248   nextstage:
249         for (e=e->next; e!=NULL; e=e->next) {
250                 dest = e->dest;
251                 doh = atomic_read(&dest->activeconns) * 50
252                         + atomic_read(&dest->inactconns);
253                 /* moh/mw < doh/dw ==> moh*dw < doh*mw, where mw,dw>0 */
254                 if ((moh * atomic_read(&dest->weight) <
255                      doh * atomic_read(&most->weight))
256                     && (atomic_read(&dest->weight) > 0)) {
257                         most = dest;
258                         moh = doh;
259                 }
260         }
261         read_unlock(&set->lock);
262
263         IP_VS_DBG(6, "ip_vs_dest_set_max: server %d.%d.%d.%d:%d "
264                   "activeconns %d refcnt %d weight %d overhead %d\n",
265                   NIPQUAD(most->addr), ntohs(most->port),
266                   atomic_read(&most->activeconns),
267                   atomic_read(&most->refcnt),
268                   atomic_read(&most->weight), moh);
269         return most;
270 }
271
272
273 /*
274  *      IPVS lblcr entry represents an association between destination
275  *      IP address and its destination server set
276  */
277 struct ip_vs_lblcr_entry {
278         struct list_head        list;
279         __u32                   addr;           /* destination IP address */
280         struct ip_vs_dest_set   set;            /* destination server set */
281         unsigned long           lastuse;        /* last used time */
282 };
283
284
285 /*
286  *      IPVS lblcr hash table
287  */
288 struct ip_vs_lblcr_table {
289         rwlock_t                lock;           /* lock for this table */
290         struct list_head        bucket[IP_VS_LBLCR_TAB_SIZE];  /* hash bucket */
291         atomic_t                entries;        /* number of entries */
292         int                     max_size;       /* maximum size of entries */
293         struct timer_list       periodic_timer; /* collect stale entries */
294         int                     rover;          /* rover for expire check */
295         int                     counter;        /* counter for no expire */
296 };
297
298
299 /*
300  *      IPVS LBLCR sysctl table
301  */
302
303 static ctl_table vs_vars_table[] = {
304         {
305                 .ctl_name       = NET_IPV4_VS_LBLCR_EXPIRE,
306                 .procname       = "lblcr_expiration",
307                 .data           = &sysctl_ip_vs_lblcr_expiration,
308                 .maxlen         = sizeof(int),
309                 .mode           = 0644, 
310                 .proc_handler   = &proc_dointvec_jiffies,
311         },
312         { .ctl_name = 0 }
313 };
314
315 static ctl_table vs_table[] = {
316         {
317                 .ctl_name       = NET_IPV4_VS,
318                 .procname       = "vs",
319                 .mode           = 0555,
320                 .child          = vs_vars_table
321         },
322         { .ctl_name = 0 }
323 };
324
325 static ctl_table ipvs_ipv4_table[] = {
326         {
327                 .ctl_name       = NET_IPV4,
328                 .procname       = "ipv4", 
329                 .mode           = 0555,
330                 .child          = vs_table
331         },
332         { .ctl_name = 0 }
333 };
334
335 static ctl_table lblcr_root_table[] = {
336         {
337                 .ctl_name       = CTL_NET,
338                 .procname       = "net", 
339                 .mode           = 0555, 
340                 .child          = ipvs_ipv4_table
341         },
342         { .ctl_name = 0 }
343 };
344
345 static struct ctl_table_header * sysctl_header;
346
347 /*
348  *      new/free a ip_vs_lblcr_entry, which is a mapping of a destination
349  *      IP address to a server.
350  */
351 static inline struct ip_vs_lblcr_entry *ip_vs_lblcr_new(__u32 daddr)
352 {
353         struct ip_vs_lblcr_entry *en;
354
355         en = kmalloc(sizeof(struct ip_vs_lblcr_entry), GFP_ATOMIC);
356         if (en == NULL) {
357                 IP_VS_ERR("ip_vs_lblcr_new(): no memory\n");
358                 return NULL;
359         }
360
361         INIT_LIST_HEAD(&en->list);
362         en->addr = daddr;
363
364         /* initilize its dest set */
365         atomic_set(&(en->set.size), 0);
366         en->set.list = NULL;
367         rwlock_init(&en->set.lock);
368
369         return en;
370 }
371
372
373 static inline void ip_vs_lblcr_free(struct ip_vs_lblcr_entry *en)
374 {
375         list_del(&en->list);
376         ip_vs_dest_set_eraseall(&en->set);
377         kfree(en);
378 }
379
380
381 /*
382  *      Returns hash value for IPVS LBLCR entry
383  */
384 static inline unsigned ip_vs_lblcr_hashkey(__u32 addr)
385 {
386         return (ntohl(addr)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;
387 }
388
389
390 /*
391  *      Hash an entry in the ip_vs_lblcr_table.
392  *      returns bool success.
393  */
394 static int
395 ip_vs_lblcr_hash(struct ip_vs_lblcr_table *tbl, struct ip_vs_lblcr_entry *en)
396 {
397         unsigned hash;
398
399         if (!list_empty(&en->list)) {
400                 IP_VS_ERR("ip_vs_lblcr_hash(): request for already hashed, "
401                           "called from %p\n", __builtin_return_address(0));
402                 return 0;
403         }
404
405         /*
406          *      Hash by destination IP address
407          */
408         hash = ip_vs_lblcr_hashkey(en->addr);
409
410         write_lock(&tbl->lock);
411         list_add(&en->list, &tbl->bucket[hash]);
412         atomic_inc(&tbl->entries);
413         write_unlock(&tbl->lock);
414
415         return 1;
416 }
417
418
419 /*
420  *  Get ip_vs_lblcr_entry associated with supplied parameters.
421  */
422 static inline struct ip_vs_lblcr_entry *
423 ip_vs_lblcr_get(struct ip_vs_lblcr_table *tbl, __u32 addr)
424 {
425         unsigned hash;
426         struct ip_vs_lblcr_entry *en;
427
428         hash = ip_vs_lblcr_hashkey(addr);
429
430         read_lock(&tbl->lock);
431
432         list_for_each_entry(en, &tbl->bucket[hash], list) {
433                 if (en->addr == addr) {
434                         /* HIT */
435                         read_unlock(&tbl->lock);
436                         return en;
437                 }
438         }
439
440         read_unlock(&tbl->lock);
441
442         return NULL;
443 }
444
445
446 /*
447  *      Flush all the entries of the specified table.
448  */
449 static void ip_vs_lblcr_flush(struct ip_vs_lblcr_table *tbl)
450 {
451         int i;
452         struct ip_vs_lblcr_entry *en, *nxt;
453
454         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
455                 write_lock(&tbl->lock);
456                 list_for_each_entry_safe(en, nxt, &tbl->bucket[i], list) {
457                         ip_vs_lblcr_free(en);
458                         atomic_dec(&tbl->entries);
459                 }
460                 write_unlock(&tbl->lock);
461         }
462 }
463
464
465 static inline void ip_vs_lblcr_full_check(struct ip_vs_lblcr_table *tbl)
466 {
467         unsigned long now = jiffies;
468         int i, j;
469         struct ip_vs_lblcr_entry *en, *nxt;
470
471         for (i=0, j=tbl->rover; i<IP_VS_LBLCR_TAB_SIZE; i++) {
472                 j = (j + 1) & IP_VS_LBLCR_TAB_MASK;
473
474                 write_lock(&tbl->lock);
475                 list_for_each_entry_safe(en, nxt, &tbl->bucket[j], list) {
476                         if (time_after(en->lastuse+sysctl_ip_vs_lblcr_expiration,
477                                        now))
478                                 continue;
479
480                         ip_vs_lblcr_free(en);
481                         atomic_dec(&tbl->entries);
482                 }
483                 write_unlock(&tbl->lock);
484         }
485         tbl->rover = j;
486 }
487
488
489 /*
490  *      Periodical timer handler for IPVS lblcr table
491  *      It is used to collect stale entries when the number of entries
492  *      exceeds the maximum size of the table.
493  *
494  *      Fixme: we probably need more complicated algorithm to collect
495  *             entries that have not been used for a long time even
496  *             if the number of entries doesn't exceed the maximum size
497  *             of the table.
498  *      The full expiration check is for this purpose now.
499  */
500 static void ip_vs_lblcr_check_expire(unsigned long data)
501 {
502         struct ip_vs_lblcr_table *tbl;
503         unsigned long now = jiffies;
504         int goal;
505         int i, j;
506         struct ip_vs_lblcr_entry *en, *nxt;
507
508         tbl = (struct ip_vs_lblcr_table *)data;
509
510         if ((tbl->counter % COUNT_FOR_FULL_EXPIRATION) == 0) {
511                 /* do full expiration check */
512                 ip_vs_lblcr_full_check(tbl);
513                 tbl->counter = 1;
514                 goto out;
515         }
516
517         if (atomic_read(&tbl->entries) <= tbl->max_size) {
518                 tbl->counter++;
519                 goto out;
520         }
521
522         goal = (atomic_read(&tbl->entries) - tbl->max_size)*4/3;
523         if (goal > tbl->max_size/2)
524                 goal = tbl->max_size/2;
525
526         for (i=0, j=tbl->rover; i<IP_VS_LBLCR_TAB_SIZE; i++) {
527                 j = (j + 1) & IP_VS_LBLCR_TAB_MASK;
528
529                 write_lock(&tbl->lock);
530                 list_for_each_entry_safe(en, nxt, &tbl->bucket[j], list) {
531                         if (time_before(now, en->lastuse+ENTRY_TIMEOUT))
532                                 continue;
533
534                         ip_vs_lblcr_free(en);
535                         atomic_dec(&tbl->entries);
536                         goal--;
537                 }
538                 write_unlock(&tbl->lock);
539                 if (goal <= 0)
540                         break;
541         }
542         tbl->rover = j;
543
544   out:
545         mod_timer(&tbl->periodic_timer, jiffies+CHECK_EXPIRE_INTERVAL);
546 }
547
548
549 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
550 static struct ip_vs_lblcr_table *lblcr_table_list;
551
552 /*
553  *      /proc/net/ip_vs_lblcr to display the mappings of
554  *                  destination IP address <==> its serverSet
555  */
556 static int
557 ip_vs_lblcr_getinfo(char *buffer, char **start, off_t offset, int length)
558 {
559         off_t pos=0, begin;
560         int len=0, size;
561         struct ip_vs_lblcr_table *tbl;
562         unsigned long now = jiffies;
563         int i;
564         struct ip_vs_lblcr_entry *en;
565
566         tbl = lblcr_table_list;
567
568         size = sprintf(buffer, "LastTime Dest IP address  Server set\n");
569         pos += size;
570         len += size;
571
572         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
573                 read_lock_bh(&tbl->lock);
574                 list_for_each_entry(en, &tbl->bucket[i], list) {
575                         char tbuf[16];
576                         struct ip_vs_dest_list *d;
577
578                         sprintf(tbuf, "%u.%u.%u.%u", NIPQUAD(en->addr));
579                         size = sprintf(buffer+len, "%8lu %-16s ",
580                                        now-en->lastuse, tbuf);
581
582                         read_lock(&en->set.lock);
583                         for (d=en->set.list; d!=NULL; d=d->next) {
584                                 size += sprintf(buffer+len+size,
585                                                 "%u.%u.%u.%u ",
586                                                 NIPQUAD(d->dest->addr));
587                         }
588                         read_unlock(&en->set.lock);
589                         size += sprintf(buffer+len+size, "\n");
590                         len += size;
591                         pos += size;
592                         if (pos <= offset)
593                                 len=0;
594                         if (pos >= offset+length) {
595                                 read_unlock_bh(&tbl->lock);
596                                 goto done;
597                         }
598                 }
599                 read_unlock_bh(&tbl->lock);
600         }
601
602   done:
603         begin = len - (pos - offset);
604         *start = buffer + begin;
605         len -= begin;
606         if(len>length)
607                 len = length;
608         return len;
609 }
610 #endif
611
612
613 static int ip_vs_lblcr_init_svc(struct ip_vs_service *svc)
614 {
615         int i;
616         struct ip_vs_lblcr_table *tbl;
617
618         /*
619          *    Allocate the ip_vs_lblcr_table for this service
620          */
621         tbl = kmalloc(sizeof(struct ip_vs_lblcr_table), GFP_ATOMIC);
622         if (tbl == NULL) {
623                 IP_VS_ERR("ip_vs_lblcr_init_svc(): no memory\n");
624                 return -ENOMEM;
625         }
626         svc->sched_data = tbl;
627         IP_VS_DBG(6, "LBLCR hash table (memory=%Zdbytes) allocated for "
628                   "current service\n",
629                   sizeof(struct ip_vs_lblcr_table));
630
631         /*
632          *    Initialize the hash buckets
633          */
634         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
635                 INIT_LIST_HEAD(&tbl->bucket[i]);
636         }
637         rwlock_init(&tbl->lock);
638         tbl->max_size = IP_VS_LBLCR_TAB_SIZE*16;
639         tbl->rover = 0;
640         tbl->counter = 1;
641
642         /*
643          *    Hook periodic timer for garbage collection
644          */
645         init_timer(&tbl->periodic_timer);
646         tbl->periodic_timer.data = (unsigned long)tbl;
647         tbl->periodic_timer.function = ip_vs_lblcr_check_expire;
648         tbl->periodic_timer.expires = jiffies+CHECK_EXPIRE_INTERVAL;
649         add_timer(&tbl->periodic_timer);
650
651 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
652         lblcr_table_list = tbl;
653 #endif
654         return 0;
655 }
656
657
658 static int ip_vs_lblcr_done_svc(struct ip_vs_service *svc)
659 {
660         struct ip_vs_lblcr_table *tbl = svc->sched_data;
661
662         /* remove periodic timer */
663         del_timer_sync(&tbl->periodic_timer);
664
665         /* got to clean up table entries here */
666         ip_vs_lblcr_flush(tbl);
667
668         /* release the table itself */
669         kfree(svc->sched_data);
670         IP_VS_DBG(6, "LBLCR hash table (memory=%Zdbytes) released\n",
671                   sizeof(struct ip_vs_lblcr_table));
672
673         return 0;
674 }
675
676
677 static int ip_vs_lblcr_update_svc(struct ip_vs_service *svc)
678 {
679         return 0;
680 }
681
682
683 static inline struct ip_vs_dest *
684 __ip_vs_wlc_schedule(struct ip_vs_service *svc, struct iphdr *iph)
685 {
686         struct ip_vs_dest *dest, *least;
687         int loh, doh;
688
689         /*
690          * We think the overhead of processing active connections is fifty
691          * times higher than that of inactive connections in average. (This
692          * fifty times might not be accurate, we will change it later.) We
693          * use the following formula to estimate the overhead:
694          *                dest->activeconns*50 + dest->inactconns
695          * and the load:
696          *                (dest overhead) / dest->weight
697          *
698          * Remember -- no floats in kernel mode!!!
699          * The comparison of h1*w2 > h2*w1 is equivalent to that of
700          *                h1/w1 > h2/w2
701          * if every weight is larger than zero.
702          *
703          * The server with weight=0 is quiesced and will not receive any
704          * new connection.
705          */
706         list_for_each_entry(dest, &svc->destinations, n_list) {
707                 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
708                         continue;
709
710                 if (atomic_read(&dest->weight) > 0) {
711                         least = dest;
712                         loh = atomic_read(&least->activeconns) * 50
713                                 + atomic_read(&least->inactconns);
714                         goto nextstage;
715                 }
716         }
717         return NULL;
718
719         /*
720          *    Find the destination with the least load.
721          */
722   nextstage:
723         list_for_each_entry_continue(dest, &svc->destinations, n_list) {
724                 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
725                         continue;
726
727                 doh = atomic_read(&dest->activeconns) * 50
728                         + atomic_read(&dest->inactconns);
729                 if (loh * atomic_read(&dest->weight) >
730                     doh * atomic_read(&least->weight)) {
731                         least = dest;
732                         loh = doh;
733                 }
734         }
735
736         IP_VS_DBG(6, "LBLCR: server %d.%d.%d.%d:%d "
737                   "activeconns %d refcnt %d weight %d overhead %d\n",
738                   NIPQUAD(least->addr), ntohs(least->port),
739                   atomic_read(&least->activeconns),
740                   atomic_read(&least->refcnt),
741                   atomic_read(&least->weight), loh);
742
743         return least;
744 }
745
746
747 /*
748  *   If this destination server is overloaded and there is a less loaded
749  *   server, then return true.
750  */
751 static inline int
752 is_overloaded(struct ip_vs_dest *dest, struct ip_vs_service *svc)
753 {
754         if (atomic_read(&dest->activeconns) > atomic_read(&dest->weight)) {
755                 struct ip_vs_dest *d;
756
757                 list_for_each_entry(d, &svc->destinations, n_list) {
758                         if (atomic_read(&d->activeconns)*2
759                             < atomic_read(&d->weight)) {
760                                 return 1;
761                         }
762                 }
763         }
764         return 0;
765 }
766
767
768 /*
769  *    Locality-Based (weighted) Least-Connection scheduling
770  */
771 static struct ip_vs_dest *
772 ip_vs_lblcr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
773 {
774         struct ip_vs_dest *dest;
775         struct ip_vs_lblcr_table *tbl;
776         struct ip_vs_lblcr_entry *en;
777         struct iphdr *iph = skb->nh.iph;
778
779         IP_VS_DBG(6, "ip_vs_lblcr_schedule(): Scheduling...\n");
780
781         tbl = (struct ip_vs_lblcr_table *)svc->sched_data;
782         en = ip_vs_lblcr_get(tbl, iph->daddr);
783         if (en == NULL) {
784                 dest = __ip_vs_wlc_schedule(svc, iph);
785                 if (dest == NULL) {
786                         IP_VS_DBG(1, "no destination available\n");
787                         return NULL;
788                 }
789                 en = ip_vs_lblcr_new(iph->daddr);
790                 if (en == NULL) {
791                         return NULL;
792                 }
793                 ip_vs_dest_set_insert(&en->set, dest);
794                 ip_vs_lblcr_hash(tbl, en);
795         } else {
796                 dest = ip_vs_dest_set_min(&en->set);
797                 if (!dest || is_overloaded(dest, svc)) {
798                         dest = __ip_vs_wlc_schedule(svc, iph);
799                         if (dest == NULL) {
800                                 IP_VS_DBG(1, "no destination available\n");
801                                 return NULL;
802                         }
803                         ip_vs_dest_set_insert(&en->set, dest);
804                 }
805                 if (atomic_read(&en->set.size) > 1 &&
806                     jiffies-en->set.lastmod > sysctl_ip_vs_lblcr_expiration) {
807                         struct ip_vs_dest *m;
808                         m = ip_vs_dest_set_max(&en->set);
809                         if (m)
810                                 ip_vs_dest_set_erase(&en->set, m);
811                 }
812         }
813         en->lastuse = jiffies;
814
815         IP_VS_DBG(6, "LBLCR: destination IP address %u.%u.%u.%u "
816                   "--> server %u.%u.%u.%u:%d\n",
817                   NIPQUAD(en->addr),
818                   NIPQUAD(dest->addr),
819                   ntohs(dest->port));
820
821         return dest;
822 }
823
824
825 /*
826  *      IPVS LBLCR Scheduler structure
827  */
828 static struct ip_vs_scheduler ip_vs_lblcr_scheduler =
829 {
830         .name =                 "lblcr",
831         .refcnt =               ATOMIC_INIT(0),
832         .module =               THIS_MODULE,
833         .init_service =         ip_vs_lblcr_init_svc,
834         .done_service =         ip_vs_lblcr_done_svc,
835         .update_service =       ip_vs_lblcr_update_svc,
836         .schedule =             ip_vs_lblcr_schedule,
837 };
838
839
840 static int __init ip_vs_lblcr_init(void)
841 {
842         INIT_LIST_HEAD(&ip_vs_lblcr_scheduler.n_list);
843         sysctl_header = register_sysctl_table(lblcr_root_table, 0);
844 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
845         proc_net_create("ip_vs_lblcr", 0, ip_vs_lblcr_getinfo);
846 #endif
847         return register_ip_vs_scheduler(&ip_vs_lblcr_scheduler);
848 }
849
850
851 static void __exit ip_vs_lblcr_cleanup(void)
852 {
853 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
854         proc_net_remove("ip_vs_lblcr");
855 #endif
856         unregister_sysctl_table(sysctl_header);
857         unregister_ip_vs_scheduler(&ip_vs_lblcr_scheduler);
858 }
859
860
861 module_init(ip_vs_lblcr_init);
862 module_exit(ip_vs_lblcr_cleanup);
863 MODULE_LICENSE("GPL");