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