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");